Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

3-Party Distributed ORAM from Oblivious Set Membership

  • Conference paper
  • First Online:
Security and Cryptography for Networks (SCN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13409))

Included in the following conference series:

Abstract

Distributed Oblivious RAM (DORAM) protocols allow a group of participants to obliviously access a secret-shared array at a secret-shared index, and DORAM is the key tool for secure multiparty computation (MPC) in the RAM model.

In this work we present an efficient DORAM protocol with \(O((\kappa + D) \log N)\) communication per access, where N is the size of the memory, \(\kappa \) is a security parameter and D is the block size.

Our DORAM protocol is secure in the 3-party honest-majority setting, and is built from two novel, efficient components.

The first is a novel data structure for answering set membership queries. This data structure has asymptotically optimal (with tiny constants) memory usage, lookup cost and negligible failure probability. We show how this data structure can also be efficiently instantiated under MPC. The second is a Distributed Oblivious Hash Table protocol (in the 3-party honesty-majority setting) with asymptotically optimal memory usage and \(O(\kappa + D)\) communication per access. To our knowledge, this is the first Distributed Oblivious Hash Table with this efficiency that does not use homomorphic encryption.

Finally, we use this to build the aforementioned DORAM protocol. Our protocol performs polylogarithmic computation and does not require homomorphic encryption. Under natural parameter choices, it is the most communication-efficient DORAM with these properties.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Note that a k-server DORAM protocol does not immediately yield a \((k-1)\)-server active ORAM by allowing one of the DORAM servers to play role of the trusted client, because in active ORAM the client must use sublinear storage, and there is no such restriction for DORAM servers.

  2. 2.

    Our protocol could also be executed using garbled circuits. This would increase the communication cost by a factor of \(\kappa \), since 2 ciphertexts would need to be sent per AND gate [57]. However the round complexity would be reduced to linear in the “openings” depth of the protocol, rather than the AND depth of the circuit.

  3. 3.

    https://github.com/LowMC/lowmc/blob/master/determine_rounds.py.

  4. 4.

    Note that lookups require looking in a constant number of locations, but each location stores an identifier which must be at least \(\log n\) bits, so the total lookup cost requires transmitting (at least) a logarithmic number of bits. Even Cuckoo filters [19] requires storing keys that are at least \(\log n\) bits.

