(57)【要約】【課題】分割可能な複数票電子投票方式を、従来の方式より少ない計算量，通信量で実施可能とすること。【解決手段】投票者が投票内容を入力する投票内容入力装置と、投票内容を暗号化した投票電文を作成する投票電文作成手段と、作成された投票電文を送信する投票電文送信手段と、送信された投票電文を受信する投票電文受信手段と、受信された投票電文の正当性をチェックする投票電文チェック手段と、チェックを通過した投票電文を記憶する電子投票箱と、電子投票箱に記憶された投票電文を開票する開票手段と、開票により得られた開票結果を出力する開票結果出力装置を、有して構成される分割可能な複数票電子投票方式において、投票内容入力装置に入力された投票内容に応じて、ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔと呼ばれる自然数の多重集合の構成と分割を行ってから、暗号化して投票電文を作成する。【選択図】図１
2004289564.tif 000002
【特許請求の範囲】
【請求項１】
投票者が投票内容を入力する投票内容入力装置と、投票内容を暗号化した投票電文を作成する投票電文作成手段と、作成された投票電文を送信する投票電文送信手段と、送信された投票電文を受信する投票電文受信手段と、受信された投票電文の正当性をチェックする投票電文チェック手段と、チェックを通過した投票電文を電子投票箱に書き込む電子投票箱書き込み手段と、投票電文を記憶する電子投票箱と、電子投票箱に記憶された投票電文を読み出す電子投票箱読み出し手段と、読み出した投票電文を開票する開票手段と、開票により得られた開票結果を出力する開票結果出力装置を、有して構成される分割可能な複数票電子投票方式において、投票電文作成手段が、ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段とＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段を有して構成されることを特徴とする分割可能な複数票電子投票方式。
【請求項２】
コンピュータを、投票内容入力装置から読み出した投票内容に対して投票電文を作成するＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段とＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段と選択肢暗号化手段と、作成された投票電文を送信する投票電文送信手段と、送信された投票電文を受信する投票電文受信手段と、受信された投票電文の正当性をチェックする投票電文チェック手段と、チェックを通過した投票電文を電子投票箱に書き込む電子投票箱書き込み手段と、電子投票箱に記憶された投票電文を読み出す電子投票箱読み出し手段と、読み出した投票電文を開票する開票手段、として機能させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
電子投票方式には、各投票者の持ち票が一票である単票電子投票方式と、各投票者の持ち票が複数票である複数票電子投票方式がある。さらに複数票電子投票方式には、各投票者が選択した一選択肢に持ち票をすべて投票する方式と、各投票者が複数の選択肢に持ち票を分割して投票できる方式がある。後者は、分割可能な複数票電子投票方式と呼ばれている。本発明は、分割可能な複数票電子投票方式に関する発明である。
【０００２】
なお、分割可能な複数票電子投票方式は下記の様に形式化されている。
分割可能な複数票電子投票方式は、Ｌ人の投票者Ｖ１，．．．，ＶＬと開票者によって構成される。投票者Ｖｉ（１≦ｉ≦Ｌ）の持ち票数をＮｉとする。投票者Ｖｉは、Ｍ通りの選択肢Ａ１，．．．，ＡＭに、持ち票を分割して投票する。すなわち、投票者Ｖｉの選択肢Ａｊ（１≦ｊ≦Ｍ）への投票数をｖｉ，ｊとすると、すべてのｉに対してΣ１≦ｊ≦Ｍｖｉ，ｊ＝Ｎｉが成り立つ必要がある。開票者は、すべてのｊに対して選択肢Ａｊの得票数Σ１≦ｉ≦Ｌｖｉ，ｊを求める。
【０００３】
【従来の技術】
従来の分割可能な複数票電子投票方式としては、単票電子投票方式を用いた方式と、松尾らの方式（非特許文献１参照）がある。単票電子投票方式を用いた方式では、各投票者が単票電子投票方式による単票投票を、各投票者の持ち票数回繰り返す必要があった。松尾らの方式では、各投票者に投票以前の準備段階で通知される投票電文の数が、各投票者の持ち票数以上であった。
【０００４】
【非特許文献１】
松尾真一郎、尾形わかは、「分割可能な複数票電子投票方式」信学技報、２００２年、ＩＳＥＣ２００２−９６
【非特許文献２】
Ｐ．Ｐａｉｌｌｉｅｒ、「Ｐｕｂｌｉｃ−Ｋｅｙ  ＣｒｙｐｔｏｓｙｓｔｅｍｓＢａｓｅｄ  ｏｎ  Ｃｏｍｐｏｓｉｔｅ  Ｄｅｇｒｅｅ  Ｒｅｓｉｄｕｏｓｉｔｙ  Ｃｌａｓｓｅｓ」ＥＵＲＯＣＲＹＰＴ’９９、１９９９年、ｐ．２２３−２３８
【非特許文献３】
Ｉ．Ｄａｍｇａｒｄ、Ｍ．Ｊｕｒｉｋ、「Ａ  Ｇｅｎｅｒａｌｉｓａｔｉｏｎ，ａ  Ｓｉｍｐｌｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｓｏｍｅ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｐａｉｌｌｉｅｒ’ｓ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｓｙｓｔｅｍ」ＰＫＣ２００１、２００１年、ｐ．１１９−１３６
【０００５】
【発明が解決しようとする課題】
従来の分割可能な複数票電子投票方式では、各投票者毎の計算量および通信量が少なくとも各投票者の持ち票数に比例しているため、下記の様な問題点がある。第一に、単票電子投票方式を用いた方式では、集計すべき票の総数が各投票者の持ち票数の総和となるので、迅速な集計ができないという問題点がある。第二に、松尾らの方式では、各投票者に投票以前の準備段階で通知される投票電文の数が、各投票者の持ち票数以上となるので、投票電文の作成に時間がかかるという問題点がある。第三に、単票電子投票方式を用いた方式および松尾らの方式では、暗号化された投票電文の数が少なくとも各投票者の持ち票数に比例しているため、各投票者の持ち票数が多くなると通信コストが増大するという問題点がある。
本発明は、各投票者毎の計算量および通信量が各投票者の持ち票数に対してｌｏｇオーダとなる分割可能な複数票電子投票方式を実現し、上記の問題点を解決することを目的とする。
【０００６】
【課題を解決するための手段】
投票者が投票内容を入力する投票内容入力装置と、投票内容を暗号化した投票電文を作成する投票電文作成手段と、作成された投票電文を送信する投票電文送信手段と、送信された投票電文を受信する投票電文受信手段と、受信された投票電文の正当性をチェックする投票電文チェック手段と、チェックを通過した投票電文を電子投票箱に書き込む電子投票箱書き込み手段と、投票電文を記憶する電子投票箱と、電子投票箱に記憶された投票電文を読み出す電子投票箱読み出し手段と、読み出した投票電文を開票する開票手段と、開票により得られた開票結果を出力する開票結果出力装置を、有して構成される分割可能な複数票電子投票方式において、投票内容入力装置に入力された投票内容に応じて、ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔと呼ばれる自然数の多重集合の構成と分割を行ってから、暗号化して投票電文を作成する。すなわち、本発明の分割可能な複数票電子投票方式では、投票電文作成手段はＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段とＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段を有して構成される。
【０００７】
本発明のために考案したＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔについて以下に述べる。
選択肢の数をＭ、投票者Ｖｉの持ち票数をＮｉとする。任意の持ち票の分割ｖｉ，１，．．．，ｖｉ，Ｍ（Σ１≦ｊ≦Ｍｖｉ，ｊ＝Ｎｉ）に対して、下記の（条件１）及び（条件２）を満たす自然数の多重集合Ｘｉ，１，．．．，Ｘｉ，Ｍ⊆Ｘｉが存在するならば、自然数の多重集合Ｘｉは（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔである。
（条件１）∪１≦ｊ≦ＭＸｉ，ｊ＝Ｘｉであること。
（条件２）すべてのｊ（１≦ｊ≦Ｍ）に対して、自然数の多重集合Ｘｉ，ｊに含まれる自然数の和がｖｉ，ｊと等しいこと。
【０００８】
ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの例を以下に示す。
Ｍ＝２、Ｎｉ＝１００のとき、Ｘｉ＝｛１，２，４，８，１６，３２，３７｝は（２，１００）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔである。例えば、ｖｉ，１＝４５、ｖｉ，２＝５５に対して、Ｘｉ，１＝｛１，４，８，３２｝、Ｘｉ，２＝｛２，１６，３７｝とすると、上記の（条件１）及び（条件２）を満たす。Ｍ＝３、Ｎｉ＝１０００のとき、Ｘｉ＝｛１，２，４，８，１６，３２，６４，１２８，７８，１，２，４，８，１６，３２，６４，１２８，７８，３３４｝は（３，１０００）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔである。例えば、ｖｉ，１＝１３３、ｖｉ，２＝２６７、ｖｉ，３＝６００に対して、Ｘｉ，１＝｛１，４，１２８｝、Ｘｉ，２＝｛２，８，１６，３２，６４，７８，１，２，６４｝、Ｘｉ，３＝｛４，８，１６，３２，１２８，７８，３３４｝とすると、上記の（条件１）及び（条件２）を満たす。
【０００９】
【発明の実施の形態】
本発明の構成について図面を参照しながら説明する。
図１は、本発明の分割可能な複数票電子投票方式Ａの一実施例を示した図である。図１において、分割可能な複数票電子投票方式Ａは、投票者１が投票内容を入力する投票内容入力装置２と、投票内容を暗号化した投票電文を作成する投票電文作成手段３と、作成された投票電文を送信する投票電文送信手段４と、送信された投票電文を受信する投票電文受信手段５と、受信された投票電文の正当性をチェックする投票電文チェック手段６と、チェックを通過した投票電文を電子投票箱７に書き込む電子投票箱書き込み手段７１と、投票電文を記憶する電子投票箱７と、電子投票箱７に記憶された投票電文を読み出す電子投票箱読み出し手段７２と、読み出した投票電文を開票する開票手段８と、開票により得られた開票結果を出力する開票結果出力装置９から構成される。
なお、投票電文作成手段３は、選択肢の数と投票者１の持ち票数に応じてＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔを構成するＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段３１と、選択肢毎の投票数に応じてＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔを分割するＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段３２と、選択肢の暗号化を行う選択肢暗号化手段３３から構成される。
また、開票手段８は、暗号文のまま集計を行う暗号集計手段８１と、集計された暗号文の復号を行う復号手段８２と、復号された集計データから選択肢毎の得票数を抽出する得票数抽出手段８３から構成される。
【００１０】
本発明の動作について図面を参照しながら説明する。
ただし、本発明の動作を実行する以前に、選挙管理委員会から投票者Ｖｉに、選択肢の数Ｍと、持ち票数Ｎｉと、総票数ｗ＝Σ１≦ｉ≦ＬＮｉと、暗号化鍵ＰＫと、パスワードＰｉが通知されているものとする。
【００１１】
最初に、図２で示すように、投票者１は投票内容入力装置２に投票内容を入力する。各投票者Ｖｉ（１≦ｉ≦Ｌ）が入力する投票内容は、選択肢の数Ｍと、持ち票数Ｎｉと、選択肢Ａｊ（１≦ｊ≦Ｍ）への投票数ｖｉ，ｊと、総票数ｗと、暗号化鍵ＰＫと、パスワードＰｉである。
【００１２】
次に、図３で示すように、投票電文作成手段３により投票内容を暗号化した投票電文を作成する。
ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段３１への入力は、選択肢の数Ｍと、持ち票数Ｎｉである。ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段３１の出力は、（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ  Ｘｉと、Ｍ≧３のときＮｉ，ｊおよびＹｉ，ｊである。ただし、１≦ｊ≦Ｍである。
ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段３２への入力は、選択肢の数Ｍと、（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ  Ｘｉと、選択肢Ａｊへの投票数ｖｉ，ｊと、Ｍ≧３のときＮｉ，ｊおよびＹｉ，ｊである。ただし、１≦ｊ≦Ｍである。ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段３２の出力は、選択肢Ａｊ（１≦ｊ≦Ｍ）に対応する自然数の多重集合Ｘｉ，ｊである。
選択肢暗号化手段３３への入力は、選択肢Ａｊ（１≦ｊ≦Ｍ）に対応する自然数の多重集合Ｘｉ，ｊと、総票数ｗと、暗号化鍵ＰＫである。選択肢暗号化手段３３の出力は、投票電文（ｘｉ，ｊ，ｋ，ＥＰＫ（（ｗ＋１）ｊ−１））と、暗号文チェック情報Ｃｉ，ｊ，ｋである。ただし、１≦ｊ≦Ｍ、Ｘｉ，ｊ＝｛ｘｉ，ｊ，ｋ｜１≦ｋ≦＃Ｘｉ，ｊ｝、Ｅは準同型性を持った確率的公開鍵暗号系の暗号化アルゴリズム、ＥＰＫ（ａ）は平文ａを暗号化鍵ＰＫで暗号化した出力値である。
【００１３】
ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段３１で実行される、ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手続きについて図６を参照しながら説明する。
（Ｓ３１−０１）選択肢の数Ｍが２の場合と、Ｍが２以外の場合とに、場合分けを行う。
（Ｓ３１−０２）選択肢の数Ｍが２の場合には、後述する（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きに従ってＸｉを構成する。
（Ｓ３１−０３）選択肢の数Ｍが２以外の場合には、後述する（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きに従ってＸｉと、Ｎｉ，ｊと、Ｙｉ，ｊを構成する。
【００１４】
（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きについて図７を参照しながら説明する。
（Ｓ３１−１１）フローチャートで示した式に従ってＸを構成する。
【００１５】
（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きについて図８を参照しながら説明する。
（Ｓ３１−２１）フローチャートで示した式に従って、選択肢の数Ｍ個分のＮｉ，ｊの値を求める。容易に分かるように、Ｎｉ，ｊの総和はＮｉに等しい。
（Ｓ３１−２２）選択肢の数Ｍ個分の各Ｎｉ，ｊについて、  後述するＹｉ，ｊの構成手続きに従ってＹｉ，ｊを構成する。
（Ｓ３１−２３）Ｙｉ，ｊの和集合をＸｉとする。
【００１６】
Ｙｉ，ｊの構成手続きについて図９を参照しながら説明する。
（Ｓ３１−３１）ｊがＭの場合と、ｊがＭ以外の場合とに、場合分けを行う。
（Ｓ３１−３２）ｊがＭ以外の場合には、さらに、Ｎｉ，ｊが０の場合と、Ｎｉ，ｊが０以外の場合とに、場合分けを行う。
（Ｓ３１−３３）Ｎｉ，ｊが０以外の場合には、Ｎｉ，ｊをＮとして、前述した（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きに従ってＹｉ，ｊを構成する。
（Ｓ３１−３４）Ｎｉ，ｊが０の場合には、空集合をＹｉ，ｊとする。
（Ｓ３１−３５）ｊがＭの場合には、Ｎｉ，ｊを要素とする自然数の多重集合をＹｉ，ｊとする。
【００１７】
ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段３２で実行される、ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手続きについて図１０を参照しながら説明する。
（Ｓ３２−０１）選択肢の数Ｍが２の場合と、Ｍが２以外の場合とに、場合分けを行う。
（Ｓ３２−０２）選択肢の数Ｍが２の場合には、後述する（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きに従ってＸｉをＸｉ，１とＸｉ，２に分割する。
（Ｓ３２−０３）選択肢の数Ｍが２以外の場合には、後述する（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きに従ってＸｉをＸｉ，ｊに分割する。
【００１８】
（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きについて図１１を参照しながら説明する。
（Ｓ３２−１１）集合｛ｎ１，ｎ２｝に対してｎ１≦ｎ２を満たすように置換πを用いて添字を置換する。
（Ｓ３２−１２）ｎ１が０の場合と、ｎ１が０以外の場合とに、場合分けを行う。
（Ｓ３２−１３）ｎ１が０の場合には、空集合をＸ１、ＸをＸ２とする。
（Ｓ３２−１４）ｎ１が０以外の場合には、ｎ１の２進数表現を用いてＸ１を求め、Ｘ−Ｘ１をＸ２とする。
（Ｓ３２−１５）集合｛Ｘ１，Ｘ２｝に対して逆置換π−１を用いて添字を置換する。
【００１９】
（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きについて図１２を参照しながら説明する。
（Ｓ３２−２１）集合｛ｖｉ，１，ｖｉ，２，．．．，ｖｉ，Ｍ｝に対してｖｉ，１≦ｖｉ，２≦・・・≦ｖｉ，Ｍを満たすように置換ρを用いて添字を置換する。
（Ｓ３２−２２）後述するＸｉ，１の構成手続きに従ってＸｉ，１を構成する。
（Ｓ３２−２３）２からＭ−１のｊに対して昇順に、後述するＸｉ，ｊの構成手続きに従ってＸｉ，ｊを構成する。
（Ｓ３２−２４）後述するＸｉ，Ｍの構成手続きに従ってＸｉ，Ｍを構成する。
（Ｓ３２−２５）集合｛Ｘｉ，１，Ｘｉ，２，．．．，Ｘｉ，Ｍ｝に対して逆置換ρ−１を用いて添字を置換する。
【００２０】
Ｘｉ，１の構成手続きについて図１３を参照しながら説明する。
（Ｓ３２−３１）Ｎｉ，１が０の場合と、Ｎｉ，１が０以外の場合とに、場合分けを行う。
（Ｓ３２−３２）Ｎｉ，１が０の場合には、空集合をＸｉ，１とする。
（Ｓ３２−３３）Ｎｉ，１が０以外の場合には、Ｙｉ，１とｖｉ，１について、前述した（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きに従ってＸｉ，１を構成する。
【００２１】
Ｘｉ，ｊの構成手続きについて図１４を参照しながら説明する。
（Ｓ３２−４１）空集合をＺ０とする。１からｊ−１のａに対して、Ｙｉ，ａの要素のうち、Ｘｉ，１，．．．，Ｘｉ，ｊ−１に含まれていない要素からなる自然数の多重集合をＺａとする。すなわち、Ｙｉ，ａの要素のうち、まだ分割に使用されていない要素からなる自然数の多重集合をＺａとする。Ｙｉ，ｊをＺｊとする。
（Ｓ３２−４２）等号が成立する場合には、Ｓ３２−４３に進む。等号が成立しない場合には、Ｓ３２−４４に進む。
（Ｓ３２−４３）フローチャートで示した式に従ってＸｉ，ｊを構成する。
（Ｓ３２−４４）フローチャートで示した式を満たすｍを求める。すなわち、Ｚ０，．．．，Ｚｍに含まれる要素をＸｉ，ｊの要素とすることができる。
（Ｓ３２−４５）フローチャートで示した式に従ってｎ１を求める。すなわち、Ｚ０，．．．，Ｚｍに含まれる要素をＸｉ，ｊの要素とするならば、Ｘｉ，ｊに含まれる自然数の和がｖｉ，ｊと等しくなるためには、あとｎ１票不足している。Ｙｉ，ｊとｎ１について、前述した（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きに従ってＹ’ｉ，ｊを構成する。
（Ｓ３２−４６）フローチャートで示した式に従ってＸｉ，ｊを構成する。すなわち、Ｘｉ，ｊは、Ｚ０，．．．，Ｚｍと、不足していたｎ１票を補うＹ’ｉ，ｊの和集合である。
【００２２】
Ｘｉ，Ｍの構成手続きについて図１５を参照しながら説明する。
（Ｓ３２−５１）フローチャートで示した式に従ってＸｉ，Ｍを構成する。容易に分かるように、Ｘｉ，Ｍは、Ｘｉの要素のうちまだ分割に使用されていない要素からなる自然数の多重集合である。
【００２３】
選択肢暗号化手段３３で実行される、選択肢暗号化手続きについて説明する。
すべてのｊ，ｋ（１≦ｊ≦Ｍ，１≦ｋ≦＃Ｘｉ，ｊ）に対して、自然数ｘｉ，ｊ，ｋと暗号文ＥＰＫ（（ｗ＋１）ｊ−１）の組を投票電文として出力する。ただし、Ｘｉ，ｊ＝｛ｘｉ，ｊ，ｋ｜１≦ｋ≦＃Ｘｉ，ｊ｝、Ｅは準同型性を持った確率的公開鍵暗号系の暗号化アルゴリズム、ＥＰＫ（ａ）は平文ａを暗号化鍵ＰＫで暗号化した出力値である。確率的公開鍵暗号系の暗号化アルゴリズムＥが準同型性を持つとは、任意の平文ａ１，ａ２に対して、ＥＰＫ（ａ１）×ＥＰＫ（ａ２）＝ＥＰＫ（ａ１＋ａ２）となることである。準同型性を持った確率的公開鍵暗号系としては、Ｐａｉｌｌｉｅｒ暗号（非特許文献２参照）がある。
すべてのｊ，ｋ（１≦ｊ≦Ｍ，１≦ｋ≦＃Ｘｉ，ｊ）に対して、投票電文として出力した上記の暗号文がＥＰＫ（（ｗ＋１）０），．．．，ＥＰＫ（（ｗ＋１）Ｍ−１）のいずれかであることの証拠として、暗号文チェック情報Ｃｉ，ｊ，ｋを出力する。すなわち、暗号文チェック情報Ｃｉ，ｊ，ｋとは、ゼロ知識証明において証明者（選択肢暗号化手段３３）から検証者（投票電文チェック手段６）に送信される情報である。（非特許文献３参照）
【００２４】
投票電文作成手段３により出力された投票電文（ｘｉ，ｊ，ｋ，ＥＰＫ（（ｗ＋１）ｊ−１））と暗号文チェック情報Ｃｉ，ｊ，ｋとパスワードＰｉは、投票電文送信手段４により送信され、投票電文受信手段５により受信される。ただし、１≦ｊ≦Ｍ、１≦ｋ≦＃Ｘｉ，ｊである。
【００２５】
次に、図４で示すように、投票電文チェック手段６により投票電文の正当性をチェックする。
投票電文チェック手段６への入力は、投票電文（ｘｉ，ｊ，ｋ，ＥＰＫ（（ｗ＋１）ｊ−１））と、暗号文チェック情報Ｃｉ，ｊ，ｋと、パスワードＰｉと、選挙管理委員会により入力される選択肢の数Ｍ，持ち票数Ｎｉ，総票数ｗ，投票者Ｖｉの正しいパスワードＰ’ｉである。投票電文チェック手段６により、下記の（チェック１）及び（チェック２）及び（チェック３）を満たすことが確認できたならば、投票電文（ｘｉ，ｊ，ｋ，ＥＰＫ（（ｗ＋１）ｊ−１））は電子投票箱書き込み手段７１により電子投票箱７に書き込まれる。ただし、１≦ｊ≦Ｍ、１≦ｋ≦＃Ｘｉ，ｊである。
（チェック１）Ｐｉ＝Ｐ’ｉであること。
（チェック２）ΣｊΣｋｘｉ，ｊ，ｋ＝Ｎｉであること。
（チェック３）すべてのｊ，ｋ（１≦ｊ≦Ｍ，１≦ｋ≦＃Ｘｉ，ｊ）に対して、暗号文チェック情報Ｃｉ，ｊ，ｋが、ゼロ知識証明において検証者にａｃｃｅｐｔされること。（非特許文献３参照）
【００２６】
投票締切後、図５で示すように、電子投票箱読み出し手段７２により電子投票箱７に記憶された投票電文の読み出しを行う。そして、開票手段８により投票電文を開票する。
【００２７】
暗号集計手段８１への入力は、電子投票箱読み出し手段７２により読み出された投票電文（ｘｉ，ｊ，ｋ，ＥＰＫ（（ｗ＋１）ｊ−１））である。暗号集計手段８１の出力は、ΠｉΠｊΠｋ（（ＥＰＫ（（ｗ＋１）ｊ−１））のｘｉ，ｊ，ｋ乗）を計算することにより得られる、集計データＳ＝Σ１≦ｊ≦Ｍ（（Σｉｖｉ，ｊ）（ｗ＋１）ｊ−１）の暗号文ＥＰＫ（Ｓ）である。
なぜならば、準同型性から容易に分かるように、
ΠｉΠｊΠｋ（（ＥＰＫ（（ｗ＋１）ｊ−１））のｘｉ，ｊ，ｋ乗）
＝ΠｉΠｊΠｋ（ＥＰＫ（ｘｉ，ｊ，ｋ（ｗ＋１）ｊ−１））
＝ＥＰＫ（ΣｉΣｊΣｋｘｉ，ｊ，ｋ（ｗ＋１）ｊ−１）
＝ＥＰＫ（ΣｉΣｊｖｉ，ｊ（ｗ＋１）ｊ−１）
＝ＥＰＫ（Σ１≦ｊ≦Ｍ（（Σｉｖｉ，ｊ）（ｗ＋１）ｊ−１））
＝ＥＰＫ（Ｓ）
となるからである。
【００２８】
復号手段８２への入力は、集計データの暗号文ＥＰＫ（Ｓ）と、選挙管理委員会により入力される復号鍵ＳＫである。復号手段８２の出力は、ＤＳＫ（ＥＰＫ（Ｓ））を計算することにより得られる、集計データＳである。ただし、Ｄは準同型性を持った確率的公開鍵暗号系の復号アルゴリズム、ＤＳＫ（ａ）は暗号文ａを復号鍵ＳＫで復号した出力値である。
【００２９】
得票数抽出手段８３への入力は、集計データＳと、選挙管理委員会により入力される総票数ｗである。得票数抽出手段８３の出力は、Ｓ１＝Ｓ  ｍｏｄ  （ｗ＋１）、２からＭのａに対して昇順にＳａ＝（Ｓ−Σ１≦ｂ≦ａ−１Ｓｂ（ｗ＋１）ｂ−１）（ｗ＋１）−（ａ−１）  ｍｏｄ  （ｗ＋１）を計算することにより得られる、選択肢Ａｊ（１≦ｊ≦Ｍ）の得票数Ｓｊであり、開票結果出力装置９により出力される。
【００３０】
【発明の効果】
本発明の分割可能な複数票電子投票方式Ａにおける各投票者Ｖｉ毎の投票電文の数は、選択肢暗号化手段３３で実行される選択肢暗号化手続きより、選択肢の数をＭ、持ち票数をＮｉとすると、（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの要素数と等しい。ここで、（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの要素数が、持ち票数Ｎｉに対してｌｏｇオーダとなることを、ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段３１で実行されるＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手続きより示す。ただし、ｆｌｏｏｒ（ａ）を実数ａ以下の最大の整数、ｃｅｉｌ（ａ）を実数ａ以上の最小の整数とする。選択肢の数Ｍが２の場合には、（Ｓ３１−１１）よりＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの要素数はｆｌｏｏｒ（ｌｏｇ２Ｎｉ）＋１である。選択肢の数Ｍが２以外の場合には、（Ｓ３１−２１）よりＮｉ，ｊはｃｅｉｌ（Ｎｉ／Ｍ）以下、（Ｓ３１−２２）よりＹｉ，ｊの要素数はｆｌｏｏｒ（ｌｏｇ２ｃｅｉｌ（Ｎｉ／Ｍ））＋１以下、（Ｓ３１−２３）よりＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの要素数はＭ×（ｆｌｏｏｒ（ｌｏｇ２ｃｅｉｌ（Ｎｉ／Ｍ））＋１）以下である。
したがって、本発明により、各投票者毎の計算量および通信量が各投票者の持ち票数に対してｌｏｇオーダとなる分割可能な複数票電子投票方式を実現することが可能となった。すなわち、分割可能な複数票電子投票をより迅速に、より少ない通信コストで実施することが可能となった。
【００３１】
本発明の分割可能な複数票電子投票方式Ａの安全性について述べる。
ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段３２で実行されるＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手続きにより、任意の持ち票の分割ｖｉ，１，．．．，ｖｉ，Ｍ（Σ１≦ｊ≦Ｍｖｉ，ｊ＝Ｎｉ）に対して、（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ  Ｘｉを（条件１）及び（条件２）を満たす自然数の多重集合Ｘｉ，１，．．．，Ｘｉ，Ｍに分割して出力できる。よって、ｖｉ，ｊに関する情報を得るためには、投票電文に含まれる暗号文が（ｗ＋１）０，．．．，（ｗ＋１）Ｍ−１のいずれを暗号化したものであるかを区別できなければならない。しかし、そのような不正を行うのには、復号鍵が必要である。
したがって、本発明の分割可能な複数票電子投票方式Ａは、選挙管理委員会から復号鍵が流出しない限り各投票者の持ち票の分割は秘匿にされるので、各投票者は分割可能な複数票電子投票方式Ａによる電子投票を信頼して使用することができる。
また、一般的に準同型性を持った確率的公開鍵暗号系では、復号鍵を複数の選挙管理委員で分散共有し、復号に閾値法を用いることができる。（非特許文献３参照）これにより分割可能な複数票電子投票方式Ａは、閾値法により定まる閾値以下の選挙管理委員が不正をしたとしても、安全性を保つことができる。
【図面の簡単な説明】
【図１】本発明の一実施例を示した図である。
【図２】投票内容入力装置への投票を示した図である。
【図３】投票電文の作成の流れを示した図である。
【図４】投票電文のチェックと電子投票箱への書き込みの流れを示した図である。
【図５】投票電文の電子投票箱からの読み出しと開票および開票結果出力の流れを示した図である。
【図６】ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手続きを示した図である。
【図７】（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きを示した図である。
【図８】（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの構成手続きを示した図である。
【図９】Ｙｉ，ｊの構成手続きを示した図である。
【図１０】ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手続きを示した図である。
【図１１】（２，Ｎ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きを示した図である。
【図１２】（Ｍ，Ｎｉ）‐ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔの分割手続きを示した図である。
【図１３】Ｘｉ，１の構成手続きを示した図である。
【図１４】Ｘｉ，ｊの構成手続きを示した図である。
【図１５】Ｘｉ，Ｍの構成手続きを示した図である。
【符号の説明】
１    投票者
２    投票内容入力装置
３    投票電文作成手段
３１  ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ構成手段
３２  ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ分割手段
３３  選択肢暗号化手段
４    投票電文送信手段
５    投票電文受信手段
６    投票電文チェック手段
７    電子投票箱
７１  電子投票箱書き込み手段
７２  電子投票箱読み出し手段
８    開票手段
８１  暗号集計手段
８２  復号手段
８３  得票数抽出手段
９    開票結果出力装置
Ａ    分割可能な複数票電子投票方式
【図１】
2004289564.tif 000003
【図２】
2004289564.tif 000004
【図３】
2004289564.tif 000005
【図４】
2004289564.tif 000006
【図５】
2004289564.tif 000007
【図６】
2004289564.tif 000008
【図７】
2004289564.tif 000009
【図８】
2004289564.tif 000010
【図９】
2004289564.tif 000011
【図１０】
2004289564.tif 000012
【図１１】
2004289564.tif 000013
【図１２】
2004289564.tif 000014
【図１３】
2004289564.tif 000015
【図１４】
2004289564.tif 000016
【図１５】
2004289564.tif 000017