Author name cluster

Ron D. Rothblum

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

2 author rows

STOC Conference 2025 Conference Paper

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

Lijie Chen 0001
Ron D. Rothblum
Roei Tell

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 T P ; and every uniform adversary running in probabilistic time poly ( T P ) cannot find x ∉ L and π such that V ( x ,π)=1, except with negligible probability in T P . As a corollary in the area of bounded arithmetic, under the same assumptions, we deduce that NP ≠ PSPACE is not provable in the theory APC 1 . 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 ( SNARG s) 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,1} n → {0,1} k 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.

Details

SODA Conference 2025 Conference Paper

Locally Testable Tree Codes

Tamer Mour
Alon Rosen
Ron D. Rothblum

Tree codes (Schulman, STOC 93’, IEEE Transactions on Information Theory 96’) are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the i -th codeword symbol depends only on the first i message symbols. Codewords should have good tree distance meaning that for any two codewords, starting at the first point of divergence, they should have large Hamming distance. We investigate whether tree codes can be made to be locally testable. That is, can a tester, given oracle access to an alleged codeword w of the tree code, decide whether w is a codeword or far from such, while only reading a sub-linear number of symbols from w. As the main result of this work, we construct, for any r ≥ 3, a probabilistic tree code that is locally testable using Õ ( n 2/ r ) queries. The tester accepts any codeword with probability 1 and rejects strings that are δ r -far from the code with high probability, where δ r < 1 degrades with r. Our probabilistic notion of a tree code is a relaxation of the standard notion and allows the encoder to toss random coins. We require that encoded messages are far (in tree distance) from any possible encoding of any other message.

Details

STOC Conference 2024 Conference Paper

Batch Proofs Are Statistically Hiding

Nir Bitansky
Chethan Kamath
Omer Paneth
Ron D. Rothblum
Prashant Nalini Vasudevan

