2022-12-14

我们现在说的 PDP，一般指发表于 2007 年论文《Provable Data Possession at Untrusted Stores》里的 PDP，第一作者是 Giuseppe Ateniese。这篇论文之前，已经有一些文件证明的概念，比如 B-PDP，但是都没有做到，能够保证服务器端保存了文件。

S-PDP 是论文中首次提出的一种 scheme，可以用于客户端确认，某个文件确实被保存到了服务器环境上，这个服务器环境是不受信任的。

PDP 在解决的问题，就是我把一个文件保存到服务器上，不是说服务器告诉我它保存了，我就相信它真的保存了，我需要一种机制，确认文件真的在服务器上了。

PDP 也有很多种类型，有公开的、私有的、静态的、动态的。S-PDP 是比较基础的一种公开验证的 PDP。

同态加密是实现 S-PDP 的关键。

示例

我想举一个简单的例子来说明 S-PDP 的过程。因为论文中不着边的东西比较多，概括性的定义比较多，而且语焉不详，没有提供太具体的实现方式。我是按照自己的理解来解释。

现在客户端有一个原始的文件，内容是：

F = 12345

把这个文件分割成小的 block，比如分成 5 份：

F = [1, 2, 3, 4, 5]

在客户端这边生成一个随机数组成的数组 W，数组的长度和文件的 block 数量一致。W 的内容一定要是不可预测的：

W = [8, 1, 7, 3, 6]

生成同态加密标签分 2 步，首先，我们对 F 和 W 使用加法同态加密，接着，使用客户端公钥对同态加密后的数组，进行非对称加密：

T = r[ h(9),  h(3),  h(10),  h(7),  h(11)]
  =  [rh(9)) rh(3), rh(10), rh(7), rh(11)]

客户端将会把原始文件 F、同态加密标签 T 一起发送到服务端进行保存，客户端只保留本地生成的随机数组 W，W 是唯一私密不能泄漏的内容。客户端发送完毕后，就可以把本地的原始文件 F 和同态加密标签 T 都删掉了。

当客户端想要验证服务端的文件，由客户端生成一个挑战，比如随机验证第 1 个和第 3 个 block：

chal = [1, 3]

服务端在收到挑战后，生成证明也分 2 步，首先，使用客户端的公钥对原始文件 F 的第 1 个和第 3 个 block 进行非对称加密，接着，使用同态加密标签 T 去做减法同态加密：

V = [rh(9), rh(10)] - r[h(1),  h(3)]
  = [rh(9), rh(10)] - [rh(1), rh(3)]
  = [rh(8), rh(7)]

客户端拿到证明 V 后，使用私钥对证明进行非对称解密：

sW = r'[rh(8), rh(7)]
   =   [ h(8),  h(7)]

可以验证，证明经过解密后的 sW 正对应随机数组 W 第 1 个和第 3 个索引的值。由于同态加密的使用，整个过程中，W 的内容都没有泄漏。

用户只要手里有一开始生成的随机数组 W，在没有原始文件的情况下，就可以验证服务端的文件确实存在。这个随机数组 W 的数据占用是非常少的。而且过程中由于非对称加密的使用，服务端必须同时拥有同态加密标签 T 和原始文件 F，才能够完成挑战。因为 T 是公钥加密的，如果服务端作恶，客户端会解密不出来，服务端挑战失败。

局限性

在 PDP 的过程中，存在个问题：既然 V = T - F，如果服务端事先把整个 V 保存下来，即使删掉 T 和 F，也是可以通过挑战的，而且客户端并不会发现？

这是 PDP 的局限性，PDP 只能保证服务器至少保存了这个文件 1 次（如果一次都不保存，是不能生成 V 的），但是无法保证文件持续保存在服务器上，也无法反复验证证明的有效性。

假如第一次挑战是 [1, 3]，服务器通过了挑战并且保存了挑战为 [1, 3] 的证明，那么之后只要是 [1, 3] 的挑战，服务器都可以直接返回已经通过挑战的证明，而不需要对文件进行计算。客户端无法知晓，证明是立即生成的，还是早已生成的。这是所有 PDP 证明的局限性。