3 ms·

One of the main drawbacks of FHE is that it usually leaks some details of your data. E.g., if you do a multiplication of two (encrypted) values, an attacker can

One of the main drawbacks of FHE is that it usually leaks some details of your data. E.g., if you do a multiplication of two (encrypted) values, an attacker can memorize the input and output. Since for most useful applications (eg ML) your computations must be deterministic, an attacker can build up a table of calculations. Once this is filled a bit, he can use that with some heuristics to estimate the data. The problem here is that it can be very difficult to prove that an application using FHE is really secure against leaking information. I guess Intel will just do some marketing a la "it's encrypted, thus is safe" BS that semi- or non-technical managers will buy to put a checkmark on their security checklists.

bawolff 6y ago
I'm confused who is the attacker in this scenario? The entity doing the computation? If the party doing the computation can only see the encrypted inputs and outputs, and the ciphertexts are not deterministic, how would they create a table out of that?
- klyrs 6y ago
  The threat model for FHE is that the attacker is the entity doing the computation
  - monstersinF 6y ago
    Doesn’t that threat model defeat the purpose of the algorithm leaks?
  - bawolff 6y ago
    Principally yes, but it also aims to protect against evesdroppers for example. Many usecases want to keep the algorithm being invoked secret (by having it run on a computer the requester does not have access to) Anyways, the reason i asked is because the grandparent said "attacker can memorize the input and output", which is not something the entity doing the computation can do, as they only see the encrypted text, and encrypted values never repeat (or only with negligible probability) even if the plaintext they are encrypting are the same. The end user entity on the other hand, could try (in theory, not practically) every single value, memorize it, and recreate the secret function. So if the attacker in this scenario is the entity encrypting/decrypting the data, some of the grandparent's post makes more sense.
- infogulch 6y ago
  Yes it's encrypted, but the unit of encryption is individual values. If you multiply two arrays of values, they the computer/attacker can't tell exactly what each value is but could observe that, say, elements 7 and 12 are the same. Thus leaking some information about the data set.
  - im3w1l 6y ago
    Would it be possible to add random low order bits to prevent that? E.g instead of doing 7 * 9 you do 7.00024378 * 9.00003891
    - bawolff 6y ago
      FHE involves adding random noise pretty constantly (FHE kind of works by adding noise at every step, and regulary does a magic encrypted re-encryption step where during evaluation the intermediate values are reencrypted without ever revealing the original value, to get rid of the excess noise). Anyways, FHE is secure against (non-adaptive) chosen plaintext attacks. That among other things means that if E is the encryption function, E(7) != E(7), and if you have E(x) and E(y) you cant tell if x and y are related to each other unless you have access to the decryption function.
  - bawolff 6y ago
    FHE is semantically secure against chosen plaintext attacks. (The gentry latice scheme paper claims it is semantically secure against chosen plaintext attacks [1]) If i understand that correctly, it means that when you encrypt a value, you always get a different value, even if the plaintext is the same. So how would the attacker observe that value 7 and 12 are the same without decrypting the value? [1] https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf&ved=2ahUKEwjk3_GVtqLvAhXOv54KHXr7AL8QFjAAegQIARAC&usg=AOvVaw2TF2r7JBQH-oS953IAY4Is https://www.google.com/url?sa=t&source=web&rct=j&url=https:/... P.s. are you maybe confusing FHE with deterministic encryption or order-preserving-encryption which is sometimes used in "encrypted" (scare quotes because they're pretty bad) db products that still want to allow queries on encrypted data. That's a totally different thing with much much weaker security garuntees.
sigstoat 6y ago
> Once this is filled a bit, he can use that with some heuristics to estimate the data. how many inputs do you need before the heuristics start letting you guess than a function with 128 bits of input is a 64 bit multiply? and if the input is 8192 bits? i feel like you're reporting some theoretical ("needs 2^1024 ciphertexts!") attack as though it is a practical concern.
glitchc 6y ago
FHE leaks information indeed. It's proven to not be secure against a chosen ciphertext attack.
- bawolff 6y ago
  Well this is unfortunate, i can't help but feel that many of the usecases for FHE are much less likely to have decryption oracles than traditional encryption would. I'm also not sure if i would say "leak information" is the right word to describe a chosen ciphertext attack.
