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

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

#contents

*宣伝 [#o66ea960]

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

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

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


*安全性 [#vfa519c0]

**DDH仮定、ハッシュ関数がスムースの下でSS [#ra42d56a]

[定理]~
Hashed ElGamal暗号は、DDH仮定とハッシュ関数がスムースであるという下で、SSである。~
Hashed ElGamal暗号は、[[DDH仮定]]とハッシュ関数がスムースであるという下でSSである。~
ちなみに、スムースというのはハッシュ値が十分ランダムネスであること。

[証明](Sequences of Games)

∀A:攻撃アルゴリズム(Adversary)

[1]Game0

 Game0におけるAの動作は次の通り。

#img(http://s-akademeia.sakura.ne.jp/main/image8/game0.jpg)
#img(,clear)

SSUB{0};=SUP{def};the event that b=^b in Game0

[2]Game1

 Game1におけるAの動作は次の通り。

#img(http://s-akademeia.sakura.ne.jp/main/image8/game1.jpg)
#img(,clear)

SSUB{1};=SUP{def};the event that b=^b in Game1

 次のように動作するアルゴリズムD(α,β,γ)を作る。

#img(http://s-akademeia.sakura.ne.jp/main/image8/game2-2.jpg)
#img(,clear)

 εSUB{ddh};(D)というのは「DDH仮定の下で」という意味。

∴|Pr[SSUB{0};]-Pr[SSUB{1};]|:neg

[3]Game2

 Game2におけるAの動作は次の通り。

#img(http://s-akademeia.sakura.ne.jp/main/image8/game3.jpg)
#img(,clear)

SSUB{2};=SUP{def};the event that b=^b in Game2

 次のように動作するアルゴリズムD'(k,h)を作る。

#img(http://s-akademeia.sakura.ne.jp/main/image8/game3-2.jpg)
#img(,clear)

#img(http://s-akademeia.sakura.ne.jp/main/image8/game3-3.gif)
#img(,clear)

 εSUB{es};(D')はエントロピースムーシングという意味。

∴|Pr[SSUB{1};]-Pr[SSUB{2};]|:neg

 さらに、Pr[SSUB{2};]=1/2である。

したがって、[1][2][3]より、

|Pr[SSUB{0};]-Pr[SSUB{2};]|~
≦|Pr[SSUB{0};]-Pr[SSUB{1};]|+|Pr[SSUB{1};]-Pr[SSUB{2};]|~
=εSUB{ddh};+εSUB{e};s~
=εSUB{ddh};+εSUB{es};~
=ε (Q.E.D.)

*参考文献 [#cc64dad7]

-「Sequences of Games:A Tool for Taming Complexity in Security Proofs」