Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

1. Problem Statement

The paper addresses a fundamental question regarding the PRIM-LWE (Learning with Errors with Primitive-root determinant) problem, introduced by Sehrawat, Yeo, and Desmedt.

• Context: PRIM-LWE is a variant of the standard LWE problem where the secret matrix $S$ is constrained to have a determinant that is a primitive root modulo the prime field $p$ (i.e., $\det(S)$ generates the multiplicative group $\mathbb{F}_p^*$).
• The Core Question: The security reduction from standard Decision-LWE to Decision-PRIM-LWE relies on the ability to sample secret matrices with primitive-root determinants. The efficiency of this reduction is governed by the dimension-uniform constant $c(p)$, defined as the limiting density of $n \times n$ matrices over $\mathbb{F}_p$ with primitive-root determinants as $n \to \infty$:
  $$c(p) = \frac{\phi(p-1)}{p-1} \prod_{j=1}^{\infty} \left(1 - \frac{1}{p^j}\right)$$
• The Open Problem: Sehrawat et al. previously observed that if there are infinitely many primorial primes (primes of the form $N_k + 1$ where $N_k$ is the product of the first $k$ primes), then $\inf_p c(p) = 0$. They asked whether this infimum is zero unconditionally (without assuming the unproven infinitude of primorial primes).
• Implication: If $\inf_p c(p) = 0$, the rejection-sampling overhead ($1/c(p)$) in the reduction could theoretically become arbitrarily large for certain primes, potentially weakening the practical security guarantees of PRIM-LWE for specific modulus choices.

2. Methodology

The author resolves the problem using classical analytic number theory, avoiding unproven conjectures. The methodology relies on:

• Dirichlet's Theorem on Primes in Arithmetic Progressions: To guarantee the existence of primes $p \equiv 1 \pmod{N_k}$ for any $k$.
• Mertens' Third Theorem: To estimate the asymptotic behavior of the product $\prod (1 - 1/p_i)$.
• Linnik's Theorem: To bound the size of the least prime in an arithmetic progression, establishing the quantitative rate of decay.
• Erdős–Wintner Theory: To analyze the limiting distribution of additive functions evaluated at shifted primes ($p-1$).
• Transport Lemmas: To transfer distributional results from the totient ratio $\phi(p-1)/(p-1)$ to the full density $c(p)$.

3. Key Contributions and Results

A. Unconditional Vanishing of the Infimum

The paper proves unconditionally that $\inf_{p \text{ prime}} c(p) = 0$.

• Mechanism: For any $k$, Dirichlet's theorem ensures infinitely many primes $p \equiv 1 \pmod{N_k}$. For such primes, $N_k \mid (p-1)$. Consequently, the ratio $\frac{\phi(p-1)}{p-1}$ is bounded above by $\prod_{i=1}^k (1 - 1/p_i)$. By Mertens' theorem, this product tends to 0 as $k \to \infty$.
• Significance: This resolves the open question without needing the conjecture that primorial primes are infinite. It confirms that the reduction constant can be arbitrarily small for specific sequences of primes.

B. Sharp Asymptotic Order

The paper establishes the precise rate at which the minimum density decays:
$$\min_{p \le x} c(p) \asymp \frac{1}{\log \log x}$$

• Upper Bound: Derived using Linnik's theorem to find the smallest prime $p \equiv 1 \pmod{N_k}$ below $x$.
• Lower Bound: Derived by showing that for any $p \le x$, the number of distinct prime factors $\omega(p-1)$ is bounded, preventing the density from decaying faster than $1/\log \log x$.
• Implication: The decay is extremely slow. For cryptographic security parameters (e.g., $2^{128}$ or $2^{4096}$), $\log \log x$ is small (approx. 4.5 to 7.95), meaning the density remains practically significant.

C. Limiting Distribution

The paper characterizes the statistical behavior of $c(p)$ over the set of all primes:

• Distribution: $c(p)$ possesses a continuous, purely singular limiting distribution $G$ over the primes.
• Support: The support of this distribution is exactly the interval $[0, 1/2]$.
• Properties: The distribution function $G$ is strictly increasing on $[0, 1/2]$. This implies that for any threshold $\tau \in (0, 1/2)$, the set of primes with $c(p) \le \tau$ has a positive relative density $G(\tau)$.
• Connection: The distribution of $c(p)$ is identical to that of the totient ratio $\phi(p-1)/(p-1)$, as the infinite product term $\prod (1 - p^{-j})$ converges to 1 rapidly.

D. Explicit Bounds for Cryptographic Moduli

The paper provides concrete lower bounds for $c(q)$ based on the factorization structure of $q-1$, specifically the number of distinct prime factors $\omega(q-1)$.

• General Bound: $c(q) \ge P_3 \prod_{i=1}^{\omega(q-1)} (1 - 1/p_i)$, where $P_3 \approx 0.56$.
• NIST Standards:
  • ML-KEM ($q=3329$): $\omega(q-1)=2$. The overhead $1/c(q) \le 2.17$.
  • ML-DSA ($q=8380417$): $\omega(q-1)=4$. The overhead $1/c(q) \le 3.42$.
• NTT-Friendly Primes: The paper clarifies that "NTT-friendliness" (usually $q \equiv 1 \pmod{2^t}$) alone does not guarantee a good bound, as it only controls the 2-adic part of $q-1$. However, most practical NTT primes also have few small odd prime factors, leading to small $\omega(q-1)$ and thus small rejection-sampling overheads.
• Universal Bound: For any prime $q > 2^{30}$, $1/c(q) \le 1.79 \log q$.

4. Significance and Implications

1. Resolution of Theoretical Uncertainty: The paper definitively answers that the reduction constant $c(p)$ can approach zero, but does so very slowly ($\Theta(1/\log \log p)$). This rules out the possibility of a uniform lower bound across all primes but confirms that the "worst-case" primes are rare and decay slowly.
2. Practical Security of PRIM-LWE: The results validate the practical use of PRIM-LWE with standard cryptographic moduli. The rejection-sampling overhead for NIST-standardized primes is small (factors of 2.17 and 3.42), meaning the security reduction remains tight and efficient.
3. Guidance for Modulus Selection: The paper quantifies the trade-off in modulus selection. To ensure a small overhead, one must choose primes $q$ where $q-1$ has a controlled factorization structure (specifically, a small number of distinct prime factors $\omega(q-1)$).
4. Mathematical Insight: It establishes a deep connection between the PRIM-LWE density and classical number-theoretic distributions (Erdős–Wintner), proving that the density follows a continuous singular law with full support on $[0, 1/2]$.

In conclusion, while the theoretical infimum of the density is zero, the paper demonstrates that for all practical cryptographic purposes, the density is bounded away from zero by a small constant factor, ensuring that the PRIM-LWE problem remains a viable and secure variant of LWE.