(57)【特許請求の範囲】
【請求項１】
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘｉを群Ｚｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝が記憶されている情報公開サーバに対して電子投票を行う電子投票装置であって、
投票者ｉに固有の秘密鍵ｘｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｘｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ１＝（σｉ／Ｈ’（ｎ，ｙＮ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σｊ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗｉ∈Ｚｑについてａｉ＝ｇ＾ｗｉとｂｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｗｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚｊ、ｃｊ∈Ｚｑを用いて、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）とｂｊ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｊ）×（σｊ＾ｃｊ）を求め、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ１，ａ２，…，ａｎ，ｂ１，ｂ２，…，ｂｎ）、β（ｊ）＝ｃｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を満たす次数（ｎ−１）の多項式β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋…＋β１ｘ＋β０∈Ｚｑ［ｘ］の係数βφ（φ＝０，１，２，…，ｎ−１）を求め、さらに、ｚｉ＝ｗｉ−β（ｉ）×ｘｉを求め、ξｉ＝（Ａ１，β０，β１，…，βｎ−１，ｚ１，ｚ２，…，ｚｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えた電子投票装置。
【請求項２】
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘｉを群Ｚｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝が記憶されている情報公開サーバに対して電子投票を行う電子投票装置であって、
投票者ｉに固有の秘密鍵ｘｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｘｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ１＝（σｉ／Ｈ’（ｎ，ｙＮ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σｊ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗｉ∈Ｚｑについてａｉ＝ｇ＾ｗｉとｂｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｗｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚｊ、ｃｊ∈Ｚｑを用いて、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）とｂｊ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｊ）×（σｊ＾ｃｊ）を求め、ｃｉ＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ１，ａ２，…，ａｎ，ｂ１，ｂ２，…，ｂｎ）−Σj∈{1,…,n}-{i}ｃjを求め、さらに、ｚｉ＝ｗｉ−ｃｉ×ｘｉを求め、ξｉ＝（Ａ１，ｃ０，ｃ１，…，ｃｎ，ｚ１，ｚ２，…，ｚｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えた電子投票装置。
【請求項３】
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝と請求項１に記載の電子投票装置から送信された投票内容ｍに対する署名（以下、投票署名という）ξｉ＝（Ａ１，β０，β１，…，βｎ−１，ｚ１，ｚ２，…，ｚｎ）とが記憶されている情報公開サーバから、少なくとも全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅ（ｅ≦ｎ）を受信して、投票内容ｍに関する開票を行う開票装置であって、
上記情報公開サーバから、少なくとも全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを受信する受信手段と、
各投票署名ξ１，…，ξｅについてσｆ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ１，…，ξｅについて、β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋…＋β１ｘ＋β０として、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]とｂ’ｆ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｆ）×（σｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]を求め、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ’１，ａ’２，…，ａ’ｎ，ｂ’１，ｂ’２，…，ｂ’ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ１，…，σｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えた開票装置。
【請求項４】
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝と請求項２に記載の電子投票装置から送信された投票内容ｍに対する署名（以下、投票署名という）ξｉ＝（Ａ１，ｃ０，ｃ１，…，ｃｎ，ｚ１，ｚ２，…，ｚｎ）とが記憶されている情報公開サーバから、少なくとも全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅ（ｅ≦ｎ）を受信して、投票内容ｍに関する開票を行う開票装置であって、
上記情報公開サーバから、少なくとも全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを受信する受信手段と、
各投票署名ξ１，…，ξｅについてσｆ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ１，…，ξｅについて、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾ｃｆ）[ｆ＝１，２，…，ｎ]とｂ’ｆ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｆ）×（σｆ＾ｃｆ）[ｆ＝１，２，…，ｎ]を求め、Σj∈{1,…,n}ｃj＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ’１，ａ’２，…，ａ’ｎ，ｂ’１，ｂ’２，…，ｂ’ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ１，…，σｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えた開票装置。
【請求項５】
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムであって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘｉを群Ｚｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバは、
投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝、投票内容ｍに対する署名（以下、投票署名という）を記憶可能な記憶手段と、
上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を送信可能な対電子投票装置送信手段と、
上記電子投票装置から送信された投票署名を受信可能な対電子投票装置受信手段と、
上記開票装置に対して、少なくとも、上記情報公開サーバの記憶手段に記憶される全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名を送信可能な対開票装置送信手段と
を備えており、
上記電子投票装置は、
投票者ｉに固有の秘密鍵ｘｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｘｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ１＝（σｉ／Ｈ’（ｎ，ｙＮ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σｊ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗｉ∈Ｚｑについてａｉ＝ｇ＾ｗｉとｂｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｗｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚｊ、ｃｊ∈Ｚｑを用いて、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）とｂｊ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｊ）×（σｊ＾ｃｊ）を求め、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ１，ａ２，…，ａｎ，ｂ１，ｂ２，…，ｂｎ）、β（ｊ）＝ｃｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を満たす次数（ｎ−１）の多項式β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋…＋β１ｘ＋β０∈Ｚｑ［ｘ］の係数βφ（φ＝０，１，２，…，ｎ−１）を求め、さらに、ｚｉ＝ｗｉ−β（ｉ）×ｘｉを求め、ξｉ＝（Ａ１，β０，β１，…，βｎ−１，ｚ１，ｚ２，…，ｚｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えており、
上記開票装置は、
電子投票後に投票内容ｍに対する全ての投票署名ξ１，…，ξｅ（ｅ≦ｎ）を記憶する上記情報公開サーバから、少なくとも全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを受信する受信手段と、
各投票署名ξ１，…，ξｅについてσｆ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ１，…，ξｅについて、β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋…＋β１ｘ＋β０として、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]とｂ’ｆ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｆ）×（σｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]を求め、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ’１，ａ’２，…，ａ’ｎ，ｂ’１，ｂ’２，…，ｂ’ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ１，…，σｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えている
電子投開票システム。
【請求項６】
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムであって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘｉを群Ｚｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバは、
投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝、投票内容ｍに対する署名（以下、投票署名という）を記憶可能な記憶手段と、
上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を送信可能な対電子投票装置送信手段と、
上記電子投票装置から送信された投票署名を受信可能な対電子投票装置受信手段と、
上記開票装置に対して、少なくとも、上記情報公開サーバの記憶手段に記憶される全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名を送信可能な対開票装置送信手段と
を備えており、
上記電子投票装置は、
投票者ｉに固有の秘密鍵ｘｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｘｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ１＝（σｉ／Ｈ’（ｎ，ｙＮ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σｊ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗｉ∈Ｚｑについてａｉ＝ｇ＾ｗｉとｂｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｗｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚｊ、ｃｊ∈Ｚｑを用いて、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）とｂｊ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｊ）×（σｊ＾ｃｊ）を求め、ｃｉ＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ１，ａ２，…，ａｎ，ｂ１，ｂ２，…，ｂｎ）−Σj∈{1,…,n}-{i}ｃjを求め、さらに、ｚｉ＝ｗｉ−ｃｉ×ｘｉを求め、ξｉ＝（Ａ１，ｃ０，ｃ１，…，ｃｎ，ｚ１，ｚ２，…，ｚｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えており、
上記開票装置は、
電子投票後に投票内容ｍに対する全ての投票署名ξ１，…，ξｅ（ｅ≦ｎ）を記憶する上記情報公開サーバから、少なくとも全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを受信する受信手段と、
各投票署名ξ１，…，ξｅについてσｆ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ１，…，ξｅについて、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾ｃｆ）[ｆ＝１，２，…，ｎ]とｂ’ｆ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｆ）×（σｆ＾ｃｆ）[ｆ＝１，２，…，ｎ]を求め、Σj∈{1,…,n}ｃj＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ’１，ａ’２，…，ａ’ｎ，ｂ’１，ｂ’２，…，ｂ’ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ１，…，σｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えている
電子投開票システム。
【請求項７】
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムにおける電子投票方法であって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘｉを群Ｚｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバの対電子投票装置送信手段が、上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を送信する対電子投票装置送信ステップと、
上記電子投票装置の受信手段が、上記対電子投票装置送信ステップにおいて送信された投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を受信する電子投票装置受信ステップと、
上記電子投票装置の固有臨時公開鍵生成手段が、投票者ｉに固有の固有臨時公開鍵σｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｘｉを求める固有臨時公開鍵生成ステップと、
上記電子投票装置の撹乱因子生成手段が、撹乱因子Ａ１＝（σｉ／Ｈ’（ｎ，ｙＮ，ｍ））＾（１／ｉ）を求める撹乱因子生成ステップと、
上記電子投票装置の撹乱臨時公開鍵生成手段が、ｎ−１個の撹乱臨時公開鍵σｊ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成ステップと、
上記電子投票装置の署名情報生成手段が、任意に選択した元ｗｉ∈Ｚｑについてａｉ＝ｇ＾ｗｉとｂｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｗｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚｊ、ｃｊ∈Ｚｑを用いて、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）とｂｊ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｊ）×（σｊ＾ｃｊ）を求め、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ１，ａ２，…，ａｎ，ｂ１，ｂ２，…，ｂｎ）、β（ｊ）＝ｃｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を満たす次数（ｎ−１）の多項式β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋…＋β１ｘ＋β０∈Ｚｑ［ｘ］の係数βφ（φ＝０，１，２，…，ｎ−１）を求め、さらに、ｚｉ＝ｗｉ−β（ｉ）×ｘｉを求め、ξｉ＝（Ａ１，β０，β１，…，βｎ−１，ｚ１，ｚ２，…，ｚｎ）を投票内容ｍに対する署名とする署名情報生成ステップと、
上記電子投票装置の送信手段が、投票内容ｍおよび当該投票内容ｍに対する上記署名（以下、投票署名という）ξｉ＝（Ａ１，β０，β１，…，βｎ−１，ｚ１，ｚ２，…，ｚｎ）を電子投票として上記情報公開サーバに送信する対情報公開サーバ送信ステップと、
上記情報公開サーバの対電子投票装置受信手段が、上記対情報公開サーバ送信ステップにおいて送信された投票署名ξｉ＝（Ａ１，β０，β１，…，βｎ−１，ｚ１，ｚ２，…，ｚｎ）を受信する対電子投票装置受信ステップと、
上記情報公開サーバの記憶手段が、投票内容ｍに対する電子投票として受信した投票署名ξ１，…，ξｅ（ｅ≦ｎ）を記憶する情報公開サーバ記憶ステップと、
上記情報公開サーバの対開票装置送信手段が、上記開票装置に対して、少なくとも、全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを送信する対開票装置送信ステップと、
上記開票装置の受信手段が、上記対開票装置送信ステップにおいて送信された全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを受信する開票装置受信ステップと、
上記開票装置の臨時公開鍵生成手段が、各投票署名ξ１，…，ξｅについてσｆ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成ステップと、
上記開票装置の検証手段が、各投票署名ξ１，…，ξｅについて、β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋…＋β１ｘ＋β０として、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]とｂ’ｆ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｆ）×（σｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]を求め、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ’１，ａ’２，…，ａ’ｎ，ｂ’１，ｂ’２，…，ｂ’ｎ）が成立するか否かを判定する検証ステップと、
上記開票装置の計数手段が、上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ１，…，σｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数ステップと
を有する電子投開票方法。
【請求項８】
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムにおける電子投票方法であって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘｉを群Ｚｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙｉ＝ｇ＾ｘｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバの対電子投票装置送信手段が、上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を送信する対電子投票装置送信ステップと、
上記電子投票装置の受信手段が、上記対電子投票装置送信ステップにおいて送信された投票内容ｍと全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝を受信する電子投票装置受信ステップと、
上記電子投票装置の固有臨時公開鍵生成手段が、投票者ｉに固有の固有臨時公開鍵σｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｘｉを求める固有臨時公開鍵生成ステップと、
上記電子投票装置の撹乱因子生成手段が、撹乱因子Ａ１＝（σｉ／Ｈ’（ｎ，ｙＮ，ｍ））＾（１／ｉ）を求める撹乱因子生成ステップと、
上記電子投票装置の撹乱臨時公開鍵生成手段が、ｎ−１個の撹乱臨時公開鍵σｊ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成ステップと、
上記電子投票装置の署名情報生成手段が、任意に選択した元ｗｉ∈Ｚｑについてａｉ＝ｇ＾ｗｉとｂｉ＝Ｈ（ｎ，ｙＮ，ｍ）＾ｗｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚｊ、ｃｊ∈Ｚｑを用いて、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）とｂｊ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｊ）×（σｊ＾ｃｊ）を求め、ｃｉ＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ１，ａ２，…，ａｎ，ｂ１，ｂ２，…，ｂｎ）−Σj∈{1,…,n}-{i}ｃjを求め、さらに、ｚｉ＝ｗｉ−ｃｉ×ｘｉを求め、ξｉ＝（Ａ１，ｃ０，ｃ１，…，ｃｎ，ｚ１，ｚ２，…，ｚｎ）を投票内容ｍに対する署名とする署名情報生成ステップと、
上記電子投票装置の送信手段が、投票内容ｍおよび当該投票内容ｍに対する上記署名（以下、投票署名という）ξｉ＝（Ａ１，ｃ０，ｃ１，…，ｃｎ，ｚ１，ｚ２，…，ｚｎ）を電子投票として上記情報公開サーバに送信する対情報公開サーバ送信ステップと、
上記情報公開サーバの対電子投票装置受信手段が、上記対情報公開サーバ送信手段において送信された投票署名ξｉ＝（Ａ１，ｃ０，ｃ１，…，ｃｎ，ｚ１，ｚ２，…，ｚｎ）を受信する対電子投票装置受信ステップと、
上記情報公開サーバの記憶手段が、投票内容ｍに対する電子投票として受信した投票署名ξ１，…，ξｅ（ｅ≦ｎ）を記憶する記憶ステップと、
上記情報公開サーバの対開票装置送信手段が、上記開票装置に対して、少なくとも、全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを送信する対開票装置送信ステップと、
上記開票装置の受信手段が、上記対開票装置送信ステップにおいて送信された全投票者の公開鍵ｙＮ＝｛ｙ１，…，ｙｎ｝および投票内容ｍに対する全ての投票署名ξ１，…，ξｅを受信する開票装置受信ステップと、
上記開票装置の臨時公開鍵生成手段が、各投票署名ξ１，…，ξｅについてσｆ＝Ｈ’（ｎ，ｙＮ，ｍ）（Ａ１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成ステップと、
上記開票装置の検証手段が、各投票署名ξ１，…，ξｅについて、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾ｃｆ）[ｆ＝１，２，…，ｎ]とｂ’ｆ＝（Ｈ（ｎ，ｙＮ，ｍ）＾ｚｆ）×（σｆ＾ｃｆ）[ｆ＝１，２，…，ｎ]を求め、Σj∈{1,…,n}ｃj＝Ｈ”（ｎ，ｙＮ，ｍ，Ｈ（ｎ，ｙＮ，ｍ），Ｈ’（ｎ，ｙＮ，ｍ），Ａ１，ａ’１，ａ’２，…，ａ’ｎ，ｂ’１，ｂ’２，…，ｂ’ｎ）が成立するか否かを判定する検証ステップと、
上記開票装置の計数手段が、上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ１，…，σｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数ステップと
を有する電子投開票方法。
【請求項９】
請求項１または請求項２に記載された電子投票装置としてコンピュータを機能させるための電子投票プログラム。
【請求項１０】
請求項３または請求項４に記載された開票装置としてコンピュータを機能させるための開票プログラム。 
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術に関するものであり、詳しくは電子投開票技術に関する。
【背景技術】
【０００２】
従来的な電子投開票技術の代表的な例として、選挙管理者が投票にブラインド署名を付けることにより匿名性と一人一票を実現する方式がある（例えば非特許文献１参照。）。以下に、その電子投開票方法の概要を説明する。
【０００３】
[準備]
選挙管理者Ａは、ブラインド署名の署名鍵と検証鍵を生成し、検証鍵を公開する。
【０００４】
［投票］
投票者ｉ∈Ｎ（Ｎは、投票者の集合を表す。）は、投票内容ｍをマスキングしたものであるＭを選挙管理者Ａに送る。ここで選挙管理者Ａとは、人間ではなく、所定の機能（ブラインド署名の付与）を実現するサーバである。
選挙管理者Ａは、投票者ｉ∈Ｎを所定の方法（例えば本人確認など）で認証し有権者であることを確認したら、ブラインド署名σ（Ｍ）を生成し投票者ｉ∈Ｎに送る。投票者ｉ∈Ｎは、受信したブラインド署名σ（Ｍ）からマスクを外し選挙管理者Ａの署名σ（ｍ）を得て、投票内容ｍおよび署名σ（ｍ）を、匿名通信路を経由して公開掲示板Ｂに公開する。ここで公開掲示板Ｂとは、例えば端末装置からアクセスを受けた場合に、所定の情報を提供することのできるサーバである。
ブラインド署名としては、例えばＲＳＡ暗号に基づく方式などがある（例えば非特許文献２参照。）。
【０００５】
［開票］
開票者は、公開掲示板Ｂに公開された選挙管理者Ａの署名σ（ｍ）を検証鍵で検証し、検証に合格した投票内容ｍおよび署名σ（ｍ）を投票結果として公開する。
【０００６】
この方式では、ブラインド署名の性質から、（Ｍ，σ（Ｍ））と（ｍ，σ（ｍ））とを関連付けることができないので、匿名性を実現することができる。また、ブラインド署名σ（ｍ）を偽造することができないので、一人一票を実現することができる。
【非特許文献１】Atsushi Fujioka, Tatsuaki Okamoto, Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, ASIACRYPT 1992, 244-251.
【非特許文献２】岡本龍明、山本博資著、「シリーズ／情報科学の数学  現代暗号」、初版、産業図書株式会社、１９９７年
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、従来的な電子投開票方式においては、信頼できる選挙管理者Ａという電子投開票のための特別なサーバが必要である。信頼できるサーバを実現するためには分散実装などコストがかかるため、一回の投票のためだけに信頼できるサーバを設置するのは不経済であり、電子投開票を簡単に行なえないという問題点があった。
【０００８】
そこで、本発明は、選挙管理者を必要としない電子投票装置、開票装置、電子投開票システム、電子投開票方法並びにプログラムを提供することを目的とする。 
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明では、電子投票装置によって、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵および各投票者に固有の秘密鍵を用いて投票内容に対する署名を生成し、この署名（投票署名）をもって電子投票を行う。開票については、開票装置によって、電子投票装置から電子投票された投票署名に対して、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵を用いた検証を行い、検証に合格した投票署名を計数することで行う。また、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵、投票内容、さらには投票署名を、情報公開サーバで公開しておく。
【００１０】
また、電子投票装置においては、投票者に固有の秘密鍵および全投票者の公開鍵を用いて、投票者に固有の固有臨時公開鍵を生成し、固有臨時公開鍵および全投票者の公開鍵を用いて撹乱因子を生成し、さらに、撹乱因子および全投票者の公開鍵を用いて、全投票者数から１を引いた数の撹乱臨時公開鍵を生成するとし、この固有臨時公開鍵および撹乱臨時公開鍵を用いて投票内容に対する署名情報を生成して、この署名情報および撹乱因子からなる組を投票内容に対する署名（投票署名）としてもよい。なお、固有臨時公開鍵および撹乱臨時公開鍵は、撹乱因子から生成されるものであり、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能である。開票については、所定の投票内容に対する全ての投票署名について、投票署名ごとに、臨時公開鍵（固有臨時公開鍵と撹乱臨時公開鍵）を生成し、この臨臨時公開鍵および全投票者の公開鍵を用いて、臨時公開鍵が生成された投票署名の検証を行い、検証に合格した投票署名を計数するようにする。
【００１１】
また、本発明の電子投票装置、開票装置をコンピュータ上で機能させる電子投票プログラム、開票プログラムによって、コンピュータを電子投票装置、開票装置として作動処理させることができる。 
【発明の効果】
【００１２】
本発明によれば、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵および各投票者に固有の秘密鍵を用いて投票内容に対する署名を生成し、この署名（投票署名）をもって電子投票を行い、開票については、開票装置によって、電子投票装置から電子投票された投票署名に対して、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵を用いた検証を行い、検証に合格した投票署名を計数することで行うので、電子投開票のための特別なサーバ（選挙管理装置）を用いることなく電子投開票を実現することができる。
【００１３】
また、固有臨時公開鍵および撹乱臨時公開鍵を生成し、これらが撹乱因子から生成可能であるが、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能であるとすることで、少なくとも開票においては、投票署名に含まれる撹乱因子から生成される臨時公開鍵のいずれが固有臨時公開鍵であるか判別不明であるため匿名性が実現でき、さらには、臨時公開鍵に固有臨時公開鍵が含まれるから、各投票署名から生成されたた臨時公開鍵を比較することで重複投票の排除（一人一票）を実現できる。
【発明を実施するための最良の形態】
【００１４】
＜第１実施形態＞
本発明の第１実施形態を以下に説明する。
まず、Ｇを離散対数問題の難しい素数位数ｑの巡回群とし、ｇをその生成元とする。巡回群Ｇの例としては、例えば乗法群Ｚｐ＊〔ｑ＝ｐ−１〕、楕円曲線上の点で定義される群などが上げられる。
また、Ｈ、Ｈ’、Ｈ”を、Ｈ：｛０，１｝＊→Ｇ、Ｈ’：｛０，１｝＊→Ｇ、Ｈ”：｛０，１｝＊→Ｚｑなる性質を有するハッシュ関数（一方向性関数）とする。ここで｛０，１｝＊は、任意のビット長のバイナリ系列を表し、Ｚｑは、加法群を表す。
さらに、投票者はｎ人であるとし、これら投票者の集合をＮ＝｛１，・・・，ｎ｝とする。各投票者は後述する投票装置を用いて電子投票に参加する。ここでは、投票者ｉのＩＤ（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）（４）は、ＰＫＩにおける認証局を表している。
情報公開サーバ（１）、１つ以上の投票装置（２−１），（２−２），・・・，（２−ｎ）、開票装置（３）、ＣＡ（４）は、ネットワーク（５）を介して相互に通信可能に接続されている。なお、少なくとも、各投票装置とネットワークとの間は、各投票装置を利用する投票者のプライバシーが保たれるように匿名通信路とするのがよい。
【００３４】
第１実施形態では、ｎ人の投票者各人には、それぞれ１つの投票装置が割り当てられている。つまり、各投票者は、各別の投票装置を用いて電子投票を行う。しかしながら後述のとおり、各投票者は、各投票者に固有の秘密鍵・公開鍵を用いることで電子投票を行うので、各投票者に各別の投票装置を割り当てることは必須ではない。同じ投票装置であっても、各投票者が、投票者に固有の秘密鍵・公開鍵を投票装置に入力する（例えば、秘密鍵・公開鍵が記録された記録媒体を投票装置に読み取らせる。）ことで、各投票者固有の電子投票が行える。
【００３５】
[準備]
第１実施形態における電子投票を実施するための準備について説明する（図４参照）。
まず、投票者ｉは、秘密鍵ｘｉを群Ｚｑの元から選択し、巡回群Ｇの生成元ｇを用いて、公開鍵ｙｉ＝ｇ＾ｘｉを生成する。記号＾は、べき乗を表す。投票者ｉは、投票者ｉに固有の公開鍵ｙｉをＣＡ（４）に送信し、ＣＡ（４）に公開鍵ｙｉを登録する。ＣＡ（４）は、公開鍵ｙｉに対して公開鍵証明書Ｃｅｒｔｉを発行する。このようにして、ＣＡ（４）は、各投票者の公開鍵ｙ１，ｙ２，・・・，ｙｎに対して、公開鍵証明書Ｃｅｒｔ１，Ｃｅｒｔ２，・・・，Ｃｅｒｔｎを発行する（公知技術）。
【００３６】
次に、情報公開サーバ（１）は、ＣＡ（４）にネットワーク（５）経由でアクセスし、各投票者の公開鍵ｙ１，ｙ２，・・・，ｙｎおよびＣＡ（４）から発行された公開鍵証明書Ｃｅｒｔ１，Ｃｅｒｔ２，・・・，Ｃｅｒｔｎを取得する。
【００３７】
情報公開サーバ（１）は、取得した各投票者の公開鍵ｙ１，ｙ２，・・・，ｙｎおよびＣＡ（４）から発行された公開鍵証明書Ｃｅｒｔ１，Ｃｅｒｔ２，・・・，Ｃｅｒｔｎを、各公開鍵と各公開鍵証明書とを対応付けて外部記憶装置（１７）に記憶保存する。これらは、いわば有権者名簿に相当するものであると云える。
【００３８】
また、情報公開サーバ（１）は、電子投票における投票内容ｍ１，ｍ２，・・・，ｍｓも、外部記憶装置（１７）に保存記憶している。ここでｓは、投票内容の種類の数を表す。
【００３９】
情報公開サーバ（１）は、各投票装置や開票装置からアクセスがあった場合に、これらのデータ（公開鍵ｙ１，ｙ２，・・・，ｙｎ、公開鍵証明書Ｃｅｒｔ１，Ｃｅｒｔ２，・・・，Ｃｅｒｔｎ、投票内容ｍ１，ｍ２，・・・，ｍｓ）を、情報提供部（８００）によって、その通信部（１３）を通じて、アクセスした装置に対して送信する。また、電子投票後においては、外部記憶装置（１７）に保存記憶されている署名も、情報提供部（８００）によって、その通信部（１３）を通じて、アクセスした開票装置に対して送信する。
【００４０】
以下、図４〜図１４を参照して、第１実施形態における電子投開票処理の処理を説明する。
図５は、情報公開サーバ（１）における処理フローを示す図である。
図６は、投票装置（２）の機能構成例を示す図である。
図７は、投票装置（２）における処理フローを示す図である（その１）。
図８は、投票装置（２）における処理フローを示す図である（その２）。
図９は、電子投票後における状態を示す図である。
図１０は、開票装置（３）の機能構成例を示す図である。
図１１は、開票装置（３）における処理フローを示す図である（その１）。
図１２は、開票装置（３）における処理フローを示す図である（その２）。
図１３は、開票装置（３）において重複投票を検証する処理における機能構成を例示した図である。
図１４は、開票装置（３）において重複投票を検証する処理フローを示す図である。
【００４１】
[投票]
まず、投票装置による電子投票について説明する。
以下では、投票者ｉは、投票装置ｉによって電子投票を行うとする。
投票装置ｉの外部記憶装置（２７）には、投票装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘｉが予め保存記憶されているとする。既述のとおり、投票装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘｉが記録された記録媒体をある投票装置に読み取らせることで、この投票装置を投票装置ｉとして用いることが可能になる。
【００４２】
投票装置ｉは、制御部（６１３）の制御によって、その通信部（２３）を通じて、情報公開サーバ（１）にアクセスし、情報公開サーバ（１）の通信部（１３）を通じて送信された（ステップＳ１ｓ）、情報公開サーバ（１）の外部記憶装置（１７）に記憶される全ての投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝、全ての公開鍵証明書｛ｃｅｒｔ１，・・・，ｃｅｒｔｎ｝（これらは有権者名簿に相当するものである。）、投票内容ｍ（投票内容がｍ１，ｍ２，・・・，ｍｓと複数ある場合は、これら全てについてｍと同様の投開票処理を行うことで複数の投票内容につき投票を行うことができる。）を受信し、これらを投票装置ｉの外部記憶装置（２７）に保存記憶する。また、全ての投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎも、投票装置ｉの外部記憶装置（２７）に保存記憶する（ステップＳ２）。
次いで、投票装置ｉの図示しない検証部（所定のプログラムを解釈実行するＣＰＵ（２４）によって機能が実現する。）は、各公開鍵証明書を検証する（ステップＳ３）。この検証に全て合格したならば、下記の所定の処理を実行する。この検証に合格しなかったならば、取得した公開鍵の中に不正な公開鍵が含まれていることを示すものであるから、投票装置ｉは下記の処理を実行せずに終了する（ステップＳ４）。
なお、検証処理は、ＰＫＩにおける公知技術で達成されるから詳細な説明を省略する。また、相互に通信可能なサーバ（情報公開サーバ）−クライアント（投票装置）間で、サーバからクライアント（あるいは逆に、クライアントからサーバ）にアクセスして所定の情報（データ）を取得し、取得した情報（データ）を外部記憶装置に保存記憶することも公知技術で達成されるから、この明細書ではその詳細な説明を省略する。
【００４３】
なお、情報公開サーバ（１）において公開される情報に含まれる投票内容ｍに賛成か反対かを選択する所作は、人間によってのみ為しえるものであり、この点のみは投票装置（ハードウェア）による所作とは言えない。しかしながら、一旦投票内容が１つ選択されたならば、その後の処理は、投票装置（ハードウェア）による所定のプログラム（ソフトウェア）の解釈実行に従った情報処理が行われ、この情報処理によって電子投票が実現するものであることに留意しなければならない。
【００４４】
予め、制御部（６１３）の制御の下、外部記憶装置（２７）から、投票装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘｉ、全ての投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝、投票内容ｍ、全ての投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（２５）の所定の格納領域に格納しておく。以後、全ての投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝をｙＮと略記する。また、「ＲＡＭから○○を読み込む」旨の説明をした場合は、「ＲＡＭにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【００４５】
まず、ｈ生成部（６００）は、ＲＡＭ（２５）からｎ、ｍ、ｙＮをそれぞれ読み込み、ｈ＝Ｈ（ｎ，ｙＮ，ｍ）を演算し、この演算結果ｈをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ５）。ここでハッシュ演算Ｈ（ｎ，ｙＮ，ｍ）は、バイナリ系列で結合した値ｎ‖ｙＮ‖ｍ（＝ｎ‖ｙ１‖ｙ２‖・・・‖ｙｎ‖ｍ）〔記号‖はバイナリ系列同士の結合を表す。〕を入力として、ハッシュ関数Ｈを演算することを表す。その他のハッシュ関数Ｈ’、Ｈ”についても同様である。なお、ｈは巡回群Ｇの元、即ちｈ∈Ｇであることに留意する。なお、ハッシュ関数Ｈの入力は、値ｎ‖ｙＮ‖ｍに限定するものではないが、電子投票における安全性確保の観点からは、少なくともｙＮおよびｍを用いたバイナリ系列の結合値を用いるのがよい。
【００４６】
次に、σｉ生成部（６０１）は、ＲＡＭ（２５）からｈ、ｘｉをそれぞれ読み込み、σｉ＝ｈ＾ｘｉを演算し、この演算結果σｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ６）。なお、σｉは巡回群Ｇの元、即ちσｉ∈Ｇであることに留意する。このσｉは、端末装置ｉに固有の固有臨時公開鍵に相当する。
【００４７】
続いて、Ａ０生成部（６０２）は、ＲＡＭ（２５）からｎ、ｍ、ｙＮをそれぞれ読み込み、Ａ０＝Ｈ’（ｎ，ｙＮ，ｍ）を演算し、この演算結果Ａ０をＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ７）。なお、Ａ０は巡回群Ｇの元、即ちＡ０∈Ｇであることに留意する。また、ハッシュ関数Ｈ’の入力は、ハッシュ関数Ｈの入力と同じにする必要はないが、この実施形態では同じものを入力としている。
【００４８】
次に、Ａ１生成部（６０３）は、ＲＡＭ（２５）からｉ、Ａ０、σｉをそれぞれ読み込み、Ａ１＝（σｉ／Ａ０）＾（１／ｉ）を演算し、この演算結果Ａ１をＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ８）。Ａ１は巡回群Ｇの元、即ちＡ１∈Ｇであることに留意する。このＡ１は、撹乱因子に相当する。
【００４９】
次に、σｊ生成部（６０４）は、ＲＡＭ（２５）からＡ０、Ａ１、ｎ、ｉをそれぞれ読み込み、σｊ＝Ａ０（Ａ１＾ｊ）を演算し、この演算結果σｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ９）。ここでｊは、ｊ∈Ｎ−｛ｉ｝、即ち、ｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎである。なお、σｊは巡回群Ｇの元、即ちσｊ∈Ｇであることに留意する。このσｊは、撹乱臨時公開鍵に相当する。
【００５０】
さらに、Ａ０＝ｈ＾α（０）かつσｆ＝ｈ＾α（ｆ）〔但し、ｆ∈Ｎ〕を満足する次数１の多項式α（ｘ）∈Ｚｑ［ｘ］が存在することに留意しなければならない。
なお、記号α（ｘ）∈Ｚｑ［ｘ］は、多項式α（ｘ）が、群Ｚｑの元を係数に有する多項式であることを表す。
【００５１】
続いて、元選択部（６０５）は、群Ｚｑの元の中から任意に１つの元ｗｉを選択し、この元ｗｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１０）。
【００５２】
次に、ａｉ生成部（６０６）は、ＲＡＭ（２５）からｇ、ｗｉをそれぞれ読み込み、ａｉ＝ｇ＾ｗｉを演算し、この演算結果ａｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１１）。なお、ａｉは巡回群Ｇの元、即ちａｉ∈Ｇであることに留意する。
【００５３】
次に、ｂｉ生成部（６０７）は、ＲＡＭ（２５）からｈ、ｗｉをそれぞれ読み込み、ｂｉ＝ｈ＾ｗｉを演算し、この演算結果ｂｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１２）。なお、ｂｉは巡回群Ｇの元、即ちｂｉ∈Ｇであることに留意する。
【００５４】
続いて、元選択部（６０５）は、ＲＡＭ（２５）からｉ、ｎをそれぞれ読み込み、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、群Ｚｑの元の中から任意に２つの元ｚｊ、ｃｊを選択し、これらの元ｚｊ、ｃｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１３）。
【００５５】
次に、ａｊ生成部（６０８）は、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、ＲＡＭ（２５）からｇ、ｚｊ、ｃｊ、ｙｊをそれぞれ読み込み（ｙｊは、ｙＮからｙｉを除いたものである。）、ａｊ＝（ｇ＾ｚｊ）×（ｙｊ＾ｃｊ）を演算し、この演算結果ａｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１４）。なお、ａｊは巡回群Ｇの元、即ちａｊ∈Ｇであることに留意する。
【００５６】
次に、ｂｊ生成部（６０９）は、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、ＲＡＭ（２５）からｈ、ｚｊ、ｃｊ、σｊをそれぞれ読み込み、ｂｊ＝（ｈ＾ｚｊ）×（σｊ＾ｃｊ）を演算し、この演算結果ｂｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１５）。なお、ｂｊは巡回群Ｇの元、即ちｂｊ∈Ｇであることに留意する。
【００５７】
続いて、βφ生成部（６１０）は、次数（ｎ−１）の多項式β（ｘ）∈Ｚｑ［ｘ］の係数βφ（φ＝０，１，２，・・・，ｎ−１）を求める。つまり、多項式β（ｘ）＝βｎ−１ｘ＾（ｎ−１）＋βｎ−２ｘ＾（ｎ−２）＋・・・＋β１ｘ＋β０とすると、ｎ個の係数βｎ−１，βｎ−２，・・・，β１、β０の値を求めるのである（β０はｘ＾（０）の係数とする。）。これら係数は、ｘに０，１，・・・，ｉ−１，ｉ＋１，・・・，ｎを代入したｎ個の連立方程式を解くことで求めることができる。連立方程式を解くアルゴリズムは公知であるからその説明は省略する。
βφ生成部（６１０）は、ＲＡＭ（２５）からｎ、ｙＮ、ｍ、ｈ、Ａ０、Ａ１、ａｉ、ａｊ、ｂｉ、ｂｊ、ｃｊをそれぞれ読み込み、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，ｈ，Ａ０，Ａ１，ａＮ，ｂＮ）、β（ｊ）＝ｃｊ（ｊ∈Ｎ−｛ｉ｝）からなるｎ個の連立方程式を公知のアルゴリズムで解いてｎ個の係数βｎ−１，βｎ−２，・・・，β１、β０の値を求め、これらの係数βｎ−１，βｎ−２，・・・，β１、β０をＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１６）。ここで、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎであり、ａＮは、ａＮ＝（ａ１，ａ２，・・・，ａｎ）であり、ｂＮは、ｂＮ＝（ｂ１，ｂ２，・・・，ｂｎ）であるとする。なお、β（０）、β（ｊ）は群Ｚｑの元であることに留意する。
【００５８】
続いて、ｚｉ生成部（６１１）は、ＲＡＭ（２５）からｎ、ｉ、ｗｉ、ｘｉ、βφ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、ｚｉ＝ｗｉ−β（ｉ）×ｘｉを演算し、この演算結果ｚｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１７）。β（ｉ）は、読み込んだβφを用いて、β（ｉ）＝βｎ−１×ｉ＾（ｎ−１）＋βｎ−２×ｉ＾（ｎ−２）＋・・・＋β１×ｉ＋β０によって求めることができる。なお、ｚｉは群Ｚｑの元、即ちｚｉ∈Ｚｑであることに留意する。
【００５９】
続いて、署名生成部（６１２）は、ＲＡＭ（２５）からＡ１、ｍ、ｚｉ、ｚｊ、βφ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、このうち、Ａ１、ｚｉ、ｚｊ、βφの組み合わせを、投票装置ｉにおける投票内容ｍに対する署名ξｉとする（ステップＳ１８）。即ち、ξｉ＝（Ａ１、β、ｚＮ）とする。ここでβは、β＝（β０，β１，・・・，βｎ−１）、ｚＮは、ｚＮ＝（ｚ１，ｚ２，・・・，ｚｎ）である。
【００６０】
続いて、投票装置ｉは、制御部（６１３）の制御によって、通信部（２３）を通じて、ステップＳ１８で生成された署名ξｉおよび投票内容ｍを、匿名通信路を経由して情報公開サーバ（１）に送信する（ステップＳ１９）。これが「電子投票」に相当する。
【００６１】
情報公開サーバ（１）は、情報取得部（８０１）によって、その通信部(１３）を通じて、ステップＳ１９で送信された署名ξｉおよび投票内容ｍを受信し、署名ξｉおよび投票内容ｍを対応付けて外部記憶装置（１７）に保存記憶する（ステップＳ２ｓ）。
【００６２】
各投票装置からも同様の電子投票が行われ、結果として、情報公開サーバ（１）の外部記憶装置（１７）には、各投票装置から電子投票された投票結果が保存記憶される（図１０参照）。
【００６３】
［開票］
続いて、開票装置（３）による電子投票の開票処理について説明する。
開票装置（３）の外部記憶装置（３７）には、巡回群Ｇの生成元ｇが予め保存記憶されているとする。
【００６４】
開票装置（３）は、制御部（７１１）の制御によって、その通信部（３３）を通じて、情報公開サーバ（１）にアクセスし、情報公開サーバ（１）の通信部（１３）を通じて送信された（ステップＳ３ｓ）、情報公開サーバ（１）の外部記憶装置（１７）に記憶される全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝、全公開鍵証明書｛ｃｅｒｔ１，・・・，ｃｅｒｔｎ｝（これらは有権者名簿に相当する。）を受信し、これらを開票装置（３）の外部記憶装置（３７）に保存記憶する。また、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎも、開票装置（３）の外部記憶装置（３７）に保存記憶する（ステップＳ２１）。
次いで、開票装置（３）の図示しない検証部（所定のプログラムを解釈実行するＣＰＵ（３４）によって機能が実現する。）は、各公開鍵証明書を検証する（ステップＳ２２）。この検証に全て合格したならば、下記の所定の処理を実行する。この検証に合格しなかったならば、取得した公開鍵の中に不正な公開鍵が含まれていることを示すものであるから、開票装置（３）は下記の処理を実行せずに終了する（ステップＳ２３）。
なお、検証処理は、ＰＫＩにおける公知技術で達成されるから詳細な説明を省略する。また、相互に通信可能なサーバ（情報公開サーバ）−クライアント（投票装置）間で、サーバからクライアント（あるいは逆に、クライアントからサーバ）にアクセスして所定の情報（データ）を取得し、取得した情報（データ）を外部記憶装置に保存記憶することも公知技術で達成されるから、この明細書ではその詳細な説明を省略する。
【００６５】
まず、開票装置（３）は、制御部（７１１）の制御によって、その通信部（３３）を通じて、情報公開サーバ（１）にアクセスし、情報公開サーバ（１）の通信部（１３）を通じて送信された（ステップ４ｓ）、情報公開サーバ（１）の外部記憶装置（１７）に記憶される有効投票総数の計数処理を行う投票内容ｍおよびその投票内容ｍに対応付けられた署名を全て受信し、外部記憶装置（３７）に保存記憶する（ステップＳ２４）。ここでは、投票内容ｍに電子投票した投票総数（有効投票総数ではない。）をｅ（ｅ≦ｎ）とする。従って、受信する署名はｅ個である。
【００６６】
続いて、制御部（７１１）の制御によって、外部記憶装置（３７）から、巡回群Ｇの生成元ｇ、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝、投票内容ｍ、ｅ個の署名から１個選択した署名ξ＝（Ａ１、β、ｚＮ）、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２５）。また、制御部（７１１）の制御によって、ＲＡＭ（３５）に値ｖおよび値Ｆを格納する所定の格納領域を確保する。値ｖおよび値Ｆの初期値は０とする。
【００６７】
次に、ｈ生成部（７００）は、ＲＡＭ（３５）からｎ、ｍ、ｙＮをそれぞれ読み込み、ｈ＝Ｈ（ｎ，ｙＮ，ｍ）を演算し、この演算結果ｈをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２６）。なお、ｈは巡回群Ｇの元、即ちｈ∈Ｇであることに留意する。
【００６８】
次に、Ａ０生成部（７０１）は、ＲＡＭ（３５）からｎ、ｍ、ｙＮをそれぞれ読み込み、Ａ０＝Ｈ’（ｎ，ｙＮ，ｍ）を演算し、この演算結果Ａ０をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２７）。なお、Ａ０は巡回群Ｇの元、即ちＡ０∈Ｇであることに留意する。
【００６９】
次に、Ａ１検証部（７０２）は、ＲＡＭ（３５）からＡ１を読み込み、Ａ１が巡回群Ｇの元であるか否かを検証する（ステップＳ２８）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。
【００７０】
次に、σＮ生成部（７０３）は、ＲＡＭ（３５）からＡ０、Ａ１、ｎをそれぞれ読み込み、σｆ＝Ａ０（Ａ１＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果σＮ（＝（σ１，σ２，・・・，σｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２９）。このσＮが、臨時公開鍵に相当する。なお、σＮ（＝（σ１，σ２，・・・，σｎ））はそれぞれ巡回群Ｇの元、即ちσＮ∈Ｇであることに留意する。また、ステップＳ２９で生成されたσＮには固有臨時公開鍵と撹乱臨時公開鍵が含まれるが、いずれのσｆが署名ξをもって電子投票した投票装置において生成された固有臨時公開鍵であるかは判別できないことにも留意すること（電子投票における匿名性の確保）。
【００７１】
続いて、βφ検証部（７０４）は、ＲＡＭ（３５）からβφ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、各βφ（φ＝０，１，２，・・・，ｎ−１）が群Ｚｑの元であるか否かを検証する（ステップＳ３０）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。
【００７２】
続いて、次数検証部（７０５）は、ＲＡＭ（３５）からｎ、βφ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、βφの個数がｎであるか否かを検証する（ステップＳ３１）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。
【００７３】
続いて、ｚ検証部（７０６）は、ＲＡＭ（３５）からｚＮ（＝（ｚ１，ｚ２，・・・，ｚｎ））をそれぞれ読み込み、各ｚＮ（＝（ｚ１，ｚ２，・・・，ｚｎ））が群Ｚｑの元であるか否かを検証する（ステップＳ３２）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。
【００７４】
続いて、ａ’Ｎ生成部（７０７）は、ＲＡＭ（３５）からｎ、ｇ、βφ、ｚＮ、ｙＮをそれぞれ読み込み、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾β（ｆ））〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ａ’Ｎ（＝（ａ’１，ａ’２，・・・，ａ’ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３３）。β（ｆ）は、読み込んだβφを用いて、β（ｆ）＝βｎ−１×ｆ＾（ｎ−１）＋βｎ−２×ｆ＾（ｎ−２）＋・・・＋β１×ｆ＋β０によって求めることができる。なお、ａ’Ｎ（＝（ａ’１，ａ’２，・・・，ａ’ｎ））はそれぞれ巡回群Ｇの元、即ちａ’Ｎ∈Ｇであることに留意する。
【００７５】
続いて、ｂ’Ｎ生成部（７０８）は、ＲＡＭ（３５）からｎ、ｈ、βφ、ｚＮ、σＮをそれぞれ読み込み、ｂ’ｆ＝（ｈ＾ｚｆ）×（σｆ＾β（ｆ））〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ｂ’Ｎ（＝（ｂ’１，ｂ’２，・・・，ｂ’ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３４）。β（ｆ）は、読み込んだβφを用いて、β（ｆ）＝βｎ−１×ｆ＾（ｎ−１）＋βｎ−２×ｆ＾（ｎ−２）＋・・・＋β１×ｆ＋β０によって求めることができる。なお、ｂ’Ｎ（＝（ｂ’１，ｂ’２，・・・，ｂ’ｎ））はそれぞれ巡回群Ｇの元、即ちｂ’Ｎ∈Ｇであることに留意する。
【００７６】
続いて、判定部（７０９）は、ＲＡＭ（３５）からｎ、ｙＮ、ｍ、ｈ、Ａ０、Ａ１、ａ’Ｎ、ｂ’Ｎ、βφをそれぞれ読み込み、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，ｈ，Ａ０，Ａ１，ａ’Ｎ，ｂ’Ｎ）が成立するか否かを判定し、この判定結果ＲをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３５）。この判定が成立しなかった場合（判定不成立）、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ以降の処理を行う。この判定が成立した場合（判定成立）、制御部（７１１）は、以下の処理を実行するように制御する。
【００７７】
続いて、カウンタ部（７１０）は、ＲＡＭ（３５）からｖを読み込み、この値に１を加えた値ｖ＋１を、ＲＡＭ（３５）の値ｖが格納されている格納領域に上書きで格納する（ステップＳ３６）。ここで上書きとは、予め格納されている値を消除して新たな値を格納することをいう。
【００７８】
続いて、フラッグ部（７１２）は、フラッグ値Ｆ＝１をＲＡＭ（３５）の値Ｆが格納されている格納領域に上書きで格納する（ステップＳ３７）。
【００７９】
制御部（７１１）の制御によって、以上の処理で求められた値ＦおよびσＮを、外部記憶装置（３７）に保存記憶される署名ξに対応付けて保存記憶する（ステップＳ３８）。なお、ステップＳ３７の処理が実行されなかった署名ξには、フラッグ値Ｆ＝０が対応付けられる。
【００８０】
以上の処理をｅ個の署名全てについて行うことで（ステップＳ３９）、投票内容ｍに対応付けられたｅ個の署名のうち、有権者による投票の総数を計数することができる。つまり、ｅ個の署名全てについて以上の処理を行った後に、ＲＡＭ（３５）の所定の格納領域に格納されているｖの値が、有権者による（投票内容ｍの）投票の総数を表している。そこで、制御部（７１１）の制御によって、以上の処理で求められた値ｖを、外部記憶装置（３７）に保存記憶する（ステップＳ４０）。
【００８１】
続いて、重複投票の有無を検証する処理を行う。
ステップＳ２９で生成されたσＮには固有臨時公開鍵と撹乱臨時公開鍵が含まれるが、この固有臨時公開鍵は投票装置（投票者）に固有のものであるから、複数の署名に同一の固有臨時公開鍵が含まれないことを利用する（もし、同一の固有臨時公開鍵が含まれれば、重複投票と看做すことができる。）。なお、既述のとおり、いずれのσｆが投票装置（投票者）に固有の固有臨時公開鍵であるかは不明であるが、投票装置ｉから電子投票された署名から求められたσＮにおいては、ｉ番目のσｉが固有臨時公開鍵であるから、各署名から求められたσＮそれぞれのｉ番目のσｉの値を比較し、同一の値が存在すれば、この同一値を与えるσｉを含むσＮを生成した署名は不正な電子投票に基づくものとして、計数から除外することが可能になる（電子投票における一人一票の確保）。
【００８２】
まず、制御部（７１１）の制御によって、値Ｆ＝１が対応付けられた署名に対応付けられたσＮを外部記憶装置（３７）から読み込み、ＲＡＭ（３５）の所定の格納領域に格納する。また、制御部（７１１）の制御によって、値ｖも外部記憶装置（３７）から読み込み、ＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ４１）。ここでは説明の便宜から、投票内容ｍに対応付けられたｅ個の署名をξ２、ξ３、ξ５、ξ８、ξ１０、ξ１７、・・・とし、このうち値Ｆ＝１が対応付けられた署名をξ３、ξ５、ξ８、ξ１７、・・・とする。また、値Ｆ＝１が対応付けられた署名に対応付けられたσＮをσＮ（ξ３）、σＮ（ξ５）、σＮ（ξ８）、σＮ（ξ１７）、・・・とする。
【００８３】
次に、重複投票検証部（７１３）は、ＲＡＭ（３５）からσＮ（ξ３）、σＮ（ξ５）、σＮ（ξ８）、σＮ（ξ１７）、・・・およびｖを読み込み、ｆ＝１，２，・・・，ｎについて、σｆ（ξ３）、σｆ（ξ５）、σｆ（ξ８）、σｆ（ξ１７）、・・・に同一の値が存在するか否かを検証し、同一の値が存在する場合、その値が存在するσＮの数（τ）を計数する（ステップＳ４２）。重複投票検証部（７１３）は、ｖ−τを求めて、この値をＲＡＭ（３５）の値ｖが格納されている格納領域に上書きで格納する（ステップＳ４３）。
【００８４】
制御部（７１１）の制御によって、以上の処理で求められた値ｖを、外部記憶装置（３７）に保存記憶する。この値ｖが、重複投票による無効投票を排除した、有権者による（投票内容ｍに対する）電子投票の有効投票総数を表している。
【００８５】
以上の処理を、各投票内容ｍ１，ｍ２，・・・，ｍｓについて行うことで、各投票内容に対する有効投票総数を計数できる。
【００８６】
開票装置（３）は、制御部（７１１）の制御によって、その通信部（３３）を通じて、情報公開サーバ（１）に対し、計数された各投票内容に対する有効投票総数を送信する。情報公開サーバ（１）は、開票装置（３）から各投票内容に対する有効投票総数を受信し、この各投票内容に対する有効投票総数を外部記憶装置（１７）に保存記憶する。
結果、各投票装置は、情報公開サーバに対してアクセスすることで、開票結果（各投票内容に対する有効投票総数）を取得することが可能になる。
【００８７】
＜第２実施形態＞
次に、本発明の第２実施形態について、図１５から図２０を参照しながら説明する。
第１実施形態では、多項式β（ｘ）の係数を用いた電子投票・開票処理を行ったが、第２実施形態では、多項式の係数を用いない電子投票・開票処理を説明する。これにより、電子投票における署名生成処理・開票における検証処理の演算量を低減することができる。
なお、第２実施形態では、第１実施形態と同一の機能・処理については同一の符号を与えるなどして説明を省略する。
図１５は、第２実施形態における投票装置（２’）の機能構成例を示す図である。
図１６は、投票装置（２’）における処理フローを示す図である（その１）。
図１７は、投票装置（２’）における処理フローを示す図である（その２）。
図１８は、第２実施形態における開票装置（３）の機能構成例を示す図である。
図１９は、開票装置（３’）における処理フローを示す図である（その１）。
図２０は、開票装置（３’）における処理フローを示す図である（その２）。
【００８８】
[投票装置]
第２実施形態における投票装置（２’）について説明する。
第２実施形態に係わる投票装置（２’）の外部記憶装置（２７）には、電子投票のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。
【００８９】
第２実施形態に係わる投票装置（２’）の外部記憶装置（２７）〔あるいはＲＯＭなど〕には、値βφを生成するプログラムに替えて値ｃｉを生成するためのプログラムが保存記憶されている。その他のプログラムは第１実施形態と同様である。
【００９０】
第２実施形態に係わる投票装置（２’）では、外部記憶装置（２７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（２５）に読み込まれて、ＣＰＵ（２４）で解釈実行・処理される。その結果、ＣＰＵ（２４）が所定の機能（ｈ生成部、σｉ生成部、σｊ生成部、Ａ０生成部、Ａ１生成部、ａｉ生成部、ｂｉ生成部、ａｊ生成部、ｂｊ生成部、ｚｉ生成部、ｃｉ生成部、元選択部、署名生成部、制御部）を実現することで、電子投票における投票が実現される。
【００９１】
［開票装置］
第２実施形態における開票装置について説明する。
第２実施形態に係わる開票装置（３’）の外部記憶装置（３７）〔あるいはＲＯＭなど〕には、βφを検証するためのプログラム、βφの個数を検証するためのプログラム、βφ（φ＝０）と所定の値との一致を判定するためのプログラムに替えて、元ｃを検証するためのプログラム、元ｃと所定の値との一致を判定するためのプログラムが保存記憶されている。
【００９２】
開票装置（３’）では、外部記憶装置（３７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（３５）に読み込まれて、ＣＰＵ（３４）で解釈実行・処理される。その結果、ＣＰＵ（３４）が所定の機能（ｈ生成部、σＮ生成部、Ａ０生成部、ａ’Ｎ生成部、ｂ’Ｎ生成部、ｚ検証部、ｃ検証部、Ａ１検証部、判定部、カウンタ部、フラッグ部、重複投票検証部、制御部）を実現することで、電子投票における開票が実現される。
【００９３】
[投票]
第１実施形態のステップＳ１からステップＳ１５までは同じ処理を行う。
第１実施形態における投票装置ｉのステップＳ１６では、βφ生成部（６１０）が、次数（ｎ−１）の多項式β（ｘ）∈Ｚｑ［ｘ］の係数βφ（φ＝０，１，２，・・・，ｎ−１）を求めたが、第２実施形態では、ｃｉ生成部（６１５）がｃｉを求める。即ち、ｃｉ生成部（６１５）は、ＲＡＭ（２５）からｎ、ｙＮ、ｍ、ｈ、Ａ０、Ａ１、ａｉ、ａｊ、ｂｉ、ｂｊ、ｃｊをそれぞれ読み込み、式（１）の演算を行い、この演算結果ｃｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１６’）。ここで、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎであり、ａＮは、ａＮ＝（ａ１，ａ２，・・・，ａｎ）であり、ｂＮは、ｂＮ＝（ｂ１，ｂ２，・・・，ｂｎ）であるとする。なお、ｃｉは群Ｚｑの元、即ちｃｉ∈Ｚｑであることに留意する。
【数１】
0004630144.tif 000002
【００９４】
第１実施形態における投票装置ｉのステップＳ１７では、ｚｉ生成部（６１１）が、ｚｉ＝ｗｉ−β（ｉ）×ｘｉを演算し、この演算結果ｚｉを求めたが、第２実施形態では、ｚｉ生成部（６１６）が第１実施形態とは異なるｚｉを求める。即ち、ｚｉ生成部（６１６）は、ＲＡＭ（２５）からｗｉ、ｘｉ、ｃｉをそれぞれ読み込み、ｚｉ＝ｗｉ−ｃｉ×ｘｉを演算し、この演算結果ｚｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１７’）。なお、ｚｉは群Ｚｑの元、即ちｚｉ∈Ｚｑであることに留意する。
【００９５】
第１実施形態における投票装置ｉのステップＳ１８では、署名生成部（６１２）が、Ａ１、ｚｉ、ｚｊ、βφの組み合わせを、投票装置ｉにおける投票内容ｍに対する署名ξｉとしたが、第２実施形態では、署名生成部（６１７）が第１実施形態とは異なる署名を求める。即ち、署名生成部（６１７）は、ＲＡＭ（２５）からＡ１、ｍ、ｚｉ、ｚｊ、ｃｉ、ｃｊをそれぞれ読み込み、このうち、Ａ１、ｚｉ、ｚｊ、ｃｉ、ｃｊの組み合わせを、投票装置ｉにおける投票内容ｍに対する署名ξｉとする（ステップＳ１８’）。即ち、ξｉ＝（Ａ１、ｃＮ、ｚＮ）とする。ここでｚＮは、ｚＮ＝（ｚ１，ｚ２，・・・，ｚｎ）、ｃＮは、ｃＮ＝（ｃ１，ｃ２，・・・，ｃｎ）である。ステップＳ１８’以降は、第１実施形態と同様の処理を行う。
【００９６】
[開票]
第１実施形態のステップＳ２０からステップＳ２３までは同じ処理を行う。
第１実施形態における開票装置（３）のステップＳ２４では、制御部（７１１）の制御によって、外部記憶装置（３７）から、巡回群Ｇの生成元ｇ、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝、投票内容ｍ、ｅ個の署名から１個選択した署名ξ＝（Ａ１、β、ｚＮ）、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（３５）の所定の格納領域に格納したが、第２実施形態では、制御部（７１１）の制御によって、外部記憶装置（３７）から、巡回群Ｇの生成元ｇ、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝、投票内容ｍ、ｅ個の署名から１個選択した署名ξ＝（Ａ１、ｃＮ、ｚＮ）、全投票者（有権者）の公開鍵｛ｙ１，…，ｙｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２４’）。
【００９７】
ステップＳ２４’以降は、第１実施形態におけるステップＳ２５からステップＳ２９までと同様の処理を行う。
【００９８】
第１実施形態における開票装置（３）のステップＳ３０では、βφ検証部（７０４）が、ＲＡＭ（３５）からβφ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、各βφ（φ＝０，１，２，・・・，ｎ−１）が群Ｚｑの元であるか否かを検証したが、第２実施形態では不要の処理となる。
【００９９】
また、第１実施形態における開票装置（３）のステップＳ３１では、次数検証部（７０５）は、ＲＡＭ（３５）からｎ、βφ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、βφの個数がｎであるか否かを検証したが、第２実施形態では不要の処理となる。
【０１００】
第２実施形態では、ステップＳ３２に続き、ｃ検証部（７１５）が、ＲＡＭ（３５）からｃＮ（＝（ｃ１，ｃ２，・・・，ｃｎ））をそれぞれ読み込み、各ｃＮ（＝（ｃ１，ｃ２，・・・，ｃｎ））が群Ｚｑの元であるか否かを検証する（ステップＳ３２ａ）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行い（ステップＳ４５）、この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御することは第１実施形態と同様である。
【０１０１】
第１実施形態における開票装置（３）のステップＳ３３では、ａ’Ｎ生成部（７０７）がａ’Ｎを求めたが、第２実施形態では、第１実施形態と異なるａ’Ｎを求める。即ち、ａ’Ｎ生成部（７１６）は、ＲＡＭ（３５）からｎ、ｇ、ｃＮ、ｚＮ、ｙＮをそれぞれ読み込み、ａ’ｆ＝（ｇ＾ｚｆ）×（ｙｆ＾ｃｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ａ’Ｎ（＝（ａ’１，ａ’２，・・・，ａ’ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３３’）。なお、ａ’Ｎ（＝（ａ’１，ａ’２，・・・，ａ’ｎ））はそれぞれ巡回群Ｇの元、即ちａ’Ｎ∈Ｇであることに留意する。
【０１０２】
第１実施形態における開票装置（３）のステップＳ３４では、ｂ’Ｎ生成部（７０８）がｂ’Ｎを求めたが、第２実施形態では、第１実施形態と異なるｂ’Ｎを求める。即ち、ｂ’Ｎ生成部（７１７）は、ＲＡＭ（３５）からｎ、ｈ、ｃＮ、ｚＮ、σＮをそれぞれ読み込み、ｂ’ｆ＝（ｈ＾ｚｆ）×（σｆ＾ｃｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ｂ’Ｎ（＝（ｂ’１，ｂ’２，・・・，ｂ’ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３４’）。なお、ｂ’Ｎ（＝（ｂ’１，ｂ’２，・・・，ｂ’ｎ））はそれぞれ巡回群Ｇの元、即ちｂ’Ｎ∈Ｇであることに留意する。
【０１０３】
第１実施形態における開票装置（３）のステップＳ３５では、判定部（７０９）が、β（０）＝Ｈ”（ｎ，ｙＮ，ｍ，ｈ，Ａ０，Ａ１，ａＮ，ｂＮ）が成立するか否かを判定したが、第２実施形態では異なる判定を行う。即ち、判定部（７１８）は、ＲＡＭ（３５）からｎ、ｙＮ、ｍ、ｈ、Ａ０、Ａ１、ａ’Ｎ、ｂ’Ｎ、ｃＮをそれぞれ読み込み、式（２）が成立するか否かを判定し、この判定結果ＲをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３５’）。この判定が成立しなかった場合（判定不成立）、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行い（ステップＳ４５）、この判定が成立した場合（判定成立）、制御部（７１１）は、以下の処理を実行するように制御することは第１実施形態と同様である。ステップＳ３５’以降は、第１実施形態と同様の処理を行う。
【数２】
0004630144.tif 000003
【０１０４】
本発明である電子投票装置、開票装置、情報公開サーバ、電子投開票システム・方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、署名生成方法や投票署名の検証方法は適宜に変更可能である。また、上記電子投開票システム・方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１０５】
また、上記電子投票装置、開票装置、情報公開サーバにおける処理機能をコンピュータによって実現する場合、電子投票装置、開票装置、情報公開サーバが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記電子投票装置、開票装置、情報公開サーバにおける処理機能がコンピュータ上で実現される。
【０１０６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１０７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、電子投票装置、開票装置、情報公開サーバを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１１０】
本発明は電子投開票に有用である。
【図面の簡単な説明】
【０１１１】
【図１】第１実施形態に係わる情報公開サーバ（１）のハードウェア構成を例示した構成ブロック図。
【図２】第１実施形態に係わる投票装置（２）のハードウェア構成を例示した構成ブロック図である。
【図３】第１実施形態に係わる開票装置（３）のハードウェア構成を例示した構成ブロック図。
【図４】第１実施形態の電子投票システムにおけるネットワーク構成を示す図（但し、電子投票が行われる前の状態を示している。）。
【図５】情報公開サーバ（１）における処理フローを示す図。
【図６】投票装置（２）の機能構成例を示す図。
【図７】投票装置（２）における処理フローを示す図（その１）。
【図８】投票装置（２）における処理フローを示す図（その２）。
【図９】電子投票後における状態を示す図。
【図１０】開票装置（３）の機能構成例を示す図。
【図１１】開票装置（３）における処理フローを示す図（その１）。
【図１２】開票装置（３）における処理フローを示す図（その２）。
【図１３】開票装置（３）において重複投票を検証する処理における機能構成を例示した図。
【図１４】開票装置（３）において重複投票を検証する処理フローを示す図。
【図１５】第２実施形態における投票装置（２’）の機能構成例を示す図。
【図１６】投票装置（２’）における処理フローを示す図（その１）。
【図１７】投票装置（２’）における処理フローを示す図（その２）。
【図１８】第２実施形態における開票装置（３）の機能構成例を示す図。
【図１９】開票装置（３’）における処理フローを示す図（その１）。
【図２０】開票装置（３’）における処理フローを示す図（その２）。
【符号の説明】
【０１１２】
１  情報公開サーバ
２  投票装置
３  開票装置
４  ＣＡ（認証局）
５  ネットワーク
６０１  σｉ生成部
６０３  Ａ１生成部
６０４  σｊ生成部
６１２  署名生成部
７０２  Ａ１検証部
７０３  σＮ生成部
７０９  判定部
７１０  カウンタ部
【図１】
0004630144.tif 000004
【図２】
0004630144.tif 000005
【図３】
0004630144.tif 000006
【図４】
0004630144.tif 000007
【図５】
0004630144.tif 000008
【図６】
0004630144.tif 000009
【図７】
0004630144.tif 000010
【図８】
0004630144.tif 000011
【図９】
0004630144.tif 000012
【図１０】
0004630144.tif 000013
【図１１】
0004630144.tif 000014
【図１２】
0004630144.tif 000015
【図１３】
0004630144.tif 000016
【図１４】
0004630144.tif 000017
【図１５】
0004630144.tif 000018
【図１６】
0004630144.tif 000019
【図１７】
0004630144.tif 000020
【図１８】
0004630144.tif 000021
【図１９】
0004630144.tif 000022
【図２０】
0004630144.tif 000023