11 ms·
TFHE: Fast Fully-Homomorphic Encryption Over the Torus
- otoburb 9y agoFor a layman like myself, downloading and skimming the reference papers at the bottom of the page, starting with Craig Gentry 2013's paper[1], really helped. [1] https://eprint.iacr.org/2013/340 https://eprint.iacr.org/2013/340
- EGreg 9y agoIs this available now? Can we do fast homomorphic encryption baby??
- mSparks43 9y agohave to say, i'm extremely skeptical of homomorphic encryption. it just screams side channel attacks. so skeptical i dont have the energy to find them, better to wait until something with monetary value is cruising around the internet using it.
- striking 9y agoHomomorphic programs are designed to run without knowledge of the key. You have to process every piece of data in basically the same way. So I'm not entirely sure where you think the side-channel attack would arise.
- rocqua 9y agoMy first guess would be conditionals, but I'd guess there is no real branching in the execution of operations on data. Another would be evaluating comparisons, but those aren't very easy to do in bitwise terms, and you can't read the output either.
- schoen 9y agoBut the thing about this setting is that you don't possess the secrets, so you can't reveal the secrets by noticing how long things take. An analogy to think about might be blind signatures. In blind signatures you sign a blinded token and then the other party can unblind it to get a valid signature from you over a message whose content you don't know. This is classical public-key cryptography. In that case there is a secret key, and a timing attack against someone who can observe the signature creation might reveal that key. The connection between the blinded and unblinded message is also meant to be secret, and a timing attack against someone performing the blinding or unblinding operations might also reveal that relationship. However, there is no timing attack that the signer can perform against itself to reveal the relationship between the blinded and unblinded messages, and there is no timing attack that the other party can perform against itself to reveal the secret key. I think this analogy holds up for most purposes (indeed, blind signatures can be viewed as an extremely specific, narrow kind of homomorphic encryption), but I'd be happy to hear corrections if someone can see a way that it doesn't.
- mSparks43 9y agoso whats the "cloud-keyset " then? the "side channel" i am referring to is in however this impliments this mixing you refer to. if you can observe how the internal state is changing given a cloud keyset you should be able to infer the secret key. in the same way you can infer the iv used in a mesernine twister from like 27 cycles (or whatever). downvotes and promises definately wont reduce my skeptacism.
- enigma83 9y agoThe "cloud keyset" is another name for "public key". Usually, public key enables encryption but no decryption, here, the cloud key enables computations on ciphertexts, but not decryption. Like in public key cryptography, you can give a RSA public key to an adversary, he can use it as much as he want, he will not be able to get any information on the private key (in any practical time). Most importantly, the cloud key is not secret, nor obfuscated: the cloud already knows each bits of it (side channel attacks are not relevant). The "cloud key" is the public part of the key given to the cloud so that he can perform his operations (circuit, bootstrapping). There are strong security proofs that show that it is impossible to recover the secret key from the cloud key. In the case of TFHE, if there was a polynomial algorithm that would recover even a single bit of the secret key given the cloud key, this algorithm could be used to break the LWE problem, and also worst case instances of lattice problems (which are much harder than factorization or discrete log for instance).
- mSparks43 9y agobecause the simple fact you can process the data and examine the output reveals untold quantities of information about the key. the known plaintext attack breaks pretty much every crypto system, mix that with statistical analysis of this "processing" and I'm sure whatever is in the cloud will surrender its secrets pretty quick. And all that risk for what benefit? none of this processing will ever be faster than doing the processing in place.
- benchaney 9y ago> the known plaintext attack breaks pretty much every crypto system This isn't true at all.
- mSparks43 9y agoaside from aes and its varients, which of the other thousands of crypto systems arent vulnerable to it?
- benchaney 9y agoNone of the other AES finalists were vulnerable to known plaintexts attacks. Neither is 3-DES or chacha20. DES and RC4 are now considered insecure, but in their day they were resistant known plaintext attacks as well. Other than some toy examples, and cryptosystems that were used before cryptography was studied academically, I can't think of any that are vulnerable to known plaintext attacks.
- yorwba 9y ago> And all that risk for what benefit? none of this processing will ever be faster than doing the processing in place. The benefit comes into play when you mix data from different sources that don't trust each other (to the point where they would never agree to one of them doing the processing in place). Homomorphic encryption allows combining the data without ever revealing it to the one doing the computation.
- 9y ago
- striking 9y ago"Each binary gate takes about 20 milliseconds single-core time to evaluate" So yes, for varying definitions of "fast".
- SilasX 9y agoIf you equate a binary gate operation with an instruction, then that's 50 instructions per second, which compares to UNIVAC's 2000 IPS (0.002 MIPS). https://en.wikipedia.org/wiki/Instructions_per_second#Timeline_of_instructions_per_second https://en.wikipedia.org/wiki/Instructions_per_second#Timeli... Of course, an op on a single bit is still far short of a CPU instruction, AIUI. You gotta start somewhere though!
- jacobush 9y agoSo a cluster of modern cores could approach a UNIVAC...
- jondubois 9y agoI feel like there are so many use cases for this library.
- tome 9y agoWhat operations can I do homomorphically with this library? The page says "With the cloud-keyset, the library can evaluate a net-list of binary gates homomorphically at a rate of about 50 gates per second per core, without decrypting its input. It suffices to provide the sequence of gates, as well as ciphertexts of the input bits. And the library computes ciphertexts of the output bits." but what does "evaluating a net list of binary gates" come to in practice? What operations could I expect to be able to perform?
- mmastrac 9y ago> What operations can I do homomorphically with this library? Basically anything. If you can generate a netlist of gates of your HE CPU, you can write a program to compute it (perhaps slowly, though).
- tveita 9y ago"The library supports the homomorphic evaluation of the 10 binary gates (And, Or, Xor, Nand, Nor, etc…), as well as the negation and the Mux gate." So you'd program it by designing a digital circuit using AND, OR, and NOT gates, somewhat similar to how you would make a circuit with physical components. You have millions, maybe billions of these gates in your CPU, each capable of doing millions of calculations for each tick of your homomorphic gate, so the "fast" in the title should be taken with a grain of salt. Your homomorphic circuit could have a noticeable delay adding two 64-bit numbers. https://en.wikipedia.org/wiki/Logic_gate#Symbols https://en.wikipedia.org/wiki/Logic_gate#Symbols https://tfhe.github.io/tfhe/tuto-cloud.html https://tfhe.github.io/tfhe/tuto-cloud.html
- lisper 9y agoIt's fast relative to the previous state of the art in homomorphic encryption. But the path to practical applications is always paved with incremental improvements.
- simcop2387 9y agoI wonder then how implementable this is in an FPGA for accelerating the whole thing? This could be a killer use of the FPGA instances on AWS and similar cloud services.
- saganus 9y agoThis looks very interesting! However, not being an expert on FHE, is there a way to leverage this on current RDBMS systems for example? It says the library can evaluate binary gates. If we would like to run a SQL query for example, how do we translate it to a series of gates? Is it possible? Or is this so low level that we basically would need to build our own "processor" with binary gates and then build the rest of the stack on top of it so we can, in the end, run a query? Can anyone shed some light on how exactly can we take advantage of this library?
- gravypod 9y agoWe could implement an idealized RISC processor in gates and "flash" it with a program..... That would be fun.
- roywiggins 9y agoAt 20ms per AND, that's 50 Hz. That's... slower than useful, surely?
- swordswinger12 9y agoFully homomorphic encryption isn't tremendously useful for database queries - you end up having to put the entire database in a massive FHE ciphertext, then expressing the query as a circuit which requires time linear in the size of the database to return a result.
- proofofstake 9y agohttps://www.youtube.com/watch?v=xsaXMUelOEA https://www.youtube.com/watch?v=xsaXMUelOEA "CryptDB: Processing Queries on an Encrypted Database - Microsoft Research"
- swordswinger12 9y agoTFHE is not even in the same galaxy as CryptDB. Comparing the two is like comparing an apple and a 2007 Honda Civic. They're polar opposite approaches to executing queries on encrypted databases.
- sandGorgon 9y agoWill this be useful for machine learning in the same way as this ? https://medium.com/numerai/encrypted-data-for-efficient-markets-fffbe9743ba8 https://medium.com/numerai/encrypted-data-for-efficient-mark...
- amenghra 9y agoThis is very interesting from an academic/theory point of view. There currently aren't a lot practical use cases where we can afford a performance loss of ~100,000,000x (your homomorphic crypto algorithm is going to run on the order of ~Hz on a ~Ghz CPU).
- proofofstake 9y agoYes, but not to the same degree. Numerai uses structure-preserving encryption / neural encryption. This allows people to use any existing machine learning algorithm on the data. For fully homomorphic encryption you would need specialized algorithms. These are way more difficult to design. They also run slower.
- fenollp 9y agoThis looks like the slowest routines are FFT and GEMM (CPU bound). I wonder if one can find DSPs easily for racked servers. Maybe hardware h264 encoders can be repurposed that way? I obviously don't know what I am talking about! Would an FPGA implementation accelerate execution?
- DannyBee 9y agoYes, FPGA can help, as can GPU. The real problem tends to be the (CPU to other thing and back again) latency, not the how fast can the other thing do the computation.
- michwill 9y agoThat's a seriously cool thing to have in the toolbox! Does it produce only encrypted output, or can it optionally produce unencrypted results also? Can it optionally use public data as an input? Also I am guessing if it could be accelerated on GPUs. I worked with a guy who accelerated a standard FFT on CUDA 100..1000 times for scientific computations (and later NVidia copied his code, lol). I wonder if something similar can be done here
- hmottestad 9y agoThe point is to be able to give encrypted data to a third party and have them do operations on that data (ex. sum all the values) and give you an encrypted result back. tldr. computations in the cloud with encrypted, private data
- michwill 9y agoYes, I understand. I was thinking about: a) smart contracts controlling something within the encrypted data based on publicly available data; b) encrypted key-value store where you traverse the tree structure based on encrypted query and encrypted tree buckets, but get a publicly available result about which bucket is next (similarly to how it was done in Arx paper using garbled circuits).
- mSparks43 9y agobecause, obviously, summing all the values is something you couldnt do yourself?
- proofofstake 9y ago> This work leaves much room for improvement, however. For example, the throughput and latency can be significantly improved by using GPUs and FPGAs to accelerate the computation. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/04/CryptonetsTechReport.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... > We demonstrate CryptoNets on the MNIST optical character recognition tasks. CryptoNets achieve 99% accuracy and can make more than 51000 predictions per hour on a single PC. Therefore, they allow high throughput, accurate, and private predictions.
- phkahler 9y agoOne interesting thing about this: You are performing known operations on unknown data. But theoretically you could simulate a generic computer whose program is encrypted data as well, thus enabling unknown operations on unknown data. However, with speeds in the ms per gate we are a long way from that being practical right now.
- erikpukinskis 9y ago> with speeds in the ms per gate I wonder if you could write your programs in such a way that the bulk of the computation was done publically, and only sensitive ops were shunted out to the secure processing network. Maybe in a language similar to Erlang, but instead of writing code that's amenable to sharing between multiple CPUs, you'd be sharing between multiple degrees of privacy.
- Bromskloss 9y ago> I wonder if you could write your programs in such a way that the bulk of the computation was done publically, and only sensitive ops were shunted out to the secure processing network. Do you have some example of what such an application may be?
- dllthomas 9y agoOff the top of my head, maybe something like: 1) Secretly compute a list of encrypted tags and associated, unencrypted scores. 2) Sort by scores. 3) Convert the highest N tags back to encrypted data. As a plus, steps 1 and 3 should be embarrassingly parallel. You are, of course, leaking a count, which can be important (but your opponent can already make inferences based on the amount of data you have stored...).
- phaedrus 9y agoEncode computations as NP hard graph optimization problems. Use the public computation resources to solve the hard part, but keep the labels of the nodes and edges in the slower encrypted computing resource.
- 9y ago
- anfractuosity 9y agoSounds very interesting!, I'm going to have to look at in more detail. I'm just wondering how it compares to something like https://github.com/shaih/HElib https://github.com/shaih/HElib
- enigma83 9y agoThe best analogy is that Helib is a homomorphic GPU while TFHE is a homomorphic CPU. Elementary operations (addition, multiplication modulo p) with Helib are slower (especially bootstrapping), but are performed on a huge vector of data simultaneously. In the opposite, elementary operations with TFHE (binary gates) are extremely fast, but deal with a single bit. In other word, if the application you are aiming at is suitable for running on a GPU, go for Helib, else if it would be faster on a CPU, use TFHE.
- anfractuosity 9y agoInteresting! Thanks for the reply.
- Bromskloss 9y agoWould it be correct to say that general homomorphic computing is now (and perhaps already before this) possible, though slow?
- Bromskloss 9y agoWhat does "over the torus" mean here?
- cypherpunks01 9y agoI think it means that this implementation of homomorphic encryption relies on polynomial computations being done on the plane of a geometrical torus? See the relevant paper here: https://eprint.iacr.org/2016/870.pdf https://eprint.iacr.org/2016/870.pdf Someone with more background could probably expand on that.
- gigatexal 9y agoso who's going to write the Python wrapper to this?
- deleted 9y ago[deleted]