Paper 2026/1554
On the Hardness of some Vandermonde Knapsack problems
, Florida Atlantic University, Achhruram Memorial CollegeAbstract
The Vandermonde Knapsack problem comprises a family of algebraic variants of the Knapsack problem. This includes the Partial Vandermonde $(\mathsf{PV})$ Knapsack problem (DCC’15, ACNS’14, ACISP’18, DCC’20, Indocrypt'25), the Vanishing $\mathsf{SIS}$ $(\mathsf{vSIS})$-based commitment problem (Crypto’23, PKC'25), and related assumptions. These problems have played an important role in enabling efficient lattice-based cryptographic constructions. Recently, two independent works by Boudgoust, Gachon, and Pellet-Mary (Crypto’22), and by Das and Joux (Eurocrypt’24), proposed attacks demonstrating that certain instances of the $\mathsf{PV}$ Knapsack problem are weak. In this paper, we present new attacks on the $\mathsf{PV}$ Knapsack problem for power-of-two cyclotomic rings. By combining our techniques with the attack of Das and Joux, we show that a substantially larger fraction of keys are weak in this setting than was previously known. We then extend our attack to the integer variant of the $\mathsf{vSIS}$ commitment problem, demonstrating that certain instances are also weak for specific parameter regimes.
Note: Experimental results have been added to Section 6.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Lattice-based assumptionsLattice reductionsVanishing SIS commitment problemPV Knapsack problem
- Contact author(s)
-
dasd @ fau edu
arindamaths @ gmail com - History
- 2026-08-15: last of 3 revisions
- 2026-07-29: received
- See all versions
- Short URL
- https://ia.cr/2026/1554
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1554,
author = {Dipayan Das and Arindam Mukherjee},
title = {On the Hardness of some Vandermonde Knapsack problems},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1554},
year = {2026},
url = {https://eprint.iacr.org/2026/1554}
}
