Steven Galbraith Publications

New Papers and Preprints

Books

Refereed Publications

2012

49. S. D. Galbraith and M. Holmes, A non-uniform birthday problem with applications to discrete logarithms, Discrete Applied Mathematics Vol. 160, No. 10-11 (2012) 1547-1560.
eprint 2010/616.

2011

48. R. Avanzi, W. D. Benits Jr., S. D. Galbraith and J. McKee, On the distribution of the coefficients of normal forms for Frobenius Expansions, Designs, Codes and Cryptography, Volume 61, Number 1 (2011) 71-89.

47. P. N. J. Eagle, S. D. Galbraith and J. Ong, Point compression for Koblitz curves, Advances in Mathematics of Communication, Volume 5, Number 1 (2011) 1-10.
Early version:
P. N. J. Eagle and S. D. Galbraith, Point Compression for Koblitz Elliptic Curves, eprint 2009/086.

46. S. D. Galbraith, X. Lin and M. Scott, Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves, Journal of Cryptology, Volume 24, Number 3 (2011) 446-469.
Also available as: eprint 2008/194

2010

45. S. D. Galbraith and R. S. Ruprai, Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval, in P. Nguyen and D. Pointcheval (eds.), PKC 2010, Springer LNCS 6056 (2010) 368-383.
Full version: eprint 2010/615.

2009

44. S. D. Galbraith and R. S. Ruprai, An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems, in M. Parker (ed.), Twelfth IMA International Conference on Cryptography and Coding, Cirencester, Springer LNCS 5921 (2009) 368-382.
Full version: pdf

43. S. D. Galbraith and X. Lin, Computing Pairings Using x-Coordinates Only, Designs, Codes and Cryptography, Vol. 50, No. 3 (2009) 305-324.
Early version: eprint 2008/019.

42. S. D. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curve cryptography on general curves, in A. Joux (ed.), EUROCRYPT 2009, Springer LNCS 5479 (2009) 518-535.

41. S. D. Galbraith, J. Pujolas, C. Ritzenthaler and B. A. Smith, Distortion maps for genus two curves, Journal of Mathematical Cryptology, Volume 3, Issue 1 (2009) 1-18.
Preprint version: arxiv math.NT/0611471.
Much earlier version:
S. D. Galbraith and J. Pujolas, Distortion maps for genus two curves, in R. Cramer and T. Okamoto (eds.), Proceedings of a workshop on Mathematical Problems and Techniques in Cryptology, CRM Barcelona (2005) 46--58.

2008

40. S. D. Galbraith and E. R. Verheul, An analysis of the vector decomposition problem, in R. Cramer (ed), PKC 2008, Springer LNCS 4939 (2008) 308-327.
Full version

39. S. D. Galbraith, X. Lin and D. J. Mireles, Pairings on hyperelliptic curves with a real model, in S. D. Galbraith and K. G. Paterson (eds), Pairing 2008, Springer LNCS 5209 (2008) 265--281.
Early version: eprint 2008/250

38. W. D. Benits Jr. and S. D. Galbraith, The GPS identification scheme using Frobenius expansions, in S. Lucks, A.-R. Sadeghi and C. Wolf (eds.), Research in Cryptology, Proceedings of the Second Western European Workshop, WEWoRC 2007, Bochum, Germany, Springer LNCS 4945 (2008) 13-27.

37. S. D. Galbraith and M. Scott, Exponentiation in pairing-friendly groups using homomorphisms, in S. D. Galbraith and K. G. Paterson (eds), Pairing 2008, Springer LNCS 5209 (2008) 211--224.
Early version: eprint 2008/117

36. S. D. Galbraith, M. Harrison and D. Mireles, Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors, in A. J. van der Poorten and A. Stein (eds.), ANTS 2008, Springer LNCS 5011 (2008) 342--356.
Journal link
Full version: pdf.
Biographical Note: My PhD student Dave worked this out, but then we found out that Mike had already discovered it and implemented it in Magma, but had never got around to writing it up.

35. S. D. Galbraith, K. G. Paterson and N. P. Smart, Pairings for cryptographers, Discrete Applied Mathematics, Volume 156, Issue 16 (2008) 3113-3121
Journal link: doi:10.1016/j.dam.2007.12.010
Early version: eprint 2006/165.
Biographical note: The original title of this paper was "pairings for dummies".

34. S. D. Galbraith, F. Hess and F. Vercauteren, Aspects of pairing inversion, IEEE Trans. Information Theory, Volume 54, Issue 12 (2008) 5719-5728.
Early version: eprint 2007/256.

2007

33. S. D. Galbraith, F. Hess and F. Vercauteren, Hyperelliptic pairings, in T. Takagi et al (eds), Pairing 2007, Springer LNCS 4575 (2007) 108--131.
Full version: pdf.

