seminar (2022-2023)

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.