Paper 2008/468

A CCA2 Secure Variant of the McEliece Cryptosystem

Nico Döttling, Rafael Dowsley, Jörn Müller-Quade, and Anderson C. A. Nascimento

Abstract

The McEliece public-key encryption scheme has become an interesting alternative to cryptosystems based on number-theoretical problems. Differently from RSA and ElGa- mal, McEliece PKC is not known to be broken by a quantum computer. Moreover, even tough McEliece PKC has a relatively big key size, encryption and decryption operations are rather efficient. In spite of all the recent results in coding theory based cryptosystems, to the date, there are no constructions secure against chosen ciphertext attacks in the standard model – the de facto security notion for public-key cryptosystems. In this work, we show the first construction of a McEliece based public-key cryptosystem secure against chosen ciphertext attacks in the standard model. Our construction is inspired by a recently proposed technique by Rosen and Segev.

Note: This is an expanded version accepted to the IEEE Transactions on Information Theory. One author was added. We include new results on the encryption of correlated but different messages. The proofs are now written as sequences of games. Also, we introduced a minor modification to the definition of a toy cryptosystem used in the proof of security (k-repetition PKC) to include explicitly the role of randomness. In the previous version, this was specified in the final proposed McEliece based PKC. This rules out the possibility of any kind of ambiguity in the security proof and answers questions raised by the referees and independently by Edoardo Persichetti (http://eprint.iacr.org/2012/268 and private communication).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Public-key encryptionCCA2 securityMcEliece assumptionsstandard model
Contact author(s)
rdowsley @ cs ucsd edu
History
2012-06-01: last of 5 revisions
2008-11-18: received
See all versions
Short URL
https://ia.cr/2008/468
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/468,
      author = {Nico Döttling and Rafael Dowsley and Jörn Müller-Quade and Anderson C.  A.  Nascimento},
      title = {A CCA2 Secure Variant of the McEliece Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2008/468},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/468}},
      url = {https://eprint.iacr.org/2008/468}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.