ABSTRACT
Index calculus is a rich area of research in number theory and cryptography. This technique is common to a large family of algorithms that can be used for many applications. From a number theoretic point-of-view, these algorithms allow to factor large integers, to compute discrete logarithms in finite fields, to compute the class numbers of number field and even apply to discrete logarithms on the jacobians of some algebraic curves. From a cryptographic perspective, the above applications are directly interesting but in addition, index calculus techniques have recently been used to undermine the security of several cryptographic primitives in some specific contexts. With these cryptographic primitives which, at the present time, include the plain RSA e-th root extraction problem [JNT07] and the static Diffie-Hellman problem, an adversary learns enough to solve the problem on his own after asking a large number of questions about well-chosen instances of the problem. The total cost of index calculus in these cryptographic applications is less than the cost of the corresponding index calculus algorithm against the underlying number theoretic problem: factoring or computation of discrete logarithms.
