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

The Beginner's Textbook for Fully Homomorphic Encryption

arxiv.org

Post reply on HN
Print view View original

21–30 of 51 posts

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#21

Post by treyd »

k__ wrote: post #19
pclmulqdq wrote: post #5

Earlier quoted context omitted.

Both of these are correct-ish. You can do a renornalization that resets the operation counter without decrypting on FHE schemes, so in that sense there is no strict limit on operation count. However, FHE operations are still about 6 orders of magnitude more expensive than normal, so you are not going to be running an LLM, for instance, any time soon. A small classifier maybe.

Does this mean, according to Moore's Law, FHE can operate at speeds from 6 years ago?

The rule of thumb is "about a 100000x slowdown". With Moore's law of 2 years that means it would operate at speeds of computers from about 40 years ago. Although really that's still making it seem like it's faster than it is. Making direct comparisons is hard.

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#22

Post by gametorch »

EGreg wrote: post #11

Funny thing is Since neural networks are differentiable, they can be homomorphically encrypted! That’s right, your LLM can be made to secretly produce stuff hehe

ReLU, commonly used in neural networks, is not differentiable at zero but it's still able to be approximated by expressions that are efficiently FHE-evaluable. You don't truly care about differentiability here, if you're being pedantic.

Very insightful comment, though. LLMs run under FHE (or just fully local LLMs) are a great step forwards for mankind. Everyone should have the right to interact with LLMs privately. That is an ideal to strive for.

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#23

Post by j2kun »

pclmulqdq wrote: post #5
Hizonner wrote: post #3

I was under the impression that, for any FHE scheme with "good" security, (a) there was a finite and not very large limit to the number of operations you could do on encrypted data before the result became undecryptable, and (b) each operation on the encrypted side was a lot more expensive than the corresponding operation on plaintext numbers or whatever. Am I wrong? I freely admit I don't know how it's supposed to w…

Both of these are correct-ish. You can do a renornalization that resets the operation counter without decrypting on FHE schemes, so in that sense there is no strict limit on operation count. However, FHE operations are still about 6 orders of magnitude more expensive than normal, so you are not going to be running an LLM, for instance, any time soon. A small classifier maybe.

LLMs are at the current forefront of FHE research. There are a few papers doing some tweaked versions of BERT in https://arxiv.org/html/2410.02486v1#S5

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#24

Post by j2kun »

sandworm101 wrote: post #9
layer8 wrote: post #8

Earlier quoted context omitted.

It’s at least a million times slower than non-encrypted computation. 1000x or 100x would be a huge progress.

Oh. It really is that bad still. So if the question is between wrapping the plaintext in layers of security, or building out a million new server instances to do it via FHE, i know which one everyone will choose.

It is not that bad these days, closer to 10,000x.

Accelerators are being developed that claim to get down to 10x, though i think they will be more like 100-1000x, which would still be a huge improvement considering how people use LLMs today for basic tasks like string matching.

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#26

Post by vishakh82 »

sandworm101 wrote: post #7

What is the computational burden of FHE over doing the same operation in plaintext? I realize that many cloud proponants think that FHE may allow them to work with data without security worries (if it is all encrypted, and we dont have the keys, it aint our problem) but if FHE requires a 100x or 1000x increase in processor capacity then i am not sure it will be practical at scale.

It's really not that bad. We're close to using FHE in a production consumer app.

https://vishakh.blog/2025/08/06/lessons-from-using-fhe-to-bu...

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#27

Post by seanhunter »

EGreg wrote: post #11

Funny thing is Since neural networks are differentiable, they can be homomorphically encrypted! That’s right, your LLM can be made to secretly produce stuff hehe

Differentiability isn’t a requirement for homomorphism I don’t think.

Homomorphism just means say I have a bijective function [1] f: A -> B and a binary operator * in A and *’ in B, f is homomorphic if f(a1*a2) = f(a1)*’f(a2). Loosely speaking it “preserves structure”.

So if f is my encryption then I can do *’ outside the encryption and I know because f is homomorphic that the result is identical to doing * inside the encryption. So you need your encryption to be an isomorphism [2]and you need to have ”outside the encryption “ variants of any operation you want to do inside the encryption. That is a different requirement to differentiability.

