JP5871826B2 - 認証子生成装置、検証装置、およびプログラム - Google Patents

Description

本発明は、情報セキュリティ技術に関し、特に、メッセージ認証子技術に関する。

証明可能安全性を持つメッセージ認証子が、共通鍵暗号のプリミティブの安全性の下で提案されている。また、通常の安全性を持つ暗号方式を関連鍵攻撃に対する安全性をもつ方式に変換する技術もいくつか知られている（例えば、非特許文献１から３参照）。

Mihir Bellare and David Cash, "Pseudorandom functions and permutations provably secure against related-key attacks," in Tal Rabin, editor, CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 666-684, Springer, Heidelberg, 2010. Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, and Daniel Wichs, "Message authentication, revisited," in David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 355-374, Springer, Heidelberg, 2012. Mihir Bellare, Kenneth G. Paterson, and Susan Thomson, "RKA security beyond the linear barrier: IBE, encryption and signatures," Cryptology ePrint Archive, Report 2012/514, 2012, to appear ASIACRYPT 2012.

しかしながら、従来の関連鍵攻撃に対する安全性をもつ方式は、関連鍵攻撃を検知した場合に自壊しなければ安全性を保てない。

本発明では、自壊することなく関連鍵攻撃に対する安全性を向上させることができるメッセージ認証子技術を提供する。

メッセージ認証子の生成時には、対応鍵とメッセージとを含む情報に対応するラベル情報を得、乱数対応値と秘密鍵対応値とラベル情報とに対する像と当該乱数対応値とを含むメッセージ認証子を得る。ただし、秘密鍵と対応鍵とが鍵ペアであり、乱数対応値が乱数を含む情報に対応し、秘密鍵対応値が秘密鍵を含む情報に対応する。検証時には、対応鍵とメッセージとを含む情報に対応する検証ラベル情報を得、メッセージ認証子と秘密鍵対応値と検証ラベル情報とを用いてメッセージを検証する。

本発明では、ラベル情報が秘密鍵の対応鍵とメッセージとに対応する。そのため、自壊を行うことなく、関連鍵攻撃に対する安全性を向上させることができる。

図１は第１実施形態の認証システムを例示する図である。 図２Ａは第１実施形態の認証子生成処理を説明するためのフロー図であり、図２Ｂは第１実施形態の検証処理を説明するためのフロー図である。 図３は第２実施形態の認証システムを例示する図である。 図４Ａは第２実施形態の認証子生成処理を説明するためのフロー図であり、図４Ｂは第２実施形態の検証処理を説明するためのフロー図である。

以下、図面を参照して本発明の実施形態を説明する。
＜定義＞
各実施形態で用いる記号や用語を定義する。
［ラベルに基づく適応的トラップドア関係の属］
ラベルに基づく適応的トラップドア関係（ＡＴＲ：Adaptive Trapdoor Relations）の属は、以下の属Ｆ_ｆ，ＬとアルゴリズムＳｅｔｕｐ（１^κ），ＴｒａｐＧｅｎ（ｐｐ），Ｓａｍｐ（ｐｐ，ｆ，Ｌ），Ｇ（ｓ）とからなる。
Ｓｅｔｕｐ（１^κ）は、セットアップアルゴリズムであり、セキュリティパラメータ１^κを入力とし、共通パラメータｐｐを得て出力する。１^κはκ個の１からなる列を表す。κは１以上の所定の整数である。
ＴｒａｐＧｅｎ（ｐｐ）は、鍵生成アルゴリズムであり、ｐｐを入力とし、秘密鍵ｔとそれに対応する対応鍵（例えば公開鍵）ｆとの鍵ペア（ｆ，ｔ）を得て出力する。鍵ペア（ｆ，ｔ）は、写像μ（第１写像）に対してｆ＝μ（ｔ）の関係を満たす。すなわち、ｔの鍵空間を表す集合がＴＳであり、ｆの鍵空間を表す集合がＦＳである場合、写像μは鍵空間ＴＳを鍵空間ＦＳに写す写像μ：ＴＳ→ＦＳである。本形態の写像μは準同型性写像である。また、写像の例は関数やアルゴリズムなどである。
Ｓａｍｐ（ｐｐ，ｆ，Ｌ）は、公開サンプリングアルゴリズムであり、ｐｐとｆとラベル情報Ｌとを入力とし、乱数ｓとｙ＝Ｆ_ｆ，Ｌ（ｓ）とを得て出力する。Ｆ_ｆ，Ｌは、ｆとＬとの組に対応する単射なラベル付き写像の属である。言い換えると、Ｆ_ｆ，Ｌは、ｆとＬとの組に対応する単射な写像を要素とする集合である。すなわち、ｙ＝Ｆ_ｆ，Ｌ（ｓ）は、ｐｐ，ｆ，Ｌ，ｓを入力とし、ｆとＬとの組に対応する単射な写像をｓに作用させてｙを得て出力することを表す。本形態のＦ_ｆ，Ｌ（ｓ）は準同型性を持つ。Ｉｎｖ（ｐｐ，ｔ，Ｌ，ｙ）は、逆元探索アルゴリズムであり、ｐｐ，ｔ，Ｌ，ｙを入力とし、逆元ｓ＝Ｆ_ｆ，Ｌ ^−１（ｙ）を出力する。
Ｇ（ｓ）は、抽出アルゴリズムであり、ｓを入力として共通鍵（セッション鍵）Ｇ（ｓ）∈Ｇ_Ｋを出力する。Ｇ_Ｋは加法的な可換群（アーベル群）を表す。

［ハッシュ証明系］
ラベルに基づくハッシュ証明系（ＨＰＳ：hash proof system）は、以下のアルゴリズムＳｅｔｕｐ（１^κ），ＳａｍｐＲ（ｒ），Ｐｕｂ（ｐｐ，μ（ｔ），Ｌ，ｒ），Ｐｒｉｖ（ｐｐ，ｔ，Ｌ，υ）からなる。
Ｓｅｔｕｐ（１^κ）は、セットアップアルゴリズムであり、セキュリティパラメータ１^κを入力とし、共通パラメータｐｐを得て出力する。ｐｐは、有限集合Υ，ν，ＦＳ，ＴＳ、写像の集合Ｄ_ｆ，Ｌ、および写像μである。ν⊂Υであり、Ｄ_ｆ，Ｌはｆ∈ＦＳとＬ∈ＬＳとの組に対応する写像を要素とする集合であり、ＬＳはラベル情報Ｌの空間を表す集合である。
ＳａｍｐＲ（ｒ）は、サンプリングアルゴリズムであり、乱数ｒを入力とし、υ∈ν⊂Υを得て出力する。
Ｐｕｂ（ｐｐ，μ（ｔ），Ｌ，ｒ）は、ｐｐ，μ（ｔ），Ｌ，ｒを入力とし、ｊ＝Ｄ_ｆ，Ｌ（υ）を得て出力するアルゴリズムである。すなわち、Ｐｕｂ（ｐｐ，μ（ｔ），Ｌ，ｒ）は、ｐｐ，μ（ｔ），Ｌ，ｒを用い、ｆとＬとの組に対応する写像をυに作用させて得られる値ｊを計算して出力する。
Ｐｒｉｖ（ｐｐ，ｔ，Ｌ，υ）は、ｐｐ，ｔ，Ｌ，υを入力とし、ｊ＝Ｄ_ｆ，Ｌ（υ）を得て出力するアルゴリズムである。すなわち、Ｐｒｉｖ（ｐｐ，ｔ，Ｌ，υ）は、ｆとＬとの組に対応する写像Ｄ_ｆ，Ｌをυに作用させて値ｊを得て出力する。本形態の写像Ｄ_ｆ，Ｌは準同型性を持つ。

［双線形写像］
双線形写像ｅ：Ｇ_Ｋ×Ｇ_Ｋ→Ｇ_Ｔは、双線形性、非退化性および効率的計算可能性を持つ写像である。ただし、Ｇ_Ｋ，Ｇ_Ｔは位数が素数ｑである可換群である。
双線形性により、任意のｈ_１，ｈ_２∈Ｇ_Ｋおよび任意のα，β∈Ｚ_ｑについてｅ（ｈ_１ ^α，ｈ_２ ^β）＝ｅ（ｈ_１，ｈ_２）^αβとなる。非退化性により、ｅ（ｈ_１，ｈ_１）のＧ_Ｔでの位数がｑとなる。効率的計算可能性により、ｅを効率よく計算することができる。なお、Ｚ_ｑはｑによる剰余群を表す。双線形写像の例はペアリングである。

