Paper 2026/1658
Upper bounds for failure probabilities of reductions from low density subset sum problems to lattice problems on linearly independent vectors
Abstract
As a new lattice problem, we introduce $l$-Shortest Independent Vectors Problem ($l$-SIVP for short), where $l$ is a positive integer no greater than the rank of a lattice. In the case where $l=1$, $l$-SIVP means SVP, and in the case where $l$ is the rank of a lattice, $l$-SIVP means SIVP. We estimate upper bounds on the failure probabilities of the reductions from the subset sum problems to the $l$-SIVPs in terms of Ehrhart theory. Especially, in the case of $l=1$, our upper bound is tighter than the previous result given by Coster et al. We give some considerations for dominating terms of our upper bounds of failure probabilities when $l$ is general.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- subset sum problemlattice problemsknapsack cryptographyEhrhart theory
- Contact author(s)
- kamada shoichi ft @ u tsukuba ac jp
- History
- 2026-08-15: approved
- 2026-08-11: received
- See all versions
- Short URL
- https://ia.cr/2026/1658
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1658,
author = {Shoichi Kamada},
title = {Upper bounds for failure probabilities of reductions from low density subset sum problems to lattice problems on linearly independent vectors},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1658},
year = {2026},
url = {https://eprint.iacr.org/2026/1658}
}
