Programme

A handful of recent cryptographic proposals rely on the conjectured hardness of the following problem in the ring of integers of a cyclotomic number field: given a basis of an ideal that is guaranteed to have a “rather short” generator, find such a generator. In the past year, Bernstein and Campbell-Groves-Shepherd have sketched potential attacks against this problem. Most notably, the latter authors feared a potential quantum polynomial-time algorithm (alternatively, replacing the quantum component with an algorithm of Biasse and Fieker would yield a classical subexponential-time algorithm). A key claim of Campbell et al. is that one step of their algorithm—namely, decoding the log-unit lattice of the ring to recover a short generator from an arbitrary one—is efficient (whereas the standard approach takes exponential time). However, very few convincing details were provided to substantiate this claim, and as a result it has met with some skepticism.

In this work, we remedy the situation by giving a rigorous theoretical and practical confirmation that the log-unit lattice is indeed efficiently decodable, in cyclotomics of prime-power index. The proof consists of two main technical contributions: the first is a geometrical analysis, using tools from analytic number theory, of the canonical generators of the group of cyclotomic units. The second shows that for a wide class of typical distributions of the short generator, a standard lattice-decoding algorithm can recover it, given any generator.

Joint work with Ronald Cramer, Chris Peikert and Oded Regev.

The talk will survey recent progress in algorithms for the elliptic curve discrete logarithm problem. I will briefly mention some results on the baby-step-giant-step and Pollard kangaroo algorithms. Then I will discuss index calculus algorithms using summation polynomials. Group actions on summation polynomials will be explained, together with the use of invariant coordinates and symmetry-breaking. In addition to surveying the work of many authors, the talk includes joint work with Wang and Zhang, Pollard and Ruprai, Gebregiyorgis.

Spy agencies are using the Internet to undermine liberal democracy. Despite—or possibly because—of this, Internet cryptography in practice barely goes beyond the state of the art of 1977. The GNUnet is a libre decentralised network designed for security and privacy using a wide range of modern cryptographic protocols instead of “trusted” third parties.

This talk will present some of the cryptographic protocols of the GNUnet system in a way that is suitable for an audience familiar with common cryptographic primitives. Specifically, we will cover confidential communication, the GNUnet public key infrastructure, secure multiparty computation for scalar product and privacy-preserving payments.

In pairing-friendly constructions, the target group is a finite field of small extension degree, commonly F_pⁿ with 1 ≤ n ≤ 12. To design pairing-friendly curves of suitable security, the discrete logarithm problem (DLP) should be of the same difficulty both on the curve and in the finite field. In this talk we study the difficulty of breaking the DLP in a finite field F_pⁿ. We improve the Number Field Sieve (NFS) algorithm to speed up DL computations in F_pⁿ of medium and large characteristic.

The NFS algorithm is the best known method to compute discrete logarithms (DL) in large characteristic finite fields F_pⁿ, with p large and n ≥ 1 small. This algorithm comprises four steps: polynomial selection, relation collection, linear algebra and finally, individual logarithm computation.

The first part of the talk will focus on polynomial selection dedicated to F_pⁿ for small n. This step outputs two polynomials defining two number fields. We will present the generalized Joux-Lercier and the Conjugation methods, providing the best asymptotic complexity (excluding MNFS variants) for computing DL in finite fields of medium and large characteristic. They are also the best methods in practice for small n (2 and 3).

After the relation collection and linear algebra phases, the (virtual) logarithm of a subset of elements in each number field is known. We will explain how to speed up these two phases with Galois automorphisms and explicit units.

The fourth step computes the discrete logarithm of the target element in F_pⁿ. If one can write a target preimage in one number field as a product of elements with known (virtual) logarithms, then one can deduce the discrete logarithm of the target. The traditional approach can be extremely slow, and it is too slow especially for n greater than 3. We present a significant improvement for individual logarithm computations for small n, both in practice and in asymptotic running-time.

The improvements to NFS will be illustrated by DL record computations in finite fields of about 600 bits and small n.

Elliptic curve crypto deployments are hindered by the complexity of the systems themselves, and of efficient implementations. Furthermore, the simplest implementations of ECC sometimes make less clear security guarantees than more complex ones. This talk will focus on trade-offs between complexity, performance, security and flexibility, particularly in the design of elliptic curve libraries.

We investigate the security of Diffie-Hellman key exchange as used in popular Internet protocols and find it to be less secure than widely believed. With the number field sieve algorithms, computing a single discrete log in prime fields is more difficult than factoring an RSA modulus of the same size. However, an adversary who performs a large precomputation for a prime p can then quickly calculate arbitrary discrete logs in groups modulo that prime, amortizing the cost over all targets that share this parameter. The algorithm can be tuned to reduce individual log costs even further. Although this fact is well known among mathematical cryptographers, it seems to have been lost among practitioners deploying cryptosystems. Using these observations, we implement a new attack on TLS in which a man-in-the-middle can downgrade a connection to 512-bit export-grade cryptography. In the 1024-bit case, we estimate that discrete log computations are plausible given nation-state resources, and a close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break.

Joint work with David Adrian, Karthikeyan Bhargavan, J. Alex Halderman, Benjamin VanderSloot, Eric Wustrow, Zakir Durumeric, Pierrick Gaudry, Matthew Green, Drew Springall, Emmanuel Thomé, Luke Valenta, Santiago Zanella-Béguelin, and Paul Zimmermann.

