迷袋密碼系統為最早被提出的公鑰密碼系統之一，運算效率高為其最主要優勢。近年來量子運算的研究，使安全性基於因數分解與離散對數的公鑰密碼系統，例如：目前廣泛使用的RSA、ECC等系統，可能面臨瓦解危機，但也因此突顯安全性基於迷袋問題之迷袋密碼系統的重要性。然而，迷袋密碼系統自提出以來，即不斷有攻擊出現，其中，以格狀攻擊的影響最為嚴重，大部分的迷袋密碼系統皆無法抵擋此攻擊。過去的文獻透過理論分析，指出此攻擊可破解公鑰密度低於0.9408的迷袋問題，故提高密度成為迷袋密碼系統設計者努力的方向。而在眾多迷袋密碼系統當中，已知線性平移迷袋密碼系統可產生密度高於0.9408之公鑰，理論上應屬安全，但本論文透過實作格狀攻擊，卻證實此系統仍可被破解。因此，本論文首先分析實作與理論預期不符之原因，並透過大規模實驗，分析攻擊中各項變因對於攻擊困難度的影響，再將此結果應用於設計改良型迷袋密碼系統，使之維持迷袋密碼系統之高運作效率特性，並有效提升抵禦格狀攻擊之能力，且能在量子運算架構下，保有公鑰密碼系統之安全性。

The knapsack problem served as the basis for one of the first viable public-key cryptosystem. Knapsack cryptosystems have the advantages of encryption and decryption speed compared to other public-key cryptosystems. However, security of knapsack cryptosystems has always been a concern. In recent years, research into quantum computing greatly impacted practical public-key cryptosystems constructed on the bases of integer factoring or the discrete logarithm problem, such as RSA and ECC. Interestingly, the knapsack problem remains unaffected by quantum advances. This warrants additional investigation into the resiliency of knapsack. Among all attacks against knapsack, lattice attack is the most critical, and most knapsack cryptosystems cannot prevent it. Coster et al. showed that ciphertexts with public key densities lower than 0.9408 were recoverable using theoretical analysis. Therefore, increasing density became a goal for designing of knapsack cryptosystems.
Linear Shift knapsack cryptosystem can generate public keys with density higher than 0.9408, and in theory, is supposed to be secure. However, we prove the Linear Shift knapsack cryptosystem is unsecure using a lattice attack implementation. In this paper, we explain the apparent difference between practice and theory. Using extensive experiments, we deduce the impact of lattice attack variables on difficulty of the attack, and find that linear shift can increase the difficulty of lattice attack. Based on the findings, we suggest improvements to the security of knapsack cryptosystems, which increases their ability to protect against lattice attack maintaining quick encryption and decryption speed.

