TFHE: Fast Fully Homomorphic Encryption over the Torus | Hacker News Reader

TFHE: Fast Fully Homomorphic Encryption over the Torus

tfhe.github.io

97 pointsEvgeniyZh54 comments

Quick 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

If 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?

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

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

It 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)

unfortunately FHE doesn't work like you describe. in FHE, the answer output is always indistinguishable from random noise. in fact, the "encrypted decryptor" routine you're describing is more or less how bootstrapping works - the ciphertext is double-encrypted to the bootstrapping key, the circuit evaluates decryption of the encrypted ciphertext to produce a fresh ciphertext against the bootstrapping key, then a key switching operation exchanges the bootstrapping key for the evaluation key.

* needing certain policies to be met for decryption is the field of attribute-based encryption.

* only being able to evaluate certain functions of a ciphertext to decrypted plaintext is the field of functional encryption.

* the general holy grail you're describing is program obfuscation - a secure black box that evaluates an arbitrary circuit on an input. unfortunately there are strong impossibility results in program obfuscation, though there's some theoretical progress towards weaker obfuscation or much more limited types of circuits, involving extremely inefficient mathematical wizardry that's regularly being badly broken by cryptanalysis.

in summary, you've confused FHE with program obfuscation, and the decryptor routine you describe is just bootstrapping.

I still think even with viable FHE, my personal information should not be shared with a 3rd party, it should be treated as if it was still plain text. I say this because like any crypto work,being vaible isn't enough it needs rigorous testing over time and lots of peer review.

Even for FHE adoption, it would be horrible if a lot if trust went into it and one popular method or implementation messed it up, ruining its reputation.

I 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?

You can't do control flow homomorphicly, so that tends to throw a wrench into this kind of thing.

What is the set of operations that are supported?

I think the answer to this would be enough to determine if it's a base for the vector space of operations.

This may be enough, right? https://tfhe.github.io/tfhe/gate-bootstrapping-api.html

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

Please 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?

Are loops general control flow? Can they do branching?

I don't think so, but not sure.

loops as in "feedback in a circuit", not code loops. Feedback is necessary to create stateful circuits, state is necessary for "control flow"

Yes, it can be stateful. We built processor

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

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

I guess then that my hypothetical fully homomorphic C-64 would be huge and would have a limited run-time?

Yes. No recursion. Essentially what could be fabbed as a circuit

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

If you can branch then you can always run a program that compares the encrypted value to a constant, then iterate over the whole space of possible values for the constant and that way decrypt the value

CPUs are a circuit. What are you on about?

Ergo, you can model anything CPUs do as a matrix.

We've asked you before to edit the swipes out of your comments here. If you keep doing it, like here and https://news.ycombinator.com/item?id=22847040 from yesterday, we're going to have to ban you. I don't want to do that, so would you please just make your substantive points thoughtfully?

If you wouldn't mind reviewing https://news.ycombinator.com/newsguidelines.html and sticking to the rules when posting here, we'd be grateful.

No, any program can be converted into a matrix form.

Non-terminating programs are modelled as infinitely-sized matrixes, which are obviously not computable; but neither are non-terminating programs computable in the real sense.

Yes, of course you can do if conversion. The exponential increase in execution time is the wrench I was talking about ;).

Not if you can properly model sparse matrices.

If you can do a NAND gate homomorphically you can do an entire computer.

only if you are allowed stateful circuits! if its a FUNCTION i.e. straight input->output mapping, then no, you cannot do a "computer"

ShapeCPU was the first one that I know of (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

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

From 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?

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

We made our original CPU&ISA emulator over TFHE. 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)

Our original CPU, CAHP-emerald is 5 stage pipeline, super-scalar processor. Pipelining improved performance well. https://github.com/virtualsecureplatform/cahp-emerald

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

I'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/... 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.

It looks like ShapeCPU originated around 2012 but only made it into posters, not papers. It's kind of a shame because I spent quite some time reproducing their work to confirm that it was viable, then building on top of it with HideCPU.

Lots of prior art in that implementation!

How hard would it be to use Yosys (http://www.clifford.at/yosys/documentation.html) for logical gate synthesis to run arbitrary Verilog on TFHE?

Something equivalent is done in 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.

Cingulata currently supports TFHE. 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

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

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

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

Tallying of encrypted votes, allowing for secure voting over the internet.

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

Theoretically, FHE can perform any computation including training neural networks. Practically, it's still not viable because of the overhead.

I 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?

Regard the process of fitting a statistical model as a function mapping input training data to output model parameters.

If the homomorphic encryption scheme allows for arbitrary functions to be computed, it could work for particular functions of statistical model fitting (perhaps appallingly slowly).

The output model will be encoded as cyphertext.

It would be possible to evaluate the fitted cyphertext model on new features to make predictions, also output as cyphertext.

> the library can evaluate a net-list of binary gates homomorphically at a rate of about 76 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.

You could do secure anonymous DNA testing. Just submit your encrypted genome and their FHE algorithm, presto chango, computes the answer to your sensitive queries without them knowing the result.

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

If you can do binary, then you can represent floating point numbers, no?

TFHE is known to be switchable between other RLWE based Homomorphic Encryption. 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

AFAIK, Homomorphic Encryption which supports floating point arithmetic is not known. Fixed point one is known, CKKS. https://github.com/snucrypto/HEAAN

I imaging further developments in this technology will lead to some sort of private ethereum-like coin.

Reply on news.ycombinator.com