Hacker News Reader

Comment by bawolff | Hacker News Reader

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?

View on HN

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?

Reply on news.ycombinator.com