[1] L. M. Adleman, "On breaking generalized knapsack public key cryptosystems," in Proc. 15th ACM Symposium on Theory of Computing, pp. 402-412, 1983.
[2] E. F. Brickell, "Solving low density knapsacks," in Proc. Crypto '83, pp. 25-37, 1984.
[3] E. F. Brickell, "Breaking iterated knapsacks," in Proc. Crypto '84, pp. 342-358, 1985.
[4] C. H. Bennett and G. Brassard, "An update on quantum cryptography," in Proc. Crypto '84, pp.475-480, 1985.
[5] C. H. Bennett, G. Brassard, C. Crepeau and M. H. Skubiszewska, "Practical quantum oblivious transfer," in Proc. Crypto '91, LNCS., vol. 576, pp. 351-366, 1992.
[6] G. Brassard and C. Crepeau, "Quantum bit commitment and coin tossing protocols," in Proc. Crypto '90, LNCS., vol. 537, pp. 49-61, 1991.
[7] E. F. Brickell and G. J. Simmons, "A status report on knapsack based public key cryptosystems," in Sandia Nat. Lab. Rep., 1983.
[8] H. Cohen, "A course in computational algebraic number theory," ISBN:0-387-55640-0, Springer-Verlag, 1993.
[9] D. Coppersmith, "Fast evaluation of logarithms in fields of characteristic two," in IEEE Transactions on Information Theory, vol. IT-30, pp.587-594, 1984.
[10] M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr and J. Stern, "Improved low-density subset sum algorithms," in Computational Complexity, vol. 2, pp. 111-128, 1992.
[11] B. Chor and R. L. Rivest, "A knapsack-type public key cryptosystem based on arithmetic in finite fields," in Proc. Crypto '84, LNCS., pp. 54-65, 1985.
[12] C. Crepeau and L. Salvail, "Quantum oblivious mutual identification," in Proc. EUROCRYPT '95, LNCS., vol. 921, pp. 133-146, 1995.
[13] W. Diffie and M. E. Hellman, "New directions in cryptography," in IEEE Transactions on Information Theory, vol. IT-22, pp. 644-654, Nov. 1976.
[14] Y. G. Desmedt, J. P. Vandewalle and R. J. M. Govaerts, "A general public key cryptographic knapsack algorithm based on linear algebra," in IEEE International Symposium on Information Theory, pp. 129-130, 1983.
[15] Y. G. Desmedt, J. P. Vandewalle and R. J. M. Govaerts, "A critical analysis of the security of knapsack public key algorithms," in IEEE Transactions on Information Theory, vol. IT-30, pp. 601-611, 1984.
[16] N. Howgrave-Graham and A. Joux, "New generic algorithms for hard knapsacks," in Proc. EUROCRYPT 2010, LNCS, vol. 6110, pp. 235-256, 2010.
[17] N. Gama and P. Q. Nguyen, "Predicting lattice reduction," in Proc. EUROCRYPT 2008, LNCS., vol. 4965, pp. 31-51, 2008.
[18] J. Hoffstein, J. Pipher and J. H. Silverman, "NTRU: A ring-based public key cryptosystem," in Algorithmic Number Theory, LNCS., vol. 1423, pp. 267-288, 1998.
[19] E. Horowitz and S. Sahni, "Computing partitions with applications to the knapsack problem," in Journal of the ACM, vol. 21, no. 2, pp. 277-292, Apr. 1974.
[20] T. Izu, J. Kogure, T. Koshiba and T. Shimoyama, "Low-density attack revisited," in Designs, Codes and Cryptography, vol. 43(1), pp. 47-59, 2007.
[21] R. M. Karp, "Reducibility among combinatorial problems" in Complexity of Computer Computations, pp. 85-104, 1972.
[22] N. Kunihiro, "New definition of density on knapsack cryptosystems," in Proc. AFRICACRYPT 2008, LNCS., vol. 5023, pp. 156-173, 2008.
[23] C. S. Laih, J. Y. Lee, L. Harn and Y. K. Su, "Linearly shift knapsack public-key cryptosystem," in IEEE Journal on Selected Areas in Communications, vol. 7, no. 4, May 1989.
[24] A. K. Lenstra, H. W. Lenstra and L. Lovasz, "Factoring polynomials with rational coefficients," in Mathematische Annalen, vol. 261, no. 4, pp. 515-534, 1982.
[25] J. C. Lagarias and A. M. Odlyzko, "Solving low density subset sum problems," in Journal of the ACM, vol. 32, pp. 229-246, 1985.
[26] D. Mayers, "Quantum key distribution and string oblivious transfer in noisy channels," in Proc. Crypto '96, LNCS., vol. 1109, pp. 343-357, 1996.
[27] D. Micciancio and S. Goldwasser, "Complexity of lattice problems: A cryptographic perspective," Kluwer Academic Publishers, 2002.
[28] R. Merkle and M. Hellman, "Hiding information and signatures in trapdoor knapsacks," in IEEE Transactions on Information Theory, vol. IT-24, pp. 525-530, Sep. 1978.
[29] J. E. Mazo and A. M. Odlyzko, "Lattice points in high-dimensional spheres," in Monatshefte Fur Mathematik, vol. 110, pp. 47-61, 1990.
[30] P. Q. Nguyen and J. Stern, "The two faces of lattices in cryptology," in Cryptography and Lattices Conference, LNCS., vol. 2146, 2001.
[31] P. Q. Nguyen and J. Stern, "Adapting density attacks to low-weight knapsacks," in Proc. ASIACRYPT 2005, LNCS., vol. 3788, pp. 41-58, 2005.
[32] P. Q. Nguyen and D. Stehle, "Floating-point LLL revisited," in Proc. EUROCRYPT 2005, LNCS., vol. 3494, pp. 215-233, 2005.
[33] A. M. Odlyzko, "Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature system," in IEEE Transactions on Information Theory, vol. IT-30, pp. 594-601, 1984.
[34] A. M. Odlyzko, "The rise and fall of knapsack cryptosystems," in Cryptology and Computational Number Theory, pp. 75-88, 1990.
[35] T. Okamoto, K. Tanaka and S. Uchiyama, "Quantum public-key cryptosystems," in Proc. Crypto '00, 2000.
[36] M. Pohst, "A modification of the LLL-algorithm," in Journal of Symbolic Computation, vol. 44(1), Aug. 1987.
[37] R. C. Pohlig and M. Hellman, "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance," in IEEE Transactions on Information Theory, vol. IT-24, pp.106-110, 1978.
[38] R. Rivest, A. Shamir and L. Adlman, "A method for obtaining digital signatures and public-key cryptosystem," in Communication of the ACM, vol. 21, no. 2, pp. 120-126, Feb. 1978.
[39] A. Shamir, "A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem," in Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 145-152, Nov. 1982.
[40] A. Shamir, "Embedding cryptographic trapdoors in arbitrary knapsack systems," in Information Processing Letters, no. 17, pp. 77-79, Aug. 1983.
[41] P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," in SIAM Journal on Computing, vol. 26, pp. 1484-1509, Oct. 1997.
[42] C. P. Schnorr and M. Euchner, "Lattice basis reduction: improved practical algorithms and solving subset sum problems," in Mathematical Programming, vol. 66, pp. 181-199, 1994.
[43] C. P. Schnorr and H. H. Horner, "Attacking the Chor-Rivest cryptosystem," in Proc. EUROCRYPT '95, LNCS., vol. 921, pp.1-12, 1995.
[44] R. Schroeppel and A. Shamir, "A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems," in 20th Annual IEEE Symposium on Foundations of Computer Science, pp. 328-336, 1979.
[45] A. Shamir and R. E. Zippel, "On the security of the Merkle-Hellman cryptographic scheme," in IEEE Transactions on Information Theory, vol. IT-26, pp. 339-340, May. 1980.
[46] S. Vaudenay, "Cryptanalysis of the Chor-Rivest Cryptosystem," in Journal of Cryptology, vol. 14, pp. 87-100, 2001.
[47] NTL: A Library for doing Number Theory, which is available at http://www.shoup.net/.