Algorithmic Number Theory (ANTS-XIV)

The Fourteenth Algorithmic Number Theory Symposium, ANTS-XIV, will take place at the University of Auckland, New Zealand on June 30 – July 4, 2020.

The deadline for submissions is February 25. To submit, please go to the call for papers on the conference website.

I decided to have a look at the history of the ANTS conferences, and in particular to identify the most highly cited papers (using google scholar). The ANTS conferences started in 1994, with the first conference held at Cornell.

First I want to mention that citation counts are not a good measure of research quality or difficulty or importance. Citations are biased towards subject areas that have a culture of writing lots of papers and citing widely. Citation counts are also biased to older papers, since they have had more time to accrue citations. Hence, we would expect the most highly cited papers at ANTS to be in cryptography, and from 16 or more years ago.

Nevertheless, citation counts do tell something about the interest in a paper, and are a reasonable proxy for impact on the field.

The most highly cited paper in the history of the ANTS conferences (with nearly 1700 citations according to google scholar) is:

  • J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, ANTS III, 1998.

There is no doubt that this is a massively influential paper on lattice cryptography. Several of the lattice-based submissions to the NIST Post-Quantum standardisaton process were very closely building on NTRU. The irony (if you can call it that) is that this paper was rejected from CRYPTO, and yet has had higher impact than most other papers published in CRYPTO around that time.

Here are the following 14 most cited ANTS papers:

  • A. Joux, A One Round Protocol for Tripartite Diffie-Hellman, ANTS IV, 2000. 1369 cites.
  • D. Boneh, The Decision Diffie-Hellman Problem, ANTS III, 1998. 1078 cites.
  • S. D. Galbraith, K. Harrison and D. Soldera, Implementing the Tate Pairing, ANTS V, 2002. 689 cites.
  • A. Joux, The Weil and Tate Pairings as Building Blocks for Public KeyC ryptosystems, ANTS V, 2002. 287 cites.
  • L. M. Adleman, J. DeMarrais and M.-D. A. Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields, ANTS I, 1994. 258 cites.
  • P. Gaudry and R. Harley, Counting Points on Hyperelliptic Curves over Finite Fields, ANTS VI, 2000. 199 cites.
  • P. Q. Nguyen and D. Stehlé, LLL on the Average, ANTS VII, 2006. 168 cites.
  • O. Schirokauer, D. Weber and T. F. Denny, Discrete Logarithms: The Effectiveness of the Index Calculus Method, ANTS II, 1996. 167 cites.
  • L. M. Adleman, The function field sieve, ANTS I, 1994. 165 cites.
  • G.-J. Lay and H. G. Zimmer, Constructing elliptic curves with given group order over large finite fields, ANTS I, 1994. 163 cites.
  • P. Q. Nguyen and J. Stern, Lattice Reduction in Cryptology: An Update, ANTS IV, 2000. 144 cites.
  • N. D. Elkies, Shimura Curve Computations, ANTS III, 1998. 106 cites.
  • M. Fouquet and F. Morain, Isogeny Volcanoes and the SEA Algorithm, ANTS V, 2002. 104 cites.
  • A. Shallue and C. E. van de Woestijne, Construction of Rational Points on Elliptic Curves over Finite Fields, ANTS VII, 2006. 100 cites.

Of course, these rankings will change over time. But that is what it looked like in early 2020.

Looking at this list I see many important and favourite papers: Antoine Joux’s paper on One Round Tripartite Diffie-Hellman kick-started pairing-based crypto; the Adleman-DeMarrais-Huang paper was the first to show high genus curves are weak for DLP crypto; the Lay-Zimmer paper was influential in the early days of ECC; Fouquet and Morain introduced the phrase “Isogeny Volcano”; etc. It is also notable that several of the papers listed (e.g., those by Boneh, Elkies, Nguyen-Stern, and the second paper by Joux) are invited papers, which shows that the community does value survey/overview papers.

Anyway, I look forward to strong submissions to ANTS XIV in Auckland, including on elliptic curves, lattices and isogenies. Hopefully in 15-20 years the impact of some of those papers will be apparent.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s