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:
Delegating RAM Computations with Adaptive Soundness and Privacy Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Adaptive Succinct Garbled RAM or: How to Delegate Your Database

verfasst von : Ran Canetti, Yilei Chen, Justin Holmgren, Mariana Raykova

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

We show how to garble a large persistent database and then garble, one by one, a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. The garbled database and programs reveal only the outputs of the programs when run in sequence on the database. Still, the runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. We assume indistinguishability obfuscation for circuits and somewhat-regular collision-resistant hash functions. In contrast, all previous garbling schemes with persistent data were shown secure only in the static setting where all the programs are known in advance.
As an immediate application, we give the first scheme for efficiently outsourcing a large database and computations on the database to an untrusted server, then delegating computations on this database, where these computations may update the database.
Our scheme extends the non-adaptive RAM garbling scheme of Canetti and Holmgren [ITCS 2016]. We also define and use a new primitive of independent interest, called adaptive accumulators. The primitive extends the positional accumulators of Koppula et al. [STOC 2015] and somewhere statistical binding hashing of Hubáček and Wichs [ITCS 2015] to an adaptive setting.

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 Interactive Oracle Proofs
Nächstes Kapitel Delegating RAM Computations
Fußnoten
1
To get an idea of why enforceability is needed, consider two programs \(C_0\) and \(C_1\), such that \(C_0(L^*, v^*) = C_1(L^*, v^*)\), but whose functionality may differ elsewhere, and let \(C'_i(L,v)\) be the program “if L, v are consistent with \(\mathsf {ac}^*\) then run \(C_i\), else output \(\bot \)”. Let \(\mathsf {i}\mathcal {O}\) be an indistinguishability obfuscator, i.e. it is guaranteed that \(\mathsf {i}\mathcal {O}(A)\approx \mathsf {i}\mathcal {O}(B)\) whenever equal sized programs A, B have the same functionality everywhere. We would like to argue that \(\mathsf {i}\mathcal {O}(C'_0)\approx \mathsf {i}\mathcal {O}(C'_1)\); however, we cannot do it directly using a plain Merkle hash tree, since collisions exist and so \(C'_0\) and \(C'_1\) have very different functionalities. Positional accumulators get around this difficulty: Using enforceability it is possible to argue that, when \(C'_0\) and \(C'_1\) use the rigged public key for the accumulator, the two programs have exactly the same functionality, and so indistinguishability holds. Due to the indistinguishability of rigged public accumulator keys from honest ones, indistinguishability holds even for the case of non-rigged accumulator keys.
 
2
Looking ahead, all the intermediate \((\mathsf {sk}, \mathsf {vk})\) key pairs are generated by applying \(\mathsf {F}\) to the (index, time-step) tuple.
 
3
This notion is similar but stronger to the “localized randomness” defined in [9].
 
Literatur
1.
Ananth, P., Chen, Y.-C., Chung, K.-M., Lin, H., Lin, W.-K.: Delegating ram computations with adaptive soundness and privacy. Cryptology ePrint Archive, Report 2015/1082 (2015)
2.
Ananth, P., Sahai, A.: Functional encryption for turing machines. IACR Cryptology ePrint Archive 2015, p. 776 (2015)
3.
Bellare, M., Hoang, V.T., Rogaway, P.: Adaptively secure garbling with applications to one-time programs and secure outsourcing. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 134–153. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34961-4_​10 CrossRef
4.
Bitansky, N., Canetti, R., Chiesa, A., Goldwasser, S., Lin, H., Rubinstein, A., Tromer, E.: The hunting of the SNARK. IACR Cryptology ePrint Archive 2014, p. 580 (2014)
5.
Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: Rubinfeld, R. (ed.) Symposium on the Theory of Computing (STOC) (2015)
6.
Bösch, C.T., Hartel, P.H., Jonker, W., Peter, A.: A survey of provably secure searchable encryption. ACM Comput. Surv. 47(2), 18:1–18:51 (2014)CrossRef
7.
8.
Canetti, R., Chen, Y., Holmgren, J., Raykova, M.: Succinct adaptive garbled ram. Cryptology ePrint Archive, Report 2015/1074 (2015)
9.
Canetti, R., Holmgren, J.: Fully succinct garbled ram. In: ITCS (2016)
10.
Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Indistinguishability obfuscation of iterated circuits and ram programs. Cryptology ePrint Archive, Report 2014/769 (2014)
11.
Chen, Y.-C., Chow, S.S., Chung, K.-M., Lai, R.W., Lin, W.-K., Zhou, H.-S.: Computation-trace indistinguishability obfuscation and its applications. IACR Cryptology ePrint Archive (2015)
12.
Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​26 CrossRef
13.
Chung, K.-M., Pass, R.: A simple ORAM. IACR Cryptology ePrint Archive 2013, p. 243 (2013)
14.
Damgård, I.B.: Collision free hash functions and public key signature schemes. In: Chaum, D., Price, W.L. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 203–216. Springer, Heidelberg (1988). doi:10.​1007/​3-540-39118-5_​19
15.
Garg, S., Steve, L., Ostrovsky, R., Scafuro, A.: Garbled ram from one-way functions. In: STOC (2015)
16.
Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​25 CrossRef
17.
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
18.
Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private ram computation. In: FOCS (2014)
19.
20.
21.
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)MathSciNetCrossRefMATH
22.
Hemenway, B., Jafargholi, Z., Ostrovsky, R., Scafuro, A., Wichs, D.: Adaptively secure garbled circuits from one-way functions
23.
Hubáček, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS (2015)
24.
Kalai, Y.T., Paneth, O.: Delegating ram computations. Cryptology ePrint Archive, Report 2015/957 (2015)
25.
Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 485–494 (2014)
26.
27.
Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. Cryptology ePrint Archive, Report 2014/925 (2014)
28.
Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: STOC (2015)
29.
30.
Okamoto, T., Pietrzak, K., Waters, B., Wichs, D.: New realizations of somewhere statistically binding hashing and positional accumulators. IACR Cryptology ePrint Archive 2015, p. 869 (2015)
31.
Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal verification of operations on dynamic sets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 91–110. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22792-9_​6 CrossRef
32.
Popa, R.A., Redfield, C., Zeldovich, N., Balakrishnan, H.: Cryptdb: protecting confidentiality with encrypted query processing. In: SOSP 2011, Cascais, Portugal, October 23–26, 2011, pp. 85–100 (2011)
33.
Rogaway, P.: The round complexity of secure protocols. Ph.D. thesis, Massachusetts Institute of Technology (1991)
34.
Walfish, M., Blumberg, A.J.: Verifying computations without reexecuting them. Commun. ACM 58(2), 74–84 (2015)CrossRef
35.
Yao, A.C.-C.: How to generate and exchange secrets. In: FOCS, pp. 162–167 (1986)
Metadaten
Titel
Adaptive Succinct Garbled RAM or: How to Delegate Your Database
verfasst von
Ran Canetti
Yilei Chen
Justin Holmgren
Mariana Raykova
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Theory of Cryptography

Print ISBN: 978-3-662-53643-8

Electronic ISBN: 978-3-662-53644-5

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-53644-5_3