In this talk we will discuss various claims of algorithms which solve certain instances of ECDLP (elliptic curve discrete logarithm problem) for finite fields in sub-exponential time. In particular, we will discuss approaches which try to solve systems coming from summation polynomials in which the complexity relies on the so-called first fall degree assumption. We will raise doubt on this first fall degree assumption and hence on the claimed complexity of such algorithms.

Starting in 2004, several fault attacks against pairing computations have been described theoretically. Only ten years later, the first practical fault attack was published, proving that fault attacks against pairing-based cryptography are indeed possible and even practical—thus posing a serious threat to cryptographic devices and their sensitive secrets.

This talk will give an overview about fault attacks on pairing computations from 2004 until today. Special emphasis will be placed on the first practical higher-order fault attack against a real-world pairing implementation. Both mathematical and technical details of this attack will be presented, and countermeasures to prevent such attacks will also be discussed.

In this talk we present an improved variant of Claus Diem's quasi-linear index calculus for breaking the discrete logarithm problem on Jacobians of non-hyperelliptic genus 3 curves. Detailed and explicit computational complexity and memory complexity estimates will be given, resulting in a clear picture of the weaknesses of genus 3 non-hyperelliptic curves. This carries over to the security of genus 3 hyperelliptic curves via isogeny attacks, such as that of Smith. In addition to the attack of Smith, in recent years significant advances have been made in such explicit isogeny computations, turning them together with the quasi-linear non-hyperelliptic index calculus into a complex threat for hyperelliptic genus 3 cryptography.

Let p be a prime number. The classical modular polynomial of degree p is a polynomial that parameterizes isomorphism classes of elliptic curves (abelian varieties of dimension 1) together with an isogeny of degree p. The aim of the talk is to explain how to generalize and compute these polynomials in the dimension 2 case, where we consider principally polarized abelian surfaces.

The history of L(1/3)-algorithms started in 1984 when Coppersmith proposed a heuristic algorithm to solve the discrete logarithm problem in fields of characteristic 2. This initial progress quickly led to the introduction of several other heuristic algorithms with L(1/3) complexity both for factoring and discrete logarithm computations. Yet, for a long time, these algorithms only focused on fields with small characteristic, prime fields and occasionally fields of the form F_pⁿ for small values of n. Even if it was shown in 2006 that, taken together, the Number Field Sieve and the Function Field Sieve were enough to cover the whole range of finite fields with heuristic L(1/3) algorithms, medium characteristic finite fields continued to be considered as the hardest case to compute discrete logarithms.

In 2013 and 2014, several algorithmic improvements appeared. Besides the breathtaking step forward that has been made for finite fields with small characteristic, five variants of the Number Field Sieve have been designed for finite fields with medium to large characteristics.

In this talk, I focus on finite fields that still embody the hardest case for discrete logs, that is, when the characteristic is of medium size compared to the field cardinality. Combining two recent variants of the Number Field Sieve, namely the Conjugation Method and the Multiple variant, I present the currently best-known asymptotic algorithm to compute discrete logarithms in this case. Compared to previous state-of-the-art algorithms for medium characteristic, this theoretical improvement means that asymptotically the bitsize of the order of the finite fields should be increased by 6 per cent to recover the same security level.

Since the early times of elliptic-curve cryptography until today, the performance of ECC software has always been a very important research topic. Consequently, we saw (and still see) many papers optimizing elliptic-curve cryptography for a broad variety of target platforms ranging from small embedded microcontrollers to the latest server architectures by Intel and AMD. A somewhat more recent development is that most papers also propose software that does not leak secret information through timing. New ECC speed records every year and an increasing awareness of security against timing attacks clearly demonstrate the progress in this research area; however, for none of the speed-record-setting implementations we have any guarantees that those are actually correct. Multiple examples in the past showed that real-world ECC software was in fact not correct. Also, various claims of software to run in constant time turned out to be wrong, which lowers the confidence in such claims.

In my talk I will describe how we can regain confidence in the correcness and security of ECC software by means of formal verification. The target is to fully automatically verify that hand-optimized ECC software matches a high-level mathematical description and that this software is not leaking any secret information through timing. While we have not reached this target quite yet, I will show that is well within reach.

A relatively new hard problem in lattice-based cryptography is Ring Learning with Errors. I will describe the problem, its applications, and discuss its security from the perspective of recent attacks.

Elliptic curve cryptography (ECC) is the current main standard for asymmetric cryptography. Hyper-elliptic curve cryptography (HECC) is investigated for future applications. Our research group studies and prototypes hardware accelerators for ECC and HECC. Our accelerator architecture can be customized at design time with various numbers and types of units, curve parameters, key recoding methods and embedded protections against physical attacks (both passive and active ones). Finite field operations are handled in dedicated hardware units. Curve level operations (e.g. point addition and doubling) are handled in software using an instruction memory programmable by users at run time. Various configurations of the accelerator can be generated for very low cost solutions up to fast but costly ones. Various protections can be added such as randomized key recoding schemes, arithmetic units with uniform power profiles, randomized internal memory accesses. We also develop a complete software tool chain to program our accelerator (from assembly level to Python code inside Sage). Some configurations of our accelerator, and the corresponding software tools, will be available for academic and industrial collaborations. In this talk, we will present our architecture, our tool chain, several configurations of the arithmetic units and the impact of various protections. Our current results in mid-range FPGAs show that HECC leads to 40% more efficient solutions than ECC for a similar security level and silicon cost.