seminar

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)

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

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, Feb 14, 2025 - 10:30 - 24-25/405

Augustin Bariant

TBD

(ALMASTY Seminar)

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, 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 21, 2025 - 10:30 - 24-25/405

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, May 16, 2025 - 11:30 - 24-25/405

Guirec Lebrun

TBD

(ALMASTY Seminar)

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)

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)