[2609.18275] Witness Encryption via Prime-Order Generic Groups
Abstract:We unconditionally construct witness encryption for NP in the classical generic-group model, using an ordinary cyclic group of prime order. For SAT instances of size $n$, the encryption algorithm runs in time poly$(n)$, and any satisfying assignment can be used to decrypt in poly$(n)$ time with correctness error $2^{-n^{\Omega(1)}}$. If no satisfying assignment exists, then every generic adversary making at most $n^{\Theta(\log n)}$ group queries has distinguishing advantage at most $n^{-\Theta(\log n)}$. Along the way, we prove the first superconstant-factor NP-hardness of approximation result for homogeneous MinRank under randomized polynomial-time reductions, achieving a logarithmic gap even when the rank-one witness has a Boolean right factor.