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