Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fully homomorphic encryption and the dawn of a private internet

bozmen.io

Post reply on HN
Print view View original

181–190 of 202 posts

Re: Fully homomorphic encryption and the dawn of a private internet

#181

Post by j2kun »

littlecranky67 wrote: post #22
dachrillz wrote: post #19

Earlier quoted context omitted.

A very basic way of how it works: encryption is basically just a function e(m, k)=c. “m” is your plaintext and “c” is the encrypted data. We call it an encryption function if the output looks random to anyone that does not have the key If we could find some kind of function “e” that preserves the underlying structure even when the data is encrypted you have the outline of a homomorphic system. E.g. if the following h…

I get how that works for arithmetic operations - what about stuff like sorting, finding an element in a set etc? This would require knowledge of the cleartext data, wouldn't it?

Comparisons can be implemented by approximating a 
    0.5 * (sign(a - b) + 1)
And the sign function can be approximated by a polynomial that uses only additions and multiplications and products with constants.

Other FHE schemes have support for small-bitwidth lookup tables that makes supporting comparison more direct.

Re: Fully homomorphic encryption and the dawn of a private internet

#182

Post by NoImmatureAdHom »

throwaway478484 wrote: post #85
NoImmatureAdHom wrote: post #80

Earlier quoted context omitted.

> The statements made in the linked description of this cannot be true, such as Google not being able to read what you sent them and not being able to read what they responded with. The beautiful thing is: they are :-)

If Google’s services can respond to queries, they must be able to read them. If A uses a cereal box cipher and B has a cereal box cipher, B can can make sense of encoded messages A sends them, A can ask about the weather, and B can reply with an encoded response that A can decode and read. B is able to read A’s decoded query, and B knew what the weather was, and responded to A with that information. Security is not m…

The thing that you find magical is not only actually possible but implemented and in use! What a day for you! Enjoy it, this is a rare event :-D

Re: Fully homomorphic encryption and the dawn of a private internet

#183

Post by mti »

blintz wrote: post #167
mti wrote: post #152

Earlier quoted context omitted.

There is an even more fundamental reason why FHE cannot realistically be used for arbitrary computation: it is that some computations have much larger asymptomatic complexity on encrypted data compared to plaintext. A critical example is database search: searching through a database on n elements is normally done in O(log n), but it becomes O(n) when the search key is encrypted. This means that fully homomorphic Goog…

There has been a theoretical breakthrough that makes search a O(log n) problem, actually, ( https://eprint.iacr.org/2022/1703 ) but it is pretty impractical (and not getting much faster).

Good point. Note however that PIR is a rather restricted form of search (e.g., with no privacy for the server), but even so, DEPIR has polylog(n) queries (not log n), and requires superlinear preprocessing and a polynomial blowup in the size of the database. I think recent concrete estimates are around a petabyte of storage for a database of 2^20 words. So as you say, pretty impractical.

Re: Fully homomorphic encryption and the dawn of a private internet

#184

Post by j2kun »

charcircuit wrote: post #61

How do you send a password reset email with this. Eventually your mail server will need the plaintext address in order to send the email. And that point can be leaked in a data breach. It's idealistic to think this could solve data braches because businesses knowing who their customers are is such a fundamental concept.

I don't think this is possible with FHE alone.

Re: Fully homomorphic encryption and the dawn of a private internet

#185

Post by toolslive »

txdv wrote: post #20
blintz wrote: post #3

I say this as a lover of FHE and the wonderful cryptography around it: While it’s true that FHE schemes continue to get faster, they don’t really have hope of being comparable to plaintext speeds as long as they rely on bootstrapping. For deep, fundamental reasons, bootstrapping isn’t likely to ever be less than ~1000x overhead. When folks realized they couldn’t speed up bootstrapping much more, they started talking…

I get that there is a big LLM hype, but is there really no other application for FHE? Like for example trading algorithms (not the high speed once) that you can host on random servers knowing your stuff will be safe or something similar?

I encountered the situation where one company had the data, and considered this to be really valuable and did not want to show/share it. Another company had a model, which was very considered very valuable and did not want to show it. So they were stuck in a catch22. Eventually they solved the perceived risk via contracts, but it could have been solved technically if FHE were viable.

Re: Fully homomorphic encryption and the dawn of a private internet

#187

Post by j2kun »

perlgeek wrote: post #178
j2kun wrote: post #136

Earlier quoted context omitted.

You're right about incentives, but wrong about the first part. Private lookups of a plaintext database are possible and have been for a while now (5+ years?). The problem is it often requires some nontrivial preprocessing of the plaintext database, or in the worst case a linear scan of the entire database.

> Private lookups of a plaintext database are possible and have been for a while now (5+ years?). The problem is it often requires some nontrivial preprocessing of the plaintext database, or in the worst case a linear scan of the entire database. So that basically means that if a company has data that my program might want to use, the entirety of that data needs to be loaded into my program. Not quite feasible for so…

> the entirety of that data needs to be loaded into my program

What? No. I'm not saying the entire Google search index is feasible, but you can do a lot. Here are some concrete numbers from what is now considered an "old" paper (2022; it has been improved since then)

https://eprint.iacr.org/2022/949

To make queries to a 1 GB database [in a scheme called DoublePIR] the client must download a 16 MB "hint" about the database contents; thereafter, the client may make an unbounded number of queries, each requiring 345 KB of communication, and a throughput of 7.4 GB/s/core.

Re: Fully homomorphic encryption and the dawn of a private internet

#188

Post by IshKebab »

j2kun wrote: post #169
IshKebab wrote: post #35

I think this should talk about the kinds of applications you can actually do with FHE because you definitely can't implement most applications (not at a realistic scale anyway).

You might enjoy https://jeremykun.com/fhe-in-production

I meant it should say what can't be implemented. What are the constraints? Currently the article makes it sound like you can do anything, just slower, which definitely isn't the case.

Re: Fully homomorphic encryption and the dawn of a private internet

#189

Post by haiku2077 »

hoppp wrote: post #76
haiku2077 wrote: post #12

Earlier quoted context omitted.

You're not joking. If you're like most people and have only a few TiB of data in total, self hosting on a NAS or spare PC is very viable. There are even products for non-technical people to set this up (e.g. software bundled with a NAS). The main barrier is having an ISP with a sufficient level of service.

But if you have a lot of data, self hosting is still cheaper. Its always gonna be cheaper because you don't have the cloud provider's profit margin, which can be quite high.

For very large amounts of data, the cloud provider can hit economies of scale using tape drives ($$$$ to buy a tape drive yourself) or enterprise-class hard drives (very loud + high price of entry if you want redundancy + higher failure rate than other storage). That's why storing data in the slower storage classes in S3 and other object stores is so cheap compared to buying and replacing drives.

Re: Fully homomorphic encryption and the dawn of a private internet

#190

Post by bcrl »

meindnoch wrote: post #101
yorwba wrote: post #69

Earlier quoted context omitted.

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.

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…

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