vec znx api

Spqlios VEC_ZNX-arithmetic library

The spqlios arithmetic library provides fast arithmetic over vectors of small integer polynomials. In particular, it provides fast (prepared) vector-matrix and vector-convolution powered by DFT (either FFT or NTT).

Summary of main modules

int64 representation of $\mathbb{Z}_N[X]$ of small norm

Definition of the layout

A single small polynomial $\in \mathbb{Z}_N[X]$ is represented by its $N$ integer coefficients in natural order, forming an int64_t[N] contiguous array.

A vector of $\ell$ small polynomials (i.e. $\mathbb{Z}_N[X]^\ell$) is represented by $\ell$ arrays regularly spaced in memory.

Concretely, given the ring dimension uint64_t N, a vector of polynomial is represented by one pointer int64_t* p, the size of the vector ell, and a stride/slice size slice >= N. The $j$-th coefficient of the $i$-th polynomial is at address &p[i*slice+j] (C notation): For $i\in[0,\ell-1]$ and $j\in[0,N-1]$, the int64_t element at this address shall be properly allocated and accessible.

Allocation/deallocation

The int64_t* pointer can be allocated and freed using standard allocators (malloc, new int64_t[], ...), using the default endianess of the machine (usually little-endian on most cpus). The structure can be allocated, filled, and read externally to the library. If the layout is not contiguous (slice is $>N$), the functions of the library will never dereference addresses in the inter-slice space.

Alignment: An alignment of 64-bytes is recommended for speed reasons, but not mandatory. Serialization/IO: fread and fwrite-based are fine. Some care may be needed to make the endianess canonical (TBD)

Elementary operations

/** @brief sets res = 0 */
void vec_znx_zero(const MODULE*,                  // N
                  int64_t* res, res_size, res_sl  // res
);
/** @brief sets res = a */
void vec_znx_copy(const MODULE*,                   // N
                  int64_t* res, res_size, res_sl,  // res
                  const int64_t* a, a_size, a_sl   // a
);
/** @brief sets res = a + b */
void vec_znx_add(const MODULE*,                    // N
                 int64_t* res, res_size, res_sl,   // res
                 const int64_t* a, a_size, a_sl,   // a
                 const int64_t* b, b_size, b_sl    // b
);
/** @brief sets res = a + b */
void vec_znx_sub(const MODULE*,                    // N
                 int64_t* res, res_size, res_sl,   // res
                 const int64_t* a, a_size, a_sl,   // a
                 const int64_t* b, b_size, b_sl    // b
);
/** @brief sets res = k-normalize-reduce(a) */
void vec_znx_normalize(MODULE*,                          // N
                       uint64_t base_2k,                 // output base 2^K
                       int64_t* res, res_size, res_sl,   // res
                       const int64_t* a, a_size, a_sl    // a
);

Vector-matrix products (vmp)

1. Allocate the space for a pmat matrix to the right dimension

   /** @brief allocates space a prepared matrix (release with delete_vmp_pmat) */
   VMP_PMAT* pmat = new_vmp_pmat(MODULE*, nrows, ncols);
   /** @brief allocates space for the resulting dft vector (release with delete_vec_znx_dft) */
   VEC_ZNX_DFT* vdft = new_vec_znx_dft(MODULE*, size);
   /** @brief allocates space for the resulting big coeff vector (release with delete_vec_znx_big) */
   VEC_ZNX_BIG* vbig = new_vec_znx_big(MODULE*, size);
   
   // it also is possible to use a standard allocation functions: 
   // malloc/free, new int8_t[...]/delete[],
   // or spqlios_alloc/spqlios_free
   // in this case, the number of bytes to allocate are: 
   
   /** @brief number of bytes in a VMP_PMAT (for manual allocation) */
   uint64_t bytes_of_vmp_pmat(const MODULE* module,           // N
                              uint64_t nrows, uint64_t ncols); // dimensions
   /** @brief number of bytes in a VEC_ZNX_DFT (for manual allocation) */
   uint64_t bytes_of_vec_znx_dft(MODULE*, size);
   /** @brief number of bytes in a VEC_ZNX_BIG (for manual allocation) */
   uint64_t bytes_of_vec_znx_big(MODULE*, size);

