When constructing practical zero-knowledge proofs based on the hardness of the Ring-LWE or the Ring-SIS problems over polynomial rings Z_p[X]/(X~n +1), it is often necessary that the challenges corne from a set 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 C - 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 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 Z_p[X]/(Φ_(rn)(X)) are invertible (where "small" depends on the size of p and how many irreducible factors the m~(th) cyclotomic polynomial Φ_m(X) splits into). We furthermore establish sufficient conditions for p under which Φ_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 Karat-suba multiplication. Experimentally, we show that increasing the number of levels from one to three or four results in a speedup by a factor of ≈ 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.
展开▼
