hcrypt

The attacker can do whatever she wants. You can't prevent her from doing anything. But maybe you can elaborate on what you mean with "each power of two". When trying to compare with zero (what zero?), keep in mind we're talking about a probabilistic cryptosystem. The machine is just an application of the underlying scheme, so it's not the machine that provides the atomic functions.

To be precise, the state of the machine includes the flags, the PC and memory. It's easy to implement a simple stack pattern in circuits but you don't need it in order to implement arbitrary functions.

We already published the solution for encrypted memory access and encrypted program flow control (without unfolding) but halting is an issue you (at least to my knowledge) cannot solve under the assumptions we made.

The termination problem is the major issue. You cannot generate a selectively decryptable signal from inside the encrypted code. In other words, being able to generate a halt signal to mark the end of the program flow immediately invalidates the security of the entire container.

>FHE extends HE so that you can perform arbitrary computation

FHE doesn't extend HE in the sense that it adds operation types other than addition and multiplication but it allows unlimited chaining of the two operations. This in turn enables arbitrary operations because you can express any function (i. e. any chain of atomic operations) by means of additions mod 2 and multiplications mod 2 (which is equivalent to XOR and AND) when you turn it into a boolean circuit representation. The contribution of FHE is a way to a) clean operands from noise or to b) do not add noise to the operands in the first place because noise is the limiting factor for circuit depth in HE, where "depth" means the number of possible subsequent multiplications.

>Now, when the program executes, it's obviously possible to monitor it and watch what's being done.

That's the trick. It isn't. Let's loosely stick to your example.

  if (var == op)
  { 
    do this
  }
  else
  { 
    do that
  }

This, when compiled for the hcrypt VM, turns into something like

  0 La var //look at var
  1 CMPa op //var==op?
  2 BEQ 5 //yes
  3 <do that>
  4 JMP 6
  5 <do this>
  6 <continue>

The obvious question is: How do you hide what branch is taken? The hcrypt VM (as all processors and TMs) is a state machine. The states essentially are the status flags (zero result, addition overflow, minus result,...) and the program counter PC. In line (address) 1, the machine decides, whether op is equal to var and sets the zero-flag to 1 if this is the case. The comparison is an implicit subtraction, so if the two values are equal, then the result is 0 and the zero flag switches to 1. In the next machine cycle (PC is 3) we want to branch. The branch operation is just a simple assignment (PC=address). The assigned value can be expressed bitwise

  PC = ((branch AND zero-flag) XOR (PC+1 AND !zero-flag))

Case 1: var==op

  PC = ((5 AND 1) XOR (3 AND 0))

Case 2: var!=op

  PC = ((5 AND 0) XOR (3 AND 1))

Thinking in wires, this is the implementation of a demultiplexer or selector. This is the essential curcuit for the hcrypt VM and oblivious to an observer. The most basic application is the command selector. Assume, we have the opcode in a register OP and the operands in OP1 and OP2. The ALU then operates like

  res_add = OP1 + OP2
  res_sub = OP1 - OP2
  res_mul = OP1 * OP2
  res_div = OP1 / OP2
  result = ((res_add AND OP==ADD) XOR (res_sub AND OP==SUB) XOR (res_mul AND OP==MUL) XOR (res_div AND OP==DIV))

Since all the operands and registers (this incudes the machine opcodes) are encrypted, the observer does know, she's looking at a branch selector or an encrypted ALU but she cannot decide what branch is taken or what operation is executed.