Abstract
We'll see how to transform every doubly efficient constant-round interactive protocol into an NP-type verifier that has essentially the same time complexity, and that looks sound to any efficient adversary (under strong hardness assumptions). Consequently, for every eps>0, we conditionally construct an NP-type (deterministic) argument system for counting the number of satisfying assignments for an n-bit formula of size 2^{o(n)} in time 2^{eps*n}, with soundness against adversaries running in time 2^{O(n)}. Our approach requires hardness assumptions that, albeit very strong, fall within the complexity-theoretic regime. In particular, they don't seem to imply even one-way functions.
To achieve the aforementioned results, we employ targeted pseudorandom generators (tarPRGs), a more relaxed form of classical PRGs that has been heavily utilized in recent works on derandomization, and apply them to the interactive protocol setting. This method bears significant resemblance to the standard Fiat-Shamir approach, with targeted PRGs functioning similarly to correlation intractable hash functions, albeit with a completely different analysis.
In the first part of this two-talk series, we will introduce our main results, cover essential background on derandomization, and introduce the necessary technical tools. In the second part, we will apply these technical tools to the interactive protocol setting to prove our main results.
This talk is based on a joint work with Roei Tell