This repository contains the LaTeX and C++ code of the homomorphic pattern matching algorithm from the paper "Faster homomorphic comparison operations for BGV and BFV" by Ilia Iliashenko and Vincent Zucca.
To build the code, install HElib (>= 2.0.0), go to the code folder and run
cmake .
and finally
make
To test the basic comparison of integers, use the following command
./comparison_circuit circuit_type p d m q l runs print_debug_info
where
circuit_typetakes one of three valuesU,BorTcorresponding to our univariate, bivariate circuits and the circuit of Tan et al..p: the plaintext modulus, must be a prime number.d: the dimension of a vector space over the slot finite field.m: the order of the cyclotomic ring.q: the minimal bitsize of the ciphertext modulus in ciphertexts. The actual size of the modulus is automatically chosen by HElib.l: the length of finite field vectors to be compared.runs: the number of experiments.print_debug_info: typeyornto show/hide more details on computation. More details on these parameters can be found in Section 5 of the paper.
The following line performs 10 tests of our bivariate comparison circuit comparing vectors of length 3 over the finite field of order 49.
./comparison_circuit B 7 2 300 90 3 10 y
The sorting algorithm can be executed by the following line
./sorting_circuit p d m q l N runs print_debug_info
where the most arguments are analogous to the comparison circuit above. The additional argument is
N: the number of values to be sorted (see Section 4.1 of the paper).
By default, the sorting algorithm uses the univariate circuit.
To test the minimum function, run this command
./min_max_circuit p d m q l N T runs print_debug_info
where
N: the number of values in the input array.T: the number of tournament stages (see Section 4.2 of the paper).
Other arguments have the same meaning as above. The univariate circuit is used here by default.