Jonathan Katz

ICML Conference 2023 Conference Paper

A Watermark for Large Language Models

• John Kirchenbauer
• Jonas Geiping
• Yuxin Wen
• Jonathan Katz
• Ian Miers
• Tom Goldstein

Potential harms of large language models can be mitigated by watermarking model output, i. e. , embedding signals into generated text that are invisible to humans but algorithmically detectable from a short span of tokens. We propose a watermarking framework for proprietary language models. The watermark can be embedded with negligible impact on text quality, and can be detected using an efficient open-source algorithm without access to the language model API or parameters. The watermark works by selecting a randomized set of "green" tokens before a word is generated, and then softly promoting use of green tokens during sampling. We propose a statistical test for detecting the watermark with interpretable p-values, and derive an information-theoretic framework for analyzing the sensitivity of the watermark. We test the watermark using a multi-billion parameter model from the Open Pretrained Transformer (OPT) family, and discuss robustness and security.

AAMAS Conference 2021 Conference Paper

RPPLNS: Pay-per-last-N-shares with a Randomised Twist

• Philip Lazos
• Francisco J. Marmolejo Cossío
• Xinyu Zhou
• Jonathan Katz

“Pay-per-last-𝑁-shares” (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies such as Bitcoin. As with any payment scheme, it is imperative to study issues of incentive compatibility of miners within the pool. For PPLNS this question has only been partially answered; we know that reasonably-sized miners within a PPLNS pool prefer following the pool protocol over employing specific deviations. In this paper, we present a novel modification to PPLNS where we randomise the protocol in a natural way. We call our protocol “Randomised pay-per-last-𝑁-shares” (RPPLNS), and note that the randomised structure of the protocol greatly simplifies the study of its incentive compatibility. We show that RPPLNS maintains the strengths of PPLNS (i. e. , fairness, variance reduction, and resistance to pool hopping), while also being robust against a richer class of strategic mining than what has been shown for PPLNS.

I&C Journal 2014 Journal Article

Authenticated broadcast with a partially compromised public-key infrastructure

• S. Dov Gordon
• Jonathan Katz
• Ranjit Kumaresan
• Arkady Yerukhimovich

Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. Existing protocols, however, do not distinguish between corrupted parties who do not follow the protocol, and honest parties whose secret (signing) keys have been compromised but continue to behave honestly. We explore conditions under which it is possible to construct broadcast protocols that still provide the usual guarantees (i. e. , validity/agreement) to the latter. Consider a network of n parties, where an adversary has compromised the secret keys of up to t c honest parties and, in addition, fully controls the behavior of up to t a other parties. We show that for any fixed t c > 0 and any fixed t a, there exists an efficient protocol for broadcast if and only if 2 t a + min ( t a, t c ) < n. (When t c = 0, standard results imply feasibility for all t a < n.) We also show that if t c, t a are not fixed, but are only guaranteed to satisfy the above bound, then broadcast is impossible to achieve except for a few specific values of n; for these “exceptional” values of n, we demonstrate broadcast protocols. Taken together, our results give a complete characterization of this problem.

FOCS Conference 2013 Conference Paper

Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy

• Raef Bassily
• Adam Groce
• Jonathan Katz
• Adam Smith 0006

We propose a new framework for defining privacy in statistical databases that enables reasoning about and exploiting adversarial uncertainty about the data. Roughly, our framework requires indistinguishability of the real world in which a mechanism is computed over the real dataset, and an ideal world in which a simulator outputs some function of a "scrubbed" version of the dataset (e. g. , one in which an individual user's data is removed). In each world, the underlying dataset is drawn from the same distribution in some class (specified as part of the definition), which models the adversary's uncertainty about the dataset. We argue that our framework provides meaningful guarantees in a broader range of settings as compared to previous efforts to model privacy in the presence of adversarial uncertainty. We also show that several natural, "noiseless" mechanisms satisfy our definitional framework under realistic assumptions on the distribution of the underlying data.

TCS Journal 2013 Journal Article

One-round multi-party communication complexity of distinguishing sums

• Daniel Apon
• Jonathan Katz
• Alex J. Malozemoff

We consider an instance of the following problem: Parties P 1, …, P k each receive an input x i, and a coordinator (distinct from each of these parties) wishes to compute f ( x 1, …, x k ) for some predicate f. We are interested in one-round protocols where each party sends a single message to the coordinator; there is no communication between the parties themselves. What is the minimum communication complexity needed to compute f, possibly with bounded error? We prove tight bounds on the one-round communication complexity when f corresponds to the promise problem of distinguishing sums (namely, determining which of two possible values the { x i } sum to) or the problem of determining whether the { x i } sum to a particular value. Similar problems were studied previously by Nisan and in concurrent work by Viola. Our proofs rely on basic theorems from additive combinatorics, but are otherwise elementary.

FOCS Conference 2013 Conference Paper

Rational Protocol Design: Cryptography against Incentive-Driven Adversaries

• Juan A. Garay 0001
• Jonathan Katz
• Ueli M. Maurer
• Björn Tackmann
• Vassilis Zikas

Existing work on "rational cryptographic protocols" treats each party (or coalition of parties) running the protocol as a selfish agent trying to maximize its utility. In this work we propose a fundamentally different approach that is better suited to modeling a protocol under attack from an external entity. Specifically, we consider a two-party game between an protocol designer and an external attacker. The goal of the attacker is to break security properties such as correctness or privacy, possibly by corrupting protocol participants; the goal of the protocol designer is to prevent the attacker from succeeding. We lay the theoretical groundwork for a study of cryptographic protocol design in this setting by providing a methodology for defining the problem within the traditional simulation paradigm. Our framework provides ways of reasoning about important cryptographic concepts (e. g. , adaptive corruptions or attacks on communication resources) not handled by previous game-theoretic treatments of cryptography. We also prove composition theorems that-for the first time-provide a sound way to design rational protocols assuming "ideal communication resources" (such as broadcast or authenticated channels) and then instantiate these resources using standard cryptographic tools. Finally, we investigate the problem of secure function evaluation in our framework, where the attacker has to pay for each party it corrupts. Our results demonstrate how knowledge of the attacker's incentives can be used to circumvent known impossibility results in this setting.

TCS Journal 2010 Journal Article

Bounds on the efficiency of black-box commitment schemes

• Omer Horvitz
• Jonathan Katz

Constructions of cryptographic primitives based on general assumptions (e. g. , one-way functions) tend to be less efficient than constructions based on specific (e. g. , number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) cryptographic constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of perfectly-binding schemes. Our bounds hold in an extension of the Impagliazzo–Rudich model: we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a statistically-binding commitment scheme could be constructed “from scratch”).

FOCS Conference 2010 Conference Paper

Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage

• Zvika Brakerski
• Yael Tauman Kalai
• Jonathan Katz
• Vinod Vaikuntanathan

In recent years, there has been a major effort to design cryptographic schemes that remain secure even when arbitrary information about the secret key is leaked (e. g. , via side-channel attacks). We explore the possibility of achieving security under \emph{continual} leakage from the \emph{entire} secret key by designing schemes in which the secret key is updated over time. In this model, we construct public-key encryption schemes, digital signatures, and identity-based encryption schemes that remain secure even if an attacker can leak a constant fraction of the secret memory (including the secret key) in each time period between key updates. We also consider attackers who may probe the secret memory during the updates themselves. We stress that we allow unrestricted leakage, without the assumption that ``only computation leaks information''. Prior to this work, constructions of public-key encryption schemes secure under continual leakage were not known even under this assumption.

I&C Journal 2009 Journal Article

Improving the round complexity of VSS in point-to-point networks

• Jonathan Katz
• Chiu-Yuen Koo
• Ranjit Kumaresan

We revisit the following question: what is the optimal round complexity of verifiable secret sharing (VSS)? We focus here on the case of perfect VSS where the number of corrupted parties t satisfies t < n / 3, with n the total number of parties. Work of Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006) shows that, assuming a broadcast channel, three rounds are necessary and sufficient for efficient VSS. Existing protocols, however, treat the broadcast channel as being available “for free” and do not attempt to minimize its usage. This approach leads to relatively poor round complexity when such protocols are compiled to run over a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also satisfies a certain “2-level sharing” property that makes it useful for constructing protocols for general secure computation.

