Skip to main content

Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption

Author(s): Bartusek, James; Ishai, Yuval; Jain, Aayush; Ma, Fermi; Sahai, Amit; et al

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr10v6p
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBartusek, James-
dc.contributor.authorIshai, Yuval-
dc.contributor.authorJain, Aayush-
dc.contributor.authorMa, Fermi-
dc.contributor.authorSahai, Amit-
dc.contributor.authorZhandry, Mark-
dc.date.accessioned2021-10-08T19:48:09Z-
dc.date.available2021-10-08T19:48:09Z-
dc.date.issued2020en_US
dc.identifier.citationBartusek, James, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, and Mark Zhandry. "Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption." In 11th Innovations in Theoretical Computer Science Conference (2020): pp. 82:1-82:39. doi:10.4230/LIPIcs.ITCS.2020.82en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr10v6p-
dc.description.abstractAn affine determinant program ADP: {0,1}^n → {0,1} is specified by a tuple (A,B_1,…,B_n) of square matrices over 𝔽_q and a function Eval: 𝔽_q → {0,1}, and evaluated on x ∈ {0,1}^n by computing Eval(det(A + ∑_{i∈[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 (i𝒪) 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.en_US
dc.format.extent82:1 - 82:39en_US
dc.language.isoen_USen_US
dc.relation.ispartof11th Innovations in Theoretical Computer Science Conferenceen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleAffine Determinant Programs: A Framework for Obfuscation and Witness Encryptionen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.ITCS.2020.82-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
FrameworkObfuscationWitnessEncryption.pdf766.85 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.