@article {3516, title = {A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles}, year = {2024}, month = {1/30/2024}, abstract = {

We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a \"lifting theorem\" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle.

}, url = {https://arxiv.org/abs/2401.14319}, author = {Jonathan Katz and Ben Sela} } @article {3313, title = {A Watermark for Large Language Models}, year = {2023}, month = {6/6/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2301.10226}, author = {John Kirchenbauer and Jonas Geiping and Yuxin Wen and Jonathan Katz and Ian Miers and Tom Goldstein} } @article {2931, title = {Post-Quantum Security of the Even-Mansour Cipher}, journal = {Eurocrypt}, year = {2022}, month = {12/14/2021}, abstract = {

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.\ 

}, doi = {https://doi.org/10.48550/arXiv.2112.07530}, url = {https://arxiv.org/abs/2112.07530}, author = {Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz} } @article {3201, title = {Post-Quantum Security of the (Tweakable) FX Construction, and Applications}, year = {2022}, month = {8/29/2022}, abstract = {

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\&$\#$39;s lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC

}, url = {https://eprint.iacr.org/2022/1097}, author = {Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz and Patrick Struck} } @article {2881, title = {EasyPQC: Verifying Post-Quantum Cryptography}, journal = {ACM CCS 2021}, year = {2021}, month = {9/20/2021}, abstract = {

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.

}, doi = {https://dx.doi.org/10.1145/3460120.3484567}, author = {Manuel Barbosa and Gilles Barthe and Xiong Fan and Benjamin Gr{\'e}goire and Shih-Han Hung and Jonathan Katz and Pierre-Yves Strub and Xiaodi Wu and Li Zhou} } @article {2767, title = {RPPLNS: Pay-per-last-N-shares with a Randomised Twist}, year = {2021}, month = {2/15/2021}, abstract = {

\"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.

}, url = {https://arxiv.org/abs/2102.07681}, author = {Philip Lazos and Francisco J. Marmolejo-Coss{\'\i}o and Xinyu Zhou and Jonathan Katz} } @article {2407, title = {Competing (Semi)-Selfish Miners in Bitcoin}, year = {2019}, month = {06/11/2019}, abstract = {

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.\ 

}, url = {https://arxiv.org/abs/1906.04502}, author = {Francisco J. Marmolejo-Coss{\'\i}o and Eric Brigham and Benjamin Sela and Jonathan Katz} } @article {2367, title = {Statistical Privacy in Distributed Average Consensus on Bounded Real Inputs}, year = {2019}, month = {03/20/2019}, abstract = {

This paper proposes a privacy protocol for distributed average consensus algorithms on bounded real-valued inputs that guarantees statistical privacy of honest agents\&$\#$39; 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\&$\#$39; 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\&$\#$39; inputs, where bounds are known apriori to all the agents.\ 

}, url = {https://arxiv.org/abs/1903.09315}, author = {Nirupam Gupta and Jonathan Katz and Nikhil Chopra} } @article {2368, title = {Information-Theoretic Privacy For Distributed Average Consensus: Bounded Integral Inputs}, year = {2018}, month = {03/28/2019}, abstract = {

We propose an asynchronous distributed average consensus algorithm that guarantees information-theoretic privacy of honest agents\&$\#$39; 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\&$\#$39; 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\&$\#$39; inputs are bounded integers, where the bounds are apriori known to all the agents.

}, url = {https://arxiv.org/abs/1809.01794}, author = {Nirupam Gupta and Jonathan Katz and Nikhil Chopra} } @article {2212, title = {Information-Theoretic Privacy in Distributed Average Consensus}, year = {2018}, abstract = {

We propose an asynchronous distributed average consensus algorithm that guarantees information-theoretic privacy of honest agents\&$\#$39; 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\&$\#$39; 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.\ 

}, url = {https://arxiv.org/abs/1809.01794}, author = {Nirupam Gupta and Jonathan Katz and Nikhil Chopra} } @article {2214, title = {More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting}, year = {2018}, abstract = {

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.\ 

}, url = {https://arxiv.org/abs/1809.00825}, author = {Hubert Chan and Jonathan Katz and Kartik Nayak and Antigoni Polychroniadou and Elaine Shi} }