nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Better Two-Round Adaptive Multi-party Computation

verfasst von : Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

Erschienen in: Public-Key Cryptography – PKC 2017

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

The only known two-round multi-party computation protocol that withstands adaptive corruption of all parties is the ingenious protocol of Garg and Polychroniadou [TCC 15]. We present protocols that improve on the GP protocol in a number of ways. First, concentrating on the semi-honest case and taking a different approach than GP, we show a two-round, adaptively secure protocol where:

Only a global (i.e., non-programmable) reference string is needed. In contrast, in GP the reference string is programmable, even in the semi-honest case.
Only polynomially-secure indistinguishability obfuscation for circuits and injective one way functions are assumed. In GP, sub-exponentially secure IO is assumed.

Second, we show how to make the GP protocol have only RAM complexity, even for Byzantine corruptions. For this we construct the first statistically-sound non-interactive Zero-Knowledge scheme with RAM complexity.

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 On the Computational Overhead of MPC with Dishonest Majority

Nächstes Kapitel Constant Round Adaptively Secure Protocols in the Tamper-Proof Hardware Model

Nur mit Berechtigung zugänglich

For instance, parties can choose randomness \(r_i\), make it part of their input, and evaluate the functionality \(F((x_1, r_1), \ldots , (x_n, r_n)) = f(x_1, \ldots , x_n; \bigoplus r_i)\).

To be more precise, [BCH12] require that there exist a translation function which maps ideal world internal state into real world internal state.

Indeed, some simple functions can be computed in a randomness-hiding way even in the plain model; for instance, the function \(f(r) = g^r\), where g is a group generator and r is randomness, can be simply computed by choosing a random element in a group; in this case randomness r remains unknown.

Recall that the security of MPC requires that no information about inputs of parties is leaked. Running time of a program M on input x could potentially leak information about x. Therefore if full security is needed then programs should necessarily work as long as their worst-case running time, even if computation on this particular input is short.

We underline that the approach of [GP14] requires a local CRS even in the honest-but-curious setting.

We note however that merely using their protocol in the semi-honest case doesn’t allow for a local CRS: their approach requires proving statements to an obfuscated program, which requires NIZK (and therefore a local CRS) even in the honest-but-curious case.

Which cannot be easily switched to the garbling scheme for RAM. For instance, in both protocols the underlying garbling scheme should support bit-by-bit garbling of an input. [DKR14] makes even further use of the actual construction of garbled circuits.

Note that usually the term “adaptive security” in the context of garbling is used to denote a different property: that the adversary can choose new inputs and functions after seeing garbled values.

With this approach the environment has to fix inputs before seeing the CRS, i.e. this garbling scheme is only selectively secure. However, this is good enough for the protocol of [GP14], since they anyway use complexity leveraging and subexponentially-secure \(\mathsf {iO}\).

Note that merely randomizing the PDE plaintext doesn’t yield a PRE.

If the protocol revealed randomness of the computation, then the garbling scheme would have to be adaptively secure, i.e. the simulator of the garbling scheme would have to first simulate it and then, once it learned inputs, provide consistent generation randomness of the garbling scheme (note that the term “adaptive security” is ambiguous: in the context of garbling it usually denotes a different property, saying that simulation is possible even if inputs or functions are chosen adaptively after seeing some garbled values. Here by adaptive security we mean that random coins can be generated by the simulator).

Note that the proof of garbling done correctly doesn’t save us, since the garbler followed the garbling algorithm; it’s just the scheme itself allows for wrong garbling.

In fact, for them it is enough that OWF is poly-to-one. Thus we can relax our assumptions for MPC protocol from injective OWF to poly-to-one OWF.

In fact, this requirement can be relaxed down to one way functions with at most polynomial-size preimage, since such OWF suffices to prove that the construction of [BST14] is secure; and therefore the PRE scheme (Sect. 2.1) exists under this assumption and \(\mathsf {iO}\).

We remark that the [GOS06] do not explicitly claim simulation soundness. It is easy to obtain a simulation-sound argument by sampling an independent CRS for every pair of parties.

