Panoramic view across the Narrows and into St. John's harbour

Douglas Stebila

recent archives categories tags

Security analysis of Apple's iMessage PQ3 protocol

February 21, 2024 at 09:00AM     Research

Today Apple announced its new iMessage PQ3 protocol, which is an update to the cryptographic protocol used in iMessage that adds post-quantum cryptography. I worked with Apple over the past few months to analyze the protocol and show that it meets the security goals, and have written a paper describing my findings. I’m glad to see the adoption of post-quantum cryptography protocols continuing.

Comparison of quantum-secure cryptography in messaging apps (Credit: Apple)
Comparison of quantum-secure cryptography in messaging apps (Credit: Apple)

Launch of the Linux Foundation's Post-Quantum Cryptography Alliance

February 6, 2024 at 09:00AM     Research

Today is the launch of the Post-Quantum Cryptography Alliance, a new open-source software foundation within the Linux Foundation. The PQCA will be the new home of the Open Quantum Safe project.

Michele Mosca and I founded the OQS project about a decade ago as a research project, to share code and enable experiments using post-quantum algorithms in applications like OpenSSL. People seemed interested in the code especially because it enabled experimental use of post-quantum in applications that relied on OpenSSL. The initiative was jump-started in 2016 with the NIST Post-Quantum Cryptography Standardization project, when suddenly there were lots of algorithms to evaluate. Since then interest in the project has grown and many people and organizations have helped build the project into a highly useful tool for prototyping, experimentation, and research. With the move into the Linux Foundation and the support of the PQCA, our goal is to have a permanent home for the OQS project and enable it to mature into a reliable open-source cryptography library that can support the transition to post-quantum cryptography, and also continue to enable research as PQ algorithms and capabilities evolve.

Many people and organizations have supported OQS over the years.

Current and past members of our core team: Norm Ashley, Michael Baentsch, Thomas Bailleux, Eric Crockett, Vlad Gheorghiu, Jason Goertzen, Basil Hess, Shravan Mishra, Michele Mosca, Christian Paquin, John Schanck, Pravek Sharma, Goutam Tamvada, Thom Wiggers, and Spencer Wilson.

Additional contributors, supporters, and champions: Mark Albert, Nicholas Allan, Matthew Campagna, Ben Davies, Nir Drucker, Ted Eaton, Karen Easterbrook, Linux Färnstrand, Jannis Fengler, Andrew Fregly, Shay Gueron, Torben Hansen, Alex Harrison, Brian Jarvis, Jeff Johnson, Burt Kaliski Jr., Kevin Kane, Matthias Kannwischer, Brian LaMacchia, Tancrède Lepoint, Yong Jian Ming, Keane Moraes, Dimitris Mouris, Brian Neill, Duc Tri Nguyen, PhD, Michael Osborne, Alex Parent, Geovandro Pereira, Sebastian Ramacher, Peter Schwabe, Dimitrios Sikeridis, John Underhill, Sebastian Verschoor, John F. Weston; see also the full list of contributors on GitHub.

Funding support for OQS has been provided by ARC, AWS, the Canadian Centre for Cyber Security, Cisco, NSERC, the NGI Assure Fund, the Unitary Fund, VeriSign Inc., and the University of Waterloo.

Thanks to the team at the Linux Foundation (Hart Montgomery, Todd Benzies, Scott Nicholas, Michael Dolan) and others involved in the formation of the PQCA, including Michael Maximilien who pushed for the creation of the PQCA inside the Linux Foundation.

New York Times article on post-quantum cryptography

October 22, 2023 at 11:15AM     Research

The New York Times has an article today about the need to transition to post-quantum cryptography, and the governemnt and academic efforts over the past few years. I have a small contribution to the article in the form of an image about lattice-based cryptography.

Lattice cryptography in the New York Times
Lattice cryptography in the New York Times

Joint Statement on Contact Tracing

April 20, 2020 at 10:45AM     Research

Open letter from 300+ scientists from 25+ countries laying out 4 principles for open, transparent and private-by-design COVID-19 contact tracing systems, focusing on decentralised approaches to limit surveillance repurposing.

