Comment by sillysaurus3 | Hacker News Reader

Comment by sillysaurus3 | Hacker News Reader

Parent Full thread

Agreed, it's fun to speculate! I love this stuff.

So my understanding of FHE is that it can take an arbitrary circuit (any arbitrary program) and convert it into a circuit which operates on encrypted data.

That means it must be possible to write the equivalent of

  if (op == OP_ADD) { /* interpret addition bytecode */ }
  else if (op == OB_MUL) { /* interpret multiplication bytecode */ }
  ...

etc, where "op" is encrypted data. By extension, you can write an entire interpreter for encrypted bytecodes.

Now, when the program executes, it's obviously possible to monitor it and watch what's being done. However, until it executes, the bytecode remains secret. That means it should be possible to ship programs which are impossible to analyze until they're actually executed.

It's a common malware technique to write a program which contains an encrypted subprogram, which is only decryptable on a certain target machine. (For example, you could use a specific computer's MAC address as an ecryption key, which means no reverse engineer can analyze it except on that specific machine.)

FHE, on the other hand, provides the opportunity to ship a turing-complete interpreter to everyone, which executes encrypted bytecodes which can't be analyzed until execution time. That means a FHE program could be a timebomb set to wipe your harddrive at some specific date and you wouldn't know it, since the best you could determine beforehand is "this interpreter sometimes tries to execute shell commands" without actually seeing which commands it's capable of executing in practice until it's too late.

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

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.

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.

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.

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.

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: sillysaurus3@gmail.com)

    if (op == OP_ADD) { /* interpret addition bytecode */ }
    where "op" is encrypted data.

Ah, but that's why it doesn't work. The trick would be to test if if op == OP_ADD when decrypted, which is precisely what you don't know. If you're merely testing that op == OP_ADD as an encrypted value (i.e. OP_ADD is actually the encrypted form of your add opcode), then the program is actually not encrypted, but merely has annoying-to-read semantics. To analogize: it's like encrypting a password on the client before sending it to the server, and then just straight string comparing them; it means your passwords aren't encrypted on the server, merely that your passwords are uglier than what the user entered.

The trick would be to test if if op == OP_ADD when decrypted

Hmm, this is a point of confusion for me then, because isn't that exactly what FHE allows you to do (and in fact its entire point)? HE allows you to add or multiply encrypted values, and FHE extends HE so that you can perform arbitrary computation. That must mean the == operator is supported, so it seems like it must be possible to do this.

Also, thank you for talking through this with me. It's much appreciated.

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

You're very welcome, this is totally fun, and hopefully we'll both come out wiser.

> That must mean the == operator is supported, so it seems like it must be possible to do this.

OK, I understand what you meant with the code now, but the problem is you won't know the answer to your equality comparison. In the same way that add(encryptedIntegerA, encryptedIntegerB) gives you encryptedIntegerC whose value is unknown but which you know decrypts to a + b, you know that equals(encryptedIntegerA, encryptedIntegerB) results in encryptedBooleanC, but you don't know whether that decrypts to true or false. So what do you execute next? It's not that it doesn't know until runtime which branch to take; it's that it doesn't know ever. The whole point FHE is that the executing machine doesn't know the answers themselves, just what they encrypt to. So I'm not sure--no matter how much meta eval you make it do--how it can decide what code to actually execute without decrypting something.

Edit: though I appear to be wrong about this. From Wikipedia:

If the morphisms of some wide supercategory of C include the primitive recursive functions or even all computable functions, then any encryption operation which qualifies as an endofunctor of this supercategory is "more fully" homeomorphic since additional operations on encrypted data (for example conditionals and loops) are possible.

That certainly supports your point. I suppose--more speculation by me-- it must compute both sides of the conditional (in this case, execute the OP_ADD branch and the OP_MULT branch) and then pick one in a way that makes it impossible to tell which "won". That would make a bytecode interperter really impractical, since it would have to compute a huge superset of what any actual bytecode program does, but not logically impossible.

the problem is you won't know the answer to your equality comparison.

You don't need to know the answer, though.

  if (x == 5) { print "hello world"; }
  else { print "goodbye world"; }

The output of the above program would be either "hello world" or "goodbye world". The output is encrypted, so you won't be able to tell. However, it's not true that you needed the decryption key to evaluate "x == 5". That must mean you can do arbitrary conditionals, loops, branching etc without the decryption key.

If I'm wrong about this, I don't understand why.

Did you see my edit above? I think you're right based on working back through the Wikipedia FHE article, but I also think it would mean executing every possible path, i.e. you'd need to at least evaluate "hello world" and "goodbye world", since the computer executing it doesn't know which it turns out to be. As applied to a bytecode interpreter, that would seem to mean it has to execute every possible program the same length as your bytecode, since it doesn't know what any of them do.

tl;dr here be dragons.

The ability to evaluate statements such as x == 5 falls under the realm of functional encryption ( see Boneh, Sahai, and Waters for a good intro http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.383... ).

You have to be very careful when mixing functional schemes with FHE schemes as it is very easy to create a completely insecure system.

For example, if you could evaluate arbitrary circuits consider what happens if you can evaluate equals and bitwise AND, two simple circuits.

  ({x}&{0x1}) == {0x1}
  ({x}&{0x2}) == {0x2}
  ({x}&{0x4}) == {0x4}

Keep going for all the powers of two expressible in the system and you can quickly check if every bit is set. This makes proving security for functional schemes that allow malleability very difficult, since you have to prove that the reachable set of states with the built in malleability does not reveal sufficient information for the attacker to compromise the security of the system.

One more thing worth mentioning is that a direct comparison of ciphertexts doesn't work for semantically secure schemes. Anything that is IND-CPA, for example RSA-OAEP, will have the same plaintext encrypt to two different ciphertexts. Giving the untrusted server the ability to determine whether two ciphertexts will destroy the semantic security of the scheme, by definition.

You can do arbitrary computations, but you only get the encrypted result. So you can't actually tell whether x == y unless you have the key.

If you can do arbitrary computations, you can do loops and conditionals and whatever else you want. FHE claims to support arbitrary computations, so by definition it must support the ability to do any loop or any conditional.

Think of it this way: A conditional is "if this, do that." If the conditional is true, then the branch is executed. The output of the branch is still encrypted, but it's not true that you need the decryption key just to evaluate the branch. Right?

Reply on news.ycombinator.com