4 ms·

> In other words, is there something about the structure of machine learning tasks which makes them more suited for FHE than other computing tasks? Yes, FHE is

> In other words, is there something about the structure of machine learning tasks which makes them more suited for FHE than other computing tasks? Yes, FHE is not (currently) good at general-purpose computing. Complex conditional logic for example is a non-starter because every branch has to be evaluated. But tensor multiplication is well supported with existing FHE schemes, and many kinds of machine learning tasks consist of non-conditional tensor multiplications.

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 ago
  No, 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 ago
    So [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 ago
      I think this is a different approach to FHE that concedes to timing based side channels to get this speedup.
- dlubarov 6y ago
  I 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.

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 ago
No, 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 ago
  So [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 ago
    I think this is a different approach to FHE that concedes to timing based side channels to get this speedup.
dlubarov 6y ago
I 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.