Past Cryptography Seminar

7 March 2018
Elisabeth Oswald

Side channel leakage is no longer just a concern for industries that
traditionally have a high degree of awareness and expertise in
(implementing) cryptography. With the rapid growth of security
sensitive applications in other areas, e.g. smartphones, homes, etc.
there is a clear need for developers with little to no crypto
expertise to implement and instantiate cryptography securely on
embedded devices. In this talk, I explain what makes finding side
channel leaks challenging (in theory and in practice) and give an
update on our latest work to develop methods and tools to enable
non-domain experts to ‘get a grip’ on leakage in their

  • Cryptography Seminar
21 February 2018
Giacomo Micheli

Let n be a positive integer. In this talk we provide a recipe to 
construct full orbit sequences in the affine n-dimensional space over a 
finite field. For n=1 our construction covers the case of the well 
studied pseudorandom number generator ICG.

This is a joint work with Federico Amadio Guidi.

  • Cryptography Seminar
14 February 2018

Multivariate cryptography is one of a handful of proposals for post-quantum cryptographic schemes, i.e. cryptographic schemes that are secure also against attacks carried on with a quantum computer. Their security relies on the assumption that solving a system of multivariate (quadratic) equations over a finite field is computationally hard. 

Groebner bases allow us to solve systems of polynomial equations. Therefore, one of the key questions in assessing the robustness of multivariate cryptosystems is estimating how long it takes to compute the Groebner basis of a given system of polynomial equations. 

After introducing multivariate cryptography and Groebner bases, I will present a rigorous method to estimate the complexity of computing a Groebner basis. This approach is based on techniques from commutative algebra and is joint work with Alessio Caminata (University of Barcelona).

  • Cryptography Seminar
7 February 2018
Peter Schwabe

Large parts of the cryptography in use today,

key-agreement protocols and digital signatures based on the

hardness of factoring large integers or solving the

discrete-logarithm problem, are not secure against attackers

equipped with a large universal quantum computer. It is not

clear when such a large quantum computer will be built, but

continuous progress by various labs around the world suggests

that it may well be less than two decades until today's

cryptography will become insecure.

To address this issue, NIST started a public competition to

identify suitable replacements for today's cryptosystems. In

my talk, I will describe two of these systems: the

key-encapsulation mechanism Kyber and the digital signature

scheme Dilithium. Both schemes are based on the hardness of

solving problems in module lattices and they together form the

"Cryptographic Suite for Algebraic Lattices -- CRYSTALS".

  • Cryptography Seminar
24 January 2018
Daniel Dadush

Integer programming, the problem of finding an optimal integer solution satisfying linear constraints, is one of the most fundamental problems in discrete optimization. In the first part of this talk, I will discuss the important open problem of whether there exists a single exponential time algorithm for solving a general n variable integer program, where the best current algorithm requires n^{O(n)} time. I will use this to motivate a beautiful conjecture of Kannan & Lovasz (KL) regarding how "flat" convex bodies not containing integer points must be.

The l_2 case of KL was recently resolved in breakthrough work by Regev & Davidowitz `17, who proved a more general "Reverse Minkowski" theorem which gives an effective way of bounding lattice point counts inside any ball around the origin as a function of sublattice determinants. In both cases, they prove the existence of certain "witness" lattice subspaces in a non-constructive way that explains geometric parameters of the lattice. In this work, as my first result, I show how to make these results constructive in 2^{O(n)} time, i.e. which can actually find these witness subspaces, using discrete Gaussian sampling techniques. As a second main result, I show an improved complexity characterization for approximating the covering radius of a lattice, i.e. the farthest distance of any point in space to the lattice. In particular, assuming the slicing conjecture, I show that this problem is in coNP for constant approximation factor, which improves on the corresponding O(log^{3/2} n) approximation factor given by Regev & Davidowitz's proof of the l_2 KL conjecture.

  • Cryptography Seminar
17 January 2018

With the evolution towards the IoT and cyber-physical systems, the role that the underlying hardware plays in securing an application is becoming more prominent. Hardware can be used constructively, e.g. for accelerating computationally- intensive cryptographic algorithms. Hardware can also be used destructively, e.g., for physical attacks or transistor-level Trojans which are virtually impossible to detect. In this talk, we will present case studies for high-speed cryptography used in car2x communication and recent research on low-level hardware Trojans. 

  • Cryptography Seminar
22 November 2017

Broken cryptographic algorithms and hardness assumptions are a constant
threat to real-world protocols. Prominent examples are
hash functions for which collisions become known, or number-theoretic
assumptions which are threatened by advances in quantum computing.
Especially when it comes to key exchange protocols, the switch to
quantum-resistant primitives has begun and aims to protect today’s
secrets against future developments, moving from common Diffie–Hellman
based solutions to Learning-With-Errors-based approaches. Remarkably,
the authentication step in such protocols is usually still carried out
with quantum-vulnerable signature schemes. The intuition here is that
the adversary would need to break this protocol primitive today, without
having quantum power yet. The question we address here is if this
intuition is justified, and if so, if we can show this rigorously. We
particularly consider the authenticated variant of the recently
introduced post-quantum secure key exchange protocol NewHope (Alkim et
al., USENIX Security 2016), as well as by TLS 1.3, which is currently
being developed by the Internet Engineering Task Force.

  • Cryptography Seminar
8 November 2017
Fabrice Mouhartem

Adaptive oblivious transfer (OT) is a protocol where a sender
initially commits to a database {M_i}_{i=1}^N . Then, a receiver can query the
sender up to k times with private indexes ρ_1, …, ρ_k so as to obtain
M_{ρ_1}, …, M_{ρ_k} and nothing else. Moreover, for each i ∈ [k], the receiver’s
choice ρ_i may depend on previously obtained messages {M_ρ_j}_{j<i} . Oblivious transfer
with access control (OT-AC) is a flavor of adaptive OT
where database records are protected by distinct access control policies
that specify which credentials a receiver should obtain in order to access
each M_i . So far, all known OT-AC protocols only support access policies
made of conjunctions or rely on ad hoc assumptions in pairing-friendly
groups (or both). In this paper, we provide an OT-AC protocol where access policies may consist of any branching program of polynomial length, which is sufficient to realize any access policy in NC^1. The security of
our protocol is proved under the Learning-with-Errors (LWE) and Short-
Integer-Solution (SIS) assumptions. As a result of independent interest,
we provide protocols for proving the correct evaluation of a committed
branching program on a committed input.

Joint work with Benoît Libert, San Ling, Khoa Nguyen and Huaxiong Wang.

  • Cryptography Seminar