8 ms·

The Beginner's Textbook for Fully Homomorphic Encryption

251 points by Qision 1y ago

Direct link to the book: https://fhetextbook.github.io/ https://fhetextbook.github.io/

noman-land 1y ago
Direct link to the book: https://fhetextbook.github.io/ https://fhetextbook.github.io/
Hizonner 1y ago
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 work inside, because I've never taken the time to learn, because I believed those limitations made it unusable for most purposes. Yet the abstract suggests that FHE is useful for running machine learning models, and I assume that means models of significant size.
- pclmulqdq 1y ago
  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.
  - k__ 1y ago
    Does this mean, according to Moore's Law, FHE can operate at speeds from 6 years ago?
    - jammaloo 1y ago
      Moore's Law roughly states that we get a doubling of speed every 2 years. If we're 6 orders of magnitude off, then we need to double our speed 20 times (2^20 = 1,048,576), which would give us speeds approximately in line with 40 years ago. Unless my understanding is completely off.
    - treyd 1y 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.
  - j2kun 1y ago
    LLMs are at the current forefront of FHE research. There are a few papers doing some tweaked versions of BERT in <1 minute per token. Which is only ~4 orders of magnitude slower than cleartext. https://arxiv.org/html/2410.02486v1#S5 https://arxiv.org/html/2410.02486v1#S5
    - Nevermark 1y ago
      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.)
    - pclmulqdq 1y ago
      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.
- benlivengood 1y ago
  The difference between homomorphic schemes and fully homomorphic schemes is that FHE can be bootstrapped; there's a circuit that can be homomorphically evaluated that removes the noise from an encrypted value, allowing any homomorphic calculation's result to have its noise removed for further computation.
- Nzen 1y ago
  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/File:Full-adder_logic_diagram.svg 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/ https://www.jeremykun.com/2024/05/04/fhe-overview/
- 1oooqooq 1y ago
  the goalpost moved and it's not private anymore, just private enough.
  - cindyllm 1y ago
    [dead]
deleted 1y ago
[deleted]
sandworm101 1y ago
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.
- layer8 1y ago
  It’s at least a million times slower than non-encrypted computation. 1000x or 100x would be a huge progress.
  - sandworm101 1y ago
    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.
    - bgnn 1y ago
      It's so bad that the only way FHE can get more efficient is to use a non-conventional compute technology. Some want to do it in optical donain.
    - j2kun 1y ago
      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.
      - aitchnyu 1y ago
        Are those accelerators software-only? 10x could let 4$ VPS run server side checks for backup software (evil clients cant clean backups) and git forges (eg, dont allow X to push to main).
EGreg 1y ago
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
- LeGrosDadai 1y ago
  That's pretty cool, but isn't any computable function can be computed via FHE, so I'm not sure the differentiable part is necessary.
  - ogogmad 1y ago
    Any program which you apply FHE to needs to be expressed as a circuit, which implies that the time taken to run a computation needs to be fixed in advance. It's therefore impossible to express a branch instruction (or "if" statement, if you prefer). The circuits are built out of "+" and "×" gates, which are enough to express any polynomial. In turn, these are enough to approximate any continuous function (Weierstrass's approximation theorem). In turn, every computable function on the real numbers is a continuous function - so FHE is very powerful.
    - jlokier 1y ago
      > In turn, every computable function on the real numbers is a continuous function That doesn't seem right. Consider the function f(x: ℝ) = 1 if x ≥ 0, 0 otherwise. That's computable but not continuous.
      - ogogmad 1y ago
        That's uncomputable because equality of real numbers is undecidable. Think infinite strings of digits.
- gametorch 1y ago
  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.
arjvik 1y ago
Is the title broken? I see “Unified Line and Paragraph Detection by Graph Convolutional Networks (2022)”
- fhe 1y ago
  I see the same, and there is a posting of that title (and linking to the correct paper) also on HN frontpage. wondering what's going on.
  - EarlKing 1y ago
    You're not alone. I saw that FHE paper earlier, so... what's going on?
- deleted 1y ago
  [deleted]
- Qision 1y ago
  Sorry for not responding earlier. This is probably a bug but it's super weird... I just emailed the mods about this.
- tomhow 1y ago
  Sorry about this. That was my screwup. There were (at least) two posts from arxiv.org on the front page at the time, and when I was updating the title on the other one I must have applied it to this one instead. I've fixed it now and re-upped it onto the front page so I can have its full exposure on the front page with its correct title.