References

  1. Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_17

    Chapter  Google Scholar 

  2. Anati, I., Gueron, S., Johnson, S., Scarlata, V.: Innovative technology for CPU based attestation and sealing. In: HASP (2013)

    Google Scholar 

  3. Angluin, D.: Circuits to test equality. https://zoo.cs.yale.edu/classes/cs201/topics/topic-compare-equality.pdf

  4. Apon, D., Katz, J., Shi, E., Thiruvengadam, A.: Verifiable oblivious storage. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 131–148. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_8

    Chapter  Google Scholar 

  5. Araki, T., Furakawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: CCS (2016)

    Google Scholar 

  6. Asharov, G., Komargodski, I., Lin, W.-K., Nayak, K., Peserico, E., Shi, E.: OptORAMa: optimal oblivious RAM. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 403–432. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_14

    Chapter  Google Scholar 

  7. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: STOC. ACM, New York (1988). https://doi.org/10.1145/62212.62213

  8. Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337–367. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_12

    Chapter  Google Scholar 

  9. Brasser, F., Müller, U., Dmitrienko, A., Kostiainen, K., Capkun, S., Sadeghi, A.R.: Software grand exposure: SGX cache attacks are practical. In: WOOT (2017)

    Google Scholar 

  10. Bunn, P., Katz, J., Kushilevitz, E., Ostrovsky, R.: Efficient 3-party distributed ORAM. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 215–232. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_11

    Chapter  Google Scholar 

  11. Chan, T.-H.H., Katz, J., Nayak, K., Polychroniadou, A., Shi, E.: More is less: perfectly secure oblivious algorithms in the multi-server setting. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 158–188. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_7

    Chapter  Google Scholar 

  12. Cook, S.A., Reckhow, R.A.: Time bounded random access machines. J. Comp. Syst. Sci. 7(4), 354–375 (1973)

    Article  MathSciNet  Google Scholar 

  13. Costan, V., Devadas, S.: Intel SGX explained. IACR ePrint 2017/086 (2016)

    Google Scholar 

  14. 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_6

    Chapter  Google Scholar 

  15. Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: CCS (2017)

    Google Scholar 

  16. 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_16

    Chapter  Google Scholar 

  17. Falk, B.H., Noble, D., Ostrovsky, R.: 3-party distributed oram from oblivious set membership. Cryptology ePrint Archive, Paper 2021/1463 (2021). https://eprint.iacr.org/2021/1463

  18. Hemenway Falk, B., Noble, D., Ostrovsky, R.: Alibi: a flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 338–369. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_12

    Chapter  MATH  Google Scholar 

  19. Fan, B., Andersen, D.G., Kaminsky, M., Mitzenmacher, M.D.: Cuckoo filter: Practically better than bloom. In: CoNEXT (2014)

    Google Scholar 

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

    Google Scholar 

  21. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_17

    Chapter  Google Scholar 

  22. Gilboa, N., Ishai, Y.: Distributed point functions and their applications. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 640–658. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_35

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  24. Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious RAM simulation. In: SODA (2012)

    Google Scholar 

  25. Gordon, S.D., et al.: Secure two-party computation in sublinear (amortized) time. In: CCS (2012)

    Google Scholar 

  26. Gordon, S.D., Katz, J., Wang, X.: Simple and efficient two-server ORAM. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 141–157. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_6

    Chapter  Google Scholar 

  27. Gullasch, D., Bangerter, E., Krenn, S.: Cache games-bringing access-based cache attacks on AES to practice. In: S &P (2011)

    Google Scholar 

  28. Hamlin, A., Varia, M.: Two-server distributed ORAM with sublinear computation and constant rounds. IACR ePrint 2020/1547 (2020)

    Google Scholar 

  29. Hoekstra, M., Lal, R., Pappachan, P., Phegade, V., Del Cuvillo, J.: Using innovative instructions to create trustworthy software solutions. In: HASP (2013)

    Google Scholar 

  30. Jarecki, S., Wei, B.: 3PC ORAM with low latency, low bandwidth, and fast batch retrieval. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 360–378. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_19

    Chapter  MATH  Google Scholar 

  31. Kaplan, D., Powell, J., Woller, T.: AMD memory encryption. Technical report, AMD (2016)

    Google Scholar 

  32. Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput. (2009)

    Google Scholar 

  33. Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in) security of hash-based oblivious RAM and a new balancing scheme. In: SODA (2012)

    Google Scholar 

  34. Kushilevitz, E., Mour, T.: Sub-logarithmic distributed oblivious RAM with small block size. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11442, pp. 3–33. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17253-4_1

    Chapter  Google Scholar 

  35. Larsen, K.G., Nielsen, J.B.: Yes, there is an oblivious RAM lower bound! In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 523–542. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_18

    Chapter  Google Scholar 

  36. Laur, S., Willemson, J., Zhang, B.: Round-efficient oblivious database manipulation. In: Lai, X., Zhou, J., Li, H. (eds.) ISC 2011. LNCS, vol. 7001, pp. 262–277. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24861-0_18

    Chapter  Google Scholar 

  37. Lu, S., Ostrovsky, R.: Distributed oblivious RAM for secure two-party computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 377–396. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_22

    Chapter  Google Scholar 

  38. McKeen, F., et al.: Innovative instructions and software model for isolated execution. In: HASP (2013)

    Google Scholar 

  39. Mitchell, J.C., Zimmerman, J.: Data-oblivious data structures. In: STACS. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)

    Google Scholar 

  40. Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, Cambridge (2017)

    MATH  Google Scholar 

  41. Moghimi, A., Irazoqui, G., Eisenbarth, T.: CacheZoom: how SGX amplifies the power of cache attacks. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 69–90. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_4

    Chapter  Google Scholar 

  42. Noble, D.: An intimate analysis of cuckoo hashing with a stash. IACR ePrint 2021/447 (2021)

    Google Scholar 

  43. Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC (1990)

    Google Scholar 

  44. Ostrovsky, R.: Software protection and simulation on oblivious RAMs. Ph.D. thesis (1992)

    Google Scholar 

  45. Ostrovsky, R., Shoup, V.: Private information storage. In: STOC, vol. 97 (1997)

    Google Scholar 

  46. Patel, S., Persiano, G., Raykova, M., Yeo, K.: PanORAMa: oblivious RAM with logarithmic overhead. In: FOCS (2018)

    Google Scholar 

  47. Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 502–519. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_27

    Chapter  Google Scholar 

  48. Pippenger, N., Fischer, M.J.: Relations among complexity measures. JACM 26(2), 361–381 (1979)

    Article  MathSciNet  Google Scholar 

  49. Ren, L., et al.: Ring ORAM: closing the gap between small and large client storage oblivious RAM. IACR ePrint 2014/997 (2014)

    Google Scholar 

  50. Roy, L., Singh, J.: Large message homomorphic secret sharing from DCR and applications. IACR ePrint 2021/274 (2021)

    Google Scholar 

  51. Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with \(O((\log N)^3)\) 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_11

    Chapter  Google Scholar 

  52. Stefanov, E., e tal.: Path ORAM: an extremely simple oblivious RAM protocol. In: CCS (2013)

    Google Scholar 

  53. Tromer, E., Osvik, D.A., Shamir, A.: Efficient cache attacks on AES, and countermeasures. J. Cryptology 23(1), 37–71 (2009). https://doi.org/10.1007/s00145-009-9049-y

    Article  MathSciNet  MATH  Google Scholar 

  54. Wang, X.S., Liu, C., Nayak, K., Huang, Y., Shi, E.: ObliVM: a programming framework for secure computation. In: S & P (2015). http://www.cs.umd.edu/~elaine/docs/oblivm.pdf

  55. Wang, X., Chan, H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: CCS (2015)

    Google Scholar 

  56. Wang, X.S., Huang, Y., Chan, T.H.H., shelat, a., Shi, E.: SCORAM: oblivious RAM for secure computation. In: CCS (2014)

    Google Scholar 

  57. Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 220–250. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_8

    Chapter  MATH  Google Scholar 

  58. Zahur, S., et al.: Revisiting square-root ORAM: efficient random access in multi-party computation. In: S & P (2016)

    Google Scholar 

