Government Research Program: Advancing Computation on Encrypted Data

• Mathematical Foundations of Fully Homomorphic Encryption – Discovery and development of new mathematical underpinnings for efficient computation on encrypted data is needed in a noninteractive setting. The solution might involve fully homomorphic encryption [Gentry09, Gentry10, Smart10] that allow noninteractive computation on encrypted data. This area is captured in RA-10-80, and interested proposers are referred to that solicitation.

• Mathematical Foundations of Secure Multiparty Computation – Discovery and development of new mathematical underpinnings for efficient computation on encrypted data is needed in an interactive setting. Secure multiparty computation [Yao86, Bickson10] has a rich history of interactive computation on encrypted data, but requires further improvements to be truly practical.

• Mathematical Foundations of Supporting Security Technologies – Computation on encrypted data preserves the confidentiality of the data being computed on, but does not inherently protect the integrity of the computation, nor provide strong protection of the program, among other potentially desirable security goals. Techniques to address these and other related security issues are sought in the PROCEED research effort.

• Implementation/Measurement/Optimization – To make computation on encrypted data practical, highly optimized implementations, possibly including programmable hardware, will be needed. Experience shows there can be at least an order of magnitude difference in the performance of highly optimized cryptography implementations over less sophisticated implementations.

• Algorithms – Practical computation on encrypted data will require libraries of data structures and algorithms that are optimized for efficiency in the encrypted domain. Most current approaches to computation on encrypted data work by turning a program (with a bounded maximum input size) into a circuit. An important goal for optimization is minimizing circuit depth, which is traditionally a goal of hardware designers, not programmers.

• Programming Languages – More advanced languages are sought, with type systems that embed cryptographic knowledge, making programming computation on encrypted data no more difficult than conventional programming. Today’s languages for computation on encrypted data, such as the one in the FairPlay system [Malkhi04] are simple, imperative languages that have little, if any, type system support for cryptography.

PROCEED will have a research integrator role to define a common cryptographic application programming interface (API), ensuring the compilers and cryptography implementations are interoperable and to support the Government’s evaluation team.

• Mathematical Foundations of Fully Homomorphic Encryption – Discovery and development of new mathematical underpinnings for efficient computation on encrypted data is needed in a noninteractive setting. The solution might involve fully homomorphic encryption [Gentry09, Gentry10, Smart10] that allow noninteractive computation on encrypted data. This area is captured in RA-10-80, and interested proposers are referred to that solicitation.

• Mathematical Foundations of Secure Multiparty Computation – Discovery and development of new mathematical underpinnings for efficient computation on encrypted data is needed in an interactive setting. Secure multiparty computation [Yao86, Bickson10] has a rich history of interactive computation on encrypted data, but requires further improvements to be truly practical.

• Mathematical Foundations of Supporting Security Technologies – Computation on encrypted data preserves the confidentiality of the data being computed on, but does not inherently protect the integrity of the computation, nor provide strong protection of the program, among other potentially desirable security goals. Techniques to address these and other related security issues are sought in the PROCEED research effort.

• Implementation/Measurement/Optimization – To make computation on encrypted data practical, highly optimized implementations, possibly including programmable hardware, will be needed. Experience shows there can be at least an order of magnitude difference in the performance of highly optimized cryptography implementations over less sophisticated implementations.

• Algorithms – Practical computation on encrypted data will require libraries of data structures and algorithms that are optimized for efficiency in the encrypted domain. Most current approaches to computation on encrypted data work by turning a program (with a bounded maximum input size) into a circuit. An important goal for optimization is minimizing circuit depth, which is traditionally a goal of hardware designers, not programmers.

• Programming Languages – More advanced languages are sought, with type systems that embed cryptographic knowledge, making programming computation on encrypted data no more difficult than conventional programming. Today’s languages for computation on encrypted data, such as the one in the FairPlay system [Malkhi04] are simple, imperative languages that have little, if any, type system support for cryptography.

PROCEED will have a research integrator role to define a common cryptographic application programming interface (API), ensuring the compilers and cryptography implementations are interoperable and to support the Government’s evaluation team.