Hacker News Reader

Comment by guelo | Hacker News Reader

According to https://hcrypt.com/scarab-library/, the functions that you can do on encrypted texts are

  Add cyphertexts (= XOR)
  Multiply cyphertexts (= AND)
  Add with carry in and carry out
  Add with carry out

I'm not really familiar with homomorphic theory, but it doesn't seem like you could build that much on top of these primitives.

View on HN

You can build everything on top of that - (a AND b) XOR 1 = a NAND b and you can build any boolean function out of NAND gates. So just make the cipher text the (encrypted) memory of a virtual machine, design a processor out of the mentioned primitives just like you design any ordinary processor and then execute it. And that is what they actually did with the Shape CPU [1].

[1] https://hcrypt.com/shape-cpu/

You may want to start here:

https://en.wikipedia.org/wiki/Group_homomorphism

The way I've understood it is that only addition has been possible so far. With a multiplication operation, you can get a field, and do "everything" with the real/complex numbers.

Well a homomorphism applies to a group and a group can only have one operator by definition. That won't change probably. Rings have two operators, fields are rings that support cancellation and integral fields I believe support inverses as a rule and where you'd get "everything" I believe.

"Well a homomorphism applies to a group"

Not so. The notion's far more general: https://en.wikipedia.org/wiki/Ring_homomorphism

This gives us a notion of homomorphisms between fields.

https://en.wikipedia.org/wiki/Homomorphism for more general notions of homomorphisms.

You're right. My bad. Thanks for correcting me.

You could run transactions on a signed wallet and even compute interest... I'm sure there are also other, less obvious, use cases as well.

Add with carry-out seems like it could be use to build some complex systems.

Reply on news.ycombinator.com