TFHE: Fast Fully-Homomorphic Encryption Over the Torus

[phkahler]

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

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

[branja]

all the fun problems in CS are intractible

[otoburb]

For 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

[tome]

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

[tveita]

"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://tfhe.github.io/tfhe/tuto-cloud.html

[mmastrac]

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

[skybrian]

I haven't studied this much, but to speculate, it sounds like each gate is a boolean expression (AND, OR, XOR, NOT). So this lets you compute boolean functions on bits. I don't see a way to compute a loop, though, other than perhaps to unroll it and send lots of instructions.

Also, 50ms per bit operation, though apparently an improvement, sounds extremely inefficient compared to normal programming.

[Cyph0n]

You can compute anything, given enough time of course.

The CPU running on your device boils down to a netlist describing a bunch of gates and their interconnections. This is somewhat of an oversimplification, of course.

[Bromskloss]

What does "over the torus" mean here?

[cypherpunks01]

I 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

Someone with more background could probably expand on that.

[Bromskloss]

Would it be correct to say that general homomorphic computing is now (and perhaps already before this) possible, though slow?

[anfractuosity]

Sounds 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

[enigma83]

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

[saganus]

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

[swordswinger12]

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

[michwill]

I would apply it instead of garbled circuits here https://eprint.iacr.org/2016/591.

Although slower, it feels like TFHE would provide better security against an active adversary. So, at least, simple server-side encrypted queries would well be possible

[gravypod]

We could implement an idealized RISC processor in gates and "flash" it with a program..... That would be fun.

[proofofstake]

https://www.youtube.com/watch?v=xsaXMUelOEA "CryptDB: Processing Queries on an Encrypted Database - Microsoft Research"

[michwill]

That'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]

The 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

[proofofstake]

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

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

[fenollp]

This 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]

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

[sandGorgon]

Will this be useful for machine learning in the same way as this ?

https://medium.com/numerai/encrypted-data-for-efficient-mark...

[maffydub]

Open Mined (http://openmined.org/) are looking at this from the other angle - sharing the encrypted neural network with their users so that they can train it without sharing their data at all - the encrypted gradients are computed by the user and collated and decrypted by the company that wants to train the neural network.

(Not affiliated in any way, but went to a really interesting talk on this a few weeks ago as part of the London Machine Learning meetup group - https://www.meetup.com/London-Machine-Learning-Meetup/events...)

[proofofstake]

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

[amenghra]

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

[EGreg]

Is this available now? Can we do fast homomorphic encryption baby??

[striking]

"Each binary gate takes about 20 milliseconds single-core time to evaluate"

So yes, for varying definitions of "fast".

[mSparks43]

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

[gigatexal]

so who's going to write the Python wrapper to this?

[jondubois]

I feel like there are so many use cases for this library.