Hmm, given that "mov is Turing-complete" [0], is it possible to get around the requirement that loops must be fully unrolled? Obviously you couldn't tell if your algorithm was finished, but if you could ask the key holder if the algorithm had completed or needed more work, you could theoretically compute any algorithm. What am I missing?
[append] Perhaps, could you create a "fully homomorphically encrypted" 6502, where each application of the program corresponded with a single clock of the emulated microprocessor?
The "mov is turing complete" thing is mostly about x86 mov having a lot of functionality. It can do arithmetic. The mov mnemonic basically encapsulates a bunch of functions (and opcodes), kind of like how git checkout can do at least ~3 distinct operations depending on arguments.
That said, to have unbounded loops, they either need:
- A branch at the end.
OR
- The use of pagefaults.
So even then, it's not quite just the mov instruction alone.
Combinatorial circuits aren't turing complete. The novelty of mov being turing complete is that they were able to do conditional branching with just loads and stores. In the FHE case, they can't read and write to parts of memory, so it's a no-go.
This is why their compiler essentially only works on pure functions whose inputs have a statically known size.
[append] Perhaps, could you create a "fully homomorphically encrypted" 6502, where each application of the program corresponded with a single clock of the emulated microprocessor?
[0] https://drwho.virtadpt.net/files/mov.pdf