［使い捨て署名］
使い捨て署名は、三つ組のアルゴリズムｏｔｓ．ｇｅｎ（１^κ），ｏｔｓ．ｓｉｇｎ（ｏｓｋ，Ｍ），ｏｔｓ．ｖｒｆｙ（ｏｖｋ，σ）からなる。
ｏｔｓ．ｇｅｎ（１^κ）は、鍵生成アルゴリズムであり、セキュリティパラメータ１^κを入力とし、署名検証鍵ｏｖｋとそれに対応する署名生成鍵ｏｓｋとの鍵ペア（ｏｖｋ，ｏｓｋ）を得て出力する。
ｏｔｓ．ｓｉｇｎ（ｏｓｋ，ｍ）は、署名生成アルゴリズムであり、ｏｓｋとメッセージｍとを入力として、署名σを得て出力する。
ｏｔｓ．ｖｒｆｙ（ｏｖｋ，σ，ｍ）は、署名検証アルゴリズムであり、ｏｖｋ，σ，ｍを入力として署名検証を行って、受け入れａｃｃまたは拒絶ｒｅｊを出力する。

［衝突困難性（衝突耐性）を持つ写像］
写像Ｈが衝突困難性を持つとは、多項式時間で動作する敵が、写像の属からそれに属する写像Ｈを定める情報とセキュリティパラメータ１^κとを受け取ったとき、γ≠δかつＨ（γ）＝Ｈ（δ）なる組（γ，δ）を無視できる確率でしか出力することができないことを表す。衝突困難性を持つ写像Ｈの例は、ＳＨＡ−１等の暗号学的なハッシュ関数などである。通常、衝突困難性を持つ写像は一方向性も持つ。

＜原理＞
各実施形態に共通する原理を説明する。
認証子生成装置は、対応鍵とメッセージとを含む情報に対応するラベル情報を得、乱数対応値と秘密鍵対応値とラベル情報とに対する像と乱数対応値とを含むメッセージ認証子を得、メッセージとメッセージ認証子とを出力する。ただし、秘密鍵と対応鍵とが鍵ペアであり、乱数対応値が乱数を含む情報に対応し、秘密鍵対応値が秘密鍵を含む情報に対応する。ラベル情報の例は、対応鍵とメッセージとを含む情報に衝突困難性を持つ写像を作用させて得られる値である。

メッセージとメッセージ認証子とは検証装置に入力される。検証装置は、対応鍵とメッセージとを含む情報に対応する検証ラベル情報を得、メッセージ認証子と秘密鍵対応値と検証ラベル情報とを用いてメッセージを検証し、検証結果を出力する。検証ラベル情報の例は、対応鍵とメッセージとを含む情報に衝突困難性を持つ写像を作用させて得られる値である。

以上の構成では、ラベル情報が秘密鍵の対応鍵とメッセージとに対応するため、自壊を行うことなく、関連鍵攻撃に対する安全性を向上させることができる（詳細は後述）。

＜第１実施形態＞
第１実施形態を説明する。第１実施形態は、ラベルに基づく適応的トラップドア関係の属に上述の原理を適用したものである。
［構成］
図１に例示するように、本形態の認証システム１は、設定装置１１０と鍵生成装置１２０と認証子生成装置１３０と検証装置１４０とを有する。設定装置１１０と鍵生成装置１２０と認証子生成装置１３０と検証装置１４０とは、それぞれ、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）等を含む汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置１１０と鍵生成装置１２０と認証子生成装置１３０と検証装置１４０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。

認証子生成装置１３０は、入力部１３１と記憶部１３２と対応鍵生成部１３３とラベル情報生成部１３４とメッセージ認証子生成部１３５と出力部１３６とを有する。メッセージ認証子生成部１３５は、サンプリング部１３５ａと暗号化部１３５ｂと署名鍵生成部１３５ｃと署名生成部１３５ｄとを有する。認証子生成装置１３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み出される。

検証装置１４０は、入力部１４１と記憶部１４２と対応鍵生成部１４３と検証ラベル情報生成部１４４と検証部１４５と出力部１４６とを有する。検証部１４５は、署名検証部１４５ａと逆元探索部１４５ｂと判定部１４５ｃとを有する。検証装置１４０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１４２に格納され、必要に応じて各部に読み出される。

［セットアップ処理］
本形態のセットアップ処理では、設定装置１１０がセキュリティパラメータ１^κを入力とし、鍵生成アルゴリズムＳｅｔｕｐ（１^κ）を実行し、ラベルに基づく適応的トラップドア関係の属の共通パラメータｐｐを得て出力する。さらに設定装置１１０は、衝突困難性を持つ写像Ｈ：｛０，１｝^*→Ｇ_Ｋを得て出力する。例えば、設定装置１１０は、暗号学的なハッシュ関数を写像Ｈとして出力する。ｐｐは鍵生成装置１２０に送られて格納され、ｐｐおよびＨは、認証子生成装置１３０および検証装置１４０に送られ、記憶部１３２および１４２にそれぞれ格納される。

［鍵生成処理］
本形態の鍵生成処理では、鍵生成装置１２０が、共通パラメータｐｐを入力とし、鍵生成アルゴリズムＴｒａｐＧｅｎ（ｐｐ）を実行して鍵ペア（ｆ，ｔ）を得る。さらに鍵生成装置１２０は、群Ｇ_Ｋからランダムに秘密鍵ｋ∈Ｇ_Ｋを得る。鍵生成装置１２０は、第１秘密鍵ｔおよび第２秘密鍵ｋからなる秘密鍵（ｔ，ｋ）を出力する。秘密鍵（ｔ，ｋ）は認証子生成装置１３０および検証装置１４０に送られ、記憶部１３２および１４２にそれぞれ格納される。

［認証子生成処理］
任意長のメッセージＭ∈｛０，１｝^*が認証子生成装置１３０の入力部１３１に入力され、記憶部１３２に格納され、以下の認証子生成処理（図２Ａ）が実行される。

対応鍵生成部１３３は、第１秘密鍵ｔを入力とし、第１秘密鍵ｔに写像μを作用させて対応鍵ｆ＝μ（ｔ）を得て出力する（ステップＳ１３１）。署名鍵生成部１３５ｃは、セキュリティパラメータ１^κを入力とし、鍵生成アルゴリズムｏｔｓ．ｇｅｎ（１^κ）を実行し、使い捨て署名の署名検証鍵ｏｖｋと署名生成鍵ｏｓｋとの鍵ペア（ｏｖｋ，ｏｓｋ）を得て出力する（ステップＳ１３２）。

ラベル情報生成部１３４は、対応鍵ｆとメッセージＭとを入力とし、対応鍵ｆとメッセージＭとを含む情報に写像Ｈを作用させてラベル情報ｄ＝Ｈ（ｆ，Ｍ）∈Ｇ_Ｋを得て出力する。対応鍵ｆとメッセージＭとを含む情報の例は、対応鍵ｆのビット列表現値とメッセージＭとのビット結合値や、対応鍵ｆのビット列表現値とメッセージＭと付加ビット列とのビット結合値などである。付加ビット列の例は、共通パラメータの一部やヘッダ情報などである。写像Ｈがハッシュ関数である場合、ラベル情報ｄは、対応鍵ｆとメッセージＭとを含む情報のダイジェスト値となる（ステップＳ１３３）。

サンプリング部１３５ａは、共通パラメータｐｐと対応鍵ｆと署名検証鍵ｏｖｋとを入力とし、公開サンプリングアルゴリズムＳａｍｐ（ｐｐ，ｆ，ｏｖｋ）を実行し、乱数ｓと乱数対応値ｙとの組（ｓ，ｙ）を得て出力する。この乱数対応値ｙは、対応鍵ｆと署名検証鍵ｏｖｋとに対応する第２写像Ｆ_{ｆ，ｏｖｋ}を乱数ｓに作用させて得られる値ｙ＝Ｆ_{ｆ，ｏｖｋ}（ｓ）である（ステップＳ１３４）。

