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"