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

The quantum decoding problem : achievability bounds and applications to finding short codewords

Agathe Blanvillain

Published Sep 24, 2026• 0 citations
OpenAlex

Abstract

This thesis lies within the framework of post-quantum cryptography, whose goal is to conceive cryptosystems that resist classical and quantum attacks. Our focus here is on the Decoding Problem (DP) and the Short Codeword Problem (SCP) in code-based cryptography. We study here how quantum algorithms can exploit the structure of these problems. In a first part, we generalized the information-theoretic achievability threshold for the Quantum Decoding Problem (QDP) to all memoryless noise models. By combining this result with Regev's reduction, we obtain a quantum algorithm that samples dual codewords whose weight approaches the minimum at the achievability threshold. In a second part, we formulate a general framework for adapting to coding theory the lattice reduction from Learning With Errors (LWE) to the Extrapolated Dihedral Coset Problem (EDCP). We study this framework in the binary Hamming case and show that the resulting parameter regime can already be decoded classically in polynomial time.

Related papers

The quantum decoding problem : achievability bounds and applications to finding short codewords

Agathe Blanvillain

This thesis lies within the framework of post-quantum cryptography, whose goal is to conceive cryptosystems that resist classical and quantum attacks. Our focus here is on the Decoding Problem (DP) and the Short Codeword Problem (SCP) in code-based cryptography. We study here how quantum algorithms can exploit the structure of these problems. In a first part, we generalized the information-theoretic achievability threshold for the Quantum Decoding Problem (QDP) to all memoryless noise models. By combining this result with Regev's reduction, we obtain a quantum algorithm that samples dual codewords whose weight approaches the minimum at the achievability threshold. In a second part, we introduce Action-EDCP, give a conditional reduction from the Decoding Problem to this problem, and establish a limitation of a natural construction in the binary Hamming metric.

•Sep 24, 2026•0 citations

The Quantum Decoding Problem: Tight Achievability Bounds and Application to Regev's Reduction

Agathe Blanvillain, André Chailloux, Jean–Pierre Tillich

We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.

arXiv:2509.24796•IEEE Transactions on Information Theory•May 5, 2026•0 citations

The Quantum Decoding Problem

André Chailloux, Jean–Pierre Tillich

One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.

arXiv:2310.20651•Leibniz international proceedings in informatics•Oct 31, 2023•1 citation

Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard, Maxime Remaud, Jean–Pierre Tillich

We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes the Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.

arXiv:2106.02747•IEEE Transactions on Information Theory•Oct 26, 2023•7 citations

Classical and quantum cryptanalysis of lattices and codes

Lynn Engelberts

This thesis studies the security of lattice-based and code-based cryptography, two leading approaches to post-quantum cryptography. Although several lattice-based and code-based schemes have been selected for standardization and deployment, these schemes and their underlying computational problems have received less scrutiny than those they aim to replace. Continued cryptanalysis is therefore essential to build confidence in the security of post-quantum cryptography. The first part of this thesis concerns the classical cryptanalysis of lattice-based cryptography. We provide an algorithm that solves the Short Integer Solution problem in subexponential time for nontrivial parameter regimes. Moreover, we develop a predictive model for analyzing the practical performance of module-BKZ, a module-lattice analog of the BKZ algorithm. The second part considers the quantum cryptanalysis of lattice-based and code-based cryptography, focusing on quantum speedups for sieving algorithms. We present a new quantum algorithm for 3-tuple lattice sieving that yields an improved time-memory trade-off for solving the Shortest Vector Problem. We also introduce quantum algorithms for code sieving and investigate their potential for attacking code-based cryptography. Together, these results provide new insights into the security of lattice-based and code-based cryptography and highlight several directions for future research.

•Jan 1, 2026•0 citations

MATHEMATICAL FOUNDATIONS, ALGORITHMS AND SECURITY ANALYSIS POST-QUANTUM CRYPTOGRAPHY

Dilnoz Muhamediyeva, Farkhad Tagaev

