Whether the Minimum Circuit Size Problem (MCSP) is NP-hard or not is a long-standing open question. Indeed, Levin delayed the publication of his fundamental work on the theory of NP-completeness because he hoped to prove NP-completeness of MCSP.In this paper, we present the first plausible assumptions under which MCSP is NP-hard. Specifically, we prove that MCSP is NP-hard under deterministic quasi-polynomial-time nonadaptive reductions, assuming:•subexponentially-secure non-interactive witness indistinguishable proof systems for SAT exist,•coNP requires subexponential-size non-deterministic circuits, and•PNP/poly requires circuits of size Ω(2n/n).This is arguably the first evidence that MCSP is not in coNP, which indicates that there is no short proof that witnesses the hardness of a function.

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. ‘94] shows that zeroknowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs - namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness. This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is “game-based” instead of “simulation-based.” Our construction builds on the work of Kuykendall and Zhandry [TCC ‘20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajíček and Pudlák’s 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert’s second problem (and, hence, also Gödel’s incompleteness theorem). Our highlevel idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.

We study several problems in the intersection of cryptography and complexity theory based on the following highlevel thesis.1)Obfuscation can serve as a general-purpose worst-case to average-case reduction, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.2)We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worstcase hardness assumptions beyond $P \neq N P$, and (ii) leveraging worst-case hardness reductions, either proved by traditional complexity-theoretic methods or facilitated further by cryptography.Concretely, our results include:•Optimal Hardness. Assuming sub-exponential indistinguishability obfuscation, we give fine-grained worst-case to average case reductions for circuit-SAT. In particular, if finding an NP-witness requires nearly brute-force time in the worst case, then the same is true for some efficiently sampleable distribution. In fact, we show that under these assumptions, there exist families of one-way functions with optimal time-probability security tradeoffs. Under an additional, stronger assumption - the optimal non-deterministic hardness of refuting circuit-SAT - we construct additional cryptographic primitives such as PRGs and public-key encryption that have such optimal timeadvantage security tradeoffs.•Direct Product Hardness. Again assuming iO and optimal non-deterministic hardness of SAT refutation, we show that the “(search) k-fold SAT problem” - the computational task of finding satisfying assignments to k circuit-SAT instances simultaneously - has (optimal) hardness roughly $\left(T / 2^{n}\right)^{k}$ for time T algorithms. In fact, we build “optimally secure one-way product functions” (Holmgren-Lombardi, FOCS ‘18), demonstrating that optimal direct product theorems hold for some choice of one-way function family.•Single-Input Correlation Intractability. Assuming either iO or LWE, we show a worst-case to average-case reduction for strong forms of single-input correlation intractability. That is, powerful forms of correlation-intractable hash functions exist provided that a collection of worst-case “correlationfinding” problems are hard.•Non-interactive Proof of Quantumness. Assuming subexponential iO and OWFs, we give a non-interactive proof of quantumness based on the worst-case hardness of the whitebox Simon problem. In particular, this proof of quantumness result does not explicitly assume quantum advantage for an average-case task.To help prove our first two results, we show along the way how to improve the Goldwasser-Sipser “set lower bound” protocol to have communication complexity quadratically smaller in the multiplicative approximation error $\varepsilon$.

Abstract. It is a longstanding open problem whether the Minimum Circuit Size Problem ([Formula: see text]) and related meta-complexity problems are [Formula: see text]-complete and hard to approximate. In this work, we prove NP-hardness of approximating meta-complexity with nearly optimal approximation gaps. Our key idea is to use cryptographic constructions in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present three results that give both conditional and unconditional hardness of approximation. First, assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity ([Formula: see text]) in the regime where [Formula: see text]. Second, we unconditionally show near-optimal NP-hardness of approximation for the minimum oracle circuit size problem where Yes instances have circuit complexity at most [Formula: see text], and No instances are essentially as hard as random truth tables. Finally, we define a “multivalued” version of [Formula: see text], called [Formula: see text], and show that with probability 1 over a random oracle [Formula: see text], [Formula: see text] is NP-hard to approximate under quasi-polynomial-time reductions with [Formula: see text] oracle access.

