CWI Cryptology Group

Abstract: Ring and module lattices are widespread in lattice-based cryptography, allowing to dramatically improve the efficiency of several constructions. Most of these improvements are agnostic to the precise algebraic structure of the underlying ring. However, in some cases such a black-box approach fails to provide any gain and a finer-grained analysis is needed. In this talk, I will review some of these corner cases. Most of the time the underlying ring (e.g. Z[x] / (x^n + 1)) sits atop a tower of ring extensions, and comes with a set of tools which can be leveraged to project algorithmic problems in subrings. I will give a few examples where this approach yields improved algorithms. Based on [1,2,3]. [1] https://ia.cr/2015/1014 (joint work w/ Léo Ducas) [2] https://ia.cr/2019/015 (joint work w/ Thomas Pornin) [3] https://ia.cr/2019/320 (join work w/ Léo Ducas, Steven Galbraith and Yang Yu)

Abstract: In this presentation, I will first recall the Fiat-Shamir transformation, which is an important design principle for non-interactive zero-knowledge proofs and for digital signature schemes. In order to rigorously analyze the security of this transformation, one typically considers the random oracle model (ROM), which treats cryptographic hash functions as ideal objects. It is well known that (in the ROM) the Fiat-Shamir transformation preserves the security properties one cares about. However, the proof for this result breaks down in the quantum setting where the attacker is allowed to make superposition queries to the random oracle. Indeed, the security of the Fiat-Shamir transformation against a quantum attack was largely open; only some limited results were known, and some negative claims were actually made in the literature. Having set up the stage, I will then discuss our recent result, which shows full-fledged security of the Fiat-Shamir transformation against quantum attacks, i.e., in the so-called quantum ROM, and I will give some high-level intuition for our result. In the last part, I will briefly introduce a modification to a security definition for interactive proofs, which allows us to relativize a certain negative result, and which then makes our result on the Fiat-Shamir transformation relevant for a larger class of schemes.

Abstract:  The hardness of the shortest and closest lattice vector problems (SVP, CVP) lies at the basis of many lattice-based cryptosystems, and algorithms for these problems have now been studied for several decades. One particular variant of the closest vector problem, which allows for an initial preprocessing phase (CVPP), has received considerably less attention, even though applications are known in speeding up enumeration for SVP/CVP and, more recently, solving approximate SVP on ideal lattices. This talk will survey existing and new techniques for CVPP, part of which is based on ongoing work.

Abstract: Finding a short non zero vector in an Euclidean lattice is a well-studied problem which has proven useful to construct many cryptographic primitives. The current best asymptotic algorithm to find a relatively short vector in an arbitrary lattice is the BKZ algorithm. This algorithm recovers a vector which is at most $2^{n^{\alpha}}$ times larger than the shortest non zero vector in time $2^{n^{1-\alpha}}$ for any $\alpha$ between 0 and 1. In order to gain in efficiency, it is sometimes interesting to use structured lattices instead of general lattices. An example of such structured lattices are principal ideal lattices. One may then wonder whether, on the security front, it is easier to find short vectors in a structured lattice or not. Until 2016, there was no known algorithm which would perform better on principal ideal lattices than the BKZ algorithm (either classically or quantumly). In 2016, Cramer et al. proposed a quantum algorithm that finds a $2^{\sqrt n}$ approximation of the shortest non zero vector in polynomial time. However, the BKZ algorithm remained the best algorithm in the classical setting or for approximation factor smaller than $2^{\sqrt n}$ in the quantum setting. In this talk, I will present an algorithm that extends the one of Cramer et al. After some exponential pre-computation (which only depends on the number field and not on the ideal), this algorithm enables us to achieve better trade-offs for ideal lattices than the ones achieved by the BKZ algorithm for general lattices. If I have enough time, I will present some work in progress, which uses the same techniques. This is a joint work with Guillaume Hanrot, Changmin Lee, Damien Stehlé and Alexandre Wallet