poulpyFully homomorphic encryption
GitHub ↗Get started →
Menu

Layouts and operations

From polynomials.
To ciphertexts.

For readers exploring the arithmetic internals: polynomial layouts, their products, and key switching. These polynomial vectors implement cryptographic operations; they are distinct from the numerical slot vectors in CKKS.

Explore the layouts ↓

01 / Layouts and products

Polynomials, vectors, matrices

Each square is one polynomial with N coefficients in ℤ[X]/(Xᴺ + 1). Group squares into a vector, then stack vectors into a matrix.

Front-end

ScalarZnx

One polynomial

s

Backend representation

SvpPPol
The scalar prepared for repeated scalar–vector products.

Front-end

VecZnx

A vector of polynomials

v₁
v₂
v₃

Backend representations

VecZnxDft
Transformed limbs for products and accumulation.
VecZnxBig
Wide coefficient limbs after IDFT, before normalization.

Front-end

MatZnx

Each row is a VecZnx

m₁₁
m₁₂
m₁₃
m₂₁
m₂₂
m₂₃
m₃₁
m₃₂
m₃₃

Backend representation

VmpPMat
The matrix prepared for repeated vector–matrix products.

Base 2ᴷ / Signed limbs

One value, several signed limbs

K = base2k sets the digit width, not the machine-word size. Storage can leave headroom for additions.

Each limb has a weight

Three polynomial limbs; values are taken modulo 1.

A polynomial represented by three signed base two to the K limbsv of X equals v one times two to minus K plus v two times two to minus two K plus v three times two to minus three K, coefficientwise modulo one. Each square is a polynomial with N coefficients. After normalization, each limb coefficient is a balanced signed integer from minus two to the power K minus one through plus two to the power K minus one, including both endpoints.v(X) =v₁· 2⁻ᴷ+v₂· 2⁻²ᴷ+v₃· 2⁻³ᴷBalanced digits: −2ᴷ⁻¹ ≤ d ≤ 2ᴷ⁻¹

Each square still contains N coefficients. Its position supplies the weight 2−Ki.

Normalization propagates carries

One coefficient across three limbs · K = 4 · base 16.

Normalize the signed digits 2, 19, minus 3 to 3, 3, minus 3At base sixteen, nineteen equals three plus one times sixteen. Keep three in the middle limb and carry one into the limb on its left. The negative last digit stays minus three. The represented value is unchanged: both weighted sums equal 813 over 4096. Balanced digits may range from minus eight to plus eight, including both endpoints.+123193−3−3NormalizeVecZnxBigVecZnx

19 = 3 + 1 × 16: keep 3, carry 1 to the left. The value stays the same.

SVP Scalar–vector product

Scale each vⱼ by s.

Scalar-vector product: c equals s times vOne square labeled s multiplies a vector of three squares labeled v one, v two, and v three. The output vector contains c one, c two, and c three. Each c j equals s times v j. All symbols name polynomials, and each square has the same size.ScalarZnx · ss×VecZnx · v=VecZnx · cv₁c₁v₂c₂v₃c₃cⱼ = s · vⱼ

VMP Vector–matrix product

Each cⱼ is the dot product of v with column j of M.

Vector-matrix product: c equals v times MA row vector with polynomial entries v one, v two, and v three multiplies a three-by-three matrix whose entries are named m i j, with i and j from one to three. The output row vector contains c one, c two, and c three. Each c j is v one times m one j plus v two times m two j plus v three times m three j.VecZnx · vMatZnx · MVecZnx · c×=v₁m₁₁m₁₂m₁₃v₂m₂₁m₂₂m₂₃v₃m₃₁m₃₂m₃₃c₁c₂c₃cⱼ = v₁m₁ⱼ + v₂m₂ⱼ + v₃m₃ⱼ

Conservative capacity estimate≈ 2K + ⌈log₂ N⌉ bitsFor one product of two polynomial limbs with K-bit signed coefficients. Summing r products adds up to ⌈log₂ r⌉ bits. Signed terms usually cancel, so typical magnitudes are much smaller.

From products back to digitsVecZnxDft supports the computation using the backend’s FFT precision or NTT range. IDFT writes wide VecZnxBig coefficients; normalization carries them back into K-bit signed limbs in VecZnx.

02 / Data lifecycle

