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

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 -