Alon Rosen

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.

STOC Conference 2019 Conference Paper

Finding a Nash equilibrium is no easier than breaking Fiat-Shamir

• Arka Rai Choudhuri
• Pavel Hubácek
• Chethan Kamath
• Krzysztof Pietrzak
• Alon Rosen
• Guy N. Rothblum

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography. We show that solving the END − OF − METERED − LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in # P gives rise to a hard distribution in the class CLS , which is contained in PPAD . Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to # SAT . Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly ( n ). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly ( n ).

STOC Conference 2017 Conference Paper

Average-case fine-grained hardness

• Marshall Ball
• Alon Rosen
• Manuel Sabin
• Prashant Nalini Vasudevan

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.

FOCS Conference 2015 Conference Paper

On the Cryptographic Hardness of Finding a Nash Equilibrium

• Nir Bitansky
• Omer Paneth
• Alon Rosen

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is complete. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong "virtual black-box" notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps. Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.

FOCS Conference 2014 Conference Paper

An Algebraic Approach to Non-malleability

• Vipul Goyal
• Silas Richelson
• Alon Rosen
• Margarita Vald

In their seminal work on non-malleable cryptography, Dolev, Dwork and Naor, showed how to construct a non-malleable commitment with logarithmically-many "rounds"/"slots", the idea being that any adversary may successfully maul in some slots but would fail in at least one. Since then new ideas have been introduced, ultimately resulting in constant-round protocols based on any one-way function. Yet, in spite of this remarkable progress, each of the known constructions of non-malleable commitments leaves something to be desired. In this paper we propose a new technique that allows us to construct a non-malleable protocol with only a single "slot", and to improve in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge argument (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols. Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers' tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.

STOC Conference 2014 Conference Paper

On the existence of extractable one-way functions

• Nir Bitansky
• Ran Canetti
• Omer Paneth
• Alon Rosen

A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y . When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.

FOCS Conference 2014 Conference Paper

One-Way Functions and (Im)Perfect Obfuscation

• Ilan Komargodski
• Tal Moran
• Moni Naor
• Rafael Pass
• Alon Rosen
• Eylon Yogev

A program obfuscator takes a program and outputs a "scrambled" version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. (CRYPTO 2001), the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. Recently, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. (FOCS 2013). This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters, STOC 2014). Most of them explicitly rely on additional hardness assumptions, such as one-way functions. Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if P ≠ NP, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if P ≠ NP and program obfuscation is possible, then one-way functions exist. Our main result is that if NP ⊈; io-BPP and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for NP. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the average NP problems. To get some of our results we need obfuscators for simple programs such as 3CNF formulas

FOCS Conference 2010 Conference Paper

Sequential Rationality in Cryptographic Protocols

• Ronen Gradwohl
• Noam Livne
• Alon Rosen

Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers. We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of sub game perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat-free Nash equilibrium that is more permissive but still eliminates the undesirable "empty threats'' of non-sequential solution concepts. To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria (Dodis-Halevi-Rabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a non-trivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.

STOC Conference 2007 Conference Paper

Lattices that admit logarithmic worst-case to average-case connection factors

• Chris Peikert
• Alon Rosen

We exhibit an average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n -dimensional lattices in the worst case, for γ(n) = O(√log n). The previously best known factor for any non-trivial class of lattices was γ(n) = Õ(n).

FOCS Conference 2006 Conference Paper

Input-Indistinguishable Computation

• Silvio Micali
• Rafael Pass
• Alon Rosen

We put forward a first definition of general secure computation that, without any trusted set-up, handles an arbitrary number of concurrent executions; and is implementable based on standard complexity assumptions. In contrast to previous definitions of secure computation, ours is not simulation-based

FOCS Conference 2005 Conference Paper

Concurrent Non-Malleable Commitments

• Rafael Pass
• Alon Rosen

We present a non-malleable commitment scheme that retains its security properties even when concurrently executed a polynomial number of times. That is, a man-in-the-middle adversary who is simultaneously participating in multiple concurrent commitment phases of our scheme, both as a sender and as a receiver cannot make the values he commits to depend on the values he receives commitments to. Our result is achieved without assuming an a-priori bound on the number of executions and without relying on any set-up assumptions. Our construction relies on the existence of standard collision resistant hash functions and only requires a constant number of communication rounds.

STOC Conference 2005 Conference Paper

New and improved constructions of non-malleable cryptographic protocols

• Rafael Pass
• Alon Rosen

We present a new constant round protocol for non-malleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for non-malleable commitments. Our constructions rely on the existence of (standard) collision resistant hash functions. Previous constructions either relied on the existence of trapdoor permutations and hash functions that are collision resistant against sub-exponential sized circuits, or required a super-constant number of rounds.Additional results are the first construction of a non-malleable commitment scheme that is statistically hiding (with respect to opening), and the first non-malleable protocols that satisfy a strict polynomial-time simulation requirement. The latter are constructed by additionally assuming the existence of trapdoor permutations.Our approach differs from the approaches taken in previous works in that we view non-malleable zero-knowledge as a building-block rather than an end goal. This gives rise to a modular construction of non-malleable commitments and results in a somewhat simpler analysis.The techniques that we use to construct our zero-knowl-edge protocol are non black-box, but are different than the non black-box techniques previously used in the context of non-malleable coin-tossing.

STOC Conference 2004 Conference Paper

Completeness in two-party secure computation: a computational view

• Danny Harnik
• Moni Naor
• Omer Reingold
• Alon Rosen

A Secure Function Evaluation (SFE) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". A rich body of work deals with the study of completeness for secure two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.The previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity ) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.

FOCS Conference 2003 Conference Paper

Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds

• Rafael Pass
• Alon Rosen

We consider the problem of constructing a general protocol for secure two-party computation in a way that preserves security under concurrent composition. In our treatment, we focus on the case where an a-priori bound on the number of concurrent sessions is specified before the protocol is constructed. (a. k. a. bounded concurrency). We make no setup assumptions. Lindel (STOC 2003) has shown that any protocol for bounded-concurrent secure two-party computation, whose security is established via black-box simulation, must have round complexity that is strictly larger than the bound on the number of concurrent sessions. In this paper, we construct a (non black-box) protocol for realizing bounded-concurrent secure two-party computation in a constant number of rounds. Our constructions rely on the existence of enhanced trapdoor permutations, as well as on the existence of hash functions that are collision-resistant against subexponential sized circuits.

FOCS Conference 2002 Conference Paper

Concurrent Zero Knowledge with Logarithmic Round-Complexity

• Manoj Prabhakaran 0001
• Alon Rosen
• Amit Sahai

We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using O/spl tilde/(log n) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP requires at least /spl Omega//spl tilde/(log n) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw free functions. Assuming only the existence of one-way functions, we show the existence of O/spl tilde/(log n)-round concurrent zero-knowledge arguments for all languages in NP.

STOC Conference 2001 Conference Paper

Black-box concurrent zero-knowledge requires Omega~(log n) rounds

• Ran Canetti
• Joe Kilian
• Erez Petrank
• Alon Rosen

We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least \tildeΩ(log n ) rounds of interaction. This result substantially improves over previous lower bounds, and is the first bound to rule out the possibility of constant-round black-box concurrent zero-knowledge. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ~$\NP$.

STOC Conference 2000 Conference Paper

Pseudo-random functions and factoring (extended abstract)

• Moni Naor
• Omer Reingold
• Alon Rosen