Portrait of Patrick Longa

Patrick Longa

Senior Software Development Engineer

About

I am a researcher and developer with the MSR-T Security and Cryptography team at Microsoft Research, in Redmond.

I completed my Ph.D. in Electrical and Computer Engineering at the University of Waterloo in 2011, after which I briefly occupied a post-doc position in the Department of Combinatorics and Optimization (C&O) of the same university. During my time at Waterloo, I was a member of the Centre for Applied Cryptographic Research (CACR) and the Laboratory for Side-Channel Security of Embedded Systems.

My research interests mainly involve elliptic curve and pairing-based cryptography, post-quantum cryptography, efficient algorithmic design, high-performance implementation of cryptographic primitives, and side-channel analysis attacks and countermeasures.

Projects

Publications

Other

News

  • June/2016  Version 2.0 of FourQlib has been released. See project webpage.
  • April/2016  LatticeCrypto, a high-performance and portable software library that implements lattice-based cryptographic algorithms, is released (version 1.0). See project webpage.
  • April/2016  SIDH, a fast and portable library supporting post-quantum secure supersingular isogeny Diffie-Hellman key exchange, is released (version 1.0). See project webpage.
  • September/2015  FourQlib, a secure and efficient library supporting FourQ, is released (version 1.0). See project webpage.
  • June/2015  FourQ, a new high-security high-performance elliptic curve for the 128-bit sec level, is introduced. See paper and slides at the NIST Workshop on Elliptic Curve Cryptography Standards 2015.
  • June/2015  Version 2.0 of MSR ECCLib has been released. See project webpage.
  • January/2015  Ted37919, a new high-performance high-security curve for the 192-bit sec level, is introduced at RWC 2015. See the slides.
  • July/2014  Version 1.1 of MSR ECCLib has been released. See project webpage.
  • June/2014  MSR ECCLib, an efficient, portable and secure elliptic curve cryptography library that supports the NUMS curves, is released. See project webpage.
  • June/2014  A set of efficient, high-security elliptic curves, called NUMS (Nothing Up My Sleeve) curves, is formally announced. For curve specifications and parameters, see this document.
  • Mar/2013  New speed record for computing constant-time elliptic curve point multiplication on x86-64 and ARM processors. See paper.
  • Aug/2012  New speed record for computing non-constant-time and constant-time elliptic curve point multiplication on x86-64 processors. See paper ([Slides] at Asiacrypt 2012). We also held the previous records reported here (06/2011, published at Designs, Codes and Cryptography) and here (08/2010, CHES 2010 [Slides]).
  • July/2012  New speed record for computing pairings on ARM processors. See paper.
  • Sep/2011  Invited speaker at the 15th Workshop on Elliptic Curve Cryptography (ECC 2011), Sep 19-21 in Nancy, France [Slides].
  • Apr/2011  My Ph.D. thesis titled “High-Speed Elliptic Curve and Pairing-Based Cryptography” is online!
  • Oct/2010  New speed record for computing pairings on x86-64 processors. See paper.

Recent Talks

Recent Talks

  • Invited lecture at the S3 – Summer School (SAC 2016): “Software Implementation of Public-Key Cryptography”, St. John’s, Canada, August 2016.
  • Slides from my talk at SAC 2016: “FourQNEON: faster elliptic curve scalar multiplications on ARM processors”, St. John’s, Canada, August 2016.
  • Slides from my invited talk at the University of Luxembourg: “FourQ: pushing the limits of curve-based cryptography”, Luxembourg, November 2015.
  • Slides from my invited talk at COSIC – KU Leuven: “FourQ and FourQlib: faster curve-based scalar multiplications”, Leuven, Belgium, November 2015.
  • Slides from my talk at the NIST Workshop on Elliptic Curve Cryptography Standards, “An Analysis of High-Performance Primes at High-Security Levels”, Gaithersburg, MD, June 2015.
  • Slides from my talk at the Real World Cryptography Workshop 2015, “Post-Snowden Elliptic Curve Cryptography”, London, UK, January 2015.
  • Slides from my invited talk at the University of Washington (Tacoma): “NUMS Elliptic Curves and their Implementation”, Tacoma, WA, November 2014.
  • Slides from my presentation for the IETF Crypto Forum Research Group (CFRG), “Selecting Elliptic Curves for Cryptography”, interim teleconference meeting, April 2014.
  • Slides from my talk at CT-RSA 2014: “Efficient and Secure Methods for GLV-Based Scalar Multiplication and their Implementation on GLV-GLS Curves”, San Francisco, USA, February 2014.
  • Slides from my talk at ASIACRYPT2012: “Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication”, Beijing, China, December 2012.
  • Slides from my invited talk at the Peking University: “Highly-Efficient and Secure Elliptic Curve Scalar Multiplication using the 4-GLV Method”, Beijing, China, December 2012.
  • Slides from my invited talk at the 15th Workshop on Elliptic Curve Cryptography (ECC2011): “Elliptic Curve Cryptography at High Speeds”, Nancy, France, September 2011.
  • Slides from my talk at EUROCRYPT2011: “Faster Explicit Formulas for Computing Pairings over Ordinary Curves”, Tallinn, Estonia, May 2011.
  • Slides from my talk at CHES2010: “Efficient Techniques for High-Speed Elliptic Curve Cryptography”, University of California, Sta. Barbara, California, USA, August 2010.
  • Slides from my talk at the Centre for Applied Cryptographic Research (CACR): “Record-Breaking Implementations of Elliptic Curve Scalar Multiplication on x86-64 Processors”, University of Waterloo, Waterloo, Canada, July 2010.
  • Slides from my invited talk at the MITACS Workshop on Network Security and Cryptography 2010: “High-Speed Elliptic Curve Cryptography: New Records in Software”, Toronto, Canada, June 2010.

