Reference : A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
Coron, Jean-Sébastien mailto [University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS) >]
Gini, Agnese mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) >]
Advances in Cryptology -- CRYPTO 2020
Springer International Publishing
August 17-21 2020
[en] public-key cryptography ; Subset-sum problem ; cryptanalysis ; LLL
[en] At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the Nguyen-Stern algorithm works quite well in practice for moderate values of n, we argue that its complexity is actually exponential in n; namely in the final step one must recover a very short basis of a n-dimensional lattice, which takes exponential-time in n, as one must apply BKZ reduction with increasingly large block-sizes.

File(s) associated to this reference

Fulltext file(s):

Limited access
HSSP.pdfAuthor postprint551.11 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.