48 西安电子科技大学学报 ( 自然科学版 ) 第 43 卷本文使用随机置换方法, 提出了一个新的模指数批计算外包方案方案基于单个服务器, 同时实现了底数和指数的隐私性当服务器不诚实时, 外包用户能以接近于的概率检测到错误与同类方案相比, 本文方案仅需少量的预计算操作, 效率优于文献 [6-8]

Size: px

Start display at page:

Download "48 西安电子科技大学学报 ( 自然科学版 ) 第 43 卷本文使用随机置换方法, 提出了一个新的模指数批计算外包方案方案基于单个服务器, 同时实现了底数和指数的隐私性当服务器不诚实时, 外包用户能以接近于的概率检测到错误与同类方案相比, 本文方案仅需少量的预计算操作, 效率优于文献 [6-8]"

牛被樊
6 years ago
Views:

1 06 年 8 月西安电子科技大学学报 ( 自然科学版 ) Ag.06 第 43 卷第 4 期 JOURNAL OF XIDIAN UNIVERSITY Vol.43 No.4 do:0.3969/j.ssn 可验证模指数批计算外包方案黄春水, 任艳丽, 蔡建兴 ( 上海大学通信与信息工程学院, 上海 00444) 摘要 : 随着云计算的发展, 如何将一些耗时的计算任务安全地外包给不受信任的云服务器引起了人们的广泛关注目前的模指数运算外包方案大多基于两个不可信的服务器, 或者外包结果的可验证概率不高我们使用随机置换方法, 提出了一个新的模指数批计算外包方案模指数运算的底数和指数对于服务器都是保密的, 并且用户的可验证概率接近于与已有方案相比, 所提方案基于单个不可信服务器, 实现了输入数据的隐私性, 并提高了外包结果的可验证概率我们对所提方案进行了模拟实现, 测试结果表明外包方案极大地降低了用户的计算代价关键词 : 云计算 ; 外包方案 ; 可验证 ; 模指数运算中图分类号 : TP309 文献标识码 :A 文章编号 :00-400(06) Verfble otsorcng scheme for btch modlr eonenttons HUANG Chnsh,REN Ynl,CAI Jnng (School of Commncton nd Informton Eng., Shngh Unv., Shngh 00444, Chn) Abstrct: Wth the develoment of clod comtng, more nd more eole focs on how to otsorce the eensve comttons to the ntrsted clod servers. Crrentl, the otsorcng schemes for modlr eonenttons re mostl bsed on two ntrsted servers, or the checkblt s ver smll. We roose new otsorcng lgorthm for btch modlr eonenttons b sng the rndom ermtton. The eonent nd the bse re both rvte for the server, nd the otsorcer cn detect the error wth robblt close to. Comre wth the revos lgorthms, the roosed one s bsed on sngle server, whch relzes the rvc of nts nd ncreses the checkblt of otsorcng reslt. Fnll, we smlte the roosed lgorthm, nd the eerment reslt shows tht t cn gretl redce the comttonl cost for the otsorcer. Ke words: clod comtng; otsorcng lgorthm; verfble; modlr eonentton [] 随着云计算的兴起, 外包计算引起了人们广泛的关注通过外包计算, 计算能力有限的客户可以将任务外包给云服务器, 这将为那些资源受限的设备节省大量的计算时间同时, 外包计算也面临着许多挑战 [][3], 对安全性有很高的要求由于云服务器并不是完全可信的, 有可能存在泄露用户的信息, 或故意返回错误结果的情况可验证计算 [4] (Verfble Comtton,VC) 方案很好地解决了这个问题, 通过可验证计算方案, 用户的信息都是对服务器保密的, 并且服务器返回的任何错误结果都将不能通过验证 [5] 模指数运算是密码系统中最常见的最为耗时的运算之一, 许多公钥加密数字签名方案需要用到模指数运算, 研究如何实现模指数安全外包计算具有重要的现实意义 Hohenbergerd 等 [6] 定义了第一个外包计算安全模型, 并且基于两个不可信的服务器, 提出了单个模指数运算外包算 [7] 法 Chen 等提出了新的模指数运算外包方案, 在计算效率与可验证率方面都要优于 Hohenbergerd 尽管[6] 和 [7] 的方案实现了指数与底数的隐私性, 但它们都需要进行大量复杂的预计算操作, 效率不高并且遇到恶意的服务器时, 用户检测出错误的概率的也都不是很高,[6] 和 [8] [7] 的可验证率分别为 / /3 Wng 等提出了多个模指数相乘的外包计算方案, 与文献 [6-7] 比, [8] 只用了一个服务器, 也同时实现了指数与底数的隐私但是, 由于 [8] 的方案是针对多个模指数相乘的外包计算方案, 在单个模指数外包方面效率远低于文献 [6-7], 并且遇到恶意的服务器时, [9] 文献 [8] 的可验证率也仅有 / M 等提出了基于单个服务器的批量模指数外包方案, 与文献 [6-8] 比,[9] 的方案不需要复杂的预计算操作, 因此在批量外包计算模指数方面效率更高, 且可验证概率接近于但是,[9] 的方案在隐私性方面有明显的缺陷, 不能同时实现指数和底数的隐私性收稿日期 : 网络出版时间 : :46:3 基金项目 : 国家自然科学基金资助项目 ( 60367); 上海市自然科学基金资助项目 (ZR443700); 上海市教委创新基金资助项目 (4YZ00) 作者简介 : 黄春水 (99-), 男, 上海大学硕士研究生,E-ml: chnsh_h@63.com 网络出版地址 : htt://

