Do the specific powers of two $2^{23}$ and $2^{13}$ in the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$ have any special purpose in its design?

Question

I recently started exploring Post-Quantum Cryptography, particularly Lattice-based Cryptography, and came across the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$, which is used in schemes like Dilithium. Can it be any other large number or other number would affect the security?

I noticed that $q$ has a very specific structure involving powers of two $2^{23}$ and $2^{13}$. Do these powers of two have any special purpose or significance in the design of $q$? For instance, does it contribute to computational efficiency or facilitate certain mathematical properties needed for lattice-based schemes?

Any insights or explanations would be greatly appreciated!

Answer 1

Here's a few important factors for choosing the modulus:

1. SIS gets easy if the modulus is too big or too small. If it's too big, the corresponding lattice problems get easier. If it's too small, guesses will be easy (trivial case: if you want to solve $Ax\equiv 0\bmod q$ for $\Vert x\Vert\leq\beta$ and $n$-dimensional $x$, of $\frac{q}{2}\sqrt{n}\geq \beta$, you can basically take any element in the kernel of $A$ and it works). Dilithium signatures mask the secret with a larger value $y$. If $y$ is too small, you spend too much time rejection sampling, so $y$ is chosen to be fairly large, but this means the effective value of $\beta$ (for which the scheme reduces to SIS-$\beta$) is also "fairly" large (the bounds are about $2^{19}$ in each coordinate for larger parameter sets), so that gives us a minimum for $q$ already: $q\geq 2^{20}$.
2. Everything is more efficient with a smaller modulus.
3. In Ring-LWE and Module-LWE, ring multiplications can be made much more efficient using the fast Fourier transform, if the polynomial $X^N+1$ splits in that modulus. Since $N=256$ for Dilithium, we want a prime modulus equal to $q=512k+1$ for some $k$ (this means $q-1=512k$, so there is an element of multiplicative order $512$).
4. "Sparse" moduli generally make modular arithmetic easier (where sparse means having few 1s in a binary representation). For example, to multiply $x$ by $q$, you just need to bit-shift $x$ by 23 bits, then 13 bits, subtract the second result from the first, then add 1.
5. Modular reduction is done with Montgomery arithmetic, so Dilithium will frequently multiply by $2^{32}\bmod q$ and $q^{-1}\bmod 2^{32}$. You especially want both of these multiplications to always fit in a 64-bit register (so $q$ should be at most $2^{32}$), and when I check the Dilithium reference implementation, the binary representations of those Montgomery constants are 01111111110001000000001 and 11100000000010000000000001, respectively. I'm not sure if $q$ was chosen to make these sparse as well? You can show with a bit of work that any number of the form $2^x-2^y+1$ will have a relatively sparse inverse modulo $2^z$ if $x > y$ and $x+y \geq z$ (the inverse is $\sum_{r=x}^{2y-1}2^r + 2^y +1$), so maybe that's why.

Writing a short SAGE script, 8380417 is the smallest prime $q$ satisfying:

1. $2^{32} \geq q \geq 2^{20}$
2. $512$ divides $q-1$
3. $q$ has a "sparse" binary representation: $q=2^x-2^y+1$ such that $x+y\geq 32$.