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

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

著者

• MURAKAMI Yasuyuki

  Osaka Electoro-Communication University

• HAMASHO Shinsuke

  Osaka Electro-Communication University

関連論文

• A Further Improvement on Implementation of Diffie-Hellman Type ID-NIKS
• Security of a Class of Knapsack Public-Key Cryptosystems against Low-Density Attack
• A New ID-Based Key Sharing Scheme based on DH Problem over Composite Modulus
• A New Trapdoor in Modular Knapsack Public-Key Cryptosystem
• Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem
• A Note on Security of Public-Key Cryptosystem Provably as Secure as Subset Sum Problem

スポンサーリンク