seminar (2024-2025)

{{ item.date | date: "%A, %b %-d, %Y" }} - {{ item.date | date: " %R" }} {% if item.room %} - {{ item.room }} {% endif %}

{{ item.name }}

{{ item.title }}

{% if item.seminar %} {% if item.seminar=='almasty' %}

(ALMASTY Seminar)

{% endif %} {% if item.seminar=='parisian' %}

(Parisian Cryptography Seminar)

{% endif %} {% if item.seminar=='hdr' %}

(Soutenance HDR)

{% endif %} {% endif %}

{{ item.content }}

Monday, May 19, 2025 - 10:30 - 24-25/509

Guirec Lebrun

A Tale of Trees: Improving the Efficiency of Secure Group Messaging Protocols

(ALMASTY Seminar)

While Secure Messaging protocols, used by widely known applications like WhatsApp and Signal, have reached a certain amount of maturity in terms of security and efficiency, their transposition to the group setting (with over tens of thousands of users) is still a new research topic. The IETF has released in July 2024 a new standard of Secure Group Messaging protocol called Messaging Layer Security (MLS), which is considered as the state-of-the-art in that field. The core subprotocol of MLS is a group key exchange mechanism named TreeKEM, which relies on a binary tree in order to carry out a handshake with a communication cost logarithmic in the number of users. However, that bandwidth highly depends on the tree structure, which is itself influenced by the group history. Therefore, the aimed logarithmic cost appears to be a lower bound that is rarely reached in practice.

In that context, I present you two works that aim to reduce the communication cost of a Secure Group Messaging protocol. Firstly, we have analyzed the impact of the tree structure of TreeKEM on its communication cost, and the way to keep that tree as close as possible to the optimal balance. Then, in order to further increase the efficiency of our protocol, we have designed a novel protocol architecture that offers significantly enhanced communication and storage performances compared to TreeKEM, using the fact that some group members are administrators with the ability to perform operations on the member group.

Tuesday, Apr 22, 2025 - 09:30 - Roscoff, Station biologique

WRACH 2025

Workshop on Randomness and Arithmetics for Cryptographic Hardware

Webpage

Friday, Apr 11, 2025 - 10:30 - 25-26/105

Andersson Calle Viera

Implantations d'algorithmes de cryptographie post-quantique sécurisées contre les attaques physiques

Cette thèse étudie les défis liés à la mise en œuvre d’une version sécurisée et optimisée du schéma de signature Dilithium sur des dispositifs embarqués, en se concentrant sur les attaques par canaux auxiliaires et les attaques par fautes. La thèse contribue au domaine plus large de la cryptographie post-quantique en explorant les vulnérabilités pratiques et les contre-mesures dans les déploiements du monde réel. La première contribution concerne l’optimisation de l’algorithme de signature de Dilithium. L’étude compare les implémentations basées sur les polynômes et celles basées sur les vecteurs (de polynômes), démontrant qu’un choix judicieux des structures de données et des calculs peut conduire à des économies de mémoire significatives sans surcoût substantiel en termes de performances. Cette optimisation est cruciale pour les appareils embarqués, où la mémoire est souvent la ressource la plus limitée. La thèse se concentre également sur les attaques par canaux auxiliares et par fautes contre Dilithium. En ce qui concerne les attaques par canaux auxiliaires, les travaux ont permis d’identifier une fuite de valeur intermédiaire exploitable par des attaques profilées, permettant la récupération robuste de la clé secrète avec un minimum de 200 000 signatures. En ce qui concerne les attaques par fautes, la thèse a permit d’identifier plusieurs endroits pertinents à la fois dans l’algorithme de signature, permettant la récupération de la clé secrète, et dans les algorithmes de vérification, permettant l’acceptation de signatures incorrectes. La thèse contribue finalement à comprendre comment équilibrer la sécurité et l’efficacité dans les implémentations cryptographiques post-quantiques.

Monday, Mar 31, 2025 - 09:00 - Village vacances VVF, Blériot-Plage

Journées C2

Journées Codage et Cryptographie 2026

Webpage

Monday, Mar 31, 2025 - 09:00 - Village vacances Azureva, La Baule, Pornichet.

Journées C2

Journées Codage et Cryptographie 2025

Webpage

Friday, Mar 21, 2025 - 10:30 - 26-00/534

Guilhem Niot

Short Shares, Small Coefficients: A New Secret Sharing Scheme and its Applications to Lattice-based Threshold Cryptography

(ALMASTY Seminar)

Secret sharing schemes are fundamental cryptographic primitives with applications in secure multi-party computation and threshold cryptography. This talk introduces a secret sharing scheme tailored for lattice-based schemes that offers both short shares and small reconstruction coefficients. While its support is limited to small numbers of parties, we demonstrate the versatility of this scheme by applying it to two significant use cases:

1. Threshold Raccoon with Identifiable Aborts: We enhance the security of Threshold Raccoon by incorporating our secret sharing scheme to enable the identification of malicious parties that induce aborts. Our short sharing provides both a very natural and efficient construction.
2. Compact Threshold Signature Scheme: We construct a highly efficient threshold signature scheme based on the Fiat-Shamir with Aborts paradigm, leveraging our secret sharing scheme along with new simulation results to minimize the size of signatures.

Friday, Mar 14, 2025 - 10:30 - 24-25/405

Dhekra Mahmoud et Abdul Rahman Taleb

A Tale of Two Worlds, a Story of WireGuard Hybridization

(ALMASTY Seminar)

PQ-WireGuard, published in 2021 IEEE Symposium on Security and Privacy, is a post-quantum variant of WireGuard VPN, where ECDH-based key exchange is replaced by KEM-based key exchange instantiated with dedicated post-quantum constructions. During our talk, we will present our new work, where we improve PQ-WireGuard by pointing out and fixing vulnerabilities thanks to formal verifications tools. Moreover, we propose a new protocol, named Hybrid-WireGuard, in-line with current best practices for post-quantum transition about hybridization techniques. Using SAPIC+ and the automatic cryptographic protocol verifiers PROVERIF, DEEPSEC and TAMARIN, we prove that our construction is secure in the symbolic model. Furthermore, we show that Hybrid-WireGuard security is a conjunction of WireGuard security and PQ-WireGuard security. We propose an efficient Rust implementation of our new protocol and show that its performance ensures its usability.

Friday, Mar 7, 2025 - 10:30 - 24-25/405

Dung Bui

FOLEAGE: F4OLE-Based Multi-Party Computation for Boolean Circuits

(ALMASTY Seminar)

Secure Multi-party Computation (MPC) allows two or more parties to compute any public function over their privately-held inputs, without revealing any information beyond the result of the computation. Modern protocols for MPC generate a large amount of input-independent preprocessing material called multiplication triples, in an offline phase. This preprocessing can later be used by the parties to efficiently instantiate an input-dependent online phase computing the function.

To date, the state-of-the-art secure multi-party computation protocols in the preprocessing model are tailored to secure computation of arithmetic circuits over large fields and require little communication in the preprocessing phase, typically O(N · m) to generate m triples among N parties. In contrast, when it comes to computing preprocessing for computations that are naturally represented as Boolean circuits, the state-of-the-art techniques have not evolved since the 1980s, and in particular, require every pair of parties to execute a large number of oblivious transfers before interacting to convert them to N-party triples, which induces an Ω(N^2 · m) communication overhead.

In this paper, we introduce FOLEAGE, which addresses this gap by introducing an efficient preprocessing protocol tailored to Boolean circuits. FOLEAGE exhibits excellent performance: It generates m multiplication triples over F2 using only N · m + O(N^2 · log m) bits of communication for N-parties, and can concretely produce over 12 million triples per second in the 2-party setting on one core of a commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator (PCG) for multiplication triples over the field F4. Roughly speaking, a PCG enables parties to stretch a short seed into a large number of pseudorandom correlations non-interactively, which greatly improves the efficiency of the offline phase in MPC protocols. Our construction significantly outperforms the state-of-the-art, which we demonstrate via a prototype implementation. This is achieved by introducing a number of protocol-level, algorithmic-level, and implementation-level optimizations on the recent PCG construction of Bombar et al. (Crypto 2023) from the Quasi-Abelian Syndrome Decoding assumption.

Friday, Feb 14, 2025 - 10:00 - 24-25/405

Augustin Bariant

Polynomial-solving Attacks against Arithmetization-Oriented Primitives

