IDベース暗号

IDベース暗号 (ID-Based Encryption) とは公開鍵暗号の一種であり識別子を利用した暗号方式である。この暗号では、利用者の公開鍵として、利用者の識別子に関する一意な情報を用いる。例えば、利用者のメールアドレス、姓名やドメイン名、物理的なIPアドレス等を公開鍵として用いることが出来る。ID-Based Encryptionの略からIBEとも呼ばれる。

1984年にメールアドレスに基づく公開鍵基盤方式 (PKI) がアディ・シャミア（RSAの"S"）によって提案された^[1]。これは利用者の識別子のように公開されている情報のみからデジタル署名の検証を可能とする。

最近では、ボネ (en:Dan Boneh) とフランクリン (en:Matthew K. Franklin) のペアリングに基づく暗号方式^[2]、コックスの平方剰余に基づく暗号方式^[3]も存在する。

利用法

IDベースの方式は、任意の利用者に、たとえば文字列といった識別子から公開鍵を生成することを許す。秘密鍵生成局 (Private Key Generator:PKG) と呼ばれる信頼された第三者は、対応する秘密鍵を生成する。まず秘密鍵生成局はマスター公開鍵を公開し、マスター秘密鍵 (以下ではマスター鍵と呼ぶ) を秘密に保持する。マスター公開鍵が与えられると、利用者は識別子IDに対応する公開鍵を、マスター公開鍵と識別子から計算できる。対応する秘密鍵を得るには、識別子IDと認証された参加者が秘密鍵生成局にアクセスする。この際、秘密鍵生成局はマスター秘密鍵を用いて識別子ID用の秘密鍵を生成する。

個々の利用者間で通信に先立って鍵を配布することなく、利用者はメッセージを暗号化 (または署名を検証) することができる。認証済みのカギを先行配布するのが不便な場合、または技術的な制限により不可能な場合に、非常に有用である。しかし、復号または署名を行うためには、認証済みの利用者は秘密鍵生成局から秘密鍵を受け取らねばならない。この方法論の注意点として、秘密鍵生成局が非常に信頼されているという点がある。（秘密鍵生成局は、任意の利用者の秘密鍵を生成できるので、認証無しに復号または署名を行える）任意の利用者の秘密鍵は第三者のマスター秘密鍵から生成されるので、この方式は必然的に鍵供託を行っていることになる。この方式の変種では、鍵供託問題を取り除くことが可能である。（en:certificate-based encryption、en:secure key issuing cryptography、en:certificateless cryptography^[4].^[要出典]

プロトコルの枠組み

ボネーとフランクリンはIDベース暗号方式を4つのアルゴリズムからなるものとして定義した。

初期設定 (Setup) : このアルゴリズムは秘密鍵生成局がIDベース暗号方式の利用を始める際に一度だけ用いられる。マスター鍵は秘密に保存され利用者の秘密鍵を抽出するために用いられる。一方、システムパラメータは公開される。このアルゴリズムはセキュリティパラメータ $\textstyle k$ を入力とし、以下を出力する。

システムパラメータからなる集合 $\textstyle {\mathcal {P}}$ 。これは平文空間 $\textstyle {\mathcal {M}}$ および暗号文空間 $\textstyle {\mathcal {C}}$ を含む。
マスター鍵 $\textstyle K_{m}$ .

秘密鍵生成 (Extract) : 秘密鍵生成局が利用者から秘密鍵を生成するよう要求されたときに用いられる。要求者の認証および利用者の秘密鍵 $\textstyle d$ を送信する際の安全な通信はIDベース暗号のプロトコルでは扱わない。秘密鍵生成アルゴリズムは入力として $\textstyle {\mathcal {P}}$ , $\textstyle K_{m}$ および識別子 $\textstyle ID\in \left\{0,1\right\}^{*}$ を受け取り、利用者 $\textstyle ID$ 用の秘密鍵 $\textstyle d$ を出力する。
暗号化 (Encrypt): $\textstyle {\mathcal {P}}$ 、平文 $\textstyle m\in {\mathcal {M}}$ 、および識別子 $\textstyle ID\in \left\{0,1\right\}^{*}$ を入力とし、暗号文 $\textstyle c\in {\mathcal {C}}$ を出力する。
復号 (Decrypt): $\textstyle d$ 、 $\textstyle {\mathcal {P}}$ 、 $\textstyle c\in {\mathcal {C}}$ を入力とし、 $\textstyle m\in {\mathcal {M}}$ を出力する。

