Paper 2017/523

Partially Splitting Rings for Faster Lattice-Based Zero-Knowledge Proofs

Vadim Lyubashevsky and Gregor Seiler

Abstract

When constructing zero-knowledge proofs based on the hardness of the Ring-LWE or the Ring-SIS problems over the ring $R_p^n=\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 exponentially 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 speed of the multiplication operation in $R_p^n$ 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. For the most common parameters that are used in such zero-knowledge proofs, we show that $X^n+1$ can split into $8$ or $16$ irreducible factors. Experimentally, having the rings split in this fashion, increases the speed of polynomial multiplication by around $30\%$. This is a modest improvement, but it comes completely for free simply by working over the ring $R^n_p$ with a different modulus $p$. In addition to the speed improvement, the splitting of the ring into more factors is useful in scenarios where one embeds information into the Chinese Remainder representation of the ring elements.