nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

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

verfasst von : Jean-Sébastien Coron, Agnese Gini

Erschienen in: Advances in Cryptology – CRYPTO 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \simeq 250\) in a few hours on a single PC.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Asymptotic Complexities of Discrete Logarithm Algorithms in Pairing-Relevant Finite Fields

[Bab86]

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)MathSciNetCrossRef

[BNNT11]

Brier, É., Naccache, D., Nguyen, P.Q., Tibouchi, M.: Modulus fault attacks against RSA-CRT signatures. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 192–206. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_13CrossRef

[BPV98]

Boyko, V., Peinado, M., Venkatesan, R.: Speeding up discrete log and factoring based schemes via precomputations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 221–235. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054129CrossRef

[CG20]

Coron, J.-S., Gini, A.: A polynomial-time algorithm for solving the hidden subset sum problem. Full version of this paper. Cryptology ePrint Archive, Report 2020/461 (2020). https://eprint.iacr.org/2020/461

[CJL+92]

Coster, M.J., Joux, A., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.-P., Stern, J.: Improved low-density subset sum algorithms. Comput. Complex. 2, 111–128 (1992)MathSciNetCrossRef

[CKPS00]

Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_27CrossRef

[CLO05]

Cox, D.A., Little, J., Oshea, D.: Using Algebraic Geometry. Springer, New York (2005). https://doi.org/10.1007/b138611CrossRef

[CLT13]

Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_26CrossRef

[CN11]

Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_1CrossRef

[CN19]

Coron, J.-S., Notarnicola, L.: Cryptanalysis of CLT13 multilinear maps with independent slots. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 356–385. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_13CrossRef

[CNT10]

Coron, J.-S., Naccache, D., Tibouchi, M.: Fault attacks against emv signatures. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 208–220. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11925-5_15CrossRef

[CP19]

Coron, J.-S., Pereira, H.V.L.: On Kilian’s randomization of multilinear map encodings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 325–355. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_12CrossRef

[FLLT15]

Fouque, P.-A., Lee, M.S., Lepoint, T., Tibouchi, M.: Cryptanalysis of the Co-ACD assumption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 561–580. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_27CrossRef

[fpl16]

The FPLLL development team. FPLLL, a lattice reduction library (2016). https://github.com/fplll/fplll

[HPS11]

Hanrot, G., Pujol, X., Stehlé, D.: Analyzing blockwise lattice algorithms using dynamical systems. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 447–464. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_25CrossRef

[LLL82]

Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982). https://doi.org/10.1007/BF01457454MathSciNetCrossRefMATH

[LO85]

Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229–246 (1985)MathSciNetCrossRef

[LT15]

Lepoint, T., Tibouchi, M.: Cryptanalysis of a (somewhat) additively homomorphic encryption scheme used in PIR. In: Brenner, M., Christin, N., Johnson, B., Rohloff, K. (eds.) FC 2015. LNCS, vol. 8976, pp. 184–193. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48051-9_14CrossRef

[NS97]

Nguyen, P., Stern, J.: Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 198–212. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052236CrossRef

[NS98a]

Nguyen, P., Stern, J.: The Béguin-Quisquater server-aided RSA protocol from Crypto ’95 is not secure. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 372–379. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49649-1_29CrossRef

[NS98b]

Nguyen, P., Stern, J.: Cryptanalysis of the Ajtai-Dwork cryptosystem. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 223–242. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055731CrossRef

[NS99]

Nguyen, P., Stern, J.: The hardness of the hidden subset sum problem and its cryptographic implications. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 31–46. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_3CrossRef

[NS09]

Nguyen, P.Q., Stehlé, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874–903 (2009)MathSciNetCrossRef

[NSS04]

Naccache, D., Smart, N.P., Stern, J.: Projective coordinates leak. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 257–267. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_16CrossRef

[Sag19]

The Sage Developers. Sagemath, the Sage Mathematics Software System (Version 8.9) (2019). https://www.sagemath.org

[Sch87]

Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201–224 (1987)MathSciNetCrossRef

[Sho]

Shoup, V.: Number theory C++ library (NTL) version 3.6. http://www.shoup.net/ntl/

[vDGHV10]

van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_2CrossRef

Titel: A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
verfasst von: Jean-Sébastien Coron
Agnese Gini
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56879-5

Electronic ISBN: 978-3-030-56880-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-56880-1_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"