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
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和Hellman提出了一個輕型的公開金鑰加密系統:背包加密演算法,該系統的安全性是基於子集合加總問題,這個問題,已經被証實是一個NP-hard問題。因此,背包問題不是在多項式時間內可解決之問題,但由於背包系統的密度不夠高再加上它是一個絕對遞增數列,已經有人提出低密度攻擊可以破解密度低於0.9408的背包加密系統。 在這篇論文中,我們提出了一種新的背包加密系統,首先利用明文編碼的方式,先將原始長度為u的明文轉換成長度為n的編碼後再進行加密,此加密系統的密文為兩個非絕對遞增數列的乘積再加上一個絕對遞增數列的和。 經由我們的分析,這樣的架構可以提高背包系統的密度,也可以減少公開金鑰的長度,藉以提升加解密的速度。因此我們提出的背包加密系統不但在運算效能上比原本好,在安全性的分析中也能抵抗低密度攻擊(LDA)、低權重攻擊(LWA)、Shamir攻擊等攻擊。
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:通訊工程研究所



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