32. S. D. Galbraith, C. O hEigeartaigh, C. Sheedy, Simplified pairing computation and security implications, J. Mathematical Crypt, Vol. 1, No. 3 (2007) 267--281.
Early version: eprint 2006/169.

31. W. D. Benits Jr. and S. D. Galbraith, Constructing pairing-friendly elliptic curves using Groebner basis reduction, in S. D. Galbraith (ed.), Cryptography and Coding, Springer LNCS 4887 (2007) 336--345.

30. S. D. Galbraith, J. McKee and P. Valença, Ordinary abelian varieties having small embedding degree, Finite Fields and Their Applications, 13 (2007) 800--814.
Early version: eprint 2004/365.
The early version was also printed as:
S. D. Galbraith, J. McKee and P. Valença, Ordinary abelian varieties having small embedding degree, in R. Cramer and T. Okamoto (eds.), Proceedings of a workshop on Mathematical Problems and Techniques in Cryptology, CRM Barcelona (2005) 29--45.
For full tables of families of elliptic curves with cofactors up to 1024 see Paula Valença's web page.

29. P. S. L. M. Barreto, S. D. Galbraith, C. O'hEigeartaigh and M. Scott, Efficient Pairing Computation on Supersingular Abelian Varieties, Designs, Codes and Cryptography, Vol. 42, No. 3 (2007) 239--271. Online.
Earlier version: eprint 2004/375.
Biographical Note: We worked on this paper for a very long time, and it got bigger and bigger.

2006

28. S. R. Blackburn, C. Cid and S. D. Galbraith, Cryptanalysis of a Cryptosystem based on Drinfeld modules, IEE Proceedings Information Security, Vol. 153, No. 1 (2006) 12--14.
Earlier version: eprint 2003/223.

27. A. W. Dent and S. D. Galbraith, Hidden Pairings and Trapdoor DDH Groups, in F. Hess, S. Pauli and M. Pohst (eds.), ANTS-VII, Springer LNCS 4076 (2006) 436--451.

2005

26. S. D. Galbraith, Pairings, Chapter IX of book Advances in elliptic curve cryptography edited by I. Blake, G. Seroussi and N. Smart, Cambridge University Press, 2005.

25. S. D. Galbraith, C. Heneghan and J. McKee, Tunable balancing of RSA, in C. Boyd and J. M. Gonzalez Nieto (eds.), ACISP 2005, Springer LNCS 3574 (2005) 280--292.
Publisher's link
Full version: pdf.
For cryptanalysis also see: D. Bleichenbacher and A. May, New attacks on RSA with small secret CRT-exponents, PKC 2006, Springer LNCS 3958.

24. S. D. Galbraith and A. Menezes, Algebraic curves and cryptography, Finite Fields and Applications, Volume 11, Issue 3 (2005) 544--577.
Earlier version: CACR Technical report 2005/2.

23. S. D. Galbraith and J. F. McKee, Pairings on elliptic curves over finite commutative rings, in N. P. Smart (ed.), Cryptography and Coding: 10th IMA International Conference, Cirencester, UK, Springer LNCS 3796 (2005) 392--409.
Journal link

2004

22. S. D. Galbraith, H. Hopkins and I. Shparlinski, Secure Bilinear Diffie-Hellman Bits, in H. Wang, J. Pieprzyk and V. Varadharajan (eds.), ACISP 2004, Springer LNCS 3108 (2004) 370--378.
Earlier version: eprint 2002/155.

21. S. D. Galbraith and V. Rotger, Easy decision Diffie-Hellman groups, LMS J. Comput. Math. 7 (2004) 201--218.
Early draft version.
Slides from a survey of this work presented in August 2004 at Chuo University, Tokyo.
Biographical Note: I lectured on these questions in Spain, and Victor was in the audience. He had some ideas which we worked on for some months by email.

2003

20. S. D. Galbraith and W. Mao, Invisibility and anonymity of undeniable and confirmer signatures, in M. Joye (ed.) Topics in Cryptology CT-RSA 2003, Springer LNCS 2612 (2003) 80--97.
Full version.
Early version: Anonymity and denial of undeniable and confirmer signatures, HP Labs technical report HPL-2001-303 (2001).

19. S. D. Galbraith, Weil descent of Jacobians, Discrete Applied Mathematics Vol. 128, Issue 1, (2003) 165--180.
Electronic Journal link
Full version.
Conference version published as:
S. D. Galbraith, Weil descent of Jacobians, in D. Augot and C. Carlet (eds.), WCC2001, Elsevier, Electron. Notes Discrete Math. 6 (2001).

2002

18. S. D. Galbraith, W. Mao, K. G. Paterson, RSA-based undeniable signatures for general moduli, in B. Preneel (ed.), Topics in Cryptology - CT-RSA 2002, Springer LNCS 2271, p. 200-217 (2002)
Full version.
Preliminary version: HP Labs technical report HPL-2001-304,

