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

arXiv:quant-ph/0310078

Quantum message authentication based on classical NP-complete problem

Li Yang, Lei Hu, Dengguo Feng

Published Oct 12, 2003• 3 citations
arXivHTMLPDF

Abstract

This note presents a method to authenticate a quantum message based on classical SN-S authentication code and the computations between different quantum registers. If the pre-coding generator matrix in SN-S code is public, the quantum scheme is a public-key data integrity scheme; if it is secret, the quantum scheme is a hybrid data origin authentication scheme.

DOI
10.48550/arxiv.quant-ph/0310078

Related papers

Quantum message authentication based on algebraic coding theory

Li Yang, Lei Hu, Dengguo Feng

We present a new type of authentication scheme for quantum message based on algebraic coding theory and quantum computation operations between different quantum registers. The results are that if the pre-coding generator matrix in SN-S code is public, the quantum scheme is a public-key data integrity scheme; if it is secret, the quantum scheme is a hybrid data origin authentication scheme. The advantage of this scheme is that the public and secret keys are merely some classical data.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jan 11, 2005•1 citation

A public-key cryptosystem for quantum message transmission

Li Yang

We present a quantum public-key cryptography protocol for quantum message transmission. The private key of this protocol includes three classical matrices: a generator matrix of a Goppa code, an invertible matrix and a permutation matrix. The public key is product of these three matrices. The encryption and decryption algorithms are merely quantum computations related with the transformations between bases of the quantum registers. The security of this protocol is based on the hypothesis that there is no effective algorithm of NP-complete problem.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jan 11, 2005•10 citations

Quantum message authentication scheme based on remote state preparation

Min-Sung Kang, Yeon-Ho Choi, Yong‐Su Kim +4 more

Abstract We propose a quantum message authentication scheme that provides integrity and origin authentication using a remote state preparation. Authentication is one of the security services that must be provided in secure communication. Quantum message authentication is the base scheme for realizing quantum authentication that is known to be a secure technique even in a forthcoming quantum computer environment. The proposed scheme creates a quantum message authentication code (QMAC) with only a single qubit measurement. It is therefore easy to implement and operate compared to existing technology that normally generates a QMAC with a Bell measurement or controlled unitary operation. For security analysis, we design a quantum random oracle model based on the random oracle model and demonstrate the quantum collision resistance with it. From the analysis, the probability of the quantum collision is 0.69 N per qubit, where N is the size of the message sequence. Since the probability of quantum collision in the case of N ≥ 13 becomes extremely low of under 0.8%, we confirm that the proposed scheme guarantees the integrity and origin authentication of the message.

Physica Scripta•Sep 14, 2018•12 citations

Information-Theoretically Secure Data Origin Authentication with Quantum and Classical Resources

Georgios M. Nikolopoulos, Marc Fischlin

In conventional cryptography, information-theoretically secure message authentication can be achieved by means of universal hash functions, and requires that the two legitimate users share a random secret key, which is at least twice as long as the tag. We address the question of whether quantum resources can offer any advantage over classical unconditionally secure message authentication codes. It is shown that a broad class of symmetric prepare-and-measure quantum message-authentication schemes cannot do better than their classical counterparts.

arXiv:2011.06849•Cryptography•Nov 13, 2020•10 citations

Quantum Public-Key Cryptosystem Based on Classical NP-Complete Problem

Li Yang

We present a quantum public-key cryptosystem based on a classical NP-complete problem related with finding a code word of a given weight in a linear binary code.

arXiv:quant-ph/0310076•Oct 12, 2003•23 citations

A Quantum Public-Key Cryptosystem and Message Authentication Scheme Based on Quantum CSS Error Correcting Codes

Pla Information

This paper presents a quantum public-key cryptosystem by using quantum Calderbank-Shor-Steane(CSS) error correcting codes and the NPC problem related with decoding general linear codes. It uses classical key to encrypt quantum message, and its security relies on the fact that NPC problem can not be solved on quantum Turing machines. Based on this public-key cryptosystem, this paper also gives a message authentication scheme and proves its security.

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY•Jan 1, 2006•0 citations
This note presents a method to authenticate a quantum message based on classical SN-S authentication code and the computations between different quantum registers. If the pre-coding generator matrix in SN-S code is public, the quantum scheme is a public-key data integrity scheme; if it is secret, the quantum scheme is a hybrid data origin authentication scheme.
We present a quantum public-key cryptography protocol for quantum message transmission. The private key of this protocol includes three classical matrices: a generator matrix of a Goppa code, an invertible matrix and a permutation matrix. The public key is product of these three matrices. The encryption and decryption algorithms are merely quantum computations related with the transformations between bases of the quantum registers. The security of this protocol is based on the hypothesis that there is no effective algorithm of NP-complete problem.
Abstract We propose a quantum message authentication scheme that provides integrity and origin authentication using a remote state preparation. Authentication is one of the security services that must be provided in secure communication. Quantum message authentication is the base scheme for realizing quantum authentication that is known to be a secure technique even in a forthcoming quantum computer environment. The proposed scheme creates a quantum message authentication code (QMAC) with only a single qubit measurement. It is therefore easy to implement and operate compared to existing technology that normally generates a QMAC with a Bell measurement or controlled unitary operation. For security analysis, we design a quantum random oracle model based on the random oracle model and demonstrate the quantum collision resistance with it. From the analysis, the probability of the quantum collision is 0.69 N per qubit, where N is the size of the message sequence. Since the probability of quantum collision in the case of N ≥ 13 becomes extremely low of under 0.8%, we confirm that the proposed scheme guarantees the integrity and origin authentication of the message.
In conventional cryptography, information-theoretically secure message authentication can be achieved by means of universal hash functions, and requires that the two legitimate users share a random secret key, which is at least twice as long as the tag. We address the question of whether quantum resources can offer any advantage over classical unconditionally secure message authentication codes. It is shown that a broad class of symmetric prepare-and-measure quantum message-authentication schemes cannot do better than their classical counterparts.