Hacker News Reader

Comment by KETpXDDzR | Hacker News Reader

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.

View on HN

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

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?

The threat model for FHE is that the attacker is the entity doing the computation

Doesn’t that threat model defeat the purpose of the algorithm leaks?

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.

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.

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

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.

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:/...

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.

Honestly, I don't understand how you can get downvoted for this answer. The GP should be downvoted in oblivion, because it obviously doesn't know what it's talking about, yet you are the greyed one…

If people don't believe the parent post and would like to see a visual “proof” of it, here is the (abbreviated) ciphertext for same value (`true`) encrypted by [TFHE](https://github.com/tfhe/tfhe), note how these aren't the same:

{ coefficients: [-224220402, 1267713220, 372943361, 263858338, -370546283, -605917751, -1924979310, -1572775794, 1846572795, -468768480, -290510339, -915978400, -1364310315, 809081884, -1495989601, -331539817, -1453231071, 404566454, 495420049, -879411073, 830751792, -517575314, 1556751889, 443973073, 1944290005, 674176195, -2141487034, -317403947, -460501881, -530948496, -1701307365, -1131020764, -951177975, 185735343, -607301526, -1413023671, -927580822, -1519370777, -867508577, 1783197541, -1563558893, 1077184331, 1711379115, 1493923712, 1553459001, -1181497038, 2076454627, 2090667603, -1811778643, -1964586812, -1514194032, 1847333213, -29937879, 1408366270, -246399878, -2100573013, 143332974, 355615400, -1746332080, 1803753774, 1010929751, -178538162, 2019489654, -1762380579, 1676883032, 855666812, 2078455615, 1070127391, -310916718, 1972027124, 1145751265, 1391734199, …], b: -362940425, current_variance: 0.0000000009313225746154785 }

{ coefficients: [-297806840, -994586634, 304850282, 863793687, 1840210042, -1105546555, -1110462781, 858561202, 1572862702, -1414807433, 925868178, -2022139768, 1977503124, -1355884545, 252233845, -607580470, -1640661899, 184197878, 175367248, -1883040938, -1452285303, 2135910408, 1848643984, 277669753, 1205220991, -1010438927, 344717140, -616704798, 617000592, -706461456, -1674056437, -1108542319, 1209547087, -1275731206, -1050202170, 1804450949, -212790115, 1603633119, 1581631548, 891985869, -767711288, 1662132229, -488697271, 1729020643, 68369628, 594815617, -697565685, -1119636178, -1069556471, 668091191, 2058655289, -965364559, -428300746, 1288771675, -1291673545, -1936980021, 1344393745, -566147990, -2017181358, -876369855, 1202714564, 279954504, 1954812679, -121935512, 1508624251, 1746889815, 10036320, -694130814, 1749036054, -350031511, 856310504, -486108325, 447226889, -108777191, 1323665880, 819541960, 441166350, -934866202, 837730330, 281902593, -1870154550, 963192542, 649262920, -2012432624, 1553637232, 627237492, 616166507, 781074188, 44864017, -1911286875, -1429302424, -1054092570, -1620457762, 641734226, 1629006914, 1365659737, 360668934, -874923908, …], b: 27536240, current_variance: 0.0000000009313225746154785 }

That's partially what random filler values are for.

Also, aren't there FHE algorithms or potential constructs for encrypting blocks of data using the index as part of a shared secret?

> 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.

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.

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

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.

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

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.

Reply on news.ycombinator.com