In the algorithm FHE.KeyGen on page 18 of BGV, the dimension of the secret key $\textbf{s}_j$ is $n_j+1$. Why would the dimension of the long secret key $\textbf{s}_j' \leftarrow \textbf{s}_j \otimes \textbf{s}_j$ be $\binom{n_j+1}{2}?$ Wouldn't it be $(n_j+1)^2?$
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Maybe it is because the ring is commutative, so the products $s_j[\ell]s_j[k]$ and $s_j[k]s_j[\ell]$ are equal, and therefore, it is not necessary to store all the $(n_j + 1)^2$ elements.
But even so, in this case, it would be needed to store $\frac{(n_j + 2)(n_j + 1)}{2}$ elements, which is equal to $\binom{n_j+2}{2}$ instead of $\binom{n_j+1}{2}$...
answered Aug 28, 2016 at 18:07
-
$\begingroup$ I see, so storing is an issue here. In that case, I think you are right. Would the first component of $\textbf{s}_j$ being a 1 affect the answer somehow? $\endgroup$– sycsAug 29, 2016 at 1:11
-
$\begingroup$ Okay so I think because the first component of $\textbf{s}_j$ is a 1 then we get a copy of $\textbf{s}_j$ in $\textbf{s}_j'$. If we only need to store the other coefficients then it is $\binom{n_j+1}{2}.$ $\endgroup$– sycsAug 29, 2016 at 1:26