Key Recovery Attack on the Partial Vandermonde Knapsack Problem

ePrint Report: Key Recovery Attack on the Partial Vandermonde Knapsack Problem

Dipayan Das, Antoine Joux

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 …

attack block building eprint report key low partial problem recovery report signatures sis