ngama75
commented
1 month ago Yes, that's correct, the convolution that you describe is planned, but still missing: (the user can specify which subrange of indexes must be outputted out of the 2L-sized convolution): it can be for instance [1..L] for BFV, and something like [L+1..2L] for CKKS.
Let $N$ (variable in $X$) be the vector size and $L$ (variable in $Y$) the number of limbs for the Base2K representation.
I understand the library supports:
svp_apply: scalar vector product, i.e. a Hadamard product between a vector of 1 limb (degree 0 in $Y$) and a vector of $L$ limbs (up to degree $L-1$ in $Y$):$$[a{1}, a{2}, \dots, a{N}] \odot \begin{vmatrix} [b{1, 1}, b{1, 2}, \dots, b{1, N}]\ [b{2, 1}, b{2, 2}, \dots, b{2, N}]\ \vdots\ [b{L, 1}, b{L, 2}, \dots, b{L, N}]\ \end{vmatrix}= \begin{vmatrix} [c{1, 1}, c{1, 2}, \dots, c{1, N}]\ [c{2, 1}, c{2, 2}, \dots, c{2, N}]\ \vdots\ [c{L, 1}, c{L, 2}, \dots, c_{L, N}]\ \end{vmatrix}$$
vmp_apply: vector matrix product, which is from what I understood:$$[\mathbf{a}^{1},\dots,\mathbf{a}^{L}]\cdot \begin{vmatrix} \mathbf{b}^{1, 1}, \cdots, \mathbf{b}^{1, c}\ \vdots\ \mathbf{b}^{r, 1}, \cdots, \mathbf{b}^{r, c}\ \end{vmatrix} =\sum_{i=1}^{\min(r, L)} \texttt{svp}(\mathbf{a}^{i}, [\mathbf{b}^{i, 1}, \dots, \mathbf{b}^{i, c}]) =[\mathbf{a}^{1},\dots,\mathbf{a}^{c}]$$
where $\mathbf{a}^{i}$ and $\mathbf{b}^{i, j}$ are vector of size $N$.
So it seems that the support for product in the variable $Y$ is limited to a polynomial of degree 0 for one of the operands. I've seen some traces of the word
convolutionin the library, but I'm not sure what it relates to.Is support for the full convolution in both the variable $X$ and $Y$ available or planned?:
$$[\mathbf{a}^{1},\dots,\mathbf{a}^{L}]\otimes[\mathbf{b}^{1},\dots,\mathbf{b}^{L}] = [\mathbf{c}^{1},\dots,\mathbf{c}^{2L}] \quad \text{(implicitly truncated to degree $L$)}$$