Skip to main content
SpringerLink
Log in

Two-Server Distributed ORAM with Sublinear Computation and Constant Rounds

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2021 (PKC 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12711))

Included in the following conference series:

Abstract

Distributed ORAM (DORAM) is a multi-server variant of Oblivious RAM. Originally proposed to lower bandwidth, DORAM has recently been of great interest due to its applicability to secure computation in the RAM model, where circuit complexity and rounds of communication are equally important metrics of efficiency. All prior DORAM constructions either involve linear work per server (e.g., Floram) or logarithmic rounds of communication between servers (e.g., square root ORAM). In this work, we construct the first DORAM schemes in the 2-server, semi-honest setting that simultaneously achieve sublinear server computation and constant rounds of communication. We provide two constant-round constructions, one based on square root ORAM that has \(O(\sqrt{N}\log N)\) local computation and another based on secure computation of a doubly efficient PIR that achieves local computation of \(O(N ^\epsilon )\) for any \(\epsilon > 0\) but that allows the servers to distinguish between reads and writes. As a building block in the latter construction, we provide secure computation protocols for evaluation and interpolation of multivariate polynomials based on the Fast Fourier Transform, which may be of independent interest.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.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

Notes

  1. 1.

    The exact functionality including the indicator bit is not included in their constructions, but they can be easily be extended with an additional round of a conditional computations.

  2. 2.

    A concurrent work by Boyle et al. [4] relies on an equivalent assumption called Oblivious LDC.

  3. 3.

    For any value of \(t< \log (N +t)\) then the cost of \(\varPi _{store}\) controls, but in our setting we consider a \(t\) greater than that.

References

  1. Abraham, I., Fletcher, C.W., Nayak, K., Pinkas, B., Ren, L.: Asymptotically tight bounds for composing ORAM with PIR. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10174, pp. 91–120. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54365-8_5

  2. 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 

  3. Boyle, E., Holmgren, J., Weiss, M.: Permuted puzzles and cryptographic hardness. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 465–493. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_18

    Chapter  Google Scholar 

  4. Boyle, E., Ishai, Y., Pass, R., Wootters, M.: Can we access a database both locally and privately? In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 662–693. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_22

    Chapter  Google Scholar 

  5. 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 

  6. Canetti, R., Holmgren, J., Richelson, S.: Towards doubly efficient private information retrieval. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 694–726. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_23

    Chapter  Google Scholar 

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

  8. Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex fourier series. Math. Comput. 19(90), 297–301 (1965)

    Article  MathSciNet  Google Scholar 

  9. Damgård, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 285–304. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_15

    Chapter  Google Scholar 

  10. Dodis, Y., Yampolskiy, A.: A verifiable random function with short proofs and keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416–431. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30580-4_28

    Chapter  Google Scholar 

  11. Doerner, J., Shelat, A.: Scaling ORAM for secure computation. In: ACM Conference on Computer and Communications Security, pp. 523–535. ACM (2017)

    Google Scholar 

  12. Gao, S., Mateer, T.D.: Additive fast fourier transforms over finite fields. IEEE Trans. Inf. Theory 56(12), 6265–6272 (2010)

    Article  MathSciNet  Google Scholar 

  13. Garg, S., Lu, S., Ostrovsky, R.: Black-box garbled RAM. In: FOCS, pp. 210–229. IEEE Computer Society (2015)

    Google Scholar 

  14. Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: STOC, pp. 449–458. ACM (2015)

    Google Scholar 

  15. Garg, S., Mohassel, P., Papamanthou, C.: TWORAM: round-optimal oblivious RAM with applications to searchable encryption. IACR Cryptol. ePrint Arch. 2015, 1010 (2015)

    Google Scholar 

  16. 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). https://doi.org/10.1007/978-3-642-55220-5_23

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  19. 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 

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

    Google Scholar 

  21. Hoang, T., Yavuz, A.A., Durak, F.B., Guajardo, J.: Oblivious dynamic searchable encryption via distributed PIR and ORAM. IACR Cryptol. ePrint Arch. 2017, 1158 (2017)

    Google Scholar 

  22. Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_34

    Chapter  MATH  Google Scholar 

  23. 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 

  24. Kedlaya, K.S., Umans, C.: Fast modular composition in any characteristic. In: FOCS, pp. 146–155. IEEE Computer Society (2008)

    Google Scholar 

  25. 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 

  26. 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 

  27. Lu, S., Ostrovsky, R.: How to garble RAM programs. In: EUROCRYPT. Lecture Notes in Computer Science, vol. 7881, pp. 719–734. Springer (2013)

    Google Scholar 

  28. Miao, P., Patel, S., Raykova, M., Seth, K., Yung, M.: Two-sided malicious security for private intersection-sum with cardinality. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 3–33. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_1

    Chapter  Google Scholar 

  29. Nishide, T., Ohta, K.: Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 343–360. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_23

    Chapter  Google Scholar 

  30. Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: STOC, pp. 294–303. ACM (1997)

    Google Scholar 

  31. Patel, S., Persiano, G., Raykova, M., Yeo, K.: Panorama: Oblivious RAM with logarithmic overhead. In: FOCS, pp. 871–882. IEEE Computer Society (2018)

    Google Scholar 

  32. Roche, D.S., Aviv, A.J., Choi, S.G.: A practical oblivious map data structure with secure deletion and history independence. In: IEEE Symposium on Security and Privacy, pp. 178–197. IEEE Computer Society (2016)

    Google Scholar 

  33. Wang, X., Chan, T.H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: ACM Conference on Computer and Communications Security, pp. 850–861. ACM (2015)

    Google Scholar 

  34. Wang, X.S., Huang, Y., Chan, T.H., Shelat, A., Shi, E.: SCORAM: oblivious RAM for secure computation. In: ACM Conference on Computer and Communications Security, pp. 191–202. ACM (2014)

    Google Scholar 

  35. Weiss, M., Wichs, D.: Is there an oblivious RAM lower bound for online reads? In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11240, pp. 603–635. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03810-6_22

    Chapter  Google Scholar 

  36. 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: IEEE Symposium on Security and Privacy, pp. 218–234. IEEE Computer Society (2016)

    Google Scholar 

  37. Zhang, J., Ma, Q., Zhang, W., Qiao, D.: MSKT-ORAM: a constant bandwidth ORAM without homomorphic encryption. IACR Cryptol. ePrint Arch. 2016, 882 (2016)

    Google Scholar 

Download references

Acknowledgments

We gratefully acknowledge conversations with Daniel Wichs and Jack Doerner for their valuable insights. This material is based upon work supported by the National Science Foundation under Grants 1414119, 1718135, 1750795, and 1931714.

Author information

Authors and Affiliations

  1. Khoury College of Computer Sciences, Northeastern University, Boston, MA, USA

    Ariel Hamlin

  2. Boston University, Boston, MA, USA

    Mayank Varia

Authors
  1. Ariel Hamlin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mayank Varia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ariel Hamlin .

Editor information

Editors and Affiliations

  1. Texas A&M University, College Station, TX, USA

    Juan A. Garay

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hamlin, A., Varia, M. (2021). Two-Server Distributed ORAM with Sublinear Computation and Constant Rounds. In: Garay, J.A. (eds) Public-Key Cryptography – PKC 2021. PKC 2021. Lecture Notes in Computer Science(), vol 12711. Springer, Cham. https://doi.org/10.1007/978-3-030-75248-4_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75248-4_18

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-75247-7

  • Online ISBN: 978-3-030-75248-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation