Circom Circuit Library for Fully Homomorphic Encryption

Description

Thus repository contains a library of circuit templates for Fully Homomorphic Encryption (FHE) computations in the circom language, a high-level domain-specific language for zero-knowledge proofs. You can learn more about circom by reading the circom docs.

The circuits implement schemes based on Ring Learning With Errors (RLWE) such as BGV (and a stripped-down version of CKKS), as well as the LWE schemes FHEW and TFHE. The references for the scheme implementations are shown below:

Scheme	Reference Paper	Reference Implementation
BGV	Fully Homomorphic Encryption without Bootstrapping Revisiting Homomorphic Encryption Schemes for Finite Fields	SEAL
FHEW/TFHE	FHEW: Bootstrapping Homomorphic Encryption in less than a second Bootstrapping in FHEW-like Cryptosystems	OpenFHE

Organisation

This repository contains 3 main folders: circuits, test, and bench:

Circuits

circuits
├─ mod.circom ┄┄ modular reduction
├─ add.circom ┄┄ modular addition and subtraction of integers and polynomials
├─ mul.circompoint-wise multiplication, multiplication of polynomials and ciphertexts
├─ rns.circom Residue Number System (RNS) operations
├─ ntt.circom ┄┄ Number Theoretic Transform (NTT)
├─ signed_decomposition.circom ┄┄ signed digit decomposition of integers and RLWE ciphertexts
├─ array_access.circom ┄┄ access to array elements pointed by signal indices
├─ lwe.circom ┄┄ addition, subtraction, modulus switching and key switching of LWE ciphertexts
├─ rlwe.circom ┄┄ addition of RLWE ciphertexts and RLWE-RGSW multiplication
├─ bootstrap.circom ┄┄ accumulator initialization and extractor, common to FHEW and TFHE
├─ bootstrap_fhew.circom ┄┄ accumulator update for FHEW scheme
├─ bootstrap_tfhe.circom ┄┄ accumulator update for TFHE scheme
├─ fast_compconstant.circom ┄┄ fast comparisons between signals and constants
├─ nand.circom ┄┄ bootstrapped NAND gate
├─ noise_flooding.circom ┄┄ simple additive noise flooding for RLWE ciphertexts
├─ ring.circom ┄┄ operations assuming the underlying algebra is the ring $Z_{q_1\dots q_L}[X]/(X^N+1)$, useful for ring-based ZKP such as Rinocchio
├─ util.circom ┄┄ min, max, logarithms and extended-gcd functions
├─ circomlib/ ┄┄ the circomlib repo, imported as a git submodule
└─ ...

Benchmarks

bench contains templates and circom files for various FHE (sub-)computations, as well as executables to run them.

Test

test contains tests (written as circom templates with known test vectors) for various FHE (sub-)computations.