(ALMASTY Seminar)

Recent advanced protocols for zero-knowledge, multi-party computation or fast homomorphic encryption have been the subject of active research in the last decade. Many such protocols rely on symmetric cryptography primitives which are evaluated inside the protocol. The cost of these primitives depends on the operations allowed in the protocol, and these operations are often large finite field operations (+, x) . Traditional symmetric primitives such as the AES are very costly when converted into these operations, therefore dedicated primitives have been proposed; they are called Arithmetization-Oriented (AO) primitives. AO primitives tend to minimize the number of multiplication in such protocols to lower their cost, and their security is mainly evaluated with algebraic cryptanalysis. In this talk, I give an introduction to polynomial-solving attacks, a special type of algebraic attack against AO primitives. I first recall the algebraic concepts involved in the attacks, and then show the principle of polynomial-solving attacks based on Groebner bases, with application to existing AO primitives. Finally, I will go over two recent threatening polynomial-solving attacks that do not follow the usual steps of Groebner basis attacks: the FreeLunch attack (CRYPTO 2024) and the resultant attack (ASIACRYPT 2024).

Friday, Feb 7, 2025 - 10:30 - 24-25/405

Rocco Mora

The Regular Multivariate Quadratic Problem

(ALMASTY Seminar)

In this talk, we introduce a new NP-complete variant of the multivariate quadratic problem. The computational challenge involves finding a solution to an algebraic system that meets the “regular” constraint, meaning that each block of the solution vector contains only one nonzero entry. Following this, we adapt and compare various techniques of cryptanalysis to study the asymptotic complexity of the average instance.

Friday, Jan 31, 2025 - 10:30 - 24-25/405

Damien Vidal

Analyzing the Crossbred Algorithm for the MQ Problem

(ALMASTY Seminar)

Étant donné un système polynomial de m polynômes et n variables sur un corps fini F_p, résoudre ce système est prouvé être un problème NP-complet. Les méthodes communément utilisées pour résoudre ces systèmes sont des algorithmes calculant des bases de Gröbner (F4, F5) ou basés sur l'algèbre linéaire (XL). Dans ce travail, nous nous concentrons sur le problème MQ (Multivariate Quadratic), c’est-à-dire que nous considérons des polynômes de degré 2. En particulier, nous nous intéressons au cas où le système polynomial est défini sur F₂. Dans ce cas, une recherche exhaustive (FES) devient une méthode viable pour résoudre le système polynomial.

Une autre approche consiste à spécifier certaines variables et à tenter de résoudre les systèmes résultants via une approche algébrique. C'est l'idée derrière Crossbred [JV17], par exemple. Crossbred est l’un des algorithmes les plus efficaces en pratique, avec des implémentations battant des records lors du Fukuoka MQ challenge. Cependant, la complexité théorique de cet algorithme n’est pas bien comprise. Les auteurs affirment qu’elle est similaire à celle de FXL ou BooleanSolve, mais à notre connaissance, cette conjecture reste à prouver.

L'objectif principal de ce travail est donc de mieux comprendre cet algorithme. Dans cette optique, nous proposons une variante de l’algorithme Crossbred basée sur l’algorithme matrix-F5 tel que décrit dans [Bar04], afin de faciliter son analyse.

Lors de ma présentation, je décrirai cette nouvelle variante de l’algorithme Crossbred, y compris une analyse sur le choix des paramètres pour cette variante et une compréhension plus approfondie de l’algorithme. À partir des résultats obtenus sur la variante, nous déduisons une analyse de l’algorithme Crossbred original.

• [Bar04] Magali Bardet. Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Thèse de doctorat, Université Paris 6, 2004.
• [JV17] Antoine Joux and Vanessa Vitse. A crossbred algorithm for solving boolean polynomial systems. In Number-Theoretic Methods in Cryptology - NuTMiC 2017, volume 10737 of Lecture Notes in Computer Science, pages 3–21. Springer, 2017.

Thursday, Jan 30, 2025 - 11:00 - ENS, Salle W (!!)

Arthur Herlédan Le Merdy

Unconditional foundations for supersingular isogeny-based cryptography

(Parisian Cryptography Seminar)

Isogeny-based cryptography relies on the assumption that the Isogeny Problem—finding an isogeny between two given elliptic curves—is a hard problem, even for quantum computers. In the security analysis of isogeny-based schemes, several related problems naturally arise, such as computing the endomorphism ring of an elliptic curve or determining a maximal quaternion order isomorphic to it. These problems have been shown to be equivalent to the Isogeny Problem, first under certain heuristics and later under the Generalized Riemann Hypothesis.

In this talk, we present ongoing joint work with Benjamin Wesolowski, in which we unconditionally prove these equivalences, notably using the new tools provided by isogenies in higher dimensions. We further demonstrate that these problems are also equivalent to finding the lattice of all isogenies between two elliptic curves. Finally, we show that if hard instances of the Isogeny problem exist, then all the previously mentioned problems are hard on average.

Friday, Jan 24, 2025 - 10:30 - 24-25/405

Pouria Fallahpour

Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs

(ALMASTY Seminar)

The Learning With Errors (LWE) problem asks to find s from an input of the form (A, b = As + e) in (Z/qZ)^{m × n} × (Z/qZ)^m, for a vector e that has small-magnitude entries. In this talk, I focus on the task of sampling LWE instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create s and e, and then set b = As + e. In particular, such an instance sampler knows the solution. This raises the question of whether it is possible to obliviously sample (A, As + e), namely, without knowing the underlying s.

A variant of the assumption that oblivious LWE sampling is hard has been used in a series of works to analyze the security of candidate constructions of Succinct Non-interactive Arguments of Knowledge (SNARKs). As the assumption is related to LWE, these SNARKs have been conjectured to be secure in the presence of quantum adversaries.

The main focus of the talk is a quantum polynomial-time algorithm that samples well-distributed LWE instances while provably not knowing the solution, under the assumption that LWE is hard. Moreover, the approach works for a vast range of LWE parameterizations, including those used in the above-mentioned SNARKs

Friday, Jan 17, 2025 - 10:30 - 24-25/405

Jules Baudrin

Cryptanalyse différentielle de chiffrements conjugués

(ALMASTY Seminar)

En cryptographie symétrique, le choix d’une (ou de plusieurs) représentation appropriée est un point crucial à la fois dans la recherche d’attaques et dans la conception de nouvelles primitives. En effet, les transformations mises en oeuvre sont souvent représentées commes des ensembles de polynômes univariés ou multivariés et cette pluralité de points de vue est très féconde. Par exemple, l’AES utilise un unique composant non-linéaire, sa boîte-S, dont la sécurité peut être étudiée facilement sous sa forme univariée F: GF(256) -> GF(256) mais dont la représentation multivariée F : GF(2)^{8} -> GF(2)^{8} permet d’optimiser une implémentation matérielle.

Les relations de conjugaison permettent de capturer certains de ces changements de représentation. Deux fonctions F_{1}, F_{2} sont dites conjuguées s’il existe une bijection G telle que G o F_{1} o G^{-1} = F_{2}. Dit autrement, F_{1} et F_{2} sont conjuguées si elles représentent la même fonction ``à renommage près des éléments’’. Dans le cadre d’une attaque à clairs choisis, un adversaire peut donc librement choisir le changement de variables G qui lui convient le mieux. Il est donc naturel de se demander si l’étude des conjugués d’un chiffrement par blocs peut permettre de découvrir des faiblesses non prises en compte par nos arguments de sécurité actuels.

À notre connaissance, seul l’article [ToSC:BeiCanLea18] utilise ce formalisme peu usuel pour faire le pont entre la cryptanalyse par invariant non-linéaire d’un chiffrement par blocs E_{k} et la cryptanalyse linéaire de l’un de ces conjugués G o E_{k} o G^{-1}. Dans cette présentation, nous traiterons le cas de l’analyse différentielle d’un chiffrement conjugué. Après quelques rappels sur l’analyse différentielle, nous montrerons comment sa transposition au cas d’un conjugué peut s’avérer fertile, par exemple pour l’analyse du chiffrement Midori [AC:BBISHA15]. Nous aborderons également les nombreuses questions soulevées par ce nouveau point de vue, notamment sur le choix du ``meilleur’’ changement de variables G ou encore sur l’analyse de la dépendance en la clé. Enfin, nous présenterons d’autres interprétations de ce type de faiblesses, comme des propriétés de commutation ou d’auto-équivalence du chiffrement initial E_{k}, ou encore des propriétés différentielles de E_{k} relatives à d’autres lois de groupe que l’addition modulo 2. Ces points de vue apportent des éclairages variés et complémentaires sur ce nouveau type d’analyse.

