Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
From Indifferentiability to Constructive Cryptography (and Back) Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Secure Multiparty RAM Computation in Constant Rounds

verfasst von : Sanjam Garg, Divya Gupta, Peihan Miao, Omkant Pandey

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Secure computation of a random access machine (RAM) program typically entails that it be first converted into a circuit. This conversion is unimaginable in the context of big-data applications where the size of the circuit can be exponential in the running time of the original RAM program. Realizing these constructions, without relinquishing the efficiency of RAM programs, often poses considerable technical hurdles. Our understanding of these techniques in the multi-party setting is largely limited. Specifically, the round complexity of all known protocols grows linearly in the running time of the program being computed. In this work, we consider the multi-party case and obtain the following results:
  • Semi-honest model: We present a constant-round black-box secure computation protocol for RAM programs. This protocol is obtained by building on the new black-box garbled RAM construction by Garg, Lu, and Ostrovsky [FOCS 2015], and constant-round secure computation protocol for circuits of Beaver, Micali, and Rogaway [STOC 1990]. This construction allows execution of multiple programs on the same persistent database.
  • Malicious model: Next, we show how to extend our semi-honest results to the malicious setting, while ensuring that the new protocol is still constant-round and black-box in nature.

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 Efficient Secure Multiparty Computation with Identifiable Abort
Nächstes Kapitel Constant-Round Maliciously Secure Two-Party Computation in the RAM Model
Fußnoten
1
We note that several other cutting-edge results [4, 6, 15, 19, 31] have been obtained in non-interactive secure computation over RAM programs but they all need to make strong computational assumptions such as [9, 10, 39]. Additionally they make non-black-box use of the underlying cryptographic primitives.
 
2
Interestingly for oblivious transfer extension we do know black-box construction based on stronger assumptions [28].
 
3
Additionally, black-box constructions enable implementations agnostic to the implementation of the underlying primitives. This offers greater flexibility allowing for many optimizations, scalability, and choice of implementation.
 
4
We elaborate on the fundamental issue in extending this result to the persistent database setting at the end of next section.
 
5
We note that our malicious secure protocol also achieves this weaker notion of persistent database, but in this paper we only focus on the standard notion of persistent data where later programs and inputs can be chosen dynamically.
 
6
Our protocol is non-black-box in the use of ORAM. But, since [11] and our paper use an information theoretic ORAM, we are still black-box in the use of underlying cryptography.
 
7
The labels revealed at generation time are later referred to as the tabled garbled information. For security of garbled RAM, it is crucial to hide the semantics of the labels dependent on the database contents and we will revisit this later in the technical overview.
 
8
Though this transformation is not crucial for security, it helps simplify the exposition of our protocol.
 
9
Note that for security, any garbled circuit can only be executed once. Hence, to enable multiple reads from the memory, each node consists of a sequence of garbled circuits. Number of garbled circuits at any node is chosen carefully. See [11] for details. For our purpose, we do not need to specify the number of garbled circuits at each node, but it is worth emphasizing that the total number of garbled circuits is \(|D|\cdot \mathsf {poly}(\log |D|, \kappa )\).
 
10
Note that it is public that \(j^{th}\) leaf corresponds to D[j]. Later, statistical ORAM is used to hide this correspondence.
 
11
During the protocol execution all parties would need space proportional to \(M\cdot \mathsf {poly}(\log M, \log T, \kappa ) + T\cdot \mathsf {poly}(\log M, \log T,\kappa )\). Looking ahead, this is needed to run a protocol which outputs the garbled RAM to the designated party.
 
12
This would be useful in arguing that the functionality computed under generic MPC is information theoretic as well as arguing efficiency while garbling multiple programs w.r.t. a persistent database.
 
13
The circuits described in [11] will be modified naturally to include these mask bits in evaluation. For example, consider a circuit which was originally producing output \({\mathsf {qKey}}_x\), where \({\mathsf {qKey}}\) was a collection of keys (two per bit) being selected by string x. Now new circuit will output \({\mathsf {qKey}}_{x \oplus \mathbf {\lambda }}\), where \(\mathbf {\lambda }\) contains the mask bits for all wires in x. Hence, if \({\mathsf {qKey}}\) was given as input, then we also need to provide \(\mathbf {\lambda }\) as input.
 
14
In the semi-honest setting, outputs of the honest parties are identical in the real world and the ideal world.
 
