2 ms·
> Complex conditional logic for example is a non-starter because every branch has to be evaluated Is overcoming this limitation of FHE anywhere on the horizon?
by skissane 6y ago
> Complex conditional logic for example is a non-starter because every branch has to be evaluated
Is overcoming this limitation of FHE anywhere on the horizon?
- dodobirdlord 6y agoNo, it's pretty fundamental. If the executor were able to know which side of the branch to execute it would mean the executor knows the value of the conditional.
- skissane 6y agoSo [1] claims "A variant of fully homomorphic encryption scheme for Turing machines, where one can evaluate a Turing machine M on an encrypted input x in time that is dependent on the running time of M on input x as opposed to the worst-case runtime of M". I admit understanding this paper is a bit beyond me. But, does their construction evaluate Turing machine conditionals by evaluating both branches? If it did, how could the running time be "dependent on the running time of M on input x as opposed to the worst-case runtime of M"? It seems to me that having to evaluate every branch irrespective of the input would result in the running-time always being M's worst case, not varying runtime depending on the input. [1] https://eprint.iacr.org/2013/229.pdf https://eprint.iacr.org/2013/229.pdf
- dodobirdlord 6y agoI think this is a different approach to FHE that concedes to timing based side channels to get this speedup.
- dlubarov 6y agoI don't think there's much that can be done, except trying to identify any circuitry shared among branches and moving it out. Like if we have "if (cond) { hash(x) } else { hash(y) }", we can move the hash circuit outside of the conditional. There are some circuit compilers that try to do optimizations like that automatically, like xJsnark, though it's not meant for FHE.