2 48 西安电子科技大学学报 ( 自然科学版 ) 第 43 卷本文使用随机置换方法, 提出了一个新的模指数批计算外包方案方案基于单个服务器, 同时实现了底数和指数的隐私性当服务器不诚实时, 外包用户能以接近于的概率检测到错误与同类方案相比, 本文方案仅需少量的预计算操作, 效率优于文献 [6-8], 稍逊于文献 [9]但是与 [9] 相比, 我们的方案同时实现了指数和底数的隐私性, 安全性高于 [9] 本文方案在我们的方案中, 用到了一个被称为 Rnd [6] 的子程序, 用于产生随机数对 Rnd 子程序的输入是素数 q, 底数 q, 输出 (, g mod ), 其中 Z 目前, g Z, 且满足 q 实现这一 Rnd 子程序有两种方式第一种方式是预先使用一个可信任的服务器产生形如 ( g, mod ) 的随机数对组成表, 然后将这张表加载到客户端 T 的内存中去每次调用 Rnd 子程序,T 就从表中随机取出一个随机数对, 这种查方式因此被称为查表法另一种就是用 EBPV [0] 发生器产生独立的随机数对, 这种方式可以抵挡敌手自适应的攻击, 一个 n-bt 的指数运行的时间复杂度为 O(log n ). 可验证模指数计算方案可验证模指数计算方案是一个基于可信的客户端 T 与不可信的服务器端 U 的双方协议 T 提供底数和指数作为输入, 经盲化操作后, 再发送给 U 最后,U 返回计算结果和一个验证值用户利用服务器返回的验证值验证服务器返回的计算结果的正确性一般的可验证模指数计算方案都包含三个算法 : ( σ, σ) ProbGen(, τ, ) : 输入指数秘密输入 τ 和底数, 输出盲化后的指数 σ 和盲化后的底数 σ σ Comte( σ, σ ): 输入 σ 和 σ, 输出盲化后的模指数计算结果 σ {, } Verf( σ, τ ): 输入盲化后的模指数计算结果 σ, 完成正确性证明若验证结果正确, 输出计算结果 =, 否则输出. 可验证模指数批计算外包方案我们的可验证模指数批计算外包算法是在一个不可信的服务器上实现的输入 Z q( t), Z, 输出 (,,..., t ), 其中 q 是两个大素数, 且满足 q 本文的外包方案包含具体三个子算法如下所示 : 算法 : ProbGen((,,..., t ), τ, ) T 调用 Rnd 子程序, 产生 3 个随机数对 (, g α β α ),( β, g ),(, g ), 然后从 Z q 选取两个随机数 α β α β bb,, 定义 : τ = {( α, g ),( β, g ),(, g ), bb, }, v = g mod, μ = g mod, γ =g mod 然后, 客户端 T 利用秘密输入 τ 对底数与指数进行盲化处理首先对进行逻辑分割处理, 将分割为两个部分 : α β r r = ( vw) = g w = g g w = μ g w mod, 其中 Z, [, t], w= / v mod, r r = α β modq 然后, 分别对 g, w 进行盲化处理 r 对 g 部分的盲化处理设 mk = rk, k t 客户端 T 利用一个映射函数 π :[, n] [, n] 重新随机集合 D = ( r, r,..., rt, m, m,..., mt), 得到一个新的集合 D = ( d, d,..., d n ), 其中, n= t r 对 g 部分的盲化处理设 hk = k b, h k = k b, k t客户端 T 用一个映射函数 π :[, n] [, n] 重新随机集合 A = ( h, h,..., ht, h, h,..., h t), 得到一个新的集合 A = (,,..., n ), 其中, n= t 最后输出盲化后的指数 σ = { A, D} 和盲化后的底数 σ = { g, w} 我们将 ( σ, σ ) = {( D,g, ),( A, w, )} 发给服务器算法 : Comte( σ, σ ) q htt://

