## Great animations explaining SIDH

There is a great blog post by Wouter Castryck on the COSIC research group (KU Leuven) website about supersingular Isogeny Diffie-Hellman (SIDH). I’ve been meaning to write about this for months but haven’t had the time. So in the meantime read about it here: Elliptic curves are quantum dead, long live elliptic curves.

— Steven Galbraith

## CRYPTO and PQCRYPTO

The list of accepted papers to Crypto 2017 is now online. Some highlights for ECC fans include:

• “The first collision for full SHA-1” by Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov
• “Fast Secure Two-Party ECDSA Signing” by Yehuda Lindell
• “Identity-Based Encryption from the Diffie-Hellman Assumption” by Nico Döttling and Sanjam Garg

The conference takes place August 20-24, 2017 in Santa Barbara.

The Eighth International Conference on Post-Quantum Cryptography (PQCrypto 2017)
takes place in Utrecht, the Netherlands, June 26–28, 2017.
The invited speakers are:

•     Jaya Baloo
•    Lieven Vandersypen

The list of acepted papers is available, and includes a session on isogeny-based crypto.

— Steven Galbraith

## Eurocrypt 2017

Eurocrypt 2017 was hosted by the ENS crypto group in Paris, France. There were four talks of special interest to researchers in curve-based cryptography, and a couple of items in the Rump Session.

## Twisted $\mu_4$-normal form for elliptic curves

David Kohel introduced the $\mu_4$-normal form for elliptic curves five years ago (at Indocrypt 2012). These curves are basically the “right way” to generalize Edwards curve arithmetic to characteristic 2. And they’re the right generalization not only mathematically, but also NIST-ically: existing standardized characteristic 2 curves cannot be transformed into $\mu_4$-normal form. David’s paper twists its way around that obstruction, for a small cost of two extra multiplications per point addition. These twisted $\mu_4$-normal curves are clearly the fastest and prettiest standard-compatible characteristic-2 elliptic curves out there. This is great news for binarophiles, and it will be interesting to see if implementers working on the hardware level can get much benefit from this.

## Efficient compression of SIDH public keys

Joost Renes gave a remarkably accessible talk about his work with Craig Costello, David Jao, Patrick Longa, Michael Naehrig, and David Urbanik on compressing public keys for the Supersingular Isogeny Diffie–Hellman protocol. SIDH is the best-known supposedly-quantum-resistant elliptic curve cryptosystem; while it might be slow compared with other postquantum alternatives, its principal attraction for cryptographers is its particularly small keys. Well, those keys are now even smaller (330 bytes for 128-bit security)—but the interesting thing in this paper is a much-improved key compression algorithm, which runs an order of magnitude faster than previous methods.

## Computation of a 768-bit prime field discrete logarithm

Thorsten Kleinjung gave a really nice talk on his record discrete logarithm computation with Claus Diem, Arjen Lenstra, Christine Priplata, and Colin Stahlke. Together they computed a discrete logarithm in a 768-bit prime field.
Why 768 bits? Because that matches the record for general integer factorization (from 2009, in a project that also included Thorsten and Arjen), which was computed with the General Number Field Sieve (GNFS); and GNFS is also what we use for prime-field discrete logs. In contrast to most recent finite-field discrete-log results which attack small-characteristic or pairing-related fields, this computation represents the state-of-the-art in the classic prime-field case.

The prime in question was $p = [2^{766}\pi] + 6272$, which is the smallest “safe prime” larger than $2^{766}\pi$ (“safe” meaning that $(p-1)/2$ is also prime, so that this represents the hardest case for generic algorithms applied to finite fields of the same size). The element 11 generates the multiplicative group of $\mathbb{F}_p$.

No doubt the question you are asking yourself right now is “what is the discrete logarithm of $[2^{766}e]$ with respect to the base 11?”  Ask no more, for Thorsten has the answer: it’s 325923617918270562238615985978623709128341338833721058543950813521768156295091638348030637920237175638117352442299234041658748471079911977497864301995972638266781162575370644813703762423329783129621567127479417280687495231463348812.

…So now you know. But as Thorsten points out, the journey is more interesting than the final destination: using some clever techniques detailed in the paper, this calculation took much less time and effort (a whole order of magnitude!) than the authors expected. Before you get too excited, it still took 5300 core years—but if this isn’t the exact discrete logarithm you are looking for, computing another one in the same field will now only take two core days. From a cryptographic perspective, that two-core-day figure is especially interesting, because that’s the time required to break actual keys, after a 5-core-millennium precomputation depending only on the field.

## A kilobit hidden SNFS discrete logarithm computation

Joshua Fried spoke about his work on with Pierrick Gaudry, Nadia Heninger, and Emmanuel Thomé about discrete logarithms in an even bigger prime field: 1024 bits. How can you compute discrete logs in such a large prime field? You cheat—or, I should say, the parameter generator cheats. Our estimates of the difficulty of these problems, and the cryptosystems that depend on them, are based on the performance of the General Number Field Sieve algorithm (GNFS). But Dan Gordon explained 25 years ago how to choose primes that are vulnerable to the much faster Special Number Field Sieve (SNFS)—but only if we know a secret backdoor, and detecting that backdoor is apparently infeasible. This project set up an instance of a backdoored 1024-bit prime, and then solved it.  This means that if you’re still using 1024-bit fields (and why are you doing such a thing in the twenty-first century?), then you should be extremely careful about their provenance. Kevin McCurley asked an interesting question: is Gordon’s backdoor optimal?

