Witness Encryption via Prime-Order Generic Groups

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 Ω(1). If no satisfying assignment exists, then every generic adversary making at most n Θ(n) group queries has distinguishing advantage at most n-Θ(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.