- paconbork 6y ago
  It's not that straightforward. There's two types of chosen ciphertext attacks: IND-CCA1 (non-adaptive) and IND-CCA2 (adaptive). There are in fact FHE schemes for the former such as https://www.iacr.org/archive/pkc2017/101750203/101750203.pdf https://www.iacr.org/archive/pkc2017/101750203/101750203.pdf The problem comes in the adaptive case. In the distinguishing game, an adaptive adversary can have the decryption oracle decrypt any ciphertext after it receives its challenge ciphertext (besides the challenge itself, as that would be trivially defeatable). However, if the adversary receives Enc(m), they can just compute Enc(m+m) and ask the oracle to decrypt it, thus winning the game. No FHE scheme will be IND-CCA2 secure by definition, but that doesn't mean that they "leak information" in the applications FHE is being proposed for. As long as you're not decrypting arbitrary ciphertexts for the server you just uploaded your sensitive encrypted information to, you can have your delegated computation, as a treat.
paconbork 6y ago
This is inaccurate. Any encryption that cryptographers will accept will be semantically secure at a minimum (which FHE is). Briefly, to quote Gentry's paper which first showed the existence of FHE: this means given a ciphertext c that encrypts either m0 or m1, it is hard for an adversary to decide which, even if it is allowed to choose m0 and m1. This rules out deterministic encryption, which is not sufficient for the reasons you mention (and is why, for example, you shouldn't use textbook RSA). Also it's actually easier to prove that FHE applications are secure than it is to prove a lot of other things. FHE is designed around commonly used hardness assumptions, such as the Learning With Errors problem. As long as you're encrypting your information correctly there's really nothing Intel can do to leak your information short of disproving open conjectures in computer science. At the very least, they probably won't fumble their way into doing so
joppy 6y ago
Isn’t this the whole problem in homomorphic encryption? We already have cryptographic systems for which encryption is a homomorphism, such as RSA. I thought that the whole problem was finding ways to do it that don’t leak any data, basically.

bawolff 6y ago

I'm confused who is the attacker in this scenario? The entity doing the computation? If the party doing the computation can only see the encrypted inputs and outputs, and the ciphertexts are not deterministic, how would they create a table out of that?

klyrs 6y ago
The threat model for FHE is that the attacker is the entity doing the computation
- monstersinF 6y ago
  Doesn’t that threat model defeat the purpose of the algorithm leaks?
- bawolff 6y ago
  Principally yes, but it also aims to protect against evesdroppers for example. Many usecases want to keep the algorithm being invoked secret (by having it run on a computer the requester does not have access to) Anyways, the reason i asked is because the grandparent said "attacker can memorize the input and output", which is not something the entity doing the computation can do, as they only see the encrypted text, and encrypted values never repeat (or only with negligible probability) even if the plaintext they are encrypting are the same. The end user entity on the other hand, could try (in theory, not practically) every single value, memorize it, and recreate the secret function. So if the attacker in this scenario is the entity encrypting/decrypting the data, some of the grandparent's post makes more sense.
infogulch 6y ago
Yes it's encrypted, but the unit of encryption is individual values. If you multiply two arrays of values, they the computer/attacker can't tell exactly what each value is but could observe that, say, elements 7 and 12 are the same. Thus leaking some information about the data set.
- im3w1l 6y ago
  Would it be possible to add random low order bits to prevent that? E.g instead of doing 7 * 9 you do 7.00024378 * 9.00003891
  - bawolff 6y ago
    FHE involves adding random noise pretty constantly (FHE kind of works by adding noise at every step, and regulary does a magic encrypted re-encryption step where during evaluation the intermediate values are reencrypted without ever revealing the original value, to get rid of the excess noise). Anyways, FHE is secure against (non-adaptive) chosen plaintext attacks. That among other things means that if E is the encryption function, E(7) != E(7), and if you have E(x) and E(y) you cant tell if x and y are related to each other unless you have access to the decryption function.
