低Hamming重み標数の素体上における数体篩法の計算機実験

摘要

DSAやDiffie-Hellman鍵共有は，素体GF（p）上の離散対数問題の困難性を安全性の根拠としているため，GF（p）上の離散対数問題の困難性を評価することは，DSAやDiffie-Hellman鍵共有などの安全性を考察する上で重要である．GF（p）上の離散対数問題に対する漸近的に最速な解読アルゴリズムとして，数体節法が知られている．離散対数問題に対する数体解法はGordonによって初めて提案され，その後，SchirokauerやJoux-Lercierが改良した．数体解法の実行時間は選択される代数体を定義する多項式により大きく影響されることが知られており，Joux-LercierはGaussian Integer Methodを一般化した多項式の選択方法を提案した．一方，一般的な素数pではなく，low weightなp（少ない個数の±2~eの和で表されるp）に対して，Schirokauerは従来の数体筋法よりも計算量が小さくなるような多項式の選択方法を提案した．本稿では，100bits及び110bitsのlow weightなpに対してJoux-LercierとSchirokauer の多項式選択法を実装し，実行時間の比較を行った．