Skip to content

mmastrac/oblivious-cpu

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
bin
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

oblivious-cpu Build Status

Two CPUs based on Fully Homomorphic Encryption (Wikipedia).

  1. HideCPU: a novel four-register, byte-based CPU (see definition here).

To run:

git clone --recursive https://github.com/mmastrac/oblivious-cpu.git
bin/build.sh
# Run the sort test
bin/hidecpu.sh run hidecpu/samples/sort.asm
# Run the credit-card check digit test
bin/hidecpu.sh run hidecpu/samples/creditcard.asm
  1. A re-implementation of ShapeCPU with a number of optimizations (see definition here).

To run:

git clone --recursive https://github.com/mmastrac/oblivious-cpu.git
bin/build.sh
# Run the sort test
bin/shapecpu.sh run shapecpu/samples/sort.asm
# Run the credit-card check digit test
bin/shapecpu.sh run shapecpu/samples/creditcard.asm

Implementation Notes

This project uses a register transfer language built in Java to execute a CPU in either an immediate or a "recording" mode that can be used to construct a graph of XOR, AND and NOT operators. This approach allows us to optimize the CPU offline, removing redundant operations and reducing the overall gate count of the CPU. The graph can also be exported to a form that can be executed in an alternate FHE environment (C, etc) rather that in the Java environment provided.

Optimizations

The graph optimizer currently optimizes the following patterns:

  • Unused nodes with no outputs (trimmed)
  • Greedy common-subexpression extraction
  • Constant folding (x XOR constant, x AND constant)

The graph optimizer does not optimize the following (yet):

  • !!a -> a
  • (!a XOR !b) -> (a XOR b)
  • (a XOR a XOR b) -> b
  • (a XOR b) AND !(b XOR c) -> (a XOR b) AND (a XOR c)
  • (a AND b) XOR (a AND c) -> a AND (b XOR c)

TODO

  • Proper documentation
  • An implementation of C. Gentry's fully homomorphic system (perhaps through libScarab)

Links

The original version of ShapeCPU is here: https://hcrypt.com/shape-cpu/

License: Apache v2.0 license

Note that some of the ShapeCPU samples may be under the ShapeCPU license.

About

A re-implementation of ShapeCPU

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published