2. Prepare the matrix

   /** @brief prepares a vmp matrix (contiguous row-major version) */
   void vmp_prepare_contiguous(MODULE*,                          // N
                               VMP_PMAT* pmat,                   // output
                               const int64_t* mat, nrows, ncols  // a
   );
   /** @brief prepares a vmp matrix (mat[row*ncols+col] points to the item) */
   void vmp_prepare_dblptr(MODULE*,                              // N
                           VMP_PMAT* pmat,                       // output
                           const int64_t** mat, nrows, ncols     // a
   );

3. Execute a vector matrix product

   /** @brief applies a vmp product res = a x pmat (result in DFT space) */
   void vmp_apply_dft(MODULE*,                            // N
                      VEC_ZNX_DFT* res, res_size,         // res
                      const int64_t* a, a_size, a_sl,     // a
                      const VMP_PMAT* pmat, nrows, ncols  // prep matrix
   );

   It is possible to use dimensions a_size <= nrows and res_size <= ncols. If the dimensions are smaller, this function will do a product with a submatrix.

   The product result is in DFT space, where additional additions/subtractions can be done before coming back to coeffs space.

4. Apply iDFT to return to coeffs space.

   /** @brief applies inverse DFT: res = iDFT(a) (result in BIG space) */
   void vec_znx_apply_idft(MODULE*,                           // N
                           VEC_ZNX_BIG* res, res_size,        // res
                           const VEC_ZNX_DFT* a, a_size       // a
   );

   The output coefficient can have up to 128 bits on some backends: they may not directly fit on int64_t's, hence the ZNX_COEFFS_BIG layout.

   If res_size is different than a_size, the vector is either truncated or extended with zeros.

   when res_size is < a_size, it is possible to have res and a at the same address (aliasing). In this case, the transformation can be in place.

5. Base $2^K$-normalize and reduce back to int64_t

   /** @brief applies inverse DFT: res = iDFT(a) (result in BIG space) */
   void vec_znx_big_normalize(MODULE*,                         // N
                              uint64 base_2k                   // base_2k
                              int64_t* res, res_size, res_sl,  // res
                              const VEC_ZNX_BIG* a, a_size     // a
   );

Scalar-vector products (svp)

TBD

Convolution products (cnv)

TBD

Element-wise products (ewp)

TBD

Additional operations

operations over VEC_ZNX_DFT

A vector of ell polynomial is represented by a private memory layout, contiguous and of number of bytes proportional to N and ell. The size of the layout is publicly known (it depends on the module representation), making it possible to hibernate it.

/** @brief sets res = 0 */
void vec_dft_zero(MODULE*,                     // N
                  VEC_ZNX_DFT* res, res_size   // res
);
/** @brief sets res = a+b */
void vec_dft_add(MODULE* precomp,               // N
                 VEC_ZNX_DFT* res, res_size,    // res
                 const VEC_ZNX_DFT* a, a_size,  // a
                 const VEC_ZNX_DFT* b, b_size   // b
);
/** @brief sets res = a-b */
void vec_dft_sub(MODULE*,                       // N
                 VEC_ZNX_DFT* res, res_size,    // res
                 const VEC_ZNX_DFT* a, a_size,  // a
                 const VEC_ZNX_DFT* b, b_size   // b
);

Operations over VEC_ZNX_BIG

A vector of ell polynomial that come back after an is represented by a private memory layout, contiguous and of number of bytes proportional to N and ell. The size of the layout is publicly known (it depends on the module representation), making it possible to hibernate it.

/** @brief sets res = a+b */
void vec_znx_big_add(MODULE* precomp,               // N
                     VEC_ZNX_BIG* res, res_size,    // res
                     const VEC_ZNX_BIG* a, a_size,  // a
                     const VEC_ZNX_BIG* b, b_size   // b
);
/** @brief sets res = a-b */
void vec_znx_big_sub(MODULE*,                       // N
                     VEC_ZNX_BIG* res, res_size,    // res
                     const VEC_ZNX_BIG* a, a_size,  // a
                     const VEC_ZNX_BIG* b, b_size   // b
);