Article

Practical Order-Revealing Encryption with Limited Leakage

Authors:

Nathan Chenette,

Stephen A. Weis,

David J. WuAuthors Info & Claims

FSE 2016: Revised Selected Papers of the 23rd International Conference on Fast Software Encryption - Volume 9783

Pages 474 - 493

https://doi.org/10.1007/978-3-662-52993-5_24

Published: 20 March 2016 Publication History

Abstract

In an order-preserving encryption scheme, the encryption algorithm produces ciphertexts that preserve the order of their plaintexts. Order-preserving encryption schemes have been studied intensely in the last decade, and yet not much is known about the security of these schemes. Very recently, Boneh etï źal. Eurocryptï ź2015 introduced a generalization of order-preserving encryption, called order-revealing encryption, and presented a construction which achieves this notion with best-possible security. Because their construction relies on multilinear maps, it is too impractical for most applications and therefore remains a theoretical result.

In this work, we build efficiently implementable order-revealing encryption from pseudorandom functions. We present the first efficient order-revealing encryption scheme which achieves a simulation-based security notion with respect to a leakage function that precisely quantifies what is leaked by the scheme. In fact, ciphertexts in our scheme are only about 1.6 times longer than their plaintexts. Moreover, we show how composing our construction with existing order-preserving encryption schemes results in order-revealing encryption that is strictly more secure than all preceding order-preserving encryption schemes.

References

[1]

Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order-preserving encryption for numeric data. In: SIGMOD, pp. 563---574 2004

Digital Library

[2]

Albrecht, M.R., Farshim, P., Hofheinz, D., Larraia, E., Paterson, K.G.: Multilinear maps from obfuscation. In: TCC 2016

[3]

Ananth, P., Jain, A.: Indistinguishability obfuscation from compact functional encryption. In: CRYPTO, pp. 308---326 2015

[4]

Applebaum, B., Brakerski, Z.: Obfuscating circuits via composite-order graded encoding. In: Dodis, Y., Nielsen, J.B. eds. TCC 2015, Part II. LNCS, vol. 9015, pp. 528---556. Springer, Heidelberg 2015

[5]

Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. In: Nguyen, P.Q., Oswald, E. eds. EUROCRYPT 2014. LNCS, vol. 8441, pp. 221---238. Springer, Heidelberg 2014

[6]

Binnig, C., Hildenbrand, S., Färber, F.: Dictionary-based order-preserving string compression for main memory column stores. In: ACM SIGMOD, pp. 283---296 2009

Digital Library

[7]

Boldyreva, A., Chenette, N., Lee, Y., O'Neill, A.: Order-preserving symmetric encryption. In: Joux, A. ed. EUROCRYPT 2009. LNCS, vol. 5479, pp. 224---241. Springer, Heidelberg 2009

[8]

Boldyreva, A., Chenette, N., O'Neill, A.: Order-preserving encryption revisited: improved security analysis and alternative solutions. In: Rogaway, P. ed. CRYPTO 2011. LNCS, vol. 6841, pp. 578---595. Springer, Heidelberg 2011

Digital Library

[9]

Boneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., Zimmerman, J.: Semantically secure order-revealing encryption: multi-input functional encryption without obfuscation. In: Oswald, E., Fischlin, M. eds. EUROCRYPT 2015. LNCS, vol. 9057, pp. 563---594. Springer, Heidelberg 2015

[10]

Boneh, D., Silverberg, A.: Applications of multilinear forms to cryptography. Contemp. Math. 3241, 71---90 2003

[11]

Boneh, D., Wu, D.J., Zimmerman, J.: Immunizing multilinear maps against zeroizing attacks. In: IACR Cryptology ePrint Archive 2014/930 2014

[12]

Brakerski, Z., Komargodski, I., Segev, G.: From single-input to multi-input functional encryption in the private-key setting. In: IACR Cryptology ePrint Archive 2015/158 2015

[13]

Bun, M., Zhandry, M.: Order-revealing encryption and the hardness of private learning. In: IACR Cryptology ePrint Archive 2015/417 2015

[14]

Chang, Y.-C., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A.D., Yung, M. eds. ACNS 2005. LNCS, vol. 3531, pp. 442---455. Springer, Heidelberg 2005

Digital Library

[15]

Chenette, N., Lewi, K., Weis, S.A., Wu, D.J.: Practical order-revealing encryption with limited leakage. In: IACR Cryptology ePrint Archive 2015/1125 2015

[16]

Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. eds. EUROCRYPT 2015. LNCS, vol. 9056, pp. 3---12. Springer, Heidelberg 2015

