Steven Galbraith Publications


New Papers and Preprints


Books


Refereed Publications

2017

67. Steven D. Galbraith, Ping Wang and Fangguo Zhang, Computing Elliptic Curve Discrete Logarithms with Improved Baby-step Giant-step Algorithm, Advances in Mathematics of Communications (AMC), Volume 11, Issue 3 (2017) 453-469.
eprint/2015/605.

66. Shujie Cui, Muhammad Rizwan Asghar, Steven D. Galbraith and Giovanni Russello, Secure and Practical Searchable Encryption: A Position Paper, ACISP 2017, Springer LNCS 10342, 266-281.

65. Shujie Cui, Muhammad Rizwan Asghar, Steven D. Galbraith and Giovanni Russello, P-McDb: Privacy-preserving Search using Multi-cloud Encrypted Databases, 10th International Conference on Cloud Computing (CLOUD), IEEE (2017) 334-341.

2016

64. Steven D. Galbraith, C. Petit, B. Shani and Yan Bo Ti, On the Security of Supersingular Isogeny Cryptosystems, in J. H. Cheon and T. Takagi (eds), ASIACRYPT 2016, Springer LNCS 10031 (2016) 63-91.
eprint 2016/859

63. Zengpeng Li, Steven D. Galbraith and Chunguang Ma, Preventing Adaptive Key Recovery Attacks on the GSW Levelled Homomorphic Encryption Scheme, in Liqun Chen and Jinguang Han (eds), Proceedings Provable Security - 10th International Conference, ProvSec 2016, Nanjing, China, November 10-11, 2016. Springer LNCS 10005 (2016) 373-383.
Extended full version eprint 2016/1146

62. Steven D. Galbraith, Shishay W. Gebregiyorgis and Sean Murphy, Algorithms for the Approximate Common Divisor Problem, LMS J. Comput. Math. 19 (Special issue A) (2016) 58-72.
Full version on eprint.

61. Christina Delfs and Steven D. Galbraith, Computing isogenies between supersingular elliptic curves over F_p, Designs, Codes and Cryptography, Volume 78, Issue 2 (2016) 425-440.
arXiv:1310.7789

60. Steven D. Galbraith and Pierrick Gaudry,
Recent progress on the elliptic curve discrete logarithm problem, Designs, Codes and Cryptography, Volume 78, Issue 1 (2016) 51-72.
Also see eprint 2015/1022.

2015

59. Steven D. Galbraith, Eduardo Morais and Ricardo Dahab, Adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes, in A. Lehmann and S. Wolf (eds), 8th International Conference on Information-Theoretic Security (ICITS), Springer LNCS 9063 (2015) 283-296.

58. Steven D. Galbraith and Barak Shani, The Multivariate Hidden Number Problem, in A. Lehmann and S. Wolf (eds), 8th International Conference on Information-Theoretic Security (ICITS), Springer LNCS 9063 (2015) 250-268.

2014

57. Steven D. Galbraith and Shishay W. Gebregiyorgis, Summation polynomial algorithms for elliptic curves in characteristic two, in W. Meier and D. Mukhopadhyay (eds), INDOCRYPT 2014, Springer LNCS 8885 (2014) 409-427.
eprint 2014/086

56. Ilya Chevyrev and Steven D. Galbraith, Constructing supersingular elliptic curves with a given endomorphism ring, LMS Journal of Computation and Mathematics, Volume 17, Special Issue A (2014) 71-91.
Early version: Distinguishing Maximal Orders of Quaternion Algebras by their Short Elements, arXiv:1301.6875

55. Shi Bai and Steven D. Galbraith, Lattice Decoding Attacks on Binary LWE, in W. Susilo and Y. Mu (eds.), ACISP 2014, Springer LNCS 8544 (2014) 322-337.
Also see: eprint 2013/0839.

54. Nagarjun C. Dwarakanath and Steven D. Galbraith, Efficient sampling from discrete Gaussians for lattice-based cryptography on a constrained device. Applicable Algebra in Engineering, Communication and Computing, Volume 25, Issue 3 (2014) 159-180.
The final publication is available at Springer via http://link.springer.com/article/10.1007/s00200-014-0218-3.

53. Shi Bai and Steven D. Galbraith, An Improved Compression Technique for Signatures Based on Learning with Errors, in J. Benaloh (Ed.), CT-RSA 2014, LNCS 8366 (2014) 28-47.
eprint 2013/838

2013

52. S. D. Galbraith and Chang-An Zhao, Self-pairings on hyperelliptic curves, Journal of Mathematical Cryptology, Volume 7, Issue 1 (2013) 31-42.
There is an erratum to this paper. But it is correcting an error by the journal, not an error by us.

51. S. D. Galbraith and Anton Stolbunov, Improved algorithm for the isogeny problem for ordinary elliptic curves, Applicable Algebra in Engineering, Communication and Computing, Vol. 24, No. 2 (2013) 107-131.
arxiv version

50. S. D. Galbraith, John M. Pollard and Raminder S. Ruprai, Computing discrete logarithms in an interval, Math. Comp., 82, No. 282 (2013) 1181-1195.
eprint 2010/617.

2012

49. Steven D. Galbraith and Mark 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. Roberto Avanzi, Waldyr D. Benits Jr., Steven D. Galbraith and James 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. Philip N. J. Eagle, Steven D. Galbraith and John 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. Steven D. Galbraith, Xibin Lin and Michael 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.
Errata: Igor Shparlinski pointed out (January 12, 2010) that the proof of Lemma 15 is not complete. One would need to show there are families consisting of pairs (r,q) which are prime.

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.

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
Full version: pdf.

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: 3-11-2017