Provably Solving the Hidden Subset Sum Problem via Statistical Learning

E-print/Working paper (2021)

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 ... [more ▼]

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. [less ▲]

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

in Advances in Cryptology -- CRYPTO 2020 (2020, August 10)

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 ... [more ▼]

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. [less ▲]

CRYPTO 2020

in CRYPTO 2020 (2020)

Cryptanalysis of CLT13 Multilinear Maps with Independent Slots

in Advances in Cryptology – ASIACRYPT 2019, 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part II (2019, December)

On Kilian's Randomization of Multilinear Map Encodings

in Coron, Jean-Sébastien; Pereira, Vitor (Eds.) On Kilian's Randomization of Multilinear Map Encodings (2019)

Zeroizing Attacks on Indistinguishability Obfuscation over CLT13

in Proceedings of PKC 2017 (2017)

Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme

in Proceedings of CHES 2016 (2016)

Zeroizing Without Low-Level Zeroes: New MMAP Attacks and Their Limitations

in Proceedings of Crypto 2015 (2015)

Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity

in Leander, Gregor (Ed.) Fast Software Encryption, 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers (2015, March)

A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean ... [more ▼]

A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithm against first-order attacks. Our algorithm performs well in practice, as for k=64 we obtain a 23% improvement compared to Goubin’s algorithm. [less ▲]

Higher Order Masking of Look-Up Tables

in Proceedings of Eurocrypt 2014 (2014)