Friday, Jan 10, 2025 - 10:30 - 24-25/405

Ky Nguyen

Pairing-Free Blind Signatures from Standard Assumptions in the ROM

(ALMASTY Seminar)

Blind Signatures are a useful primitive for privacy-preserving applications such as electronic payments, e-voting, and anonymous credentials. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first practical construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. This construction is secure under the strong RSA assumption and DDH (in pairing-free groups). We provide a NIZK-friendly signature based on strong RSA, with signature size of 4.28 KB and communication cost of 10.98 KB. Joint work with Julia Kastner (CWI) and Michael Reichle (ETH Zurich)

Tuesday, Dec 17, 2024 - 14:00 - ENS, Amphi Rataud (!!)

Akin Ünal

Evasive LWE Assumptions: Definitions, Classes, and Counterexamples

(Parisian Cryptography Seminar)

The evasive LWE assumption, proposed by Wee [Eurocrypt’22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions: (i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto’22 Tsabary, Asiacrypt’22 VWW, Crypto’23 ARYY] respectively, showing that these assumptions are unlikely to hold. (ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing most existing variants for which we are not aware of simple ad-hoc counterexamples.

Joint work with Chris Brzuska and Ivy K. Y. Woo, published at Asiacrypt 2024.

Monday, Dec 9, 2024 - 14:00 - 25-26/105

Ambroise Fleury

Amélioration des algorithmes de crible. Application à la factorisation des entiers.

Le Crible Algébrique (NFS) est l’algorithme de pointe pour la factorisation des entiers, et le crible est une étape cruciale du NFS. Il s’agit d’une opération qui prend beaucoup de temps et dont le but est de collecter de nombreuses relations. Son but final est de générer des entiers lisses aléatoires mod N avec leur décomposition en facteurs premiers, où le caractère lisse est défini sur les côtés rationnel et algébrique en fonction de deux bases de facteurs premiers. Dans les outils de factorisation modernes, tels que Cado-NFS, le crible est divisé en différentes étapes en fonction de la taille des nombres premiers, mais la définition de bons paramètres pour toutes les étapes est basée sur des arguments heuristiques et pratiques. Au début, les candidats sont criblés par de petits nombres premiers des deux côtés, et s’ils réussissent le test, ils passent aux étapes suivantes avec des nombres premiers plus grands, jusqu’à la dernière où nous factorisons la partie restante à l’aide de l’algorithme ECM. D’une part, les premières étapes sont rapides, mais laissent passer de nombreux faux positifs ce qui ralentit l’algorithme. D’autre part, les étapes finales prennent plus de temps mais produisent moins de relations. Il n’est pas facile d’évaluer la performance de la meilleure stratégie sur l’ensemble de l’étape de crible car elle dépend de la distribution des nombres qui résulte de chaque étape. Dans cette thèse, nous essayons d’examiner différentes stratégies de crible pour accélérer cette étape puisque de nombreuses améliorations ont été apportées à toutes les autres étapes du NFS. Sur la base des relations collectées lors de la factorisation du module RSA-250 et de tous les paramètres, nous essayons d’étudier différentes stratégies pour mieux comprendre cette étape.

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

Lucas Ottow

Threshold Niederreiter: Chosen-Ciphertext Security and Improved Distributed Decoding

(ALMASTY Seminar)

Threshold public key encryption is a variant of public key encryption in which multiple participants are required in order to decrypt a ciphertext. Many threshold PKEs already exist in the literature based on multiple assumptions. However, the topic is not well-studied in the realm of code-based cryptography. In 2023, Takahashi, Hashimoto and Ogata were the first authors to present threshold PKEs in this field. Each of their scheme rely on generic conversion to transform the OW-CPA non-threshold Niederreiter cryptosystem into a IND-CCA threshold scheme. However, each of their design either becomes inefficient when the number of participants becomes large, or contains a security flaw. In this talk, we present our own IND-CCA threshold scheme based on the Niederreiter cryptosystem. Its efficiency does not depend on the number of participants. To achieve this, we first formalize our own generic conversion from OW-CPA to IND-CCA, which is a variant of the Naor-Yung conversion. This conversion uses a NIZK proof system that is both simulation sound and straight line extractable. To instantiate the conversion, we build a variant of an existing NIZK proof system for syndrome decoding based on the MPC-in-the-Head paradigm. We also propose improvements for MPC operations that enables the decryption protocol to be more efficient.

Tuesday, Nov 26, 2024 - 11:00 - ENS, Salle des Actes (!!)

Christian Majenz

Permutation Superposition Oracles for Quantum Query Lower Bounds

(Parisian Cryptography Seminar)

Zhandry’s compressed oracle technique has been extremely successful as a proof tool for analyzing quantum algorithms with (quantum) access to a random function. It has, however, turned out to be very difficult to generalize the technique to the case of random permutations. I will begin this talk by describing the compressed oracle technique on a high level, highlighting the properties of random functions it makes crucial use of. Then I will explain the difficulties that arise when trying to construct an analogue technique for permutations. Finally, I will describe how we tackle the challenges to get a first permutation superposition oracle that has a number of the nice properties which make the function version so useful.

Joint work with Giulio Malavolta and Michael Walter.

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

Mahshid Riahinia

Fast Public-Key Silent OT and More from Constrained Naor-Reingold

(ALMASTY Seminar)

Pseudorandom Correlation Functions (PCFs) allow two parties to locally generate arbitrarily many pseudorandom correlated strings, e.g., Oblivious Transfer (OT) correlations, which can then be used by the two parties to run efficient secure computation protocols. In this talk, I will present a new and simple approach for constructing PCFs for OT correlations by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function. I will then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity weak PRFs allow us to instantiate this paradigm. This idea can be extended further to obtain efficient public-key PCFs for OT and reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZKs) for NP.

This talk is based on https://eprint.iacr.org/2024/178 , joint work with Dung Bui, Geoffroy Couteau, Pierre Meyer, and Alain Passelègue.

Tuesday, Nov 19, 2024 - 11:00 - ENS, Salle des Actes (!!)

Gregor Seiler

Recent progress in lattice-based zero-knowledge proofs

(Parisian Cryptography Seminar)

For the construction of quantum-safe privacy-preserving protocols such as anonymous credential systems for digital identities, one needs zero-knowledge proof systems for proving statements about underlying public-key schemes and ideally also about unstructured symmetric-key primitives such as hash functions. Lattice-based proof systems have improved a lot in recent years so that they now have the potential for beating the state-of-the-art quantum-safe PCP-type proof systems in terms of proof size as well as runtime even for large statements that include big unstructured circuits. I will present the recent progress and discuss where the field is headed.

Friday, Nov 15, 2024 - 10:30 - 24-25/509

Kevin Carrier

Assessing the impact of a variant of the lastest dual attack

(ALMASTY Seminar)

The dual attacks on the Learning With Errors (LWE) problem are currently a subject of controversy within the cryptographic community. In particular, the results of [MATZOV 2022], which assert a substantial reduction in the security level of Kyber— a lattice-based cryptosystem currently being standardized by NIST— have not gained widespread acceptance. Their attack analysis relies on several assumptions that, in certain contexts, contradict established theorems or well-supported heuristics, as noted in [Ducas-Pulles 2023].

In this presentation, I will discuss a collaborative effort with Charles Meyer-Hilfiger, Yixin Shen, and Jean-Pierre Tillich, where we propose a novel dual lattice attack on LWE that reexamines the approach of [MATZOV 2022]. Their method involves transforming a small-LWE problem (defined by a small secret) into another small-LWE problem, which is then reduced to a standard LWE problem where the secret is no longer small but the dimension has been significantly decreased. This second reduction relies on a modulus switching technique. We expand upon this strategy by employing a code-based approach using polar codes over ZZ_q.

I will present a new analysis of our variant of [MATZOV 2022] that does not rely on the independence assumption that they made and which has been challenged by [Ducas-Pulles 2023]. Our results demonstrate that the complexities reported in [MATZOV 2022] are, in fact, achievable.

Friday, Nov 8, 2024 - 10:30 - 24-25/509

Dounia Mfoukh

Differential Meet-in-the-Middle cryptanalysis and its improvements

(ALMASTY Seminar)

At Crypto 2023, a new type of cryptanalysis has been introduced, differential Meet-in-the-Middle cryptanalysis. This new technique can be seen new way to perform the key recovery part in differential attacks but also as a way of extending meet-in-the-middle attacks. As such it is interesting to see if techniques to improve either meet-in-the-middle attacks or differential attack can be used to improve this new type of cryptanalysis. Thus in this talk, I will present how to extend this type of cryptanalysis by using truncated differentials, and i will present some techniques to improve this type of attack, such as the use of structures to extend an attack for one or more rounds, the probabilistic key recovery technique and the state test technique.

Friday, Oct 11, 2024 - 09:30 - Amphithéâtre Durand

Jules Maire

Zero-Knowledge Arguments from Secure Multiparty Computation

This thesis aims to study zero-knowledge arguments, a cryptographic primitive that allows to prove a statement while yielding nothing beyond its truth (we may call it proof instead of argument depending on the security model). Specifically, we focus on a family of arguments whose construction is based on secure multiparty computation. It is well-known that, given any functionality, there exists a secure multiparty protocol computing it. Let us take a generic one-way function f, and a secure multiparty protocol computing f, then it has been shown quite recently that we can build a zero-knowledge argument for the NP-problem of finding a pre-image of f. This construction was considered only theoretical until a few years ago, and our work contributes to the emergence of new techniques as well as efficient applications in this paradigm. As an appetizer, we develop simple zero-knowledge protocols that significantly improve the state-of-the-art communication complexity for some well-known problems. Our first substantial contribution, with a desire to share small elements, is the introduction of a sharing over the integers that is securely embedded in our protocols with some artificial abortion. Applications are manifold, eventually in the post-quantum regime. In the line with our sharing over the integers, we propose a cryptographic string commitment scheme based on subset sum problems. In particular, it enables efficient arguments for circuit satisfiability. Then, we present a proof construction employing conversion between additive and multiplicative secret sharings, leading to efficient proofs of linear and multiplicative relations. The applications are again manifold when designing arguments and digital signatures. Finally, leaving aside protocols conception, we explore cryptography foundations with multi-prover zero-knowledge proofs, a framework for distributing the prover’s computation. To capture the full interest of this dispatching, we add to the literature a fundamental result for threshold zero-knowledge proofs for generic NP-statement.

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, Apr 5, 2024 - 11:30 - 24-25/405

Mahshid Riahinia

TBD

(ALMASTY Seminar)

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.

Tuesday, Jul 4, 2023 - 11:30 - 25-26/105

Florette Martinez

Mathematical studies of arithmetical pseudo-random numbers generators

Les générateurs de nombres pseudo-aléatoires linéaires sont faciles à comprendre et à mettre en œuvre. Le plus célèbre d’entre eux est le générateur congruentiel linéaire . Dans la première partie de cette thèse, nous présentons ce générateur et les différents algorithmes de récupération de clés qui ont été conçus contre lui depuis les années soixante-dix. Parce que ce générateur est simple, il a été utilisé pour concevoir des générateurs plus complexes, que nous avons attaqué.

D’autres générateurs de nombres pseudo-aléatoires sont basés sur des problèmes difficiles, tels que le Knapsack generator et ses variantes. Hélas ils ne sont pas prouvé, même sous l’hypothèse que le problème sous-jacent, le Subset Sum problem, est dur. Nous les avons également attaqués avec succès.

Friday, Jun 23, 2023 - 11:00 - ENS, Salle des actes (!!)

Claude Crépeau

Experimental relativistic zero-knowledge proofs

(Parisian Cryptography Seminar)

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60m) and long distances (>400m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks.

Joint work with Pouriya Alikhani, Nicolas Brunner, Sébastien Designolle, Raphaël Houlmann, Weixu Shi, Nan Yang, and Hugo Zbinden.

Article link

Friday, Jun 2, 2023 - 11:00 - ENS, Salle des actes (!!)

Adeline Roux-Langlois

On the hardness of the Module Learning With Errors problem

(Parisian Cryptography Seminar)

The Module Learning With Errors (M-LWE) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE, i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this talk, I will present recent results on the theoretical hardness of M-LWE.

Based on joint works with Katharina Boudgoust, Corentin Jeudy, and Weiqiang Wen.

Friday, Apr 21, 2023 - 11:00 - ENS, Salle des actes (!!)

Michele Orrù

Gemini - Elastic SNARKs for Diverse Environments

(Parisian Cryptography Seminar)

We introduce and study elastic SNARKs, a class of succinct arguments where the prover has multiple configurations with different time and memory tradeoffs, which can be selected depending on the execution environment and the proved statement. The output proof is independent of the chosen configuration.

We construct an elastic SNARK for rank-1 constraint satisfiability (R1CS). In a time-efficient configuration, the prover uses a linear number of cryptographic operations and a linear amount of memory. In a space-efficient configuration, the prover uses a quasilinear number of cryptographic operations and a logarithmic amount of memory. A key component of our construction is an elastic probabilistic proof. Along the way, we also formulate a streaming framework for R1CS that we deem of independent interest.

We additionally contribute Gemini, a Rust implementation of our protocol. Our benchmarks show that Gemini, on a single machine, supports R1CS instances with tens of billions of constraints.

Joint work with Jonathan Bootle, Alessandro Chiesa, and Yuncong Hu.

IACR eprint

Friday, Apr 7, 2023 - 11:00 - ENS, Salle des actes (!!)

Georg Fuchsbauer

(Concurrently Secure) Blind Schnorr from Schnorr

(Parisian Cryptography Seminar)

Many applications of blind signatures, such as those for blockchains, require the resulting signatures to be compatible with the existing system. This makes schemes that produce Schnorr signatures, which are now supported by major cryptocurrencies, including Bitcoin, desirable. Unfortunately, the existing blind-signing protocol has been shown insecure when users can open signing sessions concurrently (Eurocrypt’21). On the other hand, only allowing sequential sessions opens the door to denial-of-service attacks.

We present the first concurrently secure blind-signing protocol for Schnorr signatures, using the standard primitives NIZK and PKE and assuming that Schnorr signatures themselves are unforgeable. We cast our scheme as a generalization of blind and partially blind signatures. We formally define the notion of predicate blind signatures, in which the signer can define a predicate that the blindly signed message must satisfy.

Joint work with Mathias Wolf.

IACR eprint

Friday, Mar 31, 2023 - 10:30 - 24-25/405

Pierre Briaud

A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions

(ALMASTY Seminar)

The Regular Syndrome Decoding (RSD) problem, a variant of the Syndrome Decoding problem with a particular error distribution, was introduced almost 20 years ago by Augot et al.. In this problem, the error vector is divided into equally sized blocks, each containing a single noisy coordinate. More recently, the last five years have seen increased interest in this assumption due to its use in MPC and ZK applications. Generally referred to as “LPN with regular noise” in this context, the assumption allows to achieve better efficiency when compared to plain LPN. In all previous works of cryptanalysis, it has not been shown how to exploit the special feature of this problem in an attack.

We present the first algebraic attack on RSD. Based on a careful theoretical analysis of the underlying polynomial system, we propose concrete attacks that are able to take advantage of the regular noise distribution. In particular, we can identify several examples of concrete parameters where our techniques outperform other algorithms.

Friday, Mar 24, 2023 - 10:30 - ENS, Salle des actes (!!)

Seungki Kim

A physical study of the LLL algorithm

(Parisian Cryptography Seminar)

This work applies to LLL some methods of statistical physics that are typically used to study SOC models, or more colloquially, sandpile models. Such effort is justified by the close similarity in numerous aspects of the quantitative behavior of both algorithms/systems. There are two merits to our approach:

(i) The sandpile analogues of LLL allow rigorous mathematical studies of its RHF and time complexity to some extent.

(ii) The formulas from the finite-size scaling theory have a number of interesting implications on the output profile of LLL — GSA, average RHF and its variance, and so on.

This is a joint work with Jintai Ding (Tsinghua), Tsuyoshi Takagi (U. Tokyo), Yuntao Wang (Osaka) and Bo-Yin Yang (Academia Sinica).

Arxiv

Friday, Mar 17, 2023 - 11:00 - ENS, Salle des actes (!!)

Sven Maier

Anonymous Whistleblowing over Authenticated Channels

(Parisian Cryptography Seminar)

The goal of anonymous whistleblowing is to publicly disclose a message while at the same time hiding the identity of the sender in a way that even if suspected of being the sender, this cannot be proven. While many solutions to this problem have been proposed over the years, they all require some form of interaction with trusted or non-colluding parties. In this work, we ask whether this is fundamentally inherent. We put forth the notion of anonymous transfer as a primitive allowing to solve this problem without relying on any participating trusted parties.

We initiate the theoretical study of this question, and derive negative and positive results on the existence of such a protocol. We refute the feasibility of asymptotically secure anonymous transfer, where the message will be received with overwhelming probability while at the same time the identity of the sender remains hidden with overwhelming probability. On the other hand, resorting to fine-grained cryptography, we provide a heuristic instantiation (assuming ideal obfuscation) which guarantees that the message will be correctly received with overwhelming probability and the identity of the sender leaks with vanishing probability. Our results provide strong foundations for the study of the possibility of anonymous communications through authenticated channels, an intriguing goal which we believe to be of fundamental interest.

Joint work with Geoffroy Couteau.

IACR eprint

Friday, Mar 10, 2023 - 10:30 - 24-25/509

Andersson Calle Viera

A Practical Template Attack on CRYSTALS-Dilithium

(ALMASTY Seminar)

We present a new profiling side-channel attack on the signature scheme CRYSTALS-Dilithium, which has been selected by the NIST as the new primary standard for quantum-safe digital signatures. This algorithm has a constant-time implementation with consideration for side-channel resilience. However, it does not protect against attacks that exploit intermediate data leakage. We exploit such a leakage on a vector generated during the signing process and whose costly protection by masking is a matter of debate. We design a template attack that enables us to efficiently predict whether a given coefficient in one coordinate of this vector is zero or not. Once this value has been completely reconstructed, one can recover, using linear algebra methods, part of the secret key that is sufficient to produce universal forgeries. While our work deeply discusses the theoretical attack path, it also demonstrates the validity of the assumption regarding the required leakage model, from practical experiments with the reference implementation on an ARM Cortex-M4.

IACR eprint

Friday, Feb 24, 2023 - 11:00 - ENS, Salle des actes (!!)

Chris Brzuska

On lower bounds for garbling schemes

(Parisian Cryptography Seminar)

Secure 2-party computation allows 2 parties to compute a function on their secret inputs. For example, two severs might hold a share k1 and k2 of a secret-key and compute the encryption enc(k1 xor k2,m) of message m.

A garbling scheme first garbles circuit C, for example enc(k1 xor . , . ) in our example. Then, jointly, both parties garble the input, (k2,m) in our example, and now, server 2 can evaluate the garbled circuit on the garbled input and obtains the result of the function, enc(k1 xor k2,m) in our example.

In this talk, we revisit how efficient the garbling of the input can be when the circuit is garbled first (adaptive security). We explore an existing lower bound security by Applebaum, Ishai, Kushilevitz and Waters (Crypto 2013) and tie it closely to the simulation-based security definition of garbling.

We then propose a weaker simulation-based definition which suffices for our use case, but does not seem to suffer from the same lower bound.

Friday, Feb 10, 2023 - 11:30 - ENS, Salle des actes (!!)

Cécile Pierrot

The secret letter of Emperor Charles V - a choose-your-own-adventure decryption

(Parisian Cryptography Seminar)

1546 - The Holy Roman Emperor and King of Spain Charles V writes to his French ambassador, Jean de Saint Mauris. Make this encrypted letter speak half a millennium after it was written is the (true!) story in which you will take part. At each stage of the deciphering process we will take the route chosen by the majority of the audience. No knowledge of Drinfeld modules, S-boxes or Euclidean lattices is required, come as many as you are to answer this question: is it a shopping list or a hitherto unknown assassination plot?

This is a joint work with Camille Desenclos, Pierrick Gaudry, and Paul Zimmermann.

Friday, Jan 27, 2023 - 10:30 - 24-25/405

Julia Sauvage

Attaque de Bleichenbacher sur ECDSA

(ALMASTY Seminar)

Friday, Jan 13, 2023 - 10:30 - 24-25/405

Alex B. Grilo

Post-Quantum Zero-Knowledge with Space-Bounded Simulation

(ALMASTY Seminar)

The traditional definition of quantum zero-knowledge stipulates that the knowledge gained by any quantum polynomial-time verifier in an interactive protocol can be simulated by a quantum polynomial-time algorithm. One drawback of this definition is that it allows the simulator to consume significantly more computational resources than the verifier. We argue that this drawback renders the existing notion of quantum zero-knowledge not viable for certain settings, especially when dealing with near-term quantum devices.

In this work, we initiate a fine-grained notion of post-quantum zero-knowledge that is more compatible with near-term quantum devices. We introduce the notion of (s,f) space-bounded quantum zero-knowledge. In this new notion, we require that an s-qubit malicious verifier can be simulated by a f(s)-qubit quantum polynomial-time algorithm, for some function f, with no restriction on the amount of the classical memory consumed by either the verifier or the simulator.

We explore this notion and establish both positive and negative results:

• For verifiers with logarithmic quantum space sss and (arbitrary) polynomial classical space, we show that (s,f)-space-bounded QZK, for f(s)=2s, can be achieved based on the existence of post-quantum one-way functions. Moreover, our protocol runs in constant rounds.
• For verifiers with super-logarithmic quantum space sss, assuming the existence of post-quantum secure one-way functions, we show that (s,f)-space-bounded QZK protocols, for any function f, with fully black box simulation (classical analogue of black-box simulation) can only be achieved for languages in BQP.

Friday, Dec 16, 2022 - 10:30 - 24-25/405

Samuel Bouaziz-Ermann

Quantum security of subset cover problems

(ALMASTY Seminar)

Friday, Nov 25, 2022 - 11:00 - ENS - Salle des actes (!!)

Olivier Bernard

Log S unit Lattices Using Explicit Stickelberger Generators to Solve Approx Ideal-SVP

(Parisian Cryptography Seminar)

In 2020, Bernard and Roux-Langlois introduced the Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé. They performed experiments for prime conductors cyclotomic fields of degrees at most 70, one of the main bottlenecks being the computation of a log-S-unit lattice which requires subexponential time.

Our main contribution is to extend these experiments to cyclotomic fields of degree up to 210 for most conductors m. Building upon new results from Bernard and Kučera on the Stickelberger ideal, we use explicit generators to construct full-rank log-S-unit sublattices fulfilling the role of approximating the full Twisted-PHS lattice. In our best approximate regime, our results show that the Twisted-PHS algorithm outperforms, over our experimental range, the CDW algorithm by Cramer, Ducas and Wesolowski, and sometimes beats its asymptotic volumetric lower bound.

Additionally, we use these explicit Stickelberger generators to remove almost all quantum steps in the CDW algorithm, under the mild restriction that the plus part of the class number verifies h⁺_m <= O(sqrt(m)).

Joint work with Andrea Lesavourey, Tuong-Huy Nguyen, and Adeline Roux-Langlois.

IACR eprint

Friday, Nov 4, 2022 - 10:30 - 24-25/405

Quoc Huy Vu

On Security Notions for Encryption in a Quantum World

(ALMASTY Seminar)

Indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) is usually considered the most desirable security notion for classical encryption. In this work, we investigate its adaptation in the quantum world, when an adversary can perform superposition queries. The security of quantum-secure classical encryption has first been studied by Boneh and Zhandry (CRYPTO’13), but they restricted the adversary to classical challenge queries, which makes the indistinguishability only hold for classical messages (IND-qCCA2). We extend their work by giving the first security notions for fully quantum indistinguishability under quantum adaptive chosen-ciphertext attacks, where the indistinguishability holds for superposition of plaintexts (qIND-qCCA2).

