Hacker News Reader

Comment by krasin | Hacker News Reader

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.

View on HN

Okay 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.

> 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.

The circuit that repeatedly multiplies the previous result with itself has higher than exponential growth rate.

No, because you can only multiply a fixed number of times.

Good luck finding something that grows faster than https://en.wikipedia.org/wiki/Ackermann_function

Easy, just square it. Also, the Ackermann function is not a primitive recursive function.

FHE is just a math equation. Can you accept the requirement that you process the state more than once? If so you could do something like encode the atomic state of a silicon circuit somehow and step it forward in time.

That is probably what the researcher is referring to. You can encapsulate computation, but not in a single math equation.

The 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.

You 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.

You 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.

If 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.

I 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.

I 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.

This 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.

I 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.

In 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?)

Interesting 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 <.

Couldn’t the results indicate the need to re-run a circuit? While f(x) x=g(x) would simply return f(x)||g(x).

Reply on news.ycombinator.com