nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Asynchronous Secure Multiparty Computation in Constant Time

verfasst von : Ran Cohen

Erschienen in: Public-Key Cryptography – PKC 2016

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In the setting of secure multiparty computation, a set of mutually distrusting parties wish to securely compute a joint function. It is well known that if the communication model is asynchronous, meaning that messages can be arbitrarily delayed by an unbounded (yet finite) amount of time, secure computation is feasible if and only if at least two-thirds of the parties are honest, as was shown by Ben-Or, Canetti, and Goldreich [STOC’93] and by Ben-Or, Kelmer, and Rabin [PODC’94]. The running-time of all currently known protocols depends on the function to evaluate. In this work we present the first asynchronous MPC protocol that runs in constant time.

Our starting point is the asynchronous MPC protocol of Hirt, Nielsen, and Przydatek [Eurocrypt’05, ICALP’08]. We integrate threshold fully homomorphic encryption in order to reduce the interactions between the parties, thus completely removing the need for the expensive king-slaves approach taken by Hirt et al.. Initially, assuming an honest majority, we construct a constant-time protocol in the asynchronous Byzantine agreement (ABA) hybrid model. Using a concurrent ABA protocol that runs in constant expected time, we obtain a constant expected time asynchronous MPC protocol, secure facing static malicious adversaries, assuming \(t<n/ 3\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel KDM-Security via Homomorphic Smooth Projective Hashing

Nächstes Kapitel Adaptively Secure Multi-Party Computation from LWE (via Equivocal FHE)

The running time is measured by the elapsed time of the protocol while normalizing the maximal delay imposed on a message to 1.

Following the impossibility result of [22], asynchronous agreement protocols cannot be computed in constant time.

Which essentially means that ciphertexts can be added but not multiplied.

This behaviour is formally modeled using the eventual-delivery secure message transmission ideal functionality in [32].

For simplicity, we concentrate on the single-session version of \({\mathcal{F}_\mathsf{ZK}}\), which requires a separate common reference string for each protocol that realizes \({\mathcal{F}_\mathsf{ZK}}\). The protocols realizing \({\mathcal{F}_\mathsf{ZK}}\) will later be composed, using the universal composition with joint state of Canetti and Rabin [16], to obtain protocols that use only a single copy of the common reference string when realizing all the copies of \({\mathcal{F}_\mathsf{ZK}}\).

In the scheme of Shamir [39], fix the points corresponding to the shares \(d_i\) (for \(i\in {\mathcal {I}}\)) and the secret y, create a degree t polynomial interpolating these points, and compute the shares \(d_j\) (for \(j\notin {\mathcal {I}}\)) accordingly.

Although the protocol in [7] is proved based on the property-based definition of ABA, a simulation-based proof should follow as we consider static adversaries.

Almansa, J.F., Damgård, I.B., Nielsen, J.B.: Simplified threshold RSA with adaptive and proactive security. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 593–611. Springer, Heidelberg (2006)CrossRef

Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483–501. Springer, Heidelberg (2012)CrossRef

Backes, M., Bendun, F., Choudhury, A., Kate, A.: Asynchronous MPC with a strict honest majority using non-equivocation. In: Proceedings of the 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 10–19 (2014)

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 (STOC), pp. 503–513(1990)

Beerliová-Trubíniová, Z., Hirt, M.: Simple and efficient perfectly-secure asynchronous MPC. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 376–392. Springer, Heidelberg (2007)CrossRef

Beerliová-Trubíniová, Z., Hirt, M., Nielsen, J.B.: On the theoretical gap between synchronous and asynchronous MPC protocols. In: Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 211–218 (2010)

Ben-Or, M., El-Yaniv, R.: Resilient-optimal interactive consistency in constant time. Distrib. Comput. 16(4), 249–262 (2003)CrossRef

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

Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 52–61 (1993)

10.

Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience (Extended Abstract). In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 183–192 (1994)

11.

Bendlin, R., Damgård, I.: Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 201–218. Springer, Heidelberg (2010)CrossRef

12.

Bendlin, R., Krehbiel, S., Peikert, C.: How to share a lattice trapdoor: threshold protocols for signatures and (H)IBE. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 218–236. Springer, Heidelberg (2013)CrossRef

13.

Bracha, G.: An asynchronous [(n-1)/3]-resilient consensus protocol. In: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 154–162 (1984)

14.

Canetti, R., Security, U.C.: A new paradigm for cryptographic protocols. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 136–145 (2001)

15.

Canetti, R., Rabin, T.: Fast asynchronous Byzantine agreement with optimal resilience. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 42–51 (1993)

16.

Canetti, R., Rabin, T.: Universal composition with joint state. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 265–281. Springer, Heidelberg (2003)CrossRef

17.

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (Extended Abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 11–19 (1988)

18.

Choudhury, A., Patra, A.: Optimally resilient asynchronous MPC with linear communication complexity. In: Proceedings of the 16th International Conference on Distributed Computing and Networking (ICDCN), p. 5 (2015)

19.

Choudhury, A., Hirt, M., Patra, A.: Asynchronous multiparty computation with linear communication complexity. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 388–402. Springer, Heidelberg (2013)CrossRef

20.

Cramer, R., Damgård, I.B., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001)CrossRef

21.

De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Heidelberg (2001)CrossRef

22.

Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)CrossRefMathSciNetMATH

