Cramer-Shoup暗号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

Cramer-Shoup暗号(クレーマー シュープあんごう)とは暗号理論における暗号方式の一つ。適応的選択暗号文攻撃英語版に対する安全性(IND-CCA2)が標準モデル(暗号理論)英語版で証明された初の効率的な公開鍵暗号である。 安全性はDDH仮定英語版の計算理論的な非展性(但し証明はされていない)に基づいている。 1998年にロナルド・クレーマー英語版ビクター・シュープ英語版によって提案されたもので、ElGamal暗号の拡張になっている。 ElGamal暗号は頑強性を持たないが、Cramer-Shoup暗号は別の要素を加えることでより強力な攻撃者に対しても頑強性を達成している。 この頑強性は万能一方向ハッシュ関数の利用とElGamal暗号にはない計算の追加によって得られており、その結果、暗号文の長さはElGamal暗号の2倍になる。

概要[編集]

CramerとShoupによって示された安全性の正確な定義は、適応的選択暗号文攻撃に対する識別不可能性 (IND-CCA2) である。 これは公開鍵暗号の安全性としては現時点で最も強力な定義である。 この定義においては、攻撃者は「復号オラクル」を利用できるが、これは問い合わされたいかなる暗号文でもその暗号方式の秘密鍵を用いて復号できる神託機械である。 「適応的」とは、攻撃者が攻撃対象とする暗号文を知る前にも後にも復号オラクルを利用可能である、ということを意味する。ただし攻撃対象である暗号文をそのまま復号オラクルに問い合わせることは禁止されている。 これより弱い安全性の定義として、適応的でない選択暗号文攻撃 に対する識別不可能性(IND-CCA1)があるが、こちらの場合は攻撃対象となる暗号文を知る前に限り復号オラクルを利用できる。

こうした攻撃者に対しては、普及している多くの暗号方式が安全でないのは有名な話だったが、暗号方式の設計者は、そのような攻撃は非現実的であり理論的興味に過ぎないと長年考えていた。 ところがこの風潮は1990年代後半より変わり始めた。理由としては、特にダニエル・ブライヘンバッハー英語版がRSA暗号の一種を用いたSSLサーバに対する実用的な適応的選択暗号文攻撃を提出したことなどが大きい[1]

Cramer-Shoup暗号が初のIND-CCA2安全な暗号というわけではない。 NaorとYung、RackoffとSimon、DolevとDworkとNaorが、IND-CPA安全な暗号をIND-CCA1安全やIND-CCA2安全な暗号に変換する方法を提案している。 これらの方法は標準的な仮定のもとで(ランダムオラクル無しに)安全である。しかし複雑なゼロ知識証明のテクニックを用いており、計算コストと暗号文の長さの面で効率が悪い。 他のアプローチとしては、ミヒル・ベラーレ英語版フィリップ・ロガウェイ英語版らによるOAEPや藤崎-岡本変換が知られている。これらはランダムオラクルという数学的抽象観念を用いて効率の良い構成を達成しているが、不幸なことに、実装するにはランダムオラクルを何らかの現実的な関数(暗号学的ハッシュ関数)で置き換えなければならない。 そうした実装例に対して、実用的な攻撃方法が提出された訳ではないが、研究が進むにつれ、この種のアプローチでは安全性を証明することが困難であることが判ってきている[2][3][4]

暗号方式[編集]

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

鍵生成[編集]

  • 位数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)で暗号化する。

  • mGの要素に変換する。
  • k\{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を出力する。

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

もし、取りうる平文空間がGの位数よりも大きい場合には、メッセージを分割し、それぞれを暗号化する。 また、効率良く暗号化するために、ハイブリッド暗号の中で使われることもある。

脚注[編集]

  1. ^ Bleichenbacher, Daniel (1998), “Advances in Cryptology — CRYPTO '98”, Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, http://rd.springer.com/chapter/10.1007/BFb0055716#page-1 2014年7月31日閲覧。 
  2. ^ P. Paillier; J. Villar (2006), “Asiacrypt 2006”, Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption, https://www.iacr.org/archive/asiacrypt2006/42840253/42840253.pdf 
  3. ^ D. Brown, “What Hashes Make RSA-OAEP Secure?”, IACR ePrint 2006/233, http://eprint.iacr.org/2006/223 
  4. ^ E. Kiltz; K. Pietrzak (2009), EUROCRYPT 2009, “On the security of padding-based encryption schemes (Or: why we cannot prove OAEP secure in the standard model)”, LNCS 5479: 389-406, https://www.iacr.org/archive/eurocrypt2009/54790389/54790389.pdf 2014年7月24日閲覧。 

参考文献[編集]

関連項目[編集]