Cryptography is largely based on unproven assumptions, which, while believable, might fail. Notably if P=NP, or if we live in Pessiland, then all current cryptographic assumptions will be broken. A compelling question is if any interesting cryptography might exist in Pessiland.
A natural approach to tackle this question is to base cryptography on an assumption from finegrained complexity. Ball, Rosen, Sabin, and Vasudevan [BRSV’17] attempted this, starting from popular hardness assumptions, such as the Orthogonal Vectors (OV) Conjecture. They obtained problems that are hard on average, assuming that OV and other problems are hard in the worst case. They obtained proofs of work, and hoped to use their averagecase hard problems to build a finegrained oneway function. Unfortunately, they proved that constructing one using their approach would violate a popular hardness hypothesis. This motivates the search for other finegrained averagecase hard problems.
The main goal of this paper is to identify sufficient properties for a finegrained averagecase assumption that imply cryptographic primitives such as finegrained public key cryptography (PKC). Our main contribution is a novel construction of a cryptographic key exchange, together with the definition of a small number of relatively weak structural properties, such that if a computational problem satisfies them, our key exchange has provable finegrained security guarantees, based on the hardness of this problem. We then show that a natural and plausible averagecase assumption for the key problem ZerokClique from finegrained complexity satisfies our properties. We also develop finegrained oneway functions and hardcore bits even under these weaker assumptions.
Where previous works had to assume random oracles or the existence of strong oneway functions to get a keyexchange computable in O(n) time secure against O(n^2) time adversaries (see [Merkle’78] and [BGI’08]), our assumptions seem much weaker. Our key exchange has a similar gap between the computation of the honest party and the adversary as prior work, while being noninteractive, implying finegrained PKC.
more »
« less
Is it Easier to Prove Theorems that are Guaranteed to be True?
Consider the following two fundamental open problems in complexity theory:
• Does a hardonaverage language in NP imply the existence of oneway functions?
• Does a hardonaverage language in NP imply a hardonaverage problem in TFNP (i.e.,
the class of total NP search problem)?
Our main result is that the answer to (at least) one of these questions is yes. Both oneway functions and problems in TFNP can be interpreted as promisetrue distributional NP search problems—namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence
of a hardonaverage distributional NP search problem implies a hardonaverage promisetrue distributional NP search problem. In other words, It is no easier to find witnesses (a.k.a. proofs) for efficientlysampled statements (theorems) that are guaranteed to be true.
This result follows from a more general study of interactive puzzles—a generalization of
averagecase hardness in NP—and in particular, a novel roundcollapse theorem for computationallysound protocols, analogous to BabaiMoran’s celebrated roundcollapse theorem for informationtheoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)round publiccoin nontrivial arguments (i.e., argument systems that are not proofs) imply the existence of a hardonaverage problem in NP/poly.
more »
« less
 Award ID(s):
 1704788
 NSFPAR ID:
 10233401
 Date Published:
 Journal Name:
 IEEE Symposium on Foundations of Computer Science
 Page Range / eLocation ID:
 12551267
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)We review a study of averagecase complexity through the lens of interactive puzzles interactive games between a computationally bounded Challenger and computationallybounded Solver/Attacker. Most notably, we use this treatment to review a recent result showing that if NP is hardontheaverage, then there exists a sampleable distribution over only true statements of an NP language, for which no probabilistic polynomial time algorithm can find witnesses. We also discuss connections to the problem of whether averagecase hardness in NP implies averagecase hardness in TFNP, or the existence of cryptographic oneway functions.more » « less

Interactive proof systems allow a resourcebounded verifier to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee that the prover can only convince the verifier of true statements. In the context of centralized computation, a celebrated result shows that interactive proofs are extremely powerful, allowing polynomialtime verifiers to decide any language in PSPACE. In this work we initiate the study of interactive distributed proofs: a network of nodes interacts with a single untrusted prover, who sees the entire network graph, to decide whether the graph satisfies some property. We focus on the communication cost of the protocol — the number of bits the nodes must exchange with the prover and each other. Our model can also be viewed as a generalization of the various models of “distributed NP” (proof labeling schemes, etc.) which received significant attention recently: while these models only allow the prover to present each network node with a string of advice, our model allows for backandforth interaction. We prove both upper and lower bounds for the new model. We show that for some problems, interaction can exponentially decrease the communication cost compared to a noninteractive prover, but on the other hand, some problems retain nontrivial cost even with interaction.more » « less

null (Ed.)We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n) ≥ (1 + ε)n, ε > 0, the following are equivalent: • Oneway functions exists (which in turn is equivalent to the existence of secure privatekey encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); • ttime bounded Kolmogorov Complexity, Kt, is mildly hardonaverage (i.e., there exists a polynomial p(n) > 0 such that no PPT algorithm can compute Kt, for more than a 1 − 1/p(n) fraction of nbit strings). In doing so, we present the first natural, and wellstudied, computational problem characterizing the feasibility of the central privatekey primitives and protocols in Cryptography.more » « less

null (Ed.)A fundamental pursuit in complexity theory concerns reducing worstcase problems to averagecase problems. There exist complexity classes such as PSPACE that admit worstcase to averagecase reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the averagecase hardness of inverting oneway permutations, on NPcompleteness is a particularly intriguing instance. As there is evidence showing that classical reductions from NPhard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NPhard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NPcomplete problems reduce to inverting oneway permutations using certain types of quantum reductions, then coNP ⊆ QIP ( 2 ) .more » « less