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. AardalC. 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. BeckerJ.-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. CosterA. JouxB. A. LaMacchiaA. M. OdlyzkoC.-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. GamaP. 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. LenstraH. 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. WangQ. 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. AardalC. 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. BeckerJ.-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. CosterA. JouxB. A. LaMacchiaA. M. OdlyzkoC.-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. GamaP. 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. LenstraH. 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. WangQ. 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 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
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 $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$
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)$
$n$ $R $ right entries(on average)
$\mathcal{S}_1:30$ $40$ $100\%$
$\mathcal{S}_2:30$ $40$ $50\%$
$\mathcal{S}_3:30$ $40$ $50\%$
$\mathcal{S}_4:30$ $40$ $62.8\%$
$n$ $R $ right entries(on average)
$\mathcal{S}_1:30$ $40$ $100\%$
$\mathcal{S}_2:30$ $40$ $50\%$
$\mathcal{S}_3:30$ $40$ $50\%$
$\mathcal{S}_4:30$ $40$ $62.8\%$
Table 3.  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]

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

[4]

Zhi-Wei Sun. Unification of zero-sum problems, subset sums and covers of Z. Electronic Research Announcements, 2003, 9: 51-60.

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Jan Prüss, Gieri Simonett. On the Muskat problem. Evolution Equations & Control Theory, 2016, 5 (4) : 631-645. doi: 10.3934/eect.2016022

[18]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[19]

Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial & Management Optimization, 2010, 6 (4) : 847-860. doi: 10.3934/jimo.2010.6.847

[20]

Gengsheng Wang, Yashan Xu. Advantages for controls imposed in a proper subset. Discrete & Continuous Dynamical Systems - B, 2013, 18 (9) : 2427-2439. doi: 10.3934/dcdsb.2013.18.2427

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (108)
  • HTML views (185)
  • Cited by (0)

[Back to Top]