MinHash-HE

Installing Dependencies

In order to run MinHash homomorphically, we need to install some dependencies.

first, we will build the Google-XLS framework from their GitHub repository. Google-XLS depends on bazel so you need to install bazel beforehand.

sudo apt install apt-transport-https curl gnupg -y
curl -fsSL https://bazel.build/bazel-release.pub.gpg | gpg --dearmor >bazel-archive-keyring.gpg
sudo mv bazel-archive-keyring.gpg /usr/share/keyrings
echo "deb [arch=amd64 signed-by=/usr/share/keyrings/bazel-archive-keyring.gpg] https://storage.googleapis.com/bazel-apt stable jdk1.8" | sudo tee /etc/apt/sources.list.d/bazel.list

sudo apt update && sudo apt install bazel

sudo apt update && sudo apt install bazel-6.4.0

We run the following commands to build XLS with bazel.

git clone https://github.com/google/xls.git
cd xls

bazel --version
sudo apt install python3-distutils python3-dev libtinfo5 python-is-python3
bazel test -c opt -- //xls/...

now that we have builded our Google-XLS, we need to build Yosys from the GitHub repository.

$ sudo apt-get install build-essential clang bison flex \
	libreadline-dev gawk tcl-dev libffi-dev git \
	graphviz xdot pkg-config python3 libboost-system-dev \
	libboost-python-dev libboost-filesystem-dev zlib1g-dev

git clone https://github.com/YosysHQ/yosys.git
cd yosys
make

now we clone HELM from the GitHub repository. HELM requires at least rustc version 1.72 to build. To do this first remove any lower version of rustc you have.

apt autoremove rustc
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
export PATH=~/.cargo/bin:$PATH
rustc --version

check if the rustc version installed is at least 1.72. Now we clone and build HELM.

git clone --recurse-submodules https://github.com/TrustworthyComputing/helm.git
cd helm
cargo build --release

Now that we have built all of the dependencies, we start by cloning and running this repository.

note that Yosys, XLS, and HELM builds need to be in the same directory for the scripts to work.

Running MinHash-HE

Now we start running our scripts to generate and evaluate our circuits. First we go into the minhash-HE directory and run the xls.sh bash script. The commands we use for the Google-XLS is as follows:

../../xls/bazel-bin/xls/contrib/xlscc/xlscc "$1".cc > minhash.ir
../../xls/bazel-bin/xls/tools/opt_main minhash.ir > minhash.opt.ir
../../xls/bazel-bin/xls/tools/codegen_main minhash.opt.ir \
  --generator=combinational \
  --delay_model="unit" \
  --output_verilog_path="$1".v \
  --module_name=min_hash \
  --top=minhash

now we use Yoysys to generate a netlist from the output verilog using the following commands or running the yosys.ys script file.

proc
flatten
synth
abc -g simple,-MUX
splitnets
stat
write_verilog -noexpr ../yosys-netlists/minhash_in.v

now we run HELM preprocessor to generate our homomorphic circuits.

cargo run --bin preprocessor --release \
   --manifest-path=./hdl-benchmarks/Cargo.toml -- \
   --input ../minhash/yosys-netlists/"$1"_in.v \
   --output ../minhash/helm-preprocessed-netlists/"$1"_out.v

now we evaluate the homomorphic circuit generated using HELM.

cargo run --bin helm --release -- \
    --verilog ../minhash/helm-preprocessed-netlists/"$1"_out.v

we follow these processes for each C++ MinHash program we want to evaluate homomorphically.

How to cite this work

The MatcHEd article that details this work can be cited as follows:

@misc{shokri2023MatcHEd,
    author       = {Rostin Shokri and Charles Gouert and Nektarios Georgios Tsoutsos},
    title        = {{MatcHEd: Privacy-Preserving Set Similarity based on MinHash}},
    year         = {2023},
    note         = {\url{https://github.com/TrustworthyComputing/minhash-HE/blob/main/MatcHEd.pdf}},
}