10 ms·

Practical homomorphic encryption over integers (2017)

97 points by hamilyon2 8y ago

guiomie 8y ago
This is one of the current 'tech' trends that I'm following, the idea of homomorphic encryption is really cool. I feel like there is a lot of real world applications for it, but I have failed to find them yet.
- Yhippa 8y ago
  One of the big ones is internet searches. Also processing PII/HIPAA data.
  - soberhoff 8y ago
    How does this affect internet searches?
    - mcbits 8y ago
      Potentially a search engine could provide results without knowing the actual query, although that would make it difficult to identify new trends or determine which results are/aren't being clicked, so it probably wouldn't be competitive as a general purpose search engine.
      - betterunix2 8y ago
        It would also be completely impractical, since the search engine would necessarily have to perform some sort of scan of its entire database to respond to every query (otherwise it would, in fact, learn something about the query).
        heavenlyblue 8y ago
        Unless the database is also encrypted and provides the same homomorphism against reverse index queries.
        soberhoff 8y ago
        If the database was encrypted, you would need a different encrypted database for every user - again impractical.
        betterunix2 8y ago
        In which case you are no longer talking about FHE. With FHE the server receives a ciphertext query and produces a ciphertext output, without ever seeing any plaintexts (not even the result of a reverse index query).
- jerf 8y ago
  I really want to sarcastically say "blockchain homomorphic encryption", but, well, it's not necessarily a terrible idea, honestly. One can imagine some combination of the primitives in which you could prove that you added here the same amount you subtracted from there, that neither total is below zero, but for which the number actually transferred is encrypted. The current use case for something like BitCoin is often security focused, but there's also simply a privacy concern that could be addressed there.
  - deleted 8y ago
    [deleted]
  - ersiees 8y ago
    I think this is what zcash already does.
    - yarrel 8y ago
      zCash uses zk-SNARKs for secret transactions. Which are awesome. But homomorphic encryption allows general-purpose computation.
      - cmrx64 8y ago
        These fully homomorphic encryption systems can do boolean circuits, which are no more powerful than the arithmetic circuits you get with zk-SNARKs (in fact, are an instance of arithmetic circuits). And with some zk-SNARKs, you get recursive composition, which lets you do arbitrarily many steps of a transition function expressed as a zk-SNARK, which is just as general purpose (albeit more involved) as applying a bunch of boolean circuits to some data.
  - mhluongo 8y ago
    Hey, we're working on blockchain "somewhat homomorphic encryption" (SHE) via multiparty computation. In particular, a privacy layer for Ethereum.
    - 8y ago
- srgseg 8y ago
  The "Confidential Transactions" scheme for cryptocurrencies uses homomorphic encryption. The idea is that you can prove that the encrypted input and output amounts in a transaction balance to zero, without having to actually reveal what any of those amounts are. See https://people.xiph.org/~greg/confidential_values.txt https://people.xiph.org/~greg/confidential_values.txt
  - tuxxy 8y ago
    CTs don't use homomorphic encryption. They use "additively homomorphic commitments" which are, essentially, cryptographic proofs.
