ナップザック暗号における平文の重みと解読率の関係

摘要

密度の低いナップザック暗号は低密度攻撃によって解読されることが知られている．ナップザック暗号において密度は非常に重要な安全性の指標である．2005年NguyenとSternは符号化した平文が低重みな暗号方式に対して，従来の密度に代わる指標として疑似密度を定義した．近年，國廣は従来の密度とNguyenらによる疑似密度を統合することが可能な新たな密度を定義し，CR方式やOTU方式の評価に応用した．國廣の結論から，低重みに符号化してから暗号化する方式に限らず，符号化を行わない従来のナップザック暗号においても平文が低重みであった場合には安全ではないと推察される．従来，ナップザック暗号において弱い平文が存在することは知られていたが，平文の重みが低密度攻撃に対する安全性に与える影響については必ずしも明らかではなかった．本稿では，代表的なトラップドアである超増加性および偶奇性を例に，平文のハミング重みを変化させて低密度攻撃を行った際の解読率について調査する．