Overview
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.
Publications
- Ben Fisch, Vladimir Kolesnikov, Tal Malkin, Fernando Krell, Abishek Kumarasubramanian, Binh Vo and Steven M. Bellovin, "Malicious-Client Security in Blind Seer" In Proceedings of the 36th IEEE Symposium on Security & Privacy (S&P), May 2015, San Jose, CA.
- Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos D. Keromytis, and Steven M. Bellovin, "Blind Seer: A Scalable Private DBMS" In Proceedings of the 35th IEEE Symposium on Security & Privacy (S&P), May 2014, San Jose, CA.
- Vladimir Kolesnikov, Ranjit Kumaresan, "Improved OT Extension for Transferring Short Secrets". In Proceedings of the 33rd International Cryptology Conference (CRYPTO), August, 2013, Santa Barbara, CA.
- Tal Malkin, "Secure Computation for Big Data". In Proceedings of the Thery of Cryptography Conference (TCC), March, 2013, Tokyo, Japan. (Invited Talk)
- Vladimir Kolesnikov, Ranjit Kumaresan, Abdullatif Shikfa, "Efficient Verification of Input Consistency in Server-Assisted Secure Function Evaluation". In Proceedings of the 11th International Conference on Cryptology and Network Security (CANS), December, 2012, Darmstadt, Germany.
- Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, Yevgeniy Vahlis, "Secure Two-Party Computation with Sublinear (Amortized) Work". In Proceedings of the 19th ACM Conference on Computer and Communications Security (CCS), October, 2012, Raleigh, NC.
- Vladimir Kolesnikov, Ranjit Kumaresan "Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits". In Proceedings of the 8th Conference on Security and Cryptography for Networks (SCN), September, 2012, Amalfi, Italy.
- Vasilis Pappas, Mariana Raykova, Binh Vo, Steven M. Bellovin and Tal Malkin, "Private Search in the Real World". In Proceedings of the 27th Annual Computer Security Applications Conference (ACSAC), December, 2011, Orlando, FL.
Participants
- Tal Malkin (PI, Columbia University)
- Steven M. Bellovin (co-PI, Columbia University)
- Angelos D. Keromytis (co-PI, Columbia University)
- Vladimir Kolesnikov (co-PI, Bell Labs)
- Wesley George (visiting student, Columbia University)
- Fernando Krell (student, Columbia Univerisy)
- Vasilis Pappas (student, Columbia Univerisy)
- Mariana Raykova (student, Columbia Univerisy)
- Ben Fisch (student, Columbia Univerisy)
- Binh Vo (student, Columbia Univerisy)
- Seung Geol Choi (post-doc, Columbia Univerisy)