seminar
ALMASTY seminar
This page gives the program of the ALMASTY seminar and the joint Parisian cryptography seminar (currently organized by the CASCADE team).
Upcoming talks
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.
Friday, Nov 29, 2024 - 09: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.
Friday, Dec 6, 2024 - 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 = A s + 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 = A s + e. In particular, such an instance sampler knows the solution. This raises the question of whether it is possible to obliviously sample (A, A s + 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. This invalidates the assumptions used in their security analyses, although it does not yield attacks against the constructions themselves.
Friday, Dec 13, 2024 - 10:30 - 24-25/405
River Moreira Ferreira
Polynomial-Time Key-Recovery Attack on the NIST Specification of PROV
(ALMASTY Seminar)
Friday, Dec 13, 2024 - 10:30 - 24-25/405
Jules Baudrin
TBD
(ALMASTY Seminar)
Past talks (2024-2025)
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.