Recent Publications

Recent Publications

  • Patrick Longa, “FourQNEON: Faster Elliptic Curve Scalar Multiplications on ARM Processors”, Selected Areas in Cryptography (SAC 2016), August 2016. Posted as Cryptology ePrint Report 2016/645, June 2016. [paper]
  • Kimmo Järvinen, Andrea Miele, Reza Azarderakhsh and Patrick Longa, “FourQ on FPGA: New Hardware Speed Records for Elliptic Curve Cryptography over Large Prime Characteristic Fields”Workshop on Cryptographic Hardware and Embedded Systems (CHES 2016), August 2016. Posted as Cryptology ePrint Report 2016/569, June 2016. [paper]
  • Patrick Longa and Michael Naehrig, “Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography”, posted as Cryptology ePrint Report 2016/504, May 2016. [paper]
  • Craig Costello, Patrick Longa and Michael Naehrig, “Efficient algorithms for supersingular isogeny Diffie-Hellman”, Advances in Cryptology – CRYPTO 2016, 2016. Extended version posted as Cryptology ePrint Report 2016/413, April 2016. [paper]
  • R. Azarderakhsh, D. Fishbein, G. Grewal, S. Hu, D. Jao, P. Longa and R. Verma, “Fast Software Implementations of Bilinear Pairings”, IEEE Transactions on Dependable and Secure Computing, 2015. Posted as CACR Technical Report, CACR 2016-03, January 2016. [paper]
  • Craig Costello and Patrick Longa, “FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime”, Advances in Cryptology – ASIACRYPT 2015, December 2015. Full paper version posted as Cryptology ePrint Report 2015/565, June 2015. [paper]
  • Craig Costello, Patrick Longa, and Michael Naehrig, “A brief discussion on selecting new elliptic curves“, no. MSR-TR-2015-46, 8 June 2015.
  • Joppe Bos, Craig Costello, Patrick Longa, and Michael Naehrig, “Specification of Curve Selection and Supported Curve Parameters in MSR ECCLib“, no. MSR-TR-2015-49, June 2015.
  • Joppe Bos, Craig Costello, Patrick Longa, and Michael Naehrig, “Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis”, Journal of Cryptographic Engineering (to appear), May 2015. Posted as Cryptology ePrint Report 2013/130, February 2014. [paper]
  • A. Faz-Hernandez, P. Longa, and A.H. Sanchez, “Efficient and Secure Methods for GLV-Based Scalar Multiplication and their Implementation on GLV-GLS Curves (Extended Version)”, Journal of Cryptographic Engineering, April 2015. Posted as Cryptology ePrint Report 2013/158, March 2013. [paper]
  • A. Faz-Hernandez, P. Longa, and A.H. Sanchez, “Efficient and Secure Methods for GLV-Based Scalar Multiplication and their Implementation on GLV-GLS Curves”RSA Conference Cryptographers’ Track (CT-RSA 2014), February 2014. [paper]
  • D.F. Aranha, P.S.L.M. Barreto, P. Longa, and J. Ricardini, “The Realm of The Pairings” (Invited Paper), Selected Areas in Cryptography (SAC 2013), 2013. Posted as Cryptology ePrint Report 2013/722, November 2013. [paper]
  • P. Longa, and F. Sica, “Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication” (Full Version), Journal of Cryptology, April 2014. Posted as Cryptology ePrint Report 2011/608, November 2011. [paper]
  • P. Longa, and F. Sica, “Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication”, Advances in Cryptology – ASIACRYPT 2012, 2012. [paper]
  • G. Grewal, R. Azarderakhsh, P. Longa, S. Hu, and D. Jao, “Efficient Implementation of Bilinear Pairings on ARM Processors”, Selected Areas in Cryptography (SAC 2012), 2012. The full version is posted as Cryptology ePrint Report 2012/408, July 2012. [paper]
  • Z. Hu, P. Longa, and M. Xu, “Implementing 4-Dimensional GLV Method on GLS Elliptic Curves with j-Invariant 0”Designs, Codes and Cryptography, June 2012. The full version is posted as Cryptology ePrint Report 2011/315, June 2011. [paper]
  • D.F. Aranha, K. Karabina, P. Longa, C. Gebotys, and J. Lopez, “Faster Explicit Formulas for Computing Pairings over Ordinary Curves”, Advances in Cryptology – EUROCRYPT 2011, 2011. The full version is posted as Cryptology ePrint Report 2010/526, October 2010. [paper]
  • P. Longa, and C. Gebotys, “Efficient Techniques for High-Speed Elliptic Curve Cryptography”, Workshop on Cryptographic Hardware and Embedded Systems (CHES 2010), 2010. The full version is posted as Cryptology ePrint Report 2010/315, May 2010. [paper]
  • P. Longa, C. Gebotys, “Fast Multibase Methods and Other Several Optimizations for Elliptic Curve Scalar Multiplication”Public-Key Cryptography (PKC 2009), 2009. The full version is posted as Cryptology ePrint Report 2009/173, April 2009. [paper]
  • P. Longa, C. Gebotys, “Novel Precomputation Schemes for Elliptic Curve Cryptosystems”, Applied Cryptography and Network Security (ACNS 2009), 2009. The full version is posted as Cryptology ePrint Report 2008/526, Dec 2008. [paper]
  • P. Longa, A. Miri, “New Composite Operations and Precomputation Scheme for Elliptic Curve Cryptosystems over Prime Fields”, Public-Key Cryptography (PKC 2008), 2008. The full version is posted as Cryptology ePrint Report 2008/051, Jan 2008. [paper]
  • P. Longa, A. Miri, “Fast and Flexible Elliptic Curve Point Arithmetic over Prime Fields”IEEE Transactions on Computers, 2008. [paper]

