Top

Published in:

2019 | OriginalPaper | Chapter

Uncovering Algebraic Structures in the MPC Landscape

Authors : Navneet Agarwal, Sanat Anand, Manoj Prabhakaran

Published in: Advances in Cryptology – EUROCRYPT 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A fundamental problem in the theory of secure multi-party computation (MPC) is to characterize functions with more than 2 parties which admit MPC protocols with information-theoretic security against passive corruption. This question has seen little progress since the work of Chor and Ishai (1996), which demonstrated difficulties in resolving it. In this work, we make significant progress towards resolving this question in the important case of aggregating functionalities, in which m parties \(P_1,\dots ,P_m\) hold inputs \(x_1,\dots ,x_m\) and an aggregating party \(P_0\) must learn \(f(x_1,\dots ,x_m)\).

We uncover a rich class of algebraic structures that are closely related to secure computability, namely, “Commuting Permutations Systems” (CPS) and its variants. We present an extensive set of results relating these algebraic structures among themselves and to MPC, including new protocols, impossibility results and separations. Our results include a necessary algebraic condition and slightly stronger sufficient algebraic condition for a function to admit information-theoretically secure MPC protocols.

We also introduce and study new models of minimally interactive MPC (called UNIMPC and

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-17656-3_14/MediaObjects/483212_1_En_14_Figa_HTML.gif

), which not only help in understanding our positive and negative results better, but also open up new avenues for studying the cryptographic complexity landscape of multi-party functionalities. Our positive results include novel protocols in these models, which may be of independent practical interest.

Finally, we extend our results to a definition that requires UC security as well as semi-honest security (which we term strong security). In this model we are able to carry out the characterization of all computable functions, except for a gap in the case of aggregating functionalities.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Founding Secure Computation on Blockchains

next chapter Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies

Both PSM and NIMPC consider protocols of the following form: a coordinator sends a private message to each of \(P_1,\dots ,P_m\); each \(P_i\) uses this message and its input to compute a single message which it sends to \(P_0\); \(P_0\) computes an output. PSM has a corruption model in which only \(P_0\) could be corrupted, whereas NIMPC allows any subset of the parties (other than the coordinator) to be corrupted. But when such corruption takes place, NIMPC allows the adversary to learn the residual function determined by the honest parties’ inputs – i.e., the output for each possible setting of the inputs for the corrupt parties (unlike in MPC, where the output for only a given input of the corrupt parties is learned).

Replacing the views from the pre-processing phase of a UNIMPC protocol with correlated randomness from a trusted party turns it into an NIMPC protocol.

E.g., a 2-party functionality in which Bob receives \(a \vee b\), where \(a,b\in \{0,1\}\) are inputs to Alice and Bob respectively, has no protocol secure against passive corruption; but a protocol in which Alice simply sends a to Bob is UC secure. Also see \(\mathcal {F} _{\mathrm {AND}}\) discussed in Sect. 8.1..

We allow only the aggregating party \(P_0\) to have an output. The original definition in [PR08] allows all the parties to have outputs, but requires that for each party other than \(P_0\), its output is a function only of its own input. Such a function is “isomorphic” to an aggregated functionality as we define here.

Choice of 1 is arbitrary. Requiring identity permutation to always be part of each \(X_i\) is w.l.o.g., as a CPS without it will remain a CPS on adding it.

We let \(X_1 = \{ \pi _i \mid \pi _i(f(1,j))=f(i,j)\;\forall j\in [n]\}\), and \(X_2 = \{ \rho _j \mid \rho _j(f(i,1))=f(i,j)\;\forall i\in [n] \}\). These functions are well-defined permutations because of f being a Latin square functionality, and it is a CPS because, \(\pi _i \circ \rho _j (f(1,1)) = \rho _j \circ \pi _i (f(1,1)) = f(i,j)\). With a bijective embedding that relabels the outputs of f so that \(f(1,1)=1\), this meets the definition of a CPS.

[BGI+14]

Beimel, A., Gabizon, A., Ishai, Y., Kushilevitz, E., Meldgaard, S., Paskin-Cherniavsky, A.: Non-interactive secure multiparty computation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 387–404. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_22CrossRef

[BGW88]

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the 20th STOC, pp. 1–10 (1988)

[Blu81]

