Steven Galbraith Publications
New Papers and Preprints
 Lukas Zobernig and Steven D. Galbraith and Giovanni Russello, Indistinguishable Predicates: A New Tool for Obfuscation,
eprint 2017/787.
 Steven D. Galbraith and Frederik Vercauteren, Computational problems in supersingular elliptic curve isogenies,
eprint 2017/774.
 Steven D. Galbraith, Christophe Petit and Javier Silva, Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems, To appear at ASIACRYPT 2017, Cryptology ePrint Archive: Report 2016/1154.
Eprint updated October 26, 2017 with full version of the paper.
Best paper award at ASIACRYPT.
 Muhammad Rizwan Asghar, Steven D. Galbraith and Giovanni Russello, Obfuscation through simplicity, preprint, 2016.
 Shujie Cui, Muhammad Rizwan Asghar, Steven D. Galbraith and Giovanni Russello, ObliviousDB : Practical and Efficient Searchable Encryption with Controllable Leakage.
 Steven D. Galbraith, Joel Laity and Barak Shani, Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations, preprint, 2016.
 Shi Bai, Steven D. Galbraith, Liangze Li and Daniel Sheffield,
Improved Exponentialtime Algorithms for InhomogeneousSIS, eprint 2014/593.
 S. D. Galbraith, Spaceefficient variants of cryptosystems based on learning with errors, 2012.
Books
 S. D. Galbraith and M. Nandi (eds.), INDOCRYPT 2012,
Springer LNCS 7668, 2012.
 S. D. Galbraith, Mathematics of public key
cryptography, Cambridge University Press, April 2012.

S. D. Galbraith and
K. G. Paterson (eds), Pairing 2008,
Springer LNCS 5209, 2008.
 S. D. Galbraith,
