Re:TFHE: Fast Fully Homomorphic Encryption over the Torus
by rjeli on Monday April 13, 2020 @12:28PM
(#22857243)
From some napkin math and googling, a 6502 has 4.5k transistors, which at 13 ms per gate is about a minute per cycle, divided by how many gates there really are per transistor.
How does your implementation compare?
Re:TFHE: Fast Fully Homomorphic Encryption over the Torus
by mmastrac on Monday April 13, 2020 @12:36PM
(#22857324)
~20k gates total (ShapeCPU was ~30k gates), but the _real_ bottleneck for FHE computing is the longest path from input to output as FHE computers are highly parallel.
I am sure I had a stat for the longest path from input to output, but I'm a few years swapped out on this project.
Note that adding pipelining to a CPU drastically reduces the longest path. ShapeCPU is not pipelined at all which probably means there's a bunch of low-hanging fruit.
I built one off the same infrastructure called hideCPU. If you can create AND/XOR/NAND/etc gates _and_ feed-back output into your input, you can create a CPU.
https://github.com/mmastrac/oblivious-cpu
My goal was more to build some open prior art in the space rather than actually build a viable FHE CPU, but there's no reason why you couldn't implement one of these on top of the FHE system.
To answer some statements about FHE computing that come up over and over:
- Yes, you can loop + perform control flow in a FHE-based computer
- Yes, you can recurse in a FHE-based computer as long as you have enough emulated RAM/stack
- Yes, you can store state in a FHE computer
- No, you cannot determine if a FHE computer has reached a certain state (or halted) from the outside without decrypting the system (or at least a state bit)
- Yes, you can emulate RAM in a FHE computer
- Yes, you can emulate a HDD (well, rotating storage) in a certain FHE computer constructions