3
$\begingroup$

LWE instances have the form $\vec{a}_i,b_i = \langle\vec{a}_i,\vec{s}\rangle+e_i\bmod q$ for some integer $q$ and for $i=1,\dots,m$.

My questions are about the NIST proposed standards. In the standards

  1. Do we allow $q=2^t$ (if not why not?)? and what is relation between $q$ and $n$ where $n$ is length of $\vec{a}_i$?

  2. How large can $m$ be?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

If you are referring to the recent published FIPS 203 and FIPS 204 standards which specify ML-KEM and ML-DSA respectively (both are Module Learning with Error primitives, which are a particular variety of LWE system), then the options are very limited.

  1. No, $q=2^t$ is not a permitted parameterisation. In fact for ML-KEM the only permissible value is $q=3329$ and for ML-DSA the only permissible value is $q=8380417$. As such, there is no one-to-one relationship between $q$ and $n$. For ML-KEM $n$ can take the values 512, 768, and 1024 (note that ML-KEM uses the notation $n$ for the polynomial degree of ring elements for whereas the $n$ in Lee definitions more closely corresponds to $kn$ in the ML-KEM spefication). Likewise, in ML-DSA the permitted values of $n$ are 512, 640, and 896.

  2. The permissible values for $m$ in ML-KEM are 512, 768, and 1024. The permissible values for $m$ in ML-DSA are 512, 768, and 1024. The permissible values correspond directly to the listed permissible values of $n$.

Note that in ML-KEM and ML-DSA, the $a_i$ are of a very structured form and that $s_i$ are drawn from an error distribution similar to the $e_i$. The exact specification of parameters is given in table 2 of FIPS 203 and table 1 of FIPS 204.

To address the question of why users do not have greater freedom to choose their own parameters, I'll note that the practical difficulty of LWE problems (or more generally lattice problems) is very complex to estimate. Parameterisations rely on automatic tooling to provide estimates against a wide range of attacks. These tools and estimates tend to require expert shepherding and would be an unnecessary strain and risk for users wanting to generate their own parameters. It's not an unheard of approach: certain fixed large primes and generators are often standardised in multiplicative Diffie-Hellman to avoid issues with users generating their own primes. Likewise, standard elliptic curves such as NIST P256 or Curve25519 are preferred to users working out the arcana of how to generate a safe elliptic curve.

$\endgroup$
4
  • $\begingroup$ Do you know why $q=2^t$ is not allowed? Any specific attacks or weakness? An unrelated question.. why are recommended $q$ values primes? $\endgroup$
    – Turbo
    Commented Sep 7 at 18:09
  • 4
    $\begingroup$ @Turbo there are no specific weaknesses with $q = 2^t$. It is well-known that due to "modulus switching" arguments that the only thing that really matters for security of (R)LWE-based schemes is the size $\log q$. Saber used $q = 2^t$ iirc. But such choice of $q$ is incompatible with certain algorithmic optimizations that Kyber (now ML-KEM) chose, namely their choice of polynomial multiplication, which requires a "NTT-friendly Prime", namely $q\equiv 1\bmod 2n$ for polynomial degree $n$. Technically $q$ could be a product of such primes, but this isn't really relevant for PKE. $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 7 at 18:23
  • $\begingroup$ @MarkSchultz-Wu Thank you. What is "modulus switching" argument? $\endgroup$
    – Turbo
    Commented Sep 7 at 18:26
  • 3
    $\begingroup$ Essentially that you can take a $\bmod p$ ciphertext $[a,b]$, and produce a $\bmod q$ ciphertext $[\lfloor (q/p)a\rceil, \lfloor (q/p)b\rceil]$ while only inflating the noise by a factor $\approx q/p$. So for $\log q\approx \log p$, there is essentially no impact. It was introduced in this paper, but I'm sure you can find more modern expositions of the idea (it shows up all the time in the FHE literature). $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 7 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.