利用者:Roget/試訳/Cramer-Shoup暗号

Cramer-Shoup cryptosystem (13:33, 1 November 2008)

Cramer-Shoup暗号とは標準モデルで適切な仮定のもIND-CCA2安全が示された初めての「効率の良い」公開鍵暗号である。安全性はDDH仮定に基づいている。 1998年にとによって提案された。1998年版はElGamal暗号の拡張である。 ElGamal暗号は頑健性を持たないが、Cramer-Shoup暗号は別の要素を加えることによりより強力な敵に対しても頑健性を達成している。頑健性はハッシュ関数の利用とElGamal暗号にはない計算によって得られている。そのため、暗号文はElGamal暗号の2倍長い。

概要

CramerとShoupによって示された安全性は、正確にいえば適応的選択暗号文攻撃の元での識別不可能性 (IND-CCA2) である。公開鍵暗号の安全性要件の中では現在最も強い要件である。攻撃者は復号オラクル（暗号方式の秘密鍵を持ち暗号文を復号できるオラクル）にアクセスできる。「適応的」とは、攻撃者が攻撃者が攻撃の対象とする暗号文を知る前にも後にも復号オラクルを使用可能である、ということを意味している。（攻撃な対象となる暗号文をそのまま復号オラクルに問い合わせることは禁止されている。）より弱い安全性の定義は非適応的選択暗号文攻撃 (IND-CCA1) である。この場合、対象となる暗号文を知る前にのみ復号オラクルを使用可能である。

このような攻撃者に対しては広くつかわれている暗号が安全でないことは、かつてより知られていた。システム設計者は、このような攻撃は非現実的であり理論的興味に過ぎないと考えていた。 1990年代後半より、特にがRSA暗号を用いたSSLに対する現実的な適応的選択暗号文攻撃を示して以来、変化が起きている。

Cramer-Shoup暗号が初めてのIND-CCA2安全な暗号というわけではない。 NaorとYung、RackoffとSimon、DolevとDworkとNaorが、IND-CPA安全な暗号をIND-CCA1安全やIND-CCA2安全な暗号に変換する方法を提案している。これらの方法は標準的な仮定の下（ランダムオラクル無しに）安全である。しかし、複雑なゼロ知識証明のテクニックを用いており、暗号化コストは大きく、暗号文の長さが長い。他のアプローチとしては、やによるOAEP、また、藤崎-岡本変換が知られている。これらは効率の良い構成であるが、ハッシュ関数を理想化したランダムオラクルを用いている。現実にこの変換を用いる場合にはランダムオラクルを他の実用的な関数（暗号学的なハッシュ関数）で置き換えなければならない。研究が進むにつれ、この種のアプローチは安全でないと考えられている。（このアプローチを用いた現実的な暗号方式に対して、効率の良い攻撃が実証されているわけではない。）

暗号方式

鍵生成、暗号化、復号について説明する。

鍵生成

位数 $q$ の巡回群 $G$ の記述と、その生成元 $g_{1},g_{2}$ を生成する。
5つのランダムな値 $(x_{1},x_{2},y_{1},y_{2},z)$ を $\{0,\ldots ,q-1\}$ からランダムに選ぶ。
$c=g_{1}^{x_{1}}g_{2}^{x_{2}},d=g_{1}^{y_{1}}g_{2}^{y_{2}},h=g_{1}^{z}$ を計算する。
公開鍵は $(c,d,h)$ と $G,q,g_{1},g_{2}$ の記述である。秘密鍵は $(x_{1},x_{2},y_{1},y_{2},z)$ である。

暗号化

平文 $m$ を公開鍵 $(G,q,g_{1},g_{2},c,d,h)$ で暗号化する。

$m$ を $G$ の要素に変換する。
$k$ $k$ を $\{0,\ldots ,q-1\}$ $\{0,\ldots ,q-1\}$ からランダムに選び、以下を計算する。
- $u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}$
- $e=h^{k}m\,$
- $\alpha =H(u_{1},u_{2},e)\,$ , ただし、H()は衝突耐性を持つハッシュ関数である。
- $v=c^{k}d^{k\alpha }\,$
暗号文は $(u_{1},u_{2},e,v)$ である。

復号

暗号文 $(u_{1},u_{2},e,v)$ を秘密鍵 $(x_{1},x_{2},y_{1},y_{2},z)$ で復号する。

まず $\alpha =H(u_{1},u_{2},e)\,$ を計算し、 ${u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v\,$ が成立するかを確かめる。もしこのテストが失敗した場合、復号を止め拒否する。
テストが成功した場合、 $m=e/({u}_{1}^{z})\,$ を計算し、 $m$ を出力する。