ＭＩＸ−ｎｅｔと準同型性に基づいた電子投票システム
【課題】
従来のＭＩＸ−ｎｅｔに基づいた電子投票システムでは、投票装置の負担は軽いが、投票締切後に全投票者の投票を一度に集計する必要があるため、開票装置の負担が大きいという問題点がある。
従来の準同型性に基づいた電子投票システムでは、開票装置の負担は軽いが、投票の際にゼロ知識証明をする必要があるため、投票装置の負担が大きいという問題点がある。
【解決手段】
投票装置の組立暗号文作成指示暗号文作成手段で、ランダム置換と再暗号化の乱数リストを作成して、開票装置に送信する。
開票装置の組立暗号文作成手段で、投票装置から受信したランダム置換と再暗号化の乱数リストを用いて、組立暗号文を作成する。
従来のＭＩＸ−ｎｅｔに基づいた電子投票システムでは、投票装置の負担は軽いが、投票締切後に全投票者の投票を一度に集計する必要があるため、開票装置の負担が大きいという問題点がある。
従来の準同型性に基づいた電子投票システムでは、開票装置の負担は軽いが、投票の際にゼロ知識証明をする必要があるため、投票装置の負担が大きいという問題点がある。
【解決手段】
投票装置の組立暗号文作成指示暗号文作成手段で、ランダム置換と再暗号化の乱数リストを作成して、開票装置に送信する。
開票装置の組立暗号文作成手段で、投票装置から受信したランダム置換と再暗号化の乱数リストを用いて、組立暗号文を作成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術のうち電子投票システムに関する発明である。
一般に、電子投票システムは、ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）と投票装置Ｖによって構成される。
不正を行なう開票装置の台数をｔ以下として、ｓ≧２ｔ＋１を満たすものとする。
ｖ人の投票者Ｖｊ（１≦ｊ≦ｖ）が、投票装置Ｖへ下記の投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）を入力する。
【０００２】
投票者が選択できる選択肢をａ通りの選択肢Ａｋ（１≦ｋ≦ａ）とする。
投票者Ｖｊの持ち票数をｎｊとする。
投票者Ｖｊの選択肢Ａｋに対する投票数をｎ（ｊ，ｋ）とする。
ただし、０≦ｎ（ｊ，ｋ）≦ｎｊ、Σｋｎ（ｊ，ｋ）＝ｎｊを満たすものとする。
【０００３】
投票には、持ち票数と持ち票数の分割の仕方に応じて、様々な投票形式がある。
例えば、単票投票形式、分割不可能な複数票投票形式、分割可能な複数票投票形式がある。
単票投票形式とは、各投票者の持ち票が一票である投票形式である。
すなわち、投票者Ｖｊは、選択したａｊ番目の選択肢に一票を投票する。
すると、ｋ＝ａｊに対してｎ（ｊ，ｋ）＝１、ｋ≠ａｊに対してｎ（ｊ，ｋ）＝０が成り立つ。
分割不可能な複数票投票形式とは、各投票者の持ち票が複数票であり、一つの選択肢に持ち票をすべて投票する投票形式である。
すなわち、投票者Ｖｊは、選択したａｊ番目の選択肢に持ち票をすべて投票する。
すると、ｋ＝ａｊに対してｎ（ｊ，ｋ）＝ｎｊ、ｋ≠ａｊに対してｎ（ｊ，ｋ）＝０が成り立つ。
分割可能な複数票投票形式とは、各投票者の持ち票が複数票であり、複数の選択肢に持ち票を分割して投票できる投票形式である。
すなわち、投票者Ｖｊは、複数の選択肢にｎｊ票を０≦ｎ（ｊ，ｋ）≦ｎｊ、Σｋｎ（ｊ，ｋ）＝ｎｊを満たすようにｎ（ｊ，１）票，．．．，ｎ（ｊ，ａ）票に分割して投票できる。
【０００４】
投票締切後に、ｓ台の開票装置が協力して、すべての選択肢Ａｋに対して得票数Σｊｎ（ｊ，ｋ）を求める。
【背景技術】
【０００５】
従来の電子投票システムには、ＭＩＸ−ｎｅｔに基づいた電子投票システムと準同型性に基づいた電子投票システムが知られている。
準同型性とＭＩＸ−ｎｅｔと記号の定義について説明した後に、従来の電子投票システムについて説明する。
【０００６】
準同型性について説明する。
（Ｇａｓｙｍ，Ｅａｓｙｍ，Ｄａｓｙｍ，ＰＫａｓｙｍ，ＳＫａｓｙｍ，Ｍａｓｙｍ，Ｒａｓｙｍ，Ｃａｓｙｍ）を確率的公開鍵暗号系とする。
Ｇａｓｙｍは、セキュリティパラメータを入力とし、公開鍵ＰＫ∈ＰＫａｓｙｍと秘密鍵ＳＫ∈ＳＫａｓｙｍを出力する鍵生成アルゴリズムである。
Ｅａｓｙｍは、平文ｍ∈Ｍａｓｙｍと乱数ｒ∈Ｒａｓｙｍを入力とし、公開鍵ＰＫを用いて暗号文ｃ＝ＥａｓｙｍＰＫ（ｍ，ｒ）を出力する暗号化アルゴリズムである。
Ｄａｓｙｍは、暗号文ｃ∈Ｃａｓｙｍを入力とし、秘密鍵ＳＫを用いて平文ｍ＝ＤａｓｙｍＳＫ（ｃ）を出力する復号アルゴリズムである。
簡単のため、乱数ｒが重要でない場合は、確率的公開鍵暗号系の暗号化アルゴリズムの引数の乱数を省略する。
すなわち、ｃ＝ＥａｓｙｍＰＫ（ｍ，ｒ）の代わりにｃ＝ＥａｓｙｍＰＫ（ｍ）と記述する。
確率的公開鍵暗号系が準同型性を持つとは、任意の平文ｍ１，ｍ２に対して、ＥａｓｙｍＰＫ（ｍ１）×ＥａｓｙｍＰＫ（ｍ２）＝ＥａｓｙｍＰＫ（ｍ１＋ｍ２）が成立することである。
本発明の電子投票システムでは、任意の平文ｍ１，ｍ２と任意の乱数ｒ１，ｒ２に対して、ＥａｓｙｍＰＫ（ｍ１，ｒ１）×ＥａｓｙｍＰＫ（ｍ２，ｒ２）＝ＥａｓｙｍＰＫ（ｍ１＋ｍ２，ｒ１＋ｒ２）が成立する、準同型性を持つ確率的公開鍵暗号系を使用する。
【０００７】
ＭＩＸ−ｎｅｔについて説明する。
準同型性を持つ確率的公開鍵暗号系に基づいたＭＩＸ−ｎｅｔとは、下記の手順からなる匿名通信路である。
ただし、複数台の開票装置によって、秘密鍵が閾値法を用いて分散共有されているものとする。
最初に、複数の暗号文からなるリストが入力される。
次に、閾値台の開票装置が逐次に、リストに含まれる各暗号文を再暗号化ＥａｓｙｍＰＫ（ｍ，ｒ）×ＥａｓｙｍＰＫ（０，ｒ’）＝ＥａｓｙｍＰＫ（ｍ，ｒ＋ｒ’）して、リストに含まれる暗号文の順番をランダム置換して、再暗号化とランダム置換の処理の正当性をゼロ知識証明で示す。
最後に、複数台の開票装置が協力して、リストに含まれる各暗号文を閾値復号法を用いて復号して出力する。
閾値台以上の開票装置が結託しなければ、入力暗号文と出力復号文の対応関係が不明となるため、匿名通信路として機能する。
本発明の電子投票システムでは、複数の暗号文からなるリストに対する再暗号化とランダム置換の処理の正当性をゼロ知識証明で示すことが可能であり、秘密鍵が閾値法を用いて分散共有されることで閾値復号法を用いて復号することが可能である、準同型性を持つ確率的公開鍵暗号系を使用する。（非特許文献１、非特許文献２参照）
上記の条件を満たす準同型性を持つ確率的公開鍵暗号系の例としては、変形ＥｌＧａｍａｌ暗号ＥａｓｙｍＰＫ（ｍ，ｒ）＝（ｇｒ，ｇｍｙｒ）がある。
変形ＥｌＧａｍａｌ暗号の復号アルゴリズムのうち、ＥｌＧａｍａｌ暗号の復号アルゴリズムで復号した値ｇｍから平文ｍを求める部分には、落とし戸が存在しない。
そのため、変形ＥｌＧａｍａｌ暗号の平文空間は、可能な限り狭くする必要がある。
【０００８】
記号の定義について説明する。
ｎを総票数Σｊｎｊとする。
Πｘを｛１，．．．，ｘ｝→｛１，．．．，ｘ｝なる置換関数の集合とする。
||をビット列の結合演算子とする。
（Ｅｓｙｍ，Ｄｓｙｍ，Ｋｓｙｍ，Ｍｓｙｍ，Ｃｓｙｍ）を共通鍵暗号系とする。
Ｅｓｙｍは、平文ｍ∈Ｍｓｙｍを入力とし、共通鍵Ｋ∈Ｋｓｙｍを用いて暗号文ｃ＝ＥｓｙｍＫ（ｍ）を出力する暗号化アルゴリズムである。
Ｄｓｙｍは、暗号文ｃ∈Ｃｓｙｍを入力とし、共通鍵Ｋ∈Ｋｓｙｍを用いて平文ｍ＝ＤｓｙｍＫ（ｃ）を出力する復号アルゴリズムである。
本発明の電子投票システムのうち分割可能な複数票投票形式の場合では、ある特殊な性質を持つ自然数の多重集合ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ（特許文献１参照）を使用する。
【０００９】
ＭＩＸ−ｎｅｔに基づいた電子投票システムについて説明する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムでは、複数の暗号文からなるリストに対する再暗号化とランダム置換の処理の正当性をゼロ知識証明で示すことが可能であり、秘密鍵が閾値法を用いて分散共有されることで閾値復号法を用いて復号することが可能である、準同型性を持つ確率的公開鍵暗号系を使用する。
また、複数台の開票装置によって、秘密鍵が閾値法を用いて分散共有されているものとする。
【００１０】
まず最初に、単票投票形式の場合について説明する。
単票投票形式の場合の投開票の手順は、下記の通りである。
（ステップ１）
投票装置Ｖが、暗号文ＥａｓｙｍＰＫ（ａｊ）を開票装置へ送信する。
（ステップ２）
投票締切後に、ｓ台の開票装置が協力して、受信した暗号文からなるリストをＭＩＸ−ｎｅｔを用いて復号する。
（ステップ３）
ｓ台の開票装置が協力して、リストに含まれる各復号文がｋ（１≦ｋ≦ａ）のいずれかであることを確認して、集計して得票数を求める。
本システムにおける、投票装置の計算量は各投票者毎にＯ（１）であり、投票締切後の開票装置の計算量はＯ（ｎｔ）である。
【００１１】
次に、分割不可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投開票の手順との差分は、下記の通りである。
（ステップ２）
投票締切前から、ｓ台の開票装置が協力して、受信した暗号文ＥａｓｙｍＰＫ（ａｊ）をｎｊ個にコピーする。
投票締切後に、ｓ台の開票装置が協力して、コピーされた暗号文からなるリストをＭＩＸ−ｎｅｔを用いて復号する。
本システムにおける、投票装置の計算量は各投票者毎にＯ（１）であり、投票締切後の開票装置の計算量はＯ（ｎｔ）である。
【００１２】
最後に、分割可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投開票の手順との差分は、下記の通りである。
（ステップ１）
投票装置Ｖが、すべての選択肢Ａｋに対して、ｎ（ｊ，ｋ）個の暗号文ＥａｓｙｍＰＫ（ｋ）を開票装置へ送信する。
本システムにおける、投票装置の計算量は各投票者毎にＯ（ｎｊ）であり、投票締切後の開票装置の計算量はＯ（ｎｔ）である。
【００１３】
準同型性に基づいた電子投票システムについて説明する。
準同型性に基づいた電子投票システムでは、暗号文が特定の複数の平文のいずれかを暗号化したものであることをゼロ知識証明で示すことが可能であり、秘密鍵を閾値法を用いて分散共有することで閾値復号法を用いて復号することが可能である、準同型性を持つ確率的公開鍵暗号系を使用する。
また、複数台の開票装置によって、秘密鍵が閾値法を用いて分散共有されているものとする。
また、暗号文が特定のｘ個の平文のいずれかを暗号化したものであることを示すゼロ知識証明を１−ｏｕｔ−ｏｆ−ｘＰＭＰ（ＰｌａｉｎｔｅｘｔＭｅｍｂｅｒｓｈｉｐＰｒｏｏｆ）と記述する。
１−ｏｕｔ−ｏｆ−ｘＰＭＰの計算量と通信量は、ｘに比例する。
準同型性に基づいた電子投票システムには、開票装置が各選択肢毎に暗号文を準同型性を用いてまとめるＳｅｐａｒａｔｅ−ｔｙｐｅと、開票装置が全選択肢一緒に暗号文を準同型性を用いてまとめるＣｏｍｂｉｎｅｄ−ｔｙｐｅがある。
Ｓｅｐａｒａｔｅ−ｔｙｐｅでは、平文空間の大きさは総票数なので、変形ＥｌＧａｍａｌ暗号を使用すれば良い。
しかし、Ｃｏｍｂｉｎｅｄ−ｔｙｐｅでは、平文空間の大きさは総票数の選択肢数乗になるので、変形ＥｌＧａｍａｌ暗号を使用すると復号の効率が悪いため、Ｐａｉｌｌｉｅｒ暗号を使用する。
単票投票形式の場合では、Ｓｅｐａｒａｔｅ−ｔｙｐｅとＣｏｍｂｉｎｅｄ−ｔｙｐｅの両方を説明するが、それ以降では、Ｓｅｐａｒａｔｅ−ｔｙｐｅとＣｏｍｂｉｎｅｄ−ｔｙｐｅのうち投票装置の計算量が最少の方を説明する。
【００１４】
まず最初に、単票投票形式の場合について説明する。
単票投票形式の場合うちＳｅｐａｒａｔｅ−ｔｙｐｅの場合の投開票の手順は、下記の通りである。
（ステップ１）
投票装置Ｖが、暗号文ｅ（ｊ，ｋ）＝ＥａｓｙｍＰＫ（ｎ（ｊ，ｋ））（１≦ｋ≦ａ）を開票装置へ送信して、暗号文ｅ（ｊ，ｋ）が０，１のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−２ＰＭＰを用いて開票装置に証明して、暗号文Πｋｅ（ｊ，ｋ）が１を暗号化したものであることをゼロ知識証明で開票装置に示す。
（ステップ２）
投票締切前から、複数台の開票装置が協力して、暗号文ｅ（ｊ，ｋ）を準同型性を用いて集計暗号文ｅｋ＝Πｊｅ（ｊ，ｋ）にまとめる。
（ステップ３）
投票締切後に、複数台の開票装置が協力して、集計暗号文ｅｋを閾値復号法を用いて復号して得票数を求める。
本方式における、投票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切後の開票装置の計算量はＯ（ａｔ）である。
【００１５】
単票投票形式の場合うちＣｏｍｂｉｎｅｄ−ｔｙｐｅの場合の投開票の手順は、下記の通りである。
ただし、Ｎを総票数ｎより大きい自然数とする。
（ステップ１）
投票装置Ｖが、暗号文ｅｊ＝ＥａｓｙｍＰＫ（Ｎの（ａｊ−１）乗）を開票装置へ送信して、暗号文ｅｊがＮの（ｋ−１）乗（１≦ｋ≦ａ）のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−ａＰＭＰを用いて開票装置に証明する。
（ステップ２）
投票締切前から、複数台の開票装置が協力して、暗号文ｅｊを準同型性を用いて集計暗号文ｅ＝Πｊｅｊにまとめる。
（ステップ３）
投票締切後に、複数台の開票装置が協力して、集計暗号文ｅを閾値復号法を用いて復号して、復号文のＮ進数表現から得票数を求める。
復号文のＮ進数表現から得票数を求められるのは、次式が成立するからである。
ｅ＝ΠｊＥａｓｙｍＰＫ（Ｎの（ａｊ−１）乗）
＝ＥａｓｙｍＰＫ（ΣｊＮの（ａｊ−１）乗）
＝ＥａｓｙｍＰＫ（ΣｊΣｋｎ（ｊ，ｋ）Ｎの（ｋ−１）乗）
＝ＥａｓｙｍＰＫ（ΣｋＮの（ｋ−１）乗（Σｊｎ（ｊ，ｋ）））
本方式における、投票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切後の開票装置の計算量はＯ（ｔ）である。
【００１６】
次に、分割不可能な複数票投票形式の場合について説明する。
単票投票形式の場合うちＣｏｍｂｉｎｅｄ−ｔｙｐｅの場合の投開票の手順との差分は、下記の通りである。
（ステップ１）
投票装置Ｖが、暗号文ｅｊ＝ＥａｓｙｍＰＫ（ｎｊＮの（ａｊ−１）乗）を開票装置へ送信して、暗号文ｅｊがｎｊＮの（ｋ−１）乗（１≦ｋ≦ａ）のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−ａＰＭＰを用いて開票装置に証明する。
本方式における、投票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切前のサーバの計算量は各投票者毎にＯ（ａ）であり、投票締切後のサーバの計算量はＯ（ｔ）である。
【００１７】
最後に、分割可能な複数票投票形式の場合について説明する。
分割可能な複数票投票形式の場合うちＳｅｐａｒａｔｅ−ｔｙｐｅの場合の投開票の手順は、下記の通りである。
（ステップ１）
投票装置Ｖが、投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）のＢ進数表現を（ｂ（ｊ，ｋ，Ｂ［ｊ］），．．．，ｂ（ｊ，ｋ，０）），Ｂ［ｊ］＝ｆｌｏｏｒ（ｌｏｇＢｎｊ）とする。
ただし、ｆｌｏｏｒ（ｘ）は実数ｘ以下の最大の整数である。
投票装置Ｖが、暗号文ｅ（ｊ，ｋ，ｚ）＝ＥａｓｙｍＰＫ（ｂ（ｊ，ｋ，ｚ））（１≦ｋ≦ａ，０≦ｚ≦Ｂ［ｊ］）を開票装置へ送信して、暗号文ｅ（ｊ，ｋ，ｚ）がｂ（０≦ｂ≦Ｂ−１）のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−ＢＰＭＰを用いて開票装置に証明して、暗号文ΠｋΠｚｅ（ｊ，ｋ，ｚ）の（Ｂのｚ乗）乗がｎｊを暗号化したものであることをゼロ知識証明で開票装置に示す。
（ステップ２）
投票締切前から、複数台の開票装置が協力して、暗号文ｅ（ｊ，ｋ，ｚ）を準同型性を用いて集計暗号文ｅｋ＝ΠｊΠｚｅ（ｊ，ｋ，ｚ）の（Ｂのｚ乗）乗にまとめる。
（ステップ３）
投票締切後に、複数台の開票装置が協力して、集計暗号文ｅｋを閾値復号法を用いて復号して得票数を求める。
復号文から得票数を求められるのは、次式が成立するからである。
ｅｋ＝ΠｊΠｚＥａｓｙｍＰＫ（ｂ（ｊ，ｋ，ｚ））の（Ｂのｚ乗）乗
＝ＥａｓｙｍＰＫ（ΣｊΣｚｂ（ｊ，ｋ，ｚ）Ｂのｚ乗）
＝ＥａｓｙｍＰＫ（Σｊｎ（ｊ，ｋ））
本方式における、投票装置の計算量は各投票者毎にＯ（ａ ｌｏｇ ｎｊ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａ ｌｏｇ ｎｊ）であり、投票締切後のサーバの計算量はＯ（ａｔ）である。
ちなみに、Ｂの値が３または４の時に、効率が良いことが知られている。
【非特許文献１】Ｊ．Ｇｒｏｔｈ、「Ａ Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈｕｆｆｌｅ ｏｆ Ｈｏｍｏｍｏｒｐｈｉｃ Ｅｎｃｒｙｐｔｉｏｎｓ」ＰＫＣ２００３、２００３年、ｐ．１４５−１６０
【非特許文献２】Ｍ．Ａｂｅ、「Ｕｎｉｖｅｒｓａｌｌｙ Ｖｅｒｉｆｉａｂｌｅ Ｍｉｘ−ｎｅｔ ｗｉｔｈ Ｖｅｒｉｆｉｃａｔｉｏｎ Ｗｏｒｋ Ｉｎｄｅｐｅｎｄｅｎｔ ｏｆ ｔｈｅ Ｎｕｍｂｅｒ ｏｆ Ｍｉｘ−ｓｅｒｖｅｒｓ」ＥＵＲＯＣＲＹＰＴ’９８、１９９８年、ｐ．４３７−４４７
【特許文献１】特願２００３−０７９９０４
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従来のＭＩＸ−ｎｅｔに基づいた電子投票システムでは、投票装置の負担は軽いが、投票締切後に全投票者の投票を一度に集計する必要があるため、開票装置の負担が大きいという問題点がある。
従来の準同型性に基づいた電子投票システムでは、開票装置の負担は軽いが、投票の際にゼロ知識証明をする必要があるため、投票装置の負担が大きいという問題点がある。
本発明は、投票締切後の開票装置の負担を従来の準同型性に基づいた電子投票システムと同程度に抑えたまま、投票装置の負担を少なくできる公開検証可能な電子投票システムを実現し、上記の問題点を解決することを目的とする。
【課題を解決するための手段】
【００１９】
準同型性に基づいた電子投票システムのうち単票投票形式のＳｅｐａｒａｔｅ−ｔｙｐｅの場合では、ステップ１において投票装置はａ個の暗号文の作成およびａ回の１−ｏｕｔ−ｏｆ−２ＰＭＰの実行をしなければならず、選択肢の数ａが大きい場合には効率的でない。
そこで、本発明では、暗号化されるａ個の平文リストは（１，０，．．．，０）の置換であることに注目し、ａ個の暗号文の作成を開票装置に任せることで、投票装置の計算量を削減する。
ａ個の暗号文の作成は、投票内容の秘匿のためにＭＩＸ−ｎｅｔと同様に、閾値台の開票装置が逐次に再暗号化とランダム置換を繰り返して行なう。
投票装置は、投票内容がＭＩＸ−ｎｅｔから出力されるように、各開票装置に対して再暗号化に使用する乱数およびランダム置換を指定する。
また、各開票装置が再暗号化とランダム置換を指定した通りに実行したことを、任意の第三者が検証できるための情報もあらかじめ送信しておく。
また、開票装置が再暗号化とランダム置換を指定した通りに実行しなかった場合に、複数台の開票装置が協力して再暗号化とランダム置換を行なえるように、再暗号化に使用する乱数およびランダム置換を閾値復号法を用いて復号できるように送信しておく。
【発明の効果】
【００２０】
本発明の電子投票システムの計算量の評価を行ない、従来の電子投票システムの計算量と比較する。
ただし、準同型性を持つ確率的公開鍵暗号系として変形ＥｌＧａｍａｌ暗号の使用を想定し、計算量はべき乗計算の回数のオーダーで見積もる。
単票投票形式および分割不可能な複数票投票形式の場合について評価する。
本発明の電子投票システムにおける、投票装置の計算量は各投票者毎にＯ（ｔ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａｔ）であり、投票締切後の開票装置の計算量はＯ（ａｔ）である。
投票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（１）であり、本発明の方が多い。
準同型性に基づいた電子投票システムではＯ（ａ）であり、
一般に選択肢の数ａは不正を行なう開票装置の台数ｔより大きいので、本発明の方が少ない。
投票締切後の開票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（ｎｔ）であり、
一般に総票数ｎは選択肢の数ａより遥かに大きいので、本発明の方が非常に少ない。
準同型性に基づいた電子投票システムではＯ（ｔ）であり、本発明の方が多い。
分割可能な複数票投票形式の場合について評価する。
本発明の電子投票システムにおける、投票装置の計算量は各投票者毎にＯ（ｔ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（（ａの２乗 ｌｏｇ ｎｊ）ｔ）であり、投票締切後の開票装置の計算量はＯ（ａｔ）である。
投票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（ｎｊ）であり、
準同型性に基づいた電子投票システムではＯ（ａ ｌｏｇ ｎｊ）である。
一般に選択肢の数ａおよび各投票者の持ち票数ｎｊは不正を行なう開票装置の台数ｔより大きいので、本発明の方が少ない。
投票締切後の開票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（ｎｔ）であり、
一般に総票数ｎは選択肢の数ａより遥かに大きいので、本発明の方が非常に少ない。
準同型性に基づいた電子投票システムではＯ（ａｔ）であり、本発明と同じである。
したがって、本発明により、投票締切後の開票装置の負担を従来の準同型性に基づいた電子投票システムと同程度に抑えたまま、投票装置の負担を少なくできる公開検証可能な電子投票システムを実現できる。
【発明を実施するための最良の形態】
【００２１】
本発明の構成について図面を参照しながら説明する。
図１は、本発明の電子投票システムの一構成例を示した図である。
図１において、本発明の電子投票システムは、投票装置１と複数台の開票装置２から構成される。
投票装置１の代わりに、投票装置Ｖと記述する場合がある。
複数台の開票装置２の代わりに、ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）と記述する場合がある。
投票装置１は、投票内容入力手段３と組立暗号文作成指示暗号文作成手段４から構成される。
複数台の開票装置２は、初期暗号文作成手段５と組立暗号文作成手段６と組立暗号文集計手段７と集計暗号文記憶手段８と復号手段９から構成される。
【００２２】
本発明の動作について図面を参照しながら説明する。
まず最初に、単票投票形式の場合について説明する。
投票形式によって本発明の動作が異なる部分は、投票内容入力手段３と初期暗号文作成手段５の部分である。
【００２３】
まず最初に、本発明の動作の実行以前の状態を説明する。
ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）が秘密鍵ＳＫを（ｔ＋１，ｓ）−閾値法を用いて分散共有している確率的公開鍵暗号系の公開鍵をＰＫ、乱数空間をＲとする。
ただし、ｓ≧２ｔ＋１を満たすものとする。
１≦ｉ≦ｔ＋１に対して、開票装置Ｓｉが秘密鍵ＳＫ［ｉ］を所有している確率的公開鍵暗号系の公開鍵をＰＫ［ｉ］、乱数空間をＲ［ｉ］とする。
投票装置Ｖが、選択肢の数ａと投票者Ｖｊの持ち票数ｎｊとＰＫとＲとＰＫ［ｉ］とＲ［ｉ］（１≦ｉ≦ｔ＋１）を所有している。
ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）が、選択肢の数ａと投票者Ｖｊの持ち票数ｎｊを所有している。
集計暗号文記憶手段８に、集計暗号文ｅｋ←ＥａｓｙｍＰＫ（０）（１≦ｋ≦ａ）が記憶さている。
投票者Ｖｊが、識別子ｊと選択肢の数ａを所有している。
投票者Ｖｊは、選択したａｊ番目の選択肢に一票を投票するものとする。
ただし、１≦ａｊ≦ａを満たすものとする。
投票者Ｖｊが、投票内容入力手段３へ識別子ｊと投票内容（選択肢の番号ａｊ）を入力する。
【００２４】
次に、本発明の動作の概要を説明する。
投票内容入力手段３と組立暗号文作成指示暗号文作成手段４と初期暗号文作成手段５と組立暗号文作成手段６については、後で詳細を説明する。
組立暗号文集計手段７と集計暗号文記憶手段８と復号手段９については、準同型性に基づいた電子投票システムと同様である。
投票内容入力手段３が、識別子ｊと選択肢の番号ａｊを入力として、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
組立暗号文作成指示暗号文作成手段４が、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を入力として、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を出力する。
投票装置１が、複数台の開票装置２へ識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を送信する。
複数台の開票装置２が、投票装置１から識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を受信する。
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
組立暗号文作成手段６が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を入力として、組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を出力する。ただし、組立暗号文ｅ（ｊ，ｋ）は、投票者Ｖｊの選択肢Ａｋに対する投票数の暗号文になっている。
組立暗号文集計手段７が、組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を入力として、集計暗号文記憶手段８から集計暗号文ｅｋ（１≦ｋ≦ａ）を読み出して、ｅｋ←ｅｋｅ（ｊ，ｋ）（１≦ｋ≦ａ）を計算することで組立暗号文ｅ（ｊ，ｋ）を準同型性を用いて集計暗号文ｅｋにまとめて、集計暗号文記憶手段８へ集計暗号文ｅｋ（１≦ｋ≦ａ）を書き込む。ただし、集計暗号文ｅｋは、選択肢Ａｋの得票数の暗号文になっている。
上記の組立暗号文集計手段７の動作までは、投票者が投票を行なう度に実行される。
下記の復号手段９の動作は、投票締切後に実行される。
復号手段９が、集計暗号文記憶手段８から集計暗号文ｅｋ（１≦ｋ≦ａ）を読み出して、集計暗号文ｅｋ（１≦ｋ≦ａ）を閾値復号法を用いて復号して集計平文ｐｋを生成して、集計平文ｐｋ（１≦ｋ≦ａ）を出力する。ただし、集計平文ｐｋは、選択肢Ａｋの得票数になっている。
【００２５】
最後に、本発明の動作の詳細を説明する。
投票内容入力手段３が、識別子ｊと選択肢の番号ａｊを入力として、下記の手順によりリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を生成して、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＮ（０，ｚ）←１、ｚ≠１ならばＮ（０，ｚ）←０とする。
ｘ個の要素からなるリストＬＮｔ＋１＝（Ｎ（ｔ＋１，１），．．．，Ｎ（ｔ＋１，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝ａｊならばＮ（ｔ＋１，ｚ）←１、ｚ≠ａｊならばＮ（ｔ＋１，ｚ）←０とする。
ｘ個の要素からなるリストＬＲ０＝（Ｒ（０，１），．．．，Ｒ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｒ（０，ｚ）←０とする。
【００２６】
組立暗号文作成指示暗号文作成手段４が、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を入力として、下記の手順により組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を出力する。
図２は、組立暗号文作成指示暗号文作成手段４による組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）の生成の流れを示した図である。
ただし、組立暗号文作成指示暗号文作成手段４には、乱数生成部があるものとする。
（ステップ１）
ｉ←１とする。
（ステップ２）
ｉ≠ｔ＋１ならば、乱数生成部でリストの置換πｉ∈Πｘをランダムに生成する。
ｉ＝ｔ＋１ならば、リストの置換πｔ＋１∈ΠｘをＬＮｔ＋１＝πｔ＋１・・・π１ＬＮ０を満たすように生成する。
（ステップ３）
乱数生成部でｘ個の要素からなるリストＬＲ’ｉ＝（Ｒ’（ｉ，１），．．．，Ｒ’（ｉ，ｘ））∈Ｒｘをランダムに生成する。
（ステップ４）
乱数生成部で共通鍵Ｋ［ｉ］∈Ｋｓｙｍをランダムに生成する。
（ステップ５）
組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，３）を下記の通り生成する。
ｅ（ｊ，ｉ，１）←ＥａｓｙｍＰＫ（Ｋ［ｉ］）
ｅ（ｊ，ｉ，２）←ＥａｓｙｍＰＫ［ｉ］（Ｋ［ｉ］）
ｅ（ｊ，ｉ，３）←ＥｓｙｍＫ［ｉ］（πｉ||ＬＲ’ｉ）
（ステップ６）
ＬＮｉ←πｉＬＮｉ−１とする。
ただし、ＬＮｉ＝（Ｎ（ｉ，１），．．．，Ｎ（ｉ，ｘ））とする。
（ステップ７）
ＬＲｉ←πｉ（Ｒ（ｉ−１，１）＋Ｒ’（ｉ，１），．．．，Ｒ（ｉ−１，ｘ）＋Ｒ’（ｉ，ｘ））とする。
ただし、ＬＲｉ＝（Ｒ（ｉ，１），．．．，Ｒ（ｉ，ｘ））とする。
（ステップ８）
乱数生成部でｘ個の要素からなるリストＬＲ”ｉ＝（Ｒ”（ｉ，１），．．．，Ｒ”（ｉ，ｘ））∈Ｚ｜Ｒ｜ｘをランダムに生成する。
ただし、Ｚ｜Ｒ｜は集合｛０，１，．．．，｜Ｒ｜−１｝である。
（ステップ９）
乱数生成部で共通鍵Ｋ’［ｉ］∈Ｋｓｙｍをランダムに生成する。
（ステップ１０）
組立暗号文作成指示暗号文ｅ（ｊ，ｉ，４），．．．，ｅ（ｊ，ｉ，６）を下記の通り生成する。
ｅ（ｊ，ｉ，４）←ＥａｓｙｍＰＫ（Ｋ’［ｉ］）
ｅ（ｊ，ｉ，５）←ＥｓｙｍＫ’［ｉ］（ＬＲ”ｉ）
ｅ（ｊ，ｉ，６）←ＥａｓｙｍＰＫ（Σ１≦ｚ≦ｘＮ（ｉ，ｚ）Ｒ”（ｉ，ｚ），Σ１≦ｚ≦ｘＲ（ｉ，ｚ）Ｒ”（ｉ，ｚ））
（ステップ１１）
ｉ≠ｔ＋１ならば、ｉ←ｉ＋１として、ステップ２へ戻る。
【００２７】
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、下記の手順によりリスト長ｘと初期暗号文リストＬＥ０を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＥ０＝（Ｅ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＥ（０，ｚ）←ＥａｓｙｍＰＫ（１，０）、ｚ≠１ならばＮ（０，ｚ）←ＥａｓｙｍＰＫ（０，０）とする。
【００２８】
組立暗号文作成手段６が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を入力として、下記の手順により組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を生成して、組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を出力する。ただし、組立暗号文ｅ（ｊ，ｋ）は、投票者Ｖｊの選択肢Ａｋに対する投票数の暗号文になっている。
図３は、組立暗号文作成手段６による組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）の生成の流れを示した図である。
ただし、組立暗号文作成手段６のうちステップ２とステップ３とステップ４と閾値復号法以外の手順では、ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）のうち任意の一台の開票装置が、手順を実行して他の開票装置に実行結果を通知するものとする。
（ステップ１）
ｉ←１とする。
ｙ←ｘ／ａとする。
（ステップ２）
開票装置Ｓｉが、下記の手順によりπｉとＬＲ’ｉを生成する。
ただし、開票装置Ｓｉは、他の開票装置にπｉとＬＲ’ｉを通知しない。
Ｋ［ｉ］←ＤａｓｙｍＰＫ［ｉ］（ｅ（ｊ，ｉ，２））
πｉ||ＬＲ’ｉ←ＤｓｙｍＫ［ｉ］（ｅ（ｊ，ｉ，３））
（ステップ３）
開票装置Ｓｉが、下記の手順によりＬＥｉを生成する。
ただし、開票装置Ｓｉは、他の開票装置にＬＥｉを通知する。
ＬＥｉ←πｉ（Ｅ（ｉ−１，１）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，１）），．．．，Ｅ（ｉ−１，ｘ）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，ｘ）））
ただし、ＬＥｉ＝（Ｅ（ｉ，１），．．．，Ｅ（ｉ，ｘ））とする。
（ステップ４）
開票装置Ｓｉが、ステップ３におけるリストＬＥｉ−１に対する再暗号化とランダム置換の処理の正当性をゼロ知識証明で示す。
ゼロ知識証明がｒｅｊｅｃｔされたならば、ステップ７へ進む。
（ステップ５）
Ｋ’［ｉ］←ｓ台の開票装置が協力してｅ（ｊ，ｉ，４）を閾値復号法を用いて復号する。
ＬＲ”ｉ←ＤｓｙｍＫ’［ｉ］（ｅ（ｊ，ｉ，５））とする。
（ステップ６）
次式を満たすならば、ステップ９へ進む
Π１≦ｚ≦ｘ（Ｅ（ｉ，ｚ）のＲ”（ｉ，ｚ）乗）＝ ｅ（ｊ，ｉ，６）
（ステップ７）
Ｋ［ｉ］←ｓ台の開票装置が協力してｅ（ｊ，ｉ，１）を閾値復号法を用いて復号する。
πｉ||ＬＲ’ｉ←ＤｓｙｍＫ［ｉ］ｅ（ｊ，ｉ，３）とする。
（ステップ８）
ＬＥｉ←πｉ（Ｅ（ｉ−１，１）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，１）），．．．，Ｅ（ｉ−１，ｘ）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，ｘ）））とする。
（ステップ９）
ｉ≠ｔ＋１ならば、ｉ←ｉ＋１として、ステップ２へ戻る。
（ステップ１０）
１≦ｋ≦ａに対して、ｅ（ｊ，ｋ）←Π（ｋ−１）ｙ＋１≦ｚ≦ｋｙＥ（ｔ＋１，ｚ）とする。
【実施例１】
【００２９】
次に、分割不可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投票内容入力手段３と初期暗号文作成手段５を下記のように置き換えれば、本発明の電子投票システムで、分割不可能な複数票投票形式も実現できる。
投票者Ｖｊが、識別子ｊと選択肢の数ａと持ち票数ｎｊを所有している。
投票者Ｖｊは、選択したａｊ番目の選択肢にｎｊ票を投票するものとする。
ただし、１≦ａｊ≦ａを満たすものとする。
投票者Ｖｊが、投票内容入力手段３へ識別子ｊと投票内容（選択肢の番号ａｊ）を入力する。
【００３０】
投票内容入力手段３が、識別子ｊと選択肢の番号ａｊを入力として、下記の手順によりリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を生成して、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＮ（０，ｚ）←ｎｊ、ｚ≠１ならばＮ（０，ｚ）←０とする。
ｘ個の要素からなるリストＬＮｔ＋１＝（Ｎ（ｔ＋１，１），．．．，Ｎ（ｔ＋１，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝ａｊならばＮ（ｔ＋１，ｚ）←ｎｊ、ｚ≠ａｊならばＮ（ｔ＋１，ｚ）←０とする。
ｘ個の要素からなるリストＬＲ０＝（Ｒ（０，１），．．．，Ｒ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｒ（０，ｚ）←０とする。
【００３１】
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、下記の手順によりリスト長ｘと初期暗号文リストＬＥ０を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＥ０＝（Ｅ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＥ（０，ｚ）←ＥａｓｙｍＰＫ（ｎｊ，０）、ｚ≠１ならばＮ（０，ｚ）←ＥａｓｙｍＰＫ（０，０）とする。
【実施例２】
【００３２】
次に、分割可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投票内容入力手段３と初期暗号文作成手段５を下記のように置き換えれば、本発明の電子投票システムで、分割可能な複数票投票形式も実現できる。
投票者Ｖｊが、識別子ｊと選択肢の数ａと持ち票数ｎｊを所有している。
投票者Ｖｊは、複数の選択肢にｎｊ票を０≦ｎ（ｊ，ｋ）≦ｎｊ、Σｋｎ（ｊ，ｋ）＝ｎｊを満たすようにｎ（ｊ，１）票，．．．，ｎ（ｊ，ａ）票に分割して投票するものとする。
投票者Ｖｊが、投票内容入力手段３へ識別子ｊと投票内容（投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）（１≦ｋ≦ａ））を入力する。
【００３３】
投票内容入力手段３が、識別子ｊと投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）（１≦ｋ≦ａ）を入力として、下記の手順によりリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を生成して、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
Ｘ←（ａ，ｎｊ）−ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔとする。
ｘ←ａ＃Ｘとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。Ｘの要素を昇順に並べたリストに、ｘ−＃Ｘ個の要素からなるリスト（０，．．．，０）を結合したリストを、ＬＮ０とする。
ｘ個の要素からなるリストＬＮｔ＋１＝（Ｎ（ｔ＋１，１），．．．，Ｎ（ｔ＋１，ｘ））を下記の通り生成する。
非負の整数の組（ｎ（ｊ，１），．．．，ｎ（ｊ，ａ））に対して、∪１≦ｋ≦ａＸ［ｋ］＝Ｘかつ全てのｋ（１≦ｋ≦ａ）に対してΣＮ∈Ｘ［ｋ］Ｎ＝ｎ（ｊ，ｋ）を満たす自然数の多重集合Ｘ［１］，．．．，Ｘ［ａ］⊆Ｘを生成する。
＃Ｘ個の要素からなるリストＬＮ（ｔ＋１，ｋ）（１≦ｋ≦ａ）を、Ｘ［ｋ］の要素を並べたリストと＃Ｘ−＃Ｘ［ｋ］個の要素からなるリスト（０，．．．，０）を結合したリストとする。
リストＬＮｔ＋１を、ＬＮ（ｔ＋１，１），．．．，ＬＮ（ｔ＋１，ａ）の結合とする。
ｘ個の要素からなるリストＬＲ０＝（Ｒ（０，１），．．．，Ｒ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｒ（０，ｚ）←０とする。
【００３４】
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、下記の手順によりリスト長ｘと初期暗号文リストＬＥ０を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
Ｘ←（ａ，ｎｊ）−ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔとする。
ｘ←ａ＃Ｘとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。Ｘの要素を昇順に並べたリストに、ｘ−＃Ｘ個の要素からなるリスト（０，．．．，０）を結合したリストを、ＬＮ０とする。
ｘ個の要素からなるリストＬＥ０＝（Ｅ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｅ（０，ｚ）←ＥａｓｙｍＰＫ（Ｎ（０，ｚ），０）とする。
【００３５】
例えば、選択肢の数ａ＝３，持ち票数ｎｊ＝１０の場合、（３，１０）−ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔは、Ｘ＝｛１，１，２，２，４｝である。
これより、ｘ＝１５となる。
Ｖｊが３通りの選択肢にそれぞれ３，５，２票ずつ投票するとき、Ｘ［１］＝｛１，２｝，Ｘ［２］＝｛１，４｝，Ｘ［３］＝｛２｝となる。
したがって、ＬＮ０＝（１，１，２，２，４，０，０，０，０，０，０，０，０，０，０），
ＬＮｔ＋１＝（１，２，０，０，０，１，４，０，０，０，２，０，０，０，０）である。
【実施例３】
【００３６】
組立暗号文作成手段６のうちステップ２以外の実行結果を公開掲示板に書き込む等して公開すれば、本発明の電子投票システムは公開検証可能となる。
また、ＭＩＸ−ｎｅｔに基づいた電子投票システムでは、他の投票者が投票して送信された暗号文を参考に、
他の投票者の投票内容と関係のある投票内容の暗号文を作成して投票するという、不正を防止しなければならない。
提案方式についても同様の不正が考えられるが、使用する暗号系にｎｏｎ−ｍａｌｌｅａｂｌｅな性質を持たせることなどで、不正を防止できる。
本発明では特に、再暗号化とランダム置換の検証のための情報であるリストＬＲ”ｉの暗号化の際に、ｎｏｎ−ｍａｌｌｅａｂｌｅな性質を持つ共通鍵暗号系を使用することで、効率的に不正を防止できると考えられる。
【実施例４】
【００３７】
（ＰＲＧ，ＳＰ，ＳＥＥＤＳＰ）を擬似乱数生成系とする。
ＰＲＧは、空間ＳＰとシードＳＥＥＤ∈ＳＥＥＤＳＰを入力とし、空間ＳＰの擬似乱数を出力する擬似乱数生成アルゴリズムである。
組立暗号文作成指示暗号文作成手段４で、乱数生成部でＬＲ’ｉ，ＬＲ”ｉを生成する代わりに、乱数生成部でＳＥＥＤ’ｉ∈ＳＥＥＤＳＰ，ＳＥＥＤ”ｉ∈ＳＥＥＤＳＰを生成して、ＬＲ’ｉ←ＰＲＧ（Ｒｘ，ＳＥＥＤ’ｉ），ＬＲ”ｉ←ＰＲＧ（Ｚ｜Ｒ｜ｘ，ＳＥＥＤ”ｉ）とする。
そして、ＬＲ’ｉ，ＬＲ”ｉを暗号化して送信する代わりに、ＳＥＥＤ’ｉ，ＳＥＥＤ”ｉを暗号化して送信すれば、通信量を削減できる。
組立暗号文作成手段６で、ＳＥＥＤ’ｉ，ＳＥＥＤ”ｉを復号して、ＬＲ’ｉ←ＰＲＧ（Ｒｘ，ＳＥＥＤ’ｉ），ＬＲ”ｉ←ＰＲＧ（Ｚ｜Ｒ｜ｘ，ＳＥＥＤ”ｉ）とする。
【図面の簡単な説明】
【００３８】
【図１】本発明の電子投票システムの一構成例を示した図である。
【図２】組立暗号文作成指示暗号文作成手段４による組立暗号文作成指示暗号文の生成の流れを示した図である。
【図３】組立暗号文作成手段６による組立暗号文の生成の流れを示した図である。
【符号の説明】
【００３９】
１ 投票装置
２ 複数台の開票装置
３ 投票内容入力手段
４ 組立暗号文作成指示暗号文作成手段
５ 初期暗号文作成手段
６ 組立暗号文作成手段
７ 組立暗号文集計手段
８ 集計暗号文記憶手段
９ 復号手段
【技術分野】
【０００１】
本発明は、暗号技術のうち電子投票システムに関する発明である。
一般に、電子投票システムは、ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）と投票装置Ｖによって構成される。
不正を行なう開票装置の台数をｔ以下として、ｓ≧２ｔ＋１を満たすものとする。
ｖ人の投票者Ｖｊ（１≦ｊ≦ｖ）が、投票装置Ｖへ下記の投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）を入力する。
【０００２】
投票者が選択できる選択肢をａ通りの選択肢Ａｋ（１≦ｋ≦ａ）とする。
投票者Ｖｊの持ち票数をｎｊとする。
投票者Ｖｊの選択肢Ａｋに対する投票数をｎ（ｊ，ｋ）とする。
ただし、０≦ｎ（ｊ，ｋ）≦ｎｊ、Σｋｎ（ｊ，ｋ）＝ｎｊを満たすものとする。
【０００３】
投票には、持ち票数と持ち票数の分割の仕方に応じて、様々な投票形式がある。
例えば、単票投票形式、分割不可能な複数票投票形式、分割可能な複数票投票形式がある。
単票投票形式とは、各投票者の持ち票が一票である投票形式である。
すなわち、投票者Ｖｊは、選択したａｊ番目の選択肢に一票を投票する。
すると、ｋ＝ａｊに対してｎ（ｊ，ｋ）＝１、ｋ≠ａｊに対してｎ（ｊ，ｋ）＝０が成り立つ。
分割不可能な複数票投票形式とは、各投票者の持ち票が複数票であり、一つの選択肢に持ち票をすべて投票する投票形式である。
すなわち、投票者Ｖｊは、選択したａｊ番目の選択肢に持ち票をすべて投票する。
すると、ｋ＝ａｊに対してｎ（ｊ，ｋ）＝ｎｊ、ｋ≠ａｊに対してｎ（ｊ，ｋ）＝０が成り立つ。
分割可能な複数票投票形式とは、各投票者の持ち票が複数票であり、複数の選択肢に持ち票を分割して投票できる投票形式である。
すなわち、投票者Ｖｊは、複数の選択肢にｎｊ票を０≦ｎ（ｊ，ｋ）≦ｎｊ、Σｋｎ（ｊ，ｋ）＝ｎｊを満たすようにｎ（ｊ，１）票，．．．，ｎ（ｊ，ａ）票に分割して投票できる。
【０００４】
投票締切後に、ｓ台の開票装置が協力して、すべての選択肢Ａｋに対して得票数Σｊｎ（ｊ，ｋ）を求める。
【背景技術】
【０００５】
従来の電子投票システムには、ＭＩＸ−ｎｅｔに基づいた電子投票システムと準同型性に基づいた電子投票システムが知られている。
準同型性とＭＩＸ−ｎｅｔと記号の定義について説明した後に、従来の電子投票システムについて説明する。
【０００６】
準同型性について説明する。
（Ｇａｓｙｍ，Ｅａｓｙｍ，Ｄａｓｙｍ，ＰＫａｓｙｍ，ＳＫａｓｙｍ，Ｍａｓｙｍ，Ｒａｓｙｍ，Ｃａｓｙｍ）を確率的公開鍵暗号系とする。
Ｇａｓｙｍは、セキュリティパラメータを入力とし、公開鍵ＰＫ∈ＰＫａｓｙｍと秘密鍵ＳＫ∈ＳＫａｓｙｍを出力する鍵生成アルゴリズムである。
Ｅａｓｙｍは、平文ｍ∈Ｍａｓｙｍと乱数ｒ∈Ｒａｓｙｍを入力とし、公開鍵ＰＫを用いて暗号文ｃ＝ＥａｓｙｍＰＫ（ｍ，ｒ）を出力する暗号化アルゴリズムである。
Ｄａｓｙｍは、暗号文ｃ∈Ｃａｓｙｍを入力とし、秘密鍵ＳＫを用いて平文ｍ＝ＤａｓｙｍＳＫ（ｃ）を出力する復号アルゴリズムである。
簡単のため、乱数ｒが重要でない場合は、確率的公開鍵暗号系の暗号化アルゴリズムの引数の乱数を省略する。
すなわち、ｃ＝ＥａｓｙｍＰＫ（ｍ，ｒ）の代わりにｃ＝ＥａｓｙｍＰＫ（ｍ）と記述する。
確率的公開鍵暗号系が準同型性を持つとは、任意の平文ｍ１，ｍ２に対して、ＥａｓｙｍＰＫ（ｍ１）×ＥａｓｙｍＰＫ（ｍ２）＝ＥａｓｙｍＰＫ（ｍ１＋ｍ２）が成立することである。
本発明の電子投票システムでは、任意の平文ｍ１，ｍ２と任意の乱数ｒ１，ｒ２に対して、ＥａｓｙｍＰＫ（ｍ１，ｒ１）×ＥａｓｙｍＰＫ（ｍ２，ｒ２）＝ＥａｓｙｍＰＫ（ｍ１＋ｍ２，ｒ１＋ｒ２）が成立する、準同型性を持つ確率的公開鍵暗号系を使用する。
【０００７】
ＭＩＸ−ｎｅｔについて説明する。
準同型性を持つ確率的公開鍵暗号系に基づいたＭＩＸ−ｎｅｔとは、下記の手順からなる匿名通信路である。
ただし、複数台の開票装置によって、秘密鍵が閾値法を用いて分散共有されているものとする。
最初に、複数の暗号文からなるリストが入力される。
次に、閾値台の開票装置が逐次に、リストに含まれる各暗号文を再暗号化ＥａｓｙｍＰＫ（ｍ，ｒ）×ＥａｓｙｍＰＫ（０，ｒ’）＝ＥａｓｙｍＰＫ（ｍ，ｒ＋ｒ’）して、リストに含まれる暗号文の順番をランダム置換して、再暗号化とランダム置換の処理の正当性をゼロ知識証明で示す。
最後に、複数台の開票装置が協力して、リストに含まれる各暗号文を閾値復号法を用いて復号して出力する。
閾値台以上の開票装置が結託しなければ、入力暗号文と出力復号文の対応関係が不明となるため、匿名通信路として機能する。
本発明の電子投票システムでは、複数の暗号文からなるリストに対する再暗号化とランダム置換の処理の正当性をゼロ知識証明で示すことが可能であり、秘密鍵が閾値法を用いて分散共有されることで閾値復号法を用いて復号することが可能である、準同型性を持つ確率的公開鍵暗号系を使用する。（非特許文献１、非特許文献２参照）
上記の条件を満たす準同型性を持つ確率的公開鍵暗号系の例としては、変形ＥｌＧａｍａｌ暗号ＥａｓｙｍＰＫ（ｍ，ｒ）＝（ｇｒ，ｇｍｙｒ）がある。
変形ＥｌＧａｍａｌ暗号の復号アルゴリズムのうち、ＥｌＧａｍａｌ暗号の復号アルゴリズムで復号した値ｇｍから平文ｍを求める部分には、落とし戸が存在しない。
そのため、変形ＥｌＧａｍａｌ暗号の平文空間は、可能な限り狭くする必要がある。
【０００８】
記号の定義について説明する。
ｎを総票数Σｊｎｊとする。
Πｘを｛１，．．．，ｘ｝→｛１，．．．，ｘ｝なる置換関数の集合とする。
||をビット列の結合演算子とする。
（Ｅｓｙｍ，Ｄｓｙｍ，Ｋｓｙｍ，Ｍｓｙｍ，Ｃｓｙｍ）を共通鍵暗号系とする。
Ｅｓｙｍは、平文ｍ∈Ｍｓｙｍを入力とし、共通鍵Ｋ∈Ｋｓｙｍを用いて暗号文ｃ＝ＥｓｙｍＫ（ｍ）を出力する暗号化アルゴリズムである。
Ｄｓｙｍは、暗号文ｃ∈Ｃｓｙｍを入力とし、共通鍵Ｋ∈Ｋｓｙｍを用いて平文ｍ＝ＤｓｙｍＫ（ｃ）を出力する復号アルゴリズムである。
本発明の電子投票システムのうち分割可能な複数票投票形式の場合では、ある特殊な性質を持つ自然数の多重集合ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔ（特許文献１参照）を使用する。
【０００９】
ＭＩＸ−ｎｅｔに基づいた電子投票システムについて説明する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムでは、複数の暗号文からなるリストに対する再暗号化とランダム置換の処理の正当性をゼロ知識証明で示すことが可能であり、秘密鍵が閾値法を用いて分散共有されることで閾値復号法を用いて復号することが可能である、準同型性を持つ確率的公開鍵暗号系を使用する。
また、複数台の開票装置によって、秘密鍵が閾値法を用いて分散共有されているものとする。
【００１０】
まず最初に、単票投票形式の場合について説明する。
単票投票形式の場合の投開票の手順は、下記の通りである。
（ステップ１）
投票装置Ｖが、暗号文ＥａｓｙｍＰＫ（ａｊ）を開票装置へ送信する。
（ステップ２）
投票締切後に、ｓ台の開票装置が協力して、受信した暗号文からなるリストをＭＩＸ−ｎｅｔを用いて復号する。
（ステップ３）
ｓ台の開票装置が協力して、リストに含まれる各復号文がｋ（１≦ｋ≦ａ）のいずれかであることを確認して、集計して得票数を求める。
本システムにおける、投票装置の計算量は各投票者毎にＯ（１）であり、投票締切後の開票装置の計算量はＯ（ｎｔ）である。
【００１１】
次に、分割不可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投開票の手順との差分は、下記の通りである。
（ステップ２）
投票締切前から、ｓ台の開票装置が協力して、受信した暗号文ＥａｓｙｍＰＫ（ａｊ）をｎｊ個にコピーする。
投票締切後に、ｓ台の開票装置が協力して、コピーされた暗号文からなるリストをＭＩＸ−ｎｅｔを用いて復号する。
本システムにおける、投票装置の計算量は各投票者毎にＯ（１）であり、投票締切後の開票装置の計算量はＯ（ｎｔ）である。
【００１２】
最後に、分割可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投開票の手順との差分は、下記の通りである。
（ステップ１）
投票装置Ｖが、すべての選択肢Ａｋに対して、ｎ（ｊ，ｋ）個の暗号文ＥａｓｙｍＰＫ（ｋ）を開票装置へ送信する。
本システムにおける、投票装置の計算量は各投票者毎にＯ（ｎｊ）であり、投票締切後の開票装置の計算量はＯ（ｎｔ）である。
【００１３】
準同型性に基づいた電子投票システムについて説明する。
準同型性に基づいた電子投票システムでは、暗号文が特定の複数の平文のいずれかを暗号化したものであることをゼロ知識証明で示すことが可能であり、秘密鍵を閾値法を用いて分散共有することで閾値復号法を用いて復号することが可能である、準同型性を持つ確率的公開鍵暗号系を使用する。
また、複数台の開票装置によって、秘密鍵が閾値法を用いて分散共有されているものとする。
また、暗号文が特定のｘ個の平文のいずれかを暗号化したものであることを示すゼロ知識証明を１−ｏｕｔ−ｏｆ−ｘＰＭＰ（ＰｌａｉｎｔｅｘｔＭｅｍｂｅｒｓｈｉｐＰｒｏｏｆ）と記述する。
１−ｏｕｔ−ｏｆ−ｘＰＭＰの計算量と通信量は、ｘに比例する。
準同型性に基づいた電子投票システムには、開票装置が各選択肢毎に暗号文を準同型性を用いてまとめるＳｅｐａｒａｔｅ−ｔｙｐｅと、開票装置が全選択肢一緒に暗号文を準同型性を用いてまとめるＣｏｍｂｉｎｅｄ−ｔｙｐｅがある。
Ｓｅｐａｒａｔｅ−ｔｙｐｅでは、平文空間の大きさは総票数なので、変形ＥｌＧａｍａｌ暗号を使用すれば良い。
しかし、Ｃｏｍｂｉｎｅｄ−ｔｙｐｅでは、平文空間の大きさは総票数の選択肢数乗になるので、変形ＥｌＧａｍａｌ暗号を使用すると復号の効率が悪いため、Ｐａｉｌｌｉｅｒ暗号を使用する。
単票投票形式の場合では、Ｓｅｐａｒａｔｅ−ｔｙｐｅとＣｏｍｂｉｎｅｄ−ｔｙｐｅの両方を説明するが、それ以降では、Ｓｅｐａｒａｔｅ−ｔｙｐｅとＣｏｍｂｉｎｅｄ−ｔｙｐｅのうち投票装置の計算量が最少の方を説明する。
【００１４】
まず最初に、単票投票形式の場合について説明する。
単票投票形式の場合うちＳｅｐａｒａｔｅ−ｔｙｐｅの場合の投開票の手順は、下記の通りである。
（ステップ１）
投票装置Ｖが、暗号文ｅ（ｊ，ｋ）＝ＥａｓｙｍＰＫ（ｎ（ｊ，ｋ））（１≦ｋ≦ａ）を開票装置へ送信して、暗号文ｅ（ｊ，ｋ）が０，１のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−２ＰＭＰを用いて開票装置に証明して、暗号文Πｋｅ（ｊ，ｋ）が１を暗号化したものであることをゼロ知識証明で開票装置に示す。
（ステップ２）
投票締切前から、複数台の開票装置が協力して、暗号文ｅ（ｊ，ｋ）を準同型性を用いて集計暗号文ｅｋ＝Πｊｅ（ｊ，ｋ）にまとめる。
（ステップ３）
投票締切後に、複数台の開票装置が協力して、集計暗号文ｅｋを閾値復号法を用いて復号して得票数を求める。
本方式における、投票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切後の開票装置の計算量はＯ（ａｔ）である。
【００１５】
単票投票形式の場合うちＣｏｍｂｉｎｅｄ−ｔｙｐｅの場合の投開票の手順は、下記の通りである。
ただし、Ｎを総票数ｎより大きい自然数とする。
（ステップ１）
投票装置Ｖが、暗号文ｅｊ＝ＥａｓｙｍＰＫ（Ｎの（ａｊ−１）乗）を開票装置へ送信して、暗号文ｅｊがＮの（ｋ−１）乗（１≦ｋ≦ａ）のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−ａＰＭＰを用いて開票装置に証明する。
（ステップ２）
投票締切前から、複数台の開票装置が協力して、暗号文ｅｊを準同型性を用いて集計暗号文ｅ＝Πｊｅｊにまとめる。
（ステップ３）
投票締切後に、複数台の開票装置が協力して、集計暗号文ｅを閾値復号法を用いて復号して、復号文のＮ進数表現から得票数を求める。
復号文のＮ進数表現から得票数を求められるのは、次式が成立するからである。
ｅ＝ΠｊＥａｓｙｍＰＫ（Ｎの（ａｊ−１）乗）
＝ＥａｓｙｍＰＫ（ΣｊＮの（ａｊ−１）乗）
＝ＥａｓｙｍＰＫ（ΣｊΣｋｎ（ｊ，ｋ）Ｎの（ｋ−１）乗）
＝ＥａｓｙｍＰＫ（ΣｋＮの（ｋ−１）乗（Σｊｎ（ｊ，ｋ）））
本方式における、投票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切後の開票装置の計算量はＯ（ｔ）である。
【００１６】
次に、分割不可能な複数票投票形式の場合について説明する。
単票投票形式の場合うちＣｏｍｂｉｎｅｄ−ｔｙｐｅの場合の投開票の手順との差分は、下記の通りである。
（ステップ１）
投票装置Ｖが、暗号文ｅｊ＝ＥａｓｙｍＰＫ（ｎｊＮの（ａｊ−１）乗）を開票装置へ送信して、暗号文ｅｊがｎｊＮの（ｋ−１）乗（１≦ｋ≦ａ）のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−ａＰＭＰを用いて開票装置に証明する。
本方式における、投票装置の計算量は各投票者毎にＯ（ａ）であり、投票締切前のサーバの計算量は各投票者毎にＯ（ａ）であり、投票締切後のサーバの計算量はＯ（ｔ）である。
【００１７】
最後に、分割可能な複数票投票形式の場合について説明する。
分割可能な複数票投票形式の場合うちＳｅｐａｒａｔｅ−ｔｙｐｅの場合の投開票の手順は、下記の通りである。
（ステップ１）
投票装置Ｖが、投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）のＢ進数表現を（ｂ（ｊ，ｋ，Ｂ［ｊ］），．．．，ｂ（ｊ，ｋ，０）），Ｂ［ｊ］＝ｆｌｏｏｒ（ｌｏｇＢｎｊ）とする。
ただし、ｆｌｏｏｒ（ｘ）は実数ｘ以下の最大の整数である。
投票装置Ｖが、暗号文ｅ（ｊ，ｋ，ｚ）＝ＥａｓｙｍＰＫ（ｂ（ｊ，ｋ，ｚ））（１≦ｋ≦ａ，０≦ｚ≦Ｂ［ｊ］）を開票装置へ送信して、暗号文ｅ（ｊ，ｋ，ｚ）がｂ（０≦ｂ≦Ｂ−１）のいずれかを暗号化したものであることを１−ｏｕｔ−ｏｆ−ＢＰＭＰを用いて開票装置に証明して、暗号文ΠｋΠｚｅ（ｊ，ｋ，ｚ）の（Ｂのｚ乗）乗がｎｊを暗号化したものであることをゼロ知識証明で開票装置に示す。
（ステップ２）
投票締切前から、複数台の開票装置が協力して、暗号文ｅ（ｊ，ｋ，ｚ）を準同型性を用いて集計暗号文ｅｋ＝ΠｊΠｚｅ（ｊ，ｋ，ｚ）の（Ｂのｚ乗）乗にまとめる。
（ステップ３）
投票締切後に、複数台の開票装置が協力して、集計暗号文ｅｋを閾値復号法を用いて復号して得票数を求める。
復号文から得票数を求められるのは、次式が成立するからである。
ｅｋ＝ΠｊΠｚＥａｓｙｍＰＫ（ｂ（ｊ，ｋ，ｚ））の（Ｂのｚ乗）乗
＝ＥａｓｙｍＰＫ（ΣｊΣｚｂ（ｊ，ｋ，ｚ）Ｂのｚ乗）
＝ＥａｓｙｍＰＫ（Σｊｎ（ｊ，ｋ））
本方式における、投票装置の計算量は各投票者毎にＯ（ａ ｌｏｇ ｎｊ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａ ｌｏｇ ｎｊ）であり、投票締切後のサーバの計算量はＯ（ａｔ）である。
ちなみに、Ｂの値が３または４の時に、効率が良いことが知られている。
【非特許文献１】Ｊ．Ｇｒｏｔｈ、「Ａ Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈｕｆｆｌｅ ｏｆ Ｈｏｍｏｍｏｒｐｈｉｃ Ｅｎｃｒｙｐｔｉｏｎｓ」ＰＫＣ２００３、２００３年、ｐ．１４５−１６０
【非特許文献２】Ｍ．Ａｂｅ、「Ｕｎｉｖｅｒｓａｌｌｙ Ｖｅｒｉｆｉａｂｌｅ Ｍｉｘ−ｎｅｔ ｗｉｔｈ Ｖｅｒｉｆｉｃａｔｉｏｎ Ｗｏｒｋ Ｉｎｄｅｐｅｎｄｅｎｔ ｏｆ ｔｈｅ Ｎｕｍｂｅｒ ｏｆ Ｍｉｘ−ｓｅｒｖｅｒｓ」ＥＵＲＯＣＲＹＰＴ’９８、１９９８年、ｐ．４３７−４４７
【特許文献１】特願２００３−０７９９０４
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従来のＭＩＸ−ｎｅｔに基づいた電子投票システムでは、投票装置の負担は軽いが、投票締切後に全投票者の投票を一度に集計する必要があるため、開票装置の負担が大きいという問題点がある。
従来の準同型性に基づいた電子投票システムでは、開票装置の負担は軽いが、投票の際にゼロ知識証明をする必要があるため、投票装置の負担が大きいという問題点がある。
本発明は、投票締切後の開票装置の負担を従来の準同型性に基づいた電子投票システムと同程度に抑えたまま、投票装置の負担を少なくできる公開検証可能な電子投票システムを実現し、上記の問題点を解決することを目的とする。
【課題を解決するための手段】
【００１９】
準同型性に基づいた電子投票システムのうち単票投票形式のＳｅｐａｒａｔｅ−ｔｙｐｅの場合では、ステップ１において投票装置はａ個の暗号文の作成およびａ回の１−ｏｕｔ−ｏｆ−２ＰＭＰの実行をしなければならず、選択肢の数ａが大きい場合には効率的でない。
そこで、本発明では、暗号化されるａ個の平文リストは（１，０，．．．，０）の置換であることに注目し、ａ個の暗号文の作成を開票装置に任せることで、投票装置の計算量を削減する。
ａ個の暗号文の作成は、投票内容の秘匿のためにＭＩＸ−ｎｅｔと同様に、閾値台の開票装置が逐次に再暗号化とランダム置換を繰り返して行なう。
投票装置は、投票内容がＭＩＸ−ｎｅｔから出力されるように、各開票装置に対して再暗号化に使用する乱数およびランダム置換を指定する。
また、各開票装置が再暗号化とランダム置換を指定した通りに実行したことを、任意の第三者が検証できるための情報もあらかじめ送信しておく。
また、開票装置が再暗号化とランダム置換を指定した通りに実行しなかった場合に、複数台の開票装置が協力して再暗号化とランダム置換を行なえるように、再暗号化に使用する乱数およびランダム置換を閾値復号法を用いて復号できるように送信しておく。
【発明の効果】
【００２０】
本発明の電子投票システムの計算量の評価を行ない、従来の電子投票システムの計算量と比較する。
ただし、準同型性を持つ確率的公開鍵暗号系として変形ＥｌＧａｍａｌ暗号の使用を想定し、計算量はべき乗計算の回数のオーダーで見積もる。
単票投票形式および分割不可能な複数票投票形式の場合について評価する。
本発明の電子投票システムにおける、投票装置の計算量は各投票者毎にＯ（ｔ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（ａｔ）であり、投票締切後の開票装置の計算量はＯ（ａｔ）である。
投票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（１）であり、本発明の方が多い。
準同型性に基づいた電子投票システムではＯ（ａ）であり、
一般に選択肢の数ａは不正を行なう開票装置の台数ｔより大きいので、本発明の方が少ない。
投票締切後の開票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（ｎｔ）であり、
一般に総票数ｎは選択肢の数ａより遥かに大きいので、本発明の方が非常に少ない。
準同型性に基づいた電子投票システムではＯ（ｔ）であり、本発明の方が多い。
分割可能な複数票投票形式の場合について評価する。
本発明の電子投票システムにおける、投票装置の計算量は各投票者毎にＯ（ｔ）であり、投票締切前の開票装置の計算量は各投票者毎にＯ（（ａの２乗 ｌｏｇ ｎｊ）ｔ）であり、投票締切後の開票装置の計算量はＯ（ａｔ）である。
投票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（ｎｊ）であり、
準同型性に基づいた電子投票システムではＯ（ａ ｌｏｇ ｎｊ）である。
一般に選択肢の数ａおよび各投票者の持ち票数ｎｊは不正を行なう開票装置の台数ｔより大きいので、本発明の方が少ない。
投票締切後の開票装置の計算量について比較する。
ＭＩＸ−ｎｅｔに基づいた電子投票システムではＯ（ｎｔ）であり、
一般に総票数ｎは選択肢の数ａより遥かに大きいので、本発明の方が非常に少ない。
準同型性に基づいた電子投票システムではＯ（ａｔ）であり、本発明と同じである。
したがって、本発明により、投票締切後の開票装置の負担を従来の準同型性に基づいた電子投票システムと同程度に抑えたまま、投票装置の負担を少なくできる公開検証可能な電子投票システムを実現できる。
【発明を実施するための最良の形態】
【００２１】
本発明の構成について図面を参照しながら説明する。
図１は、本発明の電子投票システムの一構成例を示した図である。
図１において、本発明の電子投票システムは、投票装置１と複数台の開票装置２から構成される。
投票装置１の代わりに、投票装置Ｖと記述する場合がある。
複数台の開票装置２の代わりに、ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）と記述する場合がある。
投票装置１は、投票内容入力手段３と組立暗号文作成指示暗号文作成手段４から構成される。
複数台の開票装置２は、初期暗号文作成手段５と組立暗号文作成手段６と組立暗号文集計手段７と集計暗号文記憶手段８と復号手段９から構成される。
【００２２】
本発明の動作について図面を参照しながら説明する。
まず最初に、単票投票形式の場合について説明する。
投票形式によって本発明の動作が異なる部分は、投票内容入力手段３と初期暗号文作成手段５の部分である。
【００２３】
まず最初に、本発明の動作の実行以前の状態を説明する。
ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）が秘密鍵ＳＫを（ｔ＋１，ｓ）−閾値法を用いて分散共有している確率的公開鍵暗号系の公開鍵をＰＫ、乱数空間をＲとする。
ただし、ｓ≧２ｔ＋１を満たすものとする。
１≦ｉ≦ｔ＋１に対して、開票装置Ｓｉが秘密鍵ＳＫ［ｉ］を所有している確率的公開鍵暗号系の公開鍵をＰＫ［ｉ］、乱数空間をＲ［ｉ］とする。
投票装置Ｖが、選択肢の数ａと投票者Ｖｊの持ち票数ｎｊとＰＫとＲとＰＫ［ｉ］とＲ［ｉ］（１≦ｉ≦ｔ＋１）を所有している。
ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）が、選択肢の数ａと投票者Ｖｊの持ち票数ｎｊを所有している。
集計暗号文記憶手段８に、集計暗号文ｅｋ←ＥａｓｙｍＰＫ（０）（１≦ｋ≦ａ）が記憶さている。
投票者Ｖｊが、識別子ｊと選択肢の数ａを所有している。
投票者Ｖｊは、選択したａｊ番目の選択肢に一票を投票するものとする。
ただし、１≦ａｊ≦ａを満たすものとする。
投票者Ｖｊが、投票内容入力手段３へ識別子ｊと投票内容（選択肢の番号ａｊ）を入力する。
【００２４】
次に、本発明の動作の概要を説明する。
投票内容入力手段３と組立暗号文作成指示暗号文作成手段４と初期暗号文作成手段５と組立暗号文作成手段６については、後で詳細を説明する。
組立暗号文集計手段７と集計暗号文記憶手段８と復号手段９については、準同型性に基づいた電子投票システムと同様である。
投票内容入力手段３が、識別子ｊと選択肢の番号ａｊを入力として、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
組立暗号文作成指示暗号文作成手段４が、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を入力として、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を出力する。
投票装置１が、複数台の開票装置２へ識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を送信する。
複数台の開票装置２が、投票装置１から識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を受信する。
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
組立暗号文作成手段６が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を入力として、組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を出力する。ただし、組立暗号文ｅ（ｊ，ｋ）は、投票者Ｖｊの選択肢Ａｋに対する投票数の暗号文になっている。
組立暗号文集計手段７が、組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を入力として、集計暗号文記憶手段８から集計暗号文ｅｋ（１≦ｋ≦ａ）を読み出して、ｅｋ←ｅｋｅ（ｊ，ｋ）（１≦ｋ≦ａ）を計算することで組立暗号文ｅ（ｊ，ｋ）を準同型性を用いて集計暗号文ｅｋにまとめて、集計暗号文記憶手段８へ集計暗号文ｅｋ（１≦ｋ≦ａ）を書き込む。ただし、集計暗号文ｅｋは、選択肢Ａｋの得票数の暗号文になっている。
上記の組立暗号文集計手段７の動作までは、投票者が投票を行なう度に実行される。
下記の復号手段９の動作は、投票締切後に実行される。
復号手段９が、集計暗号文記憶手段８から集計暗号文ｅｋ（１≦ｋ≦ａ）を読み出して、集計暗号文ｅｋ（１≦ｋ≦ａ）を閾値復号法を用いて復号して集計平文ｐｋを生成して、集計平文ｐｋ（１≦ｋ≦ａ）を出力する。ただし、集計平文ｐｋは、選択肢Ａｋの得票数になっている。
【００２５】
最後に、本発明の動作の詳細を説明する。
投票内容入力手段３が、識別子ｊと選択肢の番号ａｊを入力として、下記の手順によりリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を生成して、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＮ（０，ｚ）←１、ｚ≠１ならばＮ（０，ｚ）←０とする。
ｘ個の要素からなるリストＬＮｔ＋１＝（Ｎ（ｔ＋１，１），．．．，Ｎ（ｔ＋１，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝ａｊならばＮ（ｔ＋１，ｚ）←１、ｚ≠ａｊならばＮ（ｔ＋１，ｚ）←０とする。
ｘ個の要素からなるリストＬＲ０＝（Ｒ（０，１），．．．，Ｒ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｒ（０，ｚ）←０とする。
【００２６】
組立暗号文作成指示暗号文作成手段４が、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を入力として、下記の手順により組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を出力する。
図２は、組立暗号文作成指示暗号文作成手段４による組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）の生成の流れを示した図である。
ただし、組立暗号文作成指示暗号文作成手段４には、乱数生成部があるものとする。
（ステップ１）
ｉ←１とする。
（ステップ２）
ｉ≠ｔ＋１ならば、乱数生成部でリストの置換πｉ∈Πｘをランダムに生成する。
ｉ＝ｔ＋１ならば、リストの置換πｔ＋１∈ΠｘをＬＮｔ＋１＝πｔ＋１・・・π１ＬＮ０を満たすように生成する。
（ステップ３）
乱数生成部でｘ個の要素からなるリストＬＲ’ｉ＝（Ｒ’（ｉ，１），．．．，Ｒ’（ｉ，ｘ））∈Ｒｘをランダムに生成する。
（ステップ４）
乱数生成部で共通鍵Ｋ［ｉ］∈Ｋｓｙｍをランダムに生成する。
（ステップ５）
組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，３）を下記の通り生成する。
ｅ（ｊ，ｉ，１）←ＥａｓｙｍＰＫ（Ｋ［ｉ］）
ｅ（ｊ，ｉ，２）←ＥａｓｙｍＰＫ［ｉ］（Ｋ［ｉ］）
ｅ（ｊ，ｉ，３）←ＥｓｙｍＫ［ｉ］（πｉ||ＬＲ’ｉ）
（ステップ６）
ＬＮｉ←πｉＬＮｉ−１とする。
ただし、ＬＮｉ＝（Ｎ（ｉ，１），．．．，Ｎ（ｉ，ｘ））とする。
（ステップ７）
ＬＲｉ←πｉ（Ｒ（ｉ−１，１）＋Ｒ’（ｉ，１），．．．，Ｒ（ｉ−１，ｘ）＋Ｒ’（ｉ，ｘ））とする。
ただし、ＬＲｉ＝（Ｒ（ｉ，１），．．．，Ｒ（ｉ，ｘ））とする。
（ステップ８）
乱数生成部でｘ個の要素からなるリストＬＲ”ｉ＝（Ｒ”（ｉ，１），．．．，Ｒ”（ｉ，ｘ））∈Ｚ｜Ｒ｜ｘをランダムに生成する。
ただし、Ｚ｜Ｒ｜は集合｛０，１，．．．，｜Ｒ｜−１｝である。
（ステップ９）
乱数生成部で共通鍵Ｋ’［ｉ］∈Ｋｓｙｍをランダムに生成する。
（ステップ１０）
組立暗号文作成指示暗号文ｅ（ｊ，ｉ，４），．．．，ｅ（ｊ，ｉ，６）を下記の通り生成する。
ｅ（ｊ，ｉ，４）←ＥａｓｙｍＰＫ（Ｋ’［ｉ］）
ｅ（ｊ，ｉ，５）←ＥｓｙｍＫ’［ｉ］（ＬＲ”ｉ）
ｅ（ｊ，ｉ，６）←ＥａｓｙｍＰＫ（Σ１≦ｚ≦ｘＮ（ｉ，ｚ）Ｒ”（ｉ，ｚ），Σ１≦ｚ≦ｘＲ（ｉ，ｚ）Ｒ”（ｉ，ｚ））
（ステップ１１）
ｉ≠ｔ＋１ならば、ｉ←ｉ＋１として、ステップ２へ戻る。
【００２７】
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、下記の手順によりリスト長ｘと初期暗号文リストＬＥ０を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＥ０＝（Ｅ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＥ（０，ｚ）←ＥａｓｙｍＰＫ（１，０）、ｚ≠１ならばＮ（０，ｚ）←ＥａｓｙｍＰＫ（０，０）とする。
【００２８】
組立暗号文作成手段６が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を入力として、下記の手順により組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を生成して、組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）を出力する。ただし、組立暗号文ｅ（ｊ，ｋ）は、投票者Ｖｊの選択肢Ａｋに対する投票数の暗号文になっている。
図３は、組立暗号文作成手段６による組立暗号文ｅ（ｊ，ｋ）（１≦ｋ≦ａ）の生成の流れを示した図である。
ただし、組立暗号文作成手段６のうちステップ２とステップ３とステップ４と閾値復号法以外の手順では、ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）のうち任意の一台の開票装置が、手順を実行して他の開票装置に実行結果を通知するものとする。
（ステップ１）
ｉ←１とする。
ｙ←ｘ／ａとする。
（ステップ２）
開票装置Ｓｉが、下記の手順によりπｉとＬＲ’ｉを生成する。
ただし、開票装置Ｓｉは、他の開票装置にπｉとＬＲ’ｉを通知しない。
Ｋ［ｉ］←ＤａｓｙｍＰＫ［ｉ］（ｅ（ｊ，ｉ，２））
πｉ||ＬＲ’ｉ←ＤｓｙｍＫ［ｉ］（ｅ（ｊ，ｉ，３））
（ステップ３）
開票装置Ｓｉが、下記の手順によりＬＥｉを生成する。
ただし、開票装置Ｓｉは、他の開票装置にＬＥｉを通知する。
ＬＥｉ←πｉ（Ｅ（ｉ−１，１）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，１）），．．．，Ｅ（ｉ−１，ｘ）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，ｘ）））
ただし、ＬＥｉ＝（Ｅ（ｉ，１），．．．，Ｅ（ｉ，ｘ））とする。
（ステップ４）
開票装置Ｓｉが、ステップ３におけるリストＬＥｉ−１に対する再暗号化とランダム置換の処理の正当性をゼロ知識証明で示す。
ゼロ知識証明がｒｅｊｅｃｔされたならば、ステップ７へ進む。
（ステップ５）
Ｋ’［ｉ］←ｓ台の開票装置が協力してｅ（ｊ，ｉ，４）を閾値復号法を用いて復号する。
ＬＲ”ｉ←ＤｓｙｍＫ’［ｉ］（ｅ（ｊ，ｉ，５））とする。
（ステップ６）
次式を満たすならば、ステップ９へ進む
Π１≦ｚ≦ｘ（Ｅ（ｉ，ｚ）のＲ”（ｉ，ｚ）乗）＝ ｅ（ｊ，ｉ，６）
（ステップ７）
Ｋ［ｉ］←ｓ台の開票装置が協力してｅ（ｊ，ｉ，１）を閾値復号法を用いて復号する。
πｉ||ＬＲ’ｉ←ＤｓｙｍＫ［ｉ］ｅ（ｊ，ｉ，３）とする。
（ステップ８）
ＬＥｉ←πｉ（Ｅ（ｉ−１，１）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，１）），．．．，Ｅ（ｉ−１，ｘ）ＥａｓｙｍＰＫ（０，Ｒ’（ｉ，ｘ）））とする。
（ステップ９）
ｉ≠ｔ＋１ならば、ｉ←ｉ＋１として、ステップ２へ戻る。
（ステップ１０）
１≦ｋ≦ａに対して、ｅ（ｊ，ｋ）←Π（ｋ−１）ｙ＋１≦ｚ≦ｋｙＥ（ｔ＋１，ｚ）とする。
【実施例１】
【００２９】
次に、分割不可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投票内容入力手段３と初期暗号文作成手段５を下記のように置き換えれば、本発明の電子投票システムで、分割不可能な複数票投票形式も実現できる。
投票者Ｖｊが、識別子ｊと選択肢の数ａと持ち票数ｎｊを所有している。
投票者Ｖｊは、選択したａｊ番目の選択肢にｎｊ票を投票するものとする。
ただし、１≦ａｊ≦ａを満たすものとする。
投票者Ｖｊが、投票内容入力手段３へ識別子ｊと投票内容（選択肢の番号ａｊ）を入力する。
【００３０】
投票内容入力手段３が、識別子ｊと選択肢の番号ａｊを入力として、下記の手順によりリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を生成して、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＮ（０，ｚ）←ｎｊ、ｚ≠１ならばＮ（０，ｚ）←０とする。
ｘ個の要素からなるリストＬＮｔ＋１＝（Ｎ（ｔ＋１，１），．．．，Ｎ（ｔ＋１，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝ａｊならばＮ（ｔ＋１，ｚ）←ｎｊ、ｚ≠ａｊならばＮ（ｔ＋１，ｚ）←０とする。
ｘ個の要素からなるリストＬＲ０＝（Ｒ（０，１），．．．，Ｒ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｒ（０，ｚ）←０とする。
【００３１】
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、下記の手順によりリスト長ｘと初期暗号文リストＬＥ０を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
ｘ←ａとする。
ｘ個の要素からなるリストＬＥ０＝（Ｅ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、ｚ＝１ならばＥ（０，ｚ）←ＥａｓｙｍＰＫ（ｎｊ，０）、ｚ≠１ならばＮ（０，ｚ）←ＥａｓｙｍＰＫ（０，０）とする。
【実施例２】
【００３２】
次に、分割可能な複数票投票形式の場合について説明する。
単票投票形式の場合の投票内容入力手段３と初期暗号文作成手段５を下記のように置き換えれば、本発明の電子投票システムで、分割可能な複数票投票形式も実現できる。
投票者Ｖｊが、識別子ｊと選択肢の数ａと持ち票数ｎｊを所有している。
投票者Ｖｊは、複数の選択肢にｎｊ票を０≦ｎ（ｊ，ｋ）≦ｎｊ、Σｋｎ（ｊ，ｋ）＝ｎｊを満たすようにｎ（ｊ，１）票，．．．，ｎ（ｊ，ａ）票に分割して投票するものとする。
投票者Ｖｊが、投票内容入力手段３へ識別子ｊと投票内容（投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）（１≦ｋ≦ａ））を入力する。
【００３３】
投票内容入力手段３が、識別子ｊと投票者Ｖｊの選択肢Ａｋに対する投票数ｎ（ｊ，ｋ）（１≦ｋ≦ａ）を入力として、下記の手順によりリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を生成して、識別子ｊとリスト長ｘと初期平文リストＬＮ０と最終平文リストＬＮｔ＋１と初期乱数リストＬＲ０を出力する。
Ｘ←（ａ，ｎｊ）−ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔとする。
ｘ←ａ＃Ｘとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。Ｘの要素を昇順に並べたリストに、ｘ−＃Ｘ個の要素からなるリスト（０，．．．，０）を結合したリストを、ＬＮ０とする。
ｘ個の要素からなるリストＬＮｔ＋１＝（Ｎ（ｔ＋１，１），．．．，Ｎ（ｔ＋１，ｘ））を下記の通り生成する。
非負の整数の組（ｎ（ｊ，１），．．．，ｎ（ｊ，ａ））に対して、∪１≦ｋ≦ａＸ［ｋ］＝Ｘかつ全てのｋ（１≦ｋ≦ａ）に対してΣＮ∈Ｘ［ｋ］Ｎ＝ｎ（ｊ，ｋ）を満たす自然数の多重集合Ｘ［１］，．．．，Ｘ［ａ］⊆Ｘを生成する。
＃Ｘ個の要素からなるリストＬＮ（ｔ＋１，ｋ）（１≦ｋ≦ａ）を、Ｘ［ｋ］の要素を並べたリストと＃Ｘ−＃Ｘ［ｋ］個の要素からなるリスト（０，．．．，０）を結合したリストとする。
リストＬＮｔ＋１を、ＬＮ（ｔ＋１，１），．．．，ＬＮ（ｔ＋１，ａ）の結合とする。
ｘ個の要素からなるリストＬＲ０＝（Ｒ（０，１），．．．，Ｒ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｒ（０，ｚ）←０とする。
【００３４】
初期暗号文作成手段５が、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）を入力として、下記の手順によりリスト長ｘと初期暗号文リストＬＥ０を生成して、識別子ｊと組立暗号文作成指示暗号文ｅ（ｊ，ｉ，１），．．．，ｅ（ｊ，ｉ，６）（１≦ｉ≦ｔ＋１）とリスト長ｘと初期暗号文リストＬＥ０を出力する。
Ｘ←（ａ，ｎｊ）−ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔとする。
ｘ←ａ＃Ｘとする。
ｘ個の要素からなるリストＬＮ０＝（Ｎ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。Ｘの要素を昇順に並べたリストに、ｘ−＃Ｘ個の要素からなるリスト（０，．．．，０）を結合したリストを、ＬＮ０とする。
ｘ個の要素からなるリストＬＥ０＝（Ｅ（０，１），．．．，Ｎ（０，ｘ））を下記の通り生成する。１≦ｚ≦ｘに対して、Ｅ（０，ｚ）←ＥａｓｙｍＰＫ（Ｎ（０，ｚ），０）とする。
【００３５】
例えば、選択肢の数ａ＝３，持ち票数ｎｊ＝１０の場合、（３，１０）−ＤｉｖｉｓｉｂｌｅＭｕｌｔｉｓｅｔは、Ｘ＝｛１，１，２，２，４｝である。
これより、ｘ＝１５となる。
Ｖｊが３通りの選択肢にそれぞれ３，５，２票ずつ投票するとき、Ｘ［１］＝｛１，２｝，Ｘ［２］＝｛１，４｝，Ｘ［３］＝｛２｝となる。
したがって、ＬＮ０＝（１，１，２，２，４，０，０，０，０，０，０，０，０，０，０），
ＬＮｔ＋１＝（１，２，０，０，０，１，４，０，０，０，２，０，０，０，０）である。
【実施例３】
【００３６】
組立暗号文作成手段６のうちステップ２以外の実行結果を公開掲示板に書き込む等して公開すれば、本発明の電子投票システムは公開検証可能となる。
また、ＭＩＸ−ｎｅｔに基づいた電子投票システムでは、他の投票者が投票して送信された暗号文を参考に、
他の投票者の投票内容と関係のある投票内容の暗号文を作成して投票するという、不正を防止しなければならない。
提案方式についても同様の不正が考えられるが、使用する暗号系にｎｏｎ−ｍａｌｌｅａｂｌｅな性質を持たせることなどで、不正を防止できる。
本発明では特に、再暗号化とランダム置換の検証のための情報であるリストＬＲ”ｉの暗号化の際に、ｎｏｎ−ｍａｌｌｅａｂｌｅな性質を持つ共通鍵暗号系を使用することで、効率的に不正を防止できると考えられる。
【実施例４】
【００３７】
（ＰＲＧ，ＳＰ，ＳＥＥＤＳＰ）を擬似乱数生成系とする。
ＰＲＧは、空間ＳＰとシードＳＥＥＤ∈ＳＥＥＤＳＰを入力とし、空間ＳＰの擬似乱数を出力する擬似乱数生成アルゴリズムである。
組立暗号文作成指示暗号文作成手段４で、乱数生成部でＬＲ’ｉ，ＬＲ”ｉを生成する代わりに、乱数生成部でＳＥＥＤ’ｉ∈ＳＥＥＤＳＰ，ＳＥＥＤ”ｉ∈ＳＥＥＤＳＰを生成して、ＬＲ’ｉ←ＰＲＧ（Ｒｘ，ＳＥＥＤ’ｉ），ＬＲ”ｉ←ＰＲＧ（Ｚ｜Ｒ｜ｘ，ＳＥＥＤ”ｉ）とする。
そして、ＬＲ’ｉ，ＬＲ”ｉを暗号化して送信する代わりに、ＳＥＥＤ’ｉ，ＳＥＥＤ”ｉを暗号化して送信すれば、通信量を削減できる。
組立暗号文作成手段６で、ＳＥＥＤ’ｉ，ＳＥＥＤ”ｉを復号して、ＬＲ’ｉ←ＰＲＧ（Ｒｘ，ＳＥＥＤ’ｉ），ＬＲ”ｉ←ＰＲＧ（Ｚ｜Ｒ｜ｘ，ＳＥＥＤ”ｉ）とする。
【図面の簡単な説明】
【００３８】
【図１】本発明の電子投票システムの一構成例を示した図である。
【図２】組立暗号文作成指示暗号文作成手段４による組立暗号文作成指示暗号文の生成の流れを示した図である。
【図３】組立暗号文作成手段６による組立暗号文の生成の流れを示した図である。
【符号の説明】
【００３９】
１ 投票装置
２ 複数台の開票装置
３ 投票内容入力手段
４ 組立暗号文作成指示暗号文作成手段
５ 初期暗号文作成手段
６ 組立暗号文作成手段
７ 組立暗号文集計手段
８ 集計暗号文記憶手段
９ 復号手段
【特許請求の範囲】
【請求項１】
投票装置が投票内容入力手段と組立暗号文作成指示暗号文作成手段を有し、
ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）が初期暗号文作成手段と組立暗号文作成手段と組立暗号文集計手段と復号手段を有する電子投票システムにおいて、各手段が下記の手順を有することを特徴とする電子投票システム。
投票内容入力手段は、投票内容を入力として、初期平文リストＬＮ０と最終平文リストＬＮｔ＋１を出力する。
組立暗号文作成指示暗号文作成手段は、初期平文リストＬＮ０と最終平文リストＬＮｔ＋１を入力として、
ＬＮｔ＋１＝πｔ＋１・・・π１ＬＮ０
を満たすｔ＋１個（ｓ≧２ｔ＋１）のランダム置換πｉ（１≦ｉ≦ｔ＋１）と
再暗号化に用いる乱数リストＬＲ’ｉ（１≦ｉ≦ｔ＋１）を作成して、
１≦ｉ≦ｔ＋１について開票装置ＳｉがπｉとＬＲ’ｉを復号できるように暗号化した暗号文と、
ｔ＋１台の開票装置がπｉ（１≦ｉ≦ｔ＋１）とＬＲ’ｉ（１≦ｉ≦ｔ＋１）を復号できるように
暗号化した暗号文と、
１≦ｉ≦ｔ＋１について、開票装置Ｓｉが実行する暗号文リストに対するランダム置換と再暗号化の処理の正当性を検証するための暗号文を作成して出力する。
初期暗号文作成手段は、初期暗号文リストＬＥ０を作成して出力する。
組立暗号文作成手段は、組立暗号文作成指示暗号文作成手段で作成された暗号文と初期暗号文リストＬＥ０を入力として、
ｉ＝１，．．．，ｔ＋１について下記の手順を繰り返して、組立暗号文ｅ（ｊ，ｋ）を作成して出力する。
開票装置Ｓｉが、組立暗号文作成指示暗号文作成手段で作成された暗号文からπｉとＬＲ’ｉを復号する。
開票装置Ｓｉが、πｉとＬＲ’ｉを用いて、暗号文リストに対するランダム置換と再暗号化の処理を実行する。
組立暗号文作成指示暗号文作成手段で作成された暗号文を用いて開票装置Ｓｉが実行した暗号文リストに対するランダム置換と再暗号化の処理の正当性を検証する。正当性が検証できない場合には、ｓ台の開票装置が、組立暗号文作成指示暗号文作成手段で作成された暗号文を閾値暗号法を用いてπｉとＬＲ’ｉを復号して、πｉとＬＲ’ｉを用いて、暗号文リストに対するランダム置換と再暗号化の処理を実行する。
組立暗号文集計手段は、組立暗号文作成手段で作成された組立暗号文ｅ（ｊ，ｋ）を集計暗号文ｅｋに集計する。
復号手段は、集計暗号文ｅｋを閾値復号法を用いて復号して集計平文ｐｋを出力する。
【請求項２】
投票装置が投票内容入力手段と組立暗号文作成指示暗号文作成手段を有し、
ｓ台の開票装置が初期暗号文作成手段と組立暗号文作成手段と組立暗号文集計手段と復号手段を
有する電子投票システムにおいて、請求項１記載の手順に従う各手段を具備することを
特徴とする投票装置と開票装置。
【請求項３】
投票装置が投票内容入力手段と組立暗号文作成指示暗号文作成手段を有し、
ｓ台の開票装置が初期暗号文作成手段と組立暗号文作成手段と組立暗号文集計手段と復号手段を
有する電子投票システムにおいて、各手段を請求項１記載の手順に従って実行させるためのプログラムを
記録した記録媒体。
【請求項４】
請求項１記載の組立暗号文作成指示暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを暗号化し、
請求項１記載の組立暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを復号する電子投票システム
【請求項５】
請求項１記載の組立暗号文作成指示暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを暗号化する投票装置、及び、
請求項１記載の組立暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを復号する開票装置。
【請求項６】
請求項１記載の組立暗号文作成指示暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを暗号化し、
請求項１記載の組立暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを復号する手続きを
コンピュータで実行させるためのプログラムを記録した記録媒体。
【請求項１】
投票装置が投票内容入力手段と組立暗号文作成指示暗号文作成手段を有し、
ｓ台の開票装置Ｓｉ（１≦ｉ≦ｓ）が初期暗号文作成手段と組立暗号文作成手段と組立暗号文集計手段と復号手段を有する電子投票システムにおいて、各手段が下記の手順を有することを特徴とする電子投票システム。
投票内容入力手段は、投票内容を入力として、初期平文リストＬＮ０と最終平文リストＬＮｔ＋１を出力する。
組立暗号文作成指示暗号文作成手段は、初期平文リストＬＮ０と最終平文リストＬＮｔ＋１を入力として、
ＬＮｔ＋１＝πｔ＋１・・・π１ＬＮ０
を満たすｔ＋１個（ｓ≧２ｔ＋１）のランダム置換πｉ（１≦ｉ≦ｔ＋１）と
再暗号化に用いる乱数リストＬＲ’ｉ（１≦ｉ≦ｔ＋１）を作成して、
１≦ｉ≦ｔ＋１について開票装置ＳｉがπｉとＬＲ’ｉを復号できるように暗号化した暗号文と、
ｔ＋１台の開票装置がπｉ（１≦ｉ≦ｔ＋１）とＬＲ’ｉ（１≦ｉ≦ｔ＋１）を復号できるように
暗号化した暗号文と、
１≦ｉ≦ｔ＋１について、開票装置Ｓｉが実行する暗号文リストに対するランダム置換と再暗号化の処理の正当性を検証するための暗号文を作成して出力する。
初期暗号文作成手段は、初期暗号文リストＬＥ０を作成して出力する。
組立暗号文作成手段は、組立暗号文作成指示暗号文作成手段で作成された暗号文と初期暗号文リストＬＥ０を入力として、
ｉ＝１，．．．，ｔ＋１について下記の手順を繰り返して、組立暗号文ｅ（ｊ，ｋ）を作成して出力する。
開票装置Ｓｉが、組立暗号文作成指示暗号文作成手段で作成された暗号文からπｉとＬＲ’ｉを復号する。
開票装置Ｓｉが、πｉとＬＲ’ｉを用いて、暗号文リストに対するランダム置換と再暗号化の処理を実行する。
組立暗号文作成指示暗号文作成手段で作成された暗号文を用いて開票装置Ｓｉが実行した暗号文リストに対するランダム置換と再暗号化の処理の正当性を検証する。正当性が検証できない場合には、ｓ台の開票装置が、組立暗号文作成指示暗号文作成手段で作成された暗号文を閾値暗号法を用いてπｉとＬＲ’ｉを復号して、πｉとＬＲ’ｉを用いて、暗号文リストに対するランダム置換と再暗号化の処理を実行する。
組立暗号文集計手段は、組立暗号文作成手段で作成された組立暗号文ｅ（ｊ，ｋ）を集計暗号文ｅｋに集計する。
復号手段は、集計暗号文ｅｋを閾値復号法を用いて復号して集計平文ｐｋを出力する。
【請求項２】
投票装置が投票内容入力手段と組立暗号文作成指示暗号文作成手段を有し、
ｓ台の開票装置が初期暗号文作成手段と組立暗号文作成手段と組立暗号文集計手段と復号手段を
有する電子投票システムにおいて、請求項１記載の手順に従う各手段を具備することを
特徴とする投票装置と開票装置。
【請求項３】
投票装置が投票内容入力手段と組立暗号文作成指示暗号文作成手段を有し、
ｓ台の開票装置が初期暗号文作成手段と組立暗号文作成手段と組立暗号文集計手段と復号手段を
有する電子投票システムにおいて、各手段を請求項１記載の手順に従って実行させるためのプログラムを
記録した記録媒体。
【請求項４】
請求項１記載の組立暗号文作成指示暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを暗号化し、
請求項１記載の組立暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを復号する電子投票システム
【請求項５】
請求項１記載の組立暗号文作成指示暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを暗号化する投票装置、及び、
請求項１記載の組立暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを復号する開票装置。
【請求項６】
請求項１記載の組立暗号文作成指示暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを暗号化し、
請求項１記載の組立暗号文作成手段において、
乱数リストＬＲ’ｉの代わりに擬似乱数生成系のシードを復号する手続きを
コンピュータで実行させるためのプログラムを記録した記録媒体。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２００６−３２９９４（Ｐ２００６−３２９９４Ａ）
【公開日】平成１８年２月２日（２００６．２．２）
【国際特許分類】
【出願番号】特願２００４−２０４０４２（Ｐ２００４−２０４０４２）
【出願日】平成１６年７月１２日（２００４．７．１２）
【出願人】（３０３００９５３７）
【出願人】（３０００４４９０８）
【出願人】（３０３０３４５８４）
【Ｆターム（参考）】
【公開日】平成１８年２月２日（２００６．２．２）
【国際特許分類】
【出願日】平成１６年７月１２日（２００４．７．１２）
【出願人】（３０３００９５３７）
【出願人】（３０００４４９０８）
【出願人】（３０３０３４５８４）
【Ｆターム（参考）】
[ Back to top ]