Density Attack to the Knapsack Cryptosystems with Enumerative Source Encoding

Keiji OMURA  Keisuke TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.6   pp.1564-1569
Publication Date: 2004/06/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
knapsack cryptosystem,  low-density attack,  enumerative source encoding,  LLL algorithm,  

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

We analyze the Lagarias-Odlyzko low-density attack precisely, and show that this low-density attack can be applied to the Chor-Rivest and the Okamoto-Tanaka-Uchiyama cryptosystemes, which are considered to be secure against the low-density attack. According to our analysis, these schemes turn out to be no longer secure against the low-density attack.