Comment by remcob | Hacker News Reader

Comment by remcob | Hacker News Reader

Parent Full thread

Imagine a FHE circuit that executes a single webassembly instruction. This is a finite circuit that takes as input the program, machine state and external input (all encrypted). As output it returns the (encrypted) new machine state and a single unencrypted bit indicating if the program terminated or not.

Now you can run the FHE step for as many times as the algorithm requires, giving you a FHE-VM that can execute any WebAssembly program from your favorite Turing complete programming language.

The limitations are that you need to define a bounded machine state, which technically breaks the Turing completeness. In practice this is no different from your laptop having a finite amount of memory which disqualifies it as a Turing machine. Real Turing machines don't exist.

The other limitation is that the FHE executor can now see the total run time of the algorithm, which was secret before. This is similar to a timing side channel and similar mitigations apply.

As others have pointed out, if you have a concrete algorithm you can do something much simpler than implement a VM. The Collatz sequence is good toy example of an algorithm with unknown loop bounds. You would make a FHE circuit that iterates a single step using the same overall design.

Totally agree. Just let me point out that this is not, theoretically speaking, an FHE computation. It is an "FHE plus a termination oracle" computation. Maybe no big difference in practice, but totally a different thing in theory, which was the point of my comment.

This is basically all that modern computers are; a giant circuit and a clock to keep sending a "do the next thing" signal.

Is it a stretch to say that "1: perform this list of multiplications and additions. 2: GOTO 1" cannot be called a FHE system?

But modern computers let you send them instructions entirely in a Turing-complete language, with no requirement that you first know how to unroll them into a static circuit (constant-bounding every loop). That seems like a bigger difference than "oh sometimes you get out-of-memory errors".

As far as I can tell it is possible to homomorphically compute a UTM. Since it's possible for a homomorphic circuit to decrypt and reencrypt its own ciphertexts as part of the bootstrapping principle it should also be possible for a circuit to fully decrypt certain values (outputs). Basically, if V = E_K(V') is the homomorphic ciphertext of V' under the primary key, K, and O is an output key, the primary circuit can compute V* = E_O(D_K(V)). An output circuit D_O(X) decrypts values encrypted with the output key, e.g. V' = D_O(V*).

A UTM is an unbounded tape T of encrypted bits, an encrypted state S, a circuit U(S, B) = (S', B', V') representing the state machine of the TM with V' as an output to control the next step, and the circuit for D_O(X). After each evaluation of U the state S is replaced by S', the bit at the current position on the tape is replaced with B', and if V = D_O(V') is 0, move the position on the tape left, if it's 1 move right, and if it's 2 then halt.

A bounded-length Turing Machine can be represented as a finite state machine (with the computing power of a standard physical computer) without leaking any information about changes to the tape by (T', S', V') = FSM(T, S) where the entire tape T is replaced by the output of the circuit at each step and D_O(V') is 1 for continue or 0 for halt.

This depends on your exact definition of an FHE computation. You could imagine a definition under which you can consider the whole scheme a single Turing complete FHE. But this definition would have to accept that the FHE computation is unbounded and leaks computation length (as would any Turing complete scheme).

I don't like the name "termination oracle", it sound too much like "halting oracle" which is not what is going on here. All we do is add an outer while-loop, a simple algorithmic transformation. I wouldn't even consider that an oracle.

Reply on news.ycombinator.com