International Association for Cryptologic Research

International Association
for Cryptologic Research



Affiliation: Osaka Electro-Communication University


Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem
Yasuyuki MURAKAMI 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.
Murakami-Kasahara ID-based Key Sharing Scheme Revisited ---In Comparison with Maurer-Yacobi Schemes---
In Sept.1990, the present authors firstly discussed DLP over composite number and presented an ID-based Key Sharing Scheme referred to as MK1. In 1991, Maurer and Yacobi presented a scheme, referred to as MY, which is similar to our scheme, MK1. Unfortunately the schemes MK1 and MY are not secure. In Dec.1990, the present authors presented a secure ID-based key sharing scheme referred to as MK2. With a rapid progress of computer power for the last 15 years, our proposed scheme would have more chance to be applied practically. Regrettably, it has not been widely known that (i) the schemes MY and MK1 are not secure, (ii) there exists a secure scheme, MK2. In this paper, we shall review MK2 and clarify the difference between MK2 and other schemes from the standpoint of security.


Masao KASAHARA (1)
Takeshi NASAKO (1)