Eprint

Friday, Oct 28, 2022 - 10:30 - 24-25/405

Orel Cosseron

An Overview of Hybrid Homomorphic Encryption

(ALMASTY Seminar)

Friday, Oct 21, 2022 - 10:30 - 24-25/405

Olivier Blazy

On The Post-Compromise Security of Messaging Protocols

(ALMASTY Seminar)

Post-Compromise Security (PCS) is a property of secure-channel establishment schemes, which limits the security breach of an adversary that has compromised one of the endpoint to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden’s revelation of mass-surveillance, PCS features in prominent messaging protocols such as Signal. In this talk, we first present a variant of Signal which improves PCS property. Since the PCS is not a binary property but rather a spectrum, we then introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal and our variant, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols. We also apply the results obtained for this latter example in order to provide a quick fix, which massively improves its post-compromise security.

Monday, Jun 27, 2022 - 11:15 - ENS, Amphi Rataud (!!)

Fabien Laguillaumie

Efficient CCA Timed Commitments in Class Groups.

(Parisian Cryptography Seminar)

Timed commitments [Boneh and Naor, CRYPTO 2000] are the timed analogue of standard commitments, where the commitment can be non-interactively opened after a pre-specified amount of time passes. Timed commitments have a large spectrum of applications, such as sealed bid auctions, fair contract signing, fair multi-party computation, and cryptocurrency payments. Unfortunately, all practical constructions rely on a (private-coin) trusted setup and do not scale well with the number of participants. These are two severe limiting factors that have hindered the widespread adoption of this primitive.

