(57)【特許請求の範囲】
【請求項１】
第１の入力値ｍＡを秘匿したままで、該第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出する秘密計算システムであって、
第１の秘密計算装置と、第３の秘密計算装置と、前記論理回路関数ｆを保有している第２の秘密計算装置と、を有し、
前記第３の秘密計算装置は、ランダムなデータＷ＝（Ｗ０，Ｗ１）を生成し、前記第１の入力値ｍＡが分割演算子＊で２つに分割された一方の断片ｔから、前記断片ｔの各ビットｂに対応したデータＷｂを生成し、前記データＷｂを前記第１の秘密計算装置に送信し、前記データＷ＝（Ｗ０，Ｗ１）を前記第２の秘密計算装置に送信し、
前記第２の秘密計算装置は、前記第１の入力値ｍＡが分割された他方の断片ｓ、前記論理回路関数ｆ、および前記データＷから、前記データＷｂを入力として前記演算結果ｆ（ｍＡ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆを秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置は、前記データＴと前記データＷｂとを入力とし、前記演算結果ｆ（ｍＡ）を算出する、秘密計算システム。
【請求項２】
前記第１の秘密計算装置は、前記第１の入力値ｍＡを保有しており、前記第１の入力値ｍＡを分割演算子＊で断片ｓと断片ｔの２つに分割し、前記断片ｓを前記第２の秘密計算装置に送信し、前記断片ｔを前記第３の秘密計算装置に送信する、請求項１に記載の秘密計算システム。
【請求項３】
前記論理回路関数ｆは、２つの入力値を入力とする論理回路関数ｆ（ｘ，ｙ）であり、第２の入力値ｍＢを前記第２の秘密計算装置が保有しており、
前記第２の秘密計算装置は、前記断片ｓ、前記論理回路関数ｆ、および前記データＷに加えて更に前記入力値ｍＢを用いて、前記データＷｂを入力として前記演算結果ｆ（ｍＡ，ｍＢ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆ（ｘ，ｍＢ）を秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置は、前記データＴと前記データＷｂとを入力とし、前記第１および第２の入力値ｍＡ，ｍＢに対する論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を算出する、請求項１または２に記載の秘密計算システム。
【請求項４】
前記第１の入力値ｍＡを、ｍＡ＝ｓ＊ｔを満たすように、前記断片ｓ，ｔに分割し、前記断片ｔを前記第３の秘密計算装置に送信し、前記断片ｓを前記第２の秘密計算装置に送信する変換装置を更に有する、請求項１に記載の秘密計算システム。
【請求項５】
第１、第２、および第３の秘密計算装置により、第１の入力値ｍＡを秘匿したままで、該第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出するための秘密計算方法であって、
第２の秘密計算装置にて前記論理回路関数ｆを保持しておき、
前記第３の秘密計算装置において、ランダムなデータＷ＝（Ｗ０，Ｗ１）を生成し、前記第１の入力値ｍＡが分割演算子＊で２つに分割された一方の断片ｔから、前記断片ｔの各ビットｂに対応したデータＷｂを生成し、前記データＷｂを前記第１の秘密計算装置に送信し、前記データＷ＝（Ｗ０，Ｗ１）を前記第２の秘密計算装置に送信し、
前記第２の秘密計算装置において、前記第１の入力値ｍＡが分割された他方の断片ｓ、前記論理回路関数ｆ、および前記データＷから、前記データＷｂを入力として前記演算結果ｆ（ｍＡ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆを秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置において、前記データＴと前記データＷｂとを入力とし、前記演算結果ｆ（ｍＡ）を算出する、秘密計算方法。
【請求項６】
前記第１の秘密計算装置において、前記第１の入力値ｍＡを保有しており、前記第１の入力値ｍＡを分割演算子＊で断片ｓと断片ｔの２つに分割し、前記断片ｓを前記第２の秘密計算装置に送信し、前記断片ｔを前記第３の秘密計算装置に送信する、請求項５に記載の秘密計算方法。
【請求項７】
前記論理回路関数ｆは、２つの入力値を入力とする論理回路関数ｆ（ｘ，ｙ）であり、第２の入力値ｍＢを前記第２の秘密計算装置にて保有しており、
前記第２の秘密計算装置において、前記断片ｓ、前記論理回路関数ｆ、および前記データＷに加えて更に前記入力値ｍＢを用いて、前記データＷｂを入力として前記演算結果ｆ（ｍＡ，ｍＢ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆ（ｘ，ｍＢ）を秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置において、前記データＴと前記データＷｂとを入力とし、前記第１および第２の入力値ｍＡ，ｍＢに対する論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を算出する、請求項５または６に記載の秘密計算方法。
【請求項８】
３台のコンピュータをそれぞれ第１、第２、および第３の秘密計算装置として動作させ、第１の入力値ｍＡを秘匿したままで、該第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出する秘密計算プログラムであって、
前記第３の秘密計算装置が、ランダムなデータＷ＝（Ｗ０，Ｗ１）を生成し、前記第１の入力値ｍＡが分割演算子＊で２つに分割された一方の断片ｔから、前記断片ｔの各ビットｂに対応したデータＷｂを生成し、前記データＷｂを前記第１の秘密計算装置に送信し、前記データＷ＝（Ｗ０，Ｗ１）を前記第２の秘密計算装置に送信する手順と、
前記論理回路関数ｆを保有している前記第２の秘密計算装置が、前記第１の入力値ｍＡが分割された他方の断片ｓ、前記論理回路関数ｆ、および前記データＷから、前記データＷｂを入力として前記演算結果ｆ（ｍＡ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆを秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信する手順と、
前記第１の秘密計算装置が、前記データＴと前記データＷｂとを入力とし、前記演算結果ｆ（ｍＡ）を算出する手順と、をそれぞれ第１、第２、および第３の秘密計算装置としてコンピュータに実行させるための秘密計算プログラム。
【請求項９】
前記第１の秘密計算装置が、前記第１の入力値ｍＡを保有しており、前記第１の入力値ｍＡを分割演算子＊で断片ｓと断片ｔの２つに分割し、前記断片ｓを前記第２の秘密計算装置に送信し、前記断片ｔを前記第３の秘密計算装置に送信する、請求項８に記載の秘密計算プログラム。
【請求項１０】
前記論理回路関数ｆは、２つの入力値を入力とする論理回路関数ｆ（ｘ，ｙ）であり、第２の入力値ｍＢを前記第２の秘密計算装置が保有しており、
前記第２の秘密計算装置が、前記断片ｓ、前記論理回路関数ｆ、および前記データＷに加えて更に前記入力値ｍＢを用いて、前記データＷｂを入力として前記演算結果ｆ（ｍＡ，ｍＢ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆ（ｘ，ｍＢ）を秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置が、前記データＴと前記データＷｂとを入力とし、前記第１および第２の入力値ｍＡ，ｍＢに対する論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を算出する、請求項８または９に記載の秘密計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関し、特に、入力値を秘匿したまま、その入力値に対する演算の結果を得る技術に関する。
【背景技術】
【０００２】
非特許文献１には、入力値を秘匿したままで演算結果を得る技術が開示されている。図４は、非特許文献１に開示された技術を用いた秘密計算システムの構成を示すブロック図である。図４を参照すると、秘密計算システムは、秘密計算装置８１Ａと秘密計算装置８１Ｂを有している。
【０００３】
秘密計算装置８１Ａは、論理回路関数ｆ（ｘ，ｙ）と、ｘへの入力となるビット列ｍAとを保有している。秘密計算装置８１Ｂは、同じく論理回路関数ｆ（ｘ，ｙ）と、ｙへの入力となるビット列ｍBとを保有している。
【０００４】
秘密計算装置８１Ａと秘密計算装置８１Ｂが互いに通信することにより、秘密計算装置８１ＡがｍBを容易に復元できるデータを得ることなく、秘密計算装置８１ＢがｍAを容易に復元できるデータを得ることなく、秘密計算装置８１Ａ，Ｂのいずれか一方または両方が論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍA，ｍB）を得ることができる。
【０００５】
非特許文献１に開示された方法について概説する。以下に、一例として、秘密計算装置８１Ａがｆ（ｍA，ｍB）を得るための処理手順を挙げる。
【０００６】
（第１のステップ）
論理回路関数ｆ（ｘ，ｙ）と、ｙへの入力となるビット列ｍBとを保有する秘密計算装置Ｂは、以下の（ａ）〜（ｄ）を実行することにより、論理回路関数ｆ（ｘ，ｍB）を秘匿化する。そして、秘密計算装置８１Ｂは、論理回路関数ｆ（ｘ，ｍB）を秘匿化したデータＴgを秘密計算装置８１Ａに送る。
（ａ）  秘密計算装置８１Ｂは、論理回路関数ｆ（ｘ，ｍB）の各ワイヤーｉに対して、固定長の乱数
【数１】
0005078632.tif 000002
を生成し、それぞれ０，１に対応させる。
（ｂ）  次に、秘密計算装置８１Ｂはランダムビットｃiを生成する。
（ｃ）  更に、秘密計算装置８１Ｂは、
【数２】
0005078632.tif 000003
をワイヤーｉに対応させる。ここで
【数３】
0005078632.tif 000004
とする。
（ｄ）次に、秘密計算装置８１Ｂは、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【数４】
0005078632.tif 000005
を行単位でランダムな順番に並べたものをＴgとする。このＴgの集合は、ｆの秘匿化データとして秘密計算装置８１Ａに送信される。ここでコロンの左側をラベル、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力として固定長の乱数を出力する関数であるとする。
【０００７】
（第２のステップ）
ｘへの入力となるビット列ｍAを保有する秘密計算装置８１Ａは、秘密計算装置８１Ｂと１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行する。これにより、秘密計算装置８１Ａは、ｍAのビットｂを入力とするワイヤーに対応するデータ
【数５】
0005078632.tif 000006
を得る。
【０００８】
（第３のステップ）
続いて、秘密計算装置８１Ａは、秘密計算装置８１Ｂから受信したデータＴgと、
【数６】
0005078632.tif 000007
とを用いて、論理回路関数ｆの最終段のワイヤーの出力
【数７】
0005078632.tif 000008
を算出する。
【０００９】
（第４のステップ）
更に、秘密計算装置８１Ａは、
【数８】
0005078632.tif 000009
から、演算結果ｆ（ｍA，ｍB）のビット
【数９】
0005078632.tif 000010
を得る。
【００１０】
上記処理手順における第３のステップでは、秘密計算装置８１Ａは、入力ワイヤーｉ，ｊ、出力ワイヤーｋのゲートに対応するデータＴgと、
【数１０】
0005078632.tif 000011
とが与えられたとき、先ずデータＴgからラベル
【数１１】
0005078632.tif 000012
を持つデータ
【数１２】
0005078632.tif 000013
を取り出し、
【数１３】
0005078632.tif 000014
を計算する。これにより、出力ワイヤーに対応するデータ
【数１４】
0005078632.tif 000015
が得られる。他のゲートについても同様の処理を行えばよい。
【００１１】
また、第４のステップでは、秘密計算装置８１Ａは、例えばゲートｇが論理回路関数ｆの最終段ゲートである場合に、ｃk＝０とすることで
【数１５】
0005078632.tif 000016
から
【数１６】
0005078632.tif 000017
を得ることができる。
【００１２】
以上説明したように、非特許文献１の方法では、第２のステップにおいて秘密計算装置８１Ａと秘密計算装置８１Ｂが１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行する必要がある。１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルは、秘密計算装置８１Ａがデータｄ0，ｄ1を保有し、秘密計算装置８１Ｂがビットｂを保有するとき、秘密計算装置８１Ｂはｄbを得ることができるが、
【数１７】
0005078632.tif 000018
を得ることはできず、かつ秘密計算装置８１Ａはｂを得ることができないような特徴をもつプロトコルである。このプロトコルの詳細は、非特許文献２に説明がある。
【００１３】
非特許文献３には、入力値を秘匿したままで演算結果を得る他の技術が開示されている。図５は、非特許文献３に開示された技術を用いた秘密計算システムの構成を示すブロック図である。図５を参照すると、秘密計算システムは、複数の変換装置９０1〜９０Nと秘密計算装置９１Ａ，９１Ｂとを有している。２つの秘密計算装置９１Ａ，９１Ｂによって秘密計算装置群９１をなしている。
【００１４】
秘密計算装置９１Ａ，９１Ｂからなる秘密計算装置群９１は、各変換装置９０1〜９０Nが保有するデータｍi（１≦ｉ≦Ｎ）を用いて、入力値ｍiを容易に復元できるデータを得ることなく、論理回路関数ｆの演算結果ｆ（ｍ1，・・・，ｍN）を求める。
【００１５】
以下にその処理手順について概説する。
【００１６】
なお、これ以降の説明では、記号を簡略化するため、特に必要が無ければｍiの添え字を省略することにする。
【００１７】
（第１のステップ）
まず、秘密計算装置９１Ｂは、以下の（ａ）〜（ｄ）を実行することにより、論理回路関数ｆを秘匿化する。そして、秘密計算装置９１Ｂは、論理回路関数ｆを秘匿化したデータＴgを、論理回路関数ｆの秘匿化データとして秘密計算装置９１Ａに送信する。
（ａ）  秘密計算装置９１Ｂは論理回路関数ｆの各ワイヤーｉに対して、固定長の乱数
【数１８】
0005078632.tif 000019
を生成し、それぞれ０，１に対応させる。
（ｂ）  次に、秘密計算装置９１Ｂは、ランダムビットｃiを生成する。
（ｃ）  更に、秘密計算装置９１Ｂは、
【数１９】
0005078632.tif 000020
をワイヤーｉに対応させる。ここで
【数２０】
0005078632.tif 000021
とする。
（ｄ）  更に、秘密計算装置９１Ｂは、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【数２１】
0005078632.tif 000022
を行単位でランダムな順番に並べたものをデータＴgとする。このデータＴgの集合が論理回路関数ｆの秘匿化データとして秘密計算装置９１Ａに送信される。ここでコロンの左側をラベル、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力して固定長の乱数を出力する関数であるとする。
【００１８】
（第２のステップ）
各変換装置９０1〜９０Nが、秘密計算装置９１Ａ，９１Ｂとともに、ｐｒｏｘｙ  １−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒを実行することにより、秘密計算装置９１Ａはｍの各ビットｂの入力ワイヤーｉに対応するデータ
【数２２】
0005078632.tif 000023
を得る。
【００１９】
（第３のステップ）
更に、秘密計算装置９１Ａは、データＴgと、
【数２３】
0005078632.tif 000024
とを用いて、論理回路関数ｆの最終段のワイヤーの出力
【数２４】
0005078632.tif 000025
を得る。
【００２０】
（第４のステップ）
更に、秘密計算装置９１Ａは、
【数２５】
0005078632.tif 000026
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
【数２６】
0005078632.tif 000027
を得る。
【００２１】
上記処理手順の第２のステップでは、ｐｒｏｘｙ  １−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒが用いられている。このプロトコルは、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒを拡張したプロトコルである。このプロトコルによれば、変換装置９０1〜９０Nが保有しているデータに関する情報ｂを秘密計算装置９１Ａに知られることなく、変換装置９０1〜９０Nの代わりに秘密計算装置９１Ａが
【数２７】
0005078632.tif 000028
を算出することができる。
【非特許文献１】Ａ．Ｃ．Ｙａｏ，  Ｈｏｗ  ｔｏ  ｇｅｎｅｒａｔｅ  ａｎｄ  ｅｘｃｈａｎｇｅ  ｓｅｃｒｅｔｓ，Ｐｒｏｃ．  ｏｆ  ＦＯＣＳ  ’８６，  ｐｐ．１６２−１６７，ＩＥＥＥ  Ｐｒｅｓｓ，１９８６．
【非特許文献２】Ｓ．Ｅｖｅｎ，  Ｏ．Ｇｏｌｄｒｅｉｃｈ  ａｎｄ  Ａ．Ｌｅｍｐｅｌ，Ａ  ｒａｎｄｏｍｉｚｅｄ  ｐｒｏｔｏｃｏｌ  ｆｏｒ  ｓｉｇｎｉｎｇ  ｃｏｎｔｒａｃｔｓ，  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，Ｖｏｌ．２８，Ｎｏ．６，ｐｐ．６３７−６４７，１９８５．
【非特許文献３】Ｍ．Ｎａｏｒ，  Ｂ．Ｐｉｎｋａｓ，  ａｎｄ  Ｒ．Ｓｕｍｎｅｒ，Ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ａｕｃｔｉｏｎｓ  ａｎｄ  ｍｅｃｈａｎｉｓｍ  ｄｅｓｉｇｎ，Ｐｒｏｃ．  ｏｆ  ＡＣＭ  ＥＣ  ’９９，ｐｐ．１２９−１３９，ＡＣＭ  Ｐｒｅｓｓ，１９９９．
【発明の開示】
【発明が解決しようとする課題】
【００２２】
上述したように、非特許文献１に開示された方法では、秘密計算装置８１Ａ，８１Ｂが１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行する必要がある。Ｄ．Ｍａｌｋｈｉ，  Ｎ．Ｎｉｓａｎ，  Ｂ．Ｐｉｎｋａｓ，  ａｎｄ  Ｙ．Ｓｅｌｌａ，Ｆａｉｒｐｌａｙ  −  ａ  ｓｅｃｕｒｅ  ｔｗｏ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｓｙｓｔｅｍ，Ｐｒｏｃ．  ｏｆ  ＵＳＥＮＩＸ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ，ｐｐ．２８７−３０２，ＵＳＥＮＩＸ，２００４．という文献によれば、実装上、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行するための計算量が秘密計算システム全体の計算量の大部分を占めると報告されている。したがって、実装上、その部分の処理を軽くすれば、秘密計算システムを構成する秘密計算装置の負荷を低減することができる。
【００２３】
また、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを拡張したｐｒｏｘｙ  １−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒを実行する際に必要となる計算量は、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒと同程度である。
【００２４】
本発明の目的は、秘密計算装置の負荷を低減した秘密計算システムを提供することである。
【課題を解決するための手段】
【００２５】
上記目的を達成するために、本発明の秘密計算システムは、第１の入力値ｍＡを秘匿したままで、該第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出する秘密計算システムであって、
第１の秘密計算装置と、第３の秘密計算装置と、前記論理回路関数ｆを保有している第２の秘密計算装置と、を有し、
前記第３の秘密計算装置は、ランダムなデータＷ＝（Ｗ０，Ｗ１）を生成し、前記第１の入力値ｍＡが分割演算子＊で２つに分割された一方の断片ｔから、前記断片ｔの各ビットｂに対応したデータＷｂを生成し、前記データＷｂを前記第１の秘密計算装置に送信し、前記データＷ＝（Ｗ０，Ｗ１）を前記第２の秘密計算装置に送信し、
前記第２の秘密計算装置は、前記第１の入力値ｍＡが分割された他方の断片ｓ、前記論理回路関数ｆ、および前記データＷから、前記データＷｂを入力として前記演算結果ｆ（ｍＡ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆを秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置は、前記データＴと前記データＷｂとを入力とし、前記演算結果ｆ（ｍＡ）を算出する。
【００２６】
また、前記第１の秘密計算装置は、前記第１の入力値ｍＡを保有しており、前記第１の入力値ｍＡを分割演算子＊で断片ｓと断片ｔの２つに分割し、前記断片ｓを前記第２の秘密計算装置に送信し、前記断片ｔを前記第３の秘密計算装置に送信するとしてもよい。
【００２７】
また、前記論理回路関数ｆは、２つの入力値を入力とする論理回路関数ｆ（ｘ，ｙ）であり、第２の入力値ｍＢを前記第２の秘密計算装置が保有しており、
前記第２の秘密計算装置は、前記断片ｓ、前記論理回路関数ｆ、および前記データＷに加えて更に前記入力値ｍＢを用いて、前記データＷｂを入力として前記演算結果ｆ（ｍＡ，ｍＢ）を求めることができる、前記断片ｓを埋め込んだ論理回路関数ｆ（ｘ，ｍＢ）を秘匿化したデータＴを生成し、前記第１の秘密計算装置に送信し、
前記第１の秘密計算装置は、前記データＴと前記データＷｂとを入力とし、前記第１および第２の入力値ｍＡ，ｍＢに対する論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を算出するとしてもよい。
【００２８】
また、本発明の秘密計算システムは、前記第１の入力値ｍＡを、ｍＡ＝ｓ＊ｔを満たすように、前記断片ｓ，ｔに分割し、前記断片ｔを前記第３の秘密計算装置に送信し、前記断片ｓを前記第２の秘密計算装置に送信する変換装置を更に有するとしてもよい。
【発明の効果】
【００２９】
本発明によれば、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを秘密計算装置のいずれも実行する必要がないので、秘密計算装置の負荷を大幅に低減することができる。
【発明を実施するための最良の形態】
【００３０】
本発明を実施するための形態について図面を参照して詳細に説明する。
【００３１】
本実施形態の秘密計算システムは３つの秘密計算装置からなるシステムであり、入力値を秘匿したまま、その入力値に対する論理回路関数ｆの演算結果を算出する。この種の秘密計算システムは、例えば、プライバシーを保護しつつ個人的な情報を活用する様々なシステムに適用することができる。具体的な例として、秘密計算システムは、オークションを含む任意の情報集計システムであるとしてもよい。各ユーザーの情報を秘匿したまま、それらの情報に対する所定の演算の結果を得る。例えば、オークション結果や多数決による意思決定の結果などを演算結果として得ることが考えられる。また、他の例として、各ユーザーが保有するデータを他者に知られること無く集計し、それらのデータを元にした各種統計処理やマイニング処理を行うことも可能である。また、更に他の例として、秘密計算システムは、生体認証システムであるとしてもよい。各ユーザーの生体情報を秘匿したままで、生体情報が正当なものであるか否か判定することができる。
【００３２】
（第１の実施例）
図１は、第１の実施例による秘密計算システムの構成を示すブロック図である。図１を参照すると、秘密計算システムは、秘密計算装置１１Ａ，１１Ｂ，１１Ｃからなるシステムであり、入力値ｍA，ｍBを秘匿したまま、論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍA，ｍB）を算出する。
【００３３】
秘密計算装置１１Ａが入力値ｍAを保持している。秘密計算装置１１Ｂが入力値ｍBと論理回路関数ｆ（ｘ，ｙ）とを保持している。
【００３４】
秘密計算装置１１Ａは、入力値ｍAを分割演算子＊で断片ｓと断片ｔの２つに分割し、断片ｓを秘密計算装置１１Ｂに送信し、断片ｔを秘密計算装置１１Ｃに送信する。
【００３５】
秘密計算装置１１Ｃは、秘密計算装置１１Ａから受信した断片ｔから、断片ｔの各ビットｂに対応したデータＷｂと、各ビットｂに対する（１−ｂ）に対応したデータＷ（１−ｂ）とを生成する。そして、秘密計算装置１１Ｃは、データＷｂを秘密計算装置１１Ａに送信し、ｂおよび（１−ｂ）との対応を特定せずにデータＷｂおよびデータＷ（１−ｂ）を含むデータＷ＝（Ｗ０，Ｗ１）を秘密計算装置１１Ｂに送信する。
【００３６】
秘密計算装置１１Ｂは、秘密計算装置１１Ａから受信した断片ｓと、保持している入力値ｍBおよび論理回路関数ｆ（ｘ，ｙ）と、秘密計算装置１１Ｃから受信したデータＷとから、データＷｂを入力として演算結果ｆ（ｍA，ｍB）を求めることができる、断片ｓを埋め込んだ論理回路関数ｆ（ｘ，ｍB）を秘匿化したデータＴを生成する。そして、秘密計算装置１１Ｂは、データＴを秘密計算装置１１Ａに送信する。
【００３７】
秘密計算装置１１Ａは、秘密計算装置１１Ｂから受信したデータＴと、秘密計算装置１１Ｃから受信したデータＷｂとを入力とし、演算結果ｆ（ｍA，ｍB）を算出する。
【００３８】
以下、本実施例の秘密計算システムおよび各装置の動作について、より具体的に説明する。演算結果ｆ（ｍA，ｍB）を求めるまでの手順は５つのステップからなる。
【００３９】
（第１のステップ）
論理回路関数ｆ（ｘ，ｙ）のｘへの入力となるビット列ｍAを保有する秘密計算装置１１Ａは、入力値ｍAを
【数２８】
0005078632.tif 000029
となるｓ，ｔに分割する。そして、秘密計算装置１１Ａは、ｓを秘密計算装置１１Ｂに、ｔを秘密計算装置１１Ｃにそれぞれ送る。
【００４０】
（第２のステップ）
秘密計算装置１１Ｃは、論理回路関数ｆにおける入力値ｍAの入力ワイヤーｉ毎に、ランダムビットｃi、および固定長の乱数とｃiの組
【数２９】
0005078632.tif 000030
を生成する。そして、秘密計算装置１１Ｃは、Ｗiを秘密計算装置１１Ｂに、
【数３０】
0005078632.tif 000031
を秘密計算装置１１Ａにそれぞれ送る。ここで
【数３１】
0005078632.tif 000032
であり、ｂ′は、ｉへの入力を入力値ｍAの下位ｗ番目のビットとしたとき、断片ｔの下位ｗ番目のビットである。
【００４１】
（第３のステップ）
論理回路関数ｆ（ｘ，ｙ）、ｙへの入力となるビット列ｍB、および秘密計算装置１１Ａから受け取った断片ｓを保有する秘密計算装置Ｂは、以下の（ａ）〜（ｄ）を実行することにより、論理回路関数ｆ（ｘ，ｍB）を秘匿化する。
（ａ）  ｆ（ｘ，ｍB）の各ワイヤーｉに対して、固定長の乱数
【数３２】
0005078632.tif 000033
を生成し、それぞれ０，１に対応させる。ただし、ｍAの入力ワイヤーに対しては秘密計算装置１１Ｃから受け取った
【数３３】
0005078632.tif 000034
を対応させる。
（ｂ）  次に、秘密計算装置１１Ｂはランダムビットｃiを生成する。ただし、ｍAの入力ワイヤーに対しては秘密計算装置１１Ｃから受け取ったｃiを対応させる。
（ｃ）  更に、秘密計算装置１１Ｂは、
【数３４】
0005078632.tif 000035
をワイヤーｉに対応させる。ただし、ワイヤーｉがｍAの下位ｗ番目のビットを入力とする場合は、
【数３５】
0005078632.tif 000036
を用いる。ここで、ｂはｓの下位ｗ番目のビットであるとする。
（ｄ）  ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【数３６】
0005078632.tif 000037
をランダムな順番に並べたものをＴgとする。このＴgの集合が論理回路関数ｆを秘匿化したデータとなる。秘密計算装置１１Ｂは、Ｔgの集合をｆの秘匿化データとして秘密計算装置１１Ａに送信する。ここでコロンの左側をラベル、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力として固定長の乱数を出力する関数であるとする。
【００４２】
（第４のステップ）
秘密計算装置１１Ａは、データＴgと
【数３７】
0005078632.tif 000038
を用いて、ｆの最終段のワイヤーの出力
【数３８】
0005078632.tif 000039
を得る。
【００４３】
（第５のステップ）
秘密計算装置１１Ａは、
【数３９】
0005078632.tif 000040
から、ｆ（ｍA，ｍB）のビット
【数４０】
0005078632.tif 000041
を得る。
【００４４】
上記処理手順の第４のステップでは、入力ワイヤーｉ，ｊ、出力ワイヤーｋのゲートｇに対応するＴgと、
【数４１】
0005078632.tif 000042
とが与えられたとき、先ずＴgからラベル
【数４２】
0005078632.tif 000043
を持つデータ
【数４３】
0005078632.tif 000044
を取り出し、
【数４４】
0005078632.tif 000045
を計算するとよい。これにより、上記出力ワイヤーに対応するデータ
【数４５】
0005078632.tif 000046
が得られる。他のゲートについても同様の処理を行えばよい。
【００４５】
また、第５のステップについては、例えばｇがｆの最終段ゲートである場合、ｃk＝０とすることにより、
【数４６】
0005078632.tif 000047
から
【数４７】
0005078632.tif 000048
を得ることができる。
【００４６】
上述した本実施形態の秘密計算システムによる処理は各装置によって実行される。以下、装置間の信号の送受信を含む処理の流れについて概説する。図２は、本実施形態の秘密計算システムの動作を示すシーケンス図である。
【００４７】
図２を参照すると、まず、秘密計算装置１１Ａは、入力値ｍAをｓ，ｔに分割し（ステップ１０１）、ｓを秘密計算装置１１Ｂに送信し（ステップ１０２）、ｔを秘密計算装置１１Ｃに送信する（ステップ１０３）。このステップ１０１〜１０３が上記第１のステップに相当する。
【００４８】
次に、秘密計算装置１１Ｃは、ｔに対応するデータを生成し（ステップ１０４）、そのときに生成したＷiを秘密計算装置１１Ｂに送信し（ステップ１０５）、
【数４８】
0005078632.tif 000049
を秘密計算装置１１Ａに送信する（ステップ１０６）。このステップ１０４〜１０６が上記第２のステップに相当する。
【００４９】
次に、秘密計算装置Ｂは、論理回路関数ｆ（ｘ，ｍB）を秘匿化し（ステップ１０７）、生成したＴgの集合をｆの秘匿化データとして秘密計算装置１１Ａに送信する（ステップ１０８）。このステップ１０７〜１０８が上記第３のステップに相当する。
【００５０】
次に、秘密計算装置１１Ａは、論理回路関数ｆの最終段のワイヤーの出力
【数４９】
0005078632.tif 000050
を得て、さらに演算結果ｆ（ｍA，ｍB）を得る（ステップ１０９）。このステップ１０９が上記第４および第５のステップに相当する。
【００５１】
以上、説明したように、本実施例によれば、非特許文献１の技術を用いた秘密計算システムでは全体の計算量の大部分を占めていた１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを秘密計算装置１１Ａ，１１Ｂ，１１Ｃのいずれも実行する必要がないので、秘密計算装置１１Ａ，１１Ｂ，１１Ｃの負荷を大幅に低減することができる。
【００５２】
なお、本実施例で追加された秘密計算装置１１Ｃには入力値ｍAの断片ｔが与えられるだけなので、秘密計算装置１１Ｃによって入力値ｍA，ｍBの秘匿性が損なわれることはない。
【００５３】
また、本実施例では、ＸＯＲを分割演算子としてデータｍAを２つの断片ｓ，ｔに分割する例を示したが、本発明はこれに限定されるものではない。論理回路ｆに一方の断片（例えばｓ）を埋め込んでデータＴgを生成し、他方の断片（例えばｔ）を入力として論理回路内でｍAを復元しつつ、データＴgから論理回路ｆの演算結果を得られればよいので、加減算、乗算、その他どのような演算子を分割演算子としてもよい。
【００５４】
（第２の実施例）
図３は、第２の実施例による秘密計算システムの構成を示すブロック図である。第２の実施例は、第１の実施例の入力値ｍAに相当する入力値ｍが複数である点で第１の実施例と異なる。また、第２の実施例では、第１の実施例の入力値ｍBに相当する入力値が無い。また、第２の実施例では、複数の変換装置がそれぞれに入力値ｍを保有しており、その入力値ｍを断片ｓ，ｔに分割し、ｓとｔを秘密計算装置に提供する点で第１の実施例と異なる。
【００５５】
図３を参照すると、秘密計算システムは、複数の変換装置２０1〜２０Nと秘密計算装置２１Ａ，２１Ｂ，２１Ｃとを有している。秘密計算装置２１Ａ〜２１Ｃで秘密計算装置群２１をなしている。論理回路関数ｆは秘密計算装置２１Ｃが保持している。
【００５６】
各変換装置２０1〜２０Nはデータｍ1〜ｍNをそれぞれ保有している。各変換装置２０1〜２０Nは、保有しているデータｍ1〜ｍNを秘匿した状態で秘密計算装置群２１に送る。その際、例えば、変換装置２０1は、データｍ1を、分割演算子を用いて２つに分割し、一方の断片ｓを秘密計算装置２１Ｂに送り、他方の断片ｔを秘密計算装置２１Ｃに送る。他の変換装置２０2〜２０Nの動作も変換装置２０1と同様である。
【００５７】
秘密計算装置２１Ａ，２１Ｂ，２１Ｃからなる秘密計算装置群２１は、変換装置２０1〜２０Nから受信したデータを用いて、データｍi（１≦ｉ≦Ｎ）を入力値とした論理回路ｆの演算結果ｆ（ｍ1，・・・，ｍN）を算出する。その際、秘密計算装置群１１は、データｍiを復元することなく、またデータｍiを容易に復元できるデータを得ることなく、演算結果ｆ（ｍ1，・・・，ｍN）を得る。
【００５８】
秘密計算装置２１Ｃは、変換装置２０1〜２０Nから受信した断片ｔから、断片ｔの各ビットｂに対応したデータＷｂと、各ビットｂに対する（１−ｂ）に対応したデータＷ（１−ｂ）とを生成する。そして、秘密計算装置２１Ｃは、データＷｂを秘密計算装置２１Ａに送信し、ｂおよび（１−ｂ）との対応を特定せずにデータＷｂおよびデータＷ（１−ｂ）を含むデータＷ＝（Ｗ０，Ｗ１）を秘密計算装置２１Ｂに送信する。
【００５９】
秘密計算装置２１Ｂは、変換装置２０1〜２０Nから受信した断片ｓと、保持している論理回路関数ｆと、秘密計算装置２１Ｃから受信したデータＷとから、データＷｂを入力として演算結果ｆ（ｍ1，・・・，ｍN）を求めることができる、断片ｓを埋め込んだ論理回路関数ｆを秘匿化したデータＴを生成する。そして、秘密計算装置２１Ｂは、データＴを秘密計算装置２１Ａに送信する。
【００６０】
秘密計算装置２１Ａは、秘密計算装置２１Ｂから受信したデータＴと、秘密計算装置２１Ｃから受信したデータＷｂとを入力とし、演算結果ｆ（ｍ1，・・・，ｍN）を算出する。
【００６１】
以下、本実施例の秘密計算システムおよび各装置の動作について、より具体的に説明する。演算結果ｆ（ｍ1，・・・，ｍN）を求めるまでの手順は５つのステップからなる。なお、記号を簡略化するため、ここでは特に必要が無ければｍiの添え字を省略することにする。
【００６２】
（第１のステップ）
各変換装置２０1〜２０Nは、保有しているデータｍに対して、
【数５０】
0005078632.tif 000051
を満たす（ｓ，ｔ）をランダムに生成する。そして、変換装置２０1〜２０Nは、ｓを秘密計算装置２１Ｂに、ｔを秘密計算装置２１Ｃにそれぞれ送る。
【００６３】
（第２のステップ）
秘密計算装置２１Ｃは、論理回路関数ｆにおける入力ワイヤーｉ毎にランダムビットｃi、および固定長の乱数とｃiの組
【数５１】
0005078632.tif 000052
を生成する。そして、秘密計算装置２１Ｃは、Ｗiを秘密計算装置２１Ｂに、
【数５２】
0005078632.tif 000053
を秘密計算装置２１Ａにそれぞれ送る。ここで
【数５３】
0005078632.tif 000054
であり、ｂ′は、ｉへの入力をｍの下位ｗ番目のビットとしたとき、ｔの下位ｗ番目のビットであるとする。
【００６４】
（第３のステップ）
秘密計算装置２１Ｂは、以下の（ａ）〜（ｄ）を実行し、論理回路関数ｆを秘匿化する。
（ａ）  秘密計算装置２１Ｂは論理回路関数ｆの各ワイヤーｉに対して、固定長の乱数
【数５４】
0005078632.tif 000055
を生成し、それぞれ０，１に対応させる。ただし、ｍの入力ワイヤーに対しては秘密計算装置２１Ｃから受け取った
【数５５】
0005078632.tif 000056
を対応させる。
（ｂ）  次に、秘密計算装置２１Ｂはランダムビットｃiを生成する。ただし、ｍAの入力ワイヤーに対しては秘密計算装置１１Ｃから受け取ったｃiを対応させる。
（ｃ）  更に、秘密計算装置２１Ｂは、
【数５６】
0005078632.tif 000057
をワイヤーｉに対応させる。ただし、ワイヤーｉがｍの下位ｗ番目のビットを入力とする場合は、
【数５７】
0005078632.tif 000058
とする。ここでｂはｓの下位ｗ番目のビットであるとする。
（ｄ）  更に、秘密計算装置２１Ｂは、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【数５８】
0005078632.tif 000059
をランダムな順番に並べたものをＴgとする。このＴgの集合が論理回路関数ｆを秘匿化したデータとなる。秘密計算装置２１Ｂは、Ｔgの集合を論理回路関数ｆの秘匿化データとして秘密計算装置２１Ａに送信する。ここでコロンの左側をラベル、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力して固定長の乱数を出力する関数であるとする。
【００６５】
（第４のステップ）
秘密計算装置２１Ａは、データＴgおよび
【数５９】
0005078632.tif 000060
を用いて、論理回路関数ｆの最終段のワイヤーの出力
【数６０】
0005078632.tif 000061
を得る。
（第５のステップ）
更に、秘密計算装置２１Ａは
【数６１】
0005078632.tif 000062
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
【数６２】
0005078632.tif 000063
を得る。
【００６６】
以上、説明したように、本実施例によれば、非特許文献３の技術を用いた秘密計算システムでは全体の計算量の大部分を占めていた、ｐｒｏｘｙ  １−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを秘密計算装置２１Ａ，２１Ｂ，２１Ｃのいずれも実行する必要がないので、秘密計算装置２１Ａ，２１Ｂ，２１Ｃの負荷を大幅に低減することができる。
【００６７】
なお、本実施例で追加された秘密計算装置２１Ｃには入力値ｍの断片ｔが与えられるだけなので、秘密計算装置２１Ｃによって入力値ｍの秘匿性が損なわれることはない。
【００６８】
また、本実施例では、ＸＯＲを分割演算子としてデータｍを２つの断片ｓ，ｔに分割する例を示したが、本発明はこれに限定されるものではない。論理回路ｆに一方の断片（例えばｓ）を埋め込んでデータＴgを生成し、他方の断片（例えばｔ）を入力として、データＴgから論理回路ｆの演算結果を得られればよいので、加減算、乗算、その他どのような演算子を分割演算子としてもよい。
【００６９】
また、第１および第２の実施例において、上述した各装置は、各部の動作の一部または全部を処理手順として規定したソフトウェアプログラムをコンピュータに実行させることにより実現することもできる。
【図面の簡単な説明】
【００７０】
【図１】第１の実施例による秘密計算システムの構成を示すブロック図である。
【図２】本実施形態の秘密計算システムの動作を示すシーケンス図である。
【図３】第２の実施例による秘密計算システムの構成を示すブロック図である。
【図４】非特許文献１に開示された技術を用いた秘密計算システムの構成を示すブロック図である。
【図５】非特許文献３に開示された技術を用いた秘密計算システムの構成を示すブロック図である。
【符号の説明】
【００７１】
１１Ａ，１１Ｂ，１１Ｃ，２１Ａ，２１Ｂ，２１Ｃ    秘密計算装置
２０1〜２０N  変換装置
【図１】
0005078632.tif 000064
【図２】
0005078632.tif 000065
【図３】
0005078632.tif 000066
【図４】
0005078632.tif 000067
【図５】
0005078632.tif 000068