3 ms·
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
by skybrian 9y 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.
- lisper 9y agoYou 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 9y agoIt'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...
- modalduality 9y agoIn 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 9y agoThe 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 https://eprint.iacr.org/2017/430. Hopefully, the packing techniques will be also present in the next version of TFHE.