NIST Post-Quantum Crypto Standardization project round 2

January 30, 2019 at 03:36PM     Research

The United States National Institute of Standards and Technology (NIST) is currently running a multi-year standardization project for post-quantum cryptography. Today, NIST announced the schemes that have made it to round 2 of the competition. Below is my categorization of the round 2 schemes.

Timeline

For a good summary as of August 2018, see the talk by Bernstein, Lange, Panny at the Workshop on Attacks in Cryptography (WAC) co-located with Crypto 2018.

Round 2 key encapsulation mechanisms / public key encryption schemes (17)

Code-based

(17 in Round 1, 7 in Round 2)

  • BIKE (some McEliece, some Niederreiter, using quasi-cyclic medium density parity check codes, IND-CPA)
  • Classic McEliece (Niederreiter, using binary Goppa codes, IND-CCA directly)
  • HQC (Hamming quasi-cyclic codes, IND-CCA using FO transform)
  • LEDAcrypt (merger of LEDAkem/LEDApkc) (Niederreiter, using quasi-cyclic low density parity check codes, IND-CCA using Kobara-Imai transform)
  • NTS-KEM (Goppa codes, IND-CCA using FO-like transform)
  • ROLLO (merger of LAKE/LOCKER/Ouroboros-R) (McEliece, rank metric codes, IND-CPA)
  • RQC (rank quasi-cyclic codes, IND-CCA using FO transform)

Structured lattices

(19 in Round 1, 8 in Round 2)

  • CRYSTALS-KYBER (module learning with errors, IND-CCA using FO transform) (University of Waterloo connection: John Schanck)
  • LAC (ring learning with errors, IND-CCA using FO transform)
  • NewHope (ring learning with errors, IND-CCA using FO transform) (University of Waterloo connection: Douglas Stebila)
  • NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM) (NTRU-based, IND-CCA using FO-like transform) (University of Waterloo connection: John Schanck)
  • NTRU Prime (NTRU-based, IND-CCA using re-encryption)
  • Round5 (merger of Hila5/Round2) (general learning with rounding, IND-CCA using FO transform)
  • SABER (module learning with rounding, IND-CCA using FO transform)

Unstructured lattices

(3 in Round 1, 1+1 in Round 2)

  • FrodoKEM (learning with errors, IND-CCA using FO transform) (University of Waterloo connection: Douglas Stebila, UW alum Patrick Longa)

Round5 (listed above in “Structured lattices”) also contains a variant based on unstructured lattices.

Isogenies

(1 in Round 1, 1 in Round 2)

  • SIKE (supersingular isogenies, IND-CCA using FO transform) (University of Waterloo connection: David Jao, David Urganik, UW alums Patrick Longa, Vladimir Soukharev)

Integer-ring

(3 in Round 1, 1 in Round 2)

  • Three Bears (integer module learning with errors, IND-CCA using custom transform)

Multivariate

(3 in Round 1, 0 in Round 2)

Other

(3 in Round 1, 0 in Round 2)

Round 2 digital signature schemes (9)

Structured lattices

(5 in Round 1, 3 in Round 2)

  • CRYSTALS-DILITHIUM (module learning with errors / module short integer solutions)
  • FALCON (NTRU short integer solutions)
  • qTESLA (ring learning with errors) (University of Waterloo connection: Edward Eaton; UW alums Gus Gutoski (ISARA), Patrick Longa)

Multivariate

(8 in Round 1, 4 in Round 2)

  • GeMSS (HFEv-)
  • LUOV (unbalanced oil and vinegar)
  • MQDSS (Fiat-Shamir applied to 5-pass identification scheme)
  • Rainbow (generalized oil and vinegar)

Symmetric crypto

(3 in Round 1, 2 in Round 2)

  • Picnic (hash functions + block ciphers + ZK proofs) (University of Waterloo connection: UW alum Greg Zaverucha)
  • SPHINCS+ (hash based, tree of trees)

Other

(4 in Round 1, 0 in Round 2)