Practical applications of homomorphic encryption algorithms?

Question

It appears there there were interesting things going on in cryptography: the first homomorphic encryption scheme appeared recently (explanation, HT). Roughly speaking, it is a way of encoding x into f(x) such that you can compute f(x+y) easily knowing f(x) and f(y) even though you can't easily restore x and y (and same for f(x*y)).

What are practical applications for schemes of this type (once their security has been established)? To me, it appears they could make writing algorithms for manipulating private data much easier.

Here are my thoughts:

1. electronic voting
2. checking the integrity of private data
3. is there a chance that would help privacy in general?

Example: I have accounts with Banks A, B, C. Entity X wants to confirm I have more than $1000 total; it would happily accept statements from Banks A, B, C or D, but unfortunately I don't have enough money in any single account. Bank A encrypts the info about my $500 dollars with my public key; similarly, Banks B and C encrypt the info that I have $200 and $300 respectively. They send these data to X who adds them to some number which I demonstrate to be in fact encrypted $1000 (by encrypting $1000 with my public key and demonstrating that the result is the same). I have proved something without disclosing to X how much money I have in each account.

Another example: Good citizens X_1, ... , X_n are teaming up to select one of two candidates, one of which is latte-drinking liberAl while another is a Bible-bearing gun lover (all names are fictional). They decide they want the voting to be private but quick. They send their votes in the vector format (1, vote_A, vote_B, vote_None) encrypted to the Election Commission which adds them publicly and obtains the result in the form (count, count_A, count_B, count_None). After checking that count = count_A + count_B + count_None, the officials declare the victory of one of the candidates, after which the election is declared invalid by the judge for some reason unrelated to electronic voting and fought in the court for the next 10 years, but, hey, that's not my problem anyway.

Notes: - I believe those particular example was possible with RSA even before, since it only requires homomorphicity in one operation. The hope is that we can have radically more interesting things with more operations -- so, come up with examples!

• I would especially like to see answers containing code and/or developing frameworks that have a chance of being used in practice, the reason being SO is not a theoretical computer science discussion board.

• The homomorphic algorithm, to repeat what was said below in comments, allows to to create a program that would manage data without knowing them. Unfortunately, the types of programs are somewhat limited: you can't have if (x=0) ... because x is encrypted, and each step is very slow (there are some lattices involved).

Answer 1

As a PKI geek, if the homomorphic cryptofunction were also an assymmetric key system, then you have some really interesting possibilities in the world of signing. The signer could potentially sign the message and a recipient could retransmit part of the message and the corresponding part of the cipher text to a third party.

In function notation, that would be:

User Signs:

sign(plaintext, private key) = ciphertext

and transmits:

send(plaintext, ciphertext, certificate)

Application gets segments:

plaintext = desiredPlaintext + otherPlaintext

and calculates the same conversion of ciphertext, using something like:

if ciphertext::plaintext then ??::desiredPlaintext

to find desiredCiphertext

Application forwards desired content only to external service:

send(desiredPlaintext, desiredCiphertext, certificate)

And the service can verify this message as though the user had sent it directly.

This depends on the hash algorithm used to compress the plaintext also being homomorphic. If not, this isn't going to work... or that no hash algorithm is applied.

This could be very useful in cases where you want an external service to do something in response to a signed user request, but you don't want to expose everything the user sent to that external service.

One example would be a simple package ordering system - I send a web app a request to buy a collection of items. To be super-secure I sign a Purchase Order that confirms that I want (and promise to pay for) some # of items, shipped to some specific location, by some specific date, and with some specific payment information. Now.. the web app will want to have several things happen:

• Finance needs to charge my account, and start getting a payment from me
• Inventory needs to pull the items from stock, or deal with any out of stock problems
• Shipping needs to receive from inventory and move the stuff to my address

There's no reason for Inventory or Shipping to know about how I pay my bill. And there may be no reason for finance to know my shipping address... In each case, the desiredPlaintext and desiredCiphertext changes, depending on who the receiver is. This is even more potent in a system like Amazon.com used books where the entity I bought from (Amazon) is different from the entity providing the item (the used book seller).

Reading the paper about lattice cryptography, it sounds more like a symmetric key system... which isn't so conducive to signing messages.

On the concept of "never say never", I'd not say it was unreasonable to use it for privacy applications. But it seems distinctly troublesome that you can find multiple ways of getting from ciphertext to plaintext.

Answer 2

The problem with the existing homomorphic encryption algorithm is that you can only execute a polylogarithmic (NC1) circuit with it, which rules out almost anything interesting algorithmically.

Plus it doesn't seem that the complexity of encoding is in any way lower than the complexity of executing the polylogarithmic circuit yourself, so you haven't picked up any free work at first blush, unless you do something particularly tricky with it.

Answer 3

Here's a wild shot in the dark:

We're thinking about protecting the plaintext from the person doing the computation on it. But what if the objective was to protect both the plaintext AND the algorithm?

