4 ms·

As a technological demonstration of homomorphic encryption and its benefit.

cogman10 2y ago
I'm having a hard time wrapping my head around how you'd do homomorphic encryption securely (particularly FHE). Like, for example, let's say I want to farm out word counts to the cloud. Wouldn't the information required to identify what a "word" is require the running software to be able to see breaks/periods/etc? Doesn't that leak information about the cyphertext? How does it stop someone from writing software that, for example, maps out the position of all the a's, then b's, then c's, etc in a cyphertext and MITMing it?
- perching_aix 2y ago
  I think the idea is that you would never get to know the answer to those individual questions, or any questions really; you'd be producing an encrypted blob of a response that supposedly has the answer and then just pass that onward. Unfortunately the mathematical details escape me as well. Maybe one day I'll set aside some time to look into it.
- fragmede 2y ago
  That wouldn't be FHE, for the reason you identified. Outside of a tiny number of algorithms, homomorphic encryption doesn't usefully generalize to something as generic as word counting of arbitrary text like that. Production use of FHE is really limited. Probably the most well known application is by Apple for phone number lookup, where they're able to get the caller id for a phone number without knowing the phone number, basically.
- uniq7 2y ago
  I have only read Craig Gentry, 2009 [1] (the first proposed FHE scheme), but the main idea is that an untrusted agent can perform operations on the encrypted data (i.e., addition and multiplication) and obtain an encrypted result. The untrusted agent cannot understand the result, but they can send it to the user, and the user can decrypt it. Since the scheme is asymmetric, the untrusted agent can also encrypt new data with the public key, meaning that they can do things like: `return encrypt(x) + encrypted_data_from_user * encrypt(y)` This alone doesn't let the untrusted agent evaluate a boolean condition or run an algorithm like the one you proposed, but they can at least run encrypted data through a neural network and send the encrypted output to the user. [1] https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-e...
- snowfoolin 2y ago
  These are good questions! FHE appears nonintuitive at first glance, but hopefully with a smaller example it can be made clear. > Wouldn't the information required to identify what a "word" is require the running software to be able to see breaks/periods/etc? Yes. But that information can be encrypted and still computed on. You might suppose that since encrypted data is essentially gibberish, then multiplying or adding different blocks of it together will only generate gibberish. The insight is that it is not entirely gibberish- or else how would we be able to decrypt it? The information to identify a word still there, and you can write a program that sees breaks/periods/etc, but you won't know when it sees a break/period until decryption of the result. > Doesn't that leak information about the cyphertext? This question seems to be encoding an assumption that the cloud in your example is able to see the result of the search query. The key insight here is that the cloud is only able to compute the encrypted result. It can only return the encrypted result to the requester who has the private key, and can decrypt the result, and see how many words were counted. > How does it stop someone from writing software that, for example, maps out the position of all the a's, then b's, then c's, etc in a cyphertext and MITMing it? I'm a bit confused by the attack here. I think it is also assuming that the untrusted computing party is able to read the plaintext result of the operation. Here's an illustrative example. Suppose my encryption scheme is Enc(key, m) = key*m = c. Suppose my decryption scheme is Dec(key, c) = c/key = m. This scheme is not secure, but pretend that it is, and that separating out key and m from c is difficult. I want the untrusted cloud to compute m1 * m2. I can perform Enc(key, m1) = c1, Enc(key, m2) = c2 and send c1 and c2 to the cloud to multiply. The cloud receives c1 and c2 which are really key*m1 and key*m2, but we are assuming that the cloud can't separate these factors from the products. The cloud returns c1*c2, which we know equals key*m1*key*m2 = key^2 * (m1*m2). If we divide c1*c2 by (key^2) - note: this is just running our decryption algorithm with a modified key - we will get m1*m2, which is what we wanted! For a more formal example using ElGamal Encryption (apologies for spelling ElGamal wrong in the paper) I wrote this up: https://github.com/lsnow99/elgamal/blob/main/elgamal.pdf https://github.com/lsnow99/elgamal/blob/main/elgamal.pdf Credit to https://www.cs.cmu.edu/~goyal/15356/lecture_notes.pdf https://www.cs.cmu.edu/~goyal/15356/lecture_notes.pdf for definitions
  - magicalhippo 2y ago
    Great explanation, thank you. In your example you decryped by key^2. The decryption requiring a different or derivative key a general feature of the algorithm or just a quirk of your example?