暗号化部１３５ｂは、乱数ｓと第２秘密鍵ｋを入力とし、抽出アルゴリズムＧ（ｓ）を実行して乱数ｓに対応する共通鍵Ｇ（ｓ）を得、所定の共通鍵暗号方式に則り、共通鍵Ｇ（ｓ）で第２秘密鍵ｋを暗号化することで秘密鍵対応値ｃを得て出力する。暗号化部１３５ｂは、例えば、ｃ＝Ｇ（ｓ）・ｋを得て出力する（ステップＳ１３５）。ただし、「・」は群で定義された演算を表す。例えば、Ｇ（ｓ），ｋ∈｛０，１｝^κである場合、Ｇ（ｓ）・ｋはＧ（ｓ）とｋの排他的論理和である。

署名生成部１３５ｄは、署名生成鍵ｏｓｋと乱数対応値ｙと秘密鍵対応値ｃとラベル情報ｄとを入力とし、署名生成アルゴリズムｏｔｓ．ｓｉｇｎ（ｏｓｋ，（ｄ，ｙ，ｃ））を実行し、乱数対応値ｙと秘密鍵対応値ｃとラベル情報ｄとを含む情報に対する署名σ（乱数対応値と秘密鍵対応値とラベル情報とに対する像）を得て出力する。乱数対応値ｙと秘密鍵対応値ｃとラベル情報ｄを含む情報の例は、ｙ，ｃ，ｄのビット列表現値のビット結合値や、ｙ，ｃ，ｄと付加ビット列とのビット結合値などである（ステップＳ１３６）。

出力部１３６は、署名検証鍵ｏｖｋと乱数対応値ｙと秘密鍵対応値ｃと署名σとを含むメッセージ認証子τ＝（ｏｖｋ，ｙ，ｃ，σ）を得て（ステップＳ１３７）、メッセージ認証子τとメッセージＭとを出力する（ステップＳ１３８）。メッセージ認証子τとメッセージＭとは検証装置１４０に送られる。

［検証処理］
メッセージ認証子τ＝（ｏｖｋ，ｙ，ｃ，σ）とメッセージＭとが検証装置１４０の入力部１４１に入力され、記憶部１４２に格納され、以下の検証処理（図２Ｂ）が実行される。

対応鍵生成部１４３は、第１秘密鍵ｔを入力とし、第１秘密鍵ｔに写像μを作用させて対応鍵ｆ＝μ（ｔ）を得て出力する（ステップＳ１４１）。

検証ラベル情報生成部１４４は、対応鍵ｆとメッセージＭとを入力とし、対応鍵ｆとメッセージＭとを含む情報に写像Ｈを作用させて検証ラベル情報ｄ’＝Ｈ（ｆ，Ｍ）∈Ｇ_Ｋを得て出力する。なお、検証ラベル情報生成部１４４での「写像Ｈ」および「対応鍵ｆとメッセージＭとを含む情報」の構造は、ラベル情報生成部１３４での「写像Ｈ」および「対応鍵ｆとメッセージＭとを含む情報」と同じである（ステップＳ１４２）。

署名検証部１４５ａは、署名検証鍵ｏｖｋと署名σと検証ラベル情報ｄ’とを入力とし、署名検証アルゴリズムｏｔｓ．ｖｒｆｙ（ｏｖｋ，σ，（ｄ’，ｙ，ｃ））を実行し、署名検証鍵ｏｖｋを用いて、乱数対応値ｙと秘密鍵対応値ｃと検証ラベル情報ｄ’とを含む情報に対して署名σが合格であるかを検証し、受け入れ（合格）ａｃｃまたは拒絶（不合格）ｒｅｊを出力する（ステップＳ１４３）。なお、「乱数対応値ｙと秘密鍵対応値ｃと検証ラベル情報ｄ’とを含む情報」の構造は、署名生成部１３５ｄでの「乱数対応値ｙと秘密鍵対応値ｃとラベル情報ｄとを含む情報」の構造と同じである。署名検証部１４５ａが拒絶ｒｅｊを出力した場合、出力部１４６は拒絶ｒｅｊを出力し（ステップＳ１４７）、処理を終了する。

一方、署名検証部１４５ａが受け入れａｃｃを出力した場合、逆元探索部１４５ｂは、共通パラメータｐｐと秘密鍵ｔと署名検証鍵ｏｖｋと乱数対応値ｙとを入力とし、逆元探索アルゴリズムＩｎｖ（ｐｐ，ｔ，ｏｖｋ，ｙ）を実行し、対応鍵ｆと署名検証鍵ｏｖｋとに対応する逆元探索写像Ｆ_ｆ，Ｌ ^−１を乱数対応値ｙに作用させて乱数復元値ｓ’＝Ｆ_ｆ，Ｌ ^−１（ｙ）を得て出力する（ステップＳ１４４）。

判定部１４５ｃは、乱数復元値ｓ’と秘密鍵対応値ｃと第２秘密鍵ｋとを入力とし、抽出アルゴリズムＧ（ｓ’）を実行して乱数復元値ｓ’に対応する共通鍵Ｇ（ｓ’）を得、前述の共通鍵暗号方式に則り、共通鍵Ｇ（ｓ’）で第２秘密鍵ｋを復号することで得られる復号値と、第２秘密鍵ｋとが一致するかを判定する。判定部１４５ｃは、例えば、ｋ＝ｃ・Ｇ（ｓ’）^−１を満たすかを判定する（ステップＳ１４５）。ただし、Ｇ（ｓ’）^−１は、Ｇ（ｓ’）の逆元を表す。

ここで、復号値と第２秘密鍵ｋとが一致しないと判定された場合、出力部１４６は拒絶ｒｅｊを出力し（ステップＳ１４７）、処理を終了する。一方、復号値と第２秘密鍵ｋとが一致すると判定された場合、出力部１４６は受け入れａｃｃを出力し（ステップＳ１４６）、処理を終了する。

＜第１実施形態の実施例１＞
第１実施形態の実施例１として、「参考文献１：Hoeteck Wee, “Public key encryption against related key attacks,” in Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, PKC 2012, volume 7293 of Lecture Notes in Computer Science, pages 262-279, Springer, Heidelberg, 2012.」および「参考文献２：Dennis Hofheinz and Eike Kiltz, “Practical chosen ciphertext secure encryption from factoring,” in Antoine Joux, editor, EUROCRYPT 2009, volume 5479 of Lecture Notes in Computer Science, pages 313-332, Springer, Heidelberg, 2009.」に開示された素因数分解仮定に基づく適応的トラップドア関係に本発明を適用した例を示す。本実施例では、Λ，Ω，κおよびωが定数、ｇが位数Ｎの群の生成元、ｒが乱数、ｆ＝ｇ^ΛΩｔ、ｓ＝ｇ^Ωｒ、ｙ＝（ｕ，ｗ）、ｕ＝ｇ^ΩΛｒ、ｗ＝（ｆ・ｇ^ｏｖｋ）^ｒ、共通鍵が（ｌｓｂ_Ｎ（ｓ），ｌｓｂ_Ｎ（ｓ^２），…，ｌｓｂ_Ｎ（ｓ^{ｖ（κ−１）}））、ｖ（ｉ）＝２^ｉ、ｌｓｂ_Ｎ（α）がαを−（Ｎ−１）／２以上（Ｎ−１）／２以下の整数で表現した値に対応する情報となり、乱数復元値が２^ｃ＝ａ*ｏｖｋ＋ｂΛΩを満たす整数ａ，ｂ，ｃに対するｓ’＝（ｗ^ａ・ｕ^ｂ−ａｔ）^{ｖ（ｏｖｋ−ｃ）}である。ただし「α*β」はαとβとの乗算を表し、特に混乱がない場合にはαとβとの乗算を「αβ」と表記する。

本実施例のＳｅｔｕｐ（１^κ），ＴｒａｐＧｅｎ（ｐｐ），Ｓａｍｐ（ｐｐ，ｆ，ｏｖｋ），Ｉｎｖ（ｐｐ，ｔ，ｏｖｋ，ｙ），Ｇ（ｓ）の詳細を示す。簡単のため、κおよびωを正整数、Ω＝２^ω，Λ＝２^κとする。この場合、［０，Ω−１］がラベル情報ｄおよび検証ラベル情報ｄ’の空間となる。ただし、［ι_１，ι_２］はι_１以上ι_２以下の区間を表す。

