Predicate Encryption for Multi-dimensional Range Queries from Lattices

Romain Gay (1, 2, 3) , Pierrick Méaux (3, 2, 1) , Hoeteck Wee (1, 2, 3)

1 ENS-PSL - École normale supérieure - Paris
2 LIENS - Laboratoire d'informatique de l'école normale supérieure
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities

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.

Domaines: Cryptographie et sécurité [cs.CR]

Romain Gay, Pierrick Méaux, Hoeteck Wee. Predicate Encryption for Multi-dimensional Range Queries from Lattices. PKC 2015 - Public-Key Cryptography, Apr 2015, Gaithersburg, United States. pp.752-776, ⟨10.1007/978-3-662-46447-2_34⟩. ⟨hal-01220353⟩