## Speeding up the Huff form of elliptic curves

Gamze Orhon gave a lightning-fast presentation of her work with Huseyin Hisil on optimizing Huff curve arithmetic during the rump session. The key is viewing these curves as curves in $\mathbb{P}^1\times\mathbb{P}^1$, rather than $\mathbb{P}^2$. The details are in their preprint.

## A database of discrete logarithm computations

Aurore Guillevic and Laurent Grémy have established a new reference website to help you keep track of records progress and progress in finite field discrete logarithm computations. It was about time we had a better solution than trawling the archives of the NMBRTHRY list! Laurent is hosting a front-end on his website, but what’s really nice is that the database itself is git-able.

—Ben Smith

Posted in Uncategorized | 3 Comments

## ECC Conference 2017

The 21st Workshop on Elliptic Curve Cryptography will take place in Nijmegen, The Netherlands, November 13–15, 2017.

— Steven Galbraith

## ECC 2017, Nijmegen November 13-15

The ECC 2017 conference will be held in Nijmegen, The Netherlands, November 13-15, 2017. There will be a school held before the conference on November 9-11.

https://ecc2017.cs.ru.nl/

## Asiacrypt 2016

Asiacrypt was held in Hanoi this year and was extremely well organised. There were quite a few papers about elliptic curves, and related areas such as post-quantum cryptography. It is worth noting that the talks were all streamed online and should eventually be able to be viewed on the IACR youtube channel.

The three invited talks were:

• Nadia Heninger “The Reality of Cryptographic Deployments on the Internet”.

Nadia described several bad implementations of finite field Diffie-Hellman key exchange, surveying work of several recent papers by many authors. She commented that finite field Diffie-Hellman is prevalent in practice partly due to concerns that elliptic curves might have US government trapdoors.

• Hoeteck Wee “Advances in Functional Encryption”

Hoeteck gave a wonderfully clear overview of functional encryption.

• Neal Koblitz “Cryptography in Vietnam in the French and American Wars”

Neal gave a fascinating historical talk, based on recent research by himself, the general chair Hieu Phan and others, and drawing on historical resources from museums in Hanoi and the writings of historians and former government employees. Neal emphasized the mathematical and cryptographical ingenuity of the Vietnamese people, as well as powerfully evoking the horrors of war and the heroism of certain individuals (both Vietnamese and American).

The best paper award went to Ilaria Chillotti, Nicolas Gama, Mariya Georgieva and Malika Izabachène for “Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds”, which shows that homomorphic encryption (in this case the GSW scheme with packed ciphertexts, together with a bunch of clever new ideas) is gradually becoming closer to practicality. Here is a photo of the best paper award authors with the two program chairs (Tsyoshi Takagi on the left and Jung Hee Cheon on the right).

Some papers related to discrete logarithms and elliptic curves included:

• Palash Sarkar and Shashank Singh “A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm”.

This work is relevant for assessing the security of pairing based cryptography, more details on this application can be found here.

• Steven D. Galbraith, Christophe Petit, Barak Shani and Yan Bo Ti “On the Security of Supersingular Isogeny Cryptosystems”

The paper contains several results about the (potentially post-quantum) isogeny-based key exchange and encryption protocols of De Feo, Jao and Plut.

• There was an entire session about ABE and IBE, containing papers that use pairings:
• Nuttapong Attrapadung “Dual System Encryption Framework in Prime-Order Groups via Computational Pair Encodings”
• Junqing Gong, Xiaolei Dong, Jie Chen and Zhenfu Cao “Efficient IBE with Tight Reduction to Standard Assumption in the Multi-challenge Setting”
• Melissa Chase, Mary Maller and Sarah Meiklejohn “Déjà Q All Over Again: Tighter and Broader Reductions of q-Type Assumptions”
• Shuichi Katsumata and Shota Yamada “Partitioning via Non-Linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps”

• Paz Morillo, Carla Ràfols and Jorge L. Villar “The Kernel Matrix Diffie-Hellman Assumption”

This talk is about relations between variants of the Diffie-Hellman problem.

• Ted Chinburg, Brett Hemenway, Nadia Heninger and Zachary Scherr “Cryptographic applications of capacity theory: On the optimality of Coppersmith’s method for univariate polynomials”

Ted Chinburg delivered a clear and interesting survey of “capacity theory” (a branch of arithmetic geometry/algebraic number theory) that is relevant to the analysis of Coppersmith’s technique for finding small solutions to polynomial equations. The authors hope these ideas will be useful in other contexts in cryptography/cryptanalysis.

Regarding the increased focus on post-quantum crypto there were talks on multivariate crypto (more efficient Multi-quadratic-polynomial signatures), lattices (Vadim Lyubashevsky presented a result about signatures based on ring-SIS in *any* ring and urged the audience to work on a much harder but more interesting problem relating to LWE in any ring) and code-based crypto (an adaptive attack on a decoding algorithm).

The rump session was chaired by me, and was thankfully short. The best and most entertaining talk was given by Pierre Karpman and Jerome Plut. The social activities included a Water Puppet show and a Vietnamese banquet with traditional music.

— Steven Galbraith