ShapeCPU was the first one that I know of (https://github.com/hcrypt-project/obliviousJ).

I built one off the same infrastructure called hideCPU. If you can create AND/XOR/NAND/etc gates _and_ feed-back output into your input, you can create a CPU.

https://github.com/mmastrac/oblivious-cpu

My goal was more to build some open prior art in the space rather than actually build a viable FHE CPU, but there's no reason why you couldn't implement one of these on top of the FHE system.

To answer some statements about FHE computing that come up over and over:

- Yes, you can loop + perform control flow in a FHE-based computer

- Yes, you can recurse in a FHE-based computer as long as you have enough emulated RAM/stack

- Yes, you can store state in a FHE computer

- No, you cannot determine if a FHE computer has reached a certain state (or halted) from the outside without decrypting the system (or at least a state bit)

- Yes, you can emulate RAM in a FHE computer

- Yes, you can emulate a HDD (well, rotating storage) in a certain FHE computer constructions

From some napkin math and googling, a 6502 has 4.5k transistors, which at 13 ms per gate is about a minute per cycle, divided by how many gates there really are per transistor.

How does your implementation compare?

~20k gates total (ShapeCPU was ~30k gates), but the _real_ bottleneck for FHE computing is the longest path from input to output as FHE computers are highly parallel.

I am sure I had a stat for the longest path from input to output, but I'm a few years swapped out on this project.

Note that adding pipelining to a CPU drastically reduces the longest path. ShapeCPU is not pipelined at all which probably means there's a bunch of low-hanging fruit.

We made our original CPU&ISA emulator over TFHE. https://github.com/virtualsecureplatform/kvsp

Because we use chisel to write CPU and we also made LLVM backend for our original CPU, your idea is not so difficult although it may be very slow. Our original CPU is about 4K gates. The most difficult point is building memory because it is most slow part. We used TFHE's LHE mode for it and this is one of the novel points of our work.

(We didn't know about Shape CPU but it seems to be similar to FURISC, which is published and using libScarab.https://eprint.iacr.org/2015/699)

Interesting. FURISC looks like it cribbed a lot of ideas off ShapeCPU without referencing prior art. I find it hard to believe someone would be working on a libScarab-based CPU without seeing ShapeCPU as well.

Encrypted termination conditions were definitely in that implementation. The memory mux too.

I'm also doubting that but before I knew Shape CPU, I believed because FURISC seems to be based on HEROIC, which is claimed to be the first processor emulation over homomorphic encryption. https://past.date-conference.com/proceedings-archive/PAPERS/... I think FURISC is more like HEROIC than ShapeCPU.

By the way, I feel sad for there is no publication of ShapeCPU. I guess that this is one of the causes of FURISC paper is lacking reference for ShapeCPU.

It looks like ShapeCPU originated around 2012 but only made it into posters, not papers. It's kind of a shame because I spent quite some time reproducing their work to confirm that it was viable, then building on top of it with HideCPU.

Lots of prior art in that implementation!

Our original CPU, CAHP-emerald is 5 stage pipeline, super-scalar processor. Pipelining improved performance well. https://github.com/virtualsecureplatform/cahp-emerald

You can't do control flow homomorphicly, so that tends to throw a wrench into this kind of thing.

No, you can. Any control flow program can be converted into a matrix multiplication. Obviously, the matrix size is exponential to the number of if conditions - but that is a pre-requisite for homomorphic encryption anyway, otherwise you would be able to tell which branch was taken.

> Any control flow program can be converted into a matrix multiplication.

Any control flow program, on a set of inputs for which it terminates[0], can be, but it's not true that any control flow program, with unspecified inputs, can be, even with variables for the inputs, since the shape of the multiplication as well as the value of elements in the matrices may depend on the inputs (also, whether it's even a terminating program can obviously depend on the inputs.)

[0] and any program which always terminates can also be, though the general form may be more complex than is necessary for some inputs.

No, any program can be converted into a matrix form.

Non-terminating programs are modelled as infinitely-sized matrixes, which are obviously not computable; but neither are non-terminating programs computable in the real sense.

I guess then that my hypothetical fully homomorphic C-64 would be huge and would have a limited run-time?

Yes. No recursion. Essentially what could be fabbed as a circuit

I get it. I think I had the misconception that you could branch in FHE, but as I think about it this would by its nature reveal quite a lot of information about the plaintext.

Would it perhaps be possible to create a weaker form of homomorphic encryption that could branch? It would not be strong enough for the most serious security use cases (authentication, financial, etc.) but would perhaps be usable for cases where you just want to protect data confidentiality e.g. processing PII. The processor could probably infer the structure of the running program but not necessarily its data if appropriate constant-time comparisons and other constructions were used.

If you can branch then you can always run a program that compares the encrypted value to a constant, then iterate over the whole space of possible values for the constant and that way decrypt the value

CPUs are a circuit. What are you on about?

Ergo, you can model anything CPUs do as a matrix.

We've asked you before to edit the swipes out of your comments here. If you keep doing it, like here and https://news.ycombinator.com/item?id=22847040 from yesterday, we're going to have to ban you. I don't want to do that, so would you please just make your substantive points thoughtfully?

If you wouldn't mind reviewing https://news.ycombinator.com/newsguidelines.html and sticking to the rules when posting here, we'd be grateful.

Yes, of course you can do if conversion. The exponential increase in execution time is the wrench I was talking about ;).

Not if you can properly model sparse matrices.

Please correct me if I am wrong: you can simulate a function built out of binary gates with encrypted data, but you cannot simulate a state machine over encrypted inputs? Since the webpage says "arbitrary circuit", so it can have loops, so it can be stateful, right? Is this somehow fundamental restriction or just not solved yet?

Are loops general control flow? Can they do branching?

I don't think so, but not sure.

loops as in "feedback in a circuit", not code loops. Feedback is necessary to create stateful circuits, state is necessary for "control flow"

Yes, it can be stateful. We built processor

What is the set of operations that are supported?

This may be enough, right? https://tfhe.github.io/tfhe/gate-bootstrapping-api.html

So it looks like you can have:

    CONSTANT NOT COPY NAND OR AND XOR XNOR NOR ANDNY ANDYN ORNY ORYN MUX

... so pure, combinational logic operators. You can build up some serious functions with these, yes.

I think the answer to this would be enough to determine if it's a base for the vector space of operations.

If you can do a NAND gate homomorphically you can do an entire computer.

only if you are allowed stateful circuits! if its a FUNCTION i.e. straight input->output mapping, then no, you cannot do a "computer"