- bawolff 6y ago
  FHE is semantically secure against chosen plaintext attacks. (The gentry latice scheme paper claims it is semantically secure against chosen plaintext attacks [1]) If i understand that correctly, it means that when you encrypt a value, you always get a different value, even if the plaintext is the same. So how would the attacker observe that value 7 and 12 are the same without decrypting the value? [1] https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf&ved=2ahUKEwjk3_GVtqLvAhXOv54KHXr7AL8QFjAAegQIARAC&usg=AOvVaw2TF2r7JBQH-oS953IAY4Is https://www.google.com/url?sa=t&source=web&rct=j&url=https:/... P.s. are you maybe confusing FHE with deterministic encryption or order-preserving-encryption which is sometimes used in "encrypted" (scare quotes because they're pretty bad) db products that still want to allow queries on encrypted data. That's a totally different thing with much much weaker security garuntees.

sigstoat 6y ago

> Once this is filled a bit, he can use that with some heuristics to estimate the data. how many inputs do you need before the heuristics start letting you guess than a function with 128 bits of input is a 64 bit multiply? and if the input is 8192 bits? i feel like you're reporting some theoretical ("needs 2^1024 ciphertexts!") attack as though it is a practical concern.

glitchc 6y ago

FHE leaks information indeed. It's proven to not be secure against a chosen ciphertext attack.

bawolff 6y ago
Well this is unfortunate, i can't help but feel that many of the usecases for FHE are much less likely to have decryption oracles than traditional encryption would. I'm also not sure if i would say "leak information" is the right word to describe a chosen ciphertext attack.
paconbork 6y ago
It's not that straightforward. There's two types of chosen ciphertext attacks: IND-CCA1 (non-adaptive) and IND-CCA2 (adaptive). There are in fact FHE schemes for the former such as https://www.iacr.org/archive/pkc2017/101750203/101750203.pdf https://www.iacr.org/archive/pkc2017/101750203/101750203.pdf The problem comes in the adaptive case. In the distinguishing game, an adaptive adversary can have the decryption oracle decrypt any ciphertext after it receives its challenge ciphertext (besides the challenge itself, as that would be trivially defeatable). However, if the adversary receives Enc(m), they can just compute Enc(m+m) and ask the oracle to decrypt it, thus winning the game. No FHE scheme will be IND-CCA2 secure by definition, but that doesn't mean that they "leak information" in the applications FHE is being proposed for. As long as you're not decrypting arbitrary ciphertexts for the server you just uploaded your sensitive encrypted information to, you can have your delegated computation, as a treat.

paconbork 6y ago

This is inaccurate. Any encryption that cryptographers will accept will be semantically secure at a minimum (which FHE is). Briefly, to quote Gentry's paper which first showed the existence of FHE: this means given a ciphertext c that encrypts either m0 or m1, it is hard for an adversary to decide which, even if it is allowed to choose m0 and m1. This rules out deterministic encryption, which is not sufficient for the reasons you mention (and is why, for example, you shouldn't use textbook RSA). Also it's actually easier to prove that FHE applications are secure than it is to prove a lot of other things. FHE is designed around commonly used hardness assumptions, such as the Learning With Errors problem. As long as you're encrypting your information correctly there's really nothing Intel can do to leak your information short of disproving open conjectures in computer science. At the very least, they probably won't fumble their way into doing so

joppy 6y ago

Isn’t this the whole problem in homomorphic encryption? We already have cryptographic systems for which encryption is a homomorphism, such as RSA. I thought that the whole problem was finding ways to do it that don’t leak any data, basically.