Prepare, compute, normalize

Front-end layouts hold signed base-2ᴷ limbs. Backend layouts hold prepared operands, transformed vectors, and wide accumulators.

Backends can customize all seven layouts, especially the backend-specific types such as VmpPMat.

Follow a value through the HAL
Poulpy HAL data representations and their lifecycleThe left region contains the standardized front-end layouts ScalarZnx, VecZnx, and MatZnx. The right region contains the backend-specific layouts SvpPPol, VmpPMat, VecZnxDft, and VecZnxBig. Backends may customize every layout, with customization especially encouraged for backend-specific types. ScalarZnx prepares into reusable SvpPPol; MatZnx prepares into reusable VmpPMat. VecZnx transforms to VecZnxDft. SVP and VMP are independent product branches. Each reads its corresponding prepared operand and a VecZnxDft input, then writes a VecZnxDft result. Neither product runs through the other. The inverse transform writes VecZnxBig, then normalization writes VecZnx. The controls highlight each path while preserving the complete graph. Dashed boxes are operations rather than data structures.FRONT-ENDStandardized layoutsBACKENDBackend-specific layouts · customization encouragedsvp_preparePreparevmp_preparePrepareRead the prepared SvpPPol operandRead the prepared VmpPMat operandvec_znx_dft_applyDFTRead VecZnxDft for the scalar-vector productRead VecZnxDft for the vector-matrix productWrite the scalar-vector product to VecZnxDftWrite the vector-matrix product to VecZnxDftvec_znx_idft_apply; vec_znx_idft_apply_tmpa may overwrite the input bufferIDFTvec_znx_big_normalizeNormalizeSINGLE-LIMB COEFFICIENTSScalarZnxOne limb per polynomial column.For example: a secret-key polynomial.PREPARED SCALARSvpPPolPrepared polynomial columns.Reuse for scalar-vector products.MATRIX OF COEFFICIENTSMatZnxRows of polynomial vectors.Each entry has columns and limbs.PREPARED MATRIXVmpPMatMatrix prepared for repeated products.For example: key-switching material.INPUT · COEFFICIENTSVecZnxN signed coefficients per limb.Normalized digits use K = base2k bits.WORKING · TRANSFORM DOMAINVecZnxDftTransformed signed polynomial limbs.FFT precision or NTT modular range.RESULT · TRANSFORM DOMAINVecZnxDftCapacity for products and their sums.IDFT recovers wide coefficients.WORKING · WIDE COEFFICIENTSVecZnxBigUnnormalized, wide coefficients.Carries may span adjacent limbs.OUTPUT · COEFFICIENTSVecZnxCarries propagated in base 2ᴷ.K-bit signed digits, ready to reuse.SCALAR × VECTORsvp_apply_dft_to_dftReuse the prepared scalar polynomial.VECTOR × MATRIXvmp_apply_dft_to_dftReuse the prepared matrix.

Prepare ScalarZnx once, then reuse SvpPPol across scalar-vector products. svp_apply_dft also accepts VecZnx directly; the graph makes the transform stage explicit.

Prepare MatZnx once, then reuse VmpPMat across vector-matrix products. vmp_apply_dft also accepts VecZnx directly; the graph makes the transform stage explicit.

Arrows describe data flow into output buffers, not ownership moves. Prepared operands remain reusable; IDFT variants may use the transform input as scratch.

03 / VMP in practice

Homomorphic key switching

Key switching is a VMP followed by body addition and normalization. Multiply the mask by the key-switching matrix, then add the original body. The message stays the same; the secret changes from s0 to s1.

K = base2k bits per signed limb · three mask limbs · three key rows · five limbs per column, including error padding.

