New Trapdoors in Knapsack Public-Key Cryptosystem with Two Sequences as Public Key

摘要

ナップザック公開鍵暗号について従来数多くの提案がなされている.しかし，その多くはShamirの攻撃あるいは低密度攻撃等に耐性がないという問題を有している.筆者らはMerkleとHellmanによって提案された超増加数列を用いる方式をベースにして，2系列の公開鍵を用いるナップザック暗号を提案していた.本稿では，筆者らが既に提案していた方式をベースにして，超増加数列をトラップドアに用いた2系列の公開鍵を用いるナップザック暗号において新たなトラップドアを提案する.%Present authors proposed a new class of knasack PKC (KMN PKC) which uses two sequences as the public key. KMN PKC uses a super-increasing sequence as the trapdoor based on Merkle-Hellman knapsack cryp­tosystem. In this paper, we propose new trapdoors in KMN type knapsack scheme in which two sequences are used as the public key. We also propose the simple class of the proposed scheme. We show that the proposed scheme can be secure against the low-density attack because the density can be made as large as one desires. We also discuss the security of the secret key of the proposed scheme.