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

Konstantinos A. Draziotis; Anastasia Papadopoulou

doi:10.3934/amc.2018026

Article Contents

2018, Volume 12, Issue 3: 429-449. Doi: 10.3934/amc.2018026

This issue Previous Article Next Article The average dimension of the Hermitian hull of constacyclic codes over finite fields of square order

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

Konstantinos A. Draziotis^1, , and
Anastasia Papadopoulou^2,

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
* Corresponding author: K. A. Draziotis

Received: May 2016

Revised: March 2018

Published: July 2018

Abstract / Introduction Full Text(HTML) Figure(5) / Table(3) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 94A60, 11D04, 11Y16.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 3. We compare SS's Method with the first variant, for $32$ randomly chosen instances of density $1$ and $\dim = 84$

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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$

| Show Table

DownLoad: CSV

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\%$

| Show Table

DownLoad: CSV

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\%$

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.