This is SAC week (i.e. Selected Areas in Cryptography). Now in its twenty first year, this is the annual meeting for cryptographers in Canada. There is always an international programme of papers being presented, and the location is a Canadian city. Given the name there is always a specific focus for the SAC conference; there is a definite bias towards symmetric cryptography and number theory. Given this it is fitting that Antoine Joux was the non-Canadian PC chair for this year, since Antoine's work spans both symmetric and number theoretic aspects of cryptography. The local PC chair was Amr Youssef from Concordia University in Montreal.
There were three invited talks this year, one by myself and one by my co-author Pierrick Gaudry, who talked about the Number Field Sieve (NFS) algorithm as applied to factoring integers and discrete logarithms. The third invited talk was by another co-author of mine, this was by Alfred Menezes, who gave a talk celebrating the life, achievements and impact of Scott Vanstone who sadly died earlier this year.
Scott was probably the most well known and influential Canadian cryptographer. Originally he worked in areas such as combinatorics, but soon got the bug to work on public key cryptography. Alf explained how his initial forays into building products for cryptography from his mathematical knowledge were scuppered by advances in cryptanalysis. An early product, developed by MITRE and Hewlett-Packard with Scott's help, used discrete logarithms in GF(2127). This field looks ridiculously small today (Alf said Antoine could solve this on his wrist watch) but at the time (early 1980s) it was considered a secure field. But then along came the first of the index calculus algorithms which rendered this field insecure. Undeterred he simply increased the field order to a larger field size; of over 500 bits.
Working on discrete logarithm algorithms for such fields he introduced some concepts which are still used in modern algorithms; in particular the trick used for the descent stage. On one of his students giving a talk on this at IBM Don Coppersmith became intrigued and quickly came up with his L(1/3) algorithm for discrete logarithms in finite fields of characteristic two. This new algorithm rendered the second product obsolete; although actually breaking a 500 bit field took another 10 years.
The he moved onto looking at a new form of cryptography based on elliptic curves. At that time computing the number of points on a curve was hard (although polynomial time), and so he initially settled on supersingular curves. But during a reading group at the University of Waterloo on Burt Kaliski's thesis on group structures for elliptic curves, there came the realization that the Weil pairing could be used to translate the discrete logarithm problem on supersingular elliptic curves to an associated finite field.
Then he turned to looking at arithmetic for elliptic curves defined over GF(2155). But these soon were declared "weak" due to Weil descent attacks. Although, as Alf pointed out, despite intense effort over the last 15 years on such attacks no one is yet able to solve an ECDLP problem over the binary field of 155 bits.
Finally, Scott (and his company Certicom) settled on general ordinary elliptic curves. These were then possible to implement due to many groups having been able to now implement the algorithm to compute the number of points on a curve (an algorithm now included in many algebra systems). Scott evangelized the use of elliptic curves. The products of Certicom were used in products by RIM (now Blackberry), Pitney Bowes and Motorola. Then the NSA endorsed the use of elliptic curves for US government business via the Suite B standard. Scott also helped coordinate the efforts to produce standards in the area, launch conferences (the annual ECC conference was founded by him) and other aspects.
A non-elliptic curve major achievement was the co-authorship of the massive tome which the the Handbook of Applied Cryptography (or HAC to its friends). Scott conceived of the idea and with his co-authors he delivered a book which has been used by countless researchers to understand how cryptographic systems are used in the real world. And the book hardly mentions elliptic curves.
Scott was honored by being a Fellow of the Royal Society of Canada, a Fellow of the IACR (he served for six years on the IACR board of directors), he was also the recipient of the RSA Mathematics award and held the Ontario Premier's Catalyst Award for Lifetime Achievement in Innovation. As well as this he was one of the founding members of the Bristol Crypto groups Industrial Advisory Board.
On a personal note Scott was always a great supporter of young (and old) researchers; he encouraged me to keep working on ECC and I remember fondly the parties held at Scott and Sherry's house during the early ECC conferences in Waterloo. Scott helped encourage people around the world to work in the area, and ECC would not be the public key technology of choice that it is today without Scott's tireless work.
Alfred's talk ended with a picture of Alfred (who was Scott's PhD student) and Scott, along with Scott's PhD supervisor Ron Mullin, and Ron's PhD supervisor Bill Tutte (of Bletchley Park fame).
Working on discrete logarithm algorithms for such fields he introduced some concepts which are still used in modern algorithms; in particular the trick used for the descent stage. On one of his students giving a talk on this at IBM Don Coppersmith became intrigued and quickly came up with his L(1/3) algorithm for discrete logarithms in finite fields of characteristic two. This new algorithm rendered the second product obsolete; although actually breaking a 500 bit field took another 10 years.
The he moved onto looking at a new form of cryptography based on elliptic curves. At that time computing the number of points on a curve was hard (although polynomial time), and so he initially settled on supersingular curves. But during a reading group at the University of Waterloo on Burt Kaliski's thesis on group structures for elliptic curves, there came the realization that the Weil pairing could be used to translate the discrete logarithm problem on supersingular elliptic curves to an associated finite field.
Then he turned to looking at arithmetic for elliptic curves defined over GF(2155). But these soon were declared "weak" due to Weil descent attacks. Although, as Alf pointed out, despite intense effort over the last 15 years on such attacks no one is yet able to solve an ECDLP problem over the binary field of 155 bits.
Finally, Scott (and his company Certicom) settled on general ordinary elliptic curves. These were then possible to implement due to many groups having been able to now implement the algorithm to compute the number of points on a curve (an algorithm now included in many algebra systems). Scott evangelized the use of elliptic curves. The products of Certicom were used in products by RIM (now Blackberry), Pitney Bowes and Motorola. Then the NSA endorsed the use of elliptic curves for US government business via the Suite B standard. Scott also helped coordinate the efforts to produce standards in the area, launch conferences (the annual ECC conference was founded by him) and other aspects.
A non-elliptic curve major achievement was the co-authorship of the massive tome which the the Handbook of Applied Cryptography (or HAC to its friends). Scott conceived of the idea and with his co-authors he delivered a book which has been used by countless researchers to understand how cryptographic systems are used in the real world. And the book hardly mentions elliptic curves.
Scott was honored by being a Fellow of the Royal Society of Canada, a Fellow of the IACR (he served for six years on the IACR board of directors), he was also the recipient of the RSA Mathematics award and held the Ontario Premier's Catalyst Award for Lifetime Achievement in Innovation. As well as this he was one of the founding members of the Bristol Crypto groups Industrial Advisory Board.
On a personal note Scott was always a great supporter of young (and old) researchers; he encouraged me to keep working on ECC and I remember fondly the parties held at Scott and Sherry's house during the early ECC conferences in Waterloo. Scott helped encourage people around the world to work in the area, and ECC would not be the public key technology of choice that it is today without Scott's tireless work.
Alfred's talk ended with a picture of Alfred (who was Scott's PhD student) and Scott, along with Scott's PhD supervisor Ron Mullin, and Ron's PhD supervisor Bill Tutte (of Bletchley Park fame).
