Paper 2026/2063 Original: eprint.iacr.org/2026/2063 ↗
Witness Encryption for NP from SNARGs and Groups
Abstract
We construct the first witness encryption for NP in the generic group model from succinct non-interactive arguments (SNARGs) for NP. Our construction applies to any SNARG with subexponential soundness and polylogarithmic online verification time after input preprocessing. Central to our result is the first Karp-Levin reduction from satisfiability for circuits of size $\mathrm{polylog}(\lambda)$ to the minimum-distance problem for linear codes (GapMDP) over a prime field of size $\lambda^{\omega(1)}$, with an approximation factor of $\omega(\log \lambda)$, where $\lambda$ is the security parameter. We obtain this reduction by adapting Hair and Sahai's recent hardness result for GapSVP. Combining our reduction with the witness encryption framework due to Barta, Ishai, Ostrovsky, and Wu [CRYPTO 2020], we obtain the first unconditional extractable witness encryption for circuits of size $\mathrm{polylog}(\lambda)$ in the generic group model. These techniques may be of independent interest.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2026-09-16: last updated
- 2026-09-16: published
- Short URL
- https://ia.cr/2026/2063
- License
- https://creativecommons.org/licenses/by-nc-sa/4.0/
BibTeX
@misc{cryptoeprint:2026/2063,
author = {Zhengzhong Jin},
title = {Witness Encryption for NP from SNARGs and Groups},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2063},
year = {2026},
url = {https://eprint.iacr.org/2026/2063}
}