01696nas a2200145 4500008004100000245005300041210005100094260001500145520127900160100001901439700001401458700001901472700002201491856003701513 2022 eng d00aPost-Quantum Security of the Even-Mansour Cipher0 aPostQuantum Security of the EvenMansour Cipher c12/14/20213 a

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.0753001152nas a2200157 4500008004100000245007900041210006900120260001400189520065900203100001900862700001400881700001900895700002200914700002000936856003800956 2022 eng d00aPost-Quantum Security of the (Tweakable) FX Construction, and Applications0 aPostQuantum Security of the Tweakable FX Construction and Applic c8/29/20223 a

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

1 aAlagic, Gorjan1 aBai, Chen1 aKatz, Jonathan1 aMajenz, Christian1 aStruck, Patrick uhttps://eprint.iacr.org/2022/109702266nas a2200133 4500008004100000245003400041210003300075260001400108520190700122100001902029700002502048700002202073856003702095 2021 eng d00aCan you sign a quantum state?0 aCan you sign a quantum state c12/6/20213 a

Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In a 2002 work, Barnum et al. argued informally that these strange features should imply that digital signatures for quantum states are impossible (Barnum et al., FOCS 2002). In this work, we perform the first rigorous study of the problem of signing quantum states. We first show that the intuition of Barnum et al. was correct, by proving an impossibility result which rules out even very weak forms of signing quantum states. Essentially, we show that any non-trivial combination of correctness and security requirements results in negligible security. This rules out all quantum signature schemes except those which simply measure the state and then sign the outcome using a classical scheme. In other words, only classical signature schemes exist. We then show a positive result: it is possible to sign quantum states, provided that they are also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion quantum signcryption. Classically, signcryption is only interesting if it provides superior efficiency to simultaneous encryption and signing. Our results imply that, quantumly, it is far more interesting: by the laws of quantum mechanics, it is the only signing method available. We develop security definitions for quantum signcryption, ranging from a simple one-time two-user setting, to a chosen-ciphertext-secure many-time multi-user setting. We also give secure constructions based on post-quantum public-key primitives. Along the way, we show that a natural hybrid method of combining classical and quantum schemes can be used to "upgrade" a secure classical scheme to the fully-quantum setting, in a wide range of cryptographic settings including signcryption, authenticated encryption, and chosen-ciphertext security.

1 aAlagic, Gorjan1 aGagliardoni, Tommaso1 aMajenz, Christian uhttps://arxiv.org/abs/1811.1185801905nas a2200157 4500008004100000245006300041210006300104260001300167300001200180490001000192520138200202100001901584700002201603700002301625856009901648 2020 eng d00aEfficient Simulation of Random States and Random Unitaries0 aEfficient Simulation of Random States and Random Unitaries c5/1/2020 a759-7870 v121073 a

We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.

This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.

In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.

These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/efficient-simulation-random-states-and-random-unitaries02359nas a2200169 4500008004100000245007400041210006900115260001300184300001300197490001000210520178100220100001902001700002202020700002302042700001502065856010902080 2020 eng d00aQuantum-Access-Secure Message Authentication via Blind-Unforgeability0 aQuantumAccessSecure Message Authentication via BlindUnforgeabili c5/1/2020 a788-817 0 v12-173 a

Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition.

We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hash-and-MAC” paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving.

Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://www.quics.umd.edu/publications/quantum-access-secure-message-authentication-blind-unforgeability02448nas a2200133 4500008004100000245006700041210006500108520202500173100001902198700002202217700002302239700001502262856003702277 2018 eng d00aQuantum-secure message authentication via blind-unforgeability0 aQuantumsecure message authentication via blindunforgeability3 a

Formulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries has been a challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with 0 divulges the value of the function on an input that starts with 1. We then propose a new definition, which we call "blind-unforgeability" (or BU.) This notion matches "intuitive unpredictability" in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use "partially blinded" oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using "Bernoulli-preserving" hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment. 

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://arxiv.org/abs/1803.0376101724nas a2200133 4500008004100000245003500041210003500076490001000111520132700121100001901448700002501467700002201492856007601514 2018 eng d00aUnforgeable Quantum Encryption0 aUnforgeable Quantum Encryption0 v108223 a

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i) ciphertext unforgeability, (ii) indistinguishability under adaptive chosen-ciphertext attack, and (iii) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies   INT-CTXT , (ii) implies   IND-CCA2 , and (iii) implies   AE . All of our new notions also imply   QIND-CPA  privacy. Combining one-time authentication and classical pseudorandomness, we construct symmetric-key quantum encryption schemes for each of these new security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

1 aAlagic, Gorjan1 aGagliardoni, Tommaso1 aMajenz, Christian uhttps://www.quics.umd.edu/publications/unforgeable-quantum-encryption-001828nas a2200121 4500008004100000245004800041210004700089490001000136520143200146100001901578700002201597856008701619 2017 eng d00aQuantum Non-malleability and Authentication0 aQuantum Nonmalleability and Authentication0 v104023 a

In encryption, non-malleability is a highly desirable property: it ensures that adversaries cannot manipulate the plaintext by acting on the ciphertext. In [6], Ambainis et al. gave a definition of non-malleability for the encryption of quantum data. In this work, we show that this definition is too weak, as it allows adversaries to “inject” plaintexts of their choice into the ciphertext. We give a new definition of quantum non-malleability which resolves this problem. Our definition is expressed in terms of entropic quantities, considers stronger adversaries, and does not assume secrecy. Rather, we prove that quantum non-malleability implies secrecy; this is in stark contrast to the classical setting, where the two properties are completely independent. For unitary schemes, our notion of non-malleability is equivalent to encryption with a two-design (and hence also to the definition of [6]).

Our techniques also yield new results regarding the closely-related task of quantum authentication. We show that “total authentication” (a notion recently proposed by Garg et al. [18]) can be satisfied with two-designs, a significant improvement over the eight-design construction of [18]. We also show that, under a mild adaptation of the rejection procedure, both total authentication and our notion of non-malleability yield quantum authentication as defined by Dupuis et al. [16].

1 aAlagic, Gorjan1 aMajenz, Christian uhttps://www.quics.umd.edu/publications/quantum-non-malleability-and-authentication01731nas a2200133 4500008004100000245003500041210003500076260001500111520136800126100001901494700002501513700002201538856003701560 2017 eng d00aUnforgeable Quantum Encryption0 aUnforgeable Quantum Encryption c2017/09/193 a

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i.) ciphertext unforgeability , (ii.) indistinguishability under adaptive chosen-ciphertext attack, and (iii.) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies INT-CTXT, (ii) implies IND-CCA2, and (iii) implies AE. All of our new notions also imply QIND-CPA privacy. Combining one-time authentication and classical pseudorandomness, we construct schemes for each of these new quantum security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

1 aAlagic, Gorjan1 aGagliardoni, Tommaso1 aMajenz, Christian uhttps://arxiv.org/abs/1709.06539