Past Cryptography Seminar

26 October 2016

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.

  • Cryptography Seminar
19 October 2016

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).

  • Cryptography Seminar
12 October 2016

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.

  • Cryptography Seminar
14 June 2016
Cas Cremers
During the last thirty years, there have been many advances in the development of protocols for
authenticated key exchange. Although signature-based variants of Diffie-Hellman have been
known since the start of this development, dozens of new (two message) protocols are still proposed each
year. In this talk, we present some of the recent history of security definitions for Authenticated Key
Exchange, their many relatives, and discuss strengths and weaknesses. We motivate why there
has been little convergence in terms of protocols or security definitions. I will also present some of our 
recent work in this domain, including new stronger security definitions, and how to achieve them.
  • Cryptography Seminar
8 June 2016
Gilles Zémor
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

Based on joint works with Christine Bachoc and Oriol Serra, and with Diego Mirandola.
  • Cryptography Seminar
1 June 2016
Roger Heath-Brown

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.

  • Cryptography Seminar
25 May 2016
Gaëtan Leurent

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.
We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon's algorithm: finding a collision requires Ω(2n/2) queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure when using a quantum-secure PRF.
Second, we show that slide attacks can also be sped up using Simon's algorithm. This is the first exponential speed up of a classical symmetric cryptanalysis technique in the quantum model.

  • Cryptography Seminar
18 May 2016
The cube attack of Dinur and Shamir and the AIDA attack of Vielhaber have been used successfully on 
reduced round versions of the Trivium stream cipher and a few other ciphers. 
These attacks can be viewed in the framework of higher order differentiation, as introduced by Lai in 
the cryptographic context. We generalise these attacks from the binary case to general finite fields, 
showing that we would need to differentiate several times with respect to each variable in order to have
a reasonable chance of a successful attack.
We also investigate the notion of “fast points” for a binary polynomial function f  
(i.e. vectors such that the derivative of f with respect to this vector has a lower 
than expected degree). These were  introduced by Duan and Lai, motivated by the fact that higher order 
differential attacks are usually more efficient if they use such points. The number of functions which 
admit fast points were computed by Duan et al in a few particular cases; we give explicit formulae for 
all remaining cases and discuss the cryptographic significance of these results.
  • Cryptography Seminar
11 May 2016
Serge Fehr

One of the peculiar features of quantum mechanics is
entanglement. It is known that entanglement is monogamous in the sense
that a quantum system can only be strongly entangled to one other
system. In this talk, I will show how this so-called monogamy of
entanglement can be captured and quantified by a "game". We show that,
in this particular game, the monogamy completely "cancels out" the
advantage of entanglement.
As an application of our analysis, we show that - in theory - the
standard BB84 quantum-key-distribution scheme is one-sided
device-independent, meaning that one of the parties, say Bob, does not
need to trust his quantum measurement device: security is guaranteed
even if his device is completely malicious.
The talk will be fully self-contained; no prior knowledge on quantum
mechanics/cryptography is necessary.

  • Cryptography Seminar