Past Cryptography Seminar

The amount of digital data that requires long-term protection 
of integrity, authenticity, and confidentiality protection is steadily 
increasing. Examples are health records and genomic data which may have 
to be kept and protected for 100 years and more. However, current 
security technology does not provide such protection which I consider a 
major challenge. In this talk I report about a storage system that 
achieves the above protection goals in the long-term. It is based on 
information theoretic secure cryptography (both classical and quantum) 
as well as on chains of committments. I discuss its security and present 
a proof-of-concept implementation including an experimental analysis.

Classical modular functions and forms may be evaluated numerically using truncations of the q-series of the Dedekind eta-function or of Jacobi theta-constants. We show that the special structure of the exponents occurring in these series makes it possible to evaluate their truncations to N terms with N+o(N) multiplications; the proofs use elementary number theory and sometimes rely on a Bateman-Horn type conjecture. We furthermore obtain a baby-step giant-step algorithm needing only a sublinear number of multiplications, more precisely O (N/log^r N) for any r>0. Both approaches lead to a measurable speed-up in practical precision ranges, and push the cross-over point for the asymptotically faster arithmetic- geometric mean algorithm even further.

(joint work with William Hart and Fredrik Johansson) ​

In this seminar, we present a fast fully homomorphic encryption (FHE) based on GSW and its ring variants. The cryptosystem relies on the hardness of lattice problems in the unique domain (e.g. the LWE family). After a brief presentation of these lattice problems, with a few notes on their asymptotic and practical average case hardness, we will present our homomorphic cryptosystem TFHE, based on a ring variant of GSW. TFHE can operate in two modes: The first one is a leveled homomorphic mode, which has the ability to evaluate deterministic automata (or branching programs) at a rate of 1 transition every 50microseconds. For the second mode, we also show that this scheme can evaluate its own decryption in only 20milliseconds, improving on the the construction by Ducas-Micciancio, and of Brakerski-Perlman. This makes the scheme fully homomorphic by Gentry's bootstrapping principle, and for instance, suitable for representing fully dynamic encrypted databases in the cloud.

We present “Ouroboros,” the first blockchain protocol based on proof of stake with rigorous security guarantees. We establish security properties for the protocol comparable to those achieved by the bitcoin blockchain protocol. As the protocol provides a “proof of stake” blockchain discipline, it offers qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). We showcase the practicality of our protocol in real world settings by providing experimental results on transaction processing time obtained with a prototype implementation in the Amazon cloud. We also present a novel reward mechanism for incentivizing the protocol and we prove that given this mechanism, honest behavior is an approximate Nash equilibrium, thus neutralizing attacks such as selfish mining. 

Joint work with  Alexander Russell and Bernardo David and Roman Oliynykov

Code based Cryptography had its beginning in 1978 when Robert McEliece
demonstrated how the hardness of decoding a general linear code up to
half the minimum distance can be used as the basis for a public key
crypto system.  At the time the proposed system was not implemented in
practice as the required public key was relatively large.

With the realization that a quantum computer would make many
practically used systems obsolete coding based systems became an
important research subject in the area of post-quantum cryptography.
In this talk we will provide an overview to the subject.

In addition  we will report on recent results where the underlying
code is a disguised Gabidulin code or more generally a subspace
code and where the distance measure is the rank metric respecively the
subspace distance.
 

We introduce Learning with Errors and Ring Learning with Errors, two hard
lattice problems which are widely used for security of Homomorphic
Encryption schemes. Following a study we conducted comparing four such
schemes, the best scheme was the so-called BGV scheme, introduced by
Brakerski-Gentry-Vaikuntanathan in 2012. We present it as an example of a
ring-based homomorphic scheme, discussing its number theoretic
optimisations.

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.

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.

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.

In this talk, I'll discuss some personal experiences - good, bad, and
ugly - of disclosing vulnerabilities in a range of different cryptographic
standards and implementations. I'll try to draw some general lessons about
what works well and what does not.