Section: Scientific Foundations

General overview

Once considered beautiful but useless, arithmetic has proven a spectacular success in the creation of a new paradigm in cryptography. Classical cryptography was mainly concerned with symmetric techniques: two parties wishing to communicate secretly had to share a common secret (the “key”) beforehand, and this same secret key was used both for encrypting the message and for decrypting it. This mode of communication is efficient enough when traffic is low, or when the parties can meet prior to communication. However, modern networks are simply too large for the classical paradigm to remain efficient any longer.

We therefore need cryptography without prior contact. In theory, this is simple: find two algorithms $E$ and $D$ that are reciprocal (that is, $D\left(E\right(m\left)\right)=m$) and such that the knowledge of $E$ does not help in computing $D$. Then $E$ is dubbed a public key, available to anyone, and $D$ is the secret key, reserved to a single user. When Alice wants to send an email message $m$ to Bob, she uses his public key $E$ to send him the encrypted message $E\left(m\right)$, which he can decrypt with the secret key $D$: we have thus achieved secret communication without a common secret key. (Of course, everything has to be presented in the modern language of complexity theory: $E$ and $D$ must be computable in polynomial time, while finding $D$ from $E$ alone without some secret knowledge should be possible only in, say, exponential time.) This simplified and somewhat idealized example is at the heart of asymmetric cryptology. Modern asymmetric cryptography provides not only secure communication channels but also solutions to the signature problem, as well as some solutions for identifying all parties in protocols, thus enabling products to be usable on the Internet (such as ssh and ssl/tls).

Now, where do the hard problems behind encryption and decryption come from? Mostly from arithmetic, where we find problems such as integer factorization and the discrete logarithm problem (DLP). It appears to be important to vary the groups which act as settings for concrete instances of the abstract hard problems, since this provides some bio-diversity which is key to resisting crypto-analytic attacks. The groups proposed include finite fields, modular integers, algebraic curves, and class groups. All of these now form cryptographic primitives that need to be assembled in protocols, and finally in commercial products.

Our activity is concerned with the beginning of this process: we are interested in difficult problems arising in computational number theory, and the efficient construction of these primitives. TANC concentrates on modular arithmetic, finite fields and algebraic curves.

We have a strong, well-known reputation for breaking records, whatever the subject is: constructing systems or breaking them. We have world-record computations in areas including primality proving, class polynomials, modular equations, computing cardinalities of algebraic curves, and discrete logarithms. This means writing programs and putting in all the work needed to support calculations that run for weeks or months. An important part of our task is now to transform record-breaking programs into programs to solve everyday cryptographic problems for current parameter sizes.

Certificates are another of our major concerns. By certificates, we mean efficiently verifiable proofs of the properties of the objects we build. While these certificates might be difficult to build, they are easy to check (by customers, for example). The traditional example is certificates for primality of prime numbers, introduced by Pratt in 1974. We know how to construct certificates for the important properties of elliptic curves, with the aim of establishing what we call an identity card for a curve (including its cardinality, together with the proof of its factorization, its group structure with proven generators, its discriminant with proven factorization, and the class number of the associated order). The theory is ready for this, and the algorithms are not out of reach. This approach must be extended to other curves; the theory is almost ready in several cases, but algorithms are still to be found. This is one of the main problems facing TANC .

The mathematics used in cryptology is becoming more and more complex (for example, consider recent algorithms based on $p$-adic cohomology). The new, more mathematically complex algorithms will remain mere theoretical curiosities if we do not implement them. For implementations, we need more and more evolved algorithmic primitives; currently, these may be available in very rare mathematical systems such as Magma . Once our algorithms work in Magma , it is customary to rewrite them in C or C++ to gain speed. Along the same lines, some of our C programs developed for our research (an old version of ECPP, some parts of discrete log computations, cardinality of curves) are now included in the Magma system, as a result of our collaboration with the Sydney group.