Paper 2026/1583

Cryptanalysis of a Candidate Witness Encryption Scheme for Affine Determinant Programs

Abstract

At ITCS 2020, Bartusek, Ishai, Jain, Ma, Sahai, and Zhandry proposed a framework for witness encryption based on affine determinant programs and gave a concrete witness encryption candidate. Yao, Chen, and Yu later broke the separate ADP-based indistinguishability-obfuscation candidate, while noting that their attack did not apply to the witness-encryption construction. More recently, Soukhanov et al. proposed witness encryption from arithmetic affine determinant programs. Soukhanov subsequently described a commutator attack on that construction and noted that the original ADP construction is also subject to the attack for sparse circuits. The recovery of hidden column spaces in our attack uses this commutator technique. We give a deterministic polynomial-time attack that recovers the encrypted bit from the public ciphertext matrices of this candidate. It covers every $q\geq 1$ in the theorem's recovery range, including $q(n)=\lceil n^\varepsilon\rceil$ for all sufficiently large $n$. Outside a fixed finite set of primes, it applies to every SUBSET-SUM instance whose coefficient vector is nonzero modulo $p$ and that has no Boolean solution modulo $p$. On an explicit efficiently generated family of integer NO instances, the encrypted bit is recovered with probability $1-\mathrm{negl}(n)$ under the field-size convention of the original paper.

Note: 2026-08-19: Added an explicit AI usage disclosure and moved the references before the appendix. The technical content and results are unchanged.