# 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] 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 [2] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 [3] Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253 [4] Giulio Ciraolo, Antonio Greco. An overdetermined problem associated to the Finsler Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021004 [5] Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384 [6] Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108 [7] Kimie Nakashima. Indefinite nonlinear diffusion problem in population genetics. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3837-3855. doi: 10.3934/dcds.2020169 [8] Xinfu Chen, Huiqiang Jiang, Guoqing Liu. Boundary spike of the singular limit of an energy minimizing problem. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3253-3290. doi: 10.3934/dcds.2020124 [9] Constantine M. Dafermos. A variational approach to the Riemann problem for hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 185-195. doi: 10.3934/dcds.2009.23.185 [10] Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453 [11] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031 [12] Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075 [13] Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171 [14] Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261 [15] Nguyen Huy Tuan. On an initial and final value problem for fractional nonclassical diffusion equations of Kirchhoff type. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020354 [16] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [17] Vo Van Au, Hossein Jafari, Zakia Hammouch, Nguyen Huy Tuan. On a final value problem for a nonlinear fractional pseudo-parabolic equation. Electronic Research Archive, 2021, 29 (1) : 1709-1734. doi: 10.3934/era.2020088 [18] Maho Endo, Yuki Kaneko, Yoshio Yamada. Free boundary problem for a reaction-diffusion equation with positive bistable nonlinearity. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3375-3394. doi: 10.3934/dcds.2020033 [19] Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099 [20] Shumin Li, Masahiro Yamamoto, Bernadette Miara. A Carleman estimate for the linear shallow shell equation and an inverse source problem. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 367-380. doi: 10.3934/dcds.2009.23.367

2019 Impact Factor: 0.734