karolcodes 1y ago
man, imagine having time to read such papers. genuinly would read it but i know this alone is like 30h study
inasio 1y ago
I was surprised that for almost 300 pages there were only 26 references listed in the back. Not the end of the world by any means, clearly a ton of work went into this, but I find it useful to see from references how it overlaps with other subjects I may know more about
logannyeMD 1y ago
FWIW: I created a github repo for compact zero-knowledge proofs that could be useful for privacy-preserving ML models of reasonable size (https://github.com/logannye/space-efficient-zero-knowledge-proofs https://github.com/logannye/space-efficient-zero-knowledge-p...). Unfortunately, FHE's computational overhead is still prohibitive for running ML workloads except on very small models. Hoping to help make ZKML a little more practical.
- infimum 1y ago
  This sounds super interesting. Can you elaborate on how you apply ZK to ML? (or can you point me to any resources?)
- oulipo2 1y ago
  Did you check Zama.ai's work on FHE?
hamburgererror 1y ago
Let's admit for a second that the problem around computational cost is solved and using FHE is similar to using plaintext data. My question might be very naive but I'd like to better understand the impact of FHE, discussions here seem to revolve very much around the use of FHE in ML, but are there other uses for FHE? For example, could it be used for everyday work in an OS or a messaging app? Also, is it the path for true obsfuscation?
- dcminter 1y ago
  That's a big stretch for the premise, but... There's no value to it in circumstances where you control all the hardware processing data, so "everyday work in an OS" - only if that OS is hosted on someone else's hardware, "a messaging app" - only if you expect some of the messages or metadata to undergo processing on someone else's hardware. It seems wildly unlikely that the performance characteristics will improve dramatically, so in practice the uses are going to remain somewhat niche.
  - hamburgererror 1y ago
    > There's no value to it in circumstances where you control all the hardware processing data But what about the case where you don't have so much control about what runs next to your program? Could it be possible for an attacker to run a program in order to extract some data when your program is run? Also, could FHE offer some protection against vulnerabilities like Meltdown and Spectre? > It seems wildly unlikely that the performance characteristics will improve dramatically Why? Are there some specific signs for this already? I had the impression that everytime people tend to believe that with technology they get proven wrong later.
    - GTP 1y ago
      The tipical, and also most useful, example use case for FHE is running computational tasks on some cloud service without having to trust it. And yes, it would provide protection against Meltdown and Spectre (if performed on the hardware running the computation), as the attacker would be able to only extract encrypted data.

251 points by Qision 1y ago

Direct link to the book: https://fhetextbook.github.io/ https://fhetextbook.github.io/

noman-land 1y ago

Direct link to the book: https://fhetextbook.github.io/ https://fhetextbook.github.io/

Hizonner 1y ago

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 work inside, because I've never taken the time to learn, because I believed those limitations made it unusable for most purposes. Yet the abstract suggests that FHE is useful for running machine learning models, and I assume that means models of significant size.

pclmulqdq 1y ago
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.
- k__ 1y ago
  Does this mean, according to Moore's Law, FHE can operate at speeds from 6 years ago?
  - jammaloo 1y ago
    Moore's Law roughly states that we get a doubling of speed every 2 years. If we're 6 orders of magnitude off, then we need to double our speed 20 times (2^20 = 1,048,576), which would give us speeds approximately in line with 40 years ago. Unless my understanding is completely off.
  - treyd 1y 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.
- j2kun 1y ago
  LLMs are at the current forefront of FHE research. There are a few papers doing some tweaked versions of BERT in <1 minute per token. Which is only ~4 orders of magnitude slower than cleartext. https://arxiv.org/html/2410.02486v1#S5 https://arxiv.org/html/2410.02486v1#S5
  - Nevermark 1y ago
    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.)
  - pclmulqdq 1y ago
    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.
benlivengood 1y ago
The difference between homomorphic schemes and fully homomorphic schemes is that FHE can be bootstrapped; there's a circuit that can be homomorphically evaluated that removes the noise from an encrypted value, allowing any homomorphic calculation's result to have its noise removed for further computation.
Nzen 1y ago
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/File:Full-adder_logic_diagram.svg 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/ https://www.jeremykun.com/2024/05/04/fhe-overview/
1oooqooq 1y ago
the goalpost moved and it's not private anymore, just private enough.
- cindyllm 1y ago
  [dead]

deleted 1y ago

[deleted]

sandworm101 1y ago

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.

