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

[modalduality]

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.

[enigma83]

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.

[lisper]

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.

[dllthomas]

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

[lisper]

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

[dllthomas]

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.