## CryptoDB

### Adeline Roux-Langlois

#### Publications

**Year**

**Venue**

**Title**

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.

#### Program Committees

- Crypto 2019

#### Coauthors

- Shi Bai (2)
- Olivier Bernard (1)
- Katharina Boudgoust (2)
- Dipayan Das (1)
- Corentin Jeudy (1)
- Tancrède Lepoint (1)
- Amin Sakzad (1)
- Damien Stehlé (1)
- Ron Steinfeld (1)
- Weiqiang Wen (2)
- Zhenfei Zhang (1)