3 第 4 期黄春水等 : 可验证模指数批计算外包方案 49 U 利用 T 发过来 σ σ 的计算出结果 D, (,, ) σ, 并将它发回给客户端 A w,u 完成计算并返回对应的查询结果 : 利用 T 传过来的 (,g, ) d Ud (, g) g, U(,w) w, 其中 t d d dn n 最后得到 : σ = ( σ, σ ) {(g,g,...,g ),(,,..., )} = w w w 算法 3: Verf ( σ, τ ) T 接收到从服务器 U 传过来的 σ 集合后, 进行如下操作来验证 U 返回的计算结果的有效性 k )T 从 σ 中取出 g r mk, g, 其中, k t m 设 M j = σ, 如果满足 d = m π () j, 其中 j [, t] 那么有, g k = M k 设 R j = σ, 如果满足 d = r π () j, 其中 j [, t] 那么有, g rk = Rk hk h )T 从 σ 中取出 w, w k, 其中, k t 设 N 设 N = σ, 如果满足 h () j j j =, 其中 [, t] π h j 那么有, g = N h = σ, 如果满足 = h π () j, 其中 j [, t] 那么有, g = N k 3) 客户端 T 利用上面取出的 g r m, g k h, w k h, k r h w 计算出结果 = μη g. w, 并进行验证 : r h m h ηg. w = ηγg. w,(a) 如果对于所有的 [, t], 上面的验证等式 (A) 都成立, 那么输出 =, 否则输出方案分析本小节我们使用了与文献 [6-7] 相同的安全定义, 从理论上证明本文所提方案的正确性和安全性受篇幅限制, 相关安全定义不再给出具体安全定义和模型请参考 [6-7]. 正确性我们通过以下引理证明方案的正确性, 即只要服务器是诚实的, 通过以上我们的方案总能够得到正确的计算结果 = 且 (A) 成立引理如果服务器是诚实的, 则 = 且 (A) 成立证明 : 由于 m = r, =g mod 又因为 h = b, h = b, h+ b h + 所以 w = w = ηw, 因此有 g w g.( ηw ) γg. η w γ, 故有 r m + g = g = γ g m, b b η = w, η = w, η h b h w = w = w, = =,(B) r r h m h 由 (B) 可知, 只要服务器是诚实的, 则 (A) 成立 α β r r r h 又因为 = ( vw) = g w = g g w = μ g w mod, 所以 = = μη g. w 也成立. 安全性我们通过以下两个引理证明方案的安全性引理基于单个不可信服务器模型, 算法 ( T,U ) 是外包算法 BE 的 λ - 安全外包的实现其中, 输入 (,,..., t ;) 可能是可信任的秘密输入, 或是可信任的受保护的输入, 或是敌手的受保护的输入证明 : 首先, 我们证明 EVIEW : 如果输入 {( ;): t} 不是可信的秘密输入, rel del E 总能知道输入信息显然, 这种情况下模拟器 S 执行过程将与实际的环境相同因此, 我们只需考虑输入 {( ;): t} 是可信任的秘密输入的情况在理想的实验环境中, 模拟器 S 执行过程如下 : 当接收到第个输入时, S 忽略它们, 并向 U htt://

