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.