seminar (2023-2024)

Friday, Jul 12, 2024 - 10:30 - 25-26/105

Workshop ALMASTY

Présentation des travaux de l'équipe

• Ahmed Alharbi, - Wishful thinking in cryptanalysis
• Samuel Bouaziz--Ermann - Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way
• Andersson Calle Viera - lmplementations of Post-Quantum Cryptography, Algorithms Secured against Physical Attacks
• Alex B. Grilo - Quantum Protocols for MPC under Weaker Assumptions
• Jules Maire - Zero-Knowledge Proofs for the Permuted Kernel Problem
• David Pulido Cornejo - Reconstruction de clés AES
• Julia Sauvage - Collisions on Multivariate Polynomial Systems

Friday, Jul 5, 2024 - 10:00 - 25-26/105

Séminaire C2

Site du séminaire

• Martino Borello - The geometry of linear codes and some recent applications
• Antonin Leroux - SQIsign2D-West The Fast, the Small, and the Safer
• Cécile Pierrot - Y a-t-il encore, au XXI° siècle, de vieux documents historiques à déchiffrer ?
• Jules Baudrin - Geometrical structures among known APN functions

Friday, Jun 21, 2024 - 10:30 - 24-25/405

Vanessa Vitse

Résolution de systèmes booléens

(ALMASTY Seminar)

Friday, Jun 14, 2024 - 10:30 - 24-25/405

Xunyue Hu

Blind-Folded: Simple Power Analysis Attacks using Data with a Single Trace and no Training

(ALMASTY Seminar)

Friday, May 24, 2024 - 10:30 - 24-25/405

Pierre Briaud

Practical Attack on All Parameters of the DME Signature Scheme

(ALMASTY Seminar)

DME is a multivariate scheme submitted to the call for additional signatures recently launched by NIST. Its performance is one of the best among all the candidates. The public key is constructed from the alternation of very structured linear and non-linear components that constitute the private key, the latter being defined over an extension field. We exploit these structures by proposing an algebraic attack which is practical on all DME parameters.

Travail en commun avec Maxime Bros, Ray Perlner et Daniel Smith-Tone.

Friday, May 3, 2024 - 10:30 - 24-25/405

Rachelle Heim Boissier

Generic attacks based on functional graphs

(ALMASTY Seminar)

The purpose of this talk is to introduce generic attacks based on functional graphs. Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which is based on exceptional random functions, i.e., functions whose graph admits a large component with an exceptionally small cycle. This attack has since then been improved by Bonnetain et al. (eprint 2024) using so-called nested exceptional functions. They also improved several attacks against hash combiners using exceptional random functions.

Tuesday, Apr 9, 2024 - 10:00 - ENS, Salle W (!!)

Amir Herzberg

Provable Security for PKI Schemes - and the (Composable) Modular Security Specifications Framework

(Parisian Cryptography Seminar)

PKI schemes provide a critical foundation for applied cryptographic protocols. However, there are no rigorous security specifications for realistic PKI schemes, and therefore, no PKI schemes were proven secure. Cryptographic systems that use PKI are analyzed by adopting overly simplified models of the PKI, often, simply assuming secure public keys. This is problematic considering the extensive reliance on PKI, the multiple failures of PKI systems, and the fact that proposed and deployed PKI are complex, have complex requirements and assume complex models.

We present game-based security specifications for PKI schemes, and analyse important, widely deployed PKIs: PKIX and two variants of Certificate Transparency (CT). All PKIs are based on the X.509v3 standard and its CRL revocation mechanism. Our analysis identified few subtle vulnerabilities, and includes reduction-based proofs showing that the PKIs ensure specific requirements under specific models (assumptions).To our knowledge, this is the first reduction-based definition and proof of security for a realistic PKI scheme.

Our specifications and analysis use the Modular Security Specifications (MoSS) framework [Crypto’21]. The talk will explain the relevant aspects of MoSS. We may briefly discuss the extensions that allow provably- secure compositions of protocols.

Joint work with Sara Wrotniak, Hemi Leibowitz and Ewa Syta.

Friday, Mar 29, 2024 - 10:30 - 24-25/405

Julia Sauvage

Preliminary Cryptanalysis of the Biscuit Signature Scheme

(ALMASTY Seminar)

Friday, Mar 22, 2024 - 10:30 - 24-25/405

Malika Izabachène

Plug-and-play sanitization for TFHE

(ALMASTY Seminar)

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, Mar 15, 2024 - 10:30 - 24-25/405

Aurélien Boeuf

Propagation of Subspaces in Primitives with Monomial Sboxes: Applications to Rescue and Variants of the AES

(ALMASTY Seminar)

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.

Monday, Mar 4, 2024 - 09:00 - ENS, Salle Cavaillès (!!)

Evgenios Kornaropoulos

Breach Extraction Attacks

(Parisian Cryptography Seminar)

Credential tweaking attacks use breached passwords to generate semantically similar passwords and gain access to victims’ services. These attacks sidestep the first generation of compromised credential checking (C3) services. The second generation of compromised credential checking services, called “Might I Get Pwned” (MIGP), is a privacy- preserving protocol that defends against credential tweaking attacks by allowing clients to query whether a password or a semantically similar variation is present in the server’s compromised credentials dataset. The desired privacy requirements include not revealing the user’s entered password to the server and ensuring that no compromised credentials are disclosed to the client.

In this work, we formalize the cryptographic leakage of the MIGP protocol and perform a security analysis to assess its impact on the credentials held by the server. We focus on how this leakage aids breach extraction attacks, where an honest-but-curious client interacts with the server to extract information about the stored credentials. Furthermore, we discover additional leakage that arises from the implementation of Cloudflare’s deployment of MIGP. We evaluate how the discovered leakage affects the guessing capability of an attacker in relation to breach extraction attacks. Finally, we propose MIGP 2.0, a new iteration of the MIGP protocol designed to minimize data leakage and prevent the introduced attacks.

Joint work with Dario Pasquini (EPFL), Danilo Francati (Aarhus University), Giuseppe Ateniese (George Mason University), to appear at S&P 2024.

Friday, Mar 1, 2024 - 10:00 - 15-16/101

Journées Numération, Arithmétique, Cryptographie

Site de l'événement

Thursday, Feb 29, 2024 - 10:00 - 15-16/101

Journées Numération, Arithmétique, Cryptographie

Site de l'événement

Friday, Feb 9, 2024 - 10:30 - 24-25/405

Sorina Ionica

Cryptanalyse algébrique en caractéristique 2: Gröbner versus SAT

(ALMASTY Seminar)

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

Camille Mutschler

Inspector Gadget - A Toolbox for Fair Comparison of Masking Gadgets Application to Crystals-Kyber Compression

(ALMASTY Seminar)

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

Pierre Pébereau

Key recovery from one vector in UOV schemes

(ALMASTY Seminar)

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

Clémence Bouvier

New tools for designing and analysing MPC/FHE/ZK-friendly primitives

(ALMASTY Seminar)

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

Aurore Guillevic

Pairing-friendly elliptic curves, design, implementation, and discrete logarithm computations

(ALMASTY Seminar)

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

Clément Ducros

Pseudorandom Correlation Functions from Variable-Density LPN, Revisited

(ALMASTY Seminar)

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

Maxime Bombar

Pseudorandom Correlation Generators from the Quasi-Abelian Decoding Problem

(ALMASTY Seminar)

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

Michele Orrù

Beyond the circuit: How to Minimize Foreign Arithmetic in ZKP Circuits

(ALMASTY Seminar)

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 (!!)

Greg Zaverucha

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.