[17]

Cheon, J.H., Lee, C., Ryu, H.: Cryptanalysis of the new CLT multilinear maps. In: IACR Cryptology ePrint Archive 2011 Observation of strains: 934 2015

[18]

Coron, J.-S.: Cryptanalysis of GGH15 multilinear maps 2015

[19]

Coron, J.-S., Gentry, C., Halevi, S., Lepoint, T., Maji, H.K., Miles, E., Raykova, M., Sahai, A., Tibouchi, M.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: CRYPTO, pp. 247---266 2015

[20]

Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. eds. CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476---493. Springer, Heidelberg 2013

[21]

Coron, J.-S., de Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: CRYPTO, pp. 267---286 2015

[22]

Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: ACM CCS, pp. 79---88 2006

Digital Library

[23]

Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. eds. EUROCRYPT 2013. LNCS, vol. 7881, pp. 1---17. Springer, Heidelberg 2013

[24]

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40---49 2013

Digital Library

[25]

Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Fully secure functional encryption without obfuscation. In: IACR Cryptology ePrint Archive 2014/666 2014

[26]

Gentry, C., Gorbunov, S., Halevi, S.: Graph-induced multilinear maps from lattices. In: Dodis, Y., Nielsen, J.B. eds. TCC 2015, Part II. LNCS, vol. 9015, pp. 498---527. Springer, Heidelberg 2015

[27]

Goldreich, O.: The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, Cambridge 2001

Digital Library

[28]

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions extended abstract. In: FOCS, pp. 464---479 1984

Digital Library

[29]

Goldwasser, S., et al.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. eds. EUROCRYPT 2014. LNCS, vol. 8441, pp. 578---602. Springer, Heidelberg 2014

[30]

Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: STOC, pp. 555---564 2013

Digital Library

[31]

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 282, 270---299 1984

[32]

Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini, R., Canetti, R. eds. CRYPTO 2012. LNCS, vol. 7417, pp. 162---179. Springer, Heidelberg 2012

Digital Library

[33]

Hu, Y., Huiwen, J.: Cryptanalysis of GGH map. In: IACR Cryptology ePrint Archive 2015/301 2015

[34]

Kadhem, H., Amagasa, T., Kitagawa, H.: A secure and efficient order preserving encryption scheme for relational databases. In: KMIS, pp. 25---35 2010

[35]

Kerschbaum, F.: Frequency-hiding order-preserving encryption. In: ACM CCS, pp. 656---667 2015

Digital Library

[36]

Kerschbaum, F., Schröpfer, A.: Optimal average-complexity ideal-security order-preserving encryption. In: ACM CCS, pp. 275---286 2014

Digital Library

[37]

Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Nguyen, P.Q., Oswald, E. eds. EUROCRYPT 2014. LNCS, vol. 8441, pp. 239---256. Springer, Heidelberg 2014

[38]

Mavroforakis, C., Chenette, N., O'Neill, A., Kollios, G., Canetti, R.: Modular order-preserving encryption, revisited. In: ACM SIGMOD, pp. 763---777 2015

Digital Library

[39]

Minaud, B., Fouque, P.-A.: Cryptanalysis of the new multilinear map over the integers. In: IACR Cryptology ePrint Archive 2015/941 2015

[40]

Naveed, M., Kamara, S., Wright, C.V.: Inference attacks on property-preserving encrypted databases. In: CCS 2015

Digital Library

[41]

Pandey, O., Rouselakis, Y.: Property preserving symmetric encryption. In: Pointcheval, D., Johansson, T. eds. EUROCRYPT 2012. LNCS, vol. 7237, pp. 375---391. Springer, Heidelberg 2012

Digital Library

[42]

Popa, R.A., Li, F.H., Zeldovich, N.: An ideal-security protocol for order-preserving encoding. In: IEEE Symposium on Security and Privacy, pp. 463---477 2013

Digital Library

[43]

Popa, R.A., Redfield, C.M.S., Zeldovich, N., Balakrishnan, H.: Cryptdb: protecting confidentiality with encrypted query processing. In: SOSP, pp. 85---100 2011

Digital Library

[44]

Roche, D., Apon, D., Choi, S.G., Yerukhimovich, A.: POPE: Partial order-preserving encoding. In: Cryptology ePrint Archive, Report 2015/1106 2015

[45]

Sahai, A., Seyalioglu, H.: Worry-free encryption: functional encryption with public keys. In: ACM CCS, pp. 463---472 2010

Digital Library

[46]

