nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

3PC ORAM with Low Latency, Low Bandwidth, and Fast Batch Retrieval

verfasst von : Stanislaw Jarecki, Boyang Wei

Erschienen in: Applied Cryptography and Network Security

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Multi-Party Computation of Oblivious RAM (MPC ORAM) implements secret-shared random access memory in a way that protects access pattern privacy against a threshold of corruptions. MPC ORAM enables secure computation of any RAM program on large data held by different entities, e.g. MPC processing of database queries on a secret-shared database. MPC ORAM can be constructed by any (client-server) ORAM, but there is an efficiency gap between known MPC ORAM’s and ORAM’s. Current asymptotically best MPC ORAM is implied by an “MPC friendly” variant of Path-ORAM [26] called Circuit-ORAM, due to Wang et al [27]. However, using garbled circuit for Circuit-ORAM’s client implies MPC ORAM which matches Path-ORAM in rounds but increases bandwidth by \(\varOmega (\kappa )\) factor, while using GMW or BGW protocols implies MPC ORAM which matches Path-ORAM in bandwidth, but increases round complexity by \(\varOmega ({\log n}\log {\log n})\) factor, where \(\kappa \) is a security parameter and \(n\) is memory size.

In this paper we bridge the gap between MPC ORAM and client-server ORAM by showing a specialized 3PC ORAM protocol, i.e. MPC ORAM for 3 parties tolerating 1 fault, which uses only symmetric ciphers and asymptotically matches client-server Path-ORAM in round complexity and for large records also in bandwidth.

Our 3PC ORAM also allows for fast pipelined processing: With postponed clean-up it processes \(b\,{=}\,O({\log n})\) accesses in \(O(b\,{+}\,{\log n})\) rounds with \(O(D\,{+}\,\mathsf {poly}({\log n}))\) bandwidth per item, where \(D\) is record size.

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 Best of Both Worlds in Secure Computation, with Low Communication Overhead

Nächstes Kapitel MergeMAC: A MAC for Authentication with Strict Time Constraints and Limited Bandwidth

In this paper we call the client-server ORAM implicit in [27] “Circuit-ORAM”, and its garbled-circuit 2PC implementation, also shown in [27], “2PC Circuit-ORAM”.

We use Path-ORAM as a client-server baseline for these comparisons because Path-ORAM has the most “MPC-friendly” client, hence most MPC ORAM’s emulate securely either Path-ORAM or its predecessor, Binary-Tree ORAM [25]. (The recent 2PC ORAM of [12] is an exception, discussed below.).

Using the BGW-style MPC over an arithmetic circuit for Circuit-ORAM, as was done by Keller and Scholl for another Path-ORAM variant [22], should also yield a bandwidth-competitive 3PC ORAM, but with round complexity at least \(\varOmega ({{\log ^2}n})\).

2PC ORAM cost of [12] has stash linear scan \(O(T\kappa {\log n})\) and amortized re-init \(O(nD/T)\). Picking \(T=O(\sqrt{nD/\kappa {\log n}})\) we get \(O(\sqrt{\kappa Dn{\log n}})\). In [12] this is rendered as \(O(\sqrt{n})\) overhead, assuming \(D=\varOmega ({\log n})\) and omitting \(\kappa \). [12] also show O(1)-round 2PC ORAM, but at the price of increased bandwidth and computation.

We estimate that the circuit depth of the Circuit-ORAM client, and hence the round complexity of the generic 3PC Circuit-ORAM, is \({>}\,1000\) even for \(n\,{=}\,2^{20}\), compared to \({\approx }15\) rounds in our 3PC ORAM and \({\approx }8\) in the client-server Path-ORAM.

We include CPU comparisons only with 2PC Circuit-ORAM, and not SQRT-ORAM [30] and DPF-ORAM [12], because the former uses the same Java ObliVM GC library while the latter two use the C library Obliv-C. Still, note that for \(n=30\), the on-line computation due to FSS evaluation and linear memory scans contributes over 1 sec to wall-clock in [12], while our on-line wall-clock comes to 40 msec.

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 805–817 (2016)

Beimel, A., Ishai, Y., Malkin, T.: Reducing the servers computation in private information retrieval: PIR with preprocessing. J. Cryptol. 17, 125–151 (2004)MathSciNetCrossRef

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

