This page gives the program of the ALMASTY seminar and the joint Parisian cryptography seminar (currently organized by the CASCADE team).
Thursday, Feb 29, 2024 - 10:00 - 15-16/101
Journées Numération, Arithmétique, Cryptographie
Friday, Mar 1, 2024 - 10:00 - 15-16/101
Journées Numération, Arithmétique, Cryptographie
Friday, Mar 15, 2024 - 10:30 - 24-25/405
Propagation of Subspaces in Primitives with Monomial Sboxes: Applications to Rescue and Variants of the AES
Motivated by progress in the field of zero-knowledge proofs, Arithmetization-Oriented (AO) symmetric primitives such as MiMC, Poseidon or Rescue are defined using simple operations over large fields. Many rely on simple low-degree monomials for their non-linear layers, essentially using x -> x^3 as an S-box. In this talk, we show that the structure of the material injected in each round could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet. Well-known security arguments have been reused in the AO setting by many designers. Our results show that such a traditional study may not be sufficient to guarantee security. To illustrate this, we present new primitives that are built using state-of-the-art security arguments, but which are actually deeply flawed.
Friday, Mar 22, 2024 - 10:30 - 24-25/405
Plug-and-play sanitization for TFHE
Fully Homomorphic Encryption allows evaluating an arbitrary function over encrypted data while preserving the privacy of the messages. This property has found numerous applications especially in the case where one would like to process data stored in the cloud in a private way. In this talk, we will focus on the privacy of the algorithm processed by the cloud. Fully Homomorphic Encryption sanitation guarantees that, all the information about how a ciphertext has been obtained is destroyed, except the associated message. In particular, it is impossible to say which computation has been processed in order to obtain a given ciphertext, even knowing the secret key. We will see how to build a sanitization algorithm from the TFHE bootstrapping (Asiacrypt 2016) and how it compares to the previous soak-and-spin strategy from Ducas and Stehlé (Eurocrypt 2016).
This is joint work with Florian Bourse.
Friday, Apr 5, 2024 - 11:30 - 24-25/405
Friday, Jun 7, 2024 - 10:30 - 24-25/405
River Moreira Ferreira
Polynomial-Time Key-Recovery Attack on the NIST Specification of PROV
Friday, Jun 21, 2024 - 10:30 - 24-25/405
Past talks (2022-2023)
Friday, Feb 9, 2024 - 10:30 - 24-25/405
Cryptanalyse algébrique en caractéristique 2: Gröbner versus SAT
En cryptanalyse algébrique, la résolution des systèmes polynomiaux définis sur un corps fini se fait en utilisant un algorithme de calcul de bases de Gröbner comme F4 ou F5. Cependant, lorsqu’on cherche des solutions dans F_2, l’expérimentation montre que la recherche exhaustive, ou encore les méthodes hybrides combinant la recherche exhaustive et les bases de Gröbner donnent des meilleurs résultats. Dans cet exposé, je montrerai une autre approche, dite logique, qui repose sur la résolution d’une formule booléenne par un solveur SAT. J’expliquerai le fonctionnement des moteurs de résolution SAT et en particulier d’un solveur dédié à la résolution de systèmes polynomiaux que nous avons proposé. Je démontrerai une similarité entre les deux approches, algébrique et logique, qui peut être exploitée davantage pour améliorer la résolution. Cet exposé repose sur des travaux joints avec Gilles Dequen et Monika Trimoska.
Friday, Jan 26, 2024 - 10:30 - 24-25/405
Inspector Gadget - A Toolbox for Fair Comparison of Masking Gadgets Application to Crystals-Kyber Compression
In this talk, I will introduce InspectorGadget, an Open-Source Python-based software for assessing and comparing the complexity of masking gadgets. By providing a limited set of characteristics of a hardware platform, our tool allows to estimate the cost of a masking gadget in terms of cycle count equivalent and memory footprint. InspectorGadget is highly flexible. It enables the user to define her own estimation functions, as well as to expand the set of gadgets and predefined microcontrollers. As a case-study, we produce a fair comparison of several masked versions of Kyber compression function from the literature, together with novel alternatives automatically generated by our tool. Our results confirm that an interesting middle ground exists between theoretical performance measures (asymptotic complexity or operations count) and real implementations benchmarks (clock cycle accurate evaluations). InspectorGadget offers both simplicity and genericity while capturing the main performance-related parameters of a hardware platform.
Friday, Jan 19, 2024 - 10:30 - 24-25/405
Key recovery from one vector in UOV schemes
After an introduction on multivariate cryptography and algebraic cryptanalysis, we will present a contribution to the cryptanalysis of UOV.
More precisely, UOV is a trapdoor scheme relying on a secret subspace called the “oil subspace”. We will show how to recover a secret key from the knowledge of one single vector in the oil subspace. In other terms, we show that breaking UOV is as hard as finding one such vector because we recover the whole trapdoor in polynomial-time once a vector is known. This attack is also practical: given a secret vector, our implementation recovers the secret key of UOV in at most 15 seconds for NIST security level V.
We will also consider the question of extending this result to schemes related to UOV, in particular MAYO and VOX.
Friday, Dec 22, 2023 - 10:30 - 24-25/405
New tools for designing and analysing MPC/FHE/ZK-friendly primitives
Recently, new symmetric primitives have been proposed for advanced protocols such as multi-party computation, in combination with fully homomorphic encryption, or in various zero-knowledge proof systems. These protocols have put forward the need to minimize the number of multiplications performed by the primitive in large finite fields. Classical symmetric algorithms are then inappropriate in this context, and these protocols have to be combined with symmetric primitives with particular properties. While the number of such primitives has increased significantly, only a few cryptanalysis works have been proposed.
In this talk, we will present new tools for both design and cryptanalysis. First, we will propose a security analysis of the MiMC block cipher, one of the first primitives proposed in this new context, giving a detailed understanding of the evolution of the algebraic degree of this cipher. We will also discuss the algebraic degree of Chaghri, a FHE-friendly cipher. Finally, we will move on to the designer’s side to introduce a new vision for the design of such primitives, exploiting a previously unknown link with the CCZ-equivalence.
Friday, Dec 15, 2023 - 10:30 - 24-25/405
Pairing-friendly elliptic curves, design, implementation, and discrete logarithm computations
Design and implementation of pairing-friendly curves knew a growing activity from 2000 to roughly 2014. Bilinear pairings are a building block for many cryptosystems, for example broadcast encryption, zero-knowledge proofs. Pairing-friendly curves have an inherent weakness due to the MOV attack that transfers the discrete logarithm problem from the curve to an embedding finite field GF(q). Serious attacks against the discrete logarithm problem in extension fields GF(2^n), GF(3^m) and GF(p^k) were developed from 2012, with as major milestones the quasi-polynomial time algorithm in small characteristic and so-called zig-zag descent, that made pairings in characteristic 2 and 3 obsolete. In medium-sized extensions such as GF(p12), variants of the TNFS algorithm are the most promising (Tower Number Field Sieve algorithm).
New specific needs of pairing-friendly elliptic curves emerged with the development of SNARK (succinct non-interactive argument of knowledge). The interest in finding prime-order pairing-friendly curves, developing efficient pairing computations, and also estimating precisely the complexity of TNFS in extension fields, was reactivated.
I will present two aspects: the development of a simulator for the TNFS algorithm to estimate the security of pairing-friendly curves, available at https://gitlab.inria.fr/tnfs-alpha/alpha and the development (in progress) of a Python/SageMath library of pairings, a preliminary version being at https://gitlab.inria.fr/zk-curves/snark-2-chains These are joint work with Youssef El Housni, Georgios Fotiadis, Diego Aranha.
Friday, Dec 8, 2023 - 10:30 - 24-25/405
Pseudorandom Correlation Functions from Variable-Density LPN, Revisited
Multi Party Computation (MPC) is a very active area of research in cryptography that allows players to compute a function together without sharing their private data. The generation of secret correlated pseudo-random strings is very useful in the various MPC protocols. Pseudo-random correlation functions (PCFs), introduced by Boyle et al in FOCS2020, are a very powerful MPC primitive that allows two parties to generate locally, from short correlated keys, an almost unlimited amount of pseudo-random samples from a target correlation. A candidate for PCF has been introduced by Boyle et al, based on a new Variable Density variant of the Learning Parity with Noise assumption. In the presentation, I will explain the initial construction, and then the various improvements that I have carried out in a work at PKC 2023.
Friday, Nov 24, 2023 - 10:30 - 24-25/405
Pseudorandom Correlation Generators from the Quasi-Abelian Decoding Problem
Secure multiparty computation often benefits from using correlated randomness to achieve better efficiency. Recently, Boyle et al. showed how Pseudorandom Correlation Generators (PCG’s) can be used to generate and distribute a large amount of useful correlated (pseudo)randomness such as random Oblivious Linear Evaluations (OLE’s) to two parties, using minimal interactions, followed solely by local computations. This enables secure two-party computation with silent preprocessing, which can be extended to N-party using so-called programmable PCG’s.
Previous constructions of programmable PCG’s for OLE’s suffer from two downsides: (1) They only generate OLE’s over large fields, and (2) They rely on a rather recent splittable Ring-LPN assumption which lacks from strong security foundations.
In this talk, I will introduce the Quasi-Abelian Syndrome Decoding problem, which generalises the well-known Quasi-Cyclic Decoding Problem, and show how its hardness allows to build programmable PCG’s for the OLE correlation over any field Fq (with q>2). This instantiation resists all attacks from the linear test framework (which encompasses essentially all known generic attacks against variants of the Decoding Problem), and admits a search-to-decision reduction. As a by-product, this work permits to identify weak instantiations which were allowed in previous constructions.
This is based on a joint work with Geoffroy Couteau, Alain Couvreur and Clément Ducros.
Friday, Nov 17, 2023 - 10:30 - 15-16/411
Beyond the circuit: How to Minimize Foreign Arithmetic in ZKP Circuits
Zero-knowledge circuits are frequently required to prove gadgets that are not optimised for the constraint system in question. A particularly daunting task is to embed foreign arithmetic such as boolean operations, field arithmetic, or public-key cryptography.
We construct techniques for offloading foreign arithmetic from a zero-knowledge circuit including
(i) equality of discrete logarithms across different groups;
(ii) scalar multiplication without requiring elliptic curve addition;
(iii) proving knowledge of an AES encryption.
To achieve our goal, we employ techniques inherited from rejection sampling and lookup protocols. We implement and provide concrete benchmarks for our protocols. In particular, proving an AES preimage is comparable with state-of-the-art MPCitH techniques.
Tuesday, Nov 7, 2023 - 10:00 - 25-26/105
Abdul Rahman Taleb
Secure and Verified Cryptographic Implementations in the Random Probing Model
The masking countermeasure is among the most potent countermeasures to counteract side-channel attacks. Leakage models have been exhibited to theoretically reason on the security of such masked implementations. So far, the most widely used leakage model is the probing model, but it has been recently challenged as it does not fully capture the capabilities of a side-channel adversary. To capture a broader class of attacks, another model was introduced, referred to as the random probing model. From a leakage parameter p, each wire of the circuit leaks its value with probability p. The random probing model enjoys practical relevance thanks to a reduction to the noisy leakage model, which is admitted as the suitable formalization for power and electromagnetic side-channel attacks. In addition, the random probing model is much more convenient than the noisy leakage model to prove the security of masking schemes.
In this thesis, we study more closely the random probing model and define the first framework dedicated to it. We formalize a composition property for secure random probing gadgets and exhibit its relation to the strong non-interference (SNI) notion used in probing security. We then revisit the expansion idea proposed by Ananth, Ishai, and Sahai (CRYPTO 2018) and introduce a compiler that builds a random probing secure circuit from small base gadgets, achieving a random probing expandability (RPE) property. We then provide an in-depth analysis of the RPE security notion, allowing us to obtain much more efficient instantiations of the expansion technique, with constructions tolerating a leakage probability of up to 2-7, against 2-26$ for the previous construction and an improved complexity of O(κ3.2) against O(κ7.87) for the previous constructions, where κ is the security parameter. We also show that our constructions achieve a quadratic complexity in κ asymptotically as the number of shares grows. Further attempts to optimize constructions include generalizing the RPE approach by considering a dynamic choice of the base gadgets at each step in the expansion. We show that such techniques can further reduce the complexity from quadratic to quasi-linear while tolerating good leakage rates.
Finally, we introduce IronMask, a new versatile verification tool for masking security. IronMask is the first to verify standard simulation-based security notions in the probing model and recent notions in the random probing model. It supports any masking gadgets with linear randomness (e.g., addition, copy, and refresh gadgets) as well as quadratic gadgets (e.g., multiplication gadgets) that might include non-linear randomness (e.g., by refreshing their inputs) while providing complete verification results for both types of gadgets.
We conclude this thesis by discussing ongoing research projects in the random probing model and suggestions for future works.
Tuesday, Oct 24, 2023 - 11:00 - ENS, Salle Histoire (!!)
Verifiable Encryption from MPC-in-the-Head
(Parisian Cryptography Seminar)
Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations.
In this work, we propose a novel framework that realizes VE protocols using zero-knowledge proof systems based on the MPC-in-the-head paradigm (Ishai et al. STOC 2007). Our generic compiler can turn a large class of zero-knowledge proofs into secure VE protocols for any secure public-key encryption scheme with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme.
Our framework is versatile: because the circuit proven by the MPC-in-the-head prover is decoupled from a complex encryption function, the work of the prover is focused on proving the encrypted data satisfies the relation, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about the encrypted data and encryption functions. We then consider concrete applications, to demonstrate the efficiency of our framework, by first giving a new approach and implementation to verifiably encrypt discrete logarithms in any prime order group more efficiently than was previously known. Then we give the first practical verifiable encryption scheme for AES keys with post-quantum security, along with an implementation and benchmarks.
This is joint work with Akira Takahashi.