- CapacitorSet 8y ago
  One of the side projects I have is [FHE-CPU](https://github.com/CapacitorSet/FHE-CPU https://github.com/CapacitorSet/FHE-CPU), an effort to make general-purpose homomorphic computation possible with a Moxie-like CPU, but it's a daunting effort to even get the basics working.
- SilasX 8y ago
  There are certainly real-world applications, just not with the current level of overhead that known algorithms require. The real-world use case is being able upload data to a cloud provider and do queries and computation on it without the provider ever knowing what's inside. e.g. "How much did I spend last month?"
- sp332 8y ago
  Cloud computing is the big one. You might want to rent some remote computer time without sending plaintext data to a third party. Homomorphic encryption lets you upload encrypted data and instructions for a third party to operate on it without having to decrypt it first. Edit: Try Greg Egan's book Permutation City.
  - tfha 8y ago
    If we had proper homorphic encryption, we could use regular home user machines for a cloud, airbnb style. You can't do that today because the security risks are completely unmanageable. But that all changes with homomorphic encryption. Today it's not practical, but we see advances like this every year, maybe in a decade it will be practical.
    - betterunix2 8y ago
      You need more than FHE for that; just because I cannot see what I am computing does not mean I will compute the answer correctly. There are ways this can be resolved but it pushes practicality even further back.
      - dlubarov 8y ago
        Not sure what you mean? Correct evaluation (modulo some negligible error) is part of the usual FHE definition.
        JadeNB 8y ago
        Perhaps it’s referring to human malice rather than mathematical error: that we’d want some sort of certification that the operation performed off-site was actually the one requested?
        tylersmith 8y ago
        You can't evaluate the correctness/trust the result without performing the computation yourself or receiving a proof of correctness, e.g. a SNARK.
- deleted 8y ago
  [deleted]
- Untit1ed 8y ago
  One of the things another team at my organisation is working on is using it so that competitors can pool their data to do better analytics over the whole corpus without actually revealing their secrets to the other company - https://www.n1analytics.com/ https://www.n1analytics.com/.
- betterunix2 8y ago
  The "textbook" application is spam filtering for encrypted mail.
KarenSatantsby 8y ago
Love, Simon was a really good movie but (yoohoo spoiler ahead)it kind of made me feel bad because of what a twat Simon is for most of the movie and when he finally gets his guy after never decrypting the letters and finding out who only because of a salt in the form of Blue making out with a hot chick I was like meh.. and the whole ferris wheel had no emotional impact - that and I wanted to punch the antagonist so badly the whole movie and I am not a punch in the face kind of guy
shry4ns 8y ago
What exactly is homomorphic encryption?
- foxes 8y ago
  A homomorphism between two sets preserves relations between elements. A set with a single operation (plus some extra properties) is called a group. The integers with addition (+) is an example of a group. Suppose I have groups X and Y. Then a group homomorphism, h, is a mapping at that preserves the + in the two groups, so h(x +_X y)=h(x) +_Y h(y) Where +_X is addition in X and +_Y is addition in Y. Homomorphic encryption means that what you used to do you encryption is a homomorphism.
- boxspam 8y ago
  Encryption while keeping the "shape"/"form" of the data intact. This way you can have secure third-party computation, without that third-party knowing exactly what data it is operating on.
- bo1024 8y ago
  You encrypt some data and send it to Bob. Bob does some computations on the encrypted data and sends you the (still-encrypted) results. You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are. The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we have f(Encrypt(data)) = Encrypt(f(data)). The left side is what Bob does, the right side is what you want to get (because you can decrypt it). EDIT. To see how cool this is, think about this: I have two numbers, I encrypt them to form long strings of gibberish. Then I have Bob perform the "multiplication" function on the gibberish and send me the result, and I am able to decrypt that to get the result of multiplying the original two numbers. If that doesn't impress you, I send Bob my database of encrypted emails, then ask him to do a string lookup for "chocolate", he sends me back the set of matching emails without ever knowing what they say or what string I looked for.
  - hossbeast 8y ago
    Does it generalize? Can you in theory perform any computation in this way?
CiPHPerCoder 8y ago
Homomorphic encryption is cool, but it's not the sort of thing most developers will want to use in their apps. Most cryptography failures (BEAST, CRIME, the Apple iMessage attack, etc.) that allow plaintext recovery are the result of chosen-ciphertext attacks. You want authenticated encryption instead. https://tonyarcieri.com/all-the-crypto-code-youve-ever-written-is-probably-broken https://tonyarcieri.com/all-the-crypto-code-youve-ever-writt... You can sort of build something authenticated on top of a homomorphic cryptosystem, but it's kind of a hack: https://paragonie.com/blog/2017/12/assuring-ciphertext-integrity-for-homomorphic-cryptosystems https://paragonie.com/blog/2017/12/assuring-ciphertext-integ...
- williamscales 8y ago
  It's not something most developers will want to use in their apps for application security, but it is absolutely something that folks may want to use when training machine learning models based on customer data. As I understand it, this is one of the big "pie in the sky" goals for homomorphic encryption—having an encrypted model trained on encrypted data that only the customer can use for inference.

97 points by hamilyon2 8y ago

This is one of the current 'tech' trends that I'm following, the idea of homomorphic encryption is really cool. I feel like there is a lot of real world applications for it, but I have failed to find them yet.

Yhippa 8y ago
One of the big ones is internet searches. Also processing PII/HIPAA data.
- soberhoff 8y ago
  How does this affect internet searches?
  - mcbits 8y ago
    Potentially a search engine could provide results without knowing the actual query, although that would make it difficult to identify new trends or determine which results are/aren't being clicked, so it probably wouldn't be competitive as a general purpose search engine.
    - betterunix2 8y ago
      It would also be completely impractical, since the search engine would necessarily have to perform some sort of scan of its entire database to respond to every query (otherwise it would, in fact, learn something about the query).
      - heavenlyblue 8y ago
        Unless the database is also encrypted and provides the same homomorphism against reverse index queries.
        soberhoff 8y ago
        If the database was encrypted, you would need a different encrypted database for every user - again impractical.
        betterunix2 8y ago
        In which case you are no longer talking about FHE. With FHE the server receives a ciphertext query and produces a ciphertext output, without ever seeing any plaintexts (not even the result of a reverse index query).
jerf 8y ago
I really want to sarcastically say "blockchain homomorphic encryption", but, well, it's not necessarily a terrible idea, honestly. One can imagine some combination of the primitives in which you could prove that you added here the same amount you subtracted from there, that neither total is below zero, but for which the number actually transferred is encrypted. The current use case for something like BitCoin is often security focused, but there's also simply a privacy concern that could be addressed there.
- deleted 8y ago
  [deleted]
- ersiees 8y ago
  I think this is what zcash already does.
  - yarrel 8y ago
    zCash uses zk-SNARKs for secret transactions. Which are awesome. But homomorphic encryption allows general-purpose computation.
    - cmrx64 8y ago
      These fully homomorphic encryption systems can do boolean circuits, which are no more powerful than the arithmetic circuits you get with zk-SNARKs (in fact, are an instance of arithmetic circuits). And with some zk-SNARKs, you get recursive composition, which lets you do arbitrarily many steps of a transition function expressed as a zk-SNARK, which is just as general purpose (albeit more involved) as applying a bunch of boolean circuits to some data.
- mhluongo 8y ago
  Hey, we're working on blockchain "somewhat homomorphic encryption" (SHE) via multiparty computation. In particular, a privacy layer for Ethereum.
  - 8y ago
srgseg 8y ago
The "Confidential Transactions" scheme for cryptocurrencies uses homomorphic encryption. The idea is that you can prove that the encrypted input and output amounts in a transaction balance to zero, without having to actually reveal what any of those amounts are. See https://people.xiph.org/~greg/confidential_values.txt https://people.xiph.org/~greg/confidential_values.txt
- tuxxy 8y ago
  CTs don't use homomorphic encryption. They use "additively homomorphic commitments" which are, essentially, cryptographic proofs.
CapacitorSet 8y ago
One of the side projects I have is [FHE-CPU](https://github.com/CapacitorSet/FHE-CPU https://github.com/CapacitorSet/FHE-CPU), an effort to make general-purpose homomorphic computation possible with a Moxie-like CPU, but it's a daunting effort to even get the basics working.
SilasX 8y ago
There are certainly real-world applications, just not with the current level of overhead that known algorithms require. The real-world use case is being able upload data to a cloud provider and do queries and computation on it without the provider ever knowing what's inside. e.g. "How much did I spend last month?"
sp332 8y ago
Cloud computing is the big one. You might want to rent some remote computer time without sending plaintext data to a third party. Homomorphic encryption lets you upload encrypted data and instructions for a third party to operate on it without having to decrypt it first. Edit: Try Greg Egan's book Permutation City.
- tfha 8y ago
  If we had proper homorphic encryption, we could use regular home user machines for a cloud, airbnb style. You can't do that today because the security risks are completely unmanageable. But that all changes with homomorphic encryption. Today it's not practical, but we see advances like this every year, maybe in a decade it will be practical.
  - betterunix2 8y ago
    You need more than FHE for that; just because I cannot see what I am computing does not mean I will compute the answer correctly. There are ways this can be resolved but it pushes practicality even further back.
    - dlubarov 8y ago
      Not sure what you mean? Correct evaluation (modulo some negligible error) is part of the usual FHE definition.
      - JadeNB 8y ago
        Perhaps it’s referring to human malice rather than mathematical error: that we’d want some sort of certification that the operation performed off-site was actually the one requested?
      - tylersmith 8y ago
        You can't evaluate the correctness/trust the result without performing the computation yourself or receiving a proof of correctness, e.g. a SNARK.
deleted 8y ago
[deleted]
Untit1ed 8y ago
One of the things another team at my organisation is working on is using it so that competitors can pool their data to do better analytics over the whole corpus without actually revealing their secrets to the other company - https://www.n1analytics.com/ https://www.n1analytics.com/.
betterunix2 8y ago
The "textbook" application is spam filtering for encrypted mail.

KarenSatantsby 8y ago

Love, Simon was a really good movie but (yoohoo spoiler ahead)it kind of made me feel bad because of what a twat Simon is for most of the movie and when he finally gets his guy after never decrypting the letters and finding out who only because of a salt in the form of Blue making out with a hot chick I was like meh.. and the whole ferris wheel had no emotional impact - that and I wanted to punch the antagonist so badly the whole movie and I am not a punch in the face kind of guy

shry4ns 8y ago

What exactly is homomorphic encryption?

foxes 8y ago
A homomorphism between two sets preserves relations between elements. A set with a single operation (plus some extra properties) is called a group. The integers with addition (+) is an example of a group. Suppose I have groups X and Y. Then a group homomorphism, h, is a mapping at that preserves the + in the two groups, so h(x +_X y)=h(x) +_Y h(y) Where +_X is addition in X and +_Y is addition in Y. Homomorphic encryption means that what you used to do you encryption is a homomorphism.
boxspam 8y ago
Encryption while keeping the "shape"/"form" of the data intact. This way you can have secure third-party computation, without that third-party knowing exactly what data it is operating on.
bo1024 8y ago
You encrypt some data and send it to Bob. Bob does some computations on the encrypted data and sends you the (still-encrypted) results. You decrypt the results to get the answer of your computation. Bob never learns what your data is or what the results are. The term "homomorphic" roughly refers to the fact that the encrypt/decrypt functions go "outside" the computation. That is, if Bob is applying the function f, we have f(Encrypt(data)) = Encrypt(f(data)). The left side is what Bob does, the right side is what you want to get (because you can decrypt it). EDIT. To see how cool this is, think about this: I have two numbers, I encrypt them to form long strings of gibberish. Then I have Bob perform the "multiplication" function on the gibberish and send me the result, and I am able to decrypt that to get the result of multiplying the original two numbers. If that doesn't impress you, I send Bob my database of encrypted emails, then ask him to do a string lookup for "chocolate", he sends me back the set of matching emails without ever knowing what they say or what string I looked for.
- hossbeast 8y ago
  Does it generalize? Can you in theory perform any computation in this way?

CiPHPerCoder 8y ago

Homomorphic encryption is cool, but it's not the sort of thing most developers will want to use in their apps. Most cryptography failures (BEAST, CRIME, the Apple iMessage attack, etc.) that allow plaintext recovery are the result of chosen-ciphertext attacks. You want authenticated encryption instead. https://tonyarcieri.com/all-the-crypto-code-youve-ever-written-is-probably-broken https://tonyarcieri.com/all-the-crypto-code-youve-ever-writt... You can sort of build something authenticated on top of a homomorphic cryptosystem, but it's kind of a hack: https://paragonie.com/blog/2017/12/assuring-ciphertext-integrity-for-homomorphic-cryptosystems https://paragonie.com/blog/2017/12/assuring-ciphertext-integ...

williamscales 8y ago
It's not something most developers will want to use in their apps for application security, but it is absolutely something that folks may want to use when training machine learning models based on customer data. As I understand it, this is one of the big "pie in the sky" goals for homomorphic encryption—having an encrypted model trained on encrypted data that only the customer can use for inference.