Search papers, labs, and topics across Lattice.
This paper analyzes the density $c(p)$ of matrices over a prime field $\mathbb{F}_p$ with primitive-root determinant, a crucial parameter in the security of the PRIM-LWE cryptosystem. It resolves a conjecture regarding the asymptotic behavior of $c(p)$ by establishing the sharp order $\min_{p\le x}c(p)\asymp 1/\log\log x$ and showing that $c(p)$ has a continuous purely singular limiting distribution. Furthermore, the paper derives explicit lower bounds on $c(q)$ for primes $q$ of cryptographic interest, demonstrating that the dimension-uniform expected rejection-sampling overhead $1/c(q)$ is small for NIST-standardized moduli.
Forget primorial primes: the density of matrices with primitive-root determinants over prime fields decays surprisingly slowly, scaling as $1/\log\log x$, with implications for PRIM-LWE security.
The \textsc{prim-lwe} problem (Sehrawat, Yeo, and Desmedt, \emph{Theoret.\ Comput.\ Sci.}\ 886, 2021) is a variant of Learning with Errors requiring the secret matrix to have a primitive-root determinant. The dimension-uniform reduction constant is $c(p)=\inf_{m\ge 1}c_m(p)$, where $c_n(p)$ is the density of $n\times n$ matrices over~$\mathbb{F}_p$ with primitive-root determinant. Those authors asked whether $\inf_{p\text{ prime}}c(p)=0$, noting that an affirmative answer would follow from the conjectural infinitude of primorial primes. We resolve this unconditionally using only Dirichlet's theorem and Mertens'product formula, bypassing the primorial-prime hypothesis entirely. We establish the sharp order $\min_{p\le x}c(p)\asymp 1/\log\log x$, prove that $c(p)$ possesses a continuous purely singular limiting distribution over the primes with support exactly $[0,1/2]$, and derive explicit lower bounds on $c(q)$ for primes of cryptographic interest parameterized solely by~$\omega(q{-}1)$, the number of distinct prime factors of~$q{-}1$. These bounds apply to every prime~$q$ whose predecessor has controlled factorization structure, as measured by~$\omega(q{-}1)$; this includes many NTT-friendly moduli, though NTT-friendliness alone does not imply the needed bound. For the NIST-standardized moduli $q=3329$ (ML-KEM) and $q=8380417$ (ML-DSA), the dimension-uniform expected rejection-sampling overhead~$1/c(q)$ is at most $2.17$ and $3.42$, respectively. As a simple conservative bound, for any prime $q>2^{30}$ one has $1/c(q)\le 1.79\log q$. The worst-case overhead among primes $p\le x$ is $\Theta(\log\log x)$, and pointwise $1/c(q)=O(\log\log q)$.
