Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

Quantum-Secure Message Authentication Codes.

Dan Boneh, Mark Zhandry

Published Jan 1, 2012• 3 citations
OpenAlex

Abstract

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

Related papers

New security notions and feasibility results for authentication of quantum data

Sumegha Garg, Henry Yuen, Mark Zhandry

We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) and well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds. Next, we present several protocols satisfying our security definitions. We show that the classical Wegman-Carter authentication scheme with 3-universal hashing is secure against superposition attacks, as well as adversaries with quantum side information. We then present conceptually simple constructions of full quantum state authentication. Finally, we prove a lifting theorem which shows that, as long as a protocol can securely authenticate the maximally entangled state, it can securely authenticate any state, even those that are entangled with the adversary. Thus, this shows that protocols satisfying a fairly weak form of authentication security automatically satisfy a stronger notion of security (in particular, the definition of Dupuis, et al (2012)).

arXiv:1607.07759•Jul 26, 2016•6 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

Quantum Message Authentication Code Independent of Computational Difficulty

Ping Wang, Yuxuan Lu, Yian Lei +1 more

The rise of quantum computing poses significant challenges to security systems, with traditional message authentication codes (MACs) at unprecedented risk of compromise. This paper proposes a quantum message authentication code (QMAC) leveraging quantum mechanics to achieve robust security. The QMAC uses quantum one-way functions (QOWFs) to convert encrypted classical bits into qubits. This approach fundamentally differs from the computational hardness assumptions of conventional MACs. The QMAC's security is computationally difficulty-independent based on the inherent properties of quantum mechanics, making it impervious to exhaustive search attacks. Additionally, the protocol integrates authentication directly into the secure communication framework, obviating the need for extra particles and reducing computational complexity compared to stabilizer code-based or controlled unitary operations. Through a rigorous security analysis, we demonstrate the resilience of the proposed QMAC protocol against a wide range of adversarial strategies, including interception-resend attacks, identity impersonation, and entanglement-based attacks, among others.

IEEE photonics journal•Jan 14, 2026•0 citations

A Unified Framework For Quantum Unforgeability

Mina Doosti, Mahshid Delavar, Elham Kashefi +1 more

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.

arXiv:2103.13994•Mar 25, 2021•5 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

Robust message authentication in the context of quantum key distribution

Dillibabu Shanmugam, Jothi Rangasamy

Universal hashing-based message authentication code (MAC) is used as the de facto method to achieve information-theoretically secure authentication in quantum key distribution. We present a critical look at the most widely used type, namely Wegman-Carter MAC based on polynomial hashing and analyse its robustness against physical attacks exploiting side information. In particular, we mount a classical DPA attack on the hash part of the Wegman-Carter MAC which leads to a possible intercept-and-resend attack on the BB84-like QKD protocols. We illustrate this case with polynomial-evaluation MACs as their variants are used in commercial QKD systems. We show that our attack methodology is much simpler compared to that of Belaid et al. at ASIACRYPT 2014. Finally, we present an algebraic countermeasure so that the resulting MAC is not susceptible to the identified attack.

International Journal of Information and Computer Security•Jan 1, 2022•1 citation
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
We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) and well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds. Next, we present several protocols satisfying our security definitions. We show that the classical Wegman-Carter authentication scheme with 3-universal hashing is secure against superposition attacks, as well as adversaries with quantum side information. We then present conceptually simple constructions of full quantum state authentication. Finally, we prove a lifting theorem which shows that, as long as a protocol can securely authenticate the maximally entangled state, it can securely authenticate any state, even those that are entangled with the adversary. Thus, this shows that protocols satisfying a fairly weak form of authentication security automatically satisfy a stronger notion of security (in particular, the definition of Dupuis, et al (2012)).
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.
The rise of quantum computing poses significant challenges to security systems, with traditional message authentication codes (MACs) at unprecedented risk of compromise. This paper proposes a quantum message authentication code (QMAC) leveraging quantum mechanics to achieve robust security. The QMAC uses quantum one-way functions (QOWFs) to convert encrypted classical bits into qubits. This approach fundamentally differs from the computational hardness assumptions of conventional MACs. The QMAC's security is computationally difficulty-independent based on the inherent properties of quantum mechanics, making it impervious to exhaustive search attacks. Additionally, the protocol integrates authentication directly into the secure communication framework, obviating the need for extra particles and reducing computational complexity compared to stabilizer code-based or controlled unitary operations. Through a rigorous security analysis, we demonstrate the resilience of the proposed QMAC protocol against a wide range of adversarial strategies, including interception-resend attacks, identity impersonation, and entanglement-based attacks, among others.
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.
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.
Universal hashing-based message authentication code (MAC) is used as the de facto method to achieve information-theoretically secure authentication in quantum key distribution. We present a critical look at the most widely used type, namely Wegman-Carter MAC based on polynomial hashing and analyse its robustness against physical attacks exploiting side information. In particular, we mount a classical DPA attack on the hash part of the Wegman-Carter MAC which leads to a possible intercept-and-resend attack on the BB84-like QKD protocols. We illustrate this case with polynomial-evaluation MACs as their variants are used in commercial QKD systems. We show that our attack methodology is much simpler compared to that of Belaid et al. at ASIACRYPT 2014. Finally, we present an algebraic countermeasure so that the resulting MAC is not susceptible to the identified attack.