正当性

全体がうまく動作するためには、当り前ではあるが以下を前提とする。 $\forall m\in {\mathcal {M}},ID\in \left\{0,1\right\}^{*}:Decrypt\left(Extract\left({\mathcal {P}},K_{m},ID\right),{\mathcal {P}},Encrypt\left({\mathcal {P}},m,ID\right)\right)=m$ 。

暗号方式

効率が良いIDベース暗号方式は、現在のところ、en:Weil pairingやen:Tate pairingといった楕円曲線上の双線形ペアリングに基づいている。最初のペアリングに基づく暗号方式は、en:Dan Bonehとen:Matthew K. Franklinによって提案された。これはElGamal暗号のようなアプローチによって構成された確率的暗号である。Boneh-Franklin暗号は安全性証明を有するが、証明は楕円曲線上の有限群のある問題の困難性に関する新しい仮定を必要とする。

他のアプローチはen:Clifford Cocksによって2001に提案された. Cocks IBE方式はよく用いられている平方剰余仮定 (QR仮定) に基づいている。しかし、メッセージを1ビットごとに暗号化するため、暗号文が非常に長くなってしまう。したがって、共通鍵暗号で用いるセッション鍵のように短いメッセージ以外では、効率が悪く実用的では無い。

利点

IDベース暗号の主要な利点の1つとして、利用者数が有限であれば、全ての利用者に秘密鍵が配布されたのちに、第三者（秘密鍵生成局）の秘密鍵を廃棄できることが挙げられる。これは、ひとたび生成された鍵は以降ずっと正しいものであると仮定されていることから可能になる (基本的な方式では鍵無効化の方法は考えられていない)。鍵無効化法を持つ多くの方式ではこの利点が失われる。

更に、公開鍵が識別子から生成されるため、IDベース暗号方式は公開鍵基盤を必要としない。この方式では、秘密鍵が識別子に対応する利用者に安全に配送されていさえすれば、公開鍵は暗に認証されている。

また、IDベース暗号は、識別子に付加的な情報を埋め込むことが出来るため、有用な機能を持つ。例えば、送信者はメッセージの満了日を設定することが可能になる。送信者は、満了日の時刻情報を受信者の識別子に加えればよい (X.509のような形式を用いることが可能であろう)。受信者が秘密鍵生成局にアクセスした際に、秘密鍵生成局は識別子を評価し、もし満了日を過ぎていた場合は秘密鍵生成を拒否できる。一般に、識別子へのデータの埋め込みは、送信者と秘密鍵生成局の間に新しい通信路を開くことに対応しており、その通信路の信頼性は秘密鍵が識別子に依存していることにより保証される。

欠点

秘密鍵生成局が利用者の秘密鍵を生成するので、生成局は認証なしに任意の暗号文を復号でき、また任意のメッセージに署名できる。
- しかし、組織の中に自前のPKGを立てて、システム管理者を信頼することを厭わないならば、これは特に問題にならないかもしれない。
この鍵供託問題は、公開鍵基盤では秘密鍵は利用者の計算機で生成されるため、現在の公開鍵基盤では存在しない。さまざまな方式が鍵供託問題を解決するため提案されている。例として、en:certificate-based encryption、秘密分散法、en:secure key issuing cryptography、en:certificateless cryptographyが挙げられる。
システムに参加するためには秘密鍵を安全に配送するため、利用者と秘密鍵生成局の間に安全な通信路が必要である。大規模なシステムでは、SSLのような通信方式がよく用いられている。

参考文献

^ Adi Shamir, Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, 7:47--53, 1984
^ Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)
^ Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, 2001
^ SS Al-Riyami, KG Paterson Certificateless Public Key Cryptography Advances in Cryptology - Proceedings of ASIACRYPT 2003 (2003)

外部リンク

[1] Adi Shamir, Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, 7:47--53, 1984

[2] Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)

[3] Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, 2001

[4] SS Al-Riyami, KG Paterson Certificateless Public Key Cryptography Advances in Cryptology - Proceedings of ASIACRYPT 2003 (2003)

[1]

[2]

[3]

[4]

利用法

プロトコルの枠組み

正当性

暗号方式

利点

欠点

関連項目

参考文献

外部リンク