In this work, we set out to resolve these two issues and propose an efficient timed commitment scheme that also satisfies the strong notion of CCA-security. Specifically, our scheme has a transparent (i.e. public-coin) one-time setup and the amount of sequential computation is essentially independent of the number of participants. As a key technical ingredient, we propose the first (linearly) homomorphic time-lock puzzle with a transparent setup, from class groups of imaginary quadratic order. To demonstrate the applicability of our scheme, we use it to construct a new distributed randomness generation protocol, where n parties jointly sample a random string. Our protocol is the first to simultaneously achieve (1) high scalability in the number of participants, (2) transparent one-time setup, (3) lightning speed in the optimistic case where all parties are honest, and (4) ensure that the output random string is unpredictable and unbiased, even when the adversary corrupts (n-1) parties. To substantiate the practicality of our approach, we implemented our protocol and our experimental evaluation shows that it is fast enough to be used in practice. We also evaluated a heuristic version of the protocol that is at least 3 orders of magnitude more efficient both in terms of communication size and computation time. This makes the protocol suitable for supporting hundreds of participants.

Monday, Jun 27, 2022 - 10:00 - ENS, Amphi Rataud (!!)

Geoffroy Couteau

Pseudorandom correlation generators - constructions and applications

(Parisian Cryptography Seminar)

