News for hackers. Stuff that matters.
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.