Batch proofs are proof systems that convince a verifier that x 1 ,…, x t ∈ L , for some NP language L , with communication that is much shorter than sending the t witnesses. In the case of statistical soundness (where the cheating prover is unbounded but the honest prover is efficient given the witnesses), interactive batch proofs are known for UP , the class of unique-witness NP languages. In the case of computational soundness (where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of NP , assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments: - Statistically sound batch proofs for L imply that L has a statistically witness indistinguishable ( SWI ) proof, with inverse polynomial SWI error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier SWI or for obtaining full-fledged SWI from public-coin protocols, whereas for private-coin protocols full-fledged SWI is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond UP (where witness indistinguishability is trivial). In particular, assuming that NP does not have SWI proofs, batch proofs for all of NP do not exist. - Computationally sound batch proofs (a.k.a batch arguments or BARG s) for NP , together with one-way functions, imply statistical zero-knowledge ( SZK ) arguments for NP with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive BARG s from one-way functions would yield constant-round SZK arguments from one-way functions. This would be surprising as SZK arguments are currently only known assuming constant-round statistically-hiding commitments. We further prove new positive implications of non-interactive batch arguments to non-interactive zero knowledge arguments (with explicit uniform prover and verifier): - Non-interactive BARG s for NP , together with one-way functions, imply non-interactive computational zero-knowledge arguments for NP . Assuming also dual-mode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language L into an SWI protocol for L .

Details

FOCS Conference 2024 Conference Paper

Dot-Product Proofs and Their Applications

Nir Bitansky
Prahladh Harsha
Yuval Ishai
Ron D. Rothblum
David J. Wu 0001

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $\boldsymbol{x}$ and the proof $\boldsymbol{\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle \boldsymbol{q}, (\boldsymbol{x}\Vert\boldsymbol{\pi})\rangle$ jointly to $\boldsymbol{x}$ and $\boldsymbol{\pi}$. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of D PPs, obtaining the following results: •Small-field DPP. For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a D PP for proving that there exists $\boldsymbol{w}$ such that $C(\boldsymbol{x}, \ \boldsymbol{w})=1$ with a proof $\boldsymbol{\pi}$ of length $S\cdot \text{poly}(\vert \mathbb{F}\vert)$ and soundness error $\varepsilon=O(1/\sqrt{\vert \mathbb{F}\vert })$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields. •Large-field DPP. If $\vert \mathbb{F}\vert\geq$ poly $(S/\varepsilon)$, there is a similar DPP with soundness error $\varepsilon$ and proof length $O(S)$ (in field elements). The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications. •Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field $\mathbb{F}$ up to some constant factor $c > 1$, independent of F. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH). •Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.

Details

STOC Conference 2022 Conference Paper

Proving as fast as computing: succinct arguments with constant prover overhead

Noga Ron-Zewi
Ron D. Rothblum

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language L ∈ NP , with communication that is much shorter than the NP witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness. In this work we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi-linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields. In more detail, for every Boolean circuit C = C ( x , w ), we construct an O (log| C |)-round argument-system in which the prover can be implemented by a size O (| C |) Boolean circuit (given as input both the instance x and the witness w ), with arbitrarily small constant soundness error and using poly (λ,log| C |) communication, where λ denotes the security parameter. The verifier can be implemented by a size O (| x |) + poly (λ, log| C |) circuit following a size O (| C |) private pre-processing step, or, alternatively, by using a purely public-coin protocol (with no pre-processing) with a size O (| C |) verifier. The protocol can be made zero-knowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linear-size circuits, such as those proposed by Applebaum et al. (ITCS, 2017). At the heart of our construction is a new information-theoretic interactive oracle proof (IOP), an interactive analog of a PCP, for circuit satisfiability, with constant prover overhead. The improved efficiency of our IOP is obtained by bypassing a barrier faced by prior IOP constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.

Details

FOCS Conference 2022 Conference Paper

Unstructured Hardness to Average-Case Randomness

Lijie Chen 0001
Ron D. Rothblum
Roei Tell

The leading technical approach in uniform hardness-to-randomness in the last two decades faced several well-known barriers that caused results to rely on overly strong hardness assumptions, and yet still yield suboptimal conclusions. In this work we show uniform hardness-to-randomness results that simultaneously break through all of the known barriers. Specifically, consider any one of the following three assumptions: 1)For some $\epsilon>0$ there exists a function f computable by uniform circuits of size $2^{O(n)}$ and depth $2^{o(n)}$ such that f is hard for probabilistic time $2^{\epsilon n}$. 2)For every $c\in \mathbb{N}$ there exists a function f computable by logspace-uniform circuits of polynomial size and depth n 2 such that every probabilistic algorithm running in time n c fails to compute f on $\mathrm{a}(1/n)$-fraction of the inputs. 3)For every $c\in \mathbb{N}$ there exists a logspace-uniform family of arithmetic formulas of degree n 2 over a field of size poly $(n)$ such that no algorithm running in probabilistic time n c can evaluate the family on a worst-case input. Assuming any of these hypotheses, where the hardness is for every sufficiently large input length $n\in \mathbb{N}$, we deduce that $\mathcal{R}\mathcal{P}$ can be derandomized in polynomial time and on all input lengths, on average. Furthermore, under the first assumption we also show that $\mathcal{B}\mathcal{P}\mathcal{P}$ can be derandomized in polynomial time, on average and on all input lengths, with logarithmically many advice bits. On the way to these results we also resolve two related open problems. First, we obtain an optimal worst-case to average-case reduction for computing problems in linear space by uniform probabilistic algorithms; this result builds on a new instance checker based on the doubly efficient proof system of Goldwasser, Kalai, and Rothblum (J. ACM, 2015). Secondly, we resolve the main open problem in the work of Carmosino, Impagliazzo and Sabin (ICALP 2018), by deducing derandomization from weak and general fine-grained hardness hypotheses. The full version of this paper is available online [5].

Details

STOC Conference 2021 Conference Paper

Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)

Justin Holmgren
Alex Lombardi
Ron D. Rothblum

In a seminal work, Goldreich, Micali and Wigderson (CRYPTO ’86) demonstrated the wide applicability of zero-knowledge proofs by constructing such a proof system for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question in the negative, assuming a standard cryptographic assumption (i.e., the hardness of learning with errors ( LWE )).

Details

