This page gives the program of the ALMASTY seminar and the joint Parisian cryptography seminar (currently organized by the CASCADE team).
Friday, Nov 25, 2022 - 11:00 - ENS - Salle des actes (!!)
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.
Friday, Dec 16, 2022 - 10:30 - 24-25/405
Quantum security of subset cover problems
Friday, Dec 16, 2022 - 11:00 - ENS, Salle des actes (!!)
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.
Friday, Jan 13, 2023 - 10:30 - 24-25/405
Alex B. Grilo
Past talks (2022-2023)
Friday, Nov 4, 2022 - 10:30 - 24-25/405
Quoc Huy Vu
On Security Notions for Encryption in a Quantum World
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).
Friday, Oct 28, 2022 - 10:30 - 24-25/405
An Overview of Hybrid Homomorphic Encryption
Friday, Oct 21, 2022 - 10:30 - 24-25/405
On The Post-Compromise Security of Messaging Protocols
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.