17. S. D. Galbraith, F. Hess, N. P. Smart, Extending the GHS Weil descent attack, in L. Knudsen (ed.), EUROCRYPT 2002, Springer LNCS 2332 (2002) 29--44.

16. S. D. Galbraith, Elliptic curve Paillier schemes, Journal of Cryptology, Vol. 15, No. 2 (2002) 129--138.
Full version.
Note: This paper contains the work of both of the preprints `Cryptanalysis of some elliptic curve based cryptosystems of Paillier' and `An elliptic curve Paillier scheme'.
Biographical Note: This has always been one of my favourite papers. I think because I learnt a lot about formal groups from writing it.

15. S. D. Galbraith, J. Malone-Lee, N. P. Smart, Public key signatures in the multi-user setting, Information Processing Letters, Volume 83, Issue 5 (2002) 263--266.
Journal link.

14. S. D. Galbraith, K. Harrison and D. Soldera, Implementing the Tate pairing, in C. Fieker and D. Kohel (eds.), ANTS-V, Springer LNCS 2369 (2002) 324--337.
ANTS slides.
Preliminary version: Hewlett-Packard laboratories technical report HPL-2002-23.
Biographical Note: This was a race with Barreto-Kim-Lynn-Scott. But we are all friends now.

13. S. D. Galbraith, Rational points on X0+(N) and quadratic Q-curves, J. de la Theorie des Nombres de Bordeaux, 14 (2002) 205--219.
Full version: pdf.
Biographical Note: This paper comes out of my thesis, many years later. Some of the computations were extremely difficult to perform.

12. S. D. Galbraith, S. Paulus, N. P. Smart, Arithmetic on superelliptic curves, Mathematics of Computation 71, No. 237 (2002) 393-405.
Preliminary Version: Hewlett-Packard Labs technical report HPL-98-179 (1998).
Biographical Note: This paper took a very very long time to be published.

2001

11. S. D. Galbraith, Supersingular curves in cryptography, in C. Boyd (ed.) ASIACRYPT 2001, Springer LNCS 2248 (2001) 495--513.
Asiacrypt slides.
Full version: pdf.
Biographical Note: Parts of this paper were once rejected for being "well-known", but now it is one of my most-cited papers.

10. S. D. Galbraith, Limitations of constructive Weil descent, in Alster, Kazimierz (ed.) et al., Public-Key Cryptography and Computational Number Theory September 11-15, 2000, Warsaw, Poland, Walter de Gruyter (2001) 59--70.
Full version: ps.

2000

9. S. R. Blackburn, S. D. Galbraith, Certification of secure RSA keys, Electronics Letters, Vol. 36, No. 1, p. 29-30 (2000)
Full Version: University of Waterloo technical report CORR 99-44 (1999)

8. S. D. Galbraith, J. F. McKee, The probability that the number of points on an elliptic curve over a finite field is prime, Journal of the London Mathematical Society, 62, no. 3, p. 671-684 (2000)
Full version: pdf.
Preliminary version: University of Waterloo technical report CORR 99-51 (1999)

7. S. D. Galbraith, On the efficiency of elliptic curves arising in French literature, In Journal of Craptology (2000).
Biographical Note: Of course, I am very proud of this paper.

1999

6. S. D. Galbraith, N. P. Smart, A cryptographic application of Weil descent, in Codes and Cryptography, Cirencester, Springer LNCS 1746, p. 191-200 (1999)
Preliminary version: Hewlett-Packard Labs technical report HPL-1999-70 (1999).

5. S. R. Blackburn, M. Burmester, S. Blake-Wilson, S. D. Galbraith, Weaknesses in shared RSA key generation, in Codes and Cryptography, Cirencester, Springer LNCS 1746, p. 300-306 (1999)

4. S. R. Blackburn, S. D. Galbraith, Cryptanalysis of two cryptosystems based on group actions, ASIACRYPT'99, Springer LNCS 1716, p. 52-61 (1999)

3. S. D. Galbraith, Constructing isogenies between elliptic curves over finite fields, London Math. Soc., Journal of Computational Mathematics, Vol. 2 (1999) p. 118-138.
Full version: pdf.

2. S. D. Galbraith, Rational points on X0+(p), Experimental Math., 8, No. 4, p. 311-318 (1999)
Biographical Note: This paper comes from my PhD thesis. It took a long time to get written up properly and published.

1. S. D. Galbraith, Elliptic curve public key cryptography, Mathematics Today, 35, No. 3, p. 76-79 (1999)
Biographical Note: This was a survey paper with no interesting content. I hope no-one reads it now.

Old Preprints and Technical Reports

Back

Last Modified: 27-10-2011