layer8 1y ago
It’s at least a million times slower than non-encrypted computation. 1000x or 100x would be a huge progress.
- sandworm101 1y ago
  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.
  - bgnn 1y ago
    It's so bad that the only way FHE can get more efficient is to use a non-conventional compute technology. Some want to do it in optical donain.
  - j2kun 1y ago
    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.
    - aitchnyu 1y ago
      Are those accelerators software-only? 10x could let 4$ VPS run server side checks for backup software (evil clients cant clean backups) and git forges (eg, dont allow X to push to main).

EGreg 1y ago

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

LeGrosDadai 1y ago
That's pretty cool, but isn't any computable function can be computed via FHE, so I'm not sure the differentiable part is necessary.
- ogogmad 1y ago
  Any program which you apply FHE to needs to be expressed as a circuit, which implies that the time taken to run a computation needs to be fixed in advance. It's therefore impossible to express a branch instruction (or "if" statement, if you prefer). The circuits are built out of "+" and "×" gates, which are enough to express any polynomial. In turn, these are enough to approximate any continuous function (Weierstrass's approximation theorem). In turn, every computable function on the real numbers is a continuous function - so FHE is very powerful.
  - jlokier 1y ago
    > In turn, every computable function on the real numbers is a continuous function That doesn't seem right. Consider the function f(x: ℝ) = 1 if x ≥ 0, 0 otherwise. That's computable but not continuous.
    - ogogmad 1y ago
      That's uncomputable because equality of real numbers is undecidable. Think infinite strings of digits.
gametorch 1y ago
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.

arjvik 1y ago

Is the title broken? I see “Unified Line and Paragraph Detection by Graph Convolutional Networks (2022)”

fhe 1y ago
I see the same, and there is a posting of that title (and linking to the correct paper) also on HN frontpage. wondering what's going on.
- EarlKing 1y ago
  You're not alone. I saw that FHE paper earlier, so... what's going on?
deleted 1y ago
[deleted]
Qision 1y ago
Sorry for not responding earlier. This is probably a bug but it's super weird... I just emailed the mods about this.
tomhow 1y ago
Sorry about this. That was my screwup. There were (at least) two posts from arxiv.org on the front page at the time, and when I was updating the title on the other one I must have applied it to this one instead. I've fixed it now and re-upped it onto the front page so I can have its full exposure on the front page with its correct title.

karolcodes 1y ago

man, imagine having time to read such papers. genuinly would read it but i know this alone is like 30h study

inasio 1y ago

I was surprised that for almost 300 pages there were only 26 references listed in the back. Not the end of the world by any means, clearly a ton of work went into this, but I find it useful to see from references how it overlaps with other subjects I may know more about

logannyeMD 1y ago

FWIW: I created a github repo for compact zero-knowledge proofs that could be useful for privacy-preserving ML models of reasonable size (https://github.com/logannye/space-efficient-zero-knowledge-proofs https://github.com/logannye/space-efficient-zero-knowledge-p...). Unfortunately, FHE's computational overhead is still prohibitive for running ML workloads except on very small models. Hoping to help make ZKML a little more practical.

infimum 1y ago
This sounds super interesting. Can you elaborate on how you apply ZK to ML? (or can you point me to any resources?)
oulipo2 1y ago
Did you check Zama.ai's work on FHE?

hamburgererror 1y ago

Let's admit for a second that the problem around computational cost is solved and using FHE is similar to using plaintext data. My question might be very naive but I'd like to better understand the impact of FHE, discussions here seem to revolve very much around the use of FHE in ML, but are there other uses for FHE? For example, could it be used for everyday work in an OS or a messaging app? Also, is it the path for true obsfuscation?

dcminter 1y ago
That's a big stretch for the premise, but... There's no value to it in circumstances where you control all the hardware processing data, so "everyday work in an OS" - only if that OS is hosted on someone else's hardware, "a messaging app" - only if you expect some of the messages or metadata to undergo processing on someone else's hardware. It seems wildly unlikely that the performance characteristics will improve dramatically, so in practice the uses are going to remain somewhat niche.
- hamburgererror 1y ago
  > There's no value to it in circumstances where you control all the hardware processing data But what about the case where you don't have so much control about what runs next to your program? Could it be possible for an attacker to run a program in order to extract some data when your program is run? Also, could FHE offer some protection against vulnerabilities like Meltdown and Spectre? > It seems wildly unlikely that the performance characteristics will improve dramatically Why? Are there some specific signs for this already? I had the impression that everytime people tend to believe that with technology they get proven wrong later.
  - GTP 1y ago
    The tipical, and also most useful, example use case for FHE is running computational tasks on some cloud service without having to trust it. And yes, it would provide protection against Meltdown and Spectre (if performed on the hardware running the computation), as the attacker would be able to only extract encrypted data.