logoalt Hacker News

teo_zero • last Saturday at 6:14 AM • 1 reply • view on HN

> IsOdd(E(x)) = E(x) mod 2

I don't get this. Did you mean

IsOdd(E(x)) = x mod 2

But who provides such function? In the case of a web search,the function is the search engine. I expect Google to provide it, not the user: the refinement and completeness level of its engine is the only reason to choose Google over its competitor. If I have to provide the function, then I'm only buying the compute power from them.

Replies

meindnoch • last Saturday at 9:25 AM

>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.
➕ show 1 reply