This repository contains examples of encrypted network measurement and control fuctions developed under DARPA funding for the I2O Open, Programmable, Secure 5G (OPS5G) program. They represent distributed set operations that would be performed among a group of nodes in a path, a simple BGP-like shortest path calculation, and a dijkstra shortest path computation for a small network.
Additionally, the aes
subdirectory contains examples of AES running
under FHEW and the google transpiler developed under DARPA funding for
the Data Protection in Virtual Environments (DPRIVE) program.
Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited). This work is supported in part by DARPA. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
The Network Measurement/Control Sub-projects work is supported by DARPA through contract number HR0011-21-9-0003. This work was conducted by Duality Technologies as the Prime contractor.
The AES work is supported by DARPA through contract number HR001120C0157. That work was conducted by Duality Technologies as a subcontractor to USC Information Sciences Institute.
Note all this code has only been run under linux. Windows is unsupported at this time.
The Google Transpiler can be found at https://github.com/google/fully-homomorphic-encryption. It runs within its own bazel build system. To simplify things we downnload and build the transplier in one directory, and this repository in another, then softlink the directories together. We then build in the transpiler repo. Our build scripts will move the resulting executables out of the bazel cache back into a bin directory in our repo.
All these projects should be soft linked to the
transpiler\experiments
directory.
Note bazel
must be run above these directories, i.e. in the
experiments
directory in order to correctly operate.
Note also that bazel
can trigger a rebuild of the build system if
any of the upstream sources get updated -- and this can take a very
long time to complete.
openfhe.BUILD.64
and openfhe.BUILD.32
are optimized files for
building 64 bit and 32 bit versions of OpenFHE. One simply replaces
the patches/openfhe.BUILD
file in the transpiler directory with one
of these files (changing the name to openfhe.BUILD
). For almost all parameter sets we recommend using 32 bit OpenFHE (see the OpenFHE documentation for which parameter sets require 64bit arithmetic).
While cloning the transpiler works well, some prefer using docker. You can build the docker image
debian:
docker build -t google-fhe-transpiler -f docker/debian-bullseye.Dockerfile .
Ubuntu:
docker build -t google-fhe-transpiler -f docker/ubuntu-jammy.Dockerfile .
Which builds the (very large) docker file.
You can then run the docker as follows, linking in this code as a
mounted directory (which gets rsynched automatically). Assuming you install this repo in /home/{yournamehere}/Documents/openfhe-transpiler-experiments
:
docker run --rm -i -v /home/{yournamehere}/Documents/openfhe-transpiler-experiments:/home/{yournamehere}/Documents/openfhe-transpiler-experiments -t google-fhe-transpiler bash
note that when running the docker image, you have to make new soft
links to the right project directories (i.e. shortest_path
) within
the examples
subdirectory of the docker image of the transpiler
tree, every time you run the docker image (as it resets).
In general each of these subprojects can generate cleartext (with and without yosys interpreted mode) and openfhe executables (with and without yosys interpeted mode and straight XLS interpreted mode ). In general we suggest always using yosys interpeted mode because a) yosys generally makes smaller circuits and b) yosys interpreted will execute gates in parallel across all available cores, for a much faster run time.
This is an implementation of a simplified BGP protocol. There is no I/O, only computation is benchmarked.
The computing node receives information from a set of upstream neighbor nodes containing path cost information. The computing node selects the minimum cost vector, adds themselves to it, and then sends the output downstream, all encrypted.
Pseudo code:
-
The compute node gets an encrypted cost and encrypted path-id structure from each upstream neighbor. The structure contains : path cost, path length, vector of node IDs with the neighbor at the last element of the vector.
-
Create new vector of encrypted costs of all neighbors.
-
Find index of the minimum cost vector.
-
Loop over all structures (loop variable is
this_index
):
4.1 Generate Boolean variable test
such that test = (this index == encrypted index)
.
4.2 Multiply all values in the struct by test
and add struct to an
accumulated updated version of the struct. Thus, the accumulated
struct contains only the selected path cost, path length and vector
of IDs (note zero is considered an invalid null node).
-
Then the compute node adds their cost to the final cost, increments the vector length and inserts their id at the end of the vector.
-
The compute node passes the new encrypted cost and path id struct downstream (this is implied).
the -c
constraint flag when true, sets a particular node ID's cost
to maximum, preventing it from being included in the computation. This
node number is set using ignoreId
in the main prgraam.
Shortest path was the first project we built using the transpiler, and
we learned alot about what works and what does not. Initially we tried
putting the entire encrypted algorithm into one set of functions
(shortest_path_singlecall
) which led to huge circuits that take a
long time to build and execute. This is primarily due to double loop unrolling.
We then split it into multiple calls,
(shortest_path_multicall
), which builds faster, but still exhibits
combinatorial explosions in the single loop unrolled circuits. Our final version
iterates over encrypted function calls in a software loop (shortest_path_iterative
)
shortest_path_singlecall
is a single call version where all
computation on the input data is done in one encrypted function. It
generates huge circuits that take a long time. Provided only for
pedagogical purposes.
There is one encrypted function compute_shortest_path()
.
shortest_path_multicall
is a multiple call version, which still has
poor runtime performance. Again provided only for pedagogical
purposes.
The following encrypted functions are used:
create_cost_vector()
and
create_constrained_cost_vector()
build the initial encrypted input.
vector_min_index()
: idenifies the index of the minimum element of a vector.
Shortest path: select_path()
: select lowest cost of two paths.
Path advertisement: update_path()
: adds our nodeID and cost to selected path.
shortest_path_iterative
is the final version developed which
combines a software control loop with encrypted function calls. It is
the most efficient way to work. The following descriptions refer only to this version.
One of these directories should be linked to shortest_path
in the transpiler
directory.
Then one can run from the transpiler/examples
directory using commands such as
bazel run //transpiler/examples/shortest_path:shortest_path_yosys_interpreted_openfhe_testbench -- -v -o {full path to output directory}/output.csv
the -c
constraint flag when true, sets the local node's path cost to maximum.
The output files log runtimes and sizes of ciphertexts of the OpenFHE version.
Note running the following will list all possible command line arguments
bazel run //transpiler/examples/shortest_path:shortest_path_cleartext_testbench -- -h
bazel run //transpiler/examples/shortest_path:shortest_path_yosys_interpreted_openfhe_testbench -- -h
To run the openFHE versions you may need to copy/link the following libraries to private_set\bin
libOPENFHEbinfhe.so
libOPENFHEbinfhe.so.1
libOPENFHEcore.so
libOPENFHEcore.so.1
libOPENFHEpke.so
libOPENFHEpke.so.1
or set LD_LIBRARY_PATH
to the appropriate location. You may need to
install the equivalent version of openFHE on your system.
The number of simulated nodes in the process for singlecall and multicall versoins is set in
shortest_paths.h
. Increasing this will increase compile and runtime.
Note in the interative version, one can set the number of nodes at
runtime by using the -n
flag. The maximum number of nodes is still
set in shortest_paths.h
.
This is an implementation of private set processing along a chain of network nodes. It performs intersection or union on a vector of data coming into a node with another vector supplied by the node. The result is passed on to the next neighboring node in a path. The number of nodes simulated is a command line parameter. There is no I/O, only computation is benchmarked.
The maximum vector length MAX_SET_LEN
is specified in
private_set.h
and is currently set to 20. Reducing this will result
in faster compile and run times. Increasing it may create problems
with compilation. YMMV.
If an intersecton causes the resulting vector's length to exceed
MAX_SET_LEN
, an overflow flag is set to true.
private_set
uses a software control loop calling smaller encrypted
modules to avoid the circuit combinatorial overload. It supports
intersection and union.
This directory should be linked to private_set
in the transpiler
directory.
Then one can run from the transpiler/examples
directory manually using
commands such as
bazel run //transpiler/examples/private_set:private_set_yosys_interpreted_cleartext_testbench -- -n 3
Note large numbers of n take a LONG time to run.
The following script will generate all cleartext versions and place them in a bin
directory in private_set
.
private_set/compile_cleartext.sh
and openfhe versions using
private_set/compile_openfhe.sh
Do not worry about warning messages for Slow Loop unrolling.
Note, for some unknown reason, this code compiles for
private_set_yosys_interpreted_openfhe_testbench
but gcc segfaults
when compiling private_set_openfhe_testbench
, so that target is
removed from the compile script.
Once compiled with the script the resutling binary is in the private_set/bin
directory
run bin/private_set_cleartext_testbench
demo with settings (default value show in parenthesis):
-c force common element
-d debug flag (false)
-n # neighbors [20]
-o output file name (out.csv)
-p parameter security set (TOY|STD128_LMKCDEY|STD128Q_LMKCDEY) [TOY] {not in cleartext}
-s seed_integer [1]`
-v verbose flag (false)
-h prints help message
To run the openFHE versions you may need to copy/link the following libraries to private_set\bin
libOPENFHEbinfhe.so
libOPENFHEbinfhe.so.1
libOPENFHEcore.so
libOPENFHEcore.so.1
libOPENFHEpke.so
libOPENFHEpke.so.1
or set LD_LIBRARY_PATH
to the appropriate location. You may need to
install the equivalent version of openFHE on your system.
This is an implementation of the Dijkstra shortest path algorithm, originally published // from https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/ . The orignal dijkstra code is contributed by shivanisinghss2110. Note this code has a hardwired network, and hardwired source node and is basically a proof of concept to show that network algorithms can be executed in encrypted form using the transplier. Note in the future we will release a version that can run with hundreds of nodes.
This version contains three encrypted functions, two of which are run in a software loop over all verticies. Those two have unrolled loops, so that puts a practical limit on the size of the network that can be processed.
Please see the README_AES.md file in the aes
directory for full details.