Arrow Research search

Author name cluster

Rafael Pass

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.

45 papers
2 author rows

Possible papers

45

TARK Conference 2025 Conference Paper

Causality Without Causal Models

  • Joseph Y. Halpern
  • Rafael Pass

Perhaps the most prominent current definition of (actual) causality is due to Halpern and Pearl. It is defined using causal models (also known as structural equations models). We abstract the definition, extracting its key features, so that it can be applied to any other model where counterfactuals are defined. By abstracting the definition, we gain a number of benefits. Not only can we apply the definition in a wider range of models, including ones that allow, for example, backtracking, but we can apply the definition to determine if A is a cause of B even if A and B are formulas involving disjunctions, negations, beliefs, and nested counterfactuals (none of which can be handled by the Halpern-Pearl definition). Moreover, we can extend the ideas to getting an abstract definition of explanation that can be applied beyond causal models. Finally, we gain a deeper understanding of features of the definition even in causal models.

Details DOI

FOCS Conference 2023 Conference Paper

Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

  • Marshall Ball
  • Yanyi Liu
  • Noam Mazor
  • Rafael Pass

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption-the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity. Roughly speaking, the promise problem requires telling apart tuples of strings $(\pi, x, y)$ with relatively (w. r. t. $\mathrm{K}(\pi)$) low time-bounded Interactive Kolmogorov Complexity $\left(\mathrm{IK}^{t}\right)$, and those with relatively high Kolmogorov complexity, given the promise that $\mathrm{K}^{t}(x \mid y)\lt s, \mathrm{~K}^{t}(y \mid x)\lt s$ and $s=\log n$, and where $\mathrm{IK}^{t}(\pi; x; y)$ is defined as the length of the shortest pair of t-bounded TMs $(A, B)$ such that the interaction of $(A, B)$ lead to the transcript $\pi$ and the respective outputs $x, y$. We demonstrate that when t is some polynomial, then not only does this hardness assumption imply the existence of KA, but it is also necessary for the existence of secure KA. As such, it yields the first natural hardness assumption characterizing the existence of key-agreement protocols. We additionally show that when the threshold s is bigger (e. g. , $s=55 \log n$), then the (worst-case) hardness of this problem instead characterizes the existence of one-way functions (OWFs). As such, our work also clarifies exactly what it would take to base KA on the existence of OWFs, and demonstrates that this question boils down to demonstrating a worst-case reduction between two closely related promise problems.

Details

FOCS Conference 2022 Conference Paper

Incrementally Verifiable Computation via Rate-1 Batch Arguments

  • Omer Paneth
  • Rafael Pass

Non-interactive delegation schemes enable producing succinct proofs (that can be efficiently verified) that a machine M transitions from c 1 to c 2 in a certain number of deterministic steps. We here consider the problem of efficiently merging such proofs: given a proof Π 1 that M transitions from c 1 to c 2, and a proof Π 2 that M transitions from c 2 to c 3, can these proofs be efficiently merged into a single short proof (of roughly the same size as the original proofs) that M transitions from c 1 to c 3? To date, the only known constructions of such a mergeable delegation scheme rely on strong non-falsifiable “knowledge extraction” assumptions. In this work, we present a provably secure construction based on the standard LWE assumption. As an application of mergeable delegation, we obtain a construction of incrementally verifiable computation (IVC) (with polylogarithmic length proofs) for any (unbounded) polynomial number of steps based on LWE; as far as we know, this is the first such construction based on any falsifiable (as opposed to knowledge-extraction) assumption. The central building block that we rely on, and construct based on LWE, is a rate-l batch argument (BARG): this is a non-interactive argument for NP that enables proving k NP statements $x_{1}, \ldots, x_{k}$ with communication/verifier complexity m + o(m), where m is the length of one witness. rate-1 BARGs are particularly useful as they can be recursively composed a super-constant number of times.

Details

STOC Conference 2021 Conference Paper

Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity

  • Yanyi Liu
  • Rafael Pass

