Improved broadcast attacks against subset sum problems via lattice oracle. (English) Zbl 1446.94165
Summary: Subset sum problem is a classical NP-hard problem viewed as a candidate to design quantum-resistant cryptography. Cryptographic constructions based on extended modular subset sum problems are proposed subsequently in recent years. In this paper, we propose an improved broadcast attack against subset sum problems via lattice oracle. We reduce multi-dimensional (modular) subset sum problems to BDD oracle and present an explicit relationship among parameters. To the best of our knowledge, it is the first analysis on the trade-off between the efficiency of broadcast attacks and the number of obtained ciphertexts on subset sum problems. We implement our broadcast attack using LLL and BKZ algorithm and show experimentally that our method is quite practical. Furthermore, our algorithm is applicable to those low-weight subset sum problems which some cryptographic schemes are based on. We claim that our attack is efficient for both binary encoding and powerline encoding under certain parameter settings.
MSC:
| 94A60 | Cryptography |
Software:
BKZReferences:
| [1] | Adleman, L. M., On breaking generalized knapsack public key cryptosystems (abstract), Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, 402-412 (1983) |
| [2] | Ajtai, M., Generating hard instances of lattice problems (extended abstract), Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, 99-108 (1996) · Zbl 0921.11071 |
| [3] | Ajtai, M., The shortest vector problem in \(L_2\) is NP-hard for randomized reductions (extended abstract), Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, 10-19 (1998) · Zbl 1027.68609 |
| [4] | Ajtai, M.; Dwork, C., A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, 284-293 (1997) · Zbl 0962.68055 |
| [5] | Bai, S.; Stehlé, D.; Wen, W., Improved reduction from the bounded distance decoding problem to the unique shortest vector problem in lattices, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, 76:1-76:12 (2016) · Zbl 1391.94869 |
| [6] | Brickell, E. F., Solving low density knapsacks, Advances in Cryptology, Proceedings of CRYPTO ’83, Santa Barbara, California, USA, August 21-24, 1983., 25-37 (1983) · Zbl 1486.94082 |
| [7] | Brickell, E. F., Breaking iterated knapsacks, Advances in Cryptology, Proceedings of CRYPTO ’84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, 342-358 (1984) · Zbl 0569.94011 |
| [8] | Castro, M.; Liskov, B., Practical Byzantine fault tolerance and proactive recovery, ACM Trans. Comput. Syst., 20, 4, 398-461 (2002) |
| [9] | Chaimovich, M.; Freiman, G.; Galil, Z., Solving dense subset-sum problems by using analytical number theory, J. Complex., 5, 3, 271-282 (1989) · Zbl 0686.68030 |
| [10] | Chen, Y.; Nguyen, P. Q., BKZ 2.0: better lattice security estimates, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, 1-20 (2011) · Zbl 1227.94037 |
| [11] | Chor, B.; Rivest, R. L., A knapsack-type public key cryptosystem based on arithmetic in finite fields, IEEE Trans. Inf. Theory, 34, 5, 901-909 (1988) · Zbl 0664.94011 |
| [12] | Coster, M. J.; Joux, A.; LaMacchia, B. A.; Odlyzko, A. M.; Schnorr, C.; Stern, J., Improved low-density subset sum algorithms, Comput. Complex., 2, 111-128 (1992) · Zbl 0768.11049 |
| [13] | Gama, N.; Nguyen, P., Predicting lattice reduction, Advances in Cryptology-EUROCRYPT 2008, 31-51 (2008) · Zbl 1149.94314 |
| [14] | Gama, N.; Nguyen, P. Q.; Regev, O., Lattice enumeration using extreme pruning, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30, - June 3, 2010. Proceedings, 257-278 (2010) · Zbl 1280.94056 |
| [15] | Gentry, C.; Peikert, C.; Vaikuntanathan, V., Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, 197-206 (2008) · Zbl 1231.68124 |
| [16] | Impagliazzo, R.; Naor, M., Efficient cryptographic schemes provably as secure as subset sum, J. Cryptol., 9, 4, 199-216 (1996) · Zbl 0862.94015 |
| [17] | Joux, A.; Stern, J., Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems, Fundamentals of Computation Theory, 8th International Symposium, FCT ’91, Gosen, Germany, September 9-13, 1991, Proceedings, 258-264 (1991) · Zbl 0925.90301 |
| [18] | Lagarias, J. C.; Odlyzko, A. M., Solving low-density subset sum problems, 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, 1-10 (1983) |
| [19] | Lyubashevsky, V.; Micciancio, D., On bounded distance decoding, unique shortest vectors, and the minimum distance problem, Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, 577-594 (2009) · Zbl 1252.94084 |
| [20] | Lyubashevsky, V.; Palacio, A.; Segev, G., Public-key cryptographic primitives provably as secure as subset sum, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings, 382-400 (2010) · Zbl 1274.94096 |
| [21] | Mazo, J. E.; Odlyzko, A. M., Lattice points in high-dimensional spheres, Monatshefte für Mathematik, 110, 1, 47-61 (1990) · Zbl 0719.11063 |
| [22] | Merkle, R. C.; Hellman, M. E., Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Inf. Theory, 24, 5, 525-530 (1978) · Zbl 1487.94132 |
| [23] | Mordell, L. J., On the representation of numbers as the sum of 2r squares, Q. J. Pure Appl. Math. Oxford, 48, 93-104 (1917) · JFM 46.0263.01 |
| [24] | Nguyen, P. Q.; Stern, J., Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations, Advances in Cryptology - CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, 198-212 (1997) · Zbl 0882.94025 |
| [25] | Nguyen, P. Q.; Stern, J., Adapting density attacks to low-weight knapsacks, Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4-8, 2005, Proceedings, 41-58 (2005) · Zbl 1142.94354 |
| [26] | Okamoto, T.; Tanaka, K.; Uchiyama, S., Quantum public-key cryptosystems, Advances in Cryptology - CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings, 147-165 (2000) · Zbl 0995.94535 |
| [27] | Pan, Y.; Zhang, F., Solving low-density multiple subset sum problems with SVP oracle, J. Syst. Science . Complex., 29, 1, 228-242 (2016) · Zbl 1461.90124 |
| [28] | Peikert, C., Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31-June 2, 2009, 333-342 (2009) · Zbl 1304.94079 |
| [29] | Plantard, T.; Susilo, W., Broadcast attacks against lattice-based cryptosystems, International Conference on Applied Cryptography and Network Security, 456-472 (2009), Springer |
| [30] | Ramanujan, S., On certain arithmetical functions, Trans. Cambr. Philos. Soc, 22, 9, 159-184 (1916) · Zbl 07426016 |
| [31] | Regev, O., New lattice based cryptographic constructions, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, 407-416 (2003) · Zbl 1192.94105 |
| [32] | Regev, O., On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, 84-93 (2005) · Zbl 1192.94106 |
| [33] | Shamir, A., A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem, IEEE Trans. Inf. Theory, 30, 5, 699-704 (1984) · Zbl 0552.94007 |
| [34] | Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509 (1997) · Zbl 1005.11065 |
| [35] | van Emde Boas, P., Another NP-complete partition problem and the complexity of computing short vectors in a lattice (1981), Universiteit van Amsterdam. Mathematisch Instituut |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
