(57)【要約】      （修正有）【課題】非対称双線形性写像群で群構造維持タグ付き使い捨て署名を構成する。【解決手段】Ｇ，Ｇ〜，ＧＴが群、群Ｇと群Ｇ〜とが互いに異なり、ｅが双線形写像Ｇ×Ｇ〜→ＧＴ、ｇ〜が群Ｇ〜の生成元、ｋが１以上の整数、ｉ＝１，…，ｋとする。鍵生成装置１１は、任意のωｚ，ωｒ，μｚ，μｓ，τについて群Ｇの元Ｇｚ＝ｇωｚ，Ｇｒ＝ｇωｒ，Ｈｚ＝ｇμｚ，Ｈｓ＝ｇμｓ，Ｇτ＝ｇτを得、ωｚ，μｚについて群Ｇ〜の元Ｇｚ〜＝ｇ〜ωｚ，Ｈｚ〜＝ｇ〜μｚを得、任意のχ（ｉ），γ（ｉ），δ（ｉ）について群Ｇの元Ｇ（ｉ）＝Ｇｚχ（ｉ）Ｇｒγ（ｉ），Ｈ（ｉ）＝Ｈｚχ（ｉ）Ｈｓδ（ｉ）を得、ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）の少なくとも一部を秘密鍵ｓｋとし、Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇｚ〜，Ｈｚ〜，Ｇ（ｉ），Ｈ（ｉ）の少なくとも一部を公開鍵ｐｋとして出力する。【選択図】図２
2015231132.tif 000002
【特許請求の範囲】
【請求項１】
Ｇ，Ｇ〜，ＧＴが群、ｅが双線形写像Ｇ×Ｇ〜→ＧＴ、ｇ〜が前記群Ｇ〜の生成元、ｋが１以上の整数、ｉ＝１，…，ｋであり、
任意のωｚ，ωｒ，μｚ，μｓ，τについて前記群Ｇの元Ｇｚ＝ｇωｚ，Ｇｒ＝ｇωｒ，Ｈｚ＝ｇμｚ，Ｈｓ＝ｇμｓ，Ｇτ＝ｇτを得、前記ωｚ，μｚについて前記群Ｇ〜の元Ｇｚ〜＝ｇ〜ωｚ，Ｈｚ〜＝ｇ〜μｚを得、任意のχ（ｉ），γ（ｉ），δ（ｉ）について前記群Ｇの元Ｇ（ｉ）＝Ｇｚχ（ｉ）Ｇｒγ（ｉ），Ｈ（ｉ）＝Ｈｚχ（ｉ）Ｈｓδ（ｉ）を得、前記ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）の少なくとも一部を秘密鍵とし、少なくとも、前記Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇｚ〜，Ｈｚ〜，Ｇ（ｉ），Ｈ（ｉ）を公開鍵とする鍵生成装置と、
Ｍ〜（１），…，Ｍ〜（ｋ）をメッセージに対応する前記群Ｇ〜の元、ζを任意値、Ｔ〜を前記群Ｇ〜から選択されたタグとし、前記群Ｇ〜の元
【数１６】
2015231132.tif 000018
を含む署名を得る署名生成装置と、
【数１７】
2015231132.tif 000019
の関係を満たすことを必要条件とする検証条件を満たすかを判定する署名検証装置と、
を有する署名システム。
【請求項２】
Ｇ，Ｇ〜が群、ｉ＝１，…，ｋ、ｋが１以上の整数であり、
任意のωｚ，ωｒ，μｚ，μｓ，τについて前記群Ｇの元Ｇｚ＝ｇωｚ，Ｇｒ＝ｇωｒ，Ｈｚ＝ｇμｚ，Ｈｓ＝ｇμｓ，Ｇτ＝ｇτを得る第１群演算部と、
前記ωｚ，μｚについて前記群Ｇ〜の元Ｇｚ〜＝ｇ〜ωｚ，Ｈｚ〜＝ｇ〜μｚを得る第２群演算部と、
任意のχ（ｉ），γ（ｉ），δ（ｉ）について前記群Ｇの元Ｇ（ｉ）＝Ｇｚχ（ｉ）Ｇｒγ（ｉ），Ｈ（ｉ）＝Ｈｚχ（ｉ）Ｈｓδ（ｉ）を得る第３群演算部と、を有し、
前記ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）の少なくとも一部を秘密鍵とし、少なくとも、前記Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇｚ〜，Ｈｚ〜，Ｇ（ｉ），Ｈ（ｉ）を公開鍵とする、鍵生成装置。
【請求項３】
請求項２の鍵生成装置であって、
前記群Ｇと前記群Ｇ〜とが互いに異なる、鍵生成装置。
【請求項４】
Ｇ，Ｇ〜が群、ｇが前記群Ｇ〜の生成元、ｇ〜が前記群Ｇ〜の生成元、ＧｚおよびＨｚが前記群Ｇの元、Ｇｚ〜およびＨｚ〜が前記群Ｇ〜の元、ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）の少なくとも一部が秘密鍵、少なくとも、Ｇｒ＝ｇωｒ，Ｈｓ＝ｇμｓ，Ｇτ＝ｇτ，Ｇ（ｉ）＝Ｇｚχ（ｉ）Ｇｒγ（ｉ），Ｈ（ｉ）＝Ｈｚχ（ｉ）Ｈｓδ（ｉ）が公開鍵、ｋが１以上の整数、ｉ＝１，…，ｋであり、Ｍ〜（１），…，Ｍ〜（ｋ）がメッセージに対応する前記群Ｇ〜の元、ζが任意値、Ｔ〜が前記群Ｇ〜から選択されたタグであり、
【数１８】
2015231132.tif 000020
を得る第１群演算部と、
【数１９】
2015231132.tif 000021
を得る第２群演算部と、
【数２０】
2015231132.tif 000022
を得る第３群演算部と、
を有する署名生成装置。
【請求項５】
請求項４の署名生成装置であって、
前記群Ｇと前記群Ｇ〜とが互いに異なる、署名生成装置。
【請求項６】
Ｇ，Ｇ〜，ＧＴが群、ｅが双線形写像Ｇ×Ｇ〜→ＧＴ、ｋが１以上の整数、Ｇτ，Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇ（１），…，Ｇ（ｋ），Ｈ（１），…，Ｈ（ｋ）が前記群Ｇの元であり、少なくとも、前記Ｇτ，Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇ（１），…，Ｇ（ｋ），Ｈ（１），…，Ｈ（ｋ）が公開鍵であり、
前記群Ｇ〜の元Ｚ〜，Ｒ〜，Ｓ〜を含む署名、前記群Ｇ〜の元であるタグＴ〜、およびメッセージを受け付ける入力部と、
前記メッセージに対応する前記群Ｇ〜の元Ｍ〜（１），…，Ｍ〜（ｋ）に対して
【数２１】
2015231132.tif 000023
を満たすことを必要条件とする検証条件を満たすかを判定する判定部と、
を有する署名検証装置。
【請求項７】
請求項６の署名検証装置であって、
前記群Ｇと前記群Ｇ〜とが互いに異なる、署名検証装置。
【請求項８】
請求項２もしくは３の鍵生成装置、請求項４もしくは５の署名生成装置、または、請求項６もしくは７の署名検証装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名技術に関し、特に、群構造維持タグ付き使い捨て署名技術に関する。
【背景技術】
【０００２】
対称双線形性写像群（例えば、対称ペアリング群）で構成された群構造維持タグ付き使い捨て署名として、非特許文献１，２に開示された方式がある。群構造維持な構成は、非対話証明（GS: Groth-Sahai）が可能であることが知られており、利便性が高い。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非対称双線形性写像群（例えば、非対称ペアリング群）で構成可能な群構造維持タグ付き使い捨て署名は知られていない。本発明はこのような点に鑑みてなされたものであり、非対称双線形性写像群でも構成可能な群構造維持タグ付き使い捨て署名を提供することを目的とする。
【課題を解決するための手段】
【０００５】
Ｇ，Ｇ〜，ＧＴが群、ｅが双線形写像Ｇ×Ｇ〜→ＧＴ、ｇ〜が群Ｇ〜の生成元、ｋが１以上の整数、ｉ＝１，…，ｋとする。任意のωｚ，ωｒ，μｚ，μｓ，τについて群Ｇの元Ｇｚ＝ｇωｚ，Ｇｒ＝ｇωｒ，Ｈｚ＝ｇμｚ，Ｈｓ＝ｇμｓ，Ｇτ＝ｇτを得、ωｚ，μｚについて群Ｇ〜の元Ｇｚ〜＝ｇ〜ωｚ，Ｈｚ〜＝ｇ〜μｚを得、任意のχ（ｉ），γ（ｉ），δ（ｉ）について群Ｇの元Ｇ（ｉ）＝Ｇｚχ（ｉ）Ｇｒγ（ｉ），Ｈ（ｉ）＝Ｈｚχ（ｉ）Ｈｓδ（ｉ）を得、ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）の少なくとも一部を秘密鍵とし、少なくとも、Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇｚ〜，Ｈｚ〜，Ｇ（ｉ），Ｈ（ｉ）を公開鍵とする。
【０００６】
署名生成時には、Ｍ〜（１），…，Ｍ〜（ｋ）をメッセージに対応する群Ｇ〜の元、ζを任意値、Ｔ〜を群Ｇ〜から選択されたタグとし、群Ｇ〜の元
【数１】
2015231132.tif 000003
を含む署名を得る。
【０００７】
署名検証時には、
【数２】
2015231132.tif 000004
の関係を満たすことを必要条件とする検証条件を満たすかを判定する。
【発明の効果】
【０００８】
本発明では、非対称双線形性写像群でも群構造維持タグ付き使い捨て署名を構成できる。
【図面の簡単な説明】
【０００９】
【図１】図１は実施形態の署名システムの機能構成を例示するためのブロック図である。
【図２】図２は実施形態の鍵生成装置の機能構成を例示するためのブロック図である。
【図３】図３は実施形態の署名生成装置の機能構成を例示するためのブロック図である。
【図４】図４は実施形態の署名検証装置の機能構成を例示するためのブロック図である。
【図５】図５は実施形態の鍵生成処理を例示するためのフロー図である。
【図６】図６は実施形態の署名生成処理を例示するためのフロー図である。
【図７】図７は実施形態の署名検証処理を例示するためのフロー図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施形態を説明する。
［定義］
実施形態で使用する用語を定義する。
Ｇ，Ｇ〜，ＧＴは素数位数ｑの群を表す。例えば、群Ｇ，Ｇ〜，ＧＴは可換群であり、例えば巡回群である。群Ｇと群Ｇ〜とは、互いに同一であってもよいし（Ｇ＝Ｇ〜）、互いに異なっていてもよい（Ｇ≠Ｇ〜）。なお「Ｇ〜」の「〜」は本来「Ｇ」の真上に表記すべきであるが、記載表記の制約上「Ｇ」の右上に表記する場合がある。その他の文字に付された「〜」も同様である。ｇは群Ｇの任意の生成元、ｇ〜は群Ｇ〜の任意の生成元、ｇＴは群ＧＴの任意の生成元である。ｅは群Ｇの元と群Ｇ〜の元とを入力として群ＧＴを出力する双線形写像Ｇ×Ｇ〜→ＧＴを意味する。双線形写像ｅは、Ｇ×Ｇ〜→ＧＴを効率的に計算可能であり（計算可能性）、任意のａ，ｂ∈Ｚｑに対してｅ（ｇａ，ｇ〜ｂ）＝ｅ（ｇ，ｇ〜）ａｂを満たし（双線形性）、ｅ（ｇ，ｇ〜）≠１を満たす（非退化性）写像である。双線形写像ｅの例はペアリングである。例えば、ｅ（ｇ，ｇ〜）＝ｇＴである。Ｇ＝Ｇ〜である双線形写像ｅを対称双線形写像（例えば、対称ペアリング）と呼び、Ｇ≠Ｇ〜である双線形写像ｅを非対称双線形写像（例えば、非対称ペアリング）と呼ぶ。対称双線形写像が存在する群Ｇ，Ｇ〜，ＧＴを対称双線形性写像群（例えば、対称ペアリング群）と呼び、非対称双線形写像が存在する群Ｇ，Ｇ〜，ＧＴを非対称双線形性写像群（例えば、非対称ペアリング群）と呼ぶ。Ｚｐは正整数ｐによる剰余群を表し、Ｚｐ*は正整数ｐによる剰余類の乗法群を表す。Ｚｐの例は集合｛０，…，ｐ−１｝であり、Ｚｐ*の例は｛１，…，ｐ−１｝である。ｐは例えば素数である。α∈βはαがβの元であることを表す。
【００１１】
タグ付き使い捨て署名（TOS: Tagged One-Time Signature）とは、署名生成のたびにメッセージに対して固有のタグが付される署名であり、(メッセージ，タグ，署名)の組み合わせがいくら得られたとしても、そのタグに対して検証式を満たすような別のメッセージに対する署名を偽造することが困難である署名を意味する。
【００１２】
群構造維持署名とは、署名の対象となるメッセージ（あるいはメッセージに対応する情報）、署名、検証鍵の全てが群の要素で表現され、また、署名の検証式が双線形写像（例えば、ペアリング）からなる等式で表現されるものを意味する。群構造維持タグ付き使い捨て署名とは、群構造維持署名であるタグ付き使い捨て署名を意味する。
【００１３】
＜構成＞
図１に例示するように、本形態の署名システム１は、鍵生成装置１１、署名生成装置１２、および署名検証装置１３を有しており、これらはインターネット等のネットワークを通じて通信可能に構成されている。図２に例示するように、本形態の鍵生成装置１１は、選択部１１１，１１２、群演算部１１３，１１４，１１５、鍵構成部１１６、および出力部１１７を有する。図３に例示するように、本形態の署名生成装置１２は、入力部１２１、分解部１２２、記憶部１２３、タグ選択部１２４、選択部１２５、群演算部１２６，１２７，１２８、および出力部１２９を有する。図４に例示するように、本形態の署名検証装置１３は、入力部１３１、分解部１３２、記憶部１３３、判定部１３４、および出力部１３５を有する。判定部１３４は第１判定部１３４１および第２判定部１３４２を有する。鍵生成装置１１、署名生成装置１２、および署名検証装置１３は、それぞれ、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、単独で処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。
【００１４】
＜前提＞
前提として、群生成器Ｇｅｎ（１λ）（λは１以上の整数からなるセキュリティパラメータ）によってグローバルパラメータｇｋが生成されているとする。グローバルパラメータｇｋは、パラメータΛ＝（ｐ，Ｇ，Ｇ〜，ＧＴ，ｇ，ｇ〜，ｇＴ，ｅ）を含む。グローバルパラメータｇｋは、鍵生成装置１１、署名生成装置１２、および署名検証装置１３に設定され、それぞれが利用可能な状態であるとする。
【００１５】
＜鍵生成処理：図５＞
鍵生成装置１１（図２）は、グローバルパラメータｇｋに対してアルゴリズムＴＯＳ．Ｋｅｙ（ｇｋ）を実行し、公開鍵ｐｋと秘密鍵ｓｋとの鍵ペアを生成して出力する。選択部１１１は、Ｚｐ*の任意の元ωｚ，ωｒ，μｚ，μｓ，τ∈Ｚｐ*を選択して出力する。元ωｚ，ωｒ，μｚ，μｓ，τは例えばランダムに選択される。元ωｚ，ωｒ，μｚ，μｓ，τは鍵生成のたびに生成されてもよいし、予め生成しておいた複数の元から選択されてもよい（ステップＳ１１１）。
【００１６】
群演算部１１３は、選択部１１１から出力された元ωｚ，ωｒ，μｚ，μｓ，τを入力とし、群Ｇの元Ｇｚ＝ｇωｚ，Ｇｒ＝ｇωｒ，Ｈｚ＝ｇμｚ，Ｈｓ＝ｇμｓ，Ｇτ＝ｇτを得て（例えば、計算して）出力する。なお、ｇωｚ，ｇωｒ，ｇμｚ，ｇμｓの上付き添え字はそれぞれωｚ，ωｒ，μｚ，μｓを表す（ステップＳ１１３）。群演算部１１４は、元ωｚ，ωｒ，μｚ，μｓを入力とし、群Ｇ〜の元Ｇｚ〜＝ｇ〜ωｚ，Ｇｒ〜＝ｇ〜ωｒ，Ｈｚ〜＝ｇ〜μｚ，Ｈｓ〜＝ｇ〜μｓを得て（例えば、計算して）出力する（ステップＳ１１４）。
【００１７】
選択部１１２は、ｉ＝１，…，ｋ（ただし、ｋは１以上の整数）について、Ｚｐの任意のχ（ｉ），γ（ｉ），δ（ｉ）∈Ｚｐを選択して出力する。χ（ｉ），γ（ｉ），δ（ｉ）は例えば一様ランダムに選択される。χ（ｉ），γ（ｉ），δ（ｉ）は鍵生成のたびに生成されてもよいし、予め生成しておいた複数の元から選択されてもよい（ステップＳ１１５）。
【００１８】
群演算部１１５は、群演算部１１３から出力されたＧｚ，Ｇｒ，Ｈｚ，Ｈｓ∈Ｇ、および選択部１１２から出力されたχ（ｉ），γ（ｉ），δ（ｉ）∈Ｚｐを入力とし、ｉ＝１，…，ｋについて、群Ｇの元Ｇ（ｉ）＝Ｇｚχ（ｉ）Ｇｒγ（ｉ），Ｈ（ｉ）＝Ｈｚχ（ｉ）Ｈｓδ（ｉ）∈Ｇを得（例えば、計算し）て出力する（ステップＳ１１５）。
【００１９】
鍵構成部１１６は、群演算部１１３から出力されたＧｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ∈Ｇ、群演算部１１４から出力されたＧｚ〜，Ｇｒ〜，Ｈｚ〜，Ｈｓ〜∈Ｇ〜、選択部１１１から出力されたωｒ，μｓ，τ∈Ｚｐ*、および選択部１１２から出力されたχ（ｉ），γ（ｉ），δ（ｉ）∈Ｚｐを入力とし、以下のように公開鍵ｐｋ∈Ｇ２ｋ＋５×Ｇ〜４および秘密鍵ｓｋ∈Ｚｐ３ｋ＋３を生成して出力する。
ｐｋ＝（Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇ（１），…，Ｇ（ｋ），Ｈ（１），…，Ｈ（ｋ），Ｇｚ〜，Ｇｒ〜，Ｈｚ〜，Ｈｓ〜）      …（１）
ｓｋ＝（ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ））      …（２）
公開鍵ｐｋおよび秘密鍵ｓｋは出力部１１７に送られる（ステップＳ１１６）。
【００２０】
出力部１１７は公開鍵ｐｋおよび秘密鍵ｓｋを出力する。公開鍵ｐｋは署名生成装置１２および署名検証装置１３に送られ、それぞれ入力部１２１，１３１に入力されて記憶部１２３，１３３に格納される。秘密鍵ｓｋは署名生成装置１２に安全に送られ、入力部１２１に入力されて記憶部１２３に安全に格納される（ステップＳ１１７）。
【００２１】
＜署名生成処理：図６＞
署名生成装置１２（図３）は、グローバルパラメータｇｋに対してアルゴリズムＴＯＳ．Ｔａｇ（ｇｋ）を実行してタグｔａｇを得、秘密鍵ｓｋ，メッセージ，ｍｓｇ，タグｔａｇに対してアルゴリズムＴＯＳ．Ｓｉｇｎ（ｓｋ,ｍｓｇ,ｔａｇ）を実行して署名σを得る。まず、メッセージｍｓｇが入力部１２１に入力され、記憶部１２３に格納される。メッセージｍｓｇは、さらに分解部１２２に送られる（ステップＳ１２１）。分解部１２２は、メッセージｍｓｇをパース（parse）し、メッセージｍｓｇに対応するｋ個の群Ｇ〜の元Ｍ〜（１），…，Ｍ〜（ｋ）∈Ｇ〜を得て出力する。Ｍ〜（１），…，Ｍ〜（ｋ）は記憶部１２３に格納される（ステップＳ１２２）。
【００２２】
タグ選択部１２４は、群Ｇ〜の任意の元Ｔ〜∈Ｇ〜を選択してタグｔａｇ＝Ｔ〜を出力する。Ｔ〜は例えばランダムに選択される。Ｔ〜は署名生成のたびに生成されてもよいし、予め生成しておいた複数の元から選択されてもよい（ステップＳ１２４）。
【００２３】
選択部１２５は、Ｚｐの任意の元ζ∈Ｚｐ（任意値）を選択して出力する。ζは例えばランダム値である。ζは署名生成のたびに生成されてもよいし、予め生成しておいた複数の元から選択されてもよい。或いはζが定数であってもよい（ステップＳ１２５）。
【００２４】
群演算部１２６は、記憶部１２３からＭ〜（１），…，Ｍ〜（ｋ）を読み出し、さらに記憶部１２３に格納された秘密鍵ｓｋからχ（１），…，χ（ｋ）を抽出する。群演算部１２６には、さらに選択部１２５から出力されたζが入力される。群演算部１２６は、これらを用いて群Ｇ〜の元
【数３】
2015231132.tif 000005
を得て（例えば、計算して）出力する（ステップＳ１２６）。
【００２５】
群演算部１２７は、記憶部１２３からＭ〜（１），…，Ｍ〜（ｋ）を読み出し、さらに記憶部１２３に格納された秘密鍵ｓｋからωｒ，τ，γ（１），…，γ（ｋ）を抽出し、公開鍵ｐｋからＧｚ〜を抽出する。群演算部１２７には、さらに選択部１２５から出力されたζおよびタグ選択部１２４から出力されたタグｔａｇ＝Ｔ〜が入力される。群演算部１２７は、これらを用いて群Ｇ〜の元
【数４】
2015231132.tif 000006
を得て（例えば、計算して）出力する（ステップＳ１２７）。
【００２６】
群演算部１２８は、記憶部１２３からＭ〜（１），…，Ｍ〜（ｋ）を読み出し、さらに記憶部１２３に格納された秘密鍵ｓｋからμｓ，δ（１），…，δ（ｋ）を抽出し、公開鍵ｐｋからＨｚ〜を抽出する。群演算部１２８には、さらに選択部１２５から出力されたζが入力される。群演算部１２７は、これらを用いて群Ｇ〜の元
【数５】
2015231132.tif 000007
を得て（例えば、計算して）出力する（ステップＳ１２８）。
【００２７】
群演算部１２６，１２７，１２８から出力されたＺ〜，Ｒ〜，Ｓ〜、タグ選択部１２４から出力されたｔａｇ、および記憶部１２３から読み出したメッセージｍｓｇが出力部１２９に入力される。出力部１２９は、Ｚ〜，Ｒ〜，Ｓ〜を含む署名σ＝（Ｚ〜，Ｒ〜，Ｓ〜）、メッセージｍｓｇ、およびタグｔａｇを出力する（ステップＳ１２９）。
【００２８】
＜署名検証処理：図７＞
署名検証装置（図４）は、公開鍵ｐｋ，タグｔａｇ，メッセージｍｓｇ，署名σに対してアルゴリズムＴＯＳ．Ｖｒｆ（ｐｋ，ｔａｇ，ｍｓｇ，σ）を実行し、検証結果を得る。署名生成装置１２から出力されたタグｔａｇ，メッセージｍｓｇ，署名σは、入力部１３１に入力され（入力部１３１が入力を受け付け）、記憶部１３３に格納される。メッセージｍｓｇは、さらに分解部１２２に送られる（ステップＳ１３１）。分解部１３２は、ステップＳ１２２と同じ方法でメッセージｍｓｇをパースし、メッセージｍｓｇに対応するｋ個の群Ｇ〜の元Ｍ〜（１），…，Ｍ〜（ｋ）∈Ｇ〜を得て出力する。Ｍ〜（１），…，Ｍ〜（ｋ）は記憶部１３３に格納される（ステップＳ１３２）。
【００２９】
判定部１３４は、記憶部１３３から、σ＝（Ｚ〜，Ｒ〜，Ｓ〜）、ｔａｇ＝Ｔ〜、Ｍ〜（１），…，Ｍ〜（ｋ）、およびｐｋを読み出し、
【数６】
2015231132.tif 000008
を満たすことを必要条件とする検証条件を満たすかを判定する。
【００３０】
本形態では、まず第１判定部１３４１が、σから抽出したＺ〜，Ｒ〜、ｔａｇ＝Ｔ〜、Ｍ〜（１），…，Ｍ〜（ｋ）、およびｐｋから抽出したＧｚ，Ｇｒ，Ｇτ，Ｇ（１），…，Ｇ（ｋ）を用い、
【数７】
2015231132.tif 000009
の関係を満たすかを判定する。なお、この判定方法に限定はなく、式（７）を満たすか否かを判定できるのであればどのような判定方法が用いられてもよい。例えば、式（７）の左辺と右辺とを計算してそれらが等しいか否かを判定してもよいし、式（７）の右辺を変形した式と左辺とを計算してそれらが等しいか否かを判定してもよい。式（７）の右辺を変形した式の例は
【数８】
2015231132.tif 000010
などである。あるいは、
【数９】
2015231132.tif 000011
が１∈ＧＴとなるか否かを判定してもよい。その他、式（７）の左辺の関数値と右辺の関数値とを比較して式（７）を満たすか否かを判定してもよい（ステップＳ１３４１）。
【００３１】
式（７）の関係を満たさないと判定された場合、判定部１３４は検証失敗を表す０を出力し、出力部１３５はこの０を出力する（ステップＳ１３５０）。一方、式（７）の関係を満たすと判定された場合、次に第２判定部１３４２が、σから抽出したＺ〜，Ｓ〜、Ｍ〜（１），…，Ｍ〜（ｋ）、およびｐｋから抽出したＨｚ，Ｈｓ，Ｈ（１），…，Ｈ（ｋ）を用い、
【数１０】
2015231132.tif 000012
の関係を満たすかを判定する。なお、この判定方法に限定はなく、式（８）を満たすか否かを判定できるのであればどのような判定方法が用いられてもよい。例えば、式（８）の右辺を計算してそれが１∈ＧＴとなるか否かを判定してもよいし、式（８）の右辺を変形した式を計算してそれが１∈ＧＴとなるか否かを判定してもよい。式（８）の右辺を変形した式の例は
【数１１】
2015231132.tif 000013
などである。その他、式（８）の左辺の関数値と右辺の関数値とを比較して式（８）を満たすか否かを判定してもよい（ステップＳ１３４２）。
【００３２】
式（８）の関係を満たさないと判定された場合、判定部１３４は検証失敗を表す０を出力し、出力部１３５はこの０を出力する（ステップＳ１３５０）。一方、式（８）の関係を満たすと判定された場合、判定部１３４は検証成功を表す１を出力し、出力部１３５はこの１を出力する（ステップＳ１３５１）。
【００３３】
＜正しく生成された署名が検証合格になる理由＞
群Ｇの元Ｔ〜は、群Ｇの生成元ｇを用いてＴ〜＝ｇｔ（ただし、ｔ∈Ｚｐ）と表現できる。署名σが正しく生成されている場合、式（７）の左辺は以下のように変形できる。
【数１２】
2015231132.tif 000014
【００３４】
群Ｇ〜の元Ｍ〜（ｉ）は、群Ｇ〜の生成元ｇ〜を用いてＭ〜（ｉ）＝ｇ〜ｍ（ｉ）（ただし、ｍ（ｉ）∈Ｚｐ）と表現できる。署名σが正しく生成されている場合、式（７）の右辺は以下のように変形できる。
【数１３】
2015231132.tif 000015
【００３５】
式（９）（１０）より、署名σが正しく生成されていた場合には式（７）の関係を満たすことが分かる。このことはＧ＝Ｇ〜であってもＧ≠Ｇ〜であっても成り立つ。
【００３６】
同様に、署名σが正しく生成されている場合、式（８）の右辺は以下のように変形できる。
【数１４】
2015231132.tif 000016
従って、署名σが正しく生成されていた場合には式（８）の関係を満たす。このことはＧ＝Ｇ〜であってもＧ≠Ｇ〜であっても成り立つ。
【００３７】
＜本形態の特徴＞
本形態では、非対称双線形写像群でも群構造維持タグ付き使い捨て署名を構成できる。また、本形態の方式は対称双線形写像群での実装も可能である。このように、本形態により、群構造維持タグ付き使い捨て署名の用途を広げることができる。また、公開鍵ｐｋ＝（Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇ（１），…，Ｇ（ｋ），Ｈ（１），…，Ｈ（ｋ），Ｇｚ〜，Ｇｒ〜，Ｈｚ〜，Ｈｓ〜）の他に１個の検証鍵を準備するだけで安全性の証明が可能となっている。
【００３８】
＜その他の変形例等＞
本発明は上述の実施の形態に限定されるものではない。例えば、上述の実施形態ではＧｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇ（１），…，Ｇ（ｋ），Ｈ（１），…，Ｈ（ｋ），Ｇｚ〜，Ｇｒ〜，Ｈｚ〜，Ｈｓ〜を公開鍵としたが、Ｇｚ，Ｇｒ，Ｈｚ，Ｈｓ，Ｇτ，Ｇ（１），…，Ｇ（ｋ），Ｈ（１），…，Ｈ（ｋ），Ｇｚ〜，Ｈｚ〜を公開鍵としてもよい。この場合には、Ｇｒ〜，Ｈｓ〜が生成されなくてもよい。上述の実施形態ではωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）を秘密鍵としたが、ωｒ，μｓ，τ，χ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）の一部を定数（例えば、単位元１∈Ｚｐ）とし、これらの残りを秘密鍵としてもよい。例えば、ωｒ，μｓ，τの何れか一つを定数（例えば、単位元１∈Ｚｐ）とし、ωｒ，μｓ，τのうち定数としないものとχ（１），γ（１），δ（１），…，χ（ｋ），γ（ｋ），δ（ｋ）とを秘密鍵としてもよい。
【００３９】
上述の実施形態では、署名生成装置１２から署名検証装置１３に署名σおよびタグｔａｇとともにメッセージｍｓｇが送信された。しかしながら、メッセージｍｓｇに代えてＭ〜（１），…，Ｍ〜（ｋ）が送信されてもよい。この場合には署名検証装置１３に分解部１３２は不要となる。
【００４０】
式（６）の関係を満たすか否かを１個の検証式で判定してもよい。例えば、以下の関係を満たすか否かが判定されてもよい。
【数１５】
2015231132.tif 000017
あるいは、式（６）の関係を満たし、かつ他の条件（検証式等）を満たすことを検証条件としてもよい。
【００４１】
各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。あるいは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。例えば、署名生成装置１２がさらに鍵生成装置１１として機能してもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４３】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００４５】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００４６】
１  署名システム
１１  鍵生成装置
１２  署名生成装置
１３  署名検証装置
【図１】
2015231132.tif 000024
【図２】
2015231132.tif 000025
【図３】
2015231132.tif 000026
【図４】
2015231132.tif 000027
【図５】
2015231132.tif 000028
【図６】
2015231132.tif 000029
【図７】
2015231132.tif 000030