A Practical Digital Signature Scheme Based on Coding Theory

A Practical Digital Signature Scheme
Based on Coding Theory

Nicolas Sendrier

Presenter: Nicolas Sendrier, INRIA, Paris

Host: Alexander Vardy, Professor in the Department of Electrical and Computer Engineering, University of California, San Diego - contact Prof. Vardy through Leah Bellacera at lbellace@soe.ucsd.edu

Date: Tuesday, May 21, 2002

Time: 1:00 PM, Reception to Follow

Location: Engineering Building Unit 1, Room 4307 (directions and parking information)

Live Webcast: http://earth.ucsd.edu:8080/ramgen/encoder/sendrier.rm
Archived Webcasts available at: http://www.calit2.net/multimedia/archive.html
Courtesy: California Institute for Telecommunications and Information Technology [Calit²]

Abstract
[Presentation]
McEliece is one of the oldest known public key cryptosystems. Though it was less studied than RSA, it is remarkable that all known attacks are still of exponential complexity. It was widely believed that code-based cryptosystems like McEliece did not allow practical digital signatures. In the present talk I will disprove this belief and show a way to build a digital signature scheme based on coding theory. The bad features of this scheme are a large key size (1.1 MB) and a long signature time (1 minute). The good ones are a extremely fast verification time and a short signature length (132 bits). The signature length can even be reduced to about 80 bits if one allows a verification time of one minute. Moreover, the scheme is easily scalable and will evolve favorably with the improvement of technology. Finally, its security can be reduced to two basic assumptions: 1. the syndrome decoding problem is difficult { em in average}, 2. binary Goppa codes are pseudo-random.

Bio
Nicolas Sendrier was born in December 11, 1965 in Rabat (Morocco). He received the Ingeneer degree from the Ecole Polytechnique, Palaiseau, France, in July 1988, a Ph.D. degree in computer science from the University Pierre et Marie Curie, Paris, France, in December 1991 and an HDR degree (Habilitation à diriger des recherches) in computer science from the University Pierre et Marie Curie, Paris, France, in March 2002. He is working as a researcher at the INRIA Rocquencourt, France, since January 1992 and is currently vice-leader of the project CODES. His research interests include coding theory, algorithmics and cryptography.