(57)【特許請求の範囲】
【請求項１】
Ｇを離散対数問題が難しい位数ｑの巡回群、
ｇを巡回群Ｇの生成元、
Ｚｑを位数ｑの加法群、
Ｈを０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ’を０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ”を０と１からなる任意長さのビット列の集合を定義域とし加法群Ｚｑを値域とするハッシュ関数、
ｍをメッセージとし、
ｎ台（ｎは２以上の予め定められた整数）の参加者装置（以下、ｎ台の参加者装置の集合を集合Ｎとする）に含まれるｓ台の参加者装置（以下、ｓ台の参加者装置の集合を集合Ｓとする）が電子署名を行う電子署名方法であって、
集合Ｎに属する各参加者装置ｉ（ｉ＝１，…，ｎ）の鍵生成部が、秘密鍵ｘｉ∈Ｚｑを選択し、公開鍵ｙｉ＝ｇ＾ｘｉ∈Ｇを生成するステップと、
署名生成装置の集合選定部が、Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合Ｔに属する参加者装置（ただし、集合Ｔに属する参加者装置はｔ台とする）と集合Ｔ’に属する参加者装置（ただし、集合Ｔ’に属する参加者装置はｔ’台とする）とをそれぞれ集合Ｎから選定するステップと、
署名生成装置の選定部が、０と１からなるｋビットのビット列ｒを選定するステップと、
集合Ｓに属する各参加者装置ｉ（ｉ＝１，…，ｓ）の鍵生成部が、秘密鍵ｘｉを用いて、使い捨て公開鍵σｉ＝ｈ＾ｘｉ（ただし、ｈ＝Ｈ（ｎ，ｔ，ｔ’,ｙ１，…，ｙｎ，ｍ，ｒ）∈Ｇ）を生成するステップと、
署名生成装置の使い捨て公開鍵選定部が、集合Ｔ’−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｔ’）の使い捨て公開鍵σｉを巡回群Ｇから任意に選定するステップと、
署名生成装置の計算部が、集合Ｔ’に属する各参加者装置ｉ（ｉ＝１，…，ｔ’）の使い捨て公開鍵σｉ（ｉ＝１，…，ｔ’）を用いて、
【数１】
0004790422.tif 000023
とし、
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ，ｒ）∈Ｇ、
【数２】
0004790422.tif 000024
（ｊ＝１，…，ｔ’）とし、集合Ｎ−Ｔ’に属する各参加者装置（ｉ＝ｔ’＋１，…，ｎ）の使い捨て公開鍵
【数３】
0004790422.tif 000025
を計算するステップと、
集合Ｓに属する各参加者装置ｉ（ｉ＝１，…，ｓ）の計算部が、任意の元ｗｉ∈Ｚｑを選定し、当該元ｗｉを用いて、ａｉ＝ｇ＾ｗｉ∈Ｇとｂｉ＝ｈ＾ｗｉ∈Ｇを生成するステップと、
署名生成装置の元生成部が、集合Ｎ−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｎ）に対応する任意のｚｉ∈Ｚｑと任意のｃｉ∈Ｚｑを選定し、ａｉ＝（ｇ＾ｚｉ）（ｙｉ＾ｃｉ）∈Ｇとｂｉ＝（ｈ＾ｚｉ）（σｉ＾ｃｉ）∈Ｇとを生成するステップと、
署名生成装置の元選定部が、集合Ｓ−Ｔに属する各参加者装置ｉ（ｉ＝ｔ＋１，…，ｓ）に対応する任意の元ｃｉ∈Ｚｑを選定するステップと、
署名生成装置の多項式計算部が、
β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,r,h,A0,…,At’,a1,…,an,b1,…,bn)∈Ｚｑ
β（ｉ）＝ｃｉ∈Ｚｑ（ただし、ｉ＝ｔ＋１，…，ｎ）
を満足する次数（ｎ−ｔ）の多項式β（ｘ）∈Ｚｑ［ｘ］を求めるステップと、
集合Ｓに属する各参加者装置ｉ（ｉ＝１，…，ｓ）の計算部が、秘密鍵ｘｉを用いて、ｚｉ＝ｗｉ−β（ｉ）ｘｉ∈Ｚｑを求めるステップと、
署名生成装置の署名生成部が、電子署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ）を出力するステップと
を有する電子署名方法。
【請求項２】
請求項１に記載の電子署名方法によって生成された上記電子署名σの検証方法であって、
署名検証装置の検証部が、
請求項１に記載の電子署名方法で用いられた巡回群Ｇ、巡回群Ｇの生成元ｇ、加法群Ｚｑ、ハッシュ関数Ｈ、ハッシュ関数Ｈ’、ハッシュ関数Ｈ”、ｎ、ｔ、ｔ’、集合Ｎに属する各参加者装置ｉ（ｉ＝１，…，ｎ）の公開鍵ｙ１，…，ｙｎ、メッセージｍ、電子署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ）を用いて、
電子署名σに含まれるｒが０と１のビット列であること、ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ，ｒ）が巡回群Ｇの元であること、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ，ｒ）が巡回群Ｇの元であること、電子署名σに含まれるＡ１，…，Ａｔ’がそれぞれ巡回群Ｇの元であること、電子署名σに含まれるｚ１，…，ｚｎがそれぞれ加法群Ｚｑの元であること、を確認するステップと、
【数４】
0004790422.tif 000026
で求められるσｉ（ｉ＝１，…，ｎ）が巡回群Ｇの元であることを確認するステップと、
電子署名σに含まれる多項式β（ｘ）、ｚ１，…，ｚｎを用いて、
【数５】
0004790422.tif 000027
（ｉ＝１，…，ｎ）を求め、電子署名σに含まれる多項式β（ｘ）の各係数が加法群Ｚｑの元であること、多項式β（ｘ）の次数がｎ−ｔであること、β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,r,h,A0,…,At’,a1’,…,an’,b1’,…,bn’)であることを確認するステップと
を有する検証方法。
【請求項３】
Ｇを離散対数問題が難しい位数ｑの巡回群、
ｇ、Ｒをそれぞれ巡回群Ｇの生成元、
Ｚｑを位数ｑの加法群、
Ｈを０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ’を０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ”を０と１からなる任意長さのビット列の集合を定義域とし加法群Ｚｑを値域とするハッシュ関数、
ｍをメッセージとし、
ｎ台（ｎは２以上の予め定められた整数）の参加者装置（以下、ｎ台の参加者装置の集合を集合Ｎとする）に含まれるｓ台の参加者装置（以下、ｓ台の参加者装置の集合を集合Ｓとする）が電子署名を行う電子署名方法であって、
集合Ｎに属する各参加者装置ｉ（ｉ＝１，…，ｎ）の鍵生成部が、秘密鍵ｘｉ∈Ｚｑを選択し、公開鍵ｙｉ＝ｇ＾ｘｉ∈Ｇを生成するステップと、
署名生成装置の集合選定部が、Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合Ｔに属する参加者装置（ただし、集合Ｔに属する参加者装置はｔ台とする）と集合Ｔ’に属する参加者装置（ただし、集合Ｔ’に属する参加者装置はｔ’台とする）とをそれぞれ集合Ｎから選定するステップと、
集合Ｓに属する各参加者装置ｉ（ｉ＝１，…，ｓ）の鍵生成部が、任意の元ｘｉ’∈Ｚｑを選び、秘密鍵ｘｉ∈Ｚｑを用いて、使い捨て公開鍵σｉ＝（ｈ＾ｘｉ）（Ｒ＾ｘｉ’）（ただし、ｈ＝Ｈ（ｎ，ｔ，ｔ’,ｙ１，…，ｙｎ，ｍ）∈Ｇ）を生成するステップと、
署名生成装置の使い捨て公開鍵選定部が、集合Ｔ’−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｔ’）の使い捨て公開鍵σｉを巡回群Ｇから任意に選定するステップと、
署名生成装置の計算部が、集合Ｔ’に属する各参加者装置ｉ（ｉ＝１，…，ｔ’）の使い捨て公開鍵σｉ（ｉ＝１，…，ｔ’）を用いて、
【数６】
0004790422.tif 000028
とし、
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ）∈Ｇ、
【数７】
0004790422.tif 000029
（ｊ＝１，…，ｔ’）とし、集合Ｎ−Ｔ’に属する各参加者装置（ｉ＝ｔ’＋１，…，ｎ）の使い捨て公開鍵
【数８】
0004790422.tif 000030
を計算するステップと、
集合Ｓに属する各参加者装置ｉ（ｉ＝１，…，ｓ）の計算部が、任意の元ｗｉ、ｗｉ’∈Ｚｑを選定し、当該元ｗｉ、ｗｉ’を用いて、ａｉ＝ｇ＾ｗｉ∈Ｇとｂｉ＝（ｈ＾ｗｉ）（Ｒ＾ｗｉ’）∈Ｇを生成するステップと、
署名生成装置の元生成部が、集合Ｎ−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｎ）に対応する任意のｚｉ、ｚｉ’、ｃｉ∈Ｚｑを選定し、ａｉ＝（ｇ＾ｚｉ）（ｙｉ＾ｃｉ）∈Ｇとｂｉ＝（ｈ＾ｚｉ）（Ｒ＾ｚｉ’）（σｉ＾ｃｉ）∈Ｇとを生成するステップと、
署名生成装置の元選定部が、集合Ｓ−Ｔに属する各参加者装置ｉ（ｉ＝ｔ＋１，…，ｓ）に対応する任意の元ｃｉ∈Ｚｑを選定するステップと、
署名生成装置の多項式計算部が、
β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,h,A0,…,At’,a1,…,an,b1,…,bn)∈Ｚｑ
β（ｉ）＝ｃｉ∈Ｚｑ（ただし、ｉ＝ｔ＋１，…，ｎ）
を満足する次数（ｎ−ｔ）の多項式β（ｘ）∈Ｚｑ［ｘ］を求めるステップと、
集合Ｓに属する各参加者装置ｉ（ｉ＝１，…，ｓ）の計算部が、秘密鍵ｘｉ、ｘｉ’を用いて、ｚｉ＝ｗｉ−β（ｉ）ｘｉ∈Ｚｑ、ｚｉ’＝ｗｉ’−β（ｉ）ｘｉ’∈Ｚｑを求めるステップと、
署名生成装置の署名生成部が、電子署名σ＝（Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’）を出力するステップと
を有する電子署名方法。
【請求項４】
請求項３に記載の電子署名方法によって生成された上記電子署名σの検証方法であって、
署名検証装置の検証部が、
請求項３に記載の電子署名方法で用いられた巡回群Ｇ、巡回群Ｇの生成元ｇおよびＲ、加法群Ｚｑ、ハッシュ関数Ｈ、ハッシュ関数Ｈ’、ハッシュ関数Ｈ”、ｎ、ｔ、ｔ’、集合Ｎに属する各参加者装置ｉ（ｉ＝１，…，ｎ）の公開鍵ｙ１，…，ｙｎ、メッセージｍ、電子署名σ＝（Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’）を用いて、
ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ）が巡回群Ｇの元であること、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ）が巡回群Ｇの元であること、電子署名σに含まれるＡ１，…，Ａｔ’がそれぞれ巡回群Ｇの元であること、電子署名σに含まれるｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’がそれぞれ加法群Ｚｑの元であること、を確認するステップと、
【数９】
0004790422.tif 000031
で求められるσｉ（ｉ＝１，…，ｎ）が巡回群Ｇの元であることを確認するステップと、
電子署名σに含まれる多項式β（ｘ）、ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’を用いて、
【数１０】
0004790422.tif 000032
（ｉ＝１，…，ｎ）を求め、電子署名σに含まれる多項式β（ｘ）の各係数が加法群Ｚｑの元であること、多項式β（ｘ）の次数がｎ−ｔであること、β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,h,A0,…,At’,a1’,…,an’,b1’,…,bn’)であることを確認するステップと
を有する検証方法。
【請求項５】
Ｇを離散対数問題が難しい位数ｑの巡回群、
ｇを巡回群Ｇの生成元、
Ｚｑを位数ｑの加法群、
Ｈを０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ’を０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ”を０と１からなる任意長さのビット列の集合を定義域とし加法群Ｚｑを値域とするハッシュ関数、
ｍをメッセージとし、
ｎ台（ｎは２以上の予め定められた整数）の参加者装置（以下、ｎ台の参加者装置の集合を集合Ｎとする）に含まれるｓ台の参加者装置（以下、ｓ台の参加者装置の集合を集合Ｓとする）が電子署名を行う電子署名システムであって、
当該電子署名システムは、ｎ台の上記参加者装置ｉ（ｉ＝１，…，ｎ）と、署名生成装置とを含み、
秘密鍵ｘｉ∈Ｚｑを選択し、公開鍵ｙｉ＝ｇ＾ｘｉ∈Ｇを生成する手段Ａと、
Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合Ｔに属する参加者装置（ただし、集合Ｔに属する参加者装置はｔ台とする）と集合Ｔ’に属する参加者装置（ただし、集合Ｔ’に属する参加者装置はｔ’台とする）とをそれぞれ集合Ｎから選定する手段Ｂと、
０と１からなるｋビットのビット列ｒを選定する手段Ｃと、
秘密鍵ｘｉを用いて、使い捨て公開鍵σｉ＝ｈ＾ｘｉ（ただし、ｈ＝Ｈ（ｎ，ｔ，ｔ’,ｙ１，…，ｙｎ，ｍ，ｒ）∈Ｇ）を生成する手段Ｄと、
集合Ｔ’−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｔ’）の使い捨て公開鍵σｉを巡回群Ｇから任意に選定する手段Ｅと、
集合Ｔ’に属する各参加者装置ｉ（ｉ＝１，…，ｔ’）の使い捨て公開鍵σｉ（ｉ＝１，…，ｔ’）を用いて、
【数１１】
0004790422.tif 000033
とし、
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ，ｒ）∈Ｇ、
【数１２】
0004790422.tif 000034
（ｊ＝１，…，ｔ’）とし、集合Ｎ−Ｔ’に属する各参加者装置（ｉ＝ｔ’＋１，…，ｎ）の使い捨て公開鍵
【数１３】
0004790422.tif 000035
を計算する手段Ｆと、
任意の元ｗｉ∈Ｚｑを選定し、当該元ｗｉを用いて、ａｉ＝ｇ＾ｗｉ∈Ｇとｂｉ＝ｈ＾ｗｉ∈Ｇを生成する手段Ｇと、
集合Ｎ−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｎ）に対応する任意のｚｉ∈Ｚｑと任意のｃｉ∈Ｚｑを選定し、ａｉ＝（ｇ＾ｚｉ）（ｙｉ＾ｃｉ）∈Ｇとｂｉ＝（ｈ＾ｚｉ）（σｉ＾ｃｉ）∈Ｇとを生成する手段Ｈと、
集合Ｓ−Ｔに属する各参加者装置ｉ（ｉ＝ｔ＋１，…，ｓ）に対応する任意の元ｃｉ∈Ｚｑを選定する手段Ｉと、
β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,r,h,A0,…,At’,a1,…,an,b1,…,bn)∈Ｚｑ
β（ｉ）＝ｃｉ∈Ｚｑ（ただし、ｉ＝ｔ＋１，…，ｎ）
を満足する次数（ｎ−ｔ）の多項式β（ｘ）∈Ｚｑ［ｘ］を求める手段Ｊと、
秘密鍵ｘｉを用いて、ｚｉ＝ｗｉ−β（ｉ）ｘｉ∈Ｚｑを求める手段Ｋと、
電子署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ）を出力する手段Ｌ
のうち、
署名生成装置は、少なくとも手段Ｂ、手段Ｃ、手段Ｅ、手段Ｆ、手段Ｈ、手段Ｉ、手段Ｊ、手段Ｌを含み、
各参加者装置ｉは、少なくとも手段Ａ、手段Ｄ、手段Ｇ、手段Ｋを含み、
署名生成装置がｎ台の上記参加者装置ｉ（ｉ＝１，…，ｎ）のいずれか一つと一致する場合には、当該参加者装置は手段Ａ、手段Ｂ、手段Ｃ、手段Ｄ、手段Ｅ、手段Ｆ、手段Ｇ、手段Ｈ、手段Ｉ、手段Ｊ、手段Ｋ、手段Ｌを含む
電子署名システム。
【請求項６】
請求項１に記載の電子署名方法によって生成された上記電子署名σの検証を行う検証装置であって、
請求項１に記載の電子署名方法で用いられた巡回群Ｇ、巡回群Ｇの生成元ｇ、加法群Ｚｑ、ハッシュ関数Ｈ、ハッシュ関数Ｈ’、ハッシュ関数Ｈ”、ｎ、ｔ、ｔ’、集合Ｎに属する各参加者装置ｉ（ｉ＝１，…，ｎ）の公開鍵ｙ１，…，ｙｎ、メッセージｍ、電子署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ）を用いて、
電子署名σに含まれるｒが０と１のビット列であること、ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ，ｒ）が巡回群Ｇの元であること、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ，ｒ）が巡回群Ｇの元であること、電子署名σに含まれるＡ１，…，Ａｔ’がそれぞれ巡回群Ｇの元であること、電子署名σに含まれるｚ１，…，ｚｎがそれぞれ加法群Ｚｑの元であること、を確認する手段と、
【数１４】
0004790422.tif 000036
で求められるσｉ（ｉ＝１，…，ｎ）が巡回群Ｇの元であることを確認する手段と、
電子署名σに含まれる多項式β（ｘ）、ｚ１，…，ｚｎを用いて、
【数１５】
0004790422.tif 000037
（ｉ＝１，…，ｎ）を求め、電子署名σに含まれる多項式β（ｘ）の各係数が加法群Ｚｑの元であること、多項式β（ｘ）の次数がｎ−ｔであること、β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,r,h,A0,…,At’,a1’,…,an’,b1’,…,bn’)であることを確認する手段と
を含む検証装置。
【請求項７】
Ｇを離散対数問題が難しい位数ｑの巡回群、
ｇ、Ｒをそれぞれ巡回群Ｇの生成元、
Ｚｑを位数ｑの加法群、
Ｈを０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ’を０と１からなる任意長さのビット列の集合を定義域とし巡回群Ｇを値域とするハッシュ関数、
Ｈ”を０と１からなる任意長さのビット列の集合を定義域とし加法群Ｚｑを値域とするハッシュ関数、
ｍをメッセージとし、
ｎ台（ｎは２以上の予め定められた整数）の参加者装置（以下、ｎ台の参加者装置の集合を集合Ｎとする）に含まれるｓ台の参加者装置（以下、ｓ台の参加者装置の集合を集合Ｓとする）が電子署名を行う電子署名システムであって、
当該電子署名システムは、ｎ台の上記参加者装置ｉ（ｉ＝１，…，ｎ）と、署名生成装置とを含み、
秘密鍵ｘｉ∈Ｚｑを選択し、公開鍵ｙｉ＝ｇ＾ｘｉ∈Ｇを生成する手段Ａと、
Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合Ｔに属する参加者装置（ただし、集合Ｔに属する参加者装置はｔ台とする）と集合Ｔ’に属する参加者装置（ただし、集合Ｔ’に属する参加者装置はｔ’台とする）とをそれぞれ集合Ｎから選定する手段Ｂと、
任意の元ｘｉ’∈Ｚｑを選び、秘密鍵ｘｉ∈Ｚｑを用いて、使い捨て公開鍵σｉ＝（ｈ＾ｘｉ）（Ｒ＾ｘｉ’）（ただし、ｈ＝Ｈ（ｎ，ｔ，ｔ’,ｙ１，…，ｙｎ，ｍ）∈Ｇ）を生成する手段Ｃと、
集合Ｔ’−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｔ’）の使い捨て公開鍵σｉを巡回群Ｇから任意に選定する手段Ｄと、
集合Ｔ’に属する各参加者装置ｉ（ｉ＝１，…，ｔ’）の使い捨て公開鍵σｉ（ｉ＝１，…，ｔ’）を用いて、
【数１６】
0004790422.tif 000038
とし、
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ）∈Ｇ、
【数１７】
0004790422.tif 000039
（ｊ＝１，…，ｔ’）とし、集合Ｎ−Ｔ’に属する各参加者装置（ｉ＝ｔ’＋１，…，ｎ）の使い捨て公開鍵
【数１８】
0004790422.tif 000040
を計算する手段Ｅと、
任意の元ｗｉ、ｗｉ’∈Ｚｑを選定し、当該元ｗｉ、ｗｉ’を用いて、ａｉ＝ｇ＾ｗｉ∈Ｇとｂｉ＝（ｈ＾ｗｉ）（Ｒ＾ｗｉ’）∈Ｇを生成する手段Ｆと、
集合Ｎ−Ｓに属する各参加者装置ｉ（ｉ＝ｓ＋１，…，ｎ）に対応する任意のｚｉ、ｚｉ’、ｃｉ∈Ｚｑを選定し、ａｉ＝（ｇ＾ｚｉ）（ｙｉ＾ｃｉ）∈Ｇとｂｉ＝（ｈ＾ｚｉ）（Ｒ＾ｚｉ’）（σｉ＾ｃｉ）∈Ｇとを生成する手段Ｇと、
集合Ｓ−Ｔに属する各参加者装置ｉ（ｉ＝ｔ＋１，…，ｓ）に対応する任意の元ｃｉ∈Ｚｑを選定する手段Ｈと、
β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,h,A0,…,At’,a1,…,an,b1,…,bn)∈Ｚｑ
β（ｉ）＝ｃｉ∈Ｚｑ（ただし、ｉ＝ｔ＋１，…，ｎ）
を満足する次数（ｎ−ｔ）の多項式β（ｘ）∈Ｚｑ［ｘ］を求める手段Ｉと、
秘密鍵ｘｉ、ｘｉ’を用いて、ｚｉ＝ｗｉ−β（ｉ）ｘｉ∈Ｚｑ、ｚｉ’＝ｗｉ’−β（ｉ）ｘｉ’∈Ｚｑを求める手段Ｊと、
電子署名σ＝（Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’）を出力する手段Ｋ
のうち、
署名生成装置は、少なくとも手段Ｂ、手段Ｄ、手段Ｅ、手段Ｇ、手段Ｈ、手段Ｉ、手段Ｋを含み、
各参加者装置ｉは、少なくとも手段Ａ、手段Ｃ、手段Ｆ、手段Ｊを含み、
署名生成装置がｎ台の上記参加者装置ｉ（ｉ＝１，…，ｎ）のいずれか一つと一致する場合には、当該参加者装置は手段Ａ、手段Ｂ、手段Ｃ、手段Ｄ、手段Ｅ、手段Ｆ、手段Ｇ、手段Ｈ、手段Ｉ、手段Ｊ、手段Ｋを含む
電子署名システム。
【請求項８】
請求項３に記載の電子署名方法によって生成された上記電子署名σの検証を行う検証装置であって、
請求項３に記載の電子署名方法で用いられた巡回群Ｇ、巡回群Ｇの生成元ｇおよびＲ、加法群Ｚｑ、ハッシュ関数Ｈ、ハッシュ関数Ｈ’、ハッシュ関数Ｈ”、ｎ、ｔ、ｔ’、集合Ｎに属する各参加者装置ｉ（ｉ＝１，…，ｎ）の公開鍵ｙ１，…，ｙｎ、メッセージｍ、電子署名σ＝（Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’）を用いて、
ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ）が巡回群Ｇの元であること、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙ１，…，ｙｎ，ｍ）が巡回群Ｇの元であること、電子署名σに含まれるＡ１，…，Ａｔ’がそれぞれ巡回群Ｇの元であること、電子署名σに含まれるｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’がそれぞれ加法群Ｚｑの元であること、を確認する手段と、
【数１９】
0004790422.tif 000041
で求められるσｉ（ｉ＝１，…，ｎ）が巡回群Ｇの元であることを確認する手段と、
電子署名σに含まれる多項式β（ｘ）、ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’を用いて、
【数２０】
0004790422.tif 000042
（ｉ＝１，…，ｎ）を求め、電子署名σに含まれる多項式β（ｘ）の各係数が加法群Ｚｑの元であること、多項式β（ｘ）の次数がｎ−ｔであること、β（０）＝Ｈ”(n,t,t’,y1,…,yn,m,h,A0,…,At’,a1’,…,an’,b1’,…,bn’)であることを確認する手段と
を含む検証装置。
【請求項９】
署名者ｉに固有の秘密鍵ｘｉと、署名者ｉに固有の識別番号ｉ、メッセージｍと、全署名者に共通のラベルＬとを記憶する記憶手段と、
記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、署名者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成手段と、
固有臨時公開鍵生成因子生成手段によって生成された固有臨時公開鍵生成因子ｈと記憶手段に記憶される署名者ｉに固有の秘密鍵ｘｉとから署名者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉ、記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成手段と、
署名者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成手段によって生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよびメッセージｍに対する署名とする署名生成手段と
を備え、
固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉおよび撹乱臨時公開鍵生成手段によって生成された撹乱臨時公開鍵σｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕は、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能に、撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０および撹乱因子生成手段によって生成された撹乱因子Ａ１から生成可能である
ことを特徴とする署名装置。
【請求項１０】
メッセージｍと、全署名者に共通のラベルＬ、ラベルＬおよびメッセージｍに対する署名とを記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と
を備えたことを特徴とする検証装置。
【請求項１１】
各署名装置によって生成された署名および各署名に対応するメッセージｍと、全署名者に共通のラベルＬを記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と、
記憶手段に記憶される各署名装置によって生成された署名から異なる２つの署名ξ、ξ’およびこれら署名に対応するメッセージｍ、ｍ’を選択する選択制御手段と、
臨時公開鍵生成手段によって生成された、選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定する重複臨時公開鍵検証手段と
を備えたことを特徴とする検証装置。
【請求項１２】
上記重複臨時公開鍵検証手段は、
上記選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定し、
ｆ＝１，２，・・・，ｎの全てについてσｆ＝σｆ’が成立する場合には、２つの署名ξ、ξ’は同一署名装置による同一メッセージに対する署名（コピー署名）であると特定し、
１つのｐ〔但し、ｐ∈｛１，２，・・・，ｎ｝〕についてσｐ＝σｐ’が成立する場合には、２つの署名ξ、ξ’は同一署名装置による異なるメッセージに対する署名（重複署名）であると特定する
ものであることを特徴とする請求項１１に記載の検証装置。
【請求項１３】
各署名装置によって生成された署名および各署名に対応するメッセージｍと、全署名者に共通のラベルＬを記憶する記憶手段と、
記憶手段に記憶される各署名装置によって生成された署名から異なる２つの署名ξ、ξ’およびこれら署名に対応するメッセージｍ、ｍ’を選択する選択制御手段と、
選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとに、各署名に対応したメッセージｍ、ｍ’およびラベルＬをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０およびＡ０’を生成する撹乱因子生成因子生成手段と、
選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとに、選択制御手段によって選択された異なる２つの署名ξ、ξ’に含まれる撹乱因子Ａ１、Ａ１’および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、Ａ０’から全署名者数に相当するｎ個の臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
臨時公開鍵生成手段によって生成された、異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定する重複臨時公開鍵検証手段と
を備えたことを特徴とする重複署名コピー署名検出装置。
【請求項１４】
上記重複臨時公開鍵検証手段は、
上記選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定し、
ｆ＝１，２，・・・，ｎの全てについてσｆ＝σｆ’が成立する場合には、２つの署名ξ、ξ’は同一署名装置による同一メッセージに対する署名（コピー署名）であると特定し、
１つのｐ〔但し、ｐ∈｛１，２，・・・，ｎ｝〕についてσｐ＝σｐ’が成立する場合には、２つの署名ξ、ξ’は同一署名装置による異なるメッセージに対する署名（重複署名）であると特定する
ものであることを特徴とする請求項１３に記載の重複署名コピー署名検出装置。
【請求項１５】
１つ以上の署名装置と、検証装置とが相互に通信可能に接続され、
上記署名装置は、
署名者ｉに固有の秘密鍵ｘｉと、署名者ｉに固有の識別番号ｉ、メッセージｍと、全署名者に共通のラベルＬとを記憶する記憶手段と、
記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、署名者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成手段と、
固有臨時公開鍵生成因子生成手段によって生成された固有臨時公開鍵生成因子ｈと記憶手段に記憶される署名者ｉに固有の秘密鍵ｘｉとから署名者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉ、記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成手段と、
署名者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成手段によって生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよびメッセージｍに対する署名とする署名生成手段と
検証装置に対して、ラベルＬ、メッセージｍ、ラベルＬおよびメッセージｍに対する署名を送信可能な対検証装置送信手段と
を備え、
固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉおよび撹乱臨時公開鍵生成手段によって生成された撹乱臨時公開鍵σｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕は、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能に、撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０および撹乱因子生成手段によって生成された撹乱因子Ａ１から生成可能であり、
上記検証装置は、
署名装置から、ラベルＬ、メッセージｍ、ラベルＬおよびメッセージｍに対する署名を受信可能な対署名装置受信手段と、
対署名装置受信手段によって受信したメッセージｍ、ラベルＬ、ラベルＬおよびメッセージｍに対する署名を記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と
を備えたことを特徴とする署名検証システム。
【請求項１６】
１つ以上の署名装置と、検証装置とが相互に通信可能に接続され、
上記署名装置は、
署名者ｉに固有の秘密鍵ｘｉと、署名者ｉに固有の識別番号ｉ、メッセージｍと、全署名者に共通のラベルＬとを記憶する記憶手段と、
記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、署名者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成手段と、
固有臨時公開鍵生成因子生成手段によって生成された固有臨時公開鍵生成因子ｈと記憶手段に記憶される署名者ｉに固有の秘密鍵ｘｉとから署名者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉ、記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成手段と、
署名者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成手段によって生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよびメッセージｍに対する署名とする署名生成手段と
検証装置に対して、ラベルＬ、メッセージｍ、ラベルＬおよびメッセージｍに対する署名を送信可能な対検証装置送信手段と
を備え、
固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉおよび撹乱臨時公開鍵生成手段によって生成された撹乱臨時公開鍵σｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕は、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能に、撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０および撹乱因子生成手段によって生成された撹乱因子Ａ１から生成可能であり、
上記検証装置は、
各署名装置から、各署名装置によって生成された署名および各署名に対応するメッセージｍと、全署名者に共通のラベルＬを受信可能な対署名装置受信手段と、
対署名装置受信手段によって受信した、各署名装置によって生成された署名、各署名に対応するメッセージｍおよびラベルＬを記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全署名者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と、
判定手段によるゼロ知識証明の検証に成功した場合に、記憶手段に記憶される各署名装置によって生成された署名から異なる２つの署名ξ、ξ’およびこれら署名に対応するメッセージを選択する選択制御手段と、
臨時公開鍵生成手段によって生成された、選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定する重複臨時公開鍵検証手段と
を備えたことを特徴とする、重複署名および／またはコピー署名を検出する署名検証システム。
【請求項１７】
１つ以上の署名装置と、検証装置とが相互に通信可能に接続され、
署名者ｉに固有の秘密鍵ｘｉと、署名者ｉに固有の識別番号ｉ、メッセージｍと、全署名者に共通のラベルＬとが署名装置の記憶手段に記憶され、
署名装置の固有臨時公開鍵生成因子生成手段が、署名装置の記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、署名者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成ステップと、
署名装置の固有臨時公開鍵生成手段が、固有臨時公開鍵生成因子生成ステップにおいて生成された固有臨時公開鍵生成因子ｈと署名装置の記憶手段に記憶される署名者ｉに固有の秘密鍵ｘｉとから署名者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成ステップと、
署名装置の撹乱因子生成因子生成手段が、署名装置の記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成ステップと、
署名装置の撹乱因子生成手段が、撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成ステップにおいて生成された固有臨時公開鍵σｉ、署名装置の記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成ステップと、
署名装置の撹乱臨時公開鍵生成手段が、撹乱因子生成ステップにおいて生成された撹乱因子Ａ１および撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０から全署名者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成ステップと、
署名装置の非対話ゼロ知識証明情報生成手段が、署名者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成ステップと、
署名装置の非対話ゼロ知識証明情報生成因子生成手段が、非対話ゼロ知識証明情報生成ステップにおいて生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成ステップと、
署名装置の署名生成手段が、撹乱因子生成ステップにおいて生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成ステップにおいて生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよびメッセージｍに対する署名とする署名生成ステップと、
署名装置の対検証装置送信手段が、検証装置に対して、ラベルＬ、メッセージｍ、ラベルＬおよびメッセージｍに対する署名を送信する対検証装置送信ステップと、
検証装置の対署名装置受信手段が、署名装置から、ラベルＬ、メッセージｍ、ラベルＬおよびメッセージｍに対する署名を受信する対署名装置受信ステップと、
検証装置の記憶手段が、対署名装置受信ステップにおいて受信したメッセージｍ、ラベルＬ、ラベルＬおよびメッセージｍに対する署名を記憶する記憶ステップと、
検証装置の撹乱因子生成因子生成手段が、検証装置の記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する第２撹乱因子生成因子生成ステップと、
検証装置の臨時公開鍵生成手段が、検証装置の記憶手段に記憶される署名に含まれる撹乱因子Ａ１および第２撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０から全署名者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成ステップと、
検証装置の非対話ゼロ知識証明情報生成手段が、検証装置の記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する第２非対話ゼロ知識証明情報生成ステップと、
検証装置の判定手段が、撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０、検証装置の記憶手段に記憶される署名に含まれる撹乱因子Ａ１、第２非対話ゼロ知識証明情報生成ステップにおいて生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定ステップと
を有することを特徴とする署名検証方法。
【請求項１８】
１つ以上の署名装置と、検証装置とが相互に通信可能に接続され、
署名者ｉに固有の秘密鍵ｘｉと、署名者ｉに固有の識別番号ｉ、メッセージｍと、全署名者に共通のラベルＬとが署名装置の記憶手段に記憶され、
署名装置の固有臨時公開鍵生成因子生成手段が、署名装置の記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、署名者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成ステップと、
署名装置の固有臨時公開鍵生成手段が、固有臨時公開鍵生成因子生成ステップにおいて生成された固有臨時公開鍵生成因子ｈと署名装置の記憶手段に記憶される署名者ｉに固有の秘密鍵ｘｉとから署名者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成ステップと、
署名装置の撹乱因子生成因子生成手段が、署名装置の記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成ステップと、
署名装置の撹乱因子生成手段が、撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成ステップにおいて生成された固有臨時公開鍵σｉ、署名装置の記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成ステップと、
署名装置の撹乱臨時公開鍵生成手段が、撹乱因子生成ステップにおいて生成された撹乱因子Ａ１および撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０から全署名者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成ステップと、
署名装置の非対話ゼロ知識証明情報生成手段が、署名者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成ステップと、
署名装置の非対話ゼロ知識証明情報生成因子生成手段が、非対話ゼロ知識証明情報生成ステップにおいて生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成ステップと、
署名装置の署名生成手段が、撹乱因子生成ステップにおいて生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成ステップにおいて生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよびメッセージｍに対する署名とする署名生成ステップと、
署名装置の対検証装置送信手段が、検証装置に対して、ラベルＬ、メッセージｍ、ラベルＬおよびメッセージｍに対する署名を送信する対検証装置送信ステップと、
検証装置の対署名装置受信手段が、各署名装置から、各署名装置によって生成された署名、各署名に対応するメッセージｍおよびラベルＬを受信する対署名装置受信ステップと、
検証装置の記憶手段が、対署名装置受信ステップにおいて受信した、各署名装置によって生成された署名、各署名に対応するメッセージｍおよびラベルＬを記憶する記憶ステップと、
検証装置の撹乱因子生成因子生成手段が、検証装置の記憶手段に記憶されるラベルＬおよびメッセージｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する第２撹乱因子生成因子生成ステップと、
検証装置の臨時公開鍵生成手段が、検証装置の記憶手段に記憶される署名に含まれる撹乱因子Ａ１および第２撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０から全署名者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成ステップと、
検証装置の非対話ゼロ知識証明情報生成手段が、検証装置の記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する第２非対話ゼロ知識証明情報生成ステップと、
検証装置の判定手段が、撹乱因子生成因子生成ステップにおいて生成された撹乱因子生成因子Ａ０、検証装置の記憶手段に記憶される署名に含まれる撹乱因子Ａ１、第２非対話ゼロ知識証明情報生成ステップにおいて生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定ステップと、
検証装置の選択制御手段が、判定ステップにおいてゼロ知識証明の検証に成功した場合に、検証装置の記憶手段に記憶される各署名装置によって生成された署名から異なる２つの署名ξ、ξ’およびこれら署名に対応するメッセージを選択する選択制御ステップと、
検証装置の重複臨時公開鍵検証手段が、臨時公開鍵生成ステップにおいて生成された、選択制御ステップにおいて選択された異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定する重複臨時公開鍵検証ステップと
を有することを特徴とする、重複署名および／またはコピー署名を検出する署名検証方法。
【請求項１９】
１つ以上の電子投票装置と、開票装置と、情報公開サーバ装置とが相互に通信可能に接続され、
上記情報公開サーバ装置は、
選挙を特定する情報を含むラベルＬ、投票内容ｍ、投票内容ｍに対する署名（投票署名）を記憶可能な記憶手段と、
電子投票装置に対して、記憶手段に記憶されるラベルＬおよび投票内容ｍを送信可能な対電子投票装置送信手段と、
電子投票装置の対情報公開サーバ装置送信手段によって送信されたラベルＬ、投票内容ｍおよび投票署名を受信可能な対電子投票装置受信手段と、
開票装置に対して、記憶手段に記憶されるラベルＬ、投票内容ｍ、投票内容ｍに対する投票署名を送信可能な対開票装置送信手段と
を備え、
上記電子投票装置は、
情報公開サーバ装置の対電子投票装置送信手段によって送信されたラベルＬおよび投票内容ｍを受信する対情報公開サーバ装置受信手段と、
対情報公開サーバ装置受信手段によって受信した投票内容ｍおよびラベルＬ並びに投票者ｉに固有の秘密鍵ｘｉと、投票者ｉに固有の識別番号ｉとを記憶する記憶手段と、
記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、投票者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成手段と、
固有臨時公開鍵生成因子生成手段によって生成された固有臨時公開鍵生成因子ｈと記憶手段に記憶される投票者ｉに固有の秘密鍵ｘｉとから投票者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成手段と、
記憶手段に記憶されるラベルＬおよび投票内容ｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉ、記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全投票者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成手段と、
投票者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成手段によって生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよび投票内容ｍに対する署名（投票署名）とする署名生成手段と、
情報公開サーバ装置に対して、ラベルＬ、投票内容ｍ、ラベルＬおよび投票内容ｍに対する投票署名を送信可能な対情報公開サーバ装置送信手段と
を備え、
固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉおよび撹乱臨時公開鍵生成手段によって生成された撹乱臨時公開鍵σｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕は、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能に、撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０および撹乱因子生成手段によって生成された撹乱因子Ａ１から生成可能であり、
上記開票装置は、
情報公開サーバ装置から、各電子投票装置によって生成された投票署名、各投票署名に対応する投票内容ｍおよびラベルＬを受信可能な対情報公開サーバ装置受信手段と、
対情報公開サーバ装置受信手段によって受信した、各電子投票装置によって生成された投票署名、各投票署名に対応する投票内容ｍおよびラベルＬを記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよび投票内容ｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される投票署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全投票者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される投票署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される投票署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と、
判定手段によるゼロ知識証明の検証に成功した場合に、記憶手段に記憶される各電子投票装置によって生成された投票署名から異なる２つの投票署名ξ、ξ’およびこれら投票署名に対応する投票内容を選択する選択制御手段と、
臨時公開鍵生成手段によって生成された、選択制御手段によって選択された異なる２つの投票署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定する重複臨時公開鍵検証手段と
判定手段によるゼロ知識証明の検証および重複臨時公開鍵検証手段による重複投票署名および／またはコピー投票署名の検出に成功した場合に、重複投票署名に対応した投票内容ついてはその全ての個数を除いて、コピー投票署名に対応した投票内容についてはその総数から１を引いた個数を除いて、投票内容に投票された投票数を計数する集計手段と
を備えたことを特徴とする、重複投票署名および／またはコピー投票署名を検出する電子投開票システム。
【請求項２０】
１つ以上の利用者装置と、１つ以上の店舗装置と、銀行の検証装置とが相互に通信可能に接続され、
上記利用者装置は、
店舗装置から取引を特定する情報である取引情報ｍを受信する対店舗装置受信手段と、
対店舗装置受信手段によって受信した取引情報ｍ並びに、利用者ｉに固有の秘密鍵ｘｉと、利用者ｉに固有の識別番号ｉと、電子現金の金額の情報を含むラベルＬとを記憶する記憶手段と、
記憶手段に記憶されるラベルＬをハッシュ関数Ｈに入力して、利用者ｉに固有の固有臨時公開鍵σｉを生成するために用いられる固有臨時公開鍵生成因子ｈを生成する固有臨時公開鍵生成因子生成手段と、
固有臨時公開鍵生成因子生成手段によって生成された固有臨時公開鍵生成因子ｈと記憶手段に記憶される利用者ｉに固有の秘密鍵ｘｉとから利用者ｉに固有の固有臨時公開鍵σｉを生成する固有臨時公開鍵生成手段と、
記憶手段に記憶されるラベルＬおよび取引情報ｍをハッシュ関数Ｈ’に入力して、撹乱因子Ａ１を生成するために用いられる撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉ、記憶手段に記憶される識別番号ｉとから撹乱因子Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を生成する撹乱因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全利用者数ｎから１を引いた個数の撹乱臨時公開鍵σｊ＝Ａ０Ａ１ｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕を生成する撹乱臨時公開鍵生成手段と、
利用者ｉに固有の秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したことを非対話ゼロ知識証明によって証明するために用いる非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子を生成する非対話ゼロ知識証明情報生成因子生成手段と、
撹乱因子生成手段によって生成された撹乱因子Ａ１および非対話ゼロ知識証明情報生成因子生成手段によって生成された非対話ゼロ知識証明情報生成因子を、記憶手段に記憶されるラベルＬおよび取引情報ｍに対する署名とする署名生成手段と
店舗装置に対して、ラベルＬ、取引情報ｍ、ラベルＬおよび取引情報ｍに対する署名を電子現金として送信する対店舗装置送信手段と
を備え、
固有臨時公開鍵生成手段によって生成された固有臨時公開鍵σｉおよび撹乱臨時公開鍵生成手段によって生成された撹乱臨時公開鍵σｊ〔ｊ＝１，２，・・・，ｉ−１、ｉ＋１，・・・，ｎ〕は、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能に、撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０および撹乱因子生成手段によって生成された撹乱因子Ａ１から生成可能であり、
上記店舗装置は、
利用者装置に対して取引情報ｍを送信する対利用者装置送信手段と、
利用者装置からラベルＬ、取引情報ｍ、ラベルＬおよび取引情報ｍに対する署名を受信する対利用者装置受信手段と、
対利用者装置受信手段によって受信した、利用者装置によって生成された署名、各署名に対応する取引情報ｍおよびラベルＬを記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよび取引情報ｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全利用者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と、
判定手段によってゼロ知識証明が成功した場合に、対利用者装置受信手段によって受信したラベルＬ、取引情報ｍ、ラベルＬおよび取引情報ｍに対する署名を銀行の検証装置に送信する対銀行検証装置送信手段と
を備え、
上記銀行の検証装置は、
各店舗装置からラベルＬ、取引情報ｍ、ラベルＬおよび取引情報ｍに対する署名を受信する対店舗装置受信手段と、
対店舗装置受信手段によって受信した、各利用者装置によって生成された署名、各署名に対応する投票内容ｍおよびラベルＬを記憶する記憶手段と、
記憶手段に記憶されるラベルＬおよび取引情報ｍをハッシュ関数Ｈ’に入力して、撹乱因子生成因子Ａ０を生成する撹乱因子生成因子生成手段と、
記憶手段に記憶される署名に含まれる撹乱因子Ａ１および撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０から全利用者数に相当するｎ個の臨時公開鍵σｆ＝Ａ０Ａ１ｆ〔ｆ＝１，２，・・・，ｎ〕を生成する臨時公開鍵生成手段と、
記憶手段に記憶される署名に含まれる非対話ゼロ知識証明情報生成因子を用いて非対話ゼロ知識証明情報を生成する非対話ゼロ知識証明情報生成手段と、
撹乱因子生成因子生成手段によって生成された撹乱因子生成因子Ａ０、記憶手段に記憶される署名に含まれる撹乱因子Ａ１、非対話ゼロ知識証明情報生成手段によって生成された非対話ゼロ知識証明情報の間でゼロ知識証明の検証を行う判定手段と、
記憶手段に記憶される各利用者装置によって生成された署名から異なる２つの署名ξ、ξ’およびこれら署名に対応する取引情報ｍ、ｍ’を選択する選択制御手段と、
臨時公開鍵生成手段によって生成された、選択制御手段によって選択された異なる２つの署名ξ、ξ’ごとの臨時公開鍵σｆ、σｆ’〔ｆ＝１，２，・・・，ｎ〕について、各ｆごとにσｆ＝σｆ’が成立するか否かを判定する重複臨時公開鍵検証手段と、
判定手段によるゼロ知識証明の検証および重複臨時公開鍵検証手段による重複署名および／またはコピー署名の検出に成功した場合に、ラベルＬに定まる金額を店舗の銀行口座に振り込む口座管理手段と、
を備えたことを特徴とする電子現金支払システム。
【請求項２１】
請求項１、２、３、４、１７、１８のいずれかに記載の方法の各ステップをコンピュータにより実行するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関するものであり、閾値つき電子署名技術に関する。
【背景技術】
【０００２】
閾値つき電子署名技術は、複数の参加者の一部が協力することで署名が生成されたことを、誰が署名生成に協力したのかが分からないように署名のみから確認できる電子署名である。ｎ人の参加者うち任意のｔ人以上が協力することで署名が生成されたことを、誰が署名生成に協力したのかが分からないように署名のみから確認できる電子署名の方式を、（ｔ，ｎ）閾値電子署名方式と呼ぶ。従来の方法として非特許文献１に示された方法がある。最初に本説明中で使用する記号について説明する。離散対数問題が難しいと考えられている巡回群をＧとし、その生成元をｇ、群の位数をｑとする（Ｇ＝＜ｇ＞，＃Ｇ＝ｑ）。Ｚｑは、ｑを法とする剰余類{０，１，２，…，ｑ−１}である。∈Ｕは一様ランダムに元を取り出すことを、{０，１}＊は０または１が任意長並んだビット列を、Ｋは有限体を意味する。また、Ｈ，Ｉ，ＪはそれぞれＨ：{０，１}＊→Ｚｑのように変換するハッシュ関数である。以下に非特許文献１に示された方法について説明する。
【０００３】
図１に、閾値つき電子署名システムの構成例と流れを示す。本システムへの参加者の総数はｎ人であり、ｎ台の参加装置９１０−ｉ（ｉ＝１，…，ｎ）では、あらかじめ定められた巡回群Ｇの元ｇ（ｇ∈Ｇ）を用いて、各参加装置の秘密鍵ｘｉと公開鍵ｙｉとが生成され、公開鍵ｙｉは公開される。署名を作成する場合は、ｎ人中の任意のｔ人以上が参加装置９１０−ｉ（ｉ＝１，…，ｔ）でコミットメントａｉを生成し、署名生成部９２０を備える装置に送信する。ここで、説明を簡略化するために、ｉ＝１，…，ｔを署名生成に使用した（協力した）参加装置を示す数、ｉ＝ｔ＋１，…，ｎを署名作成に使用していない（協力しなかった）参加装置を示す数とするが、ｔ台の参加装置はｎ台の参加装置中のどれでも良い。
【０００４】
署名生成部９２０は、独立した装置ででもかまわないし、いずれかの参加装置内に備えさせてもかまわない。署名生成部９２０は、ｉ＝ｔ＋１，…，ｎに対するダミーレスポンスｅｉ、ダミーチャレンジｃｉ、およびダミーコミットメントａｉを生成した上で、ｎ−ｔ次多項式ｆ（ｘ）、ｉ＝１，…，ｔに対するチャレンジｃｉとレスポンスｅｉとを生成し、署名σ（ｍ）を作成する。この署名σ（ｍ）はｔ台の参加装置９１０−ｉ（ｉ＝１，…，ｔ）から取得したコミットメントａｉと、署名生成部９２０がダミーとして生成したコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）等から生成されており、ｔ人が協力した署名生成になっているだけでなく、どのｔ人が協力したのかが分からない署名になっている。
【０００５】
署名検証部９３０は、署名検証を行いたい任意の装置内に備えてかまわない。署名検証部では、多項式ｆ（ｘ）の次数がｎ−ｔであること、チャレンジｃｉ（ｉ＝１，…，ｎ）とｆ（０）の値が正しいことなどを検証する。
図２は、参加装置９１０−ｉの機能構成例を示す図である。参加装置９１０−ｉは、鍵生成部９１１−ｉ、乱数生成部９１２−ｉ、記録部９１３−ｉ、および通信部９１４−ｉから構成される。図３は鍵生成部９１１−ｉの処理フローを示す図であり、図４は乱数生成部９１２−ｉの処理フローを示す図である。
【０００６】
鍵生成部９１１−ｉは、秘密鍵ｘｉ生成手段９１１１−ｉと公開鍵ｙｉ生成手段９１１２−ｉとで構成される。鍵生成部９１１-ｉでの具体的な鍵生成方法の例を次に示す。秘
密鍵ｘｉ生成手段９１１１−ｉでは、ｑを法とする剰余類Ｚｑから等確率でランダムに１つの元を選択して秘密鍵ｘｉとし（ｘｉ∈ＵＺｑ）（Ｓ９１１１）、秘密鍵ｘｉを記録部９１３−ｉに記録する（Ｓ９１１２）。公開鍵ｙｉ生成手段９１１２−ｉでは、あらかじめ定められた巡回群Ｇの元ｇを用いて、
【０００７】
【数３３】
0004790422.tif 000002
により公開鍵ｙｉ（ｙｉ∈Ｇ＝{１，ｇ，ｇ２，…，ｇｑ−１}）を生成し（Ｓ９１１３）、公開鍵ｙｉを記録部９１３−ｉに記録する（Ｓ９１１４）。ここで、巡回群Ｇは、離散対数問題が難しい群から選ばれているため、公開鍵ｙｉと元ｇが分かっても、秘密鍵ｘｉは分からない。このように生成された公開鍵ｙｉは、元ｇの情報とともに通信部９１４−ｉを介して公開される。
【０００８】
乱数生成部９１２−ｉは、署名生成に協力する場合に動作する構成部であり、乱数ｒｉ生成手段９１２１−ｉ、コミットメントａｉ生成手段９１２２−ｉ、チャレンジｃｉ取得手段９１２３−ｉ、およびレスポンスｅｉ生成手段９１２２−ｉで構成される。乱数生成部９１２−ｉでの具体的な処理手順の例を次に示す。参加者が署名に協力する場合には、乱数ｒｉ生成手段９１２１−ｉでは、ｑを法とする剰余類Ｚｑから等確率でランダムに１つの元を選択して乱数ｒｉとする（ｒｉ∈ＵＺｑ）（Ｓ９１２１）。次にコミットメントａｉ生成手段９１２２−ｉでは、元ｇを用いて、
【０００９】
【数３４】
0004790422.tif 000003
によりコミットメントａｉ（∈Ｇ）を生成し（Ｓ９１２２）、コミットメントａｉを記録部９１３−ｉに記録し、通信部９１４−ｉを介して署名生成部９２０を備える装置に送信する（Ｓ９１２３）。署名生成部９２０で署名生成処理が行われると、署名生成部９２０の計算部９２２の処理過程で生成されたチャレンジｃｉが署名生成部９２０から、署名生成に協力している参加装置９１０−ｉ（ｉ＝１，…，ｔ）に送信される。このチャレンジｃｉをチャレンジｃｉ取得手段９１２３−ｉで取得し（Ｓ９１２４）、記録部９１３−ｉに記録する（Ｓ９１２５）。また、レスポンスｅｉ生成手段９１２２−ｉで、ｅｉ：＝ｒｉ−ｃｉｘｉ（ｅｉ∈Ｚｑ）により、ｅｉ（ｉ＝１，…，ｔ）を求め（Ｓ９１２６）、記録部９１３−ｉに記録するとともに署名生成部９２０に送信する（Ｓ９１２７）。
【００１０】
図５に署名生成部９２０の機能構成例を示す。署名生成部９２０は、ダミー生成部９２１、計算部９２２、情報取得部９２３、記録部９２４、および通信部９２５から構成されている。また、図６は署名生成部９２０の処理フローを示す図である。
署名生成部９２０では、以下の手順で署名σ（ｍ）が生成される。通信部９２５を介して情報取得部９２３の公開鍵ｙｉ（ｉ＝１，…，ｎ）取得手段９２３１により、参加装置９１０−ｉ（ｉ＝１，…，ｎ）の公開鍵ｙｉを取得する（Ｓ９２３１）。ダミー生成部９２１では、次のように、ダミーレスポンスｅｉ、ダミーチャレンジｃｉ、ダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）を生成する。ダミーレスポンスｅｉ・ダミーチャレンジｃｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１１により、ｑを法とする剰余類Ｚｑから等確率でランダムに元を選択してダミーレスポンスｅｉとダミーチャレンジｃｉ（ｉ＝ｔ＋１，…，ｎ）とし（ｅｉ，ｃｉ∈ＵＺｑ）（Ｓ９２１１）、記録部９２４に記録する（Ｓ９２１２）。また、ダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）生成手段９２１３により、元ｇと公開鍵ｙｉを用いて、
【００１１】
【数３５】
0004790422.tif 000004
によりダミーコミットメントａｉ（ｉ＝ｔ＋１，…，ｎ）を生成し（Ｓ９２１５）、記録部９２４に記録する（Ｓ９２１６）。
また、通信部９２５を介して情報取得部９２３のコミットメントａｉ（ｉ＝１，…，ｔ）取得手段９２３２により、参加装置９１０−ｉ（ｉ＝１，…，ｔ）のコミットメントａｉを取得する（Ｓ９２３２）。
【００１２】
次に、計算部９２２では、以下のようにメッセージｍの（ｔ，ｎ）閾値署名σ（ｍ）を求める。ｎ−ｔ次多項式ｆ（ｘ）計算手段９２２１により、ｎ−ｔ次の多項式ｆ（ｘ）（ｆ（ｘ）＝α０＋α１ｘ＋α２ｘ２＋…＋αｎ−ｔｘｎ−ｔ，αｊ∈Ｚｑ）と定め、ｆ（０）＝Ｈ（ｔ，ｎ，ｙ１，…，ｙｎ，ａ１，…，ａｎ，ｍ）とｆ（ｉ）＝ｃｉ（ｉ＝ｔ＋１，…，ｎ）の条件からαｊ（ｊ＝０，…，ｎ−ｔ）を計算することでｎ−ｔ次多項式ｆ（ｘ）を求める（Ｓ９２２１）。また、求めたｎ−ｔ次多項式ｆ（ｘ）を記録部９２４に記録する（Ｓ９２２２）。チャレンジｃｉ（ｉ＝１，…，ｔ）生成手段９２２２では、ｃｉ：＝ｆ（ｉ）により、チャレンジｃｉ（ｉ＝１，…，ｔ）を求め（Ｓ９２２３）、記録部９２４に記録するとともに、チャレンジｃｉに対応する参加装置９１０−ｉ（ｉ＝１，…，ｔ）にチャレンジｃｉを送信する（Ｓ９２２４）。各参加者装置９１０−ｉ（ｉ＝１，…，ｔ）では、送信されたチャレンジｃｉを用いて、上記のようにレスポンスｅｉを生成し署名生成部９２０に送信する（Ｓ９１２４〜Ｓ９１２７）。そこで、レスポンスｅｉ（ｉ＝１，…，ｔ）取得手段９２２３は、レスポンスｅｉ（ｉ＝１，…，ｔ）を取得し（Ｓ９２２５）、記録部９２４に記録する（Ｓ９２２６）。署名σ（ｍ）作成手段９２２３では、σ（ｍ）＝（ｔ，ｎ，ｆ，ｃ１，…，ｃｎ，ｅ１，…，ｅｎ）により、σ（ｍ）を求め（Ｓ９２２７）、記録部９２４に記録する（Ｓ９２２８）。このようにしてメッセージｍに対する（ｔ，ｎ）閾値署名σ（ｍ）を求める。
【００１３】
図７に署名検証部９３０の機能構成例を示す。また、図８に署名検証部９３０での署名σ（ｍ）を検証するフローを示す。情報取得手段９３３は、公開鍵ｙｉ（ｉ＝１，…，ｎ）と署名σ（ｍ）を取得し（Ｓ９３３）、多項式ｆ（ｘ）の次数確認手段９３１で多項式ｆ（ｘ）の次数がｎ−ｔであることを確認し（Ｓ９３１）、チャレンジｃｉ、多項式ｆ（０）確認手段９３２で、
【００１４】
【数３６】
0004790422.tif 000005
であることを確認する（Ｓ９３２）。
このように署名σ（ｍ）の生成と検証を行うことで、署名検証部９３０（署名検証をする人）は、少なくともｔ台の参加装置９１０−ｉ（ｔ人の参加者）が協力して署名を作成したことが確認できる。また、署名検証部９３０は、ｎ台の参加装置９１０−ｉ中のどのｔ台（ｎ人の参加者中のどのｔ人）が署名生成に協力したのかは分からない。
【非特許文献１】[CDS94] R. Cramer and I. Damgard and B. Schoen-makers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, CRYPTO ’94, pp. 174-187, 1994.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
従来技術では、どの参加者が署名生成に協力したのかが分からないことを特徴としてい
るが、参加者が署名生成に協力したことを証明すること（名乗り出ること）もできなかった。
また、署名生成に協力したことを証明することができるようにする場合には、何人の参加者が証明できるのかを署名から確認できるようにすることも必要である。さらに、署名生成に協力したことを証明するときに秘密鍵の情報も流出することが考えられることから、以後、今までの秘密鍵と公開鍵が使用できなくなる問題があった。
【００１６】
本発明の目的は、秘密鍵と公開鍵とが使えなくなることなく、かつ、ｎ台（ｎは２以上の整数）の参加者装置（集合Ｎ）に含まれるｓ台の参加者装置（集合Ｓ）が署名を行った場合に、署名をした参加者装置がｔ台以上（集合Ｔ）ｔ’台（集合Ｔ’）以下であることが確認できる署名方法を提供することにある。
【課題を解決するための手段】
【００１７】
離散対数問題をもとに秘密鍵と公開鍵とを生成する場合に、署名者の使い捨て公開鍵と公開鍵との離散対数を等しくすることにより、使い捨て公開鍵と公開鍵とを関連つける。
具体的には、署名を行う集合Ｓの各参加者装置では、公開鍵ｙｉ、使い捨て公開鍵σｉの間で、離散対数を等しくするように使い捨て公開鍵σｉ（ｉ∈Ｓ）を生成する。また、集合Ｓの参加者装置で協力して集合Ｔ’−Ｓの使い捨て公開鍵σｉ（ｉ∈Ｔ’−Ｓ）を生成する。集合Ｎ−Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｎ−Ｔ’）は、σｉ（ｉ∈Ｔ’）から決まるｔ’次の多項式を用いて、計算により求める。このように使い捨て公開鍵を生成した上で、署名を作成する。また、実施形態によっては、離散対数が等しいことを証明することで、各参加者装置が署名した参加者であることを証明することもできる。
【発明の効果】
【００１８】
本発明によれば、公開鍵と使い捨て公開鍵とは、離散対数が等しいので関連付けられており、署名者になりすますことができない。また、ｎ台の参加者装置に含まれるｓ台の参加者装置が署名を行った場合に、署名をした参加者装置がｔ台以上ｔ’台以下であることが確認できる署名方法を提供することができる。
【発明を実施するための最良の形態】
【００１９】
以下にこの発明の実施形態を図面を参照して説明するが、同一の機能を有する部分は、各図中に同一参照番号を付けて重複説明を省略する。また、以下の説明では、離散対数問題が難しいと考えられている巡回群をＧ、Ｇの生成元をｇ、Ｒ、Ｇの位数をｑ、ｑを法とする剰余類{０，１，２，…，ｑ−１}をＺｑ、ｇとＲとはパブリックパラメータ、ＨとＨ’を０と１からなるビット列をＧの元に写像するハッシュ関数、Ｈ”を０と１からなるビット列をＺｑの元に写像するハッシュ関数、ｍをメッセージとする。なお、ａＮは｛ａｉ｝ｉ∈Ｎを意味する。
［第１実施形態］
図９は、本発明のシステム構成例を示している。ｎ台（ｎは２以上の整数）の参加者装置（集合Ｎ）に含まれるｓ台の参加者装置１１０−ｉ（集合Ｓ）が協力して署名を行う。協力して署名を行うとは、１つの参加者装置の恣意では署名を確定することができず、集合Ｓの各参加者装置１１０−ｉから送られる情報の全てを用いて署名を作成する意味である。したがって、これらの情報を取りまとめる装置が必要であり、図９では署名生成部１２０が行っている。この署名生成部１２０は、単独の装置でもかまわないし、集合Ｎのいずれか参加者装置の内部に備えられてもよい。もしくは、全ての参加者装置に備えられ、署名を行うたびに異なる署名生成部が情報の取りまとめや署名作成を行ってもよい。また、署名をした参加者装置がｔ台以上（集合Ｔ）ｔ’台（集合Ｔ’）以下であることが確認できる署名方法を提供する。本実施形態では、集合Ｎの各参加者装置は署名した参加者装置か署名していない参加者装置かを証明することができる。
【００２０】
図１０に参加者装置１１０−ｉの機能構成例を示す。参加者装置１１０−ｉは、秘密鍵ｘｉと公開鍵ｙｉとを生成する鍵生成部９１１−ｉ、使い捨て公開鍵を秘密鍵ｘｉから生成する鍵生成部１１２−ｉ、任意のＺｑの元ｗｉを選定するｗｉ生成手段１１３１−ｉ、ｗｉからａｉとｂｉを生成するａｉ・ｂｉ生成手段１１３２−ｉ、Ｚｑの元ｚｉを、秘密鍵ｘｉを用いて計算するｚｉ生成手段１１３４−ｉ、集合ＴとＴ’とを選定するための集合選定情報を生成する集合選定情報の生成手段１１３５−ｉ、０と１のビット列であるｒを選定するためのｒ選定情報を生成するｒ選定情報の生成手段１１３６−ｉ、集合Ｔ’−Ｓの使い捨て公開鍵を選定するためのσ選定情報を生成するσ選定情報の生成手段１１３７−ｉ、任意のＺｑの元ｚｉとｃｉを選定するためのｚｉ・ｃｉ選定情報を生成するｚｉ・ｃｉ選定情報の生成手段１１３８−ｉ、任意のＺｑの元ｃｉを選定するためのｃｉ選定情報を生成するｃｉ選定情報の生成手段１１３９−ｉ、情報を公開または集合Ｓの他の参加者装置および署名生成部に送信する通信・公開部１１５−ｉ、情報を記録する記録部１１４−ｉから構成される。
【００２１】
図１１に署名生成部１２０の機能構成例を示す。署名生成部１２０は、集合Ｓの各参加者装置１１０−ｉからの集合選定情報をもとに、Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合Ｔと集合Ｔ’の元となる参加者装置を選定する集合Ｔ，Ｔ’選定手段１２１１、集合Ｓの各参加者装置１１０−ｉからのｒ選定情報をもとに、前記ｒを選定するｒ選定手段１２１２、集合Ｓの各参加者装置１１０−ｉからのσ選定情報をもとに、集合Ｔ’−Ｓの使い捨て公開鍵を選定するσｉ選定手段１２１３、集合Ｓの各参加者装置１１０−ｉからのｚｉ・ｃｉ選定情報をもとに、集合Ｎ−Ｓのｚｉとｃｉを選定するｚｉ・ｃｉ選定手段１２１４、集合Ｓの各参加者装置１１０−ｉからのｃｉ選定情報をもとに、集合Ｓ−Ｔのｃｉを選定するｃｉ選定手段１２１５、ｚｉとｃｉから集合Ｎ−Ｓのａｉとｂｉを生成するａｉ・ｂｉ生成手段１２１６、集合Ｔ’の使い捨て公開鍵から、集合Ｎ−Ｔ’の使い捨て公開鍵σｉを計算するσｉ計算手段１２２２、Ｚｑの元であって、次数（ｎ−ｔ）の多項式β（ｘ）を計算するβ（ｘ）計算手段１２２３、署名を、ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎを用いて生成する署名出力部１２４、他の装置と通信を行う通信部１２３、情報を記録する記録部１２５から構成される。
【００２２】
図１２は、署名検証部１３０の機能構成例を示す。署名検証部１３０は、署名検証を行いたい任意の装置の内部に備えられる。また、署名検証部１３０は、ｎ，ｔ，ｔ’、集合Ｎの各参加者装置の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝、メッセージｍ、署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ）を受信し、検証結果を出力する通信部１３２、ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ）、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ）として、ｒがｋビットの０と１のビット列であること、ｈ，Ａ０，…，Ａｔ’が群Ｇの元であること、ｚ１，…，ｚｎがＺｑの元であることを確認する群の適正確認手段１３１１、σｉ（ｉ＝１，…，ｎ）がＧの元であることを確認するＡｉの適正確認手段１３１２とａＮ’＝｛ａ１’，…，ａｎ’｝，ｂＮ’＝｛ｂ１’，…，ｂｎ’｝を求め、β（ｘ）がＺｑの元であり、かつｎ−ｔ次であること、β（０）＝Ｈ”（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ，ｈ，Ａ０，…，Ａｔ’ ，ａＮ’，ｂＮ’）であることを確認するβ（ｘ）の適正
確認手段１３１３とから構成される。
【００２３】
図１３は電子署名システムの処理フローを示している。以下に、処理フローを図１３に従って説明する。
集合Ｎの各参加者装置１１０−ｉ（ｉ＝１，…，ｎ）の鍵生成部９１１−ｉは、秘密鍵ｘｉと公開鍵ｙｉとを生成し、公開鍵ｙｉを公開する（Ｓ３１０）。署名に参加する各参加者装置１１０−ｉ（集合Ｓ、ｉ＝１，…，ｓ）の集合選定情報の生成手段１１３５−ｉは、Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合ＴとＴ’とを選定するための集合選定情報を生成し、集合Ｓの他の参加者装置および署名生成部に前記集合選定情報を送信する（Ｓ３２０）。署名生成部１２０の集合Ｔ，Ｔ’選定手段１２１１で、集合Ｓの各参加者装置からの前
記集合選定情報をもとに、任意の集合Ｔと集合Ｔ’の元となる参加者装置を選定し、集合Ｓの参加者装置に送信する（Ｓ３３０）。ここで、「集合選定情報をもとに、任意の集合Ｔと集合Ｔ’の元となる参加者装置を選定する」とは、集合Ｓの参加者装置１１０−ｉ（集合Ｓ、ｉ＝１，…，ｓ）から送られたｓ個の集合選定情報全てを用いて、任意の集合を選定することを意味している。言い換えると、集合Ｓの限られた参加者装置１１０−ｉの恣意によって集合Ｔと集合Ｔ’が選ばれることはないことを意味している。また、集合選定情報は、固定された数値でなければ、適当な数値でよく、乱数などによって発生させてもよい。以下、「選定情報を用いて選定する。」と言うときは同じ意味である。なお、集合Ｔの元の数がｔであり、集合Ｔ’の元の数がｔ’である。また、集合Ｔ’の元をｋ１，…，ｋｔ’とする。集合Ｓの各参加者装置１１０−ｉ（ｉ＝１，…，ｓ）のｒ選定情報の生成手段１１３６−ｉは、ｋビットの０と１のビット列であるｒを選定するためのｒ選定情報を生成し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ３４０）。署名生成部１２０のｒ選定手段１２１２は、集合Ｓの各参加者装置１１０−ｉからの前記ｒ選定情報をもとに、ｋビットの０と１のビット列である任意のｒを選定し、集合Ｓの参加者装置１１０−ｉに送信する（Ｓ３５０）。集合Ｓの各参加者装置１１０−ｉ（ｉ＝１，…，ｓ）の鍵生成部１１２−ｉで、使い捨て公開鍵σｉ（ｉ＝１，…，ｓ）を、
【００２４】
【数３７】
0004790422.tif 000006
により生成し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ３６０）。集合Ｓの各参加者装置１１０−ｉ（ｉ＝１，…，ｓ）のσ選定情報の生成手段１１３７−ｉで、集合Ｔ’−Ｓの使い捨て公開鍵σｉ（ｉ∈Ｔ’−Ｓ）を選定するためのσ選定情報を生成し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ３７０）。署名生成部１２０のσｉ選定手段１２１３で、集合Ｓの各参加者装置１１０−ｉからの前記σ選定情報をもとに、任意の集合Ｔ’−Ｓの使い捨て公開鍵σｉ（ｉ∈Ｔ’−Ｓ）を選定し、集合Ｓの参加者装置１１０−ｉに送信する（Ｓ３８０）。署名生成部１２０のσｉ計算手段１２２２で、集合Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｔ’、ｉ＝ｋ１，…，ｋｔ’）から、
【００２５】
【数３８】
0004790422.tif 000007
として、Ａｉ（ｉ＝０，…，ｔ'）を
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ）
【００２６】
【数３９】
0004790422.tif 000008
と定め、
【００２７】
【数４０】
0004790422.tif 000009
として集合Ｎ−Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｎ−Ｔ’）を計算し、集合Ｓの参加者装置１１０−ｉに送信する（Ｓ３９０）。ステップＳ３９０の処理内容について説明する。
Ａ０＝ｈα（０）
ただし、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ）
と、
σｉ＝ｈα（ｉ）
ただし、ｉ＝ｋ１，…，ｋｔ’
が成り立つ次数ｔ’の多項式α（ｘ）を求める。そして、α（ｘ）から、集合Ｎ−Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｎ−Ｔ’）を、
σｉ＝ｈα（ｉ）
により求める。このように使い捨て公開鍵σｉ（ｉ∈Ｎ）求めることによって、集合Ｎの全ての参加者装置１１０−ｉの使い捨て公開鍵σｉが、σｉ＝ｈα（ｉ）を満たす。ところが、α（ｘ）の次数がｔ’であることから、署名に参加した参加者装置１１０−ｉはｔ’以下であることは分かる。しかし、全てのｉ（ｉ＝１，…，ｎ）に対してσｉ＝ｈα（ｉ）が成り立つので、どの参加者装置１１０−ｉが署名に参加したのかは分からない。ただし、実際にはＡ０はＨ’で生成されているから、離散対数α（０）が分からない。したがって、α（ｘ）を直接求めることはできない。そこで、ステップＳ３９０では、Ａｉを用いて計算している。
【００２８】
以下のステップでは、「秘密鍵ｘｉを知っていて、ｌｏｇｇｙｉ＝ｘｉ＝ｌｏｇｈσｉが成り立つｉがｔ以上である。」ことを証明する。まず、集合Ｓの各参加者装置１１０−ｉのｗｉ生成手段１１３１−ｉで、任意のＺｑの元ｗｉを選定する（Ｓ４００）。集合Ｓの各参加者装置１１０−ｉのａｉ・ｂｉ生成手段１１３２−ｉで、
【００２９】
【数４１】
0004790422.tif 000010
によってａｉとｂｉとを生成し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ４１０）。集合Ｓの各参加者装置１１０−ｉのｚｉ・ｃｉ選定情報の生成手段１１３８−ｉで、任意のＺｑの元ｚｉと元ｃｉを選定するためのｚｉ・ｃｉ選定情報を生成し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ４２０）。署名生成部１２０のｚｉ・ｃｉ選定手段１２１４で、前記ｚｉ・ｃｉ選定情報をもとに、集合Ｎ−Ｓのｚｉとｃｉ（ｉ∈Ｎ−Ｓ）を選定し、ａｉ・ｂｉ生成手段１２１６で、
【００３０】
【数４２】
0004790422.tif 000011
により集合Ｎ−Ｓのａｉとｂｉ（ｉ∈Ｎ−Ｓ）とを生成し、生成したａｉとｂｉとを集合Ｓの参加者装置１１０−ｉに送信する（Ｓ４３０）。集合Ｓの各参加者装置１１０−ｉのｃｉ選定情報の生成手段１１３９−ｉで、任意のＺｑの元ｃｉを選定するためのｃｉ選定
情報を生成し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ４４０）。署名生成部１２０のｃｉ選定手段１２１５は、集合Ｓの各参加者装置の前記ｃｉ選定情報生成ステップで生成されたｃｉ選定情報をもとに、集合Ｓ−Ｔのｃｉ（ｉ∈Ｓ−Ｔ）を選定し、集合Ｓの参加者装置１１０−ｉに送信する（Ｓ４５０）。署名生成部１２０のβ（ｘ）計算手段１２２３は、
β（０）＝Ｈ”（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ，ｈ，Ａ０，…，Ａｔ’，ａＮ，ｂＮ）
β（ｉ）＝ｃｉ
ただし、ｉ∈Ｎ−Ｔ
を満足するＺｑの元であって、次数（ｎ−ｔ）の多項式β（ｘ）を求め、集合Ｓの参加者装置１１０−ｉに送信する（Ｓ４６０）。集合Ｓの各参加者装置１１０−ｉのｚｉ生成手段１１３４−ｉは、
ｚｉ＝ｗｉ−β（ｉ）ｘｉ
によってＺｑの元ｚｉを計算し、集合Ｓの他の参加者装置１１０−ｉおよび署名生成部１２０に送信する（Ｓ４７０）。署名生成部１２０の署名出力部１２４で、署名を、ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎを用いて生成する（Ｓ４８０）。なお、説明が冗長となるため説明上は省略しているが、各ステップで生成、計算、受信された情報は、処理のたびに記録部１１４−ｉまたは１２５に記録され、利用される情報は記録部１１４−ｉまたは１２５から読み出される。このような処理によって、α（ｘ）がｔ’次であること、β（ｘ）が（ｎ−ｔ）次であることから、ｔ台以上ｔ’台以下の参加者装置が署名に参加したことを確認できる署名を生成できる。
【００３１】
次に署名検証部１３０での処理フローを説明する。署名検証部１３０の通信部１３２で、通信部１３２で、ｎ，ｔ，ｔ’、集合Ｎの各参加者装置の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝、メッセージｍ、署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ）を受信し、群の適正確認部１３１１で、
ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ）
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ）
を計算し、ｒがｋビットの０と１のビット列であること、ｈ，Ａ０，…，Ａｔ’が群Ｇの元であること、ｚ１，…，ｚｎがＺｑの元であることを確認する（Ｓ４９０）。Ａｉの適正確認部１３１２は、
【００３２】
【数４３】
0004790422.tif 000012
で求められるσｉ（ｉ＝１，…，ｎ）がＧの元であることを確認する（Ｓ５００）。このステップで、Ａｉがｉ＝０，…，ｔ’の（ｔ’＋１）個しかないことから、署名に参加した参加者装置１１０−ｉがｔ’台以下であることも確認される。次に、β（ｘ）の適正確認部１３１３は、
【００３３】
【数４４】
0004790422.tif 000013
としてａＮ’＝｛ａ１’，…，ａｎ’｝，ｂＮ’＝｛ｂ１’，…，ｂｎ’｝を求め、β（ｘ）の係数がＺｑの元であること、β（ｘ）がｎ−ｔ次であること、およびβ（０）＝Ｈ”（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｒ，ｈ，Ａ０，…，Ａｔ’ ，ａＮ’，ｂＮ’）であるこ
とを確認する（Ｓ５１０）。このステップで、β（ｘ）が（ｎ−ｔ）次であることから、
署名に参加した参加者装置１１０−ｉがｔ台以上であることが確認される。通信部１３２は、ステップＳ４９０からＳ５１０の確認結果がすべてＯＫであれば、署名が正しいことを出力し、そうでないときは署名は正しくないことを出力する（Ｓ５２０）。
【００３４】
また、集合Ｓの各参加者装置１１０−ｉ（ｉ∈Ｓ）は、
ｌｏｇｇ（ｙｉ）＝ｌｏｇｈ（σｉ）
を、例えば、参考文献（[Cha90] David Chaum, Zero-Knowledge Undeniable Signatures,
EUROCRYPT 1990, pp.458-464, 1990.）の方法で証明することで、署名に参加したことを証明できる。集合Ｎ−Ｓの各参加者装置１１０−ｉ（ｉ∈Ｎ−Ｓ）は、
ｌｏｇｇ（ｙｉ）≠ｌｏｇｈ（σｉ）
を、同じ方法で証明することで、署名に参加しなかったことを証明できる（Ｓ５３０）。
【００３５】
このような処理によって、ｎ台（ｎは２以上の整数）の参加者装置に含まれるｓ台の参加者装置が署名を行った場合に、署名をした参加者装置がｔ台以上ｔ’台以下であることが確認できる電子署名を生成できる。
［第２実施形態］
図１４は、本発明のシステム構成例を示している。ｎ台（ｎは２以上の整数）の参加者装置（集合Ｎ）に含まれるｓ台の参加者装置１１０−ｉ（集合Ｓ）が協力して署名を行う。また、署名から、署名をした参加者装置がｔ台以上（集合Ｔ）ｔ’台（集合Ｔ’）以下であることが確認できる署名方法を提供する。第１実施形態との違いは、本実施形態では、集合Ｎの各参加者装置は、署名した参加者装置か署名していない参加者装置かを証明することができない点である。
【００３６】
図１５に参加者装置２１０−ｉの機能構成例を示す。参加者装置２１０−ｉは、秘密鍵ｘｉと公開鍵ｙｉとを生成する鍵生成部９１１−ｉ、ｈ生成手段２１２１−ｉとｘｉ’ 
生成手段２１２２−ｉと使い捨て公開鍵σｉ生成手段２１２３−ｉを有し、使い捨て公開鍵を秘密鍵ｘｉとｘｉ’から生成する鍵生成部２１２−ｉ、任意のＺｑの元ｗｉとｗｉ’を選定するｗｉ・ｗｉ’生成手段２１３１−ｉ、ｗｉとｗｉ’からａｉとｂｉを生成するａｉ・ｂｉ生成手段２１３３−ｉ、Ｚｑの元ｚｉとｚｉ’を、秘密鍵ｘｉとｘｉ’を用いて計算するｚｉ・ｚｉ’生成手段２１３５−ｉ、集合ＴとＴ’とを選定するための集合選定情報を生成する集合選定情報の生成手段１１３５−ｉ、集合Ｔ’−Ｓの使い捨て公開鍵を選定するためのσｉ選定情報を生成するσｉ選定情報の生成手段１１３７−ｉ、任意のＺｑの元ｚｉとｚｉ’とｃｉを選定するためのｚｉ・ｚｉ’・ｃｉ選定情報を生成するｚｉ・ｚｉ’・ｃｉ選定情報の生成手段２１３７−ｉ、任意のＺｑの元ｃｉを選定するためのｃｉ選定情報を生成するｃｉ選定情報の生成手段１１３９−ｉ、情報を公開または集合Ｓの他の参加者装置および署名生成部に送信する通信・公開部２１５−ｉ、情報を記録する記録部２１４−ｉから構成される。
【００３７】
図１６に署名生成部２２０の機能構成例を示す。署名生成部２２０は、集合Ｓの各参加者装置２１０−ｉからの集合選定情報をもとに、Ｔ⊆Ｓ⊆Ｔ’⊆Ｎを満足する集合Ｔと集合Ｔ’の元となる参加者装置を選定する集合Ｔ，Ｔ’選定手段１２１１、集合Ｓの各参加者装置２１０−ｉからのσ選定情報をもとに、集合Ｔ’−Ｓの使い捨て公開鍵を選定するσｉ選定手段１２１３、集合Ｓの各参加者装置からのｚｉ・ｚｉ’・ｃｉ選定情報をもとに、集合Ｎ−Ｓのｚｉとｚｉ’とｃｉを選定するｚｉ・ｚｉ’・ｃｉ選定手段２２１１、集合Ｓの各参加者装置２１０−ｉからのｃｉ選定情報をもとに、集合Ｓ−Ｔのｃｉを選定するｃｉ選定手段２２１３、ｚｉとｚｉ’とｃｉから集合Ｎ−Ｓのａｉとｂｉを生成するａｉ・ｂｉ生成手段２２１６、集合Ｔ’の使い捨て公開鍵から、集合Ｎ−Ｔ’の使い捨て公開鍵σｉを計算するσｉ計算手段２２２２、Ｚｑの元であって、次数（ｎ−ｔ）の多項式β（ｘ）を計算するβ（ｘ）計算手段２２２３、署名を、Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’を用いて生成する署名出力部２２４、他の装置と
通信を行う通信部２２３、情報を記録する記録部２２５から構成される。
【００３８】
図１７は、署名検証部２３０の機能構成例を示す。署名検証部２３０は、署名検証を行いたい任意の装置の内部に備えられる。また、署名検証部２３０は、ｎ，ｔ，ｔ’、集合Ｎの各参加者装置の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝、メッセージｍ、署名σ＝（ｒ，Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’）を受信し、検証結果を出力する通信部２３２、ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙＮ，ｍ）、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ）として、ｈ，Ａ０，…，Ａｔ’が群Ｇの元であること、ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’がＺｑの元であることを確認する群の適正確認手段２３１１、σｉ（ｉ＝１，…，ｎ）がＧの元であることを確認するＡｉの適正確認手段２３１２とａＮ’＝｛ａ１’，…，ａｎ’｝，ｂＮ’＝｛ｂ１’，…，ｂｎ’｝を求め、β（ｘ）がＺｑの元であり、かつｎ−ｔ次であること、β（０）＝Ｈ”（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｈ，Ａ０，…，Ａｔ’ ，ａＮ’，ｂＮ’）であることを確認するβ（ｘ）の適正確認手段２３１
３とから構成される。
【００３９】
図１８に第２実施形態での電子署名システムの処理フローを示す。以下に、処理フローを図１８に従って説明する。
ステップＳ３１０からＳ３３０までは、第１実施形態と同じ処理である。次に、集合Ｓの各参加者装置２１０−ｉ（ｉ＝１，…，ｓ）のｘｉ’生成手段２１２２−ｉで、任意のＺｑの元ｘｉ’を選定する（Ｓ６１０）。集合Ｓの各参加者装置２１０−ｉの鍵生成部２１２−ｉで、使い捨て公開鍵σｉ（ｉ＝１，…，ｓ）を、
【００４０】
【数４５】
0004790422.tif 000014
により生成し、集合Ｓの他の参加者装置２１０−ｉおよび署名生成部２２０に送信する（Ｓ６２０）。ステップＳ３７０とステップＳ３８０は、第１実施形態と同じである。次に、署名生成部２２０のσｉ計算手段２２２２は、集合Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｔ’、ｉ＝ｋ１，…，ｋｔ’）から、
【００４１】
【数４６】
0004790422.tif 000015
として、Ａｉ（ｉ＝０，…，ｔ'）を
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ）
【００４２】
【数４７】
0004790422.tif 000016
と定め、
【００４３】
【数４８】
0004790422.tif 000017
として集合Ｎ−Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｎ−Ｔ’）を計算し、集合Ｓの参加者装置２１０−ｉに送信する（Ｓ６３０）。ステップＳ６３０の処理内容について説明する。
Ａ０＝ｈα（０）Ｒα’（０）
ただし、Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ）
と、
σｉ＝ｈα（ｉ）Ｒα’（ｉ）
ただし、ｉ＝ｋ１，…，ｋｔ’
が成り立つ次数ｔ’の多項式α（ｘ）とα’（ｘ）を求める。そして、α（ｘ）とα’（ｘ）から、集合Ｎ−Ｔ’の使い捨て公開鍵σｉ（ｉ∈Ｎ−Ｔ’）を、
σｉ＝ｈα（ｉ）Ｒα’（ｉ）
により求める。このように使い捨て公開鍵σｉ（ｉ∈Ｎ）求めることによって、集合Ｎの全ての参加者装置２１０−ｉの使い捨て公開鍵σｉが、σｉ＝ｈα（ｉ）Ｒα’（ｉ）を満たす。ところが、α（ｘ）とα’（ｘ）の次数がｔ’であることから、署名に参加した参加者装置２１０−ｉはｔ’以下であることは分かる。しかし、全てのｉ（ｉ＝１，…，ｎ）に対してσｉ＝ｈα（ｉ）Ｒα’（ｉ）が成り立つので、どの参加者装置２１０−ｉが署名に参加したのかは分からない。ただし、実際にはＡ０はＨ’で生成されているから、離散対数α（０）、α’（０）が分からない。したがって、α（ｘ）とα’（ｘ）を直接求めることはできない。そこで、ステップＳ３９０では、Ａｉを用いて計算している。
【００４４】
次に、集合Ｓの各参加者装置２１０−ｉのｗｉ・ｗｉ’生成手段２１３１−ｉで、任意のＺｑの元ｗｉとｗｉ’を選定する（Ｓ６４０）。集合Ｓの各参加者装置２１０−ｉのａｉ・ｂｉ生成手段２１３３−ｉで、
【００４５】
【数４９】
0004790422.tif 000018
によってａｉとｂｉとを生成し、集合Ｓの他の参加者装置２１０−ｉおよび署名生成部２２０に送信する（Ｓ６５０）。集合Ｓの各参加者装置２１０−ｉのｚｉ・ｚｉ’・ｃｉ選定情報の生成手段２１３７−ｉで、任意のＺｑの元ｚｉとｚｉ’とｃｉを選定するためのｚｉ・ｚｉ’・ｃｉ選定情報を生成し、集合Ｓの他の参加者装置２１０−ｉおよび署名生成部２２０に送信する（Ｓ６６０）。署名生成部２２０のｚｉ・ｚｉ’・ｃｉ選定手段２２１１で、前記ｚｉ・ｚｉ’・ｃｉ選定情報をもとに、集合Ｎ−Ｓのｚｉ、ｚｉ’、ｃｉ（ｉ∈Ｎ−Ｓ）を選定し、ａｉ・ｂｉ生成手段２２１６で、
【００４６】
【数５０】
0004790422.tif 000019
により集合Ｎ−Ｓのａｉとｂｉ（ｉ∈Ｎ−Ｓ）とを生成し、生成されたａｉとｂｉとを集合Ｓの参加者装置２１０−ｉに送信する（Ｓ６７０）。次のステップＳ４４０とＳ４５０とは第１実施形態と同じである。次に、署名生成部２２０のβ（ｘ）計算手段２２２３は、
β（０）＝Ｈ”（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｈ，Ａ０，…，Ａｔ’，ａＮ，ｂＮ）
β（ｉ）＝ｃｉ
ただし、ｉ∈Ｎ−Ｔ
を満足するＺｑの元であって、次数（ｎ−ｔ）の多項式β（ｘ）を求め、集合Ｓの参加者装置２１０−ｉに送信する（Ｓ６８０）。集合Ｓの各参加者装置２１０−ｉのｚｉ・ｚｉ’生成手段２１３５−ｉは、
ｚｉ＝ｗｉ−β（ｉ）ｘｉ
ｚｉ’＝ｗｉ’−β（ｉ）ｘｉ’
によってＺｑの元ｚｉとｚｉ’を計算し、集合Ｓの他の参加者装置２１０−ｉおよび署名生成部２２０に送信する（Ｓ６９０）。署名生成部２２０の署名出力部２２４で、署名を、Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’を用いて生成する（Ｓ７００）。なお、説明が冗長となるため説明上は省略しているが、各ステップで生成、計算、受信された情報は、処理のたびに記録部２１４−ｉまたは２２５に記録され、利用される情報は記録部２１４−ｉまたは２２５から読み出される。このような処理によって、α（ｘ）とα’（ｘ）がｔ’次であること、β（ｘ）が（ｎ−ｔ）次であることから、ｔ台以上ｔ’台以下の参加者装置が署名に参加したことを確認できる署名を生成できる。
【００４７】
次に署名検証部２３０での処理フローを説明する。署名検証部１３０の通信部２３２で、ｎ，ｔ，ｔ’、集合Ｎの各参加者装置の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝、メッセージｍ、署名σ＝（Ａ１，…，Ａｔ’，β（ｘ），ｚ１，…，ｚＮ，ｚ１’，…，ｚｎ’）を受信し、群の適正確認部２３１１で、
ｈ＝Ｈ（ｎ，ｔ，ｔ’，ｙＮ，ｍ）
Ａ０＝Ｈ’（ｎ，ｔ，ｔ’，ｙＮ，ｍ）
を計算し、ｈ，Ａ０，…，Ａｔ’が群Ｇの元であること、ｚ１，…，ｚｎ，ｚ１’，…，ｚｎ’がＺｑの元であることを確認する（Ｓ７１０）。Ａｉの適正確認部２３１２は、
【００４８】
【数５１】
0004790422.tif 000020
で求められるσｉ（ｉ＝１，…，ｎ）がＧの元であることを確認する（Ｓ７２０）。このステップで、Ａｉがｉ＝０，…，ｔ’の（ｔ’＋１）個しかないことから、署名に参加した参加者装置２１０−ｉがｔ’台以下であることも確認される。次に、β（ｘ）の適正確認部２３１３は、
【００４９】
【数５２】
0004790422.tif 000021
としてａＮ’＝｛ａ１’，…，ａｎ’｝，ｂＮ’＝｛ｂ１’，…，ｂｎ’｝を求め、β（ｘ）の係数がＺｑの元であること、β（ｘ）がｎ−ｔ次であること、およびβ（０）＝Ｈ”（ｎ，ｔ，ｔ’，ｙＮ，ｍ，ｈ，Ａ０，…，Ａｔ’ ，ａＮ’，ｂＮ’）であることを
確認する（Ｓ７３０）。このステップで、β（ｘ）が（ｎ−ｔ）次であることから、署名に参加した参加者装置２１０−ｉがｔ台以上であることが確認される。通信部１３２は、ステップＳ７１０からＳ７３０の確認結果がすべてＯＫであれば、署名が正しいことを出力し、そうでないときは署名は正しくないことを出力する（Ｓ７４０）。
【００５０】
第１実施形態では、集合Ｓの各参加者装置１１０−ｉ（ｉ∈Ｓ）は、
ｌｏｇｇ（ｙｉ）＝ｌｏｇｈ（σｉ）
を、例えば、参考文献（[Cha90] David Chaum, Zero-Knowledge Undeniable Signatures,
EUROCRYPT 1990, pp.458-464, 1990.）の方法で証明することで、署名に参加したことを証明できた。また、集合Ｎ−Ｓの各参加者装置１１０−ｉ（ｉ∈Ｎ−Ｓ）は、
ｌｏｇｇ（ｙｉ）≠ｌｏｇｈ（σｉ）
を、同じ方法で証明することで、署名に参加しなかったことを証明できた。しかし、第２実施形態では、集合Ｎの全ての参加者装置２１０−ｉ（ｉ∈Ｎ）に対して
【００５１】
【数５３】
0004790422.tif 000022
が成り立つｘｉ’が存在するので、その式を証明できることが署名に参加したことを示していない。したがって、参加者装置２１０−ｉ（ｉ＝１，…，ｎ）は、署名に参加したか否かを証明することができない。
このような処理によって、ｎ台（ｎは２以上の整数）の参加者装置に含まれるｓ台の参加者装置が署名を行った場合に、署名をした参加者装置がｔ台以上ｔ’台以下であることが確認できる電子署名を生成できる。
【００５２】
なお、本発明は、コンピュータ本体とコンピュータプログラムとして実行することが可能であるし、デジタルシグナルプロセッサや専用LSIに実装して実現することも可能であ
る。
【００５３】
以下では、上記の参加者装置が１台に限定された場合についての説明を行う。この場合、署名鍵の重複使用を防止できる。なぜなら、上記においてｔ＝ｔ’＝１の場合に相当し、署名鍵の重複使用者（重複署名者とも云う。）を追跡できるからである。
そこで、この重複使用者追跡可能署名方式について、説明の便宜から上記第１実施形態を基礎として説明を行うことにする。
なお、このような重複使用者追跡可能署名方式が要請されるのは、署名鍵を持っている署名者は何回でも匿名で署名できてしまい、例えば、電子投票（参考文献： Atsushi Fujioka, Tatsuaki Okamoto, Kazuo ohta, "A Practical Secret Voting Scheme for Large Scale Elections", ASIACRYPT, pp.244-251, 1992.）、電子現金（参考文献： Stefan Brands, "Untraceable Off-line Cash in Wallets with Observers (Extended Abstract)", CRYPTO, pp.302-318, 1993.）に応用した場合、重複投票、電子現金の重複使用が可能となってしまうからである。
また、この重複使用者追跡可能署名方式は、同一署名者が同一メッセージに署名を添付して複数回発行した署名付きメッセージも検出可能なものであるから、この点についても併せて説明する。なお、以下の説明では、このことを「コピー署名の検出」、「署名のコピーの検出」などとも云うことにする。
【００５４】
重複使用者追跡可能署名方式の説明を行うにあたり、改めて定義を示しておく。Ｇを離散対数問題の難しい素数位数ｑの巡回群とし、ｇをその生成元とする。巡回群Ｇの例としては、例えば乗法群Ｚｐ＊〔ｑ＝ｐ−１〕、楕円曲線上の点で定義される群などが上げられる。
【００５５】
また、Ｈ、Ｈ’、Ｈ”を、Ｈ：｛０，１｝＊→Ｇ、Ｈ’：｛０，１｝＊→Ｇ、Ｈ”：｛０，１｝＊→Ｚｑなる性質を有するハッシュ関数とする。ここで｛０，１｝＊は、任意のビット長のバイナリ系列を表し、Ｚｑは、加法群を表す。
【００５６】
さらに、署名者はｎ人であるとし、これら署名者の集合をＮ＝｛１，・・・，ｎ｝とする。各署名者は後述する署名装置（上記の参加者装置に相当する。）を用いて署名する。ここでは、署名者ｉのＩＤ（identification）をｉ（ｉ＝１，・・・，ｎ）とする。
以下では、ｙＮ＝｛ｙｉ｝ｉ∈Ｎなどと略記する。
【００５７】
［情報公開サーバ装置］
まず、情報公開サーバ装置（以下、「情報公開サーバ」という。）について説明する。
図１９は、情報公開サーバ（１０００）のハードウェア構成を例示した構成ブロック図である。
【００５８】
図１９に例示するように、情報公開サーバ（１０００）は、キーボードなどが接続可能な入力部（１１００）、液晶ディスプレイなどが接続可能な出力部（１２００）、情報公開サーバ（１０００）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３００）、ＣＰＵ（Central Processing Unit）（１４００）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（１５００）、ＲＯＭ（１６００）やハードディスクである外部記憶装置（１７００）並びにこれらの入力部（１１００）、出力部（１２００）、通信部（１３００）、ＣＰＵ（１４００）、ＲＡＭ（１５００）、ＲＯＭ（１６００）、外部記憶装置（１７００）間のデータのやり取りが可能なように接続するバス（１８００）を有している。また必要に応じて、情報公開サーバ（１０００）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００５９】
情報公開サーバ（１０００）の外部記憶装置（１７００）には、情報公開のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶されるとする。
【００６０】
より具体的には、情報公開サーバ（１０００）の外部記憶装置（１７００）〔あるいはＲＯＭなど〕には、情報公開サーバ（１０００）にアクセスした署名装置などに対して外部記憶手段（１７００）に保存記憶される情報を提供するためのプログラム、情報公開サーバ（１０００）にアクセスした署名装置などから情報を取得して外部記憶手段（１７００）に保存記憶するためのプログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムなども適宜に保存しておく。
【００６１】
情報公開サーバ（１０００）では、外部記憶装置（１７００）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（１５００）に読み込まれて、ＣＰＵ（１４００）で解釈実行・処理される。その結果、ＣＰＵ（１４００）が所定の機能（情報提供部、情報取得部）を実現することで、情報公開が実現される。
【００６２】
情報公開サーバ（１０００）は、署名装置などからのアクセスを許可し、当該装置に対して、情報公開サーバにおける所定の情報（後述する公開鍵などである。）を提供し（「公開する」ともいう。）、あるいは、当該装置から情報を取得するものである。
【００６３】
［署名装置］
署名装置について説明する。
図２０は、署名装置（２０００）のハードウェア構成を例示した構成ブロック図である。
【００６４】
図２０に例示するように、署名装置（２０００）は、キーボードなどが接続可能な入力部（２１００）、液晶ディスプレイなどが接続可能な出力部（２２００）、署名装置（２０００）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（２３００）、ＣＰＵ（Central Processing Unit）（２４００）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（２５００）、ＲＯＭ（２６００）やハードディスクである外部記憶装置（２７００）並びにこれらの入力部（２１００）、出力部（２２００）、通信部（２３００）、ＣＰＵ（２４００）、ＲＡＭ（２５００）、ＲＯＭ（２６００）、外部記憶装置（２７００）間のデータのやり取りが可能なように接続するバス（２８００）を有している。また必要に応じて、署名装置（２０００）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００６５】
署名装置（２０００）の外部記憶装置（２７００）には、署名のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。
【００６６】
より具体的には、署名装置（２）の外部記憶装置（２７）〔あるいはＲＯＭなど〕には、後述する値ｈ、σｉ、σｊ、Ａ０、Ａ１、ａｉ、ｂｉ、ａｊ、ｂｊ、ｚｉ、ｃｉを生成するためのプログラム、群の中から元を任意に選択するためのプログラム、署名を生成するためのプログラムおよびこれらのプログラムの処理において必要となるデータ（例えばメッセージｍである。）などが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存しておく。
【００６７】
署名装置（２０００）では、外部記憶装置（２７００）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（２５００）に読み込まれて、ＣＰＵ（２４００）で解釈実行・処理される。その結果、ＣＰＵ（２４００）が所定の機能（ｈ生成部、σｉ生成部、σｊ生成部、Ａ０生成部、Ａ１生成部、ａｉ生成部、ｂｉ生成部、ａｊ生成部、ｂｊ生成部、ｚｉ生成部、ｃｉ生成部、元選択部、署名生成部、制御部）を実現することで、署名が実現される。
【００６８】
［検証装置］
検証装置について説明する。検証装置は重複署名者の追跡および署名のコピーの検出にも用いられるとする。検証装置とは異なる物理的実態（装置）を重複署名者追跡兼コピー署名検出装置とすることでもよい。なお、重複署名者追跡兼コピー署名検出装置を各別の物理的実態（装置）として構成する−つまり、重複署名者追跡装置およびコピー署名検出装置である−としてもよいが、下記の説明から明らかになるとおり、実質的な機能・処理は両者で変わらないので、検証装置から機能的に分離するならば、機能的一体性の認められる重複署名者追跡兼コピー署名検出装置とするが一般的になると考えられる。
図２１は、検証装置（３０００）のハードウェア構成を例示した構成ブロック図である。
【００６９】
図２１に例示するように、検証装置（３０００）は、キーボードなどが接続可能な入力部（３１００）、液晶ディスプレイなどが接続可能な出力部（３２００）、検証装置（３０００）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（３３００）、ＣＰＵ（Central Processing Unit）（３４００）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（３５００）、ＲＯＭ（３６００）やハードディスクである外部記憶装置（３７００）並びにこれらの入力部（３１００）、出力部（３２００）、通信部（３３００）、ＣＰＵ（３４００）、ＲＡＭ（３５００）、ＲＯＭ（３６００）、外部記憶装置（３７００）間のデータのやり取りが可能なように接続するバス（３８００）を有している。また必要に応じて、検証装置（３０００）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００７０】
検証装置（３０００）の外部記憶装置（３７００）には、検証（および重複署名者の追跡、コピー署名の検出）のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。
【００７１】
より具体的には、検証装置（３０００）の外部記憶装置（３７００）〔あるいはＲＯＭなど〕には、後述するラベルＬから所定の値を抽出するためのプログラム、後述する値ｈ、σＮ、Ａ０、ａＮ、ｂＮを生成するためのプログラム、元ｚを検証するためのプログラム、Ａ１を検証するためのプログラム、元ｃを検証するためのプログラム、公開鍵を検証するためのプログラム、元ｃの総和と所定の値との一致を判定するためのプログラム、重複臨時公開鍵の検証を行うためのプログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存しておく。
【００７２】
検証装置（３０００）では、外部記憶装置（３７００）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（３５００）に読み込まれて、ＣＰＵ（３４００）で解釈実行・処理される。その結果、ＣＰＵ（３４００）が所定の機能（ラベル抽出部、ｈ生成部、σＮ生成部、Ａ０生成部、ａＮ生成部、ｂＮ生成部、ｚ検証部、ｃ検証部、Ａ１検証部、公開鍵検証部、判定部、重複臨時公開鍵検証部、制御部）を実現することで、署名検証、重複署名者の追跡、コピー署名の検出が実現される。
【００７３】
［システム構成］
重複使用者追跡可能署名方式におけるシステム構成について説明する。
図２２は、重複使用者追跡可能署名方式におけるシステム構成を示す図である。
【００７４】
ここで説明する重複使用者追跡可能署名方式では、説明の便宜から、公開鍵基盤の一例であるＰＫＩ（Public Key Infrastructure）を前提にしている。ＰＫＩは、日本国においても「電子署名及び認証業務に関する法律（平成１２年法律第１０２号）」が制定されたことなども相まって普及整備が進んでいる公知技術であるから（例えば参考文献１参照。）、その詳細の説明は省略する。なお、重複使用者追跡可能署名方式は、日本国におけるＰＫＩを前提とすることに限定するものではなく、例えば公知の電子公開掲示板でもよいし、およそ公開鍵基盤が普及整備されているならば、諸外国やあるいは公開鍵基盤の規模・性質（国家・地方・地域のような比較的大きな規模や例えば企業・大学・自治体・団体のような比較的小さな規模、社会基盤としての公的性質や私企業内における私的性質）などを問わず適用可能である。なお、日本国における政府認証基盤（ＧＰＫＩ：Government Public Key Infrastructure）については、参考文献２を参照のこと。
（参考文献１）  独立行政法人  情報処理推進機構、”ＰＫＩ関連技術解説”、［平成１８年１月１６日検索］、
インターネット  <URL : http://www.ipa.go.jp/security/pki/>
（参考文献２）  日本国総務省行政管理局、”政府認証基盤（ＧＰＫＩ）”、［平成１８年１月１６日検索］、
インターネット  <URL : http://www.gpki.go.jp/>
【００７５】
図２２に示すＣＡ（Certification Authority）（４０００）は、ＰＫＩにおける認証局を表している。
情報公開サーバ（１０００）、１つ以上の署名装置（２０００−１），（２０００−２），・・・，（２０００−ｎ）、検証装置（３０００）、ＣＡ（４０００）は、ネットワーク（５０００）を介して相互に通信可能に接続されている。
【００７６】
［鍵生成］
重複使用者追跡可能署名方式を実施するための準備（鍵生成）について説明する（図４参照）。
まず、署名者ｉは、秘密鍵ｓｋｉ＝ｘｉを群Ｚｑの元から選択し、巡回群Ｇの生成元ｇを用いて、公開鍵ｐｋｉ＝ｙｉ＝ｇ＾ｘｉを生成する。記号＾は、べき乗を表す。署名者ｉは、署名者ｉに固有の公開鍵ｙｉをＣＡ（４０００）に送信し、ＣＡ（４０００）に公開鍵ｙｉを登録する。
【００７７】
次に、情報公開サーバ（１０００）は、ＣＡ（４０００）にネットワーク（５０００）経由でアクセスし、各署名者の公開鍵ｙ１，ｙ２，・・・，ｙｎを取得する。
【００７８】
情報公開サーバ（１０００）は、取得した各署名者の公開鍵ｙ１，ｙ２，・・・，ｙｎを外部記憶装置（１７００）に記憶保存する。
【００７９】
情報公開サーバ（１０００）は、各署名装置からアクセスがあった場合に、これらのデータ（公開鍵ｙ１，ｙ２，・・・，ｙｎ）を、情報提供部（８０００）によって、その通信部（１３００）を通じて、アクセスした署名装置に対して送信する。また、署名生成処理後においては、外部記憶装置（１７００）に保存記憶されている署名なども、情報提供部（８０００）によって、その通信部（１３００）を通じて、アクセスした検証装置に対して送信する。
【００８０】
なお、後述するラベルＬの生成において、例えば全署名者の公開鍵をｙ１，ｙ２，・・・，ｙｎを用いない場合には、情報公開サーバ（１０００）やＰＫＩを不要として、検証装置（３０００）に複数の署名装置（１０００）が相互に通信可能に接続する所謂サーバ−クライアント型のシステム構成とすることも可能である。
【００８１】
以下、図２３〜図３０を参照して、重複使用者追跡可能署名方式の処理を説明する。
図２３は、情報公開サーバ（１０００）における処理フローを示す図である。
図２４は、署名装置（２０００）の機能構成例を示す図である。
図２５は、署名装置（２０００）における処理フローを示す図である（その１）。
図２６は、署名装置（２０００）における処理フローを示す図である（その２）。
図２７は、署名後における状態を示す図である。
図２８は、検証装置（３０００）の機能構成例を示す図である。
図２９は、検証装置（３０００）における処理フローを示す図である（その１）。
図３０は、検証装置（３０００）における処理フローを示す図である（その２）。
【００８２】
［署名］
まず、署名装置による署名について説明する。
以下では、署名者ｉは、署名装置ｉ（２０００）によって署名を行うとする。
署名装置ｉ（２０００）の外部記憶装置（２７００）には、署名装置ｉ（２０００）のＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘｉ、全ての署名者の公開鍵ｙＮ、ラベルＬ、メッセージｍ、全署名者の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎが予め保存記憶されているとする。
【００８３】
署名装置ｉ（２０００）は、制御部（６１３０）の制御によって、その通信部（２３００）を通じて、情報公開サーバ（１０００）にアクセスし、情報公開サーバ（１０００）の通信部（１３００）を通じて送信された（ステップＳ１ｓ）、情報公開サーバ（１０００）の外部記憶装置（１７００）に記憶される全ての署名者の公開鍵｛ｙ１，…，ｙｎ｝〔以後、全ての署名者の公開鍵｛ｙ１，…，ｙｎ｝をｙＮと略記する。〕を受信し、これを署名装置ｉ（２０００）の外部記憶装置（２７００）に保存記憶する。また、全ての投票者の公開鍵ｙＮ（以下、「リストｙＮ」とも云う。）の個数ｎも、署名装置ｉの外部記憶装置（２７）に保存記憶する。また、署名装置ｉ（２０００）は、制御部（６１３０）の制御によって、自身の外部記憶装置（２７００）に、或る文字列Ｌ０＝｛０，１｝＊およびラベルＬ＝（Ｌ０，ｙＮ）について保存記憶する（ステップＳ２）。ここで、ラベルＬは、文字列Ｌ０および公開鍵のリストｙＮをバイナリ系列で結合した値Ｌ０‖ｙＮ（＝Ｌ０‖ｙ１‖ｙ２‖・・・‖ｙｎ）〔記号‖はバイナリ系列同士の結合を表す。〕である。以下、特に断りの無い限り、（Ｘ，Ｙ）なる表記はＸおよびＹのバイナリ系列の結合を表すとする。なお、文字列Ｌ０およびラベルＬについては、全ての署名装置に共通とする。従って、正しく文字列Ｌ０およびラベルＬを使用しない署名装置は正規の署名装置ではないことになる。なお、文字列Ｌ０およびラベルＬを情報公開サーバ（１０００）で公開するようにしてもよい。この場合、情報公開サーバのラベル生成部〔所定のプログラムがＣＰＵ（１４００）で解釈・実行されて実現される。〕が、文字列Ｌ０およびリストｙＮからラベルＬを生成して、この文字列Ｌ０およびリストｙＮを外部記憶装置（１７００）に保存記憶する。
【００８４】
予め、署名装置ｉ（２０００）は、制御部（６１３０）の制御の下、外部記憶装置（２７００）から、署名装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘｉ、全ての署名者の公開鍵ｙＮ、ラベルＬ、メッセージｍ、全署名者の公開鍵ｙＮの個数ｎを読み込み、それぞれをＲＡＭ（２５００）の所定の格納領域に格納しておく。以下、「ＲＡＭから○○を読み込む」旨の説明をした場合は、「ＲＡＭにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【００８５】
まず、署名装置ｉ（２０００）のｈ生成部（６０００）は、ＲＡＭ（２５００）からＬを読み込み、ｈ＝Ｈ（Ｌ）を演算し、この演算結果ｈをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ３）。なお、ｈは巡回群Ｇの元、即ちｈ∈Ｇであることに留意する。このｈが、固有臨時公開鍵生成因子に相当する。
【００８６】
次に、署名装置ｉ（２０００）のσｉ生成部（６０１０）は、ＲＡＭ（２５００）からｈ、ｘｉをそれぞれ読み込み、σｉ＝ｈ＾ｘｉを演算し、この演算結果σｉをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ４）。なお、σｉは巡回群Ｇの元、即ちσｉ∈Ｇであることに留意する。このσｉは、署名装置ｉの固有臨時公開鍵に相当する。
【００８７】
続いて、署名装置ｉ（２０００）のＡ０生成部（６０２０）は、ＲＡＭ（２５００）からＬ、ｍをそれぞれ読み込み、Ａ０＝Ｈ’（Ｌ，ｍ）を演算し、この演算結果Ａ０をＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ５）。なお、Ａ０は巡回群Ｇの元、即ちＡ０∈Ｇであることに留意する。このＡ０が、撹乱因子生成因子に相当する。
【００８８】
次に、署名装置ｉ（２０００）のＡ１生成部（６０３０）は、ＲＡＭ（２５００）からｉ、Ａ０、σｉをそれぞれ読み込み、Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を演算し、この演算結果Ａ１をＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ６）。Ａ１は巡回群Ｇの元、即ちＡ１∈Ｇであることに留意する。このＡ１が、撹乱因子に相当する。
【００８９】
次に、署名装置ｉ（２０００）のσｊ生成部（６０４０）は、ＲＡＭ（２５００）からＡ０、Ａ１、ｎ、ｉをそれぞれ読み込み、σｊ＝Ａ０（Ａ１＾ｊ）を演算し、この演算結果σｊをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ７）。ここでｊは、ｊ∈Ｎ−｛ｉ｝、即ち、ｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎである。なお、σｊは巡回群Ｇの元、即ちσｊ∈Ｇであることに留意する。このσｊは、署名装置ｉが作った署名装置ｉ以外の署名装置の撹乱臨時公開鍵に相当する。
【００９０】
さらに、Ａ０＝ｈ＾α（０）かつσｆ＝ｈ＾α（ｆ）〔但し、ｆ∈Ｎ〕を満足する次数１の多項式α（ｘ）∈Ｚｑ［ｘ］が存在することに留意しなければならない。なお、記号α（ｘ）∈Ｚｑ［ｘ］は、多項式α（ｘ）が、群Ｚｑの元を係数に有する多項式であることを表す。
このことを換言すると、ｌｏｇｈ（σｊ）が、ｌｏｇｈ（Ａ０）およびｘｉ＝ｌｏｇｈ（σｉ）で定まる直線上に存在することを意味する。
【００９１】
続いて、ラベルＬ、固有臨時公開鍵生成因子ｈ、臨時公開鍵σＮ（臨時公開鍵σＮは、固有臨時公開鍵と撹乱臨時公開鍵とを合わせたものである。つまり、σＮ＝｛σ１，σ２，・・・，σｉ−１，σｉ，σｉ＋１，・・・，σｎ｝である。）について、ｌｏｇｇ（ｙｉ’）＝ｌｏｇｈ（σｉ’）を満たすｉ’∈Ｎが存在することを、非対話ゼロ知識証明（non-interactive zero-knowledge proof of knowledge : NIZK法）によって証明するための非対話ゼロ知識証明情報を生成可能な非対話ゼロ知識証明情報生成因子ｃＮ、ｚＮを求める。より具体的に説明すると、署名装置ｉ（２０００）が、その秘密鍵ｘｉを用いて固有臨時公開鍵σｉを生成したこと、即ち、ｌｏｇｇ（ｙｉ）＝ｌｏｇｈ（σｉ）が成立することを、非対話ゼロ知識証明によって検証装置に証明することが可能な情報を求めるのである。
なお、非対話ゼロ知識証明は公知の方法でよく、下記の非対話ゼロ知識証明に限定するものではない。
【００９２】
署名装置ｉ（２０００）の元選択部（６０５０）は、群Ｚｑの元の中から任意に１つの元ｗｉを選択し、この元ｗｉをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ８）。
【００９３】
次に、署名装置ｉ（２０００）のａｉ生成部（６０６０）は、ＲＡＭ（２５００）からｇ、ｗｉをそれぞれ読み込み、ａｉ＝ｇ＾ｗｉを演算し、この演算結果ａｉをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ９）。なお、ａｉは巡回群Ｇの元、即ちａｉ∈Ｇであることに留意する。
【００９４】
次に、署名装置ｉ（２０００）のｂｉ生成部（６０７０）は、ＲＡＭ（２５００）からｈ、ｗｉをそれぞれ読み込み、ｂｉ＝ｈ＾ｗｉを演算し、この演算結果ｂｉをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ１０）。なお、ｂｉは巡回群Ｇの元、即ちｂｉ∈Ｇであることに留意する。
【００９５】
続いて、署名装置ｉ（２０００）の元選択部（６０５０）は、ＲＡＭ（２５００）からｉ、ｎをそれぞれ読み込み、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、群Ｚｑの元の中から任意に２つの元ｚｊ、ｃｊを選択し、これらの元ｚｊ、ｃｊをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ１１）。
【００９６】
次に、署名装置ｉ（２０００）のａｊ生成部（６０８０）は、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、ＲＡＭ（２５００）からｇ、ｚｊ、ｃｊ、ｙｊをそれぞれ読み込み（ｙｊは、ｙＮからｙｉを除いたものである。）、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）を演算し、この演算結果ａｊをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ１２）。なお、ａｊは巡回群Ｇの元、即ちａｊ∈Ｇであることに留意する。
【００９７】
次に、署名装置ｉ（２０００）のｂｊ生成部（６０９０）は、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、ＲＡＭ（２５００）からｈ、ｚｊ、ｃｊ、σｊをそれぞれ読み込み、ｂｊ＝（ｈ＾ｚｊ）×（σｊ＾ｃｊ）を演算し、この演算結果ｂｊをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ１３）。なお、ｂｊは巡回群Ｇの元、即ちｂｊ∈Ｇであることに留意する。
【００９８】
以上の各処理で生成された、ａＮ＝｛ａ１，ａ２，・・・，ａｎ｝、ｂＮ＝｛ｂ１，ｂ２，・・・，ｂｎ｝が非対話ゼロ知識証明情報である。
【００９９】
次に、署名装置ｉ（２０００）のｃｉ生成部（６１００）は、ＲＡＭ（２５００）からｍ、Ｌ、Ａ０、Ａ１、ａＮ、ｂＮ、ｃｊ〔ｊ∈Ｎ−｛ｉ｝〕を読み込み、ｃｉ＝Ｈ”（Ｌ，ｍ，Ａ０，Ａ１，ａＮ，ｂＮ）−Σｊ∈Ｎ−｛ｉ｝ｃｊ  （ｍｏｄ  ｑ）＝Ｈ”（Ｌ，ｍ，Ａ０，Ａ１，ａＮ，ｂＮ）−（ｃ１＋ｃ２＋・・・＋ｃｉ−１＋ｃｉ＋１＋・・・＋ｃｎ）  （ｍｏｄ  ｑ）を演算し、この演算結果ｃｉをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ１４）。なお、ｃｉは、群Ｚｑの元であることに留意する。
ハッシュ関数Ｈ”の入力には、ラベルＬおよびメッセージｍが含まれているが、いずれか一方を含むようにしても、あるいは、両者を含まないようにすることもできる。また、ハッシュ関数Ｈ”の入力は、この実施形態に限定する趣旨ではなく、他の非対話ゼロ知識証明情報を入力に含めるようにしてもよい。この明細書では、ハッシュ関数Ｈ”の入力は、Ｌ，ｍ，Ａ０，Ａ１，ａＮ，ｂＮとする。
【０１００】
続いて、署名装置ｉ（２０００）のｚｉ生成部（６１１０）は、ＲＡＭ（２５００）からｎ、ｉ、ｗｉ、ｘｉ、ｃｉをそれぞれ読み込み、ｚｉ＝ｗｉ−ｃｉ×ｘｉ  （ｍｏｄ  ｑ）を演算し、この演算結果ｚｉをＲＡＭ（２５００）の所定の格納領域に格納する（ステップＳ１５）。なお、ｚｉは群Ｚｑの元、即ちｚｉ∈Ｚｑであることに留意する。
【０１０１】
以上の各処理で生成された、ｃＮ＝｛ｃ１，ｃ２，・・・，ｃｎ｝、ｚＮ＝｛ｚ１，ｚ２，・・・，ｚｎ｝が非対話ゼロ知識証明情報生成因子である。
【０１０２】
続いて、署名装置ｉ（２０００）の署名生成部（６１２０）は、ＲＡＭ（２５００）からＡ１、ｃｉ、ｃｊ、ｚｉ、ｚｊをそれぞれ読み込み、このうち、Ａ１、ｃｉ、ｃｊ、ｚｉ、ｚｊの組み合わせを、署名装置ｉにおけるラベルＬおよびメッセージｍの組に対する署名ξｉとする（ステップＳ１６）。即ち、ξｉ＝｛Ａ１、ｃＮ、ｚＮ｝とする。ここでｃＮは、ｃＮ＝｛ｃ１，ｃ２，・・・，ｃｎ｝、ｚＮは、ｚＮ＝｛ｚ１，ｚ２，・・・，ｚｎ｝である。
【０１０３】
続いて、署名装置ｉ（２０００）は、制御部（６１３０）の制御によって、通信部（２３００）を通じて、ステップＳ１６で生成された署名ξｉ＝｛Ａ１、ｃＮ、ｚＮ｝並びにラベルＬおよびメッセージｍの組を、匿名通信路を経由して情報公開サーバ（１０００）に送信する（ステップＳ１７）。
【０１０４】
情報公開サーバ（１０００）は、情報取得部（８０１０）によって、その通信部(１３００）を通じて、ステップＳ１７で送信された署名ξｉ＝｛Ａ１、ｃＮ、ｚＮ｝並びにラベルＬおよびメッセージｍの組を受信し、署名ξｉ＝｛Ａ１、ｃＮ、ｚＮ｝並びにラベルＬおよびメッセージｍを対応付けて外部記憶装置（１７００）に保存記憶する（ステップＳ２ｓ）。
【０１０５】
［検証］
続いて、検証装置（３０００）による署名の検証処理について説明する。
検証装置（３０００）の外部記憶装置（３７００）には、巡回群Ｇの生成元ｇが予め保存記憶されているとする。また、全署名者の公開鍵ｙＮの個数ｎも、検証装置（３０００）の外部記憶装置（３７００）に保存記憶されているとする。
【０１０６】
検証装置（３０００）は、制御部（７１１０）の制御によって、その通信部（３３００）を通じて、情報公開サーバ（１０００）にアクセスし、情報公開サーバ（１０００）の通信部（１３００）を通じて送信された（ステップＳ３ｓ）、情報公開サーバ（１０００）の外部記憶装置（１７００）に記憶される、ある署名装置で作られた署名ξ＝｛Ａ１、ｃＮ、ｚＮ｝、この署名ξに対応するラベルＬおよびメッセージｍを受信し、これらを検証装置（３０００）の外部記憶装置（３７００）に保存記憶する（ステップＳ１８）。ここで、「ある署名装置で作られた署名ξ・・・メッセージｍ」としたのは、署名およびこの署名ξに対応するラベルＬおよびメッセージｍには署名装置を特定する情報が含まれていないため、検証装置の立場からすると、どの署名装置で作られた署名であるかを知ることができないからである。以下では、情報公開サーバ（１０００）から取得した１個の署名およびこの署名ξに対応するラベルＬおよびメッセージｍについて検証を行う処理を説明する。
【０１０７】
検証装置（３０００）は、制御部（７１１０）の制御によって、外部記憶装置（３７００）から、巡回群Ｇの生成元ｇ、署名ξ＝｛Ａ１、ｃＮ、ｚＮ｝、この署名ξに対応するラベルＬおよびメッセージｍの組、全署名者の公開鍵ｙＮの個数ｎを読み込み、それぞれをＲＡＭ（３５００）の所定の格納領域に格納する。
【０１０８】
次に、検証装置（３０００）のラベル抽出部（７１５０）は、ＲＡＭ（３５００）からラベルＬを読み込み、文字列Ｌ０およびリストｙＮを抽出し、抽出した文字列Ｌ０およびリストｙＮをＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ１９）。
【０１０９】
次に、検証装置（３０００）のＡ１検証部（７０２０）は、ＲＡＭ（３５００）からＡ１を読み込み、Ａ１が巡回群Ｇの元であるか否かを検証する（ステップＳ２０）。この検証に合格しなかった場合、署名ξ＝｛Ａ１、ｃＮ、ｚＮ｝は不正な署名であることが判明して検証処理を終了する（ステップＳ５０）。この検証に合格したら、制御部（７１１０）は、以下の処理を実行するように制御する。
【０１１０】
続いて、検証装置（３０００）のｃ検証部（７０４０）は、ＲＡＭ（３５００）からｃＮ（＝｛ｃ１，ｃ２，・・・，ｃｎ｝）をそれぞれ読み込み、各ｃｆ（ｆ＝１，２，・・・，ｎ）が群Ｚｑの元であるか否かを検証する（ステップＳ２１）。この検証に合格しなかった場合、署名ξは不正な署名であることが判明して検証処理を終了する（ステップＳ５０）。この検証に合格したら、制御部（７１１０）は、以下の処理を実行するように制御する。
【０１１１】
続いて、検証装置（３０００）のｚ検証部（７０６０）は、ＲＡＭ（３５００）からｚＮ（＝｛ｚ１，ｚ２，・・・，ｚｎ｝）をそれぞれ読み込み、各ｚｆ（ｆ＝１，２，・・・，ｎ）が群Ｚｑの元であるか否かを検証する（ステップＳ２２）。この検証に合格しなかった場合、署名ξは不正な署名であることが判明して検証処理を終了する（ステップＳ５０）。この検証に合格したら、制御部（７１１０）は、以下の処理を実行するように制御する。
【０１１２】
続いて、検証装置（３０００）の公開鍵検証部（７０５０）は、ＲＡＭ（３５００）からリストｙＮ（＝｛ｙ１，ｙ２，・・・，ｙｎ｝）をそれぞれ読み込み、各ｙｆ（ｆ＝１，２，・・・，ｎ）が群Ｇの元であるか否かを検証する（ステップＳ２３）。この検証に合格しなかった場合、署名ξは不正な署名であることが判明して検証処理を終了する（ステップＳ５０）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。
【０１１３】
ステップＳ２０、Ｓ２１、Ｓ２２、Ｓ２３の各処理において移行するステップＳ５０の終了処理は、署名ξがそもそも適正な群の元を用いていないことに起因するものである。従って、後述の重複署名者追跡処理は行わない。
【０１１４】
次に、検証装置（３０００）のｈ生成部（７０００）は、ＲＡＭ（３５００）からラベルＬを読み込み、ｈ＝Ｈ（Ｌ）を演算し、この演算結果ｈをＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ２４）。なお、ｈは巡回群Ｇの元、即ちｈ∈Ｇであることに留意する。このｈは、署名装置で生成される固有臨時公開鍵生成因子に等しい。
【０１１５】
次に、検証装置（３０００）のＡ０生成部（７０１０）は、ＲＡＭ（３５００）からラベルＬ、メッセージｍをそれぞれ読み込み、Ａ０＝Ｈ’（Ｌ，ｍ）を演算し、この演算結果Ａ０をＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ２５）。なお、Ａ０は巡回群Ｇの元、即ちＡ０∈Ｇであることに留意する。このＡ０は、署名装置で生成される撹乱因子生成因子に等しい。
【０１１６】
次に、検証装置（３０００）のσＮ生成部（７０３０）は、ＲＡＭ（３５００）からＡ０、Ａ１、ｎをそれぞれ読み込み、σｆ＝Ａ０（Ａ１＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果σＮ（＝｛σ１，σ２，・・・，σｎ｝）をＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ２６）。なお、σＮ（＝｛σ１，σ２，・・・，σｎ｝）はそれぞれ巡回群Ｇの元、即ちσｆ∈Ｇであることに留意する。このσＮは、署名装置の固有臨時公開鍵および署名装置で生成される撹乱臨時公開鍵を合わせた臨時公開鍵である。
【０１１７】
続いて、検証装置（３０００）のａＮ生成部（７０７０）は、ＲＡＭ（３５００）からｎ、ｇ、ｃＮ、ｚＮ、ｙＮをそれぞれ読み込み、ａｆ＝（ｇ＾ｚｆ）×（ｙｆ＾ｃｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ａＮ（＝｛ａ１，ａ２，・・・，ａｎ｝）をＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ２７）。なお、ａＮ（＝｛ａ１，ａ２，・・・，ａｎ｝）はそれぞれ巡回群Ｇの元、即ちａｆ∈Ｇであることに留意する。
【０１１８】
続いて、検証装置（３０００）のｂＮ生成部（７０８０）は、ＲＡＭ（３５００）からｎ、ｈ、ｃＮ、ｚＮ、σＮをそれぞれ読み込み、ｂｆ＝（ｈ＾ｚｆ）×（σｆ＾ｃｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ｂＮ（＝｛ｂ１，ｂ２，・・・，ｂｎ｝）をＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ２８）。なお、ｂＮ（＝｛ｂ１，ｂ２，・・・，ｂｎ｝）はそれぞれ巡回群Ｇの元、即ちｂｆ∈Ｇであることに留意する。
【０１１９】
続いて、検証装置（３０００）の判定部（７０９０）は、ＲＡＭ（３５００）からＬ、ｍ、Ａ０、Ａ１、ａＮ、ｂＮ、ｃＮをそれぞれ読み込み、Σｆ∈Ｎｃｆ  （ｍｏｄ  ｑ）＝Ｈ”（Ｌ，ｍ，Ａ０，Ａ１，ａＮ，ｂＮ）  （ｍｏｄ  ｑ）が成立するか否かを判定し、この判定結果ＲをＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ２９）。このハッシュ関数Ｈ”の入力は、ステップＳ１４の処理におけるハッシュ関数Ｈ”の入力と同じになるようにする。
この判定が成立しなかった場合（判定不成立）、署名ξは不正な署名であることが判明して検証処理を終了する（ステップＳ５１）。ステップＳ５１の終了処理は、不正署名の検出に成功したことに起因する終了である。
この判定が成立した場合（判定成立）、制御部（７１１）は、以下の署名者追跡処理を実行するように制御する。なお、以下の署名者追跡処理では、単に重複署名者の追跡をするだけでなく、同一の署名装置で作られた同一のメッセージに対する署名のコピーも検出する処理も行っている。また、説明の便宜上、重複署名ないしコピー署名は１つであるとする（つまり、二重署名ないし１個のコピー署名が存在する場合とする。）。
【０１２０】
［署名者追跡］
検証装置（３０００）は、制御部（７１１０）の制御によって、その通信部（３３００）を通じて、情報公開サーバ（１０００）にアクセスし、情報公開サーバ（１０００）の通信部（１３００）を通じて送信された（ステップＳ４ｓ）、情報公開サーバ（１０００）の外部記憶装置（１７００）に記憶される全ての署名ξ並びに各署名に対応したラベルＬおよびメッセージｍを受信し、これらを検証装置（３０００）の外部記憶装置（３７００）に保存記憶する（ステップＳ３０）。
【０１２１】
次に、検証装置（３０００）は、制御部（７１１０）の制御によって、外部記憶装置（３７００）から読み込まれてＲＡＭ（３５００）に記憶される各署名のうち、２つの署名（各署名に対応したラベルＬおよびメッセージｍも含む。）からなるペア〔後述の重複署名者追跡およびコピー署名の検出がまだ行われていないペアとする。〕を選択して、以下の処理を行う。ここでは、選択したペアを構成する、一方の署名並びにこの署名に対応したラベルＬおよびメッセージｍと、他方の署名並びにこの署名に対応したラベルＬおよびメッセージｍとを区別するために、〈Ｌ，ｍ，ξ＝｛Ａ１、ｃＮ、ｚＮ｝〉、〈Ｌ，ｍ’，ξ’＝｛Ａ１’、ｃＮ’、ｚＮ’｝〉とする〔ラベルＬは共通であることに留意する。〕（ステップＳ３１）。
【０１２２】
まず、検証装置（３０００）のＡ０生成部（７０１０）は、ＲＡＭ（３５００）からラベルＬ、メッセージｍ、ｍ’をそれぞれ読み込み、Ａ０＝Ｈ’（Ｌ，ｍ）、Ａ０’＝Ｈ’（Ｌ，ｍ’）を演算し、この演算結果Ａ０、Ａ０’をＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ３２）。
【０１２３】
次に、検証装置（３０００）のσＮ生成部（７０３０）は、ＲＡＭ（３５００）からＡ０、Ａ１、Ａ０’、Ａ１’、ｎをそれぞれ読み込み、σｆ＝Ａ０（Ａ１＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕およびσｆ’＝Ａ０’（Ａ１’＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果σＮ（＝（σ１，σ２，・・・，σｎ））およびσＮ’（＝（σ１’，σ２’，・・・，σｎ’））をＲＡＭ（３５００）の所定の格納領域に格納する（ステップＳ３３）。
【０１２４】
次に、検証装置（３０００）の重複臨時公開鍵検証部（７１６０）は、ＲＡＭ（３５００）からσｆ＝Ａ０（Ａ１＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕およびσｆ’＝Ａ０’（Ａ１’＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕をそれぞれ読み込み、σｆ＝σｆ’が成立するか否かをｆ＝１，２，・・・，ｎについて比較する（ステップＳ３４）。
ｆ＝１，２，・・・，ｎの全てについてσｆ＝σｆ’が成立した場合、ステップＳ３１で選択された２つの署名は、同一の署名装置によって同一のメッセージｍに対して署名生成されたものであることが判明し、少なくともいずれか一方は本来１つであるはずの署名のコピーであると特定される。そこで、重複臨時公開鍵検証部（７１６０）は、コピー署名を検出したことを示す情報ΩをＲＡＭ（３５００）の所定の格納領域に格納する（コピー署名の検出；ステップＳ３５）。
また、ある１つのｐについてσｐ＝σｐ’が成立する場合、このｐに対応する署名者ｐが重複使用者として特定される。そこで、重複臨時公開鍵検証部（７１６０）は、重複署名者を示すｐをＲＡＭ（３５００）の所定の格納領域に格納する（重複使用者追跡；ステップＳ３６）。
もし、ｆ＝１，２，・・・，ｎの全てについてσｆ＝σｆ’が成立せず、かつ、ある１つのｐについてσｐ＝σｐ’が成立しない場合には、検証装置（３０００）は、制御部（７１１０）の制御によって、ステップＳ３１以降の処理を繰り返す（ステップＳ３７）。
【０１２５】
既述のとおり、二重署名ないし１個のコピー署名が存在する場合としたので、ｆ＝１，２，・・・，ｎの全てについてσｆ＝σｆ’が成立するか、あるいは、ある１つのｐについてσｐ＝σｐ’が成立した場合には、署名者追跡処理を終了できる。もちろん、このような限定をしない場合には、全てのペアで署名者追跡処理を行えばよい。
【０１２６】
このように、署名ξから得られた臨時公開鍵σｆ〔ｆ＝１，２，・・・，ｎ〕には署名装置ｐに固有の臨時公開鍵σｐが含まれるので、この臨時公開鍵σｐが異なる署名ξ’から得られた臨時公開鍵のｐ番目の臨時公開鍵σｐ’と一致する場合、この臨時公開鍵σｐを生成した署名者が重複使用者であると特定することができる。このことによって、署名の重複使用を防止することが可能となる。
【０１２７】
また、撹乱臨時公開鍵は、メッセージｍおよび固有臨時公開鍵を変数とした関数として表されることから、署名ξから得られた臨時公開鍵σｆと、署名ξ’から得られた臨時公開鍵σｆ’とが、ｆ＝１，２，・・・，ｎについて全て一致する場合は、署名ξおよび署名ξ’は、同一の署名装置によって同一のメッセージに対して生成されたものと言える。従って、どの署名装置によって生成された署名であるかは判別できないものの、全てのｆ＝１，２，・・・，ｎについてσｆ＝σｆ’が成立する関係にある複数の署名は、実質的に１個の署名として取り扱うことができる。
【０１２８】
以上に説明した重複使用者追跡可能署名方式は、例えば電子投票や電子現金方式に適用可能である。詳しい情報処理（例えば具体的な演算手段、送信手段、記憶手段などの情報処理の主体や、各主体の行う情報処理の具体的内容など）については以上に説明した重複使用者追跡可能署名方式を参照すべきであるから、以下、上記の重複使用者追跡可能署名方式の適用例を簡単に説明する。
【０１２９】
＜適用例１：電子投票＞
重複使用者追跡可能署名方式における署名者（署名装置）が投票者（電子投票装置；以下、単に投票装置という。）になり、検証者（検証装置）が集計者（開票装置）になる。投票者の集合をＮ＝｛１，２，・・・，ｎ｝とする。
【０１３０】
［鍵生成］
まず、情報公開サーバ（１０００）には、選挙名（例えば、「平成○○年××月市長リコール選挙」とする。）、投票内容（例えば、市長のリコールに「賛成」あるいは「反対」とする。）を特定する情報Ｌ０を公開する。
【０１３１】
投票者ｉの投票装置ｉは、重複使用者追跡可能署名方式において説明したように鍵生成を行い、公開鍵ｙｉをＰＫＩに登録し、情報公開サーバ（１０００）で公開鍵ｙｉが公開される。
【０１３２】
情報公開サーバ（１０００）のラベル生成部が、情報Ｌ０および投票者の公開鍵のリストｙＮからラベルＬ＝（Ｌ０，ｙＮ）を生成して公開する。このラベルＬは、各投票装置に提供される。
【０１３３】
［投票］
投票者ｉは、投票内容ｍを決定し、投票装置ｉを用いて投票を行う。ここで、投票装置ｉは、情報公開サーバ（１０００）から取得したラベルＬおよび投票内容ｍから、重複使用者追跡可能署名方式において説明した署名ξｉを生成し、ラベルＬ、投票内容ｍ、署名ξｉを（認証のない）匿名通信路を通じて情報公開サーバ（１０００）に送信する。
【０１３４】
［開票］
開票装置は、情報公開サーバ（１０００）からある投票内容（例えば「賛成」を表す投票内容とする。）の全署名を取得し、重複使用者追跡可能署名方式において説明した署名検証によって、各署名を検証する。検証に不合格の投票は全て不正として破棄する（不正な署名の付いた投票を計数しない。）。
【０１３５】
次に、開票装置は、重複使用者追跡可能署名方式において説明した署名者追跡によって、重複署名者を検出する。もし重複署名者を検出した場合には、この投票装置から投票された署名付き投票を破棄し（不正な重複署名の付いた投票を計数しない。）、この重複署名者のＩＤを情報公開サーバ（１０００）に送信して、情報公開サーバ（１０００）において重複署名者のＩＤや公開鍵を公開する。さらに、投票のコピー（つまり、同一の投票者が、同一の投票内容を複数回投票したものである。）を検出するようにして、コピーが検出された場合には、１つを除き残りのコピーを破棄する。投票のコピーの検出は、投票に付された署名について上記ステップＳ３５の処理を行うことで実現される。
【０１３６】
そして、開票装置は、投票内容ｍごとに上記の処理を行い、開票装置の集計手段〔所定のプログラムがＣＰＵで解釈・実行されて実現される。〕は、投票内容ｍごとに投票数を計数して、これを情報公開サーバ（１０００）に送信し、情報公開サーバ（１０００）において投票内容ｍごとの投票数を公開する。
【０１３７】
＜適用例２：電子現金方式＞
重複使用者追跡可能署名方式における署名者（署名装置）が利用者（利用者装置）になり、検証者（検証装置）が店舗（店舗装置）および銀行（銀行の検証装置）になり、ＰＫＩの運営者が銀行になる。また、銀行が情報公開サーバを管理し、重複使用者の検出は、銀行の検証装置で行うとする。
利用者の集合をＮ＝｛１，２，・・・，ｎ｝とする。
【０１３８】
［鍵生成：口座開設］
利用者ｉの利用者装置ｉは、重複使用者追跡可能署名方式において説明したように鍵生成を行い、公開鍵ｙｉを例えば銀行の公開鍵登録サーバ装置に登録し、情報公開サーバ（１０００）で公開鍵ｙｉが公開される。
【０１３９】
［引出］
以下、引出、振込、払戻は、銀行の口座管理装置によって行うとする。引出、振込、払戻の具体的な処理や口座管理装置の構成は公知の電子現金システムなどで実現するから、これらの詳細な説明は省略し、重複使用者追跡可能署名方式の電子現金方式への適用に焦点を当てて説明する。
【０１４０】
銀行の口座管理装置は、銀行名、利用者ｉが電子現金として用いる金額（電子現金の額面額である。）、有効期限などを特定する情報Ｌ０を決定し、情報Ｌ０と利用者全員の公開鍵ｙＮとからラベルＬ＝（Ｌ０，ｙＮ）を決定する。
【０１４１】
銀行の口座管理装置は、利用者ｉの口座からラベルＬの定める（より具体的には、情報Ｌ０を構成する金額である。）金額を引き落とす。この引き落としも、公知の電子現金システムに拠ればよい（実際に現金を引き落とすのではなく、例えば、残高を示すデータを引き落とし後の金額に書き換えればよい。）。
【０１４２】
銀行の口座管理装置は、ラベルＬおよびラベルＬに対する銀行の署名Ｓｉｇ（Ｌ）を情報公開サーバで公開する。
【０１４３】
［支払］
利用者ｉから電子現金での支払いを受ける店舗装置は、店舗を特定する情報と、取引を特定する情報（例えば取引金額、取引日時などである。）とを含む取引情報ｍを決定し、利用者装置ｉに送信する。
【０１４４】
利用者装置ｉは、情報公開サーバからはラベルＬおよびラベルＬに対する署名Ｓｉｇ（Ｌ）を受信し、店舗装置からは取引情報ｍを受信し、ラベルＬと取引情報ｍとから重複使用者追跡可能署名方式において説明した署名ξを生成する。そして、利用者装置ｉは、ラベルＬ，取引情報ｍ、署名ξの組を電子現金とし、この電子現金（Ｌ，ｍ，ξ）と銀行の署名Ｓｉｇ（Ｌ）を店舗装置に送信する。
【０１４５】
店舗装置は、重複使用者追跡可能署名方式において説明した署名検証によって、電子現金（Ｌ，ｍ，ξ）を検証する。また、店舗装置は、公知の署名検証方法によって、銀行の署名Ｓｉｇ（Ｌ）を検証する（例えば、銀行の公開鍵が情報公開サーバに公開されているとして、この銀行の公開鍵を情報公開サーバから取得し、この銀行の公開鍵で署名Ｓｉｇ（Ｌ）を検証すればよい。）。
【０１４６】
上記の検証がいずれも成立すると、店舗装置は、電子現金（Ｌ，ｍ，ξ）を銀行の検証装置に送信する。
【０１４７】
銀行の検証装置は、店舗装置から電子現金（Ｌ，ｍ，ξ）を受信すると、重複使用者追跡可能署名方式において説明した署名検証によって、電子現金（Ｌ，ｍ，ξ）を検証する。銀行の検証装置は、電子現金（Ｌ，ｍ，ξ）の検証が成立した場合には、銀行の口座管理装置は、店舗の口座にラベルＬの定める現金を振り込む。
【０１４８】
［電子現金の重複使用、電子現金のコピー検出］
銀行の検証装置は、電子現金（Ｌ，ｍ，ξ）の検証が成立しなかった場合には、重複使用者追跡可能署名方式において説明した署名者追跡によって、電子現金の重複使用および電子現金のコピーを検出する。ここで電子現金の重複使用は、異なる取引において利用者が電子現金を重複使用したことを意味する。つまり、利用者による電子現金の不正利用である。また、電子現金のコピーは、店舗（装置）が、利用者（装置）から受信した電子現金を銀行に複数回送信したことを意味する。つまり、店舗による電子現金の不正利用である。
そこで、この検出によって電子現金の重複使用が行われたと判定できた場合には、重複利用した利用者のＩＤ等を情報公開サーバで公開し、銀行取引を停止すればよい。また、電子現金のコピーが検出された場合には、コピーを生成した店舗名（この店舗名は、取引情報ｍに含まれる。）を情報公開サーバで公開し、銀行取引を停止すればよい。
【０１４９】
［払戻］
利用者は、ラベルＬの定める有効期限を経過した未使用の電子現金を保持している場合には、この未使用の電子現金を銀行の検証装置に対して送信して、払戻のための呈示を行う。
【０１５０】
利用者装置から未使用の電子現金を受信することによって払戻のための電子現金の呈示を受けた銀行の検証装置は、利用者装置から電子現金（Ｌ，ｍ，ξ）を受信すると、重複使用者追跡可能署名方式において説明した署名検証、署名者追跡、コピー署名検出によって、電子現金（Ｌ，ｍ，ξ）を検証する。銀行の検証装置が電子現金（Ｌ，ｍ，ξ）のいずれの検証にも成功した場合には、銀行の口座管理装置は、利用者の口座に取引情報ｍの定める現金を振り込む（実際に現金を振り込むのではなく、例えば、残高を示すデータを振り込み後の金額に書き換えればよい。）。
振込みによる払戻については、公知の電子現金システムに拠ればよいので、詳細な説明を略して簡潔に記すに留める。
【０１５１】
重複に署名を行った者を特定可能な重複使用者追跡可能署名方式を、電子投票、電子現金に適用することで、例えば投票内容に添付するためのブラインド署名を発行する従来的な選挙管理者と云う信頼できるサーバ装置が不要になる。
【図面の簡単な説明】
【０１５２】
【図１】閾値つき電子署名システムの構成例と流れを示す図。
【図２】参加装置９１０−ｉの機能構成例を示す図。
【図３】鍵生成部９１１−ｉの処理フローを示す図。
【図４】乱数生成部９１２−ｉの処理フローを示す図。
【図５】署名生成部９２０の機能構成例を示す図。
【図６】署名生成部９２０の処理フローを示す図。
【図７】署名検証部９３０の機能構成例を示す図。
【図８】署名検証部９３０での署名σ（ｍ）を検証するフローを示す図。
【図９】第１実施形態の閾値つき電子署名システムの構成例と流れを示す図。
【図１０】参加者装置１１０−ｉの機能構成例を示す図。
【図１１】署名生成部１２０の機能構成例を示す図。
【図１２】署名検証部１３０の機能構成例を示す図。
【図１３】第１実施形態での電子署名システムの処理フローを示す図。
【図１４】第２実施形態の閾値つき電子署名システムの構成例と流れを示す図。
【図１５】参加者装置２１０−ｉの機能構成例を示す図。
【図１６】署名生成部２２０の機能構成例を示す図。
【図１７】署名検証部２３０の機能構成例を示す図。
【図１８】第２実施形態での電子署名システムの処理フローを示す図。
【図１９】情報公開サーバ（１０００）のハードウェア構成例を示す図。
【図２０】署名装置（２０００）のハードウェア構成例を示す図。
【図２１】検証装置（３０００）のハードウェア構成例を示す図。
【図２２】重複使用者追跡可能方式におけるシステム構成例を示す図。
【図２３】情報公開サーバ（１０００）における処理フローを示す図。
【図２４】署名装置（２０００）の機能構成例を示す図。
【図２５】署名装置（２０００）における処理フローを示す図（その１）。
【図２６】署名装置（２０００）における処理フローを示す図（その２）。
【図２７】署名後における状態を示す図。
【図２８】検証装置（３０００）の機能構成例を示す図。
【図２９】検証装置（３０００）における処理フローを示す図（その１）。
【図３０】検証装置（３０００）における処理フローを示す図（その２）。
【図１】
0004790422.tif 000043
【図２】
0004790422.tif 000044
【図３】
0004790422.tif 000045
【図４】
0004790422.tif 000046
【図５】
0004790422.tif 000047
【図６】
0004790422.tif 000048
【図７】
0004790422.tif 000049
【図８】
0004790422.tif 000050
【図９】
0004790422.tif 000051
【図１０】
0004790422.tif 000052
【図１１】
0004790422.tif 000053
【図１２】
0004790422.tif 000054
【図１３】
0004790422.tif 000055
【図１４】
0004790422.tif 000056
【図１５】
0004790422.tif 000057
【図１６】
0004790422.tif 000058
【図１７】
0004790422.tif 000059
【図１８】
0004790422.tif 000060
【図１９】
0004790422.tif 000061
【図２０】
0004790422.tif 000062
【図２１】
0004790422.tif 000063
【図２２】
0004790422.tif 000064
【図２３】
0004790422.tif 000065
【図２４】
0004790422.tif 000066
【図２５】
0004790422.tif 000067
【図２６】
0004790422.tif 000068
【図２７】
0004790422.tif 000069
【図２８】
0004790422.tif 000070
【図２９】
0004790422.tif 000071
【図３０】
0004790422.tif 000072