technical Perspective
A first Glimpse of
Cryptography’s holy Grail
By daniele Micciancio

WE aLL Kno W how to protect our private or most valuable data from unauthorized access: encrypt it. When a piece of data M is encrypted under a key K to yield a ciphertext C=EncK(M), only the intended recipient (who knows the corresponding secret decryption key S) will be able to invert the encryption function and recover the original plain-text using the decryption algorithm DecS(C)=DecS(EncK(M))=M.

Encryption today—in both symmetric (where S=K) and public key versions (where S remains secret even when K is made publicly available)—is widely used to achieve confidentiality in many important and well-known applications: online banking, electronic shopping, and virtual private networks are just a few of the most common applications using encryption, typically as part of a larger protocol, like the TLS protocol used to secure communication over the Internet.

Still, the use of encryption to protect valuable or sensitive data can be very limiting and inflexible. Once the data M is encrypted, the corresponding ciphertext C behaves to a large extent as a black box: all we can do with the box is keep it closed or opened in order to access and operate on the data.

In many situations this may be
exactly what we want. For example,
take a remote storage system, where
we want to store a large collection of
documents or data files. We store the
data in encrypted form, and when we
want to access a specific piece of data,
we retrieve the corresponding cipher-
text, decrypting it locally on our own
trusted computer. But as soon as we
go beyond the simple data storage/
retrieval model, we are in trouble. Say
we want the remote system to provide
a more complex functionality, like a
database system capable of indexing
and searching our data, or answering
complex relational or semistructured
queries. Using standard encryption
technology we are immediately faced
with a dilemma: either we store our
data unencrypted and reveal our pre-
cious or sensitive data to the storage/
database service provider, or we en-
crypt it and make it impossible for the
provider to operate on it.

Daniele Micciancio is a professor in the computer science and engineering department at the university of California, san Diego.