A good usage case for partially homomorphic systems is public elections. Suppose given E(x) and E(y) you can efficiently compute E(x + y). Now imagine that you arrange a set of bit-fields as:

    1000 1100  0111 0111    0100 1110     0010 1001
    (random)  (check bits) (votes Alice)  (votes Bob)

Of course, you need more bits as you want to have more candidates and more voters; and there are problems with confirming that a number looks like 0x010100 and not 0x050500. But fundamentally you can get these really cool cryptographic voting systems which preserve the anonymity of your vote at the lowest level, but can be audited at the lowest level (i.e. we can potentially remove votes, say, from people who were not alive at the time of the election), the votes have perfectly auditable mathematics up to the regional level due to the public databases of encrypted votes; and then once the population is large enough to suitably anonymize the vote, you can decrypt and tally votes publicly too.

Now that's if you just have some function esum such that esum(E(x), E(y)) = E(x + y).

If you have enough to make a full set of logical gates, you could in principle do an entire computation on a set of inputs which you couldn't possibly know, so that the "cloud" could "compute" with your data without ever actually knowing it.

Encryption has always been something that I care about as a user, but your comment indicates that it might be a practical application for the group theory that I've been reading up on as a hobby. Bravo, good parent.

As a practical matter conplext transforms tend to produce enormous cyphertexts that can't be evaluated in any reasonable time. Which is why a lot of the cutting edge work is in renormalizing, even at the cost of restricting operations (thus somewhat rather than fully homomorphic).

I gave the same statement to a coworker who inquired about fully homomorphic encryption, but I didn't have the data to back it up. Can someone help me find performance numbers relevant to this library, or at least a recent comparable implementation?

On the other hand, so far as I know, no one has published any papers that suggest a fundamental barrier to improvement. Here's hoping!

Let's say I have access to E(N), the encryption of some secret integer N, and want to know N.

Because of the "fully homomorphic" part, given E(x) and E(y) I can compute E(x+y), E(x-y), E(x/y), etc.

So from E(N), assuming N != 0, I can compute E(N/N) = E(1). Using addition, I can compute E(2), E(3), from there.

From there, I can compute E(N mod 2), E(N mod 3), etc. Comparing them with E(1), E(2), etc, I can recover (N mod 2), (N mod 3), etc.

Once I have those for numbers whose LCM is known to be greater than N, I can use the Chinese remainder theorem to recover N. I think this is fairly efficient in terms of number of computations. If not, other methods exist. For example, one could compute E(1 << b) and from there E(N & (1 << b)) for successive values of b, thus recovering successive bits of N.

What do I overlook here?

As mentioned below, this is true for ElGamal. It is also true for all other styles of FHE scheme I'm aware of (including Ring-Learning With Errors based schemes, like this one).

In fact, if a message can only encrypt to one of a small number of ciphertexts, even more direct brute force attacks are often possible. For example, many FHE systems publish a public key. In this case, one can just encrypt E(1), E(2), etc oneself.

Besides, the big foreseen uses of HE is in applications where the confidential data is going to be changing constantly, so once you've finally figured out what one value was, it'll be worthless to have it because computation has continued.

Please reread what I wrote; it is not. Let's do the second variant: to determine whether N is odd or even, compute:

  e1 = E(N/N) (equals E(1)) ; 1, encrypted
  b1 = E(N & 1)             ; equals e1 iff N is odd
                            ; (least significant bit of N)
  e2 = E(1+1)               ; 2, encrypted
  b2 = E(N & 2)             ; equals e2 iff second bit is set
  e4 = E(2+2)               ; 4, encrypted
  e4 = E(N & 4)             ; equals e4 iff third bit is set
  e8 = E(4+4)               ; 8, encrypted
  Etc.

So you're thinking of a private key cryptosystem, where the ciphertext and the plaintext have the same length and E(.) is bijective, but in the case of ElGamal and public-key encryption in general, E(.) is not actually a function in the mathematical sense and instead encrypts one-to-many. (In fact if memory serves, n plaintext bits become 2n ciphertext bits in ElGamal.)

If that's the case in general then you could indeed compute E(1) := e_div(E(N), E(N)) and e_and(E(N), E(1)), but you could not say that E(N & 1) === E(1) if N is odd, because even though N & 1 = 1 and we've got a nice property of mathematical functions which says that if a = b then f(a) = f(b), this isn't a mathematical function and the one-to-many nature foils precisely this sort of naive comparison.

That requires that encrypting X always produces the same bits. Reading on ElGamal on Wikipedia learnt me that it does not guarantee that; it also doubles messages in size, as you thought. That will thwart this attack for any reasonable size of the encoded messages.

One could do the comparison inside the crypto system, but that would not help either, as one cannot check the outcome of such a comparison.

Also related, it might be an interesting way to encode Ricardian Contracts http://iang.org/papers/ricardian_contract.html

https://class.coursera.org/crypto-006/class

I'd highly recommend it, it's amazingly interesting, and Boneh is very good at explaining things. I used to think that cryptography was hopelessly impenetrable, but it turns out most algorithms (well, mostly symmetric cryptography) are simple to understand. We're currently at asymmetric crypto and the math's starting.

I joined the course but couldn't keep the pace.

That being said you can still access the material without doing the exams to do the course at your own rhythm.

Matasano's crypto challenge complements it nicely too, if you want to go a bit deeper.

For example, if you had a book of everyone's salaries, you can ask Bob to add $5000 to it. Normally you'd have to give him the key, but with homomorphic encryption you can just perform operations without decrypting it and having Bob know everyone's salaries.

This becomes really powerful for stuff that you need to work with lots of data without knowing the contents of - cloud computing, for example.

From: http://en.wikipedia.org/wiki/Homomorphic_encryption

I don't know much about it either.

For a recent project, I'd be interested in searching and sorting of encrypted data; I wonder if this is up to that. The tricky bit with search is that in many cases, you want to be able to search for substrings, not just an exact match.

http://www.americanscientist.org/libraries/documents/2012861... [PDF]

Try this before Wikipedia.

Basically encryption dchemes that allow operations to be done on the ciphertext that give a result that can be decrypted and is correct plaintext.

Unfortunately, FHE is nowhere near practical enough to do that sort of thing. Maybe in a decade or two we will see FHE implementations used outside the research community.

The number of downvotes my attempt at humour received would suggest that I was wrong.

Please pardon my comment about the trolling. Sometimes it's also hard to determine intentions via text-only communication.

(Here's a link for others: http://crypto.stackexchange.com/questions/3645/how-is-cipher...)

There are some guidelines here: http://ycombinator.com/newsguidelines.html

In particular: Please avoid introducing classic flamewar topics unless you have something genuinely new to say about them.

I don't blame people using the GPL either (except possibly people that use it for libraries), nor people that publish apps on the various stores, I was just clarifying a point.

YMMV.