Abstract
Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, Ostrovsky, Richelson and Scafuro (Crypto 2015) proved optimality of this result by showing how to realize arbitrary functionalities in four rounds where only one party receives the output via a black-box construction (and an extension to five rounds where both parties receive the output). In this paper we study the question of what security is achievable for stand-alone two-party protocols within four rounds.
We first provide a four-round two-party protocol for coin-tossing that achieves 1 / p-simulation security (i.e. simulation fails with probability at most \(1/p+{\mathsf{negl}}\)), in the presence of malicious corruptions. Next, we provide a four-round two-party protocol for general functionalities, where both parties receive the output, that achieves 1 / p-security in the presence of malicious adversaries corrupting one of the parties, and full security in the presence of non-aborting malicious adversaries corrupting the other party.
Next, we provide a three-round oblivious-transfer protocol, that achieves 1 / p-simulation security against arbitrary malicious senders, while simultaneously guaranteeing a meaningful notion of privacy against malicious corruptions of either party.
Finally, we show that the simulation-based security guarantees for our three-round protocols are optimal by proving that 1 / p-simulation security is impossible to achieve against both parties in three rounds or less when requiring some minimal guarantees on the privacy of their inputs.
C. Hazay—Research partially supported by a grant from the Israel Ministry of Science and Technology (grant No. 3-10883), by the European Research Council under the ERC consolidators grant agreement n. 615172 (HIPS), and by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office.
M. Venkitasubramaniam—Research supported by Google Faculty Research Grant and NSF Award CNS-1526377.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Formally, they require an “implicit input” function that can, from a transcript of the interaction, specify the input of a particular party. Our protocols provide statistical privacy guarantees and such a security guarantee cannot be input-indistinguishable.
- 2.
By fully secure, we mean standard simulation-based security.
- 3.
We can consider some canonical representation of elements in \(D_i\) in \(\{0,1\}^*\).
References
Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. IEEE J. Sel. Areas Commun. 18(4), 593–610 (2000)
Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. J. Cryptol. 23(2), 281–343 (2010)
Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. IACR Cryptology ePrint Archive 2005:106 (2005)
Beaver, D.: Foundations of secure interactive computing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 377–391. Springer, Heidelberg (1992)
Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014)
Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, USA, pp. 1444–1451
Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: STOC, pp. 364–369 (1986)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
Garay, J.A., Katz, J., Tackmann, B., Zikas, V.: How fair is your protocol? A utility-based approach to protocol optimality. In: PODC, pp. 281–290 (2015)
Garg, S., Mukherjee, P., Pandey, O., Polychroniadou, A.: The exact round complexity of secure computation. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 448–476. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49896-5_16
Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM J. Comput. 25(1), 169–192 (1996)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218–229 (1987)
Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 157–176. Springer, Heidelberg (2010)
Haitner, I., Ishai, Y., Kushilevitz, E., Lindell, Y., Petrank, E.: Black-box constructions of protocols for secure computation. SIAM J. Comput. 40(2), 225–266 (2011)
Halevi, S., Kalai, Y.T.: Smooth projective hashing and two-message oblivious transfer. J. Cryptol. 25(1), 158–193 (2012)
Hazay, C., Venkitasubramaniam, M.: What security can we achieve in 4-rounds? IACR Cryptology ePrint Arch. 2015, 797 (2015). http://eprint.iacr.org/2015/797
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient non-interactive secure computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 406–425. Springer, Heidelberg (2011)
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)
Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 171. Springer, Heidelberg (2001)
Micali, S.: Simple and fast optimistic protocols for fair electronic exchange. In: PODC, pp. 12–19 (2003)
Micali, S., Pass, R., Rosen, A.: Input-indistinguishable computation. In: FOCS, pp. 367–378 (2006)
Micali, S., Rogaway, P.: Secure computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992)
Moran, T., Naor, M., Segev, G.: An optimally fair coin toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 1–18. Springer, Heidelberg (2009)
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA, pp. 448–457 (2001)
Ostrovsky, R., Richelson, S., Scafuro, A.: Round-optimal black-box two-party computation. IACR Cryptology ePrint Archive 2015:553 (2015)
Pass, R.: Simulation in quasi-polynomial time, and its application to protocol composition. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 160–176. Springer, Heidelberg (2003)
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)
Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: STOC, pp. 242–251 (2004)
Yao, AC.-C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Hazay, C., Venkitasubramaniam, M. (2016). What Security Can We Achieve Within 4 Rounds?. In: Zikas, V., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2016. Lecture Notes in Computer Science(), vol 9841. Springer, Cham. https://doi.org/10.1007/978-3-319-44618-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-44618-9_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44617-2
Online ISBN: 978-3-319-44618-9
eBook Packages: Computer ScienceComputer Science (R0)