(57)【特許請求の範囲】
【請求項１】
複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力し、入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｂ）乱数を発生し、発生した乱数を第５の記憶手段に記憶するステップ、
ｃ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算して、該計算した検査積を第６の記憶手段に記憶するステップ、
ｄ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定し、判定結果を第７の記憶手段に記憶するステップ、
ｅ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば検査不合格の旨を出力して処理を終了し、検査積の位数が基準となる位数の約数である旨の判定結果であれば、第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、予め定められた値以上であれば第４の記憶手段に記憶された安全変数を所定値だけ減じてステップｂに処理を戻すステップ、
を含むことを特徴とする、複数の要素に対する確率的同時位数検査方法。
【請求項２】
複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力するステップ、
ｂ）入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｃ）乱数を発生するステップ、
ｄ）発生した乱数を第５の記憶手段に記憶するステップ、
ｅ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算するステップ、
ｆ）計算した検査積を第６の記憶手段に記憶するステップ、
ｇ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定するステップ、
ｈ）判定結果を第７の記憶手段に記憶するステップ、
ｉ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば、検査不合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｊ）第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｋ）第４の記憶手段に記憶された安全変数を所定値だけ減じ、ステップｃに処理を戻すステップ、
を含むことを特徴とする、複数の要素に対する確率的同時位数検査方法。
【請求項３】
複数の被検査値すべての位数が基準となる位数の約数であることを検査するプログラムであって、コンピュータに、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力し、入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｂ）乱数を発生し、発生した乱数を第５の記憶手段に記憶するステップ、
ｃ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算して、該計算した検査積を第６の記憶手段に記憶するステップ、
ｄ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定し、判定結果を第７の記憶手段に記憶するステップ、
ｅ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば検査不合格の旨を出力して処理を終了し、検査積の位数が基準となる位数の約数である旨の判定結果であれば、第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、予め定められた値以上であれば第４の記憶手段に記憶された安全変数を所定値だけ減じてステップｂに処理を戻すステップ、
を実行させる位数検査プログラム。
【請求項４】
複数の被検査値すべての位数が基準となる位数の約数であることを検査するプログラムであって、コンピュータに、
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力するステップ、
ｂ）入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ、
ｃ）乱数を発生するステップ、
ｄ）発生した乱数を第５の記憶手段に記憶するステップ、
ｅ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算するステップ、
ｆ）計算した検査積を第６の記憶手段に記憶するステップ、
ｇ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定するステップ、
ｈ）判定結果を第７の記憶手段に記憶するステップ、
ｉ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば、検査不合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｊ）第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ、
ｋ）第４の記憶手段に記憶された安全変数を所定値だけ減じ、ステップｃに処理を戻すステップ、
を実行させる位数検査プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数のデータの位数が特定の値であることを検査する方法に関し、特に複数のデータを一括して扱うことにより高速に結果を判定する方法に関する。
【０００２】
【従来の技術】
多くの公開鍵暗号系のアプリケーションでは、安全性を保証するために、暗号文を構成する数値の位数を検査することがある。ここで言う数値の位数とは、その数値が生成する巡回群の集合としての位数のことであり、数値の位数の検査とは、その数値の位数が想定されている値であるかを検査することである。位数について簡単な例を挙げて説明する。今、乗法群(Z/pZ)＊としてp=7である(Z/7Z)＊を、数値として3を想定すると、数値3が生成する巡回群の集合は、3１ mod 7=3、3２ mod 7=2、3３ mod 7=6、3４ mod 7=4、3５ mod 7=5、3６ mod 7=1、3７ mod 7=3、3８ mod 7=2、3９ mod 7=6、310 mod 7=4、311 mod 7=5、…、であり、3,2,6,4,5,1の6個の要素からなる。これを、数値3が乗法群(Z/7Z)＊上で生成する巡回群の集合としての位数は6であると言う。
【０００３】
ところで、近年電子投票等の暗号アプリケーション等、膨大な数の暗号文を一度に扱う機会が増えている。このため、これらのアプリケーションで数値の位数の検査を迅速に完了することが求められている。位数検査が必要となる具体的な例としては、「検証可能な Mix-net 」と呼ばれる暗号プロトコルを用いた電子投票システムがあげられる。ここで投票行為は、公開鍵暗号システムを用いて暗号化した投票文を集計所に送付することにより行われる。集計では、まず送付された投票暗号文を複数の集計者により共同して復号し、次に復号された投票文を集計する。一連の集計操作の終了後、「検証可能な Mix-net 」では、一連の操作が正しく行われたかを証明するデータを、集計者が協力して生成し出力する。このデータのことを以後「証明データ」と呼ぶことにする。ところで、もし集計結果が正しくなかったとしても、暗号投票文の集合と復号した投票文の集合のみからはその事実は簡単には分らない。しかし復号のための鍵を持っているならば、集計結果が正しいかどうかはたちどころに分る。なぜならこの鍵で全ての投票暗号文を復号して二つの集合を比較すれば良いからである。証明データとはこのように集計結果が正当であるかを知ることを可能にするデータであるが、鍵そのものでなく、証明データからは投票暗号文と復号結果の対応は分らない（つまり、投票の匿名性を破らない）データである。「検証可能な Mix-net 」を用いた電子投票では、投票の集計において不正がなされていないことを、投票暗号文と復号された投票文と証明データから特殊なアルゴリズムを用いて判断する。このアルゴリズムの中に、特に「検証可能な Mix-net 」がエルガマル暗号文を利用する場合、暗号文と復号された投票文と証明データを構成する値の位数を調べる操作が含まれることが多い。なぜなら、エルガマル暗号文では位数の異なる暗号文を識別できるため、同じ位数の暗号文だけを選んで使わないと、電子投票システムの安全性が低下するからである。
【０００４】
さて、従来の位数検査の方法には、以下のようなものがある。先ず、数値gの位 数がqの約数であることを検査するためには、数値gをこの数値gが定義された群上で、数値gのq+1乗である gq+1を計算する。つまり、定義された群を(Z/pZ) ＊とすると、gq+1 mod p を計算する。そして、この計算結果がgに等しければ、数値gの位数はqの約数であったと判定する。特に、qが素数の場合は、その位数は1あるいはqである。
【０００５】
【発明が解決しようとする課題】
しかし前記従来の技術におけるgq+1の計算には、多大な計算コストがかかる場合が多いため、多数の数値の位数の検査を行うには膨大な時間がかかるという問題がある。特にMix-netにより大規模な電子投票を行う場合などには、位数を検査する必要のある暗号文が膨大なため、多大な時間が必要になり、システムの運用が困難になる場合がある。
【０００６】
本発明はこのような事情に鑑みて提案されたものであり、その目的は、多数の数値の位数をより少ない時間で検査する方法を提供することにある。
【０００９】
【課題を解決するための手段】
本発明の第１の複数の要素に対する確率的同時位数検査方法は、複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、以下のステップを含むことを特徴とする。
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力し、入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ
ｂ）乱数を発生し、発生した乱数を第５の記憶手段に記憶するステップ
ｃ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算して、該計算した検査積を第６の記憶手段に記憶するステップ
ｄ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定し、判定結果を第７の記憶手段に記憶するステップ
ｅ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば検査不合格の旨を出力して処理を終了し、検査積の位数が基準となる位数の約数である旨の判定結果であれば、第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、予め定められた値以上であれば第４の記憶手段に記憶された安全変数を所定値だけ減じてステップｂに処理を戻すステップ
【００１０】
本発明の第２の複数の要素に対する確率的同時位数検査方法は、複数の被検査値すべての位数が基準となる位数の約数であることをコンピュータにより検査する方法において、以下のステップを含むことを特徴とする。
ａ）群を定義する変数、前記群の要素である複数の被検査値、基準となる位数および安全変数を入力するステップ
ｂ）入力した群を定義する変数を第１の記憶手段に、入力した複数の被検査値を第２の記憶手段に、入力した基準となる位数を第３の記憶手段に、入力した安全変数を第４の記憶手段に、それぞれ記憶するステップ
ｃ）乱数を発生するステップ
ｄ）発生した乱数を第５の記憶手段に記憶するステップ
ｅ）第１の記憶手段から群を定義する変数を、第２の記憶手段から複数の被検査値を、第５の記憶手段から乱数をそれぞれ取得し、乱数の値に基づいて複数の被検査値の中から検査積生成に用いる被検査値を選択し、該選択した被検査値の前記群上での積である検査積を計算するステップ
ｆ）計算した検査積を第６の記憶手段に記憶するステップ
ｇ）前記第１の記憶手段から群を定義する変数を、第３の記憶手段から基準となる位数を、第６の記憶手段から検査積をそれぞれ取得して、検査積の位数が基準となる位数の約数であるかどうかを判定するステップ
ｈ）判定結果を第７の記憶手段に記憶するステップ
ｉ）第７の記憶手段から判定結果を取り出し、検査積の位数が基準となる位数の約数でない旨の判定結果であれば、検査不合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ
ｊ）第４の記憶手段から安全変数を取り出し、予め定められた値以上か否かを判定し、予め定められた値以上でなければ、検査合格の旨を出力して処理を終了し、それ以外は処理を継続するステップ
ｋ）第４の記憶手段に記憶された安全変数を所定値だけ減じ、ステップｃに処理を戻すステップ
【００１１】
【作用】
本発明にあっては、被検査値の中にその位数が与えられた位数の約数でないものがある場合には、安全変数を十分大きくとれば十分に1に近い確率で、そのようであることを確認できる。また、前記安全変数が位数のbit数よりも十分に小さく、かつ、位数を検査する検査値の数が位数のbit数よりも十分に大きい場合には、従来の方式による位数の検査よりも効率良く位数を検査することができる。例えば、位数のbit数が160以上の数であれば、安全変数は40ほどで十分な精度の検査が可能であり、この場合、被検査数値列が45個以上の要素からなる場合には、計算コストが従来技術に比べて低減される。
【００１２】
【発明の実施の形態】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００１３】
図１を参照すると、本発明を適用したコンピュータの一例は、入力装置100、出力装置200、プログラム記憶装置300、メモリ400、及びそれらに接続された中央処理装置500で構成される。入力装置100は、キーボード等の手動入力装置、入力データを記憶するファイル装置、通信回線を通じて送られてくるデータを受信する通信装置などで構成される。出力装置200は、表示装置、プリンタ、出力データを記憶するファイル装置、通信回線を通じて出力データを送信する通信装置などで構成される。プログラム記憶装置300は、当該コンピュータの基本プログラムや位数検査プログラムなどのソフトウェアを記憶するための磁気ディスク等で構成される。メモリ400は、位数検査処理の過程で必要となる各種のデータを記憶するための記憶部で、RAM等で構成される。本実施の形態の場合、メモリ400には、ファイルやテーブル等で構成される第1乃至第7の記憶手段401〜407が設けられている。中央処理装置500は、プログラム記憶装置300に記憶されたプログラムを実行することにより、本コンピュータの全体を制御する。特に、プログラム記憶装置300に記憶された位数検査プログラムを実行することにより、本発明にかかる位数検査方法を実行する。
【００１４】
次に図２を参照して、位数検査プログラムによる処理の流れを説明する。
【００１５】
［前提］
pを整数、φ(p)を、p未満の正整数のうちpと互いに素な正整数の総数、qを、q|φ(p)なる整数、つまりφ(p)が割り切れる整数とする。この意味を簡単な例を挙げて説明すると、p=15の場合、p未満の正整数のうちpと互いに素な正整数は、1,2,4,7,8,11,13,14の合計8個であるから、φ(p)=8であり、8が割り切れる整数であるqは1,2,4,8である。なお、この複数の値のqのうち、特定の値のqを基準となる位数として位数検査が行われる。
【００１６】
［入力処理S101］
中央処理装置500は、入力装置100から、乗法群(Z/pZ)＊を定義する変数p、この群の要素であるn個の被検査値g１,g２,…,gｎ、基準となる位数qおよび安全変数sを入力し、第1の記憶手段401、第2の記憶手段402、第3の記憶手段403および第4の記憶手段404に記憶する。例えば本発明を従来技術の項で説明した「検証可能な Mix-net 」と呼ばれる暗号プロトコルを用いた電子投票システムに適用する場合、変数pは公開鍵暗号が用いる群を定義する変数に相当し、複数の被検査値は暗号化されて投票された票、復号が終了した票、集計処理が正常に行われたことを証明するデータを構成する要素に相当し、基準となる位数qは当該電子投票システムで用いることが定められた位数に相当する。また、安全変数sは検査に要求される精度に応じて事前に定められる。
【００１７】
［乱数生成処理S102］
中央処理装置500は、乱数発生手段を用いて、被検査値の個数nと等しいnビットの乱数rを生成し、第5の記憶手段405に記憶する。ここで、乱数rの各ビットの値は1または0である。
【００１８】
［検査積生成処理S103］
中央処理装置500は、第1、第2、第5の記憶手段401、402、405から、群を定義する変数p、n個の被検査値g１,g２,…,gｎ、nビットの乱数rをそれぞれ取得し、n個の被検査値g１,g２,…,gｎと乱数の各ビットとを1対1に対応付けた場合に、乱数rの対応するビットの値が予め定められた値（例えば1）である被検査値だけを選び出し、それらの被検査値の前記群上での積である検査積Qを計算し、第6の記憶手段406に記憶する。検査積Qの計算を簡単な例で説明すると、群を(Z/7Z)＊、選ばれた2つの被検査値g１,g２を3，4とすると、それらの被検査値の前記群上での積である検査積Qは、3＊4 mod 7 =5 と計算する。
【００１９】
［検査積位数判定処理S104］
中央処理装置500は、第1、第3、第6の記憶手段401、403、406から、群を定義する変数p、基準となる位数q、検査積Qをそれぞれ取得して、検査積Qの位数が基準となる位数qの約数であるかどうかを、以下の式が成立するかどうかを計算することによって判定し、その判定結果を第7の記憶手段407に記憶する。
Qq+1 mod p =Q
上記の式が成立するときは、当該検査積Qの計算の元となった全ての被検査値の位数が位数qの約数であるため、判定結果を「受理」とし、安全変数判断処理S107へ分岐する。反対に、上記の式が成立しないときは、当該検査積Qの計算の元となった被検査値の中に少なくとも位数が位数qの約数でない被検査値が含まれているため、判定結果を「不受理」とし、不受理出力処理S105へ分岐する。
【００２０】
［不受理出力処理S105］
中央処理装置500は、「不受理」の判定結果を第7の記憶手段407から取り出し、出力装置200から出力する。そして、当該被検査値に対する位数検査処理を終了する（S106）。
【００２１】
［安全変数判断処理S107］
中央処理装置500は、第4の記憶手段404から安全変数sを取り出し、予め定められた値（本例では1）より大きいかどうかを判定し、1より大きければ繰り返し処理S109へ分岐し、1より大きくなければ、受理出力処理S108へ分岐する。
【００２２】
［受理出力処理S108］
中央処理装置500は、「受理」の判定結果を第7の記憶手段407から取り出し、出力装置200から出力する。そして、当該被検査値に対する位数検査処理を終了する（S106）。
【００２３】
［繰り返し処理S109］
中央処理装置500は、第4の記憶手段404に記憶されている安全変数sを所定値（本例では１）だけ減じ、乱数生成処理S102に分岐する。これにより、上述した処理が繰り返される。この繰り返しは、処理S103で生成された検査積Qの位数が位数qの約数でないと判定されるか、処理S107で安全変数sの値が1より大きくないと判定されるまで続けられる。
【００２４】
次に、本実施例の効果を説明する。
【００２５】
全ての被検査数値列gi;(i=1、2、…、n)に関して、giq+1 mod p =giが成り立つならば、本実施例では必ず「受理」を出力する。これは明らかである。一つでもgiq+1 mod p ≠giなるgiが存在する場合、各検査積Qがgiを含む確率は1/2である。なぜなら、検査積を構成するその他の要素を同じとして、検査積Qがgiを含む場合と含まない場合の両方の場合に、共にQq+1 mod p =Qが成り立つことは有り得ない。よって、一つでもgiq+1 mod p ≠giなるgiが存在する場合、無作為に選ばれた乱数rに関して、Qq+1 mod p =Qが成り立つ確立は、1/2以下であるからである。
【００２６】
本実施例において「受理」を出力した場合は、s個の乱数に関して生成された検査積Q全てが、Qq+1 mod p =Qを満たしたと言うことであるので、一つでもgiq+1 mod p≠giなるgiが存在する確率は1/2ｓ以下である。従って、安全変数sを十分に大きくとれば、giq+1 mod p ≠giなるgiの存在を見逃す確率は無視できるほど小さくなる。
【００２７】
従来の方法でn個のgiに関して、giq+1 mod p=giを確認するには、冪乗剰余算をn回行わなければならなかった。そして、一回の冪乗剰余算にはおよそqのビット数の3/2倍の乗算剰余が必要である。qのビット数を|q|とすると、全体で(3/2)|q|n回の乗算剰余が必要である。
【００２８】
一方本実施例では、検査積Qを生成するにはn/2回の乗算剰余が必要で、Qq+1 を計算するには(3/2)|q|回の乗算剰余が必要なので、全体として、{(1/2)n + (3/2)|q|}s回の乗算剰余が必要になる。
【００２９】
従って、nが|q|より十分大きい場合、すなわち多くの位数検査を行う必要がある場合で、かつs＜3|q|であれば本実施例は従来の方法よりも効率が良い。現実的に、前述した電子投票システム等の場合、位数のbit数|q|は160以上の数が選ばれる場合が多く、安全変数sは40ほどで十分な場合が多い。このような条件では、被検査数値列が45個以上の要素からなる場合では、本実施例の方が効果的である。
【００３０】
【発明の効果】
以上説明したように本発明によれば、多数の数値の位数をより少ない時間で検査することが可能である。その理由は、複数のデータを一括して扱い且つ確率的に検査しているからである。
【図面の簡単な説明】
【図１】本発明を適用したコンピュータの一例を示すブロック図である。
【図２】位数検査プログラムによる処理の流れを示すフローチャートである。
【符号の説明】
100…入力装置
200…出力装置
300…プログラム記憶装置
400…メモリ
401〜407…第1〜第7の記憶手段
500…中央処理装置
【図１】
0004122856.tif 000002
【図２】
0004122856.tif 000003