Ｓｅｔｕｐ（１^κ）は、セキュリティパラメータ１^κを入力とし、κビットの強素数Ｐ，Ｑ≡３（ｍｏｄ４）を一様分布に従ってランダムに選び（Ｐ＝２ｐ＋１，Ｑ＝２ε＋１）、Ｎ＝Ｐ*Ｑとする。さらにＳｅｔｕｐ（１^κ）は、ＱＲ_Ｎ ^＋＝Ｊ_Ｎ ^＋となる符号付商群ＱＲ_Ｎ ^＋を定め、ｇをＱＲ_Ｎ ^＋の生成元とし、共通パラメータｐｐ＝（Ｎ，ｇ）を出力する。ＱＲ_Ｎ ^＋およびＪ_Ｎ ^＋は以下のように定義される。
ＱＲ_Ｎ ^＋＝｛｜ｘ｜｜ｘ∈ＱＲ_Ｎ ^＋｝
Ｊ_Ｎ ^＋＝｛｜ｘ｜｜ｘ∈Ｊ_Ｎ｝ （すなわち、Ｊ_Ｎ ^＋＝Ｊ_Ｎ／（±１））
ただし、Ｚ_Ｎ ^*はＮによる剰余のうちで逆元をもつもの全体がなす群であり、Ｊ_Ｎはヤコビ記号１のものがなすＺ_Ｎ ^*の部分群であり、ＱＲ_Ｎは平方剰余がなす群であり、｜ｘ｜∈Ｚ_Ｎはｘ∈［−（Ｎ−１）／２，（Ｎ−１）／２］とみたときのｘの絶対値である。

ＴｒａｐＧｅｎ（ｐｐ）は、ｐｐを入力とし、区間［１，（Ｎ−１）／４］から一様分布に従ってｔをランダムに選び、ｆ＝μ（ｔ）＝ｇ^ΛΩｔを計算し、鍵ペア（ｆ，ｔ）を出力する。

Ｓａｍｐ（ｐｐ，ｆ，ｏｖｋ）は、ｐｐ，ｆ，ｏｖｋを入力とし、第２乱数ｒについて（ｓ，ｕ）＝（ｇ^Ωｒ，ｇ^ΩΛｒ）を計算し、ｗ＝（ｆ・ｇ^ｏｖｋ）^ｒを計算し、ｓとｙ＝（ｕ，ｗ）とを出力する。

Ｉｎｖ（ｐｐ，ｔ，ｏｖｋ，ｙ）は、ｙ＝（ｕ，ｗ）について、ｕ，ｗ∈ＱＲ_Ｎ ^＋かどうかを確認し、ｕ，ｗ∈ＱＲ_Ｎ ^＋である場合にｗ^ΩΛ＝ｕ^{ｏｖｋ＋ΛΩｔ}かどうかを確認し、ｗ^ΩΛ＝ｕ^{ｏｖｋ＋ΛΩｔ}である場合に、２^ｃ＝ａ*ｏｖｋ＋ｂΛΩとなる整数ａ，ｂ，ｃ∈Ｚに対するｓ’＝（ｗ^ａ・ｕ^ｂ−ａｔ）^{ｖ（ｏｖｋ−ｃ）}を計算し、ｓ’を出力する。

Ｇ（ｓ）は、ｓ∈ＱＲ_Ｎ ^＋を入力として（ｌｓｂ_Ｎ（ｓ），ｌｓｂ_Ｎ（ｓ^２），…，ｌｓｂ_Ｎ（ｓ^{ｖ（κ−１）}））∈｛０，１｝^κを出力する。ｌｓｂ_Ｎ（α）は、αを［−（Ｎ−１）／２，（Ｎ−１）／２］で表現し、さらにそれをビット列表現した場合の最下位ビットを表す。

［Ｇ（ｓ）の可換性］
本実施例のＧ（ｓ）で得られる共通鍵は｛０，１｝^κの元である。｛０，１｝^κは位数２の有限体ＧＦ（２）のκ次拡大体ＧＦ（２）^κとみることができる。従って本実施例のＧ（ｓ）で得られる共通鍵は加法的な可換群の元であるといえる。

［写像μの準同型性］
任意のΔ∈Ｚとｔ∈［１，（Ｎ−１）／４］について以下が成立する。ただし、Ｚは整数集合を表す。
μ（ｔ＋Δ）＝ｇ^{ΛΩ（ｔ＋Δ）}＝ｇ^ΛΩｔ・ｇ^ΛΩΔ＝μ（ｔ）＋μ（Δ）
従って、写像μは準同型性を持つ。

[写像Ｆ_{μ（ｔ），ｏｖｋ}の準同型性]
ｔ∈［１，（Ｎ−１）／４］と任意のｏｖｋについてｓ＝ｇ^Ωｒとしたとき、Ｆ_{μ（ｔ），ｏｖｋ}（ｓ）＝（ｕ，ｗ）＝(ｇ^ΩΛｒ,（ｇ^ΛΩｔ・ｇ^ｏｖｋ）^ｒ)である。このとき任意のΔ∈Ｚについて、以下が成立する。
Ｆ_{μ（ｔ＋Δ），ｏｖｋ}（ｓ）＝(ｇ^ΩΛｒ,（ｇ^{ΛΩ（ｔ＋Δ）}・ｇ^ｏｖｋ）^ｒ)
＝(ｇ^ΩΛｒ,（ｇ^ΛΩｔ・ｇ^ｏｖｋ）^ｒ・ｇ^ΛΩｒΔ)
＝(ｕ，ｗ・ｕ^Δ)
そのため、Ｆ_{μ（ｔ＋Δ），ｏｖｋ}（ｓ）はＦ_{μ（ｔ），ｏｖｋ}（ｓ）とΔとから計算可能であり、写像Ｆ_{μ（ｔ），ｏｖｋ}は準同型性を有する。

＜第１実施形態の実施例２＞
第１実施形態の実施例２として、非特許文献３に開示されたＤＢＤＨ仮定に基づく適応的トラップドア関係に本形態を適用した例を示す。本実施例では、ｖおよびｈが群の元、ｇが群の生成元、ｒが乱数、ｅが双線形写像、第１秘密鍵がｔ、第２秘密鍵がｋであり、ｆ＝ｇ^ｔ、ｓ＝ｖ^ｒ、ｙ＝（ｕ，ｗ）、ｕ＝ｇ^ｒ、ｗ＝（ｆ・ｖ^ｏｖｋ）^ｒであり、共通鍵がｅ（ｓ，ｈ）、乱数復元値がｓ’＝（ｗ・ｕ^−ｔ）^{（１／ｏｖｋ）}である。以下に本実施例のＳｅｔｕｐ（１^κ），ＴｒａｐＧｅｎ（ｐｐ），Ｓａｍｐ（ｐｐ，ｆ，ｏｖｋ），Ｉｎｖ（ｐｐ，ｔ，ｏｖｋ，ｙ），Ｇ（ｓ）の詳細を示す。

Ｓｅｔｕｐ（１^κ）は、セキュリティパラメータ１^κを入力とし、双線形写像用グループ（Ｇ_Ｋ，Ｇ_Ｔ，ｑ，ｅ，ｇ）を生成する。さらにＳｅｔｕｐ（１^κ）は、群Ｇ_Ｋからｖ，ｈ∈Ｇ_Ｋをランダムに選び、共通パラメータｐｐ＝（Ｇ_Ｋ，Ｇ_Ｔ，ｑ，ｅ，ｇ，ｖ，ｈ）を得て出力する。

ＴｒａｐＧｅｎ（ｐｐ）は、ｐｐを入力としてｔ∈Ｚ_ｑをランダムに選び、ｆ＝ｇ^ｔを計算し、鍵ペア（ｆ，ｔ）を出力する。

Ｓａｍｐ（ｐｐ，ｆ，ｏｖｋ）は、ｐｐ，ｆ，ｏｖｋを入力とし、乱数ｒについて（ｓ，ｕ）＝（ｖ^ｒ，ｇ^ｒ）を計算する。さらにＳａｍｐ（ｐｐ，ｆ，ｏｖｋ）は、ｗ＝（ｆ・ｖ^ｏｖｋ）^ｒを計算し、ｓとｙ＝（ｕ，ｗ）を出力する。

Ｉｎｖ（ｐｐ，ｔ，ｏｖｋ，ｙ）は、ｐｐ，ｔ，ｏｖｋ，ｙを入力とし、ｙ＝（ｕ，ｗ）について、ｕ，ｗ∈Ｇ_Ｋかどうかを確認し、ｕ，ｗ∈Ｇ_Ｋである場合にｓ’＝（ｗ・ｕ^−ｔ）^{（１／ｏｖｋ）}を計算する。さらにＩｎｖ（ｐｐ，ｔ，ｏｖｋ，ｙ）は、ｅ（ｇ，ｓ’）＝ｅ（ｖ，ｕ）かどうかを確認し、ｅ（ｇ，ｓ’）＝ｅ（ｖ，ｕ）である場合にｓ’を出力する。

