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:1703.00263

Quantum Information Set Decoding Algorithms

Ghazal Kachigar, Jean–Pierre Tillich

Published Mar 1, 2017• 19 citations
arXivHTMLPDF

Abstract

The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in Overbeck and Sendrier's 2009 survey on code-based cryptography, and the best algorithm to date has been Bernstein's quantising of the simplest information set decoding algorithm, namely Prange's algorithm. It consists in applying Grover's quantum search to obtain a quadratic speed-up of Prange's algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem by Bernstein, Jeffery, Lange and Meurer. This results in improving the worst-case complexity of $2^{0.06035n}$ of Bernstein's algorithm to $2^{0.05869n}$ with the best algorithm presented here (where $n$ is the codelength).

DOI
10.48550/arxiv.1703.00263

Related papers

Classical algorithm techniques for decoding generic linear codes

Nicolas Sendrier

The security of code-based cryptosystems relies heavily on the hardness of decoding in an arbitrary linear code. The problem only has exponential solutions in the classical computing model, and it seems that it remains the case with quantum computing, placing code-based crypto among the so-called post-quantum cryptographic techniques. Even though quantum computer are not likely to allow generic decoding techniques with non-exponential complexity, it still allows some significant improvements. A few works have already explore this path. The purpose of this survey is not to propose new decoding techniques taking advantage a quantum computing. Instead we intend to give a comprehensive description of the main decoding techniques. The best techniques are recent (2011 and 2012) and are in fact finely tuned trade-offs between several very basic techniques. We will come back to those basics, which are the birthday decoding (based on the birthday paradox), and the Prange or Lee & Brickell algorithms (which are essentially enumerations). We feel that understanding each of those techniques in a quantum setting will simplify the search of an optimal quantum algorithm, and, hopefully, provide a simpler approach than directly "quantumize" the best known decoding techniques.

•Sep 9, 2013•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•17 citations

Quantum McEliece public-key cryptosystem

Hachiro Fujita

The McEliece cryptosystem is one of the best-known (classical) public-key cryptosystems, which is based on algebraic coding theory. In this paper, we present a quantum analogue of the classical McEliece cryptosystem. Our quantum McEliece public-key cryptosystem is based on the theory of stabilizer codes and has the key generation, encryption and decryption algorithms similar to those in the classical McEliece cryptosystem. We present an explicit construction of the quantum McEliece public-key cryptosystem using Calderbank-Shor-Steane codes based on generalized Reed-Solomon codes. We examine the security of our quantum McEliece cryptosystem and compare it with alternative systems.

Quantum Information and Computation•Mar 1, 2012•18 citations

Étude et conception d'algorithmes quantiques pour le décodage de codes linéaires

Ghazal Kachigar

\n Les cryptosystèmes basés sur les codes correcteurs sont de bons candidatspour la cryptographie post-quantique. Afin de bien choisir leurs paramètres desécurité, il faut tenir compte des attaques quantiques les plus puissantes.Bernstein avait montré en 2009 qu'il est possible d'utiliser l'algorithme derecherche non-structurée de Grover avec l'algorithme de Prange pour obtenir unalgorithme ISD quantique dont la complexité est la racine carrée de l'algorithme dePrange classique. Nous avons réussi à faire mieux que ce résultat en considérant lesalgorithmes classiques plus sophistiqués et en se servant de techniques basées sur lamarche aléatoire quantique (Quantum Walk) et inspirées par les meilleurs algorithmesquantiques de résolution du problème de la somme des sous-ensembles (subset sum).\n

•Sep 9, 2016•1 citation

Advanced Techniques in Post-Quantum Cryptography for Ensuring Data Security in the Quantum Era

Latika Rahul Desai

The arrival of quantum computers is a major threat to current security methods, which depend on problems like discrete logarithms and integer factorization being hard. Post-quantum cryptography (PQC) is getting to be an critical field for making secure strategies that can't be broken by quantum assaults. This exposition talks almost progressed PQC strategies, centered on the most up to date thoughts and what they cruel for securing information within the quantum age. To begin with, we see at lattice-based cryptography, which appears like a great choice since it has solid security roots and can be utilized in numerous circumstances. This incorporates strategies such as Learning With Mistakes (LWE) and Ring-LWE, which are exceptionally great at ensuring against quantum dangers and are simple to utilize. Another critical zone is code-based cryptography, which employments the trouble of breaking irregular straight codes as an case. The McEliece cryptosystem is one such framework. It is checked to see how valuable and successful these strategies are in real-life circumstances. We see into multivariate polynomial encryption, which builds security on the truth that it's difficult to illuminate sets of multivariate quadratic equations. People are particularly curious about this strategy since it may be utilized to form proficient marking plans. Another imperative strategy is hash-based cryptography, which employments hash capacities to create secure advanced marks. The consider moreover talks around blended cryptography frameworks that utilize both conventional and post-quantum strategies. These frameworks make beyond any doubt that the switch to quantum computing goes easily and give way better security. We see at the issues that come up with implementation, like additional work that has to be done on the computer and joining it with current frameworks, and come up with ways to urge around these issues. At long last, moving to post-quantum security is necessary, but it comes with a part of problems that ought to be illuminated in numerous ways.

Panamerican mathematical journal.•Nov 13, 2024•5 citations

Designing quantum circuits for decoding binary linear codes

Hyungkee Yoo, Whan-Hyuk Choi, Yoonjin Lee

Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.

