seminar

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

(Soutenance Thèse)

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 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.

(Soutenance Thèse)

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

(Soutenance Thèse)

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.