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, 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: those whose kernels are maximal isotropic subgroups of the l-torsion for the Weil pairing. We use these two results to write an algorithm giving a path of computable isogenies from an arbitrary absolutely simple ordinary abelian surface towards one with maximal endomorphism ring, which has immediate 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.

Arithmetic and geometric structures in cryptography

Benjamin Pierre Charles Wesolowski

We explore a few algebraic and geometric structures, through certain questions posed by modern cryptography. We focus on the cases of discrete logarithms in finite fields of small characteristic, the structure of isogeny graphs of ordinary abelian varieties, and the geometry of ideals in cyclotomic rings. The presumed difficulty of computing discrete logarithms in certain groups is essential for the security of a number of communication protocols deployed today. One of the most classic choices for the underlying group is the multiplicative group of a finite field. Yet this choice is showing its age, and particularly when the characteristic of the field is small: recent algorithms allow to compute logarithms efficiently in these groups. However, these methods are only heuristic: they seem to always work, yet we do not know how to prove it. In the first part, we propose to study these methods in the hope to get a better understanding, notably by revealing the geometric structures at play. A more modern choice is the group of rational points of an elliptic curve defined over a finite field. There, the difficulty of the discrete logarithm problem seems at its peak. More generally, the group of rational points of an abelian variety (notably the Jacobian of a curve of small genus) could be appropriate. One of the main tools for studying discrete logarithms on such objects is the notion of isogeny: a morphism from a variety to another one, which allows, among other things, to transfer the computation of a logarithm. Whereas the theory for elliptic curves is already mature, little is known about the structures formed by these isogenies (the isogeny graphs) for varieties of higher dimension. In the second part, we study the structure of isogeny graphs of absolutely simple, ordinary abelian varieties, with a few consequences regarding discrete logarithms on Jacobians of hyperelliptic curves of genus 2, the main object of concern of so-called hyperelliptic cryptography. The security of quite a few protocols, notably those relying on discrete logarithms, would collapse in front of an adversary equipped with a large-scale quantum computer. This perspective motivates cryptographers to study problems that would resist this technological feat. One of the major directions is cryptography based on Euclidean lattices, relying on the difficulty to find short vectors in a given lattice. For efficiency, one benefits from considering lattices endowed with more structure, such as the ideals of a cyclotomic field. In the third part, we study the geometry of these ideals, and show that a quantum computer allows to efficiently find much shorter vectors in these ideals than is currently possible in generic lattices.

EPFL2018

Computational Aspects of Jacobians of Hyperelliptic Curves

Alina Dudeanu

Nowadays, one area of research in cryptanalysis is solving the Discrete Logarithm Problem (DLP) in finite groups whose group representation is not yet exploited. For such groups, the best one can do is using a generic method to attack the DLP, the fastest of which remains the Pollard rho algorithm with

r

-adding walks. For the first time, we rigorously analyze the Pollard rho method with

r

-adding walks and prove a complexity bound that differs from the birthday bound observed in practice by a relatively small factor. There exist a multitude of open questions in genus

2

cryptography. In this case, the DLP is defined in large prime order subgroups of rational points that are situated on the Jacobian of a genus~

2

curve defined over a large characteristic finite field. We focus on one main topic, namely we present a new efficient algorithm for computing cyclic isogenies between Jacobians. Comparing to previous work that computes non cyclic isogenies in genus~

2

, we need to restrict to certain cases of polarized abelian varieties with specific complex multiplication and real multiplication. The algorithm has multiple applications related to the structure of the isogeny graph in genus~

2

, including random self-reducibility of DLP. It helps support the widespread intuition of choosing \emph{any} curve in a class of curves that satisfy certain public and well studied security parameters. Another topic of interest is generating hyperelliptic curves for cryptographic applications via the CM method that is based on the numerical estimation of the rational Igusa class polynomials. A recent development relates the denominators of the Igusa class polynomials to counting ideal classes in non maximal real quadratic orders whose norm is not prime to the conductor. Besides counting, our new algorithm provides precise representations of such ideal classes for all real quadratic fields and is part of an implementation in Magma of the recent theoretic work in the literature on the topic of denominators.

EPFL2016

Attacks on some post-quantum cryptographic protocols: The case of the Legendre PRF and SIKE

Novak Kaluderovic

Post-quantum cryptography is a branch of cryptography which deals with cryptographic algorithms whose hardness assumptions are not based on problems known to be solvable by a quantum computer, such as the RSA problem, factoring or discrete logarithms.This thesis treats two such algorithms and provides theoretical and practical attacks against them.The first protocol is the generalised Legendre pseudorandom function - a random bit generator computed as the Legendre symbol of the evaluation of a secret polynomial at an element of a finite field. We introduce a new point of view on the protocol by analysing the action of the group of Möbius transformations on the set of secret keys (secret polynomials).We provide a key extraction attack by creating a table which is cubic in the number of the function queries, an improvement over the previous algorithms which only provided a quadratic yield. Furthermore we provide an ever stronger attack for a new set of particularly weak keys.The second protocol that we cover is SIKE - supersingular isogeny key encapsulation.In 2017 the American National Institute of Standards and Technology (NIST) opened a call for standardisation of post-quantum cryptographic algorithms. One of the candidates, currently listed as an alternative key encapsulation candidate in the third round of the standardisation process, is SIKE.We provide three practical side-channel attacks on the 32-bit ARM Cortex-M4 implementation of SIKE.The first attack targets the elliptic curve scalar multiplication, implemented as a three-point ladder in SIKE. The lack of coordinate randomisation is observed, and used to attack the ladder by means of a differential power analysis algorithm.This allows us to extract the full secret key of the target party with only one power trace.The second attack assumes coordinate randomisation is implemented and provides a zero-value attack - the target party is forced to compute the field element zero, which cannot be protected by randomisation. In particular we target both the three-point ladder and isogeny computation in two separate attacks by providing maliciously generated public keys made of elliptic curve points of irregular order.We show that an order-checking countermeasure is effective, but comes at a price of 10% computational overhead. Furthermore we show how to modify the implementation so that it can be protected from all zero-value attacks, i.e., a zero-value is never computed during the execution of the algorithm.Finally, the last attack targets a point swapping procedure which is a subroutine of the three-point ladder. The attack successfully extracts the full secret key with only one power trace even if the implementation is protected with coordinate randomisation or order-checking. We provide an effective countermeasure --- an improved point swapping algorithm which protects the implementation from our attack.

EPFL2022