Login | Register

Cryptanalysis of a quadratic knapsack cryptosystem


Cryptanalysis of a quadratic knapsack cryptosystem

Youssef, Amr M. (2011) Cryptanalysis of a quadratic knapsack cryptosystem. Computers & Mathematics with Applications, 61 (4). pp. 1261-1265. ISSN 08981221

Text (application/pdf)
amr2011.pdf - Accepted Version

Official URL: http://dx.doi.org/10.1016/j.camwa.2011.01.006


Wang and Hu [B. Wang and Y. Hu, Quadratic compact knapsack public-key cryptosystem, Comput. Math. Appl. 59 (1) (2010) 194–206] proposed a knapsack-type public-key cryptosystem by introducing an easy quadratic compact knapsack problem and then using the Chinese remainder theorem to disguise the easy knapsack instant. In this paper, we present a heuristic stereotyped message attack that allows the cryptanalyst to recover the plaintext message when partial information about the original message is known. In particular, as shown by our experiments, for the proposed system parameter n = 100 which corresponds to a block length of 400 bits, exposing 60% of the plaintext allows the
cryptanalyst to recover the remaining 160 bits of the essage with a success probability of about 90% in about 2 hours.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering
Item Type:Article
Authors:Youssef, Amr M.
Journal or Publication:Computers & Mathematics with Applications
Digital Object Identifier (DOI):10.1016/j.camwa.2011.01.006
Keywords:Public-key cryptography Cryptanalysis Knapsack cryptosystem Lattice basis reduction Stereotyped message attack
ID Code:976802
Deposited On:28 Jan 2013 13:30
Last Modified:18 Jan 2018 17:43


[1] R.C. Merkle, M.E. Hellman, Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Inform. Theory 24 (1978) 525–530.

[2] A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptographic Research, CRC Press, 1996.

[3] A.M. Odlyzko, The rise and fall of knapsack cryptosystems, in: Cryptology and Computational Number Theory, in: Proc. of Symposia in Applied Mathematics, vol. 42, AMS, 1990, pp. 75–88.

[4] P. Nguyen, J. Stern, Lattice reduction in cryptology: an update, in: Algorithmic Number Theory, Proc. of ANTS-IV, in: LNCS, vol. 1838, Springer-Verlag,
2000, pp. 85–112.

[5] A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) 515–534.

[6] B. Wang, Y. Hu, Quadratic compact knapsack public-key cryptosystem, Comput. Math. Appl. 59 (1) (2010) 194–206.

[7] P. Nguyen, J. Stern, Merkle–Hellman revisited: a cryptanalysis of the Qu–Vanstone cryptosystem based on group factorizations, in: Proc. of Crypto’97, in: LNCS, vol. 1294, Springer-Verlag, Berlin, 1997, pp. 198–212.

[8] S.Y. Yan, Cryptanalytic Attacks on RSA, 1st ed., Springer, 2008.

[9] M.J. Hinek, Cryptanalysis of RSA and its Variants, CRC Press, Taylor & Francis Group, 2009.

[10] D. Boneh, Twenty Years of Attacks on the RSA Cryptosystem, in: Notices of the AMS, vol. 46, 1999, pp. 203–213.

[11] Antoine Joux, Algorithmic Cryptanalysis, Chapman & Hall, CRC Cryptography and Network Security Series, 2009.

[12] T. Nagell, Introduction to Number Theory, Wiley, New York, 1951.

[13] Rainer Dietmann, Small solutions of quadratic diophantine equations, Proc. London Math. Soc. 86 (3) (2003) 545–582.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top