TY - JOUR T1 - A Watermark for Large Language Models Y1 - 2023 A1 - John Kirchenbauer A1 - Jonas Geiping A1 - Yuxin Wen A1 - Jonathan Katz A1 - Ian Miers A1 - Tom Goldstein AB -

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.

UR - https://arxiv.org/abs/2301.10226 ER - TY - JOUR T1 - Post-Quantum Security of the Even-Mansour Cipher JF - Eurocrypt Y1 - 2022 A1 - Gorjan Alagic A1 - Chen Bai A1 - Jonathan Katz A1 - Christian Majenz AB -

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation~P:{0,1}n→{0,1}n. It is secure against classical attacks, with optimal attacks requiring qE queries to E and qP queries to P such that qE⋅qP≈2n. If the attacker is given \emph{quantum} access to both E and P, however, the cipher is completely insecure, with attacks using qE,qP=O(n) queries known. In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation~E implemented by honest parties, even while retaining quantum access to~P. Attacks in this setting with qE⋅q2P≈2n are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural, "post-quantum" setting. We resolve this question, showing that any attack in that setting requires qE⋅q2P+qP⋅q2E≈2n. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest. 

UR - https://arxiv.org/abs/2112.07530 U5 - https://doi.org/10.48550/arXiv.2112.07530 ER - TY - JOUR T1 - Post-Quantum Security of the (Tweakable) FX Construction, and Applications Y1 - 2022 A1 - Gorjan Alagic A1 - Chen Bai A1 - Jonathan Katz A1 - Christian Majenz A1 - Patrick Struck AB -

