
-
Previous Article
The average dimension of the Hermitian hull of constacyclic codes over finite fields of square order
- AMC Home
- This Issue
- Next Article
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.
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. |





density | |||||
success round (average) | |||||
success round (average) | |||||
success round (average) |
density | |||||
success round (average) | |||||
success round (average) | |||||
success round (average) |
right entries(on average) | ||
|
right entries(on average) | ||
|
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]