QC-MDPC-McEliece: A public-key code-based encryption scheme based on quasi-cyclic moderate density parity check codes

Abstract : The McEliece cryptosystem is the oldest code-based cryptosystem and itis believed to resist to quantum attacks. The system was proposed in1978 by Robert McEliece. It uses irreducible binary Goppa codes, butit can be instantiated with any family of linear codes for which anefficient decoder is available. The security is provably reduced totwo problems: the pseudorandomnes of the family in which the code ischosen and the hardness of decoding in an arbitrary linear codes.In the past few years, many variants have been proposed whichattempted to reduce the key size of the system (one of its majordrawbacks) by choosing families of strutured codes (quasi-cyclic orquasi-daydic). Many of those variants have been weakened. This wasmainly due to the fact that the attacker could combine the nativealgebraic structure of alternant codes to the added cyclic (or dyadic)structure.We propose here a new quasi-cyclic variant of McEliece arising fromModerate Density Parity-Check codes. These codes are LDPC codes ofhigher density than what is usually adopted for telecommunicationsolutions. The use of quasi-cyclic LDPC codes was considered dangerousuntil recently, when Baldi et al. proposed new ways to disguise thepublic-key. We extend Baldi's idea by using the family of MDPC codes,which is much larger than the family of disguised LDPC codes. Thisstrengthens considerably the security and, under a reasonableassumption, the pseudorandomness of MDPC codes reduces to the hardnessof computing words of minimal weight in a linear code.This allows us to propose the smallest public-keys for a McEliece-likecode-based encryption scheme. For 80-bits of security, the public-keyhas only 4800 bits. Its security relies on confidence inspiringassumptions, and we also benefit from the usual low complexityencryption and decryption of code-based schemes. In summary, wepropose a very competitive code-based system which represents is acredible alternative to traditional public-key encryption.
Type de document :
Communication dans un congrès
Workshop “Post-Quantum Cryptography: Recent Results and Trends”, Nov 2014, Fukuoka, Japan. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01095935
Contributeur : Nicolas Sendrier <>
Soumis le : mardi 6 janvier 2015 - 10:27:40
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mercredi 3 juin 2015 - 11:50:57

Fichier

mdpc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01095935, version 1

Collections

Citation

Nicolas Sendrier. QC-MDPC-McEliece: A public-key code-based encryption scheme based on quasi-cyclic moderate density parity check codes. Workshop “Post-Quantum Cryptography: Recent Results and Trends”, Nov 2014, Fukuoka, Japan. 2014. 〈hal-01095935〉

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

633