Key Recovery Attack on the Partial Vandermonde Knapsack Problem

Summary

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 worstcase 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.