Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs
verfasst von : Vadim Lyubashevsky, Gregor Seiler
Erschienen in: Advances in Cryptology – EUROCRYPT 2018
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
When constructing practical zero-knowledge proofs based on the hardness of the Ring-LWE or the Ring-SIS problems over polynomial rings \(\mathbb {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 non-zero 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 sub-optimal; 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 non-zero polynomials with “small” coefficients in the cyclotomic ring \(\mathbb {Z}_p[X]/(\varPhi _m(X))\) are invertible (where “small” depends on the size of p and how many irreducible factors the \(m^{th}\) cyclotomic polynomial \(\varPhi _m(X)\) splits into). We furthermore establish sufficient conditions for p under which \(\varPhi _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.