4 50 西安电子科技大学学报 ( 自然科学版 ) 第 43 卷提交 4t 个型如 ( j RZ q, g RZ ) 的查询操作然后, S 随机检测 t 个输出 : 如果有一个错误被检测出来, 输出 Y = " erro", Y =, nd = ; 如果没有错误被检测出来, S 继续检查其他 t 个输出 ; 如果所有的输出都通过检测, S 输出 = Y, Y =, nd = 0 否则, S 挑选 t 个随机数 z, z,..., zt R Z, 并输出 Y = ( z, z,..., z t ), Y =, nd = 在上面的所有情况中, 模拟器 S 都要保存它自己的所有状态 U 的输入分布在实际和理想的实验环境中在计算上都是不可区分的在理想实验环境中, 所有的输入都是随机选取的在实际实验环境中, 由于 T 在向 U 提交查询请求操作之前, 所有指数已经过一个映射函数加密扰乱, 因此两次查询操作的过程是独立随机的, 在计算上不可区分在第轮, 如果服务器 U 是可信的, 那么有 EVIEW rel del, 因为这意味着在实 U 际环境 T 正确的执行了 BE 算法, 并且模拟器 S 的输出结果与在理想环境中的结果完全相同如果在第轮服务器 U 是恶意的并且向 T 返回了错误的计算结果, 它将有 (4t ) 4t 的概率被 T 检测出来并输出 error 反之, 如果没有检测出来,T 就被成功欺骗, 输出这个错误结果在实际环境中, 由于 T 向服务器 U 提供的 4t 个输入是经过映射函数加密扰乱的, 对应的输出的 4t 个计算结果也是乱序的而在理想环境中, 模拟器 S 用 4t 个随机数代替了这些计算结果因此, 在服务器 U 是恶意的情况下, 仍然有 EVIEW rel del 成立综上所述, 无论服务器可信与否, 始终有 EVIEW rel del 成立接下来我们证明 UVIEWrel ~ UVIEW del 如果输入{( ;): t} 不是可信的秘密输入可信的受保护的输入和敌手的受保护的输入时, U 总能知道输入信息显然, 这种情况下模拟器 S 执行过程将与实际的环境相同因此, 我们只需考虑输入是可信的秘密输入可信的受保护的输入和敌手的受保护的输入时的情况在理想的实验环境中, 模拟器 S 执行过程如下 : 当接收到第个输入时, S 忽略它们, 并向 U 提交 4t 个型如 ( j RZ q, g RZ) 的查询操作, 然后保存自己和的所有状态类似的, 同上面证明 EVIEW rel del 的过程一样, U 的输入分布在实际和理想的实验环境中在计算上都是不可区分的因此, 尽管通过 nd 的值 E 能够很容易的区别真实环境和理想环境, 但是 E 不能把这一信息传递给 U 所以, 有 UVIEWrel ~ UVIEW del 成立引理 3 在单个服务器恶意模型中, 算法 ( T,U ) 是外包算法 BE 的 ( O((6t+ log n) nt ),(4t ) t 4, ) λ - 安全外包的实现证明 : 我们用平方乘算法计算一个模指数型如 mod, 大概需要.5n 次的模乘运算, 其中 n 表示指数的 bt 长度因此, 用平方乘算法直接计算 t 个指数大概需要进行.5nt 次模乘运算而用我们的 BE 算法计算 t 个指数, 需要次模逆运算,6t+ 次模乘运算另外, 还调用了三次 Rnd 子程序, 在. 小节我们提到过如果使用 EBPV 发生器来实现 Rnd 子程序, 那么一个 n-bt 的指数运行的时间复杂度为 O(log n ) 所以, 算法 BE 的时间复杂度为 O((6t + log n) nt) 在. 小节算法中, 用户 T 向服务器提交了两次查询操作, 每次计算的模指数长度为 t 这两次查询的结果影响着算法 3 的最终验证结果假设某次外包计算过程中 U 向 T 返回了一个错误的结果, 要想通过算法 3 的验证使用户 T 接受这个错误的结果,U 必须选取个合适的数字, 代替算法产生的两个结果集合中的某两个数但由于算法中两次查询操作在计算上是不可区分的, 并且查询操作前输入已经通过映射函数扰乱, 所以替换成功的概率为 4t 即 U 给 T 返回了一个错误的计算结果, 最终被 T 检测出来的概率为 (4t ) 4t ( 本文 3. 小节实验中 t 取的都是 000 以上, 可验证率接近于 ) 所以, 算法 BE 的可验证率 (4t ) 4t 综上所述, 我们说算法 ( T,U ) 是外包算法 BE 的 ( O((6t+ log n) nt),(4t ) 4 t, λ) - 安全外包的实现 htt://

