Patrick Longa

SENIOR SD ENGINEER | Microsoft Research Redmond | Patrick Longa |

I am with the Security and Cryptography team, a research and development organization within 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 cryptography (ECC), pairing-based cryptography, efficient algorithms and implementation of crypto primitives, and side-channel analysis attacks and countermeasures.

# News

**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****June/2014****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

- 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

- Craig Costello and Patrick Longa, "FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime", in
*Advances in Cryptology - ASIACRYPT 2015 (to appear)*, 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", in
*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)", in
*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", in Proc.
*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), in Proc.
*Workshop on 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), in
*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", in Proc.
*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" in Proc.
*Workshop on 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", in
*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", in Proc.
*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", in Proc.
*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" in Proc.
*International Conference on Theory and Practice of 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" in Proc.
*International Conference on 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" in Proc.
*International Conference on Theory and Practice of 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" in
*IEEE Transactions on Computers*, 2008. [paper]

# 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].

# Contact Info

Microsoft Research |

One Microsoft Way, |

Redmond, WA 98052 |

USA |

Office: 112/3234 |

Tel: +1 (425) 706-4823 |

E-mail: plonga at microsoft dot com |