IEICE Trans - A Note on Security of Public-Key Cryptosystem Provably as Secure as Subset Sum Problem

A Note on Security of Public-Key Cryptosystem Provably as Secure as Subset Sum Problem

Shinsuke HAMASHO  Yasuyuki MURAKAMI

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.1   pp.298-299
Publication Date: 2014/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.298
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Cryptography and Information Security)
Category:
Keyword:
subset sum problem,  provable security,  attack,

Full Text: PDF>>

Summary:
In TCC2010, Lyubashevsky et al. proposed a public-key cryptosystem provably as secure as subset sum problem which will be referred to as LPS scheme. This fact gave an impact at the study of the knapsack schemes. However, this scheme seems to be very weak in practical use. In this paper, we propose an attack against LPS scheme by converting from the problem of computing the secret key into a low-density subset sum problem. Moreover, we confirm the effectiveness of the proposed attack with the computer experiment by using the conventional low-density attack proposed Coster et al. This result means that even a scheme with the provable security does not always have the practical security.