Abstract
We study efficiency tradeoffs for secure two-party computation in presence of malicious behavior. We investigate two main approaches for defending against malicious behavior in Yao’s garbled circuit method: (1) Committed-input scheme, (2) Equality-checker scheme. We provide asymptotic and concrete analysis of communication and computation costs of the designed protocols. We also develop a weaker definition of security (k-leaked model) for malicious two-party computation that allows for disclosure of some information to a malicious party. We design more efficient variations of Yao’s protocol that are secure in the proposed model.
Chapter PDF
Similar content being viewed by others
Keywords
References
Abadi, M., Feigenbaum, J., Kilian, J.: On hiding information from an oracle. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 195–203. ACM Press, New York (1987)
Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, p. 119. Springer, Heidelberg (2001)
Bar-Yehuda, R., Chor, B., Kushilevitz, E., Orlitsky, A.: Privacy, additional information, and communication. IEEE Transactions on Information Theory (1993)
Cleve, R.: Controlled gradual disclosure schemes for random bits and their applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 573–588. Springer, Heidelberg (1990)
Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Commun. ACM 39(5), 77–85 (1996)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proofs. In: Proceedings of the 27th FOCS, pp. 174–187 (1986)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of 19th Annual ACM Symposium on Theory of Computing, pp. 218–229 (1987)
Goldreich, O.: Foundations of cryptography - vol.2, ch. 7 (2004)
Goldreich, O., Petrank, E.: Quantifying knowledge complexity. Computational Complexity 8, 50–98 (1999)
luby, M., Micali, S., Rackoff., C.: How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In: FOCS (1983)
Lindell, Y., Pinkas, B.: A proof of yao’s protocol for secure two-party computation. eprint archive (2004)
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay– a secure twoparty computation system. In: Proceedings of Usenix security (2004)
Pederson, T.P.: Non-interactive and information-theoritic secure verifiable secret-sharing (1991)
Pinkas, B.: Fair secure two-party computation. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 87–105. Springer, Heidelberg (2003)
Rabin, M.: How to exchange secrets by oblivious transfer. Technical Report Tech., Memo. TR-81, Aiken Computation Labratory, Harvard University (1981)
Woodruff, D.: unpublished manuscript (2006)
Yao, A.C.: How to generate and exchange secrets. In: Proceedings of the 27th IEEE symposioum on Foundations of Computer science, pp. 162–167 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mohassel, P., Franklin, M. (2006). Efficiency Tradeoffs for Malicious Two-Party Computation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11745853_30
Download citation
DOI: https://doi.org/10.1007/11745853_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33851-2
Online ISBN: 978-3-540-33852-9
eBook Packages: Computer ScienceComputer Science (R0)