1: bijective means it’s a one to one correspondence

2: a bijection that has the homomorphism property is called an isomorphism because it makes set A equivalent to set B in our example.

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#28

Post by pclmulqdq »

j2kun wrote: post #23
pclmulqdq wrote: post #5

Earlier quoted context omitted.

Both of these are correct-ish. You can do a renornalization that resets the operation counter without decrypting on FHE schemes, so in that sense there is no strict limit on operation count. However, FHE operations are still about 6 orders of magnitude more expensive than normal, so you are not going to be running an LLM, for instance, any time soon. A small classifier maybe.

LLMs are at the current forefront of FHE research. There are a few papers doing some tweaked versions of BERT in https://arxiv.org/html/2410.02486v1#S5

This paper uses a very heavily modified version of an encoder-only BERT model. Forward pass on a single 4090 is cited there at 13 seconds after switching softmax out for a different kernel (21 seconds with softmax). They are missing a non-FHE baseline, but that model has only about 35 million parameters when you look at its size. At FP16, you would expect this to be about 100x faster than a normal BERT because it's so damn small. On a 4090, that model's forward pass probably runs at something like 100k-1M tokens per second given some batching. It sounds like 6 orders of magnitude is still about right.

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#29

Post by Nzen »

Hizonner wrote: post #3

I was under the impression that, for any FHE scheme with "good" security, (a) there was a finite and not very large limit to the number of operations you could do on encrypted data before the result became undecryptable, and (b) each operation on the encrypted side was a lot more expensive than the corresponding operation on plaintext numbers or whatever. Am I wrong? I freely admit I don't know how it's supposed to w…

My understanding is largely ten years old and high level and only for one kind of fully homomorphic encryption. Things have changed and there is more than one kind.

I heard it described as a system that encrypts each bit and then evaluates the "encrypted bit" in a virtual gate-based circuit that implements the desired operations that one wants applied to the plaintext. The key to (de|en)crypt plaintext will be at least one gigabyte. Processing this exponentially larger data is why FHE based on the system I've described is so slow.

So, if you wanted to, say, add numbers, that would involve implementing a full adder [0] circuit in the FHE system.

[0] https://en.wikipedia.org/wiki/Adder_(electronics)#/media/Fil...

For a better overview that is shorter than the linked 250 page paper, I encourage you to consider Jeremy Kun's 2024 overview [1]

[1] https://www.jeremykun.com/2024/05/04/fhe-overview/

Re: The Beginner's Textbook for Fully Homomorphic Encryption

#30

Post by Nevermark »

j2kun wrote: post #23
pclmulqdq wrote: post #5

Earlier quoted context omitted.

Both of these are correct-ish. You can do a renornalization that resets the operation counter without decrypting on FHE schemes, so in that sense there is no strict limit on operation count. However, FHE operations are still about 6 orders of magnitude more expensive than normal, so you are not going to be running an LLM, for instance, any time soon. A small classifier maybe.

LLMs are at the current forefront of FHE research. There are a few papers doing some tweaked versions of BERT in https://arxiv.org/html/2410.02486v1#S5

Given individual LLM parameters are not easily interpreted, naturally obfuscated by the diffuse nature of their impact, I would think leaning into that would be a more efficient route.

Obfuscating input and output formats could be very effective.

Obfuscation layers can be incorporated into training. With an input (output) layer that passes information forward, but whose output (input) is optimized to have statistically flat characteristics, resistant to attempts to interpret.

Nothing like apparent pure noise for obfuscation!

The core of the model would then be trained, and infer, on the obfuscated data.

When used, the core model would publicly operate on obfuscated data. While the obfuscation/de-obfuscation layers would be used privately.

In addition to obfuscating, the pre and post-layers could also reduce data dimensionality. Naturally increasing obfuscation and reducing data transfer costs. It is a really good fit.

Even the most elaborate obfuscation layers will be orders and orders of magnitude faster than today's homomorphic approaches.

(Given the natural level parameter obfuscation, and the highly limited set of operations for most deep models, I wouldn't be surprised if efficient homomorphic approaches were found in the future.)

Post reply on HN