TY - GEN
T1 - Affine determinant programs
T2 - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020
AU - Bartusek, James
AU - Ishai, Yuval
AU - Jain, Aayush
AU - Ma, Fermi
AU - Sahai, Amit
AU - Zhandry, Mark
N1 - Funding Information:
Funding YI was supported by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, and a joint Israel-India grant. MZ, FM, AS, and AJ were supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. MZ and FM were also supported under NSF grant 1616442. AS and AJ were also supported in part by a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. AJ was also supported by a Google PhD Fellowship in Privacy and Security. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, the U.S. Government or Google.
Funding Information:
YI was supported by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, and a joint Israel-India grant. MZ, FM, AS, and AJ were supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. MZ and FM were also supported under NSF grant 1616442. AS and AJ were also supported in part by a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. AJ was also supported by a Google PhD Fellowship in Privacy and Security. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, the U.S. Government or Google.
Publisher Copyright:
© James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, and Mark Zhandry.
PY - 2020/1
Y1 - 2020/1
N2 - 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.
AB - 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.
KW - Obfuscation
KW - Witness encryption
UR - http://www.scopus.com/inward/record.url?scp=85078005982&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078005982&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2020.82
DO - 10.4230/LIPIcs.ITCS.2020.82
M3 - Conference contribution
AN - SCOPUS:85078005982
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 11th Innovations in Theoretical Computer Science Conference, ITCS 2020
A2 - Vidick, Thomas
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 12 January 2020 through 14 January 2020
ER -