Paper 2021/1227

Efficient Boolean Search over Encrypted Data with Reduced Leakage

Sarvar Patel, Giuseppe Persiano, Joon Young Seo, and Kevin Yeo


Encrypted multi-maps enable outsourcing the storage of a multi-map to an untrusted server while maintaining the ability to query privately. We focus on encrypted Boolean multi-maps that support arbitrary Boolean queries over the multi-map. Kamara and Moataz [Eurocrypt’17] presented the first encrypted multi-map, BIEX, that supports CNF queries with optimal communication, worst-case sublinear search time and non-trivial leakage. We improve on previous work by presenting a new construction CNFFilter for CNF queries with significantly less leakage than BIEX, while maintaining both optimal communication and worst-case sublinear search time. As a direct consequence our construction shows additional resistance to leakage-abuse attacks in comparison to prior works. For most CNF queries, CNFFilter avoids leaking the result sets for any singleton queries for labels appearing in the CNF query. As an example, for the CNF query of the form (l1 ∨ l2) ∧ l3, our scheme does not leak the result sizes of queries to l1, l2 or l3 individually. On the other hand, BIEX does leak some of this information. This is just an example of the reduced leakage obtained by CNFFilter. The core of CNFFilter is a new filtering algorithm that performs set intersections with significantly less leakage compared to prior works. We implement CNFFilter and show that CNFFilter achieves faster search times and similar communication overhead compared to BIEX at the cost of a small increase in server storage.

Available format(s)
Publication info
Published elsewhere. Minor revision. Asiacrypt 2021
Contact author(s)
sarvar @ google com
giuper @ gmail com
jyseo @ google com
kwlyeo @ google com
2021-09-20: received
Short URL
Creative Commons Attribution


      author = {Sarvar Patel and Giuseppe Persiano and Joon Young Seo and Kevin Yeo},
      title = {Efficient Boolean Search over Encrypted Data with Reduced Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1227},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.