Skip to Main content Skip to Navigation
Conference papers

Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme

Magali Bardet 1, 2 Vlad Dragoi 1, 2 Jean-Gabriel Luque 1, 2 Ayoub Otmani 1, 2
1 CA - LITIS - Equipe Combinatoire et algorithmes
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : We analyze a new key recovery attack against the Quasi-Cyclic MDPC McEliece scheme. Retrieving the secret key from the public data is usually tackled down using exponential time algorithms aiming to recover minimum weight codewords and thus constructing an equivalent code. We use here a different approach and give under certain hypothesis an algorithm that is able to solve a key equation relating the public key to the private key. We relate this equation to a well known problem the Rational Reconstruction Problem and therefore propose a natural solution based on the extended Euclidean algorithm. All private keys satisfying the hypothesis are declared weak keys. In the same time we give a precise number of weak keys and extend our analysis by considering all possible cyclic shifts on the private keys. This task is accomplished using combinatorial objects like Lyndon words. We improve our approach by using a generalization of the Frobenius action which enables to increase the proportion of weak keys. Lastly, we implement the attack and give the probability to draw a weak key for all the security parameters proposed by the designers of the scheme.
Document type :
Conference papers
Complete list of metadatas
Contributor : Magali Bardet <>
Submitted on : Tuesday, April 2, 2019 - 10:37:08 AM
Last modification on : Thursday, March 5, 2020 - 6:36:18 PM



Magali Bardet, Vlad Dragoi, Jean-Gabriel Luque, Ayoub Otmani. Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme. AFRICACRYPT 2016 (8th International Conference on Cryptology in Africa), Apr 2016, Fes, Morocco. pp.346-367, ⟨10.1007/978-3-319-31517-1_18⟩. ⟨hal-02087520⟩



Record views