Paper 2018/551

Structured Encryption and Leakage Suppression

Seny Kamara, Tarik Moataz, and Olga Ohrimenko


Structured encryption (STE) schemes encrypt data structures in such a way that they can be privately queried. One aspect of STE that is still poorly understood is its leakage. In this work, we describe a general framework to design STE schemes that do not leak the query/search pattern (i.e., if and when a query was previously made). Our framework consists of two compilers. The first can be used to make any dynamic STE scheme rebuildable in the sense that the encrypted structures it produces can be rebuilt efficiently using only O(1) client storage. The second transforms any rebuildable scheme that leaks the query/search pattern into a new scheme that does not. Our second compiler is a generalization of Goldreich and Ostrovsky's square root oblivious RAM (ORAM) solution but does not make use of black-box ORAM simulation. We show that our framework produces STE schemes with query complexity that is asymptotically better than ORAM simulation in certain (natural) settings and comparable to special-purpose oblivious data structures. We use our framework to design a new STE scheme that is ``almost" zero-leakage in the sense that it reveals an, intuitively-speaking, small amount of information. We also show how the scheme can be used to achieve zero-leakage queries when one can tolerate a probabilistic guarantee of correctness. This construction results from applying our compilers to a new STE scheme we design called the piggyback scheme. This scheme is a general-purpose STE construction (in the sense that it can encrypt any data structure) that leaks the search/query pattern but hides the response length on non-repeating queries.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2018
structured encryptionsearchable symmetric encryptionleakagesquare root solution
Contact author(s)
seny @ brown edu
tarik_moataz @ brown edu
oohrim @ microsoft com
2018-06-04: received
Short URL
Creative Commons Attribution


      author = {Seny Kamara and Tarik Moataz and Olga Ohrimenko},
      title = {Structured Encryption and Leakage Suppression},
      howpublished = {Cryptology ePrint Archive, Paper 2018/551},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.