Please use this identifier to cite or link to this item:
標題: 一個基於三個背包和具有明文編碼的新型加密系統
A New Cryptosystem Based on Three Knapsacks with Plaintext Encoding
作者: 黃耀樟
Haung, Yao-Zhang
關鍵字: 背包加密系統;knapsack public-key cryptosystem;子集合加總問題;低密度攻擊;明文編碼;Shamir攻擊;low density attack;subset sum problem;plaintext encoding;Shamir attack
出版社: 通訊工程研究所
引用: [1] R. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM, vol.21, no.2,pp. 120-126, 1978. [2] N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation, vol.48, pp.203–209, 1987. [3] W. P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, IEEE Computer Society Press, pp.124-134, 1994. [4] R. C. Merkle and M. E. Hellman, “Hiding Information and Signatures in Trapdoor Knapsacks,” IEEE Trans. Inf. Theory, IT-24(5), pp.525–530, 1978. [5] A. Shamir, “A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem,” Proc. Crypto’82, LNCS, pp.279–288, Springer-Verlag, Berlin, 1982. [6] L. M. Adleman, On breaking the titrated Merkle-Hellman public-key cryptosystem, Plenum Press. Crypto’82, pp.303–308. 1982. [7] J. C. Lagarias and A. M. Odlyzko, Solving Low Density Subset Sum Problems, J. Assoc. Comp. Math., vol.32, pp.229–246, Preliminary version in Proc. 24th IEEE, 1985. [8] M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr, “An improved low-density subset sum algorithm,” Advances in Cryptology Proc. EUROCRYPT’91, LNCS, vol.547, pp.54–67. Springer-Verlag, Berlin, 1991. [9] W.Diffie and M. E. Hellman, “New directions in cryptography”, IEEE Trans, Inform. Theory, vol.IT-22, no.6, pp.644-654 1976. [10] M. Kasahara and Y. Murakami, “New Public Key Cryptosystems and the Application,” Technical report of IEICE, pp.21-28, 1999. [11] T. Hattori, Y. Murakami and M. Kasahara: “Notes on security of SHP cryptosystems,” The 24th Symposium on Information Theory and Its Applications, pp.351–354, 2001. [12] T. Nasako and Y. Murakami: “A high-density knapsack cryptosystem using combined trapdoor,” Trans. the Japan Society for Industrial and Applied Mathematics, Vol.16, No.4, pp.519-605, 2006. [13] T. DOUZONO ,T. NASAKO,Y. MURAKAMI:” Effectiveness of Plaintext Encoding in Knapsack PKC “International Symposium on Information Theory and its Applications, ISITA2008, 2008 [14] K. Kobayashi, K. Tadaki, M. Kasahara and S. Tsujii: A Knapsack Cryptosystem Based on Multiple Knapsacks, International Symposium on Information Theory and its Applications, ISITA2010, 2010 [15] K. Omura, K. Tanaka: Density Attack to Knapsack Cryptosystems with Enumerative Source Encoding. IEICE Transactions on Fundamentals 87-A(6), 1564–1569(2004) [16] T. Izu, J. Kogure, T. Koshiba, T. Shimoyama: Low-Density Attack Revisited. Designs, Codes and Cryptography 43(1), 47–59 (2007) (Preliminary version appeared in 2004) [17] Y. Murakami and T. Nasako:” A knapsack public-key cryptosystem with cyclic code over GF(2)” JSIAM Letters Vol.2, pp.29–32, 2010 [18] M.K. Lai, Knapsack cryptosystems: the past and the future, online manuscript, 2003, pp. 1–21. [19] H. Shimizu, “Lattice basis reduction and its application,” Presented at the 6th JANT meeting, The Japan Society for Industrial and Applied Mathematics, January 26, 2002, Ochanomizu University, Tokyo, Japan. In Japanese. Available at URL:

Merkle and Hellman proposed a knapsack cryptosystem, which is a light-weight public key cryptosystem (PKC). The knapsack PKC is based on the subset sum problem which is NP-hard, but it is known to be vulnerable to low density attack (LDA) because the density is not sufficiently high.
We proposed a modified knapsack cryptosystem using three knapsacks with plaintext encoding to enhance the security of Knapsack cryptosystem. The ciphertext is composed by multiplying two non-superincresing knapsacks and then adding to a superincresing knapsack. In the first instance we encode a plaintext before encrypting. Then the ciphertext is composed by multiplying two non-superincresing knapsacks and then adding to a superincresing knapsack. Using plaintext encoding method can not only increase the density of the knapsack, but also reduce the size of the public key. Our proposed scheme can be secure against the low density attack because using the plaintext encoding the density can be made as large as our desire. Due to the structure of the ciphertext, our knapsack cryptosystem is thought to be secure against all existing attacks, i.e., Shamir attack.
其他識別: U0005-1608201216264700
Appears in Collections:通訊工程研究所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.