• 追加された行はこの色です。
  • 削除された行はこの色です。
  • DDH仮定 へ行く。

*目次 [#k03fb3e7]

#contents

*宣伝 [#ucb5031d]

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

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

[[&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]]でも発売中です。


*DDH問題とDDH仮定 [#f7692821]

 CDH問題に似た問題としてDDH問題と呼ばれる問題を考えることができる。

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

 先ほどのCDH問題ではgSUP{xy};の値を完全に求めることであった。一方、DDH問題では、gSUP{xy};の値の部分情報、つまり1ビットさえ求めればよいことを意味する。よって、明らかにCDH問題よりもDDH問題の方が解くことが容易な問題を意味していることがわかる。

 このDDH問題は識別不可能という表現を使って、言い換えると次のようになる。 Gを素数位数qの巡回群、gをGの原始元、x,y,zを(&mimetex("\mathbb{Z}_q^*");上の)ランダム値とする。このとき、(G,q,g,gSUP{x};,gSUP{y};,gSUP{xy};)と(G,q,g,gSUP{x};,gSUP{y};,gSUP{z};)を識別する問題のことを''DDH問題''という。

 一般的に後者の定義の方が表現しやすいので使われている。しかし、慣れるまでは意味的は全射の方がわかりやすいのではないだろうか。

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