Friday, July 16, 2010

New DARPA Programs in Cryptography

DARPA-BAA-10-81: PROgramming Computation on EncryptEd Data
DARPA-RA-10-80: PROgramming Computation on EncryptEd Data
Frequently Asked Questions

Initial Responses due August 24, 2010.
Here is some relevent text:

The goal of the PROCEED research effort is to develop practical
methods for computation on encrypted data without decrypting the data
and to develop modern programming languages to describe these
computations. PROCEED is a comprehensive research effort with six
primary research thrusts:

- 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.1 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