## CryptoDB

### Katharina Boudgoust

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Some Easy Instances of Ideal-SVP and Implications to the Partial Vandermonde Knapsack Problem
📺 ★
Abstract

In this article, we generalize the works of Pan et al. (Eurocrypt'21) and Porter et al. (ArXiv'21) and provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely, we show that the more automorphisms stabilize the ideal, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois fields, and we generalize it to any ideal (whose prime factors are not ramified) of any number field.
We then provide a cryptographic application of this result by showing that particular instances of the partial Vandermonde knapsack problem, also known as partial Fourier recovery problem, can be solved classically in polynomial time. As a proof of concept, we implemented our attack and managed to solve those particular instances for concrete parameter settings proposed in the literature. For random instances, we can halve the lattice dimension with non-negligible probability.

2022

JOFC

On the Hardness of Module Learning with Errors with Short Distributions
Abstract

The Module Learning With Errors ( $$\text {M-LWE}$$ 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 $$\text {M-LWE}$$ M-LWE , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that $$\text {M-LWE}$$ M-LWE with uniform $$\eta $$ η -bounded secret for any $$1 \le \eta \ll q$$ 1 ≤ η ≪ q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of $$\text {M-LWE}$$ M-LWE , provided that the module rank d is at least logarithmic in the ring degree n . We also prove that the search version of $$\text {M-LWE}$$ M-LWE with large uniform secret and uniform $$\eta $$ η -bounded error is at least as hard as the standard $$\text {M-LWE}$$ M-LWE problem, if the number of samples m is close to the module rank d and with further restrictions on $$\eta $$ η . The latter result can be extended to provide the hardness of search $$\text {M-LWE}$$ M-LWE with uniform $$\eta $$ η -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

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.

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.

#### Coauthors

- Shi Bai (1)
- Dipayan Das (1)
- Erell Gachon (1)
- Corentin Jeudy (2)
- Alice Pellet-Mary (1)
- Adeline Roux-Langlois (3)
- Weiqiang Wen (3)
- Zhenfei Zhang (1)