Ｇ（ｓ）は、ｐｐおよびｓ∈Ｇ_Ｋを入力とし、ｅ（ｓ，ｈ）∈Ｇ_Ｔを出力する。

［Ｇ（ｓ）の可換性］
本実施例のＧ（ｓ）で得られる共通鍵は可換群Ｇ_Ｔの元である。

［写像μの準同型性］
任意のΔ∈Ｚ_ｑとｔ∈Ｚ_ｑについて以下が成立する。
μ（ｔ＋Δ）＝ｇ^{（ｔ＋Δ）}＝ｇ^ｔ・ｇ^Δ＝μ（ｔ）＋μ（Δ）
従って、写像μは準同型性を持つ。

[写像Ｆ_{μ（ｔ），ｏｖｋ}の準同型性]
ｔ∈Ｚ_ｑと任意のｏｖｋについてｓ＝ｖ^ｒとしたとき、Ｆ_{μ（ｔ），ｏｖｋ}（ｓ）＝（ｕ，ｗ）＝（ｇ^ｒ，（ｇ^ｔ・ｖ^ｏｖｋ）^ｒ）である。このとき任意のΔ∈Ｚ_ｑについて、以下が成立する。
Ｆ_{μ（ｔ＋Δ），ｏｖｋ}（ｓ）＝（ｇ^ｒ，（ｇ^ｔ＋Δ・ｖ^ｏｖｋ）^ｒ）
＝（ｇ^ｒ，（ｇ^ｔ・ｖ^ｏｖｋ）^ｒ・g^Δｒ）
＝(ｕ，ｗ・ｕ^Δ)
そのため、Ｆ_{μ（ｔ＋Δ），ｏｖｋ}（ｓ）はＦ_{μ（ｔ），ｏｖｋ}（ｓ）とΔとから計算可能であり、写像Ｆ_{μ（ｔ），ｏｖｋ}は準同型性を有する。
［写像μの衝突困難性］
写像μの衝突困難性は、ｇの離散対数仮定により証明可能である。

＜関連鍵攻撃に対する安全性について＞
次に本形態の方式の関連鍵攻撃に対する安全性を説明する。
[関連鍵攻撃に対する安全性の指標]
関連鍵攻撃に対する安全性の指標として、敵Ａの利得を以下のように定義する。

Ｐｒ｜Θ｜は｜Θ｜の確率を表す。ＫＳ（ｐｐ）は、共通パラメータｐｐを入力として秘密鍵ｋｅｙ（第１実施形態ではｋｅｙ＝（ｔ，ｋ））を出力する鍵生成アルゴリズムである。Ｒ−Ｔａｇ_κは関連鍵攻撃の秘密鍵間の写像φとメッセージＭとを入力とし、ｐｐ，ｋｅｙ，Ｍに対する署名ＴＡＧ（ｐｐ，φ（ｋｅｙ），Ｍ）を返す神託機械である。Ｌ_Ｔは神託機械Ｒ−Ｔａｇ_κへの問合せ内容の順序付きリスト（（φ_１，Ｍ_１），...，（φ_η，Ｍ_η））である。任意の多項式時間の敵Ａに対して、式（１）の利得が無視できるとき、メッセージ認証子はＵＦ−ＲＫ−ＣＭＶＡ安全であるという。

本形態の方式は従来構成よりも式（１）の利得を小さくでき、関連鍵攻撃に対する安全性を向上させることができる。特に、本形態の方式は加法的な関連鍵攻撃に対して強い。また、写像μおよびＦ_{μ（ｔ），ｏｖｋ}が準同型性を持つとき、式（１）の利得が無視できることを証明できる（詳細な証明は省略）。以下では非特許文献３に基づくメッセージ認証子方式に対する加法的な関連鍵攻撃を想定し、その関連鍵攻撃が本形態の構成で成功しないことを示す。

[非特許文献３に基づくメッセージ認証子方式]
以下に非特許文献３に基づくメッセージ認証子方式を例示する。
鍵生成：鍵生成アルゴリズムは、秘密鍵（ｔ，ｋ）＝（（ｔ１，ｔ２，ｔ３，ｔ４），ｋ）∈Ｚ_ｑ ^４×Ｇ_Ｋをランダムに選択する。ｇ_１，ｇ_２が群Ｇ_Ｋの生成元であり、暗黙ではあるがｇ_２＝ｇ_１ ^ｔ１である。
認証子生成：認証子生成アルゴリズムは、メッセージＭ∈｛０，１｝^*について、ｒを乱数とし、ｃ_１＝ｇ_１ ^ｒ、ｃ_２＝ｃ_１ ^ｔ１（＝ｇ_２ ^ｒ）、ラベル情報Ｌ＝Ｈ（ｃ_１，ｃ_２，Ｍ）とする。さらに認証子生成アルゴリズムは、ν＝ｃ_１ ^{ｔ２*Ｌ＋ｔ３}，ｃ＝ｋ・ｃ_１ ^ｔ４とし、メッセージ認証子τ＝（ｃ_１，ｃ_２，ν，ｃ）を出力する。
検証：検証アルゴリズムは、τとＭを入力とし、Ｌ’＝Ｈ（ｃ_１，ｃ_２，Ｍ）を得て、ν＝ｃ_１ ^{ｔ２*Ｌ’＋ｔ３}およびｋ＝ｃ・ｃ_１ ^−ｔ４かどうかを確かめ、ν＝ｃ_１ ^{ｔ２*Ｌ’＋ｔ３}およびｋ＝ｃ・ｃ_１ ^−ｔ４であればａｃｃを出力し、そうでないならｒｅｊを出力する。

[加法的な関連鍵攻撃]
上記の非特許文献３に基づくメッセージ認証子方式に対し、以下の加法的な関連鍵攻撃が成功する。
１．敵は偽造メッセージをＭ∈｛０，１｝^*とする。
２．敵は０以外のδ，η∈Ｚ_ｑを適当に選び、Δ＝（０，ξ２，ξ３，０，１_Ｇ）∈Ｚ_ｑ ^４×Ｇ_Ｋとする。ただし、１_Ｇは群Ｇ_Ｋの単位元である。
３．敵は秘密鍵（ｔ，ｋ）＝（（ｔ１，ｔ２，ｔ３，ｔ４），ｋ）を関連鍵φ（ｔ，ｋ）＝（ｔ＋ξ，ｋ）＝（（ｔ１，ｔ２＋ξ２，ｔ３＋ξ３，ｔ４），ｋ）に写す写像φとメッセージＭとで神託機械Ｒ−Ｔａｇ_κに問い合わせる。
４．敵は神託機械Ｒ−Ｔａｇ_κからの返答として以下を受け取る。
τ’＝（ｃ_１，ｃ_２，ν’，ｃ）＝（ｃ_１，ｃ_２，ｃ_１ ^{（ｔ２+ξ２）*Ｌ＋（ｔ３＋ξ３）}，ｋ・ｃ_１ ^ｔ４）
ここで、Ｌ＝Ｈ（ｃ_１，ｃ_２，Ｍ），ｃ_１＝ｇ_１ ^ｒ，ｃ_２＝ｇ_２ ^ｒ（＝ｃ_１ ^ｔ１）である。
５．敵は上記の返答を用い、Ｌ＝Ｈ（ｃ_１，ｃ_２，Ｍ）を計算し、さらにν＝ν’・（ｃ_１ ^ξ２*Ｌ・ｃ_１ ^ξ３）^−１を計算する。
６．敵は偽造したメッセージ認証子τ＝（ｃ_１，ｃ_２，ν，ｃ）を出力する。
このメッセージ認証子τは、秘密鍵（ｔ，ｋ）＝（（ｔ１，ｔ２，ｔ３，ｔ４），ｋ）を用いて偽造メッセージＭに対して得られるものと同一であり、検証アルゴリズムはａｃｃを出力する。よって式（１）の利得は１となる。

