- How Hard Are Non-interactive Proof Systems?
- Project Year:
2020
- REU Student (s):
John Gouwar | Grinnell College IA
| Caleb Robelle | University of Maryland-Baltimore County MD
- Student 1 Institution:
Grinnell College
- Student 2 Institution:
University of Maryland-Baltimore County
- Project Mentor:
Eric Allender
- Project Mentor Area:
Computer Science
- Project Abstract:
Zero-knowledge proof systems are of great interest to cryptographers, since they allow for the sharing of knowledge of secret information without divulging the actual secret. Interactive versions of these proof systems contain fundamental cryptographic problems such as discrete log and decisional Diffie-Helman. We analyzed the class of non-interactive versions of these proof systems, NISZK and a variant where the verfier in the system is limited to being a log-space machine, NISZKL. We show that EA for NC0 circuits is complete for NISZKL under AC0-many one reductions. We also show that a problem concerning the minimum time-bounded Kolmogorov complexity of strings, MKTP, is hard for co-NISZKL under P/poly many-one reductions by reduction from EA. MKTP is a candidate NP-intermediate problem and previously had only been shown to be hard under NC0 reductions for a subclass of P.
