# Dimension of secret key vector tensor with itself?

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?$

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}$...
• 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? – sycs Aug 29 '16 at 1:11
• 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}.$ – sycs Aug 29 '16 at 1:26