Theses

Theses

  • P. Longa, “High-Speed Elliptic Curve and Pairing-Based Cryptography”, Ph.D. Thesis, University of Waterloo, April 2011. The full text can be accessed in [Ph.D. Thesis].
  • P. Longa, “Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields”. Master’s Thesis, University of Ottawa, June 2007. The full text can be accessed in [Master’s Thesis].

Professional Activities

Professional Activities

I serve(d) on the following program committees:

  • 19th Information Security Conference (ISC 2016).
  • 3rd International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2014).
  • XVIII IEEE International Conference of Electrical, Electronics and Systems Engineering (INTERCON 2011).

I reviewed papers for the following journals: Journal of Cryptology, IEEE Transactions on Computers, IEEE Transactions on Very Large Scale Integration Systems (VLSI), Journal of Cryptographic Engineering (JCEN), IET Circuits, Devices & Systems, International Journal of Computer Mathematics, Integration – The VLSI Journal, International Journal of Electronics.

I reviewed papers for the following conferences and workshops: ACNS 2016, PKC 2015, LATINCRYPT 2015, ACISP 2015, LightSec 2015, SPACE 2015, PST 2015, ASIACRYPT 2014, PKC 2013, PKC 2011, CHES 2010, PKC 2010, CCECE 2009.

Interns

Interns

I have been lucky to work with the following bright interns at MSR:

  • Angshuman Karmakar (Ph.D. student at KULeuven, Belgium), Summer 2016.
  • Zhe Liu (former Ph.D. student at University of Luxembourg, Luxembourg; currently postdoc at University of Waterloo, Canada), Summer 2015.
  • Michael Wesolowski (former master Student at University of Waterloo, Canada; currently at Deloitte Canada), Summer 2014.
  • Armando Faz-Hernandez (former master student at CINVESTAV-IPN, Mexico; currently Ph.D. student at University of Campinas, Brazil), Summer 2012.