Abstract
We present a constant-round protocol for general secure multiparty computation which makes a black-box use of a pseudorandom generator. In particular, the protocol does not require expensive zero-knowledge proofs and its communication complexity does not depend on the computational complexity of the underlying cryptographic primitive. Our protocol withstands an active, adaptive adversary corrupting a minority of the parties. Previous constant-round protocols of this type were only known in the semi-honest model or for restricted classes of functionalities.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. In: Proc. 20th Conference on Computational Complexity (2005)
Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in a constant number of rounds. In: Proc. 8th ACM PODC, pp. 201–209 (1989)
Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Security with low communication overhead (extended abstract). In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 62–76. Springer, Heidelberg (1991)
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proc. of 22nd STOC, pp. 503–513 (1990)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. of 20th STOC, pp. 1–10 (1988)
Cachin, C., Camenisch, J., Kilian, J., Muller, J.: One-round secure computation and secure autonomous mobile agents. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, p. 512. Springer, Heidelberg (2000)
Canetti, R.: Security and composition of multiparty cryptographic protocols. J. of Cryptology 13(1) (2000)
Canetti, R.: Universally Composable Security: A New Paradigm for Cryptographic Protocols. In: FOCS 2001, pp. 136–145 (2001)
Cramer, R., Damgård, I.: Secure distributed linear algebra in a constant number of rounds. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 119. Springer, Heidelberg (2001)
Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient Multiparty Computations Secure Against an Adaptive Adversary. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 311–326. Springer, Heidelberg (1999)
Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005)
Cramer, R., Damgård, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)
Cramer, R., Damgård, I., Nielsen, J.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–299. Springer, Heidelberg (2001)
Feige, U., Fiat, A., Shamir, A.: Zero-Knowledge Proofs of Identity. J. Cryptology 1(2), 77–94 (1988)
Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Proc. 26th STOC, pp. 554–563. ACM, New York (1994)
Feldman, P., Micali, S.: An Optimal Algorithm for Synchronous Byzantine Agreement. SIAM. J. Computing 26(2), 873–933 (1997)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In: Proceedings of the 33rd ACM Symp. on Theory of Computing (STOC 2001), pp. 580–589 (2001)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: On 2-round secure multiparty computation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 178. Springer, Heidelberg (2002)
Gilboa, N., Ishai, Y.: Compressing cryptographic resources. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 591. Springer, Heidelberg (1999)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game (extended abstract). In: Proc. of 19th STOC, pp. 218–229 (1987)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)
Hirt, M., Maurer, U.M.: Robustness for Free in Unconditional Multi-party Computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 101–118. Springer, Heidelberg (2001)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: Proc. 41st FOCS, pp. 294–304 (2000)
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of 21st Annual ACM Symposium on the Theory of Computing, pp. 44–61 (1989)
Katz, J., Ostrovsky, R.: Round-Optimal Secure Two-Party Computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 335–354. Springer, Heidelberg (2004)
Katz, J., Ostrovsky, R., Smith, A.: Round Efficiency of Multi-party Computation with a Dishonest Majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 578–595. Springer, Heidelberg (2003)
Kilian, J.: Founding cryptography on oblivious transfer. In: Proc. 20th STOC, pp. 20–31 (1988)
Lindell, Y.: Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation. J. Cryptology 16(3), 143–184 (2003); Preliminary version in Crypto 2001 (2001)
Lindell, Y., Lysyanskaya, A., Rabin, T.: Sequential composition of protocols without simultaneous termination. In: Proc. PODC 2002, pp. 203–212 (2002)
Lindell, Y., Pinkas, B.: A Proof of Yao’s Protocol for Secure Two-Party Computation. Cryptology ePrint Archive, Report 2004/175 (2004)
Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: Proc. STOC 2001, pp. 590–599 (2001)
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: Proc. 1st ACM Conference on Electronic Commerce, pp. 129–139 (1999)
Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Proc. STOC 2004, pp. 232–241 (2004)
Pass, R., Rosen, A.: Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. In: FOCS 2003 (2003)
Rabin, T., Ben-Or, M.: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority. In: Proc. 21st STOC, pp. 73–85. ACM, New York (1989)
Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of Reducibility between Cryptographic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004)
Rogaway, P.: The Round Complexity of Secure Protocols. PhD thesis, MIT (June 1991)
Shamir, A.: How to share a secret. Commun. ACM 22(6), 612–613 (1979)
Tate, S.R., Xu, K.: On garbled circuits and constant round secure function evaluation. CoPS Lab Technical Report 2003-02, University of North Texas (2003)
Yao, A.C.: How to generate and exchange secrets. In: Proc. 27th FOCS, pp. 162–167 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I., Ishai, Y. (2005). Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_23
Download citation
DOI: https://doi.org/10.1007/11535218_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28114-6
Online ISBN: 978-3-540-31870-5
eBook Packages: Computer ScienceComputer Science (R0)