## CryptoDB

### Charles Bouillaguet

#### Publications

**Year**

**Venue**

**Title**

2024

CIC

Preliminary Cryptanalysis of the Biscuit Signature Scheme
Abstract

<p> Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded. </p>

2023

ASIACRYPT

We Are on the Same Side. Alternative Sieving Strategies for the Number Field Sieve
Abstract

The Number Field Sieve (NFS) is the state-of-the art algorithm for integer
factoring, and sieving is a crucial step in the NFS. It is a very
time-consuming operation, whose goal is to collect many relations. The
ultimate goal is to generate random smooth integers mod $N$ with their prime
decomposition, where smooth is defined on the rational and algebraic sides
according to two prime factor bases.
In modern factorization tool, such as \textsf{Cado-NFS}, sieving is split into
different stages depending on the size of the primes, but defining good
parameters for all stages is based on heuristic and practical arguments. At
the beginning, candidates are sieved by small primes on both sides, and if
they pass the test, they continue to the next stages with bigger primes, up to
the final one where we factor the remaining part using the ECM algorithm. On
the one hand, first stages are fast but many false relations pass them, and we
spend a lot of time with useless relations. On the other hand final stages are
more time demanding but outputs less relations. It is not easy to evaluate the
performance of the best strategy on the overall sieving step since it depends
on the distribution of numbers that results at each stage.
In this article, we try to examine different sieving strategies to speed up
this step since many improvements have been done on all other steps of the
NFS. Based on the relations collected during the RSA-250 factorization and all
parameters, we try to study different strategies to better understand this
step. Many strategies have been defined since the discovery of NFS, and we
provide here an experimental evaluation.

2020

TOSC

Practical seed-recovery for the PCG Pseudo-Random Number Generator
📺
Abstract

The Permuted Congruential Generators (PCG) are popular conventional (non-cryptographic) pseudo-random generators designed in 2014. They are used by default in the NumPy scientific computing package. Even though they are not of cryptographic strength, their designer stated that predicting their output should nevertheless be "challenging".In this article, we present a practical algorithm that recovers all the hidden parameters and reconstructs the successive internal states of the generator. This enables us to predict the next “random” numbers, and output the seeds of the generator. We have successfully executed the reconstruction algorithm using 512 bytes of challenge input; in the worst case, the process takes 20 000 CPU hours.This reconstruction algorithm makes use of cryptanalytic techniques, both symmetric and lattice-based. In particular, the most computationally expensive part is a guessand-determine procedure that solves about 252 instances of the Closest Vector Problem on a very small lattice.

2018

TOSC

Revisiting and Improving Algorithms for the 3XOR Problem
Abstract

The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions F,G and H and she has to find three inputs x, y and z such that F(x) ⊕ G(y) ⊕ H(z) = 0. The 3XOR problem is a difficult case of the more-general k-list birthday problem. Wagner’s celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to F, G and H is minimal. If they are n-bit random functions, it is possible to solve the problem with roughly

2014

ASIACRYPT

#### Coauthors

- Elena Andreeva (2)
- Alex Biryukov (1)
- Charles Bouillaguet (13)
- Hsieh-Chung Chen (1)
- Chen-Mou Cheng (1)
- Tung Chou (1)
- Claire Delaplace (1)
- Patrick Derbez (1)
- Orr Dunkelman (2)
- Jean-Charles Faugère (1)
- Ambroise Fleury (1)
- Pierre-Alain Fouque (9)
- Jonathan J. Hoch (2)
- John Kelsey (2)
- Dmitry Khovratovich (1)
- Paul Kirchner (1)
- Gaëtan Leurent (1)
- Gilles Macario-Rat (1)
- Florette Martinez (1)
- Ruben Niederhagen (1)
- Ludovic Perret (1)
- Julia Sauvage (2)
- Adi Shamir (3)
- Amandine Véber (1)
- Bo-Yin Yang (1)
- Sébastien Zimmer (2)