Arrow Research search

Author name cluster

Jonathan Katz

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.

13 papers
2 author rows

Possible papers

13

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.

Details

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.

PDF

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.

Details

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.

Details

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.

Details

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.

Details