McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks

DOI10.1007/978-3-642-22792-9_43MaRDI QIDQ5199224zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hang Dinh, Cristopher Moore, Alexander Russell

Publication date 12 August 2011

Published in Advances in Cryptology – CRYPTO 2011 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.2390

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will someday become a reality, we would like to have emph{post-quantum} cryptosystems which can be implemented today with classical computers, but which will remain secure even in the presence of quantum attacks. In this article we show that the McEliece cryptosystem over emph{well-permuted, well-scrambled} linear codes resists precisely the attacks to which the RSA and El Gamal cryptosystems are vulnerable---namely, those based on generating and measuring coset states. This eliminates the approach of strong Fourier sampling on which almost all known exponential speedups by quantum algorithms are based. Specifically, we show that the natural case of the Hidden Subgroup Problem to which the McEliece cryptosystem reduces cannot be solved by strong Fourier sampling, or by any measurement of a coset state. We start with recent negative results on quantum algorithms for Graph Isomorphism, which are based on particular subgroups of size two, and extend them to subgroups of arbitrary structure, including the automorphism groups of linear codes. This allows us to obtain the first rigorous results on the security of the McEliece cryptosystem in the face of quantum adversaries, strengthening its candidacy for post-quantum cryptography.

Recommendations

• Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling
• Quantum McEliece public-key cryptosystem
• Code-based cryptosystems using generalized concatenated codes
• Compact McEliece keys based on quasi-dyadic Srivastava codes
• Quantum attacks on public-key cryptosystems

Cited in

(10)

• General linear group action on tensors: a candidate for post-quantum cryptography
• Mathematical models of modified crypto-code means of information protection based on coding theory schemes
• Quantum McEliece public-key cryptosystem
• Quantum attacks on public-key cryptosystems
• On the generating matrices of Goppa codes over hyperelliptic curves
• LESS is more: code-based signatures without syndromes
• Enumeration of extended irreducible binary Goppa codes of degree 2ᵐ and length 2ⁿ+1
• Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling
• A fault attack on the Niederreiter cryptosystem using binary irreducible Goppa codes
• Computer algebra tales on Goppa codes and McEliece cryptography

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199224)