×

A knapsack-based probabilistic encryption scheme. (English) Zbl 1142.94361

Summary: Knapsack-based cryptosystems had been viewed as the most attractive and the most promising asymmetric cryptographic algorithms for a long time due to their NP-completeness nature and high speed in encryption/decryption. Unfortunately, most of them are broken for the low-density feature of the underlying knapsack problems. In this paper, we investigate a new easy compact knapsack problem and propose a novel knapsack-based probabilistic public-key cryptosystem in which the cipher-text is non-linear with the plaintext. For properly chosen parameters, the underlying knapsack problem enjoys a high density larger than 1.06 in the worst case. Hence, it is secure against the low-density subset-sum attacks. Our scheme can also defeat other potential attacks such as the brute force attacks and the simultaneous Diophantine approximation attack. Compared with previous knapsack-based cryptosystems, our scheme is efficient and practical.

MSC:

94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Brickell, E.F., Solving low-density knapsacks, (), 24-37
[2] Brickell, E.F.; Odlyzko, A.M., Cryptanalysis: a survey of recent results, (), 501-540 · Zbl 0818.94014
[3] Chor, B.; Rivest, R.L., A knapsack-type public-key cryptosystem based on arithmetic in finite fields, IEEE transactions on information theory, 34, 901-909, (1988) · Zbl 0664.94011
[4] Coster, M.J.; LaMacchia, B.A.; Odlyzko, A.M.; Schnorr, C.P., An improved low-density subset-sum algorithm, (), 54-67 · Zbl 0774.11075
[5] Goodman, R.M.F.; McAuley, A.J., New trapdoor-knapsack public-key cryptosystem, IEE Proceedings, 132 Pt. E, 6, 282-292, (1985) · Zbl 1392.94915
[6] S. Han, E. Chang, T. Dillon, Knapsack Diffie-Hellman: a new family of Diffie-Hellman, Cryptology ePrint Archive: Report 2005/347, pp. 1-17. http://eprint.iacr.org/2005/347.
[7] Janardan, R.; Lakshmanan, K.B., A public-key cryptosystem based on the matrix cover NP-complete problem, (), 21-37 · Zbl 0516.94012
[8] Koskinen, J.A., Non-injective knapsack public-key cryptosystems, Theoretical computer science, 255, 401-422, (2001) · Zbl 0971.94010
[9] Lagarias, J.C., Knapsack public-key cryptosystems and Diophantine approximation, (), 3-23
[10] Lagarias, J.C.; Odlyzko, A.M., Solving low-density subset-sum problems, Journal of the ACM, 32, 229-246, (1985) · Zbl 0632.94007
[11] M.K. Lai, Knapsack cryptosystems: the past and the future, online manuscript, 2003, pp. 1-21. http://www.ics.uci.edu/ mingl/knapsack.html.
[12] Laih, C.S.; Gau, M.J., Cryptanalysis of a Diophantine equation oriented public-key cryptosystem, IEEE transactions on computers, 46, 511-512, (1997) · Zbl 1361.94042
[13] Lenstra, A.K.; Lenstra, H.W.; Lovász, L., Factoring polynomials with rational coefficients, Mathematische annualen, 261, 513-534, (1982) · Zbl 0488.12001
[14] Lin, C.H.; Chang, C.C.; Lee, R.C.T., A new public-key cipher system based upon the Diophantine equations, IEEE transactions on computers, 44, 1, 13-19, (1995) · Zbl 1061.68530
[15] Merkle, R.C.; Hellman, M.E., Hiding information and signatures in trapdoor knapsacks, IEEE transactions on information theory, 24, 525-530, (1978)
[16] Morii, M.; Kasahara, M., New public-key cryptosystem using discrete logarithm over GF(p), IEICE transactions, J71-D, 2, 448-453, (1988)
[17] Naccache, D.; Stern, J., A new public-key cryptosystem, (), 27-36
[18] Nguyen, P.; Stern, J., Adapting density attacks to low-weight knapsacks, (), 41-58 · Zbl 1142.94354
[19] Nguyen, P.; Stern, J., Merkle – hellman revisited: a cryptanalysis of the qu-vanstone cryptosystem based on group factorizations, (), 198-212 · Zbl 0882.94025
[20] Niemi, V., A new trapdoor in knapsacks, (), 405-411 · Zbl 0825.94176
[21] Odlyzko, A.M., The rise and fall of knapsack cryptosystems, (), 75-88 · Zbl 0733.94012
[22] Okamoto, T.; Tanaka, K.; Uchiyama, S., Quantum public-key cryptosystems, (), 147-165 · Zbl 0995.94535
[23] Omura, K.; Tanaka, K., Density attack to the knapsack cryptosystems with enumerative source encoding, IEICE transaction on fundamentals, E84-A, 1, 1564-1569, (2001)
[24] Orton, G., A multiple-iterated trapdoor for dense compact knapsacks, (), 112-130 · Zbl 1126.94334
[25] Pieprzyk, J.P., On public-key cryptosystems built using polynomial rings, (), 73-80
[26] Qu, M.; Vanstone, St.A., The knapsack problem in cryptography, (), 291-308 · Zbl 0834.94014
[27] Shamir, A., A polynomial-time algorithm for breaking the basic merkle – hellman cryptosystem, IEEE transactions on information theory, 30, 699-704, (1984) · Zbl 0552.94007
[28] Shamir, A.; Zippel, R.E., On the security of the merkle – hellman cryptographic scheme, IEEE transactions on information theory, 26, 339-340, (1980) · Zbl 0431.94031
[29] Su, P.C.; Lu, E.; Chang, H., A knapsack public-key cryptosystem based on elliptic curve discrete logarithm, Applied mathematics and computation, 168, 1, 40-46, (2005) · Zbl 1076.94014
[30] Vaudenay, S., Cryptanalysis of the chor – rivest cryptosystem, Journal of cryptology, 14, 87-100, (2001) · Zbl 0979.94037
[31] Wang, B.; Hu, Y., Diophantine approximation attack on a fast public-key cryptosystem, (), 25-32
[32] Wang, B.; Hu, Y., Public-key cryptosystem based on two cryptographic assumptions, IEE Proceedings of communications, 152, 6, 861-865, (2005)
[33] Webb, W.A., A public-key cryptosystem based on complementing sets, Cryptologia, XVI, 2, 177-181, (1992) · Zbl 0752.94010
[34] Yasinsac, A.; Childs, J., Formal analysis of modern security protocols, Information sciences, 171, 1-3, 4, 189-211, (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.