秘密分散情報処理システム
【課題】 複数のユーザが各自の秘密の入力を持ち、その入力を秘密にしたまま協調して通信によってある計算を行う秘密分散情報処理システムにおいて、加算と乗算に関しては効率的な方法があったが、大小比較を比較される値を多項式共有によって秘密にしたまま効率的に行う方法がないため、そのための通信方法を提供すること。
【解決手段】 従来の分散計算技術であるＢＧＷ方式とその応用であるＤＦＮＴプロトコルによる方式を複雑な計算を含まないよう改良し、より効率的な大小比較通信プロトコルを構成し、これによってオークションプロトコルなどのような大小比較演算を含む計算をより効率的に実現する秘密分散情報処理システムを構築する。
【解決手段】 従来の分散計算技術であるＢＧＷ方式とその応用であるＤＦＮＴプロトコルによる方式を複雑な計算を含まないよう改良し、より効率的な大小比較通信プロトコルを構成し、これによってオークションプロトコルなどのような大小比較演算を含む計算をより効率的に実現する秘密分散情報処理システムを構築する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数ユーザが各自秘密に入力を持ち、その入力を秘密にしたままである決められた関数を通信によって分散計算するＭｕｌｔｉｐａｒｔｙ Ｃｏｍｐｕｔａｔｉｏｎにおいて効率よく大小比較を秘密に計算する秘密分散情報処理システムに関する。
【背景技術】
【０００２】
分散計算技術において複数のユーザ（あるいは人工知能の分野ではエージェントなどとも呼ばれる）が協調して一つの計算を行う研究は昔から行われている。このような分散計算においてプライバシーを確保するために各ユーザの入力情報を秘密にしたままで協調した分散計算を行いたいという要請があり、それらを実現する分散計算技術として暗号分野では代表的な非特許文献１を含めてたくさんの研究が行われてきている。非特許文献１に示された技術（以下、非特許文献１の３名の著者の頭文字を取って「ＢＧＷ方式」と呼ぶ）はＳｈａｍｉｒによって提案された秘密の値を有限体上の多項式を用いてユーザ間で共有する技術（非特許文献２、非特許文献６参照）を使い、途中の計算結果を秘密にしながら最終的な計算結果を全員が得ることができる分散計算技術である。形式的に言えばｎユーザたちが各自の秘密の入力ｘ＿ｉを持ち関数（ｙ＿１，ｙ＿２，…，ｙ＿ｎ）＝ｆ（ｘ＿１，ｘ＿２，…，ｘ＿ｎ）を計算し各ユーザは対応する出力ｙ＿ｉのみを最後に得ることができる。
【０００３】
この分散計算技術はオークション理論や最適リソース割り当てのような各自が競争相手であり自分の入力を秘密にしたい環境であっても協調し全体として最適な経済効果を得るための通信プロトコルとして重要となってきている。例えば非特許文献３では安全なダブルオークションを実現するための通信方法として、特定のパラメータ設定を仮定した状況でのＢＧＷ方式を基にした大小比較プロトコルをソフトウェアとして実際に実装している。
ＢＧＷ方式では加算と乗算は効率的に計算できることが示されている。より複雑な計算を効率的に行うにはその他の演算も効率的に計算できることが必要である。大小比較演算は重要な基本演算のひとつであるが秘密の値がビット表現による多項式共有されていなければ効率的に計算できないという問題があった。それではビット表現による多項式共有を用いれば問題が解決するように見えるが、ビット表現による多項式共有では各ビット毎にデータを持つ必要があるため扱うデータ量が増加し、分散計算を行う際にユーザ間で相互にやりとりするデータの通信量が増えるという問題があった。今まではビット表現ではない通常の多項式共有によって入力を秘密にしたまま大小比較計算する効率的な方法が提案されずにいた。
【０００４】
しかし非特許文献４で多項式共有された値を秘密に比較するためのより現実的な効率を持った方法が提案された。ここで言う「秘密に比較する」とはｎユーザたちがｘ＿１，ｘ＿２を（ビット表現でなく通常の）多項式共有している状況で関数ｆがｆ（ｘ＿１，ｘ＿２）∈｛０，１｝として計算され、（ｘ＿１＜ｘ＿２）であれば１（つまりＴＲＵＥ）を、ｘ＿１≧ｘ＿２であれば０（つまりＦＡＬＳＥ）を出力することである。ここで出力値の０，１は再度多項式共有によってユーザ間で共有されている。
【０００５】
【非特許文献１】 Ｍ．Ｂｅｎ−Ｏｒ，Ｓ．Ｇｏｌｄｗａｓｓｅｒ，ａｎｄ Ａ．Ｗｉｇｄｅｒｓｏｎ，“Ｃｏｍｐｌｅｔｅｎｅｓｓ Ｔｈｅｏｒｅｍ ｆｏｒ Ｎｏｎ ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｆａｕｌｔ−ｔｏｌｅｒａｎｔ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ，ｐｐ．１−１０，１９８８．
【非特許文献２】 Ａｄｉ Ｓｈａｍｉｒ，“Ｈｏｗ ｔｏ ｓｈａｒｅ ａ ｓｅｃｒｅｔ”，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ＡＣＭ，２２（１１）：６１２−６１３，１９７９．
【非特許文献３】 Ｐｅｔｅｒ Ｂｏｇｅｔｏｆｔ，Ｉｖａｎ Ｄａｍｇａｒｄ，Ｔｈｏｍａｓ Ｊａｋｏｂｓｅｎ，Ｋｕｒｔ Ｎｉｅｌｓｅｎ，Ｊａｋｏｂ Ｐａｇｔｅｒ，ａｎｄ Ｔｏｍａｓ Ｔｏｆｔ，“Ｓｅｃｕｒｅ ｃｏｍｐｕｔｉｎｇ，ｅｃｏｎｏｍｙ，ａｎｄ ｔｒｕｓｔ：Ａ ｇｅｎｅｒｉｃ
ＲＳ−０５−１８，２００５．
【非特許文献４】 Ｉｖａｎ Ｄａｍｇａｒｄ，Ｍａｔｔｈｉａｓ Ｆｉｔｚｉ，Ｊｅｓｐｅｒ Ｂｕｕｓ Ｎｉｅｌｓｅｎ，ａｎｄ Ｔｏｍａｓ Ｔｏｆｔ，“Ｈｏｗ ｔｏ Ｓｐｌｉｔ ａ Ｓｈａｒｅｄ Ｓｅｃｒｅｔ ｉｎｔｏ Ｓｈａｒｅｄ Ｂｉｔｓ ｉｎ Ｃｏｎｓｔａｎｔ−Ｒｏｕｎｄ”，ＣｒｙｐｔｏｌｏｇｙｅＰｒｉｎｔ Ａｒｃｈｉｖｅ ２００５／１４０，Ｊｕｎｅ２３，２００５．
【非特許文献５】 Ｒｏｓａｒｉｏ Ｇｅｎｎａｒｏ，Ｍｉｃｈａｅｌ Ｏ．Ｒａｂｉｎ，ａｎｄ Ｔａｌ Ｒａｂｉｎ，“Ｓｉｍｐｌｉｆｉｅｄ ＶＳＳ ａｎｄ ｆａｓｔ−ｔｒａｃｋ ｍｕｌｔｉｐａｒｔｙ ｃｏｍｐｕｔａｔｉｏｎｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｔｈｒｅｓｈｏｌｄ ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｉｎ Ｐｒｏｃ．１７ｔｈ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，ｐｐ．１０１−１１０，１９９８．
【非特許文献６】 Ｄｏｕｇｌａｓ Ｒ．Ｓｔｉｎｓｏｎ著、櫻井幸一監訳「暗号理論の基礎」共立出版株式会社、１９９６年１１月１日、ｐ．３４９−３５５
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記非特許文献４に記載の通信プロトコル（以下、非特許文献４の４名の著者の頭文字を取って「ＤＦＮＴプロトコル」と呼ぶ）は、大小比較に必要な計算以上のことを行っており通信オーバヘッドはまだ大きく改良の余地がある。
本発明の目的は、ＤＦＮＴプロトコルの通信回数と通信量を減らし、より効率のよい大小比較プロトコルを実現する情報処理システムを構築することである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明の秘密分散情報処理システムは、
クライアント端末と、ｎ個のサーバ１〜サーバｎとがネットワークによって接続され、前記クライアント端末が保持する秘密の数値ａに対する多項式ｆ＿ａ（ｘ）が、前記数値ａを定数項とする多項式を公開された素数ｐで除した剰余として定義される場合に、多項式ｆ＿ａ（ｘ）に対するシェアｆ＿ａ（１）〜ｆ＿ａ（ｎ）が、それぞれ前記サーバ１〜サーバｎに対して、前記ネットワークを経由して、前記クライアント端末から他のサーバには秘密に分散して配布される秘密分散情報処理システムであって、
前記クライアント端末が、
秘密の乱数ｒを発生させて、前記多項式のシェアｆ＿ｒ（１）〜ｆ＿ｒ（ｎ）をそれぞれ前記サーバ１〜サーバｎに秘密に配布し、
前記各サーバが、
それぞれ自己のサーバに配布されているシェア［ａ］ｐ及び［ｒ］ｐの和［ｃ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
公開された前記各サーバのシェア［ｃ］ｐから元の数値ｃを復元し、
前記復元された数値ｃと公開された数値ｄとの値から（ｃ−ｒ’＜？ｄ）≠（ｃ＜？ｄ）となるようなｒ’の範囲｛ｌｏｗ，…，ｈｉｇｈ｝を求め、
前記乱数ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に含まれるかを（ｌｏｗ−１＜？ｒ）と（ｒ＜？ｈｉｇｈ＋１）を判定することで求め、
当該ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に属するか否かの判定結果から、前記公開された数値ｄと前記数値ａとの大小関係を、数値ａを秘密に保持したまま求めることを特徴とする。
【０００８】
また、上記目的を達成するために、本発明の秘密分散情報処理システムは、前記特徴に加え、
第二のクライアント端末が更に前記ネットワークによって接続され、
前記第二のクライアント端末が保持する秘密の数値ｂに対する前記多項式のシェアｆ＿ｂ（１）〜ｆ＿ｂ（ｎ）が前記サーバ１〜サーバｎに秘密に分散されて保持され、
前記各サーバが、
それぞれ自己のサーバに配布されているシェアから、式［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
前記公開された結果から、前記数値ａと前記数値ｂとの大小関係を、秘密に保持したまま求めることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ユーザたちあるいはユーザの代理人としてのエージェントプログラムが入力を秘密にしながら大小比較を含む分散計算を、ビット表現による多項式共有によって引き起こされる通信データ量の増加無しに、効率的に行うことが可能となり、入力の秘匿性を必要とされるオークションなどの大小比較演算を含む演算を効率的に実行できる情報処理システムを構築できる。
実際にＤＦＮＴプロトコルでは通信回数と総通信量はパラメータＬ（多項式共有における素数ｐのビット長）によって１３３Ｒｏｕｎｄｓ／２５８Ｌ＋２２０Ｌ＊ｌｏｇ２（Ｌ）と表現されるが、本発明では４３Ｒｏｕｎｄｓ／４２０Ｌ＋６となる。パラメータＬは実用上、通常Ｌ＞８と仮定できるため、理論的には、通信によるオーバヘッドを通信回数では約１／３に、また通信量では約１／２に軽減できる。
【発明を実施するための最良の形態】
【００１０】
本発明による大小比較のための具体的な情報処理システムを説明する前に、まず基本となるＢＧＷの通信方式について簡単に述べ、いくつかの用語、記号、数式の定義を行う。ＢＧＷ方式では計算される関数に与えられる引数がＳｈａｍｉｒの方式によって秘密分散される。Ｓｈａｍｉｒの多項式共有による秘密分散とは次式（１）のようなある有限体上の多項式によって与えられる。
【００１１】
ここでｐはある公開された奇数の素数であり各ａ［ｉ］は有限体Ｚｐからランダムに選ばれた値である。例えばあるユーザが秘密の入力ａを秘密分散するときは上記ｆ＿ａ（）のような定数項にａをもつランダム多項式を生成し（つまり上記の多項式の各係数をランダムに選択する）、他ユーザ１≦ｉ≦に対してｆ＿ａ（ｉ）（これはシェアと呼ばれる）を秘密通信路を通じて配布する。このようにａが多項式によって秘密分散されている（つまりシェアｆ＿ａ（ｉ）がユーザｉに保持されている状態）ことを以下では［ａ］ｐと表記する。多項式ｆ＿ａ（ｘ）はｔ＋１個のシェアを集めることでＬａｇｒａｎｇｅの補間公式と呼ばれる標準的な方法によって復元できる。
【００１２】
加算とは、ａとｂが多項式ｆ＿ａ（ｘ）とｆ＿ｂ（ｘ）で秘密分散されているときａ＋ｂ ｍｏｄ ｐのシェアを計算することであるが、これは各ユーザｉがｆ＿ａ（ｉ）＋ｆ＿ｂ（ｉ）を行うことで計算できる。このときａ＋ｂを復元することなしにａもｂも秘密のままでａ＋ｂのシェアを各ユーザが計算できることがＢＧＷ方式の利点である。また非特許文献５の乗算方式を用いることで［ａ］ｐと［ｂ］ｐから［ａｂ ｍｏｄ ｐ］ｐのシェアも計算できることが知られている。
このようにａとｂが多項式共有による秘密分散されている状況から、ユーザたちが加算、乗算のシェアを計算することを以下では［ａ＋ｂ ｍｏｄ ｐ］ｐ＝［ａ］ｐ＋［ｂ］ｐ，［ａｂ］ｐ＝［ａ］ｐ＊［ｂ］ｐと表記することにする。
【００１３】
図１に、本発明を実施する場合の基本的な秘密分散情報処理システムの構成を表す。本システムは、クライアント１０１、１０２等と、ｎ個のサーバ（この図では４個）１１１、１１２、１１３、１１４及びそれらを接続するネットワーク１２１から構成される。
クライアント１０１が秘密に保持する数値ａについて、ｆ＿ａ（ｘ）が前述のような多項式で表現され、シェアｆ＿ａ（１）、ｆ＿ａ（２）、ｆ＿ａ（３）、ｆ＿ａ（４）が、それぞれサーバ１１１、サーバ１１２、サーバ１１３、サーバ１１４に対して、クライアント１０１からネットワーク１２１経由で、互いに他のサーバやクライアントには知られないように、秘密に送付される。同様に、クライアント１０２が秘密に保持する数値ｂについても、多項式の各要素であるｆ＿ｂ（１）、ｆ＿ｂ（２）、ｆ＿ｂ（３）、ｆ＿ｂ（４）が、それぞれサーバ１１１、サーバ１１２、サーバ１１３、サーバ１１４に対して、クライアント１０２からネットワーク１２１経由で秘密に送付される。
【００１４】
更に、非特許文献４では他の部品となる通信プロトコルが提案されている。本発明の中でも、これらの部品を使うため利用する部品についてのみ述べる。
秘密乱数生成プロトコルであるＤＦＮＴプロトコルによって有限体Ｚｐからあるランダムな秘密の値をユーザたちが誰も知ることなく生成できる。これを［ｒ∈Ｚｐ］ｐと表す。このとき秘密乱数ｒがユーザたちによって秘密分散されている状態を作り出すことができる。ただしどのユーザもｒの値は知らないことに注意。
また、ＤＦＮＴプロトコルによって乱数の中でも特に０，１のどちらかを秘密に生成することができる。これを［ｂ∈｛０，１｝］ｐと表す。このとき秘密ビットｂがユーザたちによって秘密分散されている状態を作り出すことができる。ただしどのユーザもｂが０か１か知らないことに注意。
【００１５】
ここで「ｂｉｔｗｉｓｅ秘密分散」についてまず説明する。これは今まで「ビット表現による多項式共有」と呼んでいたものに相当する。いま各ａ［ｉ］∈｛０，１｝であるｋ個の秘密分散［ａ［ｋ−１］］ｐ，…，［ａ［０］］ｐがあり（ａ［ｋ−１］，ａ［ｋ−２］，…，ａ［０］）のビット列によって、ａ＝Σ（（２＾ｉ）＊ａ［ｉ］）（０≦ｉ≦ｋ−１）となるａを表現しているとする。このときａをｋ個のビットによって「ｂｉｔｗｉｓｅ秘密分散」していると表現し、［ａ］＿Ｂと表記する。このときａの通常の秘密分散［ａ］ｐはＢＧＷ方式の加算の性質から、次式（２）によって得ることができる。
［ａ］ｐ＝Σ（２＾ｉ）＊［ａ［ｉ］］ｐ …（２）
【００１６】
ＤＦＮＴプロトコルはＢｉｔｗｉｓｅ Ｌｅｓｓ−Ｔｈａｎプロトコルとしてｂｉｔｗｉｓｅ秘密分散された［ａ］＿Ｂと［ｂ］＿Ｂを比較し、ａ＜ｂであれば［１］ｐ、ａ！＜ｂつまりａ≧ｂであれば［０］ｐの秘密分散を結果である０，１を秘密にしたまま作り出すプロトコルである。このプロトコルの計算結果を［ａ＜？Ｂｂ］ｐのように表す。つまりｂｉｔｗｉｓｅ秘密分散されたａとｂを秘密にしたままでその大小比較結果の｛０，１｝をまた秘密分散できる。これはａとｂがｂｉｔｗｉｓｅ秘密分散されていれば大小比較を効率的に行えるという事実に基づいている。
ＤＦＮＴプロトコルは秘密ｂｉｔｗｉｓｅ乱数生成プロトコルとして秘密ビット生成プロトコルをパラレルに実行し最初からビット表現で乱数ｒを生成する。このプロトコルで乱数を生成することを［ｒ∈Ｚｐ］＿Ｂのように表す。
【００１７】
本発明は上記の部品プロトコルを使いａとｂが［ａ］ｐと［ｂ］ｐとして多項式共有による秘密分散（ｂｉｔｗｉｓｅ秘密分散ではない）されているときに、［ａ＜？ｂ］ｐ，ｗｈｅｒｅ（ａ＜ｂ）＝１ ｉｆａ＜ｂ，となるような計算を行う方法である。
多くの場合、ａとｂの値は［ａ］＿Ｂ，［ｂ］＿Ｂで与えられるよりも、［ａ］ｐ，［ｂ］ｐで与えられるため、本発明を用いれば［ａ］ｐから［ａ］＿Ｂへの変換を回避できることに注意。
【００１８】
以下に本発明の秘密分散情報処理システムにおける計算方法について述べる。
まずここでは秘密分散された［ａ］ｐと有限体の位数ｐの半分の値との比較を行いその結果の０，１を秘密に判定できると仮定し、その結果の秘密分散を［ａ＜？ｐ／２］ｐとする。このとき最終目標である［ａ＜？ｂ］ｐは、図２の真理値表によって、各論理値（ａ＜？ｐ／２）と（ｂ＜？ｐ／２）と（（ａ−ｂ ｍｏｄ ｐ）＜？ｐ／２）から決定できる。
よってｚは、次式（３）の論理式で与えられる。
ｚ＝ｗ（１−ｘ）＋（１−ｗ）（１−ｘ）（１−ｙ）＋ｗｘ（１−ｙ） …（３）
ここで、第１項ｗ（１−ｘ）は図２の２０１から、第２項（１−ｗ）（１−ｘ）（１−ｙ）は２０２から、第３項ｗｘ（１−ｙ）は２０３から、それぞれ求められる式である。
ユーザたちはｗ，ｘ，ｙ∈｛０，１｝のそれぞれの秘密分散を計算できればＢＧＷ方式の加算と乗算によってｚつまり（ａ＜？ｂ）の秘密分散である［ａ＜？ｂ］ｐを秘密に計算することができる。
【００１９】
次に秘密分散された［ａ］ｐから［ａ＜？ｐ／２］ｐを計算する判定プロトコルについて述べる。
ユーザたちは以下のプロトコルに従って計算する。
１． 秘密ｂｉｔｗｉｓｅ乱数生成プロトコルによって［ｒ∈Ｚｐ］＿Ｂを得る。また［ｒ∈Ｚｐ］＿Ｂからユーザたちは［ｒ∈Ｚｐ］ｐを式（２）によって容易に計算できる。
２． ユーザたちは［ｃ］ｐ＝［ａ］ｐ＋［ｒ］ｐを実行し、［ｃ］ｐのシェアを公開することでｃを復元しｃ＝ａ＋ｒ ｍｏｄ ｐを公開する。ｒが秘密の値であるためａ＋ｒを公開してもａに関する情報は秘匿されたままである。
３． ユーザたちは公開したｃから論理式が（ｃ−ｒ’ｍｏｄ ｐ＜？ｐ／２）≠（ｃ＜？ｐ／２）を満たすようなｒ’の範囲を求める。この範囲を｛ｌｏｗ，…，ｈｉｇｈ｝とする。ここではｐが公開されていることに注意。
４． ユーザたちはｒが｛ｌｏｗ，…，ｈｉｇｈ｝の範囲に入っているかをＢｉｔｗｉｓｅ Ｌｅｓｓ−Ｔｈａｎプロトコルを用いて
［ｒ∈？｛ｌｏｗ，…，ｈｉｇｈ｝］ｐ＝［ｌｏｗ−１ ＜？Ｂ ｒ］ｐ ＊ ［ｒ ＜？Ｂ ｈｉｇｈ＋１］ｐ …（４）
を計算することで得られる。ここでｒは［ｒ］＿Ｂとしてユーザたちに保持されており、ｌｏｗとｈｉｇｈは公開された値であるため［ｌｏｗ］＿Ｂ，［ｈｉｇｈ］＿Ｂとしてユーザたちに保持されることが可能であることに注意。
５． 最後にユーザたちは値ｃとｐ／２の大小関係を用いた場合分けによって以下のように［ａ＜？ｐ／２］ｐを求める。
［ａ＜？ｐ／２］ｐ＝１−［ｒ∈？｛ｌｏｗ，…，ｈｉｇｈ｝］ｐ ｉｆ （ｃ＜？ｐ／２）＝１． …（５）
［ａ＜？ｐ／２］ｐ＝［ｒ∈？｛ｌｏｗ，…，ｈｉｇｈ｝］ｐ ｉｆ （ｃ＜？ｐ／２）＝０． …（６）
【００２０】
ここで具体例で上記のプロトコルについて説明する。
ｐ＝７，ａ＝４としユーザたちはａを秘密にしたままで［４＜？７／２］７を計算しようとしているとする。このときユーザたちは秘密の乱数ｒ＝５を生成したとする。すると公開される値はｃ＝４＋５ｍｏｄ７＝２である。ｃから上記のｒ’の範囲を求めると｛３，４，５｝となる。ｒ＝５が｛３，４，５｝の範囲に含まれていればｃとａ（＝ｃ−ｒ ｍｏｄ ｐ）はｐ／２＝７／２を境としてそれぞれ反対側に存在することになる。ｒが｛３，４，５｝に含まれているかは［３−１＜？ｒ］ｐ＊［ｒ＜？５＋１］ｐの結果から計算できる。この計算結果が１であれば（ｃ＜？ｐ／２）の論理値が反転するようプロトコルを構成すればよい。
【００２１】
上記の［ａ＜ｐ／２］ｐを判定するプロトコルを応用し、公開された定数であるｐ／２を他の値にする、あるいは比較演算を逆にすることで次のような判定プロトコルも容易に構成できる。ここでａ，ｂ∈｛０，１，…，ｐ−１｝は多項式共有された体Ｚｐのある値とする。
１． ａがゼロか判定するプロトコル。
［ａ＝？０］ｐ＝［ａ＜？１］ｐ …（７）
２． ａとｂが等しいか判定するプロトコル。
［ａ＝？ｂ］ｐ＝［ａ−ｂ＜？１］ｐ …（８）
３． ａとある定数ｃ１，ｃ２∈Ｚｐ（ｃ１＜ｃ２とする）との様々な判定プロトコル。
［ａ＜？ｃ１］ｐ …（９）
［ｃ１＜？ａ］ｐ …（１０）
［ａ∈？｛ｃ１，…，ｃ２｝］ｐ＝［ｃ１−１＜？ａ］ｐ＊［ａ ＜？ ｃ２＋１］ｐ …（１１）
４． ａとｂから大きい方を選択するプロトコル
［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐ …（１２）
【００２２】
次に、本発明を実施する場合の、より具体的な実施形態（以下、「本実施形態」と記載する。）について図３以下を参照して具体的に説明する。ここでは複数サーバによるオークションシステムを考える。このオークションシステム（以下、「本システム」または単に「システム」と記載する。）では入札値の中の最大値とその入札者のみが公表され他の入札値は秘匿することが出来る。
図３は本システム全体の構成図である。システムは、管理サーバ１、３台以上の仲介サーバ２（図３においては仲介サーバ２ｘ、２ｙ、２ｚの３台のサーバを記載している。以下、特に区分する必要がない場合、「仲介サーバ２」と総称する。）、複数台のクライアント３（図３においてはクライアント３ａ、３ｂ、３ｃの３台のクライアントを記載している。以下、特に区分する必要がない場合、「クライアント３」と総称する。）および、ネットワーク（通信回線）４から構成される。図示した構成要素以外にも通信機器（ルータ等）が存在するが、本発明とは特に関係がないので説明を省略する。
管理サーバ１、仲介サーバ２、クライアント３はいずれもＰＣ（パーソナル・コンピュータ）等によって実現できる。また、通信回線４は、管理サーバ１、仲介サーバ２、クライアント３を相互に通信可能に接続することができれば、有線、無線を問わず、どのような技術によって実装されてもよいが、以降はインターネットを想定して説明する。
【００２３】
図４は本実施形態において管理サーバ１、仲介サーバ２およびクライアント３の記録装置に置かれる主な情報資源の一覧である。
管理サーバ１にはオークションの会員管理、出品管理等を行うための管理ソフトがインストールされ、会員が各クライアント３にダウンロードして使用するためのオークション用クライアントソフト、会員情報、出品情報などが記録されている。
すなわち、オークションに出品したり、入札したりすることを希望する者は、例えば、管理サーバが公開するＷＥＢページから会員ＩＤ、認証用パスワード、決済用のクレジット番号等を会員情報として登録することで、オークションの会員になることができ、オークションの会員（以下、「会員」と記載する。）になったものは、オークションに出品、入札するために必要なオークション用クライアントソフトを、管理サーバからダウンロードすることができる。会員は、オークション用クライアントソフトを起動させ、図示しないがメニュー画面から出品処理を選択し、出品入力画面から出品品名、落札期日、最低落札価格、出品物についての説明など必要な情報を入力して送信することで、オークションへの出品を行うことができる。会員が入力した情報は、出品会員の会員ＩＤとともに出品ＩＤを付与して、出品情報として管理サーバに記録される。また、出品情報には、落札者が決まった後で、落札者の会員ＩＤ、落札価格等が追記される。
【００２４】
仲介サーバ２にはオークションの仲介を行うための仲介ソフトがインストールされ、管理サーバ１から送付された、出品ＩＤ等の出品情報が記録される。
会員は、オークション用クライアントソフトを起動させ、図示しないがメニュー画面から入札処理を選択することで出品物の一覧や、各出品物についての説明等を参照することができ、気に入ったものがあれば入札することができる。
そして、会員が入札した場合、会員ＩＤ等の入札情報は、管理サーバ１ではなく、仲介サーバ２ｘ、２ｙ、２ｚに送付され、対応する出品情報とともに、経過情報として記録される。後述するように、管理サーバ１には入札完了するまでは入札に関する情報は送付されず、また、入札金額そのものは仲介サーバ２にも送付されない。さらに、入札完了した場合にも、最終的に知られるのは、落札者および、その落札金額のみである。従って、会員は入札価格について、オークションの開催者も含め、誰にも知られることなく入札を行うことができる。
【００２５】
クライアント３にはオークションへの出品、入札等を行うためのオークション用クライアントソフトがインストールされ、オークションへの参加情報として、会員登録時に指定した会員ＩＤ、入札した出品物の出品ＩＤ、入札価格（同じ出品に対して複数回入札した場合には最後の入札価格）および入札日時が記録される。
なお、本システムにおいては、管理サーバ１と仲介サーバ２が物理的に異なった装置として説明を行うが、必ずしもその必要はなく、仲介サーバ２のうちの１台が管理サーバを兼用していても良いし、仲介サーバ２の全てが管理サーバ１としての機能を兼用し、例えば出品物によって負荷分散を行うようにしても良い。
【００２６】
図５は本実施形態において、仲介サーバ２に記録される経過情報のデータ構造図である。経過情報には、管理サーバ１から送付された、出品物に関する情報、すなわち出品ＩＤ、落札期日、最低落札価格が記録され、この出品物に対してクライアント３から入札が行われた場合には、入札情報すなわち入札者の会員ＩＤ毎に入札値が記録される。また入札終了した時点で、各入札者の落札値が記録される。
ここで、入札値、落札値は入札価格、落札価格そのものではない。入札値は入札価格を仲介サーバ２ｘ、２ｙ、２ｚでシェアした値、すなわち、３台の仲介サーバ２のうちの任意の２台に記録された値によって入札額を求めることが可能な値である。同様に、落札値は落札価格を仲介サーバ２ｘ、２ｙ、２ｚでシェアした値、すなわち、３台の仲介サーバ２のうちの任意の２台に記録された値によって落札額を求めることが可能な値である。このような値を求める方法は、「課題を解決するための手段」において説明した通りである。
【００２７】
図６は本実施形態におけるオークションシステムの動作を示すフローチャートである。フローチャートには出品が行われてから落札者が決まるまでの処理を記載している。オークションにおいては、この前後に出品物を管理サーバ１に登録する処理、落札者に対して入金を求める処理などが必要になるが、これらについては本発明とは特に関係がなく、また既存の各オークションシステムと同様の機能でよいので説明を省略する。
まず、管理サーバ１から仲介サーバ２ｘ、２ｙ、２ｚに出品情報（出品ＩＤ、落札期日、最低落札価格）が送付され、各仲介サーバ２は、送付された情報を経過情報に登録する（Ｓ４１）。
各仲介サーバ２は、落札期日（落札時刻を含む）になるまで、クライアントからの入札情報を受け入れる（Ｓ４２）。
【００２８】
この間、クライアント３で入札処理が行われると、クライアント３には参加情報として、入札対象とした出品物の出品ＩＤおよび入札価格が記録され、仲介サーバ２ｘ、２ｙ、２ｚに入札情報（会員ＩＤ、入札値）が送付される（Ｓ４３）。入札価格をａとすると、あるランダム多項式ｆ（ｘ）＝ａ＋ａ［１］ｘ ｍｏｄ ｐによって定義されるシェア｛ｆ（１），ｆ（２），ｆ（３）｝（＝｛ａ１，ａ２，ａ３｝）がそれぞれのサーバに対して送付される（ａ１が仲介サーバ２ｘに、ａ２が仲介サーバ２ｙに、ａ３が仲介サーバ２ｚに送付される）。このようなランダム多項式の定義方法については、既に説明した通りである。
こうすることでユーザの入札値ａはオークションサーバの内２台以上が結託しなければ秘密に保たれる。さらに秘密性を高めるためには、通信経路として秘密通信路を使用する、各シェアに電子署名をつけておくなどの方法を取ることもできる。
【００２９】
落札期日（落札時刻を含む）に達すると入札は終了し、各仲介サーバ２は落札価格を算出し、管理サーバ１に出品ＩＤとその落札価格、および入札に参加した全ての会員の会員ＩＤを送付する（Ｓ４４）。
入札終了後、入札に参加した会員がオークション用クライアントソフトを起動すると、例えばオークション用クライアントソフト起動時には会員ＩＤを管理サーバ１に通知するようにしておくことで、管理サーバ１は、送付された会員ＩＤと照合することができる。照合の結果、入札に参加した会員たった場合、管理サーバ１はオークション用クライアントソフトに、出品ＩＤと落札価格を送付する。オークション用クライアントソフトは送付された出品ＩＤ、落札価格とクライアント３に記録されている出品ＩＤ、落札価格を照合し、一致している場合には、管理サーバ１にその旨の情報および入札日時を通知する。不一致の場合には、クライアント３の画面上に落札できなかったことを表示する（Ｓ４５）。
【００３０】
管理サーバ１は、予め会員に通知していた所定の期間（例えば２４時間）を落札申出期限として待ち、その間、上述したようにクライアント３からの落札通知を受付ける（同じ額で落札した会員が複数人いる場合に、最初にその額を入札したものを選ぶためである）。所定の期間が経過すると、クライアント３から落札者として通知された全ての会員について、仲介サーバ２ｘ、２ｙ、２ｚに出品ＩＤと会員ＩＤを送付し、当該会員の入札額を確認するように要求する。仲介サーバ２は、当該出品物の経過情報から当該会員の入札価格を求め、管理サーバ１に送付する。管理サーバ１は送付された入札価格と落札価格を照合し、一致している場合には、そのうち入札日時が最も古いものについて、クライアント３から送付された会員ＩＤを落札者の会員ＩＤとして出品情報に記録するとともに、当該会員ＩＤのクライアント３に、出品ＩＤと落札した旨の情報を送付する。落札価格が一致しても入札時刻が最も古くない場合には、当該会員ＩＤのクライアント３に、出品ＩＤと落札できなかった旨の情報を送付する。不一致の場合には、当該クライアント３において何らかの不正が行われたことになるので、当該会員ＩＤのクライアント３に、警告メッセージ等を送付する。クライアント３は管理サーバ１から送付された情報により、クライアント３の画面上に落札したことの表示または警告表示を行う（Ｓ４６）。
【００３１】
図７は本実施形態における経過情報の概要説明図である。本図を使用して、Ｓ４３、Ｓ４４、Ｓ４６における仲介サーバ２の処理について説明を補足する。
まず、Ｓ４３において、クライアント３ａ、３ｂ、３ｃにおいて、それぞれの入札価格（ａ、ｂ、ｃ）をシェアした値、｛ａ１、ａ２、ａ３｝、｛ｂ１、ｂ２、ｂ３｝、｛ｃ１、ｃ２、ｃ３｝が生成され、仲介サーバ２に送付される。この結果、仲介サーバ２ｘ、２ｙ、２ｚには、入札情報としてそれそれ｛ａ１、ｂ１、ｃ１｝、｛ａ２、ｂ２、ｃ２｝、｛ａ３、ｂ３、ｃ３｝が記録される。
Ｓ４４において、各仲介サーバ２は入札情報を用いてユーザの入札価格を秘密にしたままトーナメント方式で勝者を決める。ここではａとｂのシェアからその勝者ｍａｘ（ａ，ｂ）に対応するシェアを計算する方式を用いることができる。
Ｓ４４において、各仲介サーバ２は入札情報を用いてユーザの入札価格を秘密にしたままトーナメント方式で勝者を決める。ここではａとｂのシェアから、その勝者ｍａｘ（ａ，ｂ）に対応するシェアを計算する方式、即ち前述の式（１２）を用いることができる（［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐ）。
【００３２】
つまり［ａ＜？ｂ］ｐ∈｛０，１｝を本発明方式によって秘密に計算し、それを秘密にしたままｍａｘ（ａ，ｂ）のシェアを上記の公式によって計算できる。このとき途中計算結果のｍａｘ（ａ，ｂ）も秘密したまま計算が可能である。これを最終的な勝者が決まるまでトーナメントで行い最後の勝者の入札価格のみに対応するシェア｛ｚ１、ｚ２、ｚ３｝（落札情報）が各仲介サーバ２に記録される。各仲介サーバ２は落札情報を公開しＬａｇｒａｎｇｅの補間公式で勝者の入札価格を求める。
Ｓ４６において、公開された入札価格に対応するシェアを仲介サーバ２に送信した会員ＩＤが、管理サーバ１から仲介サーバ２に通知されるので、仲介サーバ２は通知された会員から送信されたシェアを公開し、ユーザによる電子署名の正当性とシェアから計算される入札値が公開された最大入札値と一致するか確認する。勝者が複数いた場合は、前述したような早い者勝ちとする方式のほか、くじ引きや勝者のみで更にオークションを続行するなどができる。
【００３３】
次に本発明方式を用いた応用例としてＭｕｌｔｉｐａｒｔｙ Ｃｏｍｐｕｔａｔｉｏｎにおける除算プロトコルとｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎプロトコルの実現例を示す。ここでいう除算とは例えば秘密ａ，ｂが秘密分散されて［ａ］ｐ，［ｂ］ｐをユーザが持つときにａ＝ｋｂ＋ａ’ ｗｈｅｒｅ０≦ａ’＜ｂとなるようなｋを求めることである。上記のａ’を求めることをｂによるａのｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎと呼ぶ。つまりａ’はａをｂで割ったときの余りとなる。効率的な大小比較プロトコルによって［ａ］ｐ，［ｂ］ｐから［ｋ］ｐ，［ａ’］ｐを以下のように求めることができる。著者の知る限りでは本発明以外にｋやａ’を正確に求める実現例は今まで提案されていなかった。
まず前提としてｂに関してｂは秘密ではあるがそのビット長については分かっているとし、ｔビット長の秘密であるとする。つまり２＾（ｔ−１）＜ｂ＜２＾ｔとする。
このときｐ／（２＾ｔ）＜ｐ／ｂ＜ｐ／（２＾（ｔ−１））が成立する。ｐとｔは公開された値なのでｐ／ｂの範囲が分かる。ｐ／（２＾ｔ）の整数部分をｓとする。
【００３４】
以下、［ａ］ｐ，［ｂ］ｐから［ａ’］ｐを求めるプロトコルについて示す。
１． ユーザたちはまず以下のプロトコルを実行し［ａ’１］ｐを求める。このプロトコルで必要となる比較プロトコルは本発明による方式で効率的に計算できる。
［ａ’１］ｐ＝［ｓｂ＜？ａ］ｐ＊［ａ−ｓｂ］ｐ＋（１−［ｓｂ＜？ａ］ｐ）＊［ａ］ｐ
＝［ａ］ｐ−［ｓｂ＜？ａ］ｐ＊［ｓｂ］ｐ …（１３）
２． ユーザたちはステップ１のプロトコルを再度実行し［ａ’２］ｐを求める。
［ａ’２］ｐ＝［ａ’１］ｐ−［ｓｂ ＜？ａ’１］ｐ＊［ｓｂ］ｐ …（１４）
３． この時点でａ’２＜ｓｂが確実に成立している。ａ’２より２分探索的にｂの倍数を減算し最終結果である［ａ’］ｐを求める。今ａ’２はｓｂより小さいためａ’２がｓ／２＊ｂより大きいかどうか判定し、ａ’２がｓ／２＊ｂより大きければａ’２よりｓ／２＊ｂを減算するという方法を取る。ｓ／２がｓが奇数のため割り切れないときは桁上げを行い整数にする。たとえばｓ＝５のときｓ／２として３を採用する。以下のプロトコルを実行することでａ’３はｓ／２＊ｂより小さいことが成立する。
［ａ’３］ｐ＝［ａ’２］ｐ−［ｓ／２＊ｂ＜？ａ’２］ｐ＊［ｓ／２＊ｂ］ｐ …（１５）
同様にａ’４を以下のように求める。
［ａ’４］ｐ＝［ａ’３］ｐ−［ｓ／４＊ｂ＜？ａ’３］ｐ＊［ｓ／４＊ｂ］ｐ …（１６）
これを繰り返すことでｓを２で割り算し、１以下となるまで繰り返すことで［ａ’］ｐが求まる。このときほぼｌｏｇ（ｓ）回の比較プロトコルを繰り返すことで［ａ’］ｐが求まる。
【００３５】
上記のプロトコルの感覚的な実行例としてａ＝１７，ｂ＝５とするとａ’１＝１７−５＊２＝７，ａ’２＝７−５＝２，ａ’３＝ａ’＝２−０＊５＝２として最終的にａ’＝２が求まる。つまりａよりｂの倍数を引き算し、引き算した結果がｂより小さくなるまで繰り返す。
［ａ］ｐと［ｂ］ｐからａ＝ｋｂ＋ａ’ｗｈｅｒｅ ０≦ａ’＜ｂを満たすような［ａ’］ｐが上記の方法で求まれば［ｋｂ］ｐ＝［ａ］ｐ−［ａ’］ｐによって［ｋｂ］ｐが求まる。［ｂ］ｐから［ｂ＾（−１）］ｐを求めるプロトコルはＤＦＮＴプロトコルで既に提案されているためそのプロトコルを使えば［ｋ］ｐ＝［ｋｂ］ｐ＊［ｂ＾（−１）］ｐによって［ｋ］ｐが求まり、除算プロトコルを実行できる。
除算プロトコルを用いて例えば次のようなシステムの実現に応用できる。複数のＤＢの所有者がそれぞれのデータを秘匿し、ＤＢ内のプライバシーを保護しながら、全てのＤＢを統合した結果に対するある統計的な値を計算する、あるいはある規則性を発見する場合である。具体的には複数の病院が患者の症状に関するＤＢを保持しており、それぞれのＤＢを他の病院に対しては、患者のプライバシー保護のため秘匿しながら、ある症状に関する統計的な値や規則性を発見することである。これらの計算は一般に複雑で除算を正確に計算できなければ正しい値が求
る。
【００３６】
なお、本発明は以上の実施形態に限定されるのではなく、本発明の要旨を変更しない範囲において上記実施の形態を変形あるいは修正してもよいことはいうまでもない。例えば、共有機密データを暗号化しておき、クライアントコンピュータ側でデータを復号し、編集後書き込み前に暗号化し書き込むようにする。
また、共有機密フォルダおよび共有機密データに関するログを取得のも望ましい形態である。
また、機密フォルダ１０２１は、サーバ内１０２内に設けたが、外付けの記憶装置であってもよい。
【図面の簡単な説明】
【００３７】
【図１】本発明の最も単純な実施例である情報処理システムの構成図
【図２】本発明の論理演算に用いる真理値表
【図３】本発明の一実施例である情報処理システム全体構成図
【図４】本発明の一実施例である情報処理システムにおける主な情報資源の一覧
【図５】本発明の一実施例である情報処理システムにおける経過情報のデータ構造図
【図６】本発明の一実施例である情報処理システムの動作を示すフローチャート
【図７】本発明の一実施例である情報処理システムにおける経過情報の概要説明図
【符号の説明】
【００３８】
１０１、１０２、３ａ、３ｂ、３ｃ クライアント端末
１１１、１１２、１１３、１１４、２ｘ、２ｙ、２ｚ 秘密分散サーバ
１ 管理サーバ
１２１、４ ネットワーク
【技術分野】
【０００１】
本発明は、複数ユーザが各自秘密に入力を持ち、その入力を秘密にしたままである決められた関数を通信によって分散計算するＭｕｌｔｉｐａｒｔｙ Ｃｏｍｐｕｔａｔｉｏｎにおいて効率よく大小比較を秘密に計算する秘密分散情報処理システムに関する。
【背景技術】
【０００２】
分散計算技術において複数のユーザ（あるいは人工知能の分野ではエージェントなどとも呼ばれる）が協調して一つの計算を行う研究は昔から行われている。このような分散計算においてプライバシーを確保するために各ユーザの入力情報を秘密にしたままで協調した分散計算を行いたいという要請があり、それらを実現する分散計算技術として暗号分野では代表的な非特許文献１を含めてたくさんの研究が行われてきている。非特許文献１に示された技術（以下、非特許文献１の３名の著者の頭文字を取って「ＢＧＷ方式」と呼ぶ）はＳｈａｍｉｒによって提案された秘密の値を有限体上の多項式を用いてユーザ間で共有する技術（非特許文献２、非特許文献６参照）を使い、途中の計算結果を秘密にしながら最終的な計算結果を全員が得ることができる分散計算技術である。形式的に言えばｎユーザたちが各自の秘密の入力ｘ＿ｉを持ち関数（ｙ＿１，ｙ＿２，…，ｙ＿ｎ）＝ｆ（ｘ＿１，ｘ＿２，…，ｘ＿ｎ）を計算し各ユーザは対応する出力ｙ＿ｉのみを最後に得ることができる。
【０００３】
この分散計算技術はオークション理論や最適リソース割り当てのような各自が競争相手であり自分の入力を秘密にしたい環境であっても協調し全体として最適な経済効果を得るための通信プロトコルとして重要となってきている。例えば非特許文献３では安全なダブルオークションを実現するための通信方法として、特定のパラメータ設定を仮定した状況でのＢＧＷ方式を基にした大小比較プロトコルをソフトウェアとして実際に実装している。
ＢＧＷ方式では加算と乗算は効率的に計算できることが示されている。より複雑な計算を効率的に行うにはその他の演算も効率的に計算できることが必要である。大小比較演算は重要な基本演算のひとつであるが秘密の値がビット表現による多項式共有されていなければ効率的に計算できないという問題があった。それではビット表現による多項式共有を用いれば問題が解決するように見えるが、ビット表現による多項式共有では各ビット毎にデータを持つ必要があるため扱うデータ量が増加し、分散計算を行う際にユーザ間で相互にやりとりするデータの通信量が増えるという問題があった。今まではビット表現ではない通常の多項式共有によって入力を秘密にしたまま大小比較計算する効率的な方法が提案されずにいた。
【０００４】
しかし非特許文献４で多項式共有された値を秘密に比較するためのより現実的な効率を持った方法が提案された。ここで言う「秘密に比較する」とはｎユーザたちがｘ＿１，ｘ＿２を（ビット表現でなく通常の）多項式共有している状況で関数ｆがｆ（ｘ＿１，ｘ＿２）∈｛０，１｝として計算され、（ｘ＿１＜ｘ＿２）であれば１（つまりＴＲＵＥ）を、ｘ＿１≧ｘ＿２であれば０（つまりＦＡＬＳＥ）を出力することである。ここで出力値の０，１は再度多項式共有によってユーザ間で共有されている。
【０００５】
【非特許文献１】 Ｍ．Ｂｅｎ−Ｏｒ，Ｓ．Ｇｏｌｄｗａｓｓｅｒ，ａｎｄ Ａ．Ｗｉｇｄｅｒｓｏｎ，“Ｃｏｍｐｌｅｔｅｎｅｓｓ Ｔｈｅｏｒｅｍ ｆｏｒ Ｎｏｎ ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｆａｕｌｔ−ｔｏｌｅｒａｎｔ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ，ｐｐ．１−１０，１９８８．
【非特許文献２】 Ａｄｉ Ｓｈａｍｉｒ，“Ｈｏｗ ｔｏ ｓｈａｒｅ ａ ｓｅｃｒｅｔ”，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ＡＣＭ，２２（１１）：６１２−６１３，１９７９．
【非特許文献３】 Ｐｅｔｅｒ Ｂｏｇｅｔｏｆｔ，Ｉｖａｎ Ｄａｍｇａｒｄ，Ｔｈｏｍａｓ Ｊａｋｏｂｓｅｎ，Ｋｕｒｔ Ｎｉｅｌｓｅｎ，Ｊａｋｏｂ Ｐａｇｔｅｒ，ａｎｄ Ｔｏｍａｓ Ｔｏｆｔ，“Ｓｅｃｕｒｅ ｃｏｍｐｕｔｉｎｇ，ｅｃｏｎｏｍｙ，ａｎｄ ｔｒｕｓｔ：Ａ ｇｅｎｅｒｉｃ
ＲＳ−０５−１８，２００５．
【非特許文献４】 Ｉｖａｎ Ｄａｍｇａｒｄ，Ｍａｔｔｈｉａｓ Ｆｉｔｚｉ，Ｊｅｓｐｅｒ Ｂｕｕｓ Ｎｉｅｌｓｅｎ，ａｎｄ Ｔｏｍａｓ Ｔｏｆｔ，“Ｈｏｗ ｔｏ Ｓｐｌｉｔ ａ Ｓｈａｒｅｄ Ｓｅｃｒｅｔ ｉｎｔｏ Ｓｈａｒｅｄ Ｂｉｔｓ ｉｎ Ｃｏｎｓｔａｎｔ−Ｒｏｕｎｄ”，ＣｒｙｐｔｏｌｏｇｙｅＰｒｉｎｔ Ａｒｃｈｉｖｅ ２００５／１４０，Ｊｕｎｅ２３，２００５．
【非特許文献５】 Ｒｏｓａｒｉｏ Ｇｅｎｎａｒｏ，Ｍｉｃｈａｅｌ Ｏ．Ｒａｂｉｎ，ａｎｄ Ｔａｌ Ｒａｂｉｎ，“Ｓｉｍｐｌｉｆｉｅｄ ＶＳＳ ａｎｄ ｆａｓｔ−ｔｒａｃｋ ｍｕｌｔｉｐａｒｔｙ ｃｏｍｐｕｔａｔｉｏｎｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｔｈｒｅｓｈｏｌｄ ｃｒｙｐｔｏｇｒａｐｈｙ”，Ｉｎ Ｐｒｏｃ．１７ｔｈ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，ｐｐ．１０１−１１０，１９９８．
【非特許文献６】 Ｄｏｕｇｌａｓ Ｒ．Ｓｔｉｎｓｏｎ著、櫻井幸一監訳「暗号理論の基礎」共立出版株式会社、１９９６年１１月１日、ｐ．３４９−３５５
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記非特許文献４に記載の通信プロトコル（以下、非特許文献４の４名の著者の頭文字を取って「ＤＦＮＴプロトコル」と呼ぶ）は、大小比較に必要な計算以上のことを行っており通信オーバヘッドはまだ大きく改良の余地がある。
本発明の目的は、ＤＦＮＴプロトコルの通信回数と通信量を減らし、より効率のよい大小比較プロトコルを実現する情報処理システムを構築することである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明の秘密分散情報処理システムは、
クライアント端末と、ｎ個のサーバ１〜サーバｎとがネットワークによって接続され、前記クライアント端末が保持する秘密の数値ａに対する多項式ｆ＿ａ（ｘ）が、前記数値ａを定数項とする多項式を公開された素数ｐで除した剰余として定義される場合に、多項式ｆ＿ａ（ｘ）に対するシェアｆ＿ａ（１）〜ｆ＿ａ（ｎ）が、それぞれ前記サーバ１〜サーバｎに対して、前記ネットワークを経由して、前記クライアント端末から他のサーバには秘密に分散して配布される秘密分散情報処理システムであって、
前記クライアント端末が、
秘密の乱数ｒを発生させて、前記多項式のシェアｆ＿ｒ（１）〜ｆ＿ｒ（ｎ）をそれぞれ前記サーバ１〜サーバｎに秘密に配布し、
前記各サーバが、
それぞれ自己のサーバに配布されているシェア［ａ］ｐ及び［ｒ］ｐの和［ｃ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
公開された前記各サーバのシェア［ｃ］ｐから元の数値ｃを復元し、
前記復元された数値ｃと公開された数値ｄとの値から（ｃ−ｒ’＜？ｄ）≠（ｃ＜？ｄ）となるようなｒ’の範囲｛ｌｏｗ，…，ｈｉｇｈ｝を求め、
前記乱数ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に含まれるかを（ｌｏｗ−１＜？ｒ）と（ｒ＜？ｈｉｇｈ＋１）を判定することで求め、
当該ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に属するか否かの判定結果から、前記公開された数値ｄと前記数値ａとの大小関係を、数値ａを秘密に保持したまま求めることを特徴とする。
【０００８】
また、上記目的を達成するために、本発明の秘密分散情報処理システムは、前記特徴に加え、
第二のクライアント端末が更に前記ネットワークによって接続され、
前記第二のクライアント端末が保持する秘密の数値ｂに対する前記多項式のシェアｆ＿ｂ（１）〜ｆ＿ｂ（ｎ）が前記サーバ１〜サーバｎに秘密に分散されて保持され、
前記各サーバが、
それぞれ自己のサーバに配布されているシェアから、式［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
前記公開された結果から、前記数値ａと前記数値ｂとの大小関係を、秘密に保持したまま求めることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ユーザたちあるいはユーザの代理人としてのエージェントプログラムが入力を秘密にしながら大小比較を含む分散計算を、ビット表現による多項式共有によって引き起こされる通信データ量の増加無しに、効率的に行うことが可能となり、入力の秘匿性を必要とされるオークションなどの大小比較演算を含む演算を効率的に実行できる情報処理システムを構築できる。
実際にＤＦＮＴプロトコルでは通信回数と総通信量はパラメータＬ（多項式共有における素数ｐのビット長）によって１３３Ｒｏｕｎｄｓ／２５８Ｌ＋２２０Ｌ＊ｌｏｇ２（Ｌ）と表現されるが、本発明では４３Ｒｏｕｎｄｓ／４２０Ｌ＋６となる。パラメータＬは実用上、通常Ｌ＞８と仮定できるため、理論的には、通信によるオーバヘッドを通信回数では約１／３に、また通信量では約１／２に軽減できる。
【発明を実施するための最良の形態】
【００１０】
本発明による大小比較のための具体的な情報処理システムを説明する前に、まず基本となるＢＧＷの通信方式について簡単に述べ、いくつかの用語、記号、数式の定義を行う。ＢＧＷ方式では計算される関数に与えられる引数がＳｈａｍｉｒの方式によって秘密分散される。Ｓｈａｍｉｒの多項式共有による秘密分散とは次式（１）のようなある有限体上の多項式によって与えられる。
【００１１】
ここでｐはある公開された奇数の素数であり各ａ［ｉ］は有限体Ｚｐからランダムに選ばれた値である。例えばあるユーザが秘密の入力ａを秘密分散するときは上記ｆ＿ａ（）のような定数項にａをもつランダム多項式を生成し（つまり上記の多項式の各係数をランダムに選択する）、他ユーザ１≦ｉ≦に対してｆ＿ａ（ｉ）（これはシェアと呼ばれる）を秘密通信路を通じて配布する。このようにａが多項式によって秘密分散されている（つまりシェアｆ＿ａ（ｉ）がユーザｉに保持されている状態）ことを以下では［ａ］ｐと表記する。多項式ｆ＿ａ（ｘ）はｔ＋１個のシェアを集めることでＬａｇｒａｎｇｅの補間公式と呼ばれる標準的な方法によって復元できる。
【００１２】
加算とは、ａとｂが多項式ｆ＿ａ（ｘ）とｆ＿ｂ（ｘ）で秘密分散されているときａ＋ｂ ｍｏｄ ｐのシェアを計算することであるが、これは各ユーザｉがｆ＿ａ（ｉ）＋ｆ＿ｂ（ｉ）を行うことで計算できる。このときａ＋ｂを復元することなしにａもｂも秘密のままでａ＋ｂのシェアを各ユーザが計算できることがＢＧＷ方式の利点である。また非特許文献５の乗算方式を用いることで［ａ］ｐと［ｂ］ｐから［ａｂ ｍｏｄ ｐ］ｐのシェアも計算できることが知られている。
このようにａとｂが多項式共有による秘密分散されている状況から、ユーザたちが加算、乗算のシェアを計算することを以下では［ａ＋ｂ ｍｏｄ ｐ］ｐ＝［ａ］ｐ＋［ｂ］ｐ，［ａｂ］ｐ＝［ａ］ｐ＊［ｂ］ｐと表記することにする。
【００１３】
図１に、本発明を実施する場合の基本的な秘密分散情報処理システムの構成を表す。本システムは、クライアント１０１、１０２等と、ｎ個のサーバ（この図では４個）１１１、１１２、１１３、１１４及びそれらを接続するネットワーク１２１から構成される。
クライアント１０１が秘密に保持する数値ａについて、ｆ＿ａ（ｘ）が前述のような多項式で表現され、シェアｆ＿ａ（１）、ｆ＿ａ（２）、ｆ＿ａ（３）、ｆ＿ａ（４）が、それぞれサーバ１１１、サーバ１１２、サーバ１１３、サーバ１１４に対して、クライアント１０１からネットワーク１２１経由で、互いに他のサーバやクライアントには知られないように、秘密に送付される。同様に、クライアント１０２が秘密に保持する数値ｂについても、多項式の各要素であるｆ＿ｂ（１）、ｆ＿ｂ（２）、ｆ＿ｂ（３）、ｆ＿ｂ（４）が、それぞれサーバ１１１、サーバ１１２、サーバ１１３、サーバ１１４に対して、クライアント１０２からネットワーク１２１経由で秘密に送付される。
【００１４】
更に、非特許文献４では他の部品となる通信プロトコルが提案されている。本発明の中でも、これらの部品を使うため利用する部品についてのみ述べる。
秘密乱数生成プロトコルであるＤＦＮＴプロトコルによって有限体Ｚｐからあるランダムな秘密の値をユーザたちが誰も知ることなく生成できる。これを［ｒ∈Ｚｐ］ｐと表す。このとき秘密乱数ｒがユーザたちによって秘密分散されている状態を作り出すことができる。ただしどのユーザもｒの値は知らないことに注意。
また、ＤＦＮＴプロトコルによって乱数の中でも特に０，１のどちらかを秘密に生成することができる。これを［ｂ∈｛０，１｝］ｐと表す。このとき秘密ビットｂがユーザたちによって秘密分散されている状態を作り出すことができる。ただしどのユーザもｂが０か１か知らないことに注意。
【００１５】
ここで「ｂｉｔｗｉｓｅ秘密分散」についてまず説明する。これは今まで「ビット表現による多項式共有」と呼んでいたものに相当する。いま各ａ［ｉ］∈｛０，１｝であるｋ個の秘密分散［ａ［ｋ−１］］ｐ，…，［ａ［０］］ｐがあり（ａ［ｋ−１］，ａ［ｋ−２］，…，ａ［０］）のビット列によって、ａ＝Σ（（２＾ｉ）＊ａ［ｉ］）（０≦ｉ≦ｋ−１）となるａを表現しているとする。このときａをｋ個のビットによって「ｂｉｔｗｉｓｅ秘密分散」していると表現し、［ａ］＿Ｂと表記する。このときａの通常の秘密分散［ａ］ｐはＢＧＷ方式の加算の性質から、次式（２）によって得ることができる。
［ａ］ｐ＝Σ（２＾ｉ）＊［ａ［ｉ］］ｐ …（２）
【００１６】
ＤＦＮＴプロトコルはＢｉｔｗｉｓｅ Ｌｅｓｓ−Ｔｈａｎプロトコルとしてｂｉｔｗｉｓｅ秘密分散された［ａ］＿Ｂと［ｂ］＿Ｂを比較し、ａ＜ｂであれば［１］ｐ、ａ！＜ｂつまりａ≧ｂであれば［０］ｐの秘密分散を結果である０，１を秘密にしたまま作り出すプロトコルである。このプロトコルの計算結果を［ａ＜？Ｂｂ］ｐのように表す。つまりｂｉｔｗｉｓｅ秘密分散されたａとｂを秘密にしたままでその大小比較結果の｛０，１｝をまた秘密分散できる。これはａとｂがｂｉｔｗｉｓｅ秘密分散されていれば大小比較を効率的に行えるという事実に基づいている。
ＤＦＮＴプロトコルは秘密ｂｉｔｗｉｓｅ乱数生成プロトコルとして秘密ビット生成プロトコルをパラレルに実行し最初からビット表現で乱数ｒを生成する。このプロトコルで乱数を生成することを［ｒ∈Ｚｐ］＿Ｂのように表す。
【００１７】
本発明は上記の部品プロトコルを使いａとｂが［ａ］ｐと［ｂ］ｐとして多項式共有による秘密分散（ｂｉｔｗｉｓｅ秘密分散ではない）されているときに、［ａ＜？ｂ］ｐ，ｗｈｅｒｅ（ａ＜ｂ）＝１ ｉｆａ＜ｂ，となるような計算を行う方法である。
多くの場合、ａとｂの値は［ａ］＿Ｂ，［ｂ］＿Ｂで与えられるよりも、［ａ］ｐ，［ｂ］ｐで与えられるため、本発明を用いれば［ａ］ｐから［ａ］＿Ｂへの変換を回避できることに注意。
【００１８】
以下に本発明の秘密分散情報処理システムにおける計算方法について述べる。
まずここでは秘密分散された［ａ］ｐと有限体の位数ｐの半分の値との比較を行いその結果の０，１を秘密に判定できると仮定し、その結果の秘密分散を［ａ＜？ｐ／２］ｐとする。このとき最終目標である［ａ＜？ｂ］ｐは、図２の真理値表によって、各論理値（ａ＜？ｐ／２）と（ｂ＜？ｐ／２）と（（ａ−ｂ ｍｏｄ ｐ）＜？ｐ／２）から決定できる。
よってｚは、次式（３）の論理式で与えられる。
ｚ＝ｗ（１−ｘ）＋（１−ｗ）（１−ｘ）（１−ｙ）＋ｗｘ（１−ｙ） …（３）
ここで、第１項ｗ（１−ｘ）は図２の２０１から、第２項（１−ｗ）（１−ｘ）（１−ｙ）は２０２から、第３項ｗｘ（１−ｙ）は２０３から、それぞれ求められる式である。
ユーザたちはｗ，ｘ，ｙ∈｛０，１｝のそれぞれの秘密分散を計算できればＢＧＷ方式の加算と乗算によってｚつまり（ａ＜？ｂ）の秘密分散である［ａ＜？ｂ］ｐを秘密に計算することができる。
【００１９】
次に秘密分散された［ａ］ｐから［ａ＜？ｐ／２］ｐを計算する判定プロトコルについて述べる。
ユーザたちは以下のプロトコルに従って計算する。
１． 秘密ｂｉｔｗｉｓｅ乱数生成プロトコルによって［ｒ∈Ｚｐ］＿Ｂを得る。また［ｒ∈Ｚｐ］＿Ｂからユーザたちは［ｒ∈Ｚｐ］ｐを式（２）によって容易に計算できる。
２． ユーザたちは［ｃ］ｐ＝［ａ］ｐ＋［ｒ］ｐを実行し、［ｃ］ｐのシェアを公開することでｃを復元しｃ＝ａ＋ｒ ｍｏｄ ｐを公開する。ｒが秘密の値であるためａ＋ｒを公開してもａに関する情報は秘匿されたままである。
３． ユーザたちは公開したｃから論理式が（ｃ−ｒ’ｍｏｄ ｐ＜？ｐ／２）≠（ｃ＜？ｐ／２）を満たすようなｒ’の範囲を求める。この範囲を｛ｌｏｗ，…，ｈｉｇｈ｝とする。ここではｐが公開されていることに注意。
４． ユーザたちはｒが｛ｌｏｗ，…，ｈｉｇｈ｝の範囲に入っているかをＢｉｔｗｉｓｅ Ｌｅｓｓ−Ｔｈａｎプロトコルを用いて
［ｒ∈？｛ｌｏｗ，…，ｈｉｇｈ｝］ｐ＝［ｌｏｗ−１ ＜？Ｂ ｒ］ｐ ＊ ［ｒ ＜？Ｂ ｈｉｇｈ＋１］ｐ …（４）
を計算することで得られる。ここでｒは［ｒ］＿Ｂとしてユーザたちに保持されており、ｌｏｗとｈｉｇｈは公開された値であるため［ｌｏｗ］＿Ｂ，［ｈｉｇｈ］＿Ｂとしてユーザたちに保持されることが可能であることに注意。
５． 最後にユーザたちは値ｃとｐ／２の大小関係を用いた場合分けによって以下のように［ａ＜？ｐ／２］ｐを求める。
［ａ＜？ｐ／２］ｐ＝１−［ｒ∈？｛ｌｏｗ，…，ｈｉｇｈ｝］ｐ ｉｆ （ｃ＜？ｐ／２）＝１． …（５）
［ａ＜？ｐ／２］ｐ＝［ｒ∈？｛ｌｏｗ，…，ｈｉｇｈ｝］ｐ ｉｆ （ｃ＜？ｐ／２）＝０． …（６）
【００２０】
ここで具体例で上記のプロトコルについて説明する。
ｐ＝７，ａ＝４としユーザたちはａを秘密にしたままで［４＜？７／２］７を計算しようとしているとする。このときユーザたちは秘密の乱数ｒ＝５を生成したとする。すると公開される値はｃ＝４＋５ｍｏｄ７＝２である。ｃから上記のｒ’の範囲を求めると｛３，４，５｝となる。ｒ＝５が｛３，４，５｝の範囲に含まれていればｃとａ（＝ｃ−ｒ ｍｏｄ ｐ）はｐ／２＝７／２を境としてそれぞれ反対側に存在することになる。ｒが｛３，４，５｝に含まれているかは［３−１＜？ｒ］ｐ＊［ｒ＜？５＋１］ｐの結果から計算できる。この計算結果が１であれば（ｃ＜？ｐ／２）の論理値が反転するようプロトコルを構成すればよい。
【００２１】
上記の［ａ＜ｐ／２］ｐを判定するプロトコルを応用し、公開された定数であるｐ／２を他の値にする、あるいは比較演算を逆にすることで次のような判定プロトコルも容易に構成できる。ここでａ，ｂ∈｛０，１，…，ｐ−１｝は多項式共有された体Ｚｐのある値とする。
１． ａがゼロか判定するプロトコル。
［ａ＝？０］ｐ＝［ａ＜？１］ｐ …（７）
２． ａとｂが等しいか判定するプロトコル。
［ａ＝？ｂ］ｐ＝［ａ−ｂ＜？１］ｐ …（８）
３． ａとある定数ｃ１，ｃ２∈Ｚｐ（ｃ１＜ｃ２とする）との様々な判定プロトコル。
［ａ＜？ｃ１］ｐ …（９）
［ｃ１＜？ａ］ｐ …（１０）
［ａ∈？｛ｃ１，…，ｃ２｝］ｐ＝［ｃ１−１＜？ａ］ｐ＊［ａ ＜？ ｃ２＋１］ｐ …（１１）
４． ａとｂから大きい方を選択するプロトコル
［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐ …（１２）
【００２２】
次に、本発明を実施する場合の、より具体的な実施形態（以下、「本実施形態」と記載する。）について図３以下を参照して具体的に説明する。ここでは複数サーバによるオークションシステムを考える。このオークションシステム（以下、「本システム」または単に「システム」と記載する。）では入札値の中の最大値とその入札者のみが公表され他の入札値は秘匿することが出来る。
図３は本システム全体の構成図である。システムは、管理サーバ１、３台以上の仲介サーバ２（図３においては仲介サーバ２ｘ、２ｙ、２ｚの３台のサーバを記載している。以下、特に区分する必要がない場合、「仲介サーバ２」と総称する。）、複数台のクライアント３（図３においてはクライアント３ａ、３ｂ、３ｃの３台のクライアントを記載している。以下、特に区分する必要がない場合、「クライアント３」と総称する。）および、ネットワーク（通信回線）４から構成される。図示した構成要素以外にも通信機器（ルータ等）が存在するが、本発明とは特に関係がないので説明を省略する。
管理サーバ１、仲介サーバ２、クライアント３はいずれもＰＣ（パーソナル・コンピュータ）等によって実現できる。また、通信回線４は、管理サーバ１、仲介サーバ２、クライアント３を相互に通信可能に接続することができれば、有線、無線を問わず、どのような技術によって実装されてもよいが、以降はインターネットを想定して説明する。
【００２３】
図４は本実施形態において管理サーバ１、仲介サーバ２およびクライアント３の記録装置に置かれる主な情報資源の一覧である。
管理サーバ１にはオークションの会員管理、出品管理等を行うための管理ソフトがインストールされ、会員が各クライアント３にダウンロードして使用するためのオークション用クライアントソフト、会員情報、出品情報などが記録されている。
すなわち、オークションに出品したり、入札したりすることを希望する者は、例えば、管理サーバが公開するＷＥＢページから会員ＩＤ、認証用パスワード、決済用のクレジット番号等を会員情報として登録することで、オークションの会員になることができ、オークションの会員（以下、「会員」と記載する。）になったものは、オークションに出品、入札するために必要なオークション用クライアントソフトを、管理サーバからダウンロードすることができる。会員は、オークション用クライアントソフトを起動させ、図示しないがメニュー画面から出品処理を選択し、出品入力画面から出品品名、落札期日、最低落札価格、出品物についての説明など必要な情報を入力して送信することで、オークションへの出品を行うことができる。会員が入力した情報は、出品会員の会員ＩＤとともに出品ＩＤを付与して、出品情報として管理サーバに記録される。また、出品情報には、落札者が決まった後で、落札者の会員ＩＤ、落札価格等が追記される。
【００２４】
仲介サーバ２にはオークションの仲介を行うための仲介ソフトがインストールされ、管理サーバ１から送付された、出品ＩＤ等の出品情報が記録される。
会員は、オークション用クライアントソフトを起動させ、図示しないがメニュー画面から入札処理を選択することで出品物の一覧や、各出品物についての説明等を参照することができ、気に入ったものがあれば入札することができる。
そして、会員が入札した場合、会員ＩＤ等の入札情報は、管理サーバ１ではなく、仲介サーバ２ｘ、２ｙ、２ｚに送付され、対応する出品情報とともに、経過情報として記録される。後述するように、管理サーバ１には入札完了するまでは入札に関する情報は送付されず、また、入札金額そのものは仲介サーバ２にも送付されない。さらに、入札完了した場合にも、最終的に知られるのは、落札者および、その落札金額のみである。従って、会員は入札価格について、オークションの開催者も含め、誰にも知られることなく入札を行うことができる。
【００２５】
クライアント３にはオークションへの出品、入札等を行うためのオークション用クライアントソフトがインストールされ、オークションへの参加情報として、会員登録時に指定した会員ＩＤ、入札した出品物の出品ＩＤ、入札価格（同じ出品に対して複数回入札した場合には最後の入札価格）および入札日時が記録される。
なお、本システムにおいては、管理サーバ１と仲介サーバ２が物理的に異なった装置として説明を行うが、必ずしもその必要はなく、仲介サーバ２のうちの１台が管理サーバを兼用していても良いし、仲介サーバ２の全てが管理サーバ１としての機能を兼用し、例えば出品物によって負荷分散を行うようにしても良い。
【００２６】
図５は本実施形態において、仲介サーバ２に記録される経過情報のデータ構造図である。経過情報には、管理サーバ１から送付された、出品物に関する情報、すなわち出品ＩＤ、落札期日、最低落札価格が記録され、この出品物に対してクライアント３から入札が行われた場合には、入札情報すなわち入札者の会員ＩＤ毎に入札値が記録される。また入札終了した時点で、各入札者の落札値が記録される。
ここで、入札値、落札値は入札価格、落札価格そのものではない。入札値は入札価格を仲介サーバ２ｘ、２ｙ、２ｚでシェアした値、すなわち、３台の仲介サーバ２のうちの任意の２台に記録された値によって入札額を求めることが可能な値である。同様に、落札値は落札価格を仲介サーバ２ｘ、２ｙ、２ｚでシェアした値、すなわち、３台の仲介サーバ２のうちの任意の２台に記録された値によって落札額を求めることが可能な値である。このような値を求める方法は、「課題を解決するための手段」において説明した通りである。
【００２７】
図６は本実施形態におけるオークションシステムの動作を示すフローチャートである。フローチャートには出品が行われてから落札者が決まるまでの処理を記載している。オークションにおいては、この前後に出品物を管理サーバ１に登録する処理、落札者に対して入金を求める処理などが必要になるが、これらについては本発明とは特に関係がなく、また既存の各オークションシステムと同様の機能でよいので説明を省略する。
まず、管理サーバ１から仲介サーバ２ｘ、２ｙ、２ｚに出品情報（出品ＩＤ、落札期日、最低落札価格）が送付され、各仲介サーバ２は、送付された情報を経過情報に登録する（Ｓ４１）。
各仲介サーバ２は、落札期日（落札時刻を含む）になるまで、クライアントからの入札情報を受け入れる（Ｓ４２）。
【００２８】
この間、クライアント３で入札処理が行われると、クライアント３には参加情報として、入札対象とした出品物の出品ＩＤおよび入札価格が記録され、仲介サーバ２ｘ、２ｙ、２ｚに入札情報（会員ＩＤ、入札値）が送付される（Ｓ４３）。入札価格をａとすると、あるランダム多項式ｆ（ｘ）＝ａ＋ａ［１］ｘ ｍｏｄ ｐによって定義されるシェア｛ｆ（１），ｆ（２），ｆ（３）｝（＝｛ａ１，ａ２，ａ３｝）がそれぞれのサーバに対して送付される（ａ１が仲介サーバ２ｘに、ａ２が仲介サーバ２ｙに、ａ３が仲介サーバ２ｚに送付される）。このようなランダム多項式の定義方法については、既に説明した通りである。
こうすることでユーザの入札値ａはオークションサーバの内２台以上が結託しなければ秘密に保たれる。さらに秘密性を高めるためには、通信経路として秘密通信路を使用する、各シェアに電子署名をつけておくなどの方法を取ることもできる。
【００２９】
落札期日（落札時刻を含む）に達すると入札は終了し、各仲介サーバ２は落札価格を算出し、管理サーバ１に出品ＩＤとその落札価格、および入札に参加した全ての会員の会員ＩＤを送付する（Ｓ４４）。
入札終了後、入札に参加した会員がオークション用クライアントソフトを起動すると、例えばオークション用クライアントソフト起動時には会員ＩＤを管理サーバ１に通知するようにしておくことで、管理サーバ１は、送付された会員ＩＤと照合することができる。照合の結果、入札に参加した会員たった場合、管理サーバ１はオークション用クライアントソフトに、出品ＩＤと落札価格を送付する。オークション用クライアントソフトは送付された出品ＩＤ、落札価格とクライアント３に記録されている出品ＩＤ、落札価格を照合し、一致している場合には、管理サーバ１にその旨の情報および入札日時を通知する。不一致の場合には、クライアント３の画面上に落札できなかったことを表示する（Ｓ４５）。
【００３０】
管理サーバ１は、予め会員に通知していた所定の期間（例えば２４時間）を落札申出期限として待ち、その間、上述したようにクライアント３からの落札通知を受付ける（同じ額で落札した会員が複数人いる場合に、最初にその額を入札したものを選ぶためである）。所定の期間が経過すると、クライアント３から落札者として通知された全ての会員について、仲介サーバ２ｘ、２ｙ、２ｚに出品ＩＤと会員ＩＤを送付し、当該会員の入札額を確認するように要求する。仲介サーバ２は、当該出品物の経過情報から当該会員の入札価格を求め、管理サーバ１に送付する。管理サーバ１は送付された入札価格と落札価格を照合し、一致している場合には、そのうち入札日時が最も古いものについて、クライアント３から送付された会員ＩＤを落札者の会員ＩＤとして出品情報に記録するとともに、当該会員ＩＤのクライアント３に、出品ＩＤと落札した旨の情報を送付する。落札価格が一致しても入札時刻が最も古くない場合には、当該会員ＩＤのクライアント３に、出品ＩＤと落札できなかった旨の情報を送付する。不一致の場合には、当該クライアント３において何らかの不正が行われたことになるので、当該会員ＩＤのクライアント３に、警告メッセージ等を送付する。クライアント３は管理サーバ１から送付された情報により、クライアント３の画面上に落札したことの表示または警告表示を行う（Ｓ４６）。
【００３１】
図７は本実施形態における経過情報の概要説明図である。本図を使用して、Ｓ４３、Ｓ４４、Ｓ４６における仲介サーバ２の処理について説明を補足する。
まず、Ｓ４３において、クライアント３ａ、３ｂ、３ｃにおいて、それぞれの入札価格（ａ、ｂ、ｃ）をシェアした値、｛ａ１、ａ２、ａ３｝、｛ｂ１、ｂ２、ｂ３｝、｛ｃ１、ｃ２、ｃ３｝が生成され、仲介サーバ２に送付される。この結果、仲介サーバ２ｘ、２ｙ、２ｚには、入札情報としてそれそれ｛ａ１、ｂ１、ｃ１｝、｛ａ２、ｂ２、ｃ２｝、｛ａ３、ｂ３、ｃ３｝が記録される。
Ｓ４４において、各仲介サーバ２は入札情報を用いてユーザの入札価格を秘密にしたままトーナメント方式で勝者を決める。ここではａとｂのシェアからその勝者ｍａｘ（ａ，ｂ）に対応するシェアを計算する方式を用いることができる。
Ｓ４４において、各仲介サーバ２は入札情報を用いてユーザの入札価格を秘密にしたままトーナメント方式で勝者を決める。ここではａとｂのシェアから、その勝者ｍａｘ（ａ，ｂ）に対応するシェアを計算する方式、即ち前述の式（１２）を用いることができる（［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐ）。
【００３２】
つまり［ａ＜？ｂ］ｐ∈｛０，１｝を本発明方式によって秘密に計算し、それを秘密にしたままｍａｘ（ａ，ｂ）のシェアを上記の公式によって計算できる。このとき途中計算結果のｍａｘ（ａ，ｂ）も秘密したまま計算が可能である。これを最終的な勝者が決まるまでトーナメントで行い最後の勝者の入札価格のみに対応するシェア｛ｚ１、ｚ２、ｚ３｝（落札情報）が各仲介サーバ２に記録される。各仲介サーバ２は落札情報を公開しＬａｇｒａｎｇｅの補間公式で勝者の入札価格を求める。
Ｓ４６において、公開された入札価格に対応するシェアを仲介サーバ２に送信した会員ＩＤが、管理サーバ１から仲介サーバ２に通知されるので、仲介サーバ２は通知された会員から送信されたシェアを公開し、ユーザによる電子署名の正当性とシェアから計算される入札値が公開された最大入札値と一致するか確認する。勝者が複数いた場合は、前述したような早い者勝ちとする方式のほか、くじ引きや勝者のみで更にオークションを続行するなどができる。
【００３３】
次に本発明方式を用いた応用例としてＭｕｌｔｉｐａｒｔｙ Ｃｏｍｐｕｔａｔｉｏｎにおける除算プロトコルとｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎプロトコルの実現例を示す。ここでいう除算とは例えば秘密ａ，ｂが秘密分散されて［ａ］ｐ，［ｂ］ｐをユーザが持つときにａ＝ｋｂ＋ａ’ ｗｈｅｒｅ０≦ａ’＜ｂとなるようなｋを求めることである。上記のａ’を求めることをｂによるａのｍｏｄｕｌａｒ ｒｅｄｕｃｔｉｏｎと呼ぶ。つまりａ’はａをｂで割ったときの余りとなる。効率的な大小比較プロトコルによって［ａ］ｐ，［ｂ］ｐから［ｋ］ｐ，［ａ’］ｐを以下のように求めることができる。著者の知る限りでは本発明以外にｋやａ’を正確に求める実現例は今まで提案されていなかった。
まず前提としてｂに関してｂは秘密ではあるがそのビット長については分かっているとし、ｔビット長の秘密であるとする。つまり２＾（ｔ−１）＜ｂ＜２＾ｔとする。
このときｐ／（２＾ｔ）＜ｐ／ｂ＜ｐ／（２＾（ｔ−１））が成立する。ｐとｔは公開された値なのでｐ／ｂの範囲が分かる。ｐ／（２＾ｔ）の整数部分をｓとする。
【００３４】
以下、［ａ］ｐ，［ｂ］ｐから［ａ’］ｐを求めるプロトコルについて示す。
１． ユーザたちはまず以下のプロトコルを実行し［ａ’１］ｐを求める。このプロトコルで必要となる比較プロトコルは本発明による方式で効率的に計算できる。
［ａ’１］ｐ＝［ｓｂ＜？ａ］ｐ＊［ａ−ｓｂ］ｐ＋（１−［ｓｂ＜？ａ］ｐ）＊［ａ］ｐ
＝［ａ］ｐ−［ｓｂ＜？ａ］ｐ＊［ｓｂ］ｐ …（１３）
２． ユーザたちはステップ１のプロトコルを再度実行し［ａ’２］ｐを求める。
［ａ’２］ｐ＝［ａ’１］ｐ−［ｓｂ ＜？ａ’１］ｐ＊［ｓｂ］ｐ …（１４）
３． この時点でａ’２＜ｓｂが確実に成立している。ａ’２より２分探索的にｂの倍数を減算し最終結果である［ａ’］ｐを求める。今ａ’２はｓｂより小さいためａ’２がｓ／２＊ｂより大きいかどうか判定し、ａ’２がｓ／２＊ｂより大きければａ’２よりｓ／２＊ｂを減算するという方法を取る。ｓ／２がｓが奇数のため割り切れないときは桁上げを行い整数にする。たとえばｓ＝５のときｓ／２として３を採用する。以下のプロトコルを実行することでａ’３はｓ／２＊ｂより小さいことが成立する。
［ａ’３］ｐ＝［ａ’２］ｐ−［ｓ／２＊ｂ＜？ａ’２］ｐ＊［ｓ／２＊ｂ］ｐ …（１５）
同様にａ’４を以下のように求める。
［ａ’４］ｐ＝［ａ’３］ｐ−［ｓ／４＊ｂ＜？ａ’３］ｐ＊［ｓ／４＊ｂ］ｐ …（１６）
これを繰り返すことでｓを２で割り算し、１以下となるまで繰り返すことで［ａ’］ｐが求まる。このときほぼｌｏｇ（ｓ）回の比較プロトコルを繰り返すことで［ａ’］ｐが求まる。
【００３５】
上記のプロトコルの感覚的な実行例としてａ＝１７，ｂ＝５とするとａ’１＝１７−５＊２＝７，ａ’２＝７−５＝２，ａ’３＝ａ’＝２−０＊５＝２として最終的にａ’＝２が求まる。つまりａよりｂの倍数を引き算し、引き算した結果がｂより小さくなるまで繰り返す。
［ａ］ｐと［ｂ］ｐからａ＝ｋｂ＋ａ’ｗｈｅｒｅ ０≦ａ’＜ｂを満たすような［ａ’］ｐが上記の方法で求まれば［ｋｂ］ｐ＝［ａ］ｐ−［ａ’］ｐによって［ｋｂ］ｐが求まる。［ｂ］ｐから［ｂ＾（−１）］ｐを求めるプロトコルはＤＦＮＴプロトコルで既に提案されているためそのプロトコルを使えば［ｋ］ｐ＝［ｋｂ］ｐ＊［ｂ＾（−１）］ｐによって［ｋ］ｐが求まり、除算プロトコルを実行できる。
除算プロトコルを用いて例えば次のようなシステムの実現に応用できる。複数のＤＢの所有者がそれぞれのデータを秘匿し、ＤＢ内のプライバシーを保護しながら、全てのＤＢを統合した結果に対するある統計的な値を計算する、あるいはある規則性を発見する場合である。具体的には複数の病院が患者の症状に関するＤＢを保持しており、それぞれのＤＢを他の病院に対しては、患者のプライバシー保護のため秘匿しながら、ある症状に関する統計的な値や規則性を発見することである。これらの計算は一般に複雑で除算を正確に計算できなければ正しい値が求
る。
【００３６】
なお、本発明は以上の実施形態に限定されるのではなく、本発明の要旨を変更しない範囲において上記実施の形態を変形あるいは修正してもよいことはいうまでもない。例えば、共有機密データを暗号化しておき、クライアントコンピュータ側でデータを復号し、編集後書き込み前に暗号化し書き込むようにする。
また、共有機密フォルダおよび共有機密データに関するログを取得のも望ましい形態である。
また、機密フォルダ１０２１は、サーバ内１０２内に設けたが、外付けの記憶装置であってもよい。
【図面の簡単な説明】
【００３７】
【図１】本発明の最も単純な実施例である情報処理システムの構成図
【図２】本発明の論理演算に用いる真理値表
【図３】本発明の一実施例である情報処理システム全体構成図
【図４】本発明の一実施例である情報処理システムにおける主な情報資源の一覧
【図５】本発明の一実施例である情報処理システムにおける経過情報のデータ構造図
【図６】本発明の一実施例である情報処理システムの動作を示すフローチャート
【図７】本発明の一実施例である情報処理システムにおける経過情報の概要説明図
【符号の説明】
【００３８】
１０１、１０２、３ａ、３ｂ、３ｃ クライアント端末
１１１、１１２、１１３、１１４、２ｘ、２ｙ、２ｚ 秘密分散サーバ
１ 管理サーバ
１２１、４ ネットワーク
【特許請求の範囲】
【請求項１】
クライアント端末と、ｎ個のサーバ１〜サーバｎとがネットワークによって接続され、前記クライアント端末が保持する秘密の数値ａに対する多項式ｆ＿ａ（ｘ）が、前記数値ａを定数項とする多項式を公開された素数ｐで除した剰余として定義される場合に、多項式ｆ＿ａ（ｘ）に対するシェアｆ＿ａ（１）〜ｆ＿ａ（ｎ）が、それぞれ前記サーバ１〜サーバｎに対して、前記ネットワークを経由して、前記クライアント端末から他のサーバには秘密に分散して配布される秘密分散情報処理システムであって、
前記クライアント端末が、
秘密の乱数ｒを発生させて、前記多項式のシェアｆ＿ｒ（１）〜ｆ＿ｒ（ｎ）をそれぞれ前記サーバ１〜サーバｎに秘密に配布し、
前記各サーバが、
それぞれ自己のサーバに配布されているシェア［ａ］ｐ及び［ｒ］ｐの和［ｃ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
公開された前記各サーバのシェア［ｃ］ｐから元の数値ｃを復元し、
前記復元された数値ｃと公開された数値ｄとの値から（ｃ−ｒ’＜？ｄ）≠（ｃ＜？ｄ）となるようなｒ’の範囲｛ｌｏｗ，…，ｈｉｇｈ｝を求め、
前記乱数ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に含まれるかを（ｌｏｗ−１＜？ｒ）と（ｒ＜？ｈｉｇｈ＋１）を判定することで求め、
当該ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に属するか否かの判定結果から、前記公開された数値ｄと前記数値ａとの大小関係を、数値ａを秘密に保持したまま求めることを特徴とする秘密分散情報処理システム。
【請求項２】
請求項１に記載の秘密分散情報処理システムにおいて、
第二のクライアント端末が更に前記ネットワークによって接続され、
前記第二のクライアント端末が保持する秘密の数値ｂに対する前記多項式のシェアｆ＿ｂ（１）〜ｆ＿ｂ（ｎ）が前記サーバ１〜サーバｎに秘密に分散されて保持され、
前記各サーバが、
それぞれ自己のサーバに配布されているシェアから、式［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
前記公開された結果から、前記数値ａと前記数値ｂとの大小関係を、秘密に保持したまま求めることを特徴とする秘密分散情報処理システム。
【請求項１】
クライアント端末と、ｎ個のサーバ１〜サーバｎとがネットワークによって接続され、前記クライアント端末が保持する秘密の数値ａに対する多項式ｆ＿ａ（ｘ）が、前記数値ａを定数項とする多項式を公開された素数ｐで除した剰余として定義される場合に、多項式ｆ＿ａ（ｘ）に対するシェアｆ＿ａ（１）〜ｆ＿ａ（ｎ）が、それぞれ前記サーバ１〜サーバｎに対して、前記ネットワークを経由して、前記クライアント端末から他のサーバには秘密に分散して配布される秘密分散情報処理システムであって、
前記クライアント端末が、
秘密の乱数ｒを発生させて、前記多項式のシェアｆ＿ｒ（１）〜ｆ＿ｒ（ｎ）をそれぞれ前記サーバ１〜サーバｎに秘密に配布し、
前記各サーバが、
それぞれ自己のサーバに配布されているシェア［ａ］ｐ及び［ｒ］ｐの和［ｃ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
公開された前記各サーバのシェア［ｃ］ｐから元の数値ｃを復元し、
前記復元された数値ｃと公開された数値ｄとの値から（ｃ−ｒ’＜？ｄ）≠（ｃ＜？ｄ）となるようなｒ’の範囲｛ｌｏｗ，…，ｈｉｇｈ｝を求め、
前記乱数ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に含まれるかを（ｌｏｗ−１＜？ｒ）と（ｒ＜？ｈｉｇｈ＋１）を判定することで求め、
当該ｒが範囲｛ｌｏｗ，…，ｈｉｇｈ｝に属するか否かの判定結果から、前記公開された数値ｄと前記数値ａとの大小関係を、数値ａを秘密に保持したまま求めることを特徴とする秘密分散情報処理システム。
【請求項２】
請求項１に記載の秘密分散情報処理システムにおいて、
第二のクライアント端末が更に前記ネットワークによって接続され、
前記第二のクライアント端末が保持する秘密の数値ｂに対する前記多項式のシェアｆ＿ｂ（１）〜ｆ＿ｂ（ｎ）が前記サーバ１〜サーバｎに秘密に分散されて保持され、
前記各サーバが、
それぞれ自己のサーバに配布されているシェアから、式［ｍａｘ（ａ，ｂ）］ｐ＝［ａ＜？ｂ］ｐ＊［ｂ−ａ］ｐ＋［ａ］ｐを計算して他のサーバ及びクライアント端末に公開し、
前記クライアント端末または各サーバのいずれかが、
前記公開された結果から、前記数値ａと前記数値ｂとの大小関係を、秘密に保持したまま求めることを特徴とする秘密分散情報処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−２０８７１（Ｐ２００８−２０８７１Ａ）
【公開日】平成２０年１月３１日（２００８．１．３１）
【国際特許分類】
【出願番号】特願２００６−２２０６１３（Ｐ２００６−２２０６１３）
【出願日】平成１８年７月１４日（２００６．７．１４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 研究集会名： ２００６年暗号と情報セキュリティシンポジウム 主催者名： 電子情報通信学会 情報セキュリティ研究専門委員会 開催日： 平成１８年１月１７日
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
【公開日】平成２０年１月３１日（２００８．１．３１）
【国際特許分類】
【出願日】平成１８年７月１４日（２００６．７．１４）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 研究集会名： ２００６年暗号と情報セキュリティシンポジウム 主催者名： 電子情報通信学会 情報セキュリティ研究専門委員会 開催日： 平成１８年１月１７日
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
[ Back to top ]