ペアリング暗号はもう使えないのか？
Takuya Hayashi
@Tak884
まず、「ペアリング暗号はもう使えないのか？」について。そんなことはなく、適切なパラメータを使用すれば、安全に利用することができます。今回の成果は「ペアリング暗号のあるパラメータにおいて攻撃に成功した」という内容です。
2012-06-20 16:25:46
Takuya Hayashi
@Tak884
ペアリング暗号というのはいわゆる総称で、その中で利用するペアリングという写像には色々な種類があります。今回の成果は、その中の「有限体GF(3^n)上のηTペアリング」というペアリングを利用したペアリング暗号において、n=97というパラメータの攻撃に成功したというものです。
2012-06-20 16:28:26
Takuya Hayashi
@Tak884
なので、その他のペアリング、例えばBN曲線上のペアリングだとかを利用したペアリング暗号は、この攻撃方法では攻撃できません。
2012-06-20 16:31:02
Takuya Hayashi
@Tak884
@zusanzusan 今回の攻撃は標数の小さな有限体に限定された攻撃方法なので、標数の大きな有限体に対しての攻撃は原理的に難しいです。
2012-06-20 16:38:47
杜選な研究者
@zusanzusan
@Tak884 あーそうか、今回はソルバー部分が関数体篩法だから、小標数にしか適用できないのですね。BNに適用するには数体篩法が必要ですからね。今回の公開資料では、ECDLPを有限体のDLPに埋め込んで解くというフレームになっていたので、フレーム自体の有効性かと誤解していました。
2012-06-20 16:42:29
Takuya Hayashi
@Tak884
@zusanzusan そうです。GF(3^97)のECDLPは雑に言うと2^75くらいの計算量が必要ですが、ペアリングで飛ばした先のGF(3^6・97)のDLPは2^53程度の計算量で済むことが分かった（ISPEC2012で発表済）ので、こちらを攻撃しました。
2012-06-20 16:45:23
Takuya Hayashi
@Tak884
さらに付け加えると、さきほどの「有限体GF(3^n)上のηTペアリング」において、nが暗号の鍵長に直接影響するのですが、nを97よりも大きく、より正確には n>193 程度をとれば、「スーパーコンピュータKを１年間利用しても攻撃できない」レベルの安全性を確保することができます。
2012-06-20 16:35:18ペアリング暗号はRSA暗号よりも弱いのか？
Takuya Hayashi
@Tak884
今回攻撃した「GF(3^n)上のηTペアリングを利用したペアリング暗号」の安全性は「n=97（923ビット）」においては、RSA1024ビットの安全性には届いておらず、RSA1024ビットと同程度の安全性を確保するには「n=193程度（1836ビット程度）」とすることが必要です。
2012-06-20 17:20:32
M. Tibouchi
@mtibouchi
@Tak884 横から失礼します。n=97が923ビットの鍵長になるのもちょっと誤解を招く言い方ではないかと。ほとんどの場合は、鍵が群の元（楕円曲線の点）であるので鍵長は154ビットな訳ですね。実はペアリング値も圧縮されるのでそちらも実用的な観点では923ビットとは言えないかと。
2012-06-20 17:38:52
Takuya Hayashi
@Tak884
@mtibouchi ありがとうございます。そうですね。鍵長は154ビット（or 258?）で今回攻撃をしたのはペアリング先の「位数923ビットの有限体GF(3^6・97)における素数位数151ビットのDLP」です。
2012-06-20 17:42:58
Takuya Hayashi
@Tak884
ではまず、ECC160とRSA1024がなぜ同程度の安全性なのかについて述べて、そこから今回の攻撃の成果に話しを伸ばしてみます。
2012-06-20 17:29:54
Takuya Hayashi
@Tak884
「RSA1024の攻撃」≒「512ビット素数×512ビット素数=1024ビット合成数の素因数分解」の現最速の計算法は数体篩法で、1024ビット合成数に対しては2^80程度の計算量が必要です。（これはかなり雑な見積もりで、最近は計算実験などによる精密な評価が行われています。）
2012-06-20 18:01:47
Takuya Hayashi
@Tak884
楕円曲線暗号の攻撃は「楕円曲線上定義される素数位数群上の離散対数問題（ECDLP）」を計算することで攻撃することができます。これの現最速の攻撃方法はPollardのρ法で、160ビット素数位数に対しては2^80程度の計算量になります。
2012-06-20 18:03:58
Takuya Hayashi
@Tak884
つまり、「RSA1024の攻撃計算量」 ≒ 「160ビット楕円曲線暗号の攻撃計算量」なので、安全性は同じくらいであると考えられています。付け加えると、計算量2^80は現時点では、現実的な時間での計算は困難であると考えられています。
2012-06-20 18:05:50
Takuya Hayashi
@Tak884
続き。さて、今回攻撃したペアリング暗号は二つの攻撃手法を考えることができます。ひとつは、ペアリングの入力である楕円曲線におけるECDLPを解く方法。この場合は楕円曲線暗号の攻撃と同じ方法を利用します。もうひとつはペアリングの出力である有限体におけるDLPを解く方法。
2012-06-20 18:29:16
Takuya Hayashi
@Tak884
有限体上のDLPには有限体の標数に応じて異なる攻撃方法があります。標数が大きい場合は数体篩法が使われます。RSA暗号の攻撃方法と同じ名前で、中身も計算量もほとんど変わりません。標数が小さい場合は関数対篩法が使われます。こちらも名前が似ていますが、計算量が数体篩法よりも小さいです。
2012-06-20 18:29:44
Takuya Hayashi
@Tak884
今回の攻撃ターゲットに置き換えると、楕円曲線におけるECDLPを解く場合、151ビットのECDLPを解く必要があります。これは計算量が2^75程度なので、2^80と比べると30倍程度簡単ですが、それでも計算は困難です。
2012-06-20 18:30:08