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
makeTo test the basic comparison of integers, use the following command
./comparison_circuit circuit_type p d m q l runs print_debug_infowhere
circuit_type takes one of three values U, B or T corresponding 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: type y or n to 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 yThe sorting algorithm can be executed by the following line
./sorting_circuit p d m q l N runs print_debug_infowhere 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_infowhere
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.