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

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 2

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.