Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms. Our results concern fundamental questions in complexity theory, such as the NP vs PSPACE question, and also in cryptography, such as the question of constructing non-interactive zero-knowledge arguments for NP from unstructured assumptions. Relying on strong complexity-theoretic hardness assumptions (that will be described below): 1. Complexity theory. We prove that PSPACE is contained in the “computationally sound” version of NP. Specifically, for every L∈PSPACE, membership in L can be verified by an NP-type (deterministic, polynomial-time) verifier V with the following guarantee: The verifier accepts every x∈ L when given a proof π from an honest prover that runs in fixed exponential time TP; and every uniform adversary running in probabilistic time poly(TP) cannot find x∉ L and π such that V(x,π)=1, except with negligible probability in TP. As a corollary in the area of bounded arithmetic, under the same assumptions, we deduce that NP≠PSPACE is not provable in the theory APC1. This is a strong theory, which captures many of the major results in complexity. 2. Cryptography. We construct new cryptographic protocols, including succinct non-interactive arguments (SNARGs) for NC in the plain model, as well as non-interactive zero-knowledge and witness indistinguishable (NIZK and NIWI) proof systems for NP, all with computational soundness against uniform adversaries. The SNARG relies solely on the aforementioned complexity-theoretic assumption, whereas the NIZK and NIWI require also a sub-exponentially secure one-way function (which should be injective in the case of the NIWI). These are the first constructions of the above protocols that do not rely on highly structured cryptographic primitives. Roughly speaking, following Chen and Tell (FOCS 2021, STOC 2023), the complexity-theoretic hardness assumptions throughout our paper assert the existence of functions f ∶ 0,1n → 0,1k that are computable in polynomial time and hard for bounded-space machines (say, linear space) in a strong average-case sense: No efficient algorithm can find an input x on which the bounded-space machine computes f, except with negligible probability.