ANTS 2012

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:

— Steven Galbraith

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s