# American Institute of Mathematical Sciences

August  2018, 12(3): 429-449. doi: 10.3934/amc.2018026

## Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme

 1 Aristotle University of Thessaloniki, Department of Informatics, P.O. Box 114, Thessaloniki 54124, Greece 2 Aristotle University of Thessaloniki, Department of Mathematics, Thessaloniki 54124, Greece

* Corresponding author: K. A. Draziotis

Received  May 2016 Revised  March 2018 Published  July 2018

In the present study we consider two variants of Schnorr-Shevchenko method (SS) for solving hard knapsack problems, which are on average faster than the SS method. Furthermore, we study the compact knapsack problem i.e. the solution space is not {0, 1} as in knapsack problem but some larger set, and we present an algorithm to attack this problem. Finally, we provide a three move sound id-scheme based on the compact knapsack problem.

Citation: Konstantinos A. Draziotis, Anastasia Papadopoulou. Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme. Advances in Mathematics of Communications, 2018, 12 (3) : 429-449. doi: 10.3934/amc.2018026
##### References:
 [1] K. Aardal, C. Hurkens and A. Lenstra, Solving a linear Diophantine equation with lower and upper bounds on the variables, Integer Programming and Combinatorial Optimization, LNCS, 1412 (1998), 229-242. doi: 10.1007/3-540-69346-7_18. Google Scholar [2] K. Aardal and F. Eisenbrand, The LLL Algorithm and Integer Programming, The LLL Algorithm (Survey and Applications), Springer, 2010, 293–314. doi: 10.1007/978-3-642-02295-1_9. Google Scholar [3] M. Ajtai, The shortest vector problem in $L_2$ is NP-hard for randomized reduction, Proc. 30th ACM Symposium on Theory of Computing (STOC), 1998, 10-19. doi: 10.1145/276698.276705. Google Scholar [4] A. Becker, J.-S. Coron and A. Joux, Improved generic algorithm for hard knapsacks, Eurocrypt 2011, LNCS, 6632 (2011), 364-385. doi: 10.1007/978-3-642-20465-4_21. Google Scholar [5] M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C.-P. Schnorr and J. Stern, Improved low-density subset sum algorithms, Computational Complexity, 2 (1992), 111-128. doi: 10.1007/BF01201999. Google Scholar [6] I. Damgård, On Sigma-protocols, http://www.cs.au.dk/~ivan/Sigma.pdf, Course material, 2010.Google Scholar [7] K. A. Draziotis, Balanced Integer solutions of linear equations, AMIMS 2013(Greece), Optimization and its Applications (SOIA), Springer, 91 (2014), 173–188. doi: 10.1007/978-3-319-04720-1_11. Google Scholar [8] K. A. Draziotis and A. Papadopoulou, https://github.com/drazioti/python_scripts/tree/master/paper_knapsack.Google Scholar [9] A. M. Freize, On the Lagarias-Odlyzko algorithm for the subset sum problem, SIAM J. Comput., 15 (1986), 536-539. doi: 10.1137/0215038. Google Scholar [10] S. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, 2012. doi: 10.1017/CBO9781139012843. Google Scholar [11] N. Gama, P. Q. Nguyen and O. Regev, Lattice enumeration using extreme pruning, Eurocrypt 2010, LNCS, 6110 (2010), 257-278. doi: 10.1007/978-3-642-13190-5_13. Google Scholar [12] N. Gama and P. Q. Nguyen, Predicting lattice reduction, LNCS, Springer, 4965 (2008), 31–51. doi: 10.1007/978-3-540-78967-3_3. Google Scholar [13] M. R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. Google Scholar [14] G. Hanrot, X. Pujol and D. Stehlé. Analyzing blockwise lattice algorithms using dynamical systems, LNCS, Springer, 6841 (2011), 447–464. doi: 10.1007/978-3-642-22792-9_25. Google Scholar [15] N. Howgrave-Graham and A. Joux, New generic algorithms for hard knapsacks, Eurocrypt 2010, LNCS, 6110 (2010), 235-256. doi: 10.1007/978-3-642-13190-5_12. Google Scholar [16] R. Impagliazzo and M. Naor, Efficient Cryptographic schemes Provably as secure as subset sum, Journal of Cryptology, 9 (1996), 199-216. doi: 10.1007/s001459900012. Google Scholar [17] J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, J. Assoc. Comput. Mach., 32 (1985), 229-246. doi: 10.1145/2455.2461. Google Scholar [18] M. S. Lee, Improved cryptanalysis of a knapsack-based probabilistic encryption scheme, Information Sciences, 222 (2013), 779-783. doi: 10.1016/j.ins.2012.07.063. Google Scholar [19] A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454. Google Scholar [20] V. Lyubashevsky, Lattice-based identification schemes secure under active attacks, Public Key Cryptography 2008, LNCS, 4939 (2008), 162-179. doi: 10.1007/978-3-540-78440-1_10. Google Scholar [21] A. May and M.Herrmann, Solving linear equations modulo divisors: On factoring given any bits, In Advances in Cryptology (Asiacrypt 2008), 5350 (2008), 406–424. doi: 10.1007/978-3-540-89255-7_25. Google Scholar [22] D. Micciancio and O. Regev, Lattice-Based Cryptography, In Post Quantum Cryptography, Springer, 2009, 147–191. doi: 10.1007/978-3-540-88702-7_5. Google Scholar [23] D. Micciancio and S. Goldwasser, Complexity of Lattice Problems A cryptographic Perspective, Springer 2002. doi: 10.1007/978-1-4615-0897-7. Google Scholar [24] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511814075. Google Scholar [25] The FpLLL development team, fplll, Available at https://github.com/fplll/fplll.Google Scholar [26] The FpyLLL development team, fpylll: A python interface for fplll, Available at https://github.com/fplll/fpylll.Google Scholar [27] S. Radziszowski and D. Kreher, Solving subset sum problems with the $L^3$ algorithm, Journal of Combinatorial Mathematics and Combinatorial Computing, 3 (1988), 49-63. Google Scholar [28] C.-P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174. doi: 10.1007/BF00196725. Google Scholar [29] C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical Programming, 66 (1994), 181-199. doi: 10.1007/BF01581144. Google Scholar [30] C.-P. Schnorr and T. Shevchenko, Solving Subset Sum Problems of Density close to 1 by "randomized" BKZ-reduction. Cryptology ePrint Archive, Report 2012/620.Google Scholar [31] R. Schroeppel and A. Shamir, A $T = O(2^{n/2}), \ S = O(2^{n/4})$ algorithm for certain NP-complete problems, SIAM J. Comput., 10 (1981), 456-464. doi: 10.1137/0210033. Google Scholar [32] The Sage Developers, SageMath, the Sage Mathematics Software System (Ver. 6.9) http://www.sagemath.org.Google Scholar [33] B. Wang, Q. Wu and Y. Hu, A knapsack-based probabilistic encryption scheme, Information Science, 177 (2007), 3981-3994. doi: 10.1016/j.ins.2007.03.010. Google Scholar [34] A. M. Youssef, Cryptanalysis of a knapsack-based probabilistic encryption scheme, Information Sciences, 179 (2009), 3116-3121. doi: 10.1016/j.ins.2009.05.015. Google Scholar

