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

## Vadim Lyubashevsky and Gregor Seiler

```
```When constructing zero-knowledge proofs based on the hardness of the Ring-LWE or the
Ring-SIS problems over the ring R p n = Z p [X]/(X n + 1), it is often necessary that the challenges come
from a set 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 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 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 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 30is a modest improvement, but it comes completely for free simply by working over the ring R p n 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.