In this talk, I will survey recent advances in the construction of pseudorandom correlation generators (PCG). A PCG generates a pair of short correlated seeds which can be locally stretched into long pseudorandom instances of a target correlation. Secure sources of random correlations are often used in secure computation, since they enable the use of very efficient MPC protocols in the preprocessing model. A PCG provides a silent way to generate such correlations, following a one-time short interaction. I will cover the basic principles underlying all modern constructions of PCGs, and explain the challenges that arise along the way. I will also survey some more advanced constructions of (variants of) PCGs and discuss their applications.

Tuesday, Jun 7, 2022 - 10:30 - ENS, Salle Simone Weil (!!)

Hoeteck Wee

Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption

(Parisian Cryptography Seminar)

We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree 3 polynomials with compact parameters: the public key, ciphertext and secret keys comprise O(n) group elements, where n is input length for the function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for N users with O(N^{1/3})-sized parameters, breaking the long-standing sqrt{N} barrier for pairing-based broadcast encryption. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) $k$-Lin assumption in prime-order bilinear groups.

Monday, May 16, 2022 - 11:45 - ENS, Salle des Actes (!!)

Marine Minier

Differential Analysis of a Cipher using Constraint Programming

(Parisian Cryptography Seminar)

The aim of this presentation is to show the problems raised by modeling a differential attack on a given cipher. The main obstacle lies on the difficulty of correctly modeling the XOR operator that increases the size of the search tree. For this, we will first use high-level the language Minizinc and a SAT solver then the constraint programming language written in Java, Choco.

Monday, May 16, 2022 - 10:30 - ENS, Salle des Actes (!!)

Yann Rotella

Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2

(Parisian Cryptography Seminar)

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time 240 GEA-1 evaluations and using 44.5 GiB of memory. The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design.

In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time 245.1 GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

Joint work with Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, David Rupprecht, Lukas Stennes.

Thursday, May 12, 2022 - 14:00 - 24-25/509

Florette Martinez

Practical Seed Recovery of Fast Cryptographic Pseudo Random Number Generators

(ALMASTY Seminar)

Trifork is a family of pseudo-random number generators described in 2010 by Orue et al. It is based on Lagged Fibonacci Generators and has been claimed as cryptographically secure. In 2017 was presented a new family of lightweight pseudo-random number generators: Arrow. These generators are based on the same techniques as Trifork and designed to be light, fast and secure, so they can allow private communication between resource-constrained devices. The authors based their choices of parameters on NIST standards on lightweight cryptography and claimed these pseudo-random number generators were of cryptographic strength. We present practical implemented algorithms that reconstruct the internal states of the Arrow generators for different parameters given in the original article. These algorithms enable us to predict all the following outputs and recover the seed. These attacks are all based on a simple guess-and-determine approach which is efficient enough against these generators. We also present an implemented attack on Trifork, this time using lattice-based techniques. We show it cannot have more than 64 bits of security, hence it is not cryptographically secure.

Monday, Apr 25, 2022 - 11:15 - ENS, Salle des Actes (!!)

Magali Bardet

An Algebraic Attack on Rank Metric Code-Based Cryptosystems.

(Parisian Cryptography Seminar)

The Rank metric decoding problem is the main problem considered in cryptography based on codes in the rank metric. Very efficient schemes based on this problem or quasi-cyclic versions of it have been proposed recently, such as those in the submissions ROLLO and RQC currently at the second round of the NIST Post-Quantum Cryptography Standardization Process. While combinatorial attacks on this problem have been extensively studied and seem now well understood, the situation is not as satisfactory for algebraic attacks, for which previous work essentially suggested that they were ineffective for cryptographic parameters. In this paper, starting from Ourivski and Johansson’s algebraic modelling of the problem into a system of polynomial equations, we show how to augment this system with easily computed equations so that the augmented system is solved much faster via Groebner bases. This happens because the augmented system has solving degree r, r+1 or r+2 depending on the parameters, where r is the rank weight, which we show by extending results from Verbel et al. (PQCrypto 2019) on systems arising from the MinRank problem; with target rank r, Verbel et al. lower the solving degree to r+2, and even less for some favorable instances that they call superdetermined. We give complexity bounds for this approach as well as practical timings of an implementation using Magma. This improves upon the previously known complexity estimates for both Groebner basis and (non-quantum) combinatorial approaches, and for example leads to an attack in 200 bits on ROLLO-I-256 whose claimed security was 256 bits.

Joint work with Pierre Briaud, Maxime Bros, Philippe Gaborit, Vincent Neiger, Olivier Ruatta, Jean-Pierre Tillich.

Monday, Apr 25, 2022 - 10:00 - ENS, Salle des Actes (!!)

Alex Grilo

Oblivious Transfer is in MiniQCrypt

(Parisian Cryptography Seminar)

MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security in the plain model against malicious quantum polynomial-time adversaries, building on the foundational work of Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT. In the common random string model, we achieve a constant-round universally composable (UC) OT protocol.

Joint work with Huijia Lin, Fang Song, Vinod Vaikuntanathan.

Thursday, Apr 21, 2022 - 14:00 - 24-25/405

Sarah Bordage

Fast proximity tests for algebraic linear codes

(ALMASTY Seminar)

Most constructions of probabilistically checkable proofs (as well as their interactive variants) involve a proximity testing problem for linear codes. Specifically, the goal is to determine whether an input word belong to a given linear code or is far from any codeword. In many cases, this problem corresponds to a low-degree testing problem, or a variant thereof.

In this talk, we will discuss proximity tests for multivariate polynomial codes and algebraic geometry codes, with linear-time proof generation and logarithmic verification time. Our constructions are inspired from a highly-efficient protocol which solves the Reed-Solomon proximity testing problem, called FRI protocol [Ben-Sasson, Bentov, Horesh, Riabzev. ICALP’2018]. We will first describe the FRI protocol for Reed-Solomon codes, which can be viewed as a univariate low-degree test. Then, we will show how to apply the same design principles in order to construct proximity tests with similar efficiency parameters for codes beyond Reed-Solomon codes.

Thursday, Apr 7, 2022 - 14:30 - 24-25/405