Skyhigh Networks Inc. https://www.skyhighnetworks.com/. Accessed 11 Dec 2015

[47]

Teranishi, I., Yung, M., Malkin, T.: Order-preserving encryption secure beyond one-wayness. In: Sarkar, P., Iwata, T. eds. ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 42---61. Springer, Heidelberg 2014

[48]

Xiao, L., Yen, I-L., Huynh, D.T.: Extending order preserving encryption for multi-user systems. In: IACR Cryptology ePrint Archive, 2011 Observation of strains: 192 2012

[49]

Zimmerman, J.: How to obfuscate programs directly. In: Oswald, E., Fischlin, M. eds. EUROCRYPT 2015. LNCS, vol. 9057, pp. 439---467. Springer, Heidelberg 2015

Cited By

Karn RNawaz KElfadel IDe V(2024)Order-Preserving Cryptography for the Confidential Inference in Random Forests: FPGA Design and ImplementationProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3658481(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3658481
Peng CChen RWang YHe DHuang X(2024)Parameter-Hiding Order-Revealing Encryption Without PairingsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57728-4_8(227-256)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57728-4_8
Berger RDörre FKoch A(2024)Two-Party Decision Tree Training from Updatable Order-Revealing EncryptionApplied Cryptography and Network Security10.1007/978-3-031-54770-6_12(288-317)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_12
Show More Cited By

Practical Order-Revealing Encryption with Limited Leakage

Recommendations

Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) scheme (...
Practical leakage-resilient identity-based encryption from simple assumptions
CCS '10: Proceedings of the 17th ACM conference on Computer and communications security

We design the first Leakage-Resilient Identity-Based Encryption (LR-IBE) systems from static assumptions in the standard model. We derive these schemes by applying a hash proof technique from Alwen et.al. (Eurocrypt '10) to variants of the existing IBE ...
Leakage-resilient certificate-based encryption

Certificate-based encryption is a new cryptography primitive, which can be used to construct efficient public key infrastructure. However, side-channel attacks are not considered in certificate-based encryption. In order to capture these attacks, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FSE 2016: Revised Selected Papers of the 23rd International Conference on Fast Software Encryption - Volume 9783

March 2016

568 pages

ISBN:9783662529928

Editor:
Thomas Peyrin
Nanyang Technological University, Singapore, Singapore

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 March 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Karn RNawaz KElfadel IDe V(2024)Order-Preserving Cryptography for the Confidential Inference in Random Forests: FPGA Design and ImplementationProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3658481(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3658481
Peng CChen RWang YHe DHuang X(2024)Parameter-Hiding Order-Revealing Encryption Without PairingsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57728-4_8(227-256)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57728-4_8
Berger RDörre FKoch A(2024)Two-Party Decision Tree Training from Updatable Order-Revealing EncryptionApplied Cryptography and Network Security10.1007/978-3-031-54770-6_12(288-317)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54770-6_12
Li F(2023)Modernization of Databases in the Cloud Era: Building Databases that Run Like LegosProceedings of the VLDB Endowment10.14778/3611540.361163916:12(4140-4151)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.14778/3611540.3611639
Pennekamp JDahlmanns MFuhrmann FHeutmann TKreppein AGrunert DLange CSchmitt RWehrle K(2023)Offering Two-way Privacy for Evolved Purchase InquiriesACM Transactions on Internet Technology10.1145/359996823:4(1-32)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3599968
Hu DWang QYan SLiu XLi MZheng S(2023)Reversible Database Watermarking Based on Order-preserving Encryption for Data SharingACM Transactions on Database Systems10.1145/358976148:2(1-25)Online publication date: 13-May-2023
https://dl.acm.org/doi/10.1145/3589761
Ren XSu LGu ZWang SLi FXie YBian SLi CZhang F(2022)HEDAProceedings of the VLDB Endowment10.14778/3574245.357424816:4(601-614)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574248
Wang SLi YLi HLi FTian CSu LZhang YMa YYan LSun YCheng XXie XZou Y(2022)OperonProceedings of the VLDB Endowment10.14778/3554821.355482615:12(3332-3345)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.14778/3554821.3554826
Wang ZDing XJin HZhou P(2022)Efficient secure and verifiable location-based skyline queries over encrypted dataProceedings of the VLDB Endowment10.14778/3538598.353860515:9(1822-1834)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.14778/3538598.3538605
Roy Chowdhury ADing BJha SLiu WZhou JYin HStavrou ACremers CShi E(2022)Strengthening Order Preserving Encryption with Differential PrivacyProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560610(2519-2533)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560610
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten