Welcome to the resource topic for 2024/366
Title:
Key Recovery Attack on the Partial Vandermonde Knapsack Problem
Authors: Dipayan Das, Antoine Joux
Abstract:The Partial Vandermonde (PV) Knapsack problem is an algebraic variant of the low-density inhomogeneous SIS problem. The problem has been used as a building block for various lattice-based constructions, including signatures (ACNS’14, ACISP’18), encryptions (DCC’15,DCC’20), and signature aggregation (Eprint’20). At Crypto’22, Boudgoust, Gachon, and Pellet-Mary proposed a key distinguishing attack on the PV Knapsack exploiting algebraic properties of the problem. Unfortunately, their attack doesn’t offer key recovery, except for worst-case keys.
In this paper, we propose an alternative attack on the PV Knapsack problem, which provides key recovery for a much larger set of keys. Like the Crypto’22 attack, it is based on lattice reduction and uses a dimension reduction technique to speed-up the underlying lattice reduction algorithm and enhance its performance. As a side bonus, our attack transforms the PV Knapsack problem into uSVP instances instead of SVP instances in the Crypto’22 attack. This also helps the lattice reduction algorithm, both from a theoretical and practical point of view.
We use our attack to re-assess the hardness of the concrete parameters used in the literature. It appears that many contain a non-negligible fraction of weak keys, which are easily identified and extremely susceptible to our attack. For example, a fraction of 2^{-19} of the public keys of a parameter set from ACISP’18 can be solved in about 30 hours on a moderate server using off-the-shelf lattice reduction. This parameter set was initially claimed to have a 129-bit security against key recovery attack. Its security was reduced to 87-bit security using the distinguishing attack from Crypto’22. Similarly, the ACNS’14 proposal also includes a parameter set containing a fraction of 2^{-19} of weak keys; those can be solved in about 17 hours.
ePrint: https://eprint.iacr.org/2024/366
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .