Paper 2015/271

Toward Secure Implementation of McEliece Decryption

Mariya Georgieva and Frédéric de Portzamparc

Abstract

We analyse the security regarding timing attacks of implementations of the decryption in McEliece PKC with binary Goppa codes. First, we review and extend the existing attacks, both on the messages and on the keys. We show that, until now, no satisfactory countermeasure could erase all the timing leakages in the Extended Euclidean Algorithm (EEA) step. Then, we describe a version of the EEA never used for McEliece so far. It uses a constant number of operations for given public parameters. In particular, the operation flow does not depend on the input of the decryption, and thus closes all previous timing attacks. We end up with what should become a central tool toward a secure implementation of McEliece decryption.

Note: Extended version of the COSADE 2015 article "Toward Secure Implementation of McEliece Decryption".

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision. COSADE 2015
Keywords
McElieceExtended Euclidean Algorithmtiming attacks
Contact author(s)
frederic urvoy-de-portzamparc @ polytechnique org
History
2015-03-23: received
Short URL
https://ia.cr/2015/271
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/271,
      author = {Mariya Georgieva and Frédéric de Portzamparc},
      title = {Toward Secure Implementation of McEliece Decryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/271},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/271}},
      url = {https://eprint.iacr.org/2015/271}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.