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.

1 aAlagic, Gorjan1 aBai, Chen1 aKatz, Jonathan1 aMajenz, Christian uhttps://arxiv.org/abs/2112.0753001385nas a2200205 4500008004100000245004900041210004700090260001400137520077400151100002000925700001900945700001500964700002400979700001901003700001901022700002301041700001501064700001301079856008701092 2021 eng d00aEasyPQC: Verifying Post-Quantum Cryptography0 aEasyPQC Verifying PostQuantum Cryptography c9/20/20213 aEasyCrypt 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.

1 aBarbosa, Manuel1 aBarthe, Gilles1 aFan, Xiong1 aGrégoire, Benjamin1 aHung, Shih-Han1 aKatz, Jonathan1 aStrub, Pierre-Yves1 aWu, Xiaodi1 aZhou, Li uhttps://www.quics.umd.edu/publications/easypqc-verifying-post-quantum-cryptography01423nas a2200145 4500008004100000245005800041210005300099260001400152520098400166100001801150700003701168700001601205700001901221856003701240 2021 eng d00aRPPLNS: Pay-per-last-N-shares with a Randomised Twist0 aRPPLNS PayperlastNshares with a Randomised Twist c2/15/20213 a"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.

1 aLazos, Philip1 aMarmolejo-Cossío, Francisco, J.1 aZhou, Xinyu1 aKatz, Jonathan uhttps://arxiv.org/abs/2102.0768101524nas a2200145 4500008004100000245004700041210004400088260001500132520110100147100003701248700001801285700001901303700001901322856003701341 2019 eng d00aCompeting (Semi)-Selfish Miners in Bitcoin0 aCompeting SemiSelfish Miners in Bitcoin c06/11/20193 aThe 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.

1 aMarmolejo-Cossío, Francisco, J.1 aBrigham, Eric1 aSela, Benjamin1 aKatz, Jonathan uhttps://arxiv.org/abs/1906.0450201408nas a2200133 4500008004100000245008000041210006900121260001500190520097500205100001901180700001901199700001901218856003701237 2019 eng d00aStatistical Privacy in Distributed Average Consensus on Bounded Real Inputs0 aStatistical Privacy in Distributed Average Consensus on Bounded c03/20/20193 aThis 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.

1 aGupta, Nirupam1 aKatz, Jonathan1 aChopra, Nikhil uhttps://arxiv.org/abs/1903.0931501169nas a2200133 4500008004100000245009300041210006900134260001500203520072300218100001900941700001900960700001900979856003700998 2018 eng d00aInformation-Theoretic Privacy For Distributed Average Consensus: Bounded Integral Inputs0 aInformationTheoretic Privacy For Distributed Average Consensus B c03/28/20193 aWe 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.

1 aGupta, Nirupam1 aKatz, Jonathan1 aChopra, Nikhil uhttps://arxiv.org/abs/1809.0179406429nas a2200121 4500008004100000245006700041210006600108520603900174100001906213700001906232700001906251856003706270 2018 eng d00aInformation-Theoretic Privacy in Distributed Average Consensus0 aInformationTheoretic Privacy in Distributed Average Consensus3 aWe 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.

1 aChan, Hubert1 aKatz, Jonathan1 aNayak, Kartik1 aPolychroniadou, Antigoni1 aShi, Elaine uhttps://arxiv.org/abs/1809.00825