Paper 2020/889

Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption

James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, and Mark Zhandry


An affine determinant program ADP: {0,1}^n → {0,1} is specified by a tuple (A,B_1,...,B_n) of square matrices over F_q and a function Eval: F_q → {0,1}, and evaluated on x \in {0,1}^n by computing Eval(det(A + sum_{i \in [n]} x_i B_i)). In this work, we suggest ADPs as a new framework for building general-purpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADP-based framework may one day yield secure, practically feasible obfuscation. As a proof-of-concept, we give a candidate ADP-based construction of indistinguishability obfuscation (iO) for all circuits along with a simple witness encryption candidate. We provide cryptanalysis demonstrating that our schemes resist several potential attacks, and leave further cryptanalysis to future work. Lastly, we explore practically feasible applications of our witness encryption candidate, such as public-key encryption with near-optimal key generation.

Available format(s)
Publication info
Published elsewhere. Minor revision. Innovations in Theoretical Computer Science (ITCS 2020)
obfuscationwitness encryption
Contact author(s)
bartusek james @ gmail com
yuvali @ cs technion ac il
aayushjain @ cs ucla edu
fermima @ alum mit edu
sahai @ cs ucla edu
mzhandry @ princeton edu
2020-07-16: received
Short URL
Creative Commons Attribution


      author = {James Bartusek and Yuval Ishai and Aayush Jain and Fermi Ma and Amit Sahai and Mark Zhandry},
      title = {Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/889},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.