Cramer-Shoup暗号

Cramer-Shoup暗号︵クレーマー シュープあんごう︶とは暗号理論における暗号方式の一つ。適応的選択暗号文攻撃に対する安全性︵IND-CCA2︶が標準モデル︵暗号理論︶で証明された初の効率的な公開鍵暗号である。 安全性はDDH仮定の計算理論的な非展性︵但し証明はされていない︶に基づいている。 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$$q$の巡回群$G$$G$の記述と、その生成元$g_{1},g_{2}$$g_{1},g_{2}$を生成する。

●5つのランダムな値 $(x_{1},x_{2},y_{1},y_{2},z)$$(x_{1},x_{2},y_{1},y_{2},z)$を$\{0,\ldots ,q-1\}$$\{0,\ldots ,q-1\}$からランダムに選ぶ。

●以下を計算する。
●$c=g_{1}^{x_{1}}g_{2}^{x_{2}}$$c=g_{1}^{x_{1}}g_{2}^{x_{2}}$
●$d=g_{1}^{y_{1}}g_{2}^{y_{2}}$$d=g_{1}^{y_{1}}g_{2}^{y_{2}}$
●$h=g_{1}^{z}$$h=g_{1}^{z}$
●公開鍵は$(c,d,h)$$(c,d,h)$と$G,q,g_{1},g_{2}$$G,q,g_{1},g_{2}$の記述である。秘密鍵は$(x_{1},x_{2},y_{1},y_{2},z)$$(x_{1},x_{2},y_{1},y_{2},z)$である。

暗号化

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

●$m$$m$を$G$$G$の要素に変換する。

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

●$v=c^{k}d^{k\alpha }\,$$v=c^{k}d^{k\alpha }\,$
●暗号文は$(u_{1},u_{2},e,v)$$(u_{1},u_{2},e,v)$である。

復号

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

●まず$\alpha =H(u_{1},u_{2},e)\,$$\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\,$${u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v\,$が成立するかを確かめる。もしこのテストが失敗した場合、復号を止め拒否する。

●テストが成功した場合、$m=e/({u}_{1}^{z})\,$$m=e/({u}_{1}^{z})\,$を計算し、$m$$m$を出力する。

${u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,$${u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,$と$m=e/h^{k}\,$$m=e/h^{k}\,$より、正しい暗号文であれば、正しく復号される。

もし、取りうる平文空間が$G$$G$の位数よりも大きい場合には、ハイブリッド暗号を利用することができる。メッセージを短く分割してそれぞれを暗号化する、という単純な方法では、安全性が保てないことに注意。

参考文献

• en:Ronald Cramer and en:Victor Shoup. "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack." in proceedings of Crypto 1998, LNCS 1462, p.13ff (ps,pdf)
• Emacs LispとJavaでの簡単な実装例
• 1998年のCramer-Shoup暗号出版のWired Newsでのニュース（2000年8月15日時点のアーカイブ）とen:Bruce SchneierのCrypto-Gram（2003年7月16日時点のアーカイブ）
• Ronald Cramer and Victor Shoup: "Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption." in proceedings of Eurocrypt 2002, LNCS 2332, pp.45--64. Full Version (pdf)

関連項目

• ElGamal暗号
• 公開鍵暗号
• 暗号理論