乱数系列を秘密鍵とする論理積を用いるナップザック暗号

摘要

量子コンピュータにより，素因数分解問題·離散対数問題·楕円離散対数問題を多項式時間で解けることが証明された．ナップザック暗号は，NP困難な部分和問題を安全性の根拠とするため，量子コンピュータに対抗し得る公開鍵暗号の一つとして期待されている．筆者らは，符号化率を低くすることにより，秘密鍵に乱数を利用することができるナップザック暗号を提案していた．長尾，森井らによりいくつかの方式が部分和問題の本来の解ではない別解から解読可能であることが示されたが，その後，筆者らは，別解攻撃に安全な方式として，四系列の乱数を使用する方式（MHK4）及び三系列方式（MHK3）を提案した．前者は論理積（AND），後者は排他的論理和（XOR）を用いており，両者の関係は必ずしも明らかではなかった．本論文ではANDを利用した多系列のナップザック暗号を提案し，MHK3を多系列のXOR利用方式に一般化して再定義することにより，AND利用方式とXOR利用方式の関係，及び，AND利用方式とMHK4の関係を明らかにする．その結果，XOR方式がすべての基本方式であることを示す．