Isogenies are algebraic group morphisms of elliptic curves. Let E, E' be two (ordinary) elliptic curves defined over a finite field of characteristic p, and suppose that there exists an isogeny ψ between E and E'. The explicit isogeny problem asks to compute a rational function expression for ψ. Various specializations of this problem appear naturally in point counting and elliptic curve cryptography. There exist essentially two families of algorithms to compute isogenies. Algorithms based on Weierstraß' differential equation are very fast and well suited in the point count setting, but are clumsier in general. Algorithms based on interpolation work more generally, but have exponential complexity in log(p) (the characteristic of the finite field). We propose a new interpolation-based algorithm that solves the explicit isogeny problem in polynomial time in all the involved parameters. Our approach is inspired by a previous algorithm of Couveignes', that performs interpolation on the p-torsion on the curves. We replace the p-torsion in Couveignes' algorithm with the ℓ-torsion for some small prime ℓ; however this adaptation requires some non-trivial work on isogeny graphs in order to yield a satisfying complexity. Joint work with Cyril Hugounenq, Jérôme Plût and Éric Schost.

# Past Cryptography Seminar

Commitment schemes are a fundamental primitive in cryptography. Their security (more precisely the computational binding property) is closely tied to the notion of collision-resistance of hash functions. Classical definitions of binding and collision-resistance turn out too be weaker than expected when used in the quantum setting. We present strengthened notions (collapse-binding commitments and collapsing hash functions), explain why they are "better", and show how they be realized under standard assumptions.

Gauss was the first to give a formula for the number of monic irreducible polynomials of degree n over a finite field. A natural problem is to determine the number of such polynomials for which certain coefficients are prescribed. While some asymptotic and existence results have been obtained, very few exact results are known. In this talk I shall present an algorithm which for any finite field GF(q) of characteristic p expresses the number of monic irreducibles of degree n for which the first l < p coefficients are prescribed, for n >= l and coprime to p, in terms of the number of GF(q^n)-rational points of certain affine varieties defined over GF(q).

The GF(2) base field case is related to the distribution of binary Kloosterman sums, which have numerous applications in coding theory and cryptography, for example via the construction of bent functions. Using a variant of the algorithm, we present varieties (which are all curves) for l <= 7 and compute explicit formulae for l <= 5; before this work such formulae were only known for l <= 3. While this connection motivates the problem, the talk shall focus mainly on computational algebraic geometry, with the algorithm, theoretical questions and computational challenges taking centre stage.

Not considering classified work, the first person to have asked and solved the problem of secure communication over insecure communication channels was Ralph Merkle, in a project for a Computer securitjohn y course at UC Berkeley in 1974. In this work, he gave a protocol that allow two legitimate parties to establish a secret key with an effort of the order of N, but such that an eavesdropper can not discover the secret key with non-vanishing probability if he is not willing to spend an effort of at least the order of N^2.

In this talk, we will consider key exchange protocols in the presence of a quantum eavesdropper. Unfortunately, it is easy to see that in this case, breaking Merkle’s original protocol only requires an effort of the order of N, similar to the one of the legitimate parties. We will show how to restore the security by presenting two sequences of protocols with the following properties:

- In the first sequence, the legitimate parties have access to a quantum computer, and the eavesdropper's effort is arbitrarily close to N^2.

- In the second sequence, the protocols are classical, but the eavesdropper’s effort is arbitrarily close to N^{3/2}.

We will show the key exchange protocols, the quantum attacks with the proof of their optimality. We will focus mostly on the techniques from quantum algorithms and complexity theory used to devise quantum algorithms and to prove lower bounds. The underlying tools are the quantum walk formalism, and the quantum adversary lower bound method, respectively. Finally, we will introduce a new method to prove average-case quantum query complexity lower bounds.

The introduction of Edwards' curves in 2007 relaunched a

deeper study of the arithmetic of elliptic curves with a

view to cryptographic applications. In particular, this

research focused on the role of the model of the curve ---

a triple consisting of a curve, base point, and projective

(or affine) embedding. From the computational perspective,

a projective (as opposed to affine) model allows one to

avoid inversions in the base field, while from the

mathematical perspective, it permits one to reduce various

arithmetical operations to linear algebra (passing through

the language of sheaves). We describe the role of the model,

particularly its classification up to linear isomorphism

and its role in the linearization of the operations of addition,

doubling, and scalar multiplication.

The Algebraic Eraser is a cryptosystem (more precisely, a class of key

agreement schemes) introduced by Anshel, Anshel, Goldfeld and Lemieux

about 10 years ago. There is a concrete instantiation of the Algebraic

Eraser called the Colored Burau Key Agreement Protocol (CBKAP), which

uses a blend of techniques from permutation groups, matrix groups and

braid groups. SecureRF, the company owning the trademark to the

Algebraic Eraser, is marketing this system for lightweight

environments such as RFID tags and other Internet of Things

applications; they have proposed making this scheme the basis for an

ISO RFID standard.

This talk gives an introduction to the Algebraic Eraser, a brief

history of the attacks on this scheme using ideas from group-theoretic

cryptography, and describes the countermeasures that have been

proposed. I would not recommend the scheme for the proposed

applications: the talk ends with a brief sketch of a recent convincing

cryptanalysis of this scheme due to Ben-Zvi, Blackburn and Tsaban

(which appeared at CRYPTO this summer), and significant attacks

on the protocol in the proposed ISO standard due to Blackburn and

Robshaw (which appeared at ACNS earlier this year).

Linear algebra is a widely used tool both in mathematics and computer science, and cryptography is no exception to this rule. Yet, it introduces some particularities, such as dealing with linear systems that are often sparse, or, in other words, linear systems inside which a lot of coefficients are equal to zero. We propose to enlarge this notion to nearly sparse matrices, caracterized by the concatenation of a sparse matrix and some dense columns, and to design an algorithm to solve this kind of problems. Motivated by discrete logarithms computations on medium and high caracteristic finite fields, the Nearly Sparse Linear Algebra briges the gap between classical dense linear algebra problems and sparse linear algebra ones, for which specific methods have already been established. Our algorithm particularly applies on one of the three phases of NFS (Number Field Sieve) which precisely consists in finding a non trivial element of the kernel of a nearly sparse matrix.

Additive combinatorics enable one to characterise subsets S of elements in a group such that S+S has small cardinality. In particular a theorem of Vosper says that subsets of integers modulo a prime p with minimal sumsets can only be arithmetic progressions, apart from some degenerate cases. We are interested in q-analogues of these results, namely characterising subspaces S in some algebras such that the linear span of its square S^2 has small dimension. Analogues of Vosper's theorem will imply that such spaces will have bases consisting of elements in geometric progression. We derive such analogues in extensions of finite fields, where bounds on codes in the space of quadratic forms play a crucial role. We also obtain that under appropriately formulated conditions, linear codes with small squares for the component-wise product can only be generalized Reed-Solomon codes. Based on joint works with Christine Bachoc and Oriol Serra, and with Diego Mirandola.

Efficient factorization or efficient computation of class

numbers would both suffice to break RSA. However the talk lies more in

computational number theory rather than in cryptography proper. We will

address two questions: (1) How quickly can one construct a factor table

for the numbers up to x?, and (2) How quickly can one do the same for the

class numbers (of imaginary quadratic fields)? Somewhat surprisingly, the

approach we describe for the second problem is motivated by the classical

Hardy-Littlewood method.