4 ms·
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 o
by 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 agoThe threat model for FHE is that the attacker is the entity doing the computation
- monstersinF 6y agoDoesn’t that threat model defeat the purpose of the algorithm leaks?
- bawolff 6y agoPrincipally 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 agoYes 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 agoWould 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 agoFHE 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 agoFHE 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.
- littlestymaar 6y agoHonestly, 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 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 }