MathCrypt 2018

The MathCrypt 2018 event (affiliated with Crypto 2018) took place in Santa Barbara CA on the 19th of August. Five out of fifteen talks were devoted to Elliptic Curve Cryptography. The slides of talks are available on the conference website.

An improvement to the quaternion analogue of the L-isogeny path problem, by Spike Smith

This talk focused on the analogue of the l-isogeny path problem, important for the security of the Charles-Goren-Lauter hash function, under the Deuring correspondence between supersingular elliptic curves and left ideals of quaternion orders. While an algorithm by Kohel-Lauter-Petit-Tignol is known that solves the problem in probabilistic polynomial time, this work improves on the run time of the algorithm, and the size of the solution that is found. This improvement allows for smaller signatures in the Galbraith-Petit-Silva identification protocol. Two more significant improvements to the KLPT are being developed and will be published in an extended version of the paper.

Multi-Party Non-interactive Key Exchange and more from Isogenies on Elliptic Curves, by Dan Boneh

The room was packed for the talk about “Multi-Party Non-interactive Key Exchange and more from Isogenies on Elliptic Curves”. Dan reminded the audience of cryptographic group actions such as CRS and CSIDH and how they give rise to elegant Post Quantum secure Diffe-Hellmann like protocols. Then he talked about the new paper which introduces a new generalization of cryptographic group actions that would result in NIKE, BLS signatures and more. The paper gives a candidate construction of this powerful new primitive apart from the fact that one crucial ingredient, namely an efficiently computable isomorphism invariant of a product of elliptic curves, is missing.

Extra Secrets from Automorphisms and SIDH-based NIKE, by David Urbanik

The basic observation underlying this talk is that when doing SIDH starting from a curve which has nontrivial automorphisms, it is possible to exploit these automorphisms to derive multiple secrets for the same pair of public keys. This can be used to protect against the GPST attack and obtain non-interactive key exchanges in ways that are more efficient than previous approaches.

A new Poly space attack on CRS and CSIDH, by Jason Legrow

This work gives a new implementation of Regev’s quantum algorithm for inverting the CM action which can be used to attack the CRS and CSIDH cryptosystems. Like earlier attacks, the time and space complexity of the attack is subexponential, however the advantage of the new attack is that it only requires polynomial quantum space. The problem with previous attacks was that evaluating the CM action (which happens in superposition) required subexponential time and space. This is solved with a purely classical precomputation that allows the CM action to be evaluated in subexponential time, but in polynomial space, eliminating the need for subexponential amounts of quantum memory.

Quasi-subfield polynomials and the Elliptic Curve Discrete Log Problem, by Michiel Kosters

This work investigates if it is possible to generalize index calculus attacks to break the ECDLP problem for curves over the field GF(p^n), where p is a small prime, and n is a prime. The main idea is to replace the subfield polynomial X^p - X, which is used in the usual Gaudry/Diem-type index calculus attack on curves over GF(p^n) with large p, and replace this polynomial by a polynomial of the form f(X) = X^{p^{n'}} - \lambda(X), where \lambda(X) has small degree such that f(X) splits completely over GF(q^n). To make the index calculus algorithm efficient the degree of \lambda is low. When the degree of \lambda is low enough, the polynomial f(X) is called a quasi-subfield polynomial. Quasi-subfield polynomials can be used to solve the ECDLP slightly faster than with exhaustive search, but to improve over the baby-step giant-step algorithm much better quasi-subfield polynomials would need to be found.

— Ward Beullens

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