低密度ナップザック暗号

摘要

The knapsack cryptosystem invented by Merkle and Hellman has been proven to be insecure against the low density attack by Lagarias-Odlyzko (LO method). Various high-density variants of knapsack systems were proposed. In this report we propose a knapsach system of low density, and we show it will be promising.%MerkleとHellmanが考案したナップザック暗号は．Lagarias-Odlyzkoの低密度攻撃（LO法）に対して弱いとされる．この攻撃に対抗するため高密度化への工夫が検討されてきた．本報告では低密度ながらこのLO法に耐性を有するナップザック暗号を提案し，計算機実験によりその有効性を検証する．