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

摘要

The density is a very important parameter in knapsack public-key cryptosystems. It is known that the knapsack cryptosystem is broken with the low-density attack when the density is low. In 2005, Nguyen and Stern introduced the pseudo-density instead of the conventional density in order to evaluate CR and OTU cryptosystems. Recently, Kunihiro introduced a new density in order to unify the conventional density and the pseudo-density. From Kunihiro's result, we can guess that the conventional knapsack PKC is vulnerable to the low-density attack when the weight of the plaintext is low. In this paper, we investigate the relationship between the weight of plaintext and successful attacks in conventional knapsack cryptosystems.%密度の低いナップザック暗号は低密度攻撃によって解読されることが知られている．ナップザック暗号において密度は非常に重要な安全性の指標である．2005 年 Nguyen と Stern は符号化した平文が低垂みな暗号方式に対して，従来の密度に代わる指標として疑似密度を定義した．近年，国展は従来の密度と Nguyen らによる疑似密度を統合することが可能な新たな密度を定義し，CR 方式や OTU 方式の評価に応用した．國廣の結論から，低重みに符号化してから暗号化する方式に限らず，符号化を行わない従来のナップザック暗号においても平文が低重みであった場合には安全ではないと推察される．従来，ナップザック暗号において弱い平文が存在することは知られていたが，平文の重みが低密度攻撃に対する安全性に与える影響については必ずしも明らかではなかった．本稿では，代表的なトラップドアである超増加性および偶奇性を例に，平文のハミング重みを変化させて低密度攻撃を行った際の解読率について調査する．