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

implementations.

# Past Cryptography Seminar

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.

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

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

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.

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.

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.

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.

Identity-based cryptography can be useful in situations where a full-scale public-key infrastructure is impractical. Original identity-based proposals relied on elliptic curve pairings and so are vulnerable to quantum computers. I will describe some on-going work to design a post-quantum identity-based encryption scheme using ideas from Ring Learning with Errors. Our scheme has the advantage that it can be extended to the hierarchical setting for more flexible key management.

In this lecture, we present practical and provably

secure (authenticated) key exchange protocol and password

authenticated key exchange protocol, which are based on the

learning with errors problems. These protocols are conceptually

simple and have strong provable security properties.

This type of new constructions were started in 2011-2012.

These protocols are shown indeed practical. We will explain

that all the existing LWE based key exchanges are variants

of this fundamental design. In addition, we will explain

some issues with key reuse and how to use the signal function

invented for KE for authentication schemes.