Poulpy

Poulpy is a Rust FHE library using spqlios-arithmetic as backend. Traditional FHE implementations (such as Lattigo or OpenFHE) use the residue-number-system (RNS) to represent large integers. Although the parallelism and carry-less arithmetic provided by the RNS representation enables a very efficient modular arithmetic over large-integers, it introduces the following issues when used it in the context of FHE:

The main idea behind the approach taken by spqlios is to decouple the cyclotomic arithmetic from the large number arithmetic. Instead of using the RNS representation for large integer, they are decomposed in base $2^{-k}$ over the Torus $\mathbb{T}_{N}[X]$.

• Easy, efficient and reusable parameterization/instance: Only the bit-size of the modulus needs to be specified. As such, parameters are generic and can be reused for any circuit consuming the same homomorphic capacity, without loss of efficiency. With the RNS representation, individual NTT friendly primes needs to be specified, making the parameterization circuit-specific and inefficient to reuse across different circuits.
• Optimal and granular rescaling: Ciphertext division is carried out with bit-shifting, enabling a granular rescaling and optimal noise/homomorphic capacity management. In the RNS representation, ciphertext division can only be done by one of the primes composing the modulus, leading to frequent inefficient noise/homomorphic capacity management.
• Linear number of DFT in the half external product: the base2K representation of the coefficients implicitly provides the decomposition, as such the number of DFT is linear in the number of limbs, contrary to the RNS representation where it is quadratic.
• Friendly to hardware acceleration: Since the cyclotomic arithmetic is decoupled from the coefficient representation, the same pipeline (including DFT) can be reused for all limbs, and thus possible parameterizations. Unlike in the RNS representation, where a different and prime-specific DFT is used for each limb, making the pipeline circuit-specific.
• Unified ciphertext/plaintext space: All schemes are instantiated over the Torus $\mathbb{T}_{N}[X]$, which provides a unified ciphertext and plaintext space, independent of the scheme parameterization.

A detailed explanation of the base2K representation is given in Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic.

Poulpy aims to provide:

• A user friendly, generic and scheme agnostic low-level API
• A user friendly implementation, API and parameterization for all mainstream FHE schemes (BFV/BGV, CKKS, TFHE/FHEW)
• Scheme switching
• Multiparty protocols (MHE) and key generation
• Noise estimations for the core functions