A New Knapsack Public-Key Cryptosystem Based on Permutation Combination Algorithm
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:51011", author = "Min-Shiang Hwang and Cheng-Chi Lee and Shiang-Feng Tzeng", title = "A New Knapsack Public-Key Cryptosystem Based on Permutation Combination Algorithm", 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.", volume = "3", number = "9", pages = "2167-6", }
