## CryptoDB

### Adeline Roux-Langlois

#### Publications

**Year**

**Venue**

**Title**

2022

ASIACRYPT

Log-$\mathcal{S}$-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP
Abstract

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-$\mathcal{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-$\mathcal{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\leq O(\sqrt{m})$.

2020

ASIACRYPT

Towards Classical Hardness of Module-LWE: The Linear Rank Case
📺
Abstract

We prove that the module learning with errors (M-LWE) problem with arbitrary polynomial-sized modulus $p$ is \emph{classically} at least as hard as standard worst-case lattice problems, as long as the module rank $d$ is
not smaller than the ring dimension $n$.
Previous publications only showed the hardness under quantum reductions.
We achieve this result in an analogous manner as in the case of the learning with errors (LWE) problem.
First, we show the classical hardness of M-LWE with an exponential-sized modulus.
In a second step, we prove the hardness of M-LWE using a binary secret.
And finally, we provide a modulus reduction technique.
The complete result applies to the class of power-of-two cyclotomic fields.
However, several tools hold for more general classes of number fields and may be of independent interest.

2020

ASIACRYPT

Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices
📺
Abstract

Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal lattices than in arbitrary ones, in particular in the quantum setting.
Our main contribution is to propose a new ``twisted'' version of the PHS (by Pellet-Mary, Hanrot and Stehlé 2019) algorithm, that we call Twisted-PHS. As a minor contribution, we also propose several improvements of the PHS algorithm. On the theoretical side, we prove that our twisted-PHS algorithm performs at least as well as the original PHS algorithm. On the practical side though, we provide a full implementation of our algorithm which suggest that much better approximation factors are achieved, and that the given lattice bases are a lot more orthogonal than the ones used in PHS. This is the first time to our knowledge that this type of algorithm is completely implemented and tested for fields of degrees up to 60.

2019

ASIACRYPT

Middle-Product Learning with Rounding Problem and Its Applications
Abstract

At CRYPTO 2017, Roşca et al. introduce a new variant of the Learning With Errors (LWE) problem, called the Middle-Product LWE (
$${\mathrm {MP}\text {-}\mathrm{LWE}}$$
). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the
$${\mathrm {MP}\text {-}\mathrm{LWE}}$$
problem. In this paper, we propose a deterministic variant of their encryption scheme, which does not need Gaussian sampling and is thus simpler than the original one. Still, it has the same quasi-optimal asymptotic key and ciphertext sizes. The main ingredient for this purpose is the Learning With Rounding (LWR) problem which has already been used to derandomize LWE type encryption. The hardness of our scheme is based on a new assumption called Middle-Product Computational Learning With Rounding, an adaption of the computational LWR problem over rings, introduced by Chen et al. at ASIACRYPT 2018. We prove that this new assumption is as hard as the decisional version of MP-LWE and thus benefits from worst-case to average-case hardness guarantees.

2015

ASIACRYPT

#### Program Committees

- Eurocrypt 2021
- Crypto 2019
- PKC 2018

#### Coauthors

- Martin R. Albrecht (1)
- Shi Bai (3)
- Olivier Bernard (2)
- Katharina Boudgoust (2)
- Catalin Cocis (1)
- Dipayan Das (1)
- Corentin Jeudy (1)
- Fabien Laguillaumie (2)
- Tancrède Lepoint (2)
- Andrea Lesavourey (1)
- Benoît Libert (1)
- San Ling (1)
- Thuc D. Nguyen (1)
- Khoa Nguyen (1)
- Amin Sakzad (1)
- Damien Stehlé (4)
- Ron Steinfeld (3)
- Huaxiong Wang (1)
- Weiqiang Wen (2)
- Zhenfei Zhang (1)