A compression problem is defined with respect to an efficient encoding function f; given a string x, our task is to find the shortest y such that f(y) = x. The obvious brute-force algorithm for solving this compression task on n-bit strings runs in time O(2ℓ · t(n)), where ℓ is the length of the shortest description y and t(n) is the time complexity of f when it prints n-bit output. We prove that every compression problem has a Boolean circuit family which finds short descriptions more efficiently than brute force. In particular, our circuits have size 24 ℓ / 5 · poly(t(n)), which is significantly more efficient for all ℓ ≫ log(t(n)). Our construction builds on Fiat-Naor’s data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length. As a consequence, the Minimum Circuit Size Problem for generic fan-in two circuits of size s(n) on truth tables of size 2n can be solved by circuits of size 24/5 · w + o(w) · poly(2n), where w = s(n) log2(s(n) + n). This improves over the brute-force approach of trying all possible size-s(n) circuits for all s(n) ≥ n. Similarly, the task of computing a short description of a string x when its t-complexity is at most ℓ, has circuits of size 24/5 ℓ · poly(t). We also give nontrivial circuits for computing Kt complexity on average, and for solving NP relations with “compressible” instance-witness pairs.

Attempts to prove the intractability of the Minimum Circuit Size Problem ($\mathsf{MCSP}$) date as far back as the 1950s and are well motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing $\mathsf{MCSP}$ is intractable under worst-case assumptions. While Masek showed in the late 1970s that the version of $\mathsf{MCSP}$ for $\mathsf{DNF}$ formulas is $\mathsf{NP}$-hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that determining the minimum size of a depth-$d$ formula computing a given Boolean function is $\mathsf{NP}$-hard under quasipolynomial-time randomized reductions for all constant $d \geq 2$. Our approach is based on a method to “lift” depth-$d$ formula lower bounds to depth-$(d+1)$. This method also implies the existence of a function with a $2^{\Omega_d(n)}$ additive gap between its depth-$d$ and depth-$(d+1)$ formula complexity. We also make progress in the case of general, unrestricted circuits. We show that the version of $\mathsf{MCSP}$ where the input is a partial function (represented by a string in $\{0,1,\star\}^*$) is not in $\mathsf{P}$ under the Exponential Time Hypothesis (ETH). Intriguingly, we formulate a notion of lower bound statements being $(\mathsf{P/poly})$-recognizable that is closely related to Razborov and Rudich's definition of being $(\mathsf{P/poly})$-constructive. We show that unless there are subexponential-sized circuits computing $\mathsf{SAT}$, the collection of lower bound statements used to prove the correctness of our reductions cannot be $(\mathsf{P/poly})$-recognizable.

Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 2008) and Mironov, Pandey, Reingold, and Vadhan (CRYPTO 2009). In contrast to SDP, CDP only requires privacy guarantees to hold against computationally-bounded adversaries rather than computationally-unbounded statistical adversaries. Despite the question being raised explicitly in several works (e.g., Bun, Chen, and Vadhan, TCC 2016), it has remained tantalizingly open whether there is any task achievable with the CDP notion but not the SDP notion. Even a candidate such task is unknown. Indeed, it is even unclear what the truth could be!In this work, we give the first construction of a task achievable with the CDP notion but not the SDP notion, under the following strong but plausible cryptographic assumptions:•Non-Interactive Witness Indistinguishable Proofs,•Laconic Collision-Resistant Keyless Hash Functions,•Differing-Inputs Obfuscation for Public-Coin Samplers.In particular, we construct a task for which there exists an $\varepsilon$-CDP mechanism with $\varepsilon=O(1)$ achieving $1-o(1)$ utility, but any $(\varepsilon, \delta)$-SDP mechanism, including computationally-unbounded ones, that achieves a constant utility must use either a super-constant $\varepsilon$ or an inverse-polynomially large $\delta$.To prove this, we introduce a new approach for showing that a mechanism satisfies CDP: first we show that a mechanism is “private” against a certain class of decision tree adversaries, and then we use cryptographic constructions to “lift” this into privacy against computationally bounded adversaries. We believe this approach could be useful to devise further tasks separating CDP from SDP.

