Research in Computational Number Theory

Public-key cryptography relies crucially on number theoretical constructions: the security of a public key cryptosystem is based on the premise that a certain problem is computationally hard to solve. For example, the security of the most widely used public-key cryptosystem, the so-called RSA cryptosystem, is based on the premise that factoring a large integer into prime factors is a hard computational problem, in the sense that the computational resources required to perform the factoring task grow exponentially with the length of the integer. Another important cryptosystem, the Elliptic Curve Cryptosystem (ECC), bases its hardness on the premise that the discrete logarithm problem is hard in the group of rational points of an elliptic curve over a finite field if the curve and the field are chosen properly.

The sizes of the public and the private keys of a Public Key Cryptosystem (PKC) are important parameters of a PKC. Smaller keys provide faster encryption and decryption, and allow the realization of hardware implementations on smaller processors. In recent years, better algorithms for the factoring and the discrete logarithm problem have forced the users of the RSA and the ECC to use larger key sizes. It is quite possible that future more efficient algorithms may render practical key sizes for the RSA and the ECC ineffective. It is therefore important to design PKCs which are based on other hard computational problems, and yet have efficient encryption and decryption algorithms. Such computational problems are often called "primitives". Algorithmic number theory and some related fields offer a wealth of primitives. Prominent among them are discrete logarithm problems in groups that are of interest to number theoreticians. Examples of such groups are the group of points on the Jacobian of a curve, or more generally, the group of points of an Abelian variety, or the class group of a number field. These groups and their properties have been studied extensively by number theorists over the last decades. These theoretical results, paired with new algorithmic methods, provide a rich source for new and robust PKCs.

An important research area in computational number theory is Elliptic Curve pairing. EC pairing is a bilinear operation over the group of points of an elliptic-curve, and has proved to be a powerful tool for designing new cryptographic schemes. One of the most interesting application is Identity-Based Encryption, a concept invented by Shamir in 1984, but whose first practical realization using EC pairing appeared in 2001 (D. Boneh and M. K. Franklin, Identity-based encryption from the Weil pairing, Proceedings of Crypto 2001). Pairing computation can be defined on many possible elliptic and hyperelliptic curves. A goal is to obtain a better understanding of the computational aspects of the