FOCS Conference 2020 Conference Paper

Local Proofs Approaching the Witness Length [Extended Abstract]

Noga Ron-Zewi
Ron D. Rothblum

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). Efficient IOPs are at the core of leading practical implementations of highly efficient proof-systems. In this work we construct, for a large class of N P relations, IOPs in which the communication complexity approaches the witness length. More precisely, for any N P relation for which membership can be decided in polynomial-time and bounded polynomial space (e. g. , SAT, Hamiltonicity, Clique, Vertex-Cover, etc.) and for any constant, we construct an IOP with communication complexity (1+γ)·n, where n is the original witness length. The number of rounds, as well as the number of queries made by the IOP verifier, are constant. This result improves over prior works on short IOPs/PCPs in two ways. First, the communication complexity in these short IOPs is proportional to the complexity of verifying the NP witness, which can be polynomially larger than the witness size. Second, even ignoring the difference between witness length and non-deterministic verification time, prior works incur (at the very least) a large constant multiplicative overhead to the communication complexity. In particular, as a special case, we also obtain an IOP for CircuitSAT with communication complexity (1+γ)·t, for circuits of size t and any constant. This improves upon the prior state-of-the-art work of Ben Sasson et al. (ICALP, 2017) who construct an IOP for CircuitSAT with communication length c·t for a large (unspecified) constant c ≥ 1. Our proof leverages the local testability and (relaxed) local correctability of high-rate tensor codes, as well as their support of a sumcheck-like procedure. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e. g. , Reed-Solomon, Reed-Muller or AG codes) - a key building block of all known short PCP/IOP constructions.

Details

FOCS Conference 2020 Conference Paper

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract

Lijie Chen 0001
Ron D. Rothblum
Roei Tell
Eylon Yogev

The Exponential-Time Hypothesis (ETH) is a strengthening of the P ≠ NP conjecture, stating that 3-SAT on n variables cannot be solved in (uniform) time 2 ε·n, for some. In recent years, analogous hypotheses that are “exponentially-strong” forms of other classical complexity conjectures (such as NP ⊄ eq BPP or coNP ⊄ eq NP) have also been introduced, and have become widely influential. In this work, we focus on the interaction of exponential-time hypotheses with the fundamental and closely-related questions of derandomization and circuit lower bounds. We show that even relatively-mild variants of exponential-time hypotheses have far-reaching implications to derandomization, circuit lower bounds, and the connections between the two. Specifically, we prove that: 1) The Randomized Exponential-Time Hypothesis (rETH) implies that BPP can be simulated on “average-case” in deterministic (nearly-)polynomial-time (i. e. , in time 2 ~O(log(n)) =n loglog(n)O(1) ). The derandomization relies on a conditional construction of a pseudorandom generator with near-exponential stretch (i. e. , with seed length ~O(log(n))); this significantly improves the state-of-the-art in uniform “hardness-to-randomness” results, which previously only yielded pseudorandom generators with sub-exponential stretch from such hypotheses. 2) The Non-Deterministic Exponential-Time Hypothesis (NETH) implies that derandomization of BPP is completely equivalent to circuit lower bounds against E, and in particular that pseudorandom generators are necessary for derandomization. In fact, we show that the foregoing equivalence follows from a very weak version of NETH, and we also show that this very weak version is necessary to prove a slightly stronger conclusion that we deduce from it. Lastly, we show that disproving certain exponential-time hypotheses requires proving breakthrough circuit lower bounds. In particular, if CireuitSAT for circuits over n bits of size poly(n) can be solved by probabilistic algorithms in time 2 n/polylog(n), then BPε does not have circuits of quasilinear size.

Details

STOC Conference 2019 Conference Paper

Fiat-Shamir: from practice to theory

Ran Canetti
Yilei Chen 0001
Justin Holmgren
Alex Lombardi
Guy N. Rothblum
Ron D. Rothblum
Daniel Wichs