5 第 4 期黄春水等 : 可验证模指数批计算外包方案 5 3 性能分析 3. 理论分析假设我们将 t 个底数相同指数不同的模指数外包给云服务器, 统计出在不同方案中, 客户 T 需要做的模乘运算次数模逆运算次数查询服务器的次数隐私性状况可验证率以及使用的服务器数量, 如表所示, 其中 m 表示方案 [4] 中选取的随机数个数,m>00 根据表, 同 [6][7] 相比, 本文在实现用户的指数底数都对服务器保密同时, 效率上有明显的提高所做的模乘运算模逆运算和查询服务器的次数都要少于 [6][7], 随着外包模指数数量增多 (t 越大 ), 这种效率的提升越明显并且, 本文只用了一个服务器, 可验证率也要高于 [6][7] [8] 虽然也只用了一个服务器并能够实现完全隐私, 但在效率和可验证率上都不及本文与 [9] 相比, 尽管 [9] 的可验证率和服务器个数都与本文相同, 甚至模乘运算模逆运算和查询服务器的次数比本文方案少, 效率方面比本文的略高但是,[9] 不能实现用户的指数底数同时对服务器保密, 安全性方面不如本文方案表模指数运算外包方案比较方案模乘模逆查询服务器隐私性可验证率服务器个数 [6] 7t 3t 6t 完全隐私 /3 [7] 9t 5t 8t 完全隐私 / [8] t 4t 6t 完全隐私 / [9] (m+t-) 0 t 部分隐私本文 6t+ t 完全隐私 3. 实验分析首先, 我们对本文方案进行实验, 统计出外包不同数量的模指数时, 用户端所需要的时间曲线图 ( 如图所示 ) 其中, 横坐标为要计算的模指数个数, 纵坐标为用户所用的时间, 时间单位是 ms 由图可知, 采用本文的外包方案, 用户通过外包方案计算出结果的时间远小于用户直接计算的时间并且, 随着待外包模指数个数的增多, 两者之间的时间差值越大, 本文方案在大批量模指数外包方面的高效率特性越突出图外包模指数方案实验结果图接着, 我们分别对文献 [7-9] 的外包方案进行实验, 我们一共测试了 9 组不同个数的模指数, 统计用户端所需要的时间如表所示表四种外包方案的计算时间方案 000 个 000 个 3000 个 4000 个 5000 个 6000 个 7000 个 8000 个 9000 个 [7] 87ms 68ms 44ms 39ms 40ms 480ms 54ms 63ms 78ms [8] 540ms 067ms 574ms 7ms 648ms 30ms 3644ms 499ms 470ms [9] 0ms 33 ms 49 ms 63 ms 85 ms 97 ms 09 ms ms 45ms 本文 6ms 6ms 43ms 70ms 8ms 343ms 397ms 46ms 503ms 根据表, 我们可以得出与 3. 小节相同的结论在外包的模指数个数相同的情况下,[8] 的时间明显高于其他三种方案, 这是由于 [8] 的方案主要是用于外包多个模指数乘法运算, 所以在单个模指数外包上效率很低本文方案的时间介于 [7][9] 之间, 这也和 3. 小节方案分析的结论吻合在外包的模指数个数相同情况下, 和 [7] 相比, 本文方案时间较少, 这说明本文方案效率高于 [7] 并且随外包的模指数个数增多,[7] 和本文方案的时间差值增大, 这意味着在实现大批量的模指数 htt://

