• 02/10/2014: We got a paper accepted in IEEE S&P!
  • 10/17/2012: We presented a paper in CCS!
  • 01/14/2012: The website is online!



Efficient, secure and private information access is critical to today’s business and defense operations. While the need for data protection is clear, the queries must be protected as well, since they may reveal insights of the requester’s interests, agenda, mode of operation, etc. Thus, there is a clear need for efficient and secure systems and mechanisms of database access, which allow execution of complex queries, and guarantee protection to both server and client. We propose to develop such a system.

We build on our existing successful solution, SADS, which relies on encrypted Bloom Filters (BF) and novel reroutable encryption to achieve simple keyword searches. In this work, we propose to expand and enhance our previous work to handle far more complicated queries, support verifiable and private compliance checking, and maintain high performance even for very large databases. Our proposed work builds on the above foundation and relies on several new ideas.

  • First, our main tool will again be the encrypted BF; we will design novel BF population and matching algorithms, which will allow for secure querying based on combinations of basic keywords. We will then design and apply various heuristics and data representation and tokenization to extend this power to range, wildcard, and other queries.
  • Some of our subprotocols will be implemented using Yao’s Garbled Circuit (GC) technique. Our innovation will come via techniques for seamless integration of BF- and GC-based secure computations. In particular, this will prove useful in secure query compliance checking. Using our technique, a user-submitted encrypted BF query will be checked for compliance using a policy implemented with GC. Later, if approved by Policy Checker, the same query will be executed, efficiently preventing Client’s query substitution – a dangerous malicious behavior.
  • Our third avenue of innovation aims for elimination of helper third parties. This will involve application of (and possibly enhancements to) proxy re-encryption schemes, which are cryptosystems allowing third-parties (proxies) to convert a ciphertext which has been encrypted with party P1’s public key, into one which may be decrypted by another party P2. Using this tool, the (single) server in possession of the searchable encrypted DB will be able to perform a search and to re-encrypt the obtained result for decryption with the client’s key.



This work is supported by the Intelligence Advanced Research Projects Activity (IARPA) via DoI/NBC contract number D11PC20194. Opinions, findings, conclusions and recommendations expressed in this material are those of the authors and do not necessarily reflect the position or the policy of the US Government, IARPA, or DoI/NBS, and no official endorsement should be inferred.
© Vasilis Pappas, Columbia University