排序问题的安全多方计算协议

1、 唐春明等: 排序问题的安全多方计算协议 证明 显然, 为了保证在 3.1 小节所构造的协议的合理性, 根据计算阶段的第一步必须有 2t + 1 n, 而根据式 (3.2 必须有 2t < n, 因此 t (n 1/2. 为了证明在 3.1 小节所构造的协议是一个安全多方计算协议, 我们只需要证明该协议满足正确性 和秘密性. 1 正确性. 因为我们假设的攻击者是被动攻击者, 所以所有的参与者 (包括所有攻击者和诚实者 都是遵循协议的步骤. 因此, 我们只需要验证此协议是否能给秘密数据数组 s1 , s2 , . . . , sn 进行排序. 2t+1 由引理 1, 我们可以知道 si =

2、 r1 si + r2 s2 , 其中 1 i n. 而由定理 1, 我们知 i + · · · + r2t+1 si 道任意 t + 1 参与者都能计算所有的 si , i = 1, 2, . . . , n. 显然, s1 , s2 , . . . , sn 的排序就是 s1 , s2 , . . . , sn 的 正确排序. 也就是说, 我们能够得到 s1 , s2 , . . . , sn 的正确排序, 即正确性满足. 2 秘密性. 根据文献 13 中多方计算协议秘密性的定义, 如果协议满足下面的 (a 和 (b, 则协议 的秘密性成立: (a 每个 Pi

3、 观察到的信息串与等长的随机串具有相同的概率分布, 即 Pi 观察到的信息 串与等长的随机串不可区分, (b 任意 t (n 1/2 个参与者联合也不能得到任意其他参与者输入的 任何信息, 即任意 Pi1 , . . . , Pit 使用它们的 si1 , . . . , sit 和所有的输出, 也不可能得到 si / si1 , . . . , sit 的任何信息. 假设 Pi 是被动攻击者之一, 则它观察到的数据为: 输入阶段中 Pi 生成的数据串 fi1 (xj , fi2 (xj , . . . , fi2t+1 (xj , ri (xj , 1 它的数据串 fj1 (xi , fj2

4、 (xi , . . . , fj2t+1 (xi , 1 j n. j n, 其他参与者发送给 计算阶段中如果 Pi 是参与计算的 2t +1 个参与者之一, 则 Pi 生成的数据串为 hi1 (xj , hi2 (xj , . . . , hin (xj , 1 j n, 其他参与计算的 2t +1 个参与者 (包括它自己 发送给它的数据串为 hj 1 (xi , hj 2 (xi , . . . , hjn (xi , 1 j 2t + 1. 如果 Pi 不是参与计算的 2t + 1 个参与者之一, 则它没有生成任何数据串, 仅仅得到 2t + 1 个参与者发送给它的数据串为 hj 1

5、(xi , hj 2 (xi , . . . , hjn (xi , 1 j 2t + 1. 输出阶段中 Pi 所观察到的数据 yi , 1 i n. 所有的 2t + 1 个参与计算的参与者选择的多项式是随机的, 所以它们生成的所有串, 即随机多项 式上的点, 也是随机的. 因此, Pi 观察到的所有数据串与相同长的随机串具有同一样的概率, (a 满足. 如果 Shamir 的密钥共享方案中密钥 s 共享使用的多项式是 t 阶多项式, 则任意 t 个秘密分块是独 立的 16 , 也就是说, 对于任意 t 个随机串与任意的 s 都能唯一决定一个 t 阶多项式. 因为被动攻击者 的总数最多是 t

6、 个, 也就是说, 被动攻击者拥有在 3.1 小节的协议中每个随机多项式上的至多 t 个点, 因此对于任意被共享的 s, 被动攻击者都不能得到任意的信息. 另外, 假设我们的所有 s1 , s2 , . . . , sn 已 2t+1 经被构造出. 由 si = r1 si + r2 s2 , 1 i n, t 个被动参与者能得到 t 个方程组, 这 t 个 i + · · · + r2t+1 si 方程组中含有 t + 1 个未知数, 因此无法推出其他参与者的这 t + 1 个随机数, 从而也无法推出其他参与 者的秘密值, 即 t 个被动参与者使用它们的 si1

7、 , . . . , sit 和所有的输出, 也不可能得到 si / si1 , . . . , sit 的任何信息. 这样, (b 成立. 因此, 秘密性成立, 而且, 即使参与者计算能力无界, 秘密性依然成立 3.3 13 . 主动攻击情形下的排序问题的安全多方计算 在 3.1 小节中构造的协议中, 只有至多有 t (n 1/2 参与者是被动参与者的情形下, 协议才是 安全的, 否则, 参与者也许通过数据的替换或者终止协议的执行来进行欺骗. 为了防止类似的欺骗, 即 防止不诚实参与者的主动攻击, 我们不得不使用可验证的秘密共享方案和纠错码的理论 13 . 1 794 2t+1 显然, 在

8、3.1 小节中的安全多方计算协议主要是为了计算 si = r1 si + r2 s2 , 其中 i + · · · + r2t+1 si i n. 而这 n 个函数都是多项式可计算的函数, 根据文献 13 中的定理 3, 只要使用可验证秘密 中国科学 : 信息科学 第 41 卷 第 7 期 共享方案和纠错码原理, 我们能为任意的多项式可计算函数构造一个在主动攻击下的安全多方计算协 议. 该类协议有一个限制条件, 即主动攻击者控制的参与者数 t 必须满足 t < n/3. 因此, 我们有如下 的结论成立. 定理 3 若不诚实的参与者个数 t 与参与者总数 n

9、满足 t < n/3, 则对于 n 个参与者的排序问题 存在一个在主动攻击下完全安全的多方计算协议. 3.4 补充 在我们的排序协议中, 因为 1 t (n 1/2, 所以 n > 2. 强调的是, 在本文中我们考虑秘密值和随机数都是任意正有理数, 所有的计算都在有理数域中进 行. 若在整数或者有限域内取值和计算, 则本文中的协议用穷举法可被成功攻击, 任意 t 各不诚实参 与者可计算出其他参与者的秘密值. 事实上, 如果秘密数 s1 , s2 , . . . , sn 和随机数 r1 , r2 , . . . , r2t+1 都是正实数, 所有运行都在实数域中 进行, 则使用我们

10、的安全多方计算协议仍然能够实现秘密的排序. 4 排序问题的安全多方计算协议的一个实例 我们在这里例举 4 个秘密数据排序的例子. 由初始化阶段知 t = 1, 即至多只有一个参与者不诚 实. 4 个参与者分别记为 P1 , P2 , P3 , P4 , 他们拥有的秘密数据分别为 5, 15, 14, 8. 输入阶段: P1 随机独立选择 4 个 1 阶多项式: f11 (x = 5 + 2x, f12 (x = 52 + 12x, f13 (x = 53 + 10x, r1 (x = 4 + 7x; P2 随机独立选择 4 个 1 阶多项式: f21 (x = 15 + x, f22 (x =

11、 152 + 7x, f23 (x = 153 +6x, r2 (x = 6+9x; P3 随机独立选择 4 个一阶多项式: f31 (x = 14+8x, f32 (x = 142 +11x, f33 (x = 143 + 4x, r3 (x = 7 + 8x; P4 随机独立选择 4 个一阶多项式: f41 (x = 8 + 14x, f42 (x = 82 + 20x, f43 (x = 83 + 12x, r4 (x = 5 + 3x; 表 1 为 4 个参与者分发分享值的表格. 计算阶段: 4 个参与者共同选定 P1 , P2 , P4 , 那么 8/3 2 1/3 1 1 1 A

12、= 1 2 4 , A1 = . 1 4 16 P1 计算并选择 4 个 1 阶多项式 h11 (x, h12 (x, h13 (x, h14 (x 分别共享: 8 g1 (1 = 3 8 g2 (1 = 3 8 g3 (1 = 3 8 g4 (1 = 3 8 8 (11 × 7 + 15 × 37 + 8 × 135 = × 1712, 3 3 8 8 (11 × 16 + 15 × 232 + 8 × 3381 = × 30704, 3 3 8 8 (11 × 22 + 15 × 207 +

13、 8 × 2748 = × 25331, 3 3 8 8 (11 × 22 + 15 × 84 + 8 × 524 = × 5694; 3 3 同样 P2 计算并选择 4 个 1 阶多项式 h21 (x, h22 (x, h23 (x, h24 (x 分别共享: 2g1 (2 = 2 × 2933, 2g2 (2 = 2 × 43299, 795 唐春明等: 排序问题的安全多方计算协议 表1 4 个参与者分发分享值 All shares owned by four participants respectively

14、 in this example P1 P1 . P2 (2,9,(2,49, (2,145,(2,18 P2 (1,16,(1,232, (1,3381,(1,15 P3 (1,22,(1,207, (1,2748,(1,15 P4 (1,22,(1,84, (1,524,(1,8 (2,30,(2,218, (2,2752,(2,23 (2,36,(2,104, (2,536,(2,11 (3,50,(3,124, (2,536,(2,11 . P3 (3,11,(3,61, (3,155,(3,25 (3,18,(3,246, (3,3393,(3,33 . P4 (4,13,(4,73

15、, (4,165,(4,32 (4,19,(4,253, (4,3399,(4,42 (4,46,(4,240, (4,2760,(4,39 . Table 1 2g3 (2 = 2 × 36044, 2g4 (2 = 2 × 9040. P4 计算并选择 4 个 1 阶多项式 h41 (x, h42 (x, h43 (x, h44 (x 分别共享: 1 1 1 1 g1 (4 = × 6287, g2 (4 = × 69017, 3 3 3 3 1 1 1 1 g3 (4 = × 58472, g4 (4 = × 17616. 3

16、3 3 3 输出阶段: y1 = (y11 (1, y12 (1, y13 (1, y14 (1, y2 = (y21 (2, y22 (2, y23 (2, y24 (2, y3 = (y31 (3, y32 (3, y33 (3, y34 (3, y4 = (y41 (4, y42 (4, y43 (4, y44 (4, 其中, yij (i = hij (i + h2j (i + h4j (i, 1 i 4, 1 j 4. 排序的实现: 4 个参与者中任意 2 个参与者可以计算出 8 g1 (1 2g1 (2 + 3 8 g3 (1 2g3 (2 + 3 1 8 1 g1 (4 = 79

17、5, g2 (1 2g2 (2 + g2 (4 = 18285, 3 3 3 1 8 1 g3 (4 = 14952, g4 (1 2g4 (2 + g4 (4 = 2976. 3 3 3 参与者广播 (P1 , 795, (P2 , 18285, (P3 , 14952, (P4 , 2976. 任何人都可以对其进行排序, 显然 (P2 , 18285 > (P3 , 14952 > (P4 , 2976 > (P1 , 795. 对照前面的秘密值 5, 15, 14, 8, 知道执行协议 得到了正确的排序. 5 结论 关于排序问题的安全多方计算协议构造一直是密码学领域中一

18、个难解的问题. 本文使用秘密共享 方案为排序问题构造了一个有效的安全多方计算协议, 不仅在理论上还是在应用上都具有重要的价值. 796 中国科学 : 信息科学 第 41 卷 第 7 期 参考文献 1 Yao A C. Protocols for secure computations. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982. 160164 2 Fagin R, Naor M, Winkler P. Comparing information witho

19、ut leaking it. Commun ACM, 1996, 39: 7785 3 Schoenmakers B, Tuyls P. Practical two-party computation based on the conditional gate. In: Proceedings of Advances in Cryptology-ASIACRYPT 04 LNCS 3329. Berlin/Heidelberg: Springer-Verlag, 2004. 119136 4 Qin J, Zhang Z F, Feng D G, et al. A protocol of co

20、mparing information without leaking. J Softw, 2004, 15: 421427 5 Blake I F, Kolesnikov V. Strong condition oblivious transfer and computing on intervals. In: Proceedings of Advances in Cryptology-ASIACRYPT04. LNCS 3329. Berlin/Heidelberg: Springer-Verlag, 2004. 515529 6 Ioannidis I, Grama A. An ecie

21、nt protocol for Yaos millionaires problem. In: Proceedings of the 36th Hawaii International Conference on System Sciences, 2003 7 Fischlin M. A cost-eective pay-per-multiplication comparison method for millionaires. In: Progress on CryptologyCT-RSA 2001: the Cryptographers Track at RSA Conference 20

22、01 San Francisco, 2001. 457472 8 Lin H Y, Tzeng W G. An ecient solution to the millionaires problem based on hormomorphic encryption. In: ASIACRYPT 2005. LNCS 3531. Berlin/Heidelberg: Springer-Verlag, 2005. 456466 9 Cachin C. Ecient private bidding and auctions with an oblivious third party. In: Pro

23、ceedings of the 6th ACM Conference on Computer and Communications Security, 1999. 120127 10 Luo Y L. Key issues and application of secure multiparty computation. PhD Dissertation Hefei: Chinese University of Science and Technology, 2005 11 Lindell Y, Pinkas B. A proof of yaos protocol for secure two

24、-party computation. J Cryptol, 2009, 22: 161188 12 Goldreich O, Micali S, Wigderson A. How to play any mental gamea completeness theorem for protocols with honest majority. In: Proceedings of the 19th ACM Symposium on Theory of Computing, 1987. 218229 13 Ben-Or M, Goldwasser S, Wigderson A. Complete

25、ness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the 20th ACM Symposium on Theory of Computing, 1988. 110 14 Chaum D, Crepeau C, Damgard I. Multi-party unconditionally secure protocols. In: Proceedings of the 20th ACM Symposium on Theory of Computing, 19

26、88. 1119 15 Cramer R, Damgard I, Maurer U. General secure multi-party computation from linear secret sharing scheme. In: Advances in Crypto-EUROCRYPT 2000. LNCS 1807. Berlin/Heidelberg: Springer-Verlag, 2000. 316334 16 Shamir A. How to share a secret. Commun ACM, 1979 22: 612613 Secure multi-party computation protocol for sequencing problem TANG ChunMing1,2 , SHI GuiHua1 & YAO ZhengAn3 1 School of Mathematics and Information Science, Guangzhou University, Guangzhou 51