6 ms·

Intro to Fully Homomorphic Encryption

126 points by yuedongze 6y ago

arkadiyt 6y ago
The author touched on the performance problem but is anyone aware of homomorphic encryption being used in the real world today, outside of academia?
- staycoolboy 6y ago
  I googled and found a Brazilian bank trying it out: https://www.darkreading.com/threat-intelligence/major-brazilian-bank-tests-homomorphic-encryption-on-financial-data/d/d-id/1336779 https://www.darkreading.com/threat-intelligence/major-brazil...
- Taek 6y ago
  Because of the sheer performance challenges, and the availability of SGX as an alternative, and also the competitiveness of MPC, I think most use cases struggle to justify selecting homomorphic encryption as the best choice. To me, who is involved in related fields but not FHE directly, it seems like practical FHE is probably 15 or more years away, even for niche use cases.
  - FabioBertone 6y ago
    What are SGX and MPC? :-)
    - coolspot 6y ago
      Intel SGX - allows you to run your code on a someone’s hardware fully assured that owner can’t get nor your code not your data. MPC - Multi-Party Computations. To protect your data and algorithms, you split data and code between multiple parties in special way that prevents them from knowing what exactly was computed. https://en.wikipedia.org/wiki/Software_Guard_Extensions https://en.wikipedia.org/wiki/Software_Guard_Extensions https://en.wikipedia.org/wiki/Secure_multi-party_computation https://en.wikipedia.org/wiki/Secure_multi-party_computation
  - exdsq 6y ago
    Way longer than 15 years
- aildours 6y ago
  This is the webpage of TFHE, a recent and quite fast FHE scheme - https://tfhe.github.io/tfhe/ https://tfhe.github.io/tfhe/ . They have a (surely incomplete) list of applications. I work in a somewhat related field, and I know that current FHE schemes can be used for things like voting and computing basic statistics when the data size is smallish.
  - Taek 6y ago
    Out of that entire list, all of them are either academic projects or toolchain projects. None of them are FHE in use in an actual production system. FHE is interesting but very early.
