Issac 2002
Issac 2002
Homepage Committees Other Issac Other conferences
Call for papers Call for posters Call for demos Accepted papers, posters & demos
Tutorials Advanced program Related events Participants
Travel Information Tourist Information Registration Accommodation

[Tutorials main page] [Tutorial 1] [Tutorial 2] [Tutorial 3]

Introduction to public key cryptography based on algorithmic number theory

Pierrick Gaudry

Laboratoire d'informatique, École polytechnique


In the past, cryptography was mainly used in specific and often classified areas like banking or defense. The situation has changed, especially in the last decade, since new technologies (mobile phones, Internet) required efficient, reliable but also public tools to protect the communications.

Cryptographic methods can be divided in two large classes: symmetric systems where the same key is used to cipher and to decipher, and asymmetric systems (a.k.a. public key cryptosystems) where the key used to encipher is different from the one used to decipher, the latter being impossible to deduce from the former.

Both have advantages and disadvantages. Depending on the context, one or the other will be used, and sometimes both together, mixed in complicated protocols.

Mathematical tools involved in symmetric algorithms include information theory, statistics, boolean functions. On the other hand, most of the cryptosystems used in public key cryptography rely on problems coming from number theory. The most famous, RSA, should be safe as long as we do not have efficient algorithms for factoring integers. Others rely on the difficulty of the discrete logarithm problem in a finite abelian group.

Optimizing and implementing the algorithms involved in these systems have become crucial. Some of them are highly non-trivial and make heavy use of tools coming from computer algebra or computational algebraic number theory.


Target Audience

The prerequisites for the first two parts of the presentation are very low. The third part will involve more mathematical knowledge in the area of algebraic and arithmetic geometry; we shall recall a few facts to make the talk accessible to a graduate student.

For technical remarks, contact webmaster :
Last modified on Fri Jul 5 11:46:51 MET DST 2002