I'm having a hard time wrapping my head around how you'd do homomorphic encryption securely (particularly FHE). Like, for example, let's say I want to farm out word counts to the cloud. Wouldn't the information required to identify what a "word" is require the running software to be able to see breaks/periods/etc? Doesn't that leak information about the cyphertext? How does it stop someone from writing software that, for example, maps out the position of all the a's, then b's, then c's, etc in a cyphertext and MITMing it?

perching_aix 2y ago
I think the idea is that you would never get to know the answer to those individual questions, or any questions really; you'd be producing an encrypted blob of a response that supposedly has the answer and then just pass that onward. Unfortunately the mathematical details escape me as well. Maybe one day I'll set aside some time to look into it.
fragmede 2y ago
That wouldn't be FHE, for the reason you identified. Outside of a tiny number of algorithms, homomorphic encryption doesn't usefully generalize to something as generic as word counting of arbitrary text like that. Production use of FHE is really limited. Probably the most well known application is by Apple for phone number lookup, where they're able to get the caller id for a phone number without knowing the phone number, basically.
uniq7 2y ago
I have only read Craig Gentry, 2009 [1] (the first proposed FHE scheme), but the main idea is that an untrusted agent can perform operations on the encrypted data (i.e., addition and multiplication) and obtain an encrypted result. The untrusted agent cannot understand the result, but they can send it to the user, and the user can decrypt it. Since the scheme is asymmetric, the untrusted agent can also encrypt new data with the public key, meaning that they can do things like: `return encrypt(x) + encrypted_data_from_user * encrypt(y)` This alone doesn't let the untrusted agent evaluate a boolean condition or run an algorithm like the one you proposed, but they can at least run encrypted data through a neural network and send the encrypted output to the user. [1] https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-e...
snowfoolin 2y ago
These are good questions! FHE appears nonintuitive at first glance, but hopefully with a smaller example it can be made clear. > Wouldn't the information required to identify what a "word" is require the running software to be able to see breaks/periods/etc? Yes. But that information can be encrypted and still computed on. You might suppose that since encrypted data is essentially gibberish, then multiplying or adding different blocks of it together will only generate gibberish. The insight is that it is not entirely gibberish- or else how would we be able to decrypt it? The information to identify a word still there, and you can write a program that sees breaks/periods/etc, but you won't know when it sees a break/period until decryption of the result. > Doesn't that leak information about the cyphertext? This question seems to be encoding an assumption that the cloud in your example is able to see the result of the search query. The key insight here is that the cloud is only able to compute the encrypted result. It can only return the encrypted result to the requester who has the private key, and can decrypt the result, and see how many words were counted. > How does it stop someone from writing software that, for example, maps out the position of all the a's, then b's, then c's, etc in a cyphertext and MITMing it? I'm a bit confused by the attack here. I think it is also assuming that the untrusted computing party is able to read the plaintext result of the operation. Here's an illustrative example. Suppose my encryption scheme is Enc(key, m) = key*m = c. Suppose my decryption scheme is Dec(key, c) = c/key = m. This scheme is not secure, but pretend that it is, and that separating out key and m from c is difficult. I want the untrusted cloud to compute m1 * m2. I can perform Enc(key, m1) = c1, Enc(key, m2) = c2 and send c1 and c2 to the cloud to multiply. The cloud receives c1 and c2 which are really key*m1 and key*m2, but we are assuming that the cloud can't separate these factors from the products. The cloud returns c1*c2, which we know equals key*m1*key*m2 = key^2 * (m1*m2). If we divide c1*c2 by (key^2) - note: this is just running our decryption algorithm with a modified key - we will get m1*m2, which is what we wanted! For a more formal example using ElGamal Encryption (apologies for spelling ElGamal wrong in the paper) I wrote this up: https://github.com/lsnow99/elgamal/blob/main/elgamal.pdf https://github.com/lsnow99/elgamal/blob/main/elgamal.pdf Credit to https://www.cs.cmu.edu/~goyal/15356/lecture_notes.pdf https://www.cs.cmu.edu/~goyal/15356/lecture_notes.pdf for definitions
- magicalhippo 2y ago
  Great explanation, thank you. In your example you decryped by key^2. The decryption requiring a different or derivative key a general feature of the algorithm or just a quirk of your example?