この攻撃は秘密鍵（ｔ，ｋ）とその関連鍵φ（ｔ，ｋ）とでラベル情報Ｌが変化しないことに基づいている。これに対し、本形態のラベル情報は、対応鍵ｆ＝μ（ｔ）とメッセージＭとを含む情報に対応するｄ＝Ｈ（ｆ，Ｍ）である。すなわち本形態では、秘密鍵（ｔ，ｋ）に対応するラベル情報Ｈ（μ（ｔ），Ｍ）と、関連鍵φ（ｔ，ｋ）＝（ｔ＋ξ，ｋ）に対応するラベル情報Ｈ（μ（ｔ＋ξ），Ｍ）とが異なる。よって、この攻撃は本形態には通じず、従来方式よりも式（１）の利得が小さくなる。なお、写像Ｈの衝突困難性により、μ（ｔ）≠μ（ｔ＋ξ）かつＨ（μ（ｔ），Ｍ）＝Ｈ（μ（ｔ＋ξ），Ｍ）となる確率は無視できるほど小さい。また、写像μの衝突困難性により、敵がｔ≠ｔ＋ξかつμ（ｔ）＝μ（ｔ＋ξ）となるξを選ぶ確率は無視できるほど小さい。

＜第２実施形態＞
第２実施形態を説明する。第１実施形態は、ラベルに基づくハッシュ証明系に上述の原理を適用したものである。以下では第１実施形態との相違点を説明し、第１実施形態と共通する事項については説明を簡略化する。
［構成］
図２に例示するように、本形態の認証システム２は、設定装置２１０と鍵生成装置２２０と認証子生成装置２３０と検証装置２４０とを有する。設定装置２１０と鍵生成装置２２０と認証子生成装置２３０と検証装置２４０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置２１０と鍵生成装置２２０と認証子生成装置２３０と検証装置２４０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。

認証子生成装置２３０は、入力部１３１と記憶部１３２と対応鍵生成部１３３とラベル情報生成部２３４とメッセージ認証子生成部２３５と出力部２３６とを有する。メッセージ認証子生成部２３５は、サンプリング部２３５ａと写像部２３５ｂとを有する。認証子生成装置２３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み出される。

検証装置２４０は、入力部１４１と記憶部１４２と対応鍵生成部１４３と検証ラベル情報生成部２４４と検証部２４５と出力部２４６とを有する。検証部２４５は、写像部２４５ａと判定部２３４ｂとを有する。検証装置２４０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１４２に格納され、必要に応じて各部に読み出される。

［セットアップ処理］
本形態のセットアップ処理では、設定装置２１０がセキュリティパラメータ１^κを入力とし、鍵生成アルゴリズムＳｅｔｕｐ（１^κ）を実行し、ラベルに基づくハッシュ証明系の共通パラメータｐｐを得て出力する。さらに設定装置２１０は、衝突困難性を持つ写像Ｈ：｛０，１｝^*→Ｇ_Ｋを得て出力する。ｐｐは鍵生成装置２２０に送られて格納され、ｐｐおよびＨは、認証子生成装置２３０および検証装置２４０に送られ、記憶部１３２および１４２にそれぞれ格納される。

［鍵生成処理］
本形態の鍵生成処理では、鍵生成装置２２０が、共通パラメータｐｐを入力とし、秘密鍵ｔをランダムに選択して出力する。秘密鍵ｔは認証子生成装置２３０および検証装置２４０に送られ、記憶部１３２および１４２にそれぞれ格納される。

［認証子生成処理］
任意長のメッセージＭ∈｛０，１｝^*が認証子生成装置２３０の入力部１３１に入力され、記憶部１３２に格納され、以下の認証子生成処理（図４Ａ）が実行される。

対応鍵生成部１３３は、第１秘密鍵ｔを入力とし、第１秘密鍵ｔに写像μを作用させて対応鍵ｆ＝μ（ｔ）を得て出力する（ステップＳ１３１）。

サンプリング部２３５ａは、乱数ｒを一様分布に従って選択し（ステップＳ２３２）、サンプリングアルゴリズムＳａｍｐＲ（ｒ）を実行し、乱数ｒの像ＳａｍｐＲ（ｒ）を乱数対応値υとして得て出力する（ステップＳ２３３）。

ラベル情報生成部２３４は、対応鍵ｆと乱数対応値υとメッセージＭとを入力とし、対応鍵ｆと乱数対応値υとメッセージＭとを含む情報に写像Ｈを作用させてラベル情報ｄ＝Ｈ（ｆ，υ，Ｍ）を得て出力する。対応鍵ｆと乱数対応値υとメッセージＭとを含む情報の例は、対応鍵ｆのビット列表現値と乱数対応値υのビット列表現値とメッセージＭとのビット結合値や、対応鍵ｆのビット列表現値と乱数対応値のビット列表現値υとメッセージＭと付加ビット列とのビット結合値などである。写像Ｈがハッシュ関数である場合、ラベル情報ｄは、対応鍵ｆと乱数対応値υとメッセージＭとを含む情報のダイジェスト値となる（ステップＳ２３４）。

写像部２３５ｂは、共通パラメータｐｐと秘密鍵ｔとラベル情報ｄと乱数対応値υとを入力とし、アルゴリズムＰｒｉｖ（ｐｐ，ｔ，ｄ，υ）を実行し、像ｊ＝Ｄ_ｆ，ｄ（υ）を得て出力する。すなわち、像ｊは秘密鍵ｔ（秘密鍵対応値）およびラベル情報ｄに対応する第２写像Ｄ_ｆ，ｄを乱数対応値υに作用させて得られる（ステップＳ２３５）。

出力部２３６は、乱数対応値υと像ｊ（第２写像Ｄ_ｆ，ｄ（υ）を乱数対応値υに作用させて得られる値）とを含むメッセージ認証子τ＝（υ，ｊ）を得て（ステップＳ２３７）、メッセージ認証子τとメッセージＭとを出力する（ステップＳ１３８）。メッセージ認証子τとメッセージＭとは検証装置２４０に送られる。

［検証処理］
メッセージ認証子τ＝（υ，ｊ）とメッセージＭとが検証装置２４０の入力部１４１に入力され、記憶部１４２に格納され、以下の検証処理（図４Ｂ）が実行される。

対応鍵生成部１４３は、第１秘密鍵ｔを入力とし、第１秘密鍵ｔに写像μを作用させて対応鍵ｆ＝μ（ｔ）を得て出力する（ステップＳ１４１）。

検証ラベル情報生成部２４４は、対応鍵ｆと乱数対応値υとメッセージＭとを入力とし、対応鍵ｆと乱数対応値υとメッセージＭとを含む情報に写像Ｈを作用させて検証ラベル情報ｄ’＝Ｈ（ｆ，υ，Ｍ）∈Ｇ_Ｋを得て出力する。なお、検証ラベル情報生成部１４４での「写像Ｈ」および「対応鍵ｆと乱数対応値υとメッセージＭとを含む情報」の構造は、ラベル情報生成部１３４での「写像Ｈ」および「対応鍵ｆと乱数対応値υとメッセージＭとを含む情報」と同じである（ステップＳ２４２）。

写像部２４５ａは、共通パラメータｐｐと秘密鍵ｔと検証ラベル情報ｄ’と乱数対応値υとを入力とし、アルゴリズムＰｒｉｖ（ｐｐ，ｔ，ｄ’，υ）を実行し、像ｊ’＝Ｄ_ｆ，ｄ’（υ）を得て出力する。すなわち、像ｊ’は秘密鍵ｔ（秘密鍵対応値）および検証ラベル情報ｄ’に対応する第２写像Ｄ_ｆ，ｄ’を乱数対応値υに作用させて得られる（ステップＳ２４３）。

判定部２４５ｂは、得られた像ｊ’とメッセージ認証子τ＝（υ，ｊ）に含まれる像ｊとを入力とし、それらが一致するかを判定する（ステップＳ２３５）。ここで、像ｊ’と像ｊとが一致しないと判定された場合（ｊ’≠ｊ）、出力部２４６は拒絶ｒｅｊを出力し（ステップＳ２４７）、処理を終了する。一方、像ｊ’と像ｊとが一致すると判定された場合（ｊ’＝ｊ）、出力部２４６は受け入れａｃｃを出力し（ステップＳ２４６）、処理を終了する。

