undefined | Better HN

0 pointsmeindnoch9mo ago0 comments

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

0 comments

teo_zero9mo ago

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

meindnochOP9mo ago

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.

j / k navigate · click thread line to collapse

0 comments

teo_zero9mo ago

Now I see it. Thank you.

meindnochOP9mo ago

j / k navigate · click thread line to collapse