小さな標数の有限体上の離散対数問題の困難性に関する考察

点击翻译按钮获取中文摘要

新たな公開鍵暗号方式の一つであるペアリング暗号では、従来の公開鍵暗号では実現困難であったIDベース暗号などの利便性の高い暗号プロトコルが構成可能である。一方、新たな方式であるため、RSA暗号などの既存の公開鍵暗号と比較して安全性解析は進んでいない。本研究では、ペアリング暗号の安全性に関わる計算問題の一つであるGF(3^6n)上の離散対数問題の計算困難性の解析を行うために、この計算問題の漸近的に最高速なアルゴリズムである関数体箭法について、詳細な計算量解析や実装実験による実計算時間の見積もりを行う。本年度では、ペアリング暗号の実装で利用されるパラメータの一つであるn=97について、GF(3^6・97)上の離散対数問題の計算を行うことによりペアリング暗号の解読を行い、さらに大きなパラメータ(n=163,193など)における解読計算量の見積もりを行った。結果、パラメータn=97においては、Core 2 Quad,XeonなどのCPU 252コアを利用して148.2日の計算により解読に成功した。この解読計算量は、Xeon CPUにおいて2^62.9クロックサイクル程度の計算量に相当する。また、この結果からn=163では2^78.3クロックサイクル、n=193では2^82.0クロックサイクル、n=313では2^100.2クロックサイクル、n=509では2^121.5クロックサイクル程度の計算量が必要であると見積もることができ、n=193が現状安全であるとされている80ビットセキュリティを有すると評価できることを示した。