Octavio Perez Kempner

Improved Constructions of Anonymous Credentials From Structure-Preserving Signatures on Equivalence Classes

(ALMASTY Seminar)

Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them.

In this work, we additionally consider equivalence classes on the signing-key space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology ‘19) with a recent SPS-EQ scheme (ASIACRYPT ‘19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO ‘20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials.

To further increase functionality and efficiency, we augment the set-commitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.

Monday, Apr 4, 2022 - 10:30 - ENS, Salle des Actes (!!)

Alice Pellet-Mary

On the Hardness of the NTRU Problem

(Parisian Cryptography Seminar)

The NTRU problem is an algorithmic problem over structured lattices that was introduced by Hoffstein, Pipher, and Silverman more than 20 years ago, and which has been used to construct various cryptographic primitives. However, its relations to other lattice problems is still not well understood.

In this talk, we will see different variants of the NTRU problem, and study how they compare to each other, and to other more classical lattice problems, in terms of reductions. More precisely, we will show that a search variant of the NTRU problem is at least as hard as the shortest vector problem (SVP) in ideal lattices; and that the decisional variant of NTRU is at least as hard as another search variant of NTRU. Unfortunately, the two search variants of NTRU that are considered in these reductions do not match, meaning that we cannot combine the reductions in order to obtain a reduction from the ideal shortest vector problem to the decisional NTRU problem.

Joint work with Damien Stehlé.

Thursday, Mar 31, 2022 - 14:00 - 24-25/405

Ambroise Fleury

Accélération du crible dans CADO-NFS via les arbres de factorisation

(ALMASTY Seminar)

Ma présentation concernera nos travaux sur l’accélération du crible dans CADO-NFS grâce à la factorisation par lot. CADO-NFS est l’implémentation du crible algébrique derrière les derniers records de factorisation RSA-240 (2019) et RSA-250 (2020). Son temps de calcul est dominé par le crible dont l’objectif est d’identifier rapidement un grand nombre d’entiers friables d’une certaine forme. Marquer les multiples des petits nombres premiers représente une fraction importante du temps total.

Nos travaux explorent l’utilisation d’un algorithme de factorisation par lots dû à Bernstein, qui avait suggéré de l’utiliser pour éviter de cribler les grands nombres premiers. Nous nous intéressons à l’idée inverse, c’est-à-dire l’utiliser pour éviter de cribler les petits premiers qui ne correspondent qu’à une petite partie des bits des nombres candidats et apportent donc peu d’information sur leur friabilité. Un crible partiel ne traitant pas les petits premiers permet d’effectuer un filtrage intermédiaire en ´eliminant les entiers candidats dont le produit des facteurs inconnus est trop grand, c’est `a dire les nombres ayant peu de chance d’être friable. Les arbres de factorisation sont finalement utilisés sur le petit ensemble des candidats survivants afin de compléter leur factorisation et d’éliminer alors une deuxième vague de mauvais candidats.

Nous avons réussi à trouver des bornes telles qu’un nombre assez grand de candidats soient éliminés avant la factorisation par lots pour obtenir un gain de temps mais qu’il y ait en contrepartie assez de survivants pour conserver l’essentiel des candidats. Ceci devrait permettre d’accélérer (un peu) la factorisation des grands entiers.

Thursday, Mar 17, 2022 - 14:30 - 55-65/211

Charles Bouillaguet

Les attaques cryptographique sophistiquées sont-elles toujours meilleures que la force brute ?

(Soutenance HDR)

Si la cryptographie est la science du secret, la cryptanalyse est l’art de casser des mécanismes cryptographiques. Un algorithme suffisamment efficace qui brise une propriété de sécurité offerte par un mécanisme cryptographique est une “attaque”. L’efficacité, donc la dangerosité des attaques cryptographiques est généralement évaluée dans le modèle calculatoire usuel des cours d’algorithmique : la Random Access Machine, (ou une de ses variantes) que personne ne se risque à définir précisément.

Dans cet exposé, je voudrais essayer de souligner qu’envisager des modèles de calculs plus réalistes, notamment le modèle AT en vogue dans l’étude des circuits VLSI dès la fin des années 1970 soulève un certain nombre de questions.

Quand on y réfléchit quelques minutes, on peut se rendre compte que, si jamais on essayait de les programmer, on trouverait que de nombreuses attaques cryptographiques sophistiquées sont inférieures dans la pratique à des idées très naïves (recherche exhaustive, etc.).

De plus, optimiser la complexité de certaines attaques dans le modèle AT est un objectif complètement différent de celui d’optimiser le nombre d’opérations. Cela aboutit à des résultats différents. Alors, quelle est la “bonne” manière de faire de la cryptanalyse ?

Thursday, Mar 10, 2022 - 14:00 - 24-25/405

Jules Maire

Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials (following Sakumoto, Shirai and Hiwatari)

(ALMASTY Seminar)

A problem of solving a system of multivariate quadratic polynomials over a finite field, which is called an MQ problem, is a promising problem in cryptography. A number of studies have been conducted on designing public-key schemes using the MQ problem, which are known as multivariate public-key cryptography (MPKC). However, the security of the existing schemes in MPKC relies not only on the MQ problem but also on an Isomorphism of Polynomials (IP) problem. In this talk, we present public-key identification schemes based on the conjectured intractability of the MQ problem under the assumption of the existence of a non-interactive commitment scheme. The schemes (due to Sakumoto, Shirai and Hiwatari) do not rely on the IP problem, and they consist of an identification protocol which is zero-knowledge argument of knowledge for the MQ problem. For a practical parameter choice, the efficiency of these schemes is highly comparable to that of identification schemes based on another problem including Permuted Kernels, Syndrome Decoding, Constrained Linear Equations, and Permuted Perceptrons. Furthermore, even if the protocol is repeated in parallel, the schemes can achieve the security under active attack with some additional cost.

Thursday, Feb 17, 2022 - 14:00 - 24-25/405

Paola de Perthuis

MyOPE - Malicious securitY for Oblivious Polynomial Evaluation

(ALMASTY Seminar)

Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a sender with a private polynomial and a receiver with a private evaluation point where the receiver learns the evaluation of the polynomial in their point and no additional information. They are used in Private Set Intersection (PSI) protocols. We introduce MyOPE, a ``short-sighted’’ polynomial evaluation scheme in the presence of malicious senders. In addition to strong privacy guarantees, MyOPE enforces honest sender behavior and consistency by adding verifiability to the calculations.

The main tools are Verifiable Computation (VC) of inner products between committed vectors for honest behavior enforcement and Fully Homomorphic Encryption (FHE) for input privacy. While classical techniques in pairing-based settings allow generic succinct proofs for such evaluations, they require large prime order subgroups which highly impact the communication complexity, and prevent the use of FHE with practical parameters. MyOPE builds on generic secure encoding techniques for succinct commitments, that allow real-world FHE parameters and Residue Number System (RNS) optimizations, suitable for very high-degree polynomials.

Thursday, Feb 10, 2022 - 14:00 - 24-25/405

Abdul Rahman Taleb

IronMask - Versatile Verification of Masking Security

(ALMASTY Seminar)

This talk introduces IronMask, a new versatile verification tool for masking security. IronMask is the first to offer the verification of standard simulation-based security notions in the probing model as well as recent composition and expandability 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 achieve this complete verifiability by introducing a new algebraic characterization for such quadratic gadgets and exhibiting a complete method to determine the sets of input shares which are necessary and sufficient to perform a perfect simulation of any set of probes. We report various benchmarks which show that IronMask is competitive with state-of-the-art verification tools in the probing model (maskVerif, scVerif, SILVER, matverif). IronMask is also several orders of magnitude faster than VRAPS –the only previous tool verifying random probing composability and expandability– as well as SILVER –the only previous tool providing complete verification for quadratic gadgets with non-linear randomness. Thanks to this completeness and increased performance, we obtain better bounds for the tolerated leakage probability of state-of-the-art random probing secure compilers.

Thursday, Jan 13, 2022 - 14:00 - 24-25/405

Léonard Assouline

Multi-Party PSM, Revisited - Improved Communication and Unbalanced Communication

(ALMASTY Seminar)

We improve the communication complexity in the Private Simultaneous Messages (PSM) model, which is a minimal model of non-interactive information-theoretic multi-party computation. The state-of-the-art PSM protocols were recently constructed by Beimel, Kushilevitz and Nissim (EUROCRYPT 2018). We present new constructions of k-party PSM protocols. The new protocols match the previous upper bounds when k=2 or 3 and improve the upper bounds for larger k. We also construct 2-party PSM protocols with unbalanced communication complexity. More concretely, - For infinitely many k (including all k≤20), we construct k-party PSM protocols for arbitrary functionality f:[N]^k→{0,1}, whose communication complexity is O_k(N^{(k−1)/2}). This improves the former best known upper bounds of O_k(N^{k/2}) for k≥6, O(N^{7/3}) for k=5, and O(N^{5/3}) for k=4. - For all rational 0<η<1 whose denominator is ≤20, we construct 2-party PSM protocols for arbitrary functionality f:[N]×[N]→{0,1}, whose communication complexity is O(N^η) for one party, O(N^{1−η}) for the other. Previously the only known unbalanced 2-party PSM has communication complexity O(log(N)),O(N).

Thursday, Jan 6, 2022 - 14:00 - 24-25/405

Quentin Meunier

LeakageVerif - Scalable and Efficient Leakage Verification in Symbolic Expressions

(ALMASTY Seminar)

Side-channel attacks are a powerful class of attacks targeting cryptographic devices. Masking is a popular protection technique to thwart such attacks as it can be theoretically proven secure. However, correctly implementing masking schemes is a non-trivial task and error-prone. If several techniques have been proposed to formally verify masked implementations, they all come with limitations regarding expressiveness, scalability or accuracy. In this work, we propose a symbolic approach, based on a variant of the classical substitution method, for formally verifying arithmetic and boolean masked programs. This approach is more accurate and scalable than existing approaches thanks to a careful design and implementation of key heuristics, algorithms and data structures involved in the verification process. We present all the details of this approach and the open-source tool called LeakageVerif which implements it as a python library, and which offers constructions for symbolic expressions and functions for their verification. We compare LeakageVerif to three existing state-of-the-art tools on a set of 46 masked programs, and we show that it has very good scalability and accuracy results while providing all the necessary constructs for describing algorithmic to assembly masking schemes. Finally, we also provide the set of 46 benchmarks, named MaskedVerifBenchs and written for comparing the different verification tools, in the hope that they will be useful to the community for future comparisons.

Friday, Dec 10, 2021 - 11:00 - 24-25/309

Thibauld Feneuil

Multi-Party Permutation for Syndrome Decoding - a new zk protocol and code-based signature

(ALMASTY Seminar)

Friday, Nov 26, 2021 - 11:00 - 24-25/405

Nicolas Bordes and Pierre Karpman

Fast Verification of Masking Schemes in Characteristic Two

(ALMASTY Seminar)

We revisit the matrix model for non-interference (NI) probing security of masking gadgets introduced by Belaïd et al. at CRYPTO 2017. This leads to two main results. 1) We generalise the theorems on which this model is based, so as to be able to apply them to masking schemes over any finite field – in particular F_2 – and to be able to analyse the strong non-interference (SNI) security notion. We also follow Faust et al. (TCHES 2018) to additionally consider a robust probing model that takes hardware defects such as glitches into account. 2) We exploit this improved model to implement a very efficient verification algorithm that improves the performance of state-of-the-art software by three orders of magnitude. We show applications to variants of NI and SNI multiplication gadgets from Barthe et al. (EUROCRYPT 2017) which we verify to be secure up to order 11 after a significant parallel computation effort, whereas the previous largest proven order was 7; SNI refreshing gadgets (ibid.); and NI multiplication gadgets from Gross et al. (TIS@CCS 2016) secure in presence of glitches. We also reduce the randomness cost of some existing gadgets, notably for the implementation-friendly case of 8 shares, improving here the previous best results by 17% (resp. 19%) for SNI multiplication (resp. refreshing).

Thursday, Nov 18, 2021 - 14:30 - 24-25/405

Claire Delaplace

Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

(ALMASTY Seminar)

For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We present low memory algorithms for subset-sum and LPN based on a combination of techniques from representations, multiple collision finding, and the Schroeppel-Shamir algorithm. For random subset sum instances 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 techniques 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 k/log k}$. This is a joint work with Andre Esser and Alexander May published at IMACC 2019.

Thursday, Nov 4, 2021 - 14:00 - 24-25/405

Simona Etinski

Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric

(ALMASTY Seminar)

The security of code-based cryptography usually relies on the hardness of the syndrome decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms both in the classical and quantum case. We then apply our results to the Lee metric, which currently receives a significant amount of attention. By providing the parameters of SD for which decoding in the Lee weight seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.

Thursday, Oct 28, 2021 - 14:00 - 24-25/405

Charles Bouillaguet

Algorithms for the Sparse Random 3XOR Problem

(ALMASTY Seminar)

We present algorithms for variants of the 3XOR problem with lists consisting of random sparse n-bit vectors. We consider two notions of sparsity: low-density (each bit is independently biased towards zero) and low-weight (the Hamming weight of n-bit vectors is fixed). We show that the random sparse 3XOR problem can be solved in strongly subquadratic time, namely less than O(N^{2−epsilon}) operations for a constant epsilon > 0. This stands in strong contrast with the regular case, where it has not been possible to have the exponent drop below 2 − o(1). In the low-density setting, a very simple algorithm even runs in linear time with overwhelming success probability when the density is less than 0.0957. Our algorithms exploit the randomness (and sparsity) of the input in an essential way.

Thursday, Oct 14, 2021 - 14:00 - 24-25/405

Florette Martinez

Attacks on Pseudo-Random Number Generators Hiding a Linear Structure

(ALMASTY Seminar)

We introduce lattice-based practical seed-recovery attacks against two efficient number-theoretic pseudo-random number generators: the fast knapsack generator and a family of combined multiple recursive generators. The fast knapsack generator was introduced in 2009 by Von Zur Gathen and Shparlinski. It generates pseudo-random numbers very efficiently with strong mathematical guarantees on their statistical properties but its resistance to cryptanalysis was left open since 2009. The given attacks are surprisingly efficient when the truncated bits do not represent a too large proportion of the internal states. Their complexities do not strongly increase with the size of parameters, only with the proportion of discarded bits. A multiple recursive generator is a pseudo-random number generator based on a constant-recursive sequence. A combined multiple recursive generator is a pseudo-random number generator based on combining two or more multiple recursive generators. L’Écuyer presented the general construction in 1996 and a popular instantiation deemed MRG32k3a in 1999. We use algebraic relations of both pseudo-random generators with underlying algebraic generators to show that they are cryptographically insecure. We provide a theoretical analysis as well as efficient implementations.

Thursday, Oct 7, 2021 - 14:00 - 24-25/405

Abdul Rahman Taleb

On the Power of Expansion - More Efficient Constructions in the Random Probing Model

(ALMASTY Seminar)

The random probing model is a leakage model in which each wire of a circuit leaks with a given probability p. This model enjoys practical relevance thanks to a reduction to the noisy leakage model, which is admitted as the right 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 a recent work, Ananth, Ishai and Sahai (CRYPTO 2018) introduce a nice expansion strategy to construct random probing secure circuits. Their construction tolerates a leakage probability of 2^{−26}, which is the first quantified achievable leakage probability in the random probing model. In a follow-up work, Belaïd, Coron, Prouff, Rivain and Taleb (CRYPTO 2020) generalize their idea and put forward a complete and practical framework to generate random probing secure circuits. The so-called expanding compiler can bootstrap simple base gadgets as long as they satisfy a new security notion called random probing expandability (RPE). They further provide an instantiation of the framework which tolerates a 2^{−8} leakage probability in complexity O(κ^7.5) where κ denotes the security parameter. In this paper, we provide an in-depth analysis of the RPE security notion. We exhibit the first upper bounds for the main parameter of a RPE gadget, which is known as the amplification order. We further show that the RPE notion can be made tighter and we exhibit strong connections between RPE and the strong non-interference (SNI) composition notion. We then introduce the first generic constructions of gadgets achieving RPE for any number of shares and with nearly optimal amplification orders and provide an asymptotic analysis of such constructions. Last but not least, we introduce new concrete constructions of small gadgets achieving maximal amplification orders. This allows us to obtain much more efficient instantiations of the expanding compiler: we obtain a complexity of O(κ^3.9) for a slightly better leakage probability, as well as O(κ^3.2) for a slightly lower leakage probability.