The FX construction provides a way to increase the effective key length of a block cipher E. We prove security of a tweakable version of the FX construction in the post-quantum setting, i.e., against a quantum attacker given only classical access to the secretly keyed construction while retaining quantum access to E, a setting that seems to be the most relevant one for real-world applications. We then use our results to prove post-quantum security—in the same model—of the (plain) FX construction, Elephant (a finalist of NIST's lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC

UR - https://eprint.iacr.org/2022/1097 ER - TY - JOUR T1 - EasyPQC: Verifying Post-Quantum Cryptography JF - ACM CCS 2021 Y1 - 2021 A1 - Manuel Barbosa A1 - Gilles Barthe A1 - Xiong Fan A1 - Benjamin Grégoire A1 - Shih-Han Hung A1 - Jonathan Katz A1 - Pierre-Yves Strub A1 - Xiaodi Wu A1 - Li Zhou AB -

EasyCrypt is a formal verification tool used extensively for formalizing concrete security proofs of cryptographic constructions. However, the EasyCrypt formal logics consider only classical attackers, which means that post-quantum security proofs cannot be formalized and machine-checked with this tool. In this paper we prove that a natural extension of the EasyCrypt core logics permits capturing a wide class of post-quantum cryptography proofs, settling a question raised by (Unruh, POPL 2019). Leveraging our positive result, we implement EasyPQC, an extension of EasyCrypt for post-quantum security proofs, and use EasyPQC to verify post-quantum security of three classic constructions: PRF-based MAC, Full Domain Hash and GPV08 identity-based encryption.

U5 - https://dx.doi.org/10.1145/3460120.3484567 ER - TY - JOUR T1 - RPPLNS: Pay-per-last-N-shares with a Randomised Twist Y1 - 2021 A1 - Philip Lazos A1 - Francisco J. Marmolejo-Cossío A1 - Xinyu Zhou A1 - Jonathan Katz AB -

"Pay-per-last-N-shares" (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies. 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-N-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.

UR - https://arxiv.org/abs/2102.07681 ER - TY - JOUR T1 - Competing (Semi)-Selfish Miners in Bitcoin Y1 - 2019 A1 - Francisco J. Marmolejo-Cossío A1 - Eric Brigham A1 - Benjamin Sela A1 - Jonathan Katz AB -

The Bitcoin protocol prescribes certain behavior by the miners who are responsible for maintaining and extending the underlying blockchain; in particular, miners who successfully solve a puzzle, and hence can extend the chain by a block, are supposed to release that block immediately. Eyal and Sirer showed, however, that a selfish miner is incentivized to deviate from the protocol and withhold its blocks under certain conditions. The analysis by Eyal and Sirer, as well as in followup work, considers a \emph{single} deviating miner (who may control a large fraction of the hashing power in the network) interacting with a remaining pool of honest miners. Here, we extend this analysis to the case where there are \emph{multiple} (non-colluding) selfish miners. We find that with multiple strategic miners, specific deviations from honest mining by multiple strategic agents can outperform honest mining, even if individually miners would not be incentivised to be dishonest. This previous point effectively renders the Bitcoin protocol to be less secure than previously thought. 

UR - https://arxiv.org/abs/1906.04502 ER - TY - JOUR T1 - Statistical Privacy in Distributed Average Consensus on Bounded Real Inputs Y1 - 2019 A1 - Nirupam Gupta A1 - Jonathan Katz A1 - Nikhil Chopra AB -

This paper proposes a privacy protocol for distributed average consensus algorithms on bounded real-valued inputs that guarantees statistical privacy of honest agents' inputs against colluding (passive adversarial) agents, if the set of colluding agents is not a vertex cut in the underlying communication network. This implies that privacy of agents' inputs is preserved against t number of arbitrary colluding agents if the connectivity of the communication network is at least (t+1). A similar privacy protocol has been proposed for the case of bounded integral inputs in our previous paper~\cite{gupta2018information}. However, many applications of distributed consensus concerning distributed control or state estimation deal with real-valued inputs. Thus, in this paper we propose an extension of the privacy protocol in~\cite{gupta2018information}, for bounded real-valued agents' inputs, where bounds are known apriori to all the agents. 

UR - https://arxiv.org/abs/1903.09315 ER - TY - JOUR T1 - Information-Theoretic Privacy For Distributed Average Consensus: Bounded Integral Inputs Y1 - 2018 A1 - Nirupam Gupta A1 - Jonathan Katz A1 - Nikhil Chopra AB -

We propose an asynchronous distributed average consensus algorithm that guarantees information-theoretic privacy of honest agents' inputs against colluding passive adversarial agents, as long as the set of colluding passive adversarial agents is not a vertex cut in the underlying communication network. This implies that a network with (t+1)-connectivity guarantees information-theoretic privacy of honest agents' inputs against any t colluding agents. The proposed protocol is formed by composing a distributed privacy mechanism we provide with any (non-private) distributed average consensus algorithm. The agent' inputs are bounded integers, where the bounds are apriori known to all the agents.

UR - https://arxiv.org/abs/1809.01794 ER - TY - JOUR T1 - Information-Theoretic Privacy in Distributed Average Consensus Y1 - 2018 A1 - Nirupam Gupta A1 - Jonathan Katz A1 - Nikhil Chopra AB -

We propose an asynchronous distributed average consensus algorithm that guarantees information-theoretic privacy of honest agents' inputs against colluding semi-honest (passively adversarial) agents, as long as the set of colluding semi-honest agents is not a vertex cut in the underlying communication network. This implies that a network with (t+1)-connectivity guarantees information-theoretic privacy of honest agents' inputs against any t colluding semi-honest agents. The proposed protocol is formed by composing a distributed privacy mechanism we provide with any (non-private) distributed average consensus algorithm. 

UR - https://arxiv.org/abs/1809.01794 ER - TY - JOUR T1 - More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting Y1 - 2018 A1 - Hubert Chan A1 - Jonathan Katz A1 - Kartik Nayak A1 - Antigoni Polychroniadou A1 - Elaine Shi AB -

The problem of Oblivious RAM (ORAM) has traditionally been studied in a single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case. In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process, we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting. 

UR - https://arxiv.org/abs/1809.00825 ER -