Speakers and Talks
Diego Aranha (University of Campinas, BR): Pairings are not dead, just resting
Since their first introduction as a cryptanalytic tool, bilinear pairings have moved to a very useful building block for cryptography. Current real-world applications of pairings include remote attestation, privacy-preserving blockchains and identity-based encryption. However, recent advances in the discrete log computation have reduced the efficiency of the main pairing constructions and previous candidates for standardization. This talk examines new sets of parameters for bilinear groups, to adjust security against these recent attacks, and discusses techniques for their efficient implementation in software.
Craig Costello (Microsoft Research, USA): Key encapsulation using supersingular isogenies
The National Institute of Standards and Technology (NIST) have called for proposals of quantum-resistant public-key cryptographic algorithms, with a deadline of November 30, 2017. Based on the scheme of Jao and De Feo, this talk will describe one such proposal for key encapsulation that is based on computing isogenies between supersingular elliptic curves. Time permitting, I will also touch on some recent and current research in this area. This is joint work with a whole bunch of people.
Joan Daemen (Radboud University, NL; and STMicroelectronics, BE): Innovations in permutation-based crypto
Imagine there's no block ciphers, it's easy if you try:-) A (cryptographic) permutation can be thought of as a block cipher (like AES or DES) without a key (or with a fixed key if you prefer). During the SHA-3 competition it became clear that permutation-based hashing, e.g., by using the sponge construction, is superior to block-cipher based hashing (as in MD5, SHA-1 and SHA-2). By including a key in the sponge input, it can readily be used for message authentication (MAC) and by exploiting the arbitrarily long sponge output even for stream encryption. The duplex variant of sponge widens the spectrum to, among other, authenticated encryption and reseedable pseudorandom generation and was adopted by a dozen submissions to the CAESAR competition for authenticated ciphers. The disadvantage of the sponge and duplex constructions is that they are inherently serial. To address this, we introduced a fully parallel counterpart of the sponge, called Farfalle. Clearly, there is a lot going on in permutation-based crypto and this talk will get you up to date.
Maria Dubovitskaya (IBM Zurich, CH): Privacy-preserving authentication from ECC for Blockchain and beyond
With an increasing number of identity and service providers, it is really
hard to gain the control over one’s personal data.
Therefore, identity management systems and privacy-preserving technologies
are becoming a key ingredient of modern IT infrastructure.
IBM Identity Mixer is an anonymous credential system that provides
user-centric identity management and strong authentication without
collecting personal data.
In this talk, I will explain the principles behind the Identity Mixer
technology and show a live demo.
I will also present our resent result – the first hierarchical (or
delegatable) anonymous credential system that is practical.
Our instantiation is based on a pairing-based signature scheme by Groth and
features a number of optimizations and efficiency improvements.
Finally, I will report on the implementation of our elliptic curve based
schemes in different programming languages in the context of transaction
authentication for Blockchain.
Luca De Feo (Université de Versailles Saint-Quentin, FR; and Inria Saclay, FR): 20 years of isogeny based cryptography
In this talk I will review the use of isogeny graphs in cryptography,
starting from Couveignes' "Hard Homogeneous Spaces" protocol, through
hash functions based on supersingular isogeny graphs, to the most
recent results on SIDH and related protocols.
I will try as much as possible to make the contents accessible to
non-specialists, and will highlight some open problems in the field.
Daniel Genkin (University of Pennsylvania and University of Maryland, US): May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519
In recent years, applications increasingly adopt security primitives designed with better countermeasures against side channel attacks. A concrete example is Libgcrypt's
implementation of ECDH encryption with Curve25519. The implementation employs the Montgomery ladder scalar-by-point multiplication, uses the unified, branchless Montgomery
double-and-add formula and implements a constant-time argument swap within the ladder. However, Libgcrypt's field arithmetic operations are not implemented in a constant-time
side-channel-resistant fashion.
Based on the secure design of Curve25519, users of the curve are advised that there is no need to perform validation of input points. In this work we demonstrate that when this
recommendation is followed, the mathematical structure of Curve25519 facilitates the exploitation of side-channel weaknesses.
We demonstrate the effect of this vulnerability on three software applications---encrypted git, email and messaging---that use Libgcrypt. In each case, we show how to craft
malicious OpenPGP files that use the Curve25519 point of order 4 as a chosen ciphertext to the ECDH encryption scheme. We find that the resulting interactions of the point at
infinity, order-2, and order-4 elements in the Montgomery ladder scalar-by-point multiplication routine create side channel leakage that allows us to recover the private key in as
few as 11 attempts to access such malicious files.
The talk will be based on joint work with Luke Valenta and Yuval Yarom.
Aurore Guillevic (Inria Nancy, FR): Simulating DL computation in GF(pn) with the new variants of the Tower-NFS algorithm to deduce security level estimates
The discrete logarithm problem (DLP) in cyclic groups is at the heart of many
asymmetric cryptosystems. At its start in the 70's, it was instantiated in
prime finite fields, or characteristic two finite fields. It was later
switched to elliptic curves.
The rise of pairing-based cryptography, in the year 2000, developed the
interest into DL in other type of finite fields such as GF(p2), GF(p6),
GF(p12), or GF(36*509). The quasi-polynomial-time algorithm has completely
broken the pairings over small characteristic finite fields (ECC 2013 talks).
Since then, the researchers started to look at DL in GF(pn) for small n,
specially for n≤6.
At the Asiacrypt 2015, Barbulescu, Gaudry and Kleinjung revisited the Tower
number field sieve technique for computing discrete logarithm in finite fields
GF(pn). It was then adapted to specific cases of pairings and turned out to
be very efficient, for example in GF(p12) (Kim-Barbulescu,
Menezes-Sarkar-Singh). In prime fields, the complexity of the NFS algorithm
is much more studied and understood. The size recommendations are based on the
asymptotic complexity and the latest record computations. With TNFS and its
variants, a record computation is not at hand yet, and the asymptotic
complexity can not be directly used to decide the security levels due to
unknown hidden constants.
Our first step to fill the gap between theory and computation records is to
simulate the extended Tower NFS variant, in particular for GF(p6) and
GF(p12). Then we will sketch a way to extrapolate the results to get a
security level, and propose size intervals for pairing-based cryptosystems
using MNT, BN, BLS and other curves.
Kimmo Järvinen (University of Helsinki, FI): Fast endomorphisms in hardware
Fast endomorphisms lead to fast scalar multiplications and, consequently, result in high-performance elliptic curve cryptosystems. Utilization of these endomorphisms requires manipulations with scalars and precomputations. This is often not a problem in software implementations where they result in only small increases of code and data memory requirements, which are typically insignificant compared to the achievable speed increase. However, the situation is less clear in hardware implementations because significant changes to computation architectures are required to support these extra operations; for example, a separate scalar conversion unit may be needed. In this talk, we survey recent works that have studied implementations of elliptic curve cryptosystems utilizing fast endomorphisms. We show that fast endomorphisms allow significant efficiency improvements also in hardware and, in particular, in modern field-programmable gate arrays (FPGAs) where special resources such as block memories or hardwired multipliers reduce the costs of computations required by the endomorphisms.
Pınar Kılıçer (University Oldenburg, DE): On primes dividing the denominators of the invariants of genus-3 curves
The j-invariants of elliptic curves with complex multiplication (CM) are algebraic integers hence the class polynomial has integer coefficients. For invariants of genus g = 2 or 3, this is not the case. Bounds on the primes in the denominators have been given for g=2 (Goren-Lauter). In this talk, we discuss the bounds on the primes appearing in the denominators of class polynomials of CM curves of genus 3.
David Kohel (Université d'Aix-Marseille, FR): Efficient arithmetic on binary elliptic curves
We recall the development of canonical models for elliptic curves with application to efficient arithmetic on binary curves. In particular we detail the μ4-normal form, its properties and its arithmetic. We conclude with its generalisation to the twisted μ4-normal form, from which we can extend efficient arithmetic to any ordinary elliptic curve over a finite field of characteristic~2. In particular, this provides backward compatibility with binary curve standards.
Tancrède Lepoint (SRI International, US): What's Up in Lattice Crypto?
In this talk, I'll review what is currently happening in lattice-based cryptography, from the practical deployement and standardization of its major building blocks (encryption, signature, key agreement protocols), to the ever-escaping practicality of fully homomorphic encryption and obfuscation, to its disadvantages compared to pairings, to its security landscape, and to its challenging open-problems.
Joost Renes (Radboud University, NL): qDSA: Small and Secure Digital Signatures with Curve-based Diffie-Hellman Key Pairs
In classic curve-based signature schemes such as ECDSA or EdDSA we explicitly rely on the group structure associated to the (hyper)elliptic curve. Therefore, Kummer varieties cannot be directly plugged into these schemes. However, there is no intrinsic reason why Kummer varieties cannot be efficiently used for signatures. In this talk I will present the "quotient Digital Signature Algorithm", which is an adaptation of the Schnorr signature scheme, removing the need for an explicit group addition.
Emmanuel Thomé (Inria Nancy, FR): A kilobit hidden SNFS discrete logarithm computation
We report a special number field sieve discrete logarithm computation in a 1024-bit prime field. Our chosen prime p looks random, and p-1 has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our p has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in Fp*, yet detecting that p has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of backdoored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. Our work highlights the importance of verifiably random primes.
Mehdi Tibouchi (NTT Secure Platform Laboratories, JP): Attacks on (EC)DSA with biased nonces
The "nonces" used to generate DSA, ECDSA and other Schnorr-like signatures are
very sensitive to biases: not only does reusing nonces cause immediate secret
key exposure, but even sampling them from a slightly non-uniform distribution
can yield to key recovery attacks.
This observation was originally due to Bleichenbacher, who proposed a Fourier
transform-based algorithm in the late 1990s to exploit such nonce biases. A
few years later, a less general but much more efficient attack based on
lattice reduction was proposed by Howgrave-Graham and Smart, and further
analyzed by Nguyen and Shparlinski.
In this talk, we propose to present both of these approaches, and discuss some
recent work in which those attacks have been revisited and extended.
Jaap Top (University of Groningen, NL): Arithmetic concerning Poncelet's closure theorem
Abstract: Given two smooth quadratic curves C, D in the plane and a pair (P, L) with P a point on C and L a line containing P and moreover tangent to D, one constructs a new such pair (P', L') by taking P' the "other" intersection point of L and C, and taking L' to be the "other" tangent line to D which contains P'. Iterating this process, one obtains a sequence of such pairs. Already Jacobi in the 19th century saw a connection between these sequences and the theory of elliptic functions. A century later Griffiths and Harris made this connection much more algebraic by explaining how it is related to elliptic curves. In the talk we make this much more explicit: we discuss the case where one works over a finite field, and we especially consider cases (including over the rational numbers and over quadratic fields) where the sequences obtained are periodic.
Benjamin Wesolowski (École polytechnique fédérale de Lausanne, CH): Isogeny graphs of ordinary abelian varieties
Fix a prime number l. Graphs of isogenies of degree a power of l are well-understood for elliptic curves, but not for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse graphs of so-called L-isogenies (for some ideals L above l), resolving that, in arbitrary dimension, their structure is similar, but not identical, to the "volcanoes" occurring as graphs of isogenies of elliptic curves. Specializing to the case of principally polarizable abelian surfaces, we then exploit this structure to describe graphs of a particular class of isogenies known as (l,l)-isogenies. These results lead to new, provable algorithms to navigate in isogeny graphs, with consequences for the CM-method in genus 2, for computing explicit isogenies, and for the random self-reducibility of the discrete logarithm problem in genus 2 cryptography.