Secure Multi-Party Proof and its Applications

Chunming Tang, Shuhong Gao

.

DOI: 10.4236/jsea.2010.37081                

Abstract

We define a new type cryptographical model called secure multi-party proof that allows any players and a verifier to securely compute a function : each of the players learns nothing about other players’ input and about the value of , and the verifier obtains the value of and it’s validity but learns nothing about the input of any of the players. It is implemented by a protocol using oblivious transfer and Yao’s scrambled circuit. We prove that our protocol is secure if the players and the verifier are semi-honest (i.e. they follow the protocol) and polynomial time bounded. The main applications of our protocol are for electronic voting and electronic bidding.

Keywords

Multi-Party Proof, Multi-Party Computation, Electronic Voting, Electronic Bidding

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. Yao, “Protocols for Secure Computation,” Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, Chicago, November 1982, pp. 160-164.
[2]	Y. Lindell and B. Pinkas, “A Proof of Yao’s Protocol for Secure Two-Party Computation,” Journal of Cryptology, Vol. 22, No. 2, April 2009, pp. 161-188.
[3]	Y. Lindell and B. Pinkas, “An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries,” Advances in Cryptology-Eurocrypt 2007, LNCS 4515, Barcelona, May 2007, pp. 52-78.
[4]	O. Goldreich, S. Micali and A. Wigderson, “How to Play Any Mental Game—A Completeness Theorem for Protocols with Honest Majority,” Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, 1987, pp. 218-229.
[5]	O. Goldreich, “Foundations of Cryptography: Volumne 2—Basic Applications,” Cambridge University Press, 2004.
[6]	M. Ben-Or, S. Goldwasser and A. Wigderson, “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation,” Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, 1988, pp. 1-10.
[7]	D. Chaum, C. Crepeau and I. Damgard, “Multiparty Unconditionally Secure Protocols,” Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, 1988, pp. 11-19.
[8]	S. Goldwasser and L. Levin, “Fair Computation of General Functions in Presence of Immoral Majority,” Advances of Cryptology-Crypto’90, LNCS 537, Santa Barbara, California, August 1990, pp. 77-93.
[9]	B. Chor and E. Kushilevitz, “A Zero-One Law for Boolean Privacy,” SIAM Journal on Discrete Mathematics, Vol. 4, No. 1, February 1991, pp. 36-47.
[10]	O. Goldreich, S. Goldwasser and N. Linial, “Fault-Tolerant Computation in the Full Information Model,” SIAM Journal on Computing, Vol. 27, No. 2, 1991, pp. 506- 544.
[11]	R. Ostrovsky and M. Yung, “How to Withstand Mobile Virus Attacks,” Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, Montreal, August 1991, pp. 51-59.
[12]	S. Micali and P. Rogaway, “Secure Computation,” Advances of Cryptology-Crypto’91, LNCS 576, Santa Barbara, California, August 1991, pp. 392-404.
[13]	D. Beaver, “Foundations of Secure Interactive Computing,” Advances of Cryptology-Crypto’91, LNCS 576, Santa Barbara, California, August 1991, pp. 377-391.
[14]	R. Canetti, U. Feige, O. Goldreich and M. Naor, “Adaptively Secure Multi-Party Computation,” Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996, pp. 639-648.
[15]	J. A. Garay and R. Ostrovsky, “Almost-Everywhere Secure Computation,” Advances of Cryptology-Eurocrypt 2008, LNCS 4965, Istanbul, April 2008, pp. 307-323.
[16]	R. Pass, “Bounded-Concurrent Secure Multi-Party Computation with a Dishonest Majority,” Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, 2004, pp. 232-241.
[17]	C. Cachin and J. Camenisch, “Optimistic Fair Secure Computation,” Advances of Cryptology-Crypto’00, LNCS 1880, Santa Barbara, California, August 2000, pp. 93- 111.
[18]	S. D. Gordon, C. Hazay, J. Katz and Y. Lindell, “Complete Fairness in Secure Two-Party Computation,” Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, 2008, pp. 413-422.
[19]	B. Pinkas, “Fair Secure Two-Party Computation,” Advance in Cryptology-Eurocrypt 2003, LNCS 2656, Warsaw, May 2003, pp. 87-106.
[20]	S. Even, O. Goldreich and A. Lempel, “A Randomized Protocol for Signing Contracts,” Communications of the ACM, Vol. 28, No. 6, 1985, pp. 637-647.
[21]	O. Goldreich, S. Goldwasser and S. Micali, “How to Construct Random Functions,” Journal of the ACM, Vol. 33, No. 4, 1986, pp. 792-807.
[22]	O. Goldreich, H. Krawcyzk and M. Luby, “On the Existence of Pseudorandom Generators,” SIAM Journal on Computing, Vol. 22, No. 6, 1993, pp. 1163-1175.
[23]	J. Hastad, R. Impagliazzo, L. A. Levin and M. Luby, “Construction of a Psedorandom Generator from Any One-Way Function,” SIAM Journal on Computing, Vol. 28, No. 4, 1999, pp. 1364-1396.