Figure 1.
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
-
Previous Article
The average dimension of the Hermitian hull of constacyclic codes over finite fields of square order
- AMC Home
- This Issue
- Next Article
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 |
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.
Keywords:
Subset sum problem,
lattice,
BKZ reduction,
id-scheme,
compact knapsack problem,
cryptography.
Mathematics Subject Classification:
94A60, 11D04, 11Y16.
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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [6] |
I. Damgård, On Sigma-protocols, http://www.cs.au.dk/~ivan/Sigma.pdf, Course material, 2010. |
| [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. |
| [8] |
K. A. Draziotis and A. Papadopoulou, https://github.com/drazioti/python_scripts/tree/master/paper_knapsack. |
| [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. |
| [10] |
S. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, 2012.
doi: 10.1017/CBO9781139012843. |
| [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. |
| [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. |
| [13] |
M. R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [23] |
D. Micciancio and S. Goldwasser, Complexity of Lattice Problems A cryptographic Perspective, Springer 2002.
doi: 10.1007/978-1-4615-0897-7. |
| [24] |
R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995.
doi: 10.1017/CBO9780511814075. |
| [25] |
The FpLLL development team, fplll, Available at https://github.com/fplll/fplll. |
| [26] |
The FpyLLL development team, fpylll: A python interface for fplll, Available at https://github.com/fplll/fpylll. |
| [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.
|
| [28] |
C.-P. Schnorr,
Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174.
doi: 10.1007/BF00196725. |
| [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. |
| [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. |
| [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. |
| [32] |
The Sage Developers, SageMath, the Sage Mathematics Software System (Ver. 6.9) http://www.sagemath.org. |
| [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. |
| [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. |
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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [6] |
I. Damgård, On Sigma-protocols, http://www.cs.au.dk/~ivan/Sigma.pdf, Course material, 2010. |
| [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. |
| [8] |
K. A. Draziotis and A. Papadopoulou, https://github.com/drazioti/python_scripts/tree/master/paper_knapsack. |
| [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. |
| [10] |
S. Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, 2012.
doi: 10.1017/CBO9781139012843. |
| [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. |
| [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. |
| [13] |
M. R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [23] |
D. Micciancio and S. Goldwasser, Complexity of Lattice Problems A cryptographic Perspective, Springer 2002.
doi: 10.1007/978-1-4615-0897-7. |
| [24] |
R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, Cambridge, 1995.
doi: 10.1017/CBO9780511814075. |
| [25] |
The FpLLL development team, fplll, Available at https://github.com/fplll/fplll. |
| [26] |
The FpyLLL development team, fpylll: A python interface for fplll, Available at https://github.com/fplll/fpylll. |
| [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.
|
| [28] |
C.-P. Schnorr,
Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174.
doi: 10.1007/BF00196725. |
| [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. |
| [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. |
| [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. |
| [32] |
The Sage Developers, SageMath, the Sage Mathematics Software System (Ver. 6.9) http://www.sagemath.org. |
| [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. |
| [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. |
Figure 5.
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
Figure 2.
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
Figure 3.
We compare SS's Method with the first variant, for $32$ randomly chosen instances of density $1$ and $\dim = 84$
Figure 4.
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
Table 1.
Relation of the density of random knapsack problems and the average number of rounds until SS-method terminates successfully
| density | |||||
| success round (average) | |||||
| success round (average) | |||||
| success round (average) |
| density | |||||
| success round (average) | |||||
| success round (average) | |||||
| success round (average) |
Table 2.
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)$
| right entries(on average) | ||
| |
| right entries(on average) | ||
| |
Table 3.
Here ${{a}_{j}}\xleftarrow{\$}{{I}_{R/8}}.$ We executed 80 random instances for each row
| right entries(on average) | ||
| right entries(on average) | ||
| [1] |
Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial and 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 and Management Optimization, 2005, 1 (3) : 315-321. doi: 10.3934/jimo.2005.1.315 |
| [3] |
Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048 |
| [4] |
Thomas Espitau, Antoine Joux. Certified lattice reduction. Advances in Mathematics of Communications, 2020, 14 (1) : 137-159. doi: 10.3934/amc.2020011 |
| [5] |
Zhi-Wei Sun. Unification of zero-sum problems, subset sums and covers of Z. Electronic Research Announcements, 2003, 9: 51-60. |
| [6] |
Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015 |
| [7] |
Shengbing Deng, Zied Khemiri, Fethi Mahmoudi. On spike solutions for a singularly perturbed problem in a compact riemannian manifold. Communications on Pure and Applied Analysis, 2018, 17 (5) : 2063-2084. doi: 10.3934/cpaa.2018098 |
| [8] |
Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial and Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 |
| [9] |
Frédéric Legoll, William Minvielle. Variance reduction using antithetic variables for a nonlinear convex stochastic homogenization problem. Discrete and Continuous Dynamical Systems - S, 2015, 8 (1) : 1-27. doi: 10.3934/dcdss.2015.8.1 |
| [10] |
Gabriela Marinoschi. Well posedness of a time-difference scheme for a degenerate fast diffusion problem. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 435-454. doi: 10.3934/dcdsb.2010.13.435 |
| [11] |
Yoshiho Akagawa, Elliott Ginder, Syota Koide, Seiro Omata, Karel Svadlenka. A Crank-Nicolson type minimization scheme for a hyperbolic free boundary problem. Discrete and Continuous Dynamical Systems - B, 2022, 27 (5) : 2661-2681. doi: 10.3934/dcdsb.2021153 |
| [12] |
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 and Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591 |
| [13] |
François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete and Continuous Dynamical Systems, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221 |
| [14] |
Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure and Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087 |
| [15] |
Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative lattice dynamical systems with delays. Discrete and Continuous Dynamical Systems, 2008, 21 (2) : 643-663. doi: 10.3934/dcds.2008.21.643 |
| [16] |
Pablo Amster, Colin Rogers. On a Ermakov-Painlevé II reduction in three-ion electrodiffusion. A Dirichlet boundary value problem. Discrete and Continuous Dynamical Systems, 2015, 35 (8) : 3277-3292. doi: 10.3934/dcds.2015.35.3277 |
| [17] |
Holger R. Dullin, Jürgen Scheurle. Symmetry reduction of the 3-body problem in $ \mathbb{R}^4 $. Journal of Geometric Mechanics, 2020, 12 (3) : 377-394. doi: 10.3934/jgm.2020011 |
| [18] |
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 |
| [19] |
Maike Schulte, Anton Arnold. Discrete transparent boundary conditions for the Schrodinger equation -- a compact higher order scheme. Kinetic and Related Models, 2008, 1 (1) : 101-125. doi: 10.3934/krm.2008.1.101 |
| [20] |
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 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]