Download references

Acknowledgements

This research was sponsored in part by ONR grant (N00014-15-1-2750) “SynCrypt: Automated Synthesis of Cryptographic Constructions”. Supported in part by DARPA under Cooperative Agreement HR0011-20–2-0025, NSF grant CNS-2001096, US-Israel BSF grant 2015782, Google Faculty Award, JP Morgan Faculty Award, IBM Faculty Research Award, Xerox Faculty Research Award, OKAWA Foundation Research Award, B. John Garrick Foundation Award, Teradata Research Award, Lockheed-Martin Research Award, and Sunday Group. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, the Department of Defense, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes not withstanding any copyright annotation therein.

Author information

Authors and Affiliations

  1. University of Pennsylvania, Philadelphia, USA

    Brett Hemenway Falk & Daniel Noble

  2. UCLA, Los Angeles, USA

    Rafail Ostrovsky

Authors
  1. Brett Hemenway Falk
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Noble
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rafail Ostrovsky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Brett Hemenway Falk .

Editor information

Editors and Affiliations

  1. Università degli Studi di Salerno, Fisciano, Italy

    Clemente Galdi

  2. University of California at Irvine, Irvine, CA, USA

    Stanislaw Jarecki

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Falk, B.H., Noble, D., Ostrovsky, R. (2022). 3-Party Distributed ORAM from Oblivious Set Membership. In: Galdi, C., Jarecki, S. (eds) Security and Cryptography for Networks. SCN 2022. Lecture Notes in Computer Science, vol 13409. Springer, Cham. https://doi.org/10.1007/978-3-031-14791-3_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-14791-3_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-14790-6

  • Online ISBN: 978-3-031-14791-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation