Reference : Provably Solving the Hidden Subset Sum Problem via Statistical Learning
E-prints/Working papers : Already available on another site
Engineering, computing & technology : Computer science
Provably Solving the Hidden Subset Sum Problem via Statistical Learning
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) > PI Coron >]
[en] Cryptanalysis ; lattice reduction ; statistical attack ; FastICA
[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. As an application, they showed how to break the Boyko et al. fast generator of random pairs (x, g x(mod p)). The Nguyen-Stern algorithm works quite well in practice for moderate values of n, but its complexity is exponential in n. A polynomial-time variant was recently described at Crypto 2020, based on a multivariate technique, but the approach is heuristic only. In this paper, we describe a proven polynomial-time algorithm for solving the hidden subset-sum problem, based on statistical learning. In addition, we show that the statistical approach is also quite efficient in practice: using the FastICA algorithm, we can reach n = 250 in reasonable time.

File(s) associated to this reference

Fulltext file(s):

Limited access
hlc_MC.pdfAuthor preprint407.8 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.