Paper 2026/175 Original: eprint.iacr.org/2026/175 ↗
Implementable Witness Encryption from Arithmetic Affine Determinant Programs
Abstract
Witness encryption (WE) for general NP remains challenging to realize with practical efficiency. A natural approach is to combine WE with SNARKs to obtain succinct witnesses; however, embedding general-purpose SNARK verification into existing WE constructions leads to prohibitive overhead. We introduce arithmetic affine determinant programs (AADPs), a variant of affine determinant programs designed to natively support arithmetic constraint systems. This enables direct expression of SNARK verification. To address security challenges in the arithmetic setting, we define projectively safe constraint systems and develop algebraic gadgets that preserve this property. Using these components, we construct a WE scheme for all NP languages based on AADPs, instantiated with a tailored SNARK. Our estimates indicate ciphertext sizes on the order of hundreds of terabytes at 100-bit security, which, to the best of our knowledge, is the most efficient instantiation of WE for general NP.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2026-05-10: last updated
- 2026-02-03: published
- Short URL
- https://ia.cr/2026/175
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/175,
author = {Lev Soukhanov and Yaroslav Rebenko and Muhammad El Gebali and Mikhail Komarov and Handan Kilinc-Alper and Michel Abdalla and Patrick Towa},
title = {Implementable Witness Encryption from Arithmetic Affine Determinant Programs},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/175},
year = {2026},
url = {https://eprint.iacr.org/2026/175}
}