The rapid development of quantum computing technologies poses a serious threat to modern public-key cryptographic systems. Classical cryptographic algorithms such as RSA and elliptic-curve cryptography rely on mathematical problems that can be efficiently solved using quantum algorithms. Post-quantum cryptography (PQC) aims to develop cryptographic schemes that remain secure even in the presence of quantum adversaries. This paper investigates the mathematical foundations of PQC, focusing on lattice-based, code-based, and hash-based cryptographic constructions. Security models based on computational complexity theory are analyzed, and illustrative examples using Learning With Errors (LWE) and decoding problems are presented. Experimental analysis demonstrates that PQC schemes provide strong resistance against both classical and quantum attacks when appropriate parameters are selected. The results highlight the importance of adopting new cryptographic standards to ensure long-term data security in quantum computing environments.

•May 3, 2026•0 citations
This thesis lies within the framework of post-quantum cryptography, whose goal is to conceive cryptosystems that resist classical and quantum attacks. Our focus here is on the Decoding Problem (DP) and the Short Codeword Problem (SCP) in code-based cryptography. We study here how quantum algorithms can exploit the structure of these problems. In a first part, we generalized the information-theoretic achievability threshold for the Quantum Decoding Problem (QDP) to all memoryless noise models. By combining this result with Regev's reduction, we obtain a quantum algorithm that samples dual codewords whose weight approaches the minimum at the achievability threshold. In a second part, we formulate a general framework for adapting to coding theory the lattice reduction from Learning With Errors (LWE) to the Extrapolated Dihedral Coset Problem (EDCP). We study this framework in the binary Hamming case and show that the resulting parameter regime can already be decoded classically in polynomial time.
This thesis lies within the framework of post-quantum cryptography, whose goal is to conceive cryptosystems that resist classical and quantum attacks. Our focus here is on the Decoding Problem (DP) and the Short Codeword Problem (SCP) in code-based cryptography. We study here how quantum algorithms can exploit the structure of these problems. In a first part, we generalized the information-theoretic achievability threshold for the Quantum Decoding Problem (QDP) to all memoryless noise models. By combining this result with Regev's reduction, we obtain a quantum algorithm that samples dual codewords whose weight approaches the minimum at the achievability threshold. In a second part, we introduce Action-EDCP, give a conditional reduction from the Decoding Problem to this problem, and establish a limitation of a natural construction in the binary Hamming metric.
We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.
One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes. We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons. We then revisit Regev's reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev's reduction matches the best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev's reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.
We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes the Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.
This thesis studies the security of lattice-based and code-based cryptography, two leading approaches to post-quantum cryptography. Although several lattice-based and code-based schemes have been selected for standardization and deployment, these schemes and their underlying computational problems have received less scrutiny than those they aim to replace. Continued cryptanalysis is therefore essential to build confidence in the security of post-quantum cryptography. The first part of this thesis concerns the classical cryptanalysis of lattice-based cryptography. We provide an algorithm that solves the Short Integer Solution problem in subexponential time for nontrivial parameter regimes. Moreover, we develop a predictive model for analyzing the practical performance of module-BKZ, a module-lattice analog of the BKZ algorithm. The second part considers the quantum cryptanalysis of lattice-based and code-based cryptography, focusing on quantum speedups for sieving algorithms. We present a new quantum algorithm for 3-tuple lattice sieving that yields an improved time-memory trade-off for solving the Shortest Vector Problem. We also introduce quantum algorithms for code sieving and investigate their potential for attacking code-based cryptography. Together, these results provide new insights into the security of lattice-based and code-based cryptography and highlight several directions for future research.
The rapid development of quantum computing technologies poses a serious threat to modern public-key cryptographic systems. Classical cryptographic algorithms such as RSA and elliptic-curve cryptography rely on mathematical problems that can be efficiently solved using quantum algorithms. Post-quantum cryptography (PQC) aims to develop cryptographic schemes that remain secure even in the presence of quantum adversaries. This paper investigates the mathematical foundations of PQC, focusing on lattice-based, code-based, and hash-based cryptographic constructions. Security models based on computational complexity theory are analyzed, and illustrative examples using Learning With Errors (LWE) and decoding problems are presented. Experimental analysis demonstrates that PQC schemes provide strong resistance against both classical and quantum attacks when appropriate parameters are selected. The results highlight the importance of adopting new cryptographic standards to ensure long-term data security in quantum computing environments.