Applied Crypto Group
Wednesday, September 28th, 2022, 11:00 AM: Robin Köstler (University of Freiburg, Germany)
Room MNO 1.030, Belval Campus
A survey on modern bootstrapping for fully homomorphic encryption (FHE)
Abstract: we present a survey on the mathematical details of FHE,
focusing on the technique of blind rotations that is applicable to
many nowadays used schemes (CKKS, BFV, BGV). We also describe an
implementation based on BFV encoding, in order to provide an
introduction to bootstrapping.
Source:
eprint.iacr.org/2021/691.pdf
Thursday, March 24th, 2022, 11:00 AM: Benoit Cogliati (CISPA, Germany)
Room MNO 1.030, Belval Campus
Title: Mirror Theory and Cryptography
Abstract: In symmetric cryptography, one of the most common proof
strategy is to rely on the H coefficients technique to transform a
cryptographic problem (typically a distinguishing experiment) into a
combinatorial problem. In particular, one often has to lower bound
the number of solutions of some system of linear equalities that
also satisfy some distinctness conditions. The study of such systems
has been systematized by Jacques Patarin and dubbed Mirror
Theory. In this talk, we present the first complete and streamlined
proof of a fundamental Mirror Theory result, dubbed the Pi+Pj
theorem for any ximax, along with a few cryptographic
applications. In more details, we prove that the number of tuples of
n-bit strings (P1,...,Pq) that are pairwise distinct and satisfy a
system of equations of the form Pi xor Pj = lambda(i,j) is
either 0, or greater than the average over all n-bit strings
lambda(i,j).
Tuesday, March 8th, 2022, 2:00 PM: Gaëtan Cassiers (UCL, Belgium)
Room MNO 1.030, Belval Campus
Title: Composable masking schemes for side-channel security: the probe isolation approach.
Abstract:
Masking is a well-known countermeasure against side-channel attacks. Over the
last decade, the secure and efficient masking of block cipher implementations
against side-channel attacks has been shown to be a difficult task. It is common
practice to analyze the security of masking schemes in the probing model, or its
robust variant which takes into account physical effects such as glitches and
transitions. Such analysis in the (robust) probing model allows to avoid flaws
in the countermeasure that are difficult to detect with other means such as
leakage assessment techniques. In particular, the (robust) probing model allows
to analyze complex computations such as block cipher evaluations or even
asymetric cryptographic operations. Such analyzes are however challenging, since
security in the probing model is not composable: putting probing-secure
components together may break their security. In this talk, I will introduce the
Probe-Isolating Non-Interference (PINI) approach to solve the composition
problem. This approach is versatile and can be used in many contexts, from the
implementation in hardware of block ciphers (where security against glitches and
transitions is required) to implementation of lattice-based key ecapsulation
mechanisms, where masking in multiple fields is required.
Wednesday, November 10th, 2021, 11:00 AM: Pierrick Méaux (University of Luxembourg)
Room MNO 1.030, Belval Campus
Title: Investigating the improved filter permutator paradigm and
connected topics.
Abstract:
In this talk I will present the improved filter permutator (IFP), a
streamcipher paradigm designed for hybrid homomorphic
encryption. After recalling the motivation behind hybrid homomorphic
encryption and IFP, I will introduce the recent outcomes related to
this construction. First, I will talk about the security of IFP,
homomorphic evaluation of Boolean functions and efficiency of
IFP. Then, I will focus on outcomes in the domain of Boolean
functions: determination of the cryptographic parameters of two
homomorphic-friendly families of Boolean functions, fast algebraic
immunity of symmetric functions, and algebraic immunity of direct
sums. Finally, I will get into the connection between IFP and local
pseudorandom generators (PRG), focusing on the recent advances on the
minimal locality of a secure local PRG.
Tuesday, September 15th, 2020, 11:00 AM: François Gérard (ULB, Belgium)
Room MSA 3.220, Belval Campus
Title: Lattice-based cryptography: Implementations and side-channel countermeasures
Abstract: The third round of the NIST post-quantum standardization
project has just started. Now that the candidates have made a more
or less definitive choice of design and parameters, only minor
tweaks to the schemes should appear in the future and it is time to
tackle more practical issues. Performances being mostly critical on
embedded devices, cheap microcontrollers are a common target for
optimized implementations. In the first part of the talk, we will
describe how to implement efficiently some lattice-based schemes and
discuss some optimizations on ARM Cortex-M4. Embedded devices tend
also to be more vulnerable to side-channel attacks. Thus,
implementing countermeasures and assessing side-channel resistance
of the candidates will be of utmost importance for the later phases
of the standardization process. In the second part of the talk, we
will discuss a high order masking scheme for a lattice-based
signature qTESLA that has been ejected after round 2 but has a
design very similar to the round 3 candidate Dilithium.
Tuesday, February 25th, 2020, 10:00 AM: Claire Delaplace (Ruhr University Bochum, Germany)
Room MNO 1.030, Belval Campus
Title: Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions
Abstract: For enabling post-quantum cryptanalytic experiments on a
meaningful scale, there is a strong need for low-memory algorithms.
We show that the combination of techniques from representations,
multiple collisions finding, and the Schroeppel-Shamir algorithm leads
to improved low-memory algorithms.
For random subset sum instances $(a_1, \ldots, a_n,t)$ defined modulo
$2^n$, our algorithms improve over the Dissection technique for small
memory $M < 2^{0.02n}$ and in the mid-memory regime $2^{0.13n} < M < 2^{0.2n}$.
An application of our technique to LPN of dimension $k$ and constant error $p$
yields significant time complexity improvements over the Dissection-BKW algorithm
from Crypto 2018 for all memory parameters $M< 2^{0.35 \frac{k}{\log k}}$.
This is joined work with Andre Esser and Alexander May, published at IMACC 2019.
Thursday, January 9th, 2020, 10:00 AM: Ilaria Chillotti (KU Leuven)
Room MNO 1.030, Belval Campus
Title: Multi-Key Homomophic Encryption from TFHE (joint work with Hao Chen and Yongsoo Song).
Abstract: In this paper, we propose a Multi-Key Homomorphic Encryption (MKHE) scheme by generalizing the low-latency homomorphic encryption by Chillotti et al. (ASIACRYPT 2016). Our scheme can evaluate a binary gate on ciphertexts encrypted under different keys followed by a bootstrapping. The biggest challenge to meeting the goal is to design a multiplication between a bootstrapping key of a single party and a multi-key RLWE ciphertext. We propose two different algorithms for this hybrid product. Our first method improves the ciphertext extension by Mukherjee and Wichs (EUROCRYPT 2016) to provide better performance. The other one is a whole new approach which has advantages in storage, complexity, and noise growth. Compared to previous work, our construction is more efficient in terms of both asymptotic and concrete complexity. The length of ciphertexts and the computational costs of a binary gate grow linearly and quadratically on the number of parties, respectively. We provide experimental results demonstrating the running time of a homomorphic NAND gate with bootstrapping. To the best of our knowledge, this is the first attempt in the literature to implement an MKHE scheme.
Monday, December 2nd, 2019, 14:00: Romain Gay (University of California, Berkeley)
Room MNO 1.030, Belval Campus
Title: Functional Encryption: a bottom up approach
Abstract:
This talk will present recent advances in Functional Encryption, a cryptographic object that allows users to perform selective computation on the encrypted data. Namely, in a Functional Encryption scheme, it is possible to derive a key associated with a function f, which allows users to recover from an encryption of the message m, the value f(m), and nothing else. We will see a series of work that aims at building Functional Encryption from the ground up; that is, practical schemes that rely on mathematically sound assumptions, for restricted classes of functions that we show have interesting applications. We will present the work of [BCFG18], which builds the first public-key Functional Encryption that supports the generation of keys associated with degree-2 polynomials, with succinct ciphertexts. We will show how such schemes can be used to perform private inference, as done in [RDGPP19]. Finally, we will talk about decentralizing Functional Encryption, as done in [CDGPP18].
[BCFG18]: https://eprint.iacr.org/2017/151
[RDGPP19]: https://arxiv.org/abs/1905.10214
[CDGPP18]: https://eprint.iacr.org/2017/989
Thursday, November 21st, 2019, 10:00 AM: Changmin Lee (ENS Lyon)
Room MNO 1.030, Belval Campus
Title: Cryptanalysis of FRS Obfuscation based on the CLT13 Multilinear Map
Abstract:
We present classical polynomial-time attacks against the FRS branching program obfuscator of Fernando-Rasmussen-Sahai (Asiacrypt 17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators, when instantiated with the CLT13 multilinear map.
To do that
1) We (heuristically) reproduce a new zerotest parameter from the original one and recover a secret message space. The new zerotest parameter mitigates parameter constraints of the message space recovering algorithm proposed by Coron and Notarnicola (Asiacrypt'19), so it enables us to directly apply the algorithm to the FRS obfuscation.
2) We propose two cryptanalyses of the FRS obfuscation based on the recovered message space. One analysis enables to obtain all secret elements of CLT13, but it requires extra parameter constraints. On the other hand, the other analysis shows that there exist two functionally equivalent programs such that their obfuscated programs are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints.
Monday, November 11th, 2019, 10:00 AM: Benjamin Wesolowski (CWI)
Room MNO 1.030, Belval Campus
Title: Discrete logarithms in quasi-polynomial time in finite fields of small characteristic
Abstract: We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. In 1987, Pomerance proved that this problem can be solve in expected subexponential time L(1/2). The following 30 years saw a number of heuristic improvements, but no provable results. The quasi-polynomial complexity has been conjectured to be reachable since 2013, when a first heuristic algorithm was proposed by Barbulescu, Gaudry, Joux, and Thome. We prove this conjecture, and more generally that this problem can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2 log_2(n)+O(1)}$.
Friday, May 11th, 2018, 10:30 AM: Claire Delaplace (University of Rennes, France)
Room MNO-E03-25-110, Belval Campus.
Title: Revisiting and Improving Algorithms for the 3XOR Problem
Abstract: The 3SUM problem is a well-known problem in computer science and many geometric
problems have been reduced to it. We study the 3XOR variant which is more cryptologically
relevant. In this problem, the attacker is given black-box access to three random functions
$F$, $G$ and $H$ and she has to find three inputs $x$, $y$ and $z$ such that
$F(x) \oplus G(y) \oplus H(z) = 0$. The 3XOR problem is a difficult case of the more-general
k-list birthday problem.
Wagner's celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the
functions more than strictly necessary from an information-theoretic point of view. This gives
some leeway to target a solution of a specific form, at the expense of processing a huge amount
of data. However, to handle such a huge amount of data can be very difficult in practice. This is
why we first restricted our attention to solving the 3XOR problem for which the total number of queries
to $F$, $G$ and $H$ is minimal. If they are $n$-bit random functions, it is possible to solve the problem
with roughly $O(2^{n/3})$ queries. In this setting, the folklore quadratic algorithm finds a solution after
$O(2^{2n/3})$ operations.
We present a 3XOR algorithm that generalizes an idea of Joux, with complexity $O(2^{2n/3} / n)$ in
time and $O(2^{n/3})$ in space. This algorithm is practical: it is up to 3 times faster than the quadratic
algorithm. Furthermore, we show that it is possible to adapt this algorithm to any number of queries, so
that it will always be at least as good as, if not better than, Wagner's descendants in the same settings.
We also revisit a 3SUM algorithm by Baran-Demaine-Patrascu which is asymptotically $n^2 / \log^2 n$
times faster than the quadratic algorithm when adapted to the 3XOR problem, but is otherwise completely
impractical.
This is a joint work with Pierre-Alain Fouque and Charles Bouillaguet.
April 13th, 2018, 11:00 AM: Benoit Cogliati
Room MNO-E03-25-110, Belval Campus
TItle: Provable security in symmetric cryptography
Abstract: Provable security is an essential part of both symmetric and public-key cryptography. Indeed, security proofs can increase confidence in the resistance of an algorithm against various types of attacks and justify its soundness. Moreover, theorems guide the choice of the security parameters in applications. In this context, tight security proofs are essential, since they prevent the use of unnecessarily high values for those parameters. In this talk, I will start by giving an overview of the indistinguishability notion and of the main theoretical models that are considered in symmetric cryptography. I will then illustrate these notions by presenting several results on the design of tweakable block ciphers, and on the construction of provably secure MACs based on block ciphers and tweakable block ciphers.
November 22nd, 2017, 10:30 AM: Tancrede Lepoint
Room MNO-E03-25-110, Belval Campus
Title: Post-Quantum Cryptography using Module Lattices
Abstract:
Recent advances in quantum computing and the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols, spurred on the design and analysis of many post-quantum cryptographic schemes. One of the most efficient quantum-resilient alternatives for the above basic primitives is that of lattice cryptography.
Many lattice cryptography schemes are based on the learning-with-error problem over a ring. Past works have described digital signature schemes, encryption schemes, and key encapsulation mechanisms in one of two ways. Either they set the ring as Z_q[x]/(x^n+1) or as Z_q^n. The former choice results in schemes based on the hardness of the Ring-LWE and Ring-SIS problems (or the NTRU problem), while the latter choice of parameters results in schemes based on the LWE and SIS problems. In this talk, we consider the general case of setting the ring to (Z_q[x]/(x^d+1))^m, and design schemes based on the Module-LWE and Module-SIS hardness assumption. First, we explain how module lattices enable to design cryptographic primitives that are not only simple to implement securely, conservatively designed, and have a small memory footprint, but are modular, i.e., easily enable to vary security while keeping the same core operations. Then, we present CRYSTALS, the Cryptographic Suite for Algebraic Lattices submitted to the NIST call for post-quantum standards, that includes Kyber (Bos et al., 2017), a key encapsulation mechanism, and Dilithium (Ducas et al., 2017), a digital signature.
LACS Crypto Day, June 13th, 2017, room MSA 4.410, Belval campus
-
10:00: Aleksei Udovenko. On division property cryptanalysis.
-
10:30: Dmitry Khovratovich. BIP32-Ed25519: Hierarchical Deterministic Keys over a Non-linear Keyspace.
-
11:00: Benoit Cogliati: Security proofs for symmetric-key constructions
-
11:30: Jun Wang. vdNets: Applying Very Deep Neural Networks to Encrypted Data
Abstract: Very deep neural networks have recently demonstrated start-of-the-art accuracy on very complex visual and speech recognition tasks. To those problems which involve sensitive data, e.g. medicine and finance, the privacy and security requirements may prevent the use of cloud-based machine learning service. To address this issue, a number of works have explored how to apply machine learning models, including neural networks, to encrypted data. Unfortunately, such works either focus on conventional machine learning models or shallow neural networks. In this paper, we describe the design and implementation of a secure multiparty computation (SMC) system called vdNets which allows performing a learned very deep and large neural network on encrypted data. We first demonstrate the ability of vdNets by applying GoogLeNet convolutional neural network \cite{szegedy2015going} to encrypted data, and analyze its computation and communication cost. GoogLeNet has 22 layers (approximately 100 independent sub-layers) and overall 1.5 billion multiply-adds at inference time. We further discuss the bottleneck of vdNets and introduce different methods to eliminate or alleviate it. Our results provide compelling evidence that an SMC approach to very deep and large neural networks is worth pursuing.
-
14:00:
Moon Sung Lee. Attacks on Multilinear Maps
-
14:30: Vincenzo Iovino. The Simplest Oblivious Transfer Protocol.
-
15:00: Alfredo Rial Duran. UC Commitments for Modular Protocol Design and Applications to Revocation and Attribute Tokens
Abstract: Complex cryptographic protocols are often designed from simple cryptographic primitives, such as signature schemes, encryption schemes, verifiable random functions, and zero-knowledge proofs, by bridging between them with commitments to some of their inputs and outputs. Unfortunately, the known universally composable (UC) functionalities for commitments and the cryptographic primitives mentioned above do not allow such constructions of higher-level protocols as hybrid protocols. Therefore, protocol designers typically resort to primitives with property-based definitions, often resulting in complex monolithic security proofs that are prone to mistakes and hard to verify.
We address this gap by presenting a UC functionality for non-interactive commitments that enables modular constructions of complex protocols within the UC framework. We also show how the new functionality can be used to construct hybrid protocols that combine different UC functionalities and use commitments to ensure that the same inputs are provided to different functionalities.
We further provide UC functionalities for attribute tokens and revocation that can be used as building blocks together with our UC commitments. As an example of building a complex system from these new UC building blocks, we provide a construction (a hybrid protocol) of anonymous attribute tokens with revocation. Unlike existing accumulator-based schemes, our scheme allows one to accumulate several revocation lists into a single commitment value and to hide the revocation status of a user from other users and verifiers.
Co-authors: Jan Camenisch, Maria Dubovitskaya.