The 3rd PQC Standardization Conference, organized by NIST, took place online from June 7 to 9, featuring a mix of live talks, pre-recorded talks, and panels. The oral exchanges were complemented by a text-based forum, provided by an app well known for its lack of end-to-end encryption, where some topics were eventually debated at length. Slides for the talks will be available in a few days, and video recordings in a few weeks. In the meantime, I will give a personal account of the conference based exclusively on my recollections. I took no notes, and I was often preparing or eating dinner at the same time, so nothing of what I will report should be taken as an established truth.
Kicking-off the conference, NIST gave some interesting bits of information on the status of the selection process and the future. The timeline for the 3rd round stays put: NIST expects to announce the selected standards sometimes between the end of 2021 and the beginning of 2022, as well as the alternates that will move to Round 4. Two announcements stirred more emotions in the audience: NIST reported on the difficulties of acquiring patents that are perceived to hinder standardization of some candidates, and specifically pointed to a statement recently published by CNRS (archived). Several researchers with links to French academia have already expressed their disappointment with CNRS’ strategy. The second was a confirmation of a possibility that NIST had already hinted at previously: roughly 6 months after the end of the 3rd round, NIST plans to reopen the process to submissions, specifically seeking to add more variety to signatures. The audience understood that NIST will not accept new KEM candidates in this phase. Given the recent progress in designing post-quantum signature schemes, including some that received accolades at AsiaCrypt, this announcement should interest the readers of this blog. In the same spirit, NIST doubled down on the possibility of standardizing SPHINCS+ at the end of the 3rd round.
Throughout the three days, each of the finalists and alternate finalists had a 15 minutes slot to present their updates for the 3rd round. In most cases, there were minimal or no updates. PicNic appears to be the most notable exception, with important changes to the structure of the LowMC block cipher. Rainbow and GeMSS had some explaining to do, in response to recent advances in cryptanalysis, and GeMSS had to drop some parameters. Vadim Lyubashevsky and Dan Bernstein possibly gave the most opinionated talks, I recommend watching both when they are available.
Several contributed talks reported on various aspects of post-quantum cryptography. Lattices had the greatest share, I especially enjoyed the talks by Thomas Espitau and Yu Yang on variants of Falcon… or maybe was it the excellent Château Latour I was having at the same time? I also enjoyed the “Applications” session, which opened my eyes on how difficult it is to put any of the PQC candidates in constrained environments such as smartcards and IoT.
Of particular interest to the readers of this blog should be the three contributed talks on isogeny-based cryptography:
- Péter Kutas (joint work with Christophe Petit) gave an excellent, if somewhat time-constrained, survey talk on several different “torsion point attacks” against SIDH and variants, which have previously appeared in this blog. The take-away message is that SIDH, SIKE and B-SIDH are well protected against all of them, be it because of the Fujisaki–Okamoto transform, or because of their intrinsic limitations, but the broader space of generalizations of SIDH a cryptographer might imagine is somewhat limited by these attacks, as it has already been repeatedly shown. I would certainly like to see more research in this promising direction, which has applications beyond cryptanalysis.
- Élise Tasso (joint work with Nadia El Mrabet, Simon Pontié and myself) presented an in-the-lab confirmation of a fault-injection attack on SIDH first proposed by Ti. The attack is alarmingly easy to mount (ok, we used equipment worth 40k€, but that’s only because we’re rich), but at the same time:
- It requires multiple repetitions of key generation with the same secret key, something that should never happen in a correct implementation of SIDH or SIKE;
- It appears to be difficult to exploit in presence of key compression;
- It has a countermeasure so simple and cheap, that it may as well be included by default in the reference code.
The old-timers of this blog will not be surprised to learn that the best talk of the conference was delivered by Craig Costello. In only 5 minutes, Craig pretended to use SageMath code to generate pairs of toy SIDH public keys (one for Alice, one for Bob), discard the secrets, and (clumsily fail to) upload the public keys to a GitHub repo. Then, he announced that Microsoft is offering $5,000 for the solution of the smaller instance, named $IKEp182, and $50, 000 for that of the larger instance, named $IKEp217. The prize money matches what the SIKE team estimates to be the material cost of breaking the instances, so think twice before reallocating your BitCoin mining resources.
If you believe this stunt, then be our guest and start cracking, but don’t come whining when some mysterious bounty catcher from Australia claims the big prize. For now, I can only observe that everybody seems to trust Microsoft and no one has even forked the GitHub repo (but, do you trust GitHub, anyway?). As a public service to the community, here is the SHA1 of the latest commit, dated June 9, 2021:
72dc1cb50d5a78fee605757e2f33043b2f36f9b4, and here is the SHA-512 of the contents of the repo (excluding
.gitignore), as of June 9:
$ git clone https://github.com/microsoft/SIKE-challenges $ cd SIKE-challenges/ $ cat * | sha512sum d2d6c6b7627a0cdbdfc98515f0e99c3387f08ce06196f767b65541442d36fd5978a49761f6c8e6c4704c87bad3629a604ad176517a966023780288cc2c1e3ae9 -
Anyway, the video recording will be available in a few days, and you will all get a chance to have a close look at Craig’s sleight of hand. Be on the watch for video stitching by “those cheeky devils at the NSA”!
— Luca de Feo