README
A reference implementation for Prof. Elaine Shi's Circuit Oblivious Heap algorithm, on top of wangxiao1254's garbled circuit implementation (https://github.com/wangxiao1254/FlexSC).
Requirements
Known to compile with OpenJDK 11.0.4.
Files
Significant changes from wangxiao1254's Circuit ORAM implementation include:
src/oheap/CircuitOHeap: the primary file, containing reference implementations for all six operations (findMin, delete, insert, extractMin, decreaseKey, increaseKey) as well as an option for enabling type-hiding security.src/oheap/BlockandPlainBlock: now contain a key field in addition to the previous t/iden, leafId/pos, data, and isDummy fields. Corresponding changes in other files have been made to e.g. serialization to account for the extra field.src/oheap/TreeBasedOHeapParty: now handles securely updating subtree mins.test/oheap/CountCircuitOHeap: Runs the Circuit OHeap with an env set toMode.COUNT, which quickly counts circuit statistics in place of running the full protocol.test/oheap/TestCircuitOHeapVerify: Runs the Circuit OHeap with an env set toMode.VERIFYalongside the same operations done on a regular heap to verify the correctness of the implementation.test/oheap/TestCircuitOHeapReal: Similar to above, but runs the Circuit OHeap with an env set toMode.REALinstead. This test may run slower than the previous two tests.
For more information on CompEnv modes, see https://github.com/wangxiao1254/FlexSC/blob/master/README.md.
Compiling and Running
Compile with ./compile.sh and run with any of ./runCountOHeap.sh, ./runTestOHeapVerify.sh, or ./runTestOHeapReal.sh.