Bogdanov, D., Kamm, L., Kubo, B.: Students and taxes: a privacy-preserving study using secure computation. In: Proceedings on Privacy Enhancing Technologies (PET), pp. 117–135 (2016)

Bogdanov, D., Laur, S., Willemson, J.: Sharemind: a framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88313-5_13CrossRef

Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03549-4_20CrossRef

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001. IEEE Computer Society, Washington, DC (2001)

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, 2–4 May 1988, Chicago, Illinois, USA, pp. 11–19 (1988)

Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)MathSciNetCrossRef

10.

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). https://doi.org/10.1007/978-3-642-19571-6_10CrossRef

11.

Devadas, S., van Dijk, M., Fletcher, C.W., Ren, L., Shi, E., Wichs, D.: Onion ORAM: a constant bandwidth blowup oblivious RAM. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 145–174. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_6CrossRef

12.

Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, pp. 523–535. ACM, New York (2017)

13.

Dvir, Z., Gopi, S.: 2 server PIR with subpolynomial communication. J. ACM 63(4), 391–3915 (2016)MathSciNetCrossRef

14.

Faber, S., Jarecki, S., Kentros, S., Wei, B.: Three-party ORAM for secure computation. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 360–385. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_16CrossRef

15.

Fletcher, C.W., Naveed, M., Ren, L., Shi, E., Stefanov, E.: Bucket ORAM: single online roundtrip, constant bandwidth oblivious RAM. IACR Cryptology ePrint Archive, 2015:1065 (2015)

16.

Gentry, C., Goldman, K.A., Halevi, S., Julta, C., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: De Cristofaro, E., Wright, M. (eds.) PETS 2013. LNCS, vol. 7981, pp. 1–18. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39077-7_1CrossRef

17.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 218–229. ACM, New York (1987)

18.

Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)MathSciNetCrossRef

19.

Gordon, S.D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., Vahlis, Y.: Secure two-party computation in sublinear (amortized) time. In: Computer and Communications Security (CCS), CCS 2012, pp. 513–524 (2012)

20.

Ishai, Y., Kushilevitz, E., Lu, S., Ostrovsky, R.: Private large-scale databases with distributed searchable symmetric encryption. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 90–107. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_6CrossRef

21.

Jarecki, S., Wei, B.: 3PC ORAM with low latency, low bandwidth, and fast batch retrieval. IACR Cryptology ePrint Archive, 2018:347 (2018)

22.

Keller, M., Scholl, P.: Efficient, oblivious data structures for MPC. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 506–525. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_27CrossRef

23.

Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, 4–6 May 1997, pp. 294–303 (1997)

24.

Ren, L., Fletcher, C., Kwon, A., Stefanov, E., Shi, E., Van Dijk, M., Devadas, S.: Constants count: practical improvements to oblivious RAM. In: Proceedings of the 24th USENIX Conference on Security Symposium, SEC 2015, pp. 415–430. USENIX Association, Berkeley (2015)

25.

Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with O((logN)³) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197–214. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_11CrossRef

26.

Stefanov, E., van Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., Devadas, S.: Path ORAM: an extremely simple oblivious ram protocol. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer Communications Security, CCS 2013, pp. 299–310. ACM, New York (2013)

27.

Wang, X., Chan, H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 850–861 (2015). ACM, New York

28.

Wang, X.S., Huang, Y., Chan, T.-H.H., Shelat, A., Shi, E.: SCORAM: oblivious ram for secure computation. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 2014, pp. 191–202. ACM, New York (2014)

29.

Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, FOCS 1982, pp. 160–164 (1982)

30.

Zahur, S., Wang, X., Raykova, M., Gascón, A., Doerner, J., Evans, D., Katz, J.: Revisiting square-root ORAM efficient random access in multi-party computation. In: Proceedings of the 37th IEEE Symposium on Security and Privacy (“Oakland”). IEEE 2016 (2016)

Titel: 3PC ORAM with Low Latency, Low Bandwidth, and Fast Batch Retrieval
verfasst von: Stanislaw Jarecki
Boyang Wei
Verlag: Springer International Publishing
Buch: Applied Cryptography and Network Security
Print ISBN: 978-3-319-93386-3

Electronic ISBN: 978-3-319-93387-0

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93387-0_19

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"