＜第２実施形態の実施例＞
第２実施形態の実施例として、ＤＤＨ仮定に基づくハッシュ証明系に本形態を適用した例を示す。本実施例では、ｇ_１およびｇ_２が群Ｇ_Ｋ（可換群、例えば巡回群）の生成元、ラベル情報がｄ、検証ラベル情報がｄ’、秘密鍵がｔ＝（ｘ１，ｘ２，ｙ１，ｙ２）、対応鍵が（Ｘ，Ｙ）＝（ｇ_１ ^ｘ１ｇ_２ ^ｘ２，ｇ_１ ^ｙ１ｇ_２ ^ｙ２）、乱数対応値がυ＝（υ_１，υ_２）∈Ｇ_Ｋ ^２、認証子生成時の第２写像を乱数対応値に作用させて得られる値がｊ＝υ_１ ^{ｘ１*ｄ＋ｙ１}・υ_２ ^{ｘ２*ｄ＋ｙ２}、検証時の第２写像を乱数対応値に作用させて得られる値がｊ’＝υ_１ ^{ｘ１*ｄ’＋ｙ１}・υ_２ ^{ｘ２*ｄ＋ｙ２}である。

以下に本実施例のＳｅｔｕｐ（１^κ），鍵生成アルゴリズム，Ｐｕｂ（ｐｐ，μ（ｔ），Ｌ，ｒ），Ｐｒｉｖ（ｐｐ，ｔ，Ｌ，υ）の詳細を示す。
Ｓｅｔｕｐ（１^κ）は、セキュリティパラメータ１^κを入力とし、ｇ_１およびｇ_２を位数ｑの群Ｇ_Ｋの生成元とし、ｇ_２＝ｇ_１ ^ωを（ｇ_１，ｇ_２）用の言語落とし戸とする。
鍵生成アルゴリズムは、共通パラメータｐｐを入力とし、秘密鍵ｔ＝（ｘ１，ｘ２，ｙ１，ｙ２）∈Ｚ_ｑ ^４を一様分布に従ってランダムに選択し、（ｘ１，ｘ２，ｙ１，ｙ２）に写像μを作用させて対応鍵（Ｘ，Ｙ）＝（ｇ_１ ^ｘ１・ｇ_２ ^ｘ２，ｇ_１ ^ｙ１・ｇ_２ ^ｙ２）を得る。
Ｐｕｂ（ｐｐ，μ（ｔ），ｄ，ｒ）は、ｐｐ，μ（ｔ）＝（Ｘ，Ｙ），ｄ，ｒを入力とし、ｊ＝（Ｘ^ｄ・Ｙ）^ｒを計算して出力する。
Ｐｒｉｖ（ｐｐ，ｔ，ｄ，υ）は、ｐｐ，ｔ，ｄ，υ＝（υ_１，υ_２）を入力とし、ｊ＝υ_１ ^{ｘ１*ｄ＋ｙ１}・υ_２ ^{ｘ２*ｄ＋ｙ２}を計算して出力する。

［写像μの準同型性］
任意のΔ＝（δ１，δ２，η１，η２）∈Ｚ_ｑ ^４とｔ＝（ｘ１，ｘ２，ｙ１，ｙ２）について以下が成立する。
μ（ｔ＋Δ）＝（ｇ_１ ^{ｘ１＋δ１}・ｇ_２ ^{ｘ２＋δ２}，ｇ_１ ^{ｙ１＋η１}・ｇ_２ ^{ｙ２＋η２}）
＝（ｇ１^ｘ１・ｇ２^ｘ２・ｇ１^δ１・ｇ２^δ２，
ｇ１^ｙ１・ｇ２^ｙ２・ｇ１^η１・ｇ２^η２）
＝（ｇ_１ ^ｘ１・ｇ_２ ^ｘ２，ｇ_１ ^ｙ１・ｇ_２ ^ｙ２）・
（ｇ_１ ^δ１・ｇ_２ ^δ２，ｇ_１ ^η１・ｇ_２ ^η２）
＝μ（ｔ）・μ（Δ）
よって写像μは準同型性を有する。

[写像Ｄ_ｆ，ｄの準同型性]
任意のΔ＝（δ１，δ２，η１，η２）、μ（ｔ＋Δ）＝（ｇ_１ ^{ｘ１＋δ１}・ｇ_２ ^{ｘ２＋δ２}，ｇ_１ ^{ｙ１＋η１}・ｇ_２ ^{ｙ２＋η２}）、ラベル情報ｄおよびυ＝（υ_１，υ_２）∈Ｇ_Ｋ ^２について以下が成立する。
Ｄ_{μ（ｔ＋Δ），ｄ}（υ_１，υ_２）＝υ_１ ^{（ｘ１＋δ１）ｄ＋（ｙ１＋η１）}・υ_２ ^{（ｘ２＋δ２）ｄ＋（ｙ２＋η２）}
＝υ_１ ^{ｘ１*ｄ＋ｙ１}・υ_２ ^{ｘ２*ｄ＋ｙ２}・υ_１ ^{δ１*ｄ＋η１}・υ_２ ^{δ２*ｄ＋η２}
＝Ｄ_{μ（ｔ），ｄ}（υ_１，υ_２）・Ｄ_{μ（δ），ｄ}（υ_１，υ_２）
よって写像Ｄ_ｆ，ｄは準同型性を有する。
［写像μの衝突困難性］
写像μの衝突困難性は、（ｇ_１，ｇ_２）の離散対数仮定により証明可能である。

[非特許文献３に基づくメッセージ認証子方式]
以下に非特許文献３に基づくメッセージ認証子方式を例示する。
鍵生成：鍵生成アルゴリズムは、秘密鍵ｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）∈Ｚ_ｑ ^４をランダムに選択する。
認証子生成：認証子生成アルゴリズムは、メッセージＭ∈Ｚ_ｑについて、υ＝（υ_１，υ_２）＝（ｇ_１ ^ｒ，ｇ_２ ^ｒ）をランダムに選び、ラベル情報Ｌ＝Ｍとする。ただしｇ_１，ｇ_２は群Ｇ_Ｋの生成元である。さらに認証子生成アルゴリズムは、ｊ＝Ｄ_ｆ，Ｌ（υ）＝υ_１ ^{ｘ１*Ｌ＋ｙ１}・υ_２ ^{ｘ２*Ｌ＋ｙ２}を計算し、τ＝（υ_１，υ_２，ｊ）をメッセージ認証子として出力する。
検証：検証アルゴリズムは、τとＭを入力とし、ラベル情報Ｌ＝Ｍとし、ｊ’＝Ｄ_ｆ，Ｌ（υ）＝υ_１ ^{ｘ１*Ｌ＋ｙ１}・υ_２ ^{ｘ２*Ｌ＋ｙ２}を計算し、ｊ’＝ ｊであればａｃｃを出力し、そうでないならｒｅｊを出力する。

[加法的な関連鍵攻撃]
上記の非特許文献３に基づくメッセージ認証子方式に対し、以下の加法的な関連鍵攻撃が成功する。
１．敵は偽造メッセージをＭ∈Ｚ_ｑとする。
２．敵は（０，０，０，０）以外のΔ＝（δ１，δ２，η１，η２）∈Ｚ_ｑ ^４を適当に選ぶ
３．敵は秘密鍵ｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）を関連鍵φ（ｔ）＝（ｔ１＋δ１，ｔ２＋δ２，ｔ３＋η１，ｔ４＋η２）に写す写像φとメッセージＭとで神託機械Ｒ−Ｔａｇ_κに問い合わせる。
４．敵は神託機械Ｒ−Ｔａｇ_κからの返答として以下を受け取る。
τ’＝（υ_１，υ_２，ｊ’’）＝（υ_１，υ_２，Ｄ_{μ（ｔ＋ξ），Ｍ}（υ_１，υ_２））＝（υ_１，υ_２，υ_１ ^{（ｘ１＋δ１）Ｍ＋（ｙ１＋η１）}・υ_２ ^{（ｘ２＋δ２）Ｍ＋（ｙ２＋η２）}）
ここで、ｃ_１＝ｇ_１ ^ｒ，ｃ_２＝ｇ_２ ^ｒである。
５．敵は上記の返答を用い、以下を計算する。
ｊ＝ｊ’’・（υ_１ ^{δ１*Ｍ＋η１}・υ_２ ^{δ２*Ｍ＋η２}）^−１
＝υ_１ ^{ｘ１*Ｍ＋ｙ１}・υ_２ ^{ｘ２*Ｍ＋ｙ２}＝Ｄ_{μ（ｔ），Ｍ}（υ_１，υ_２）
６．敵は偽造したメッセージ認証子τ＝（ｃ_１，ｃ_２，ｊ）を出力する。
このメッセージ認証子τは、秘密鍵ｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）を用いて偽造メッセージＭに対して得られるものと同一であり、検証アルゴリズムはａｃｃを出力する。よって式（１）の利得は１となる。

