(57)【要約】【課題】署名検証時の計算コストを削減可能なタグ付き使い捨て署名技術を提供する。【解決手段】署名生成時に、群Ｇ２の任意の元Ａ２に対応するタグＴ２＝Ａ２ｙを得、メッセージとタグＴ２とを含む情報の像ｃを得、群Ｇ２の元Ｚ２＝Ａ２Ｘ２−ｃを得る。署名検証時に、ｅ（Ｙ１，Ｚ２）・Ｖｃ＝ｅ（ｇ１，Ｔ２）の関係を満たすことを必要条件とする検証条件を満たすかを判定する。ただし、Ｇ１，Ｇ２，ＧＴが群、ｇ１が群Ｇ１の生成元、ｇ２が群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴ、秘密鍵が少なくともｘ，ｙの何れかを含み、公開鍵がＹ１＝ｇ１ｙ，Ｘ２＝ｇ２ｘ，Ｖ＝ｅ（Ｙ１，Ｘ２）を含む。【選択図】図１
2015231133.tif 000002
【特許請求の範囲】
【請求項１】
Ｇ１，Ｇ２，ＧＴが群、ｇ１が前記群Ｇ１の生成元、ｇ２が前記群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴ、秘密鍵が少なくともｘ，ｙの何れかを含み、公開鍵がＹ１＝ｇ１ｙ，Ｘ２＝ｇ２ｘ，Ｖ＝ｅ（Ｙ１，Ｘ２）を含み、
前記群Ｇ２の任意の元Ａ２に対応するタグＴ２＝Ａ２ｙを得、メッセージと前記タグＴ２とを含む情報の像ｃを得、前記群Ｇ２の元Ｚ２＝Ａ２Ｘ２−ｃを得る署名生成装置と、
ｅ（Ｙ１，Ｚ２）・Ｖｃ＝ｅ（ｇ１，Ｔ２）の関係を満たすことを必要条件とする検証条件を満たすかを判定する署名検証装置と、
を有する署名システム。
【請求項２】
Ｇ１，Ｇ２，ＧＴが群、ｇ１が前記群Ｇ１の生成元、ｇ２が前記群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴであり、ｘ，ｙが任意値であり、
前記群Ｇ１の元Ｙ１＝ｇ１ｙを得る第１群演算部と、
前記群Ｇ２の元Ｘ２＝ｇ２ｘを得る第２群演算部と、
前記群ＧＴの元Ｖ＝ｅ（Ｙ１，Ｘ２）を得る双線形写像演算部と、
を有し、秘密鍵がｘ，ｙの少なくとも一方を含み、公開鍵が少なくともＹ１，Ｘ２，Ｖを含む、鍵生成装置。
【請求項３】
請求項２の鍵生成装置であって、
前記群Ｇ２のＹ２＝ｇ２ｙを得る第３群演算部を有し、
前記秘密鍵がｘ，ｙを含み、前記公開鍵がさらにＹ２を含む、鍵生成装置。
【請求項４】
Ｇ１，Ｇ２，ＧＴが群、ｇ１が前記群Ｇ１の生成元、ｇ２が前記群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴ、秘密鍵が少なくともｘ，ｙの何れかを含み、公開鍵がＹ１＝ｇ１ｙ，Ｘ２＝ｇ２ｘ，Ｖ＝ｅ（Ｙ１，Ｘ２）含み、
前記群Ｇ２の任意の元Ａ２に対応するタグＴ２＝Ａ２ｙを得るタグ選択部と、
メッセージと前記タグＴ２とを含む情報の像ｃを得る写像部と、
前記群Ｇ２の元Ｚ２＝Ａ２Ｘ２−ｃを得る群演算部と、
を有する署名生成装置。
【請求項５】
請求項４の署名生成装置であって、
前記像ｃは、メッセージと前記タグＴ２とを含む情報に衝突困難性を持つ写像を作用させて得られる像である、署名生成装置。
【請求項６】
Ｇ１，Ｇ２，ＧＴが群、ｇ１が前記群Ｇ１の生成元、ｇ２が前記群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴ、秘密鍵が少なくともｘ，ｙの何れかを含み、公開鍵がＹ１＝ｇ１ｙ，Ｘ２＝ｇ２ｘ，Ｖ＝ｅ（Ｙ１，Ｘ２）を含み、
前記群Ｇ２の元であるタグＴ２、メッセージと前記タグＴ２とを含む情報に対応する情報、前記群Ｇ２の元Ｚ２を受け付ける入力部と、
前記メッセージと前記タグＴ２とを含む情報の像ｃに対してｅ（Ｙ１，Ｚ２）・Ｖｃ＝ｅ（ｇ１，Ｔ２）の関係を満たすことを必要条件とする検証条件を満たすかを判定する判定部と、
を有する署名検証装置。
【請求項７】
Ｇ１，Ｇ２，ＧＴが群、ｇ１が前記群Ｇ１の生成元、ｇ２が前記群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴ、秘密鍵が少なくともｘ，ｙの何れかを含み、公開鍵がＹ１＝ｇ１ｙ，Ｘ２＝ｇ２ｘ，Ｖ＝ｅ（Ｙ１，Ｘ２）を含み、
署名生成装置が、前記群Ｇ２の任意の元Ａ２に対応するタグＴ２＝Ａ２ｙを得、メッセージと前記タグＴ２とを含む情報の像ｃを得、前記群Ｇ２の元Ｚ２＝Ａ２Ｘ２−ｃを得、
署名検証装置が、ｅ（Ｙ１，Ｚ２）・Ｖｃ＝ｅ（ｇ１，Ｔ２）の関係を満たすことを必要条件とする検証条件を満たすかを判定する、署名方法。
【請求項８】
請求項２もしくは３の鍵生成装置、請求項４もしくは５の署名生成装置、または、請求項６の署名検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名技術に関し、特に、タグ付き使い捨て署名技術に関する。
【背景技術】
【０００２】
対称双線形性写像群（例えば、対称ペアリング群）で構成された群構造維持タグ付き使い捨て署名として、非特許文献１，２に開示された方式がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Masayuki Abe, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Tagged One-Time Signatures: Tight Security and Optimal Tag Size,” Public Key Cryptography 2013, 312-331.
【非特許文献２】Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions,” ASIACRYPT 2012: 4-24.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１，２に開示された方式では署名検証に必要な双線形写像の演算量が多く、計算コストが大きいという問題点がある。例えば、非特許文献１に開示された方式の署名検証式は７＋２ｋ個の双線形写像を含んでいる。
【０００５】
本発明はこのような点に鑑みてなされたものであり、従来よりも署名検証時の計算コストを削減可能なタグ付き使い捨て署名技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
Ｇ１，Ｇ２，ＧＴが群、ｇ１が群Ｇ１の生成元、ｇ２が群Ｇ２の生成元、ｅが双線形写像Ｇ１×Ｇ２→ＧＴ、秘密鍵が少なくともｘ，ｙの何れかを含み、公開鍵がＹ１＝ｇ１ｙ，Ｘ２＝ｇ２ｘ，Ｖ＝ｅ（Ｙ１，Ｘ２）を含む。署名生成時には、群Ｇ２の任意の元Ａ２に対応するタグＴ２＝Ａ２ｙを得、メッセージとタグＴ２とを含む情報の像ｃを得、群Ｇ２の元Ｚ２＝Ａ２Ｘ２−ｃを得る。署名検証時には、ｅ（Ｙ１，Ｚ２）・Ｖｃ＝ｅ（ｇ１，Ｔ２）の関係を満たすことを必要条件とする検証条件を満たすかを判定する。
【発明の効果】
【０００７】
本発明では、従来よりも署名検証に必要な双線形写像の演算量が少なく、署名検証時の計算コストを削減できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の署名システムの機能構成を例示するためのブロック図である。
【図２】図２は実施形態の鍵生成装置の機能構成を例示するためのブロック図である。
【図３】図３は実施形態の署名生成装置の機能構成を例示するためのブロック図である。
【図４】図４は実施形態の署名検証装置の機能構成を例示するためのブロック図である。
【図５】図５は実施形態の鍵生成処理を例示するためのフロー図である。
【図６】図６Ａは実施形態の署名生成処理を例示するためのフロー図である。図６Ｂは実施形態の署名検証処理を例示するためのフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［定義］
実施形態で使用する用語を定義する。
Ｇ１，Ｇ２，ＧＴは素数位数ｑの群を表す。例えば、群Ｇ１，Ｇ２，ＧＴは可換群であり、例えば巡回群である。群Ｇ１と群Ｇ２とは、互いに同一であってもよいし（Ｇ１＝Ｇ２）、互いに異なっていてもよい（Ｇ１≠Ｇ２）。ｇ１は群Ｇ１の任意の生成元、ｇ２は群Ｇ２の任意の生成元、ｇＴは群ＧＴの任意の生成元である。ｅは群Ｇ１の元と群Ｇ２の元とを入力として群ＧＴを出力する双線形写像Ｇ１×Ｇ２→ＧＴを意味する。双線形写像ｅは、Ｇ１×Ｇ２→ＧＴを効率的に計算可能であり（計算可能性）、任意のａ，ｂ∈Ｚｑに対してｅ（ｇ１ａ，ｇ２ｂ）＝ｅ（ｇ１，ｇ２）ａｂを満たし（双線形性）、ｅ（ｇ１，ｇ２）≠１を満たす（非退化性）写像である。双線形写像ｅの例はペアリングである。例えば、ｅ（ｇ１，ｇ２）＝ｇＴを満たす。Ｇ１＝Ｇ２である双線形写像ｅを対称双線形写像（例えば、対称ペアリング）と呼び、Ｇ１≠Ｇ２である双線形写像ｅを非対称双線形写像（例えば、非対称ペアリング）と呼ぶ。対称双線形写像が存在する群Ｇ１，Ｇ２，ＧＴを対称双線形性写像群（例えば、対称ペアリング群）と呼び、非対称双線形写像が存在する群Ｇ１，Ｇ２，ＧＴを非対称双線形性写像群（例えば、非対称ペアリング群）と呼ぶ。Ｚｐは正整数ｐによる剰余群を表す。Ｚｐの例は集合｛０，…，ｐ−１｝である。ｐは例えば素数である。α∈βはαがβの元であることを表す。
【００１０】
タグ付き使い捨て署名（TOS: Tagged One-Time Signature）とは、署名生成のたびにメッセージに対して固有のタグが付される署名であり、(メッセージ，タグ，署名)の組み合わせがいくら得られたとしても、そのタグに対して検証式を満たすような別のメッセージに対する署名を偽造することが困難である署名を意味する。
【００１１】
［第１実施形態］
図面を参照しつつ、本発明の第１実施形態を説明する。本形態ではＧ１＝Ｇ２であってもよいし、Ｇ１≠Ｇ２であってもよい。Ｇ１＝Ｇ２の場合にはｇ１＝ｇ２とする。
＜構成＞
図１に例示するように、本形態の署名システム１は、鍵生成装置１１、署名生成装置１２、および署名検証装置１３を有しており、これらはインターネット等のネットワークを通じて通信可能に構成されている。図２に例示するように、本形態の鍵生成装置１１は、選択部１１１、群演算部１１２，１１３、双線形写像演算部１１４、鍵構成部１１５、および出力部１１６を有する。図３に例示するように、本形態の署名生成装置１２は、入力部１２１、分解部１２２、記憶部１２３、選択部１２４、タグ選択部１２５、写像演算部１２６、群演算部１２７、および出力部１２８を有する。図４に例示するように、本形態の署名検証装置１３は、入力部１３１、分解部１３２、記憶部１３３、判定部１３４、および出力部１３５を有する。鍵生成装置１１、署名生成装置１２、および署名検証装置１３は、それぞれ、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、単独で処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。
【００１２】
＜前提＞
前提として、群生成器Ｇｅｎ（１λ）（λは１以上の整数からなるセキュリティパラメータ）によってグローバルパラメータｇｋが生成されているとする。グローバルパラメータｇｋは、パラメータΛ＝（ｐ，Ｇ１，Ｇ２，ＧＴ，ｇ１，ｇ２，ｇＴ，ｅ）を含む。ただし、Ｇ１＝Ｇ２である場合には、ｇ１＝ｇ２としてパラメータΛ＝（ｐ，Ｇ１，ＧＴ，ｇ１，ｇＴ，ｅ）としてもよい。グローバルパラメータｇｋは、鍵生成装置１１、署名生成装置１２、および署名検証装置１３に設定され、それぞれが利用可能な状態であるとする。
【００１３】
＜鍵生成処理：図５＞
鍵生成装置１１（図２）は、グローバルパラメータｇｋに対してアルゴリズムＴＯＳ．Ｋｅｙ（ｇｋ）を実行し、公開鍵ｐｋと秘密鍵ｓｋとの鍵ペアを生成して出力する。この処理を詳細に説明する。
【００１４】
まず、選択部１１１はＺｐの任意の元ｘ，ｙ∈Ｚｐを選択して出力する。元ｘ，ｙは例えば一様ランダムに選択される。元ｘ，ｙは鍵生成のたびに生成されてもよいし、予め生成しておいた複数の元から選択されてもよい（ステップＳ１１１）。
【００１５】
群演算部１１２は、選択部１１１から出力された元ｙを入力とし、群Ｇ１の元Ｙ１＝ｇ１ｙ∈Ｇ１を得て出力する（ステップＳ１１２）。なお、「αを得る」とは、「αを計算してその結果を得る」ことであってもよいし、「予め計算しておいた値からαを選択してその値を得る」ことであってもよい。群演算部１１３は、選択部１１１から出力された元ｘを入力とし、群Ｇ２の元Ｘ２＝ｇ２ｘ∈Ｇ２を得て出力する（ステップＳ１１３）。
【００１６】
双線形写像演算部１１４は、群演算部１１２，１１３から出力されたＹ１，Ｘ２を入力とし、それらの双線形写像Ｖ＝ｅ（Ｙ１，Ｘ２）∈ＧＴを得て出力する（ステップＳ１１４）。
【００１７】
鍵構成部１１５は、選択部１１１から出力されたｘ，ｙ、群演算部１１２，１１３から出力されたＹ１，Ｘ２、および双線形写像演算部１１４から出力されたＶを入力とし、公開鍵ｐｋ＝（Ｙ１，Ｘ２，Ｖ）および秘密鍵ｓｋ＝（ｘ，ｙ）を得て出力する。公開鍵ｐｋおよび秘密鍵ｓｋは出力部１１７に送られる（ステップＳ１１５）。
【００１８】
出力部１１６は公開鍵ｐｋおよび秘密鍵ｓｋを出力する。公開鍵ｐｋは署名生成装置１２および署名検証装置１３に送られ、それぞれ入力部１２１，１３１に入力されて記憶部１２３，１３３に格納される。秘密鍵ｓｋは署名生成装置１２に安全に送られ、入力部１２１に入力されて記憶部１２３に安全に格納される（ステップＳ１１６）。
【００１９】
＜署名生成処理（６Ａ）＞
署名生成装置１２（図３）は、グローバルパラメータｇｋおよび秘密鍵ｓｋに対してアルゴリズムＴＯＳ．Ｔａｇ（ｇｋ，ｓｋ）を実行してタグｔａｇを得、秘密鍵ｓｋ，メッセージｍｓｇ，タグｔａｇに対してアルゴリズムＴＯＳ．Ｓｉｇｎ（ｓｋ，ｍｓｇ，ｔａｇ）を実行して署名σを得て出力する。この処理を詳細に説明する。
【００２０】
まず、メッセージｍｓｇが入力部１２１に入力され、記憶部１２３に格納される。メッセージｍｓｇは、さらに分解部１２２に送られる（ステップＳ１２１）。分解部１２２は、メッセージｍｓｇをパース（parse）し、メッセージｍｓｇに対応するｋ個（ただし、ｋは１以上の整数）のパースされたメッセージｍ１，…，ｍｋ∈Ｚｐｋを得て出力する。パースされたメッセージｍ１，…，ｍｋは記憶部１２３に格納される（ステップＳ１２２）。
【００２１】
選択部１２４は群Ｇ２の任意の元Ａ２∈Ｇ２を選択して出力する。元Ａ２は例えばランダムに選択される。元Ａ２は署名生成のたびに生成されてもよいし、予め生成しておいた複数の元から選択されてもよい（ステップＳ１２４）。
【００２２】
タグ選択部１２５は、記憶部１２３から読み出した公開鍵ｐｋからｙを抽出（パース）する。さらにタグ選択部１２５は、選択部１２４が出力したＡ２を入力とし、元Ａ２に対応するタグｔａｇ＝Ｔ２＝Ａ２ｙ∈Ｇ２を得て出力する（ステップＳ１２５）。
【００２３】
写像演算部１２６は、記憶部１２３からパースされたメッセージｍ１，…，ｍｋを読み出す。さらに写像演算部１２６は、タグ選択部１２５から出力されたタグｔａｇ＝Ｔ２を入力とし、パースされたメッセージｍ１，…，ｍｋとタグｔａｇ＝Ｔ２とを含む情報Ｍの像ｃ∈Ｚｐを得て出力する。情報Ｍはメッセージｍ１，…，ｍｋとタグｔａｇ＝Ｔ２のみを含むものであってもよいし、さらに公開情報（例えば、グローバルパラメータｇｋや公開鍵ｐｋ）を含むものであってもよい。像ｃの例は情報Ｍに衝突困難性（collision resistance）を持つ写像を作用させて得られる像である。衝突困難性を持つ写像の例は衝突困難ハッシュ関数（例えば、ＳＨＡ−２）や共通鍵暗号化関数（例えば、ＡＥＳやCamellia（登録商標））などである。情報Ｍに所定の変換関数を作用させて得られた結果に対し、衝突困難性を持つ写像を作用させて像ｃを得てもよい（ステップＳ１２６）。
【００２４】
群演算部１２７は、記憶部１２３から読み出した公開鍵ｐｋからＸ２を抽出（パース）する。群演算部１２７にはさらに、選択部１２４から出力されたＡ２、および写像演算部１２６から出力された像ｃが入力される。群演算部１２７は、これらを用いて群Ｇ２の元Ｚ２＝Ａ２Ｘ２−ｃ∈Ｇ２を得、署名σ＝（ｃ，Ｚ２）を出力する（ステップＳ１２７）。
【００２５】
出力部１２８には、記憶部１２３から読み出されたメッセージｍｓｇ、タグ選択部１２５から出力されたタグｔａｇ、および群演算部１２７から出力された署名σが入力される。出力部１２８は、メッセージｍｓｇ、タグｔａｇ、および署名σを出力する（ステップＳ１２８）。
【００２６】
＜署名検証処理（６Ｂ）＞
署名検証装置１３（図４）は、公開鍵ｐｋ、メッセージｍｓｇ、タグｔａｇ、および署名σに対してアルゴリズムＴＯＳ．Ｖｒｆ（ｐｋ，ｍｓｇ，ｔａｇ，σ）を実行して検証結果を出力する。この処理を詳細に説明する。
【００２７】
まず、メッセージｍｓｇ、タグｔａｇ、および署名σが入力部１３１に入力され、記憶部１３３に格納される。これらは上述のように正しく得られたものであるとは限らない。メッセージｍｓｇは、さらに分解部１３２に送られる（ステップＳ１３１）。分解部１３２は、メッセージｍｓｇをパースし、メッセージｍｓｇに対応するｋ個のパースされたメッセージｍ１，…，ｍｋ∈Ｚｐｋを得て出力する。パースされたメッセージｍ１，…，ｍｋは記憶部１３３に格納される（ステップＳ１３２）。
【００２８】
判定部１３４は、記憶部１３３から公開鍵ｐｋ＝（Ｙ１，Ｘ２，Ｖ）、署名σ＝（ｃ，Ｚ２）、タグｔａｇ＝Ｔ２、およびメッセージｍ１，…，ｍｋを読み出し、メッセージｍ１，…，ｍｋとタグｔａｇ＝Ｔ２とを含む情報Ｍの像ｃ＝Ｈ（Ｍ）に対して
ｅ（Ｙ１，Ｚ２）・Ｖｃ＝ｅ（ｇ１，Ｔ２）    …（１）
の関係を満たすことを必要条件とする検証条件を満たすかを判定する。ただし、情報Ｍおよび像ｃの生成方法はステップＳ１２６のものと同じである。例えば、判定部１３４は、メッセージｍ１，…，ｍｋとタグｔａｇ＝Ｔ２とを含む情報Ｍの像Ｈ（Ｍ）を得て、これが署名σに含まれたｃと一致するか（ｃ＝Ｈ（Ｍ）であるか）を判定し、ｃ＝Ｈ（Ｍ）であれば式（１）の関係を満たすかを判定する。式（１）の関係を満たすか否かの判定方法には限定はなく、どのような方法が用いられてもよい。例えば、式（１）の左辺と右辺とを計算してそれらが等しいか否かを判定してもよいし、式（１）の左辺の関数値と右辺の関数値とを比較してこの判定を行ってもよい。あるいは式（１）に代えてｅ（Ｙ１，Ｚ２）・Ｖｃ・ｅ（ｇ１，Ｔ２）−１＝１の関係を満たすか否かによって式（１）の関係を満たすか否かを判定してもよい。あるいは、さらに他の条件（例えば、他の検証式）を満たすことを検証条件に加えてもよい（ステップＳ１３４）。
【００２９】
検証条件を満たさないと判定された場合（例えば、ｃ≠Ｈ（Ｍ）であるか、式（１）の関係を満たさない）、判定部１３４は検証失敗を表す０を出力し、出力部１３５はこの０を出力する（ステップＳ１３５０）。一方、検証条件を満たすと判定された場合（例えば、ｃ＝Ｈ（Ｍ）であり、かつ、式（１）の関係を満たす）、判定部１３４は検証成功を表す１を出力し、出力部１３５はこの１を出力する（ステップＳ１３５１）。
【００３０】
＜正しく生成された署名が検証合格になる理由＞
群Ｇ２の元Ａ２は、群Ｇ２の生成元ｇ２を用いてＡ２＝ｇ２ａ（ただし、ａ∈Ｚｐ）と表現できる。署名σが正しく生成されている場合、式（１）の左辺は以下のように変形できる。
ｅ（Ｙ１，Ｚ２）・Ｖｃ
＝ｅ（ｇ１ｙ，ｇ２ａｇ２−ｃｘ）・ｅ（ｇ１ｙ，ｇ２ｘ）ｃ
＝ｅ（ｇ１，ｇ２）−ｃｘｙ＋ａｙ・ｅ（ｇ１，ｇ２）ｃｘｙ
＝ｅ（ｇ１，ｇ２）ａｙ    …（２）
式（１）の右辺は以下のように変形できる。
ｅ（ｇ１，Ｔ２）
＝ｅ（ｇ１，Ａ２ｙ）
＝ｅ（ｇ１，ｇ２ａｙ）
＝ｅ（ｇ１，ｇ２）ａｙ    …（３）
式（２）（３）より、署名σが正しく生成されていた場合には式（１）の関係を満たすことが分かる。このことはＧ１＝Ｇ２であってもＧ１≠Ｇ２であっても成り立つ。
【００３１】
＜本形態の特徴＞
本形態のタグ付き使い捨て署名では、２個の双線形写像を計算するだけで署名検証を行うことができるため（式（１））、従来よりも演算コストを削減できる。これにより、計算機の負担を軽減してアプリケーションの処理速度を向上させることができる。
【００３２】
［第２実施形態］
本形態は非対称双線形性写像群（Ｇ１≠Ｇ２）での実装において安全性を向上させるものである。以下では第１実施形態との相違点を中心に説明し、これと共通する事項については同じ参照番号を引用して説明を簡略化する。
【００３３】
＜構成＞
図１に例示するように、本形態の署名システム２は、鍵生成装置２１、署名生成装置１２、および署名検証装置１３を有しており、これらはインターネット等のネットワークを通じて通信可能に構成されている。図２に例示するように、本形態の鍵生成装置２１は、選択部１１１、群演算部１１２，１１３，２１２、双線形写像演算部１１４、鍵構成部２１５、および出力部１１６を有する。その他はＧ１≠Ｇ２であること以外、第１実施形態と同じである。
【００３４】
＜前提＞
鍵生成装置１１が鍵生成装置２１に置換され、Ｇ１≠Ｇ２であること以外は、第１実施形態の＜前提＞と同じである。
【００３５】
＜鍵生成処理：図５＞
鍵生成装置１１（図２）は、グローバルパラメータｇｋに対してアルゴリズムＴＯＳ．Ｋｅｙ（ｇｋ）を実行し、公開鍵ｐｋと秘密鍵ｓｋとの鍵ペアを生成して出力する。この処理を詳細に説明する。
【００３６】
まず、前述したステップＳ１１１〜Ｓ１１３の処理が実行される。次に、群演算部２１２は、選択部１１１から出力された元ｙを入力とし、群Ｇ２の元Ｙ２＝ｇ２ｙ∈Ｇ２を得て出力する（ステップＳ２１２）。その後、前述したステップＳ１１４の処理が実行された後、鍵構成部２１５は、選択部１１１から出力されたｘ，ｙ、群演算部１１２，１１３，２１２から出力されたＹ１，Ｘ２，Ｙ２、および双線形写像演算部１１４から出力されたＶを入力とし、公開鍵ｐｋ＝（Ｙ１，Ｘ２，Ｙ２，Ｖ）および秘密鍵ｓｋ＝（ｘ，ｙ）を得て出力する。公開鍵ｐｋおよび秘密鍵ｓｋは出力部１１７に送られる（ステップＳ２１５）。その後の処理は第１実施形態と同じである。
【００３７】
＜署名生成処理（６Ａ）・署名検証処理（６Ｂ）＞
Ｇ１≠Ｇ２であること以外は、第１実施形態の署名生成処理および署名検証処理と同じである。
【００３８】
＜本形態の特徴＞
本形態のタグ付き使い捨て署名でも、２個の双線形写像を計算するだけで署名検証を行うことができるため、従来よりも演算コストを削減できる。さらに、安全性証明のためのシミュレーションを行う場合、秘密鍵ｙに対応する群Ｇ１の公開鍵Ｙ１＝ｇ１ｙ∈Ｇ１だけではなく、群Ｇ２の公開鍵Ｙ２＝ｇ２ｙ∈Ｇ２も必要となる。本形態ではＧ１≠Ｇ２であるが、公開鍵として署名検証に用いる公開鍵Ｙ１に加えて公開鍵Ｙ２をも生成することとした。これにより、非対称双線形性写像群（Ｇ１≠Ｇ２）での実装に対しも安全性証明を行うことができ、安全性を担保できる。
【００３９】
［その他の変形例等］
本発明は上述の実施の形態に限定されるものではない。例えば、上述の方法において、パースされたメッセージｍ１，…，ｍｋに代えて、メッセージｍｓｇやメッセージｍｓｇに対応するその他の情報を用いてもよい。上述の実施形態では、署名σ＝（ｃ，Ｚ２）としたが、署名σがｃを含まなくてもよい。この場合には署名検証装置がメッセージｍ１，…，ｍｋとタグｔａｇ＝Ｔ２とを含む情報Ｍの像ｃ＝Ｈ（Ｍ）を得て、式（１）の関係を満たすか否かを判定する。また、ｘ，ｙの何れか一方が定数（例えば、１∈Ｚｐ）であり、秘密鍵が定数ではないｘ，ｙの何れか一方であってもよい。また、公開鍵がその他の公開パラメータを含んでもよい。また、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。例えば、署名生成装置がさらに鍵生成装置として機能してもよい。
【００４０】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４１】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４２】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００４４】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００４５】
１，２  署名システム
１１，２１  鍵生成装置
１２  署名生成装置
１３  署名検証装置
【図１】
2015231133.tif 000003
【図２】
2015231133.tif 000004
【図３】
2015231133.tif 000005
【図４】
2015231133.tif 000006
【図５】
2015231133.tif 000007
【図６】
2015231133.tif 000008