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.

# Past Cryptography Seminar

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.

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.

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.

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.

We hope to bring together all Oxford researchers interested in Cryptography, in Quantum Computing and in the interactions between the two.

Please register at: http://oxford-cryptography-day.eventbrite.co.uk

Structure-preserving signatures are an important cryptographic primitive that is useful for the design of modular cryptographic protocols. In this work, we show how to bypass most of the existing lower bounds in the most efficient Type-III bilinear group setting. We formally define a new variant of structure-preserving signatures in the Type-III setting and present a number of fully secure schemes with signatures half the size of existing ones. We also give different constructions including constructions of optimal one-time signatures. In addition, we prove lower bounds and provide some impossibility results for the variant we define. Finally, we show some applications of the new constructions.

Trusted Platform Modules (TPMs) are currently used in large numbers of computers. In this talk, I will discuss the cryptographic algorithms supported by the current version of the Trusted Platform Modules (Version 1.2) and also those due to be included in the new version (Version 2.0). After briefly introducing the history of TPMs, and the difference between these two generations TPMs, I will focus on the challenges faced in developing Direct Anonymous Attestation (DAA) an algorithmic scheme designed to preserve privacy and included in TPMs.

The security of pairings-based cryptography relies on the difficulty of two problems: computing discrete logarithms over elliptic curves and, respectively, finite fields GF(p^n) when n is a small integer larger than 1. The real-life difficulty of the latter problem was tested in 2006 by a record in a field GF(p^3) and in 2014 and 2015 by new records in GF(p^2), GF(p^3) and GF(p^4). We will present the new methods of polynomial selection which allowed to obtain these records. Then we discuss the difficulty of DLP in GF(p^6) and GF(p^12) when p has a special form (SNFS) for which two theoretical algorithms were presented recently.