nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Practical Order-Revealing Encryption with Limited Leakage

verfasst von : Nathan Chenette, Kevin Lewi, Stephen A. Weis, David J. Wu

Erschienen in: Fast Software Encryption

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

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.

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 Modeling Random Oracles Under Unpredictable Queries

Nächstes Kapitel Strengthening the Known-Key Security Notion for Block Ciphers

This definition is inspired by the similar definition for PRF security [28], which compares the output of a keyed function to that of a truly random function.

This application was also observed and independently achieved by Goldwasser et al. [29] using indistinguishability obfuscation.

There are “mutable” order-preserving encryption schemes [35, 36, 42] that do satisfy IND-OCPA, but they require stateful encryption, and oftentimes, an interactive protocol to “update” ciphertexts. We survey some of these constructions in Sect. 1.2.

Either \(u_i + 1 = u_i' \pmod {3}\), in which case \(m < m'\), or \(u_i - 1 = u_i' \pmod {3}\), in which case \(m > m'\).

This is the only distribution for which we have concrete analysis of the leakage in any POPF-CCA secure scheme.

To date, the only concrete instantiations of indistinguishability obfuscation [4, 5, 24, 49] leverage multilinear maps.

If no reduction modulo \(M\) occurs in the \(\mathsf {ORE.Encrypt}\) encryption, then numerically comparing the transformed ciphertexts is identical to evaluating the \(\mathsf {ORE.Compare}\) procedure (since all relations hold over the integers).

In most cases, the security of the composed scheme is strictly greater than that of the base OPE scheme since our ORE construction provides semantic security for a single ciphertext, whereas existing OPE schemes generally do not.

Strictly speaking, the adversary they describe is for the window one-wayness experiment, but any adversary that succeeds in the window one-wayness experiment also succeeds in the generalized one-wayness experiment (Definition 4.1).

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

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

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

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)CrossRef

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)CrossRef

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)

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)CrossRef

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)CrossRef

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. 324(1), 71–90 (2003)MathSciNetCrossRefMATH

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)CrossRef

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)CrossRef

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)

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)CrossRef

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)

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)CrossRef

27.

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

28.

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

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)CrossRef

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)

31.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRefMATH

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)CrossRef

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)

36.

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

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)CrossRef

38.

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

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)

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)CrossRef

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)

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)

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)

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)

Titel: Practical Order-Revealing Encryption with Limited Leakage
verfasst von: Nathan Chenette
Kevin Lewi
Stephen A. Weis
David J. Wu
Verlag: Springer Berlin Heidelberg
Buch: Fast Software Encryption
Print ISBN: 978-3-662-52992-8

Electronic ISBN: 978-3-662-52993-5

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-52993-5_24

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"