×

Parameter-hiding order revealing encryption. (English) Zbl 1440.68055

Peyrin, Thomas (ed.) et al., Advances in cryptology – ASIACRYPT 2018. 24th international conference on the theory and application of cryptology and information security, Brisbane, QLD, Australia, December 2–6, 2018. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 11272, 181-210 (2018).
Summary: Order-revealing encryption (ORE) is a primitive for outsourcing encrypted databases which allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with [M. Naveed et al., in: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, CCS 2015. New York, NY: Association for Computing Machinery (ACM). 644–655 (2015; doi:10.1145/2810103.2813651)], have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.
For the entire collection see [Zbl 1402.94008].

MSC:

68P15 Database theory
68P25 Data encryption (aspects in computer science)
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abraham, I.; Fletcher, CW; Nayak, K.; Pinkas, B.; Ren, L.; Fehr, S., Asymptotically tight bounds for composing ORAM with PIR, Public-Key Cryptography - PKC 2017, 91-120 (2017), Heidelberg: Springer, Heidelberg · Zbl 1404.94033 · doi:10.1007/978-3-662-54365-8_5
[2] Ajtai, M.: Oblivious RAMs without cryptographic assumptions. In: STOC (2010) · Zbl 1293.68120
[3] Chan, T-HH; Guo, Y.; Lin, W-K; Shi, E.; Takagi, T.; Peyrin, T., Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM, Advances in Cryptology - ASIACRYPT 2017, 660-690 (2017), Cham: Springer, Cham · Zbl 1420.94048 · doi:10.1007/978-3-319-70694-8_23
[4] Chan, T.-H.H., Guo, Y., Lin, W.K., Shi, E.: Cache-oblivious and data-oblivious sorting and applications. In: SODA (2018) · Zbl 1403.68048
[5] Chan, T.-H.H., Katz, J., Nayak, K., Polychroniadou, A., Shi, E.: More is less: Perfectly secure oblivious algorithms in the multi-server setting. CoRR, abs/1809.00825 (2018) · Zbl 1447.94025
[6] Chan, T.-H.H., Nayak, K., Shi, E.: Perfectly secure oblivious parallel RAM. In: TCC (2018) · Zbl 1430.94063
[7] Chan, T.-H.H., Shi, E.: Circuit OPRAM: a unifying framework for computationally and statistically secure ORAMs and OPRAMs. In: TCC (2017) · Zbl 1416.68015
[8] Chung, K-M; Liu, Z.; Pass, R.; Sarkar, P.; Iwata, T., Statistically-secure ORAM with \(\tilde{O}(\log^2 n)\) overhead, Advances in Cryptology - ASIACRYPT 2014, 62-81 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94097 · doi:10.1007/978-3-662-45608-8_4
[9] Damgård, I.; Meldgaard, S.; Nielsen, JB; Ishai, Y., Perfectly secure oblivious RAM without random oracles, Theory of Cryptography, 144-163 (2011), Heidelberg: Springer, Heidelberg · Zbl 1295.94046 · doi:10.1007/978-3-642-19571-6_10
[10] Demertzis, I.; Papadopoulos, D.; Papamanthou, C.; Shacham, H.; Boldyreva, A., Searchable encryption with optimal locality: achieving sublogarithmic read efficiency, Advances in Cryptology - CRYPTO 2018, 371-406 (2018), Cham: Springer, Cham · Zbl 1444.94061 · doi:10.1007/978-3-319-96884-1_13
[11] Knuth, D.E.: The Art of Computer Programming, Volume 2 (3rd edn.): Seminumerical Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston (1997). ISBN: 0-201-89684-2 · Zbl 0883.68015
[12] Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: STOC (1987)
[13] Goldreich, O.; Ostrovsky, R., Software protection and simulation on oblivious RAMs, J. ACM, 43, 3, 431-473 (1996) · Zbl 0885.68041 · doi:10.1145/233551.233553
[14] Goodrich, M.T.: Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data. In: SPAA (2011)
[15] Goodrich, MT; Mitzenmacher, M.; Aceto, L.; Henzinger, M.; Sgall, J., Privacy-preserving access of outsourced data via oblivious RAM simulation, Automata, Languages and Programming, 576-587 (2011), Heidelberg: Springer, Heidelberg · Zbl 1333.68100 · doi:10.1007/978-3-642-22012-8_46
[16] Gordon, D., Katz, J., Wang, X.: Simple and efficient two-server ORAM. In: Asiacrypt (2018) · Zbl 1447.94040
[17] Hoang, T., Ozkaptan, C.D., Yavuz, A.A., Guajardo, J., Nguyen, T.: S3ORAM: a computation-efficient and constant client bandwidth blowup ORAM with shamir secret sharing. In: CCS (2017)
[18] Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. In: SODA (2012) · Zbl 1422.68061
[19] Kushilevitz, E., Mour, T.: Sub-logarithmic distributed oblivious RAM with small block size. CoRR, abs/1802.05145 (2018) · Zbl 1465.94075
[20] Lin, W.-K., Shi, E., Xie, T.: Can we overcome the \(n \log n\) barrier for oblivious sorting? Cryptology ePrint Archive, Report 2018/227 (2018)
[21] Lu, S.; Ostrovsky, R.; Sahai, A., Distributed oblivious RAM for secure two-party computation, Theory of Cryptography, 377-396 (2013), Heidelberg: Springer, Heidelberg · Zbl 1315.94088 · doi:10.1007/978-3-642-36594-2_22
[22] Raskin, M., Simkin, M.: Oblivious RAM with small storage overhead. Cryptology ePrint Archive, Report 2018/268 (2018). https://eprint.iacr.org/2018/268 · Zbl 1455.94188
[23] Ren, L., et al.: Constants count: practical improvements to oblivious RAM. In: USENIX Security Symposium, pp. 415-430 (2015)
[24] Shi, E.; Chan, T-HH; Stefanov, E.; Li, M.; Lee, DH; Wang, X., Oblivious RAM with O((logN)^3) worst-case cost, Advances in Cryptology - ASIACRYPT 2011, 197-214 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.68025 · doi:10.1007/978-3-642-25385-0_11
[25] Stefanov, E., Shi, E.: Multi-cloud oblivious storage. In: CCS (2013)
[26] Stefanov, E., et al.: Path ORAM - an extremely simple oblivious RAM protocol. In: CCS (2013) · Zbl 1426.68008
[27] Tople, S., Dang, H., Saxena, P., Chang, E.-C.: Permuteram: Optimizing oblivious computation for efficiency. Cryptology ePrint Archive, Report 2017/885 (2017)
[28] Wang, X.S., Chan, T.-H.H., Shi, E.: Circuit ORAM: on tightness of the Goldreich-Ostrovsky lower bound. In: ACM CCS (2015)
[29] Hofheinz, D.; Jager, T.; Safavi-Naini, R.; Canetti, R., Tightly secure signatures and public-key encryption, Advances in Cryptology - CRYPTO 2012, 590-607 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94152 · doi:10.1007/978-3-642-32009-5_35
[30] Hofheinz, D.; Kiltz, E.; Menezes, A., Secure hybrid encryption from weakened key encapsulation, Advances in Cryptology - CRYPTO 2007, 553-571 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94051 · doi:10.1007/978-3-540-74143-5_31
[31] Hofheinz, D.; Koch, J.; Striecks, C.; Katz, J., Identity-based encryption with (almost) tight security in the multi-instance, multi-ciphertext setting, Public-Key Cryptography - PKC 2015, 799-822 (2015), Heidelberg: Springer, Heidelberg · Zbl 1345.94069 · doi:10.1007/978-3-662-46447-2_36
[32] Jutla, CS; Ohkubo, M.; Roy, A.; Abdalla, M.; Dahab, R., Improved (almost) tightly-secure structure-preserving signatures, Public-Key Cryptography - PKC 2018, 123-152 (2018), Cham: Springer, Cham · Zbl 1406.94069 · doi:10.1007/978-3-319-76581-5_5
[33] Jutla, CS; Roy, A.; Sako, K.; Sarkar, P., Shorter quasi-adaptive NIZK proofs for linear subspaces, Advances in Cryptology - ASIACRYPT 2013, 1-20 (2013), Heidelberg: Springer, Heidelberg · Zbl 1300.94072 · doi:10.1007/978-3-642-42033-7_1
[34] Kiltz, E.; Wee, H.; Oswald, E.; Fischlin, M., Quasi-adaptive NIZK for linear subspaces revisited, Advances in Cryptology - EUROCRYPT 2015, 101-128 (2015), Heidelberg: Springer, Heidelberg · Zbl 1326.94103 · doi:10.1007/978-3-662-46803-6_4
[35] Kurosawa, K.; Desmedt, Y.; Franklin, M., A new paradigm of hybrid encryption scheme, Advances in Cryptology - CRYPTO 2004, 426-442 (2004), Heidelberg: Springer, Heidelberg · Zbl 1104.94028 · doi:10.1007/978-3-540-28628-8_26
[36] Lewko, A.; Waters, B.; Nguyen, PQ; Oswald, E., Why proving HIBE systems secure is difficult, Advances in Cryptology - EUROCRYPT 2014, 58-76 (2014), Heidelberg: Springer, Heidelberg · Zbl 1326.94109 · doi:10.1007/978-3-642-55220-5_4
[37] Libert, B.; Joye, M.; Yung, M.; Peters, T.; Sarkar, P.; Iwata, T., Concise multi-challenge CCA-secure encryption and signatures with almost tight security, Advances in Cryptology - ASIACRYPT 2014, 1-21 (2014), Heidelberg: Springer, Heidelberg · Zbl 1311.94107 · doi:10.1007/978-3-662-45608-8_1
[38] Libert, B.; Peters, T.; Joye, M.; Yung, M.; Iwata, T.; Cheon, JH, Compactly hiding linear spans, Advances in Cryptology - ASIACRYPT 2015, 681-707 (2015), Heidelberg: Springer, Heidelberg · Zbl 1380.94112 · doi:10.1007/978-3-662-48797-6_28
[39] Morillo, P.; Ràfols, C.; Villar, JL; Cheon, JH; Takagi, T., The kernel matrix Diffie-Hellman assumption, Advances in Cryptology - ASIACRYPT 2016, 729-758 (2016), Heidelberg: Springer, Heidelberg · Zbl 1404.94100 · doi:10.1007/978-3-662-53887-6_27
[40] Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS, pp. 458-467. IEEE Computer Society Press, October 1997
[41] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: 22nd ACM STOC, pp. 427-437. ACM Press, May 1990
[42] Shoup, V., Shoup, V.: Why chosen ciphertext security matters. IBM research report RZ 3076 (1998) · Zbl 0919.94031
[43] Wang, Y.; Matsuda, T.; Hanaoka, G.; Tanaka, K.; Nielsen, JB; Rijmen, V., Memory lower bounds of reductions revisited, Advances in Cryptology - EUROCRYPT 2018, 61-90 (2018), Cham: Springer, Cham · Zbl 1423.94113 · doi:10.1007/978-3-319-78381-9_3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.