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

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

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.

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

I think this is a different approach to FHE that concedes to timing based side channels to get this speedup.

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.

Re your last question, I don't think so. It's just an attractive application, hidding neural network weights is valuable in some settings, for instance.

Its less about structure and more about use cases. In my opinion there are only two major uses of data collection by organizations - Machine learning training data and targeted advertisements. A federated fully homomorphic system will allow these companies to train their models without invading personal privacy.

It will also allow organizations to train models collaboratively in a privacy preserving way, which if you think about it has lot of consequences.

set intersection is a big one.

If you want to share data on common customers, without revealing who your unique customers are, you need set intersection.