A New Knapsack Public-Key Cryptosystem Based on Permutation Combination Algorithm

Authors: Min-Shiang Hwang, Cheng-Chi Lee, Shiang-Feng Tzeng

Abstract:

A new secure knapsack cryptosystem based on the Merkle-Hellman public key cryptosystem will be proposed in this paper. Although it is common sense that when the density is low, the knapsack cryptosystem turns vulnerable to the low-density attack. The density d of a secure knapsack cryptosystem must be larger than 0.9408 to avoid low-density attack. In this paper, we investigate a new Permutation Combination Algorithm. By exploiting this algorithm, we shall propose a novel knapsack public-key cryptosystem. Our proposed scheme can enjoy a high density to avoid the low-density attack. The density d can also exceed 0.9408 to avoid the low-density attack.

Keywords: Public key, Knapsack problem, Knapsack cryptosystem, low-density attack.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330019

References:

[1] L. Adleman. ÔÇÿÔÇÿOn breaking generalized knapsack public key cryptosystems,". Internal Rep. TR-83-207, Univ. Southern Calif., Los Angeles, Mar 1983.
[2] C. C. Chang and M. S. Hwang, "Parallel computation of the generating keys for RSA cryptosystems," IEE Electronics Letters, vol. 32, no. 15, pp. 1365-1366, 1996.
[3] BENNY CHOR and RONALD L. RIVEST, "A knapsack-type public key cryptosystem based on arithmetic in finite fields," IEEE Trans. Inform. Theory, vol. 34, pp. 901-909, September 1988.
[4] M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, and C. P. Schnorr, "An improved low-density subset sum algorithm," in Advances in Cryptology, EUROCRYPT-91, pp. 54-67, Lecture Notes in Computer Science, Vol. 547, 1991.
[5] Y. G. Desmedt, J. P. Vandewalle, and R. M. Govarets, "A critical analysis of the security of knapsack public-key algorithms," IEEE Trans. Inform. Theory, vol. IT-30, pp. 601-611, July 1984.
[6] W. Diffie and M. E. Hellman, "New directions in cryptography," IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, Nov 1976.
[7] T. ElGamal, "A public-key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory, vol. IT-31, pp. 469-472, July 1985.
[8] M. S. Hwang, C. C. Chang, and K. F. Hwang, "An ElGamal-like cryptosystem for enciphering large messages," IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 2, 2002.
[9] M. S. Hwang, and C. C. Lee, "Research issues and challenges for multiple digital signatures," International Journal of Network Security, vol. 1, no. 1, pp. 1-7, 2005.
[10] M. S. Hwang, Eric J. L. Lu, and I. C. Lin, "A practical (t, n) threshold proxy signature scheme based on the RSA cryptosystem," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 5, pp. 1-9, 2003.
[11] Kiyoko Katayanagi, Yasuyuki Murakami, and Masao Kasahara, "A new product-sum public-key cryptosystem using message extension," IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, Special Section on Cryptography and Information Security, vol. E84-A, pp. 2482-2487, October 2001.
[12] J. C. Lagarias and A. M. Odlyzko, "Solving low-density subset sum problems," in Proceedings of 24rd Annu. Symp. Foundations of comput. Sci., pp. 1-10, 1983.
[13] R. Merkle and M. E. Hellman, "Hiding information and signatures in trapdoor knapsack," IEEE Trans. Inform. Theory, vol. IT-24, pp. 525-530, Sept 1978.
[14] R. Michael, and S. David, "Computers and Intractability: A guide to the theory of NP-completeness," W. H. Freeman & Co., San Francisco, 1979.
[15] M.O. Rabin, "Digitalized signatures and public-key functions as intractable as factorization," Technical Report, MIT/LCS/TR212, MIT Lab., Computer Science Cambridge, MA, USA, January 1979.
[16] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key cryptosystems," Communications of the ACM, vol. 21, pp. 120-126, Feb. 1978.
[17] A. Shamir. ÔÇÿÔÇÿA fast signature scheme,". Laboratory for Computer Science Report RM-107, MIT, Cambridge, MA, july 1978.
[18] H. Shimizu. ÔÇÿÔÇÿOn the security of kasahara-murakami public key cryptosystem,". tech. rep., IEICE Technical Report., Los Angeles, Nov. 1999.
[19] M. Sramka, "Cryptanalysis of the Cryptosystem Based on DLP r =a ab b ," International Journal of Network Security, vol. 6, no. 1, pp. 80-81, 2008.
[20] P. C. Su, E. H. Lu, and K. C. Henry, "A knapsack public-key cryptosystem based on elliptic curve discrete logarithm," Applied Mathematics and Computation, vol. 168, no. 1, pp. 40-46, 2005.
[21] Daisuke Suzuki, Yasuyuki Murakami, Ryuichi Sakai, and Masao Kasahara, "A new product-sum type public key cryptosystem based on reduced bases," IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences, Special Section on Cryptography and Information Security, vol. E84-A, pp. 326-330, January 2001.
[22] B. Wang, Q. Wu, and Y. Hu, "A knapsack-based probabilistic encryption scheme," Information Sciences, vol. 177, no. 19, pp. 3981-3994, 2007.