Paper published in a book (Scientific congresses, symposiums and conference proceedings)
A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
Coron, Jean-Sébastien; Gini, Agnese
2020In Advances in Cryptology -- CRYPTO 2020
Peer reviewed
 

Files


Full Text
HSSP.pdf
Author postprint (566.5 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
public-key cryptography; Subset-sum problem; cryptanalysis; LLL
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Coron, Jean-Sébastien ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Gini, Agnese  ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
no
Language :
English
Title :
A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
Publication date :
10 August 2020
Event name :
CRYPTO 2020
Event date :
August 17-21 2020
Main work title :
Advances in Cryptology -- CRYPTO 2020
Publisher :
Springer International Publishing, Cham, Unknown/unspecified
ISBN/EAN :
978-3-030-56880-1
Pages :
3--31
Peer reviewed :
Peer reviewed
Available on ORBilu :
since 24 August 2020

Statistics


Number of views
285 (31 by Unilu)
Number of downloads
36 (9 by Unilu)

Scopus citations®
 
2
Scopus citations®
without self-citations
2
OpenCitations
 
0

Bibliography


Similar publications



Contact ORBilu