Hacker News Reader

Comment by tedunangst | Hacker News Reader

I feel like phone number lookup is the textbook example of homomorphic encryption not actually working because there's so few keys you can simply enumerate them.

View on HN

I think here the query exposes who called who, which isn't as enumerable. By encrypting the query homomorphically on the client, the answering service has no knowledge of what number the lookup is for, and so Apple can't build a database of who calls you.

It includes both numbers? That wasn't clear. It sounded like they're just looking up the calling number for fancy caller id. How does the recipient affect the query?

The lookup has to come from your phone, which implicitly discloses you. Encrypting the caller-id symmetrically or asymmetrically wouldn't get privacy, because the receiver would have the decryption key. Hashing it, even with a seed, would be dumb because it's enumerable as you pointed out. But encrypting the entire query does work, because it becomes on a homomorphic search on uniform looking data. So the receiver has no idea what you queried.

That said, research on things like memory access side-channels is thin here. Like if I take a guess and try a query for my guess number, are there timings there that could be exploited because of cache effects? I have no idea, but a lot of PIR schemes have fallen to this.

Okay, I figure if Apple wanted, they could simply query every number and see which disk blocks get read. But now maybe I'm confused. They read the whole database on every query?

My understanding of encrypted search in FHE is that there can be multiple copies of the same search key, and that search keys aren't simply in-place encrypted versions of themselves - as encrypted fields in a database are - but are mappings embedded in a higher dimensional space that is encrypted.

That reads like sci-fi nonsense, but the "on the metal" result is that a search key will translate to a set of memory locations that are combined to determine the match, and a separate query for the same search key will translate to a different (but potentially overlapping) set of memory locations that produce the same result.

Do I have this right?

If the server could actually decode things it would’ve gotten something that could be decrypted into let’s say 15 phone numbers. A little bit like if they were hashed, to simplify.

So the answer the server returns isn’t who the phone number belongs to, it’s who those 15 phone numbers belong to.

And then the client can decrypt it and just get the one that it cares about.

But unlike if you were just doing hash buckets no one who saw the data going back-and-forth could actually understand any of it. Correct?

Is this only really good for data to look up cases? I had thought homomorphic encryption could be used to do actual calculations, at least certain kinds.

Theoretically it can, but the tech isn't quite there yet, so we don't know for sure.

> I had thought homomorphic encryption could be used to do actual calculations, at least certain kinds.

Well yes. There was this:

- https://news.ycombinator.com/item?id=21638639

- https://news.ycombinator.com/item?id=31933995

- https://azeemba.com/posts/homomorphic-encryption-with-images...

And quite a few more.

AFAIK (but my knowledge is 2/3 years out of date) the problem with general computation is that current schemes are still too slow for parctical use. But recent developments give hope that it could be doable in the future.

I'm not sure what enumeration attack you have in mind, but if you were to encrypt the same value many times you would not get the same ciphertext under most schemes.

The novelty is that the server processing the phone number can perform the lookup without actually knowing the phone number or whether it matched.

Are you thinking of hashing?

As far as I'm aware homomorphic encryption can keep even a single bit safe, but maybe I missed something.

add a seed.

Reply on news.ycombinator.com