Abstract. The minimum circuit size problem ([Formula: see text]) asks, given the truth table of a Boolean function [Formula: see text] and an integer [Formula: see text], if there is a circuit computing [Formula: see text] of size at most [Formula: see text]. It is a long-standing open question whether [Formula: see text] is [Formula: see text]-complete. We give, in our view, the strongest evidence yet that [Formula: see text] is in fact [Formula: see text]-complete. Specifically, we show that, with probability one, there is a [Formula: see text] reduction from the [Formula: see text]-hard problem of approximating vertex cover on hypergraphs to [Formula: see text] on circuits that have access to a uniformly random oracle [Formula: see text] (the reduction can be made uniform if it is given access to [Formula: see text]). Our reduction yields near-optimal additive hardness of approximation and extends to computing time-bounded Kolmogorov complexity ([Formula: see text]). Heuristically “instantiating” [Formula: see text] with real-world cryptographic hash functions, we get a plethora of candidate uniform deterministic polynomial-time many-one reductions from [Formula: see text] to [Formula: see text] and [Formula: see text] in the standard unrelativized world. To our knowledge, no candidate reduction from [Formula: see text] to [Formula: see text] or [Formula: see text] was known previously. Moreover, our results hold in the regime where [Formula: see text] has a non–black-box worst-case to average-case reduction [Hirahara, Non-black-box worst-case to average-case reductions within NP, 2018]. Thus, intriguingly, the existence of sufficiently “unstructured” functions implies that a problem with a known (non–black-box) worst-case to average-case reduction is [Formula: see text]-complete.

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds.

It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C:{0,1}n→{0,1}m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist?

We show broad equivalences in the average-case complexity of many different meta-complexity problems, including Kolmogorov complexity, time-bounded Kolmogorov complexity, and the Minimum Circuit Size Problem. These results hold for a wide range of parameters (various thresholds, approximation gaps, weak or strong average-case hardness, etc.) and complexity notions, showing the theory of meta-complexity is very *robust* in the average-case setting.

How difficult is it to compute the communication complexity of a two-argument total Boolean function f:[N]×[N] → {0,1}, when it is given as an N×N binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard. In this work, we show that it is NP-hard to approximate the size (number of leaves) of the smallest constant-round protocol for a two-argument total Boolean function f:[N]×[N] → {0,1}, when it is given as an N×N binary matrix. Along the way to proving this, we show a new deterministic variant of the round elimination lemma, which may be of independent interest.

A longstanding open question is whether the Minimum Circuit Size Problem (MCSP) is NP-complete. In fact, even determining whether MCSP has a search-to-decision reduction has been open for over twenty years. We show that, under the Exponential Time Hypothesis, the Minimum (DeMorgan) Formula Size Problem, MFSP, is not in P. Building on this, we show that MFSP has a polynomial-time (exact) search-to-decision reduction, a result that does not relativize. Our main technique relates the formula complexity of a partial function with the formula complexity of an associated total function and is proved using the “leaf weighting” technique of Buchfuhrer and Umans.

