Abstract:
Public key cryptosystems such as Diffie-Hellman key exchange and homomorphic encryption over the integers are based on the assumption that the Discrete Logarithm Problem (DLP) and the Approximate Common Divisor (ACD) problem are hard respectively. These computational assumptions can be tested by developing improved algorithms to solve them. The DLP for elliptic curves defined over certain finite fields is believed to be hard. The best current algorithm for this problem is Pollard rho. The most promising new idea for attacking the DLP over these curves is the index calculus algorithm, since it solves the DLP for finite fields in subexponential time. It is important to understand this class of algorithms. We study the index calculus algorithm based on summation polynomials. This reduces the DLP to solving systems of multivariate polynomial equations. We explain recent research on exploiting symmetries arising from points of small order. The use of such symmetries can be used to speed up solving the system of polynomial equations, and hence speed up the algorithm. We give an improved index calculus algorithm for solving the DLP for binary elliptic curves. Despite our improved ideas, our experiments suggest that Pollard rho is still the best algorithm for the DLP in practice. We discuss and analyse a new idea called the “splitting technique”, which does not make use of symmetries. We finally suggest a new definition of the factor base to bring the probability of finding a relation close to 1. To extend the notion of symmetries we investigate the use of an automorphism of elliptic curves defined over a field of characteristic 3 to speed up the index calculus algorithm. Our finding is that an automorphism speeds up the algorithm, but not to the extent that we would wish. Finally we review, compare and precisely analyse some existing algorithms to solve the ACD problem. Our experiments show that the Cohn-Heninger algorithm is slower than the orthogonal lattice based approach. We propose a preprocessing of the ACD instances to speed up these algorithms. We explain that the preprocessing does not seem to threaten the ACD problem in practice.