5 ms·
in FHE you need to execute all branches, but the result could be just like you executed the right one. Consider the following conventional code: if (flag) {
by krasin 6y ago
in FHE you need to execute all branches, but the result could be just like you executed the right one.
Consider the following conventional code:
if (flag) {
a = b + c
} else {
a = b * c
}
In FHE it could look:
a = flag * (b+c) + (1-flag) * b * c
That way, you can express almost arbitrary programs. I don't make a claim that a Turing machine could be, though.
- rocqua 6y agoThe big question isn't branching, it's unbounded loops. It seems to me the only option is unrolling those loops. But that has a massive performance penalty. Because you need to always run through however deep you unrolled.
- giomasce 6y agoYou can't unroll an unbounded loop, you don't know how many times to unroll. To have Turing machine you need to need to know from your program state if you reached the end of your loop or not (i.e., you need to evaluate the "while" condition), and by definition FHE shouldn't allow you to extract information from your program state.
- IshKebab 6y agoYou can unroll a sufficient number of times. There would be an upper limit on iterations and it would presumably be horrible inefficient, but I can't see why it wouldn't work.
- layer8 6y agoIf you know how many iterations are sufficient, the unbounded loop could have been written as a bounded loop in the first place. For truly unbounded loops, you’re still stuck.
- IshKebab 6y agoI mean, that's the same as saying no computer is Turing complete because it doesn't have infinite memory. I'm not saying it is a practical solution to unroll a loop that might run a billion times.
- giomasce 6y agoI am not saying there are not practical ways to do useful computation with this stuff. I am commenting on the theoretical remark that any algorithm (as in any Turing machine) can be executed with FHE, which is false, as it can be proved that it is impossible to compute, given an abstract Turing machine, an upper bound on the length of its execution.
- extropy 6y agoThis is generally solved by unrolling the program into a single loop. Essentially having a function state(N) => state(N+1), shouldContinue. This exposes the number of iterations needed to finish the computation. That could further be limited by underlying code rounding the iterations to mask the real count. TLDR: either the run time is fixed or you leak some info via the run time.
- tgv 6y agoI believe that's not the issue: the remote machine which performs the calculations on the encrypted data is TM complete and can perform unbounded loops. Comparison is the puzzler for me too: e.g., how do you take min(a, b) if you don't know how a and b compare? We know that F(a) + F(b) = F(a + b), so the remote machine can use "normal" addition operations, but still a > b and F(a) < F(b) can both be true, so it can't use "normal" comparisons, unless there's some implication of the properties of FHE I didn't see.
- dlubarov 6y agoIn theory we could compute the full table of values of a function like less(x: F, y: F) -> {0, 1}, interpolate a bivariate polynomial containing all those values, and build a circuit to evaluate that polynomial. Its degree would be around 2|F| though, so it would be completely impractical. In SNARK programming, we would usually decompose field elements into bits, then apply a binary comparison circuit. Binary decomposition can be done non-determinstically, by having the prover give the purported bits as "advice" inputs, then having the circuit accumulate those bits and check the sum. I haven't done any FHE circuit programming, but I imagine that approach wouldn't work, since the circuit must be deterministic. I imagine any values that might need to be compared would just be encoded as binary from the start. (Or is there a better approach?)
- tgv 6y agoInteresting idea, but then it's not TM complete, since the problem space is by definition finite, isn't it? So it seems to me the importance of comparison for TM-completeness is still unsolved. Then again, it just occurred to me that perhaps fully homomorphic implies that F(0) = 0 and F(1) = 1, so a > b could become F(a - b) ρ 0, and you only need to determine beforehand if ρ is > or <.
- DSingularity 6y agoCouldn’t the results indicate the need to re-run a circuit? While f(x) x=g(x) would simply return f(x)||g(x).
- SilasX 6y agoOkay but that example is just one conditional branching. Turing-completeness requires that you be able to e.g. keep looping back until some condition is met. If you want to build arbitrary functions like you've described, it reduces to the question of whether you can "unroll" the function, given its inputs[1], into a (stateless) circuit. But that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts), not the general recursive functions you need for Turing-completeness. Anyone know how you pull off general recursive functions from just addition and multiplication? [1] and in FHE you don't know the inputs either, which is another kink.
- ogogmad 6y ago> that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts) The primitive recursive functions cannot be expressed using circuits. Circuits by definition can only express polynomials, which have a much smaller growth rate than what primitive recursive functions are capable of. [edit] Actually, probably a better reason is that in primitive recursion, the running time can depend on the input. For a circuit, the running time is independent of the input.
- extropy 6y agoThe circuit that repeatedly multiplies the previous result with itself has higher than exponential growth rate.
- ogogmad 6y agoNo, because you can only multiply a fixed number of times.
- lalaland1125 6y agoGood luck finding something that grows faster than https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function