Let MK t P[ s ] be the set of strings x such that K t ( x ) ≤ s (| x |), where K t ( x ) denotes the t -bounded Kolmogorov complexity of the truthtable described by x . Our main theorem shows that for an appropriate notion of mild average-case hardness, for every ε>0, polynomial t ( n ) ≥ (1+ε) n , and every “nice” class F of super-polynomial functions, the following are equivalent: (i) the existence of some function T ∈ F such that T -hard one-way functions (OWF) exists (with non-uniform security); (ii) the existence of some function T ∈ F such that MK t P[ T −1 ] is mildly average-case hard with respect to sublinear-time non-uniform algorithms (with running-time n δ for some 0<δ<1). For instance, existence of subexponentially-hard (resp. quasi-poly-nomially-hard) OWFs is equivalent to mild average-case hardness of MK t P[ poly log n ] (resp. MK t P[2 O (√log n ) )]) w.r.t. sublinear-time non-uniform algorithms. We additionally note that if we want to deduce T -hard OWFs where security holds w.r.t. uniform T -time probabilistic attackers (i.e., uniformly-secure OWFs), it suffices to assume sublinear time hardness of MK t P w.r.t. uniform probabilistic sublinear-time attackers. We complement this result by proving lower bounds that come surprisingly close to what is required to unconditionally deduce the existence of (uniformly-secure) OWFs: MK t P[ poly log n ] is worst-case hard w.r.t. uniform probabilistic sublinear-time algorithms, and MK t P[ n −log n ] is mildly average-case hard for all O ( t ( n )/ n 3 )-time deterministic algorithms.

Details

STOC Conference 2021 Conference Paper

Indistinguishability obfuscation from circular security

  • Romain Gay
  • Rafael Pass

We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: (a) the Learning with Errors (LWE) assumption (with subexponential modulus-to-noise ratio); (b) a circular security conjecture regarding the Gentry-Sahai-Waters' (GSW) encryption scheme and a Packed version of Regev's encryption scheme. The circular security conjecture states that a notion of leakage-resilient security, that we prove is satisfied by GSW assuming LWE, is retained in the presence of an encrypted key-cycle involving GSW and Packed Regev.

Details

FOCS Conference 2020 Conference Paper

Is it Easier to Prove Theorems that are Guaranteed to be True?

  • Rafael Pass
  • Muthuramakrishnan Venkitasubramaniam

