Witness Encryption via Prime-Order Generic Groups
Unconditional witness encryption construction for NP in the generic-group model, plus first superconstant NP-hardness result for homogeneous MinRank.
A cryptography paper unconditionally constructs witness encryption for NP in the classical generic-group model using an ordinary cyclic group of prime order. For SAT instances of size n, encryption and decryption run in poly(n) time with correctness error 2^-n^Ω(1), while generic adversaries making n^Θ(log n) queries achieve at most n^-Θ(log n) distinguishing advantage. It also proves the first superconstant-factor NP-hardness of approximation for homogeneous MinRank under randomized reductions.
- Encryption from a plain prime-order cyclic group
- Satisfying assignments decrypt in polynomial time
- First superconstant-factor inapproximability result for homogeneous MinRank
Full article105 words · extracted from arxiv.org · click to collapse
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^{Θ(\log n)}$ group queries has distinguishing advantage at most $n^{-Θ(\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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.18275