A proof system is publicly verifiable, if anyone, by looking at the transcript of the proof, can be convinced that the corresponding theorem is true. Public verifiability is important in many applications since it allows to compute a proof only once while convincing an unlimited number of verifiers.
Popular interactive proof systems (e.g., 𝛴 protocols) protect the witness through various properties (e.g., witness indistinguishability (WI) and zero knowledge (ZK)) but typically they are not publicly verifiable since such proofs are convincing only for those verifiers who contributed to the transcripts of the proofs. The only known proof systems that are publicly verifiable rely on a noninteractive (NI) prover, through trust assumptions (e.g., NIZK in the CRS model), heuristic assumptions (e.g., NIZK in the random oracle model), specific numbertheoretic assumptions on bilinear groups or relying on obfuscation assumptions (obtaining NIWI with no setups).
In this work we construct publicly verifiable witnessindistinguishable proof systems from any 𝛴 protocol, based only on the existence of a very generic blockchain. The novelty of our approach is in enforcing a noninteractive verification (thus guaranteeing public verifiability) while allowing the prover to be interactive and talk to the blockchain (this allows us to circumvent the need of strong assumptions and setups). This opens interesting directions for the design of cryptographic protocols leveraging on blockchain technology.
more »
« less
Improved StraightLine Extraction in the Random Oracle Model With Applications to Signature Aggregation
The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover on some theorem, is able to produce a witness for with roughly the same probability that produces a verifying proof. This notion applies to both zeroknowledge protocols and verifiable computation where the goal is compressing a proof.
Pass (CRYPTO '03) first showed how to achieve this property for NP using a cutandchoose technique which incurred a bit overhead in communication where is a security parameter. Fischlin (CRYPTO '05) presented a more efficient technique based on ``proofs of work'' that sheds this cost, but only applies to a limited class of Sigma Protocols with a ``quasiunique response'' property, which for example, does not necessarily include the standard OR composition for Sigma protocols.
With Schnorr/EdDSA signature aggregation as a motivating application, we develop new techniques to improve the computation cost of straightline extractable proofs. Our improvements to the state of the art range from 70X200X for the best compression parameters. This is due to a uniquely suited polynomial evaluation algorithm, and the insight that a proofofwork that relies on multicollisions and the birthday paradox is faster to solve than inverting a fixed target.
Our collision based proofofwork more generally improves the Prover's random oracle query complexity when applied in the NIZK setting as well. In addition to reducing the query complexity of Fischlin's Prover, for a special class of Sigma protocols we can for the first time closely match a new lower bound we present.
Finally we extend Fischlin's technique so that it applies to a more general class of stronglysound Sigma protocols, which includes the OR composition. We achieve this by carefully randomizing Fischlin's techniquewe show that its current deterministic nature prevents its application to certain multiwitness languages.
more »
« less
 NSFPAR ID:
 10389802
 Date Published:
 Journal Name:
 ASIACRYPT'2022
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We present gOTzilla, a protocol for interactive zeroknowledge proofs for very large disjunctive statements of the following format: given publicly known circuit C, and set of values Y = {y1 , . . . , yn }, prove knowledge of a witness x such that C(x) = y1 ∨ C(x) = y2 ∨ · · · ∨ C(x) = yn . These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key sk that associates with the hash of a public key H(pk) posted on the ledger. We note that the size of n in popular cryptocurrencies, such as Bitcoin, is estimated to 80 million. For the construction of gOTzilla, we start by observing that if we restructure the proof statement to an equivalent of proving knowledge of (x, y) such that (C(x) = y) ∧ (y = y1 ∨ · · · ∨ y = yn )), then we can reduce the disjunction of equalities to 1outofN oblivious transfer (OT). Our overall protocol is based on the MPC in the head (MPCitH) paradigm. We additionally provide a concrete, efficient extension of our protocol for the case where C combines algebraic and nonalgebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of O(log n) plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total runtime of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and nonalgebraic elements.more » « less

Tessaro, Stefano (Ed.)A Proof of Sequential Work (PoSW) allows a prover to convince a resourcebounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including timestamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depthrobust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depthrobust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long ℋsequence and that any malicious party running in sequential time T1 will fail to produce an ℋsequence of length T except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time T1 will fail to produce an ℋsequence except with negligible probability  even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry’s recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish postquantum security of a noninteractive PoSW obtained by applying the FiatShamir transform to Cohen and Pietrzak’s efficient construction (EUROCRYPT 2018).more » « less

Amir Hashemi (Ed.)The proofofwork interactive protocol by Shafi Goldwasser, Yael T. Kalai and Guy N. Rothblum (GKR) [STOC 2008, JACM 2015] certifies the execution of an algorithm via the evaluation of a corresponding boolean or arithmetic circuit whose structure is known to the verifier by circuit wiring algorithms that define the uniformity of the circuit. Here we study protocols whose prover time and spacecomplexities are within a polylogarithmic factor of the time and spacecomplexity of the algorithm; we call those protocols `prover efficient.' We show that the uniformity assumptions can be relaxed from LOGSPACE to polynomialtime in the bitlengths of the labels which enumerate the nodes in the circuit. Our protocol applies GKR recursively to the arising sumcheck problems on each level of the circuit whose values are verified, and deploys any of the prover efficient versions of GKR on the constructed sorting/prefix circuits with logdepth wiring functions. The verifier timecomplexity of GKR grows linearly in the depth of the circuit. For deep circuits such as the MillerRabin integer primality test of an nbit integer, the large number of rounds may interfere with soundness guarantees after the application of the FiatShamir heuristic. We rearrange the circuit evaluation problem by the babysteps/giantsteps method to achieve a depth of n^(1/2+o(1)), at prover cost n^(2+o(1)) bit complexity and communication and verifier cost n^(3/2+o(1)).more » « less

Querytocommunication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated “lifted” function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. A number of important complexity questions could be resolved if we could make substantial improvements in the input size required for lifting with the Index function, which is a universal gadget for lifting, from its current nearlinear size down to polylogarithmic in the number of inputs N of the original function or, ideally, constant. The nearlinear size bound was recently shown by Lovett, Meka, Mertz, Pitassi and Zhang [20] using a recent breakthrough improvement on the Sunflower Lemma to show that a certain graph associated with an Index function of that size is a disperser. They also stated a conjecture about the Index function that is essential for further improvements in the size required for lifting with Index using current techniques. In this paper we prove the following;  The conjecture of Lovett et al. is false when the size of the Index gadget is less than logarithmic in N .  The same limitation applies to the InnerProduct function. More precisely, the InnerProduct function, which is known to satisfy the disperser property at size O(log N ), also does not have this property when its size is less than log N .  Notwithstanding the above, we prove a lifting theorem that applies to Index gadgets of any size at least 4 and yields lower bounds for a restricted class of communication protocols in which one of the players is limited to sending parities of its inputs.  Using a modification of the same idea with improved lifting parameters we derive a strong lifting theorem from decision tree size to parity decision tree size. We use this, in turn, to derive a general lifting theorem in proof complexity from treeresolution size to treelike Res(⊕) refutation size, which yields many new exponential lower bounds on such proofs.more » « less