Top

Published in:

2017 | OriginalPaper | Chapter

Robust Non-interactive Multiparty Computation Against Constant-Size Collusion

Authors : Fabrice Benhamouda, Hugo Krawczyk, Tal Rabin

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Non-Interactive Multiparty Computations (Beimel et al., Crypto 2014) is a very powerful notion equivalent (under some corruption model) to garbled circuits, Private Simultaneous Messages protocols, and obfuscation. We present robust solutions to the problem of Non-Interactive Multiparty Computation in the computational and information-theoretic models. Our results include the first efficient and robust protocols to compute any function in \(NC^1\) for constant-size collusions, in the information-theoretic setting and in the computational setting, to compute any function in P for constant-size collusions, assuming the existence of one-way functions. Our constructions start from a Private Simultaneous Messages construction (Feige, Killian Naor, STOC 1994 and Ishai, Kushilevitz, ISTCS 1997) and transform it into a Non-Interactive Multiparty Computation for constant-size collusions.

We also present a new Non-Interactive Multiparty Computation protocol for symmetric functions with significantly better communication complexity compared to the only known one of Beimel et al.

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 Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

next chapter The Price of Low Communication in Secure Multi-party Computation

Name given by Ishai and Kushilevitz [9].

We can always represent the message \(m'_{\varvec{\sigma },i,b}\) as a tuple of elements in \(\mathbb {F}_q\), and use an independent message-outputting protocol for each of these elements.

Note that while the honest parties’ inputs are from \(\{0,1\}\), we cannot control the inputs the adversary uses. The adversary can choose inputs from \(\mathbb {F}_q\).

In Sect. 3.2 we slightly change notation for vectors \(\varvec{x}_T\).

One refers to the vector \((\rho _0,\rho _1,\dots ,\rho _n)\) as the correlated randomness of the parties, with \(\rho _0\) called public randomness.

Better bounds for intervals containing a prime (power) exist. See [1].

The notation \(\mathsf {Setup}^{\varPi '}\) is a shortcut for \(\mathsf {Setup}^{\mathsf {Setup}',\mathsf {Msg}',\mathsf {Rec}'}\), i.e., \(\mathsf {Setup}\) with the three oracles \(\mathsf {Setup}',\mathsf {Msg}',\mathsf {Rec}'\).

We recall that \(\varPi '\) is assumed not to use any public randomness: \(\rho _0 = \perp \).

Better bounds for intervals containing a prime (power) exist. See [1].

Baker, R.C., Harman, G., Pintz, J.: The difference between consecutive primes, ii. Proc. Lond. Math. Soc. 83(3), 532–562 (2001). http://www.cs.umd.edu/~gasarch/BLOGPAPERS/BakerHarmanPintz.pdf

Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in nc\({^1}\). In: Hartmanis, J. (ed.) Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 28–30 May 1986, Berkeley, California, USA, pp. 1–5. ACM (1986). http://doi.acm.org/10.1145/12130.12131

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. LNCS, vol. 8617, pp. 387–404. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44381-1_22 CrossRef

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

Goldwasser, S., et al.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 578–602. Springer, Heidelberg (2014). doi:10.1007/978-3-642-55220-5_32 CrossRef

Goldwasser, S., Rothblum, G.N.: On best-possible obfuscation. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 194–213. Springer, Heidelberg (2007). doi:10.1007/978-3-540-70936-7_11 CrossRef

Halevi, S., Ishai, Y., Jain, A., Kushilevitz, E., Rabin, T.: Secure multiparty computation with general interaction patterns. In: Sudan, M. (ed.) ITCS 2016, pp. 157–168. ACM, New York (2016)

Halevi, S., Lindell, Y., Pinkas, B.: Secure computation on the web: computing without simultaneous interaction. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 132–150. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22792-9_8 CrossRef

Ishai, Y., Kushilevitz, E.: Private simultaneous message protocols with applications. In: Proceedings of ISTCS, pp. 174–184 (1997)

10.

Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002). http://dx.doi.org/10.1007/3-540-45465-9_22 CrossRef

11.

Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of Structures in Complexity Theory, pp. 102–111 (1993)

12.

Kilian, J.: Founding cryptography on oblivious transfer. In: 20th ACM STOC, pp. 20–31. ACM Press, May 1988

13.

MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-correcting Codes. Elsevier, Amsterdam (1977)MATH

14.

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). doi:10.1007/978-3-319-48965-0_39 CrossRef

15.

Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986

16.

Yoshida, M., Obana, S.: On the (in)efficiency of non-interactive secure multiparty computation. In: Kwon, S., Yun, A. (eds.) ICISC 2015. LNCS, vol. 9558, pp. 185–193. Springer, Cham (2016). doi:10.1007/978-3-319-30840-1_12 CrossRef

Title: Robust Non-interactive Multiparty Computation Against Constant-Size Collusion
Authors: Fabrice Benhamouda
Hugo Krawczyk
Tal Rabin
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2017
Print ISBN: 978-3-319-63687-0

Electronic ISBN: 978-3-319-63688-7

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-63688-7_13

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