2月 04 2008
標準化
ペアリング暗号に関する標準化は、IDベース暗号を中心として行われています。標準化が進んでいる団体としては、現在私が把握しているもので2団体（IEEE、IETF）あります。ここではそれらの標準化作業などについて調査した事項や、それぞれの標準化に関連するサイトなどを紹介していきます。
IEEE
IEEEでは、P1363というプロジェクトで公開鍵暗号系の標準化を行っています。そこはさらに細分化されていくつかの標準化作業が行われています。その中でP1363.3においてIDベース暗号が標準化作業中です。
IEEE P1363.3: Identity-Based Public Key Cryptography Techniques using Pairings
P1363.3ではペアリングを用いたIDベース公開鍵暗号を定義します。 ただ、現在ではまだ草案の段階であり標準化はされていません。本ドキュメント作成時の最新ドキュメントはD1であり、内容はそれに沿ったものとなっています。
1.1節にある「Scope」において示されているドキュメント目的は以下のとおり。
This document specifies identity-based cryptographic schemes based on the bilinear mappings on elliptic curves known as pairings. Specific techniques include algorithms to compute pairings, and specification of recommended elliptic curves on which the pairings are defined. The class of computer and communications systems is not restricted.
ポイントを書いてみると次のようになります。
- ペアリング（楕円曲線上の双線形写像）に基づいたIDベース暗号スキームの仕様
- 仕様が含むもの
- ペアリング計算アルゴリズム
- 推奨楕円曲線
「ペアリング暗号アルゴリズム」とあるが、実際にはBB1、BF、境-笠原のKEMなどの暗号スキームが規定されていて、たとえばMillerのアルゴリズムやDuursma-Leeのアルゴリズムが規定されているわけではありません。また推奨する楕円曲線に関する記述は特段大きく触れてはいないと思われます。ハッシュの部分で2つ書いてありますが、「推奨する」とは書いていないと思います。参考までに以下に記しておきます。
- y^2 = x^3+1
- y^2 = x^3+x
標数についても特別な記述はありませんが、詳しい方に伺ったところ「標数p」をターゲットとしている様子が伺えるとのことで、「標数2」や「標数3」といった小さな数をターゲットにしているわけではなさそうだということです。ただ、標数pのサイズに関しての記述は現段階では記載はありません。
ドキュメント内ではまず暗号技術を以下の3つのタイプに分けることを示しています。（4.1節参照）
- プリミティブ（Primitives）
- 数論の困難性を基礎とした数学的オペレーション。それ自体でセキュリティを実現するものではないが、スキームの基礎要素となっているもの。
- スキーム（Schemes）
- プリミティブと他の方法を組み合わせたオペレーションの集まり。Complexity Theoreticなセキュリティを提供する。
- プロトコル（Protocols）
- あるセキュリティの目的を達成するために複数の組織により実行されるオペレーションの列。正しく実装されればアプリケーションのあるべきセキュリティを実現する。
この文書ではIDベースでの鍵管理スキームとして2つのスキーム（IDベース暗号、IDベース鍵カプセル化メカニズム）をいくつかの種類規定し、それらスキームに利用されるプリミティブ群を規定しています。プロトコルは規定していません。
プリミティブ：Pairing-based Diffied-Hellman Inversionプリミティブ（P-DHI系）
以下の4つのコンポーネントより構成される。プリミティブの詳細は割愛（どなたかからリクエストがあればやるかもしれません）。
- Generation（P-DHI-G）
- Verification（P-DHI-V）
- Encryption（P-DHI-E）
- Decryption（P-DHI-D）
プリミティブ：Pairing-based commutative blindingプリミティブ（P-CB系）
以下の4つのコンポーネントより構成される。プリミティブの詳細は割愛（どなたかからリクエストがあればやるかもしれません）。
- Generation（P-CB-G）
- Verification（P-CB-V）
- Encryption（P-CB-E）
- Decryption（P-CB-D）
プリミティブ：Pairing-based full-domain hashプリミティブ（P-FDH系）
以下の4つのコンポーネントより構成される。プリミティブの詳細は割愛（どなたかからリクエストがあればやるかもしれません）。
- Generation（P-FDH-G）
- Verification（P-FDH-V）
- Encryption（P-FDH-E）
- Decryption（P-FDH-D）
スキーム：SK-KEM
P-DHI系プリミティブを利用したIDベースの鍵カプセル化メカニズム（ID-KEM）。境、笠原による論文を基にしてます（文中では[SAKAI03]と参考文献が指定してあるが、文献詳細が書かれた部分が存在していません。おそらくSCIS2003の論文だと思われます）。
スキーム概要は以下のとおり。詳細は割愛いたします。
- Setup:SK-KEM-S
- Extract:SK-KEM-EX
- Encapsulate:SK-KEM-EN
- Decapsulate:SK-KEM-DE
スキーム：BB1-KEM
P-CB系プリミティブを利用した鍵カプセル化メカニズム。BonehとBoyenによる2004年の論文が基となっています（こちらも詳細未記述）。
スキーム概要は以下のとおり。詳細は割愛いたします。
- BB1-KEM-S
- BB1-KEM-EX
- BB1-KEM-EN
- BB1-KEM-DE
スキーム：BB1-IBE
P-CB系プリミティブを利用したIDベース暗号（だとおもうのですが・・・文中ではKEMと書いてある。先述のBB1-KEM部と一言一句同じなので、たぶんコピペした後の修正忘れだと思われます）。BonehとBoyenによる2004年の論文が基となっています（こちらも詳細未記述）。
スキーム概要は以下のとおり。詳細は割愛いたします。
- BB1-IBE-S
- BB1-IBE-EX
- BB1-IBE-EN
- BB1-IBE-DE
スキーム：BF-IBE
P-FDH系プリミティブを利用したIDベース暗号スキーム。BonehとFranklinによる2001年の論文が基となっています（こちらも詳細未記述）。
スキーム概要は以下のとおり。詳細は割愛いたします。
- BF-IBE-S
- BF-IBE-EX
- BF-IBE-EN
- BF-IBE-DE
P1363.3関連ページ
P1363.3に関するページは存在するのですが、最近は管理がされていないようで、2006年10月以降は更新されていません。そこに載っているドラフトなどもその時期のものになっていますが、先述のP1363WGのページにあるメーリングリストの情報やミーティングの情報などから最新のものがポストされていることがわかりますので、そちらをチェックしているほうが信頼性が高い情報が得られるということだと思います。
IETF
IETFでは現在3つのドキュメントが標準化の土台にあがっています。そのうち1つはRFC 5091として標準化されており、他の2つは現在はインターネットドラフトの段階にあります。RFC 5091の方はIndividual submissionによりドラフトが提出されてRFC化されていますが、他の2つのドキュメントはS/MIME WGによるWG submissionによりドラフトが提出されています。
RFC 5091：Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems
2007年12月に標準化されました。Voltage Security社のX. BoyenとL. Martinにより書かれています。最初のドラフトが2006年6月に提出されていますので、標準化までに1年半がかかっています。
文書自身はVoltage Security社の仕様であるIBCS（Identity-based Cryptography Standards）のv2を基に作られた文書であることが明記されています。
文書に書かれている内容は、Introductionの中に下記に引用している部分に書かれているところが参考になります。
This document provides a set of specifications for implementing
identity-based encryption (IBE) systems based on bilinear pairings.
Two cryptosystems are described: the IBE system proposed by Boneh and
Franklin (BF) [BF], and the IBE system proposed by Boneh and Boyen
(BB1) [BB1]. Fully secure and practical implementations are
described for each system, comprising the core IBE algorithms as well
as ancillary hybrid components used to achieve security against
active attacks. These specifications are restricted to a family of
supersingular elliptic curves over finite fields of large prime
characteristic, referred to as “type-1″ curves (see Section 2.1).
Implementations based on other types of curves currently fall outside
the scope of this document.
ポイントをまとめると以下のとおり。
- 双線形ペアリングによりIDベース暗号を実装するための仕様を提供
- 2つの暗号システムを記述：BFとBB1
- 大きな素数を標数としたSupersingularな楕円曲線を使うことに制限された仕様
- 他の曲線は現状はスコープ外
ということで、IEEE P1363.3 D1と同じくいわゆる「標数p」をターゲットとしていること、さらにそれに限定していることがわかります。また曲線に関しても「Type-1」カーブに限定しています。Type-1カーブとは以下のように定義されています。
- y^2 = x^3+1
- 素数pは12で割った余りが11
標数pのサイズに関しては、IEEE P1363.3と異なりきちんと指定がされています。pのサイズは512ビット、1024ビット、1536ビット、3840ビット、7680ビットの5種類のみが利用可能です。
さらにIEEE P1363.3と異なる部分としてペアリングの計算アルゴリズムが規定されていることがあります。RFC 5091ではペアリング計算アルゴリズムとしてMillerのアルゴリズムが記載されています。
BFとBB1のアルゴリズムも書かれていますが、どうも見た感じP1363.3の方とは違うような感覚も受けます。これに関しては詳しいひとに聞いてみて追記することといたします。
全体としてP1363.3の仕様よりもより実装が可能な状態に近いものとなっていると思われます。しかし、Voltage Security社はIDベース暗号まわりで特許を持っているので、実装は注意しなければならないかもしれません。
Using the Boneh-Franklin and Boneh-Boyen identity-based encryption algorithms with the Cryptographic Message Syntax (CMS)
こちらも2006年6月に一番最初の版が作成されたドキュメントです。こちらの文書は暗号化アルゴリズムを決めているわけではなく、先述のRFC 5091のBFとBB1を電子メールの暗号化・デジタル署名の用途で用いられるCMSで使う際のASN.1フォーマットなどが定められている文書です。
現在は「IESG Evaluation」のステータスにあります。
Identity-based Encryption Architecture
こちらも2006年6月に初版が作成されたものです。こちらの文書はIDベース暗号を使う際に、公開パラメータをどのように受け取るかの遷移などが記述されたもので、短い文書となっています。細かい通信形態（SSL/TLSを用いる、など）について多少の記載はありますが、基本的にはプレーヤーがどういうものを受け渡しし合うか、などがかかれたもののみとなっています。
現在は「IESG Evaluation」のステータスにあります。