HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 metadata

Contributor : Magali Bardet Connect in order to contact the contributor
Submitted on : Tuesday, April 2, 2019 - 10:37:08 AM
Last modification on : Wednesday, March 2, 2022 - 10:10:10 AM



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