Witness encryption created using prime order cyclic groups
Witness Encryption via Prime-Order Generic Groups
Cryptography and Security
Summary
Some problems in computer science are easy to check but hard to solve. The paper shows a way to create 'witness encryption,' where you can lock a message using a problem and unlock it only if you have a solution to that problem. This encryption uses special mathematical groups with prime order and guarantees security in a general setting for computers that interact with these groups in any possible way. The authors also prove some new hardness results for a related mathematical puzzle called MinRank, which supports the security of their construction.
What this means in practice
- •For cryptographic engineers: Securely encrypt data that can only be decrypted with a valid solution to a specific hard problem, improving flexible encryption schemes.
- •For security protocol designers: Use theoretical guarantees from prime-order generic groups to build novel protocols relying on witness encryption for NP statements.
A theory result. No direct application yet.
Authors
Isaac M Hair, Amit Sahai
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^{Ω(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.