← Back to context

Comment by yorwba

6 months ago

In the case of searching Google, E(x) is the encrypted query and y is Google's database. Can you compute E(x + y) without doing at least as much work as computing E(y)? I don't think so. Instead, you use public key cryptography so that the server can compute E(y) (yes, encrypting the entire database) without being able to decrypt D(E(x)) = x.

7 comments

yorwba

Reply
meindnoch  6 months ago

Wrong. In the case of searching, the database is the function that you feed the input query into.

E.g. consider the following system:

E(x) = x ^ k, D(x) = x ^ k

So a one-time pad. Let's say that I provide a service that lets you decide whether a number is even or odd:

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

You give it an encrypted number, and it gives you back an encrypted bit that you can decrypt to see if the original number was even or not. All while it has zero knowledge of your plaintext number.

A homomorphically encrypted database is just like IsOdd(x), except orders of magnitude more complex. One idea is that any computation can be turned into a Boolean circuit, so if you have homomorphic building blocks for Boolean circuits, you can implement any computation. Obviously, some caveats apply, like all loops have to be unrolled, etc. That's why the whole thing is so inefficient. But mathematically it works.

  • yorwba  6 months ago

    If I'm generous, that "database" stores a single number. If you transform a more realistic database (one that can store many arbitrary values) into a Boolean circuit, you'll generally end up with at least one operation per stored value. And when you evaluate the circuit on encrypted data, you have to evaluate all those operations every time. That's why I wrote "without doing at least as much work as computing E(y)" instead of just "without computing E(y)." Yes, you do not necessarily explicitly encrypt all stored values. But you'll end up performing a corresponding amount of computation anyways.

  • teo_zero  6 months ago

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

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

      2 replies →

  • bcrl  6 months ago

    It's an excellent way of upholding Wirth's Law: software will continue to get slower more rapidly than hardware becomes faster.