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:
� Cryptographic processes utilized, including key management
� Database structures to which this method might be applied (e.g., relational, structured, unstructured)
� Operations (add, multiple, etc) possible vs. complexity
� Strength of mechanism � as generally defined in ISO 15408 and how it might be evaluated
� Computational comparison with traditional decrypt-process-encrypt process
� Description of potential solutions for both use cases described above

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.

REFERENCES:
1 - Suat Ozdemir and Yang Xiao. 2011. Integrity protecting hierarchical concealed data aggregation for wireless sensor networks. Comput. Netw. 55, 8 (June 2011), 1735-1746.

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

** TOPIC AUTHOR (TPOC) **

DoD Notice:   Between July 26 and August 26, 2012, you may talk directly with the Topic Authors (TPOC) to ask technical questions about the topics. Their contact information is listed above. For reasons of competitive fairness, direct communication between proposers and topic authors is not allowed starting August 27, 2012, , when DoD begins accepting proposals for this solicitation.

However, proposers may still submit written questions about solicitation topics through the DoD's SBIR/STTR Interactive Topic Information System (SITIS), in which the questioner and respondent remain anonymous and all questions and answers are posted electronically for general viewing until the solicitation closes. All proposers are advised to monitor SITIS (12.3 Q&A) during the solicitation period for questions and answers, and other significant information, relevant to the SBIR 12.3 topic under which they are proposing.

If you have general questions about DoD SBIR program, please contact the DoD SBIR Help Desk at (866) 724-7457 .

Return