A Proof of Security of Yao's Protocol for Two-Party Computation

被引:406
作者
Lindell, Yehuda [1 ,3 ]
Pinkas, Benny [2 ]
机构
[1] Bar Ilan Univ, Dept Comp Sci, IL-52900 Ramat Gan, Israel
[2] Univ Haifa, Dept Comp Sci, IL-31905 Haifa, Israel
[3] IBM TJ Watson Res, New York, NY USA
关键词
Secure two-party computation; Semi-honest adversaries; Yao's two-party protocol; Proofs of security;
D O I
10.1007/s00145-008-9036-8
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In the mid 1980s, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao's protocol, along with a rigorous proof of security. Despite the importance of Yao's protocol to the theory of cryptography and in particular to the field of secure computation, to the best of our knowledge, this is the first time that an explicit proof of security has been published.
引用
收藏
页码:161 / 188
页数:28
相关论文
共 15 条
[1]  
Beaver D., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P479, DOI 10.1145/237814.237996
[2]  
BEAVER D, 1992, LECT NOTES COMPUT SC, V576, P377
[3]  
BEAVER D, 1990, PROCEEDINGS OF THE TWENTY SECOND ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, P503, DOI 10.1145/100216.100287
[4]   Security and composition of multiparty cryptographic protocols [J].
Canetti, R .
JOURNAL OF CRYPTOLOGY, 2000, 13 (01) :143-202
[5]  
Dwork C, 2004, LECT NOTES COMPUT SC, V3027, P342
[6]   A RANDOMIZED PROTOCOL FOR SIGNING CONTRACTS [J].
EVEN, S ;
GOLDREICH, O ;
LEMPEL, A .
COMMUNICATIONS OF THE ACM, 1985, 28 (06) :637-647
[7]   HOW TO CONSTRUCT RANDOM FUNCTIONS [J].
GOLDREICH, O ;
GOLDWASSER, S ;
MICALI, S .
JOURNAL OF THE ACM, 1986, 33 (04) :792-807
[8]  
Goldreich O., 2004, FDN CRYPTOGRAPHY, V2
[9]  
GOLDWASSER S, 1991, LECT NOTES COMPUT SC, V537, P77
[10]  
Goldwasser Shafi, 1987, STOC, P218, DOI DOI 10.1145/28395.28420