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.
- 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)
(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)
(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)
(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.
(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)
(3 in Round 1, 1 in Round 2)
- Three Bears (integer module learning with errors, IND-CCA using custom transform)
(3 in Round 1, 0 in Round 2)
(3 in Round 1, 0 in Round 2)
Round 2 digital signature schemes (9)
(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)
(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)
(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)
(4 in Round 1, 0 in Round 2)
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.
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.
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:
Crypto 2018 will take place in August 2018 at—where else?—UC Santa Barbara.
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.
Here are a few more pictures, and you can find more in my photo gallery.
I'm currently in Trondheim, Norway, the first stop of my 5.5 month research sabbatical, here to work with Prof Colin Boyd whom I worked with in Brisbane before he moved to Trondheim.
Like many people I have desired to see the northern lights. Trondheim is the furthest north I've even been, so I was hopeful I would be able to see them, but knew the chance would still be pretty low.
On Friday morning my mom emailed me telling me she'd heard on the radio there was a solar storm that would be hitting Earth that night, with the possibility of aurora. Making use of aurora forecast websites such as Aurora Service, Soft Serve News, and OVATION, we managed to figure out that there was a good chance of aurora in Trondheim that night, and that the skies were going to be cloudless. One forecast suggested the storm would start around midnight and peak around 5am; we weren't sure whether to stay up or get up early.
Around 10 o'clock the forecast was looking pretty good: a "Kp number" of around 5 was forecast, whereas a Kp number of at least 3.5 is required to see the northern lights in Trondheim. We headed out to a shoreline road along the fjord on the northern edge of Trondheim. Looking out the window, I saw little bits of the northern lights in the sky, so we tried to find somewhere to stop. We got out at one roadside stop along the road, but then moved on to try to find somewhere quieter. We found a nice place right alongside the water, but then noticed right next door was the meeting point of the Hell's Angels (really!) so we moved on. We ended up walking down past some cottages to a rocky beach that would have been underwater at high tide, but was perfect at the time.
And there they were! Northern lights!
Looking out over the water, we saw sheets of light patches in the sky, like tufts of cloud, but fading in and out, moving around. Unexpectedly, they were mostly monochrome to the naked eye, but my camera was picking up colour. They were nebulous to look at, you couldn't really focus on them, as soon as you look at them, the focus shifts and they seem to disappear. It was better to look at a fixed point and let them move in the sky around you, in and out of your focus.
They were different types of aurora, it seemed. Sometimes they were in bands across the lower sky, like in the picture above. Sometimes there were in sheets and clouds all across the middle sky, like this:
And near the end they were like tendrils snaking across the sky, rapidly forming and dissipating in just a second or two, like a stream of smoke in a jet stream.
I managed to take a series of pictures to create a timelapse video showing the progression of the lights over about 10 minutes:
I feel very lucky that on my third night in Trondheim we managed to see the northern lights in one of the strongest solar storms of the year.