81–90 of 135 posts
Earlier quoted context omitted.
I don't think the set of bad numbers needs to be encrypted.
It does - otherwise you would know which numbers are queried to process the query, letting you narrow things down (ie huge side channel and thus not HE anymore).
If we assume that server is “evil” then the server can store both PIR encrypted and plain text phone number in the same row in the database and when this row is read, simply log plain text phone number. What do I miss here? We can send PIR request and trust server not to do the above; or we can send plain text phone number and trust server not to log it — what’s the difference?
A very simple PIR scheme on top of homomorphic encryption that supports multiplying with a plaintext and homomorphic addition, would look like this: The client one-hot-encodes the query: Enc(0), Enc(1), Enc(0). The server has 3 values: x, y, z. Now the server computes: Enc(0) * x + Enc(1) * y + Enc(0) * z == Enc(y). Client can decrypt Enc(y) and get the value y. Server received three ciphertexts, but does not know wh…
Earlier quoted context omitted.
Exactly, plain text phone number in the same db row
Yeah but as I wrote elsewhere, the DB isn’t a KV store of plain text numbers and their encrypted representation. Instead the entire database would be encrypted and you’d do set containment operations in encrypted space which wouldn’t /couldn’t leak anything about your query (modulo unexpected side channels in the design). I don’t know how they do this efficiently and at scale with lots of updates, but maybe this data…
Earlier quoted context omitted.
A very simple PIR scheme on top of homomorphic encryption that supports multiplying with a plaintext and homomorphic addition, would look like this: The client one-hot-encodes the query: Enc(0), Enc(1), Enc(0). The server has 3 values: x, y, z. Now the server computes: Enc(0) * x + Enc(1) * y + Enc(0) * z == Enc(y). Client can decrypt Enc(y) and get the value y. Server received three ciphertexts, but does not know wh…
Does the server reads specific rows from spam numbers DB or the whole database?
In this PIR model the server runtime is O(n) where n is the number of rows.
To keep it practical, we do support sharding the database. Client leaks a few bits of hashed query to pick the right shard, where we process the entire shard. There is a inherent privacy-performance tradeoff: less shards = less leakage vs more shards = better performance & less privacy.
The thing that I always want to know with FHE: the gold standard of modern encryption is IND-CCA security. FHE by definition cannot meet that standard (being able to change a ciphertext to have predictable effects on the plaintext is the definition of a chosen ciphertext attack). So how close do modern FHE schemes get? ie how much security am I sacrificing to get the FHE goodness?
Is the used scheme fully homomorphic encryption or just homomorphic wrt a specific operation? Because they only mention "homomorphic" without the "fully".
[Disclosure: I work on the team responsible for the feature]
Earlier quoted context omitted.
Not really. You could do it the way the Have I Been Pwned database works. You hash your query and then send only the first X number of bits. The server returns all results that hash up to that same first X number of bits. The server doesn’t know exactly what number you were looking for, and you don’t have to download the entire database. But in this case the server WOULD be able to figure out the set of possible phon…
Indeed, I wasn't clear enough in my original message that it was under the assumption that you want to keep the caller 100% private from Apple. Though there is a valid argument that you're still leaking information (e.g. "Person X received a call at 21:05:43"), but I'm not sure how you could possibly make an API that avoided that given the time sensitive nature of identifying callers.
[Disclosure: I work on the team responsible for the feature]
Earlier quoted context omitted.
Does the server reads specific rows from spam numbers DB or the whole database?
In this PIR model the server has to read the whole database, otherwise it would be easy on the server to see, that these rows were not accessed and therefore they are not the one the client queried. In this PIR model the server runtime is O(n) where n is the number of rows. To keep it practical, we do support sharding the database. Client leaks a few bits of hashed query to pick the right shard, where we process the…
What is the processing that the server does on the encrypted phone number? I am not sure I understand. I always thought that this type of encryption was (roughly and imprecisely) - you send some encrypted blob to the server, it does some side effect free number crunching on the blob and returns the output blob. You decrypt the blob and everyone is happy. But to return information if some number is spam it has to be e…
[Disclosure: I work on the team responsible for the feature]
The name is hilarious because HME is anything but speedy -- by many orders of magnitude. I think the real fix is secure enclaves, and those have proven to be difficult as well.
“Cheddar: A Swift Fully Homomorphic Encryption Library for CUDA GPUs” - https://arxiv.org/pdf/2407.13055
We were a little worried, but quickly discovered that they used Swift as an adjective not as a programming language.
[Disclosure: I work on the team responsible for the feature]