Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

TFHE: Fast Fully-Homomorphic Encryption Over the Torus

tfhe.github.io

Post reply on HN
Print view View original

81–90 of 98 posts

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#81

Post by dllthomas »

Bromskloss wrote: post #62
erikpukinskis wrote: post #56

Earlier quoted context omitted.

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

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

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

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#82

Post by dllthomas »

lisper wrote: post #20
skybrian wrote: post #14

Earlier quoted context omitted.

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.

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.

It's not clear to me that this is still "impractically slow" for all purposes. An 8080 is a few thousand gates. What can you do on an 8080 in 100 cycles? You can now do that in about an hour on secret data by naively simulating the chip. That actually sounds like it might make some things practical that weren't before...

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#83

Post by lisper »

dllthomas wrote: post #82
lisper wrote: post #20

Earlier quoted context omitted.

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.

It's not clear to me that this is still "impractically slow" for all purposes. An 8080 is a few thousand gates. What can you do on an 8080 in 100 cycles? You can now do that in about an hour on secret data by naively simulating the chip. That actually sounds like it might make some things practical that weren't before...

It might. But I can't think of any.

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#84

Post by yorwba »

mSparks43 wrote: post #70
yorwba wrote: post #41

Earlier quoted context omitted.

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

for example?

For example when two parties are interested in making a deal, but don't want to reveal it unless the other party is interested as well. (The example is usually a date, but it could be applicable to voting or other situations where both privacy and unanimity are desired.)

By performing a homomorphically encrypted computation, they can set it up to only reveal the final decision, but not the individual inputs that determined it, so nobody loses face.

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#85

Post by proofofstake »

swordswinger12 wrote: post #77
proofofstake wrote: post #27

Earlier quoted context omitted.

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

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.

Maybe you are right. Couldn't quite gather it from your post.

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#86

Post by cypherpunks01 »

Bromskloss wrote: post #64

What does "over the torus" mean here?

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.

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#87

Post by sandGorgon »

lkowalcz wrote: post #50
proofofstake wrote: post #49

Earlier quoted context omitted.

Do you think neural encryption is closer to encryption? GAN-style: One network encrypts while preserving structure, another network tries to reverse engineer to the original features. Edit: No specific sources for what Numerai is using, but in general: https://arxiv.org/abs/1610.06918 "Learning to Protect Communications with Adversarial Neural Cryptography". Edit2: Yes, in general. I would say "yes, this is a valid f…

I've never heard of neural encryption before, do you have a good source for me? From the Wikipedia page for "Neural cryptography", it seems like there's some success in using NN's for cryptanalysis, but not for constructions... Edit: Do you mean the Google GAN experiment? ( https://arxiv.org/pdf/1610.06918v1.pdf ) Ahh ok, well at least for this there looks like an attempt at defining a security model (security agains…

That particular paper got a LOT of flames when it was posted to /r/MachineLearning

https://www.reddit.com/r/MachineLearning/comments/59v9ua/r_1...

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#88

Post by dllthomas »

lisper wrote: post #83
dllthomas wrote: post #82

Earlier quoted context omitted.

It's not clear to me that this is still "impractically slow" for all purposes. An 8080 is a few thousand gates. What can you do on an 8080 in 100 cycles? You can now do that in about an hour on secret data by naively simulating the chip. That actually sounds like it might make some things practical that weren't before...

It might. But I can't think of any.

Nor I, TBH, but I've not been thinking about it very hard or very long. It just surprised me that we're no longer talking about months or years, where things are more obviously impractical for just about everything.

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#89

Post by phaedrus »

Bromskloss wrote: post #62
erikpukinskis wrote: post #56

Earlier quoted context omitted.

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

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

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

Re: TFHE: Fast Fully-Homomorphic Encryption Over the Torus

#90

Post by kevin_thibedeau »

ris wrote: post #69
simcop2387 wrote: post #23

Earlier quoted context omitted.

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.

Well, no, other way around more likely - the most practical way of building programs for these systems would probably be through VHDL/Verilog with a specialized toolchain. (edit: although actually FPGAs could be useful simply because they can be very good at running FFTs (as are GPUs), not because of the gate-programmable nature of them)

HDLs have no special advantage in evaluating boolean operations in simulation. Most simulators are significantly slower than native code unless they use compiler infrastructure used by mainstream languages and even then they still have the penalty of maintaining the simulation environment which serves no purpose in this application.
Post reply on HN