STOC Conference 2008 Conference Paper

Complete fairness in secure two-party computation

• S. Dov Gordon
• Carmit Hazay
• Jonathan Katz
• Yehuda Lindell

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness , which guarantees that if either party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved in general in the two-party setting; specifically, he showed (essentially) that it is impossible to compute Boolean XOR with complete fairness. Since his work, the accepted folklore has been that nothing non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s.

STOC Conference 2007 Conference Paper

On achieving the "best of both worlds" in secure multiparty computation

• Jonathan Katz

Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type.

FOCS Conference 2007 Conference Paper

Round Complexity of Authenticated Broadcast with a Dishonest Majority

• Juan A. Garay 0001
• Jonathan Katz
• Chiu-Yuen Koo
• Rafail Ostrovsky

Broadcast among n parties in the presence of t ges n/3 malicious parties is possible only with some additional setup. The most common setup considered is the existence of a PKI and secure, digital signatures, where so-called authenticated broadcast is achievable for any t 2 ) rounds. In particular, we obtain expected constant-round pivtocols for t = n/2 + O(1). ldr On the negative side, we show that even randomized protocols require Omega(2n/(n-t)) rounds. This in particular rules out expected constant-round protocols when the fraction of honest parties is sub-constant.

STOC Conference 2003 Conference Paper

Lower bounds on the efficiency of encryption and digital signature schemes

• Rosario Gennaro
• Yael Gertner
• Jonathan Katz

A central focus of modern cryptography is to investigate the weakest possible assumptions under which various cryptographic algorithms exist. Typically, a proof that a "weak" primitive (e.g., a one-way function) implies the existence of a "strong" algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. In addition to showing the existence of such a construction, an equally important research direction is to explore the efficiency of such constructions.Among the most fundamental cryptographic algorithms are digital signature schemes and schemes for public- or private-key encryption. Here, we show the first lower bounds on the efficiency of any encryption or signature construction based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can invert π on a fraction larger than 1/S of its inputs), our results show that: Any public-key encryption scheme for m-bit messages must query π at least Ω(m log S) times.

STOC Conference 2000 Conference Paper

Complete characterization of security notions for probabilistic private-key encryption

• Jonathan Katz
• Moti Yung

STOC Conference 2000 Conference Paper

On the efficiency of local decoding procedures for error-correcting codes

• Jonathan Katz
• Luca Trevisan 0001