A longstanding open question is whether there is an equivalence between the computational task of determining the minimum size of any circuit computing a given function and the task of producing a minimum-sized circuit for a given function. While it is widely conjectured that both tasks require "perebor," or brute-force search, researchers have not yet ruled out the possibility that the search problem requires exponential time but the decision problem has a linear time algorithm. In this paper, we make progress in connecting the search and decision complexity of minimizing formulas. Let MFSP denote the problem that takes as input the truth table of a Boolean function f and an integer size parameter s and decides whether there is a formula for f of size at most s. Let Search- denote the corresponding search problem where one has to output some optimal formula for computing f. Our main result is that given an oracle to MFSP, one can solve Search-MFSP in time polynomial in the length N of the truth table of f and the number t of "near-optimal" formulas for f, in particular O(N⁶t²)-time. While the quantity t is not well understood, we use this result (and some extensions) to prove that given an oracle to MFSP: - there is a deterministic 2^O(N/(log log N))-time oracle algorithm for solving Search-MFSP on all but a o(1)-fraction of instances, and - there is a randomized O(2^.67N)-time oracle algorithm for solving Search-MFSP on all instances. Intriguingly, the main idea behind our algorithms is in some sense a "reverse application" of the gate elimination technique.

Can we design efficient algorithms for finding fast algorithms?This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications.Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NP-complete.While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive.In this work, we establish the first NP-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits.More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function f : {0, 1} n → {0, 1} m is NP-hard under many-one polynomial-time randomized reductions.Our argument builds on a simpler NP-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators.Complementing these results, we investigate the computational hardness of minimizing communication.We establish that several variants of this problem are NP-hard under deterministic reductions.In particular, unless P = NP, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial.This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions.

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions. While Masek showed in the late 1970s that the version of MCSP for DNF formulas is NP-hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that determining the minimum size of a depth- d formula computing a given Boolean function is N P-hard under quasipolynomial-time randomized reductions for all constant d ≥ 2. Our approach is based on a method to “lift” depth- d formula lower bounds to depth-( d+1). This method also implies the existence of a function with a 2Ωd(n1/5) additive gap between its depth-d and depth-( d+1) formula complexity. We also make progress in the case of general, unrestricted circuits. We show that the version of MCSP where the input is a partial function (represented by a string in {0,1, ?}*) is not in P under the Exponential Time Hypothesis (ETH). Intriguingly, we formulate a notion of lower bound statements being (P/poly)-recognizable that is closely related to Razborov and Rudich's definition of being (P/poly)-constructive. We show that unless there are subexponential-sized circuits computing SAT, the lower bound statements used to prove the correctness of our reductions cannot be (P/poly)-recognizable.

The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a half-century and has deep connections throughout theoretical computer science including to cryptography, computational learning theory, and proof complexity. For example, we know (informally) that if MCSP is easy to compute, then most cryptography can be broken. Despite this cryptographic hardness connection and extensive research, we still know relatively little about the hardness of MCSP unconditionally. Indeed, until very recently it was unknown whether MCSP can be computed in AC^0[2] (Golovnev et al., ICALP 2019). Our main contribution in this paper is to formulate a new "oracle" variant of circuit complexity and prove that this problem is NP-complete under randomized reductions. In more detail, we define the Minimum Oracle Circuit Size Problem (MOCSP) that takes as input the truth table of a Boolean function f, a size threshold s, and the truth table of an oracle Boolean function O, and determines whether there is a circuit with O-oracle gates and at most s wires that computes f. We prove that MOCSP is NP-complete under randomized polynomial-time reductions. We also extend the recent AC^0[p] lower bound against MCSP by Golovnev et al. to a lower bound against the circuit minimization problem for depth-d formulas, (AC^0_d)-MCSP. We view this result as primarily a technical contribution. In particular, our proof takes a radically different approach from prior MCSP-related hardness results.

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an n-variate boolean function has circuit complexity less than a given parameter s. We prove that MCSP is hard for constant-depth circuits with mod p gates, for any prime p >= 2 (the circuit class AC^0[p]). Namely, we show that MCSP requires d-depth AC^0[p] circuits of size at least exp(N^{0.49/d}), where N=2^n is the size of an input truth table of an n-variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random N-bit strings from those generated using independent samples from a biased random coin which is 1 with probability 1/2+N^{-0.49}, and 0 otherwise. Solving the coin problem with such parameters is known to require exponentially large AC^0[p] circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform AC^0 circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in NC^1 (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size AC^0 circuit with MCSP-oracle gates.