この攻撃は秘密鍵ｔとその関連鍵φ（ｔ）とでラベル情報Ｌ＝Ｍが変化しないことに基づいている。これに対し、本形態のラベル情報は、対応鍵ｆ＝μ（ｔ）と乱数対応値υとメッセージＭとを含む情報に対応するｄ＝Ｈ（ｆ，υ，Ｍ）である。すなわち本形態では、秘密鍵ｔに対応するラベル情報Ｈ（μ（ｔ），υ，Ｍ）と関連鍵φ（ｔ）に対応するラベル情報Ｈ（μ（φ（ｔ）），Ｍ）とが異なる。よって、この攻撃は本形態には通じず、従来方式よりも式（１）の利得が小さくなる。なお、写像Ｈの衝突困難性により、μ（ｔ）≠μ（φ（ｔ））かつＨ（μ（ｔ），υ，Ｍ）＝Ｈ（μ（φ（ｔ）），υ，Ｍ）となる確率は無視できるほど小さい。また、写像μの衝突困難性により、ｔ≠μ（ｔ）かつμ（ｔ）＝μ（φ（ｔ））となる確率は無視できるほど小さい。

＜その他の変形例等＞
本発明は上述の実施の形態に限定されるものではない。例えば、認証子生成装置や検証装置が複数存在してもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。

このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。

上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。

１，２ 認証システム
１１０，２１０ 設定装置
１２０，２２０ 鍵生成装置
１３０，２３０ 認証子生成装置
１４０，２４０ 検証装置

Claims (15)

1. 秘密鍵と対応鍵とが鍵ペアであり、乱数対応値が乱数を含む情報に対応し、秘密鍵対応値が前記秘密鍵を含む情報に対応し、
   前記対応鍵とメッセージとを含む情報に対応するラベル情報を得るラベル情報生成部と、
   前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とに対する像と前記乱数対応値とを含むメッセージ認証子を得るメッセージ認証子生成部と、
   を有する認証子生成装置。
2. 請求項１の認証子生成装置であって、
   前記ラベル情報が、前記対応鍵と前記メッセージとを含む情報に衝突困難性を持つ写像を作用させて得られる値である、
   ことを特徴とする認証子生成装置。
3. 請求項１または２の認証子生成装置であって、
   前記秘密鍵が、第１秘密鍵と第２秘密鍵とを含み、
   前記対応鍵が、前記第１秘密鍵に第１写像を作用させて得られる値であり、
   前記乱数対応値が、前記対応鍵と署名検証鍵とに対応する第２写像を前記乱数に作用させて得られる値であり、
   前記秘密鍵対応値が、前記乱数に対応する共通鍵で前記第２秘密鍵を暗号化することで得られる暗号文であり、
   前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とに対する像が、前記署名検証鍵に対応する署名生成鍵を用いて、前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とを含む情報に対して得られた署名であり、
   前記メッセージ認証子が、前記署名検証鍵と前記乱数対応値と前記秘密鍵対応値と前記署名とを含む、
   ことを特徴とする認証子生成装置。
4. 請求項３の認証子生成装置であって、
   Λ，Ωおよびκが定数、ｇが位数Ｎの群の生成元、ｒが第２乱数、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇ^ΛΩｔ、前記乱数がｓ＝ｇ^Ωｒ、前記乱数対応値がｙ＝（ｕ，ｗ）、ｕ＝ｇ^ΩΛｒ、ｗ＝（ｆ・ｇ^ｏｖｋ）^ｒ、前記署名検証鍵がｏｖｋ、前記共通鍵が（ｌｓｂ_Ｎ（ｓ），ｌｓｂ_Ｎ（ｓ^２），…，ｌｓｂ_Ｎ（ｓ^{ｖ（κ−１）}））、ｖ（ｉ）＝２^ｉ、ｌｓｂ_Ｎ（α）がαを−（Ｎ−１）／２以上（Ｎ−１）／２以下の整数で表現した値に対応する情報である、
   ことを特徴とする認証子生成装置。
5. 請求項３の認証子生成装置であって、
   ｖおよびｈが群の元、ｇが前記群の生成元、ｒが第２乱数、ｅが双線形写像、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇ^ｔ、前記乱数がｓ＝ｖ^ｒ、前記乱数対応値がｙ＝（ｕ，ｗ）、ｕ＝ｇ^ｒ、ｗ＝（ｆ・ｖ^ｏｖｋ）^ｒ、前記署名検証鍵がｏｖｋ、前記共通鍵がｅ（ｓ，ｈ）である、
   ことを特徴とする認証子生成装置。
6. 請求項３から５の何れかの認証子生成装置であって、
   前記第１写像および前記第２写像が準同型性写像である、
   ことを特徴とする認証子生成装置。
7. 秘密鍵と対応鍵とが鍵ペアであり、
   前記対応鍵とメッセージとを含む情報に対応する検証ラベル情報を得る検証ラベル情報生成部と、
   メッセージ認証子と秘密鍵対応値と前記検証ラベル情報とを用い、前記メッセージを検証する検証部と、を有し、
   前記メッセージ認証子が、乱数対応値と前記秘密鍵対応値とラベル情報とに対する像と前記乱数対応値とを含む、
   ことを特徴とする検証装置。
8. 請求項７の検証装置であって、
   前記検証ラベル情報が、前記対応鍵と前記メッセージとを含む情報に衝突困難性を持つ写像を作用させて得られる値である、
   ことを特徴とする検証装置。
9. 請求項７または８の検証装置であって、
   前記秘密鍵が、第１秘密鍵を含み、
   前記対応鍵が、前記第１秘密鍵に第１写像を作用させて得られる値であり、
   前記メッセージ認証子が、署名検証鍵と前記乱数対応値と前記秘密鍵対応値と署名とを含み、
   前記検証部が、前記署名検証鍵を用い、前記乱数対応値と前記秘密鍵対応値と前記検証ラベル情報とを含む情報に対して前記署名が合格であるかを検証する署名検証部を含む、
   ことを特徴とする検証装置。
10. 請求項９の検証装置であって、
    前記秘密鍵が、さらに第２秘密鍵を含み、
    前記検証部が、
    前記対応鍵と前記署名検証鍵とに対応する逆元探索写像を前記乱数対応値に作用させて乱数復元値を得る逆元探索部と、
    前記乱数復元値に対応する共通鍵で前記秘密鍵対応値を復号して得られる復号値と前記第２秘密鍵とが一致するかを判定する判定部と、をさらに含む、
    ことを特徴とする検証装置。
11. 請求項１０の検証装置であって、
    Λ，Ωおよびκが定数、ｇが位数Ｎの群の生成元、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇ^ΛΩｔ、前記乱数復元値がｓ、前記乱数対応値がｙ＝（ｕ，ｗ）、前記署名検証鍵がｏｖｋ、前記共通鍵が（ｌｓｂ_Ｎ（ｓ），ｌｓｂ_Ｎ（ｓ^２），…，ｌｓｂ_Ｎ（ｓ^{ｖ（κ−１）}））、ｖ（ｉ）＝２^ｉ、ｌｓｂ_Ｎ（α）がαを−（Ｎ−１）／２以上（Ｎ−１）／２以下の整数で表現した値に対応する情報であり、
    前記逆元探索部が、２^ｃ＝ａ*ｏｖｋ＋ｂΛΩを満たす整数ａ，ｂ，ｃに対する（ｗ^ａ・ｕ^ｂ−ａｔ）^{ｖ（ｏｖｋ−ｃ）}を前記乱数復元値として得る、
    ことを特徴とする検証装置。
12. 請求項１０の検証装置であって、
    ｖおよびｈが群の元、ｇが前記群の生成元、ｅが双線形写像、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇ^ｔ、前記乱数対応値がｙ＝（ｕ，ｗ）、前記署名検証鍵がｏｖｋ、前記共通鍵がｅ（ｓ，ｈ）であり、
    前記逆元探索部が、（ｗ・ｕ^−ｔ）^{（１／ｏｖｋ）}を前記乱数復元値として得る、
    ことを特徴とする検証装置。
13. 請求項９から１２の何れかの検証装置であって、
    前記第１写像が準同型性写像である、
    ことを特徴とする検証装置。
14. 請求項１から６の何れかの認証子生成装置としてコンピュータを機能させるためのプログラム。
15. 請求項７から１３の何れかの検証装置としてコンピュータを機能させるためのプログラム。

Images