Affine determinant programs: A framework for obfuscation and witness encryption

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An affine determinant program ADP: {0, 1}n → {0, 1} is specified by a tuple (A, B1, . . ., Bn) of square matrices over Fq and a function Eval: Fq → {0, 1}, and evaluated on x ∈ {0, 1}n by computing Eval(det(A + Pi∈[n] xiBi)). 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.

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume151

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
CountryUnited States
CitySeattle
Period1/12/201/14/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Obfuscation
  • Witness encryption

Cite this

Bartusek, J., Ishai, Y., Jain, A., Ma, F., Sahai, A., & Zhandry, M. (2020). Affine determinant programs: A framework for obfuscation and witness encryption. In T. Vidick (Ed.), 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 [82] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 151). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2020.82