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
From the original article
1 min read at arxiv.orgWe 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)}}$.
By Isaac M Hair · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.