Paper 2020/461

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

Jean-Sébastien Coron and Agnese Gini

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Keywords
Subset-sum problemlattice cryptanalysisLLL.
Contact author(s)
jscoron @ gmail com
agnese gini @ uni lu
History
2021-07-28: last of 3 revisions
2020-04-24: received
See all versions
Short URL
https://ia.cr/2020/461
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/461,
      author = {Jean-Sébastien Coron and Agnese Gini},
      title = {A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2020/461},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/461}},
      url = {https://eprint.iacr.org/2020/461}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.