Cramer-Shoup暗号
Cramer-Shoup暗号（クレーマーシュープあんごう）は、暗号理論における重要な公開鍵[[暗号]]の一つです。この暗号方式の最大の特徴は、適応的選択暗号文攻撃（IND-CCA2）に対する安全性が、標準モデルにおいて数学的に証明されている点にあります。これは、暗号文を解読しようとする攻撃者が、暗号化されたメッセージを入手した後でも、復号を試みることができる状況下での安全性を保証するもので、非常に強力なセキュリティレベルを意味します。
Cramer-Shoup暗号の安全性は、DDH（Decisional Diffie-Hellman）仮定に基づいています。これは、特定の数学的な計算が困難であるという仮定であり、暗号理論における安全性の根拠として広く用いられています。ただし、Cramer-Shoup暗号の安全性は、DDH仮定の計算理論的な非展性に基づくとされていますが、この点が数学的に厳密に証明されているわけではありません。
この暗号方式は、1998年にロナルド・クレーマーとビクター・シュープによって提案されました。Cramer-Shoup暗号は、ElGamal暗号を拡張したものであり、ElGamal暗号が持たない頑強性を実現しています。ElGamal暗号は、特定の攻撃に対して脆弱性がありましたが、Cramer-Shoup暗号では、万能一方向ハッシュ関数と追加の計算を導入することで、より強力な攻撃者に対しても安全性を確保しています。ただし、この追加の処理の結果、暗号文の長さはElGamal暗号の約2倍になります。
CramerとShoupが定義した「IND-CCA2」安全性は、現在、公開鍵[[暗号]]の安全性を評価する上で最も強力な基準の一つとされています。この定義では、攻撃者は「復号オラクル」という特別な機能を利用できます。これは、攻撃者が任意の暗号文を復号できる神託機械（ブラックボックス）のようなものです。「適応的」という言葉が示すように、攻撃者は攻撃対象とする暗号文を知る前にも後にも、この復号オラクルを利用できます。ただし、攻撃対象の暗号文そのものを直接復号オラクルに問い合わせることは禁止されています。
これよりも弱い安全性として、「IND-CCA1」があります。これは、攻撃対象となる暗号文を知る前にのみ復号オラクルを利用できる、という条件です。過去には、多くの暗号方式がこの種の攻撃に脆弱であることが知られていましたが、暗号方式の設計者は、このような攻撃が現実的ではないと考えていました。しかし、1990年代後半にダニエル・ブライヘンバッハーがRSA[[暗号]]に対する実用的な適応的選択暗号文攻撃を示したことで、状況は大きく変わりました。
Cramer-Shoup暗号は、初めてIND-CCA2安全性を実現した暗号ではありません。過去には、NaorとYung、RackoffとSimon、DolevとDworkとNaorなどが、IND-CPA安全な暗号をIND-CCA1やIND-CCA2安全な暗号に変換する方法を提案しています。これらの方法は、標準的な仮定の下で安全性が証明されますが、複雑なゼロ知識証明技術を用いるため、計算コストが高く、暗号文も長くなるという欠点がありました。一方、ミヒル・ベラーレとフィリップ・ロガウェイらによるOAEPや藤崎-岡本変換などは、ランダムオラクルと呼ばれる数学的な概念を用いることで効率の良い構成を実現していましたが、ランダムオラクルを現実的な関数（ハッシュ関数など）で置き換えた場合に、安全性を証明することが困難であることがわかってきました。
Cramer-Shoup暗号の具体的な鍵生成、暗号化、復号プロセスについて説明します。
1. 位数qの巡回群Gとその生成元g1, g2を生成します。
2. {0, …, q-1}からランダムに5つの値(x1, x2, y1, y2, z)を選びます。
3. 以下の値を計算します。
- c = g1^x1 g2^x2
- d = g1^y1 g2^y2
- h = g1^z
公開鍵は(c, d, h)と群G, q, g1, g2の記述となり、秘密鍵は(x1, x2, y1, y2, z)となります。
1. 平文mを群Gの要素に変換します。
2. {0, …, q-1}からランダムにkを選びます。
3. 以下の値を計算します。
- u1 = g1^k
- u2 = g2^k
- e = h^k m
- α = H(u1, u2, e) (H()は衝突耐性を持つハッシュ関数)
- v = c^k d^(kα)
暗号文は(u1, u2, e, v)となります。
1. 暗号文(u1, u2, e, v)と秘密鍵(x1, x2, y1, y2, z)を受け取ります。
2. α = H(u1, u2, e) を計算します。
3. u1^x1 u2^x2 (u1^y1 * u2^y2)^α = vが成立するかを検証します。
4. 検証に失敗した場合、復号を拒否します。
5. 検証が成功した場合、m = e / (u1^z) を計算し、平文mを出力します。
正しい暗号文であれば、上記の計算によって正しく復号されます。
もし、平文空間が群Gの位数よりも大きい場合、ハイブリッド暗号を利用する必要があります。単純にメッセージを分割してそれぞれを暗号化する方法は、安全性が損なわれるため注意が必要です。
この暗号方式に関するより詳しい情報は、以下の文献で確認できます。
Cramer-Shoup暗号は、ElGamal暗号や公開鍵[[暗号]]、暗号理論といった分野と密接に関連しています。
安全性の基盤
Cramer-Shoup暗号の安全性は、DDH（Decisional Diffie-Hellman）仮定に基づいています。これは、特定の数学的な計算が困難であるという仮定であり、暗号理論における安全性の根拠として広く用いられています。ただし、Cramer-Shoup暗号の安全性は、DDH仮定の計算理論的な非展性に基づくとされていますが、この点が数学的に厳密に証明されているわけではありません。
歴史的背景
この暗号方式は、1998年にロナルド・クレーマーとビクター・シュープによって提案されました。Cramer-Shoup暗号は、ElGamal暗号を拡張したものであり、ElGamal暗号が持たない頑強性を実現しています。ElGamal暗号は、特定の攻撃に対して脆弱性がありましたが、Cramer-Shoup暗号では、万能一方向ハッシュ関数と追加の計算を導入することで、より強力な攻撃者に対しても安全性を確保しています。ただし、この追加の処理の結果、暗号文の長さはElGamal暗号の約2倍になります。
IND-CCA2安全性とは
CramerとShoupが定義した「IND-CCA2」安全性は、現在、公開鍵[[暗号]]の安全性を評価する上で最も強力な基準の一つとされています。この定義では、攻撃者は「復号オラクル」という特別な機能を利用できます。これは、攻撃者が任意の暗号文を復号できる神託機械（ブラックボックス）のようなものです。「適応的」という言葉が示すように、攻撃者は攻撃対象とする暗号文を知る前にも後にも、この復号オラクルを利用できます。ただし、攻撃対象の暗号文そのものを直接復号オラクルに問い合わせることは禁止されています。
これよりも弱い安全性として、「IND-CCA1」があります。これは、攻撃対象となる暗号文を知る前にのみ復号オラクルを利用できる、という条件です。過去には、多くの暗号方式がこの種の攻撃に脆弱であることが知られていましたが、暗号方式の設計者は、このような攻撃が現実的ではないと考えていました。しかし、1990年代後半にダニエル・ブライヘンバッハーがRSA[[暗号]]に対する実用的な適応的選択暗号文攻撃を示したことで、状況は大きく変わりました。
Cramer-Shoup暗号の位置づけ
Cramer-Shoup暗号は、初めてIND-CCA2安全性を実現した暗号ではありません。過去には、NaorとYung、RackoffとSimon、DolevとDworkとNaorなどが、IND-CPA安全な暗号をIND-CCA1やIND-CCA2安全な暗号に変換する方法を提案しています。これらの方法は、標準的な仮定の下で安全性が証明されますが、複雑なゼロ知識証明技術を用いるため、計算コストが高く、暗号文も長くなるという欠点がありました。一方、ミヒル・ベラーレとフィリップ・ロガウェイらによるOAEPや藤崎-岡本変換などは、ランダムオラクルと呼ばれる数学的な概念を用いることで効率の良い構成を実現していましたが、ランダムオラクルを現実的な関数（ハッシュ関数など）で置き換えた場合に、安全性を証明することが困難であることがわかってきました。
暗号方式の詳細
Cramer-Shoup暗号の具体的な鍵生成、暗号化、復号プロセスについて説明します。
鍵生成
1. 位数qの巡回群Gとその生成元g1, g2を生成します。
2. {0, …, q-1}からランダムに5つの値(x1, x2, y1, y2, z)を選びます。
3. 以下の値を計算します。
- c = g1^x1 g2^x2
- d = g1^y1 g2^y2
- h = g1^z
公開鍵は(c, d, h)と群G, q, g1, g2の記述となり、秘密鍵は(x1, x2, y1, y2, z)となります。
暗号化
1. 平文mを群Gの要素に変換します。
2. {0, …, q-1}からランダムにkを選びます。
3. 以下の値を計算します。
- u1 = g1^k
- u2 = g2^k
- e = h^k m
- α = H(u1, u2, e) (H()は衝突耐性を持つハッシュ関数)
- v = c^k d^(kα)
暗号文は(u1, u2, e, v)となります。
復号
1. 暗号文(u1, u2, e, v)と秘密鍵(x1, x2, y1, y2, z)を受け取ります。
2. α = H(u1, u2, e) を計算します。
3. u1^x1 u2^x2 (u1^y1 * u2^y2)^α = vが成立するかを検証します。
4. 検証に失敗した場合、復号を拒否します。
5. 検証が成功した場合、m = e / (u1^z) を計算し、平文mを出力します。
正しい暗号文であれば、上記の計算によって正しく復号されます。
ハイブリッド暗号
もし、平文空間が群Gの位数よりも大きい場合、ハイブリッド暗号を利用する必要があります。単純にメッセージを分割してそれぞれを暗号化する方法は、安全性が損なわれるため注意が必要です。
参考文献
この暗号方式に関するより詳しい情報は、以下の文献で確認できます。
- - Ronald Cramer and Victor Shoup. "A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack." in proceedings of Crypto 1998, LNCS 1462, p.13ff
- - 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.
関連技術
Cramer-Shoup暗号は、ElGamal暗号や公開鍵[[暗号]]、暗号理論といった分野と密接に関連しています。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。