International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jean-Sebastien Coron , University of Luxembourg
Agnese Gini , University of Luxembourg
Download:
DOI: http://dx.doi.org/10.1007/978-3-030-56880-1_1 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: 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. In this paper, we describe a variant of the Nguyen-Stern algorithm that works in polynomial-time. The first step is the same orthogonal lattice attack with LLL as in the original algorithm. In the second step, instead of applying BKZ, we use a multivariate technique that recovers the short lattice vectors and finally the hidden secrets in polynomial time. Our algorithm works quite well in practice, as we can reach n=250 in a few hours on a single PC.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30345,
  title={A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem},
  publisher={Springer-Verlag},
  doi={http://dx.doi.org/10.1007/978-3-030-56880-1_1},
  author={Jean-Sebastien Coron and Agnese Gini},
  year=2020
}