3 ms·
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. Compari
by tgv 6y ago
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.
- 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 <.