Synergies Between Proof Complexity and Cryptography

We show the surprising power of combining the following two well-studied assumptions from cryptography and proof complexity:

 

    1. (Cryptography) there exists a subexponentially secure indistinguishability obfuscator, and

    2. (Proof Complexity) there are no subexponentially optimal propositional proof systems in the sense of Cook and Reckhow (J. Symb. Log. 1979).

 

The first assumption allows one to hide the inner workings of a given algorithm in a certain

weak sense. The second assumption is a “constructive” version of coNP ⊈ NTIME[subexp].

 

We show that together these assumptions imply strong circuit lower bounds for NP \cap coNP (in fact, UP \cap coUP). Our proof uses the proof complexity assumption to circumvent a black-box barrier of Bitansky, Degwekar, and Vaikuntanathan (CRYPTO 2017). Combined with prior work, this implies that the two assumptions imply (a) quasipolynomial-time derandomization of BPP, and (b) public-key encryption.

 

We also show, under our two assumptions, that an “implicit” version of the Minimum Circuit Size Problem, ImpMCSP, is (a) NP-hard under randomized polynomial-time Karp reductions, and (b) provably not NP-hard under randomized “Levin” reductions. Here, an instance of ImpMCSP is a circuit S : {0,1}^{poly(n)} -> {0,1}^{n+1} whose range is the set {(x, f(x)) : x \in {0,1}^n}, and a size parameter s. The task is to distinguish between the case where f has circuit complexity less than s and the case where f has circuit complexity much larger than s.

 

We prove our results by developing a general framework of “fooling” efficiently computable Pi_1 properties, using proof complexity; our framework builds upon the recent results of Ilango (FOCS 2025).

 

This talk is based on joint work with Halley Goldberg and Valentine Kabanets: https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1012.pdf, https://eccc.weizmann.ac.il/report/2026/091/ (older draft)