TFHE: Fast Fully-Homomorphic Encryption Over the Torus

https://tfhe.github.io/tfhe/

by _d4bj • 9 years ago

196 94 9 years ago

tfhe.github.io

otoburb• 9 years ago

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

EGreg• 9 years ago

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

mSparks437• 9 years ago

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.

striking3• 9 years ago

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

striking3• 9 years ago

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

So yes, for varying definitions of "fast".

SilasX• 9 years ago

If 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#Timeli...

Of course, an op on a single bit is still far short of a CPU instruction, AIUI.

You gotta start somewhere though!

jondubois• 9 years ago

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

tome• 9 years ago

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?

mmastrac• 9 years 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).

Cyph0n• 9 years ago

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.

skybrian• 9 years ago

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.

lisper3• 9 years ago

You can compute a loop by essentially building a CPU out of gates. But you're right that this would be impractically slow even with this latest improvement in performance.

modalduality• 9 years ago

In general it's much easier to reason about Boolean circuits because they always have an answer, unlike arbitrary programs that may never halt, for example, so you see a lot of theoretic results focusing on Boolean circuits (sometimes with limitations on the depth) instead.

Early on it was thought that considering circuits instead of regular programs could result in "polynomial with advice" algorithms for NP-complete problems, but results such as the Karp-Lipton theorem have shown this to be unlikely.

enigma834• 9 years ago

The current version of the library achieves 13ms per binary operation on a core-i7 instead of 50ms in the original paper.

The improvements are described in the new paper: https://eprint.iacr.org/2017/430. Hopefully, the packing techniques will be also present in the next version of TFHE.

tveita• 9 years 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://tfhe.github.io/tfhe/tuto-cloud.html

lisper3• 9 years ago

It'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• 9 years ago

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

dllthomas5• 9 years ago

Why would we expect to need a full modern CPU? An 8080 had thousands, and that's still general purpose. Something built for a specific task might well be substantially smaller. Still slow, but possibly realistic for some tasks.

saganus• 9 years ago

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?

gravypod• 9 years ago

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

roywiggins• 9 years ago

At 20ms per AND, that's 50 Hz. That's... slower than useful, surely?

swordswinger123• 9 years ago

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.

proofofstake6• 9 years ago

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

swordswinger123• 9 years ago

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

michwill4• 9 years ago

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

swordswinger123• 9 years ago

Can you explain how you would use FHE instead of garbled circuits in the Arx range query data structure? I don't see how that would work - wouldn't you have to (re-)introduce interaction to let the server learn intermediate results?

sandGorgon4• 9 years ago

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

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

amenghra• 9 years ago

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

tgtweak2• 9 years ago

There are applications for it, despite the speed penalty.

proofofstake6• 9 years ago

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.

lkowalcz5• 9 years ago

Worth pointing out that Numerai actually doesn't use encryption in any standard sense (including structure-preserving encryption), but instead seems to be using some heuristic method of obfuscating their data.

Their (closed-source) method of obfuscating their data apparently does have the property that it preserves the structure of the data, but calling it "structure-preserving encryption" is misleading imo since it risks confusing it with standard notions of encryption and structure-preserving encryption which have much stronger security guarantees.

(Their marketing seems to encourage this conflation by, for example, citing academic advances in standard notions of homomorphic encryption and SPE and implying that these advances have enabled Numerai's technology)

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

maffydub• 9 years ago

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

sandGorgon4• 9 years ago

oh - its very similar to numerai. Pretty cool. I think this is their library - https://github.com/OpenMined/R-Homomorphic-Encryption-Packag... (they havent ported this to python, so are having to use R-bridge to use it in jupyter. I wonder why).

michwill4• 9 years ago

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• 9 years ago

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

michwill4• 9 years ago

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

mSparks437• 9 years ago

because, obviously, summing all the values is something you couldnt do yourself?

proofofstake6• 9 years 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/...

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.

michwill4• 9 years ago

Oh wow! I didn't ask for the last one, but this is insanely interesting also!

phkahler• 9 years ago

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.

branja• 9 years ago

all the fun problems in CS are intractible

_d4bj• 9 years ago

I think the OP is referring to simulating an oblivious Turing machine on the encrypted data, which itself is a Turing machine and some data.

I don't think this is known to be intractable, just really slow (for now).

erikpukinskis• 9 years 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.

Bromskloss3• 9 years 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?

anfractuosity2• 9 years ago

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

enigma834• 9 years ago

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.

anfractuosity2• 9 years ago

Interesting! Thanks for the reply.

fenollp• 9 years ago

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• 9 years ago

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.

Bromskloss3• 9 years ago

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

Bromskloss3• 9 years ago

What does "over the torus" mean here?

cypherpunks01• 9 years ago

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.

gigatexal• 9 years ago

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

TFHE: Fast Fully-Homomorphic Encryption Over the Torus

Related Stories