crypt@b-it 2007
Pascal Paillier
Security reductions for asymmetric systems
Abstract.
Provable security is a set of mathematical techniques by means of which cryptographers analyze a cryptographic system and demonstrate its security. Indeed, beside their functional properties and practical efficiency, cryptosystems must be convincingly secure in a sense that depends on their nature and mode of use. The recent formalization of security notions for cryptosystems allows one to formulate security by relating resistance to attacks to so-called intractability assumptions using polynomial reductions. Reductions provide security guarantees under current human knowledge and bounds on realistic computational capabilities. Initially of theoretical interest, reductionist security has become over the past few years an extremely popular, practical and powerful tool for both the design and evaluation of cryptographic systems. This series of lectures explains the reductionist provable security approach with a focus on privacy (encryption) and authenticity (signature) in the public-key setting. The scope of this course extends from foundations of encryption and signature schemes to proof methodologies (with an emphasis on the random oracle model) for existing constructions and research issues related to improving current reduction techniques. The course is therefore suitable for undergraduate and graduate students in computer science with minimal or basic knowledge in cryptography.