News for hackers. Stuff that matters.
Re:An open-source fully homomorphic encryption library by drostie on Tuesday April 30, 2013 @05:21AM (#5631138)
"Fully homomorphic" means "a computation can be done on two encrypted values without decrypting them." It is an extension of partially homomorphic systems, which allow some computation which cannot be extended to arbitrary computations.

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)
In other words, the current vote tally is being represented as a number E(0x8C774E29). You can now create two ballots, E(0xBF010100) and E(0xBF010001). You can add either of those ballots to the vote tally even though you cannot read the vote tally. We can make all of these numbers public knowledge without disclosing your vote -- i.e. a public database can say "Alice's vote was E(0xBF010100)" and "Bob's vote was E(0xDB010001)" and once that encryption is performed, third parties cannot actually verify that Alice didn't vote for Bob or vice versa. So any member of the population can take the public database and confirm that the arithmetic was done properly on the encrypted vote tallies, without figuring out what the actual votes were. Then at the highest level, the tally can be decrypted to find out that Alice won the vote, without disclosing exactly who voted for her. The "check bits" form here a sum of votes as a quick check that someone didn't just add some random ballot in there to screw with the system.

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.

Re:An open-source fully homomorphic encryption library by clebio on Tuesday April 30, 2013 @10:29AM (#5632347)
This is a phenomenally good comment. You take the core concept, homomorphic, which is possibly opaque to someone not skilled in the art (of encryption algorithms) and explain the main advantage of this approach using a real-world example that is both complete for the purpose of illustration and also relevant for 'why should I care'.

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.

Re:An open-source fully homomorphic encryption library by hyperbovine on Tuesday April 30, 2013 @11:58AM (#5632941)
Operations which preserve structure aren't just confined to group theory. Everyone in a quantitative field should understand the core idea.
Re:An open-source fully homomorphic encryption library by bradleyjg on Tuesday April 30, 2013 @07:25AM (#5631469)
In theory if you have arbitrary addition and arbitrary multiplication (i.e. a ring structure) you can perform any transform on the cyphertext that you could on the (finite) plaintext.

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).

Re:An open-source fully homomorphic encryption library by Cyranix on Tuesday April 30, 2013 @11:33AM (#5632725)
> can't be evaluated in any reasonable time

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?

Re:An open-source fully homomorphic encryption library by bradleyjg on Tuesday April 30, 2013 @12:03PM (#5632981)
I don't see benchmarks for this particular implimentation yet, but the readme references the Gentry-Halevi-Smart optimizations as an inspiration. That paper Homomorphic Evaluation of the AES Circuit (http://eprint.iacr.org/2012/099.pdf), discusses three FHE methods of computing AES-128. The fastest disclosed implementation has an amortized run time (on a beast of a machine -- 18MB cache, 256GB RAM) of around 19 seconds per byte. In contrast some CPU have native instructions that can run AES-128 on the order of cycles per byte. So we are roughly talking a 10 billion fold slowdown.
Re:An open-source fully homomorphic encryption library by bhitov on Tuesday April 30, 2013 @01:19PM (#5633537)
I thought the Gentry method solved the problem of enormous cyphertexts (via 'bootstrapping') while still preserving addition and multiplication operations. Is that not true?
Re:An open-source fully homomorphic encryption library by bradleyjg on Wednesday May 01, 2013 @01:24PM (#5639324)
Sure but that method just trades time for space. Later work did reduce the overall complexity by substituting different "hard problems" as the cryptographic primitive, but it's still in the realm of unusable scaling characteristics.

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!

Re:An open-source fully homomorphic encryption library by Someone on Tuesday April 30, 2013 @03:50PM (#5634481)
I never understand how one could call anything that is fully homomorphic encryption.

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?

Re:An open-source fully homomorphic encryption library by tbmbob on Tuesday April 30, 2013 @10:57PM (#5636206)
To build off of the comments below, this attack is foiled by the fact that one message can be encrypted to one of a large number of ciphertexts.

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.

Re:An open-source fully homomorphic encryption library by kedean on Tuesday April 30, 2013 @04:24PM (#5634644)
Well, ideally you wouldn't be using tiny numbers. If you're using huge numbers, then what you're describing is the equivalent of a rainbow table technique. It's going to take an extraordinary amount of time, computations, and comparisons to be able to figure out what a value was originally, and once you do you've only done it for that one key, whose value you still don't know.

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.

Re:An open-source fully homomorphic encryption library by Someone on Tuesday April 30, 2013 @05:06PM (#5634861)
"If you're using huge numbers, then what you're describing is the equivalent of a rainbow table technique"

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.
Each line is one homomorphic operation. You need ceil(2 log(N)) lines to recover N.
Re:An open-source fully homomorphic encryption library by drostie on Tuesday April 30, 2013 @05:34PM (#5635019)
This is a great question! I freely confess that I'm not totally sure about the fully homomorphic systems, but you are making the assumption that you can test for equality "outside" the cryptosystem, and for at least one partially homomorphic case I know of, that's not true (viz. ElGamal).

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.

Re:An open-source fully homomorphic encryption library by Someone on Tuesday April 30, 2013 @06:55PM (#5635409)
Thanks for the reply. I indeed was thinking of just comparing the encrypted bits.

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.

Re:An open-source fully homomorphic encryption library by AndrewDucker on Tuesday April 30, 2013 @07:48AM (#5631568)
Would everyone who voted Alice have the same vote representation? Because that would make it fairly trivial to work out how everyone voted, surely?
Re:An open-source fully homomorphic encryption library by tel on Tuesday April 30, 2013 @08:56AM (#5631842)
That's the point of the random bits.
Re:An open-source fully homomorphic encryption library by AndrewDucker on Tuesday April 30, 2013 @09:07AM (#5631897)
Of course! Thank you.
Re:An open-source fully homomorphic encryption library by jchrisa on Tuesday April 30, 2013 @02:06PM (#5633877)
Can this be computed with map reduce?

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