show all references

##### References:
 [1] K. Aardal, C. Hurkens and A. Lenstra, Solving a linear Diophantine equation with lower and upper bounds on the variables, Integer Programming and Combinatorial Optimization, LNCS, 1412 (1998), 229-242. doi: 10.1007/3-540-69346-7_18. Google Scholar [2] K. Aardal and F. Eisenbrand, The LLL Algorithm and Integer Programming, The LLL Algorithm (Survey and Applications), Springer, 2010, 293–314. doi: 10.1007/978-3-642-02295-1_9. Google Scholar [3] M. Ajtai, The shortest vector problem in $L_2$ is NP-hard for randomized reduction, Proc. 30th ACM Symposium on Theory of Computing (STOC), 1998, 10-19. doi: 10.1145/276698.276705. Google Scholar [4] A. Becker, J.-S. Coron and A. Joux, Improved generic algorithm for hard knapsacks, Eurocrypt 2011, LNCS, 6632 (2011), 364-385. doi: 10.1007/978-3-642-20465-4_21. Google Scholar [5] M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C.-P. Schnorr and J. Stern, Improved low-density subset sum algorithms, Computational Complexity, 2 (1992), 111-128. doi: 10.1007/BF01201999. Google Scholar [6] I. Damgård, On Sigma-protocols, http://www.cs.au.dk/~ivan/Sigma.pdf, Course material, 2010.Google Scholar [7] K. A. Draziotis, Balanced Integer solutions of linear equations, AMIMS 2013(Greece), Optimization and its Applications (SOIA), Springer, 91 (2014), 173–188. doi: 10.1007/978-3-319-04720-1_11. Google Scholar [8] K. A. Draziotis and A. Papadopoulou, https://github.com/drazioti/python_scripts/tree/master/paper_knapsack.Google Scholar [9] A. M. Freize, On the Lagarias-Odlyzko algorithm for the subset sum problem, SIAM J. Comput., 15 (1986), 536-539. doi: 10.1137/0215038. Google Scholar [10] S. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, 2012. doi: 10.1017/CBO9781139012843. Google Scholar [11] N. Gama, P. Q. Nguyen and O. Regev, Lattice enumeration using extreme pruning, Eurocrypt 2010, LNCS, 6110 (2010), 257-278. doi: 10.1007/978-3-642-13190-5_13. Google Scholar [12] N. Gama and P. Q. Nguyen, Predicting lattice reduction, LNCS, Springer, 4965 (2008), 31–51. doi: 10.1007/978-3-540-78967-3_3. Google Scholar [13] M. R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. Google Scholar [14] G. Hanrot, X. Pujol and D. Stehlé. Analyzing blockwise lattice algorithms using dynamical systems, LNCS, Springer, 6841 (2011), 447–464. doi: 10.1007/978-3-642-22792-9_25. Google Scholar [15] N. Howgrave-Graham and A. Joux, New generic algorithms for hard knapsacks, Eurocrypt 2010, LNCS, 6110 (2010), 235-256. doi: 10.1007/978-3-642-13190-5_12. Google Scholar [16] R. Impagliazzo and M. Naor, Efficient Cryptographic schemes Provably as secure as subset sum, Journal of Cryptology, 9 (1996), 199-216. doi: 10.1007/s001459900012. Google Scholar [17] J. C. Lagarias and A. M. Odlyzko, Solving low-density subset sum problems, J. Assoc. Comput. Mach., 32 (1985), 229-246. doi: 10.1145/2455.2461. Google Scholar [18] M. S. Lee, Improved cryptanalysis of a knapsack-based probabilistic encryption scheme, Information Sciences, 222 (2013), 779-783. doi: 10.1016/j.ins.2012.07.063. Google Scholar [19] A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534. doi: 10.1007/BF01457454. Google Scholar [20] V. Lyubashevsky, Lattice-based identification schemes secure under active attacks, Public Key Cryptography 2008, LNCS, 4939 (2008), 162-179. doi: 10.1007/978-3-540-78440-1_10. Google Scholar [21] A. May and M.Herrmann, Solving linear equations modulo divisors: On factoring given any bits, In Advances in Cryptology (Asiacrypt 2008), 5350 (2008), 406–424. doi: 10.1007/978-3-540-89255-7_25. Google Scholar [22] D. Micciancio and O. Regev, Lattice-Based Cryptography, In Post Quantum Cryptography, Springer, 2009, 147–191. doi: 10.1007/978-3-540-88702-7_5. Google Scholar [23] D. Micciancio and S. Goldwasser, Complexity of Lattice Problems A cryptographic Perspective, Springer 2002. doi: 10.1007/978-1-4615-0897-7. Google Scholar [24] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511814075. Google Scholar [25] The FpLLL development team, fplll, Available at https://github.com/fplll/fplll.Google Scholar [26] The FpyLLL development team, fpylll: A python interface for fplll, Available at https://github.com/fplll/fpylll.Google Scholar [27] S. Radziszowski and D. Kreher, Solving subset sum problems with the $L^3$ algorithm, Journal of Combinatorial Mathematics and Combinatorial Computing, 3 (1988), 49-63. Google Scholar [28] C.-P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174. doi: 10.1007/BF00196725. Google Scholar [29] C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematical Programming, 66 (1994), 181-199. doi: 10.1007/BF01581144. Google Scholar [30] C.-P. Schnorr and T. Shevchenko, Solving Subset Sum Problems of Density close to 1 by "randomized" BKZ-reduction. Cryptology ePrint Archive, Report 2012/620.Google Scholar [31] R. Schroeppel and A. Shamir, A $T = O(2^{n/2}), \ S = O(2^{n/4})$ algorithm for certain NP-complete problems, SIAM J. Comput., 10 (1981), 456-464. doi: 10.1137/0210033. Google Scholar [32] The Sage Developers, SageMath, the Sage Mathematics Software System (Ver. 6.9) http://www.sagemath.org.Google Scholar [33] B. Wang, Q. Wu and Y. Hu, A knapsack-based probabilistic encryption scheme, Information Science, 177 (2007), 3981-3994. doi: 10.1016/j.ins.2007.03.010. Google Scholar [34] A. M. Youssef, Cryptanalysis of a knapsack-based probabilistic encryption scheme, Information Sciences, 179 (2009), 3116-3121. doi: 10.1016/j.ins.2009.05.015. Google Scholar
