Public Key Cryptography 2015, Gaithersburg, USA

PKC 2015 was held at the Gaithersburg Campus of the National Institute of Standards and Technology (NIST), USA, March 30th to April 1st. There were 36 accepted papers and two invited talks. The venue was quite impressive. However, our global impression is that the conference held few surprises.

In the cryptanalysis session, I (Ludovic) had two papers: ‘A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems’ (joint work Jean-Charles Faugère, Danilo Gligoroski, Simona Samardjiska, Enrico Thomae) and `Algebraic Cryptanalysis of a Quantum Money Scheme — the Noise-Free Case’ (joint work with Marta Conde Pena, Jean-Charles Faugère). The first paper, presented by Simona, describes a polynomial-time attacks against the multivariate schemes which use quasi-groups (such systems provided up to know the fastest signature scheme on eBACS). The second paper, presented by Marta, proposes a heuristic polynomial-time attack against a quantum-money scheme of Scott Aaronson and Paul Christiano (STOC’2012). The situation of the quantum-money scheme is not as bad as the MQQ cryptosystems. A tweak, already proposed by Scott Aaronson and Paul Christiano, allows to circumvent the attack presented by Marta, so your quantum money is still safe for now.

Ayoub Otmani gave a nice talk about a `Polynomial-Time Attack on the BBCRS Scheme’ (joint work with Alain Couvreur, Jean-Pierre Tillich, and Valérie Gautier Umaña). This is yet another attack using the square code distinguishing technique. The target was a McEliece scheme using somewhat `hidden’ GRS codes (you can find a description of the BBCRS scheme in your favourite Journal of Cryptology).

Antoine Joux gave a very accessible invited talk on `Recent Advances in Algorithms for Computing Discrete Logarithms’, focusing primarily on his recent result with Cecile Peirrot (presented at Asiacrypt 2014) which enables one to compute the logs of the factor base elements with lower complexity than before, in small characteristic fields.

Sanjam Garg gave an invited talk on `New Advances in Obfuscation and its Applications’ on his latest results (EC’14) about obfuscation. In reply to a question from the audience, obfuscation, with rigorous security proofs, is not yet practical.

Nico Döttling gave a clear presentation about `Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification’. In particular, a connection between solving LPN with small error and bounded number of samples and solving LPN with unbounded number of samples. This result can be used to construct a KDM secure public-key cryptosystem from LPN with small noise.

Vadim Lyubashevsky gave a well motivated and very clear presentation on `Simple Lattice Trapdoor Sampling from a Broad Class of Distributions’ (joint work with Daniel Wichs). The timely question that the authors investigated is whether we really need Gaussian distributions in lattice-based cryptography. According to Vadim, Gaussians could be replaced in most situations by different (suitable) distributions without harming the security. However, from a practical point of view, Gaussians lead to the most practical schemes. So, `we can view Gaussian distributions as an optimisation parameter’.

There were only a couple of talks directly relevant to ECC.

Allison B. Lewko gave a well motivated and very clear presentation on `A Profitable Sub-Prime Loan: Obtaining the Advantages of Composite Order in Prime-Order Bilinear Groups’ (joint work with Sarah Meiklejohn). As the title indicates, this work shows how one can obtain for prime order bilinear groups, several useful features which occur naturally for composite order bilinear groups.

I (Rob) presented `Faster ECC over GF(2^521 – 1)’ (joint work with Mike Scott) which gave improved timings for point multiplication on the NIST curve P-521 and the Edwards curve E-521. The latter is now under serious consideration for several new ECC standards (including NIST’s).

After PKC, NIST organised a workshop on `Cybersecurity in a Post-Quantum World’. The event was a success with 140 participants (which is more than attended the PKC conference) with many of them from industry, namely from CISCO, Microsoft, Security Innovation, even RSA security. It seems that quantum-safe cryptography is going to be a very hot topic in future.

— Rob Granger and Ludovic Perret

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s