Blum, M.: Three applications of the oblivious transfer: part I: coin flipping by telephone; part II: how to exchange secrets; part III: how to send certified electronic mail. Technical report, University of California, Berkeley (1981)

[CCD88]

Chaum, D., Crépeau, C., Damgård, I.,: Multiparty unconditionally secure protocols. In: Proceedings of the 20th STOC, pp. 11–19 (1988)

[CI96]

Chor, B., Ishai, Y., On privacy and partition arguments. In: Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, Jerusalem, Israel, 10–12 June 1996, pp. 191–194 (1996). Journal version appears in Inf. Comput. 167(1)

[CK91]

Chor, B., Kushilevitz, E.: A zero-one law for Boolean privacy. SIAM J. Discrete Math. 4(1), 36–47 (1991)MathSciNetCrossRef

[CKL06]

Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. J. Cryptol. 19(2), 135–167 (2006)MathSciNetCrossRef

[FKN94]

Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: STOC, pp. 554–563 (1994)

[GL02]

Goldwasser, S., Lindell, Y.: Secure computation without agreement. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol. 2508, pp. 17–32. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36108-1_2CrossRef

[HIJ+16]

Halevi, S., Ishai, Y., Jain, A., Kushilevitz, E., Rabin, T.: Secure multiparty computation with general interaction patterns. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, 14–16 January 2016, pp. 157–168 (2016)

[HIJ+17]

Halevi, S., Ishai, Y., Jain, A., Komargodski, I., Sahai, A., Yogev, E.: Non-interactive multiparty computation without correlated randomness. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part III. LNCS, vol. 10626, pp. 181–211. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_7CrossRef

[HIKR18]

Halevi, S., Ishai, Y., Kushilevitz, E., Rabin, T.: Best possible information-theoretic MPC. In: Proceedings of Theory of Cryptography - 16th Theory of Cryptography Conference, TCC (2018, to appear)

[HM97]

Hirt, M., Maurer, U.M.: Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract). In: PODC, pp. 25–34 (1997)

[IK97]

Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: Israel Symposium on the Theory of Computing and Systems, ISTCS, pp. 174–184 (1997)

[IK00]

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: FOCS, pp. 294–304 (2000)

[KMR09]

Künzler, R., Müller-Quade, J., Raub, D.: Secure computability of functions in the IT setting with dishonest majority and applications to long-term security. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 238–255. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_15CrossRefMATH

[Kus89]

Kushilevitz, E.: Privacy and communication complexity. In: FOCS, pp. 416–421 (1989)

[MPR09]

Maji, H.K., Prabhakaran, M., Rosulek, M.: Complexity of multi-party computation problems: the case of 2-party symmetric secure function evaluation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 256–273. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_16CrossRefMATH

[MPR13]

Maji, H., Prabhakaran, M., Rosulek, M.: Complexity of multi-party computation functionalities. In: Secure Multi-Party Computation. Cryptology and Information Security Series, vol. 10, pp. 249–283. IOS Press, Amsterdam (2013)

[OY16]

Obana, S., Yoshida, M.: An efficient construction of non-interactive secure multiparty computation. In: Foresti, S., Persiano, G. (eds.) CANS 2016. LNCS, vol. 10052, pp. 604–614. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48965-0_39CrossRef

[PR08]

Prabhakaran, M., Rosulek, M.: Cryptographic complexity of multi-party computation problems: classifications and separations. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 262–279. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_15. Full version available as ECCC Report TR08-050 from https://eccc.weizmann.ac.ilCrossRef

[Rys51]

Ryser, H.J.: A combinatorial theorem with an application to Latin rectangles. Proc. Am. Math. Soc. 2(4), 550–552 (1951)MathSciNetCrossRef

[SRA79]

Shamir, A., Rivest, R.L., Adleman, L.M.: Mental poker. Technical report LCS/TR-125, Massachusetts Institute of Technology, April 1979

[Yao82]

Yao, A.C.-C.: Protocols for secure computation. In: Proceedings of the 23rd FOCS, pp. 160–164 (1982)

Title: Uncovering Algebraic Structures in the MPC Landscape
Authors: Navneet Agarwal
Sanat Anand
Manoj Prabhakaran
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17655-6

Electronic ISBN: 978-3-030-17656-3

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-17656-3_14

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner