Jean-Sébastien Coron

Ph.D. Thesis: Cryptanalysis and Security Proofs for Public-key Schemes.

May 16th, 2001

Download: Cryptanalyses et preuves de sécurité de schémas à clef publique

Abstract

This thesis deals with the security of encryption schemes and signature schemes based on the RSA algorithm, which are commonly used in real-world applications. It is split into two parts, "cryptanalysis" and "security proofs".  In the first part, we show that some existing cryptographic schemes have weaknesses which make them vulnerable to some attacks. The RSA-based digital signature standards ISO 9796-1 and ISO 9796-2, and the RSA-based encryption standard PKCS#1 v1.5 are shown to be insecure. We also extend Girault and Misarsky's attack on RSA signatures with affine redundancy.  In the second part, we study security proofs for signature schemes. We provide an improved security proof for the Full-Domain-Hash signature scheme, and for the Gennaro-Halevi-Rabin signature scheme. We also show that a signature scheme in which each message has a unique signature can not reach the same level of security as a signature scheme which messages have many possible signatures.  The attacks presented in the first part of this thesis illustrate the risk induced by using cryptographic schemes which security is not clearly justified. This strongly motivates the search for provably secure schemes. 

Jury

From left to right: Marc Girault, Adi Shamir, Jean-Marc Steyaert, Jean-Sebastien Coron, Ronald Rivest, Jacques Stern and David Naccache. Are not present on the photo Mihir Bellare and Serge Vaudenay.