Communication publiée dans un ouvrage (Colloques, congrès, conférences scientifiques et actes)
Predicate encryption for multi-dimensional range queries from lattices
Gay, Romain; MEAUX, Pierrick; Wee, Hoeteck
2015 • In Katz, Jonathan (Ed.) Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
Inner product; Lattice-based; Learning with Errors; Multi dimensional; Multi-dimensional range queries; Predicate encryptions; Searching on encrypted data; Subset queries; Theoretical Computer Science; Computer Science (all)
Résumé :
[en] We construct a lattice-based predicate encryption scheme for multi-dimensional range and multi-dimensional subset queries. Our scheme is selectively secure and weakly attribute-hiding, and its security is based on the standard learning with errors (LWE) assumption. Multi-dimensional range and subset queries capture many interesting applications pertaining to searching on encrypted data. To the best of our knowledge, these are the first lattice-based predicate encryption schemes for functionalities beyond IBE and inner product.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Gay, Romain; ENS, Paris, France
MEAUX, Pierrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron ; ENS, Paris, France
Wee, Hoeteck; ENS, Paris, France
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Predicate encryption for multi-dimensional range queries from lattices
Date de publication/diffusion :
2015
Nom de la manifestation :
Public Key Cryptography
Lieu de la manifestation :
Gaithersburg, Usa
Date de la manifestation :
30-03-2015 => 01-04-2015
Manifestation à portée :
International
Titre de l'ouvrage principal :
Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
International Association for Cryptologic Research
Subventionnement (détails) :
P. Méaux— INRIA and ENS. Supported in part by ANR-13-JS02-0003 (Project CLE).H. Wee— ENS and CNRS. Supported in part by ANR-14-CE28-0003 (Project EnBiD), NSF Award CNS-1445424, ERC Project CryptoCloud (FP7/2007-2013 Grant Agreement no. 339563), the Alexander von Humboldt Foundation and a Google Faculty Research Award.
Agrawal, S., Boneh, D., Boyen, X.: Efficient Lattice (H)IBE in the Standard Model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010)
Agrawal, S., Boneh, D., Boyen, X.: Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 98–115. Springer, Heidelberg (2010)
Agrawal, S., Boyen, X., Vaikuntanathan, V., Voulgaris, P., Wee, H.: Functional Encryption for Threshold Functions (or, Fuzzy IBE) from Lattices. In: Public Key Cryptography, pp. 280–297 (2012)
Agrawal, S., Freeman, D.M., Vaikuntanathan, V.: Functional Encryption for Inner Product Predicates from Learning with Errors. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 21–40. Springer, Heidelberg (2011)
Ajtai, M.: Generating Hard Instances of Lattice Problems (Extended Abstract). In: STOC, pp. 99–108 (1996)
Alwen, J., Peikert, C.: Generating Shorter Bases for Hard Random Lattices. In: STACS, pp. 75–86 (2009)
Boneh, D., Waters, B.: Conjunctive, Subset, and Range Queries on Encrypted Data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535–554. Springer, Heidelberg (2007)
Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai Trees, or How to Delegate a Lattice Basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010)
De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry. Springer, Heidelberg (2000)
Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1), 97–139 (2008)
Gay, R., Méaux, P., Wee, H.: Predicate Encryption for Multi-Dimensional Range Queries from Lattices. Cryptology ePrint Archive, Report 2014/965 (2014), http:// eprint.iacr.org/
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for finegrained access control of encrypted data. In: ACM Conference on Computer and Communications Security, pp. 89–98 (2006)
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from oneway functions. In: STOC 1989 Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 12–24. ACM, New York (1989)
Katz, J., Sahai, A., Waters, B.: Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 146–162. Springer, Heidelberg (2008)
Micciancio, D., Peikert, C.: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC. pp. 84–93 (2005)
Shi, E., Bethencourt, J., Chan, H.T.H., Song, D.X., Perrig, A.: Multi-Dimensional Range Query over Encrypted Data. In: IEEE Symposium on Security and Privacy, pp. 350–364 (2007)
Xagawa, K.: Improved (Hierarchical) Inner-Product Encryption from Lattices. In: Public Key Cryptography, pp. 235–252 (2013)
