Paper 2021/229

Fast Boolean Queries with Minimized Leakage for Encrypted Databases in Cloud Computing

Zhiqiang Wu, Kenli Li, Keqin Li, and Jin Wang


This research revisits the fundamental problem of processing privacy-preserving Boolean queries over outsourced databases on untrusted public clouds. Many current Searchable Encryption (SE) schemes try to seek an appropriate trade-off between security and efficiency, yet most of them suffer from an unacceptable query leakage due to their conjunctive/disjunctive terms that are processed individually. We show, however, this trade-off still can be deeply optimized for more security. We consider a Boolean formula as a set of deterministic finite automatons (DFAs) and propose a novel approach to running an encrypted DFA, which can be effectively and efficiently processed by the cloud. We give three constructions for conjunctive, disjunctive, and Boolean queries, respectively. Their notable advantages are single-round, highly-efficient, adaptively-secure, and leakage-minimized. A lot of experiments are made to evaluate overall efficiency. Testing results show that the schemes achieve enhanced security almost without sacrificing anything of search efficiency.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.IEEE Access
Cloud ComputingPrivacy PreservingSearchable Encryption.
Contact author(s)
wzq @ csust edu cn
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Zhiqiang Wu and Kenli Li and Keqin Li and Jin Wang},
      title = {Fast Boolean Queries with Minimized Leakage for Encrypted Databases in Cloud Computing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/229},
      year = {2021},
      doi = {10.1109/ACCESS.2019.2910457},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.