このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

  • 追加された行はこの色です。
  • 削除された行はこの色です。
*目次 [#z4f7f52c]

#contents

*宣伝 [#n45d43a0]

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。~

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

[[&ref(http://s-akademeia.sakura.ne.jp/main/books/cipher/img/cover_mini.jpg,nolink,『暗号技術のすべて』宣伝サイト);>http://s-akademeia.sakura.ne.jp/main/books/cipher/]]

 興味がある方は[[宣伝サイト:http://s-akademeia.sakura.ne.jp/main/books/cipher/]]を参照してください。[[Amazon:https://www.amazon.co.jp/dp/4798148814/securityakade-22]]でも発売中です。


*CDH問題とCDH仮定 [#x527d239]

 Gを素数位数qの巡回群、gをGの原始元、x,yを(&mimetex("\mathbb{Z}_q^*");上の)ランダム値とする。このとき、(G,q,g,gSUP{x};,gSUP{y};)が与えられたときに、gSUP{xy};を求める問題を''CDH(Computational Diffie-Hellman)問題''という。

 そして、CDH問題を解く効率的なアルゴリズムが存在しないという仮定のことを、''CDH仮定''と呼ぶ。


*各仮定との関係 [#u723d2b1]

 CDH仮定と他の仮定との関係は次のようになる。不等号は仮定の強弱を意味している。

[[DL仮定]]<CDH仮定<[[DDH仮定]]

 なお、暗号に使われているほとんどの群においてはCDH問題とDL問題は計算理論の意味において等価だと信じられていいる。「計算理論の意味のおいて等価」とは、「一方の問題から他方の問題への多項式時間による還元が可能であり、逆もまた同様にできる」という意味である。