For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Note on Security of Public-Key Cryptosystem Provably as Secure as Subset Sum Problem
Shinsuke HAMASHO Yasuyuki MURAKAMI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2014/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Cryptography and Information Security)
subset sum problem, provable security, attack,
Full Text: PDF(72.3KB)>>
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.