Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem

Content Provider	CiteSeerX
Author	Murakami, Yasuyuki Nasako, Takeshi
Abstract	Abstract. The realization of the quantum computer will enable to break publickey 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 lowdensity 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.
File Format	PDF
Access Restriction	Open
Subject Keyword	Quantum Computer Subset Sum Problem Modular Transformation Lowdensity Attack Chinese Remainder Theorem Large Dimension New Class Practical Low-density Attack Publickey Cryptosystems Np-hard Problem Polynomial Time Knapsack Scheme Knapsack Cryptosystem High Density Secret Key Discrete Logarithm Problem
Content Type	Text
Resource Type	Article