Arbitrary programs that terminate on every input (no infinite loops), and with a few important caveats:
1. Random access (reading input-dependent memory address) must be simulated with linear scans of the array.
2. Input-dependent branches must be transformed as follows: both branches are evaluated, and the side effects must be combined using the branch condition (e.g. x <- xc + new_x(1-c)).
3. Loops with input-dependent bounds must be unrolled to their maximum number of iterations (this is not always easy to compute).
In general you would probably write your programs in a special-purpose language that is easy to compile for this model of computation. Efficiency can suffer for some algorithms -- sorting winds up being O(n lg^2 n) instead of O(n lg n), for example.
Also the best FHE schemes are still nowhere near practical for the majority of computations people care about.
I didn't realize HE was still so primitive. Whenever there is a privacy kerfulffle for thing X, HN commenters say "X should be implemented with homomorphic encryption instead!"
1. Random access (reading input-dependent memory address) must be simulated with linear scans of the array.
2. Input-dependent branches must be transformed as follows: both branches are evaluated, and the side effects must be combined using the branch condition (e.g. x <- xc + new_x(1-c)).
3. Loops with input-dependent bounds must be unrolled to their maximum number of iterations (this is not always easy to compute).
In general you would probably write your programs in a special-purpose language that is easy to compile for this model of computation. Efficiency can suffer for some algorithms -- sorting winds up being O(n lg^2 n) instead of O(n lg n), for example.
Also the best FHE schemes are still nowhere near practical for the majority of computations people care about.