Comment by meindnoch
6 months ago
>I don't get this. Did you mean
>IsOdd(E(x)) = x mod 2
No, that's literally the point. IsOdd() operates on the cyphertext E(x). It doesn't see the plaintext x. And yet, due to its algebraic properties, the server can answer the query without decrypting it.
For example:
Client:
x = 13
k = 45
E(x) = 13 xor 45 = 32
Server:
IsOdd(E(x)) = 32 mod 2 = 0
Client:
D(IsOdd(E(x))) = D(0) = 0 xor TrimLength(45, 1) = 1 (we trim the decryption key to the length of the response, which is 1bit)
So what happens in this case is the server sends you a bit, which you'll either flip or not flip, depending on the key k. The server doesn't know whether you're going to flip its answer or not, so it doesn't know if your plaintext number is odd or even.
Now I see it. Thank you.
What I still don't understand is how this can be used to have the remote host give me responses that I couldn't have calculated myself locally, because all the data is stored in the cloud, not locally (that's how Google search works).
Well, consider a function that is vastly more complex than IsOdd() from my previous example. IsOdd() was a function from Z[2]^n to Z[2]. Instead, imagine a function from Z[2]^n to Z[2]^m, aka a general N-to-M bit Boolean function. Any such Boolean function can be represented as a logic circuit, that is, AND/OR/NOT gates and connections between them. Now, if we can implement these logic gates (and the connections between them) homomorphically, then we can implement a homomorphic realization of arbitrary functions. One "small" caveat when transforming programs into logic circuits is that all data must be inlined, all loops must be unrolled, all branches must be executed.