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.

---

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

• December 2016: Formal call for proposals released
• November 30, 2017: Round 1 deadline: 82 submissions received (59 KEMs, 23 signatures)
• December 21, 2017: Round 1 public release: 69 “complete and proper” submissions
• January 30, 2019: Round 2 announcement: 26 accepted to round 2 (17 KEMs, 9 signatures)
• March 15, 2019: Round 2 “tweak” deadline

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)

---

Crypto 2017 conference report

August 28, 2017 at 11:21PM     Travel Research California

Last week, Crypto 2017 took place at UC Santa Barbara. There were more than 425 attendees for this year's 4-day conference, with 72 papers being presented.

Monday morning was interrupted by a very special coffee break: the ecliptic curve cryptography coffee break, a.k.a. viewing the solar eclipse. General Chair Steve Myers had very conveniently ordered solar eclipse glasses for everyone (from a legitimate vendor!). The sky was cloudy during the coffee break, but the eclipse occasionally peeked through, and the skies cleared afterward for a clearer view of the eclipse.

Later that morning, John Martinis, a physicist from UCSB, gave an invited lecture on the prospects of a quantum factoring (and, presumably, discrete logarithm-ing) machine.

On Monday afternoon, Yehuda Lindell gave a talk on his paper Fast Secure Two-Party ECDSA Signing. Fast protocols exist for many factoring-, discrete logarithm-, and elliptic curve-based signature and public key encryption schemes. DSA and ECDSA are tricky because signing involves operations both additive and multiplicative operations using k and k^-1, but in a threshold scheme this must be done without knowing k. Past work by MacKenzie and Reiter (Crypto 2001) and Gennaro, Goldfeder, and Narayanan (ACNS 2016) gives two-party protocols for computing ECDSA using multiplicative sharing of the signing key x and ephemeral secret k and then Paillier encryption to combine their equations. Proving honest behaviour ends up being quite expensive, unfortunately. Lindell showed how to improve performance by simplifying the shared tasks that one of the party participates in while still using Paillier homomorphic encryption. The key idea is that the second party, before releasing the signature, can check whether the first party behaved honestly simply by checking the final signature, which is publicly checkable efficient by definition of a digital signature scheme. The paper reports experimental results that show that two-party signing for ECDSA (with the NIST P-256 curve) can be run in approximately 37 milliseconds. The techniques also apply to DSA.

Tuesday featured the three award papers. Sam Kim and David J. Wu won the best student paper award for Watermarking Cryptographic Functionalities from Standard Lattice Assumptions. Best paper awards went to Nico Döttling and Sanjam Garg for Identity-Based Encryption from the Diffie-Hellman Assumption and Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov for The first collision for full SHA-1.

Döttling and Garg's paper showed how to construct identity-based encryption from the computational Diffie–Hellman problem in any group, including elliptic curve groups. Previous results had shown it impossible to construct IBE in a black-box way from CDH, so this paper had to make non-black-box use of the underlying cryptographic primitives. While the scheme is polynomial-time, this non-black-box use ends up making the scheme quite inefficient. On Wednesday another paper expanded the set of assumptions from which one can construct identity-based encryption: Identity-based Encryption from Codes with Rank Metric.

Tuesday evening featured the annual rump session, including the program chair's report, reminiscences, announcements, songs, joke talks, and, unfortunately, some serious talks too. Most poignant was the second talk, entitled "Forty years and still running". Jean-Jacques Quisquater presented a list of cryptosystems still running after 40 years, including the DES/Triple-DES algorithm and the RSA cryptosystem. In fact, 2017 marks the 40th anniversary of the invention of RSA, and Quisquater had arranged a wonderful surprise: Ron Rivest, Adi Shamir, and Leonard Adleman were all present for the rump session, and they took the stage to commemorate this milestone.

Later in the rump session, Michael Naehrig, co-inventor of the Barreto–Naehrig (BN) family of elliptic curves, performed (via Youtube) his original song The Sound of Quantum.

On Wednesday, Cédric Fournet of Microsoft Research Cambridge gave the second invited talk on Project Everest, a massive multi-institution multi-year project to create a fully verified efficient implementation of the TLS protocol. One component of Everest is a verified implementation of Curve25519 in a language called HaCL*, which compiles down to verified C code. This invited lecture was a joint talk between Crypto 2017 and the 30th IEEE Computer Security Foundations Symposium (CSF), also taking place at UCSB last week.

The full proceedings of Crypto 2017 are available on SpringerLink:

• Proceedings Part I
• Proceedings Part II
• Proceedings Part III

Crypto 2018 will take place in August 2018 at—where else?—UC Santa Barbara.

---

Visiting Hobbiton

December 3, 2015 at 08:00PM     Travel Dunedin New Zealand North Island South Island

I've been in lovely New Zealand for the past week. Last week I visited my friend Matt at the University of Otago in Dunedin to give a talk. Matt took me out for a run on the peninsula overlooking Otago Harbour and Dunedin.

The main reason for my visit was to attend the Asiacrypt 2015 conference at the University of Auckland, one of the three main cryptography conferences each year. Among the scientific papers was a very interesting invited talk by Phil Rogaway on the moral character of cryptographic research, which prompted a lot of discussion.

On previous trips to New Zealand, I visited several filming locations for The Lord of the Rings (it's pretty much the biggest tourist draw in the country, and it's hard to throw a stone and not hit something connected with the film series), including the inspiration for Mount Doom and the river down which the Fellowship canoed:

But one location I'd never been to was The Shire. It's in the middle of the north island. The set for the original Lord of the Rings trilogy was never built to last, and so it was mostly torn down after filming completed. When time came to film The Hobbit trilogy, the owners of the farm, knowing the tourism interest, asked that they rebuild using permanent structures that would last, and a new tourist destination was born: Hobbiton!

So, after the conference finished on Thursday afternoon, I drove down to a farm in the middle of nowhere about 2 hours south of Auckland for a tour of the Shire. The location is part of a family farm with sheep, in a little valley surrounded by hills such that you can't see any roads, buildings, or modern creations (making it a perfect filming location). There are a bunch of Hobbit holes, the gigantic Party Tree in the centre of the Shire, a pond, the Green Dragon Pub, and Bilbo and Frodo's house at Bag End at the top of the hill. The various Hobbit holes were built at different scales: 40% so that Gandalf would appear gigantic, and then some at 60%, 80%, and finally 100%, so that adult actors would match the size of their Hobbit holes.

You can find more pictures in my photo gallery.