赵海春等：基于索引-存根表的云存储数据完整性审计 495· 首先假设响应信息中包含g而不是山，同时，承诺 询，敌手对该问询的响应值是4,2，…，4，和σ.假 信息中包含的内容是而不是T,(1≤j≤s),因为 设期望的响应值为山，2，…，4和σ，通过方案的正 这些值之间分别是一一对应的. 确性，可知期望的响应值满足验证方程： 现存在一个挑战者和一个敌手A(即，恶意的 CSP).挑战者构造了一个模拟器S,它将为敌手 e(o,h) A模拟出该方案的整个环境.对于之前进行过 S问询的任何文件F,敌手A都可以与挑战者一起 6 执行Audite(的审计协议.在这些协议执行过程中， 因为挑战者中止了，所以我们知道σ≠σ并且 模拟器S扮演验证者的角色，而敌手A扮演证明 σ通过了验证方程： 者的角色：S(pk,sk,)=A. 对于某个文件F,如果敌手A能够以不可忽略的 e(o ,h 概率成功地伪造聚合签名c,导致σ≠ΠQσY,g, 且能够通过数据完整性审计验证，那么，模拟器可 7 以利用敌手A解决计算Diffie-Hellman困难问题. 可以观察到，如果对于每个方，都有4=，那 假设该模拟器的输入值为h,X=h,Y=P,其目标 么我们可以得到σ'=σ，这与我们上面的假设相矛 是输出hB 设H:0,1°→G为一个哈希函数，将被建模为 盾.因此，如果我们定义兽4-4,1≤j≤s,那 么一定是集合{△如中至少有一个值是非零的.设 一个随机预言机.模拟器将对随机预言机H进行 编程.当回答敌手A的问询时，模拟器随机选择 o'=Π.eQo片，4=∑e0m,用等式(7)除以 r仁Zp,并用H∈G作为响应值，当回答形如H(m)的 等式(6)，我们得到 问询时，模拟器以下面描述的特殊方式对预言机 e(()n(y.h)=e(u)a.y) 进行编程 对于每个，1≤j≤3，模拟器选择随机值 ,8是Zp并设置山←(X9Wi.h9 对于每个i,1≤i≤n,模拟器选择一个随机值 厅？乙，并将值处的随机预言机编程为 H(m)=h1(Y)=1m (5) e(XP=ra4广y,-eh29y,Y） 接下来，模拟器计算： e((.(r= =(H(m) c(y. (8) h 因此，如果1△4≠0，我们找到了计算 Diffie-Hellman问题的解： h=(《c'y(c*yl(Yr4r4 (9) hri,h②=1mB= 其中，∑=1△等于零的情况除外.然而，我们 (X)r.(Y)=m 已经了解到，并非所有{△都等于零.此外，{ 值在理论上是对敌手隐藏的数据.因此，=旷 挑战者保存一份对敌手A提出的S问询的响 △4；=0的概率为1/p,是可以忽略不计的. 应列表.然后，挑战者观察与对手A执行的每一个 如前所述，我们知道σ'=σ.由等式(6)和(7) Audit(~)审计协议的实例，如果在任何一个实例中，敌 可以得到： 手是成功的（即，验证方程成立），但敌手的聚合签 名o'≠ΠeQy·g',则挑战者宣告失败并中止. e(o.h)=e(c,h) (10) 假设挑战值Q={(i,)是导致挑战者中止的问 通过代入μ和μ的值，我们得到g r ψ λj T j (1 ⩽ j ⩽ s) 首先假设响应信息中包含 而不是 ，同时，承诺 信息中包含的内容是 而不是 ， ，因为 这些值之间分别是一一对应的. St Audit(·) S(pk,sk,t) ⇌ A 现存在一个挑战者和一个敌手 A（即，恶意的 CSP）. 挑战者构造了一个模拟器 S，它将为敌手 A 模拟出该方案的整个环境. 对于之前进行过 问询的任何文件 F，敌手 A 都可以与挑战者一起 执行 的审计协议. 在这些协议执行过程中， 模拟器 S 扮演验证者的角色，而敌手 A 扮演证明 者的角色： . σ ′ σ ′ , ∏ (i,vi )∈Q σi vi ·γ · g r h,X = h α ,Y = h β h α·β 对于某个文件 F，如果敌手 A 能够以不可忽略的 概率成功地伪造聚合签名 ，导致 ， 且能够通过数据完整性审计验证，那么，模拟器可 以利用敌手 A 解决计算 Diffie-Hellman 困难问题. 假设该模拟器的输入值为 ，其目标 是输出 . H : {0,1} ∗ → G r R← Zp h r ∈ G H (mi) 设 为一个哈希函数，将被建模为 一个随机预言机. 模拟器将对随机预言机 H 进行 编程. 当回答敌手 A 的问询时，模拟器随机选择 ，并用 作为响应值，当回答形如 的 问询时，模拟器以下面描述的特殊方式对预言机 进行编程. j 1 ⩽ j ⩽ s ηj , θ j R← Zp uj ← (X) ηj · h θ j 对 于 每 个 , ， 模 拟 器 选 择 随 机 值 ，并设置 .. i 1 ⩽ i ⩽ n ri R← Zp i 对于每个 , ，模拟器选择一个随机值 ，并将 值处的随机预言机编程为 H (mi) = h ri/(Y) ∑s j=1 ηj ·mi j （5） 接下来，模拟器计算： σi = (H(mi))α ·   ∏s j=1 uj mi j   β =   h ri (Y) ∑s j=1 ηj ·mi j   α · ∏s j=1 ((X) ηj · h θ j ) mi j) β =   h ri (Y) ∑s j=1 ηj ·mi j   α · ( (X) ∑s j=1 ηj ·mi j · h ∑s j=1 θ j ·mi j)β = h α·ri · h ( ∑s j=1 θ j ·mi j)·β = (X) ri ·(Y) ∑s j=1 θ j ·mi j S t Audit(·) σ ′ , ∏ (i,vi )∈Q σi vi ·γ · g r 挑战者保存一份对敌手 A 提出的 问询的响 应列表. 然后，挑战者观察与对手 A 执行的每一个 审计协议的实例，如果在任何一个实例中，敌 手是成功的（即，验证方程成立），但敌手的聚合签 名 ，则挑战者宣告失败并中止. 假设挑战值 Q = {(i, vi)} 是导致挑战者中止的问 µ ′ 1 , µ ′ 2 ,··· , µ ′ s σ ′ µ1, µ2,··· , µs σ 询，敌手对该问询的响应值是 和 . 假 设期望的响应值为 和 ，通过方案的正 确性，可知期望的响应值满足验证方程： e (σ,h) ψ = e     ∏ (i,vi )∈Q (H (mi)) vi   γ ,X   · e   ∏s j=1 T j µj · uj −1 ,Y   （6） σ , σ ′ σ ′ 因为挑战者中止了，所以我们知道 并且 通过了验证方程： e ( σ ′ ,h ) ψ = e     ∏ (i,vi )∈Q (H (mi)) vi   γ ,X   · e   ∏s j=1 T j µj ′ · uj −1 ,Y   （7） µ ′ j = µj σ ′ = σ ∆µj def = µ ′ j −µj ,1 ⩽ j ⩽ s {∆µj} σ ∗ = ∏ (i,vi )∈Qσi vi µ ∗ j = ∑ (i,vi )∈Qvi ·mi j 可以观察到，如果对于每个 j，都有 ，那 么我们可以得到 ，这与我们上面的假设相矛 盾. 因此，如果我们定义 , 那 么一定是集合 中至少有一个值是非零的. 设 ， ，用等式（7）除以 等式（6），我们得到 e ( (σ ∗ ′ ) γ /(σ ∗ ) γ ,h ) = e( ∏s j=1 ( uj )γ·∆µj ∗ ,Y) = e   ∏s j=1 (X ηj · h θ j ) γ·∆µj ∗ ,Y   = e   ∏s j=1 (X) γ·ηj ·∆µj ∗ ,Y   · e   ∏s j=1 h γ·θ j ·∆µj ∗ ,Y   = e ((X) ∑s j=1 ηj ·∆µj ∗ ·γ ,Y)· e ( h ∑s j=1 θ j ·∆µj ∗ ·γ ,Y ) . e ( (σ ∗ ′ ) γ ·(σ ∗γ ) −1 ·(Y) −γ· ∑s j=1 θ j ·∆µj ∗ ,h ) = e (( (X) γ· ∑s j=1 ηj ·∆µj ∗ )β ,h ) （8） ∑s j=1 ηj 因此 ，如果 ·∆µj , 0 ，我们找到了计 算 Diffie-Hellman 问题的解： h αβ = ((σ ∗ ′ ) γ ·(σ ∗γ ) −1 ·(Y) −γ· ∑s j=1 θ j ·∆µj ∗ ) 1/(γ· ∑s j=1 ηj ·∆µj ∗ ) （9） ∑s j=1 ηj ·∆µj {∆µj ∗ } { ηj } ∑s j=1 ηj · ∆µj = 0 1/p 其中， 等于零的情况除外. 然而，我们 已经了解到，并非所有 都等于零. 此外， 值在理论上是对敌手隐藏的数据. 因此， 的概率为 ，是可以忽略不计的. σ ′ 如前所述，我们知道 = σ. 由等式（6）和（7） 可以得到： e (σ,h) = e ( σ ′ ,h ) （10） µ µ ′ 通过代入 和 的值，我们得到 赵海春等： 基于索引‒存根表的云存储数据完整性审计 · 495 ·