Seminar • Algorithms and Complexity • Fiat-Shamir in the Plain Model from Derandomization

Please note: This seminar will take place in M3 4206 and virtually.

Roei Tell, Assistant Professor
Department of Computer and Mathematical Sciences, University of Toronto

Do efficient algorithms believe that NP = PSPACE? Under strong complexity-theoretic assumptions, we prove that every problem in PSPACE can be solved by an NP-type verifier running in polynomial time that looks correct to any efficient observer (i.e., it has computational soundness). For example, the PSPACE-complete problem TQBF can be decided by a polytime NP-type verifier V, interacting with an honest prover whose runtime is T(n) = 2^O(n), such that no adversary running in time poly(T) can find an input and a proof that mislead V (except with probability negligible in T over the adversary’s coins).

The proof uses recent techniques from non-black-box derandomization in order to compile the interactive proof system underlying IP = PSPACE into a deterministic (non-interactive) argument system. This is an instance from a broader set of results applying derandomization-based techniques and assumptions to instantiate (versions of) the Fiat-Shamir heuristic in cryptography, in the plain model and without (or with weak) cryptographic assumptions.

From an upcoming joint work with Lijie Chen and Ron Rothblum.

To attend this seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/95773268163.