PQCrypto 2018 and NIST’s First PQC Conference

PQCrypto is a recent conference dedicated to post-quantum cryptography. This year’s edition was organized at Fort Lauderdale, in Florida, and co-located with NIST’s first PQC standardization conference. Both conferences gathered about 350-400 attendees. The schedule was as follows:

  • From Monday morning to Wednesday noon : PQCrypto (24 talks + 3 invited talks)

  • From Wednesday afternoon to Friday evening : NIST’s PQC conference (56 talks)

PQCrypto : on a purely personal note, my favorite talks were the following:

  • The first invited talk given by Jean-Pierre Tillich: Jean-Pierre presented cryptanalytic techniques in code-based cryptography, and concluded the talk with a new technique (origami) that he and a student used to break the signature scheme RankSign. The attack is available on ePrint;

  • The second invited given talk by Dave Wecker, engineer at Microsoft: David presented the company’s strategy to build quantum computers. As I understood it, the technique relies on Majorana fermions and is quite bold as it is very hard to get a functional qubit with it but if it succeeds, it will be easy to scale. He expects quantum computers to be interesting for cryptanalysis in 10 years;

  • Koen de Boer presented a MITM attack on a recently proposed encryption scheme based on Mersenne numbers; the attack relies on locality-sensitive hashing to find approximate collisions;

  • David Derler showed how to build ring signatures from symmetric primitives (hash functions and block ciphers). The proposal relies on and extend ideas from Picnic (a post-quantum signature scheme based on a MPC-in-the-head evaluation of one-way functions);

  • Hart Montgomery presented a variant of the LWR problem; as a reminder, LWR is a deterministic variant of the LWE problem, which is convenient in many situations. Hart’s version of LWR is not practical for concrete use but plays well with security proofs. I found it to be a very interesting theoretic paper;

  • Leon Groot Bruinderink showed that the sponge construction is safe in the Quantum Random Oracle Model. However, this requires the underlying function f to be a one-way permutation, which we currently don’t know how to build (In particular, Keccak uses an inversible permutation);

There were also talks given by members of the project RISQ:

  • Matthieu Lequesne,  PhD student in the INRIA team Secret, presented an improvement and a generalization of a timing attack against some QC-MDPC encryption schemes, as well as a mitigation of this attack;

  • Pauline Bert, PhD student at IRISA, presented an instantiation of an identity-based encryption scheme based on ring-SIS and ring-LWE;

  • I presented a fault attack against signature schemes of the SPHINCS family;

  • Elena Kirshanova, postdoctoral researcher at ENS de Lyon, presented a quantum speed-up of an information set decoding algorithm;

Right now, the articles are available here, the slides are here and the videos should be online in a few weeks.

The next edition of PQCrypto will be at Chongqing, in China.

NIST’s PQC conference : it is the first important event in NIST’s process for standardizing post-quantum cryptographic schemes. The schedule and slides are on the dedicated website. Submitters of each proposed scheme had (most of the time) 15 minutes to present the scheme. I found this event quite interesting: due to the restricted time, presenters were going straight to the point, which made most talks pleasant to follow. The only caveat is that many schemes were similar (I’ll get back to that later). There were nine sessions each of about six presentations, roughly ordered with respect to the mathematical building blocks they use :

  1. Exotic (isogenies, hash-based, post-quantum RSA, Picnic, braids)

  2. Lattices

  3. Lattices

  4. Multivariate

  5. Lattices + Codes

  6. Codes

  7. Lattices + Codes

  8. Exotic + Lattices

  9. Codes

NIST noticed (and I think most of us agree) that many schemes were quite similar. For example:

  • Many lattice-based KEMs are isomorphic to NewHope;

  • A few multivariate signature schemes are similar (a notable exception being MQDSS);

  • Gravity-SPHINCS and SPHINCS+ follow the same framework;

  • Ramstake and Mersenne are virtually identical;

  • At a very high level, NTRU encryption, QC-MDPC, Ramstake/Mersenne rely on similar ideas, but on different rings and metrics;

  • Classic McEliece, Big Quake and DAGS are based on the same principle, but with different choices regarding security/performance trade-offs (Classic McEliece is the most conservative);

This point was further emphasized by Philippe Gaborit in the final slides of his last talk:

Image

For this reason, NIST encouraged submitters of similar proposals to merge their proposals. Given that there are 64 submissions still running, I hope that they will be heard.

 Again, a strictly personal list of my favorite talks would be:

  • SIKE

  • SPHINCS+

  • CRYSTALS-Kyber/Dilithium

  • Saber

  • Mersenne

  • Classic McEliece

Now, about the future: NIST expects to select candidates for the round 2 at the beginning of 2019. The next NIST PQC conference will be co-located with CRYPTO 2019.

For complementary points of view, you can also check these nice blog posts by Thomas Attema and Steven Galbraith.