(57)【要約】無記名電子投票において、票の水増しや投票内容の改竄が行われていないことの確認を票の売買等の不正に利用できるような情報を使わずにできるようにする。投票端末１０は、暗号化部１０５で投票内容ｖｉを暗号化したＥ（ｖｉ）を作成し、署名生成部１０６でＥ（ｖｉ）に対する投票端末のデジタル署名Ｓｅｉを作成し、（Ｅ（ｖｉ），Ｓｅｉ）の組を記録し、投票者の持ち帰り用の記録媒体１０７−ｉに記録する。集計端末２０は、（Ｅ（ｖｉ），Ｓｅｉ）の組全てについて、署名検証部２０３でデジタル署名の正当性を検証し、合格となった全ての（Ｅ（ｖｉ），Ｓｅｉ）の組に対してシャッフル復号部２０２でＥ（ｖｉ）を復号し、元の順番を入換えたｖｉのリストを得ると共に、Ｅ（ｖｉ）とｖｉとの間に１対１の対応関係があることの証明データｐを作成し、（Ｅ（ｖｉ），Ｓｅｉ）の組のリストとｖｉのリストと前記証明データを公表する。【特許請求の範囲】
【請求項１】
無記名電子投票システムにおいて、投票者の投票内容を暗号化して暗号化投票内容を作成し、暗号化投票内容に対する投票端末のデジタル署名を作成し、得られた暗号化投票内容とデジタル署名との組を記録媒体に記録して投票者に出力するとともに、投票端末内部の記憶装置に記録する投票端末と、前記投票端末内部の記憶装置に記録されたすべての暗号化投票内容とデジタル署名との組を読み込み、デジタル署名の正当性を検証し、暗号化投票内容のリストを復号するとともに順序を入れ替えて平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとのあいだに１対１の対応関係が存在することの証明データを作成する集計端末とを含むことを特徴とする電子投票システム。
【請求項２】
請求項１に記載の無記名電子投票システムにおいて、投票者の持ち帰った記録媒体に記録されたデータが、集計端末に入力された暗号化データのリストに含まれていることの確認を行なう検証装置を含むことを特徴とする電子投票システム。
【請求項３】
請求項１に記載の無記名電子投票システムにおいて、投票者の持ち帰った記録媒体に記録されたデータが、集計端末に入力された暗号化データのリストに含まれていることの確認と、集計端末の作成した証明データの正当性の検証を行なう検証装置を含むことを特徴とする電子投票システム。
【請求項４】
請求項１に記載の無記名電子投票システムにおいて、集計端末の出力した暗号投票内容と投票端末のデジタル署名の組とのリストについて、投票端末のデジタル署名が正当なものかどうかの検証を行なう検証装置を含むことを特徴とする電子投票システム。
【請求項５】
無記名電子投票システムにおいて、投票者個人とは関連づけされない、投票用ＩＣカード固有のデジタル署名を生成して出力する投票用ＩＣカードと、投票内容を暗号化して暗号化投票データを作成し、暗号化投票データに対し、前記投票用ＩＣカードによりデジタル署名を作成し、得られた暗号化投票データと投票用ＩＣカードのデジタル署名との組とを記録媒体に記録して投票者に出力するとともに、投票端末内部の記憶装置に記録する投票端末と、前記投票端末内部の記憶装置に記録されたすべての暗号化投票データと投票用ＩＣカードのデジタル署名との組を読み込み、デジタル署名の正当性を検証し、暗号化投票データのリストを復号するとともに順序を入れ替えて平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとのあいだに１対１の対応関係が存在することの証明データを作成する集計端末とを含むことを特徴とする電子投票システム。
【請求項６】
請求項５に記載の無記名電子投票システムにおいて、投票者の持ち帰った記録媒体に記録されたデータが、集計端末に入力された暗号化データのリストに含まれていることの確認を行なう検証装置を含むことを特徴とする電子投票システム。
【請求項７】
請求項５に記載の無記名電子投票システムにおいて、投票者の持ち帰った記録媒体に記録されたデータが、集計端末に入力された暗号化データのリストに含まれていることの確認と、集計端末の作成した証明データの正当性の検証を行なう検証装置を含むことを特徴とする電子投票システム。
【請求項８】
請求項５に記載の無記名電子投票システムにおいて、集計端末の出力した暗号投票内容と投票用ＩＣカードのデジタル署名の組とのリストについて、投票用ＩＣカードのデジタル署名が正当なものかどうかの検証を行なう検証装置を含むことを特徴とする電子投票システム。
【請求項９】
投票端末と集計端末と検証装置とで構成され、
前記投票端末は、投票入力装置、投票出力装置、投票記憶装置および投票制御装置を備え、前記投票制御装置は、前記投票入力装置から投票者の投票内容を入力し前記投票記憶装置に記憶する投票入力手段と、前記投票記憶装置から投票内容を入力し暗号化して前記投票記憶装置に記憶する暗号化手段と、前記投票記憶装置から暗号化投票内容を入力しそれに対する前記投票端末のデジタル署名を作成し、前記暗号化投票内容と前記デジタル署名との組を前記投票記憶装置に記憶する署名生成手段と、前記投票記憶装置から前記暗号化投票内容と前記デジタル署名との組を入力し、前記投票出力装置により前記投票者に持ち帰らせる記録媒体に出力する出力手段とを備え、
前記集計端末は、集計記憶装置、公表装置および集計制御装置を備え、前記集計制御装置は、前記投票記憶装置に記録された全ての暗号化投票内容とデジタル署名との組を入力し前記集計記憶装置に記憶する集計入力手段と、前記集計記憶装置から前記暗号化投票内容とデジタル署名の組を入力し、それぞれのデジタル署名の正当性を検証し、検証に合格した暗号化投票内容のリストを前記集計記憶装置に記憶する署名検証手段と、前記集計記憶装置から暗号化投票内容のリストを入力し、復号するとともに順序を入れ替えて平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとの間に１対１の対応関係が存在することの証明データを作成し、前記平文の投票内容のリストと前記証明データを前記集計記憶装置に記憶するシャッフル復号手段と、前記集計記憶装置に記憶された暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを前記公表装置により公表する公表手段とを備え、
前記検証装置は、検証記憶装置、検証制御装置、検証入力装置及び検証出力装置を備え、前記検証制御装置は、前記公表装置により公表された暗号化投票内容のリスト、平文の投票内容のリスト及び証明データを取得して前記検証記憶装置に記憶する取得手段と、前記投票者に持ち帰らせた前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力して前記検証記憶装置に記憶する入力手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力しそのデジタル署名の正当性を検証すると共に前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中の各デジタル署名の正当性を検証し、検証結果を前記検証記憶装置に記憶する署名検証手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力し、その組と同じものが前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中に存在するかどうかを調べ、その結果を前記検証記憶装置に記憶するリスト照合手段と、前記検証記憶装置から暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを入力し、前記証明データの正当性を検証し、その検証結果を前記検証記憶装置に記憶するシャッフル復号検証手段と、前記検証記憶装置から前記署名検証部および前記シャッフル復号検証手段の検証結果および前記リスト照合手段の照合結果を入力し、前記検証出力装置から出力する出力手段とを備えることを特徴とする電子投票システム。
【請求項１０】
投票端末と集計端末と検証装置とで構成され、
前記投票端末は、投票者個人とは関連づけされない投票用ＩＣカード固有のデジタル署名を生成して出力する機能を持つ投票用ＩＣカードに対するＩＣカード入出力装置、投票入力装置、投票出力装置、投票記憶装置および投票制御装置を備え、前記投票制御装置は、前記投票入力装置から投票者の投票内容を入力し前記投票記憶装置に記憶する投票入力手段と、前記投票記憶装置から投票内容を入力し暗号化して前記投票記憶装置に記憶する暗号化手段と、前記投票記憶装置から暗号化投票内容を入力して前記ＩＣカード入出力装置に装填された前記投票用ＩＣカードに送り、前記暗号化投票内容と前記投票用ＩＣカードが前記暗号化投票内容に対して作成したデジタル署名との組を前記投票記憶装置に記憶する署名要請手段と、前記投票記憶装置から前記暗号化投票内容と前記デジタル署名との組を入力し、前記投票出力装置により前記投票者に持ち帰らせる記録媒体に出力する出力手段とを備え、
前記集計端末は、集計記憶装置、公表装置および集計制御装置を備え、前記集計制御装置は、前記投票記憶装置に記録された全ての暗号化投票内容とデジタル署名との組を入力し前記集計記憶装置に記憶する集計入力手段と、前記集計記憶装置から前記暗号化投票内容とデジタル署名の組を入力し、それぞれのデジタル署名の正当性を検証し、検証に合格した暗号化投票内容のリストを前記集計記憶装置に記憶する署名検証手段と、前記集計記憶装置から暗号化投票内容のリストを入力し、復号するとともに順序を入れ替えて平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとの間に１対１の対応関係が存在することの証明データを作成し、前記平文の投票内容のリストと前記証明データを前記集計記憶装置に記憶するシャッフル復号手段と、前記集計記憶装置に記憶された暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを前記公表装置により公表する公表手段とを備え、
前記検証装置は、検証記憶装置、検証制御装置、検証入力装置及び検証出力装置を備え、前記検証制御装置は、前記公表装置により公表された暗号化投票内容のリスト、平文の投票内容のリスト及び証明データを取得して前記検証記憶装置に記憶する取得手段と、前記投票者に持ち帰らせた前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力して前記検証記憶装置に記憶する入力手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力しそのデジタル署名の正当性を検証すると共に前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中の各デジタル署名の正当性を検証し、検証結果を前記検証記憶装置に記憶する署名検証手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力し、その組と同じものが前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中に存在するかどうかを調べ、その結果を前記検証記憶装置に記憶するリスト照合手段と、前記検証記憶装置から暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを入力し、前記証明データの正当性を検証し、その検証結果を前記検証記憶装置に記憶するシャッフル復号検証手段と、前記検証記憶装置から前記署名検証部および前記シャッフル復号検証手段の検証結果および前記リスト照合手段の照合結果を入力し、前記検証出力装置から出力する出力手段とを備えることを特徴とする電子投票システム。
【請求項１１】
投票端末が、投票者の投票内容を暗号化して暗号化投票内容を作成し、暗号化投票内容に対する投票端末のデジタル署名を作成し、得られた暗号化投票内容とデジタル署名との組を記録媒体に記録して投票者に出力するとともに、投票端末内部の記憶装置に記録し、集計端末が、前記投票端末内部の記憶装置に記録されたすべての暗号化投票内容とデジタル署名との組を読み込み、デジタル署名の正当性を検証し、暗号化投票内容のリストをシャッフル復号して平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとのあいだに１対１の対応関係が存在することの証明データを作成することを特徴とする電子投票方法。
【請求項１２】
投票用ＩＣカードが、投票内容を入力とし、投票内容に対して、投票者個人とは関連づけされない、投票用ＩＣカード固有のデジタル署名を生成して出力し、投票端末が投票内容を暗号化して暗号化投票データを作成し、暗号化投票データに対して前記投票用ＩＣカードによりデジタル署名を作成し、得られた暗号化投票データと投票端末のデジタル署名との組を記録媒体に記録して投票者に出力するとともに、投票端末内部の記憶装置に記録し、集計端末が、前記投票端末内部の記憶装置に記録されたすべての暗号化投票データと投票用ＩＣカードのデジタル署名との組を読み込み、デジタル署名の正当性を検証し、暗号化投票データのリストを復号するとともに順序の入れ換えを行なって平文の投票内容のリストを作成することを特徴とする電子投票方法。
【請求項１３】
投票入力装置、投票出力装置、投票記憶装置および投票制御装置を備えた投票システムの前記投票制御装置を構成するコンピュータを、前記投票入力装置から投票者の投票内容を入力し前記投票記憶装置に記憶する投票入力手段と、前記投票記憶装置から投票内容を入力し暗号化して前記投票記憶装置に記憶する暗号化手段と、前記投票記憶装置から暗号化投票内容を入力しそれに対する前記投票端末のデジタル署名を作成し、前記暗号化投票内容と前記デジタル署名との組を前記投票記憶装置に記憶する署名生成手段と、前記投票記憶装置から前記暗号化投票内容と前記デジタル署名との組を入力し、前記投票出力装置により前記投票者に持ち帰らせる記録媒体に出力する出力手段として機能させる電子投票用プログラム。
【請求項１４】
集計記憶装置、公表装置および集計制御装置を備えた投票システムの前記集計制御装置を構成するコンピュータを、前記投票記憶装置に記録された全ての暗号化投票内容とデジタル署名との組を入力し前記集計記憶装置に記憶する集計入力手段と、前記集計記憶装置から前記暗号化投票内容とデジタル署名の組を入力し、それぞれのデジタル署名の正当性を検証し、検証に合格した暗号化投票内容のリストを前記集計記憶装置に記憶する署名検証手段と、前記集計記憶装置から暗号化投票内容のリストを入力し、復号するとともに順序を入れ替えて平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとの間に１対１の対応関係が存在することの証明データを作成し、前記平文の投票内容のリストと前記証明データを前記集計記憶装置に記憶するシャッフル復号手段と、前記集計記憶装置に記憶された暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを前記公表装置により公表する公表手段として機能させる電子投票用プログラム。
【請求項１５】
検証記憶装置、検証制御装置、検証入力装置及び検証出力装置を備えた投票システムの前記検証制御装置を構成するコンピュータを、前記公表装置により公表された暗号化投票内容のリスト、平文の投票内容のリスト及び証明データを取得して前記検証記憶装置に記憶する取得手段と、前記投票者に持ち帰らせた前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力して前記検証記憶装置に記憶する入力手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力しそのデジタル署名の正当性を検証すると共に前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中の各デジタル署名の正当性を検証し、検証結果を前記検証記憶装置に記憶する署名検証手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力し、その組と同じものが前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中に存在するかどうかを調べ、その結果を前記検証記憶装置に記憶するリスト照合手段と、前記検証記憶装置から暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを入力し、前記証明データの正当性を検証し、その検証結果を前記検証記憶装置に記憶するシャッフル復号検証手段と、前記検証記憶装置から前記署名検証部および前記シャッフル復号検証手段の検証結果および前記リスト照合手段の照合結果を入力し、前記検証出力装置から出力する出力手段として機能させる電子投票用プログラム。
【請求項１６】
投票者個人とは関連づけされない投票用ＩＣカード固有のデジタル署名を生成して出力する機能を持つ投票用ＩＣカードに対するＩＣカード入出力装置、投票入力装置、投票出力装置、投票記憶装置および投票制御装置を備えた投票システムの前記投票制御装置を構成するコンピュータを、前記投票入力装置から投票者の投票内容を入力し前記投票記憶装置に記憶する投票入力手段と、前記投票記憶装置から投票内容を入力し暗号化して前記投票記憶装置に記憶する暗号化手段と、前記投票記憶装置から暗号化投票内容を入力して前記ＩＣカード入出力装置に装填された前記投票用ＩＣカードに送り、前記暗号化投票内容と前記投票用ＩＣカードが前記暗号化投票内容に対して作成したデジタル署名との組を前記投票記憶装置に記憶する署名要請手段と、前記投票記憶装置から前記暗号化投票内容と前記デジタル署名との組を入力し、前記投票出力装置により前記投票者に持ち帰らせる記録媒体に出力する出力手段として機能させる電子投票用プログラム。
【請求項１７】
集計記憶装置、公表装置および集計制御装置を備えた投票システムの前記集計制御装置を構成するコンピュータを、前記投票記憶装置に記録された全ての暗号化投票内容とデジタル署名との組を入力し前記集計記憶装置に記憶する集計入力手段と、前記集計記憶装置から前記暗号化投票内容とデジタル署名の組を入力し、それぞれのデジタル署名の正当性を検証し、検証に合格した暗号化投票内容のリストを前記集計記憶装置に記憶する署名検証手段と、前記集計記憶装置から暗号化投票内容のリストを入力し、復号するとともに順序を入れ替えて平文の投票内容のリストを作成し、暗号化投票内容のリストと平文の投票内容のリストとの間に１対１の対応関係が存在することの証明データを作成し、前記平文の投票内容のリストと前記証明データを前記集計記憶装置に記憶するシャッフル復号手段と、前記集計記憶装置に記憶された暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを前記公表装置により公表する公表手段として機能させる電子投票用プログラム。
【請求項１８】
検証記憶装置、検証制御装置、検証入力装置及び検証出力装置を備えた投票システムの前記検証制御装置を構成するコンピュータを、前記公表装置により公表された暗号化投票内容のリスト、平文の投票内容のリスト及び証明データを取得して前記検証記憶装置に記憶する取得手段と、前記投票者に持ち帰らせた前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力して前記検証記憶装置に記憶する入力手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力しそのデジタル署名の正当性を検証すると共に前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中の各デジタル署名の正当性を検証し、検証結果を前記検証記憶装置に記憶する署名検証手段と、前記検証記憶装置から前記記録媒体に記録された暗号化投票内容とデジタル署名の組を入力し、その組と同じものが前記記録媒体に記録された暗号化投票内容とデジタル署名の組のリスト中に存在するかどうかを調べ、その結果を前記検証記憶装置に記憶するリスト照合手段と、前記検証記憶装置から暗号化投票内容とデジタル署名の組のリスト、平文の投票内容のリスト及び証明データを入力し、前記証明データの正当性を検証し、その検証結果を前記検証記憶装置に記憶するシャッフル復号検証手段と、前記検証記憶装置から前記署名検証部および前記シャッフル復号検証手段の検証結果および前記リスト照合手段の照合結果を入力し、前記検証出力装置から出力する出力手段として機能させる電子投票用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電子投票システム、電子投票方法および電子投票用プログラムに関し、特に、投票所でコンピュータを操作して無記名で投票を行う電子投票システム、電子投票方法および電子投票用プログラムに関する。
【背景技術】
【０００２】
従来のこの種の電子投票システムの一例が、特許第３３０９８７４号公報（以下、特許文献１という。）、特開２０００−２０７４８３号公報（以下、特許文献２という。）および特開２００３−２３７８１０号広報（以下、特許文献３という。）に記載されている。【０００３】
特許文献１に記載される電子投票システムは、図１０に示すように、投票所１０００に受付端末１００１と投票端末１００２を備え、集計センタ１１００に集計端末１１０１を備える。この集計端末１１０１は図示しない乱数発生器と署名作成器を備える。この従来の電子投票システムは次のように動作する。【０００４】
投票者１００３は、受付端末１００１にて有権者であることと未投票であることの確認を受け、合格であれば磁気カードなどの投票券１００４を交付される。投票者１００３が投票券１００４を投票端末１００２に入力すると、投票端末１００２は投票者１００３の投票操作を受付け、集計端末１１０１に投票データを送信する。集計端末１１０１は投票端末１００２からの投票データを受信すると、乱数発生器を用い、受信した投票データごとに相異なる乱数を生成してタグとし、署名作成器を用い、生成したタグと受信した投票データの組に対する集計端末１１０１のデジタル署名を受取署名として作成し、投票端末１００２にタグと受取署名とを送信する。投票端末１００２は、投票データと集計端末１１０１から送信されたタグと受取署名とを投票券１００４に記録し、投票者１００３はこれらが記録された投票券１００４を持ち帰る。投票期間終了後、集計端末１１０１は開票結果とともに、受信したすべての投票データとタグと受取署名の組のリストを公表する。投票者１００３は持ち帰った投票券１００４に記録された投票データとタグと受取署名の組が、集計端末１１０１の公表したリストに含まれているかどうかを確認することで、自分の投票が正しく集計されていることを確認する。【０００５】
特許文献２に記載される電子投票システムは、図１１に示すように、集計者装置２０００、管理者装置２１００、投票者装置２２００からなる。集計者装置２０００は署名検証器２００１と復号器２００２を備え、管理者装置２１００はブラインド署名生成器２１０１を備え、投票者装置２２００は暗号化器２２０１と乱数発生器２２０２と乱数成分除去器２２０３と図示しない攪乱器とを備える。この電子投票システムは次のように動作する。【０００６】
投票者は、投票内容を暗号化器２２０１により暗号化し、乱数発生器２２０２によって生成した乱数により、攪乱器を用いて暗号化した投票内容を攪乱して前処理文を作成し、管理者装置２１００に送信する。管理者装置２１００は、投票者装置２２００の正当性を確認し、受信した前処理文を署名生成器２１０１に入力し、前処理文に対するブラインド署名を生成して投票者装置２２００に送信する。各投票者は、乱数成分除去器２２０３を用い、受信した前処理文に対するブラインド署名から乱数の影響を除去し、送信した暗号化投票内容に対する管理者の管理者署名を求め、その管理者署名と上記暗号化投票内容を含む情報を集計者装置２０００へ送信するとともに、暗号化投票内容と管理者署名の組を記録する。集計者装置２０００は、署名検証器２００１により管理者署名を検証する。投票期間終了後、集計者装置２０００は、復号器２００２により上記暗号化投票内容を含む情報を復号して投票内容を得て集計を行なうとともに、受信したすべての暗号化投票内容と管理者署名の組のリストを公表する。投票者は記録した暗号化投票内容と管理者署名の組が公表されたリストに含まれているかどうか確認することで、自分の投票が受付けられていることを確認する。【０００７】
特許文献３に記載される電子投票システムは、図１２に示すように、投票管理センタ３０００、窓口センタ３１００、ひとつ以上の復号シャッフルセンタ３２００とからなる。【０００８】
投票管理センタ３０００は窓口センタ３１００を介して暗号化公開鍵を生成し、投票者（図示せず）に通知する。投票者は、投票管理センタ３０００より通知された暗号化公開鍵を用いて投票内容を暗号化する。さらに投票者個人が所有するデジタル署名用の署名鍵を用い、暗号データに投票者自身のデジタル署名を付与して投票管理センタ３０００に送信する。投票管理センタ３０００はデジタル署名を検証し、有権者名簿をもとに投票者の投票権を確認し、二重投票が行なわれていないことを確認した後、受信した暗号データを受け付ける。投票期間が終わると投票の受け付けを終了し、受け付けた暗号データのリストを窓口センタ３１００に送信する。窓口センタ３１００は暗号データのリストを受信すると、復号シャッフルセンタ３２００を介して暗号データのリストの順序入れ替えと復号を行ない、復号結果のリストと証明データを投票管理センタ３０００に返送する。投票管理センタ３０００は受け付けた暗号データとデジタル署名の組のリストと復号結果のリスト、証明データを公表する。投票者は、公表された暗号データのリストに自分が送信した暗号データが含まれているかどうか確認する。さらに、公開された暗号データとデジタル署名の組すべてについて、デジタル署名が正しいことを検証する。復号結果のリストが暗号データのリストから正しく生成されていることを、証明データをもとに検証する。これにより、投票者は自分の投票が受付けられていることと、票の改竄や水増しがないことを確認できる。また、証明データは暗号データと復号結果との対応関係を特定できないものであり、票の売買などの不正には利用できない。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
特許文献１に記載される従来技術によれば、票の水増しや投票内容の改竄が行なわれていないことを集計後に確認することができる。しかし、投票者は集計後の確認のために投票内容そのものが記録された媒体を持ち帰る必要があり、第三者がそれを見れば、投票者の投票内容を確認することができる。従って、票が集計されていることの確認のために投票者が持ち帰る情報が、票の売買などの不正に利用されるおそれがある。【００１０】
他方、特許文献２に記載される従来技術によれば、投票者が確認のため持ち帰る情報は投票内容そのものではなく、暗号化された投票内容であるため、第三者が投票内容を知ることはできない。従って、投票者が持ち帰る情報が票の売買などの不正に利用されるおそれはないが、そのかわり、投票した投票内容が正しく集計されているかどうかの確認ができない。その理由は、投票者が確認できるのは暗号化された投票内容が受付けられていることのみであり、それを復号して得られる投票内容そのものが確かに集計されているかどうかという確認を行う手段が提供されていないためである。【００１１】
また、特許文献３に記載される従来技術によれば、票の水増しや改竄が行なわれていないことの確認を、票の売買などの不正に利用できるような情報を使うことなく行なえるが、投票者はそれぞれ固有のデジタル署名を生成する必要がある。現在、デジタル署名を利用できる人は多くなく、投票のように多数の投票者が利用するシステムに用いるには問題がある。【００１２】
従って、票の水増しや投票内容の改竄が行なわれていないことの確認を、票の売買などの不正に利用できるような情報を使うことなく行え、なおかつ投票者が個人用の署名鍵を所有していなくても投票を行なえる電子投票システムの実現が要望されている。【００１３】
本発明はこのような事情に鑑みて提案されたものであり、その目的は、票の売買のような不正を防ぎつつ、投票者が自分の投票内容が集計されていることを確認でき、なおかつ投票者が個人用の署名鍵を所有していなくても投票を行なえる電子投票システムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の第１の電子投票システムは、投票所の投票端末に、暗号化部と投票端末固有の署名生成部を備え、集計端末に署名検証部とシャッフル復号部とを備えることを特徴とする。投票者は投票端末にて暗号化部により投票内容ｖｉを暗号化してＥ（ｖｉ）を作成し、署名生成部によりＥ（ｖｉ）に対する投票端末のデジタル署名Ｓｅｉを作成する。投票端末は（Ｅ（ｖｉ），Ｓｅｉ）の組を集計用に記録するとともに、投票者の持ち帰り用にも別途媒体に記録を行ない、投票者は（Ｅ（ｖｉ），Ｓｅｉ）の記録された持ち帰り用の媒体を持ち帰る。集計端末では（Ｅ（ｖｉ），Ｓｅｉ）の組すべてについて、署名検証部により投票端末のデジタル署名の正当性を検証し、合格となったすべての（Ｅ（ｖｉ），Ｓｅｉ）の組に対してシャッフル復号部によりＥ（ｖｉ）を復号し、もとのＥ（ｖｉ）の入力順とは順番を入れ換えたｖｉのリストを得るとともに、すべてのＥ（ｖｉ）とｖｉとの間に１対１の対応関係があることの証明を作成する。集計端末はｖｉにより集計を行ない、すべての（Ｅ（ｖｉ），Ｓｅｉ）の組のリスト、復号して順番を入れ換えたｖｉのリスト、すべてのＥ（ｖｉ）とｖｉとのあいだに１対１の対応関係があることの証明を公表する。【００１５】
投票者は持ち帰った（Ｅ（ｖｉ），Ｓｅｉ）が公表されたリストに含まれているかどうか確認し、さらに、公表されたＥ（ｖｉ）とｖｉとの間に１対１の対応関係があることの証明を検証する。【００１６】
投票者が確認のために持ち帰る（Ｅ（ｖｉ），Ｓｅｉ）からは平文の投票内容ｖｉがわからず、また、集計端末は（Ｅ（ｖｉ），Ｓｅｉ）のリストを復号して得られるｖｉを、（Ｅ（ｖｉ），Ｓｅｉ）のリストとは異なる順番に入れ換えてから公表するため、第三者は投票者の持ち帰る（Ｅ（ｖｉ），Ｓｅｉ）から投票内容ｖｉを確認できず、票の売買は行なえない。【００１７】
また、集計端末が公表する（Ｅ（ｖｉ），Ｓｅｉ）のリストとｖｉのリストについて、すべてのＥ（ｖｉ）とｖｉとの間に１対１の対応があることの証明が公表されるため、この証明を検証することで、公表された（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれた票が、改竄などされずに確かにすべて集計されていることの確認ができる。【００１８】
また、暗号文Ｅ（ｖｉ）に対しては投票端末のデジタル署名Ｓｅｉが付与されるため、投票者個人はデジタル署名のための署名鍵を所有していなくとも投票を行なえる。【００１９】
これにより、本発明の目的を達成することができる。【００２０】
本発明の第２の電子投票システムは、さらに、署名生成部をもつ投票用ＩＣカードを備えることを特徴とする。また、投票端末には署名生成部を備えてなくともよい。投票者は未投票の有権者であることが確認されると、投票用ＩＣカードを１枚交付される。その後、投票者は投票端末にて暗号化部により投票内容ｖｉを暗号化してＥ（ｖｉ）を作成し、交付された投票用ＩＣカードにより、Ｅ（ｖｉ）に対する投票用ＩＣカードのデジタル署名Ｓｅｉを作成する。このようにすることで、投票端末の誤動作などで実際には投票されていない投票データｖｊについて、（Ｅ（ｖｉ），Ｓｅｊ）が投票端末に記録され、集計されるといった事態を防ぐことができる。
【発明の効果】
【００２１】
本発明の第１の効果は、票の売買の証拠となる情報を使わずに、票の水増しや改竄が行なわれていないことを確認できることにある。その理由は、投票者が自分の投票が集計されていることの確認のために持ち帰る情報には、投票内容そのものではなく暗号化された投票内容が含まれ、なおかつ、投票内容そのものと暗号化された投票内容との直接の対応関係を示す情報は公表されないためである。【００２２】
第２の効果は、投票内容そのものが確かに集計されていることを確認できることである。その理由は、集計端末の受付けたすべての暗号化された投票内容と、集計端末が実際に集計したすべての投票内容との間に１対１の対応関係があることの証明が公表されるためである。【００２３】
第３の効果は、票の水増しや改竄が行なわれていないことを、投票者だけでなく、誰でも確認できることにある。その理由は、投票終了後に公表される投票一覧に、集計端末には生成できない、誰でも検証可能な投票端末のデジタル署名が含まれることと、暗号化された投票内容と復号された投票内容との間に１対１の対応関係が存在することの証明を、誰でも検証できるためである。【００２４】
第４の効果は、投票者が個人用の署名鍵を所有していなくとも、投票を行なえることにある。その理由は、署名生成を投票端末か投票時に交付される投票用ＩＣカードにより行なうためである。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施の形態の構成を示すブロック図である。
【図２】本発明の第１の実施の形態の動作を示す流れ図である。
【図３】投票端末の一実施例を示すブロック図である。
【図４】集計端末の一実施例を示すブロック図である。
【図５】検証装置の一実施例を示すブロック図である。
【図６】本発明の第２の実施の形態における投票端末の構成を示すブロック図である。
【図７】本発明の第２の実施の形態における投票端末の動作を示す流れ図である。
【図８】投票端末の別の実施例を示すブロック図である。
【図９】本発明の第３の実施の形態における集計端末の構成を示すブロック図である。
【図１０】従来技術の構成を示すブロック図である。
【図１１】従来技術の構成を示すブロック図である。
【図１２】従来技術の構成を示すブロック図である。
【発明を実施するための最良の形態】
【００２６】
次に、本発明の実施の形態について図面を参照して詳細に説明する。【００２７】
図１を参照すると、本発明の第１の実施の形態としての電子投票システムが示されている。本電子投票システムは、投票端末１０と、集計端末２０と、検証装置３０とから構成される。ここで、投票端末は同じ構成のものを複数用意してもよい。【００２８】
投票端末１０は、キーボードやタッチパネルなどの入力装置１０１と、投票券入力装置１０２と、プリンタやフレキシブルディスクドライブなどの出力装置１０３と、投票データ記憶装置１０４と、暗号化部１０５と、署名生成部１０６と、紙やフレキシブルディスクなどの記録媒体１０７−１〜１０７−ｎとを備える。【００２９】
投票券入力装置１０２は、磁気カードなどの投票券（図示せず）が入力されたことを検出し、入力装置１０１に通知する。【００３０】
入力装置１０１は、投票券入力装置１０２から磁気カードなどの投票券（図示せず）が入力されたことの通知を受けると、投票内容の入力操作を受付ける。【００３１】
暗号化部１０５は、入力装置１０１によって入力された投票内容ｖｉを入力とし、暗号化された投票内容Ｅ（ｖｉ）を出力する。【００３２】
署名生成部１０６は、暗号化された投票内容Ｅ（ｖｉ）を入力とし、この暗号化された投票内容に対する投票端末１０のデジタル署名Ｓｅｉを出力する。【００３３】
出力装置１０３は、暗号化投票内容Ｅ（ｖｉ）と投票端末１０のデジタル署名Ｓｅｉの組を記録媒体１０７−ｉに出力する。【００３４】
投票データ記憶装置１０４は、暗号化投票内容Ｅ（ｖｉ）と投票端末１０のデジタル署名Ｓｅｉの組を複数記録蓄積する。【００３５】
集計端末２０は、投票データ読み取り装置２０１と、シャッフル復号装置２０２と、署名検証部２０３とを備える。【００３６】
投票データ読み取り装置２０１は、投票データ記憶装置１０４に記録されたすべての（Ｅ（ｖｉ），Ｓｅｉ）、つまり暗号化投票内容Ｅ（ｖｉ）と投票端末１０のデジタル署名Ｓｅｉの組すべてを読み取る。【００３７】
署名検証部２０３は、投票データ読み取り装置２０１が読み取った暗号化投票内容Ｅ（ｖｉ）と投票端末１０のデジタル署名Ｓｅｉの組すべてについて、投票端末１０のデジタル署名Ｓｅｉが正当なものかどうかの検証を行なう。【００３８】
シャッフル復号部２０２は、署名検証部２０３によるデジタル署名検証で合格となった全ての（Ｅ（ｖｉ），Ｓｅｉ）のリスト（Ｅ（ｖ１），Ｓｅ１），（Ｅ（ｖ２），Ｓｅ２），・・・，（Ｅ（ｖｔ），Ｓｅｔ）を入力とし、ｖｉに復号し、さらにｖｉのリストをその順番をランダムに並び換えて出力する。つまり、ｖ１，ｖ２，・・・，ｖｔという順番ではなく、ｖ８，ｖ３，・・・，ｖ６のようにランダムな順番に並び換えられたリストを出力する。また、入力となったすべてのＥ（ｖｉ）と出力されたすべてのｖｉとの間に１対１の対応関係があることの証明データｐを出力する。【００３９】
集計端末２０は、全ての（Ｅ（ｖｉ），Ｓｅｉ）のリスト、ｖｉのリストおよび証明データｐを、電子掲示板やｗｅｂページ上などで公表したり、印刷物に印刷して公表する。【００４０】
検証装置３０は、署名検証部３０１と、リスト照合部３０２と、シャッフル復号検証部３０３とを備える。【００４１】
検証装置３０は、投票者から記録媒体１０７−ｊの記録内容を入力し、集計端末２０からその出力した（Ｅ（ｖｉ），Ｓｅｉ）のリスト、ｖｉのリスト、証明データｐとを入力し、検証結果を投票者に提示する。【００４２】
署名検証部３０１は、記録媒体１０７−ｊに記録された（Ｅ（ｖｊ），Ｓｅｊ）を入力し、そのＳｅｊがＥ（ｖｊ）に対する投票端末１０の正当なデジタル署名かどうかを判定する。また、署名検証部３０１は、集計端末２０の出力した（Ｅ（ｖｉ），Ｓｅｉ）のリストを入力し、各ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを判定する。【００４３】
リスト照合部３０２は、記録媒体１０７−ｊに記録された（Ｅ（ｖｊ），Ｓｅｊ）と集計端末２０の出力した（Ｅ（ｖｉ），Ｓｅｉ）のリストとを入力とし、記録媒体１０７−ｊに記録された（Ｅ（ｖｊ），Ｓｅｊ）が、集計端末２０の出力した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれているかどうかを判定する。【００４４】
シャッフル復号検証部３０３は、集計端末２０の出力した（Ｅ（ｖｉ），Ｓｅｉ）のリスト、ｖｉのリスト、証明データｐとを入力とし、証明データｐが、入力された（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれるすべてのＥ（ｖｉ）と、入力されたｖｉのリストとの間に１対１の対応関係があることの正しい証明になっているかどうかの判定を行なう。【００４５】
検証装置３０は、署名検証部３０１によるデジタル署名の検証結果、リスト照合部３０２のリスト照合結果およびシャッフル復号検証部３０３の検証結果を総合的に考慮して、記録媒体１０７−ｊを入力した投票者に検証結果を出力する。【００４６】
投票端末１０の署名生成部１０６、集計端末２０の署名検証部２０３および検証装置３０の署名検証部３０１は、例えばＲＳＡ暗号などの公開鍵暗号を用いることができる。その場合、署名対象のデータＶに対するディジタル署名Ｓｊｖは、Ｖと署名用秘密鍵ｄｊを用いてＳｊｖ＝Ｖ＾ｄｊ ｍｏｄ ｎｊにより計算され、署名検証は、ＶとＳｊｖと、ｄｊに対応する検証用公開鍵ｅｊを用いてＳｖｊ＾ｅｊ = Ｖ（ｍｏｄ ｎｊ）が成り立てば合格となる。ここで、二つの素数ｐｊ，ｑｊに対して、ｎｊ＝ｐｊ×ｑｊ，ｄｊ×ｅｊ=１ ｍｏｄ （ｐｊ−１）（ｑｊ−１）と表わせる。なお、＾は羃乗を示す記号であり、例えばＶ＾ｄｊはＶをｄｊ回羃乗した結果を表わす。投票端末１０が複数存在する場合、署名検証部２０３、３０１は検証するデジタル署名に対応する検証用公開鍵ｅｊを使う必要があるが、検証するデジタル署名に対応する検証用公開鍵ｅｊを決定する方法としては、デジタル署名自体に検証用公開鍵ｅｊを特定するキーを挿入しておく方法、検証用公開鍵ｅｊ自体を挿入しておく方法が利用できる。【００４７】
投票端末１０の暗号化部１０５および集計端末２０のシャッフル復号部２０２には、例えば特開平０８−２６３５７５号公報（以下、参考文献１という。）に示された、シャッフル復号部へ入力されたデータリストと、シャッフル復号後に出力されるデータリストとの間に１対１の対応関係があることを、具体的な対応関係そのものの情報は一切漏らさずに証明できる技術を用いることができる。以下、参考文献１に示された技術を本発明に用いる場合の暗号化部１０５とシャッフル復号部２０２の詳細を説明する。【００４８】
参考文献１に示された技術を用いる場合、公開情報（ｐ，ｑ，ｇ）に対して、集計端末２０はｑ未満の乱数Ｘ１を選んで復号鍵とし、部分公開鍵Ｙ１＝ｇ＾Ｘ１  ｍｏｄ  ｑを計算する。部分公開鍵Ｙ１は公開し、復号鍵Ｘ１は秘密裏に保持する。ここで、ｐ、ｑはともに素数で、ある整数ｈによりｐ＝ｈ×ｑ＋１という関係で表わされる数である。【００４９】
投票データｖの暗号化Ｅ（ｖ）は（Ｇ，Ｖ）という組で表わされ、（Ｇ，Ｖ）＝（ｇ＾ｒ ｍｏｄ ｐ，ｖ×Ｙ＾ｒ ｍｏｄ ｐ）の計算によって得られる。ここで、ｒは投票データｖに対して無作為に選んだ乱数であり、ＹはＹ＝Ｙ１  ｍｏｄ  ｐにより計算される数である。【００５０】
集計端末２０が行なう、ｎ個の暗号データのリスト｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）のシャッフル復号は以下のようにする。【００５１】
まず、入力された｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）の各暗号データ（Ｇ＿ｉ，Ｖ＿ｉ）に対してランダム置換写像π（ｉ）を決定し、それに基づいて（Ｇ＿ｉ，Ｖ＿ｉ）の順番を変更し、リスト｛（Ｇ’＿ｊ，Ｖ’＿ｊ）｝を得る。ここで、（Ｇ’＿ｊ，Ｖ’＿ｊ）＝（Ｇ＿π（ｉ），Ｖ＿π（ｉ））が成り立っている。【００５２】
つぎに、すべての（Ｇ’＿ｊ，Ｖ’＿ｊ）それぞれについて、乱数ｓｊを生成し、Ｇ’’＿ｊ＝Ｇ’＿ｊ×ｇ＾ｓｊ ｍｏｄ ｐ、Ｖ’’＿ｊ＝Ｖ’＿ｊ×Ｙ＾ｓｊ ｍｏｄ ｐを計算し、新たなリスト｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝を求める。【００５３】
つぎに、各（Ｇ’’＿ｊ，Ｖ’’＿ｊ）について、Ｇ’’’＿ｊ＝Ｇ’’＿ｊとし、Ｖ’’’＿ｊ＝Ｖ’’＿ｊ／（Ｇ’’＿ｊ＾Ｘｋ） ｍｏｄ ｐを計算し、復号後のリスト｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝を求める。【００５４】
証明データの生成は以下のように行なう。【００５５】
（１）まず、｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）に対して、ランダム置換写像π（ｉ）と乱数列｛ｓｊ｝を用いてリスト｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝を計算したことを、ランダム置換写像π（ｉ）と乱数列｛ｓｊ｝を秘密にしたまま証明する。【００５６】
まず、ｔ個のランダム置換写像π’ｕ（ｕ＝１，２，・・・，ｔ）と、ｔ×ｎ個の乱数列｛ｓ’（ｕ，ｗ）｝（ｕ＝１，２，・・・，ｔ，ｗ＝１，２，・・・，ｎ）を生成する。ここで、ｔは公開された、あらかじめ決められた繰り返し回数である。そして、Ａ（ｕ，ｗ）＝Ｇ＿π’ｕ×ｇ＾ｓ’（ｕ，ｗ） ｍｏｄ ｐ、Ｂ（ｕ，ｗ）＝Ｖ＿π’ｕ×Ｙ＾ｓ’（ｕ，ｗ） ｍｏｄ ｐを、ｕ＝１，２，・・・，ｔ、ｗ＝１，２，・・・，ｎについて計算する。【００５７】
次に、ｃ＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙ｜｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）｜｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）｜｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝（ｕ＝１，２，・・・，ｔ，ｖ＝１，２，・・・，ｎ））を計算する。ここで、｜は連結を表わし、ＨａｓｈはＳＨＡ１などの安全なハッシュ関数とする。【００５８】
そして、ｃのｕ番目のｂｉｔをｃ［ｕ］とすると、ｃ［ｕ］＝０であればαｕ＝π’ｕ、β（ｕ，ｗ）＝ｓ’（ｕ，ｗ）とおき、ｃ［ｕ］＝１であればαｕ＝π＾−１○π’ｕ、β（ｕ，ｗ）＝ｓ’（ｕ，ｗ）−ｓ（π＾−１○π’ｕ）とおく。ここで、○は置換の合成を示す記号であり、置換πと置換π’の合成π○π’をπ’’と表わすと、π’’（ｉ）により、ｉはまずπ（ｉ）によりｊに置換され、さらにπ’（ｊ）によってｋへと置換される。【００５９】
証明データは｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）、｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝、αｕ、β（ｕ，ｗ）（ｕ＝１，２，・・・，ｔ，ｗ＝１，２，・・・，ｎ）となる。【００６０】
（２）つづいて、｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝に対して、部分公開鍵Ｙ１に対応する復号鍵Ｘ１により正しく復号して｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝を計算したことを、復号鍵Ｘ１を秘密にしたまま証明する。【００６１】
まず、ｑ未満の乱数ｒ’を生成する。【００６２】
つぎに、ｃ’＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙ１｜｛Ｇ’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜｛Ｖ’’＿ｊ／Ｖ’’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜ｇ＾ｒ’｜｛Ｇ’’＿ｊ＾ｒ’｝（ｊ＝１，２，・・・，ｎ））を計算する。【００６３】
そして、α’＝ｒ’−ｃ’×Ｘｊ ｍｏｄ ｐを計算する。【００６４】
証明データはｃ’、α’となる。【００６５】
この場合、検証装置３０のシャッフル復号検証部３０３におけるシャッフル復号処理の正当性の検証は以下のようにして行なう。【００６６】
まず、シャッフル復号処理の入力｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）と、証明データ｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）、｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝と、公開情報（ｐ，ｑ，ｇ）と部分公開鍵Ｙ１とから、ｃ＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙ１｜｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）｜｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）｜｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝（ｕ＝１，２，・・・，ｔ，ｗ＝１，２，・・・，ｎ））を計算する。【００６７】
ｃのｕ番目のｂｉｔをｃ［ｕ］とすると、ｃ［ｕ］＝０のとき、Ａ（ｕ，ｗ）＝Ｇ＿αｕ（ｗ）×ｇ＾β（ｕ，ｗ） ｍｏｄ ｐ、Ｂ（ｕ，ｗ）＝Ｖ＿αｕ（ｗ）×Ｙ１＾β（ｕ，ｗ） ｍｏｄ ｐが成り立つことを確認し、ｃ［ｕ］＝１のとき、Ａ（ｕ，ｗ）＝Ｇ’’＿αｕ（ｗ）×ｇ＾β（ｕ，ｗ） ｍｏｄ ｐ、Ｂ（ｕ，ｗ）＝Ｍ’’＿αｕ（ｗ）×Ｙ１＾β（ｕ，ｗ） ｍｏｄ ｐが成り立つことを確認する。【００６８】
次に、シャッフル復号処理の出力｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝と証明データの｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝について、すべてのｊについてＧ’’’＿ｊ＝Ｇ’’＿ｊであることを確認する。【００６９】
そして、ｃ’＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙ１｜｛Ｇ’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜｛Ｖ’’＿ｊ／Ｖ’’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜ｇ＾α’×Ｙ１＾ｃ’｜｛Ｇ’’＿ｊ＾α’×（Ｖ’’＿ｊ／Ｖ’’’＿ｊ）＾ｃ’｝（ｊ＝１，２，・・・，ｎ））が成り立つことを確認する。【００７０】
さらに、すべてのｊについて、Ｖ’’＿ｊ＾ｑ＝１ ｍｏｄ ｐが成り立つことを確認する。【００７１】
以上の確認がすべて合格であれば、証明は正しいとみなす。【００７２】
以上は参考文献１に示される技術を用いて投票端末１０の暗号化部１０５、集計端末２０のシャッフル復号部２０２および検証装置３０のシャッフル復号検証部３０３を実現した例を示した。しかし、シャッフル復号部へ入力されたデータリストと、シャッフル復号後に出力されるデータリストとの間に１対１の対応関係があることを、具体的な対応関係そのものの情報は一切漏らさずに証明できる技術は、特開２００２−２３７８１０号公報（以下、参考文献２という。）、特開２００１−２５１２８９号公報（以下、参考文献３という。）、特開２００２−３４４４４５号公報（以下、参考文献４という。）などにも示されており、これら参考文献２、３、４に記載された技術を用いて投票端末１０の暗号化部１０５、集計端末２０のシャッフル復号部２０２および検証装置３０のシャッフル復号検証部３０３を実現することも可能である。【００７３】
次に、図１および図２を参照して本実施の形態の動作について詳細に説明する。【００７４】
（１）投票段階  まず、投票者は有権者であることと未投票であることの確認をうける（図２のステップＡ１）。有権者確認の方法としては、あらかじめ自治体などから交付された選挙はがきや身分証明書などを提示して有権者名簿と照合する方法や、投票者個人が所有するＩＣカードの情報と有権者情報データベースなどを用いた電子的な照合を行なう方法が考えられる。未投票の有権者であることが確認されると、磁気カードなどの投票券を交付される（図２のステップＡ２）。【００７５】
次に、投票者は交付された投票券を投票端末１０の投票券入力装置１０２に挿入する（ステップＡ３）。投票券入力装置１０２は投票券が入力されたことを検出すると、その旨を入力装置１０１に通知し、入力装置１０１はこの通知があると投票者からの投票内容の受付を可能とし、投票内容ｖｉの入力を受付ける（ステップＡ４）。【００７６】
次に、暗号化部１０５は入力装置１０１から投票内容ｖｉを読み込み、暗号化投票内容Ｅ（ｖｉ）を出力する（ステップＡ５）。【００７７】
次に、署名生成部１０６は暗号化部１０５の出力したＥ（ｖｉ）を読み込み、投票端末１０のデジタル署名Ｓｅｉを出力する（ステップＡ６）。【００７８】
次に、暗号化投票内容Ｅ（ｖｉ）とデジタル署名Ｓｅｉの組を投票データ記憶装置１０４に記録する（ステップＡ７）。【００７９】
また、暗号化投票内容Ｅ（ｖｉ）とデジタル署名Ｓｅｉの組を出力装置１０３により記録媒体１０７−ｉに記録する（ステップＡ８）。【００８０】
投票者は記録媒体１０７−ｉを持ち帰る。【００８１】
以上のステップＡ１〜Ａ８の処理が各投票者毎に繰り返されることにより、投票端末１０において投票された全ての投票データが投票データ記憶装置１０４に蓄積される。【００８２】
（２）集計段階
投票期間が終わると、集計端末２０は投票データ読み取り装置２０１により、投票データ記憶装置１０４に記録されたすべての（Ｅ（ｖｉ），Ｓｅｉ）の組を読み取る（ステップＡ９）。これは、投票データ記憶装置１０４を可搬型記憶装置で構成し、投票期間終了後に端末装置１０から投票データ記憶装置１０４を取り出し、集計端末２０まで搬送して装填し、投票データ読み取り装置２０１で読み取るようにしても良いし、投票端末１０と集計端末２０を通信回線で接続し、投票データ読み取り装置２０１が通信回線を介して投票端末１０の投票データ記憶装置１０４の内容を読み取るようにしても良い。【００８３】
次に、読み取ったすべての（Ｅ（ｖｉ），Ｓｅｉ）の組のリストを署名検証部２０３に入力し、それぞれの（Ｅ（ｖｉ），Ｓｅｉ）について、ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを検証する（ステップＡ１０）。【００８４】
次に、デジタル署名の検証に合格したすべてのＥ（ｖｉ）＝（Ｇ＿ｉ’，Ｖ＿ｉ’）のリストをシャッフル復号部２０２に入力し、復号結果リスト｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝（ｊ＝１．．．ｎ）と証明データｐを得る。（ステップＡ１１）。【００８５】
集計端末２０は、投票端末１０のデジタル署名の検証に合格したすべての（Ｅ（ｖｉ），Ｓｅｉ）の組のリスト、（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）のリスト、証明データｐを公開する（ステップＡ１２）。【００８６】
（３）検証段階
自分自身の投票が確かに集計されており投票に不正がないことを確認したい投票者は、持ち帰った記録媒体１０７−ｉを検証装置３０に入力して、検証する。検証装置３０には、他に、集計端末２０が公表したすべての（Ｅ（ｖｉ），Ｓｅｉ）の組と，復号結果リスト、証明データｐとが入力される。【００８７】
検証装置３０は、まず、署名検証部３０１により、記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）について、ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを検証する（ステップＡ１３）。この検証に合格しない場合、検証装置３０は、記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）のＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名でないという理由を添えて不合格を出力する（ステップＡ１８）。【００８８】
次に、署名検証部３０１により、集計端末２０の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれるすべての（Ｅ（ｖｉ），Ｓｅｉ）について、ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを検証する（ステップＡ１４）。この検証に合格しない場合、検証装置３０は、集計端末２０の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリスト中に投票端末１０の正当なデジタル署名でないものが含まれているという理由を添えて不合格を出力する（ステップＡ１８）。集計端末２０は投票端末１０の正当なデジタル署名を生成できないため、集計端末２０が実際には投票されていない（Ｅ（ｖｉ’），Ｓｅｉ’）を加えたり、投票内容の改竄を行なった場合には検証に合格しない。これにより、集計端末２０が受付けた投票内容を改竄したり、受付けていない不正な投票内容を水増ししていないかどうかを確認できる。【００８９】
つぎに、リスト照合部３０２により、記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）が、集計端末２０の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれているかどうかを確認する（ステップＡ１５）。記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）が集計端末２０の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれていなかった場合、その旨と共に不合格を出力する（ステップＡ１８）。これにより、投票者は自分の投票内容が受付けられていない不正が行われていたことを確認できる。【００９０】
次に、シャッフル復号検証部３０３により、集計端末３０の公表した証明データｐが、集計端末２０の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれるすべてのＥ（ｖｉ）＝（Ｇ’＿ｉ，Ｖ’＿ｉ）と、集計端末３０の出力した復号リストに含まれるすべての（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）との間に１対１の対応関係があることの正しい証明になっているかどうか検証する（ステップＡ１６）。この検証に合格しない場合、検証装置３０は、集計端末２０の公表した証明データｐが不正である旨を添えて不合格を出力する（ステップＡ１８）。他方、この検証に合格し、ステップＡ１３、Ａ１４の検証にも合格しており、且つ、ステップＡ１５において記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）が集計端末２０の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれていることが確認されていた場合、合格を出力する（ステップＡ１７）。これにより、投票者は、受付けられたすべての投票について、投票内容が正しく集計されているかどうかの確認が行なえる。【００９１】
図３は投票端末１０の実施例のブロック図であり、図１中の符号と同一符号は同一部分を示し、１１は中央処理装置などで構成された制御装置、１２は主記憶などで構成された記憶装置、１３は投票券、１４は磁気ディスクなどのコンピュータ可読記録媒体、１１１は入力部、１１２は暗号化部、１１３は署名生成部、１１４は出力部、１２１は投票内容記憶部、１２２は暗号化投票内容記憶部である。【００９２】
記録媒体１４には投票プログラムが記録されている。ここに記録された投票プログラムは、制御装置１１に読み取られ、制御装置１１の動作を制御することにより、制御装置１１上に入力部１１１、暗号化部１１２、署名生成部１１３、出力部１１４を実現する。【００９３】
入力部１１１は、磁気カードなどの投票券１３を交付された投票者がそれを投票券入力装置１０２に挿入することにより投票の受け付けが可能となる入力装置１０１から、投票者の投票内容を入力し、投票内容記憶部１２１に記憶する機能手段である。暗号化部１１２は図１の暗号化部１０５に相当する機能手段であり、投票内容記憶部１２１から投票内容を入力して暗号化し、暗号化された投票内容を記憶部１２２に記憶する。署名生成部１１３は、図１の署名生成部１０６に相当する機能手段であり、暗号化投票内容記憶部１２２から暗号化された投票内容を入力し、それに対して当該投票端末のデジタル署名を生成し、暗号化された投票内容とデジタル署名の組を投票データ記憶装置１０４に記憶する。出力部１１４は、投票データ記憶装置１０４から暗号化された投票内容とデジタル署名の組を入力し、出力装置１０３によって記録媒体１０７−ｉに出力する機能手段である。【００９４】
図４は集計端末２０の実施例のブロック図であり、図１中の符号と同一符号は同一部分を示し、２１は中央処理装置などで構成された制御装置、２２は主記憶などで構成された記憶装置、２３は公表装置、２４は磁気ディスクなどのコンピュータ可読記録媒体、２１１は入力部、２１２は署名検証部、２１３はシャッフル復号部、２１４は公表部、２２１は投票データ記憶部、２２２はデータリスト記憶部、２２３は復号投票記憶部、２２４は証明データ記憶部である。【００９５】
記録媒体２４には集計プログラムが記録されている。ここに記録された集計プログラムは、制御装置２１に読み取られ、制御装置２１の動作を制御することにより、制御装置２１上に入力部２１１、署名検証部２１２、シャッフル復号部２１３、公表部２１４を実現する。【００９６】
入力部２１１は、図１の投票データ読み取り装置２０１に相当する機能手段であり、全ての投票端末１０の投票データ記憶装置１０４に記憶された投票データを全て入力し、投票データ記憶部２２１に記憶する。署名検証部２１２は、図１の署名検証部２０３に相当する機能手段であり、投票データ記憶部２２１から投票データを入力し、それに含まれる投票端末のデジタル署名が正当かどうかを検証し、正当なデジタル署名が付された投票データだけをデータリスト記憶部２２２に記憶する。シャッフル復号部２１３は、図１のシャッフル復号部２０２に相当する機能手段であり、データリスト記憶部２２２から投票データを入力し、投票内容の復号とその並べ替えを行った結果を復号投票記憶部２２３に記憶し、また、入力した投票データのリストと復号した投票データのリストとの間に１対１の対応関係があることの証明データを作成して証明データ記憶部２２４に記憶する。公表部２１４は、データリスト記憶部２２２、復号投票記憶部２２３および証明データ記憶部２２４から投票データのリスト、復号した投票データのリスト、証明データを入力し、これらの内容を公表装置２３によって不特定多数の者に公表する機能手段である。公表装置２３は、例えば電子掲示板、選挙管理委員会のホームページなどである。【００９７】
図５は検証装置３０の実施例のブロック図であり、図１および図４中の符号と同一符号は同一部分を示し、３１は中央処理装置などで構成された制御装置、３２は主記憶などで構成された記憶装置、３３は主記憶などで構成された検証結果記憶装置、３４は投票者が持参する記録媒体１０７−ｉに記録された暗号化された投票内容と投票端末のデジタル署名との組を読み取る入力装置、３５は投票者に検証結果を出力する出力装置、３６は磁気ディスクなどのコンピュータ可読記録媒体、３１１は入力部、３１２は署名検証部、３１３はリスト照合部、３１４はシャッフル復号検証部、３１５は出力部、３１６は取得部、３２１は投票データ記憶部、３２２はデータリスト記憶部、３２３は復号投票記憶部、３２４は証明データ記憶部である。【００９８】
記録媒体３６には検証プログラムが記録されている。ここに記録された検証プログラムは、制御装置３１に読み取られ、制御装置３１の動作を制御することにより、制御装置３１上に入力部３１１、署名検証部３１２、リスト照合部３１３、シャッフル復号検証部３１４、出力部３１５、取得部３１６を実現する。【００９９】
取得部３１６は、集計端末２０が選挙管理委員会のホームページなどに公表装置２３で公開している投票データのリスト、復号した投票データのリスト、証明データを取得するｗｅｂブラウザなどの機能手段であり、取得した情報はデータリスト記憶部３２２、復号投票記憶部３２３、証明データ記憶部３２４にそれぞれ記憶される。入力部３１１は、投票者の記録媒体１０７−ｉに記録された暗号化された投票内容と投票端末のデジタル署名との組を入力装置３４によって読み取り、投票データ記憶部３２１に記憶する機能手段である。【０１００】
署名検証部３１２は、図１の署名検証部３０１に相当する機能手段であり、投票データ記憶部３２１から記録媒体１０７−ｉに記録された暗号化された投票内容と投票端末のデジタル署名との組を入力し、そのデジタル署名が投票端末のものであるかを検証し、その検証結果を検証結果記憶装置３３に記憶する機能と、データリスト記憶部３２２から集計端末２０が公表した投票データのリストを入力し、それに含まれる暗号化投票内容と投票端末のデジタル署名の組ごとに、そのデジタル署名が投票端末のものであるかを検証し、その検証結果を検証結果記憶装置３３に記憶する機能とを有する。【０１０１】
リスト照合部３１３は、図１のリスト照合部３０２に相当する機能手段であり、投票データ記憶部３２１から記録媒体１０７−ｉに記録された暗号化された投票内容と投票端末のデジタル署名との組を入力し、その組と同じ内容のものがデータリスト記憶部３２２に記憶されているかどうかを調べ、その結果を検証結果記憶装置３３に出力する。【０１０２】
シャッフル復号検証部３１４は、記憶部３２２〜３２４から集計端末２０が公表した投票データのリスト、復号した投票データのリスト、証明データを入力し、その証明データが、その投票データのリストに含まれるすべての暗号化投票内容と、その復号した投票データのリストに含まれるすべての投票内容との間に１対１の対応関係があることの正しい証明になっているかどうか検証し、その検証結果を検証結果記憶装置３３に記憶する。【０１０３】
出力部３１５は、検証結果記憶装置３３から署名検証部３１２、リスト照合部３１３およびシャッフル復号検証部３１４の検証結果を入力し、全ての検証結果が合格なら、その旨を出力装置３５を通じて利用者に出力し、何れか１つでも不合格なら不合格である旨とその理由を出力装置３５を通じて利用者に出力する。【０１０４】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。【０１０５】
図６を参照すると、本発明の第２の実施の形態としての電子投票システムにおける投票端末１０’が示されている。本発明の第２の実施の形態における投票端末１０’は、図１に示された第１の実施の形態における投票端末１０と比較して、ＩＣカード入出力装置１０８を備え、署名生成部１０６は備えていない点で相違する。また、本実施の形態では、投票者個人とは関連づけされない、投票用ＩＣカード固有のデジタル署名を生成して出力する投票用ＩＣカード４０−ｉ（ｉ＝１〜ｎ）を投票者に使用させる。この投票用ＩＣカード４０−ｉは投票用ＩＣカードごとにそれぞれ相異なる署名用秘密鍵４０１−ｉと、署名生成部４０２を備える。【０１０６】
次に、図６および図７を参照して本発明の第２の実施の形態の動作について詳細に説明する。【０１０７】
本実施の形態では、投票者は未投票の有権者であることが第１の実施の形態と同様にして確認されると、投票券として投票用ＩＣカード４０−ｉを交付される（図７のステップＢ１）。【０１０８】
次に、投票者は投票用ＩＣカード４０−ｉを投票端末１０’のＩＣカード入出力装置１０８に挿入する（ステップＢ２）。ＩＣカード入出力装置１０８は、投票用ＩＣカードが入力されたことを検出し、入力装置１０１に通知する。【０１０９】
入力装置１０１は、ＩＣカード入出力装置１０８から投票用ＩＣカードが入力されたことの通知を受けると、投票の受け付けを可能とし、投票者から投票内容ｖｉの入力を受付ける（ステップＡ４）。そして、入力されたｖｉを暗号化部１０５に送り、暗号化部１０５はそれを暗号化したＥ（ｖｉ）を計算する（ステップＡ５）。【０１１０】
次に、暗号化部１０５は、Ｅ（ｖｉ）をＩＣカード入出力装置１０８に出力し、ＩＣカード入出力装置１０８はこのＥ（ｖｉ）を挿入されている投票用ＩＣカード４０−ｉに入力する。投票用ＩＣカード４０−ｉは、Ｅ（ｖｉ）が入力されると、署名用秘密鍵４０１−ｉと署名生成部４０２により、Ｅ（ｖｉ）に対する投票用ＩＣカード４０−ｉのデジタル署名Ｓｅｉを生成して出力する（ステップＢ３）。ＩＣカード入出力装置１０８は、Ｅ（ｖｉ）とデジタル署名Ｓｅｉの組を投票データ記憶装置１０４に記録し（ステップＡ７）、かつ出力装置１０３により記録媒体１０７−ｉに出力する（ステップＡ８）。【０１１１】
投票者は、交付された投票用ＩＣカード４０−ｉを返却し、記録媒体１０７−ｉを持ち帰る。投票者から返却された投票用ＩＣカード４０−ｉは、他の投票者の投票時に再利用される。【０１１２】
以降の集計端末２０および検証装置３０の処理は第１の実施の形態と同様である。但し、集計端末２０の署名検証部２０３および検証装置３０の署名検証部３０１が検証するデジタル署名は、投票用ＩＣカード４０−ｉの署名生成部４０２が生成したデジタル署名である。投票用ＩＣカード４０−ｉの署名生成部４０２、集計端末２０の署名検証部２０３および検証装置３０の署名検証部３０１は、第１の実施の形態と同様に、例えばＲＳＡ暗号などの公開鍵暗号を用いることができ、検証するデジタル署名に対応する検証用公開鍵を決定する方法としては、デジタル署名自体に検証用公開鍵を特定するキーを挿入しておく方法、検証用公開鍵自体を挿入しておく方法などが利用できる。【０１１３】
このように本実施の形態では、デジタル署名の生成を投票用ＩＣカードで行なうため、投票端末の誤動作などにより、実際には投票されていないｖｊに対する（Ｅ（ｖｊ），Ｓｅｊ）が投票データとして記録されることがない。【０１１４】
図８は投票端末１０’の実施例のブロック図であり、図３中の符号と同一符号は同一部分を示し、１５は磁気ディスクなどのコンピュータ可読記録媒体、１１５は署名要請部である。記録媒体１５には投票プログラムが記録されている。ここに記録された投票プログラムは、制御装置１１に読み取られ、制御装置１１の動作を制御することにより、制御装置１１上に入力部１１１、暗号化部１１２、出力部１１４、署名要請部１１５を実現する。【０１１５】
署名要請部１１５は、暗号化投票内容記憶部１２２から暗号化された投票内容を入力し、この投票内容をＩＣカード入出力装置１０８を通じて投票用ＩＣカード４０−ｉに送信して署名を要請し、暗号化投票内容とＩＣカード４０−ｉのデジタル署名との組をＩＣカード入出力装置１０８から受信し、投票データ記憶装置１０４に記憶する機能手段である。【０１１６】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。【０１１７】
図９を参照すると、本発明の第３の実施の形態にかかる電子投票システムは、本発明の第１または第２の実施の形態にかかる電子投票システムにおける集計端末２０に代えて、集計端末群２０’を備えている点で相違する。【０１１８】
集計端末群２０’は、処理順序が１番の集計端末２０−１から、処理順序がｍ番の最後の集計端末２０−ｍまでの処理順序付けされた複数の集計端末２０−１〜２０−ｍで構成されている。【０１１９】
集計端末２０−１は、第１および第２の実施の形態における集計端末２０と基本的に同じ構成であるが、シャッフル復号によって得られる結果は平文の投票内容ではなく部分復号処理されたものとなる。集計端末２０−１は、集計端末２０と同様な（Ｅ（ｖｉ），Ｓｅｉ）の組のリストＬ１１と、このリストＬ１１に対して部分復号処理を行い且つ順番を入れ換えたデータリストＬ１２と、リストＬ１１とＬ１２とのあいだに１対１の対応関係があることの証明データｐ１とを公表し、次の処理順番の集計端末２０−２に部分復号処理の済んだデータリストＬ１２を送信する。【０１２０】
次の処理順番である集計端末２０−２は、集計端末２０−１から部分復号処理の済んだデータリストＬ１２を入力し、これに対してさらに部分復号処理を行ない且つ順番を入れ換える。そして、入力のデータリストＬ１２であるＬ２１と、このリストＬ２１に対して部分復号処理を行い且つ順番を入れ換えたデータリストＬ２２と、リストＬ２１とＬ２２とのあいだに１対１の対応関係があることの証明データｐ２とを公表し、次の処理順番の集計端末２０−３（図示せず）に部分復号処理の済んだデータリストＬ２２を送信する。但し、入力にデジタル署名が含まれていないので、集計端末２０−１におけるようなデジタル署名の検証処理は行なわれない。処理順番が途中の他の集計端末も、集計端末２０−２と同様の構成である。【０１２１】
処理順番が最後の集計端末２０−ｍは、前段の集計端末から部分復号処理の済んだデータリストを入力し、これに対してさらに部分復号処理を行ない且つ順番を入れ換えることにより、平文の投票内容のリストＬｍ２を生成し、入力のデータリストと、前記リストＬｍ２と、それらのリストのあいだに１対１の対応関係があることの証明データｐｍとを公表する。【０１２２】
本発明の第３の実施の形態にかかる電子投票システムにおける投票端末１０、１０’の暗号化部１０５および集計端末２０−１〜２０−ｍのシャッフル復号部２０２に、参考文献１に示された技術を用いる場合の暗号化部１０５とシャッフル復号部２０２の詳細を説明する。【０１２３】
参考文献１に示された技術を用いる場合、公開情報（ｐ，ｑ，ｇ）に対して、各集計端末２０−ｋはそれぞれｑ未満の乱数Ｘｋを選んで復号鍵とし、部分公開鍵Ｙｋ＝ｇ＾Ｘｋ  ｍｏｄ  ｑを計算する。部分公開鍵Ｙｋは公開し、復号鍵Ｘｋは秘密裏に保持する。ここで、ｐ、ｑはともに素数で、ある整数ｈによりｐ＝ｈ×ｑ＋１という関係で表わされる数である。【０１２４】
投票データｖの暗号化Ｅ（ｖ）は（Ｇ，Ｖ）という組で表わされ、（Ｇ，Ｖ）＝（ｇ＾ｒ ｍｏｄ ｐ，ｖ×Ｙ＾ｒ ｍｏｄ ｐ）の計算によって得られる。ここで、ｒは投票データｖに対して無作為に選んだ乱数であり、ＹはＹ＝Ｙ１×Ｙ２×・・・×Ｙｍ  ｍｏｄ  ｐにより計算される数である。【０１２５】
集計端末２０−ｋが行なう、ｎ個の暗号データのリスト｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）のシャッフル復号は以下のようにする。【０１２６】
まず、入力された｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）の各暗号データ（Ｇ＿ｉ，Ｖ＿ｉ）に対してランダム置換写像π（ｉ）を決定し、それに基づいて（Ｇ＿ｉ，Ｖ＿ｉ）の順番を変更し、リスト｛（Ｇ’＿ｊ，Ｖ’＿ｊ）｝を得る。ここで、（Ｇ’＿ｊ，Ｖ’＿ｊ）＝（Ｇ＿π（ｉ），Ｖ＿π（ｉ））が成り立っている。【０１２７】
つぎに、すべての（Ｇ’＿ｊ，Ｖ’＿ｊ）それぞれについて、乱数ｓｊを生成し、Ｇ’’＿ｊ＝Ｇ’＿ｊ×ｇ＾ｓｊ ｍｏｄ ｐ、Ｖ’’＿ｊ＝Ｖ’＿ｊ×Ｙ＾ｓｊｍｏｄ ｐを計算し、新たなリスト｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝を求める。【０１２８】
つぎに、各（Ｇ’’＿ｊ，Ｖ’’＿ｊ）について、Ｇ’’’＿ｊ＝Ｇ’’＿ｊとし、Ｖ’’’＿ｊ＝Ｖ’’＿ｊ／（Ｇ’’＿ｊ＾Ｘｋ） ｍｏｄ ｐを計算し、復号後のリスト｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝を求める。【０１２９】
証明データの生成は以下のように行なう。【０１３０】
（１）まず、｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）に対して、ランダム置換写像π（ｉ）と乱数列｛ｓｊ｝を用いてリスト｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝を計算したことを、ランダム置換写像π（ｉ）と乱数列｛ｓｊ｝を秘密にしたまま証明する。【０１３１】
まず、ｔ個のランダム置換写像π’ｕ（ｕ＝１，２，・・・，ｔ）と、ｔ×ｎ個の乱数列｛ｓ’（ｕ，ｗ）｝（ｕ＝１，２，・・・，ｔ，ｗ＝１，２，・・・，ｎ）を生成する。ここで、ｔは公開された、あらかじめ決められた繰り返し回数である。そして、Ａ（ｕ，ｗ）＝Ｇ＿π’ｕ×ｇ＾ｓ’（ｕ，ｗ） ｍｏｄ ｐ、Ｂ（ｕ，ｗ）＝Ｖ＿π’ｕ×Ｙ＾ｓ’（ｕ，ｗ） ｍｏｄ ｐを、ｕ＝１，２，・・・，ｔ、ｗ＝１，２，・・・，ｎについて計算する。【０１３２】
次に、ｃ＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙ｜｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）｜｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）｜｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝（ｕ＝１，２，・・・，ｔ，ｖ＝１，２，・・・，ｎ））を計算する。ここで、｜は連結を表わし、ＨａｓｈはＳＨＡ１などの安全なハッシュ関数とする。【０１３３】
そして、ｃのｕ番目のｂｉｔをｃ［ｕ］とすると、ｃ［ｕ］＝０であればαｕ＝π’ｕ、β（ｕ，ｗ）＝ｓ’（ｕ，ｗ）とおき、ｃ［ｕ］＝１であればαｕ＝π＾−１○π’ｕ、β（ｕ，ｗ）＝ｓ’（ｕ，ｗ）−ｓ（π＾−１○π’ｕ）とおく。ここで、○は置換の合成を示す記号であり、置換πと置換π’の合成π○π’をπ’’と表わすと、π’’（ｉ）により、ｉはまずπ（ｉ）によりｊに置換され、さらにπ’（ｊ）によってｋへと置換される。【０１３４】
証明データは｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）、｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝、αｕ、β（ｕ，ｗ）（ｕ＝１，２，・・・，ｔ，ｗ＝１，２，・・・，ｎ）となる。【０１３５】
（２）つづいて、｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝に対して、部分公開鍵Ｙｋに対応する復号鍵Ｘｋにより正しく復号して｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝を計算したことを、復号鍵Ｘｋを秘密にしたまま証明する。【０１３６】
まず、ｑ未満の乱数ｒ’を生成する。【０１３７】
つぎに、ｃ’＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙｋ｜｛Ｇ’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜｛Ｖ’’＿ｊ／Ｖ’’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜ｇ＾ｒ’｜｛Ｇ’’＿ｊ＾ｒ’｝（ｊ＝１，２，・・・，ｎ））を計算する。【０１３８】
そして、α’＝ｒ’−ｃ’×Ｘｊ ｍｏｄ ｐを計算する。【０１３９】
証明データはｃ’、α’となる。【０１４０】
この場合、検証装置３０のシャッフル復号検証部３０３におけるシャッフル復号処理の正当性の検証は以下のようにして行なう。【０１４１】
まず、シャッフル復号処理の入力｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）と、証明データ｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）、｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝と、公開情報（ｐ，ｑ，ｇ）と部分公開鍵Ｙｋとから、ｃ＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙｋ｜｛（Ｇ＿ｉ，Ｖ＿ｉ）｝（ｉ＝１，２，・・・，ｎ）｜｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝（ｊ＝１，２，・・・，ｎ）｜｛（Ａ（ｕ，ｗ），Ｂ（ｕ，ｗ）｝（ｕ＝１，２，・・・，ｔ，ｗ＝１，２，・・・，ｎ））を計算する。【０１４２】
ｃのｕ番目のｂｉｔをｃ［ｕ］とすると、ｃ［ｕ］＝０のとき、Ａ（ｕ，ｗ）＝Ｇ＿αｕ（ｗ）×ｇ＾β（ｕ，ｗ） ｍｏｄ ｐ、Ｂ（ｕ，ｗ）＝Ｖ＿αｕ（ｗ）×Ｙｋ＾β（ｕ，ｗ） ｍｏｄ ｐが成り立つことを確認し、ｃ［ｕ］＝１のとき、Ａ（ｕ，ｗ）＝Ｇ’’＿αｕ（ｗ）×ｇ＾β（ｕ，ｗ） ｍｏｄ ｐ、Ｂ（ｕ，ｗ）＝Ｍ’’＿αｕ（ｗ）×Ｙｋ＾β（ｕ，ｗ） ｍｏｄ ｐが成り立つことを確認する。【０１４３】
次に、シャッフル復号処理の出力｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝と証明データの｛（Ｇ’’＿ｊ，Ｖ’’＿ｊ）｝について、すべてのｊについてＧ’’’＿ｊ＝Ｇ’’＿ｊであることを確認する。【０１４４】
そして、ｃ’＝Ｈａｓｈ（ｐ｜ｑ｜ｇ｜Ｙｋ｜｛Ｇ’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜｛Ｖ’’＿ｊ／Ｖ’’’＿ｊ｝（ｊ＝１，２，・・・，ｎ）｜ｇ＾α’×Ｙｋ＾ｃ’｜｛Ｇ’’＿ｊ＾α’×（Ｖ’’＿ｊ／Ｖ’’’＿ｊ）＾ｃ’｝（ｊ＝１，２，・・・，ｎ））が成り立つことを確認する。【０１４５】
さらに、すべてのｊについて、Ｖ’’＿ｊ＾ｑ＝１ ｍｏｄ ｐが成り立つことを確認する。【０１４６】
以上の確認がすべて合格であれば、証明は正しいとみなす。【０１４７】
以上は参考文献１に示される技術を用いて投票端末１０の暗号化部１０５、集計端末２０−１〜２０−ｍのシャッフル復号部２０２および検証装置３０のシャッフル復号検証部３０３を実現した例を示した。しかし、シャッフル復号部へ入力されたデータリストと、シャッフル復号後に出力されるデータリストとの間に１対１の対応関係があることを、具体的な対応関係そのものの情報は一切漏らさずに証明できる技術は、参考文献２、参考文献２、３、４に記載された技術を用いて投票端末１０の暗号化部１０５、集計端末２０−１〜２０−ｍのシャッフル復号部２０２および検証装置３０のシャッフル復号検証部３０３を実現することも可能である。【０１４８】
次に、本実施の形態の動作を説明する。本実施の形態において、（１）投票段階における動作は第１または第２の実施の形態と同じであるので、以下では、（２）集計段階と（３）検証段階の動作について説明する。【０１４９】
（２）集計段階
投票期間が終わると、集計端末２０−１は投票データ読み取り装置２０１により、投票データ記憶装置１０４に記録されたすべての（Ｅ（ｖｉ），Ｓｅｉ）の組を読み取り、読み取ったすべての（Ｅ（ｖｉ），Ｓｅｉ）の組のリストを署名検証部２０３に入力し、それぞれの（Ｅ（ｖｉ），Ｓｅｉ）について、ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを検証する。次に、デジタル署名の検証に合格したすべてのＥ（ｖｉ）＝（Ｇ＿ｉ’，Ｖ＿ｉ’）のリストをシャッフル復号部２０２に入力し、部分復号結果リスト｛（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）｝（ｊ＝１．．．ｎ）と証明データを得る。そして、集計端末２０−１は、すべての（Ｅ（ｖｉ），Ｓｅｉ）の組のリスト、（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）のリスト、証明データを公開し、集計端末２０−２に、（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）のリストを送付する。【０１５０】
集計端末２０−２は、投票データ読み取り装置２０１により、集計端末２０−１から送付された（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）のリストを受け取り、シャッフル復号部２０２に入力し、新たな部分復号リスト（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）と証明データを生成し、入力のリスト、新たな部分復号リスト、証明データを公開し、集計端末２０−３（図示せず）に新たな部分復号リストを送付する。以降、中間の集計端末で同様の処理が行なわれる。【０１５１】
最後の集計端末２０−ｍは、集計端末２０−（ｍ−１）（図示せず）から送付された（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）のリストを受け取り、シャッフル復号部２０２に入力し、平文の投票内容のリストと証明データを生成し、入力のデータリスト、平文の投票内容のリスト、証明データを公開する。【０１５２】
（３）検証段階
投票者は持ち帰った記録媒体１０７−ｉと、集計端末２０−１が公表したすべての（Ｅ（ｖｉ），Ｓｅｉ）の組と，復号結果リスト、証明ｐとを検証装置３０に入力する。【０１５３】
検証装置３０は、まず、署名検証部３０１により、記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）について、ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを検証し、次に、署名検証部３０１により、集計端末２０−１の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれるすべての（Ｅ（ｖｉ），Ｓｅｉ）について、ＳｅｉがＥ（ｖｉ）に対する投票端末１０の正当なデジタル署名かどうかを検証する。集計端末２０−１は投票端末１０あるいは投票用ＩＣカード４０−ｉの正当なデジタル署名を生成できないため、集計端末２０−１が実際には投票されていない（Ｅ（ｖｉ’），Ｓｅｉ’）を加えたり、投票内容の改竄を行なった場合には検証に合格しない。これにより、集計端末２０−１が受付けた投票内容を改竄したり、受付けていない不正な投票内容を水増ししていないかどうかを確認できる。【０１５４】
つぎに、リスト照合部３０２により、記録媒体１０７−ｉに記録された（Ｅ（ｖｉ），Ｓｅｉ）が、集計端末２０−１の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれているかどうかを確認する。これにより、投票者は自分の投票内容が受付けられていることを確認できる。【０１５５】
次に、集計端末２０−１の公表した証明データｐが、集計端末２０−１の公表した（Ｅ（ｖｉ），Ｓｅｉ）のリストに含まれるすべてのＥ（ｖｉ）＝（Ｇ’＿ｉ，Ｖ’＿ｉ）と、集計端末２０−１の出力した復号リストに含まれるすべての（Ｇ’’’＿ｊ，Ｖ’’’＿ｊ）との間に１対１の対応関係があることの正しい証明になっているかどうか検証する。【０１５６】
本実施の形態では、集計端末が複数あるので、集計端末２０−１以外の残りの集計端末２０−２〜２０−ｍそれぞれの集計端末の公表したデータについて同様の処理を行なう。以上により、受付けられたすべての投票について、投票内容が正しく集計されているかどうかの確認ができる。
【符号の説明】
【０１５７】
１０、１０’…投票端末
２０…集計端末
２０’…集計端末群
３０…検証装置
４０−ｉ…投票用ＩＣカード
１０１…入力装置
１０２…投票券入力装置
１０３…出力装置
１０４…投票データ記憶装置
１０５…暗号化部
１０６…署名生成部
１０７−ｉ…記録媒体
１０８…ＩＣカード入出力装置
２０１…投票データ読み取り装置
２０２…シャッフル復号部
２０３、３−１…署名検証部
３０２…リスト照合部
３０３…シャッフル復号検証部
４０１−ｉ…署名用秘密鍵
４０２…署名生成部
【図１】
2005057847.tif 000002
【図２】
2005057847.tif 000003
【図３】
2005057847.tif 000004
【図４】
2005057847.tif 000005
【図５】
2005057847.tif 000006
【図６】
2005057847.tif 000007
【図７】
2005057847.tif 000008
【図８】
2005057847.tif 000009
【図９】
2005057847.tif 000010
【図１０】
2005057847.tif 000011
【図１１】
2005057847.tif 000012
【図１２】
2005057847.tif 000013
【国際調査報告】
2005057847.tif 000014
2005057847.tif 000015
2005057847.tif 000016
2005057847.tif 000017