© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2103.13994

A Unified Framework For Quantum Unforgeability

Mina Doosti, Mahshid Delavar, Elham Kashefi, Myrto Arapinis

Published Mar 25, 2021• 5 citations

Abstract

In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically, for classical message authentication codes and classical digital signatures schemes. We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions allowing us for the first time to present a complete quantum cryptanalysis framework for unforgeability. In particular, we prove how our definitions subsume previous ones while considering more fine-grained adversarial models, capturing the full spectrum of superposition attacks. The subtlety here resides in the characterisation of a forgery. We show that the strongest level of unforgeability, namely existential unforgeability, can only be achieved if only orthogonal to previously queried messages are considered to be forgeries. In particular, we present a non-trivial attack if any overlap between the forged message and previously queried ones is allowed. We further show that deterministic constructions can only achieve the weaker notion of unforgeability, that is selective unforgeability, against such restricted adversaries, but that selective unforgeability breaks if general quantum adversaries (capable of general superposition attacks) are considered. On the other hand, we show that PRF is sufficient for constructing a selective unforgeable classical primitive against full quantum adversaries. Moreover, we show similar positive results relying on Pseudorandom Unitaries (PRU) for quantum primitives. These results demonstrate the generality of our framework that could be applicable to other primitives beyond the cases analysed in this paper.

DOI: 10.48550/arxiv.2103.13994

Related papers

Classical Encryption and Authentication under Quantum Attacks

Maria Velema

Post-quantum cryptography studies the security of classical, i.e. non-quantum cryptographic protocols against quantum attacks. Until recently, the considered adversaries were assumed to use quantum computers and behave like classical adversaries otherwise. A more conservative approach is to assume that also the communication between the honest parties and the adversary is (partly) quantum. We discuss several options to define secure encryption and authentication against these stronger adversaries who can carry out 'superposition attacks'. We re-prove a recent result of Boneh and Zhandry, stating that a uniformly random function (and hence also a quantum-secure pseudorandom function) can serve as a message-authentication code which is secure, even if the adversary can evaluate this function in superposition.

arXiv:1307.3753•Jul 14, 2013•1 citation

Quantum-Secure Message Authentication Codes.

Dan Boneh, Mark Zhandry

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security. Keywords: Quantum computing, MAC,chosen message attacks, post-quantum security 1

Electronic colloquium on computational complexity•Jan 1, 2012•3 citations

Making Existential-Unforgeable Signatures Strongly Unforgeable in the Quantum Random-Oracle Model

Eaton, Edward, Fang Song

Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al., which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.

arXiv:1509.02944•Leibniz international proceedings in informatics•Jan 1, 2015•17 citations

Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World

Dan Boneh, Mark Zhandry

We initiate the study of quantum-secure digital signatures and quantum chosen ciphertext security. In the case of signatures, we enhance the standard chosen message query model by allowing the adversary to issue quantum chosen message queries: given a superposition of messages, the adversary receives a superposition of signatures on those messages. Similarly, for encryption, we allow the adversary to issue quantum chosen ciphertext queries: given a superposition of ciphertexts, the adversary receives a superposition of their decryptions. These adversaries model a natural ubiquitous quantum computing environment where end-users sign messages and decrypt ciphertexts on a personal quantum computer. We construct classical systems that remain secure when exposed to such quantum queries. For signatures, we construct two compilers that convert classically secure signatures into signatures secure in the quantum setting and apply these compilers to existing post-quantum signatures. We also show that standard constructions such as Lamport one-time signatures and Merkle signatures remain secure under quantum chosen message attacks, thus giving signatures whose quantum security is based on generic assumptions. For encryption, we define security under quantum chosen ciphertext attacks and present both public-key and symmetric-key constructions.

•Jan 1, 2013•40 citations

BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures

Cas J. F. Cremers, Samed Düzlü, Rune Fiedler +2 more

Modern digital signature schemes can provide more guarantees than the standard notion of (strong) unforgeability, such as offering security even in the presence of maliciously generated keys, or requiring to know a message to produce a signature for it. The use of signature schemes that lack these properties has previously enabled attacks on real-world protocols. In this work we revisit several of these notions beyond unforgeability, establish relations among them, provide the first formal definition of non re-signability, and a transformation that can provide these properties for a given signature scheme in a provable and efficient way.Our results are not only relevant for established schemes: for example, the ongoing NIST PQC competition towards standardizing post-quantum signature schemes has six finalists in its third round. We perform an in-depth analysis of the candidates with respect to their security properties beyond unforgeability. We show that many of them do not yet offer these stronger guarantees, which implies that the security guarantees of these post-quantum schemes are not strictly stronger than, but instead incomparable to, classical signature schemes. We show how applying our transformation would efficiently solve this, paving the way for the standardized schemes to provide these additional guarantees and thereby making them harder to misuse.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2021•46 citations

Secure Signatures and Chosen Ciphertext Security in a Post-Quantum World.

Dan Boneh, Mark Zhandry

