A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem

English

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) >]

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.