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