6 5 西安电子科技大学学报 ( 自然科学版 ) 第 43 卷外包上, 我们方案效率的优势更明显为了实现户提供的指数底数都对服务器保密, 提高算法的安全性, 我们的方案做了少量的预计算操作我们牺牲用户少量时间换取了用户安全性的提高, 这就导致了我们方案的效率比 [9] 低 4 结束语本文基于单个不可信服务器, 提出了一种新的模指数批外包计算方案与目前已知的模指数外包方案相比, 我们的方案仅需付出少量的预计算操作代价, 便能够同时实现指数和底数的隐私性在数据隐私的前提下, 用户实现外包的效率高于其它算法另外, 外包结果的可验证概率较其他方案也有明显优势, 如果服务器不诚实, 用户检测出错误的概率接近于后续的改进工作是 : 在保证用户外包效率不降低的情况下, 尽可能降低服务器的工作量参考文献 [] Clovs Chmn, Wolfgng Emmerch, Fermn Gln Mrqez, et l. Softwre rchtectre defnton for on-demnd clod rovsonng [J]. Clster Comtng, 0, 5(): [] Ren K, Wng C, Wng Q. Secrt Chllenges for the Pblc Clod [J]. Internet Comtng IEEE, 0, 6(): [3] Mezgr I, Rschecker U. The chllenge of networked enterrses for clod comtng nteroerblt [J]. Comters n Indstr, 04, 65(4): [4] Gennro R, Gentr C, Prno B. Non-nterctve verfble comtng: otsorcng comtton to ntrsted workers[c]//the 30th Interntonl Crtolog Conference. Snt Brbr, USA: Srnger, 00: [5] 江明明, 胡予濮等. 格上的代理重签名方案 [J]. 西安电子科技大学学报, 04, 4(): 0-4. Jng Mngmng, H Y, et l. Pro re-sgntre scheme over the lttce [J]. Jornl of Xdn Unverst, 04, 4(): 0-4. [6] Hohenberger S, Lsnsk A. How to secrel otsorce crtogrhc comttons[c]//the nd Annl Theor of Crtogrh Conference. Msschsetts, USA: Srnger, 005: [7] Chen X, L J, M J, et l. New Algorthms for Secre Otsorcng of Modlr Eonenttons [J]. IEEE Trnsctons on Prllel nd Dstrbted Sstems, 04, 5(9), [8] Wng Y, W Q, Wong D S, et l. Secrel Otsorcng Eonenttons wth Sngle Untrsted Progrm for Clod Storge[C]//The 9th Eroen Smosm on Reserch n Comter Secrt, Comter Scence. Wroclw: Polnd: Srnger, 04: [9] M X, L J, Zhng F. Otsorcng comtton of modlr eonenttons n clod comtng [J]. Clster Comtng, 03, 6(4): [0] Ngen P Q, Shrlnsk I E, Stern J. Dstrbton of modlr sms nd the secrt of the server ded eonentton[c]//crtogrh nd Comttonl Nmber Theor. Bsel, Schwez: Brkhser, 00: htt://

标题

第 35 卷第期西南大学学报 ( 自然科学版 ) 3 年月 Vol.35 No. JouralofSouthwestUiversity (NaturalScieceEditio) Feb. 3 文章编号 :673 9868(3) 69 4 一类积分型 Meyer-KiḡZeler-Bzier 算子的点态逼近赵晓娣, 孙渭滨宁夏大学数学计算机学院, 银川 75 摘要 : 应用一阶 DitziaṉTotik