I am sure they meant that the output of a conditional expression would be an encrypted boolean.

A conditional branch would become an encrypted conditional branch. That means, you wouldn't be able to infer the branch from the encrypted output.

Let's take a simple example. I have an algorithm X which takes two integers and returns an integer.

Let's say I want to run this algorithm on a third-party VPS. I obfuscate the algorithm X, in order to hide the operations that X does. Let's called the obfuscated version OX.

I host the OX algorithm on the third-party server, and start supplying it pairs of integers. The third-party is observing the set of inputs and outputs:

  (4, 4) => 8
  (3, 2) => 5
  (1, 0) => 1

From these observations, the third-party would be able to infer what OX does. (simple addition in this case).

Now, however, if I use HE, I will get an algorithm (HX) which takes encrypted input and spits out encrypted output. A third-party will see the corresponding log of inputs and outputs like this:

  h3830120cjfakj, 102309123clals => 293sdlzlxdf
  94ka3lkc.zdkf, 102kksdllz => 1923939nddd

From these observations, it is impossible to know what HX does (as per the theory).

Yes, that's the big caveat that needs to be added when someone tells you that XOR and AND are enough to implement arbitrary functions. What that means is, for an arbitrary function you can write a program that takes that function plus the input size, and generates the (XOR/AND-only) boolean circuit that implements the function for that input size.

Note that the output size is fixed too. So yeah, any program you actually try implement this way is going to involve a very roundabout (er, circuitous) process. If-branching? Hah! That just means you get to designate half the remaining portion of the circuit to one branch and the other half to the other branch. While loops? You get to unroll each step into another set of gates.

Here's my post from when I first discovered the FHE paper: http://blog.tyrannyofthemouse.com/2013/05/i-added-your-numbe...