Constraints on q for q-ary lattices?

Karim

1/5/23, 1:21 PM

In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we want $q$ to be prime or a prime power. However there wasn't any explanation to why that is the case. So I have a couple of questions about the choice of $q$:

Is there any issues with taking q to be any positive integer? Or are there any values that have shown to be problematic?
What's the advantage of choosing it to be prime or a prime power? And are there any primes that are better suited?

2 + 0

prime-numbers

lattice-crypto

safe-prime

Score:2

Crypto

Hilder Vitor Lima Pereira

1/5/23, 7:36 PM

Not a complete answer, but may already be useful...

It is known that only the bit length but not the form of $q$ is important for the security of the LWE (and the RLWE) problem.

Moreover, if we can solve $SIS_{n, q, \beta}$ with $\beta = O(q / \sigma)$, then we can solve $LWE_{n, q, \sigma}$ (see Corollary 2 of [MPS15]).

Thus, at least for such small bound $\beta$ on the norm of the SIS solutions, the form of $q$ should not matter.

0 + 0

Score:1

Crypto

Mark

1/5/23, 10:31 PM

As Hilder mentions, via the technique of "modulus switching" the particular choice of $q$ does not matter much for the security of LWE. Therefore, the particular form of $q$ is mostly to enable efficiency improvements. I'm the wrong person to exhaustively list all of them, but one can easily point to a few by reading the NIST PQC KEM proposals.

For example:

Choosing $q = 2^k$ for some $k$ allows one to replace modular reductions by $q$ with bit shifts, a cheaper operation. This is part of the reason that Saber chooses $q = 2^{13}$.
Choosing $q$ to be "NTT Friendly". The NTT is a certain analogue of the FFT "mod $q$" (rather than over $\mathbb{C}$) that can enable large speedups in polynomial multiplications (roughly from $O(n^2)$ naive complexity to $O(n\log n)$). The size of the speedup is directly linked to having a suitable analogue of $i\in\mathbb{C}$. The best case (say when working over $\mathbb{Z}_q[x]/(x^n+1)$ for $n = 2^k$) happens when you have a "primitive $2n$th root of unity", which happens when $q\equiv 1\bmod 2n$ (I think). Note that this is not compatible with the prior optimization. The KEM Kyber makes this choice (almost, there are small technical differences).
Choosing $q$ to be a product of small (word-size) coprimes, so one can appeal to the Chinese Remainder theorem, and keep all arithmetic word-size. I don't know of a KEM that does this, but this is popular in the FHE literature (and often goes by the name "Residue Number System", or RNS arithmetic).

So there are arguments for choosing $q \equiv 0 \bmod 2^k$, $q\equiv 1\bmod 2\times 2^k$, and $q$ a product of small coprimes. These may all seem to be mutually exclusive optimizations, but one can be somewhat clever and use multiple optimizations at once. For example, there is this work on embedding arithmetic mod $2^k$ (i.e. "modular reduction friendly") into an NTT friendly ring, letting one use both optimizations 1 and 2.

0 + 1

Hilder Vitor Lima Pereira

1/6/23, 7:28 AM

For the LWE, the form of $q$ is irrelevant, and I would guess that this is also the case for SIS, as these two problems are closely related. However, as I wrote in my answer, using the LWE to SIS reduction just gives us a definitive answer for a set of the SIS instances, not for the SIS in general. But, for example, how can we prove that SIS with $\beta=n^4=\omega(q)$ is secure regardless the form of q?