Take, for example, MRI machines. The most expensive part of the MRI machine is the algorithm in which the machine analyzes the magnetic resonance data. Because of this, they are heavily protected by hardware devices designed to destroy the program before allowing itself to be examined by an untrusted party (or anyone for that matter).

If an MRI maker could centralize MRI data computing, it would be a fantastic reduction in risk of losing their algorithm. However, laws prevent them from accessing private patient data.

So! Homomorphic encryption allows this to happen where the patient data and the algorithm are both protected. The 'fully' homomorphic encryption (i.e. inducing a ring homomorphism onto the encrypted data) allows for a much more efficient and robust set of computations to operate on the data.

Answer 4

The biggest application of homomorphic encryption would be in data mining, IMHO. The usage of this algo could solve the problems of both privacy and trend discovery at the same time. For example, say your company hosts it's sales info on some SAS provider. Now, that provider could give you sophisticated data mining services, without you having to actually reveal your real info . Basically, you would be able to send your data to a computation provider, have him utilize his CPU cycles to compute on your behalf, and send you the encrypted data back. That'd be truly fantastic for companies who are looking to move to cloud based systems, but have privacy / IP concerns preventing them from doing so.

Another potential application, on a lower and a more personal level, would be in handling of all kinds of financial data. ilya's example extended can apply to filing of tax returns by your accountant without actually seeing your financial info, credit cards processing etc.

However, I'd hold my excitement till the scheme is tested rigorously and deemed safe. Encryption algos have a notorious habit of failing their first test, going for a revision and repeating the cycle till they are "certified" by some government authority.

Answer 5

Distributed computing like SETI@Home, protein folding projects, etc., are fairly popular because they leverage the donation of CPU time and electricity from thousands of users. Even more interesting would be a model where people can get paid to provide these resources for commercial projects. However, no responsible company wants to ship its data out to thousands of anonymous computers for processing. If you can efficiently apply algorithms to encrypted data, it becomes possible to delegate the processing to anyone without a trusted relationship.

Answer 6

I don't know how expensive the f(x) + f(x) computation is going to be, but maybe it could be used as a way of implementing encrypted database.

You can store 1 million rows of some data encrypted as f(x_1), f(x_2), ... f(x_n). You could do

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

Which could be calculated by first doing SUM(f(x)) then decrypting it to SUM(x).

Answer 7

You might be interested in viewing Bruce Schneier's rather resoundingly negative take on homomorphic encryption at:

http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html?nc=11

Answer 8

With this you can execute an arbitrary non-recursive circuit of bounded depth, so given a logarithmic key length you can execute an NC1 algorithm (basically a feed-forward Boolean circuit).

So, how can you use this?

Lets look at Map/Reducing a circuit and reduction scheme over a set of inputs.

First the data:

We probably don't want the client to have to have encrypted all of the data we are going to search, so you can provide an encrypted 1 and an encrypted 0 to the server, and let it use the ring structure to construct arbitrary encrypted integers for us, or we can just use those directly as bits. That way the server can provide some or all of the data that we are searching through. For integers it can construct them by peasant arithmetic (double or double and add 1 for each bit), for bits it just provides the appropriate encrypted bit.

We can mix and match boolean and integer values in our designs, obtaining an if/then/else (that requires evaluating both branches SIMD style) by evaluating cond * then + (1 - cond) * else using 1 as true and 0 as false in cond, so you can get away with using the built in arithmetic of your ring to make your circuits more shallow.

On the other hand, we may have pre-encrypted some data as well, but since you'll have to keep recycling the same key set to use it, this becomes seriously tricky to get right.

So, now we have server provided data. Now, encrypt the stuff you don't want the server to know, like what it is you are searching for, and have them feed that into the circuit at the right points as well, say as an extra input to your map function.

We should be able to map an arbitrary NC1-like circuit over each input to extract a field, multiply some values, and generally map it into a form that you can reduce cheaply.

Then reduce those fragments using more small circuits, such as for a simple monoid that has a nicely size-bounded result. (i.e. you map to obtain a bit that indicates if you found a match, and then you reduce by counting those bits with a small adder circuit)

Since you only need to construct the circuit logically and simulate its execution on these encrypted bits in the homomorphic ring, you could probably implement it relatively quickly using a small DSL, i.e. something like Lava in Haskell, assuming you got the homomorphic encryption pieces straight.

Also, keep in mind that each gate is seriously expensive to execute.

So, to summarize,

1. Give the server an encrypted 1 and 0 and any encrypted metainfo for your map and reduce functions.
2. For each data point, encode it into your homomorphic ring, feed your map circuit both the input and the meta info to obtain a value suitable for reduction.
3. In a balanced binary tree (or other balanced arrangement to minimize tree height), apply your reduction operation to the output from your circuit and any encrypted map metainfo.
4. Hand the result over to the client for decryption

Answer 9

Electronic voting is indeed a practical application of homomorphic encryption, i.e. http://heliosvoting.org/