The Tenth Algorithmic Number Theory Symposium ANTS-X was held at the University of California, La Jolla, San Diego on July 9–13, 2012. The conference was well-organised and, apart from some issues with the temperature of the lecture room, everything went smoothly.
The ANTS conference usually contains a number of papers relevant for the study of elliptic curve cryptography, and this year was no exception.
Drew Sutherland had several papers at the conference. His excellent invited lecture surveyed the use of isogeny volcanoes to improve various algorithms in computational number theory (such as computing class polynomials for the CM method and computing modular polynomials). This theme was continued in his paper On the evaluation of modular polynomials.
Physical comedy was provided by Daniel Bernstein and Tanja Lange in the joint presentation of their paper Two grumpy giants and a baby. They might not be as tall as giants, but they do “grumpy” well. (I declined to play the role of the baby.) The paper makes two interesting contributions. First, it gives a really clear and elegant way to analyse the baby-step-giant-step and Pollard rho algorithms in terms of “slopes”. Second, the paper gives a new variant of the baby-step-giant-step algorithm that seems to perform better than previous such methods (though it still needs large storage).
Damien Robert presented the paper (joint with Kristin Lauter) Improved CRT algorithm for class polynomials in genus 2, which discusses a method to compute class polynomials for the CM method in genus 2. Unfortunately there is still a long way to go before such methods are really practical for large-scale computation of the CM method in genus 2.
The rump session featured a wonderful talk by Nadia Heninger on her work with Zakir Durumeric, Eric Wustrow and Alex Halderman about RSA and DSA keys. Resources on this work are here. While the results on RSA have been widely publicised, it is worth noting that there are implementations of discrete logarithm signatures that are also insecure. The problem arises in devices without access to an appropriate source of entropy. For discrete logarithm signatures this can result in DSA signatures with the “random” component g^k being the same for two different signatures with the same public key. It is then easy to determine the private key from the signatures. Such attacks also apply to ECDSA signatures. So it is important to ensure that devices have a suitable entropy source if they are going to be used for high-security applications.
The conference programme also featured a number of interesting papers about elliptic curves over number fields. Nils Skorrupa gave a wonderful talk about computing modular forms (a problem that for weight 2 cusp forms is more-or-less equivalent to counting points on a modular elliptic curve modulo p, for small p) and the other invited talks were also excellent.
Some readers of this blog might also be interested in the following two papers that were about applications of elliptic curves to primality testing and integer factorisation:
- Alexander Abatzoglou, Alice Silverberg, Andrew Sutherland, and Angela Wong, Deterministic elliptic curve primality proving for a special sequence of numbers.
- Razvan Barbulescu, Joppe Bos, Cyril Bouvier, Thorsten Kleinjung and Peter Montgomery, Finding ECM-friendly curves through a study of Galois properties.
— Steven Galbraith