We give new instantiations of the Fiat-Shamir transform using explicit, efficiently computable hash functions. We improve over prior work by reducing the security of these protocols to qualitatively simpler and weaker computational hardness assumptions. As a consequence of our framework, we obtain the following concrete results. 1) There exists a succinct publicly verifiable non-interactive argument system for log-space uniform computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem. 2) There exists a non-interactive zero-knowledge argument system for in the common reference string model, under either of the following two assumptions: (i) Almost optimal hardness of search-LWE against polynomial-time adversaries, or (ii) The existence of a circular-secure FHE scheme with a standard (polynomial time, negligible advantage) level of security. 3) The classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP ’89] is not zero knowledge when repeated in parallel, under any of the hardness assumptions above.

Details

FOCS Conference 2018 Conference Paper

Delegating Computations with (Almost) Minimal Time and Space Overhead

Justin Holmgren
Ron D. Rothblum

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as a central problem in cryptography, with a flurry of recent activity in both theory and practice. In all of these works, the main bottleneck is the overhead incurred by the server, both in time and in space. Assuming (sub-exponential) LWE, we construct a one-round argument-system for proving the correctness of any time T and space S RAM computation, in which both the verifier and prover are highly efficient. The verifier runs in time n ⋅ polylog(T) and space polylog(T), where n is the input length. The prover runs in time quasilinear in T, in space S + o(S), and in some cases even space S + polylog(T). Our solution uses somewhat homomorphic encryption but, surprisingly, only requires homomorphic evaluation of arithmetic circuits having multiplicative depth (which is the main efficiency bottleneck in such schemes) that is lg(lg T)+O(1). Prior works based on standard assumptions had a poly(T) time prover, with an exponent of 3 at the very least. As for the space usage, we are unaware of any work, even based on non-standard assumptions, that has space usage S + polylog(T). Along the way to constructing our delegation scheme, we introduce several technical tools that we hope will be useful for future work.

Details

I&C Journal 2018 Journal Article

Proofs of proximity for context-free languages and read-once branching programs

Oded Goldreich
Tom Gur
Ron D. Rothblum

Proofs of proximity are proof systems wherein the verifier queries a sublinear number of bits, and soundness only asserts that inputs that are far from valid will be rejected. In their minimal form, called MA proofs of proximity ( MAP ), the verifier receives, in addition to query access to the input, also free access to a short (sublinear) proof. A more general notion is that of interactive proofs of proximity ( IPP ), wherein the verifier is allowed to interact with an omniscient, yet untrusted prover. We construct proofs of proximity for two natural classes of properties: (1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are: 1. MAP s for these two classes, in which, for inputs of length n, both the verifier's query complexity and the length of the MAP proof are O ˜ ( n ). 2. IPP s for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.

Details DOI

STOC Conference 2016 Conference Paper

Constant-round interactive proofs for delegating computation

Omer Reingold
Guy N. Rothblum
Ron D. Rothblum

The celebrated IP=PSPACE Theorem of Lund et-al. (J.ACM 1992) and Shamir (J.ACM 1992), allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems.

Details

STOC Conference 2014 Conference Paper

How to delegate computations: the power of no-signaling proofs

Yael Tauman Kalai
Ran Raz
Ron D. Rothblum

We construct a 1-round delegation scheme (i.e., argument system) for every language computable in time t = t ( n ), where the running time of the prover is poly( t ) and the running time of the verifier is n · polylog( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof (MIP) that is sound against no-signaling strategies, where the running time of the provers is poly( t ), the number of provers is polylog( t ), and the running time of the verifier is n · polylog( t ). In particular, this shows that the class of languages that have polynomial-time MIPs that are sound against no-signaling strategies, is exactly EXP. Previously, this class was only known to contain PSPACE. To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al (ICALP, 2000). This method relies on the existence of a sub-exponentially secure PIR scheme, and was proved secure by Kalai et al (STOC, 2013) assuming the underlying MIP is secure against no-signaling provers.

Details

STOC Conference 2013 Conference Paper

Delegation for bounded space

Yael Tauman Kalai
Ran Raz
Ron D. Rothblum

We construct a 1-round delegation scheme for every language computable in time t=t(n) and space s=s(n), where the running time of the prover is poly(t) and the running time of the verifier is ~O(n + poly(s)) (where ~O hides polylog(t) factors).

Details