Hacker News Reader

Comment by numpad0 | Hacker News Reader

FHE was pursued by Japanese telcos pre-2000s.

Imagine a central exchange building, serving few million customers in a region, each connecting from VT110 over ISDN line, handling imagined Internet thing pre-Internet. Something like “Tanaka-san is making a golf course reservation using easy to learn SQL language”.

FHE-based database fits the bill there; there’s a risk that equipment technicians might get hold of a key. FHE can offer protections all-around.

Performances and privacy of logic is irrelevant; it’s responsibilities of service providers to account for technical implications. Code to run is supplied. Customers are not required to/expected to write it.

Researchers doing FHE works today would be fully aware of Internet, but models in some papers to explain it might still carry that Transatlantic accent.

View on HN

> Code to run is supplied. Customers are not required to/expected to write it.

Do I have this right: FHE is useful for running queries across a dataset without revealing what the queries are nor the result? If so, would write operations even be possible?

I do research on FHE. On a high level querying works by evaluating an equivalence function between the encrypted query key and keys in the database such that the result is 1 if the key matches and 0 otherwise. You can then multiply this with the values and sum all of them together to get just the row that matches.

For write operations you could do a similar trick to select a new version of each value based on the query key matching. You are in effect writing all rows, but using the old value when you don't want to change it.

Now, due to some quirks of FHE you can only do this write operation a limited number of times before you have to perform a more expensive operation called bootstrapping to "refresh" ciphertexts. I find bootstrapping to be the coolest part of homomorphic encryption: you encrypt the secret key itself with homomorphic encryption and then use it to decrypt inside FHE. The result is still encrypted but closer to a freshly encrypted ciphertext.

So in essence you're performing encrypted operations on a remote and potentially untrusted encrypted database, but these operations are very expensive? So when would this be valuable?

When it matures to be less expensive, or the hardware handles it fast enough to not be a problem.

But always orders of magnitude slower than what a vanilla CPU can do locally. The value would entail that operations on a remote server are necessary to the function. Maybe a remote database that can be accessed from multiple devices with the same key but still permitting simultaneous read/write operations? The database could be compromised without any data stolen.

Sometimes the benefit from FHE can be larger than the speed gains. Doubt facebook would use this (for scaling and privacy reasons) but if the CIA needed to not have to trust a cloud provider for something of a smaller scale? 100% worth it.

> The value would entail that operations on a remote server are necessary to the function

Yes, not every organization has the compute power necessary, or even prefer to not handle it at all in house. If you only manage keys locally, that's a significantly smaller attack surface.

> 100% worth it

I'm not sure the value proposition is clear cut. In terms of security, while the server data itself is secure, and the nature of the transactions are inscrutable, there's now reason to share a single key between multiple users, and only one of those users needs to be compromised. The key could be generated and stored in some super secure silicon with a small attack surface, but if the data needs to be available to multiple users, you're back to duplicating and distributing the key, and social engineering remains the best attack vector. A benefit could be gained with multiple users with multiple keys and limited sharing to reduce vulnerability, like sharing sensitive documents between between select individuals. But that's a pretty niche use case.

Are there any good papers (with code even) you know of demonstrating these kind of practical applications?

I don’t know, but write to 0-initialized variable is a bitwise add against 0b0, so if you random-initialize a variable, then add a value, query variable, then subtract the known initial random state from response, you end up with the value == response - initial_random(key).

If you could add/multiply cryptographically securely, such that the current_variable - initial_random = delta != data is meaningless to third parties without the key, that will be a secure write to a secure database.

Dynamic allocation is probably not possible.

Reply on news.ycombinator.com