[AIK06]

Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. Comput. Complex. 15(2), 115–162 (2006)MathSciNetCrossRefMATH

[BCH12]

Bitansky, N., Canetti, R., Halevi, S.: Leakage-tolerant interactive protocols. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 266–284. Springer, Heidelberg (2012). doi:10.1007/978-3-642-28914-9_15 CrossRef

[BCP15]

Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (Parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742–762. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_36 CrossRef

[BST14]

Bellare, M., Stepanovs, I., Tessaro, S.: Poly-many hardcore bits for any one-way function and a framework for differing-inputs obfuscation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 102–121. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45608-8_6

[CDPW07]

Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). doi:10.1007/978-3-540-70936-7_4 CrossRef

[CGP15]

Canetti, R., Goldwasser, S., Poburinnaya, O.: Adaptively Secure Two-Party Computation from Indistinguishability Obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 557–585. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46497-7_22 CrossRef

[CH16]

Canetti, R., Holmgren, J.: Fully succinct garbled RAM. In: Proceedings of the ACM Conference on Innovations in Theoretical Computer Science. Cambridge, MA, USA, 14–16 January, pp. 169–178 (2016)

[CHJV15]

Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Succinct garbling and indistinguishability obfuscation for RAM programs. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC. Portland, OR, USA, 14–17 June, pp. 429–437 (2015)

[CLOS02]

Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, 19–21 May. Montréal, Québec, Canada, pp. 494–503 (2002)

[CPR16]

Canetti, R., Poburinnaya, O., Raykova, M.: Optimal-rate non-committing encryption in a CRS model. IACR Cryptology ePrint Archive 2016:511 (2016)

[CPV16]

Canetti, R., Poburinnaya, O., Venkitasubramaniam, M.: Better two-round adaptive multiparty computation. In: Cryptology ePrint Archive, Report 2016/614 (2016). http://eprint.iacr.org/2016/614

[DKR14]

Dachman-Soled, D., Katz, J., Rao, V.: Adaptively secure, universally composable, multi-party computation in constant rounds. IACR Cryptology ePrint Archive 2014, 858 (2014)

[DMN11]

Damgård, I., Meldgaard, S., Nielsen, J.B.: Perfectly secure oblivious RAM without random oracles. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 144–163. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19571-6_10 CrossRef

[Gen09]

Gentry, C.: A Fully Homomorphic Encryption Scheme. Ph.D. thesis. Stanford, CA, USA, AAI3382729 (2009)

[GGHR14]

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). doi:10.1007/978-3-642-54242-8_4 CrossRef

[GOS06]

Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006). doi:10.1007/11761679_21 CrossRef

[GP14]

Garg, S., Polychroniadou, A.: Two-round adaptively secure MPC from indistinguishability obfuscation. IACR Cryptology ePrint Archive 2014:844 (2014)

[Gro11]

Groth, J.: Minimizing non-interactive zero-knowledge proofs using fully homomorphic encryption. IACR Cryptology ePrint Archive 2011:12 (2011)

[IK02]

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). doi:10.1007/3-540-45465-9_22 CrossRef

[IKOS10]

Ishai, Y., Kumarasubramanian, A., Orlandi, C., Sahai, A.: Proceedings on invertible sampling and adaptive security. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 466–482. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17373-8_27 CrossRef

[KSW14]

Khurana, D., Sahai, A., Waters, B.: How to generate and use universal parameters. IACR Cryptology ePrint Archive 2014:507 (2014)

[NY90]

Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. Baltimore, Maryland, USA, 13–17 May, pp. 427–437 (1990)

[SW14]

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, 31 May-03 June, pp. 475–484 (2014)

[Wat15]

Waters, B.: A punctured programming approach to adaptively secure functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 678–697. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_33 CrossRef

Titel: Better Two-Round Adaptive Multi-party Computation
verfasst von: Ran Canetti
Oxana Poburinnaya
Muthuramakrishnan Venkitasubramaniam
Verlag: Springer Berlin Heidelberg
Buch: Public-Key Cryptography – PKC 2017
Print ISBN: 978-3-662-54387-0

Electronic ISBN: 978-3-662-54388-7

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-662-54388-7_14

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