Skip to Main content Skip to Navigation
Theses

Algebraic and Physical Security in Code-Based Cryptography

Frédéric Urvoy de Portzamparc 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.
Document type :
Theses
Complete list of metadata

Cited literature [76 references]  Display  Hide  Download

https://tel.archives-ouvertes.fr/tel-01187916
Contributor : Abes Star :  Contact
Submitted on : Friday, August 28, 2015 - 9:27:20 AM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Sunday, November 29, 2015 - 10:21:02 AM

File

these_archivage_3062112o.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01187916, version 1

Citation

Frédéric Urvoy de Portzamparc. Algebraic and Physical Security in Code-Based Cryptography. Cryptography and Security [cs.CR]. Université Pierre et Marie Curie - Paris VI, 2015. English. ⟨NNT : 2015PA066106⟩. ⟨tel-01187916⟩

Share

Metrics

Record views

807

Files downloads

989