Paper 2017/523
Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to LatticeBased ZeroKnowledge Proofs
Vadim Lyubashevsky and Gregor Seiler
Abstract
When constructing practical zeroknowledge proofs based on the hardness of the RingLWE or the RingSIS problems over polynomial rings $Z_p[X]/(X^n+1)$, it is often necessary that the challenges come from a set $\mathcal{C}$ that satisfies three properties: the set should be large (around $2^{256}$), the elements in it should have small norms, and all the nonzero elements in the difference set $\mathcal{C}\mathcal{C}$ should be invertible. The first two properties are straightforward to satisfy, while the third one requires us to make efficiency compromises. We can either work over rings where the polynomial $X^n+1$ only splits into two irreducible factors modulo $p$, which makes the speed of the multiplication operation in the ring suboptimal; or we can limit our challenge set to polynomials of smaller degree, which requires them to have (much) larger norms. In this work we show that one can use the optimal challenge sets $\mathcal{C}$ and still have the polynomial $X^n+1$ split into more than two factors. This comes as a direct application of our more general result that states that all nonzero polynomials with ``small'' coefficients in the cyclotomic ring $Z_p[X]/(\Phi_m(X))$ are invertible (where ``small'' depends on the size of $p$ and how many irreducible factors the $m^{th}$ cyclotomic polynomial $\Phi_m(X)$ splits into). We furthermore establish sufficient conditions for $p$ under which $\Phi_m(X)$ will split in such fashion. For the purposes of implementation, if the polynomial $X^n+1$ splits into $k$ factors, we can run FFT for $\log{k}$ levels until switching to Karatsuba multiplication. Experimentally, we show that increasing the number of levels from one to three or four results in a speedup by a factor of $\approx 2$  $3$. We point out that this improvement comes completely for free simply by choosing a modulus $p$ that has certain algebraic properties. In addition to the speed improvement, having the polynomial split into many factors has other applications  e.g. when one embeds information into the Chinese Remainder representation of the ring elements, the more the polynomial splits, the more information one can embed into an element.
Note: A generalization of Lemma 3.1 is explicitly proven.
Metadata
 Available format(s)
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2018
 Keywords
 lattice cryptographynumber theoryimplementationzeroknowledge proofs
 Contact author(s)
 vadim lyubash @ gmail com
 History
 20180216: last of 5 revisions
 20170605: received
 See all versions
 Short URL
 https://ia.cr/2017/523
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/523, author = {Vadim Lyubashevsky and Gregor Seiler}, title = {Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to LatticeBased ZeroKnowledge Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2017/523}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/523}}, url = {https://eprint.iacr.org/2017/523} }