3 ms·
This does not make sense to me, I must be missing something important. If your input is an encrypted state of a Turing machine, then isn't FHE able to simulate
by krastanov 5y ago
This does not make sense to me, I must be missing something important. If your input is an encrypted state of a Turing machine, then isn't FHE able to simulate the evolution of that Turing machine (hence keeping state and secrets without divulging them)? After all, there is no real difference between data and program.
- sterlind 5y agooh yes. brainfreeze [0] is an example of an FHE Brainfuck machine. the problem is that your users can't decrypt any outputs at all from them. there's also a major possibility of confused deputy attacks if you blindly decrypt outputs returned to you by your users, since the users can "circuit-bend" your FHE program to a degree. for instance, nothing's stopping me from sending the output from brainfreeze back to you early - I can't even tell when it's halted! 0. https://github.com/joeltg/brainfreeze https://github.com/joeltg/brainfreeze edit: actually, that's the fatal flaw with FHEs as Turing machines. you can't ever tell when they halt, because that would require decrypting a bit and exposing it to the end user. you just have to keep running them until you get bored, or abandon Turing machines for circuits.
- FeepingCreature 5y agoDoes the user telling you when to halt leak any information?
- sterlind 5y agoyou might be able to use the user as an oracle, but the real issue is that the user has to be around. querying the user after every clock cycle will get old, fast.
- krastanov 5y agoWhat about programming in the style used to avoid timing attacks. My understanding is that there are plenty of situations even today where for security purposes (side-channel timing attacks) you need your program to execute in a fixed number of steps independent of the input. Is this not enough to solve the problem?