Cryptology ePrint Archive: Report 2007/107
Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem
Yasuyuki MURAKAMI, Takeshi NASAKO
Abstract: 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.
Category / Keywords: public-key cryptography / knapsack public-key cryptosystem, subset sum problem, low-density attack, Chinese remainder theorem
Publication Info: public-key cryptography
Date: received 23 Mar 2007
Contact author: yasuyuki at isc osakac ac jp
Available format(s): PDF | BibTeX Citation
Version: 20070326:072112 (All versions of this report)
Short URL: ia.cr/2007/107
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]