Paper 2007/107

Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem

Yasuyuki MURAKAMI and Takeshi NASAKO


The realization of the quantum computer will enable to break public-key cryptosystems based on factoring problem and discrete logarithm problem. It is considered that even the quantum computer can not solve NP-hard problem in a polynomial time. The subset sum problem is known to be NP-hard. Merkle and Hellman proposed a knapsack cryptosystem using the subset sum problem. However, it was broken by Shamir or Adleman because there exist the linearity of the modular transformation and the specialty in the secret keys. It is also broken with the low-density attack because the density is not sufficiently high. In this paper, we propose a new class of knapsack scheme without modular transformation. The specialty and the linearity can be avoidable by using the Chinese remainder theorem as the trapdoor. The proposed scheme has a high density and a large dimension to be sufficiently secure against a practical low-density attack.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. public-key cryptography
knapsack public-key cryptosystemsubset sum problemlow-density attackChinese remainder theorem
Contact author(s)
yasuyuki @ isc osakac ac jp
2007-03-26: received
Short URL
Creative Commons Attribution


      author = {Yasuyuki MURAKAMI and Takeshi NASAKO},
      title = {Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem},
      howpublished = {Cryptology ePrint Archive, Paper 2007/107},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.