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.

# Past Cryptography Seminar

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.