4 ms·
You can't do control flow homomorphicly, so that tends to throw a wrench into this kind of thing.
by KenoFischer 7y ago
You can't do control flow homomorphicly, so that tends to throw a wrench into this kind of thing.
- imglorp 7y agoWhat is the set of operations that are supported?
- aneutron 7y agoI think the answer to this would be enough to determine if it's a base for the vector space of operations.
- nindanaoto 7y agoThis may be enough, right? https://tfhe.github.io/tfhe/gate-bootstrapping-api.html https://tfhe.github.io/tfhe/gate-bootstrapping-api.html
- imglorp 7y agoSo 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.
- artemonster 7y agoPlease 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?
- lonelappde 7y agoAre loops general control flow? Can they do branching? I don't think so, but not sure.
- artemonster 7y agoloops as in "feedback in a circuit", not code loops. Feedback is necessary to create stateful circuits, state is necessary for "control flow"
- nindanaoto 7y agoYes, it can be stateful. We built processor
- heavenlyblue 7y agoNo, 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.
- dragonwriter 7y ago> 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.
- api 7y agoI guess then that my hypothetical fully homomorphic C-64 would be huge and would have a limited run-time?
- lazersharkman 7y agoYes. No recursion. Essentially what could be fabbed as a circuit
- api 7y agoI 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.
- phkahler 7y agoIf you can do a NAND gate homomorphically you can do an entire computer.
- artemonster 7y agoonly if you are allowed stateful circuits! if its a FUNCTION i.e. straight input->output mapping, then no, you cannot do a "computer"
- deleted 7y ago[deleted]