4 ms·

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 n

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.

benlivengood 6y ago
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?
- SilasX 6y ago
  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".
  - benlivengood 6y ago
    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.
remcob 6y ago
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.

benlivengood 6y ago

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?

SilasX 6y ago
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".
- benlivengood 6y ago
  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.

remcob 6y ago

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.