We considered 50 knapsack problems of dimension $80$ and density $\approx 1$ and we measured the average time for all the instances terminated in round 5 or 6, ..., or 23
We compare SS's Method, for dimension $80$, with the first variant and second variant for some randomly chosen instances of knapsack problem. The $x-$ axis is the number of instances and the $y-$axis is the cpu time. Furthermore, we sorted the results with respect to the times of the original method
We compare SS's Method, for dimension $80$, with the first variant for some randomly chosen instances of knapsack problem. The $x-$ axis is the number of instances and the $y-$axis is the cpu time. Moreover, we sorted the results with respect to the times of the original method
We compare SS's Method with the first variant, for $32$ randomly chosen instances of density $1$ and $\dim = 84$
We compare the SS's Method with the second variant for randomly chosen instances of knapsack problem with dimension $80,$ Hamming weight $n/2$ and density close to $1.$ The two horizontal axes for $16$ and $10$, are (on average) the time that the original method takes until round 16 and 10 (resp.). Furthermore, we sorted the results with respect to the times of the original method
Relation of the density of random knapsack problems and the average number of rounds until SS-method terminates successfully
 density $1$ $0.975$ $0.95$ $0.92$ ${\rm dim}=80$ success round (average) $12.57$ $10.38$ $9.69$ $8.35$ ${\rm dim}=76$ success round (average) $9.1$ $8.83$ $7.95$ $5.6$ ${\rm dim}=72$ success round (average) $8.15$ $7.9$ $7.7$ $5.5$
 density $1$ $0.975$ $0.95$ $0.92$ ${\rm dim}=80$ success round (average) $12.57$ $10.38$ $9.69$ $8.35$ ${\rm dim}=76$ success round (average) $9.1$ $8.83$ $7.95$ $5.6$ ${\rm dim}=72$ success round (average) $8.15$ $7.9$ $7.7$ $5.5$