Using VMP to implement homomorphic key switchingThe mask decomposes as a equals the sum of a i times g i. VMP produces the DFT of the pair minus c times s one plus a times s zero plus the key-switching error, c, where c is the sum of a i times b i. This pair encrypts a times s zero under s one. IDFT preserves that encrypted value. Adding b equals minus a times s zero plus m plus e cancels the old-secret terms, leaving minus c times s one plus m plus the combined error. Normalization propagates carries in base two to the K, recovering K-bit signed digits. After normalization the new mask is a prime, not the original a, and the body is minus a prime times s one plus m plus e prime. The input GLWE has three limbs in its body and mask. The message is in the second limb and the error in the third. The key-switching GGLWE is a MatZnx with three rows, one per input mask limb, and five limbs per body and mask column. Blue marks the input mask, its DFT, and its scalar limbs. Teal marks the matrix masks and carries through the product to the output mask. Green marks the original message. Small orange diagonal bars are labeled s zero: placing s zero in limb i implicitly supplies the gadget weight g i. The logical SVP diagonal is labeled a i times s zero in the same limb, and each row’s error is labeled a i times e i. After scaling by a uniform mask limb, full-range contributions use the body’s uniform fill. Lavender marks the key body. Yellow marks the input body and the logical a i times s zero diagonal, then continues across the product, addition, and normalized output. The product and IDFT vectors label their first three limbs a one times s zero, a two times s zero, and a three times s zero. Only message and error bars overlay the body fill; their size encodes magnitude. Adding the original body cancels the old-secret contribution, leaving the same yellow body fill with the green message and red error. Red markers occupy the extra fifth limb for error. DFT transforms the mask to VecZnxDft and matrix preparation transforms the key to VmpPMat. Short bars indicate small norms and full-height bars indicate the full limb range. Each uniform mask limb acts as a ScalarZnx and scales its corresponding key row as a scalar-vector product, increasing both payload and error norms. VMP sums these three scaled rows into a pair in VecZnxDft. IDFT writes VecZnxBig, then the original body is added to the product body. Normalize both columns to obtain a VecZnx ciphertext under the new secret. Colors in transformed states indicate logical contributions, not physical memory locations.Input GLWE · VecZnxStandardized coefficient layoutb = −as₀ + m + ea · random mask1b₁1a₁2b₂2a₂3b₃3a₃m: limb 2e: limb 3DFTVecZnxDftâ₁â₂â₃Transformed maskOriginal body b = −as₀ + m + eKey-switching GGLWE · MatZnx3 rows × 2 columns × 5 limbsKᵢ = (−bᵢs₁ + gᵢs₀ + eᵢ, bᵢ)1122334455K₁s₀e₁K₂s₀e₂K₃s₀e₃VmpPMatPrepared keyReusable backend layout1122334455K₁s₀e₁K₂s₀e₂K₃s₀e₃Prepare matrix · DFTBodyMask bᵢOne rowper limbVMP = Σ SVPVector × matrixScalarZnxSVP results · aᵢKᵢLogical viewa₁→a₁·s₀a₁·e₁a₂→a₂·s₀a₂·e₂a₃→a₃·s₀a₃·e₃SUM · Σᵢ aᵢKᵢAccumulate all three rowsVMP / Encrypts a·s₀ under s₁DFT(−c·s₁ + a·s₀ + εₖₛ, c)c = Σᵢ aᵢbᵢεₖₛ = Σᵢ aᵢeᵢIDFT / Same encrypted value(−c·s₁ + a·s₀ + εₖₛ, c)Now in wide coefficient limbs, before normalization.ADD / Cancel the old-secret term(−a·s₀ + m + e)+ (−c·s₁ + a·s₀ + εₖₛ)= −c·s₁ + m + (e + εₖₛ)With mask c, the result now encrypts m under s₁.OUTPUT / Encrypts m under s₁a′ = Normalize(c)b′ = −a′·s₁ + m + e′e′ includes e + εₖₛ and any rounding.Carry into adjacent limbs to recover K-bit signed digits.VecZnxDfta₁·s₀a₂·s₀a₃·s₀VecZnxBiga₁·s₀a₂·s₀a₃·s₀VecZnxBigIDFTADDMask cNORMALIZE · 2ᴷNORMALIZE · 2ᴷVecZnxb′ + a′s₁ = m + e′Same message · new secret · updated error

Limb weights. The mask decomposes as a = Σᵢ aᵢgᵢ, with gᵢ = 2−Ki and K = base2k bits per limb. Each key row encrypts gᵢs0 under s1, so their weighted sum encrypts as0. Placing s0 in limb i supplies this weight implicitly.

Coefficient magnitude. Bar heights show relative norms. Multiplication by a uniform mask limb scales both payload and error. Transformed states show these logical contributions; heights are schematic, not measured bounds.

Explore the layered architecture and reference contracts →