Abstract
Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality f to the task of securely computing a simpler functionality g. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as privacy. The special case of a degree-2 encoding g (2MPRE) has recently found several applications to secure multiparty computation (MPC) with either information-theoretic security or making black-box access to cryptographic primitives. Unfortunately, as all known constructions are based on information-theoretic MPC protocols in the plain model, they can only be private with an honest majority.
In this paper, we break the honest-majority barrier and present the first construction of general 2MPRE that remains secure in the presence of a dishonest majority. Our construction encodes every n-party functionality f by a 2MPRE that tolerates at most \(t=\lfloor 2n/3\rfloor \) passive corruptions.
We derive several applications including: (1) The first non-interactive client-server MPC protocol with perfect privacy against any coalition of a minority of the servers and up to t of the n clients; (2) Completeness of 3-party functionalities under non-interactive t-private reductions; and (3) A single-round t-private reduction from general-MPC to an ideal oblivious transfer (OT). These positive results partially resolve open questions that were posed in several previous works. We also show that t-private 2MPREs are necessary for solving (2) and (3), thus establishing new equivalence theorems between these three notions.
Finally, we present a new approach for constructing fully-private 2MPREs based on multi-round protocols in the OT-hybrid model that achieve perfect privacy against active attacks. Moreover, by slightly restricting the power of the active adversary, we derive an equivalence between these notions. This forms a surprising, and quite unique, connection between a non-interactive passively-private primitive to an interactive actively-private primitive.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For simplicity, here and throughout the paper, we think of functionalities as finite objects and accordingly derive protocols and simulators with finite fixed complexity. All our statements carry over to the asymptotic setting (possibly with a tiny loss of the privacy threshold) and yield constructions whose complexity is polynomial in the size of the formulas (or branching program) of the underlying functionality. Furthermore, if one is willing to make a black-box use of a PRG and relax privacy to computational, these results also extend to size-s circuits, where the complexity is linear in s [8, 15, 32]. In fact, all these “liftings” can be done automatically by using appropriate completeness results from [2,3,4, 22]. See the full version for details.
- 2.
More generally, one may ask whether \(k+1\) round protocols can be based on k-round OT, i.e., is it possible to obtain a single-round reduction. We focus on the minimal case of \(k=2\) for simplicity, though all our results actually hold for the general case.
- 3.
In the terminology of [3] the reduction of Patra and Srinivasan [30] is a “free Black-Box” reduction, whereas the (2-round) OT hybrid model corresponds to so-called “strict Black-box reduction”. To illustrate the distinction between the two notions, note that in a free-BB reduction, party A can, for example, generate several different “first messages” of the OT protocol, manipulate them (e.g., encrypt them) and deliver them to B or to a third party. Moreover, the 2nd part of these OT invocations can be later continued or withdrawn based on additional information (e.g., the inputs of B). In a strict BB reduction there is no notion of “first message” and the parties can only feed their inputs into the OT functionality and obtain the output. Thus a strict-BB reduction implies a free-BB reduction. See further discussion in [30].
- 4.
- 5.
We refer to this as “3-party OT” since the 2-party version of this functionality, where the output is delivered to, say, Alice, is essentially equivalent to the standard 1-out-of-2 OT.
- 6.
A related observation is in the heart of other recent round reduction techniques [4, 11, 20], though we do not see a way to obtain our result based on their techniques. Specifically, [11, 20] makes a non-black-box use of OTs and [4] exploit the specific properties of Yao’s based randomized encodings. In particular, the latter result does not seem to extend to arithmetic protocols while our result does.
- 7.
The requirement for a single call is without loss of generality in the semi-honest setting, since multiple parallel calls can be packed in a single call.
- 8.
In fact, we could take \(s_i\) to be the sum of a random bit that is sampled by A and a random bit that is sampled by B.
- 9.
Despite the equivalence of addition and subtraction over the binary field, we use both signs to indicate that the construction generalizes to general fields.
- 10.
Alternatively, one can instantiate g over the binary field, and reduce the error to \(\epsilon \) by repeating the encoding \(\log (1/\epsilon )\) times with fresh independent randomness. See [22].
References
Alon, B., Paskin-Cherniavsky, A.: On perfectly secure 2PC in the OT-hybrid model. Theor. Comput. Sci. 891, 166–188 (2021)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC\(^0\). In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 166–175 (2004)
Applebaum, B., Brakerski, Z., Garg, S., Ishai, Y., Srinivasan, A.: Separating two-round secure computation from oblivious transfer. In: 11th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 151, pp. 71:1–71:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
Applebaum, B., Brakerski, Z., Tsabary, R.: Perfect secure computation in two rounds. SIAM J. Comput. 50(1), 68–97 (2021)
Babai, L., Gál, A., Kimmel, P.G., Lokam, S.V.: Communication complexity of simultaneous messages. SIAM J. Comput. 33(1), 137–166 (2003)
Barkol, O., Ishai, Y., Weinreb, E.: On d-multiplicative secret sharing. J. Cryptol. 23(4), 580–593 (2010)
Beaver, D.: Precomputing oblivious transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_8
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, USA, 13–17 May 1990, pp. 503–513 (1990)
Beimel, A., Ishai, Y., Kushilevitz, E.: General constructions for information-theoretic private information retrieval. J. Comput. Syst. Sci. 71(2), 213–247 (2005)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pp. 1–10 (1988)
Benhamouda, F., Lin, H.: k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 500–532. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_17
Boyle, E., Gilboa, N., Ishai, Y., Lin, H., Tessaro, S.: Foundations of homomorphic secret sharing. In: ITCS 2018, vol. 94, pp. 21:1–21:21 (2018)
Crépeau, C.: Efficient cryptographic protocols based on noisy channels. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 306–317. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_21
Crépeau, C., Kilian, J.: Achieving oblivious transfer using weakened security assumptions (extended abstract). In: 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24–26 October 1988, pp. 42–52. IEEE Computer Society (1988)
Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_23
Döttling, N., Kraschewski, D., Müller-Quade, J.: Unconditional and composable security using a single stateful tamper-proof hardware token. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 164–181. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_11
Dubovitskaya, M., Scafuro, A., Visconti, I.: On efficient non-interactive oblivious transfer with tamper-proof hardware. IACR Cryptol. ePrint Arch., p. 509 (2010), http://eprint.iacr.org/2010/509
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)
Garg, S., Ishai, Y., Srinivasan, A.: Two-round MPC: information-theoretic and black-box. In: TCC 2018, pp. 123–151 (2018)
Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_16
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority. In: Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 307–328 (2019)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 294–304 (2000)
Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., Paskin-Cherniavsky, A.: On the power of correlated randomness in secure computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 600–620. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_34
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11–13 June 2007, pp. 21–30 (2007)
Ishai, Yuval, Prabhakaran, Manoj, Sahai, Amit: Founding cryptography on oblivious transfer – efficiently. In: Wagner, David (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_32
Kilian, J.: Founding cryptography on oblivious transfer. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, 2–4 May 1988, pp. 20–31. ACM (1988)
Kolesnikov, V.: Truly efficient string oblivious transfer using resettable tamper-proof tokens. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 327–342. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_20
Lin, Huijia, Liu, Tianren, Wee, Hoeteck: Information-theoretic 2-round mpc without round collapsing: adaptive security, and more. In: Pass, Rafael, Pietrzak, Krzysztof (eds.) TCC 2020. LNCS, vol. 12551, pp. 502–531. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_18
Nascimento, A.C.A., Winter, A.J.: On the oblivious transfer capacity of noisy correlations. In: Proceedings 2006 IEEE International Symposium on Information Theory, ISIT 2006, The Westin Seattle, Seattle, Washington, USA, 9–14 July 2006, pp. 1871–1875. IEEE (2006)
Patra, Arpita, Srinivasan, Akshayaram: Three-round secure multiparty computation from black-box two-round oblivious transfer. In: Malkin, Tal, Peikert, Chris (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 185–213. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_7
Rabin, M.O.: How to exchange secrets with oblivious transfer. Technical report TR-81, Aiken Computation Lab, Harvard University (1981)
Yao, A.C.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, pp. 162–167 (1986)
Acknowledgements
B. Applebaum and O. Karni are supported by the Israel Science Foundation grant no. 2805/21. Y. Ishai is supported by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20. A. Patra is supported by DST National Mission on Interdisciplinary Cyber-Physical Systems (NM-CPS) 2020–2025 and SERB MATRICS (Theoretical Sciences) Grant 2020-2023.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 International Association for Cryptologic Research
About this paper
Cite this paper
Applebaum, B., Ishai, Y., Karni, O., Patra, A. (2022). Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications. In: Dodis, Y., Shrimpton, T. (eds) Advances in Cryptology – CRYPTO 2022. CRYPTO 2022. Lecture Notes in Computer Science, vol 13510. Springer, Cham. https://doi.org/10.1007/978-3-031-15985-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-15985-5_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15984-8
Online ISBN: 978-3-031-15985-5
eBook Packages: Computer ScienceComputer Science (R0)
