Circuit for proving the correct encryption under BFV fully homomorphic encryption scheme. Note that this can be also generalized to any RLWE-based FHE scheme. Based on https://hackmd.io/@gaussian/r1W98Kqqa.
To generate the parameters for the secret key proof of encryption circuit run the following command:
python3 scripts/circuit_sk.py -n 1024 -qis '[
1152921504606584833,
1152921504598720513,
1152921504597016577,
1152921504595968001,
1152921504595640321,
1152921504593412097,
1152921504592822273,
1152921504592429057,
1152921504589938689,
1152921504586530817,
1152921504585547777,
1152921504583647233,
1152921504581877761,
1152921504581419009,
1152921504580894721
]' -t 65537Where -n is the degree of the polynomial, -qis is the list of moduli qis such that qis[i] is the modulus of the i-th CRT basis of the modulus q of the ciphertext space, -t is the plaintext modulus. The value of 𝜎 for the gaussian distribution is set to 3.2 by default.
You can modify these parameters to fit your needs. Note that the qis should be all prime numbers. That's because the python script is using ntt to perform the polynomial multiplication.
As a result:
- A file
./src/data/sk_enc_{n}_{qis_len}x{qis_bitsize}_{t}.jsonis generated including the input to the circuit that can be used for testing for those specific parameters. It includes a random secret key, a random plaintext message and the corresponding ciphertext encrypted under the secret key. - A file
./src/data/sk_enc_{n}_{qis_len}x{qis_bitsize}_{t}_zeroes.jsonis generated. In this file all the coefficients of the input polynomials are set to zero. This input is used at key generation time, when the actual inputs are not known. - A file
./src/constants/sk_enc_constants_{n}_{qis_len}x{qis_bitsize}_{t}.rsis generated including the generic constants for the circuit. Note that we separate them from the input because these should be known at compile time.
On top of that, the console will print an estimatation of the number of advice cells needed to compile the circuit in halo2 considering a single advice column and a lookup table of size 2^8. Spoiler: around 90% of the constraints are generated by the range checks on the polynomial coefficients.
cargo build
cargo test --release -- --nocapture
The halo2 circuit is based on a fork of axiom-eth that implements two minor changes:
RlcCircuitandRlcExecutorare included into a utils mod such that they can be consumed outside of the crate- The
RlcCircuitInstructionsare modified to enable equality constraints on instance column in Second Phase
To extract the benchmarks run:
cargo test --release bench_sk_enc_full_prover --features bench -- --nocapture
By default, the benchmarks are run on the input data generated by the python script described above. Namely,n = 1024 with 15 qis of 60 bits each and t = 65537.
To run the benchmarks on different parameters you have to:
- Modify the constants being imported. For example
use crate::constants::sk_enc_constants_2048_15x60_65537::... - Modify the
file_pathwithinbench_sk_enc_full_prover()function to point to the new input data file. For examplelet file_path = "src/data/sk_enc_2048_15x60_65537.json";
Given the same parameters, the benchmarks will run the prover and verifier for different values of k, where 2**k is the maximum number of rows in the advice columns. After setting a specific k, halo2-lib will configure the circuit accordingly. With less rows at disposal, the configuration will contain more columns, and viceversa.
More columns means more parallelism, which generally means faster proving times. Up to a point. Quoting halo2-lib docs, there is a limit to parallelism, so generally the proving time vs. number of columns plot looks parabolic: as you increase number of columns (while keeping number of cells the same), the proving time will decrease up to a point before starting to increase again.
Benchmarks run on M2 Macbook Pro with 12 cores and 32GB of RAM.
Note that while fixing the qis and t, doubling the degree of the polynomial will roughly double the proving time. For certain parameters, low values of k might result in errors due to the lack of advice columns. That's why for certain parameters the benchmarks start at higher values of k.
For more clarity on parameters choise, please check Homomorphic Encryption Standard.
bfv params: "src/data/sk_enc_1024_15x60_65537"
+----+--------------------+--------------------+-----------------------+-------------------------+
| K | VK Generation Time | PK Generation Time | Proof Generation Time | Proof Verification Time |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 12 | 5.295224709s | 1.358041375s | 7.991257584s | 32.794959ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 13 | 4.247296791s | 1.0530105s | 6.284730291s | 16.836083ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 14 | 3.46852s | 990.696083ms | 5.495415083s | 9.841083ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 15 | 3.016624458s | 989.328ms | 4.992188333s | 6.211917ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 16 | 2.844255667s | 889.777792ms | 4.5923275s | 3.839ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 17 | 2.248404833s | 860.284625ms | 4.977683708s | 3.209208ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 18 | 2.839828541s | 1.053538875s | 6.921447459s | 2.818334ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
bfv params: "src/data/sk_enc_2048_15x60_65537"
+----+--------------------+--------------------+-----------------------+-------------------------+
| K | VK Generation Time | PK Generation Time | Proof Generation Time | Proof Verification Time |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 12 | 10.824611041s | 2.908279875s | 16.063535333s | 68.496833ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 13 | 8.572612625s | 2.299866541s | 12.426581708s | 32.002083ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 14 | 7.34011275s | 2.065126458s | 11.075031292s | 17.973708ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 15 | 6.470459875s | 2.06113525s | 9.826643875s | 10.0565ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 16 | 5.581423042s | 1.818410542s | 8.64577325s | 6.049625ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 17 | 4.87873075s | 1.706358375s | 8.558883208s | 4.06775ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 18 | 4.70213375s | 1.794651s | 9.722160583s | 3.144958ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
bfv params: "src/data/sk_enc_4096_15x60_65537"
+----+--------------------+--------------------+-----------------------+-------------------------+
| K | VK Generation Time | PK Generation Time | Proof Generation Time | Proof Verification Time |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 13 | 18.027390875s | 5.230272125s | 24.444788333s | 62.492625ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 14 | 14.499338459s | 4.382318709s | 21.497476292s | 30.128416ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 15 | 12.869778584s | 4.183937167s | 19.691059666s | 16.315917ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 16 | 9.959281042s | 3.601998041s | 16.1026055s | 9.205875ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 17 | 9.080435667s | 3.388096417s | 15.132209917s | 6.01225ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 18 | 8.297806291s | 3.376244042s | 15.097758875s | 3.8735ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
bfv params: "src/data/sk_enc_8192_15x60_65537"
+----+--------------------+--------------------+-----------------------+-------------------------+
| K | VK Generation Time | PK Generation Time | Proof Generation Time | Proof Verification Time |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 13 | 37.169986417s | 12.0014235s | 49.280054s | 139.740625ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 14 | 30.456496542s | 10.223706459s | 44.578064458s | 64.477208ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 15 | 27.082947s | 9.938396416s | 38.883754125s | 32.343708ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 16 | 21.616090417s | 8.148581666s | 30.988306541s | 15.593083ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 17 | 17.714040042s | 7.119117709s | 27.72848125s | 8.860292ms |
+----+--------------------+--------------------+-----------------------+-------------------------+
| 18 | 16.126342959s | 6.547376875s | 26.437617458s | 5.407542ms |
+----+--------------------+--------------------+-----------------------+-------------------------+