Here we assume that ${\bf{x}}\in \mathcal{S}_i,$ where $\mathcal{S}_1,\mathcal{S}_2,\mathcal{S}_3,\mathcal{S}_4$ are $I_R^{n}$, $I_{R}^{n/2}\times I_{R/2}^{n/2}, \ I_{R/2}^{n/2}\times I_{R/4}^{n/2}$ and $I_{R}^{n/3}\times I_{R/2}^{n/3}\times I_{R/4}^{n/3}$, respectively. Further ${{a}_{j}}\xleftarrow{\$}{{I}_{R/2}}$. We executed 80 random instances for each row. Similar results we got for$(n, R) = (60, 80), (103,100)$$nR $right entries(on average)$\mathcal{S}_1:3040100\%\mathcal{S}_2:304050\%\mathcal{S}_3:304050\%\mathcal{S}_4:304062.8\%$$nR $right entries(on average)$\mathcal{S}_1:3040100\%\mathcal{S}_2:304050\%\mathcal{S}_3:304050\%\mathcal{S}_4:304062.8\%$Here${{a}_{j}}\xleftarrow{\$}{{I}_{R/8}}.$ We executed 80 random instances for each row
 $n$ $R$ right entries(on average) $\mathcal{S}_1:60$ $320$ $100\%$ $\mathcal{S}_2:60$ $320$ $50\%$ $\mathcal{S}_3:60$ $320$ $50\%$ $\mathcal{S}_4:60$ $320$ $62.4\%$
 $n$ $R$ right entries(on average) $\mathcal{S}_1:60$ $320$ $100\%$ $\mathcal{S}_2:60$ $320$ $50\%$ $\mathcal{S}_3:60$ $320$ $50\%$ $\mathcal{S}_4:60$ $320$ $62.4\%$
 [1] Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531 [2] Yuzhong Zhang, Fan Zhang, Maocheng Cai. Some new results on multi-dimension Knapsack problem. Journal of Industrial & Management Optimization, 2005, 1 (3) : 315-321. doi: 10.3934/jimo.2005.1.315 [3] Thomas Espitau, Antoine Joux. Certified lattice reduction. Advances in Mathematics of Communications, 2020, 14 (1) : 137-159. doi: 10.3934/amc.2020011 [4] Zhi-Wei Sun. Unification of zero-sum problems, subset sums and covers of Z. Electronic Research Announcements, 2003, 9: 51-60. [5] Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015 [6] Shengbing Deng, Zied Khemiri, Fethi Mahmoudi. On spike solutions for a singularly perturbed problem in a compact riemannian manifold. Communications on Pure & Applied Analysis, 2018, 17 (5) : 2063-2084. doi: 10.3934/cpaa.2018098 [7] Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 [8] Frédéric Legoll, William Minvielle. Variance reduction using antithetic variables for a nonlinear convex stochastic homogenization problem. Discrete & Continuous Dynamical Systems - S, 2015, 8 (1) : 1-27. doi: 10.3934/dcdss.2015.8.1 [9] Gabriela Marinoschi. Well posedness of a time-difference scheme for a degenerate fast diffusion problem. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 435-454. doi: 10.3934/dcdsb.2010.13.435 [10] Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591 [11] François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221 [12] Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087 [13] Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative lattice dynamical systems with delays. Discrete & Continuous Dynamical Systems - A, 2008, 21 (2) : 643-663. doi: 10.3934/dcds.2008.21.643 [14] Pablo Amster, Colin Rogers. On a Ermakov-Painlevé II reduction in three-ion electrodiffusion. A Dirichlet boundary value problem. Discrete & Continuous Dynamical Systems - A, 2015, 35 (8) : 3277-3292. doi: 10.3934/dcds.2015.35.3277 [15] Oleg V. Kaptsov, Alexey V. Schmidt. Reduction of three-dimensional model of the far turbulent wake to one-dimensional problem. Conference Publications, 2011, 2011 (Special) : 794-802. doi: 10.3934/proc.2011.2011.794 [16] Maike Schulte, Anton Arnold. Discrete transparent boundary conditions for the Schrodinger equation -- a compact higher order scheme. Kinetic & Related Models, 2008, 1 (1) : 101-125. doi: 10.3934/krm.2008.1.101 [17] Hawraa Alsayed, Hussein Fakih, Alain Miranville, Ali Wehbe. Finite difference scheme for 2D parabolic problem modelling electrostatic Micro-Electromechanical Systems. Electronic Research Announcements, 2019, 26: 54-71. doi: 10.3934/era.2019.26.005 [18] Shengfan Zhou, Caidi Zhao, Yejuan Wang. Finite dimensionality and upper semicontinuity of compact kernel sections of non-autonomous lattice systems. Discrete & Continuous Dynamical Systems - A, 2008, 21 (4) : 1259-1277. doi: 10.3934/dcds.2008.21.1259 [19] Jan Prüss, Gieri Simonett. On the Muskat problem. Evolution Equations & Control Theory, 2016, 5 (4) : 631-645. doi: 10.3934/eect.2016022 [20] Viorel Nitica, Andrei Török. On a semigroup problem. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 2365-2377. doi: 10.3934/dcdss.2019148

2018 Impact Factor: 0.879