Consider the following two fundamental open problems in complexity theory: •Does a hard-on-average language in NP imply the existence of one-way functions? •Does a hard-on-average language in NP imply a hard-on-average 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 one-way functions and problems in TFNP can be interpreted as promise-true 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 hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words, It is no easier to find witnesses (a. k. a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true. This result follows from a more general study of interactive puzzles-a generalization of average-case hardness in NP- and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols. As another consequence of this treatment, we show that the existence of $O(1)$ -round public-coin non-trivial arguments (i. e. , argument systems that are not proofs) imply the existence of a hard-on-average problem in NP/poly.

Details

FOCS Conference 2020 Conference Paper

On One-way Functions and Kolmogorov Complexity

  • Yanyi Liu
  • Rafael Pass

We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial $t(n)\geq(1+\varepsilon)n, \ \varepsilon > 0$, the following are equivalent: •One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); • $t$ -time bounded Kolmogorov Complexity, $K^{t}$, is mildly hard-on-average (i. e. , there exists a polynomial $p(n) > 0$ such that no PPT algorithm can compute $K^{t}$, for more than a $1-\frac{1}{p(n)}$ fraction of $n$ -bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.

Details

TARK Conference 2019 Conference Paper

A Conceptually Well-Founded Characterization of Iterated Admissibility Using an "All I Know" Operator

  • Joseph Y. Halpern
  • Rafael Pass

Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (IA), also known as iterated deletion of weakly dominated strategies, where uncertainty is represented using LPSs (lexicographic probability sequences). Their characterization holds in a rich structure called a complete structure, where all types are possible. In earlier work, we gave a characterization of iterated admissibility using an "all I know" operator, that captures the intuition that "all the agent knows" is that agents satisfy the appropriate rationality assumptions. That characterization did not need complete structures and used probability structures, not LPSs. However, that characterization did not deal with Samuelson's conceptual concern regarding IA, namely, that at higher levels, players do not consider possible strategies that were used to justify their choice of strategy at lower levels. In this paper, we give a characterization of IA using the all I know operator that does deal with Samuelson's concern. However, it uses LPSs. We then show how to modify the characterization using notions of "approximate belief" and "approximately all I know" so as to deal with Samuelson's concern while still working with probability structures.

Details DOI

TARK Conference 2017 Conference Paper

A Knowledge-Based Analysis of the Blockchain Protocol

  • Joseph Y. Halpern
  • Rafael Pass

At the heart of the Bitcoin is a blockchain protocol, a protocol for achieving consensus on a public ledger that records bitcoin transactions. To the extent that a blockchain protocol is used for applications such as contract signing and making certain transactions (such as house sales) public, we need to understand what guarantees the protocol gives us in terms of agents' knowledge. Here, we provide a complete characterization of agent's knowledge when running a blockchain protocol using a variant of common knowledge that takes into account the fact that agents can enter and leave the system, it is not known which agents are in fact following the protocol (some agents may want to deviate if they can gain by doing so), and the fact that the guarantees provided by blockchain protocols are probabilistic. We then consider some scenarios involving contracts and show that this level of knowledge suffices for some scenarios, but not others.

Details DOI

FOCS Conference 2017 Conference Paper

Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles

  • Huijia Lin
  • Rafael Pass
  • Pratik Soni

Non-malleable commitments are a fundamental cryptographic tool for preventing against (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991, the round-complexity of non-malleable commitments has been extensively studied, leading up to constant-round concurrent non-malleable commitments based only on one-way functions, and even 3-round concurrent non-malleable commitments based on subexponential one-way functions. But constructions of two-round, or non-interactive, nonmalleable commitments have so far remained elusive; the only known construction relied on a strong and non-falsifiable assumption with a non-malleability flavor. Additionally, a recent result by Pass shows the impossibility of basing two-round non-malleable commitments on falsifiable assumptions using a polynomial-time black-box security reduction. In this work, we show how to overcome this impossibility, using super-polynomial-time hardness assumptions. Our main result demonstrates the existence of a two-round concurrent non-malleable commitment based on subexponential “standard-type” assumptions-notably, assuming the existence of the following primitives (all with subexponential security): (1) non-interactive commitments, (2) ZAPs (i. e. , 2-round witness indistinguishable proofs), (3) collision-resistant hash functions, and (4) a “weak” time-lock puzzle. Primitives (1), (2), (3) can be based on e. g. , the discrete log assumption and the RSA assumption. Time-lock puzzles-puzzles that can be solved by “brute-force” in time 2t, but cannot be solved significantly faster even using parallel computers-were proposed by Rivest, Shamir, and Wagner in 1996, and have been quite extensively studied since; the most popular instantiation relies on the assumption that 2t repeated squarings mod N = pq require “roughly” 2t parallel time. Our notion of a “weak” time-lock puzzle, requires only that the puzzle cannot be solved in parallel time 2 t ϵ (and thus we only need to rely on the relatively mild assumption that there are no huge improvements in the parallel complexity of repeated squaring algorithms). We additionally show that if replacing assumption (2) for a non-interactive witness indistinguishable proof (NIWI), and (3) for a uniform collision-resistant hash function, then a non-interactive (i. e. , one-message) version of our protocol satisfies concurrent non-malleability w. r. t. uniform attackers.

Details

KR Conference 2016 Conference Paper

Sequential Equilibrium in Games of Imperfect Recall

  • Joseph Halpern
  • Rafael Pass

Definitions of sequential equilibrium and perfect equilibrium are given in games of imperfect recall. Subtleties regarding the definition are discussed.

TARK Conference 2015 Conference Paper

Bayesian Games with Intentions

  • Adam Bjorndahl
  • Joseph Y. Halpern
  • Rafael Pass

We show that standard Bayesian games cannot represent the full spectrum of belief-dependent preferences. However, by introducing a fundamental distinction between intended and actual strategies, we remove this limitation. We define Bayesian games with intentions, generalizing both Bayesian games and psychological games, and prove that Nash equilibria in psychological games correspond to a special class of equilibria as defined in our setting.

Details DOI

STOC Conference 2015 Conference Paper

Succinct Randomized Encodings and their Applications

  • Nir Bitansky
  • Sanjam Garg
  • Huijia Lin
  • Rafael Pass
  • Sidharth Telang

A randomized encoding allows to express a "complex" computation, given by a function f and input x, by a "simple to compute" randomized representation f(x) whose distribution encodes f(x), while revealing nothing else regarding f and x. Existing randomized encodings, geared mostly to allow encoding with low parallel-complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: the time required to encode . We construct succinct randomized encodings where the time to encode a computation, given by a program Π and input x, is essentially independent of Π's time complexity, and only depends on its space complexity, as well as the size of its input, output, and description. The scheme guarantees computational privacy of (Π,x), and is based on indistinguishability obfuscation for a relatively simple circuit class, for which there exist instantiations based on polynomial hardness assumptions on multi-linear maps.

Details

KR Conference 2014 Conference Paper

Axiomatizing Rationality

  • Adam Bjorndahl
  • Joseph Halpern
  • Rafael Pass

complexities of higher-order beliefs in a game-theoretic context. Formal logic furnishes a powerful and versatile class of such models; namely, modal logics of belief appropriately specialized for reasoning about games. Rationality is no less important in this setting; however, while it has been incorporated into these models both syntactically and semantically, no axiomatization of the resulting logical systems has been provided. This paper fills this gap. We take as our point of departure axioms for rationality in the sense of expected utility maximization given in (Bjorndahl, Halpern, & Pass 2011). We extend these axioms to arbitrary decision rules, under the assumption that the players’ uncertainty is represented by a probability measure. This allows us to deal with not just expected utility maximization, but other standard rules such as maximin and minimax regret (see (Halpern 2003) for a discussion of all the decision rules mentioned in this paper). We then go on to consider what happens when the players’ uncertainty is represented by a set of probabilities, which allows us to capture well-known decision rules such as maxmin expected utility and minimax expected regret. Finally, we consider situations where a player might be uncertain about which decision rules his opponents are using. The rest of this paper is organized as follows. In Section 2, we define the core concepts formally: games, modal logics of belief appropriate for reasoning about games, and the incorporation of rationality into these logics. Section 3 gives the axiomatization, and proves that it is sound and complete. In Section 4, we provide sound and complete axiomatizations for the cases where the players’ uncertainty is represented by sets of probabilities, and where players may be uncertain about the decision rules used by other players. In Section 5 we discuss the role of language. Section 6 concludes with a discussion of future work. More detailed proofs and further discussion can be found in the full paper, which is available at http: //www. math. cornell. edu/∼abjorndahl/Site/CV files/Axiomatizing%20Rationality. pdf. We provide a sound and complete axiomatization for a class of logics appropriate for reasoning about the rationality of players in games. Essentially the same axiomatization applies to a wide class of decision rules.

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

Details

FOCS Conference 2013 Conference Paper

Constant-Round Concurrent Zero Knowledge from P-Certificates

  • Kai-Min Chung
  • Huijia Lin
  • Rafael Pass

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, "succinct" non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.

Details

FOCS Conference 2013 Conference Paper

From Unprovability to Environmentally Friendly Protocols

  • Ran Canetti
  • Huijia Lin
  • Rafael Pass

An important security concern for crypto-graphic protocols is the extent to which they adversely affect the security of the systems in which they run. In particular, can we rule out the possibility that introducing a new protocol to a system might, as a "side effect", break the security of unsuspecting protocols in that system? Universally Composable (UC) security rules out such adverse side effects. However, many functionalities of interest provably cannot be realized with UC security unless the protocol participants are willing to put some trust in external computational entities. We propose a notion of security that: (a) allows realizing practically any functionality by protocols in the plain model without putting trust in any external entity; (b) guarantees that secure protocols according to this notion have no adverse side-effects on existing protocols in the system -- as long as the security of these existing protocols is proven via the traditional methodology of black box reduction to a game-based cryptographic hardness assumption with bounded number of rounds. Our security notion builds on the angel-based security notion of Prabhakaran and Sahai. A key part in our analysis is to come up with a CCA-secure commitment scheme that (a) cannot be proven secure via a black box reduction to a game-based assumption, but (b) can be proven secure using a non-black-box reduction. To the best of our knowledge, this is the first time that the interplay between black-box provability and unprovability is used to demonstrate security properties of protocols.

Details

TARK Conference 2013 Conference Paper

Game Theory with Translucent Players

  • Joseph Y. Halpern
  • Rafael Pass

Keywords A traditional assumption in game theory is that players are opaque to one another—if a player changes strategies, then this change in strategies does not affect the choice of other players’ strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i. e. , all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax dominated strategies: a strategy σi is minimax dominated for i if there exists a strategy σi0 for i such that minµ0−i ui (σi0, µ0−i ) > maxµ−i ui (σi, µ−i ). Epistemic logic, rationality, counterfactuals 1.

Details

FOCS Conference 2013 Conference Paper

Knowledge-Preserving Interactive Coding

  • Kai-Min Chung
  • Rafael Pass
  • Sidharth Telang

How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? If we encode each message in the communication protocol with a "good" error-correcting code (ECC), the error rate of the encoded protocol becomes poor (namely O(1/m) where m is the number of communication rounds). Towards addressing this issue, Schulman (FOCS'92, STOC'93) introduced the notion of interactive coding. We argue that whereas the method of separately encoding each message with an ECC ensures that the encoded protocol carries the same amount of information as the original protocol, this may no longer be the case if using interactive coding. In particular, the encoded protocol may completely leak a player's private input, even if it would remain secret in the original protocol. Towards addressing this problem, we introduce the notion of knowledge-preserving interactive coding, where the interactive coding protocol is required to preserve the "knowledge" transmitted in the original protocol. Our main results are as follows: The method of separately applying ECCs to each message has essentially optimal error rate: No knowledge-preserving interactive coding scheme can have an error rate of 1/m, where m is the number of rounds in the original protocol; If restricting to computationally-bounded (polynomial-time) adversaries, then assuming the existence of one-way functions (resp. sub exponentially-hard one-way functions), for every ϵ > 0, there exists a knowledge-preserving interactive coding schemes with constant error rate and information rate n -ϵ (resp. 1/polylog(n)) where n is the security parameter; additionally to achieve an error of even 1/m requires the existence of one-way functions; Finally, even if we restrict to computationally-bounded adversaries, knowledge-preserving interactive coding schemes with constant error rate can have an information rate of at most o(1 log n). This results applies even to non-constructive interactive coding schemes.

Details

TARK Conference 2013 Conference Paper

Language-based Games

  • Adam Bjorndahl
  • Joseph Y. Halpern
  • Rafael Pass

theory, beginning with [6] and expanded in [3], is an enrichment of the classical setting meant to capture these kinds of preferences and motivations. In a similar vein, work on reference-dependent preferences, as developed in [7], formalizes phenomena such as loss-aversion by augmenting players’ preferences with an additional sense of gain or loss derived by comparing the actual outcome to what was expected. In both of these theories, the method of generalization takes the same basic form: the domain of the utility functions is enlarged to include not only the outcomes of the game, but also the beliefs of the players. The resulting structure may be fairly complex; for instance, in psychological game theory, since the goal is to model preferences that depend not only on beliefs about outcomes, but also beliefs about beliefs, beliefs about beliefs about beliefs, and so on, the domain of the utility functions is extended to include infinite hierarchies of beliefs. The model we present in this paper, though motivated in part by a desire to capture belief-dependent preferences, is geared towards a much more general goal. Besides being expressive enough to subsume existing systems such as those described above, it establishes a general framework for modeling players with richer preferences. Moreover, it is equally capable of representing impoverished preferences, a canonical example of which are so-called “coarse beliefs” or “categorical thinking” [9]. More specifically, our formalism provides good practical and theoretical tools for handling beliefs as discrete rather than continuous objects, an advantage that is particularly relevant in the context of psychological effects in games. Despite this expressive power, the system is easy to use: player preferences are represented in a simple and natural manner, narrowing the divide between intuition and formalism. As a preliminary illustration of some of these points, consider the following simple example. We introduce language-based games, a generalization of psychological games [6] that can also capture referencedependent preferences [7]. The idea is to extend the domain of the utility function to situations, maximal consistent sets in some language. The role of the underlying language in this framework is thus particularly critical. Of special interest are languages that can express only coarse beliefs [9]. Despite the expressive power of the approach, we show that it can describe games in a simple, natural way. Nash equilibrium and rationalizability are generalized to this setting; Nash equilibrium is shown not to exist in general, while the existence of rationalizable strategies is proved under mild conditions.

Details

IJCAI Conference 2013 Conference Paper

Language-Based Games (Extended Abstract)

  • Adam Bjorndahl
  • Joseph Y. Halpern
  • Rafael Pass

We introduce language-based games, a generalization of psychological games [Geanakoplos et al. , 1989] that can also capture reference-dependent preferences [Kőszegi and Rabin, 2006], which extend the domain of the utility function to situations, maximal consistent sets in some language. The role of the underlying language in this framework is thus particularly critical. Of special interest are languages that can express only coarse beliefs [Mullainathan, 2002]. Despite the expressive power of the approach, we show that it can describe games in a simple, natural way. Nash equilibrium and rationalizability are generalized to this setting; Nash equilibrium is shown not to exist in general, while the existence of rationalizable strategies is proved under mild conditions.

PDF Details DOI

STOC Conference 2013 Conference Paper

Non-black-box simulation from one-way functions and applications to resettable security

  • Kai-Min Chung
  • Rafael Pass
  • Karn Seth

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

Details

IJCAI Conference 2013 Conference Paper

Sequential Equilibrium in Computational Games

  • Joseph Y. Halpern
  • Rafael Pass

We examine sequential equilibrium in the context of computational games [Halpern and Pass, 2011a], where agents are charged for computation. In such games, an agent can rationally choose to forget, so issues of imperfect recall arise. In this setting, we consider two notions of sequential equilibrium. One is an ex ante notion, where a player chooses his strategy before the game starts and is committed to it, but chooses it in such a way that it remains optimal even off the equilibrium path. The second is an interim notion, where a player can reconsider at each information set whether he is doing the “right” thing, and if not, can change his strategy. The two notions agree in games of perfect recall, but not in games of imperfect recall. Although the interim notion seems more appealing, in [Halpern and Pass, 2011b] it is argued that there are some deep conceptual problems with it in standard games of imperfect recall. We show that the conceptual problems largely disappear in the computational setting. Moreover, in this setting, under natural assumptions, the two notions coincide.

PDF Details DOI

FOCS Conference 2013 Conference Paper

Simultaneous Resettability from One-Way Functions

  • Kai-Min Chung
  • Rafail Ostrovsky
  • Rafael Pass
  • Ivan Visconti

Resettable-security, introduced by Canetti, Goldreich, Goldwasser and Micali (STOC'00), considers the security of cryptographic two-party protocols (in particular zero-knowledge arguments) in a setting where the attacker may “reset” or “rewind” one of the players. The strongest notion of resettable security, simultaneous resettability, introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS'01), requires resettable security to hold for both parties: in the context of zero-knowledge, both the soundness and the zero-knowledge conditions remain robust to resetting attacks. To date, all known constructions of protocols satisfying simultaneous resettable security rely on the existence of ZAPs; constructions of ZAPs are only known based on the existence of trapdoor permutations or number-theoretic assumptions. In this paper, we provide a new method for constructing protocols satisfying simultaneous resettable security while relying only on the minimal assumption of one-way functions. Our key results establish, assuming only one-way functions: Every language in NP has an ω(1)-round simultaneously resettable witness indistinguishable argument system; Every language in NP has a (polynomial-round) simultaneously resettable zero-knowledge argument system. The key conceptual insight in our technique is relying on black-box impossibility results for concurrent zero-knowledge to achieve resettable-security.

Details

AAAI Conference 2012 Conference Paper

I’m Doing as Well as I Can: Modeling People as Rational Finite Automata

  • Joe Halpern
  • Rafael Pass
  • Lior Seeman

We show that by modeling people as bounded finite automata, we can capture at a qualitative level the behavior observed in experiments. We consider a decision problem with incomplete information and a dynamically changing world, which can be viewed as an abstraction of many real-world settings. We provide a simple strategy for a finite automaton in this setting, and show that it does quite well, both through theoretical analysis and simulation. We show that, if the probability of nature changing state goes to 0 and the number of states in the automaton increases, then this strategy performs optimally (as well as if it were omniscient and knew when nature was making its state changes). Thus, although simple, the strategy is a sensible strategy for a resource-bounded agent to use. Moreover, at a qualitative level, the strategy does exactly what people have been observed to do in experiments.

PDF Details

IJCAI Conference 2011 Conference Paper

Approximately Strategy-Proof Voting

  • Eleanor Birrell
  • Rafael Pass

The classic Gibbard-Satterthwaite Theorem establishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have an incentive to lie about their true preferences. We consider a new approach for circumventing this result: we consider randomized voting rules that only approximate a deterministic voting rule and only are approximately strategy-proof. We show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule, and we provide asymptotically tight lower bounds on the parameters required by such voting rules.

PDF Details DOI

STOC Conference 2011 Conference Paper

Constant-round non-malleable commitments from any one-way function

  • Huijia Lin
  • Rafael Pass

We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

Details

STOC Conference 2011 Conference Paper

Limits of provable security from standard assumptions

  • Rafael Pass

We show that the security of some well-known cryptographic protocols, primitives and assumptions (e.g., the Schnorr identification scheme, commitments secure under adaptive selective-decommitment, the 'one-more' discrete logarithm assumption) cannot be based on any standard assumption using a Turing (i.e., black-box) reduction. These results follow from a general result showing that Turing reductions cannot be used to prove security of constant-round sequentially witness-hiding special-sound protocols for unique witness relations, based on standard assumptions; we emphasize that this result holds even if the protocol makes non-black-box use of the underlying assumption.

Details

TARK Conference 2011 Conference Paper

Reasoning about justified belief

  • Adam Bjorndahl
  • Joseph Y. Halpern
  • Rafael Pass

Halpern and Pass [8] introduce a logic of justified belief and go on to prove that strong rationalizability is characterized in this logic in terms of common justified belief of rationality (CJBR). Their paper provides semantics for this logic but no axiomatization. We correct this deficiency by reformulating the definition of justified belief and providing a complete axiomatization of this new system. We then prove a result analogous to the characterization of strong rationalizability in terms of CJBR, and analyze the additional assumptions needed to do so.

Details

FOCS Conference 2011 Conference Paper

The Randomness Complexity of Parallel Repetition

  • Kai-Min Chung
  • Rafael Pass

Consider a m-round interactive protocol with soundness error 1/2. How much extra randomness is required to decrease the soundness error to δ through parallel repetition? Previous work, initiated by Bell are, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, m · O(log (1/δ)) bits of extra randomness suffices. In this work, we initiate a more general study of the above question. We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with computational soundness (a. k. a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting. We show that obtaining even a sub-linear dependency on the number of rounds m (i. e. , o(m)·log(1/δ)) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting. We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting. These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.

Details

FOCS Conference 2010 Conference Paper

Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions

  • Ran Canetti
  • Huijia Lin
  • Rafael Pass

We construct the first general secure computation protocols that require no trusted infrastructure other than authenticated communication, and that satisfy a meaningful notion of security that is preserved under universal composition- assuming only the existence of enhanced trapdoor permutations. The notion of security fits within a generalization of the "angelbased" framework of Prabhakaran and Sahai (STOC'04) and implies super-polynomial time simulation security. Security notions of this kind are currently known to be realizable only under strong and specific hardness assumptions. A key element in our construction is a commitment scheme that satisfies a new and strong notion of security. The notion, security against chosen-commitment-attacks (CCA security), means that security holds even if the attacker has access to a extraction oracle that gives the adversary decommitment information to commitments of the adversary's choice. This notion is stronger than concurrent non-malleability and is of independent interest. We construct CCA-secure commitments based on standard one-way functions, and with no trusted set-up. To the best of our knowledge, this provides the first construction of a natural cryptographic primitive requiring adaptive hardness from standard hardness assumptions, using no trusted set-up or public keys.

Details

KR Conference 2010 Conference Paper

I Don't Want to Think About it Now: Decision Theory With Costly Computation

  • Joseph Halpern
  • Rafael Pass

Computation plays a major role in decision making. Even if an agent is willing to ascribe a probability to all states and a utility to all outcomes, and maximize expected utility, doing so might present serious computational problems. Moreover, computing the outcome of a given act might be difficult. In a companion paper we develop a framework for game theory with costly computation, where the objects of choice are Turing machines. Here we apply that framework to decision theory. We show how well-known phenomena like first-impression-matters biases (i. e., people tend to put more weight on evidence they hear early on), belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions), and the status quo bias (people are much more likely to stick with what they already have) can be easily captured in that framework. Finally, we use the framework to define some new notions: value of computational information (a computational variant of value of information) and computational value of conversation.

TARK Conference 2009 Conference Paper

A logical characterization of iterated admissibility

  • Joseph Y. Halpern
  • Rafael Pass

Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (i. e. , iterated deletion of weakly dominated strategies) where uncertainty is represented using LPSs (lexicographic probability sequences). Their characterization holds in a rich structure called a complete structure, where all types are possible. Here, a logical characterization of iterated admissibility is given that involves only standard probability and holds in all structures, not just complete structures. Roughly speaking, our characterization shows that iterated admissibility captures the intuition that “all the agent knows” is that agents satisfy the appropriate rationality assumptions.

Details

STOC Conference 2009 Conference Paper

A unified framework for concurrent security: universal composability from stand-alone non-malleability

  • Huijia Lin
  • Rafael Pass
  • Muthuramakrishnan Venkitasubramaniam

We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation--both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)--are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions.

Details

TARK Conference 2009 Conference Paper

An epistemic characterization of zero knowledge

  • Joseph Y. Halpern
  • Rafael Pass
  • Vasumathi Raman

Halpern, Moses and Tuttle presented a definition of interactive proofs using a notion they called practical knowledge, but left open the question of finding an epistemic formula that completely characterizes zero knowledge; that is, a formula that holds iff a proof is zero knowledge. We present such a formula, and show that it does characterize zero knowledge. Moreover, we show that variants of the formula characterize variants of zero knowledge such as concurrent zero knowledge [Dwork, Naor, and Sahai 2004] and proofs of knowledge [Feige, Fiat, and Shamir 1987; Tompa and Woll 1987].

Details

STOC Conference 2009 Conference Paper

Non-malleability amplification

  • Huijia Lin
  • Rafael Pass

We show a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length Ω(2 t ), while only incurring a constant overhead in round-complexity. As a result we obtain a construction of O(1) log* n -round (i.e., "essentially" constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.

Details

STOC Conference 2007 Conference Paper

An efficient parallel repetition theorem for Arthur-Merlin games

  • Rafael Pass
  • Muthuramakrishnan Venkitasubramaniam

We show a parallel-repetition theorem for constant-round Arthur-Merlin Games, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coinproofs of knowledge. The former of these results resolves an open questionposed by Bellare, Impagliazzo and Naor (FOCS '97).

Details

FOCS Conference 2007 Conference Paper

Cryptography from Sunspots: How to Use an Imperfect Reference String

  • Ran Canetti
  • Rafael Pass
  • Abhi Shelat

The common reference string (CRS) model equips all protocol participants with a common string that is sampled from a pre-specified distribution, say the uniform distribution. This model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security. However, knowing the precise distribution of the reference string seems crucial for all known protocols in this model, in the sense that current security analyses fail when the actual distribution of the reference string is allowed to differ from the specified one even by a small amount. This fact rules out many potential implementations of the CRS model, such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced. We study the possibility of obtaining universally composable (UC) security in a relaxed variant of the CRS model, where the reference string it taken from an adversarially specified distribution that's unknown to the protocol. On the positive side, we demonstrate that UC general secure computation is obtainable even when the reference string is taken from an arbitrary, adversarially chosen distribution, as long as (a) this distribution has some minimal min-entropy, (b) it has not too long a description, (c) it is efficiently samplable, and (d) the sampling algorithm is known to the adversary (and simulator). On the negative side, we show that if any one of these four conditions is removed then genera! UC secure computation becomes essentially impossible.

Details

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

Details

STOC Conference 2006 Conference Paper

Local zero knowledge

  • Silvio Micali
  • Rafael Pass

We put forward the notion of Local Zero Knowledge and provide its first implementations in a variety of settings under standard complexity assumptions.Whereas the classical notion of Zero Knowledge guarantees the secrecy only of information that is hard to compute, the new one meaningfully guarantees the secrecy of any information (in case of perfect zero-knowledge, and asymptotically in all other cases). Consequently, Local Zero Knowledge remains very meaningful even if DP = NP.

Details

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.

Details

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.

Details

STOC Conference 2004 Conference Paper

Bounded-concurrent secure multi-party computation with a dishonest majority

  • Rafael Pass

We show how to securely realize any multi-party functionality in a way that preserves security under an a-priori bounded number of concurrent executions, regardless of the number of corrupted parties. Previous protocols for the above task either rely on set-up assumptions such as a Common Reference String, or require an honest majority. Our constructions are in the plain model and rely on standard intractability assumptions (enhanced trapdoor permutations and collision resistant hash functions). Even though our main focus is on feasibility of concurrent multi-party computation we actually obtain a protocol using only a constant number of communication rounds. As a consequence our protocol yields the first construction of constant-round phstand-alone secure multi-party computation with a dishonest majority, proven secure under standard (polynomial-time) hardness assumptions; previous solutions to this task either require logarithmic round-complexity, or subexponential hardness assumptions. The core of our protocol is a novel construction of (concurrently) simulation-sound zero-knowledge protocols, which might be of independent interest. Finally, we extend the framework constructed to give a protocol for secure multi-party (and thus two-party) computation for any number of corrupted parties, which remains secure even when arbitrary subsets of parties concurrently execute the protocol, possibly with interchangeable roles. As far as we know, for the case of two-party or multi-party protocols with a dishonest majority, this is the first positive result for any non-trivial functionality which achieves this property in the plain model.

Details

FOCS Conference 2004 Conference Paper

Universally Composable Protocols with Relaxed Set-Up Assumptions

  • Boaz Barak
  • Ran Canetti
  • Jesper Buus Nielsen
  • Rafael Pass

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.

Details

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.

Details
v2026.09.13