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 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.

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 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.

•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 : achievability bounds and applications to finding short codewords

Agathe Blanvillain

Le problème de décodage quantique : bornes d'atteignabilité et applications à la recherche de mots de code courts Cette thèse repose sur le concept de cryptographie post-quantique, qui a pour objectif de concevoir des cryptosystèmes résistants aux attaques classiques et quantiques. Nous nous concentrons ici sur le problème de décodage (DP) et le problème du court mot de code (SCP) en cryptographie à base de codes. Nous allons étudier comment des algorithmes quantiques peuvent exploiter la structure de ces problèmes. Dans une première partie, nous avons généralisé la borne informationnelle d'atteignabilité du problème de décodage quantique à toutes les distributions de bruit sans mémoire. En combinant ce résultat avec la réduction quantique de Regev, on obtient un algorithme quantique qui échantillonne des mots du code dual dont le poids approche le minimum à la limite d'atteignabilité. Dans un second temps, nous formulons un cadre général pour adapter à la théorie des codes la réduction du problème Learning With Errors (LWE) au problème Extrapolated Dihedral Coset Problem (EDCP). Nous étudions ce cadre dans le cas de la métrique de Hamming binaire et montrons que le régime de paramètres obtenu peut déjà être décodé classiquement en temps polynomial.

•Sep 24, 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

Post-Quantum Cryptography from Quantum Stabilizer Decoding

Jonathan Z. Lu, Alexander Poremba, Yihui Quek +1 more

Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes---a quantum analog of the well-studied LPN problem---is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practically efficient: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suite of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.

quant-pharXiv:2603.19110•Lecture notes in computer science•Mar 20, 2026•0 citations

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
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.
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.
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.
Le problème de décodage quantique : bornes d'atteignabilité et applications à la recherche de mots de code courts Cette thèse repose sur le concept de cryptographie post-quantique, qui a pour objectif de concevoir des cryptosystèmes résistants aux attaques classiques et quantiques. Nous nous concentrons ici sur le problème de décodage (DP) et le problème du court mot de code (SCP) en cryptographie à base de codes. Nous allons étudier comment des algorithmes quantiques peuvent exploiter la structure de ces problèmes. Dans une première partie, nous avons généralisé la borne informationnelle d'atteignabilité du problème de décodage quantique à toutes les distributions de bruit sans mémoire. En combinant ce résultat avec la réduction quantique de Regev, on obtient un algorithme quantique qui échantillonne des mots du code dual dont le poids approche le minimum à la limite d'atteignabilité. Dans un second temps, nous formulons un cadre général pour adapter à la théorie des codes la réduction du problème Learning With Errors (LWE) au problème Extrapolated Dihedral Coset Problem (EDCP). Nous étudions ce cadre dans le cas de la métrique de Hamming binaire et montrons que le régime de paramètres obtenu peut déjà être décodé classiquement en temps polynomial.
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.
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes---a quantum analog of the well-studied LPN problem---is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practically efficient: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suite of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.
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.