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
http://hdl.handle.net/10993/44119
A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
English
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) >]
10-Aug-2020
Advances in Cryptology -- CRYPTO 2020
Springer International Publishing
3--31
Yes
978-3-030-56880-1
Cham
CRYPTO 2020
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.
http://hdl.handle.net/10993/44119
10.1007/978-3-030-56880-1_1
https://link.springer.com/chapter/10.1007%2F978-3-030-56880-1_1

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
HSSP.pdfAuthor postprint553.22 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.