- mahmoudimus 6y ago
  There are a few companies doing some stuff commercially - some have mentioned TFHC, sponsored by commercial entity called Inpher (https://www.inpher.io/ https://www.inpher.io/ ) and you have others like Enveil (https://enveil.com https://enveil.com), who are building some cool use cases for Private Information Retrieval. Ultimately, they end up being very niche use cases that are part of a broader security strategy- we are very far away from having this be practical enough for general use cases. Deployment are also difficult because they require client side changes to adapt to the underlying cryptographic protocols. At my place of employment, we believe the right approach is a combination of locked down execution environments (see: keystone enclave) + webassembly that expose what is effectively a compiler to choose the right cryptographic computation paths based on query planner (similar technologies that power database query engines). It’s not a one-size fits all, but there are ways that you can optimize down to a fully homomorphic operation _for a particular computational path_. If this stuff is interesting to you, we are hiring :)!
davidmurdoch 6y ago
This is only a "Gentle Intro" if you know advanced mathematical notation.
- staycoolboy 6y ago
  Which really speaks to the complexity of the field. It'll be another century before the ELI5 version comes along.
  - davidmurdoch 6y ago
    ELI5 level isn't what I'd want, personally. Cryptography is of interest to many programmers, and the mental gymnastics needed for mathematics and programming are quite similar. This topic could be explained to a much broader audience without the mathematical notation, albeit not nearly as concisely, and it'd likely lack the exacting precision afforded by the notation.
    - tsimionescu 6y ago
      This sounds like people are just scared of the maths. I find it very hard to imagine there are many people who know what modular arithmetic, polynomials, or groups are, but don't know the sigma notation for summing, the forall sign, or the general "prop1, prop2 : conclusion" for 'given prop1 and prop2 then conclusion'.
  - Nzen 6y ago
    The business card version, as I understand it, involves splitting our plaintext as bits, encrypt each, pass these 'bits' through a logical circuit equivalent to the desired computation (ex a full adder [0]), decrypt the 'bits', and reassemble them into the transformed plaintext. The advanced math comes in encrypting it by choosing values that they follow a lattice [1] .. maybe .. so that evaluating the circuit doesn't trash the encrypted bits. [0] https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder [1] https://en.wikipedia.org/wiki/Lattice_(group) https://en.wikipedia.org/wiki/Lattice_(group)
- 6y ago
daenz 6y ago
If Enc(2) + Enc(3) = Enc(5), and Enc(1) + Enc(4) = Enc(5). Does Enc(5) represent the same ciphertext in both cases? I'm asking because, if so, shouldn't it be trivial to uncover the plaintexts if you can perform any math op on the ciphertexts?
- KenoFischer 6y ago
  It represents the same plaintext, but the ciphertexts are different and both computationally indistinguishable from random noise (unless you know the key)
- aildours 6y ago
  As KenoFischer says, they are not the same ciphertext, even if we consider a non homomorphic encryption system. Enc is basically a random algorithm, and we need it to return different ciphertexts for the same plaintext, otherwise it would be easy to break - if I know Enc(1) and the scheme is additive, then I'd know Enc(n) for all n...
  - blincoln 6y ago
    Are there any existing FHE algorithms with that property, or is it just a theoretical goal for the field? Every time I've heard FHE mentioned, I've had the same "this sounds like it has all the problems of ECB mode plus some new ones" reaction. This article (like all of the ones I've read) doesn't seem to cover how what you're describing would be achieved. What is the input to the algorithm that makes two identical cleartexts encrypt to different ciphertexts? In a traditional block cipher, it would be an IV or a "confounder", but IVs are included with the ciphertext, so I'm assuming it's more like a "confounder". If an FHE algorithm that exists today has this property, how does essentially randomizing the ciphertext not break the ability to perform calculations on it? It seems like whatever does the randomizing would need to be known to all parties in order to take it into account, and so anyone could factor it out in some way to get back to ciphertexts that are identical for identical cleartexts.
    - bawolff 6y ago

126 points by yuedongze 6y ago

The author touched on the performance problem but is anyone aware of homomorphic encryption being used in the real world today, outside of academia?

staycoolboy 6y ago
I googled and found a Brazilian bank trying it out: https://www.darkreading.com/threat-intelligence/major-brazilian-bank-tests-homomorphic-encryption-on-financial-data/d/d-id/1336779 https://www.darkreading.com/threat-intelligence/major-brazil...
Taek 6y ago
Because of the sheer performance challenges, and the availability of SGX as an alternative, and also the competitiveness of MPC, I think most use cases struggle to justify selecting homomorphic encryption as the best choice. To me, who is involved in related fields but not FHE directly, it seems like practical FHE is probably 15 or more years away, even for niche use cases.
- FabioBertone 6y ago
  What are SGX and MPC? :-)
  - coolspot 6y ago
    Intel SGX - allows you to run your code on a someone’s hardware fully assured that owner can’t get nor your code not your data. MPC - Multi-Party Computations. To protect your data and algorithms, you split data and code between multiple parties in special way that prevents them from knowing what exactly was computed. https://en.wikipedia.org/wiki/Software_Guard_Extensions https://en.wikipedia.org/wiki/Software_Guard_Extensions https://en.wikipedia.org/wiki/Secure_multi-party_computation https://en.wikipedia.org/wiki/Secure_multi-party_computation
- exdsq 6y ago
  Way longer than 15 years
aildours 6y ago
This is the webpage of TFHE, a recent and quite fast FHE scheme - https://tfhe.github.io/tfhe/ https://tfhe.github.io/tfhe/ . They have a (surely incomplete) list of applications. I work in a somewhat related field, and I know that current FHE schemes can be used for things like voting and computing basic statistics when the data size is smallish.
- Taek 6y ago
  Out of that entire list, all of them are either academic projects or toolchain projects. None of them are FHE in use in an actual production system. FHE is interesting but very early.
mahmoudimus 6y ago
There are a few companies doing some stuff commercially - some have mentioned TFHC, sponsored by commercial entity called Inpher (https://www.inpher.io/ https://www.inpher.io/ ) and you have others like Enveil (https://enveil.com https://enveil.com), who are building some cool use cases for Private Information Retrieval. Ultimately, they end up being very niche use cases that are part of a broader security strategy- we are very far away from having this be practical enough for general use cases. Deployment are also difficult because they require client side changes to adapt to the underlying cryptographic protocols. At my place of employment, we believe the right approach is a combination of locked down execution environments (see: keystone enclave) + webassembly that expose what is effectively a compiler to choose the right cryptographic computation paths based on query planner (similar technologies that power database query engines). It’s not a one-size fits all, but there are ways that you can optimize down to a fully homomorphic operation _for a particular computational path_. If this stuff is interesting to you, we are hiring :)!

davidmurdoch 6y ago

This is only a "Gentle Intro" if you know advanced mathematical notation.

staycoolboy 6y ago
Which really speaks to the complexity of the field. It'll be another century before the ELI5 version comes along.
- davidmurdoch 6y ago
  ELI5 level isn't what I'd want, personally. Cryptography is of interest to many programmers, and the mental gymnastics needed for mathematics and programming are quite similar. This topic could be explained to a much broader audience without the mathematical notation, albeit not nearly as concisely, and it'd likely lack the exacting precision afforded by the notation.
  - tsimionescu 6y ago
    This sounds like people are just scared of the maths. I find it very hard to imagine there are many people who know what modular arithmetic, polynomials, or groups are, but don't know the sigma notation for summing, the forall sign, or the general "prop1, prop2 : conclusion" for 'given prop1 and prop2 then conclusion'.
- Nzen 6y ago
  The business card version, as I understand it, involves splitting our plaintext as bits, encrypt each, pass these 'bits' through a logical circuit equivalent to the desired computation (ex a full adder [0]), decrypt the 'bits', and reassemble them into the transformed plaintext. The advanced math comes in encrypting it by choosing values that they follow a lattice [1] .. maybe .. so that evaluating the circuit doesn't trash the encrypted bits. [0] https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder [1] https://en.wikipedia.org/wiki/Lattice_(group) https://en.wikipedia.org/wiki/Lattice_(group)
6y ago

daenz 6y ago

If Enc(2) + Enc(3) = Enc(5), and Enc(1) + Enc(4) = Enc(5). Does Enc(5) represent the same ciphertext in both cases? I'm asking because, if so, shouldn't it be trivial to uncover the plaintexts if you can perform any math op on the ciphertexts?

KenoFischer 6y ago
It represents the same plaintext, but the ciphertexts are different and both computationally indistinguishable from random noise (unless you know the key)
aildours 6y ago
As KenoFischer says, they are not the same ciphertext, even if we consider a non homomorphic encryption system. Enc is basically a random algorithm, and we need it to return different ciphertexts for the same plaintext, otherwise it would be easy to break - if I know Enc(1) and the scheme is additive, then I'd know Enc(n) for all n...
- blincoln 6y ago
  Are there any existing FHE algorithms with that property, or is it just a theoretical goal for the field? Every time I've heard FHE mentioned, I've had the same "this sounds like it has all the problems of ECB mode plus some new ones" reaction. This article (like all of the ones I've read) doesn't seem to cover how what you're describing would be achieved. What is the input to the algorithm that makes two identical cleartexts encrypt to different ciphertexts? In a traditional block cipher, it would be an IV or a "confounder", but IVs are included with the ciphertext, so I'm assuming it's more like a "confounder". If an FHE algorithm that exists today has this property, how does essentially randomizing the ciphertext not break the ability to perform calculations on it? It seems like whatever does the randomizing would need to be known to all parties in order to take it into account, and so anyone could factor it out in some way to get back to ciphertexts that are identical for identical cleartexts.
  - bawolff 6y ago