TY - GEN

T1 - Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP

AU - Pandey, Omkant

AU - Prabhakaran, Manoj

AU - Sahai, Amit

N1 - Publisher Copyright:
© International Association for Cryptologie Research 2015.

PY - 2015

Y1 - 2015

N2 - We show the following result: Assuming the existence of public-coin differing-input obfuscation (pc-diO) for the class of all polynomial time Turing machines, then there exists a four message, fully concurrent zero-knowledge proof system for all languages in NP with negligible soundness error. This result is constructive: given pc-diO,our reduction yields an explicit protocol along with an explicit simulator that is "straight line" and runs in strict polynomial time. The obfuscation security property is used only to prove soundness.Public-coin differing-inputs obfuscation is a notion of obfuscation closely related to indistinguishability obfuscation. Most importantly for our result, pc-diO does not suffer from any known impossibility results: recent negative results on standard differing-inputs obfuscation do not apply to pc-diO. Furthermore, candidate constructions for pc-diO for the class of all polynomial-time Turing Machines are known.Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. We view the development of this new non-black-box simulation technique as the main contribution of our work. In addition to assuming pc-diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions.

AB - We show the following result: Assuming the existence of public-coin differing-input obfuscation (pc-diO) for the class of all polynomial time Turing machines, then there exists a four message, fully concurrent zero-knowledge proof system for all languages in NP with negligible soundness error. This result is constructive: given pc-diO,our reduction yields an explicit protocol along with an explicit simulator that is "straight line" and runs in strict polynomial time. The obfuscation security property is used only to prove soundness.Public-coin differing-inputs obfuscation is a notion of obfuscation closely related to indistinguishability obfuscation. Most importantly for our result, pc-diO does not suffer from any known impossibility results: recent negative results on standard differing-inputs obfuscation do not apply to pc-diO. Furthermore, candidate constructions for pc-diO for the class of all polynomial-time Turing Machines are known.Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. We view the development of this new non-black-box simulation technique as the main contribution of our work. In addition to assuming pc-diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions.

UR - http://www.scopus.com/inward/record.url?scp=84924359070&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84924359070&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-46497-7_25

DO - 10.1007/978-3-662-46497-7_25

M3 - Conference contribution

AN - SCOPUS:84924359070

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 638

EP - 667

BT - Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Proceedings

A2 - Dodis, Yevgeniy

A2 - Nielsen, Jesper Buus

PB - Springer

T2 - 12th Theory of Cryptography Conference, TCC 2015

Y2 - 23 March 2015 through 25 March 2015

ER -