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