Proceedings of the 11th IMA International Conference
on Cryptography and Coding,
Springer LNCS 4887, 2007.
Refereed Publications
2017
67. Steven D. Galbraith, Ping Wang and Fangguo Zhang, Computing Elliptic Curve Discrete Logarithms with Improved Babystep Giantstep Algorithm,
Advances in Mathematics of Communications (AMC), Volume 11, Issue 3 (2017) 453469.
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, 266281.
65. Shujie Cui, Muhammad Rizwan Asghar, Steven D. Galbraith and Giovanni Russello, PMcDb: Privacypreserving Search using Multicloud Encrypted Databases, 10th International Conference on Cloud Computing (CLOUD), IEEE (2017) 334341.
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) 6391.
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 1011, 2016. Springer LNCS 10005 (2016) 373383.
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) 5872.
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) 425440.
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) 5172.
Also see eprint 2015/1022.
2015
59. Steven D. Galbraith, Eduardo Morais and Ricardo Dahab, Adaptive key recovery attacks on NTRUbased somewhat homomorphic encryption schemes, in A. Lehmann and S. Wolf (eds), 8th International Conference on InformationTheoretic Security (ICITS), Springer LNCS 9063 (2015) 283296.
58. Steven D. Galbraith and Barak Shani, The Multivariate Hidden Number Problem, in A. Lehmann and S. Wolf (eds), 8th International Conference on InformationTheoretic Security (ICITS), Springer LNCS 9063 (2015) 250268.
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) 409427.
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) 7191.
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) 322337.
Also see: eprint 2013/0839.
54. Nagarjun C. Dwarakanath and Steven D. Galbraith, Efficient sampling from discrete Gaussians for latticebased cryptography on a constrained device. Applicable Algebra in Engineering, Communication and Computing,
Volume 25, Issue 3 (2014) 159180.
The final publication is available at Springer via http://link.springer.com/article/10.1007/s0020001402183.
53. Shi Bai and Steven D. Galbraith, An Improved Compression Technique for Signatures Based on Learning with Errors,
in J. Benaloh (Ed.), CTRSA 2014, LNCS 8366 (2014) 2847.
eprint 2013/838
2013
52. S. D. Galbraith and ChangAn Zhao, Selfpairings on hyperelliptic curves,
Journal of Mathematical Cryptology, Volume 7, Issue 1 (2013) 3142.
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) 107131.
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) 11811195.
eprint 2010/617.
2012
49. Steven D. Galbraith and Mark Holmes, A nonuniform birthday problem with
applications to discrete logarithms,
Discrete Applied Mathematics Vol. 160, No. 1011 (2012) 15471560.
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) 7189.
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) 110.
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) 446469.
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)
368383.
Full version:
eprint 2010/615.
2009
44. S. D. Galbraith and R. S. Ruprai,
An Improvement to the GaudrySchost Algorithm for Multidimensional Discrete Logarithm Problems,
in M. Parker (ed.),
Twelfth IMA International Conference on Cryptography and Coding,
Cirencester, Springer LNCS 5921 (2009) 368382.
Full version: pdf
43. S. D. Galbraith and X. Lin,
Computing Pairings Using xCoordinates Only,
Designs,
Codes and Cryptography, Vol. 50, No. 3
(2009) 305324.
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) 518535.
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) 118.
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) 4658.
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) 308327.
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) 265281.
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) 1327.
37. S. D. Galbraith and M. Scott,
Exponentiation in pairingfriendly groups using homomorphisms,
in S. D. Galbraith and K. G. Paterson (eds), Pairing 2008,
Springer LNCS 5209 (2008) 211224.
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) 342356.
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) 31133121
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) 57195728.
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) 108131.
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) 267281.
Early version: eprint 2006/169.
31. W. D. Benits Jr. and S. D. Galbraith,
Constructing pairingfriendly elliptic curves
using Groebner basis reduction,
in S. D. Galbraith (ed.),
Cryptography and Coding, Springer LNCS 4887
(2007) 336345.
30. S. D. Galbraith, J. McKee and P. Valença,
Ordinary abelian varieties having small embedding degree,
Finite Fields and Their Applications, 13 (2007) 800814.
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) 2945.
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) 239271.
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) 1214.
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.), ANTSVII,
Springer LNCS 4076 (2006) 436451.
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) 280292.
Publisher's
link
Full version:
pdf.
For cryptanalysis also see:
D. Bleichenbacher and A. May,
New attacks on RSA with small secret CRTexponents,
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) 544577.
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)
392409.
Journal link
Full version:
pdf.
2004
22. S. D. Galbraith, H. Hopkins and I. Shparlinski,
Secure Bilinear DiffieHellman Bits,
in H. Wang, J. Pieprzyk and V. Varadharajan (eds.),
ACISP 2004, Springer LNCS 3108 (2004) 370378.
Earlier version:
eprint 2002/155.
21. S. D. Galbraith and V. Rotger,
Easy decision DiffieHellman groups,
LMS
J. Comput. Math. 7 (2004) 201218.
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 CTRSA 2003,
Springer LNCS
2612 (2003) 8097.
Full version.
Early version:
Anonymity and denial of undeniable and confirmer signatures,
HP Labs technical report
HPL2001303 (2001).
19. S. D. Galbraith,
Weil descent of Jacobians,
Discrete Applied Mathematics Vol. 128, Issue 1, (2003) 165180.
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,
RSAbased undeniable signatures for
general moduli,
in B. Preneel (ed.), Topics in Cryptology  CTRSA 2002,
Springer LNCS
2271, p. 200217 (2002)
Full version.
Preliminary version: HP
Labs technical report HPL2001304,
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) 2944.
16. S. D. Galbraith, Elliptic curve Paillier schemes,
Journal
of Cryptology, Vol. 15, No. 2 (2002) 129138.
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. MaloneLee, N. P. Smart,
Public key signatures in the multiuser setting,
Information Processing Letters,
Volume 83, Issue 5 (2002) 263266.
Journal link.
14. S. D. Galbraith, K. Harrison and D. Soldera,
Implementing the Tate pairing, in C. Fieker and D. Kohel (eds.),
ANTSV,
Springer LNCS
2369 (2002) 324337.
ANTS slides.
Preliminary version:
HewlettPackard laboratories technical report HPL200223.
Biographical Note: This was a race with BarretoKimLynnScott. But we are all friends now.
13. S. D. Galbraith, Rational points on X_{0}^{+}(N) and
quadratic Qcurves,
J. de la Theorie des Nombres de Bordeaux, 14
(2002) 205219.
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) 393405.
Preliminary Version:
HewlettPackard Labs
technical report HPL98179 (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) 495513.
Asiacrypt slides.
Full version: pdf.
Biographical Note: Parts of this paper were once rejected for being "wellknown", but now
it is one of my mostcited papers.
10. S. D. Galbraith, Limitations of
constructive Weil descent,
in Alster, Kazimierz (ed.) et al.,
PublicKey Cryptography and Computational Number Theory
September 1115, 2000, Warsaw, Poland,
Walter de Gruyter (2001) 5970.
Full version: ps.
2000
9. S. R. Blackburn, S. D. Galbraith,
Certification of secure RSA keys,
Electronics Letters, Vol. 36, No. 1, p. 2930 (2000)
Full Version: University of Waterloo
technical report CORR 9944 (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. 671684 (2000)
Full version: pdf.
Preliminary version: University of Waterloo
technical report CORR 9951 (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. 191200 (1999)
Preliminary version:
HewlettPackard Labs technical report HPL199970 (1999).
5. S. R. Blackburn, M. Burmester, S. BlakeWilson, S. D. Galbraith,
Weaknesses in shared RSA key generation,
in Codes and Cryptography, Cirencester,
Springer LNCS 1746, p. 300306 (1999)
4. S. R. Blackburn, S. D. Galbraith,
Cryptanalysis of two cryptosystems based on group actions,
ASIACRYPT'99,
Springer LNCS
1716, p. 5261 (1999)
3. S. D. Galbraith, Constructing isogenies between elliptic curves over finite
fields,
London Math. Soc.,
Journal of Computational Mathematics, Vol. 2 (1999)
p. 118138.
Full version: pdf.
2. S. D. Galbraith, Rational points on X_{0}^{+}(p),
Experimental
Math., 8, No. 4, p. 311318 (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. 7679 (1999)
Biographical Note: This was a survey paper with no interesting content.
I hope noone reads it now.
Old Preprints and Technical Reports
 S. Blackburn, S. BlakeWilson, M. Burmester, S. Galbraith,
Shared generation of shared RSA keys,
University of Waterloo technical report CORR 9819 (1998)
 S. D. Galbraith,
The Weil pairing on elliptic curves over C,
preprint (2005).
 S. Galbraith, W. Mao, K. G. Paterson,
A cautionary note regarding cryptographic protocols
based on composite integers,
HP
labs technical report HPL2001284.
 S. D. Galbraith,
Disguising tori and elliptic curves,
eprint 2006/248.
 S. D. Galbraith and B. A. Smith,
Discrete Logarithms in Generalized Jacobians,
arxiv math.NT/0610073.
 W. Castryck, S. D. Galbraith and R. Rezaeian Farashahi,
Efficient arithmetic on elliptic curves using a mixed
EdwardsMontgomery representation,
eprint 2008/218.
Back
Last Modified: 3112017