Journal of Physics A Mathematical and Theoretical•Nov 21, 2024•4 citations
The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in Overbeck and Sendrier's 2009 survey on code-based cryptography, and the best algorithm to date has been Bernstein's quantising of the simplest information set decoding algorithm, namely Prange's algorithm. It consists in applying Grover's quantum search to obtain a quadratic speed-up of Prange's algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem by Bernstein, Jeffery, Lange and Meurer. This results in improving the worst-case complexity of 20.06035n2^{0.06035n}20.06035n of Bernstein's algorithm to 20.05869n2^{0.05869n}20.05869n with the best algorithm presented here (where nnn is the codelength).
The security of code-based cryptosystems relies heavily on the hardness of decoding in an arbitrary linear code. The problem only has exponential solutions in the classical computing model, and it seems that it remains the case with quantum computing, placing code-based crypto among the so-called post-quantum cryptographic techniques. Even though quantum computer are not likely to allow generic decoding techniques with non-exponential complexity, it still allows some significant improvements. A few works have already explore this path. The purpose of this survey is not to propose new decoding techniques taking advantage a quantum computing. Instead we intend to give a comprehensive description of the main decoding techniques. The best techniques are recent (2011 and 2012) and are in fact finely tuned trade-offs between several very basic techniques. We will come back to those basics, which are the birthday decoding (based on the birthday paradox), and the Prange or Lee & Brickell algorithms (which are essentially enumerations). We feel that understanding each of those techniques in a quantum setting will simplify the search of an optimal quantum algorithm, and, hopefully, provide a simpler approach than directly "quantumize" the best known decoding techniques.
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.
The McEliece cryptosystem is one of the best-known (classical) public-key cryptosystems, which is based on algebraic coding theory. In this paper, we present a quantum analogue of the classical McEliece cryptosystem. Our quantum McEliece public-key cryptosystem is based on the theory of stabilizer codes and has the key generation, encryption and decryption algorithms similar to those in the classical McEliece cryptosystem. We present an explicit construction of the quantum McEliece public-key cryptosystem using Calderbank-Shor-Steane codes based on generalized Reed-Solomon codes. We examine the security of our quantum McEliece cryptosystem and compare it with alternative systems.
\n Les cryptosystèmes basés sur les codes correcteurs sont de bons candidatspour la cryptographie post-quantique. Afin de bien choisir leurs paramètres desécurité, il faut tenir compte des attaques quantiques les plus puissantes.Bernstein avait montré en 2009 qu'il est possible d'utiliser l'algorithme derecherche non-structurée de Grover avec l'algorithme de Prange pour obtenir unalgorithme ISD quantique dont la complexité est la racine carrée de l'algorithme dePrange classique. Nous avons réussi à faire mieux que ce résultat en considérant lesalgorithmes classiques plus sophistiqués et en se servant de techniques basées sur lamarche aléatoire quantique (Quantum Walk) et inspirées par les meilleurs algorithmesquantiques de résolution du problème de la somme des sous-ensembles (subset sum).\n
The arrival of quantum computers is a major threat to current security methods, which depend on problems like discrete logarithms and integer factorization being hard. Post-quantum cryptography (PQC) is getting to be an critical field for making secure strategies that can't be broken by quantum assaults. This exposition talks almost progressed PQC strategies, centered on the most up to date thoughts and what they cruel for securing information within the quantum age. To begin with, we see at lattice-based cryptography, which appears like a great choice since it has solid security roots and can be utilized in numerous circumstances. This incorporates strategies such as Learning With Mistakes (LWE) and Ring-LWE, which are exceptionally great at ensuring against quantum dangers and are simple to utilize. Another critical zone is code-based cryptography, which employments the trouble of breaking irregular straight codes as an case. The McEliece cryptosystem is one such framework. It is checked to see how valuable and successful these strategies are in real-life circumstances. We see into multivariate polynomial encryption, which builds security on the truth that it's difficult to illuminate sets of multivariate quadratic equations. People are particularly curious about this strategy since it may be utilized to form proficient marking plans. Another imperative strategy is hash-based cryptography, which employments hash capacities to create secure advanced marks. The consider moreover talks around blended cryptography frameworks that utilize both conventional and post-quantum strategies. These frameworks make beyond any doubt that the switch to quantum computing goes easily and give way better security. We see at the issues that come up with implementation, like additional work that has to be done on the computer and joining it with current frameworks, and come up with ways to urge around these issues. At long last, moving to post-quantum security is necessary, but it comes with a part of problems that ought to be illuminated in numerous ways.
Abstract In the coding theory, it is one of the most important research problems to find an efficient algorithm for the decoding process. A quantum computer is an innovative computing device that performs calculations using the principles of quantum mechanics. In this paper, we find a decoding algorithm for binary linear codes using quantum circuits; this is the first time that quantum circuits are used as a main tool for decoding binary linear codes. Our decoding algorithm is mainly based on Grover’s search algorithm. In detail, we study the process of implementing the exhaustive search using quantum circuits for decoding binary linear codes. For our purpose, we design a modified Grover’s algorithm (algorithm 1) using three tools: the matrix multiplier, the Hamming weight counter, and the state indicator. We present algorithm 2, which is a quantum decoding algorithm for binary linear codes. We illustrate algorithm 1 using the [7, 4, 3] Hamming code, and algorithm 2 is implemented by IBM Quantum Composer.