(57)【要約】      （修正有）【課題】自壊することなく関連鍵攻撃に対する安全性を向上させるメッセージ認証子技術を提供する。【解決手段】メッセージ認証子の生成時には、認証子生成装置１３０は対応鍵とメッセージとを含む情報に対応するラベル情報を得、乱数対応値と秘密鍵対応値とラベル情報とに対する像と当該乱数対応値とを含むメッセージ認証子を得る。ただし、秘密鍵と対応鍵とが鍵ペアであり、乱数対応値が乱数を含む情報に対応し、秘密鍵対応値が秘密鍵を含む情報に対応する。検証時には、検証装置１４０は対応鍵とメッセージとを含む情報に対応する検証ラベル情報を得、メッセージ認証子と秘密鍵対応値と検証ラベル情報とを用いてメッセージを検証する。【選択図】図１
2014135684.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵と対応鍵とが鍵ペアであり、乱数対応値が乱数を含む情報に対応し、秘密鍵対応値が前記秘密鍵を含む情報に対応し、
前記対応鍵とメッセージとを含む情報に対応するラベル情報を得るラベル情報生成部と、
前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とに対する像と前記乱数対応値とを含むメッセージ認証子を得るメッセージ認証子生成部と、
を有する認証子生成装置。
【請求項２】
請求項１の認証子生成装置であって、
前記ラベル情報が、前記対応鍵と前記メッセージとを含む情報に衝突困難性を持つ写像を作用させて得られる値である、
ことを特徴とする認証子生成装置。
【請求項３】
請求項１または２の認証子生成装置であって、
前記秘密鍵が、第１秘密鍵と第２秘密鍵とを含み、
前記対応鍵が、前記第１秘密鍵に第１写像を作用させて得られる値であり、
前記乱数対応値が、前記対応鍵と署名検証鍵とに対応する第２写像を前記乱数に作用させて得られる値であり、
前記秘密鍵対応値が、前記乱数に対応する共通鍵で前記第２秘密鍵を暗号化することで得られる暗号文であり、
前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とに対する像が、前記署名検証鍵に対応する署名生成鍵を用いて、前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とを含む情報に対して得られた署名であり、
前記メッセージ認証子が、前記署名検証鍵と前記乱数対応値と前記秘密鍵対応値と前記署名とを含む、
ことを特徴とする認証子生成装置。
【請求項４】
請求項３の認証子生成装置であって、
Λ，Ωおよびκが定数、ｇが位数Ｎの群の生成元、ｒが第２乱数、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇΛΩｔ、前記乱数がｓ＝ｇΩｒ、前記乱数対応値がｙ＝（ｕ，ｗ）、ｕ＝ｇΩΛｒ、ｗ＝（ｆ・ｇｏｖｋ）ｒ、前記署名検証鍵がｏｖｋ、前記共通鍵が（ｌｓｂＮ（ｓ），ｌｓｂＮ（ｓ２），…，ｌｓｂＮ（ｓｖ（κ−１）））、ｖ（ｉ）＝２ｉ、ｌｓｂＮ（α）がαを−（Ｎ−１）／２以上（Ｎ−１）／２以下の整数で表現した値に対応する情報である、
ことを特徴とする認証子生成装置。
【請求項５】
請求項３の認証子生成装置であって、
ｖおよびｈが群の元、ｇが前記群の生成元、ｒが第２乱数、ｅが双線形写像、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇｔ、前記乱数がｓ＝ｖｒ、前記乱数対応値がｙ＝（ｕ，ｗ）、ｕ＝ｇｒ、ｗ＝（ｆ・ｖｏｖｋ）ｒ、前記署名検証鍵がｏｖｋ、前記共通鍵がｅ（ｓ，ｈ）である、
ことを特徴とする認証子生成装置。
【請求項６】
請求項１または２の認証子生成装置であって、
前記対応鍵が、前記秘密鍵に第１写像を作用させて得られる値であり、
前記乱数対応値が、前記乱数の像であり、
前記ラベル情報が、前記対応鍵と前記乱数対応値と前記メッセージとを含む情報に、前記衝突困難性を持つ写像を作用させて得られる情報であり、
前記秘密鍵対応値が、前記秘密鍵であり、
前記乱数対応値と前記秘密鍵対応値と前記ラベル情報とに対する像が、前記秘密鍵および前記ラベル情報に対応する第２写像を前記乱数対応値に作用させて得られる値であり、
前記メッセージ認証子が、前記第２写像を前記乱数対応値に作用させて得られる値と、前記乱数対応値と、を含む、
ことを特徴とする認証子生成装置。
【請求項７】
請求項６の認証子生成装置であって、
ｇ１およびｇ２が群ＧＫの生成元、前記ラベル情報がｄ、前記秘密鍵が（ｘ１，ｘ２，ｙ１，ｙ２）、前記対応鍵が（Ｘ，Ｙ）＝（ｇ１ｘ１・ｇ２ｘ２，ｇ１ｙ１・ｇ２ｙ２）、前記乱数対応値が（υ１，υ２）∈ＧＫ２、前記第２写像を前記乱数対応値に作用させて得られる値がυ１ｘ１*ｄ＋ｙ１・υ２ｘ２*ｄ＋ｙ２である、
ことを特徴とする認証子生成装置。
【請求項８】
請求項３から７の何れかの認証子生成装置であって、
前記第１写像および前記第２写像が準同型性写像である、
ことを特徴とする認証子生成装置。
【請求項９】
秘密鍵と対応鍵とが鍵ペアであり、
前記対応鍵とメッセージとを含む情報に対応する検証ラベル情報を得る検証ラベル情報生成部と、
メッセージ認証子と秘密鍵対応値と前記検証ラベル情報とを用い、前記メッセージを検証する検証部と、を有し、
前記メッセージ認証子が、乱数対応値と前記秘密鍵対応値とラベル情報とに対する像と前記乱数対応値とを含む、
ことを特徴とする検証装置。
【請求項１０】
請求項９の検証装置であって、
前記検証ラベル情報が、前記対応鍵と前記メッセージとを含む情報に衝突困難性を持つ写像を作用させて得られる値である、
ことを特徴とする検証装置。
【請求項１１】
請求項９または１０の検証装置であって、
前記秘密鍵が、第１秘密鍵を含み、
前記対応鍵が、前記第１秘密鍵に第１写像を作用させて得られる値であり、
前記メッセージ認証子が、署名検証鍵と前記乱数対応値と前記秘密鍵対応値と署名とを含み、
前記検証部が、前記署名検証鍵を用い、前記乱数対応値と前記秘密鍵対応値と前記検証ラベル情報とを含む情報に対して前記署名が合格であるかを検証する署名検証部を含む、
ことを特徴とする検証装置。
【請求項１２】
請求項１１の検証装置であって、
前記秘密鍵が、さらに第２秘密鍵を含み、
前記検証部が、
前記対応鍵と前記署名検証鍵とに対応する逆元探索写像を前記乱数対応値に作用させて乱数復元値を得る逆元探索部と、
前記乱数復元値に対応する共通鍵で前記秘密鍵対応値を復号して得られる復号値と前記第２秘密鍵とが一致するかを判定する判定部と、をさらに含む、
ことを特徴とする検証装置。
【請求項１３】
請求項１２の検証装置であって、
Λ，Ωおよびκが定数、ｇが位数Ｎの群の生成元、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇΛΩｔ、前記乱数復元値がｓ、前記乱数対応値がｙ＝（ｕ，ｗ）、前記署名検証鍵がｏｖｋ、前記共通鍵が（ｌｓｂＮ（ｓ），ｌｓｂＮ（ｓ２），…，ｌｓｂＮ（ｓｖ（κ−１）））、ｖ（ｉ）＝２ｉ、ｌｓｂＮ（α）がαを−（Ｎ−１）／２以上（Ｎ−１）／２以下の整数で表現した値に対応する情報であり、
前記逆元探索部が、２ｃ＝ａ*ｏｖｋ＋ｂΛΩを満たす整数ａ，ｂ，ｃに対する（ｗａ・ｕｂ−ａｔ）ｖ（ｏｖｋ−ｃ）を前記乱数復元値として得る、
ことを特徴とする検証装置。
【請求項１４】
請求項１２の検証装置であって、
ｖおよびｈが群の元、ｇが前記群の生成元、ｅが双線形写像、前記第１秘密鍵がｔ、前記第２秘密鍵がｋ、前記対応鍵がｆ＝ｇｔ、前記乱数対応値がｙ＝（ｕ，ｗ）、前記署名検証鍵がｏｖｋ、前記共通鍵がｅ（ｓ，ｈ）であり、
前記逆元探索部が、（ｗ・ｕ−ｔ）（１／ｏｖｋ）を前記乱数復元値として得る、
ことを特徴とする検証装置。
【請求項１５】
請求項９または１０の検証装置であって、
前記秘密鍵に対応する対応鍵が、前記秘密鍵に第１写像を作用させて得られる値であり、
前記検証ラベル情報が、前記対応鍵と前記乱数対応値と前記メッセージとを含む情報に前記衝突困難性を持つ写像を作用させて得られる情報であり、
前記秘密鍵対応値が、前記秘密鍵であり、
前記検証部が、前記秘密鍵と前記検証ラベル情報とに対応する第２写像を前記乱数対応値に作用させて得られる値と前記メッセージ認証子に含まれる前記像とが一致するか検証する判定部を含む、
ことを特徴とする検証装置。
【請求項１６】
請求項１５の検証装置であって、
ｇ１およびｇ２が群ＧＫの生成元、前記検証ラベル情報がｄ’、前記秘密鍵が（ｘ１，ｘ２，ｙ１，ｙ２）、前記対応鍵が（Ｘ，Ｙ）＝（ｇ１ｘ１・ｇ２ｘ２，ｇ１ｙ１・ｇ２ｙ２）、前記乱数対応値が（υ１，υ２）∈ＧＫ２、前記第２写像を前記乱数対応値に作用させて得られる値がυ１ｘ１*ｄ’＋ｙ１・υ２ｘ２*ｄ＋ｙ２である、
ことを特徴とする検証装置。
【請求項１７】
請求項９から１６の何れかの検証装置であって、
前記第１写像および前記第２写像が準同型性写像である、
ことを特徴とする検証装置。
【請求項１８】
請求項１から８の何れかの認証子生成装置としてコンピュータを機能させるためのプログラム。
【請求項１９】
請求項９から１７の何れかの検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関し、特に、メッセージ認証子技術に関する。
【背景技術】
【０００２】
証明可能安全性を持つメッセージ認証子が、共通鍵暗号のプリミティブの安全性の下で提案されている。また、通常の安全性を持つ暗号方式を関連鍵攻撃に対する安全性をもつ方式に変換する技術もいくつか知られている（例えば、非特許文献１から３参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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Δｒ）
＝(ｕ，ｗ・ｕΔ)
そのため、Ｆμ（ｔ＋Δ），ｏｖｋ（ｓ）はＦμ（ｔ），ｏｖｋ（ｓ）とΔとから計算可能であり、写像Ｆμ（ｔ），ｏｖｋは準同型性を有する。
［写像μの衝突困難性］
写像μの衝突困難性は、ｇの離散対数仮定により証明可能である。
【００５５】
＜関連鍵攻撃に対する安全性について＞
次に本形態の方式の関連鍵攻撃に対する安全性を説明する。
[関連鍵攻撃に対する安全性の指標]
関連鍵攻撃に対する安全性の指標として、敵Ａの利得を以下のように定義する。
【数１】
2014135684.tif 000003
Ｐｒ｜Θ｜は｜Θ｜の確率を表す。ＫＳ（ｐｐ）は、共通パラメータｐｐを入力として秘密鍵ｋｅｙ（第１実施形態ではｋｅｙ＝（ｔ，ｋ））を出力する鍵生成アルゴリズムである。Ｒ−Ｔａｇκは関連鍵攻撃の秘密鍵間の写像φとメッセージＭとを入力とし、ｐｐ，ｋｅｙ，Ｍに対する署名ＴＡＧ（ｐｐ，φ（ｋｅｙ），Ｍ）を返す神託機械である。ＬＴは神託機械Ｒ−Ｔａｇκへの問合せ内容の順序付きリスト（（φ１，Ｍ１），...，（φη，Ｍη））である。任意の多項式時間の敵Ａに対して、式（１）の利得が無視できるとき、メッセージ認証子はＵＦ−ＲＫ−ＣＭＶＡ安全であるという。
【００５６】
本形態の方式は従来構成よりも式（１）の利得を小さくでき、関連鍵攻撃に対する安全性を向上させることができる。特に、本形態の方式は加法的な関連鍵攻撃に対して強い。また、写像μおよびＦμ（ｔ），ｏｖｋが準同型性を持つとき、式（１）の利得が無視できることを証明できる（詳細な証明は省略）。以下では非特許文献３に基づくメッセージ認証子方式に対する加法的な関連鍵攻撃を想定し、その関連鍵攻撃が本形態の構成で成功しないことを示す。
【００５７】
[非特許文献３に基づくメッセージ認証子方式]
以下に非特許文献３に基づくメッセージ認証子方式を例示する。
鍵生成：鍵生成アルゴリズムは、秘密鍵（ｔ，ｋ）＝（（ｔ１，ｔ２，ｔ３，ｔ４），ｋ）∈Ｚｑ４×ＧＫをランダムに選択する。ｇ１，ｇ２が群ＧＫの生成元であり、暗黙ではあるがｇ２＝ｇ１ｔ１である。
認証子生成：認証子生成アルゴリズムは、メッセージＭ∈｛０，１｝*について、ｒを乱数とし、ｃ１＝ｇ１ｒ、ｃ２＝ｃ１ｔ１（＝ｇ２ｒ）、ラベル情報Ｌ＝Ｈ（ｃ１，ｃ２，Ｍ）とする。さらに認証子生成アルゴリズムは、ν＝ｃ１ｔ２*Ｌ＋ｔ３，ｃ＝ｋ・ｃ１ｔ４とし、メッセージ認証子τ＝（ｃ１，ｃ２，ν，ｃ）を出力する。
検証：検証アルゴリズムは、τとＭを入力とし、Ｌ’＝Ｈ（ｃ１，ｃ２，Ｍ）を得て、ν＝ｃ１ｔ２*Ｌ’＋ｔ３およびｋ＝ｃ・ｃ１−ｔ４かどうかを確かめ、ν＝ｃ１ｔ２*Ｌ’＋ｔ３およびｋ＝ｃ・ｃ１−ｔ４であればａｃｃを出力し、そうでないならｒｅｊを出力する。
【００５８】
[加法的な関連鍵攻撃]
上記の非特許文献３に基づくメッセージ認証子方式に対し、以下の加法的な関連鍵攻撃が成功する。
１．敵は偽造メッセージをＭ∈｛０，１｝*とする。
２．敵は０以外のδ，η∈Ｚｑを適当に選び、Δ＝（０，ξ２，ξ３，０，１Ｇ）∈Ｚｑ４×ＧＫとする。ただし、１Ｇは群ＧＫの単位元である。
３．敵は秘密鍵（ｔ，ｋ）＝（（ｔ１，ｔ２，ｔ３，ｔ４），ｋ）を関連鍵φ（ｔ，ｋ）＝（ｔ＋ξ，ｋ）＝（（ｔ１，ｔ２＋ξ２，ｔ３＋ξ３，ｔ４），ｋ）に写す写像φとメッセージＭとで神託機械Ｒ−Ｔａｇκに問い合わせる。
４．敵は神託機械Ｒ−Ｔａｇκからの返答として以下を受け取る。
τ’＝（ｃ１，ｃ２，ν’，ｃ）＝（ｃ１，ｃ２，ｃ１（ｔ２+ξ２）*Ｌ＋（ｔ３＋ξ３），ｋ・ｃ１ｔ４）
ここで、Ｌ＝Ｈ（ｃ１，ｃ２，Ｍ），ｃ１＝ｇ１ｒ，ｃ２＝ｇ２ｒ（＝ｃ１ｔ１）である。
５．敵は上記の返答を用い、Ｌ＝Ｈ（ｃ１，ｃ２，Ｍ）を計算し、さらにν＝ν’・（ｃ１ξ２*Ｌ・ｃ１ξ３）−１を計算する。
６．敵は偽造したメッセージ認証子τ＝（ｃ１，ｃ２，ν，ｃ）を出力する。
このメッセージ認証子τは、秘密鍵（ｔ，ｋ）＝（（ｔ１，ｔ２，ｔ３，ｔ４），ｋ）を用いて偽造メッセージＭに対して得られるものと同一であり、検証アルゴリズムはａｃｃを出力する。よって式（１）の利得は１となる。
【００５９】
この攻撃は秘密鍵（ｔ，ｋ）とその関連鍵φ（ｔ，ｋ）とでラベル情報Ｌが変化しないことに基づいている。これに対し、本形態のラベル情報は、対応鍵ｆ＝μ（ｔ）とメッセージＭとを含む情報に対応するｄ＝Ｈ（ｆ，Ｍ）である。すなわち本形態では、秘密鍵（ｔ，ｋ）に対応するラベル情報Ｈ（μ（ｔ），Ｍ）と、関連鍵φ（ｔ，ｋ）＝（ｔ＋ξ，ｋ）に対応するラベル情報Ｈ（μ（ｔ＋ξ），Ｍ）とが異なる。よって、この攻撃は本形態には通じず、従来方式よりも式（１）の利得が小さくなる。なお、写像Ｈの衝突困難性により、μ（ｔ）≠μ（ｔ＋ξ）かつＨ（μ（ｔ），Ｍ）＝Ｈ（μ（ｔ＋ξ），Ｍ）となる確率は無視できるほど小さい。また、写像μの衝突困難性により、敵がｔ≠ｔ＋ξかつμ（ｔ）＝μ（ｔ＋ξ）となるξを選ぶ確率は無視できるほど小さい。
【００６０】
＜第２実施形態＞
第２実施形態を説明する。第１実施形態は、ラベルに基づくハッシュ証明系に上述の原理を適用したものである。以下では第１実施形態との相違点を説明し、第１実施形態と共通する事項については説明を簡略化する。
［構成］
図２に例示するように、本形態の認証システム２は、設定装置２１０と鍵生成装置２２０と認証子生成装置２３０と検証装置２４０とを有する。設定装置２１０と鍵生成装置２２０と認証子生成装置２３０と検証装置２４０とは、それぞれ、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成された特別な装置である。設定装置２１０と鍵生成装置２２０と認証子生成装置２３０と検証装置２４０は、ネットワークや可搬型記録媒体等を通じ、情報のやり取りが可能なように構成されている。
【００６１】
認証子生成装置２３０は、入力部１３１と記憶部１３２と対応鍵生成部１３３とラベル情報生成部２３４とメッセージ認証子生成部２３５と出力部２３６とを有する。メッセージ認証子生成部２３５は、サンプリング部２３５ａと写像部２３５ｂとを有する。認証子生成装置２３０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１３２に格納され、必要に応じて各部に読み出される。
【００６２】
検証装置２４０は、入力部１４１と記憶部１４２と対応鍵生成部１４３と検証ラベル情報生成部２４４と検証部２４５と出力部２４６とを有する。検証部２４５は、写像部２４５ａと判定部２３４ｂとを有する。検証装置２４０は、図示していない制御部の制御のもとで各処理を実行する。各部で得られたデータは記憶部１４２に格納され、必要に応じて各部に読み出される。
【００６３】
［セットアップ処理］
本形態のセットアップ処理では、設定装置２１０がセキュリティパラメータ１κを入力とし、鍵生成アルゴリズムＳｅｔｕｐ（１κ）を実行し、ラベルに基づくハッシュ証明系の共通パラメータｐｐを得て出力する。さらに設定装置２１０は、衝突困難性を持つ写像Ｈ：｛０，１｝*→ＧＫを得て出力する。ｐｐは鍵生成装置２２０に送られて格納され、ｐｐおよびＨは、認証子生成装置２３０および検証装置２４０に送られ、記憶部１３２および１４２にそれぞれ格納される。
【００６４】
［鍵生成処理］
本形態の鍵生成処理では、鍵生成装置２２０が、共通パラメータｐｐを入力とし、秘密鍵ｔをランダムに選択して出力する。秘密鍵ｔは認証子生成装置２３０および検証装置２４０に送られ、記憶部１３２および１４２にそれぞれ格納される。
【００６５】
［認証子生成処理］
任意長のメッセージＭ∈｛０，１｝*が認証子生成装置２３０の入力部１３１に入力され、記憶部１３２に格納され、以下の認証子生成処理（図４Ａ）が実行される。
【００６６】
対応鍵生成部１３３は、第１秘密鍵ｔを入力とし、第１秘密鍵ｔに写像μを作用させて対応鍵ｆ＝μ（ｔ）を得て出力する（ステップＳ１３１）。
【００６７】
サンプリング部２３５ａは、乱数ｒを一様分布に従って選択し（ステップＳ２３２）、サンプリングアルゴリズムＳａｍｐＲ（ｒ）を実行し、乱数ｒの像ＳａｍｐＲ（ｒ）を乱数対応値υとして得て出力する（ステップＳ２３３）。
【００６８】
ラベル情報生成部２３４は、対応鍵ｆと乱数対応値υとメッセージＭとを入力とし、対応鍵ｆと乱数対応値υとメッセージＭとを含む情報に写像Ｈを作用させてラベル情報ｄ＝Ｈ（ｆ，υ，Ｍ）を得て出力する。対応鍵ｆと乱数対応値υとメッセージＭとを含む情報の例は、対応鍵ｆのビット列表現値と乱数対応値υのビット列表現値とメッセージＭとのビット結合値や、対応鍵ｆのビット列表現値と乱数対応値のビット列表現値υとメッセージＭと付加ビット列とのビット結合値などである。写像Ｈがハッシュ関数である場合、ラベル情報ｄは、対応鍵ｆと乱数対応値υとメッセージＭとを含む情報のダイジェスト値となる（ステップＳ２３４）。
【００６９】
写像部２３５ｂは、共通パラメータｐｐと秘密鍵ｔとラベル情報ｄと乱数対応値υとを入力とし、アルゴリズムＰｒｉｖ（ｐｐ，ｔ，ｄ，υ）を実行し、像ｊ＝Ｄｆ，ｄ（υ）を得て出力する。すなわち、像ｊは秘密鍵ｔ（秘密鍵対応値）およびラベル情報ｄに対応する第２写像Ｄｆ，ｄを乱数対応値υに作用させて得られる（ステップＳ２３５）。
【００７０】
出力部２３６は、乱数対応値υと像ｊ（第２写像Ｄｆ，ｄ（υ）を乱数対応値υに作用させて得られる値）とを含むメッセージ認証子τ＝（υ，ｊ）を得て（ステップＳ２３７）、メッセージ認証子τとメッセージＭとを出力する（ステップＳ１３８）。メッセージ認証子τとメッセージＭとは検証装置２４０に送られる。
【００７１】
［検証処理］
メッセージ認証子τ＝（υ，ｊ）とメッセージＭとが検証装置２４０の入力部１４１に入力され、記憶部１４２に格納され、以下の検証処理（図４Ｂ）が実行される。
【００７２】
対応鍵生成部１４３は、第１秘密鍵ｔを入力とし、第１秘密鍵ｔに写像μを作用させて対応鍵ｆ＝μ（ｔ）を得て出力する（ステップＳ１４１）。
【００７３】
検証ラベル情報生成部２４４は、対応鍵ｆと乱数対応値υとメッセージＭとを入力とし、対応鍵ｆと乱数対応値υとメッセージＭとを含む情報に写像Ｈを作用させて検証ラベル情報ｄ’＝Ｈ（ｆ，υ，Ｍ）∈ＧＫを得て出力する。なお、検証ラベル情報生成部１４４での「写像Ｈ」および「対応鍵ｆと乱数対応値υとメッセージＭとを含む情報」の構造は、ラベル情報生成部１３４での「写像Ｈ」および「対応鍵ｆと乱数対応値υとメッセージＭとを含む情報」と同じである（ステップＳ２４２）。
【００７４】
写像部２４５ａは、共通パラメータｐｐと秘密鍵ｔと検証ラベル情報ｄ’と乱数対応値υとを入力とし、アルゴリズムＰｒｉｖ（ｐｐ，ｔ，ｄ’，υ）を実行し、像ｊ’＝Ｄｆ，ｄ’（υ）を得て出力する。すなわち、像ｊ’は秘密鍵ｔ（秘密鍵対応値）および検証ラベル情報ｄ’に対応する第２写像Ｄｆ，ｄ’を乱数対応値υに作用させて得られる（ステップＳ２４３）。
【００７５】
判定部２４５ｂは、得られた像ｊ’とメッセージ認証子τ＝（υ，ｊ）に含まれる像ｊとを入力とし、それらが一致するかを判定する（ステップＳ２３５）。ここで、像ｊ’と像ｊとが一致しないと判定された場合（ｊ’≠ｊ）、出力部２４６は拒絶ｒｅｊを出力し（ステップＳ２４７）、処理を終了する。一方、像ｊ’と像ｊとが一致すると判定された場合（ｊ’＝ｊ）、出力部２４６は受け入れａｃｃを出力し（ステップＳ２４６）、処理を終了する。
【００７６】
＜第２実施形態の実施例＞
第２実施形態の実施例として、ＤＤＨ仮定に基づくハッシュ証明系に本形態を適用した例を示す。本実施例では、ｇ１およびｇ２が群ＧＫ（可換群、例えば巡回群）の生成元、ラベル情報がｄ、検証ラベル情報がｄ’、秘密鍵がｔ＝（ｘ１，ｘ２，ｙ１，ｙ２）、対応鍵が（Ｘ，Ｙ）＝（ｇ１ｘ１ｇ２ｘ２，ｇ１ｙ１ｇ２ｙ２）、乱数対応値がυ＝（υ１，υ２）∈ＧＫ２、認証子生成時の第２写像を乱数対応値に作用させて得られる値がｊ＝υ１ｘ１*ｄ＋ｙ１・υ２ｘ２*ｄ＋ｙ２、検証時の第２写像を乱数対応値に作用させて得られる値がｊ’＝υ１ｘ１*ｄ’＋ｙ１・υ２ｘ２*ｄ＋ｙ２である。
【００７７】
以下に本実施例のＳｅｔｕｐ（１κ），鍵生成アルゴリズム，Ｐｕｂ（ｐｐ，μ（ｔ），Ｌ，ｒ），Ｐｒｉｖ（ｐｐ，ｔ，Ｌ，υ）の詳細を示す。
Ｓｅｔｕｐ（１κ）は、セキュリティパラメータ１κを入力とし、ｇ１およびｇ２を位数ｑの群ＧＫの生成元とし、ｇ２＝ｇ１ωを（ｇ１，ｇ２）用の言語落とし戸とする。
鍵生成アルゴリズムは、共通パラメータｐｐを入力とし、秘密鍵ｔ＝（ｘ１，ｘ２，ｙ１，ｙ２）∈Ｚｑ４を一様分布に従ってランダムに選択し、（ｘ１，ｘ２，ｙ１，ｙ２）に写像μを作用させて対応鍵（Ｘ，Ｙ）＝（ｇ１ｘ１・ｇ２ｘ２，ｇ１ｙ１・ｇ２ｙ２）を得る。
Ｐｕｂ（ｐｐ，μ（ｔ），ｄ，ｒ）は、ｐｐ，μ（ｔ）＝（Ｘ，Ｙ），ｄ，ｒを入力とし、ｊ＝（Ｘｄ・Ｙ）ｒを計算して出力する。
Ｐｒｉｖ（ｐｐ，ｔ，ｄ，υ）は、ｐｐ，ｔ，ｄ，υ＝（υ１，υ２）を入力とし、ｊ＝υ１ｘ１*ｄ＋ｙ１・υ２ｘ２*ｄ＋ｙ２を計算して出力する。
【００７８】
［写像μの準同型性］
任意のΔ＝（δ１，δ２，η１，η２）∈Ｚｑ４とｔ＝（ｘ１，ｘ２，ｙ１，ｙ２）について以下が成立する。
μ（ｔ＋Δ）＝（ｇ１ｘ１＋δ１・ｇ２ｘ２＋δ２，ｇ１ｙ１＋η１・ｇ２ｙ２＋η２）
＝（ｇ１ｘ１・ｇ２ｘ２・ｇ１δ１・ｇ２δ２，
ｇ１ｙ１・ｇ２ｙ２・ｇ１η１・ｇ２η２）
＝（ｇ１ｘ１・ｇ２ｘ２，ｇ１ｙ１・ｇ２ｙ２）・
（ｇ１δ１・ｇ２δ２，ｇ１η１・ｇ２η２）
＝μ（ｔ）・μ（Δ）
よって写像μは準同型性を有する。
【００７９】
[写像Ｄｆ，ｄの準同型性]
任意のΔ＝（δ１，δ２，η１，η２）、μ（ｔ＋Δ）＝（ｇ１ｘ１＋δ１・ｇ２ｘ２＋δ２，ｇ１ｙ１＋η１・ｇ２ｙ２＋η２）、ラベル情報ｄおよびυ＝（υ１，υ２）∈ＧＫ２について以下が成立する。
Ｄμ（ｔ＋Δ），ｄ（υ１，υ２）＝υ１（ｘ１＋δ１）ｄ＋（ｙ１＋η１）・υ２（ｘ２＋δ２）ｄ＋（ｙ２＋η２）
＝υ１ｘ１*ｄ＋ｙ１・υ２ｘ２*ｄ＋ｙ２・υ１δ１*ｄ＋η１・υ２δ２*ｄ＋η２
＝Ｄμ（ｔ），ｄ（υ１，υ２）・Ｄμ（δ），ｄ（υ１，υ２）
よって写像Ｄｆ，ｄは準同型性を有する。
［写像μの衝突困難性］
写像μの衝突困難性は、（ｇ１，ｇ２）の離散対数仮定により証明可能である。
【００８０】
[非特許文献３に基づくメッセージ認証子方式]
以下に非特許文献３に基づくメッセージ認証子方式を例示する。
鍵生成：鍵生成アルゴリズムは、秘密鍵ｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）∈Ｚｑ４をランダムに選択する。
認証子生成：認証子生成アルゴリズムは、メッセージＭ∈Ｚｑについて、υ＝（υ１，υ２）＝（ｇ１ｒ，ｇ２ｒ）をランダムに選び、ラベル情報Ｌ＝Ｍとする。ただしｇ１，ｇ２は群ＧＫの生成元である。さらに認証子生成アルゴリズムは、ｊ＝Ｄｆ，Ｌ（υ）＝υ１ｘ１*Ｌ＋ｙ１・υ２ｘ２*Ｌ＋ｙ２を計算し、τ＝（υ１，υ２，ｊ）をメッセージ認証子として出力する。
検証：検証アルゴリズムは、τとＭを入力とし、ラベル情報Ｌ＝Ｍとし、ｊ’＝Ｄｆ，Ｌ（υ）＝υ１ｘ１*Ｌ＋ｙ１・υ２ｘ２*Ｌ＋ｙ２を計算し、ｊ’＝ ｊであればａｃｃを出力し、そうでないならｒｅｊを出力する。
【００８１】
[加法的な関連鍵攻撃]
上記の非特許文献３に基づくメッセージ認証子方式に対し、以下の加法的な関連鍵攻撃が成功する。
１．敵は偽造メッセージをＭ∈Ｚｑとする。
２．敵は（０，０，０，０）以外のΔ＝（δ１，δ２，η１，η２）∈Ｚｑ４を適当に選ぶ
３．敵は秘密鍵ｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）を関連鍵φ（ｔ）＝（ｔ１＋δ１，ｔ２＋δ２，ｔ３＋η１，ｔ４＋η２）に写す写像φとメッセージＭとで神託機械Ｒ−Ｔａｇκに問い合わせる。
４．敵は神託機械Ｒ−Ｔａｇκからの返答として以下を受け取る。
τ’＝（υ１，υ２，ｊ’’）＝（υ１，υ２，Ｄμ（ｔ＋ξ），Ｍ（υ１，υ２））＝（υ１，υ２，υ１（ｘ１＋δ１）Ｍ＋（ｙ１＋η１）・υ２（ｘ２＋δ２）Ｍ＋（ｙ２＋η２））
ここで、ｃ１＝ｇ１ｒ，ｃ２＝ｇ２ｒである。
５．敵は上記の返答を用い、以下を計算する。
ｊ＝ｊ’’・（υ１δ１*Ｍ＋η１・υ２δ２*Ｍ＋η２）−１
＝υ１ｘ１*Ｍ＋ｙ１・υ２ｘ２*Ｍ＋ｙ２＝Ｄμ（ｔ），Ｍ（υ１，υ２）
６．敵は偽造したメッセージ認証子τ＝（ｃ１，ｃ２，ｊ）を出力する。
このメッセージ認証子τは、秘密鍵ｔ＝（ｔ１，ｔ２，ｔ３，ｔ４）を用いて偽造メッセージＭに対して得られるものと同一であり、検証アルゴリズムはａｃｃを出力する。よって式（１）の利得は１となる。
【００８２】
この攻撃は秘密鍵ｔとその関連鍵φ（ｔ）とでラベル情報Ｌ＝Ｍが変化しないことに基づいている。これに対し、本形態のラベル情報は、対応鍵ｆ＝μ（ｔ）と乱数対応値υとメッセージＭとを含む情報に対応するｄ＝Ｈ（ｆ，υ，Ｍ）である。すなわち本形態では、秘密鍵ｔに対応するラベル情報Ｈ（μ（ｔ），υ，Ｍ）と関連鍵φ（ｔ）に対応するラベル情報Ｈ（μ（φ（ｔ）），Ｍ）とが異なる。よって、この攻撃は本形態には通じず、従来方式よりも式（１）の利得が小さくなる。なお、写像Ｈの衝突困難性により、μ（ｔ）≠μ（φ（ｔ））かつＨ（μ（ｔ），υ，Ｍ）＝Ｈ（μ（φ（ｔ）），υ，Ｍ）となる確率は無視できるほど小さい。また、写像μの衝突困難性により、ｔ≠μ（ｔ）かつμ（ｔ）＝μ（φ（ｔ））となる確率は無視できるほど小さい。
【００８３】
＜その他の変形例等＞
本発明は上述の実施の形態に限定されるものではない。例えば、認証子生成装置や検証装置が複数存在してもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００８４】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００８５】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００８７】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００８８】
１，２  認証システム
１１０，２１０  設定装置
１２０，２２０  鍵生成装置
１３０，２３０  認証子生成装置
１４０，２４０  検証装置
【図１】
2014135684.tif 000004
【図２】
2014135684.tif 000005
【図３】
2014135684.tif 000006
【図４】
2014135684.tif 000007