15
For ease of calculation, we can include of replenishing after running \(P^{{\left( 1\right) }} \) in the cost of \(P^{{\left( 1\right) }} \) and cost of replenishing after \(P^{{\left( 2\right) }} \) in the cost of \(P^{{\left( 2\right) }} \) and so on.
 
16
This is because the keys of the successor circuit are already fed as input to the predecessor and the new circuit just has to be consistent to the previously generated circuit.
 
17
Note that a malicious party might choose its inputs for the second program execution based on the garbled memory obtained in the first execution.
 
18
We address the issue of persistent database at the end of this section.
 
19
Recall that during evaluation, when a party \(Q_i\) decrypts the key for the output of a gate, it aborts if the \(i^{th}\) sub-part of the key does not match either the 0 or 1 key of \(Q_i\).
 
20
This is because ORAM is statistical and garble table generation is information theoretic once wire labels as well PRG outputs are known.
 
21
Since we are in the malicious setting, some honest parties may output \(\bot \). This would be captured by the ideal world adversary described later.
 
22
Recall that PRG outputs are only used to mask the keys of the output wire (see gate garbled technique in Sect. 5.1). This simulator uses the PRG values provided by the adversary instead of correct PRG outputs. This change can be described by a simple deterministic transformation on output of \(\mathsf {GramSim}_{\mathsf {bmr}}\).
 
Literatur
1.
Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: 28th ACM STOC, pp. 479–488. ACM Press, May 1996
2.
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, pp. 503–513. ACM Press, May 1990
3.
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 784–796. ACM Press (2012)
4.
5.
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: STOC, pp. 103–112 (1988)
6.
7.
8.
Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)MathSciNetCrossRefMATH
9.
Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38348-9_​1 CrossRef
10.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th FOCS, pp. 40–49. IEEE Computer Society Press, October 2013
11.
Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM. In: 56th Annual IEEE Symposium on Foundations of Computer Science (2015)
12.
Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 449–458. ACM Press (2015)
13.
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press, May/June 2009
14.
Gentry, C., Halevi, S., Lu, S., Ostrovsky, R., Raykova, M., Wichs, D.: Garbled RAM revisited. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 405–422. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​23 CrossRef
15.
Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. In: 55th FOCS, pp. 404–413. IEEE Computer Society Press, October 2014
16.
Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: Aho, A. (ed.) 19th ACM STOC, pp. 182–194. ACM Press (1987)
17.
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press (1987)
18.
19.
Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: How to run turing machines on encrypted data. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 536–553. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40084-1_​30 CrossRef
20.
Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: CCS (2012)
21.
Goyal, V., Lee, C.K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach. In: 53rd FOCS, pp. 51–60. IEEE Computer Society Press, October 2012
22.
Goyal, V., Mohassel, P., Smith, A.: Efficient two party and multi party computation against covert adversaries. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289–306. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78967-3_​17 CrossRef
23.
Goyal, V., Ostrovsky, R., Scafuro, A., Visconti, I.: Black-box non-black-box zero knowledge. In: Shmoys, D.B. (ed.) 46th ACM STOC. pp. 515–524. ACM Press, May/June 2014
24.
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
25.
Hazay, C., Yanai, A.: Constant-round maliciously secure two-party computation in the RAM model. In: TCC (2016-B)
26.
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st ACM STOC, pp. 44–61. ACM Press, May 1989
27.
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, Heidelberg (1990). doi:10.​1007/​0-387-34799-2_​2 CrossRef
28.
29.
Ishai, Y., Kushilevitz, E., Lindell, Y., Petrank, E.: Black-box constructions for secure computation. In: Kleinberg, J.M. (ed.) 38th ACM STOC, pp. 99–108. ACM Press (2006)
30.
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). doi:10.​1007/​978-3-540-85174-5_​32 CrossRef
31.
32.
33.
Miao, P.: Cut-and-choose for garbled RAM. Personal Communication (2016)
34.
35.
Ostrovsky, R.: Efficient computation on oblivious RAMs. In: 22nd ACM STOC, pp. 514–523. ACM Press, May 1990
36.
Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: 29th ACM STOC, pp. 294–303. ACM Press, May 1997
37.
38.
39.
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005)
40.
Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: 51st FOCS, pp. 531–540. IEEE Computer Society Press, October 2010
41.
Yao, A.C.C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160–164. IEEE Computer Society Press, November 1982
Metadaten
Titel
Secure Multiparty RAM Computation in Constant Rounds
verfasst von
Sanjam Garg
Divya Gupta
Peihan Miao
Omkant Pandey
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Theory of Cryptography

Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53641-4_19