[hcrypt]

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

[geekbeast]

Curious about a detail here. If this machine can evaluate AND and XOR, then how do you prevent a malicious attacker with the public key from performing encrypted each power of two, performing an AND and comparing with zero?

  {x&0x2} = {0x2}

Does this imply that hcrypt VM is not necessarily equal to a Turing machine? The program counter seems like it could definitely cover finite automata, but it doesn't seem expressive enough to simulate a stack. If PC is always encrypted then it ends up having to encode both current state and the information necessary to evaluate the branch implicitly as a state change, which again seems more like finite automata.

If you guys figured out how to securely implement control ( halting, loops, etc ), without functional encryption, that would be a huge breakthrough in FHE.

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

[geekbeast]

Just went and read your paper.

  VII. OPEN ISSUES AND FUTURE WORK
  ...
  One of the main issues of our concept is the termination problem. To solve this problem, a crypto-system that can selectively decrypt information is required.

Doing the above will make it very difficult to prove the security of malleable cryptosystem, something that Boneh, Sahai, and Waters have written multiple papers on. The approach of finding a minimum number of cycles to complete the computation seems much more effective, if restrictive in the number of operations that can be evaluated.

I'll e-mail you guys offline.

[hcrypt]

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.

[sillysaurus3]

Wow, this is fantastic! Thank you so much for your reply. I'm going to sleep soon, so I'll need some time to study this, but I just wanted to say how much I appreciate your comment. And welcome to HN, by the way!

Do you happen to have an email address I could reach you at with further questions? (If you don't want to post it publicly, please feel free to email me if you'd like: [e-mail])