(57)【特許請求の範囲】
【請求項１】
複数の計算装置を含む機器を用いて与えられた関数の値を計算する方法であって、
入力処理と、
ElGamal暗号文準備処理と、
逐次置換再暗号処理と、
結果出力処理とからなり、
前記入力処理は、
前記複数の計算装置に複数のゲートから構成された回路の情報及び前記複数の計算装置に関する情報が入力される、情報入力ステップと、関数の入力データを複数に計算装置の個数に分散したデータである複数の部分データを、それぞれの計算装置にそれぞれ一つずつ入力する分散入力ステップと、からなり、
前記ElGamal暗号文準備処理は、少なくとも一つの計算装置が、与えられた関数を実現する回路のゲートに対応したElGamal暗号文の集合を生成するElGamal暗号文準備ステップとからなり、
前記逐次置換再暗号処理は、
置換再暗号処理を各計算装置が順番に行う処理で、前記置換再暗号処理は、順番が回ってきた計算装置が、一つ前の順番に対応する計算装置からElGamal暗号文の集合を受け取る暗号文取得ステップと、
前記暗号文取得ステップにて受け取った暗号文の集合を順序を入れ替えて置換し、それらを再暗号化する暗号文の置換と再暗号化ステップと、
前記暗号文の置換と再暗号化ステップで生成したデータを、少なくとも次の順番の計算装置に公開するステップと、からなり、
前記結果出力処理は、
前記逐次置換再暗号処理で生成された暗号文の一部を復号あるいは部分復号する部分復号ステップと、
前記逐次置換再暗号処理で生成された暗号文の中で前記回路の入力に対応するデータを暗号化している暗号文を復号する復号ステップと、
前記復号ステップで復号されたデータと、前記部分復号ステップで部分復号されたデータを用いて、回路の出力を評価する回路の評価ステップとからなり、
前記各ゲートに対応するElGamal暗号文の集合は、前記各計算装置が各ゲートに対応して生成した秘密鍵のElGamal暗号文の集合であり、
前記ElGamal暗号文を生成するのに用いた公開鍵は、このゲートに入力される二つの信号を生成するゲートに対応する公開鍵の和であり、
それらは、出力1に対応する暗号文と、出力0に対応する暗号文の組みが、計算する論理式に合わせて複数準備されていて、
逐次暗号化処理は、前記暗号文を再暗号化して置換する処理で、1と0に対応する暗号文がそれぞれ入れ替わる置換のみを行ない、1と1に対応する暗号文がそれぞれ入れ替わる様な置換を行なわない処理であり、
最終的な復号結果は、1と0のどちらか一方の暗号文のみ復号する処理であることを特徴とする計算方法。
【請求項２】
複数の計算装置と、
複数の計算装置と通信する手段と、
入力処理手段と、
ElGamal暗号文準備手段と、
置換再暗号処理手段と、
結果出力処理手段と、からなる関数を評価する計算システムであって、
前記入力処理手段は、出力を求めたい回路の情報と、前記複数の計算装置に関する情報と、前記複数の計算装置がそれぞれ前記回路の入力のどの部分を所持しているかという情報と、を入力し、
前記ElGamal暗号文準備処理手段は、与えられた関数を実現する回路のゲートに対応したElGamal暗号文の集合を生成するElGamal暗号文を準備し、
前記置換再暗号処理手段は、
順番が回ってきた計算装置が、一つ前の順番に対応する計算装置からElGamal暗号文の集合を受け取る暗号文取得手段と、
前記暗号文取得手段により受け取られた暗号文の集合の順序を入れ替えて置換し、それらを再暗号化する暗号文の置換と再暗号化手段と、
前記暗号文の置換と再暗号化手段を用いて生成したデータを、少なくとも次の順番の計算装置に公開する手段と、からなり、
前記結果出力手段は、
置換再暗号処理手段で生成された暗号文の一部を復号あるいは部分復号する部分復号手段と、
前記置換再暗号処理手段で生成された暗号文の中で前記回路の入力に対応するデータを暗号化している暗号文の自分に関する暗号化を復号する復号手段と、
前記複数の計算機が前記復号手段で復号したデータと前記複数の計算機が前記部分復号手段で部分復号されたデータを用いて回路の出力を評価する回路の評価手段とからなり、
前記各ゲートに対応するElGamal暗号文の集合は、前記各計算装置が各ゲートに対応して生成した秘密鍵のElGamal暗号文の集合であり、
前記ElGamal暗号文を生成するのに用いた公開鍵は、このゲートに入力される二つの信号を生成するゲートに対応する公開鍵の和であり、
それらは、出力1に対応する暗号文と、出力0に対応する暗号文の組みが、計算する論理式に合わせて複数準備されていて、
逐次暗号化処理は、前記暗号文を再暗号化して置換する処理で、1と0に対応する暗号文がそれぞれ入れ替わる置換のみを行ない、1と1に対応する暗号文がそれぞれ入れ替わる様な置換を行なわない処理であり、
最終的な復号結果は、1と0のどちらか一方の暗号文のみ復号する処理であることを特徴とする計算システム。
【請求項３】
前記請求項１に記載された計算方法において、
前記入力処理として、各計算装置にElGamal暗号方式の領域変数を入力するステップが行なわれ、
前記ElGamal暗号文準備処理として、各前記計算装置が、各前記回路の各ゲートに対応して、ElGamal暗号文の秘密鍵を生成するゲート秘密鍵生成ステップが行なわれ、
各計算装置では、
前記ゲート秘密鍵の生成ステップにて生成した秘密鍵に対応するゲート公開鍵を生成するゲート公開鍵の生成ステップと、
前記ゲート公開鍵の生成ステップにて生成した公開鍵の正当性の証明を生成するゲート公開鍵の正当性の証明生成ステップと、
前記ゲート公開鍵の正当性の証明生成ステップにて生成したゲート公開鍵の正当性の証明を公開するゲート公開鍵の正当性の証明公開ステップと、
各前記回路のゲートで回路への入力が直接入力されるゲートに対応して、ElGamal暗号文の秘密鍵を生成する入力のゲート秘密鍵の生成ステップと、
前記入力ゲート秘密鍵の生成ステップにて生成した秘密鍵に対応する入力ゲート公開鍵を生成する入力のゲート公開鍵の生成ステップと、
前記入力のゲート公開鍵の生成ステップにて生成した公開鍵の正当性の証明を生成する入力のゲート公開鍵の正当性の証明生成ステップと、
前記入力のゲート公開鍵の正当性の証明生成ステップにて生成し入力の公開鍵の正当性の証明を公開する入力のゲート公開鍵の正当性の証明公開ステップと、
その他の各計算装置が生成して公開したゲート公開鍵を取得するゲート公開鍵取得ステップと、
前記ゲート公開鍵取得ステップにおいて取得したゲート公開鍵を統合するゲート公開鍵の統合ステップと、
前記ゲート公開鍵の統合ステップにおいて統合したゲート公開鍵により、この計算装置が生成したゲート秘密鍵を暗号化するゲート秘密鍵の暗号化ステップと、
前記ゲート秘密鍵の暗号化ステップにおいて生成したゲート秘密鍵の暗号文を公開するゲート秘密鍵の暗号文の公開ステップと、
前記ゲート秘密鍵の暗号文の正当性証明を生成するゲート秘密鍵の暗号文の正当性の証明生成ステップと、
前記ゲート秘密鍵の暗号文の正当性の証明生成ステップにおいて生成したゲート秘密鍵の暗号文の正当性の証明を公開するゲート秘密鍵の暗号文の正当性の証明公開ステップと、
各計算装置に入力された回路の入力の部分に対応する暗号文を生成する入力の暗号文生成ステップと、
前記入力の暗号文生成ステップにて生成した回路の入力の部分に対応する暗号文の正当性の証明を生成する入力の暗号文の正当性の証明生成ステップと、
前記入力の暗号文の正当性の証明生成ステップにおいて生成した証明を公開する入力の暗号文の正当性の証明公開ステップと、
出力のゲートに対応する暗号文を生成して公開する出力の暗号文の生成ステップと、を含み、
前記置換再暗号処理が、
前記ゲート秘密鍵の暗号文の集合の順番をあらかじめ決められた許された置換の方法から無作為に一つの置換を選んで入れ替えて再暗号化するゲート秘密鍵の暗号文の置換と再暗号化ステップと、
前記入力の暗号文の集合の順番をあらかじめ決められた許された置換の方法から無作為に一つの置換を選んで入れ替えて再暗号化する入力の暗号文の置換と再暗号化ステップと、
前記出力の暗号文の集合の順番をあらかじめ決められた許された置換方法から無作為に一つの置換を選んで入れ替えて再暗号化する出力の暗号文の置換と再暗号化ステップと、
前記ゲート秘密鍵の暗号文の置換と再暗号化ステップと入力の暗号文の置換と再暗号化ステップと出力の暗号文の置換と再暗号化ステップとにおいてなされた置換と再暗号化の正当性の証明を生成し公開するゲート秘密鍵の暗号文と入力の暗号文と出力の暗号文の置換と再暗号化の正当性の証明生成と公開ステップと、を含み、
前記結果出力処理の部分復号ステップが、
前記計算装置が互いに通信及び計算することで前記ゲート秘密鍵の暗号文を部分復号するゲート秘密鍵の部分復号ステップと、
前記計算装置が互いに通信及び計算することで前記入力の暗号文を部分復号する入力の暗号文の部分復号ステップと、
前記計算装置が互いに通信及び計算することで前記出力の暗号文を部分復号する出力の暗号文の部分復号ステップと、
前記ゲート秘密鍵の部分復号ステップと入力の暗号文の部分復号ステップと出力の暗号文の部分復号ステップとでなされた部分復号の正当性の証明を生成し公開するゲート秘密鍵と入力の暗号文と出力の暗号文の部分復号ステップの正当性の証明生成と公開ステップと、を含み、
他の計算装置の公開した種々の正当性の証明を検証するステップを含む、ことを特徴とする計算方法。
【請求項４】
複数の計算装置、入力手段、出力手段を含み、まず一台の前記計算装置が計算を行い、その計算結果を他の計算装置のうち一台に送り、次にその計算結果を受け取った前記他の計算装置がその次の計算を行う、というとように一台ずつ順に計算を行ってその計算結果を次の一台に回し、全ての計算装置が一度ずつ計算が終わったら、最後に計算をした計算装置が最初に計算をした前記計算装置に計算結果を送り、以後何度も、一台ずつ順に計算を行ってその計算結果を次の一台に回すという各周の計算を繰り返す計算システムであって、
前記入力手段では前記計算装置に回路の情報と、前記回路への入力ビットの一部とが入力され、
第ゼロ周目の計算は第一の計算装置が第一周目の計算を行う前に行い、
前記複数の計算装置には、
前記各周の計算に使用される送られてきたデータを取得するデータ取得手段と、正当性証明検証手段と、署名文検証手段と、第一の計算装置のみが行う第一計算装置特別計算手段と、乱数生成を行う乱数生成手段と、本計算を行う本計算計算手段と、本計算で行った計算の正当性を証明する正当性証明作成手段と、署名手段とデータ送信手段とからなり、
前記送られてきたデータは、別の計算装置から送られてきたデータと、データ本体と、データ本体に対する正当性証明と、署名文とからなり、
前記署名文は、前記別の計算装置から送られてきたデータと、前記データ本体と、前記データ本体に対する正当性証明との組に対する署名文であるようなデータで、
前記正当性証明検証手段は前記送られてきたデータ中の正当性証明を検証し、
前記署名検証手段は、前記送られてきたデータ中署名文を検証し、
前記本計算は前記乱数生成手段で生成された乱数を用いて計算し、
前記署名手段が、前記送られてきたデータと、前記本計算で計算された計算結果であるデータ本体と、前記正当性証明作成手段で作成された正当性証明との組に対する署名文を作成し、
前記データ送信手段が、前記送られてきたデータと、前記本計算で計算された計算結果であるデータ本体と、前記正当性証明作成手段で作成された正当性証明と前記署名手段で作成された署名文との組を送信する事を特徴とする計算システム。
【請求項５】
請求項４に記載された計算システムにおいて、
前記送られてきたデータのデータ本体と前記本計算で計算されたデータ本体とが、第一周目の計算では、共に真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組である計算システム。
【請求項６】
請求項５に記載された計算システムにおいて、
各周の計算が、第一周目の計算手段と、第一周目以降の周の計算手段とからなり、
前記計算手段は、第ゼロ周目の計算手段では真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組を作成し、前記第一周目の計算手段が再暗号に使用する為の公開鍵を作成する再暗号用公開鍵作成手段と、送られてきたデータを変換するデータ変換手段と、秘密鍵変換手段と、乱数変換手段とからなり、
前記データ変換手段が、前記データ本体である暗号文の組を、真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる別の組に変換する為の手段であり、
前記秘密鍵変換手段が、前記データ変換手段の計算結果である暗号文達の組に使用されている秘密鍵を再暗号用公開鍵作成手段で作成された公開鍵に対応する秘密鍵に変換する手段であり、
前記秘密鍵変換手段の計算結果が真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組であり、
前記乱数変換手段が前記データ変換手段の計算結果である暗号文達の組に使用されている乱数を変換する手段であり、
前記乱数変換手段の計算結果が真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組である事を特徴とする計算システム。
【請求項７】
請求項６に記載されている計算システムにおいて、
第一周目以降の周の計算手段が、第二周目の計算手段と第二周目以降の計算手段とからなり、
前記送られてきたデータのデータ本体と前記本計算で計算されたデータ本体とが、第二周目の計算では、共に真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組であり、
前記第二周目の計算手段が、
前記送られてきたデータの前記データ本体を変換してエルガマル暗号文もしくは楕円曲線エルガマル暗号文を作成する暗号変換手段と、前記送られてきたデータのデータ本体の暗号文達を部分復号する部分復号手段とからなる計算システム。
【請求項８】
請求項７に記載されている計算システムにおいて、
第二周目以降の計算手段が、第三周目の計算手段のみからなり、第三周目の計算手段の前記本計算手段が、前記送られてきたデータをそのまま出力し、
前記正当性証明作成手段が空列を出力する計算システム。
【発明の詳細な説明】
発明の背景
本発明は、与えられた関数の入力が複数の装置に分散されて保持されている時に、これら装置が連動してこの関数の出力を計算する方法に関し、特に各装置が他の装置と行う通信回数が与えられた関数に依らず定数回で計算できる方法およびシステムに関する。
【背景技術】与えられた関数の入力が複数の装置に分散されて保持されている時に、これら装置が連動してこの関数の出力を計算する方法の従来の技術として、Ｂｅａｖｅｒ、Ｍｉｃａｌｉ、Ｒｏｇａｗａｙが文献「Ｄ．Ｂｅａｖｅｒ、Ｓ．Ｍｉｃａｌｉ、ａｎｄ  Ｐ．Ｒｏｇａｗａｙ、『Ｔｈｅ  ｒｏｕｎｄ  ｃｏｍｐｌｅｘｉｔｙ  ｏｆ  ｓｅｃｕｒｅ  ｐｒｏｔｏｃｏｌｓ』、Ａｎｎｕａｌ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ  ２２、ページ５０３−５１３、１９９０年」にて提案した方法がある。以降この文献を非特許文献１と呼ぶ。
非特許文献１に開示される技術は、ネットワークで繋がるλ人の計算者ｕαがそれぞれ秘密の入力ｘαを持ち、任意の関数ｇが与えられたときに、計算者が互いに協力して関数の出力ｇ（ｘ１，．．．，λ）を計算する方法で、各計算者の秘密がｇ（ｘ１，．．．，ｘλ）以上に漏ることがなく、かつ、この計算に必要な通信回数が定数となる方法である。非特許文献１に開示される技術について図１、図２および図１９を用いて説明する。
［ガードブル回路］
［記法］
回路ｆはｍ個の論理ゲートで構成されるものとし、各ゲートをＧ１，．．．，Ｇｌ，．．．，Ｇｍとする。各ゲート図１９に示されるように、２入力１出力で、各出力は複数のゲートに入力されても良いものとする。Ｇｋの出力配線は一般に複数のゲートに入力されるが、配線を流れる信号の値はどれも同じ値で０または１とする。また、このゲートＧｋから出る配線を全てｗｋと呼ぶ。回路ｆに入力される配線の本数をｎ個とし、これを
｛ｗｋ｝ｋ＝ｍ＋１，．．．，ｍ＋ｎとする。ｗ１．．．，ｗｌを回路ｆの出力とする。
計算者の人数をλ、計算者の集合を
0004835831.tif 000002
ｕ（α）が回路ｆへ入力するビットの個数をｌα個とし、それらの和をｎとする
0004835831.tif 000003
に関して各ｗｋに入力されるビットをｂｋとし、それぞれのビットをｕ（α）にｌα個ずつ次のように割り振る。すなわち、ｕ（α）は集合
0004835831.tif 000004
を決定する。
ゲートＧｋにゲートＧｉとゲートＧｊの出力が入力されたとき、Ｇｊの出力ｂｊ、Ｇｊの出力ｂｊ、とＧｋの出力ｂｋの間の関係を、
0004835831.tif 000005
と表す。また、□はｂｉｔの排他的論理和、・は文字列の連結を表すとする。
ｔは安全変数で、Ｇ，Ｈ，Ｆはｔλビットの文字列を出力する疑似乱数生成器とする。
［構成］
プロトコルは大きく三つの処理、（１）入力処理４０２、（２）多人数計算によるガーブルド回路の並列構築処理４００と、（３）入力の開示と回路の計算を行う結果出力処理４０１とに分かれる。
入力処理４０２は次の様に行う。計算する回路に関する情報、他の計算者に関する情報、各装置の入力データを、各装置に入力する。
ガーブルド回路の並列構築処理４００は次の様に行う。この処理の過程では、図２に示される、λ個の計算装置５０１が個別に計算を行うフェーズ５０２と、全ての計算機が互いに通信するフェーズ５０３が交互に繰り返し行われる。そして、この繰り返しの回数としてある定数回５０４が存在して、計算したい関数がどのようなものであれ以下の処理は終了できる。また、各通信フェーズでは、各計算装置がその他の全ての計算装置にデータを送信するが、この時送信するデータを生成するために、この送信と同じ通信フェーズで行われる他の計算装置の送信データを必要としてはならない。すなわち、他の計算装置のデータを待たねばできない送信があるとき、この送信を行う通信フェーズを、データを待っている通信フェーズとは別のものと数える。
［１］計算者は協力してｔビットの文字列の集合
0004835831.tif 000006
及びビットの集合
0004835831.tif 000007
を一様無作為に、計算者全員に秘密分散される様に生成する。ここで、
0004835831.tif 000008
フェーズにおいてＳｋが公開され、λｋ□ｂｋ＝１ならばＳ′ｋが公開されることになる。
［２］それぞれの計算者
ｕαには、
0004835831.tif 000009
が明かされる。
［３］それぞれの計算者
ｕαは、ｋ＝１，．．．，ｍ＋ｎに関して、それぞれｔλビットの文字列である
0004835831.tif 000010
を計算し、
0004835831.tif 000011
をコミットし、さらにこれらの値を正しく計算したことを他の計算者に証明する。
［４］ｋ＝ｍ＋１，．．．，ｍ＋ｎに関して、計算者達は、
0004835831.tif 000012
を秘密に分散して計算する。
［５］計算者達は協力してｋ＝１，．．．，ｍ＋ｎに関して、
0004835831.tif 000013
を秘密に分散して計算する。但しゲートＧｋに入力される信号はゲートＧｉとゲートＧｊの出力とする。この様子を図１９に示す。結果出力処理４０１における入力の開示と回路の生成は次の様に行う。
［１］計算者は
0004835831.tif 000014
を公開する。
［２］回路の入力により近いｋから順番にｋ＝１，．．．，ｍ＋ｎに関して、ＳｉまたはＳ′ｉ、及びＳｊ、または、Ｓ′ｊから、次のようにしてＳ＊ｋを得る。これはＳｋまたはＳ′ｋである。
0004835831.tif 000015
［３］全てのα＝１，．．．，λ；ｋ＝１，．．．，ｍ＋ｎに関して
0004835831.tif 000016
を確認することで、Ｓ＊ｋ＝ＳｋまたはＳ＊ｋ＝Ｓ′ｋを確認する。
［４］全ての計算者はｋ＝１，．．．，ｌに関して、Ｓｋを手にいれた場合はｐｋ＋ｂｋ＝０、Ｓ′ｋを手にいれた場合はｐｋ＋ｂｋ＝１が成り立つことより、ｂｋを求める。
技術分野の欄に記述された様な方法のその他の従来の技術として、Ｉｓｈａｉ、Ｋｕｓｈｉｌｅｖｉｔｚは、文献「Ｙ．Ｉｓｈａｉ  ａｎｄ  Ｅ．Ｋｕｓｈｉｌｅｖｉｔｚ、『Ｒａｎｄｏｍｉｚｉｎｇ  Ｐｏｌｙｎｏｍｉａｌｓ：Ａ  ｎｅｗ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｒｏｕｎｄ−Ｅｆｆｉｃｉｅｎｔ  Ｓｅｃｕｒｅ  Ｃｏｍｐｕｔａｔｉｏｎ』、ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２０００、ページ２９４−３０４」にて提案した方法がある。以降この文献を非特許文献２と呼ぶ。非特許文献２の従来の技術を図３および図４を用いて説明する。
［ランダマイジング多項式］
非特許文献２には、与えられた関数をある有限体上の低い次数の多項式で表現する方法が提案されている。特に任意の関数が次数３の多項式で表現可能であることが示されている。次数が低い多項式を評価することは定数回のラウンドで可能である。一般に関数は、回路等様々な形で表現することができる。
次にあげるブランチング問題も一般の関数を表現することができる。ブランチング問題ＢＰ＝（Ｇ，ψ、ｓ，ｔ）をｍｏｄ−ｐブランチング問題と呼ぶ。Ｇ＝（Ｖ，Ｅ）は向き付けられたグラフ、ψはラベル付け関数で、Ｇのそれぞれの辺に、１、ｘ１ｉ、あるいはその否定ｘ０ｉのいずれかを関係付けるもの、ｓ，ｔは特別な頂点である。
入力ｘ＝（ｘ１，．．．，ｘｎ）が与えられたとき、ラベル付け関数ψによりＧの部分グラフＧｘが与えられる。ＢＰで計算されるｂｏｏｌｅａｎ関数ｆの値は、Ｇｘにおけるｓ−ｔを結ぶ経路の数をｐで割った余りが０ならばｆ（ｘ）＝０、そうでなければｆ（ｘ）＝１とする。ＢＰの大きさをＧの頂点の数とする。
ＢＰの大きさをｌとする。部分グラフＧｘの｜￥ｔｉｍｅｓ｜隣接行列をＨｘとすると、ｓ−ｔ間を結ぶ経路の数は、
0004835831.tif 000017
となる。ここでＭｘは行列（ｌ−Ｈｘ）からｓ行とｔ列を除いた行列とする。よって、
0004835831.tif 000018
となる。また、Ｍｘはｘに関して高々１次の成分からなる。
［計算方法］
ブール関数ｆが与えられ、その入力ｘが複数の計算者に分配されている時に、ランダマイジング多項式の方法を用いてｆ（ｘ）を求める方法を記す。【００７９】  図３に示すように、
［１］計算する関数に関する情報、他の計算者に関する情報、各装置の入力データを、各装置に入力する（６０５）。
［２］ｆに対応するＢＰを構成する（６００）。
［３］次の処理を十分な回数並列して行う（６０１）。
［処理］
図４に示すように、
全ての計算者は各成分を分散して｜ｘ｜行列Ｒ１，Ｒ２を一様無作為に生成し（６０３）、３行列Ｒ１，Ｍｘ，Ｒ２の積であるＲ１ＭｘＲ２を計算する（６０４）。
各成分はＲ１，Ｒ２，ｘの要素の高々３次の式であり、その計算に必要なラウンド数は高々定数回である。
［４］全てのｒａｎｋＲ１ＭｘＲ２の値からＭｘのｒａｎｋがｌであるかを推測し、ｌである確率が高ければ１を、でなければ０を出力する（６０２）。
上記方法において、ｒａｎｋ（Ｍｘ）＝ｒａｎｋ（Ｍ′ｘ）であれば、Ｒ１ＭｘＲ２とＲ１Ｍ′ｘＲ２の分布は同じになるので、ｘに関する情報はｆ（ｘ）以外は新たに漏ることはない。
さらに、いかなるｌに対しても、ｒａｎｋ（Ｍｘ）＝ｌであるならばｒａｎｋ（Ｒ１ＭｘＲ２）＝ｌとなる確率は０．０８より大きいため、項目２の処理を実行する回数はｌに依存しない。
［計算量と通信量］
ガーブルド回路を用いた方法では、各ゲートに関する計算は独立して行われ、全体の通信量と計算量はゲートの数に比例する。ｔ−ｎ閾値分散（２ｔ２に比例する。ｔ−ｎ閾値分散での計算とはｎ人で秘密を分散して計算を行うが、このうちｔ人が各自知っているデータを持ち寄らない限り、分散された秘密や計算の途中の意味のあるデータを知ることができない計算方法である。
ランダマイジング多項式を用いた方法では、ｔ−ｎ閾値分散が行われた場合で、ｔ２とＢＰの大きさの２乗に比例し、ラウンド数は２（３）となる。
ランダマイジング多項式の方法では通信量と計算量はゲート数の高々１次に比例する。さらに、最高次の係数はランダマイジング多項式の方法のものが断然低く、効率的である。
しかし、ここではｔ−ｎ閾値分散でｔ＞ｎ／２である様な場合で第三者が計算の正当性を検証できることを要求する場合に特に注目する。この様な場合に前述の方法を拡張することは容自明である。拡張の結果は、ガーブルド回路を用いた方法で全体の通信量と計算量はゲートの数とｔ３に比例し、ランダマイジング多項式の方法を用いた場合、通信量と計算量がゲート数の１．５乗に比例し、ゲート数が大きい場合効率的ではない。
第１の問題点は、非特許文献１の方法は、各計算者の計算量及び計算の正当性を検証する検証者の計算量が膨大になるということである。
その理由は、各計算者は疑似乱数生成装置の出力を計算しなければならないが、この計算を正しく行ったことを計算結果を隠したまま証明する必要があるためである。
第２の問題点は、非特許文献２の方法も、やはり各計算者の計算量及び計算の正当性を検証する検証者の計算量が膨大になるということである。
その理由は、各計算者が計算する計算量が、関数を回路で表現した場合のゲート数の１．５乗に比例し、かつ多くの場合ゲート数は非常に多いため、全体の計算量が膨大になると言うことである。
【発明の開示】
本発明の目的は、回路を表現するゲート数が多くなってもその計算装置がゲート数に比例するに留め、計算装置がその計算の正当性を証明すべき疑似乱数生成装置の出力を計算する必要がなく、かつ計算装置の通信回数が関数に依らずに定数回となる計算方法およびシステムを提供することにある。
本発明の計算方法は、複数の計算装置を含む機器を用いて与えられた関数の値を計算する方法であって、
入力処理と、
出力処理とからなり、
前記入力処理では、前記複数の計算装置に、回路と、前記回路への入力ビットとが入力され、
まず一台の前記計算装置が計算を行い、その計算結果を他の前記計算装置のうち一台に送り、次にその計算結果を受け取った前記前記計算装置がその次の計算を行う、というとように一台ずつ順に計算を行ってその計算結果を次の一台に回し、全ての前記計算装置が一度ずつ計算が終わったら、最後に計算をした計算装置が最初に計算をした計算装置に計算結果を送り、以後何度も、一台ずつ順に計算を行ってその計算結果を次の一台に回すという各周の計算を繰り返す事を特徴とする。
本発明の他の形態による計算方法は、複数の計算装置を含む機器を用いて与えられた関数の値を計算する方法であって、
入力処理と、
ＥｌＧａｍａｌ暗号文準備処理と、
逐次置換再暗号処理と、
結果出力処理とからなり、
前記入力処理は、
前記複数の計算装置に複数のゲートから構成された回路の情報及び前記複数の計算装置に関する情報が入力される、情報入力ステップと、関数の入力データを複数に計算装置の個数に分散したデータである複数の部分データを、それぞれの計算装置にそれぞれ一つずつ入力する分散入力ステップと、からなり、
前記ＥｌＧａｍａｌ暗号文準備処理は、少なくとも一つの計算装置が、与えられた関数を実現する回路のゲートに対応したＥｌＧａｍａｌ暗号文の集合を生成するＥｌＧａｍａｌ暗号文準備ステップとからなり、
前記逐次置換再暗号処理は、
置換再暗号処理を各計算装置が順番に行う処理で、前記置換再暗号処理は、順番が回ってきた計算装置が、一つ前の順番に対応する計算装置からＥｌＧａｍａｌ暗号文の集合を受け取る暗号文取得ステップと、
前記暗号文取得ステップにて受け取った暗号文の集合を順序を入れ替えて置換し、それらを再暗号化する暗号文の置換と再暗号化ステップと、
前記暗号文の置換と再暗号化ステップで生成したデータを、少なくとも次の順番の計算装置に公開するステップと、からなり、
前記結果出力処理は、
前記逐次置換再暗号処理で生成された暗号文の一部を復号あるいは部分復号する部分復号ステップと、
前記前記逐次置換再暗号処理で生成された暗号文の中で前記回路の入力に対応するデータを暗号化している暗号文を復号する復号ステップと、
前記復号ステップで復号されたデータと、前記部分復号ステップで部分復号されたデータを用いて、回路の出力を評価する回路の評価ステップと、からなることを特徴とする。
この場合、前記各ゲートに対応するＥｌＧａｍａｌ暗号文の集合は、前記各計算装置が各ゲートに対応して生成した秘密鍵のＥｌＧａｍａｌ暗号文の集合であり、
前記ＥｌＧａｍａｌ暗号文を生成するのに用いた公開鍵は、このゲートに入力される二つの信号を生成するゲートに対応する公開鍵の和であることとしてもよい。
また、前記入力処理として、各計算装置にＥｌＧａｍａｌ暗号方式の領域変数を入力するステップが行なわれ、
前記ＥｌＧａｍａｌ暗号文準備処理として、各前記計算装置が、各前記回路の各ゲートに対応して、ＥｌＧａｍａｌ暗号文の秘密鍵を生成するゲート秘密鍵生成ステップが行なわれ、
各計算装置では、
前記ゲート秘密鍵の生成ステップにて生成した秘密鍵に対応するゲート公開鍵を生成するゲート公開鍵の生成ステップと、
前記ゲート公開鍵の生成ステップにて生成した公開鍵の正当性の証明を生成するゲート公開鍵の正当性の証明生成ステップと、
前記ゲート公開鍵の正当性の証明生成ステップにて生成したゲート公開鍵の正当性の証明を公開するゲート公開鍵の正当性の証明公開ステップと、
各前記回路のゲートで回路への入力が直接入力されるゲートに対応して、ＥｌＧａｍａｌ暗号文の秘密鍵を生成する入力のゲート秘密鍵の生成ステップと、
前記入力ゲート秘密鍵の生成ステップにて生成した秘密鍵に対応する入力ゲート公開鍵を生成する入力のゲート公開鍵の生成ステップと、
前記入力のゲート公開鍵の生成ステップにて生成した公開鍵の正当性の証明を生成する入力のゲート公開鍵の正当性の証明生成ステップと、
前記入力のゲート公開鍵の正当性の証明生成ステップにて生成し入力の公開鍵の正当性の証明を公開する入力のゲート公開鍵の正当性の証明公開ステップと、
その他の各計算装置が生成して公開したゲート公開鍵を取得するゲート公開鍵取得ステップと、
前記ゲート公開鍵取得ステップにおいて取得したゲート公開鍵を統合するゲート公開鍵の統合ステップと、
前記ゲート公開鍵の統合ステップにおいて統合したゲート公開鍵により、この計算装置が生成したゲート秘密鍵を暗号化するゲート秘密鍵の暗号化ステップと、
前記ゲート秘密鍵の暗号化ステップにおいて生成したゲート秘密鍵の暗号文を公開するゲート秘密鍵の暗号文の公開ステップと、
前記ゲート秘密鍵の暗号文の正当性証明を生成するゲート秘密鍵の暗号文の正当性の証明生成ステップと、
前記ゲート秘密鍵の暗号文の正当性の証明生成ステップにおいて生成したゲート秘密鍵の暗号文の正当性の証明を公開するゲート秘密鍵の暗号文の正当性の証明公開ステップと、
各計算装置に入力された回路の入力の部分に対応する暗号文を生成する入力の暗号文生成ステップと、
前記入力の暗号文生成ステップにて生成した回路の入力の部分に対応する暗号文の正当性の証明を生成する入力の暗号文の正当性の証明生成ステップと、
前記入力の暗号文の正当性の証明生成ステップにおいて生成した証明を公開する入力の暗号文の正当性の証明公開ステップと、
出力のゲートに対応する暗号文を生成して公開する出力の暗号文の生成ステップと、を含み、
前記置換再暗号処理が、
前記ゲート秘密鍵の暗号文の集合の順番をあらかじめ決められた許された置換の方法から無作為に一つの置換を選んで入れ替えて再暗号化するゲート秘密鍵の暗号文の置換と再暗号化ステップと、
前記入力の暗号文の集合の順番をあらかじめ決められた許された置換の方法から無作為に一つの置換を選んで入れ替えて再暗号化する入力の暗号文の置換と再暗号化ステップと、
前記出力の暗号文の集合の順番をあらかじめ決められた許された置換方法から無作為に一つの置換を選んで入れ替えて再暗号化する出力の暗号文の置換と再暗号化ステップと、
前記ゲート秘密鍵の暗号文の置換と再暗号化ステップと入力の暗号文の置換と再暗号化ステップと出力の暗号文の置換と再暗号化ステップとにおいてなされた置換と再暗号化の正当性の証明を生成し公開するゲート秘密鍵の暗号文と入力の暗号文と出力の暗号文の置換と再暗号化の正当性の証明生成と公開ステップと、を含み、
前記結果出力処理の部分復号ステップが、
前記計算装置が互いに通信及び計算することで前記ゲート秘密鍵の暗号文を部分復号するゲート秘密鍵の部分復号ステップと、
前記計算装置が互いに通信及び計算することで前記入力の暗号文を部分復号する入力の暗号文の部分復号ステップと、
前記計算装置が互いに通信及び計算することで前記出力の暗号文を部分復号する出力の暗号文の部分復号ステップと、
前記ゲート秘密鍵の部分復号ステップと入力の暗号文の部分復号ステップと出力の暗号文の部分復号ステップとでなされた部分復号の正当性の証明を生成し公開するゲート秘密鍵と入力の暗号文と出力の暗号文の部分復号ステップの正当性の証明生成と公開ステップと、を含み、
他の計算装置の公開した種々の正当性の証明を検証するステップを含む、こととしてもよい。
本発明の計算システムは、複数の計算装置と、
複数の計算装置と通信する手段と、
入力処理手段と、
ＥｌＧａｍａｌ暗号文準備手段と、
置換再暗号処理手段と、
結果出力処理手段と、からなる関数を評価する計算システムであって、
前記入力処理手段は、出力を求めたい回路の情報と、前記複数の計算装置に関する情報と、前記複数の計算装置がそれぞれ前記回路の入力のどの部分を所持しているかという情報と、を入力し、
前記ＥｌＧａｍａｌ暗号文準備処理手段は、与えられた関数を実現する回路のゲートに対応したＥｌＧａｍａｌ暗号文の集合を生成するＥｌＧａｍａｌ暗号文を準備し、
前記置換再暗号処理手段は、
順番が回ってきた計算装置が、一つ前の順番に対応する計算装置からＥｌＧａｍａｌ暗号文の集合を受け取る暗号文取得手段と、
前記暗号文取得手段により受け取られた暗号文の集合の順序を入れ替えて置換し、それらを再暗号化する暗号文の置換と再暗号化手段と、
前記暗号文の置換と再暗号化手段を用いて生成したデータを、少なくとも次の順番の計算装置に公開する手段と、からなり、
前記結果出力手段は、
置換再暗号処理手段で生成された暗号文の一部を復号あるいは部分復号する部分復号手段と、
前記前記逐次置換再暗号処理で生成された暗号文の中で前記回路の入力に対応するデータを暗号化している暗号文の自分に関する暗号化を復号する復号手段と、
前記複数の計算機が前記復号手段で復号したデータと前記複数の計算機が前記部分復号手段で部分復号されたデータを用いて回路の出力を評価する回路の評価手段と、からなることを特徴とする。
本発明の他の形態による計算システムは、複数の計算装置、入力手段、出力手段を含み、まず一台の前記計算装置が計算を行い、その計算結果を他の前記計算装置のうち一台に送り、次にその計算結果を受け取った前記前記計算装置がその次の計算を行う、というとように一台ずつ順に計算を行ってその計算結果を次の一台に回し、全ての前記計算装置が一度ずつ計算が終わったら、最後に計算をした計算装置が最初に計算をした計算装置に計算結果を送り、以後何度も、一台ずつ順に計算を行ってその計算結果を次の一台に回すという各周の計算を繰り返す計算システムであって、
前記入力手段では前記計算装置に回路の情報と、前記回路への入力ビットの一部とが入力され、
第ゼロ周目の計算は第一の計算装置が第一周目の計算を行う前に行い、
前記複数の計算装置には、
前記各周の計算に使用される送られてきたデータを取得するデータ取得手段と、正当性証明検証手段と、署名文検証手段と、第一の計算装置のみが行う第一計算装置特別計算手段と、乱数生成を行う乱数生成手段と、本計算を行う本計算計算手段と、本計算で行った計算の正当性を証明する正当性証明作成手段と、署名手段とデータ送信手段とからなり、
前記送られてきたデータは、別の計算装置から送られてきたデータと、データ本体と、データ本体に対する正当性証明と、署名文とからなり、
前記署名文は、前記別の計算装置から送られてきたデータと、前記データ本体と、前記データ本体に対する正当性証明との組に対する署名文であるようなデータで、
前記正当性証明検証手段は前記送られてきたデータ中の正当性証明を検証し、
前記署名検証手段は、前記送られてきたデータ中署名文を検証し、
前記本計算は前記乱数生成手段で生成された乱数を用いて計算し、
前記署名手段が、前記送られてきたデータと、前記本計算で計算された計算結果であるデータ本体と、前記正当性証明作成手段で作成された正当性証明との組に対する署名文を作成し、
前記データ送信手段が、前記送られてきたデータと、前記本計算で計算された計算結果であるデータ本体と、前記正当性証明作成手段で作成された正当性証明と前記署名手段で作成された署名文との組を送信する事を特徴とする。
この場合、前記送られてきたデータのデータ本体と前記本計算で計算されたデータ本体とが、第一周目の計算では、共に真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組であるとしてもよい。
また、各周の計算が、第一周目の計算手段と、第一周目以降の周の計算手段とからなり、
前記計算手段は、第ゼロ周目の計算手段では真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組を作成し、前記第一周目の計算手段が再暗号に使用する為の公開鍵を作成する再暗号用公開鍵作成手段と、送られてきたデータを変換するデータ変換手段と、秘密鍵変換手段と、乱数変換手段とからなり、
前記データ変換手段が、前記データ本体である暗号文の組を、真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる別の組に変換する為の手段であり、
前記秘密鍵変換手段が、前記データ変換手段の計算結果である暗号文達の組に使用されている秘密鍵を再暗号用公開鍵作成手段で作成された公開鍵に対応する秘密鍵に変換する手段であり、
前記秘密鍵変換手段の計算結果が真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組であり、
前記乱数変換手段が前記データ変換手段の計算結果である暗号文達の組に使用されている乱数を変換する手段であり、
前記乱数変換手段の計算結果が真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組であるとしてもよい。
また、第一周目以降の周の計算手段が、第二周目の計算手段と第二周目以降の計算手段とからなり、
前記送られてきたデータのデータ本体と前記本計算で計算されたデータ本体とが、第二周目の計算では、共に真理値群環上の多重配列エルガマル暗号文達と真理値群環上の拡張多重配列エルガマル暗号文達とからなる組であり、
前記第二周目の計算手段が、
前記送られてきたデータの前記データ本体を変換してエルガマル暗号文もしくは楕円曲線エルガマル暗号文を作成する暗号変換手段と、前記送られてきたデータのデータ本体の暗号文達を部分復号する部分復号手段とからなるとしてもよい。
さらに、第二周目以降の計算手段が、第三周目の計算手段のみからなり、第三周目の計算手段の前記本計算手段が、前記送られてきたデータをそのまま出力し、
前記正当性証明作成手段が空列を出力するとしてもよい。
本発明の多数の入力から関数を計算する方法は、ＥｌＧａｍａｌ暗号方式を利用して、その値を隠したゲートの入出力の対応表を生成する手段とを備え、各入力を持った装置が次々と順番に、図５に示すようにＥｌＧａｍａｌ暗号文の集合からなる対応表の順番を入れ替えるよう動作する。このような構成を採用し、各装置に分配された入力に対する関数の出力を計算することにより本発明の目的を達成することができる。
【発明の効果】
第１の効果は、各計算装置の計算量と通信量が回路のゲート数に比例するに留まり、効率的であることにある。
その理由は、各ゲート毎にゲートの入出力の対応表をＥｌＧａｍａｌ暗号文で生成し、疑似乱数生成装置を用いなかったため、この対応表の計算の正当性を第三者に証明するのが容易になったためである。
第２の効果は、各計算装置の他の計算装置との通信回数が、計算する回路のゲート数に依らず定数回に留まり、効率的であることにある。
その理由は、各ゲートの入出力の対応表の対応関係がいずれの計算装置にも分からなくなる操作が必要であるが、この操作が各計算装置が順番に対応関係を入れ替える操作を行えば実現されるからである。
【図面の簡単な説明】  図１は非特許文献１の従来の技術を説明したフローチャートである。
図２は非特許文献１の従来の技術における、ガーブルド回路並列構築処理における、計算フェーズと通信フェーズの関係を示した図である．同じ番号が振られた計算装置が複数回記述されているが、これらは同一のもので、動作する時間が異なっているだけである．本図において、時は上から下へ流れるよう記述されている。
図３は非特許文献２の従来の技術を説明したフローチャートである。
図４は非特許文献２の従来の技術を説明したフローチャート「図（３）」における並列したランク判定処理の中で、並列して多数回行われる処理を一つだけ取り出して記述したフローチャートである。
図５は本明細書提案の技術が従来方法の問題を解決するために考案した計算処理の流れを示すブロック図である。
図６は第１の発明を実施するための最良の形態の動作の具体例を示すフローチャートである。
図７は第１の発明を実施するための最良の形態の動作の具体例における、ＥｌＧａｍａｌ暗号文準備処理の詳細を示すフローチャートの前半である。
図８は第１の発明を実施するための最良の形態の動作の具体例における、ＥｌＧａｍａｌ暗号文準備処理の詳細を示すフローチャートの後半である。
図９は第１の発明を実施するための最良の形態の動作の具体例における、逐次置換再暗号処理の詳細を示すフローチャートの前半である。右の吹き出しの中に示されたフローチャートの処理を、各計算装置が順番に行う。
図１０は第１の発明を実施するための最良の形態の動作の具体例における、結果出力処理の詳細を示すフローチャートである。
図１１は第１の発明を実施するための最良の形態の構成を示すブロック図である。
図１２は第１の発明を実施するための最良の形態の構成を構成する計算装置の構成を示すブロック図である。
図１３は第１の発明を実施するための最良の形態の動作の具体例における、入力処理の詳細を示すフローチャートである。
図１４は第二の発明の装置の関係を示したブロック図、
図１５は第二の発明で、各計算装置が一周目から三周目までの各周で行う計算のフローチャート、
図１６は第二の発明におけるデータの流れ、
図１７は一周目の本計算のフローチャート、
図１８は二周目の本計算のフローチャート、
図１９は従来の技術における各ゲートに関して計算されるデータの理解を助けるための図である。
【発明を実施するための最良の形態】  次に、本発明の実施例について図面を参照して説明する。
【実施例１】  本発明の第１の実施例について、図６ないし図１３を用いて説明する。
［準備］
［システム構成］
図１１に示すように、計算装置３０８がλ個あり、それぞれ通信手段３０７を備えている。以下ではこの計算機を順番に、
0004835831.tif 000019
と呼ぶことにする。計算装置数、各計算装置と対応する添字αとの関係等をシステムの構成情報と呼ぶ。
［回路の情報］
後の説明で、回路の情報が各計算装置
0004835831.tif 000020
に入力されるが、この回路の情報を説明する。
まず、入力される回路の情報が表現する回路をｆと呼ぶことにする。ｆはｍ個の論理ゲートで構成されている回路とする。各ゲートをＧ１，．．．，Ｇｌ，．．．，Ｇｍと呼ぶ。ここでは各ゲートは２入力１出力であるとする。この様なゲートで回路が構成されていなかった場合は、各ゲートを複数の２入力１出力のゲートからなる等価な回路に置き換える。この置き換え方法は明らかなので省略する。また回路のあるゲートから他のゲートの入力へ信号を送る配線は、０または１に対応する信号を送るとする。Ｇ「ｋ」の出力配線をｗ〔ｋ〕とする。ｆに入力される配線の本数をｎ個とし、これを｛ｗ〔ｋ〕｝ｋ＝ｍ＋１，．．．，ｍ＋ｎとする。配線は途中で分岐して二つ以上のゲートに入力していても良い。配線〔ｋ〕は分岐しても同じ信号を送信するものとし、この分岐した配線をまとめてｗ〔ｋ〕と呼ぶ。ｗ〔１〕，．．．，ｗ〔ｌ〕を回路ｆの出力とする。回路の配線は全て、ゲートの出力配線か回路への入力配線のいずれかであるので、配線全て｛ｗ〔ｋ〕｝ｋ＝１，．．．，ｍ＋ｎが配線の全てである。
ゲートＧｋにゲートＧｉとゲートＧｊの出力が入力されたとき、すなわち、配線ｗ〔ｉ〕と配線ｗ〔ｊ〕がゲートＧｋに入力され、配線ｗｋがＧｋの出力のための配線として繋がっているときに、Ｇｉの出力ｂ「ｉ」、Ｇｊの出力ｂ「ｊ」、とＧｋの出力ｂ「ｋ」の間の関係を、ｂ「ｋ」＝ｂ「ｉ」◎Ｇ「ｋ」ｂ「ｊ」とし、各計算装置ｕ（α）は、ｆに入力する信号の一部を持っているものとする。すなわち、配線｛ｗ〔ｋ〕｝ｋ＝ｍ＋１，．．．，ｍ＋ｎのうちの一部に伝搬させる信号を知っているとする。
ｕ（α）がｆへ入力するビットの個数をｌα個とし、全ての計算装置の持つ入力を集めると、回路への入力全てとなるとする。すなわち、
0004835831.tif 000021
となる。ｋ＝ｍ＋１，．．．，ｍ＋ｎに関して各ｗ〔ｋ〕に入力されるビットをｂ「ｋ」とし、それぞれのビットをｕ（α）にｌα個ずつ次のように割り振る。すなわち、ｕ（α）は集合
0004835831.tif 000022
を決定する。ゲートの番号の割り振りを変更しても回路は本質的に変わらないため、上記のように入力を割り振っても一般性は損なわれない。
上記ｍ個のゲートＧ１，．．．，Ｇｍ、それぞれのゲートの行う演算◎Ｇ［ｋ］、それぞれのゲートに繋がる配線｛ｗ〔ｋ〕｝ｋ＝ｍ＋１，．．．，ｍ＋ｎ，入力配線の計算装置に対する割り振り｛ｌα｝α＝，．．．，λを回路の情報３００と呼ぶ。
［演算に用いる群］
本実施例では、楕円曲線上での演算を利用するのでこれを説明する。しかし、これは本発明を実施するためにはこれは必ずしも必須ではない。これに代替となるものとして、素体上の演算等、可換な乗法群であれば良い。
以降、Ｅを位数が素数ｑである楕円曲線、ＯをＥの無限遠点、Ｇ（≠Ｏ）をＥ上の点とする。ｑは、暗号学的に安全とされるに十分な大きさであるとする。楕円曲線Ｅ上の点からＺ／ｑＺ上への写像をψとする。ψは、その像の空間が十分に大きいものを選ぶ。ψの例として、楕円曲線Ｅ上の点の座標の片方の値を使う等がある。ｈをＺ／ｑＺの要素、Ｇを楕円曲線上の点としたとき、Ｇのｈ倍点を［ｈ］Ｇと表す。
［記法］
文字の右肩に記された文字は上付きの添字であって、冪乗を表す指数ではない。また、□はｂｉｔの排他的論理和を表すとする。
［入力処理２０３，３１２］
処理が開始されると、図６に示されるように、まず、入力処理２０３が行なわれる。この入力処理２０３について、処理を詳細に示す図１２および図１３を参照して説明する。
ＥｌＧａｍａｌ暗号文準備処理では情報公開手段と公開情報取得手段を使って、データの公開と取得の両方を行う（３０９）。
［領域変数の決定］
計算はＥ，Ｇ及びψを決定する。また、ハッシュ関数を利用する等の方法で、誰もがＨ＝［ｈ］ＧなるＺ／ｑＺの元ｈが分らない様な楕円曲線上の点Ｈを決定する。これらの値Ｅ，Ｇ，Ｈ，ψを領域変数３０１と呼ぶ。これらはあらかじめ全ての計算装置に格納しておく（図１３の１００）。
［回路の情報及び、回路の部分入力の入力］
回路ｆの情報及びシステムの構成情報が全ての計算装置に入力される（図１３の１０１）。
0004835831.tif 000023
を入力する（図１３の１０２）。
［ＥｌＧａｍａｌ暗号文準備処理２００，３０３］
［ゲート毎の秘密鍵と公開鍵設定］
次に、図６に示されるように、ＥｌＧａｍａｌ暗号文準備処理２００が行なわれる。このＥｌＧａｍａｌ暗号文準備処理２００について、処理を詳細に示す図７および図８を参照して説明する。
各計算装置ｕ（α）は、全てのｋ＝１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝に関して、ゲート秘密鍵
0004835831.tif 000024
を一様無作為に生成し（図７の１０３）、全てのｋ＝１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝に関して，
0004835831.tif 000025
を生成し、全てのｋ＝１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝に関して、ゲート公開鍵
0004835831.tif 000026
を生成し（図７の１０４）、各計算装置ｕαは各自の生成したゲート公開鍵をそれぞれ、情報公開装置を用いて公開する（図７における１０５）。以降本実施例１では公開するとは、情報公開装置を用いて公開することである。
併せて計算装置ｕ（α）は、各Ｙ（α）ｂ〔ｋ〕，Ｚ（α）に関してｘ（α）ｂ〔ｋ〕，ｚ（α）の知識の証明を、別記述Ａの方法に従って、ゲート公開鍵の正当性証明として生成（図７における１０６）し、公開（図７の１０７）する。
［入力の公開鍵設定］
各計算装置ｕ（α）は、全ての
0004835831.tif 000027
に関して、入力されたｂ「ｋ」∈｛０，１｝を用いて入力ゲートの秘密鍵
0004835831.tif 000028
を一様無作為に生成し（図７の１０８）、入力ゲートの公開鍵
0004835831.tif 000029
を生成し（図７の１０９）、全てのｋ＝ｍ＋１＋Σβ＝１α−１｜β，．．．，ｍ＋Σβ＝１α｜β全てのｂ∈｛０，１｝に関して、Ｙ〜ｂ〔ｋ〕を各計算装置の入力ゲートの公開鍵として公開する（図７の１１０）。
併せて、計算装置ｕ（α）は、各ｋに関して、ｂ「ｋ」＝０、または、ｂ「ｋ」＝１に対して、
0004835831.tif 000030
の知識を持っていることの証明を、別記述Ｂの方法に従って、入力ゲートの公開鍵の正当性証明として生成（図７の１１１）し、公開する（図７の１１２）。
［ゲートに関する処理］
全ての計算装置｛ｕα｝は、公開情報取得手段を用いて、ゲート公開鍵
0004835831.tif 000031
を取得する（図８の１１３）。全てのｋ＝１，．．．，ｍと全てのｂ∈｛０，１｝に関して、各自統合したゲート公開鍵
0004835831.tif 000032
を生成する（図８の１１４）。
全ての計算装置｛ｕα｝は、全てのｋ＝１，．．．，ｍ、全てのε∈｛０，１｝に関して、
0004835831.tif 000033
を一様無作為に生成して、全てのｋ＝１，．．．，ｍ、全てのｂ，ｃ，ε∈｛０，１｝に関して、楕円ＥｌＧａｍａｌ暗号方式にて暗号化することで、ゲート秘密鍵の暗号文
0004835831.tif 000034
を生成し（図８の１１５）、これらを公開する（図８の１１６）。但し、ゲートＧ〔ｋ〕には配線ｗ〔ｉ〕とｗ〔ｊ〕が入力されるとする。
併せて、それぞれのｋに関して、全てのｂ，ｃ∈｛０，１｝に関して、楕円ＥｌＧａｍａｌ暗号文
0004835831.tif 000035
の復号結果が同じになること、それぞれのｋに関して、全てのｂ，ｃ∈｛０，１｝に関して、楕円ＥｌＧａｍａｌ暗号文
0004835831.tif 000036
の復号結果が同じになることの証明を、別記述Ｃの方法を用いて、ゲート秘密鍵の暗号文の正当性証明として生成し（図８の１１７）、公開する（図８の１１８）。
全ての計算装置｛ｕα｝は各自、全てｋ＝１，．．．，ｍ、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関して、秘密鍵識別データ暗号文
0004835831.tif 000037
を生成する（図８の１１９）。但し、
0004835831.tif 000038
［入力配線に関する処理］
全ての計算装置｛ｕα｝は、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのε∈｛０，１｝に関して
0004835831.tif 000039
を一様無作為に生成し、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのｂ，ε∈｛０，１｝に関して楕円ＥｌＧａｍａｌ暗号方式を用いて、入力の暗号文
0004835831.tif 000040
を生成し（図８の１２０）、これらを公開する（図８の１２１）。併せて、それぞれのｋに関して、全てのｂ∈｛０，１｝に関して、楕円ＥｌＧａｍａｌ暗号文
0004835831.tif 000041
の復号結果が同じになること、それぞれのｋに関して、全てのｂ∈｛０，１｝に関して、楕円ＥｌＧａｍａｌ暗号文
0004835831.tif 000042
の復号結果が同じになることの証明を、別記述Ｄの方法で、入力の暗号文の正当性証明として生成し（図８の１２２）、公開する（図８の１２３）。
全ての計算装置｛ｕα｝は各自、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのｂ，ξ∈｛０，１｝に関して、入力の暗号文識別データの暗号文
0004835831.tif 000043
を生成する（図８の１２４）。但しε＝ｂ□ξ．
［出力配線に関する処理］
全ての計算装置｛ｕα｝は各自、全ての配線ｋ＝１，．．．，ｌ、全てのｂ，ε∈｛０，１｝に関して、出力の暗号文
0004835831.tif 000044
を生成する（図８の１２５）。但しε＝ｂ□ξ．
［逐次置換再暗号処理２０１−−−ゲート暗号文の置換と再暗号］
次に、図６に示されるように、逐次置換再暗号処理２０１が行なわれる。この逐次置換再暗号処理２０１について、処理を詳細に示す図９および図１２を参照して説明する。
α＝１，．．．，λに関して順番に、計算装置ｕαは以下の処理（図１２の３０４）を行う（図９の１２６）。この処理で各計算装置は、最初に公開情報取得手段を用いて必要なデータを取得し（図１２の３１０）、次に生成したデータを情報公開手段を用いて公開する（図１２の３１１）。λ個の計算装置には順番が定められており、それぞれの計算装置がデータを取得するには、この計算機よりも順番が前の計算機全てがデータの公開を終了しておかねばならない。
［暗号文取得処理］
ｕαは、ｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関する
0004835831.tif 000045
全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λ、全てのｂ，ξ∈｛０，１｝に関する
0004835831.tif 000046
全てのｋ＝１，．．．，ｌ、全てのｂ，ξ∈｛０，１｝に関する
0004835831.tif 000047
を取得する（図９の１５１）。
［配線の信号値と置換生成］
ｕαは、各配線の信号値の置換｛ＴＴ（ｋ）∈Ｒ｛０，１｝｝ｋ＝１，．．．，ｍ＋ｎを一様無作為に生成する（図９の１２７）。
［再暗号化の乱数生成］
ｕαは、ゲートの秘密鍵の再暗号化に使う乱数
0004835831.tif 000048
を一様無作為に生成する（図９の１２８）。
［ゲートの秘密鍵の暗号文の置換と再暗号化］
全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関して、
0004835831.tif 000049
と、ゲート秘密鍵を置換し再暗号化したデータを生成し（図９の１２９）、
［入力の暗号文の置換と再暗号化］
全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λ、全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000050
と、入力の暗号文を置換し再暗号化したデータを生成し（図９の１３０）、
［出力の暗号文の置換と再暗号化］
全てのｋ＝１，．．．，ｌ、全てのｂ，ξ∈｛０，１｝に関して，
0004835831.tif 000051
と、出力の暗号文を置換し再暗号化したデータを生成し（図９の１３１）、
［置換と再暗号化の正当性証明］全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関する
0004835831.tif 000052
及び、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λ、全てのｂ，ξ∈｛０，１｝に関する
0004835831.tif 000053
及び全てのｋ＝１，．．．，ｌ、全てのｂ，ξ∈｛０，１｝に関するＡ†（α）ｂ〔ｋ〕ξ，Ｂ†（α）ｂ〔ｋ〕ξをｕα＋１に送信する。
併せて上記処理を正当に行ったことの証明を、別記述Ｅの方法に従って、ゲートの秘密鍵の暗号文と入力の暗号文と出力の暗号文との置換と再暗号化の正当性証明として生成し公開する（図９の１３２）。
［結果出力処理２０２，３０５］
次に、図６に示されるように、結果出力処理２０２が行なわれる。この結果出力処理２０２について、処理を詳細に示す図１０ないし図１２を参照して説明する。
結果出力処理２０２では情報公開手段と公開情報取得手段を使って、データの公開と取得の両方を行う（図１２の３１２）。最後に、各自回路の出力（図１２の３０６）を出力する（図１２の３１３）。
［ゲート暗号文の部分復号］
全ての計算装置｛ｕα｝α＝１，．．．，λは、全てのｋ＝１，．．．，ｍ，ｂ，ｃ∈｛０，１｝，β＝１，．．．，λに関して、
0004835831.tif 000054
と、ゲート秘密鍵を部分復号し、結果を公開し（図１０の１３４）、全ての計算装置｛ｕα｝α＝１，．．．，λは、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ，ｂ∈｛０，１｝，β＝１，．．．，λに関して
0004835831.tif 000055
と、入力の暗号文を部分復号し、結果を公開し（図１０の１３５）、全ての計算装置｛ｕα｝α＝１，．．．，λは、ｋ＝１，．．．，ｌ，ｂ∈｛０，１｝に関して
0004835831.tif 000056
と、出力の暗号文を部分復号し、結果を公開する（図１０の１３６）。
併せて上記処理を正当に行ったことの証明を別記述Ｆの方法に従って、ゲート秘密鍵と入力の暗号文と出力の暗号文との部分復号の正当性証明として生成し公開する（図１０の１３７）。
［ゲート暗号文の生成］
全ての計算装置は、さらに全てのｋ＝１，．．．，ｍ，全てのα＝１，．．．，λ、全てのｂ，ｃ，∈｛０，１｝に関して、
0004835831.tif 000057
を、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのα＝１，．．．，λ、全てのｂ∈｛０，１｝に関して、
0004835831.tif 000058
を、全てのｋ＝１，．．．，ｌ、全てのｂ∈｛０，１｝に関して、
0004835831.tif 000059
をゲート暗号文として生成する（図１０の１３８）。
［入力の復号］
各計算装置ｕ（α）は、全てのｋ＝ｍ＋１＋ΣＹ＝１α−１｜Ｙ，．．．，ｍ＋ΣＹ＝１α｜Ｙ、全てのβ＝１，．．．，λに関して、ｂ「ｋ」を開示することなく
0004835831.tif 000060
を生成し、公開する（図１０の１３９）。この公開したデータは入力の暗号文を復号したデータと呼ぶ。
全ての計算装置ｕαは、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λに関して、
0004835831.tif 000061
を確認することで、入力の暗号文の復号の正当性を確認する（図１０の１４０）。但し、もしＧｂ〔ｋ〕＝０ならεｋ＝０，Ｇｂ〔ｋ〕＝Ｇならεｋ＝１とする。
［回路の評価］
全ての計算装置ｕαはそれぞれ、全てのゲートＧｋｋ＝１，．．．，ｍに関して適切な順番に、それらの入力から出力を以下のように求めていく（図１０の１４１）。これが回路の評価の処理である。但しゲートＧｋにはゲートＧｉとゲートＧｊの出力が入力されるとする。
全てのβ＝１，．．．，λに関して、
0004835831.tif 000062
を求め（図１０の１４２）、β＝１，．．．，λに関して，Ｙ（β）ε「ｋ」〔ｋ〕＝［ｘｂ（β）〔ｋ〕］Ｇを確認する（図１０の１４３）。但し、もしＧｂ〔ｋ〕＝０ならεｋ＝０，Ｇｂ〔ｋ〕＝Ｇならεｋ＝１とする。上記処理を行ったｋに関して、ｂ「ｋ」＝εｋとする。
［出力の評価］
ここまでの処理で公開した証明を検証者は検証する（図１０の１４４）。検証者が全ての証明文を受理したならば、すなわち不正が発見されなかったならば、以下の出力の復号と公開の処理を行う。
全ての計算装置ｕαはそれぞれ、全てのｋ＝１，．．．，ｌに関して，
0004835831.tif 000063
を求める（図１０の１４５）。
全ての｛ｕα｝α＝１，．．．，λはそれぞれ、全てのｋ＝１，．．．，ｌに関して，
0004835831.tif 000064
を生成して（図１０の１４６）公開する（図１０の１４７）。
併せてこの計算の正当性の証明を、別記述Ｇの方法に従って、出力の復号の正当性の証明生成と（図１０の１４８）して公開する（図１０の１４９）。
それぞれのｕαは、各自
0004835831.tif 000065
から回路の出力（図１１の３０６）を求める（図１０の１５０）。
ｋ＝１，．．．，ｌに関して、Ｇ♪〔ｋ〕＝０ならばｂ「ｋ」＝０であり、Ｇ♪〔ｋ〕＝Ｇならばｂ「ｋ」＝１である。
［別記述処理］
［別記述Ａ］
証明者（計算者）ｕαは、全てのｋ＝１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝に関して，
0004835831.tif 000066
を一様無作為に生成し，
0004835831.tif 000067
を生成する。さらに，
0004835831.tif 000068
を生成し、全てのｋ＝１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝に関して、
0004835831.tif 000069
を生成する。証明者は、全てのｋ＝１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝に関する
0004835831.tif 000070
を証明とする。上記証明の検証方法は以下の通り。検証者は、
0004835831.tif 000071
を計算して、
0004835831.tif 000072
を確認する。
［別記述Ｂ］
各証明者（計算者）ｕ（α）は、全てのｋ＝ｍ＋１＋Σβ＝１α−１｜β，．．．，ｍ＋Σβ＝１α｜βに関して、選択したｂ「ｋ」∈｛０，１｝に対して，
0004835831.tif 000073
を一様無作為に生成し、
0004835831.tif 000074
を生成する。さらに、
0004835831.tif 000075
を無作為に生成し，
0004835831.tif 000076
を生成する。
ｕαは、全てのｋ＝ｍ＋１＋Σβ＝１α−１｜β，．．．，ｍ＋Σβ＝１α｜βに関して、
0004835831.tif 000077
を生成する。さらに、
0004835831.tif 000078
を生成する。
証明者ｕαは、全てのｋ＝ｍ＋１＋Σβ＝１α−１｜β，．．．，ｍ＋Σβ＝１α｜β，ｂ＝０，１に関する
0004835831.tif 000079
を証明とする。
上記証明の検証方法は以下の通り。
検証者は、全ての
0004835831.tif 000080
に関して、
0004835831.tif 000081
を生成し、全ての
0004835831.tif 000082
に関して、
0004835831.tif 000083
が成り立つことを確認する。
［別記述Ｃ］
証明者（計算者）ｕαは、全てのｋ＝１，．．．，ｍ、全てのε＝０，１に関して、
0004835831.tif 000084
を一様無作為に生成して、
0004835831.tif 000085
を生成する。
さらに、
0004835831.tif 000086
を生成する。
次に、
0004835831.tif 000087
を生成する。証明者は、ｋ＝１，．．．，ｍ及びε＝０，１に関する
0004835831.tif 000088
を証明とする。
上記証明の検証方法は以下の通り。
検証者は、最初にそれぞれのε＝０，１、及びｋ＝１，．．．，ｍに関して、全てのｂ，ｃ＝０，１に対する
Ｃ（α）ｂｃε〔ｋ〕が全て同じ値であることを確認する。
次に、
0004835831.tif 000089
を生成する。次に、すべてのｋ＝１，．．．，ｍ及びε＝０，１に関して
0004835831.tif 000090
が成り立つことを確認する。
［別記述Ｄ］
証明者（計算者）ｕαは、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのｂ，ε＝０，１に関して、
0004835831.tif 000091
を一様無作為に生成して，
0004835831.tif 000092
を生成する。さらに、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎに関して
0004835831.tif 000093
を生成する。
次に、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのｂ，ε＝０，１に関して，
0004835831.tif 000094
を生成する。証明者は、ｋ＝ｍ＋１，．．．，ｍ＋ｎ及びε＝０，１に関する
0004835831.tif 000095
を証明とする。
上記証明の検証方法は以下の通り。検証者は、最初にそれぞれのε＝０，１、及びｋ＝１，．．．，ｍに関して、全てのｂ＝０，１に対する
0004835831.tif 000096
が全て同じ値であることを確認する。
次に、
0004835831.tif 000097
を生成する。
次に、すべてのｋ＝ｍ＋１，．．．，ｍ＋ｎ及びＥ＝０，１に関して
0004835831.tif 000098
が成り立つことを確認する。
［別記述Ｅ］
α＝１，．．．，λに関して順番に、計算者ｕαは以下の処理を行う。
ｕαは、
0004835831.tif 000099
なる
0004835831.tif 000100
をＺ／ｑＺから一様無作為に選び，全てのｋ＝１，．．．，ｍ、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関して，
0004835831.tif 000101
を生成する。
次に、全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．，λ、全てのｈ＝２／３，１／３，０、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関して、
0004835831.tif 000102
をＺ／ｑＺから一様無作為に選び，全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｂ，ｃ，μ，ｖ，ξ∈｛０，１｝に関して，
0004835831.tif 000103
を生成する。
さらに全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λ全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000104
をＺ／ｑＺから一様無作為に選び，全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ，全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000105
を生成する。さらに全てのｋ＝１，．．．，ｌ，全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000106
をＺ／ｑＺから一様無作為に選び、全てのｋ＝１，．．．，ｌ，全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000107
を生成する。
次に、全てのｋ＝１，．．．，ｍ、全てのｈ＝２／３，１／３，０に関して、
0004835831.tif 000108
をＺ／ｑＺから一様無作為に選ぶ。
次に、全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｂ，ｃ，μ，ν，ξ∈｛０，１｝に関して、
0004835831.tif 000109
をＺ／ｑＺから一様無作為に選ぶ。
次に、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λ、全てのｂ，ξ∈｛０，１｝に関して，
0004835831.tif 000110
をＺ／ｑＺから一様無作為に選ぶ。次に、全てのｋ＝１，．．．，ｌ、全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000111
をＺ／ｑＺから一様無作為に選ぶ。
次に、全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｂ，ｃ，μ，ν，ξ∈｛０，１｝に関して、
0004835831.tif 000112
を生成する。
次に、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．．，λ、全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000113
を生成する。
次に、全てのｋ＝１，．．．，ｌ、全てのｂ，ξ∈｛０，１｝に関して、
0004835831.tif 000114
を生成する。
次に、
0004835831.tif 000115
を生成する。
次に、各ｕαは、全てのｋ＝１，．．．，ｍ＋ｎに関して
0004835831.tif 000116
を生成する。
次に、全てのｋ＝１，．．．，ｍ＋ｎに関して
0004835831.tif 000117
を生成する。次に、全てのｋ＝１，．．．，ｍ、全てのβ＝１，．．．，λ、全てのｈ＝２／３，１／３，０、全てのｂ，ｃ，μ，ν，ξ∈｛０，１｝に関して、
0004835831.tif 000118
を生成する。
次に、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのβ＝１，．．，λ、全てのｂ，ξ∈｛０，１｝に関して，
0004835831.tif 000119
を生成する。
次に、全てのｋ＝１，．．．，ｌ、全てのｂ，ξ∈｛０，１｝に関して，
0004835831.tif 000120
を生成する。
最後に、全ての
0004835831.tif 000121
に関する
0004835831.tif 000122
及び、全ての
0004835831.tif 000123
に関する
0004835831.tif 000124
及び、全ての
0004835831.tif 000125
に関する
0004835831.tif 000126
及び，全てのｋ＝１，．．．，ｍ＋ｎに関する
0004835831.tif 000127
を証明とする。上記証明の検証方法は以下の通り。
検証者は、
0004835831.tif 000128
を生成し、各ｕαは、全てのｋ＝１，．．．，ｍ＋ｎに関して
0004835831.tif 000129
を生成し、全てのｋ＝１，．．．，ｍに関して、
0004835831.tif 000130
が成り立つことを確認する。検証者は次に、
0004835831.tif 000131
に関して
0004835831.tif 000132
が成り立つことを確認する。
検証者は次に、
0004835831.tif 000133
に関して
0004835831.tif 000134
が成り立つことを確認する。検証者は次に、
0004835831.tif 000135
に関して
0004835831.tif 000136
が成り立つことを確認する。
［別記述Ｆ］
0004835831.tif 000137
てのβ＝１，．．．，λに関して
0004835831.tif 000138
を生成し、全てのｋ＝ｍ＋１，．．．，ｍ＋ｎ、全てのｂ∈｛０，１｝、全てのβ＝ｉ，．．．，λに関して
0004835831.tif 000139
を生成し、全てのｋ＝１，．．．，ｌ、全てのｂ∈｛０，１｝に関して
0004835831.tif 000140
を生成する。
0004835831.tif 000141
を生成し、さらに
0004835831.tif 000142
を生成する。さらに
0004835831.tif 000143
を生成する。証明者は、
0004835831.tif 000144
を証明とする。上記証明の検証方法は以下の通り。
検証者は、
0004835831.tif 000145
を生成し、さらに
0004835831.tif 000146
を計算して、
0004835831.tif 000147
全ての
0004835831.tif 000148
に関して
0004835831.tif 000149
全ての
0004835831.tif 000150
に関して
0004835831.tif 000151
全てのｋ＝１，．．．，ｌ，ｂ∈｛０，１｝に関して
0004835831.tif 000152
を確認する。
［別記述Ｇ］
0004835831.tif 000153
して，
0004835831.tif 000154
を生成する。証明者は、
0004835831.tif 000155
を生成して、
0004835831.tif 000156
を生成する。証明者は
0004835831.tif 000157
を生成する。証明者
0004835831.tif 000158
を証明とする。上記証明の検証方法は以下の通り。検証者は、
0004835831.tif 000159
を生成して，
0004835831.tif 000160
を生成する。検証者は
0004835831.tif 000161
を確認できたら証明を受理する。
【実施例２】  本発明の第２の実施例について、図１４ないし図１８を用いて説明する。
本実施例においては、図１４に示すように計算装置１４０１がＮ個あり、それぞれ計算装置１４０３を備えているものとする。以下ではこの計算機を順番にＵ１，．．．，ＵＮと呼ぶことにする。記法の都合上、ＵＮの事をＵ０とも書く事にする。
［方式の概略］
［データの流れ］
実施例２におけるデータの流れを図１６を参照して説明する。
まず、計算装置１４０１のＵ１はＤＡＴＡ００を計算する。これを「０周目の計算」とよぶ（１７０１）。
次に「一周目の計算」を行う。
Ｕ１はＤＡＴＡ００からＤＡＴＡ１１を計算して、ＤＡＴＡ１１をＵ２に送る（１７１１）。
次にＵ２はＤＡＴＡ１１からＤＡＴＡ１２を計算し、ＤＡＴＡ１２をＵ３に送る（１７１２）。
以下順にデータを送って行き、ＵＮはＤＡＴＡ１Ｎ−１からＤＡＴＡ１Ｎを計算し、ＤＡＴＡ１ＮをＵ１に送る（１７１０）。ここまでが一周目の計算である。
次に「二周目の計算」を行う。
Ｕ１はＤＡＴＡ１ＮからＤＡＴＡ２１を計算して、ＤＡＴＡ２１をＵ２に送る（１７２１）。
次にＵ２はＤＡＴＡ２１からＤＡＴＡ２２を計算し、ＤＡＴＡ２１をＵ３に送る（１７２２）。
以下順にデータを送って行き、ＵＮはＤＡＴＡ２Ｎ−１からＤＡＴＡ２Ｎを計算し、ＤＡＴＡ２ＮをＵ１に送る（１７２０）。ここまでが二周目の計算である。
次に「三周目の計算」を行う。
Ｕ１はＤＡＴＡ２ＮからＤＡＴＡ３１を計算して、ＤＡＴＡ２１をＵ２に送る（１７３１）。
以下順にデータを送って行き、ＵＮがＤＡＴＡ３Ｎ−１からＤＡＴＡ３Ｎを計算し終えたところでプロトコルが終了となる。
［各計算装置１４０１の入出力］
次に各計算装置１４０１のやり取りするデータの入出力を図１４を参照して説明する。
各計算装置１４０１には、回路の情報１４０４、および回路の部分入力１４０２が入力される。
ここでは、回路の情報１４０４が表す回路の入力素子以外の素子のｆａｎ−ｉｎの数が２である場合に対し説明する。
回路の入力素子ｗへの入力ｂｗはＵ１、．．．、ＵＮのいずれかが秘密裡に所有しているものとする。Ｕ１の事をＵＮ＋１とも書く事にする。
Ｕｌが秘密裡に所有している入力ビットの組が回路の部分入力１４０２である。
回路の情報１４０４が表す回路の入力素子ｉを、いかなる入力が入ってもｂｗを出力する素子だと思い直した回路を以下Ｃ［１］と表す。
Ｃ［１］の全てのゲートのｆａｎ−ｉｎの数は２である。
素子ｗの左下、右下のｆａｎ−ｉｎをそれぞれＬ（ｗ）、Ｒ（ｗ）と書く事にする。
各計算装置１４０１に回路の情報１４０４、および回路の部分入力１４０２が入力されたら、まずＵ１は後で説明する手順に従って０周目の計算を行う。
１周目、２周目、３周目の計算での入出力は同様のデータ構造を持っている。ｉ＝１，２，３に対し、ユーザＵｌが第ｉ周目の計算でＵｌ＋１に送信するデータをＤＡＴＡｉｌと表す事にする。ＤＡＴＡｉ−１ＮをＤＡＴＡｉ０とも書く事にする。
また、第０周目の計算でＵ１が行った計算の計算結果をＤＡＴＡ０１と書く。
ＤＡＴＡｉｌは、ＤＡＴＡｉｌ＝ＤＡＴＡｉｌ−１‖ＢＯＤＹｉｌ‖ＰＲＯＯＦｉｌ‖ＳＩＧｉｌという形をしている。
ＤＡＴＡｉｌ−１はＵｌ−１から送られてきたメッセージ、ＢＯＤＹｉｌはメッセージの本体、ＰＲＯＯＦｉｌはＢＯＤＹｉｌの正当性証明文、ＳＩＧｉｌはＵｌのＤＡＴＡｉｌ−１‖ＢＯＤＹｉｌ‖ＰＲＯＯＦｉｌに対する署名。
１周目、２周目、３周目の計算の概略を説明する。
第ｉ周目の計算において、ＵｌはまずＤＡＴＡｉｌ−１をＵｌ−１から受け取る（１５０１）。
（一周目のＵ１のみは例外的に自分で作ったデータＤＡＴＡ０１を使う）。
ＤＡＴＡｉｌ−１を受け取ったら、Ｕｌは正当性証明文ＰＲＯＯＦ１１、．．．，ＰＲＯＯＦｌ−１１を全て検証する（１５０２）。そして次にＵｌは署名文ＳＩＧｌ１、．．．、ＳＩＧｌ−１１を全て検証する（１５０３）。
第１周目の場合で、しかもｌ＝１の場合のみ１５０４の計算を行う。次にＵｌは乱数生成を行う（１５０５）。そしてＵｌはその乱数を用いて本計算を行い、ＢＯＤＹｉｌを作成する（１５０６）。本計算を終えたらＵｌはＢＯＤＹｉｌの正当性証明文ＰＲＯＯＦｉｌを作成する（１５０７）。そしてＵｌはＤＡＴＡｉｌ−１‖ＢＯＤＹｉｌ‖
ＰＲＯＯＦｉｌに対する署名文ＳＩＧｉｌを作成する（１５０８）。
最後にＵｌはＤＡＴＡｉｌ＝ＤＡＴＡｉｌ−１‖ＢＯＤＹｉｌ‖ＰＲＯＯＦｉｌ‖ＳＩＧｉｌをＵｌ＋１に送信する（１５０９）。
［記号］
以下に、本明細書で使用する記号の説明を行う。
［暗号方式Ｅ［２７］］
Ｇ［１］を、アーベル群でＤＤＨ問題が難しいもの（例えば有限体上の楕円曲線群）とし、Ｇ［１］の位数をｐとし、Ｇ［１］の零元をＯと表す。
ηを記号とし、以下の記号を定義する。ただし、
0004835831.tif 000162
に対し、（Ｐ［｜Ｏ｜］，Ｏ）を略記して単にＰ［｜Ｏ｜］と表し、自然に
0004835831.tif 000163
とみなし、Ｇ［１２Ｂ］上の和を成分毎の和により定義し、
0004835831.tif 000164
のα成分をｗ［２｜α｜］と表し、Ｗ［１２］上の和と積を成分毎の和と積により定義し、Ｇ［１２Ｗ］上の和とスカラー倍を成分毎の和とスカラー倍により定義する。
0004835831.tif 000165
暗号方式Ｅ［２７］はＧ［１２Ｗ］における、楕円ＥｌＧａｍａｌ暗号の類似物である。
秘密鍵空間をＦｐ、公開鍵空間をＧ［１２Ｗ］２、平文空間をＧ［１２Ｗ］、乱数空間をＷ［１２］とする。
鍵生成をするには、Ｐ＝Ｐ［｜Ｏ｜］＋ηＰ［｜１｜］でＰ［｜Ｏ｜］，Ｐ［｜１｜］≠Ｏとなるものを任意に選ぶ。
0004835831.tif 000166
文Ｍを暗号化するには一様かつランダムにｒ∈Ｂ［１２］を選び、暗号文（Ｐ［３］，Ｑ［３］）＝（ｒＰ，Ｍ＋ｒＱ）を計算する。（Ｐ［３］，Ｑ［３］）を復号するにはＱ［３］−ａＰ［３］を計算すれば良い。［暗号方式Ｅ［２］，Ｅ［２５］］
以下を定義する：
0004835831.tif 000167
ｋの元ｘのｗＷｈ成分をｘ［｜ｗＷｈ｜］と書く事にし、Ａ［１２］の元ｘ［２］のｗＷｉｊｋ成分をｘ［｜ｗＷｉｊｋ｜］と書く事にし、Ａ［１２５］の元へ［２５］のｗＷｉｊｋ，ｉ［６］，ｊ［６］｛｝，ｋ［６］成分をｘ［｜ｗＷｉｊｋ｜ｉ［６］ｊ［６］ｋ［６］］と書く事にする。
多重配列の和と積、スカラー倍を、成分毎の和と積により定義する。ただし例外的に、Ａ［１２５］の元同士の積、およびＧ［１２４｜Ａ｜］の元のＡ［１２５］の元によるスカラー倍のみは
0004835831.tif 000168
により定義する。
以下の記号を定義する。
0004835831.tif 000169
暗号方式Ｅ［２］、Ｅ［２５］をそれぞれ、真理値群環上の多重配列エルガマル暗号、真理値群環上の拡張多重配列エルガマル暗号と呼ぶ事にする。［その他の記号］
0004835831.tif 000170
0004835831.tif 000171
と定義する。簡単な計算から、次が成立する事が分かる：
0004835831.tif 000172
［第０周目の計算の詳細］
第０周目の計算の詳細を述べる。
Ｕ１がＢＯＤＹ１０を計算する方法を説明する。
Ｕ１は以下を計算する。
0004835831.tif 000173
［第１周目の計算の詳細］
一周目のマルチパーティ計算を説明する。図１５に則して説明する。
［データの取得１５０１の詳細］
各ＵｌはＵｌ−１からデータＤＡＴＡ１ｌ−１を受け取る。（Ｕ１のみは、例外的に自分でデータＤＡＴＡ１ｌ−１＝ＤＡＴＡ１０を計算する）。
［データ中の証明文の検証１５０２の詳細］
さてＵｌ−１からＤＡＴＡ１ｌ−１‖ＢＯＤＹ１ｌ−１‖ＰＲＯＯＦ１ｌ−１‖ＳＩＧ１ｌ−１‖が送られてきたら、ＵｌはＰＲＯＯＦ１１、．．．，ＰＲＯＯＦ１ｌ−１の正当性を確認する。この正当性の確認についての詳細は後述する。
［データ中の署名文の検証１５０３の詳細］
ＵｌはＳＩＧ１１、．．．、ＳＩＧ１ｌ−１の正当性を確認する。さらにＲＡＮＤのハッシュ値Ｐを計算し、Ｐ［２］＝（ｅ［｜Ｏ｜］＋．．．＋ｅ［｜ｋ−１｜］）（１＋η）Ｐを確認する。
［Ｕ１のみ行う計算１５０４の詳細］
Ｕ１はまず、乱数ＲＡＮＤを任意に選び、ＲＡＮＤのハッシュ値
0004835831.tif 000174
とし、Ｐ［２］＝（ｅ［｜Ｏ｜］＋．．．＋ｅ［｜ｋ−１｜］）Ｐ［２Ｂ］とし、ＢＯＤＹ１−１＝ＲＡＮＤ‖Ｐ［２］とし、そしてＢＯＤＹ１０を後で説明する手順に従って自分で作成し、さらにＰＲＯＯＦ１０＝ＳＩＧ１０＝εとし、ＤＡＴＡ１０＝ＲＡＮＤ‖ＢＯＤＹ１０‖ＰＲＯＯＦ１０‖ＳＩＧ１０とする。
［乱数生成１５０５の詳細］
Ｕｌはランダムに以下を選ぶ（ただしかっこ内の記述を満たすように選ぶこと）：
0004835831.tif 000175
・Ｗｔ：出力素子
入力素子ｗに対し、形式的にｘ［＃ｌ｜Ｌ（ｗ）０｜］＝ｘ［＃ｌ｜Ｒ（ｗ）１｜］＝０と定義する。
以下の記号を定義する。
0004835831.tif 000176
提案方式に関し、次の事実が言える。ユーザ達がプロトコルにしたがっている場合、各Ｕｌの送るデータＢＯＤＹ１ｌは以下を満たす。
0004835831.tif 000177
0004835831.tif 000178
［本計算１５０６の詳細］
一周目のマルチパーティ計算の本計算１５０６を図１７に則して説明する。
ＵｌがＢＯＤＹ１ｌを計算する方法を説明する。
［再暗号用の公開鍵の計算１７０１］
Ｕｌはまず、
0004835831.tif 000179
を計算する。
なお、この時次が言える：
0004835831.tif 000180
0004835831.tif 000181
［再暗号化−秘密鍵の変換１７０３、再暗号化−乱数の変換１７０４、正当性証明文の作成１５０７、署名文の作成１５０８、データの送信１５０９］
最後にＵｌは以下を計算する。（かっこ内は図中の番号）。
0004835831.tif 000182
0004835831.tif 000183
正当性証明文の作成１５０７の詳細は長いので説明を後にまわす。
ＤＡＴＡ１ｌ＝（Ｑ［２：ｌ］，ｒ［２：ｌ］）‖（ｓ［２：ｌ］，Ｔ［２：ｌ］，Ｕ［２５：ｌ］）をＵｌ＋１に送る。
なお、この時次が言える：
0004835831.tif 000184
第二周目の計算の詳細を図１５に則して説明する。
［データの取得１５０１の詳細］
各ＵｌはＵｌ−１からデータＤＡＴＡ２ｌ−１＝ＤＡＴＡ２ｌ−２‖ＢＯＤＹ２ｌ−１‖ＰＲＯＯＦ２ｌ−１‖ＳＩＧ２ｌ−１を受け取る。
［データ中の証明文の検証１５０２、データ中の署名文の検証１５０３、Ｕ１のみ行う計算１５０４、乱数生成１５０５の詳細、Ｆｐ上の暗号の算出１８０１］
以下の計算を行う。
0004835831.tif 000185
［本計算１５０６の詳細］
第二周目の計算の本計算１５０６の詳細を図１８に則して説明する。
［Ｆｐ上の暗号の算出１８０１］
この節では以後添字「：Ｎ」を省略する。
Ｕｌは以下の計算をする：
0004835831.tif 000186
0004835831.tif 000187
さらに以下の計算をする。
0004835831.tif 000188
よってＵｌは以下を得る事ができる：
0004835831.tif 000189
0004835831.tif 000190
［Θ［＆１］の計算１８０２，正当性証明文の作成１５０７の詳細，署名文の作成１５０８の詳細，データの送信１５０９の詳細］
さらに以下の計算を行う：
0004835831.tif 000191
［第３周目の計算の詳細］
３周目の計算の詳細を図１５に則して説明する。
Ｕｌ−１からＤＡＴＡ３ｌ−１＝ＤＡＴＡ３ｌ−２‖ＢＯＤＹ３ｌ‖ＰＲＯＯＦ３ｌ‖ＳＩＧ３ｌが送られてきたら（１５０１）、まずＰＲＯＯＦ３１、．．．、ＰＲＯＯＦ３ｌ−１、ＳＩＧ３ｌ、．．．、ＳＩＧ３ｌ−１の正当性を確認する（１５０２，１５０３）。（１５０４），（１５０５）は第三周目の計算ではない。ＢＯＤＹ３ｌ＝εとし（１５０６）、ＰＲＯＯＦ３ｌ＝εとし（１５０７）、そしてＤＡＴＡ３ｌ−１‖ＢＯＤＹ３ｌ‖ＰＲＯＯＦ３ｌに対する署名ＳＩＧ３ｌを作成し（１５０８）、ＤＡＴＡ３ｌ＝ＤＡＴＡ３ｌ−１‖ＢＯＤＹ３ｌ‖ＰＲＯＯＦ３ｌ‖ＳＩＧ３ｌとし、ＤＡＴＡ３ｌをＵｌに送る（１５０９）。
［Ｃ［１］（｛ｂ［｜ｗ｜］｝）を求める方法１４０５］
Ｃ［１］（｛ｂ［｜ｗ｜］｝）を求める方法を説明する。
まず入力素子ｗに対してｘ［＃ｌ｜Ｌ（ｗ）０｜］＝ｘ［＃ｌ｜Ｒ（ｗ）１｜］＝０であるので、
0004835831.tif 000192
さて、下からｕ−１段目までの各素子ｗに対して、ｘ［｜μ［｜ｗ｜］｜］が求まっているとする。
以下の計算をしてｕ段目のｘ［｜μ［｜ｗ｜］｜］を求める。
0004835831.tif 000193
（Ｗに関する排他的論理和）
ただしここで
0004835831.tif 000194
0004835831.tif 000195
［一周目の計算の正当性証明］
［一周目の計算の正当性証明の作成１５０７の詳細］
以下の記号を定義する：
0004835831.tif 000196
この節では、簡単の為添字「：ｌ−１」を省略する。
以下の方法で知識を証明する。
まず乱数をハッシュ関数にいれて
0004835831.tif 000197
を作る。そして以下を計算する。
0004835831.tif 000198
Ｕｌは以下の手順でＰＲＯＯＦ１ｌを作成する。ランダムかつ一様に以下のデータを選ぶ。
0004835831.tif 000199
そして以下を計算する。
0004835831.tif 000200
0004835831.tif 000201
ただしここで
0004835831.tif 000202
0004835831.tif 000203
さらに以下の計算をする。
0004835831.tif 000204
0004835831.tif 000205
さらに以下のデータを一様かつランダムに選ぶ。
0004835831.tif 000206
そして以下を計算する。
0004835831.tif 000207
0004835831.tif 000208
さらに以下を計算する。
さらに
0004835831.tif 000209
ただしここでＨａｓｈは、Ｆｐ値ハッシュ関数。
そして次を計算。
0004835831.tif 000210
さらに次を計算。
0004835831.tif 000211
0004835831.tif 000212
そして、
0004835831.tif 000213
［一周目の計算の正当性証明の検証１５０２の詳細］
ＰＲＯＯＦ１ｌを受け取ったら、Ｕｌ＋１は以下を確認する。
0004835831.tif 000214
0004835831.tif 000215
を確認する。
0004835831.tif 000216
［二周目の計算の正当性証明］
［二周目の計算の正当性証明の作成１５０７の詳細］
Ｕｌはランダムに
0004835831.tif 000217
を選び、以下のようにしてＰＲＯＯＦ２ｌを計算する。
0004835831.tif 000218
［二周目の計算の正当性証明の検証１５０２の詳細］
ＰＲＯＯＦ１ｌを受け取ったら、Ｕｌ＋１は以下を確認する。
0004835831.tif 000219
【産業上の利用可能性】  電子入札、電子競売等で、落札者以外の入札者の入札値を秘密にしたまま、入札者と入札価格を決定したい場合で、かつその決定が正しく行われたことを第三者が検証できる必要がある場合等や、電子投票等で匿名性を保ったまま正しく票数が数えられていることを第三者が検証できる必要がある場合等に、本発明方法を用いると有効である。
なぜならば、本発明方法を用いれば、上記入札、競売、投票の結果を複数の計算装置で行えば、誰も計算結果以外の情報を新たに得ることがなく、かつその計算の正当性を誰でも検証できるからである。そしてこの計算が従来の技術を持ってして行うより効率的である。さらに、計算装置間の通信回数が少ないため、計算装置が通信に回線を確保するのに時間を費やす時間も少なく、効率的である。
【図１】
0004835831.tif 000220
【図２】
0004835831.tif 000221
【図３】
0004835831.tif 000222
【図４】
0004835831.tif 000223
【図５】
0004835831.tif 000224
【図６】
0004835831.tif 000225
【図７】
0004835831.tif 000226
【図８】
0004835831.tif 000227
【図９】
0004835831.tif 000228
【図１０】
0004835831.tif 000229
【図１１】
0004835831.tif 000230
【図１２】
0004835831.tif 000231
【図１３】
0004835831.tif 000232
【図１４】
0004835831.tif 000233
【図１５】
0004835831.tif 000234
【図１６】
0004835831.tif 000235
【図１７】
0004835831.tif 000236
【図１８】
0004835831.tif 000237
【図１９】
0004835831.tif 000238