Weak Keys for the Quasi-Cyclic MDPC Public Key Encryption Scheme - Normandie Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-02087520 , version 1 (02-04-2019)

Identifiants

Citer

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⟩
102 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More