×

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brickell, E. F., Solving low-density knapsacks, (Chaum, D. C., Advances in Cryptology - CRYPTO’83 (1984), Plenum: Plenum New York), 24-37 · Zbl 1486.94082
[2] Brickell, E. F.; Odlyzko, A. M., Cryptanalysis: a survey of recent results, (Simmons, G. J., Contemporary Cryptology, The Science of Information Integrity (1992), IEEE Press: IEEE Press New York), 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, (Davies, D. W., Advances in Cryptology - EUROCRYPT’91 (LNCS 547) (1991), Springer: Springer Berlin), 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; 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, (Chaum, D.; Rivest, R. L.; Sherman, A. T., Advances in Cryptology - CRYPTO’82 (1983), Plemum: Plemum New York), 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, (Chaum, D. C., Advances in Cryptology - CRYPTO’83 (1984), Plenum: Plenum New York), 3-23 · Zbl 1486.94123
[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; 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) · Zbl 1487.94132
[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, (Fumy, W., Advances in Cryptology - EUROCRYPT’97 (LNCS 1233) (1997), Springer: Springer Berlin), 27-36
[18] Nguyen, P.; Stern, J., Adapting density attacks to low-weight knapsacks, (Roy, B. K., Advances in Cryptology - ASIACRYPT’05 (LNCS 3788) (2005), Springer: Springer Berlin), 41-58 · Zbl 1142.94354
[19] Nguyen, P.; Stern, J., Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations, (Kaliski, B. S., Advances in Cryptology - CRYPTO’97 (LNCS 1294) (1997), Springer: Springer Berlin), 198-212 · Zbl 0882.94025
[20] Niemi, V., A new trapdoor in knapsacks, (Damgård, I. B., Advances in Cryptology - EUROCRYPT’90 (LNCS 473) (1991), Springer: Springer Berlin), 405-411 · Zbl 0825.94176
[21] Odlyzko, A. M., The rise and fall of knapsack cryptosystems, (Pomerance, C., Cryptology and Computational Number Theory. Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42 (1990), American Mathematics Society: American Mathematics Society Providence, RI), 75-88 · Zbl 0733.94012
[22] Okamoto, T.; Tanaka, K.; Uchiyama, S., Quantum public-key cryptosystems, (Bellare, M., Advances in Cryptology - CRYPTO’00 (LNCS 1880) (2000), Springer: Springer Berlin), 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, (De Santis, A., Advances in Cryptology - EUROCRYPT’94 (LNCS 950) (1995), Springer: Springer Berlin), 112-130 · Zbl 1126.94334
[25] Pieprzyk, J. P., On public-key cryptosystems built using polynomial rings, (Pichler, F., Advances in Cryptology - EUROCRYPT’85 (LNCS 219) (1985), Springer: Springer Berlin), 73-80
[26] Qu, M.; Vanstone, St. A., The knapsack problem in cryptography, (Mullen, G. L.; Shiue, P. J., Finite Fields: Theory, Applications, and Algorithms, Contemporary Mathematics, vol. 168 (1994), American Mathematics Society), 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, (Chen, K.; Deng, R. H.; Lai, X.; Zhou, J., The 2nd Information Security Practice and Experience Conference - ISPEC 2006 (LNCS 3903) (2006), Springer: Springer Berlin), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.