Michael Naehrig
I am a researcher in the Cryptography team at
Microsoft Research in
Redmond. Here is my MSR web
page.
mnaehrig@microsoft.com
michael@cryptojedi.org
Google scholar page
Publications
-
Maria Corte-Real Santos, Craig Costello, Michael Naehrig:
On cycles of pairing-friendly abelian varieties.
Advances in Cryptology – CRYPTO 2024, Lecture Notes in Computer Science 14928, Springer-Verlag (2024), Part IX, pp. 221–253.
Cryptology ePrint Archive, Report 2024/869.
-
Josh Benaloh, Michael Naehrig, Olivier Pereira, Dan S. Wallach:
ElectionGuard: a Cryptographic Toolkit to Enable Verifiable Elections.
USENIX Security 2024, USENIX Association (2024).
Cryptology ePrint Archive, Report 2024/955.
-
Giacomo Bruno, Maria Corte-Real Santos, Craig Costello, Jonathan Komada Eriksen, Michael Meyer, Michael Naehrig, Bruno Sterner:
Cryptographic Smooth Neighbors.
Advances in Cryptology – ASIACRYPT 2023, Lecture Notes in Computer Science 14444, Springer-Verlag (2024), Part VII, pp. 190–221.
Cryptology ePrint Archive, Report 2022/1439.
-
Craig Costello, Michael Meyer, Michael Naehrig:
Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem.
Advances in Cryptology – EUROCRYPT 2021, Lecture Notes in Computer Science 12696, Springer-Verlag (2021), Part I, pp. 272–301.
Cryptology ePrint Archive, Report 2020/1283.
-
Craig Costello, Patrick Longa, Michael Naehrig, Joost Renes, Fernando Virdia:
Improved Classical Cryptanalysis of SIKE in Practice.
Public Key Cryptography – PKC 2020, Lecture Notes in Computer Science 12111, Springer-Verlag (2020), Part II, pp. 505–534.
Cryptology ePrint Archive, Report 2019/298.
-
Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia:
Implementing Grover oracles for quantum key search on AES and LowMC.
Advances in Cryptology – EUROCRYPT 2020, Lecture Notes in Computer Science 12106, Springer-Verlag (2020), Part II, pp. 280–310.
Cryptology ePrint Archive, Report 2019/1146.
-
Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, Mathias Soeken:
Improved Quantum Circuits for Elliptic Curve Discrete Logarithms.
Post-Quantum Cryptography – PQCrypto 2020, Lecture Notes in Computer Science 12100, Springer-Verlag (2020), pp. 425–444.
Cryptology ePrint Archive, Report 2020/077.
-
Michael Naehrig, Joost Renes:
Dual Isogenies and Their Application to Public-key Compression for Isogeny-based Cryptography.
Advances in Cryptology – ASIACRYPT 2019, Lecture Notes in Computer Science 11922, Springer-Verlag (2019), Part II, pp. 243–272.
Cryptology ePrint Archive, Report 2019/499.
-
Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter:
Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms.
Advances in Cryptology – ASIACRYPT 2017, Lecture Notes in Computer Science 10625, Springer-Verlag (2017), Part II, pp. 241–272.
Cryptology ePrint Archive, Report 2017/598.
-
Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, David Urbanik:
Efficient compression of SIDH public keys.
Advances in Cryptology – EUROCRYPT 2017, Lecture Notes in Computer Science 10210, Springer-Verlag (2017), Part I, pp. 679–706.
Cryptology ePrint Archive, Report 2016/963.
-
Patrick Longa, Michael Naehrig:
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography.
International Conference on Cryptology and Network Security – CANS 2016, Lecture Notes in Computer Science 10052, Springer-Verlag (2016), pp. 124–139.
Cryptology ePrint Archive, Report 2016/504.
-
Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, Douglas Stebila:
Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE.
ACM Conference on Computer and Communications Security – ACM CCS 2016, ACM (2016), pp. 1006–1018, doi:10.1145/2976749.2978425.
Cryptology ePrint Archive, Report 2016/659.
-
Joppe W. Bos, Michael Naehrig, Joop van de Pol:
Sieving for Shortest Vectors in Ideal Lattices: a Practical Perspective.
International Journal of Applied Cryptography, Volume 3, Issue 4, InderScience Publishers (2016), pp. 313–329.
Cryptology ePrint Archive, Report 2014/880.
-
Craig Costello, Patrick Longa, Michael Naehrig:
Efficient algorithms for supersingular isogeny Diffie-Hellman.
Advances in Cryptology – CRYPTO 2016, Lecture Notes in Computer Science 9814, Springer-Verlag (2016), Part I, pp. 572–601.
Cryptology ePrint Archive, Report 2016/413.
-
Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Naehrig, John Wernsing:
CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy.
International Conference on Machine Learning – ICML 2016, Proceedings of Machine Learning Research (2016), pp. 201–210.
-
David J. Wu, Tony Feng, Michael Naehrig, Kristin Lauter:
Privately Evaluating Decision Trees and Random Forests.
Proceedings on Privacy Enhancing Technologies, Vol. 2016, Issues 4, pp. 335–355, De Gruyter (2016), doi:10.1515/popets-2016-0043.
Cryptology ePrint Archive, Report 2015/386.
-
Thomas Pöppelmann, Michael Naehrig, Andrew Putnam, Adrian Macias:
Accelerating Homomorphic Evaluation on Reconfigurable Hardware.
Cryptographic Hardware and Embedded Systems – CHES 2015, Lecture Notes in Computer Science 9293, Springer-Verlag (2015), pp. 143–163.
Cryptology ePrint Archive, Report 2015/631.
-
Paulo S. L. M. Barreto, Craig Costello, Rafael Misoczki, Michael Naehrig, Geovandro C. C. F. Pereira, Gustavo Zanon:
Subgroup security in pairing-based cryptography.
Progress in Cryptology – LATINCRYPT 2015, Lecture Notes in Computer Science 9230, Springer-Verlag (2015), pp. 245–265.
Cryptology ePrint Archive, Report 2015/247.
-
Joppe W. Bos, Craig Costello, Patrick Longa, Michael Naehrig:
Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis.
Journal of Cryptographic Engineering, Volume 6, Issue 4, Springer (2015), pp. 259–286, doi:10.1007/s13389-015-0097-y.
Cryptology ePrint Archive, Report 2014/130.
-
Kristin Lauter, Michael Naehrig, Tonghai Yang:
Hilbert theta series and invariants of genus 2 curves.
Journal of Number Theory, Elsevier (2015), doi:10.1016/j.jnt.2015.02.020.
-
Craig Costello, Cédric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, Samee Zahur:
Geppetto: Versatile Verifiable Computation.
IEEE Symposium on Security and Privacy – SP 2015, IEEE Computer Society (2015), pp. 253–270.
Cryptology ePrint Archive, Report 2014/976.
-
Joppe W. Bos, Craig Costello, Michael Naehrig, Douglas Stebila:
Post-quantum key exchange for the TLS protocol from the ring learning with errors problem.
IEEE Symposium on Security and Privacy – SP 2015, IEEE Computer Society (2015), pp. 553–570.
Cryptology ePrint Archive, Report 2014/599.
-
Kristin Lauter, Adriana López-Alt, Michael Naehrig:
Private Computation on Encrypted Genomic Data.
Progress in Cryptology – LATINCRYPT 2014, Lecture Notes in Computer Science 8895, Springer-Verlag (2014), pp. 3–27.
Date: 2014-11-25 [pdf], Cryptology ePrint Archive, Report 2015/133.
-
Joppe W. Bos, Kristin Lauter, Michael Naehrig:
Private predictive analysis on encrypted medical data.
Journal of Biomedical Informatics, Volume 50, Elsevier (2014), pp. 234–243.
Date: 2014-08-26 [pdf], Cryptology ePrint Archive, Report 2014/336.
-
Tancrède Lepoint, Michael Naehrig:
A Comparison of the Homomorphic Encryption Schemes FV and YASHE.
Progress in Cryptology – AFRICACRYPT 2014, Lecture Notes in Computer Science 8469, Springer-Verlag (2014), pp. 318–335.
Cryptology ePrint Archive, Report 2014/062.
-
Joppe W. Bos, J. Alex Halderman, Nadia Heninger, Jonathan Moore, Michael Naehrig, Eric Wustrow:
Elliptic Curve Cryptography in Practice.
Financial Cryptography and Data Security – FC 2014, Lecture Notes in Computer Science 8437, Springer-Verlag (2014), pp. 157–178.
Cryptology ePrint Archive, Report 2013/734.
-
Chitchanok Chuengsatiansup, Michael Naehrig, Pance Ribarski, and Peter Schwabe:
PandA: Pairings and Arithmetic.
Pairing-Based Cryptography – Pairing 2013, Lecture Notes in Computer Science 8365, Springer-Verlag (2014), pp. 229–250.
Date: 2013-12-04 [pdf] [bibtex] -
Joppe W. Bos, Kristin Lauter, Jake Loftus, Michael Naehrig:
Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme.
International Conference on Cryptography and Coding – IMACC 2013, Lecture Notes in Computer Science, Springer-Verlag (2013), pp. 45–64.
Date: 2013-11-15 [pdf] Cryptology ePrint Archive, Report 2013/075.
-
Joppe W. Bos, Craig Costello, Michael Naehrig:
Exponentiating in Pairing Groups.
Selected Areas in Cryptography – SAC 2013, Lecture Notes in Computer Science 8282, Springer-Verlag (2013), pp. 438–455.
Date: 2013-09-04 [pdf] Cryptology ePrint Archive, Report 2013/458.
-
Thore Graepel, Kristin Lauter, Michael Naehrig:
ML Confidential: Machine Learning on Encrypted Data
International Conference on Information Security and Cryptology – ICISC 2012, Lecture Notes in Computer Science 7839, Springer-Verlag (2013), pp. 1–21.
Date: 2013-02-12 [pdf], Cryptology ePrint Archive, Report 2012/323.
-
Tolga Acar, Kristin Lauter, Michael Naehrig, Daniel Shumow:
Affine Pairings on ARM.
Pairing-Based Cryptography – Pairing 2012, Lecture Notes in Computer Science 7708, Springer-Verlag (2013), pp. 203–209.
Date: 2012-06-27 [pdf], Cryptology ePrint Archive, Report 2011/243
-
Craig Costello, Kristin Lauter, Michael Naehrig:
Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings.
Progress in Cryptology – INDOCRYPT 2011, Lecture Notes in Computer Science 7107, Springer-Verlag (2011), pp. 320–342.
Date: 2011-10-18 [pdf], supersedes 2011-10-05 [pdf]
-
Kristin Lauter, Michael Naehrig, Vinod Vaikuntanathan:
Can homomorphic encryption be practical?
ACM Cloud Computing Security Workshop – CCSW 2011.
Date: 2011-09-01 [pdf]
-
Geovandro C. C. F. Pereira, Marcos A. Simplício Jr, Michael Naehrig, Paulo S. L. M. Barreto:
A Family of Implementation-Friendly BN Elliptic Curves.
Journal of Systems and Software, Volume 84, Issue 8, Elsevier (2011), pp. 1319–1326.
Date: 2011-06-03 [pdf] [bibtex] -
Kristin Lauter, Peter L. Montgomery, Michael Naehrig:
An Analysis of Affine Coordinates for Pairing Computation.
Pairing-Based Cryptography – Pairing 2010, Lecture Notes in Computer Science 6487, Springer-Verlag (2010), pp. 1–20.
Date: 2010-10-12 [pdf] [bibtex] -
Michael Naehrig, Ruben Niederhagen, and Peter Schwabe:
New software speed records for cryptographic pairings.
Progress in Cryptology – LATINCRYPT 2010, Lecture Notes in Computer Science 6212, Springer-Verlag (2010), pp. 109–123.
Date: 2010-07-14 [pdf] [bibtex] [more]
Supersedes: 2010-05-28 [pdf], supersedes: 2010-04-06 [pdf]
Caution: The software as described in versions 2010-05-28 and 2010-04-06 of the paper has a bug related to the choice of curve parameters. This also affects the version in the Latincrypt 2010 proceedings. A corrected version of the software is available and the bug is corrected from version 2010-07-14 of the paper. -
Craig Costello, Tanja Lange, Michael Naehrig:
Faster Pairing Computations on Curves with High-Degree Twists.
Public Key Cryptography – PKC 2010, Lecture Notes in Computer Science 6056, Springer-Verlag (2010), pp. 224–242.
Date: 2010-06-14 [pdf] [bibtex] -
Christophe Arène, Tanja Lange, Michael Naehrig, Christophe Ritzenthaler:
Faster computation of the Tate pairing.
Journal of Number Theory, Volume 131, Issue 5, Elliptic Curve Cryptography, Elsevier (2011), pp. 842–857.
Date: 2010-05-20 [pdf] [bibtex] -
Laura Hitt O'Connor, Gary McGuire, Michael Naehrig, Marco Streng:
A CM construction for curves of genus 2 with p-rank 1.
Journal of Number Theory, Volume 131, Issue 5, Elliptic Curve Cryptography, Elsevier (2011), pp. 920–935.
Date: 2010-05-11 [pdf] [bibtex] -
Michael Naehrig, Paulo S. L. M. Barreto and Peter Schwabe:
On compressible pairings and their computation.
Progress in Cryptology – AFRICACRYPT 2008, Lecture Notes in Computer Science 5023, Springer-Verlag (2008), pp. 371–388.
[pdf] [bibtex] [more] -
Paulo S. L. M. Barreto, Michael Naehrig:
Pairing-Friendly Elliptic Curves of Prime Order.
Selected Areas in Cryptography – SAC 2005, Lecture Notes in Computer Science 3897, Springer-Verlag (2006), pp. 319–331.
[pdf] [bibtex] Preliminary version: Cryptology ePrint Archive, Report 2005/133.
Technical Reports
-
Josh Benaloh, Michael Naehrig, Olivier Pereira:
REACTIVE: Rethinking Effective Approaches Concerning Trustees in Verifiable Elections.
Cryptology ePrint Archive, Report 2024/915.
-
Jan Buzek, Junaid Hasan, Jason Liu, Michael Naehrig, Anthony Vigil:
Finding twin smooth integers by solving Pell equations.
arXiv, arXiv:2211.04315.
-
Paulo S.L.M. Barreto, Patrick Longa, Michael Naehrig, Jefferson E. Riccardini, Gustavo Zanon:
Sharper Ring-LWE Signatures.
Cryptology ePrint Archive, Report 2016/1026.
Note: 2016-11-28: A flaw in the tight security reduction of the original Tesla paper (eprint report 2015/755) has been discovered independently by Gus Gutoski and Christopher Peikert. The mistake carries through to the proof of Ring-TESLA (eprint report 2016/030) and is also present in the proof for TESLA# presented here. Remarks similar to those made by the authors of TESLA and Ring-TESLA apply here in that the flaw does not seem to lead to an attack on these schemes. However, the concrete instantiations presented are currently not backed by a formal security argument.
ElectionGuard
- Josh Benaloh, Michael Naehrig, Olivier Pereira: ElectionGuard Design Specification, Version 2.1.0, August 2024. [pdf]
- Josh Benaloh, Michael Naehrig: ElectionGuard Design Specification, Version 2.0.0, August 2023. [pdf]
Program committees and editorial boards
- Editor of the IACR Communications in Cryptology (2024),
- Eurocrypt 2023,
- Eurocrypt 2021, Asiacrypt 2021,
- ANTS 2020,
- Crypto 2019, CT-RSA 2019, Latincrypt 2019,
- IEEE S&P 2018, CT-RSA 2018, PQCrypto 2018, ACNS 2018, SAC 2018,
- ECC 2017, Latincrypt 2017, PQCrypto 2017, ACNS 2017,
- Indocrypt 2016, ACNS 2016, WAHC 2016,
- Indocrypt 2015, SPACE 2015, Latincrypt 2015, GenoPri 2015, PKC 2015, WAHC 2015,
- SCN 2014,
- CANS 2013, SAC 2013,
- CANS 2012, Pairing 2012,
- Indocrypt 2011,
- Africacrypt 2010.
Talks
- Finding twin smooth integers, Tutte Colloquium at Combinatorics and Optimization, [pdf slides], virtual, University of Waterloo, Canada, 2021-01-29.
- Remembering Peter Montgomery, Memorial presentation together with Joppe W. Bos at ANTS 2020. [pdf slides], Virtual Conference, New Zealand, 2020-07-01.
- Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms, talk at Asiacrypt 2017, [pdf slides], Hong Kong, China, 2017-12-05.
- Supersingular Isogeny Diffie-Hellman, invited talk at the Real-World Cryptography Conference 2017, [pdf slides], Columbia University, New York City, NY, USA, 2017-01-04.
- Post-Quantum Cryptography, talk at the MSR Privacy Workshop, Microsoft Research, Redmond, WA, USA, 2015-10-29.
- Selecting Elliptic Curves for Cryptography — "Real World" Issues, talk at the University of Washington Number Theory Seminar, [pdf slides], University of Washington, Seattle, WA, USA, 2015-04-28.
- Private Computation on Encrypted Genomic Data, talk at the Workshop on Genome Privacy 2014 — GenoPri 2014, [pdf slides], Amsterdam, The Netherlands, 2014-07-15.
- Exponentiating in Pairing Groups, talk at the SIAM Conference on Applied Algebraic Geometry AG13, Minisymposium on Cryptography and Number Theory, [pdf slides], Colorado State University, Fort Collins, USA, 2013-08-01.
- Improved Security for a Ring-Based Fully-Homomorphic Encryption Scheme, invited talk at the Fifth International Conference on Post-Quantum Cryptography — PQCrypto 2013, [pdf slides], XLIM Institut de Recherche, Limoges, France, 2013-06-05.
- Curves and Fields for Efficient Cryptographic Pairings, talk at the Pacific Northwest Number Theory Conference 2013, [pdf slides], University of Washington, Seattle, WA, USA, 2013-06-01.
- Homomorphic Encryption from RLWE — Schemes and Parameters, talk at the MSR Privacy Workshop, Microsoft Research, Redmond, WA, USA, 2012-10-23.
- ML Confidential — Machine Learning on Encrypted Data, [pdf slides], talk at crypto group lunch, Microsoft Research, Redmond, WA, USA, 2012-07-27.
- Homomorphic Encryption from Ring Learning with Errors, [pdf slides], Microsoft Research, Cambridge, United Kingdom, 2012-01-10.
- Pairings at High Security Levels, [pdf slides], invited talk at the European Postdoctoral Day of Excellence in Cryptography, Darmstadt, Germany, 2011-11-21.
- Can homomorphic encryption be practical?, [pdf slides], Cryptography Working Group, Utrecht, The Netherlands, 2011-09-30.
- An Analysis of Affine Coordinates for Pairing Computation, [pdf slides], Pairing 2010, Yamanaka Hot Spring, Ishikawa, Japan, 2010-12-13.
- Pairings on elliptic curves — parameter selection and efficient computation, [pdf slides], invited talk at the Workshop on Elliptic Curves and Computation (ECC 2010), Microsoft Research, Redmond, WA, USA, 2010-10-19.
- How fast are pairings?, talk at crypto group lunch, Microsoft Research, Redmond, WA, USA, 2010-08-12.
- New software speed records for cryptographic pairings [pdf slides], invited talk at the workshop on Computer Security and Cryptography at CRM, Montreal, Canada, 2010-04-13.
- Pairings for Cryptographic Applications, European Microsoft Innovation Center (EMIC), Aachen, Germany, 2010-03-22.
- Choosing curves, coordinates and algorithms for computing cryptographic pairings, Microsoft Research, Redmond, WA, USA, 2010-03-02.
- Pairings for Cryptography [pdf slides], invited talk at the seminar of the Digital Security Group, Radboud Universiteit Nijmegen, The Netherlands, 2009-12-11.
- BN curves revisited [pdf slides], invited talk at the Mini-Workshop on Computational aspects of elliptic and hyperelliptic curves, K.U. Leuven, Belgium, 2009-10-28.
- Efficient Computation of Pairings on Elliptic Curves [pdf slides], EIDMA/DIAMANT Cryptography Working Group, Utrecht, The Netherlands, 2009-10-02.
- Pairings on Edward's curves [pdf slides], talk at the Rump Session of ECC 2009, University of Calgary, Canada, 2009-08-24.
- A Quick Guide to Efficient Pairing Computation, Microsoft Research, Redmond, WA, USA, 2009-08-12.
- Computing Pairings on Elliptic Curves [pdf slides], talk at crypto group lunch, Microsoft Research, Redmond, WA, USA, 2009-07-17.
- Constructive and Computational Aspects of Cryptographic Pairings [pdf slides], short presentation during my PhD defense, Eindhoven University of Technology, The Netherlands, 2009-05-07.
- Pairings on Edwards curves [pdf slides], invited talk at the Workshop on Pairings in Arithmetic Geometry and Cryptography, IEM, University of Duisburg-Essen, Essen, Germany, 2009-05-05.
- Pairings II [pdf slides], DIAMANT Summer School on Elliptic and Hyperelliptic Curve Cryptography, Eindhoven, The Netherlands, 2008-09-19.
- Pairings I [pdf slides], DIAMANT Summer School on Elliptic and Hyperelliptic Curve Cryptography, Eindhoven, The Netherlands, 2008-09-18.
- On compressible pairings and their computation [pdf slides], AfricaCrypt 2008, Casablanca, Morocco, 2008-06-13.
- How to construct pairing-friendly curves [pdf slides], seminar talk, LARC, University of São Paulo, Brazil, 2007-09-28.
- Pairing-friendly elliptic curves of prime order [pdf slides], seminar talk, Computer Security group, b-it Bonn, Germany, 2006-01-12.
- Pairing-friendly elliptic curves of prime order [pdf slides], Selected Areas in Cryptography — SAC 2005, Queen's University, Kingston, Canada, 2005-08-12.
Theses
In May 2009, I completed my PhD at Eindhoven University of Technology in the coding and crypto group under the supervision of Tanja Lange.-
PhD thesis: Constructive and Computational Aspects of Cryptographic Pairings,
Eindhoven University of Technology, The Netherlands, 2009.
Updated version (2009-05-13, corrected some typos and mistakes): [pdf]
Cover of the printed version: [pdf]
Statements: [pdf]
- Diploma thesis: Die Brauer-Bäume des Monsters M in Charakteristik 29, RWTH Aachen University, Germany, 2002. [pdf]
Misc
- The Sound of Quantum
- www.die-naehrigs.de
- Live music at rump sessions
- Video abstract for the paper Faster computation of the Tate pairing with Christophe Arène, Tanja Lange, and Christophe Ritzenthaler on the Journal of Number Theory YouTube channel, featuring Lukas, Julius, and Linus.
-
Slides from the joint "talk"
Secure Cloud Computing for Medical Data
with Daniel J.Bernstein, Carl Ellison, Tanja Lange, Kristin Lauter, Victor Miller,
and Eran Tromer given at the rump session of Crypto 2009 (2009-08-17).
Invited paper submitted to the Journal of Craptology. [pdf]
Here is a video of the corresponding part of the Crypto 2009 rump session (our talk is at the very end). - Redmond 2009
-
Slides from the joint talk
"A brief look at the 56 SHA-3 submissions"
with Christiane Peters
and Peter Schwabe,
given at the
rump session of
Eurocrypt 2009 (2009-04-28).
See also the Lyrics with guitar chords and the
video on YouTube.
Invited paper in the Journal of Craptology, volume 7 . [pdf] [bibtex] -
A web interface
to get parameters for BN curves.