Implementable Witness Encryption from Arithmetic Affine Determinant Programs

Lev Soukhanov; Yaroslav Rebenko; Muhammad El Gebali; Mikhail Komarov; Handan Kilinc-Alper; Michel Abdalla; Patrick Towa

Paper 2026/175

Implementable Witness Encryption from Arithmetic Affine Determinant Programs

Lev Soukhanov, [[alloc] init]

Yaroslav Rebenko, [[alloc] init]

Muhammad El Gebali, [[alloc] init]

Mikhail Komarov, [[alloc] init]

Handan Kilinc-Alper, [[alloc] init]

Michel Abdalla, [[alloc] init]

Patrick Towa, [[alloc] init]

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.
Keywords: witness encryption
Contact author(s): lev @ allocinit xyz
yar @ allocinit xyz
gebali @ allocinit xyz
nemo @ allocinit xyz
handan @ allocinit xyz
michel @ allocinit xyz
patrick @ allocinit xyz
History: 2026-05-10: revised; 2026-02-03: received; See all versions
Short URL: https://ia.cr/2026/175
License: CC BY

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}
}