(57)【要約】【課題】一般アクセス構造を持つ署名権限を委譲することができる代理署名技術を提供する。【解決手段】各代理署名装置Ｕ（θ（ｊ））は、ｉ∈Ｉ（ｊ）について、入力された｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝のｓ*ｉ，ｊ−１と｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）とを用い、署名対象に対応するｓ*ｉ，ｊを得る。ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について、｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝のｓ*ｉ，ｊ−１を用い、署名対象に対応するｓ*ｉ，ｊを得る。ｓ*ｉ，ｊの集合を｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とする。代理署名装置Ｕ（θ（ｋ））で得られた｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝を署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝とする。【選択図】図４
2015136049.tif 000002
【特許請求の範囲】
【請求項１】
Ｌが１以上の整数であり、ｋが１以上の整数であり、ｊ∈｛１，…，ｋ｝であり、Ｉ（ｊ）が｛１，…，Ｌ｝の部分集合であり、｛ｓｉ｝ｉ∈｛１，…，Ｌ｝が任意値ｓｉの集合であり、前記部分集合Ｉ（ｊ）の和集合∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ）に対応する前記任意値ｓｉの線形結合が値ｓ０であり、鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）が前記任意値ｓｉに対応する鍵ｋ*ｉの集合であり、｛ｓ*ｉ，０｝ｉ∈｛１，…，Ｌ｝が初期設定されており、
ｉ∈Ｉ（ｊ）について、入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１と前記鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）とを用い、署名対象に対応する要素ｓ*ｉ，ｊを得る第１処理部と、
ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について、前記代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１を用い、前記署名対象に対応する要素ｓ*ｉ，ｊを得る第２処理部と、を有し、
前記要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とする、代理署名装置。
【請求項２】
Ｌが１以上の整数であり、ｋが１以上の整数であり、ｊ∈｛１，…，ｋ｝であり、Ｉ（ｊ）が｛１，…，Ｌ｝の部分集合Ｉ（ｊ）であり、｛ｓｉ｝ｉ∈｛１，…，Ｌ｝が任意値ｓｉの集合であり、｛αｉ｝ｉ∈Ｉ（ｊ）が係数αｉの集合であり、ｓ０が
【数３０】
2015136049.tif 000032
を満たす値であり、ｅが双線形写像であり、ｖ＝ｗならばδ（ｖ，ｗ）＝１であり、ｖ≠ｗならばδ（ｖ，ｗ）＝０であり、基底（ｂｉ，１，…，ｂｉ，Ｎ（ｉ））および基底（ｂ*ｉ，１，…，ｂ*ｉ，Ｎ（ｉ））に対し、ｅ（ｂｉ，ｖ，ｂ*ｉ，ｗ）＝ｇＴδ（ｖ，ｗ）を満たし、Ｎ（ｉ）が１以上の整数であり、｛βｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が係数βｉ，ιの集合であり、鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）が鍵ｋ*ｉ：＝（ｓｉ＋βｉ，１）ｂ*ｉ，１＋βｉ，２ｂ*ｉ，２＋…＋βｉ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）の集合であり、｛λｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が係数λｉ，ιの集合であり、ｓ*ｉ，０：＝λｉ，１ｂ*ｉ，１＋λｉ，２ｂ*ｉ，２＋…＋λｉ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）であり、｛γｉ，ｊ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が、署名対象に対応する情報を要素に含む第１集合に対応する係数集合であり、
ｉ∈Ｉ（ｊ）について、入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝に対して要素ｓ*ｉ，ｊ：＝ｓ*ｉ，ｊ−１＋αｉｋ*ｉ＋γｉ，ｊ，１ｂ*ｉ，１＋γｉ，ｊ，２ｂ*ｉ，２＋…＋γｉ，ｊ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）を得る第１処理部と、
ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について、入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝に対して要素ｓ*ｉ，ｊ：＝ｓ*ｉ，ｊ−１＋γｉ，ｊ，１ｂ*ｉ，１＋γｉ，ｊ，２ｂ*ｉ，２＋…＋γｉ，ｊ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）を得る第２処理部と、を有し、
前記要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とする、代理署名情報生成部と、
を有する代理署名装置。
【請求項３】
請求項２の代理署名装置であって、
前記署名対象に対応する情報を要素に含む第２集合に対応する係数集合｛υｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝に対して
【数３１】
2015136049.tif 000033
の関係を満たす代理署名装置。
【請求項４】
請求項２または３の代理署名装置であって、
νｉ，１，１が０以外のランダム値であり、νｉ，１，２，…，νｉ，１，Ｎ（ｉ）が任意値であり、｛ｂ〜*ｉ，１｝ｉ∈Ｉ（ｊ）がｂ〜*ｉ，１：＝νｉ，１，１ｂ*ｉ，１＋νｉ，１，２ｂ*ｉ，２＋…＋νｉ，１，Ｎ（ｉ）ｂ*ｉ，１，Ｎ（ｉ）の集合であり、
ｂ*ｉ，１は秘匿されており、前記第１処理部と前記第２処理部は、｛ｂｉ，２，…，ｂｉ，Ｎ（ｉ）｝ｉ∈Ｉ（ｊ）の少なくとも一部と前記集合｛ｂ〜*ｉ，１｝ｉ∈Ｉ（ｊ）とを用い、前記要素ｓ*ｉ，ｊを得る代理署名装置。
【請求項５】
請求項２から４の何れかの代理署名装置であって、
Ｎ（ｉ）＝８であり、βｉ，１＝βｉ，３＝βｉ，４＝βｉ，５＝βｉ，６＝βｉ，８＝０、βｉ，２＝ｓ’ｉ、βｉ，７＝φｉであり、φｉがランダム値であり、
【数３２】
2015136049.tif 000034
を満たし、ｓ*ｉ，０＝０であり、
γｉ，ｊ，１＝ｒｉ，ｊπ、γｉ，ｊ，２＝ｒ’ｉ，ｊ、γｉ，ｊ，３＝τｉ，ｊ、γｉ，ｊ，４＝τｉ，ｊＭｅｓ、γｉ，ｊ，７＝ｒｉ，ｊφ〜ｉ，１＋ｒ*ｉ、γｉ，ｊ，５＝γｉ，ｊ，６＝γｉ，ｊ，８＝０であり、前記署名対象に対応する情報がＭｅｓであり、π，τｉ，ｊ，φ〜ｉ，１，ｒ*ｉ，ｒｉ，ｊ，ｒ’ｉ，ｊがランダム値であり、ｒ１，ｊ＋…＋ｒＬ，ｊ＝０およびｒ’１，ｊ＋…＋ｒ’Ｌ，ｊ＝０を満たす、代理署名装置。
【請求項６】
Ｌが１以上の整数であり、ｉ∈｛１，…，Ｌ｝であり、
署名対象に対応する検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝を生成する検証情報生成部と、
前記検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝および入力された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝＝｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝に対する双線形写像の像が、入力されたｓ０対応値となるかを判定する検証部と、
を有する署名検証装置。
【請求項７】
Ｌが１以上の整数であり、ｓ０が任意値であり、ｅが双線形写像であり、ｖ＝ｗならばδ（ｖ，ｗ）＝１であり、ｖ≠ｗならばδ（ｖ，ｗ）＝０であり、ｉ∈｛１，…，Ｌ｝であり、基底（ｂｉ，１，…，ｂｉ，Ｎ（ｉ））および基底（ｂ*ｉ，１，…，ｂ*ｉ，Ｎ（ｉ））に対し、ｅ（ｂｉ，ｖ，ｂ*ｉ，ｗ）＝ｇＴδ（ｖ，ｗ）を満たし、Ｎ（ｉ）が１以上の整数であり、
署名対象に対応する情報を要素に含む第２集合に対応する係数集合｛υｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝から、ｃｉ：＝υｉ，１ｂｉ，１＋…＋υｉ，Ｎ（ｉ）ｂｉ，Ｎ（ｉ）の集合である検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝を得る検証情報生成部と、
前記検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝、入力された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝、および値ｇＴｓ０が
【数３３】
2015136049.tif 000035
を満たすかを判定する検証部と、
を有する署名検証装置。
【請求項８】
請求項７の署名検証装置であって、
Ｎ（ｉ）＝８であり、υｉ，１＝１、υｉ，２＝υ、υｉ，３＝τ’ｉＭｅｓ、υｉ，４＝−τ’ｉ、υｉ，８＝ηｉ、υｉ，５＝υｉ，６＝υｉ，７＝０であり、前記署名対象に対応する情報がＭｅｓであり、τ’ｉ，ηｉがランダム値であり、υが任意値である、署名検証装置。
【請求項９】
Ｒ，Ｌが１以上の整数であり、ＭがＬ×Ｒ行列であり、ＳＥ→がＲ個の任意値からなる復元ベクトルであり、Ｎ（ｉ）が１以上の整数であり、｛βｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が係数βｉ，ιの集合であり、（ｂ*ｉ，１，…，ｂ*ｉ，Ｎ（ｉ））が基底であり、（・）Ｔが（・）の転置であり、
Ｒ個の任意値からなるベクトルｆ→を得る任意値生成部と、
（ｓ１，…，ｓＬ）Ｔ：＝Ｍ・（ｆ→）Ｔを得る分散値生成部と、
ｓ０：＝ＳＥ→・ｆ→を得る復元値生成部と、
鍵ｋ*ｉ：＝（ｓｉ＋βｉ，１）ｂ*ｉ，１＋βｉ，２ｂ*ｉ，２＋…＋βｉ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）を得る鍵生成部と、
を有する鍵生成装置。
【請求項１０】
ｎ個の代理署名装置Ｕ（１），…，Ｕ（ｎ）と署名検証装置とを有し、
ｎおよびＬが１以上の整数であり、ｋが１以上のｎ以下の整数であり、｛Ｕ（θ（１）），…，Ｕ（θ（ｋ））｝⊆｛Ｕ（１），…，Ｕ（ｎ）｝であり、ｊ∈｛１，…，ｋ｝であり、前記代理署名装置Ｕ（θ（ｊ））が｛１，…，Ｌ｝の部分集合Ｉ（ｊ）に対応し、｛ｓｉ｝ｉ∈｛１，…，Ｌ｝が任意値ｓｉの集合であり、前記部分集合Ｉ（ｊ）の和集合∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ）に対応する前記任意値ｓｉの線形結合が値ｓ０であり、鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）が前記任意値ｓｉに対応する鍵ｋ*ｉの集合であり、｛ｓ*ｉ，０｝ｉ∈｛１，…，Ｌ｝が初期設定されており、
前記代理署名装置Ｕ（θ（ｊ））は、
ｉ∈Ｉ（ｊ）について、入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１と前記鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）とを用い、署名対象に対応する要素ｓ*ｉ，ｊを得、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について、前記代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１を用い、前記署名対象に対応する要素ｓ*ｉ，ｊを得、前記要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とし、
前記署名検証装置は、
前記署名対象に対応する検証値ｃｉおよび入力された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝＝｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝に対する双線形写像の像が、前記値ｓ０に対応する値となるかを判定する、代理署名システム。
【請求項１１】
ｎ個の代理署名装置Ｕ（１），…，Ｕ（ｎ）と署名検証装置とを有し、
ｎおよびＬが１以上の整数であり、ｋが１以上のｎ以下の整数であり、｛Ｕ（θ（１）），…，Ｕ（θ（ｋ））｝⊆｛Ｕ（１），…，Ｕ（ｎ）｝であり、ｊ∈｛１，…，ｋ｝であり、前記代理署名装置Ｕ（θ（ｊ））が｛１，…，Ｌ｝の部分集合Ｉ（ｊ）に対応し、ｓ０が任意値であり、｛ｓｉ｝ｉ∈｛１，…，Ｌ｝が任意値ｓｉの集合であり、係数集合｛αｉ｝ｉ∈Ｉ（ｊ）が係数αｉの集合であり、
【数３４】
2015136049.tif 000036
を満たし、ｅが双線形写像であり、ｖ＝ｗならばδ（ｖ，ｗ）＝１であり、ｖ≠ｗならばδ（ｖ，ｗ）＝０であり、基底（ｂｉ，１，…，ｂｉ，Ｎ（ｉ））および基底（ｂ*ｉ，１，…，ｂ*ｉ，Ｎ（ｉ））に対し、ｅ（ｂｉ，ｖ，ｂ*ｉ，ｗ）＝ｇＴδ（ｖ，ｗ）を満たし、Ｎ（ｉ）が１以上の整数であり、係数集合｛βｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が係数βｉ，ιの集合であり、鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）が鍵ｋ*ｉ：＝（ｓｉ＋βｉ，１）ｂ*ｉ，１＋βｉ，２ｂ*ｉ，２＋…＋βｉ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）の集合であり、係数集合｛λｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が係数λｉ，ιの集合であり、ｓ*ｉ，０：＝λｉ，１ｂ*ｉ，１＋λｉ，２ｂ*ｉ，２＋…＋λｉ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）であり、｛γｉ，ｊ，ι｝ι∈｛１，…，Ｎ（ｉ）｝が、署名対象に対応する情報を要素に含む第１集合に対応する係数集合であり、
前記代理署名装置Ｕ（θ（ｊ））は、
入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝に対し、ｉ∈Ｉ（ｊ）について要素ｓ*ｉ，ｊ：＝ｓ*ｉ，ｊ−１＋αｉｋ*ｉ＋γｉ，ｊ，１ｂ*ｉ，１＋γｉ，ｊ，２ｂ*ｉ，２＋…＋γｉ，ｊ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）を得、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について要素ｓ*ｉ，ｊ：＝ｓ*ｉ，ｊ−１＋γｉ，ｊ，１ｂ*ｉ，１＋γｉ，ｊ，２ｂ*ｉ，２＋…＋γｉ，ｊ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）を得て、前記要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とし、
前記署名検証装置は、
前記署名対象に対応する情報を要素に含む第２集合に対応する係数集合｛υｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝から得られるｃｉ：＝υｉ，１ｂｉ，１＋…＋υｉ，Ｎ（ｉ）ｂｉ，Ｎ（ｉ）の集合である検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝、前記代理署名装置Ｕ（θ（ｋ））から出力された代理署名情報｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝である署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝、および入力された値ｇＴｓ０が
【数３５】
2015136049.tif 000037
を満たすかを判定する、代理署名システム。
【請求項１２】
請求項１１の代理署名システムであって、
【数３６】
2015136049.tif 000038
の関係を満たす代理署名システム。
【請求項１３】
請求項１から５の何れかの代理署名装置、請求項６から８の何れかの署名検証装置、または請求項９の鍵生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に代理署名方式に関する。
【背景技術】
【０００２】
代理署名方式は、ある署名者が代理署名者に署名の権限を移譲することが可能な署名方式である。従来、例えば、非特許文献１から３のような代理署名方式が提案されていた。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Beheshti-Atashgah, M., Bayat, M.: Designated verifier threshold proxy signature scheme without random oracles. ePrint, IACR, インターネット＜http://eprint.iacr.org/2012/488＞.
【非特許文献２】Mambo, M., Usuda, K., Okamoto, E.: Proxy signature: delegation of the power to sign messages. IEICE Transactions on Fundamentals. 76(1996) 1338-1353.
【非特許文献３】Zhang, K.: Threshold proxy signature schemes. Information Security Workshop, Japan. (1997) 191-197.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、従来のいずれの方式も、代理署名者に移譲する署名権限の構造が単純なものに限られており、一般のアクセス構造を持つ署名権限を委譲することができなかった。例えば、従来方式は、或る数以上の任意の代理署名者が協力した場合に署名を生成できるように署名権限を委譲するものであり、特定の組み合わせの代理署名者が協力した場合に署名を生成できるように署名権限の委譲を行うことができなかった。
【０００５】
本発明の課題は、一般アクセス構造を持つ署名権限を委譲することができる代理署名技術を提供することである。
【課題を解決するための手段】
【０００６】
ｎ個の代理署名装置Ｕ（１），…，Ｕ（ｎ）と署名検証装置とを有し、権限が委譲された｛Ｕ（θ（１）），…，Ｕ（θ（ｋ））｝⊆｛Ｕ（１），…，Ｕ（ｎ）｝が署名生成を行う。ただし、ｎは１以上の整数であり、ｋは１以上のｎ以下の整数である。各代理署名装置Ｕ（θ（ｊ））（ただし、ｊ∈｛１，…，ｋ｝）は、｛１，…，Ｌ｝の部分集合Ｉ（ｊ）に対応する（ただし、Ｌは１以上の整数）。任意値ｓｉの集合｛ｓｉ｝ｉ∈｛１，…，Ｌ｝に対し、部分集合Ｉ（ｊ）の和集合∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ）に対応する任意値ｓｉの線形結合を値ｓ０とする。
【０００７】
各代理署名装置Ｕ（θ（ｊ））は、ｉ∈Ｉ（ｊ）について、入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１と鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）とを用い、署名対象に対応する要素ｓ*ｉ，ｊを得る。ただし、鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）は上述の任意値ｓｉに対応する鍵ｋ*ｉの集合である。また、各代理署名装置Ｕ（θ（ｊ））は、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について、代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１を用い、署名対象に対応する要素ｓ*ｉ，ｊを得る。各代理署名装置Ｕ（θ（ｊ））は、得られた要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とする。なお｛ｓ*ｉ，０｝ｉ∈｛１，…，Ｌ｝は初期設定されており、代理署名装置Ｕ（θ（ｋ））で得られた代理署名情報｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝が署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝となる。
【０００８】
署名検証装置は、署名対象に対応する検証値ｃｉおよび入力された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝に対する双線形写像の像が、上述の値ｓ０に対応する値となるかを判定する。
【発明の効果】
【０００９】
本発明では、一般アクセス構造を持つ署名権限を委譲することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態の代理署名システムの構成を例示したブロック図である。
【図２】図２は、実施形態の署名管理装置（鍵生成装置）の構成を例示したブロック図である。
【図３】図３は、権限が委譲された代理署名装置を例示したブロック図である。
【図４】図４は、実施形態の代理署名装置の構成を例示したブロック図である。
【図５】図５は、実施形態の署名検証装置の構成を例示したブロック図である。
【図６】図６は、一般アクセス構造を実現する単調スパンプログラムと、一般アクセス構造の権限の委譲との関係を説明するための概念図である。
【図７】図７は、実施形態の鍵生成処理を説明するためのフロー図である。
【図８】図８は、実施形態の代理署名処理を説明するためのフロー図である。
【図９】図９は、実施形態の署名検証処理を説明するためのフロー図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を説明する。
［概要］
まず、実施形態の概要を説明する。
実施形態では、ｎ個の代理署名装置Ｕ（１），…，Ｕ（ｎ）からなる集合Ｎｓｅｔ：＝｛Ｕ（１），…，Ｕ（ｎ）｝の任意の部分集合Ｋｓｕｂｓｅｔ：＝｛Ｕ（θ（１）），…，Ｕ（θ（ｋ））｝⊆Ｎｓｅｔに署名権限を委譲する。部分集合Ｋｓｕｂｓｅｔの一例は｛Ｕ（１），…，Ｕ（ｋ）｝である。この部分集合Ｋｓｕｂｓｅｔの設定方法に制限はなく、集合Ｎｓｅｔの真部分集合であってもよいし、真部分集合でなくてもよい。また、複数個の部分集合Ｋｓｕｂｓｅｔが設定されてもよいし、１個の部分集合Ｋｓｕｂｓｅｔのみが設定されてもよい。複数個の部分集合Ｋｓｕｂｓｅｔが設定される場合、各部分集合Ｋｓｕｂｓｅｔの要素数ｋは互いに同一であってもよいし、異なっていてもよい。ただし、ｎは１以上の整数（例えば、ｎ≧２）であり、ｋは１以上のｎ以下の整数（例えば、ｋ≧２）である。また、Λ：＝Φは、ΛがΦであると定義することを意味する。
【００１２】
各代理署名装置Ｕ（θ（ｊ））（ただし、ｊ∈｛１，…，ｋ｝）は、集合｛１，…，Ｌ｝の部分集合Ｉ（ｊ）⊆｛１，…，Ｌ｝に対応付けられる。ただし、Ｌは１以上の整数（例えば、Ｌ≧２）であり、１，…，Ｌは一般アクセス構造を実現する単調スパンプログラムを構成する行列Ｍの各行のインデックスである（詳細は後述する）。各ｉ∈｛１，…，Ｌ｝にはそれぞれ任意値ｓｉが設定され、部分集合Ｉ（ｊ）の和集合∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ）に対応する任意値ｓｉの線形結合が値ｓ０となっている。すなわち、署名権限が委譲された代理署名装置Ｕ（θ（ｊ））に対応する任意値ｓｉの線形結合が値ｓ０となっており、署名権限が委譲された代理署名装置Ｕ（θ（ｊ））に対応する任意値ｓｉが集まればｓ０を復元できる関係となっている。
【００１３】
各代理署名装置Ｕ（θ（ｊ））∈Ｋｓｕｂｓｅｔは、Ｕ（θ（１）），...，Ｕ（θ（ｋ）の順序で以下の代理署名処理を行う。
＜代理署名処理＞
代理署名装置Ｕ（θ（ｊ））は、ｉ∈Ｉ（ｊ）について、入力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１と鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）とを用い、署名対象に対応する要素ｓ*ｉ，ｊを得る。ただし、鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）は上述の任意値ｓｉに対応する鍵ｋ*ｉの集合である。また、各代理署名装置Ｕ（θ（ｊ））は、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝について、代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝の要素ｓ*ｉ，ｊ−１を用い、署名対象に対応する要素ｓ*ｉ，ｊを得る。ただし、代理署名装置Ｕ（θ（１））は、初期設定された｛ｓ*ｉ，０｝ｉ∈｛１，…，Ｌ｝を用いてこれらの処理を行う。
【００１４】
最後に代理署名装置Ｕ（θ（ｋ））で得られた代理署名情報｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝が署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝となる。
【００１５】
＜署名検証処理＞
署名検証装置は、署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝を入力とし、その署名対象に対応する検証値ｃｉおよび署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝に対する双線形写像の像が、上述の値ｓ０に対応する値となるかを判定する。この双線形写像の像が上述の値ｓ０に対応する値となれば合格であり、ならなければ不合格である。上述のように、署名権限が委譲された代理署名装置Ｕ（θ（ｊ））に対応する任意値ｓｉが集まればｓ０を復元できる関係になっており、上述の代理署名処理で用いられる鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｊ）は任意値ｓｉに対応する。そのため、署名権限が委譲された代理署名装置Ｕ（θ（ｊ））∈Ｋｓｕｂｓｅｔが協力して署名を生成した場合には、上述の双線形写像の像が上述の値ｓ０に対応する値となり、合格となる。
【００１６】
以上により、ｎ個の代理署名装置Ｕ（１），…，Ｕ（ｎ）からなる集合Ｎｓｅｔの任意の部分集合Ｋｓｕｂｓｅｔ⊆Ｎｓｅｔに署名権限を委譲でき、そのような組み合わせのみが署名を正しく生成できる。このような署名権限委譲の構造は一般アクセス構造をなしている。
【００１７】
［詳細］
次に、実施形態の詳細を説明する。
＜記号＞
以下の記述で用いる記号の説明をする。
ＳＥＴが集合のとき、ｙ←ＵＳＥＴは、ｙが集合ＳＥＴからランダムに選ばれることを意味する。Ｆｑは、要素の数（位数）がｑ個の有限体を意味する。ただし、ｑは１以上の整数であり、例えば、素数である。また、Ｆｑ＼｛０｝（Ｆｑから０を除いたもの）をＦ×ｑと記す。ε→はＦｑ上のベクトルを意味する。つまり、１以上の整数Ｎにおいてε→：＝（ε１，…，εＮ）∈ＦｑＮである。２つのベクトルε→：＝（ε１，…，εＮ）とω→：＝（ω１，…，ωＮ）の間の内積演算
【数１】
2015136049.tif 000003
をε→・ω→と記す。（ε→）Ｔはε→の転置ベクトルを意味する。Ｘが行列のとき、ＸＴはＸの転置行列を意味する。すなわち、（・）Ｔは（・）の転置を表す。ＧＬ（Ｎ，Ｆｑ）は、Ｆｑ上の次数がＮの一般線形群（要素がＦｑのＮ×Ｎ正則行列の集合）を意味する。なお、記載表記の制約上、「ｙ←ＵＳＥＴ」「ε→」のように記載するが、これらはそれぞれ
【数２】
2015136049.tif 000004
と同義である。
【００１８】
＜双対双線形ベクトル空間:DPVS(Dual Pairing Vector Space)＞
双対双線形ベクトル空間（ＤＰＶＳ）は、双線形写像群の上で構成される。そこで、まず双線形写像群について説明する。
【００１９】
《双線形写像群》
双線形写像群（ｑ，Ｇ，Ｇ＊，ＧＴ，ｇ，ｇ＊，ｅ’）は、位数がｑの巡回加法群Ｇ，Ｇ＊と、位数がｑの巡回乗法群ＧＴと、巡回加法群Ｇの要素ｇ≠０∈Ｇと、巡回加法群Ｇ＊の要素ｇ＊≠０∈Ｇ＊と、双線形写像ｅ’：Ｇ×Ｇ＊→ＧＴからなる。Ｇ＝Ｇ＊であってもよいし、Ｇ≠Ｇ＊であってもよい。ここで、ｅ’（ｓｇ，ｔｇ＊）＝ｅ’（ｇ，ｇ＊）ｓｔおよびｅ’（ｇ，ｇ＊）≠１が成立する。ただしｓ，ｔ∈Ｆｑである。なお、ｅ’の例はＷｅｉｌペアリングやＴａｔｅペアリングなどのペアリングである。Ｇｂｐｇ（１λ）は、安全係数（パラメータサイズ）λを入力として双線形写像群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，Ｇ＊，ＧＴ，ｇ，ｇ＊，ｅ’）を出力するアルゴリズムである。Ｇ＝Ｇ＊の場合、Ｇｂｐｇ（１λ）は安全係数λを入力としてパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ’）を出力してもよい。
【００２０】
《双対双線形ベクトル空間（ＤＰＶＳ）》
双線形写像群（ｑ，Ｇ，Ｇ，ＧＴ，ｇ，ｇ＊，ｅ’）上の双対双線形ベクトル空間（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊，ｅ）は、１以上の整数ｑ（例えば素数）、Ｆｑ上のＮ次元のベクトル空間Ｖ：＝Ｇ×・・・×Ｇ（巡回加法群Ｇの元をＮ個（Ｎ≧１）並べたもの）、Ｆｑ上のＮ次元のベクトル空間Ｖ＊：＝Ｇ＊×・・・×Ｇ＊（巡回加法群Ｇ＊の元をＮ個並べたもの）、位数がｑの巡回乗法群ＧＴ、ベクトル空間Ｖの標準基底Ａ：＝（ａ１，...，ａＮ）、ベクトル空間Ｖ＊の標準基底Ａ＊：＝（ａ＊１，...，ａ＊Ｎ）、および双線形写像ｅ：Ｖ×Ｖ＊→ＧＴからなる。ＡおよびＡ＊はそれぞれ正規直交基底である。標準基底Ａはベクトル空間Ｖを張り（span）、標準基底Ａ＊はベクトル空間Ｖ＊を張る。例えば、ａμ（μ∈｛１，...，Ｎ｝）およびａ＊μ（μ∈｛１，...，Ｎ｝）は以下のように定義される。
【数３】
2015136049.tif 000005
【００２１】
また、Ω：＝（Ω１，...，ΩＮ）∈ＶとΘ：＝（Θ１，...，ΘＮ）∈Ｖ＊との間の双線形写像ｅは、以下のように定義される。
【数４】
2015136049.tif 000006
このとき、以下が成立する。
ｅ（ｓΩ，ｔΘ）＝ｅ（Ω，Θ）ｓｔ  …（１）
ｅ（Ωｖ，Θｗ＊）＝ｅ（ｇ，ｇ＊）δ（ｖ，ｗ）  …（２）
ただし、δ（ｖ，ｗ）はクロネッカーのデルタであり、ｖ＝ｗならばδ（ｖ，ｗ）＝１であり、ｖ≠ｗならばδ（ｖ，ｗ）＝０である。
【００２２】
Ｇｄｐｖｓ（１λ，Ｎ，ｐａｒａｍＧ）は、安全係数λと次元Ｎ（ただし、Ｎは１以上の整数）を入力として、双対双線形ベクトル空間（ＤＰＶＳ）のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，Ｖ＊，ＧＴ，Ａ，Ａ＊，ｅ）を出力するアルゴリズムである。Ｇ＝Ｇ＊の場合、Ｇｄｐｖｓ（１λ，Ｎ，ｐａｒａｍＧ）は、安全係数λと次元Ｎを入力として、ｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）を出力してもよい。このアルゴリズムの内部で、前述のＧｂｐｇ（１λ）を利用する。
【００２３】
ベクトル空間Ｖの任意の基底Ｂ：＝（ｂ１，...，ｂＮ）およびベクトル空間Ｖ＊の任意の基底Ｂ＊：＝（ｂ＊１，...，ｂ＊Ｎ）に関して、以下のように定義する。ただし、（ε１，…，εＮ）∈ＦｑＮおよび（ω１，…，ωＮ）∈ＦｑＮである。
【数５】
2015136049.tif 000007
【００２４】
＜一般アクセス構造＞
つぎに、一般アクセス構造を実現する単調スパンプログラム（一般的な秘密分散を表現する方式）について述べる。
Ｆｑを有限体とし、｛ｘ１，...，ｘｎ｝をｎ個の変数からなる集合とする。ただし、ｎは１以上の整数であり、各変数ｘｚ（ｚ∈｛１，...，ｎ｝）は、秘密を秘密分散した分散値を保持する者に対応し、代理署名の枠組みでは、各代理署名装置（代理署名者）に対応する。Ｆｑ上の単調スパンプログラムは、ラベルづけされた行列Ｓ：＝（Ｍ，ρ）である。ここで、ＭはＦｑ上の（Ｌ×Ｒ）行列である。ρは各変数ｘ１，...，ｘｎを行列Ｍの各行へラベルづけ（対応づけ）するための写像である。具体的には、ρは行列Ｍの各行のインデックスｉ∈｛１，…，Ｌ｝から変数ｘｚ（ｚ∈｛１，...，ｎ｝）への写像ｘｚ＝ρ（ｉ）である。すなわち、各行はｉ＝ρ−１（ｘｚ）（ただしｚ∈｛１，...，ｎ｝）でラベル付けされる。行列Ｍのすべての行はそれぞれ１個の変数ｘｚでラベル付けされる。すなわち、各インデックスｉ∈｛１，…，Ｌ｝は１個の変数ｘｚ∈｛１，...，ｎ｝のみに対応する。ただし、各変数ｘｚは１個のインデックスｉ∈｛１，…，Ｌ｝のみに対応してもよいし、複数個のインデックスｉ∈｛１，…，Ｌ｝に対応してもよい。すなわち、各変数ｘｚ（すなわち、各代理署名装置）は、集合｛１，...，Ｌ｝の部分集合Ｉ（ｚ）⊆｛１，...，Ｌ｝に対応する。行列Ｍのすべての行がそれぞれ１個の変数ｘｚでラベル付けされるため、ｚ１≠ｚ２であるｚ１，ｚ２∈｛１，...，ｎ｝に対し、積集合Ｉ（ｚ１）∩Ｉ（ｚ２）は空集合となる。
【００２５】
単調スパンプログラムＳは、以下のようなルールに従って、入力Γ：＝（Γ１，...，Γｎ）∈｛０，１｝ｎを受理または拒否する。ただし、Γｚ（ｚ∈｛１，...，ｎ｝）はそれぞれ変数ｘｚに一対一に対応する。入力Γが与えられると、Γｚ＝１であるような変数ｘｚがラベルづけする行（つまり
【数６】
2015136049.tif 000008
）からなるＭの部分行列ＭΓが定まる。このとき、単調スパンプログラムＳは所定のＲ次元ベクトルＳＥ→（例えば、１→＝（１，...，１））について、ＳＥ→∈ｓｐａｎ＜ＭΓ＞ならば入力Γを受理し、ＳＥ→∈＜ＭΓ＞でなければ入力Γを拒否する。なお、ＳＥ→∈ｓｐａｎ＜ＭΓ＞とは、部分行列ＭΓに属する各行がベクトルＳＥ→を張ることを意味する。言い換えると、ｓｐａｎ＜ＭΓ＞とは、部分行列ＭΓに属する各行の適当な線形結合がベクトルＳＥ→となることを意味する。ここで、単調スパンプログラム（Ｍ，ρ）が入力Γを受理することは、Γｉ＝１であるような変数ｘｚに対応する代理署名装置が協力して秘密を復元できる（署名を作成できる）ことに対応する。一方、拒否されるときは、Γｉ＝１であるような変数ｘｚに対応する代理署名装置がどのように協力しても秘密を復元できない（署名を作成できない）ことに対応する。
【００２６】
＜一般アクセス構造（単調スパンプログラム）に基づく代理署名の枠組み＞
次に、一般アクセス構造（単調スパンプログラム）に基づく代理署名の枠組みを示す。
【００２７】
《Ｓｅｔｕｐ》
アルゴリズムＳｅｔｕｐは、安全係数λを入力して、システム共通のマスター公開鍵ｍｐｋとマスター秘密鍵ｍｓｋを出力する。署名管理装置（オリジナル／マスター署名者）は、このアルゴリズムＳｅｔｕｐを用いてｍｐｋとｍｓｋを生成し、ｍｓｋを秘密に保存し、ｍｐｋを公開する。
【００２８】
《ＰＳｅｔｕｐ》
署名管理装置は、ｎ個の代理署名装置に対し、アルゴリズムＰＳｅｔｕｐを用いて、一般アクセス構造（単調スパンプログラム）Ｓ：＝（Ｍ，ρ）を持つ分散署名鍵を作成し、それぞれの代理署名装置に分散署名鍵を配布する。まず、署名管理装置は、Ｎｓｅｔ：＝｛Ｕ（１），…，Ｕ（ｎ）｝に対し、一般アクセス構造（単調スパンプログラム）Ｓを定める。これは、どのように署名権限を移譲するかという方針に基づき定める。さらに、そのときの権限移譲の付加情報（たとえば、期限等）を含む文書を“ｔｅｘｔ”とする。さらに、署名検証に用いるパラメータおよびそれらに対する署名管理装置の通常のディジタル署名（ＲＳＡ署名等）との組を（ａｕｘ，σ）とする。アルゴリズムＰＳｅｔｕｐは、（Ｓ，ｍｐｋ，ｍｓｋ，ｔｅｘｔ）を入力として、公開情報ｐｋｐｓｅｔｕｐ：＝（ａｕｘ，ｔｅｘｔ，σ，Ｓ）と代理署名装置の秘密鍵｛ｓｋｐｓｅｔｕｐ（ｚ）｝ｚ∈｛１，...，ｎ｝：＝｛（ｐｋｐｓｅｔｕｐ，ｓｋｚ）｝ｚ∈｛１，...，ｎ｝を出力する。ｓｋｚは前述の鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）である。このうち、ｓｋｐｓｅｔｕｐ（ｚ）が代理署名装置Ｕ（ｚ）（ただし、ｚ∈｛１，...，ｎ｝）の分散署名鍵として、代理署名装置Ｕ（ｚ）に秘密に渡される。
【００２９】
《Ｓｉｇ》
代理署名装置の部分集合Ｋｓｕｂｓｅｔ⊆Ｎｓｅｔが集まって代理署名を行うときのアルゴリズムがＳｉｇである。まず、最初の代理署名装置Ｕ（θ（１））がアルゴリズムＳｉｇθ（１）を用いて、ｓ〜１：＝｛ｓ*ｉ，１｝ｉ∈｛１，…，Ｌ｝を出力する。代理署名装置Ｕ（θ（１））は、ｓ〜１を次の代理署名者Ｕ（θ（２））に渡す。ｊ番目の代理署名装置Ｕ（θ（ｊ））（２≦ｊ≦ｋ−１）は、代理署名装置Ｕ（θ（ｊ−１））からｓ〜ｊ−１：＝｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝を受け取り、アルゴリズムＳｉｇθ（ｊ）を用いて、ｓ〜ｊ：＝｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝を出力し、それを次の代理署名装置Ｕ（θ（ｊ＋１））に送る。最後の代理署名装置Ｕ（θ（ｋ））は、ｓ〜ｋ−１：＝｛ｓ*ｉ，ｋ−１｝ｉ∈｛１，…，Ｌ｝を代理署名装置Ｕ（θ（ｋ−１））から受け取り、アルゴリズムＳｉｇθ（ｋ）を用いてｓ〜ｋ：＝｛ｓ*ｉ，ｋ｝ｉ∈｛１，…，Ｌ｝を出力する。最後に、ｓ*ｉ：＝ｓ*ｉ，ｋとし、ｓ*：＝（｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝，ａｕｘ，ｔｅｘｔ，σ）をＳｉｇ（ｍｐｋ，｛ｓｋｊ｝ｊ∈｛１，...，ｋ｝，Ｋｓｕｂｓｅｔ，ｍ，ｐｋｐｓｅｔｕｐ）として（つまり、代理署名装置の部分集合Ｋｓｕｂｓｅｔに対するアルゴリズムＳｉｇの出力として）出力する。
【００３０】
単調スパンプログラム（一般アクセス構造）と、代理署名装置の部分集合Ｋｓｕｂｓｅｔを対応づけるために、以下のような関係を定める。単調スパンプログラムＳの入力Γ：＝（Γ１，...，Γｎ）∈｛０，１｝ｎにおいて、Γｚ＝１（ｚ∈｛１，...，ｎ｝）であることとＵ（ｚ）∈Ｋｓｕｂｓｅｔであることとが等価であるとする。ここで、単調スパンプログラムＳが部分集合Ｋｓｕｂｓｅｔを受理するとは、単調スパンプログラムＳが入力Γを受理することとする。これ以降、以上の枠組みで述べたアルゴリズムに基づく実施形態を詳細に説明する。
【００３１】
［第１実施形態］
図面を参照して、第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の代理署名システム１は、署名管理装置（鍵生成装置）１１、ｎ個の代理署名装置１２−１〜１２−ｎ（これらはＵ（１），…，Ｕ（ｎ）に相当する）、および署名検証装置１３を有し、これらはネットワークを介して通信可能に構成されている。各装置は、例えば、ＣＰＵ（central processing unit）やＲＡＭ（random-access memory）等の汎用または専用のコンピュータに所定のプログラムが読み込まれて構成される装置である。
【００３２】
図２に例示するように、本形態の署名管理装置１１は、セットアップ部１１１、ランダム値生成部１１２、分散値生成部１１３、復元値生成部１１４、署名部１１４１、鍵生成部１１５、線形結合係数生成部１１６、記憶部１１７、制御部１１８、および出力部１１９を有する。署名管理装置１１は、制御部１１８の制御のもとで各処理を実行する。各部で得られた情報は記憶部１１７に格納され、必要に応じて読み出され、各部の処理に用いられる。
【００３３】
図３に例示するように、本形態では代理署名装置１２−１〜１２−ｎからなる集合Ｎｓｅｔの部分集合Ｋｓｕｂｓｅｔをなすｋ個の代理署名装置１２−θ（１）〜１２−θ（ｋ）（これらはＵ（θ（１）），…，Ｕ（θ（ｋ）に相当する）に署名権限が委譲され、代理署名装置１２−θ（１）〜１２−θ（ｋ）がＳｉｇθ（１）〜Ｓｉｇθ（ｋ）（すなわち、Ｓｉｇ）を実行して署名ｓ*を生成する。前述のように、部分集合Ｋｓｕｂｓｅｔの設定方法に制限はない。図４に例示するように、代理署名装置１２−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）は、入力部１２１−θ（ｊ）、判定部１２２−θ（ｊ）、第１処理部１２４−θ（ｊ）、第２処理部１２５−θ（ｊ）、出力部１２６−θ（ｊ）、記憶部１２７−θ（ｊ）、および制御部１２８−θ（ｊ）を有する。代理署名装置１２−θ（ｊ）は、制御部１１８の制御のもとで各処理を実行する。各部で得られた情報は記憶部１２７−θ（ｊ）に格納され、必要に応じて読み出され、各部の処理に用いられる。なお、その他の代理署名装置１２−ｚ（ただし、ｚ∈｛１，...，ｎ｝）の構成も同様である（図４のθ（ｊ）をｚに置換した構成）。
【００３４】
図５に例示するように、本形態の署名検証装置１３は、入力部１３１、検証情報生成部１３３、検証部１３４，１３８、出力部１３５、記憶部１３６、および制御部１３７を有する。署名検証装置１３は、制御部１３７の制御のもとで各処理を実行する。各部で得られた情報は記憶部１３６に格納され、必要に応じて読み出され、各部の処理に用いられる。
【００３５】
＜処理＞
次に各処理を説明する。なお、以下に示す｛βｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝，｛λｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝，｛γｉ，ｊ，ι｝ι∈｛１，…，Ｎ（ｉ）｝，｛υｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝は、以下の関係を満たす係数βｉ，ι，λｉ，ι，γｉ，ｊ，ι，υｉ，ι∈Ｆｑの集合である。
【数７】
2015136049.tif 000009
《Ｓｅｔｕｐ》
署名管理装置１１のセットアップ部１１１は、安全係数λを入力とし、次のようにＳｅｔｕｐを実行し、ｍｐｋとｍｓｋを生成する。まず、セットアップ部１１１は、安全係数λを入力としてＧｂｐｇを実行し、ランダムな双線形写像群ｐａｒａｍＧ＝（ｑ，Ｇ，Ｇ＊，ＧＴ，ｇ，ｇ＊，ｅ’）←ＲＧｂｐｇ（１λ）を得て出力する（Ｇ＝Ｇ＊の場合には、ｐａｒａｍＧ＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ’）でもよい）。セットアップ部１１１は、ランダム値κ←ＵＦ×ｑを選択し、
ｇＴ：＝ｅ（ｇ，ｇ*）κ  …（４）
を得て出力し、さらにＳＨＡ−２等の暗号学的ハッシュ（圧縮）関数Ｈを設定する。セットアップ部１１１は、安全係数λを入力とし、通常のディジタル署名の鍵生成アルゴリズムＫｅｙＧｅｎＡ（１λ）を実行し、通常のディジタル署名鍵ｓｋＡおよび検証鍵ｖｋＡのペア（ｓｋＡ，ｖｋＡ）←ＵＫｅｙＧｅｎＡ（１λ）を生成して出力する。
【００３６】
セットアップ部１１１は、ｔ＝１，...，ｄについて以下を設定する。ただし、ｄは単調スパンプログラムを構成する行列Ｍの行のサイズＬの最大値である。Ｎ（ｔ）は１以上の整数であり、例えば、Ｎ（ｔ）≧２である。
【００３７】
ＤＰＶＳのパラメータｐａｒａｍＶ（ｔ）：
ｐａｒａｍＶ（ｔ）：＝（ｑ，Ｖｔ，Ｖ＊ｔ，ＧＴ，Ａｔ，Ａ＊ｔ，ｅ）：＝Ｇｄｐｖｓ（１λ，Ｎ（ｔ），ｐａｒａｍＧ）
ただし、Ｖｔ，Ｖ＊ｔ，Ａｔ，Ａ＊ｔは、Ｎ＝Ｎ（ｔ）としたＶ，Ｖ＊，Ａ，Ａ＊である。また、Ｇ＝Ｇ＊の場合には、ｐａｒａｍＶ（ｔ）：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）でもよい。
【００３８】
行列（χｔ，ι，ζ）ι，ζ，（θｔ，ι，ζ）ι，ζ：
Ｘｔ：＝（χｔ，ι，ζ）ι，ζ←ＵＧＬ（Ｎ（ｔ），Ｆｑ）
（θｔ，ι，ζ）ι，ζ：＝κ・（ＸｔＴ）−１              …（５）
ただし、χｔ，ι，ζは行列Ｘｔの（ι，ζ）成分を意味する。
【００３９】
基底Ｂｔ，Ｂ*ｔ：
【数８】
2015136049.tif 000010
ただし、Ａｔ：＝（ａt,１，...，ａt,Ｎ）である。式（１）（２）（４）〜（７）の関係より、基底Ｂｔ：＝（ｂｔ，１，…，ｂｔ，Ｎ（ｔ））および基底Ｂ*ｔ：＝（ｂ*ｔ，１，…，ｂ*ｔ，Ｎ（ｔ））に対し、
ｅ（ｂｔ，ｖ，ｂ*ｔ，ｗ）＝ｇＴδ（ｖ，ｗ）  …（８）
の関係を満たす。
【００４０】
基底Ｂ＾ｔ，Ｂ*＾ｔ：
【数９】
2015136049.tif 000011
ただし、νｔ，ξ，ι∈Ｆｑは任意値（ランダム値または定数）である。例えば、ξ’∈｛１，...，Ｎ（ｔ）｝について、ξ＝ξ’のときにνｔ，ξ，ξ’＝１かつξ≠ξ’のときにνｔ，ξ，ξ’＝０とした場合、式（１０）（１１）の値ｂ*〜ｔ，ξはｂ*ｔ，ξとなる。例えば、すべてのξ’∈｛１，...，Ｎ（ｔ）｝についてνｔ，ξ，ξ’＝０とした場合、式（１０）（１１）の値ｂ*〜ｔ，ξは０となる。式（１０）からｂ*〜ｔ，ξ＝０となるものを取り除いたものを
【数１０】
2015136049.tif 000012
としてもよい。ただし、後述のＳｉｇθ（ｊ）で要素ｓ*ｉ，ｊを計算可能な構成である必要がある。
【００４１】
セットアップ部１１１は、ｍｓｋ：＝（｛Ｂ*ｔ｝ｔ∈｛１，...，ｄ｝，ｓｋＡ）、ｍｐｋ：＝（｛ｐａｒａｍＶ（ｔ），Ｂ＾ｔ，Ｂ*＾ｔ｝ｔ∈｛１，...，ｄ｝，ｇＴ，ｖｋＡ，Ｈ）を生成して出力する。ただし、Ｂ＾ｔ，Ｂ*＾ｔはそれぞれ、
【数１１】
2015136049.tif 000013
を表す。マスター秘密鍵ｍｓｋは署名管理装置１１の記憶部１１７に安全に格納される。マスター公開鍵ｍｐｋは、記憶部１１７に格納される他、代理署名装置１２−１〜１２ｎおよび署名検証装置１３にも送られ、各装置で利用可能なように設定される。
【００４２】
《ＰＳｅｔｕｐ》
署名管理装置１１は、アルゴリズムＰＳｅｔｕｐを用いて、一般アクセス構造（単調スパンプログラム）Ｓ：＝（Ｍ，ρ）を持つ分散署名鍵を作成する。ｎ個の代理署名装置１２−１〜１２−ｎからなる集合Ｎｓｅｔに対し、単調スパンプログラムＳが定められる。図６に例示するように、まず、前述の（Ｌ×Ｒ）行列ＭおよびＲ次元ベクトルＳＥ→＝Ｍ０（Ｒ個の任意値からなる復元ベクトル。例えば、１→＝（１，...，１））が定められる。各代理署名装置１２−ｚは各変数ｘｚ（ｚ∈｛１，...，ｎ｝）に一対一で対応付けられる。前述の入力Γ：＝（Γ１，...，Γｎ）∈｛０，１｝ｎにおいてΓｚ＝１であるような変数ｘｚに対応する代理署名装置１２−ｚからなる集合が部分集合Ｋｓｕｂｓｅｔである。また、前述の写像ｘｚ＝ρ（ｉ）（ただしｚ∈｛１，...，ｎ｝，ｉ∈｛１，…，Ｌ｝）が定められる。この写像ρ（ｉ）により、各代理署名装置１２−ｚが、行列Ｍの行Ｍｉを表すインデックスｉの集合｛１，...，Ｌ｝の部分集合Ｉ（ｚ）⊆｛１，...，Ｌ｝に対応付けられる。なお、行列Ｍ、Ｒ次元ベクトルＳＥ→、および写像ρ（ｉ）は、行Ｍｉ（ただし、ｉ∈∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ））からなる部分行列ＭΓについてＳＥ→＝Ｍ０∈ｓｐａｎ＜ＭΓ＞を満たすように設定される。ただし、∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ）は、部分集合Ｋｓｕｂｓｅｔに属する代理署名装置１２−（θ（ｊ））（ただし、ｊ∈｛１，...，ｋ｝）に対応する部分集合Ｉ（ｊ）の和集合である。
【００４３】
図７に例示するように、署名管理装置１１のランダム値生成部（任意値生成部）１１２は、Ｒ個の有限体Ｆｑの元からなるＲ次元ベクトルｆ→←ＵＦｑＲを得て出力する（ステップＳ１１２）。次に、分散値生成部１１３は、行列Ｍ及びＲ次元ベクトルｆ→を入力として、任意値（分散値）ｓｉからなる（ｓ１，…，ｓＬ）Ｔ：＝Ｍ（ｆ→）Ｔを得て出力する（ステップＳ１１３）。また、復元値生成部１１４は、Ｒ次元ベクトルＳＥ→およびＲ次元ベクトルｆ→を入力として、任意値（復元値）ｓ０：＝ＳＥ→・ｆ→を得て出力する（ステップＳ１１４）。ここで、ｓ０＝Ｍ０（ｆ→）Ｔ、ｓｉ＝Ｍｉ（ｆ→）Ｔ（ただし、ｉ∈｛１，…，Ｌ｝）、およびＭ０∈ｓｐａｎ＜ＭΓ＞であるため、分散値ｓｉ（ただし、ｉ∈∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ））の線形結合は値ｓ０である。言い換えると、
【数１２】
2015136049.tif 000014
を満たす係数αｉ∈Ｆｑからなる係数集合｛αｉ｝ｉ∈Ｉ（ｊ）が存在する。さらに式（１３）の変形から、
【数１３】
2015136049.tif 000015
を満たす係数αｉ∈Ｆｑからなる係数集合｛αｉ｝ｉ∈Ｉ（ｊ）が存在すると言える。
【００４４】
署名部１１４１は、ｔｅｘｔ、ｇＴ、ｓ０、およびｓｋＡを入力とし、ｓｋＡを用いてｇＴｓ０とｔｅｘｔとのビット連結ｇＴｓ０｜ｔｅｘｔに対して通常のディジタル署名σ＝ＳｉｇｎＡ（ｓｋＡ,ｇＴｓ０｜ｔｅｘｔ）を生成して出力する（ステップＳ１１４１）。
【００４５】
鍵生成部１１５は、基底の集合｛Ｂ*ｔ｝ｔ∈｛１，...，ｄ｝を用い、各ｉ∈｛１，...，Ｌ｝に対して鍵
【数１４】
2015136049.tif 000016
を得て出力する（ステップＳ１１５）。前述の関係（式（３））を満たすのであれば、係数βｉ，ιはランダム値であっても定数であってもよい。
【００４６】
鍵生成部１１５は、部分集合Ｉ（ｚ）（ただし、ｚ∈｛１，...，ｎ｝）に対応する鍵ｋ*ｉからなる鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）を鍵ｓｋｚ＝｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）とし、公開情報ｐｋｐｓｅｔｕｐ：＝（ｇＴｓ０，ｔｅｘｔ，σ，Ｓ：＝（Ｍ，ρ））とし、分散署名鍵の集合｛ｓｋｐｓｅｔｕｐ（ｚ）｝ｚ∈｛１，...，ｎ｝：＝｛（ｐｋｐｓｅｔｕｐ，ｓｋｚ）｝ｚ∈｛１，...，ｎ｝を得て出力する。各鍵ｓｋｚ＝｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）は、それぞれに対応する代理署名装置１２−ｚ（ただし、ｚ∈｛１，...，ｎ｝）へ安全に送られ、それぞれの記憶部１２７−ｚに格納される。ｐｋｐｓｅｔｕｐは、各代理署名装置１２−ｚ（ただし、ｚ∈｛１，...，ｎ｝）および署名検証装置１３に送られ、各装置が利用可能なように設定される。
【００４７】
≪Ｓｉｇ≫
次に、ｋ個の代理署名装置１２−θ（１）〜１２−θ（ｋ）∈ＫｓｕｂｓｅｔがＳｉｇθ（１）〜Ｓｉｇθ（ｋ）（すなわち、Ｓｉｇ）を実行して署名ｓ*を生成する処理を説明する（図３）。
【００４８】
まず、署名管理装置１１の線形結合係数生成部１１６が、部分集合Ｋｓｕｂｓｅｔおよび公開情報ｐｋｐｓｅｔｕｐを入力とし、式（１３）（すなわち、式（１４））を満たす係数集合｛αｉ｝ｉ∈Ｉ（ｊ）を生成して出力する。各係数集合｛αｉ｝ｉ∈Ｉ（ｊ）は、例えば、対応する代理署名装置１２−θ（ｊ）に送られ、記憶部１２７−θ（ｊ）に安全に格納される。或いは、すべての係数集合｛αｉ｝ｉ∈Ｉ（ｊ）が代理署名装置１２−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）に送られて共有され、すべての記憶部１２７−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）に格納されてもよい。
【００４９】
その後、代理署名装置１２−θ（１），...，代理署名装置１２−θ（ｋ）の順に、それぞれがＳｉｇθ（１），...，Ｓｉｇθ（ｋ）を実行する。
図８に例示するように、Ｓｉｇθ（ｊ）では、代理署名装置１２−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）の入力部１２１−θ（ｊ）に、署名対象の文書ｍと代理署名装置１２−θ（ｊ−１）から出力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝が入力される（ステップＳ１２１−θ（ｊ−１））。ただし、ｊ＝１の場合の代理署名情報｛ｓ*ｉ，０｝ｉ∈｛１，…，Ｌ｝は、初期設定された
【数１５】
2015136049.tif 000017
の集合である。前述の関係（式（３））を満たすのであれば、係数λｉ，ιはランダム値であっても定数であってもよい。例えば、ｓ*ｉ，０：＝０である。
【００５０】
制御部１２８−θ（ｊ）は、ｉを１に設定する（ｉ：＝１）（ステップＳ１２８ａ−θ（ｊ））。次に、判定部１２２−θ（ｊ）が文書ｍおよび要素ｓ*ｉ，ｊ−１を入力とし、ｓ*ｉ，ｊ−１∈Ｉ（ｊ）であるかを判定する（ステップＳ１２２−θ（ｊ））。ｉ∈Ｉ（ｊ）である場合、判定部１２２−θ（ｊ）は、文書ｍおよび要素ｓ*ｉ，ｊ−１を第１処理部１２４−θ（ｊ）に送り、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝である場合、判定部１２２−θ（ｊ）は、文書ｍおよび要素ｓ*ｉ，ｊ−１を第２処理部１２５−θ（ｊ）に送る。
【００５１】
第１処理部１２４−θ（ｊ）は、記憶部１２７−θ（ｊ）から係数αｉおよび鍵ｋ*ｉを抽出し、マスター公開鍵ｍｐｋと送られた要素ｓ*ｉ，ｊ−１を用い、要素ｓ*ｉ，ｊ：＝ｓ*ｉ，ｊ−１＋αｉｋ*ｉ＋γｉ，ｊ，１ｂ*ｉ，１＋γｉ，ｊ，２ｂ*ｉ，２＋…＋γｉ，ｊ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）（ただし、ｉ∈Ｉ（ｊ））を得、文書ｍおよび要素ｓ*ｉ，ｊを出力する。｛γｉ，ｊ，ι｝ι∈｛１，…，Ｎ（ｉ）｝は、文書ｍ（署名対象）に対応する情報Ｍｅｓを要素に含む第１集合に対応する係数集合である。文書ｍに対応する情報Ｍｅｓの例は、例えばハッシュ値Ｈ（ｍ｜ｔｅｘｔ）である。前述の関係（式（３））を満たすのであれば、係数γｉ，ｊ，ιはランダム値であっても定数であっても、ランダム値または定数と情報Ｍｅｓやマスター公開鍵ｍｐｋとによって定まる値でもよい（ステップＳ１２４−θ（ｊ））。
【００５２】
一方、第２処理部１２５−θ（ｊ）は、マスター公開鍵ｍｐｋと送られた要素ｓ*ｉ，ｊ−１を用い、要素ｓ*ｉ，ｊ：＝ｓ*ｉ，ｊ−１＋γｉ，ｊ，１ｂ*ｉ，１＋γｉ，ｊ，２ｂ*ｉ，２＋…＋γｉ，ｊ，Ｎ（ｉ）ｂ*ｉ，Ｎ（ｉ）（ただし、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝）を得、文書ｍおよび要素ｓ*ｉ，ｊを出力する（ステップＳ１２５−θ（ｊ））。
【００５３】
制御部１２８−θ（ｊ）は、ｉ＝Ｌであるかを判定する（Ｓ１２８ｂ−θ（ｊ））。ｉ≠Ｌであれば、制御部１２８−θ（ｊ）はｉ＋１を新たなｉとし（ｉ：＝ｉ＋１）、処理をステップＳ１２２−θ（ｊ）に戻す（ステップＳ１２８ｃ−θ（ｊ））。一方、ｉ＝Ｌであれば、出力部１２６−θ（ｊ）は、ｉ∈｛１，...，Ｌ｝についての要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とし、文書ｍおよび代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝を出力する。
【００５４】
１≦ｊ＜ｋである場合、代理署名装置１２−θ（ｊ）から出力された文書ｍおよび代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝は、次の代理署名装置１２−θ（ｊ＋１）の入力部１２１−θ（ｊ＋１）に入力される。ｊ＝ｋである場合、代理署名装置１２−θ（ｋ）の出力部１２６−θ（ｋ）は、｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝を署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝とし、文書ｍおよび署名ｓ*＝（｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝，ｇＴｓ０，ｔｅｘｔ，σ）を出力する。
【００５５】
《Ｖｅｒ》
次に、署名検証装置１３による署名ｓ*の検証処理を説明する。
図９に例示するように、署名検証装置１３の入力部１２１−θ（ｊ）に文書ｍおよび署名ｓ*が入力される（ステップＳ１３１）。文書ｍおよびｔｅｘｔは検証情報生成部１３３に送られ、署名ｓ*の｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝およびｇＴｓ０は検証部１３４に送られ、ディジタル署名σ、ｇＴｓ０およびｔｅｘｔは検証部１３８に送られる。
【００５６】
検証情報生成部１３３は、文書ｍおよびｔｅｘｔを入力とし、文書ｍ（署名対象）に対応する情報Ｍｅｓ（例えばハッシュ値Ｈ（ｍ｜ｔｅｘｔ））を要素に含む第２集合に対応する係数集合｛υｉ，ι｝ι∈｛１，…，Ｎ（ｉ）｝からｃｉ：＝υｉ，１ｂｉ，１＋…＋υｉ，Ｎ（ｉ）ｂｉ，Ｎ（ｉ）（ただし、ｉ∈｛１，…，Ｌ｝）を得る。検証情報生成部１３３はｃｉの集合である検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝を出力する。前述の関係（式（３））を満たすのであれば、係数υｉ，ιはランダム値であっても定数であっても、ランダム値または定数と情報Ｍｅｓやマスター公開鍵ｍｐｋとによって定まる値でもよい（ステップＳ１３３）。
【００５７】
検証部１３４は、検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝、｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝およびｇＴｓ０を入力とし、
【数１６】
2015136049.tif 000018
を満たすかを判定する（ステップＳ１３４）。式（１６）の関係を満たさない場合、出力部１３５は０（不合格を意味する）を出力する（ステップＳ１３５ｂ）。
【００５８】
一方、式（１６）の関係を満たす場合、検証部１３８は、ディジタル署名σ、ｇＴｓ０およびｔｅｘｔを入力とし、マスター公開鍵ｍｐｋの検証鍵ｖｋＡを用い、ディジタル署名σの検証ＶｅｒＡ（ｖｋＡ,σ,ｇＴｓ０｜ｔｅｘｔ）を行う（ステップＳ１３８）。この検証が合格ＶｅｒＡ（ｖｋＡ,σ,ｇＴｓ０｜ｔｅｘｔ）＝１であれば、出力部１３５は１（合格を意味する）を出力する（ステップＳ１３５ａ）。この検証が不合格ＶｅｒＡ（ｖｋＡ,σ,ｇＴｓ０｜ｔｅｘｔ）≠１であれば、出力部１３５は０（不合格を意味する）を出力する（ステップＳ１３５ｂ）。
【００５９】
＜正しく生成された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝が式（１６）を満たす理由＞
以下に正しく生成された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝が式（１６）を満たす理由を説明する。
式（１６）を変形すると以下のようになる。
【数１７】
2015136049.tif 000019
【００６０】
上述した式（８）の関係から、式（１７）は以下のように変形できる。
【数１８】
2015136049.tif 000020
【００６１】
式（３）（１４）の関係より、式（１８）は以下のように変形できる。
【数１９】
2015136049.tif 000021
【００６２】
［第２実施形態］
第２実施形態では、より具体的な方式を説明する。すなわち、第２実施形態では、Ｎ（ｉ）＝８であり、βｉ，１＝βｉ，３＝βｉ，４＝βｉ，５＝βｉ，６＝βｉ，８＝０、βｉ，２＝ｓ’ｉ、βｉ，７＝φｉであり、φｉがランダム値であり、
【数２０】
2015136049.tif 000022
を満たす。また、ｓ*ｉ，０＝０であり、γｉ，ｊ，１＝ｒｉ，ｊπ、γｉ，ｊ，２＝ｒ’ｉ，ｊ、γｉ，ｊ，３＝τｉ，ｊ、γｉ，ｊ，４＝τｉ，ｊＭｅｓ、γｉ，ｊ，７＝ｒｉ，ｊφ〜ｉ，１＋ｒ*ｉ、γｉ，ｊ，５＝γｉ，ｊ，６＝γｉ，ｊ，８＝０であり、π，τｉ，ｊ，φ〜ｉ，１，ｒ*ｉ，ｒｉ，ｊ，ｒ’ｉ，ｊがランダム値であり、ｒ１，ｊ＋…＋ｒＬ，ｊ＝０およびｒ’１，ｊ＋…＋ｒ’Ｌ，ｊ＝０を満たす。さらに、υｉ，１＝１、υｉ，２＝υ、υｉ，３＝τ’ｉＭｅｓ、υｉ，４＝−τ’ｉ、υｉ，８＝ηｉ、υｉ，５＝υｉ，６＝υｉ，７＝０であり、τ’ｉ，ηｉがランダム値であり、υが任意値である。
以下では、第１実施形態との相違点を中心に説明し、共通する事項については同一の参照番号を引用して説明を省略する。
【００６３】
＜構成＞
図１に例示するように、本形態の代理署名システム２は、署名管理装置（鍵生成装置）２１、ｎ個の代理署名装置２２−１〜２２−ｎ（これらはＵ（１），…，Ｕ（ｎ）に相当する）、および署名検証装置２３を有し、これらはネットワークを介して通信可能に構成されている。各装置は、例えば、汎用または専用のコンピュータに所定のプログラムが読み込まれて構成される装置である。
【００６４】
図２に例示するように、本形態の署名管理装置２１は、セットアップ部２１１、ランダム値生成部１１２，２１２、分散値生成部１１３，２１３、復元値生成部１１４、署名部１１４１、鍵生成部２１５、線形結合係数生成部１１６、記憶部１１７、制御部１１８、および出力部１１９を有する。
【００６５】
図３に例示するように、本形態では代理署名装置２２−１〜２２−ｎからなる集合Ｎｓｅｔの部分集合Ｋｓｕｂｓｅｔをなすｋ個の代理署名装置２２−θ（１）〜２２−θ（ｋ）（これらはＵ（θ（１）），…，Ｕ（θ（ｋ）に相当する）に署名権限が委譲され、代理署名装置２２−θ（１）〜２２−θ（ｋ）がＳｉｇθ（１）〜Ｓｉｇθ（ｋ）（すなわち、Ｓｉｇ）を実行して署名ｓ*を生成する。前述のように、部分集合Ｋｓｕｂｓｅｔの設定方法に制限はない。図４に例示するように、代理署名装置２２−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）は、入力部１２１−θ（ｊ）、判定部１２２−θ（ｊ）、第１処理部２２４−θ（ｊ）、第２処理部２２５−θ（ｊ）、出力部１２６−θ（ｊ）、記憶部１２７−θ（ｊ）、制御部１２８−θ（ｊ）、およびランダム値生成部２２３−θ（ｊ）を有する。なお、その他の代理署名装置２２−ｚ（ただし、ｚ∈｛１，...，ｎ｝）の構成も同様である（図４のθ（ｊ）をｚに置換した構成）。
【００６６】
図５に例示するように、本形態の署名検証装置２３は、入力部１３１、検証情報生成部２３３、検証部１３４，１３８、出力部１３５、記憶部１３６、制御部１３７、およびランダム値生成部２３２を有する。
【００６７】
＜処理＞
次に各処理を説明する。
《Ｓｅｔｕｐ》
署名管理装置２１のセットアップ部２１１は、第１実施形態で説明したように、ｐａｒａｍＧ、ｇＴ、Ｈ、（ｓｋＡ，ｖｋＡ）を生成して出力する。
【００６８】
セットアップ部１１１は、ｔ＝１，...，ｄについて以下を設定する。ただし、ｄは単調スパンプログラムを構成する行列Ｍの行のサイズＬの最大値である。
【００６９】
ＤＰＶＳのパラメータｐａｒａｍＶ（ｔ）：
ｐａｒａｍＶ（ｔ）：＝（ｑ，Ｖｔ，Ｖ＊ｔ，ＧＴ，Ａｔ，Ａ＊ｔ，ｅ）：＝Ｇｄｐｖｓ（１λ，８，ｐａｒａｍＧ）
ただし、Ｇ＝Ｇ＊の場合には、ｐａｒａｍＶ（ｔ）：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）でもよい。
【００７０】
行列（χｔ，ι，ζ）ι，ζ，（θｔ，ι，ζ）ι，ζ：
Ｘｔ：＝（χｔ，ι，ζ）ι，ζ←ＵＧＬ（８，Ｆｑ）
（θｔ，ι，ζ）ι，ζ：＝κ・（ＸｔＴ）−１
【００７１】
基底Ｂｔ，Ｂ*ｔ：
【数２１】
2015136049.tif 000023
【００７２】
基底Ｂ＾ｔ，Ｂ*＾ｔ：
【数２２】
2015136049.tif 000024
【００７３】
セットアップ部２１１は、ｍｓｋ：＝（｛Ｂ*ｔ｝ｔ∈｛１，...，ｄ｝，ｓｋＡ）、ｍｐｋ：＝（｛ｐａｒａｍＶ（ｔ），Ｂ＾ｔ，Ｂ*＾ｔ｝ｔ∈｛１，...，ｄ｝，ｇＴ，ｖｋＡ，Ｈ）を生成して出力する。マスター秘密鍵ｍｓｋは署名管理装置２１の記憶部１１７に安全に格納される。マスター公開鍵ｍｐｋは、記憶部１１７に格納される他、代理署名装置２２−１〜２２ｎおよび署名検証装置２３にも送られ、各装置で利用可能なように設定される。
【００７４】
《ＰＳｅｔｕｐ》
署名管理装置２１は、第１実施形態で説明したように、アルゴリズムＰＳｅｔｕｐを用いて、一般アクセス構造（単調スパンプログラム）Ｓ：＝（Ｍ，ρ）をもつ分散署名鍵を作成する（図６）。
【００７５】
図７に例示するように、署名管理装置２１は、第１実施形態で説明したようにステップＳ１１２〜Ｓ１１４、およびＳ１１４１の処理を実行する。その後、署名管理装置２１のランダム値生成部２１２は、Ｒ個の有限体Ｆｑの元からなり、０：＝ＳＥ→・ｆ’→（ただし、ＳＥ→＝Ｍ０）となるＲ次元ベクトルｆ’→←ＵＦｑＲを得て出力する（ステップＳ２１２）。次に、分散値生成部２１３は、行列Ｍ及びＲ次元ベクトルｆ’→を入力として、任意値（分散値）ｓ’ｉからなる（ｓ’１，…，ｓ’Ｌ）Ｔ：＝Ｍ・（ｆ’→）Ｔを得て出力する（ステップＳ２１３）。ここで、０＝Ｍ０（ｆ→）Ｔ、ｓ’ｉ＝Ｍｉ（ｆ’→）Ｔ（ただし、ｉ∈｛１，…，Ｌ｝）、およびＭ０∈ｓｐａｎ＜ＭΓ＞であるため、分散値ｓ’ｉ（ただし、ｉ∈∪ｊ∈｛１，…，ｋ｝Ｉ（ｊ））の線形結合は０である。言い換えると、第１実施形態で説明したαｉ∈Ｆｑに対して
【数２３】
2015136049.tif 000025
を満たす。
【００７６】
署名部１１４１は、第１実施形態で説明したステップＳ１１４１の処理を実行し、鍵生成部２１５は、基底の集合｛Ｂ*ｔ｝ｔ∈｛１，...，ｄ｝を用い、各ｉ∈｛１，...，Ｌ｝に対して鍵
【数２４】
2015136049.tif 000026
を得て出力する（ステップＳ２１５）。
【００７７】
鍵生成部２１５は、部分集合Ｉ（ｚ）（ただし、ｚ∈｛１，...，ｎ｝）に対応する鍵ｋ*ｉからなる鍵集合｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）を鍵ｓｋｚ＝｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）とし、公開情報ｐｋｐｓｅｔｕｐ：＝（ｇＴｓ０，ｔｅｘｔ，σ，Ｓ：＝（Ｍ，ρ））とし、分散署名鍵の集合｛ｓｋｐｓｅｔｕｐ（ｚ）｝ｚ∈｛１，...，ｎ｝：＝｛（ｐｋｐｓｅｔｕｐ，ｓｋｚ）｝ｚ∈｛１，...，ｎ｝を得て出力する。各鍵ｓｋｚ＝｛ｋ*ｉ｝ｉ∈Ｉ（ｚ）は、それぞれに対応する代理署名装置２２−ｚ（ただし、ｚ∈｛１，...，ｎ｝）へ安全に送られ、それぞれの記憶部１２７−ｚに格納される。ｐｋｐｓｅｔｕｐは、各代理署名装置２２−ｚ（ただし、ｚ∈｛１，...，ｎ｝）および署名検証装置２３に送られ、各装置が利用可能なように設定される。
【００７８】
≪Ｓｉｇ≫
次に、ｋ個の代理署名装置２２−θ（１）〜２２−θ（ｋ）∈ＫｓｕｂｓｅｔがＳｉｇθ（１）〜Ｓｉｇθ（ｋ）（すなわち、Ｓｉｇ）を実行して署名ｓ*を生成する処理を説明する（図３）。
【００７９】
まず、署名管理装置２１の線形結合係数生成部１１６が、第１実施形態で説明した係数集合｛αｉ｝ｉ∈Ｉ（ｊ）を生成して出力する。各係数集合｛αｉ｝ｉ∈Ｉ（ｊ）は、例えば、対応する代理署名装置２２−θ（ｊ）に送られ、記憶部１２７−θ（ｊ）に安全に格納される。或いは、すべての係数集合｛αｉ｝ｉ∈Ｉ（ｊ）が代理署名装置２２−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）に送られて共有され、すべての記憶部１２７−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）に格納されてもよい。
【００８０】
その後、代理署名装置２２−θ（１），...，代理署名装置２２−θ（ｋ）の順に、それぞれがＳｉｇθ（１），...，Ｓｉｇθ（ｋ）を実行する。
図８に例示するように、Ｓｉｇθ（ｊ）では、代理署名装置２２−θ（ｊ）（ただし、ｊ∈｛１，...，ｋ｝）の入力部１２１−θ（ｊ）に、署名対象の文書ｍと代理署名装置２２−θ（ｊ−１）から出力された代理署名情報｛ｓ*ｉ，ｊ−１｝ｉ∈｛１，…，Ｌ｝が入力される（ステップＳ１２１−θ（ｊ−１））。ただし、ｊ＝１の場合の代理署名情報｛ｓ*ｉ，０｝ｉ∈｛１，…，Ｌ｝は、初期設定されたｓ*ｉ，０：＝０の集合である。
【００８１】
ランダム値生成部２２３−θ（ｊ）は、ｒ１，ｊ＋…＋ｒＬ，ｊ＝０の関係を満たすランダム値（ｒｉ，ｊ）ｉ∈｛１，...，Ｌ｝←ＵＦｑＬおよびｒ’１，ｊ＋…＋ｒ’Ｌ，ｊ＝０を満たすランダム値（ｒ’ｉ，ｊ）ｉ∈｛１，...，Ｌ｝←ＵＦｑＬを得て出力する（ステップＳ２２３ａ−θ（ｊ））。
【００８２】
ランダム値生成部２２３−θ（ｊ）は、さらに、ランダム値（τｉ，ｊ）ｉ∈｛１，...，Ｌ｝←ＵＦｑＬおよび（ｒ*ｉ，ｊ）ｉ∈｛１，...，Ｌ｝←ＵＦｑＬを得て出力する（ステップＳ２２３ｂ−θ（ｊ））。
【００８３】
制御部１２８−θ（ｊ）は、ｉを１に設定する（ｉ：＝１）（ステップＳ１２８ａ−θ（ｊ））。次に、判定部１２２−θ（ｊ）が文書ｍおよび要素ｓ*ｉ，ｊ−１を入力とし、ｓ*ｉ，ｊ−１∈Ｉ（ｊ）であるかを判定する（ステップＳ１２２−θ（ｊ））。ｉ∈Ｉ（ｊ）である場合、判定部１２２−θ（ｊ）は、文書ｍおよび要素ｓ*ｉ，ｊ−１を第１処理部２２４−θ（ｊ）に送り、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝である場合、判定部１２２−θ（ｊ）は、文書ｍおよび要素ｓ*ｉ，ｊ−１を第２処理部２２５−θ（ｊ）に送る。
【００８４】
第１処理部１２４−θ（ｊ）は、記憶部１２７−θ（ｊ）から係数αｉおよび鍵ｋ*ｉを抽出し、マスター公開鍵ｍｐｋと送られた要素ｓ*ｉ，ｊ−１とランダム値ｒｉ，ｊ，ｒ’ｉ，ｊ，τｉ，ｊ，ｒ*ｉ，ｊを用い、要素
【数２５】
2015136049.tif 000027
（ただし、ｉ∈Ｉ（ｊ））を得、文書ｍおよび要素ｓ*ｉ，ｊを出力する（ステップＳ２２４−θ（ｊ））。
【００８５】
一方、第２処理部２２５−θ（ｊ）は、マスター公開鍵ｍｐｋと送られた要素ｓ*ｉ，ｊ−１とランダム値ｒｉ，ｊ，ｒ’ｉ，ｊ，τｉ，ｊ，ｒ*ｉ，ｊを用い、要素
【数２６】
2015136049.tif 000028
（ただし、ｉ∈Ｉ（ｊ）ではないｉ∈｛１，…，Ｌ｝）を得、文書ｍおよび要素ｓ*ｉ，ｊを出力する（ステップＳ２２５−θ（ｊ））。
【００８６】
制御部１２８−θ（ｊ）は、ｉ＝Ｌであるかを判定する（Ｓ１２８ｂ−θ（ｊ））。ｉ≠Ｌであれば、制御部１２８−θ（ｊ）はｉ＋１を新たなｉとし（ｉ：＝ｉ＋１）、処理をステップＳ１２２−θ（ｊ）に戻す（ステップＳ１２８ｃ−θ（ｊ））。一方、ｉ＝Ｌであれば、出力部１２６−θ（ｊ）は、ｉ∈｛１，...，Ｌ｝についての要素ｓ*ｉ，ｊの集合を代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝とし、文書ｍおよび代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝を出力する。
【００８７】
１≦ｊ＜ｋである場合、代理署名装置２２−θ（ｊ）から出力された文書ｍおよび代理署名情報｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝は、次の代理署名装置２２−θ（ｊ＋１）の入力部１２１−θ（ｊ＋１）に入力される。ｊ＝ｋである場合、代理署名装置２２−θ（ｋ）の出力部１２６−θ（ｋ）は、｛ｓ*ｉ，ｊ｝ｉ∈｛１，…，Ｌ｝を署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝とし、文書ｍおよび署名ｓ*＝（｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝，ｇＴｓ０，ｔｅｘｔ，σ）を出力する。
【００８８】
《Ｖｅｒ》
次に、署名検証装置２３による署名ｓ*の検証処理を説明する。
図９に例示するように、署名検証装置２３の入力部１２１−θ（ｊ）に文書ｍおよび署名ｓ*が入力される（ステップＳ１３１）。文書ｍおよびｔｅｘｔは検証情報生成部２３３に送られ、署名ｓ*の｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝およびｇＴｓ０は検証部１３４に送られ、ディジタル署名σ、ｇＴｓ０およびｔｅｘｔは検証部１３８に送られる。
【００８９】
ランダム値生成部２３２は、ランダム値（ηｉ）ｉ∈｛１，…，Ｌ｝←ＵＦｑＬおよび（τ’ｉ）ｉ∈｛１，…，Ｌ｝←ＵＦｑＬを得て出力する（ステップＳ２３２）。検証情報生成部２３３は、文書ｍ、ｔｅｘｔ、ランダム値（ηｉ）ｉ∈｛１，…，Ｌおよび（τ’ｉ）ｉ∈｛１，…，Ｌ｝を入力とし、υを任意値（定数またはランダム値）υ∈Ｆｑとし、ｉ∈｛１，…，Ｌ｝について
【数２７】
2015136049.tif 000029
を得る。検証情報生成部２３３はｃｉの集合である検証情報｛ｃｉ｝ｉ∈｛１，…，Ｌ｝を出力する（ステップＳ２３３）。以降の処理は第１実施形態と同じである。
【００９０】
＜正しく生成された署名｛ｓ*ｉ｝ｉ∈｛１，…，Ｌ｝が式（１６）を満たす理由＞
本形態の場合、式（１６）を変形すると以下のようになる。
【数２８】
2015136049.tif 000030
【００９１】
式（１４）（２１）の関係、（ｒｉ，ｊ）ｉ∈｛１，...，Ｌ｝および（ｒ’ｉ，ｊ）ｉ∈｛１，...，Ｌ｝がｒ１，ｊ＋…＋ｒＬ，ｊ＝０およびｒ’１，ｊ＋…＋ｒ’Ｌ，ｊ＝０の関係を満たすことから、式（２２）は以下のように変形できる。
【数２９】
2015136049.tif 000031
【００９２】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。例えば、複数個の代理署名装置が同一のコンピュータ上に実装されてもよいし、少なくとも一部の代理署名装置と署名検証装置とが同一のコンピュータ上に実装されてもよい。
【００９３】
また、上述したランダム値に代えて定数等の任意値が用いられてもよい。また、安全性の観点から有限体Ｆｑの位数と群Ｇ，Ｇ*，ＧＴの位数とが同一であることが好ましいが、これらの位数が互いに異なっていてもよい。また、安全性の観点から位数は素数であることが好ましいが、位数が素数以外の正の整数であってもよい。また、通常のディジタル署名を用いない構成であってもよい。有限体に代えて有限環を用いてもよい。また、署名管理装置１１が係数集合｛αｉ｝ｉ∈Ｉ（ｊ）を生成するのではなく、何れかの代理署名装置、署名検証装置、その他の装置が係数集合｛αｉ｝ｉ∈Ｉ（ｊ）を生成してもよい。
【００９４】
また、第１実施形態において、νｉ，１，１が０以外のランダム値であり、νｉ，１，２，…，νｉ，１，Ｎ（ｉ）が任意値であり、｛ｂ〜*ｉ，１｝ｉ∈Ｉ（ｊ）がｂ〜*ｉ，１：＝νｉ，１，１ｂ*ｉ，１＋νｉ，１，２ｂ*ｉ，２＋…＋νｉ，１，Ｎ（ｉ）ｂ*ｉ，１，Ｎ（ｉ）の集合であり、ｂ*ｉ，１は秘匿されており、第１処理部１２４−θ（ｊ）と第２処理部１２５−θ（ｊ）は、｛ｂｉ，２，…，ｂｉ，Ｎ（ｉ）｝ｉ∈Ｉ（ｊ）の少なくとも一部と集合｛ｂ〜*ｉ，１｝ｉ∈Ｉ（ｊ）とを用いて要素ｓ*ｉ，ｊを得てもよい。これにより、少なくともｂ*ｉ，１が秘匿されるため、安全性が向上する。
【００９５】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。例えば、第２実施形態のステップＳ２２３ｂ−θ（ｊ）に代えて、ステップＳ１２２−θ（ｊ）とステップＳ２２４−θ（ｊ），Ｓ２２５−θ（ｊ）との間にτｉ，ｊおよびｒ*ｉ，ｊを得てもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００９６】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００９７】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００９９】
上記実施形態では、ＣＰＵ等のハードウェアプロセッサやＲＡＭ等のメモリを有するコンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１００】
１，２  代理署名システム
１１，２１  署名管理装置（鍵生成装置）
１２−１〜１２−ｎ，２２−１〜２２−ｎ  代理署名装置
１３，２３  署名検証装置
【図１】
2015136049.tif 000039
【図２】
2015136049.tif 000040
【図３】
2015136049.tif 000041
【図４】
2015136049.tif 000042
【図５】
2015136049.tif 000043
【図６】
2015136049.tif 000044
【図７】
2015136049.tif 000045
【図８】
2015136049.tif 000046
【図９】
2015136049.tif 000047