07-12-2012, 11:37 AM
Computing Arbitrary Functions of Encrypted Data
Computing Arbitrary.pdf (Size: 377.37 KB / Downloads: 61)
ABSTRACT
Suppose that you want to delegate the ability to process
your data, without giving away access to it. We show that
this separation is possible: we describe a "fully
homomorphic" encryption scheme that keeps data private,
but that allows a worker that does not have the secret
decryption key to compute any (still encrypted) result of the
data, even when the function of the data is very complex. In
short, a third party can perform complicated processing of
data without being able to see it. Among other things, this
helps make cloud computing compatible with privacy.
Introduction
Is it possible to delegate processing of your data without giving away access to it?
This question, which tests the tension between convenience and privacy, has always been
important, but seems especially so now that we are headed toward widespread use of cloud
computing. To put everything online "in the cloud," unencrypted, is to risk an Orwellian
future. For certain types of data, such as medical records, storing them off-site unencrypted
may be illegal. On the other hand, encrypting one's data seems to nullify the benefits of cloud
computing. Unless I give the cloud my secret decryption key (sacrificing my privacy), what can
I expect the cloud to do with my encrypted data except send it back to me, so that I can decrypt
it and process it myself?
Homomorphic Encryption
Alice's jewelry store
At first, the notion of processing data without having access to it may seem paradoxical, even
logically impossible. To convince you that there is no fallacy, and to give you some intuition
about the solution, let us consider an analogous problem in (a fictional version of) the
"physical world."
Alice owns a jewelry store. She has raw precious materials—gold, diamonds, silver, etc.—that
she wants her workers to assemble into intricately designed rings and necklaces. But she
distrusts her workers and assumes that they will steal her jewels if given the opportunity. In
other words, she wants her workers to process the materials into finished pieces, without
giving them access to the materials. What does she do?
Here is her plan. She uses a transparent impenetrable glovebox, secured by a lock for which
only she has the key. She puts the raw precious materials inside the box, locks it, and gives it to
a worker. Using the gloves, the worker assembles the ring or necklace inside the box. Since the
box is impenetrable, the worker cannot get to the precious materials, and figures he might as
well return the box to Alice, with the finished piece inside. Alice unlocks the box with her key
and extracts the ring or necklace. In short, the worker processes the raw materials into a
finished piece, without having true access to the materials.
Homomorphic encryption: functionality
An encryption scheme ε has three algorithms: KeyGen , Encrypt , and Decrypt , all of which
must be efficient—that is, run in time poly(λ), polynomial in a security parameter λ that
specifies the bit-length of the keys. In a symmetric, or secret key, encryption scheme, KeyGen
uses λ to generate a single key that is used in both Encrypt and Decrypt , first to map a
message to a ciphertext, and then to map the ciphertext back to the message. In an
asymmetric, or public key, encryption scheme, KeyGen uses λ to generate two keys—a public
encryption key pk, which may be made available to everyone, and a secret decryption key sk.
As a physical analogy for an asymmetric encryption scheme, one can think of Alice's public key
as a padlock, which she constructs and distributes, that can be locked without a key. Anyone
can put a message inside a box secured by Alice's padlock (encrypt), and mail it via a public
channel to Alice, but only Alice has the key needed to unlock it (decrypt).
Homomorphic encryption: security
In terms of security, the weakest requirement for an encryption scheme is one-wayness: given
the public key pk and a ciphertext c that encrypts unknown message m under pk, it should be
"hard" to output m. "Hard" means that any algorithm or "adversary" A that runs in poly(λ)
time has a negligible probability of success over the choices of pk and m (i.e., the probability it
outputs m is less than 1/λ for any constant k).
Nowadays, we typically require an encryption scheme to have a stronger security property,
called semantic security against chosen-plaintext attacks (CPA) : given a ciphertext c that
encrypts either m or m , it is hard for an adversary to decide which, even if it is allowed to
choose m and m . Here, "hard" means that if the adversary A runs in polynomial time and
guesses correctly with probability 1/2 + , then , called A's advantage, must be negligible. If
this advantage is nonnegligible, then we say (informally) that the adversary breaks the
semantic security of the encryption scheme.