5 ms·

I wonder at what point might we implement a very old CPU like the 6502/6510 on this and demonstrate the proof of concept of e.g. a very very slow fully homomorp

by api 7y ago

I wonder at what point might we implement a very old CPU like the 6502/6510 on this and demonstrate the proof of concept of e.g. a very very slow fully homomorphic Commodore 64 emulator. Has it been done?

KenoFischer 7y ago
You can't do control flow homomorphicly, so that tends to throw a wrench into this kind of thing.
- imglorp 7y ago
  What is the set of operations that are supported?
  - aneutron 7y ago
    I think the answer to this would be enough to determine if it's a base for the vector space of operations.
  - nindanaoto 7y ago
    This may be enough, right? https://tfhe.github.io/tfhe/gate-bootstrapping-api.html https://tfhe.github.io/tfhe/gate-bootstrapping-api.html
    - imglorp 7y ago
      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.
- artemonster 7y ago
  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?
  - lonelappde 7y ago
    Are loops general control flow? Can they do branching? I don't think so, but not sure.
    - artemonster 7y ago
      loops as in "feedback in a circuit", not code loops. Feedback is necessary to create stateful circuits, state is necessary for "control flow"
  - nindanaoto 7y ago
    Yes, it can be stateful. We built processor
- heavenlyblue 7y ago
  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.
  - 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 ago
      I guess then that my hypothetical fully homomorphic C-64 would be huge and would have a limited run-time?
      - lazersharkman 7y ago
        Yes. No recursion. Essentially what could be fabbed as a circuit
        api 7y ago
        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.
- phkahler 7y ago
  If you can do a NAND gate homomorphically you can do an entire computer.
  - artemonster 7y ago
    only 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]
mmastrac 7y ago
ShapeCPU was the first one that I know of (https://github.com/hcrypt-project/obliviousJ 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 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
- rjeli 7y ago
  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?
  - mmastrac 7y ago
    ~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.
nindanaoto 7y ago
We made our original CPU&ISA emulator over TFHE. https://github.com/virtualsecureplatform/kvsp 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 https://eprint.iacr.org/2015/699)
- nindanaoto 7y ago
  Our original CPU, CAHP-emerald is 5 stage pipeline, super-scalar processor. Pipelining improved performance well. https://github.com/virtualsecureplatform/cahp-emerald https://github.com/virtualsecureplatform/cahp-emerald
- mmastrac 7y ago
  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.
  - nindanaoto 7y ago
    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/2014/DATE14/PDFFILES/09.3_4.PDF 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.
    - mmastrac 7y ago

by api 7y ago

KenoFischer 7y ago

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

imglorp 7y ago
What is the set of operations that are supported?
- aneutron 7y ago
  I think the answer to this would be enough to determine if it's a base for the vector space of operations.
- nindanaoto 7y ago
  This may be enough, right? https://tfhe.github.io/tfhe/gate-bootstrapping-api.html https://tfhe.github.io/tfhe/gate-bootstrapping-api.html
  - imglorp 7y ago
    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.
artemonster 7y ago
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?
- lonelappde 7y ago
  Are loops general control flow? Can they do branching? I don't think so, but not sure.
  - artemonster 7y ago
    loops as in "feedback in a circuit", not code loops. Feedback is necessary to create stateful circuits, state is necessary for "control flow"
- nindanaoto 7y ago
  Yes, it can be stateful. We built processor
heavenlyblue 7y ago
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.
- 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 ago
    I guess then that my hypothetical fully homomorphic C-64 would be huge and would have a limited run-time?
    - lazersharkman 7y ago
      Yes. No recursion. Essentially what could be fabbed as a circuit
      - api 7y ago
        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.
phkahler 7y ago
If you can do a NAND gate homomorphically you can do an entire computer.
- artemonster 7y ago
  only 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]

mmastrac 7y ago

ShapeCPU was the first one that I know of (https://github.com/hcrypt-project/obliviousJ 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 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

rjeli 7y ago
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?
- mmastrac 7y ago
  ~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.

nindanaoto 7y ago

We made our original CPU&ISA emulator over TFHE. https://github.com/virtualsecureplatform/kvsp 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 https://eprint.iacr.org/2015/699)

nindanaoto 7y ago
Our original CPU, CAHP-emerald is 5 stage pipeline, super-scalar processor. Pipelining improved performance well. https://github.com/virtualsecureplatform/cahp-emerald https://github.com/virtualsecureplatform/cahp-emerald
mmastrac 7y ago
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.
- nindanaoto 7y ago
  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/2014/DATE14/PDFFILES/09.3_4.PDF 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.
  - mmastrac 7y ago