Security of a Class of Knapsack Public-Key Cryptosystems against Low-Density Attack

Takeshi NASAKO  Yasuyuki MURAKAMI  Masao KASAHARA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.10   pp.2889-2892
Publication Date: 2008/10/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.10.2889
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)
Category: Cryptography and Information Security
knapsack PKC,  Gaussian integers,  low-density attack,  

Full Text: PDF(117.1KB)>>
Buy this Article

In 2003, Kobayashi et al. proposed a new class of knapsack public-key cryptosystems over Gaussian integer ring. This scheme using two-sequences as the public key. In 2005, Sakamoto and Hayashi proposed an improved version of Kobayashi's scheme. In this paper, we propose the knapsack PKC using l-sequences as the public key and present the low-density attack on it. We have described Schemes R and G for l=2, in which the public keys are constructed over rational integer ring and over Gaussian integer ring, respectively. We discusses on the difference of the security against the low-density attack. We show that the security levels of Schemes R and G differ only slightly.