确保第三方存储数据的完整性和有效性

Question

我正在处理不受信任的外部存储，需要确保存储提供程序不会在查询中保留任何记录。

示例：

我有两个可信实体TA和TB，这些实体应该能够更改存储在云/不可信存储中的数据，但没有其他实体。因此，我的解决方案--我为TA和TB配备了公共密钥--并且我有一个数据结构，可以与有版本的表相比较，比如

 Ver | Data | Signature       | Signee
  4  |  ... | (AAAAAAAAA)_TA  | TA
  3  |  ... | (ZZZZZZZZZ)_TB  | TB
  2  |  ... | (YYYYYYYYY)_TA  | TA
  1  |  ... | (XXXXXXXXX)_TA  | TA

因此，当我从存储提供程序中检索这样的表时，我可以很容易地验证签名，并检查签名是否正确，是否允许收货人更改表。

然而，我也想检查记录的完整性。假设TA上传版本4，但TB只知道到版本3为止的所有记录。现在，当TB查询它时，存储提供商可能会完全保留版本4。

由于TA和TB之间没有直接的旁路机制，因此无法交换当前版本。有办法绕过这件事吗？

我正在考虑定期插入虚拟记录，以便至少有一定的时间确定性。但是，这种方法缺乏可伸缩性，将导致大量存储和签名开销。我正在寻找的实际系统属性是什么(很难找到对您不知道名称的东西的研究)？

Answer 1

如果没有虚拟记录，这个问题是无法完全解决的：

让我们在当前版本为版本3时调用状态，当当前版本为“状态4”时，调用状态。无论您如何对这些状态进行签名--只要攻击者告诉您"state 3是当前状态“(向您展示整个数据库，就像在状态3期间一样)，您就无法知道这是正确的还是状态4同时存在。

因此，您必须定期签署“无更改”更新。您将无法避免签名开销，但您不必存储所有这些。您可以创建一个单独的“最新更新”表：

 Signer | Last | Timestamp | Signature
  TA    |  4   | 2013-1... | (TA;4;2013-1...)_TA
  TB    |  3   | 2013-1... | (TB;3;2013-1...)_TB

意思是“签字人TA确认，在2013-1.，我发送的最后版本是4”。如果存储提供程序不能向您显示当前所有签名者都确认他们没有发布更新版本，那么您必须假设他隐藏了什么东西(或者什么东西坏了--不管怎样，数据并不是最新的)。任何新的已签名语句都会替换该签名者的旧语句，因为它们现在已经不相关了。

现在，如果您没有一个版本化的“东西”，但是有大量的版本，那么您不一定需要每个“东西”有一个这样的虚拟日志。例如，您可以通过签名者计算所有当前行的哈希(或哈希树)。“东西A，版本3。B，版本7。东西C，版本2。”)然后将散列或哈希树的根放到lastupdate表中。

如果您真的想避免额外的签名，而且有些东西总是会被更新，您可以在您签名的版本记录的签名中包含散列和时间戳--那么最新的签名记录就足以证明它是否新鲜，如果它太旧，您仍然可以使用"lastupdate“表。这不值得这么复杂，IMHO。

Answer 2

如果问题是关于记录完整性，我建议使用MAC (消息认证代码)。在这种情况下，您应该使用对称密钥加密，而且它比加密签名(不对称)高效得多。

我想到了两个方向：

1. 您可以减少您的问题，以记录完整性。如果您有要验证的特定重要数据，则可以在存储中创建特定表，以便在每个受信任实体更新每个重要变量时保存该表。重要的数据可以是:记录的数量(总记录数、新记录数、最新版本等)。当某人做了影响重要数据的更改时，他会更新空间表中的相关记录，并在记录上签名--记录中还包含上次更新的日期。现在，为了防止不受信任的存储返回旧记录或诸如此类的东西，每个受信任方必须至少每隔一段时间更新一次记录(例如，一天)--记录可能不会更改(只有记录中的日期)，并且标记将发生更改(现在标记在较晚的日期)。当实体读取信息时，他可以验证数据是真实的，并且最多在前一天(在示例中)是正确的。如果返回记录的日期早于一天，则不应考虑此日期。您可以根据需要更改定期更新的频率。对于这个选项，您可以使用MAC而不是签名(以提高效率)。
2. 您可以尝试另一种策略:无法验证每个更新的完整性，但如果不可信存储试图说谎，则可以尝试捕获它！您可以通过为它们调度更新和查询来做到这一点。

最后一件事-你写道：

由于TA和TB之间没有直接的旁路机制，因此无法交换当前版本。有办法绕过这件事吗？

我相信你是说沟通渠道。旁路是另一回事。如果是我，我会创造这样的沟通渠道来解决这个问题。顺便说一句，类似于我描述的第一个选项，您可以创建这样一个通道：

创建一个来自不同实体的消息表，在其中宣布他们所做的重要更改，并在其中签名更改日期：

实体_

与第一个选项一样，每个实体都必须每隔一段预定义的时间段添加一次这样的消息，并且实体之间有可信的通信通道。