ナップザック暗号の鍵の性質と低密度攻撃耐性の関係および攻撃法改善の提案

摘要

Merkle-Hellmanのナップザック暗号は，Lagarias-Odlyzkoの低密度攻撃（LO法）に対して弱く，高い確率で解読されることが知られている．本報告で次の2つのことを行った．（1）ナップザック暗号の鍵の性質とLO法による解読率の関係を計算機実験により明らかにする．（2）解読率を高めるために，使用基底のベクトルの置換，LO法の反復適用などを提案しその有効性を検証する．