Querying and Processing Encrypted Databases without Decrypting
Navy SBIR 2012.3 - Topic N123-160
SPAWAR - Ms. Elizabeth Altmann - firstname.lastname@example.org
Opens: August 27, 2012 - Closes: September 26, 2012
N123-160 TITLE: Querying and Processing Encrypted Databases without Decrypting
TECHNOLOGY AREAS: Information Systems
ACQUISITION PROGRAM: Computer Network Defense (ACAT IV)
OBJECTIVE: Develop an efficient means of cryptographically protecting databases while also processing without decryption.
DESCRIPTION: Cloud-computing is a cost-effective solution that outsources storage and computational instances. As the Navy transitions into a cloud environment with consolidated data centers, three confidentiality and integrity use cases are of interest: (1) data stored, (2) data being processed, and (3) data in transit to and from the data center. Strong cryptography and key management are solutions to cases (1) and (3), but case (2) is problematic. If encrypted data is to be decrypted in the cloud environment before processing, it can be susceptible to leakage and modification should the cloud environment be compromised. This poses serious security risks, especially if the data is sensitive. The decrypt-process-encrypt also adds computation complexity, or processing time. The research question is to explore possible solutions to query and process the data while still in its encrypted form. Another interest is to determine the strength of mechanism available through the use of cryptography in such a cloud-computing environment.
Of particular interest is the use case for a database element operation where a remote, autonomous, automated sensor provides an update, involving a mathematical operation. In this use case, an unclassified subscriber could update a classified data store. Examples include changes in course and speed, quantity on hand, or status. Another use case is secure transaction processing by wireless sensor grids.
Lattice or homomorphic encryption, which allows mathematical computations to be performed on encrypted data without compromising the encryption, is not new to the cryptography world. Existing cryptosystems such as El Gamal are considered homomorphic but with respect to either addition or multiplication operations. It was not until 2009 when fully homomorphic encryption was introduced that both addition and multiplication operations (thereby allowing every computation) could be made on encrypted data. Homomorphic encryption provides a suite of benefits. This proposal scopes research and development efforts to secure database transactions, heavily used by both government and industry.
PHASE I: Conceptualize and design an innovative solution to protecting database data using homomorphic encryption (whether partial or fully homomorphic) such that the query and processing of such data will not require decryption. The solution should be practical, in terms of a small footprint and high efficiency.
The phase 1 deliverable will address at least these factors:
PHASE II: Provide a practical implementation of the solution researched and designed in Phase I. Testing and evaluation should be accompanied to illustrate both feasibility and practicality.
PHASE III: Transition this technology into current Navy systems that house tactical databases.
PRIVATE SECTOR COMMERCIAL POTENTIAL/DUAL-USE APPLICATIONS: Databases are widely used in both the government and private sector. Financial institutions, in particular, would greatly benefit from the research and development efforts in homomorphic encryption, especially if transitioning to a cloud environment.
2 - Duc H. Tran, Wee Keong Ng, Hoon Wei Lim, and Hai-Long Nguyen. 2011. An efficient cacheable secure scalar product protocol for privacy-preserving data mining. In Proceedings of the 13th international conference on Data warehousing and knowledge discovery (DaWaK'11), Alfredo Cuzzocrea and Umeshwar Dayal (Eds.). Springer-Verlag, Berlin, Heidelberg, 354-366.
3 - Marten Van Dijk and Ari Juels. 2010. On the impossibility of cryptography alone for privacy-preserving cloud computing. In Proceedings of the 5th USENIX conference on Hot topics in security (HotSec'10). USENIX Association, Berkeley, CA, USA, 1-8.
4 - Sabrina Sicari, Luigi Alfredo Grieco, Gennaro Boggia, and Alberto Coen-Porisini. 2012. DyDAP: A dynamic data aggregation scheme for privacy aware wireless sensor networks. J. Syst. Softw. 85, 1 (January 2012), 152-166.
5 - Yu Yu; Leiwo, J.; Premkumar, B.; , "A Study on the Security of Privacy Homomorphism," Information Technology: New Generations, 2006. ITNG 2006. Third International Conference on , vol., no., pp.470-475, 10-12 April 2006
6 - Daniele Micciancio. 2011. The geometry of lattice cryptography. In Foundations of security analysis and design VI, Alessandro Aldini and Roberto Gorrieri (Eds.). Springer-Verlag, Berlin, Heidelberg 185-210.
7 - Yanping Xiao; Chuang Lin; Yixin Jiang; Xiaowen Chu; Fangqin Liu; , "An Efficient Privacy-Preserving Publish-Subscribe Service Scheme for Cloud Computing," GLOBECOM 2010, 2010 IEEE Global Telecommunications Conference , vol., no., pp.1-5, 6-10 Dec. 2010
8 - Vaikuntanathan, Vinod; , "Computing Blindfolded: New Developments in Fully Homomorphic Encryption," Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on , vol., no., pp.5-16, 22-25 Oct. 2011
9 - Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan. 2011. CryptDB: protecting confidentiality with encrypted query processing. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP '11). ACM, New York, NY, USA, 85-100.
KEYWORDS: lattice-based encryption; homomorphic encryption; encryption; data confidentiality; databases; query processing