New answers tagged

1

Why use $f(x) = x^{2^n} + 1$? This is a very special polynomial called a "cyclotomic" polynomial. Cyclotomic polynomials are very interesting, and I recommend reading up on them separately (wikipedia). One very useful property is that the $m^{th}$ cyclotomic polynomial has roots that are all the $m^{th}$ primitive roots of unity. For any $n \geq 1$, the ...


2

As hinted by @kelalaka in the comments, note that $q$ is odd, and $\gcd(2,q)=1.$ Therefore within $Z_q$ we have that $2e\neq 0,$ if and only if $e \neq 0,$ so the noise is never masked.


1

As is mentioned in the comments above, there are many uses for the smoothing parameter. Here is one that provides some intuition of why it's useful. For a basis $B$ of a full-rank $n$ dimensional lattice, let $P(B)$ be a parallelepiped of the lattice $\Lambda = L(B)$. Consider the operation of taking a point $x \in \mathbb{R}^n$ mod $P(B)$, which is to ...


1

You misunderstand what "decode" does. As mentioned earlier in the paper: The system has message space $\{0,1\}^{nk}$, which we map bijectively to the cosets of $\Lambda/2\Lambda$ for $\Lambda = \Lambda(G^t)$ via some function encode that is efficient to evaluate and invert. Concretely, letting $S \in\mathbb{Z}^{nk×nk}$ be any basis of $\Lambda$, we can map ...


2

Yes. You can see Micciancio's annotated bibliography for some relevant papers (including generic transformations from CPA security to CCA security in the random oracle model). If you want to see "actual" schemes which are CCA1 secure, Kyber is a CCA2-secure KEM with security based on a variant of LWE over "Module Lattices", which can be viewed as a slight ...


Top 50 recent answers are included