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

161–170 of 202 posts

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

#161

Post by tonetegeatinst »

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'd also like to comment on how everything used to be a PCIE expansion card.

Your GPU was, and we also used to have dedicated math coprocessor accelerators. Now most of the expansion card tech is all done by general purpose hardware, which while cheaper will never be as good as a custom dedicated silicon chip that's only focused on 1 task.

Its why I advocate for a separate ML/AI card instead of using GPU's. Sure their is hardware architecture overlap but your sacrificing so much because your AI cards are founded on GPU hardware.

I'd argue the only AI accelerators are something like what goes into modern SXM (sockets). This ditches the power issues and opens up more bandwidth. However only servers have the sxm sockets....and those are not cheap.

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

#162

Post by benlivengood »

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 think the only thing that could make FHE truly world-changing is if someone figures out how to implement something like multi-party garbled circuits under FHE where anyone can verify the output of functions over many hidden inputs since that opens up a realm of provably secure HSMs, voting schemes, etc.

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

#163

Post by SilasX »

TechDebtDevin wrote: post #140
paulgerhardt wrote: post #133

Earlier quoted context omitted.

That actually sounds pretty reasonable and feels almost standard at this point? To pick one out of a dozen possible examples: I regularly read 500 word news articles from 8mb web pages with autoplaying videos, analytics beacons, and JS sludge. That’s about 3 orders of magnitude for data and 4-5 orders of magnitude for compute.

I dont remember the last time I saw a news page that was <50mb

There’s still Druge Report.

https://www.drudgereport.com

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

#164

Post by pxeger1 »

tonetegeatinst wrote: post #161
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'd also like to comment on how everything used to be a PCIE expansion card. Your GPU was, and we also used to have dedicated math coprocessor accelerators. Now most of the expansion card tech is all done by general purpose hardware, which while cheaper will never be as good as a custom dedicated silicon chip that's only focused on 1 task. Its why I advocate for a separate ML/AI card instead of using GPU's. Sure thei…

> most of the expansion card tech is all done by general purpose hardware, which while cheaper will never be as good as a custom dedicated silicon chip that's only focused on 1 task

I think one reason they can be as good as or better than dedicated silicon is that they can be adjusted on the fly. If a hardware bug is found in your network chip, too bad. If one is found in your software emulation of a network chip, you can update it easily. What if a new network protocol comes along?

Don't forget the design, verification, mask production, and other one-time costs of making a new type of chip are immense ($millions at least).

> Its why I advocate for a separate ML/AI card instead of using GPU's. Sure their is hardware architecture overlap but your sacrificing so much because your AI cards are founded on GPU hardware.

I think you may have the wrong impression of what modern GPUs are like. They may be descended from graphics cards (as in graphics ), but today they are designed fully with the AI market in mind. And they are design to strike an optional balance between fixed functionality for super-efficient calculations that we believe AI will always need, and programmability to allow innovation in algorithms. Anything more fixed would be unviable immediately because AI would have moved on by the time it could hit the market (and anything less fixed would be too slow).

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

#165

Post by plopilop »

JohnFen wrote: post #149
j2kun wrote: post #145

Earlier quoted context omitted.

Your assumption that operations leak info is just not correct. RSA has homomorphic properties (you can multiply two RSA ciphertexts and get the encrypted product of the plaintext), just not enough to enable general purpose computation.

> Your assumption that operations leak info is just not correct. My assumption is that you're right, that my assumption is incorrect. What I'm trying to do is understand why it's incorrect. It's not just about operations leaking info, though, it's also an issue that, intuitively, leaving enough underlying structure in the encrypted form of the data to allow for this implies that the encrypted form is weaker. I'm also…

> As I understand it right now, HME is a weaker form of encryption, but perhaps still strong enough to be a worthwhile tradeoff for the use cases being discussed.

Exactly. Homomorphism was first seen as a weakness in encryption, since it implies malleability. For instance, in the one-time pad encryption where you XOR your message with the secret key, flipping a bit in the ciphertext will result in same bit being flipped in the decryption. The attacker does not know what the end result is, but knows that the bit has been flipped, hence OTP encryption is malleable. This is enough for some attacks. With FHE encryption you have a bit of the same, from Enc(a) and Enc(b) it is easy to create Enc(a+b), hence is malleable too.

Cryptography uses several security levels. The top one for encryption is NM-CCA2 (non-malleability under chosen ciphertext attack). For instance, RSA-OAEP is NM-CCA2 secure. Since FHE schemes are malleable, they are not NM-CCA2 secure. However, a slightly lower security notion is IND-CPA (indistinguishability under chosen plaintext attack). FHE schemes are IND-CPA secure. Furthermore, IND-CPA security is shown to be equivalent to semantic security, which means that given a ciphertext the attacker cannot know any bit of information about the underlying cleartext.

Hence, FHE schemes guarantee that for all the ciphertexts they receive, the attacker cannot know anything about the underlying cleartexts. You can run a ton of operations on the ciphertexts, let's say run a homomorphic LLM, the attacker will still have no idea about what the final output is. Hence, in the model where you consider that the attacker has full control over the LLM, will behave honestly but will try to learn your secrets, you are fine. However, in the model where an attacker runs a MITM and just wants to disrupt the numbers you get back from the LLM, then you are not fine, since this encryption is malleable (in theory we could add some verifiable execution proofs but that is another topic).

As you say, everything is a tradeoff.

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

#166

Post by blintz »

reliabilityguy wrote: post #81
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…

Even without bootstrapping FHE will never be as fast as plaintext computation: the ciphertext is about three orders of magnitude much larger than the plaintext data it encrypts, which means you have to have more memory bandwidth and more compute. You can’t bridge this gap.

Technically, there are rate-1 homomorphic encryption schemes, where ‘rate’ refers to the size ratio between the plaintext and the ciphertext. They’re not super practical, so your general point stands.

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

#167

Post by blintz »

mti wrote: post #152
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…

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

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

#168

Post by tpurves »

It's a distraction to try and imagine homomorphic encryption for generic computing or internet needs. At least not for many more generations of moore's law and then even still.

However, where FHE will shine already is in specific high-value, high consequence and high confidentiality applies, but relatively low complexity computational calculations. Smart contracts, banking, potentially medical have lots of these usecases. And the curve of Moore's law + software optimizations are now starting to finally bend into the zone of practicality for some of these.

See what Zama https://www.zama.ai/ is doing, both on the hardware as well as the devtools for FHE.

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

#169

Post by j2kun »

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

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

#170

Post by reliabilityguy »

blintz wrote: post #166
reliabilityguy wrote: post #81

Earlier quoted context omitted.

Even without bootstrapping FHE will never be as fast as plaintext computation: the ciphertext is about three orders of magnitude much larger than the plaintext data it encrypts, which means you have to have more memory bandwidth and more compute. You can’t bridge this gap.

Technically, there are rate-1 homomorphic encryption schemes, where ‘rate’ refers to the size ratio between the plaintext and the ciphertext. They’re not super practical, so your general point stands.

Oh, interesting. Can you point to a paper about one?
Post reply on HN