安全性証明

イントロダクションが予想以上にサクサク終わってしまって、
予習軽くやっただけで解説準備まだ終わってないのに当たる。
最低限予習だけやっといてよかったけど、それでもボロボロ。
CDH、DDH、DLに関する説明をしつつ教えてもらって理解できた。
やたー、ということで軽くおさらい。

Zp*

えーと、Zpが法をpとする数の集合で元が{0,…,p-1}で、
これに*をつけることによって元のうちpと素な元だけを用いることを意味する。
たとえばpが15なら元は{1,2,4,7,8,11,13,14}の八つになる。
資料では以下の式はこのZp*の元の内で定義されている。

Decision Diffie Hellman(DDH)

えーっと、(g,g^a,g^b,Z)を与えられたとき、g^ab=Zかどうかを確かめる問題。

Computational Diffie Hellman(CDH)

これは(g,g^a,g^b)を与えられたときg^abを求める問題。

離散対数問題(DL)

g^a=xとなるときaの値を求める問題。
　
間違いがあれば指摘してください。