7 ms·
TFHE: Fast Fully Homomorphic Encryption over the Torus
- api 7y agoI wonder at what point might we implement a very old CPU like the 6502/6510 on this and demonstrate the proof of concept of e.g. a very very slow fully homomorphic Commodore 64 emulator. Has it been done?
- KenoFischer 7y agoYou can't do control flow homomorphicly, so that tends to throw a wrench into this kind of thing.
- imglorp 7y agoWhat is the set of operations that are supported?
- aneutron 7y agoI think the answer to this would be enough to determine if it's a base for the vector space of operations.
- nindanaoto 7y agoThis may be enough, right? https://tfhe.github.io/tfhe/gate-bootstrapping-api.html https://tfhe.github.io/tfhe/gate-bootstrapping-api.html
- imglorp 7y agoSo it looks like you can have: CONSTANT NOT COPY NAND OR AND XOR XNOR NOR ANDNY ANDYN ORNY ORYN MUX ... so pure, combinational logic operators. You can build up some serious functions with these, yes.
- artemonster 7y agoPlease correct me if I am wrong: you can simulate a function built out of binary gates with encrypted data, but you cannot simulate a state machine over encrypted inputs? Since the webpage says "arbitrary circuit", so it can have loops, so it can be stateful, right? Is this somehow fundamental restriction or just not solved yet?
- lonelappde 7y agoAre loops general control flow? Can they do branching? I don't think so, but not sure.
- artemonster 7y agoloops as in "feedback in a circuit", not code loops. Feedback is necessary to create stateful circuits, state is necessary for "control flow"
- nindanaoto 7y agoYes, it can be stateful. We built processor
- heavenlyblue 7y agoNo, you can. Any control flow program can be converted into a matrix multiplication. Obviously, the matrix size is exponential to the number of if conditions - but that is a pre-requisite for homomorphic encryption anyway, otherwise you would be able to tell which branch was taken.
- dragonwriter 7y ago> Any control flow program can be converted into a matrix multiplication. Any control flow program, on a set of inputs for which it terminates[0], can be, but it's not true that any control flow program, with unspecified inputs, can be, even with variables for the inputs, since the shape of the multiplication as well as the value of elements in the matrices may depend on the inputs (also, whether it's even a terminating program can obviously depend on the inputs.) [0] and any program which always terminates can also be, though the general form may be more complex than is necessary for some inputs.
- api 7y agoI guess then that my hypothetical fully homomorphic C-64 would be huge and would have a limited run-time?
- lazersharkman 7y agoYes. No recursion. Essentially what could be fabbed as a circuit
- api 7y agoI get it. I think I had the misconception that you could branch in FHE, but as I think about it this would by its nature reveal quite a lot of information about the plaintext. Would it perhaps be possible to create a weaker form of homomorphic encryption that could branch? It would not be strong enough for the most serious security use cases (authentication, financial, etc.) but would perhaps be usable for cases where you just want to protect data confidentiality e.g. processing PII. The processor could probably infer the structure of the running program but not necessarily its data if appropriate constant-time comparisons and other constructions were used.
- phkahler 7y agoIf you can do a NAND gate homomorphically you can do an entire computer.
- artemonster 7y agoonly if you are allowed stateful circuits! if its a FUNCTION i.e. straight input->output mapping, then no, you cannot do a "computer"
- deleted 7y ago[deleted]
- mmastrac 7y agoShapeCPU was the first one that I know of (https://github.com/hcrypt-project/obliviousJ https://github.com/hcrypt-project/obliviousJ). I built one off the same infrastructure called hideCPU. If you can create AND/XOR/NAND/etc gates _and_ feed-back output into your input, you can create a CPU. https://github.com/mmastrac/oblivious-cpu https://github.com/mmastrac/oblivious-cpu My goal was more to build some open prior art in the space rather than actually build a viable FHE CPU, but there's no reason why you couldn't implement one of these on top of the FHE system. To answer some statements about FHE computing that come up over and over: - Yes, you can loop + perform control flow in a FHE-based computer - Yes, you can recurse in a FHE-based computer as long as you have enough emulated RAM/stack - Yes, you can store state in a FHE computer - No, you cannot determine if a FHE computer has reached a certain state (or halted) from the outside without decrypting the system (or at least a state bit) - Yes, you can emulate RAM in a FHE computer - Yes, you can emulate a HDD (well, rotating storage) in a certain FHE computer constructions
- rjeli 7y agoFrom some napkin math and googling, a 6502 has 4.5k transistors, which at 13 ms per gate is about a minute per cycle, divided by how many gates there really are per transistor. How does your implementation compare?
- mmastrac 7y ago~20k gates total (ShapeCPU was ~30k gates), but the _real_ bottleneck for FHE computing is the longest path from input to output as FHE computers are highly parallel. I am sure I had a stat for the longest path from input to output, but I'm a few years swapped out on this project. Note that adding pipelining to a CPU drastically reduces the longest path. ShapeCPU is not pipelined at all which probably means there's a bunch of low-hanging fruit.
- nindanaoto 7y agoWe made our original CPU&ISA emulator over TFHE. https://github.com/virtualsecureplatform/kvsp https://github.com/virtualsecureplatform/kvsp Because we use chisel to write CPU and we also made LLVM backend for our original CPU, your idea is not so difficult although it may be very slow. Our original CPU is about 4K gates. The most difficult point is building memory because it is most slow part. We used TFHE's LHE mode for it and this is one of the novel points of our work. (We didn't know about Shape CPU but it seems to be similar to FURISC, which is published and using libScarab.https://eprint.iacr.org/2015/699 https://eprint.iacr.org/2015/699)
- nindanaoto 7y agoOur original CPU, CAHP-emerald is 5 stage pipeline, super-scalar processor. Pipelining improved performance well. https://github.com/virtualsecureplatform/cahp-emerald https://github.com/virtualsecureplatform/cahp-emerald
- mmastrac 7y agoInteresting. FURISC looks like it cribbed a lot of ideas off ShapeCPU without referencing prior art. I find it hard to believe someone would be working on a libScarab-based CPU without seeing ShapeCPU as well. Encrypted termination conditions were definitely in that implementation. The memory mux too.
- nindanaoto 7y agoI'm also doubting that but before I knew Shape CPU, I believed because FURISC seems to be based on HEROIC, which is claimed to be the first processor emulation over homomorphic encryption. https://past.date-conference.com/proceedings-archive/PAPERS/2014/DATE14/PDFFILES/09.3_4.PDF https://past.date-conference.com/proceedings-archive/PAPERS/... I think FURISC is more like HEROIC than ShapeCPU. By the way, I feel sad for there is no publication of ShapeCPU. I guess that this is one of the causes of FURISC paper is lacking reference for ShapeCPU.
- mmastrac 7y ago
- motohagiography 7y agoIf viable, FHE solves some very urgent problems in sharing personal health information data sets for research, and there are literally billions of dollars in individual transaction data locked up behind legal firewalls in banks. This is a great usable library we can reason about, but in terms of a trust model for it, is TFHE a candidate or on a certification path? Given people trust institutions, and institutions trust other institutions that trust math, from people who write the code - you have the math and the code, my question would be, which institutions can we help to get priority for trusting this?
- sterlind 7y agoyou might be thinking of functional encryption. FHE doesn't make much sense for data sets because you can't read the answers.. you can perform any operation you want to, run any program, but you'll just read out ciphertexts. functional encryption is the one where you can only apply certain functions but you get plaintext out.
- motohagiography 7y agoIt's possible you haven't encountered these data issues in practice as well, given the use case floated in healthcare discussions for FHE is as a replacement for the infrastructure required for something like differential privacy, tokenization, and the failures of data set de-identification. While I am not an FHE or FE developer, as a probable end architect for solutions that will use it, the question of what makes this trustworthy is key.
- candiodari 7y agoIt is trivial to create almost any encryption scheme from a fully homomorphic algorithm: You create a program, which after all is just a set of simple instructions. If you can do homomorphic add, mul and mod you have everything you need, and I believe you can work with just a few bit operations. So you make a homomorphically encrypted program that has an encryptor en decryptor routine, themselves encrypted (and can thus safely contain a private key), and that program then does the operations requested, which does indeed get you an encrypted result. Then you ask the encrypted program to please decrypt the answer. It can validate that question however it wants (implementing privacy policies seems like it would be a good way to do that here), and if it agrees, it decrypts the answer. There's all sorts of schemas you can build into this to do replay protection. For the truly paranoid such a program can be created with a random encryption key that is then deleted as soon as the program is created. Then there is no trust of anyone at all. You could implement bitcoin, or a totally secure root of trust of for example the dns root zone on the internet. The only problem is that changing the program becomes impossible for anyone, which may be a good thing. And you keep homomorphic guarantees: No need for trust. No need for trusting the CPU your homomorphic program executes on, or it's memory. NO information, not the code, not the temporary values, not the memory, not the stack ever, at any time in the program's execution, exists unencrypted. (paraphrasing a paper that pointed out that implementing bitcoin-like systems with homomorphic encryption is very easy indeed, which is a similar problem)
- isatty 7y agoQuick ELI15: Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext. A cryptosystem that supports arbitrary computation on ciphertexts is known as fully homomorphic encryption (FHE). https://en.wikipedia.org/wiki/Homomorphic_encryption https://en.wikipedia.org/wiki/Homomorphic_encryption
- physicsyogi 7y agoSince TFHE does the encryption at the binary level, it looks like it would need to also work on the float level to be useful for a lot of data science/machine learning use cases. I could be wrong though.
- malux85 7y agoIf you can do binary, then you can represent floating point numbers, no?
- nindanaoto 7y agoTFHE is known to be switchable between other RLWE based Homomorphic Encryption. https://eprint.iacr.org/2018/758 https://eprint.iacr.org/2018/758 Glyph applied it to accelerate deep learning, but they use integer level, not float. https://arxiv.org/abs/1911.07101 https://arxiv.org/abs/1911.07101 AFAIK, Homomorphic Encryption which supports floating point arithmetic is not known. Fixed point one is known, CKKS. https://github.com/snucrypto/HEAAN https://github.com/snucrypto/HEAAN
- deleted 7y ago[deleted]
- ttsda 7y agoI imaging further developments in this technology will lead to some sort of private ethereum-like coin.
- gumby 7y agoWhats the real world application? For example you can't train a neural network on such a database as all the values are no longer commensurate.
- datenwolf 7y agoOne application would be distributed storage systems where the user doesn't trust the service provider. Using FHE one could implement a distributed storage system, with replication, conflict resolution, error correction and so on, without ever revealing the plaintext to the storage and compute provider.
- canistel 7y agoA Swiss private bank can encrypt and keep its data outside Switzerland. Daily data processing batches can be executed over encrypted data. In theory at least...
- em3rgent0rdr 7y agoTallying of encrypted votes, allowing for secure voting over the internet.
- Enginerrrd 7y agoSeems like overkill. I'd rather just see every vote get a random unique identifier and all the votes get sent to a central database that is publicly searchable with the identifier.
- ajconway 7y agoTheoretically, FHE can perform any computation including training neural networks. Practically, it's still not viable because of the overhead.
- gumby 7y agoI don’t understand how that could work (unless you decrypted the data). The point of this encryption is that you can’t see what’s in the underlying data so two identical values will be encrypted to different values, no?
- rjeli 7y agoHow hard would it be to use Yosys (http://www.clifford.at/yosys/documentation.html http://www.clifford.at/yosys/documentation.html) for logical gate synthesis to run arbitrary Verilog on TFHE?
- ssmiler 7y agoSomething equivalent is done in https://github.com/CEA-LIST/Cingulata https://github.com/CEA-LIST/Cingulata The current execution run-time accepts a .blif file (a Boolean circuit) and executes it. For the moment only the BFV homomorphic encryption can be used. Although, supporting TFHE will not be so hard and some work is going on the parallel_bit_exec branch.
- nindanaoto 7y agoCingulata currently supports TFHE. https://github.com/CEA-LIST/Cingulata/wiki#headlight https://github.com/CEA-LIST/Cingulata/wiki#headlight We also used Yosys to convert Chisel into JSON netlist. It is easy to use. I hope this may help. This is archived but simple. https://github.com/virtualsecureplatform/V2TT https://github.com/virtualsecureplatform/V2TT