3 ms·
Alan Turing proved that a solution to the halting problem cannot exist. Per Wikipedia:[0] > A key part of the proof was a mathematical definition of a computer
by zenexer 6y ago
Alan Turing proved that a solution to the halting problem cannot exist. Per Wikipedia:[0]
> A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines.
It cannot be possible to “map” a Turing machine with a finite number of operations. Without true decision trees and loops, FHE isn’t Turing complete. At minimum, there needs to be a concept of a conditional jump—if X, jump to instruction Y.
You can unravel some programs into a finite set of instructions, but that doesn’t make FHE Turing complete.
Take the following code, for example:
function f(x):
while x == 1:
do nothing
return x
For a machine to be Turing complete, it must be able to run that function. FHE can’t do that, by definition; it would reveal information about the input.
[0]: https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- heavenlyblue 6y agoYou can simulate that program you gave on a finite circuit because you can simulate it on your computer which is a finite circuit.
- zenexer 6y agoYour computer has circuitry that is capable of being reused. It isn’t a simulator; it could, in theory, run that loop ad infinitum. FHE can’t reuse circuitry. There’s no concept of, “based on the output, we now need to plug it back in and repeat.” Instead, it has to literally repeat that circuitry for every possible loop.
- heavenlyblue 6y agoYou could re-run FHE until some condition fails. This is what your CPU does BTW. Again - the only reason you shouldn’t do that in homomorphic encryption is because this way you will leak run duration information.
- zenexer 6y agoYou can’t do that—that reveals timing information.
- josh2600 6y agoWould you say that this circuit was fully homomorphic if, for all inputs, the processor appeared to be doing the same work? That is to say? If X = 1 or X = 2 the processor did not appear to “do nothing” but, instead, performed an operation on an encrypted string that was constant time?
- zenexer 6y agoI’m not really sure what you’re asking. By definition, FHE cannot be Turing complete. A Turing machine must be capable of performing operations that cannot be handled in constant time, and for which the timing reveals information about the input. That is a fundamental feature of Turing machines; it’s the whole basis for how they came about.
- avmich 6y agoWhy can't FHE be capable of performing unbounded operations?
- josh2600 6y agoThere’s no way to do a FHE style system with branching unless all branches are indistinguishable from one another. All branches must execute in the same amount of time, otherwise statistical analysis will leak information. Forget Turing completeness for a second, that’s not actually what you want for a FHE style system. You want computational indistinguishability which can’t be achieved without side-channel resistance.
- R0b0t1 6y agoSome of the original work around FHE implies the researchers were applying ML models. If you had a complicated enough ML model (e.g. of a person) you could simulate a computer in that model. The assertion that FHE with just multiplication and addition is Turing-complete is true, and this is one proof. If you can think of something besides encoding a Turning machine's state as NN weights I am very interested. Perhaps encoding a quantum circuit somehow? A technically correct but intractable solution would be simulating the quantum state of every atom in a silicon circuit.