We initiate the study of quantum-secure digital signatures and quantum chosen ciphertext security. In the case of signatures, we enhance the standard chosen message query model by allowing the adversary to issue quantum chosen message queries: given a superposition of messages, the adversary receives a superposition of signatures on those messages. Similarly, for encryption, we allow the adversary to issue quantum chosen ciphertext queries: given a superposition of ciphertexts, the adversary receives a superposition of their decryptions. These adversaries model a natural post-quantum environment where end-users sign messages and decrypt ciphertexts on a personal quantum computer. We construct classical systems that remain secure when exposed to such quantum queries. For signatures we construct two compilers that convert classically secure signatures into signatures secure in the quantum setting and apply these compilers to existing post-quantum signatures. We also show that standard constructions such as Lamport one-time signatures and Merkle signatures remain secure under quantum chosen message attacks, thus giving signatures whose quantum security is based on generic assumptions. For encryption, we define security under quantum chosen ciphertext attacks and present both public-key and symmetric-key constructions.

•Jan 1, 2013•3 citations

In this paper, we continue the line of work initiated by Boneh and Zhandry at CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of unforgeability against quantum adversaries specifically, for classical message authentication codes and classical digital signatures schemes. We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions allowing us for the first time to present a complete quantum cryptanalysis framework for unforgeability. In particular, we prove how our definitions subsume previous ones while considering more fine-grained adversarial models, capturing the full spectrum of superposition attacks. The subtlety here resides in the characterisation of a forgery. We show that the strongest level of unforgeability, namely existential unforgeability, can only be achieved if only orthogonal to previously queried messages are considered to be forgeries. In particular, we present a non-trivial attack if any overlap between the forged message and previously queried ones is allowed. We further show that deterministic constructions can only achieve the weaker notion of unforgeability, that is selective unforgeability, against such restricted adversaries, but that selective unforgeability breaks if general quantum adversaries (capable of general superposition attacks) are considered. On the other hand, we show that PRF is sufficient for constructing a selective unforgeable classical primitive against full quantum adversaries. Moreover, we show similar positive results relying on Pseudorandom Unitaries (PRU) for quantum primitives. These results demonstrate the generality of our framework that could be applicable to other primitives beyond the cases analysed in this paper.

Post-quantum cryptography studies the security of classical, i.e. non-quantum cryptographic protocols against quantum attacks. Until recently, the considered adversaries were assumed to use quantum computers and behave like classical adversaries otherwise. A more conservative approach is to assume that also the communication between the honest parties and the adversary is (partly) quantum. We discuss several options to define secure encryption and authentication against these stronger adversaries who can carry out 'superposition attacks'. We re-prove a recent result of Boneh and Zhandry, stating that a uniformly random function (and hence also a quantum-secure pseudorandom function) can serve as a message-authentication code which is secure, even if the adversary can evaluate this function in superposition.

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security. Keywords: Quantum computing, MAC,chosen message attacks, post-quantum security 1

Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al., which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.

We initiate the study of quantum-secure digital signatures and quantum chosen ciphertext security. In the case of signatures, we enhance the standard chosen message query model by allowing the adversary to issue quantum chosen message queries: given a superposition of messages, the adversary receives a superposition of signatures on those messages. Similarly, for encryption, we allow the adversary to issue quantum chosen ciphertext queries: given a superposition of ciphertexts, the adversary receives a superposition of their decryptions. These adversaries model a natural ubiquitous quantum computing environment where end-users sign messages and decrypt ciphertexts on a personal quantum computer. We construct classical systems that remain secure when exposed to such quantum queries. For signatures, we construct two compilers that convert classically secure signatures into signatures secure in the quantum setting and apply these compilers to existing post-quantum signatures. We also show that standard constructions such as Lamport one-time signatures and Merkle signatures remain secure under quantum chosen message attacks, thus giving signatures whose quantum security is based on generic assumptions. For encryption, we define security under quantum chosen ciphertext attacks and present both public-key and symmetric-key constructions.

Modern digital signature schemes can provide more guarantees than the standard notion of (strong) unforgeability, such as offering security even in the presence of maliciously generated keys, or requiring to know a message to produce a signature for it. The use of signature schemes that lack these properties has previously enabled attacks on real-world protocols. In this work we revisit several of these notions beyond unforgeability, establish relations among them, provide the first formal definition of non re-signability, and a transformation that can provide these properties for a given signature scheme in a provable and efficient way.Our results are not only relevant for established schemes: for example, the ongoing NIST PQC competition towards standardizing post-quantum signature schemes has six finalists in its third round. We perform an in-depth analysis of the candidates with respect to their security properties beyond unforgeability. We show that many of them do not yet offer these stronger guarantees, which implies that the security guarantees of these post-quantum schemes are not strictly stronger than, but instead incomparable to, classical signature schemes. We show how applying our transformation would efficiently solve this, paving the way for the standardized schemes to provide these additional guarantees and thereby making them harder to misuse.

We initiate the study of quantum-secure digital signatures and quantum chosen ciphertext security. In the case of signatures, we enhance the standard chosen message query model by allowing the adversary to issue quantum chosen message queries: given a superposition of messages, the adversary receives a superposition of signatures on those messages. Similarly, for encryption, we allow the adversary to issue quantum chosen ciphertext queries: given a superposition of ciphertexts, the adversary receives a superposition of their decryptions. These adversaries model a natural post-quantum environment where end-users sign messages and decrypt ciphertexts on a personal quantum computer. We construct classical systems that remain secure when exposed to such quantum queries. For signatures we construct two compilers that convert classically secure signatures into signatures secure in the quantum setting and apply these compilers to existing post-quantum signatures. We also show that standard constructions such as Lamport one-time signatures and Merkle signatures remain secure under quantum chosen message attacks, thus giving signatures whose quantum security is based on generic assumptions. For encryption, we define security under quantum chosen ciphertext attacks and present both public-key and symmetric-key constructions.