Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Nicolas Sendrier <>
Submitted on : Tuesday, January 6, 2015 - 10:27:40 AM
Last modification on : Thursday, March 5, 2020 - 4:54:43 PM
Long-term archiving on: : Wednesday, June 3, 2015 - 11:50:57 AM


Files produced by the author(s)


  • HAL Id : hal-01095935, version 1



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. ⟨hal-01095935⟩



Record views


Files downloads