23.

Garay, J.A., MacKenzie, P.D., Yang, K.: Strengthening zero-knowledge protocols using signatures. J. cryptol. 19(2), 169–209 (2006)CrossRefMathSciNetMATH

24.

Garg, S., Gentry, C., Halevi, S., Raykova, M.: Two-round secure MPC from indistinguishability obfuscation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 74–94. Springer, Heidelberg (2014)CrossRef

25.

Gentry, C.: A fully homomorphic encryption scheme. Ph.D thesis

26.

Goldreich, O.: The Foundations of Cryptography - Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)CrossRef

27.

Goldreich, O., Micali, S., Wigderson A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 218–229 (1987)

28.

Dov Gordon, S., Liu, F.-H., Shi, E.: Constant-Round MPC with fairness and guarantee of output delivery. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 63–82. Springer, Heidelberg (2015)CrossRef

29.

Hirt, M., Nielsen, J.B., Przydatek, B.: Cryptographic asynchronous multi-party computation with optimal resilience (Extended Abstract). In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 322–340. Springer, Heidelberg (2005)CrossRef

30.

Hirt, M., Nielsen, J.B., Przydatek, B.: Asynchronous multi-party computation with quadratic communication. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 473–485. Springer, Heidelberg (2008)CrossRef

31.

Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer – efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)CrossRef

32.

Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013)CrossRef

33.

Mukherjee, P., Wichs, D.: Two round MPC from LWE via Multi-Key FHE.Cryptology ePrint Archive, Report 2015/345 (2015). http://eprint.iacr.org/

34.

Nielsen, J.B.: A threshold pseudorandom function construction and its applications. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 401–416. Springer, Heidelberg (2002)CrossRef

35.

Patra, A., Choudhary, A., Rangan, C.P.: Communication efficient statistical asynchronous multiparty computation with optimal resilience. In: Bao, F., Yung, M., Lin, D., Jing, J. (eds.) Inscrypt 2009. LNCS, vol. 6151, pp. 179–197. Springer, Heidelberg (2010)CrossRef

36.

Patra, A., Choudhury, A., Rangan, C.P.: Efficient asynchronous verifiable secret sharing and multiparty computation. J. Cryptol. 28(1), 49–109 (2015)CrossRefMATH

37.

Prabhu, B.S., Srinathan, K., Pandu Rangan, C.: Asynchronous unconditionally secure computation: an efficiency improvement. In: Menezes, A., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, pp. 93–107. Springer, Heidelberg (2002)CrossRef

38.

Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (Extended Abstract). In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 73–85 (1989)

39.

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)CrossRefMathSciNetMATH

40.

Srinathan, K., Pandu Rangan, C.: Efficient asynchronous secure multiparty distributed computation. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 117–129. Springer, Heidelberg (2000)CrossRef

41.

Toueg, S.: Randomized Byzantine agreements. In: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 163–178 (1984)

Titel: Asynchronous Secure Multiparty Computation in Constant Time
verfasst von: Ran Cohen
Verlag: Springer Berlin Heidelberg
Buch: Public-Key Cryptography – PKC 2016
Print ISBN: 978-3-662-49386-1

Electronic ISBN: 978-3-662-49387-8

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-49387-8_8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner