(57)【特許請求の範囲】
【請求項１】
入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出する秘密計算システムであって、
前記入力値ｍが２つに分割された一方の断片Ｂを入力とし、前記論理回路ｆ（ｘ）と前記断片Ｂとから、他方の断片Ａを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ）が秘匿化されたデータＴを生成する第１の秘密計算装置と、
前記断片Ａと前記データＴとを入力とし、前記演算結果ｆ（ｍ）を算出する第２の秘密計算装置と、を有する秘密計算システム。
【請求項２】
前記断片Ａ、Ｂは、前記入力値ｍを分割演算子＊で２つに分割した断片ｓ、ｔであり、
前記第１の秘密計算装置は、前記論理回路ｆ（ｘ）と前記断片ｔとから、前記断片ｓを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ＊ｔ）が秘匿化されたデータＴを生成し、
前記第２の秘密計算装置は、前記断片ｓと前記データＴとを入力とし、前記演算結果ｆ（ｍ）を算出する、請求項１に記載の秘密計算システム。
【請求項３】
前記第１の秘密計算装置は、前記断片ｔを前記論理回路ｆ（ｘ）に埋め込んだ前記論理回路ｆ（ｘ＊ｔ）を秘匿化したデータＴを生成し、
前記第２の秘密計算装置は、前記断片ｓを入力として、論理演算において前記入力値ｍを実際に復元することなく、前記データＴから演算結果ｆ（ｍ）を算出する、請求項２に記載の秘密計算システム。
【請求項４】
前記第２の秘密計算装置は、前記第１の秘密計算装置との間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行することにより取得した、秘匿された前記入力値ｍに関するデータを、前記演算結果ｆ（ｍ）の算出に用いる、請求項２または３に記載の秘密計算システム。
【請求項５】
前記入力値ｍを、ｍ＝ｓ＊ｔを満たすように、前記断片ｓ，ｔに分割し、前記断片ｔを前記第１の秘密計算装置に送信し、前記断片ｓを前記第２の秘密計算装置に送信する変換装置を更に有する、請求項２から４のいずれか１項に記載の秘密計算システム。
【請求項６】
前記断片Ａは前記入力値ｍの各ビットｂに対応したデータＷｂであり、前記断片Ｂは、前記データＷｂと前記各ビットｂに対する（１−ｂ）に対応したデータＷ（１−ｂ）とを、ｂおよび（１−ｂ）との対応を特定せずに含むデータＷ＝（Ｗ０，Ｗ１）であり、
前記第１の秘密計算装置は、前記データＷを用いて、前記データＷｂを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路関数ｆを秘匿化したデータＴを生成し、
前記第２の秘密計算装置は、前記データＴと前記データＷｂとを入力とし、前記演算結果ｆ（ｍ）を算出する、請求項１に記載の秘密計算システム。
【請求項７】
不正な処理を検知するための検証装置を更に有し、
前記入力値ｍからは、断片Ａと断片Ｂとからなる複数の断片対が生成され、
前記第１の秘密計算装置は、複数の断片対の断片Ｂを入力とし、各断片Ｂに対して前記データＴを生成し、該データＴの集合を前記論理回路ｆ（ｘ）を変換した論理回路とし、
前記検証装置は、前記論理回路ｆ（ｘ）を変換した論理回路と、複数の前記断片対のうち任意に選択されたもの以外の断片対の断片Ｂおよびそれに対応するデータＴと、該データＴの正当性を検証することが可能な検証情報とを前記第１の秘密計算装置から取得し、該データＴと該検証情報を用いて、前記論理回路ｆ（ｘ）を変換した論理回路の正当性を検証し、
前記第２の秘密計算装置は、前記検証装置によって前記正当性が確認されたら、複数の前記断片対のうち任意に選択された前記断片対に対応するデータＴと、該断片対の断片Ａとを入力とし、前記演算結果ｆ（ｍ）を算出する、
請求項１から６のいずれか１項に記載の秘密計算システム。
【請求項８】
前記検証情報は、検証の対象である前記データＴを生成するときに前記第１の秘密計算装置が用いた入力値であり、
前記検証装置は、該データＴと該入力値を用いて、前記論理回路ｆ（ｘ）を変換した論理回路の正当性を検証する、請求項７に記載の秘密計算システム。
【請求項９】
前記検証情報は、検証の対象である前記データＴのハッシュ値であり、
前記検証装置は、該ハッシュ値を用いて、前記論理回路ｆ（ｘ）を変換した論理回路の正当性を検証する、請求項６または７に記載の秘密計算システム。
【請求項１０】
前記検証装置は、前記第１の秘密計算装置または前記第２の秘密計算装置のいずれかに組み込まれている、請求項７から９のいずれか１項に記載の秘密計算システム。
【請求項１１】
前記第１の秘密計算装置は、前記論理回路ｆ（ｘ）の演算結果ｆ（ｍ）とともに、該演算結果ｆ（ｍ）と２つ以上の定数値とから算出される付加情報が出力されるように前記データＴを生成し、
前記第２の秘密計算装置は、前記演算結果ｆ（ｍ）とともに付加情報を生成して前記第１の秘密計算装置に返し、
前記第１の秘密計算装置は、前記第２の秘密計算装置から返された前記付加情報と前記定数値とを用いて、前記第２の秘密計算装置から返された前記演算結果ｆ（ｍ）を検証する、請求項７から１０のいずれか１項に記載の秘密計算システム。
【請求項１２】
第１の秘密計算装置と第２の秘密計算装置により、入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出するための秘密計算方法であって、
前記入力値ｍを２つに分割した一方の断片Ｂを前記第１の秘密計算装置に与え、他方の断片Ａを前記第２の秘密計算装置に与え、
前記第１の秘密計算装置において、前記断片Ｂを入力とし、前記論理回路ｆ（ｘ）と前記断片Ｂとから、他方の断片Ａを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ）が秘匿化されたデータＴを生成し、
前記第１の秘密計算装置から前記第２の秘密計算装置に前記データＴを送信し、
前記第２の秘密計算装置において、前記断片Ａと前記データＴとを入力とし、前記演算結果ｆ（ｍ）を算出する、秘密計算方法。
【請求項１３】
前記第１の秘密計算装置および前記第２の秘密計算装置とは別に、あるいは前記第１の秘密計算装置または前記第２の秘密計算装置に備えられた検証装置があり、
前記入力値ｍからは、断片Ａと断片Ｂとからなる複数の断片対が生成され、
前記第１の秘密計算装置は、複数の断片対の断片Ｂを入力とし、各断片Ｂに対して前記データＴを生成し、該データＴの集合を前記論理回路ｆ（ｘ）を変換した論理回路とし、
前記検証装置は、前記論理回路ｆ（ｘ）を変換した論理回路と、複数の前記断片対のうち任意に選択されたもの以外の断片対の断片Ｂおよびそれに対応するデータＴと、該データＴの正当性を検証することが可能な検証情報とを前記第１の秘密計算装置から取得し、該データＴと該検証情報を用いて、前記論理回路ｆ（ｘ）を変換した論理回路の正当性を検証し、
前記第２の秘密計算装置は、前記検証装置によって前記正当性が確認されたら、複数の前記断片対のうち任意に選択された前記断片対に対応するデータＴと、該断片対の断片Ａとを入力とし、前記演算結果ｆ（ｍ）を算出する、
請求項１２に記載の秘密計算方法。
【請求項１４】
入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出する秘密計算システムを構成する秘密計算装置であって、
前記入力値ｍを保持している変換装置から、前記入力値を２つに分割した一方の断片Ｂを受信する入力手段と、
前記入力手段から入力された前記断片Ｂと前記論理回路ｆ（ｘ）とから、他方の断片Ａを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ）が秘匿化されたデータＴを生成する秘匿化手段と、
前記秘匿化手段で生成された前記データを、前記断片Ａを持った他の秘密計算装置に送る出力手段と、を有する秘密計算装置。
【請求項１５】
入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出する第１および第２の秘密計算装置を有する秘密計算システムにおける処理を検証する検証装置であって、
断片Ａと断片Ｂとからなる複数の断片対の断片Ｂを入力として、各断片Ｂに対して生成されたデータＴの集合である、前記論理回路ｆ（ｘ）を変換した論理回路と、前記複数の断片対のうち任意に選択されたもの以外の断片対の断片Ｂおよびそれに対応するデータＴと、該データＴの正当性を検証することが可能な検証情報とを前記第１の秘密計算装置から取得する検証情報取得手段と、
検証情報取得手段で取得された前記データＴと前記検証情報を用いて、前記論理回路ｆ（ｘ）を変換した論理回路の正当性を検証する検証手段と、を有する検証装置。
【請求項１６】
コンピュータを、入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出する秘密計算システムを構成する秘密計算装置として動作させるためのプログラムであって、
前記入力値ｍを保持している変換装置から、前記入力値を２つに分割した一方の断片Ｂを受信する手順と、
入力された前記断片Ｂと前記論理回路ｆ（ｘ）とから、他方の断片Ａを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ）が秘匿化されたデータＴを生成する手順と、
生成した前記データを、前記断片Ａを持った他の秘密計算装置に送る手順と、をコンピュータに実行させるためのプログラム。
【請求項１７】
コンピュータを、入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出する第１および第２の秘密計算装置を有する秘密計算システムにおける処理を検証する検証装置として動作させるためのプログラムであって、
断片Ａと断片Ｂとからなる複数の断片対の断片Ｂを入力として、各断片Ｂに対して生成されたデータＴの集合である、前記論理回路ｆ（ｘ）を変換した論理回路と、前記複数の断片対のうち任意に選択されたもの以外の断片対の断片Ｂおよびそれに対応するデータＴと、該データＴの正当性を検証することが可能な検証情報とを前記第１の秘密計算装置から取得する手順と、
取得された前記データＴと前記検証情報を用いて、前記論理回路ｆ（ｘ）を変換した論理回路の正当性を検証する手順と、をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関し、特に、入力値を秘匿したまま、その入力値に対する演算の結果を得る技術に関する。
【背景技術】
【０００２】
非特許文献１には、入力値を秘匿したままで演算結果を得る技術が開示されている。図８は、非特許文献１に開示された技術を用いた秘密計算システムの構成を示すブロック図である。図８を参照すると、秘密計算システムは、複数の変換装置９０1〜９０Nと秘密計算装置９１Ａ，９１Ｂとを有している。２つの秘密計算装置９１Ａ，９１Ｂによって秘密計算装置群９１をなしている。
【０００３】
各変換装置９０1〜９０Nはデータｍ1〜ｍNをそれぞれ保有している。各変換装置９０1〜９０Nは、保有しているデータｍ1〜ｍNを秘匿した状態で秘密計算装置群９１に送る。
【０００４】
秘密計算装置９１Ａ，９１Ｂからなる秘密計算装置群９１は、変換装置９０1〜９０Nから受信したデータを用いて、データｍi（１≦ｉ≦Ｎ）を入力値とした論理回路ｆの演算結果ｆ（ｍ1，・・・，ｍN）を算出する。その際、秘密計算装置群９１は、データｍiを復元することなく、またデータｍiを容易に復元できるデータを得ることなく、演算結果ｆ（ｍ1，・・・，ｍN）を得る。
【０００５】
また、非特許文献１では、非特許文献２に示されている技術の応用として、データｍ1〜ｍNを秘匿し、秘匿したままのデータｍ1〜ｍNを用いて演算結果ｆ（ｍ1，・・・，ｍN）を算出するまでの一連の処理が開示されている。以下、演算結果ｆ（ｍ1，・・・，ｍN）を求める手順の概要を説明する。手順は７つのステップからなる。手順の説明には、図８に示した秘密計算システムの構成を用いる。なお、記号を簡略化するため、ここでは特に必要が無ければｍiの添え字を省略することにする。
【０００６】
（第１のステップ）
まず、秘密計算装置９１Ａと秘密計算装置９１Ｂは協力して素数ｐを生成し、ｈq≡１（ｍｏｄ  ｐ）を満たす２以上ｐ未満の整数ｈおよび最小の自然数ｑを求める。また別に２以上ｐ未満の整数ｚを選ぶ。
【０００７】
（第２のステップ）
秘密計算装置９１Ｂは、以下の（ａ）〜（ｄ）を実行し、論理回路ｆを秘匿化する。
（ａ）  ｆの各ワイヤーｉに対して固定長の乱数
【０００８】
【数１】
0005047198.tif 000002
【０００９】
を生成し、それぞれ０，１に対応させる。
（ｂ）  ランダムビットｃiを生成する。
（ｃ）
【００１０】
【数２】
0005047198.tif 000003
【００１１】
をワイヤーｉに対応させる。ここで
【００１２】
【数３】
0005047198.tif 000004
【００１３】
とする。
（ｄ）  ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【００１４】
【数４】
0005047198.tif 000005
【００１５】
を行単位でランダムな順番に並べたものをＴgとする。このＴgの集合が論理回路ｆの秘匿化データとなる。ここでコロンの左側をラベルとし、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力して固定長の乱数を出力する関数であるものとする。
【００１６】
秘密計算装置９１Ｂは、このＴgの集合を論理回路ｆの秘匿化データとして秘密計算装置９１Ａに送信する。
【００１７】
（第３のステップ）
各変換装置９０1〜９０Nはｐ，ｑ，ｈ，ｚを入力し、以下の（ａ）〜（ｄ）をｍの各ビットｂに対して実行する。これによって、秘密計算装置９１Ａがｍの各ビットｂの入力ワイヤーｉに対応するデータ
【００１８】
【数５】
0005047198.tif 000006
【００１９】
を得られるようになる。
（ａ）  ｑ未満の自然数ｕをランダムに選ぶ。
（ｂ）  ＰＫb＝ｈuｍｏｄ  ｐを計算する。
（ｃ）  ｂ＝１であれば
【００２０】
【数６】
0005047198.tif 000007
【００２１】
を計算する。
（ｄ）  各変換装置９０1〜９０NはＰＫ0を秘密計算装置９１Ｂに送り、ｕを秘密計算装置９１Ａに送る。
【００２２】
（第４のステップ）
秘密計算装置９１Ｂは、ＰＫ1＝ｚ／ＰＫ0ｍｏｄ  ｐを計算した後、
【００２３】
【数７】
0005047198.tif 000008
【００２４】
を計算し、得られた暗号文Ｚ0，Ｚ1を秘密計算装置９１Ａに送る。ここでＥPK（ｘ）は平文ｘの公開鍵ＰＫを用いた暗号化関数であるとし、その暗号文は復号鍵ｕにより復号できるものとする。またＣは平文が正しく復元できたか識別可能な関数であるとする。
【００２５】
（第５のステップ）
秘密計算装置９１Ａは復号鍵ｕを用いてＺ0，Ｚ1を復号し、正しく復元されているとＣにより識別される復号結果
【００２６】
【数８】
0005047198.tif 000009
【００２７】
を得る。
【００２８】
（第６のステップ）
秘密計算装置９１Ａは、Ｔgおよび
【００２９】
【数９】
0005047198.tif 000010
【００３０】
を用いて、ｆの最終段のワイヤーの出力
【００３１】
【数１０】
0005047198.tif 000011
【００３２】
を得る。
【００３３】
（第７のステップ）
続いて、秘密計算装置９１Ａは、
【００３４】
【数１１】
0005047198.tif 000012
【００３５】
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
【００３６】
【数１２】
0005047198.tif 000013
【００３７】
を得る。
【００３８】
以上の手順の中で第３のステップにおいて各変換装置９０1〜９０Nの選択したｕが秘密計算装置９１Ａ以外に知られると、ｂの秘匿性が損なわれる場合がある。そのため、各変換装置９０1〜９０Nと秘密計算装置９１Ａとの間の伝送路では別途、暗号化等の対策を講じることが望ましい。
【００３９】
また、第６のステップでは、入力ワイヤーｉ，ｊ、出力ワイヤーｋのゲートに対応するＴgと、
【００４０】
【数１３】
0005047198.tif 000014
【００４１】
とが与えられたとき、先ずＴgからラベル
【００４２】
【数１４】
0005047198.tif 000015
【００４３】
を持つデータ
【００４４】
【数１５】
0005047198.tif 000016
【００４５】
を取り出し、
【００４６】
【数１６】
0005047198.tif 000017
【００４７】
を計算するとよい。これにより、上記出力ワイヤーに対応するデータ
【００４８】
【数１７】
0005047198.tif 000018
【００４９】
が得られる。他のゲートについても同様の処理を行えばよい。
【００５０】
また、第７のステップについては、例えばｇがｆの最終段ゲートである場合、ｃk＝０とすることにより、
【００５１】
【数１８】
0005047198.tif 000019
【００５２】
から
【００５３】
【数１９】
0005047198.tif 000020
【００５４】
を得ることができる。
【先行技術文献】
【非特許文献】
【００５５】
【非特許文献１】Ｍ．Ｎａｏｒ，  Ｂ．Ｐｉｎｋａｓ，  ａｎｄ  Ｒ．Ｓｕｍｎｅｒ，“Ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ａｕｃｔｉｏｎｓ  ａｎｄ  ｍｅｃｈａｎｉｓｍ  ｄｅｓｉｇｎ”，Ｐｒｏｃ．  ｏｆ  ＡＣＭ  ＥＣ’９９，  ｐｐ．１２９−１３９，ＡＣＭ  Ｐｒｅｓｓ，１９９９．
【非特許文献２】Ａ．Ｃ．Ｙａｏ，“Ｈｏｗ  ｔｏ  ｇｅｎｅｒａｔｅ  ａｎｄ  ｅｘｃｈａｎｇｅ  ｓｅｃｒｅｔｓ”，Ｐｒｏｃ．  ｏｆ  ＦＯＣＳ’８６，  ｐｐ．１６２−１６７，ＩＥＥＥ  Ｐｒｅｓｓ，１９８６．
【非特許文献３】Ｋｏｊｉ  Ｃｈｉｄａ  ａｎｄ  Ｋａｔｓｕｍｉ  Ｔａｋａｈａｓｈｉ，“Ｐｒｉｖａｃｙ  Ｐｒｅｓｅｒｖｉｎｇ  Ｃｏｍｕｔａｔｉｏｎｓ  Ｗｉｔｈｏｕｔ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｉｐｔｏｇｒａｐｈｉｃ  Ｏｐｅｒａｔｉｏｎ”，  ＳＣＩＳ  ２００８，  Ｊａｎ．  ２２−２５，  ２００８
【発明の概要】
【発明が解決しようとする課題】
【００５６】
上述した方法では、保有しているデータを提供する各変換装置９０1〜９０Nは、保有データｍiに対して、１ビット毎にべき乗剰余演算を行い、ビット毎の暗号文を生成する必要がある。そのため、ｍiのサイズが大きい場合、変換装置９０1〜９０Nにおける計算時間が実用上の問題となりうる。また、変換装置９０1〜９０Nに高性能のものを用いることができない場合にも同様の問題が起こりうる。また同様に、変換装置９０1〜９０Nから秘密計算装置９１Ａ，９１Ｂに送るデータ量も実用上の問題となりうる。
【００５７】
本発明の目的は、データを提供する装置の負荷を低減した秘密計算システムを提供することである。
【課題を解決するための手段】
【００５８】
上記目的を達成するために、本発明の秘密計算システムは、
入力値ｍを秘匿したままで、該入力値ｍに対する論理回路ｆ（ｘ）の演算結果ｆ（ｍ）を算出する秘密計算システムであって、
前記入力値ｍが２つに分割された一方の断片Ｂを入力とし、前記論理回路ｆ（ｘ）と前記断片Ｂとから、他方の断片Ａを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ）が秘匿化されたデータＴを生成する第１の秘密計算装置と、
前記断片Ａと前記データＴとを入力とし、前記演算結果ｆ（ｍ）を算出する第２の秘密計算装置と、を有している。
【００５９】
また、前記断片Ａ、Ｂは、前記入力値ｍを分割演算子＊で２つに分割した断片ｓ、ｔであり、
前記第１の秘密計算装置は、前記論理回路ｆ（ｘ）と前記断片ｔとから、前記断片ｓを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路ｆ（ｘ＊ｔ）が秘匿化されたデータＴを生成し、
前記第２の秘密計算装置は、前記断片ｓと前記データＴとを入力とし、前記演算結果ｆ（ｍ）を算出することにしてもよい。
【００６０】
また、前記第１の秘密計算装置は、前記断片ｔを前記論理回路ｆ（ｘ）に埋め込んだ前記論理回路ｆ（ｘ＊ｔ）を秘匿化したデータＴを生成し、
前記第２の秘密計算装置は、前記断片ｓを入力として、論理演算において前記入力値ｍを実際に復元することなく、前記データＴから演算結果ｆ（ｍ）を算出することにしてもよい。
【００６１】
また、前記第２の秘密計算装置は、前記第１の秘密計算装置との間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行することにより取得した、秘匿された前記入力値ｍに関するデータを、前記演算結果ｆ（ｍ）の算出に用いることにしてもよい。
【００６２】
また、前記入力値ｍを、ｍ＝ｓ＊ｔを満たすように、前記断片ｓ，ｔに分割し、前記断片ｔを前記第１の秘密計算装置に送信し、前記断片ｓを前記第２の秘密計算装置に送信する変換装置を更に有することにしてもよい。
【００６３】
また、前記断片Ａは前記入力値ｍの各ビットｂに対応したデータＷｂであり、前記断片Ｂは、前記データＷｂと前記各ビットｂに対する（１−ｂ）に対応したデータＷ（１−ｂ）とを、ｂおよび（１−ｂ）との対応を特定せずに含むデータＷ＝（Ｗ０，Ｗ１）であり、
前記第１の秘密計算装置は、前記データＷを用いて、前記データＷｂを入力として前記演算結果ｆ（ｍ）を求めることのできる、論理回路関数ｆを秘匿化したデータＴを生成し、
前記第２の秘密計算装置は、前記データＴと前記データＷｂとを入力とし、前記演算結果ｆ（ｍ）を算出することにしてもよい。
【発明の効果】
【００６４】
本発明によれば、入力値であるデータを秘匿したまま、その入力値に対する演算の結果を得る秘密計算システムに対して、保有しているデータを変換して提供する装置は、保有しているデータｍをＡとＢに分割し、Ａを第２の秘密計算装置に送り、Ｂを第１の秘密計算装置に送るだけなので、負荷が低減される。
【図面の簡単な説明】
【００６５】
【図１】本実施形態による秘密計算システムの構成を示すブロック図である。
【図２】本実施形態の秘密計算システムの動作を示すシーケンス図である。
【図３】本実施形態の秘密計算装置１１Ｂの構成を示すブロック図である。
【図４】第２の実施形態の秘密計算システムの動作を示すシーケンス図である。
【図５】第３の実施形態による秘密計算システムの構成を示すブロック図である。
【図６】第３の実施形態の秘密計算システムの動作を示すシーケンス図である。
【図７】第３の実施形態における検証装置の構成を示すブロック図である。
【図８】非特許文献１に開示された技術を用いた秘密計算システムの構成を示すブロック図である。
【発明を実施するための形態】
【００６６】
本発明を実施するための形態について図面を参照して詳細に説明する。
【００６７】
（第１の実施形態）
図１は、第１の実施形態による秘密計算システムの構成を示すブロック図である。図１を参照すると、秘密計算システムは、複数の変換装置１０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）を求めることのできる、論理回路ｆが秘匿化されたデータＴgを生成する。データＴgでは論理回路ｆにｔが埋め込まれている。
【００７１】
秘密計算装置１１Ａは、ｓとデータＴgとを入力とし、演算結果ｆ（ｍ1，・・・，ｍN）を算出する。より具体的には、秘密計算装置１１Ａは、ｓを入力として、論理演算において入力値ｍを実際に復元することなく、データＴgから演算結果ｆ（ｍ1，・・・，ｍN）を算出する。
【００７２】
本実施形態の秘密計算システムは、例えば、プライバシーを保護しつつ個人的な情報を活用する様々なシステムに適用することができる。具体的な例として、秘密計算システムは、オークションを含む任意の情報集計システムであるとしてもよい。各ユーザーは、変換装置１０1〜１０Nを用いて各自の情報を秘匿して秘密計算装置群１１に送信する。秘密計算装置群１１は、各ユーザーからの情報を復元することなく、それらの情報に対する所定の演算の結果を得る。例えば、オークション結果や多数決による意思決定の結果などを演算結果として得ることが考えられる。また、他の例として、各ユーザーが保有するデータを他者に知られること無く集計し、それらのデータを元にした各種統計処理やマイニング処理を行うことも可能である。
【００７３】
また、更に他の例として、秘密計算システムは、生体認証システムであるとしてもよい。各ユーザーは、変換装置１０1〜１０Nを用いて自身の生体情報ｍiを秘匿して秘密計算装置群１１に送信する。秘密計算装置群１１は、その生体情報を復元することなく、生体情報が正当なものであるか否かｆ（ｍi）により判定する。
【００７４】
本実施形態の秘密計算システムの基本的な構成は非特許文献１に開示されたものと同様である。ただし、本実施形態の秘密計算システムは、各装置の機能や動作が非特許文献１に開示されたものとは異なっている。
【００７５】
以下、本実施形態の秘密計算システムおよび各装置の動作について説明する。本実施形態の秘密計算システムは、一連の処理によって演算結果ｆ（ｍ1，・・・，ｍN）を求める。演算結果ｆ（ｍ1，・・・，ｍN）を求めるまでの手順は５つのステップからなる。なお、記号を簡略化するため、ここでは特に必要が無ければｍiの添え字を省略することにする。
【００７６】
（第１のステップ）
まず、各変換装置１０1〜１０Nは、保有データｍに対して、
【００７７】
【数２０】
0005047198.tif 000021
【００７８】
を満たす（ｓ，ｔ）をランダムに生成し、ｓを秘密計算装置１１Ａに、ｔを秘密計算装置１１Ｂにそれぞれ送る。
【００７９】
（第２のステップ）
秘密計算装置１１Ｂは、以下の（ａ）〜（ｄ）を実行することにより、論理回路ｆを変換する。
（ａ）  ｆの各ワイヤーｉに対して固定長の乱数
【００８０】
【数２１】
0005047198.tif 000022
【００８１】
を生成し、それぞれ０，１に対応させる。
（ｂ）  ランダムビットｃiを生成する。
（ｃ）
【００８２】
【数２２】
0005047198.tif 000023
【００８３】
をワイヤーｉに対応させる。ここで
【００８４】
【数２３】
0005047198.tif 000024
【００８５】
とする。ただし、ワイヤーｉがｍの下位ｗ番目のビットｍwを入力とする場合は、
【００８６】
【数２４】
0005047198.tif 000025
【００８７】
とする。ここでｔwはｔの下位ｗ番目のビットとする。
（ｄ）  ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【００８８】
【数２５】
0005047198.tif 000026
【００８９】
を行単位でランダムな順番に並べたものをＴgとする。このＴgの集合が論理回路ｆの変換データとなる。ここでコロンの左側をラベルとし、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力して固定長の乱数を出力する関数であるものとする。
【００９０】
秘密計算装置１１Ｂは、このＴgの集合を論理回路の変換データとして秘密計算装置１１Ａに送信する。
【００９１】
（第３のステップ）
秘密計算装置１１Ａは、ｓを用いて、
【００９２】
【数２６】
0005047198.tif 000027
【００９３】
を求める。その際、秘密計算装置１１Ａは、秘密計算装置１１Ｂと１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行し、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータ
【００９４】
【数２７】
0005047198.tif 000028
【００９５】
を得る。
【００９６】
（第４のステップ）
秘密計算装置１１Ａは、Ｔgおよび
【００９７】
【数２８】
0005047198.tif 000029
【００９８】
を用いて、論理回路ｆの最終段のワイヤーの出力
【００９９】
【数２９】
0005047198.tif 000030
【０１００】
を得る。ここでｂ＝ｍwとする。
【０１０１】
（第５のステップ）
秘密計算装置１１Ａは、
【０１０２】
【数３０】
0005047198.tif 000031
【０１０３】
から、演算結果ｆ（ｍ1，・・・，ｍN）のビットｂ′を得る。
【０１０４】
上記手順の第３のステップでは１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルが用いられている。このプロトコルは、秘密計算装置１０Ｂがデータｄ0，ｄ1を保有し、秘密計算装置１０Ａがビットｂを保有するとき、秘密計算装置１０Ａはｄbを得ることができるが、
【０１０５】
【数３１】
0005047198.tif 000032
【０１０６】
を得ることはできず、かつ秘密計算装置１０Ｂはｂを得ることができないような特徴を持つものである。このプロトコルの詳細は、Ｓ．  Ｅｖｅｎ，  Ｏ．  Ｇｏｌｄｒｅｉｃｈ  ａｎｄ  Ａ．  Ｌｅｍｐｅｌ，  Ａ  ｒａｎｄｏｍｉｚｅｄ  ｐｒｏｔｏｃｏｌ  ｆｏｒ  ｓｉｇｎｉｎｇ  ｃｏｎｔｒａｃｔｓ，  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，  Ｖｏｌ．  ２８，  Ｎｏ．  ６，  ｐｐ．  ６３７−６４７，  １９８５．という文献に説明がある。
【０１０７】
また、第４のステップでは、入力ワイヤーｉ，ｊ、出力ワイヤーｋのゲートに対応するＴgと、
【０１０８】
【数３２】
0005047198.tif 000033
【０１０９】
とが与えられたとき、先ずＴgからラベル
【０１１０】
【数３３】
0005047198.tif 000034
【０１１１】
を持つデータ
【０１１２】
【数３４】
0005047198.tif 000035
【０１１３】
を取り出し、
【０１１４】
【数３５】
0005047198.tif 000036
【０１１５】
を計算するとよい。これにより、上記出力ワイヤーに対応するデータ
【０１１６】
【数３６】
0005047198.tif 000037
【０１１７】
が得られる。他のゲートについても同様の処理を行えばよい。
【０１１８】
また、第５のステップについては、例えばｇがｆの最終段ゲートである場合、ｃk＝０とすることにより、
【０１１９】
【数３７】
0005047198.tif 000038
【０１２０】
から
【０１２１】
【数３８】
0005047198.tif 000039
【０１２２】
を得ることができる。
【０１２３】
上述した本実施形態の秘密計算システムによる処理は各装置によって実行される。以下、装置間の信号の送受信を含む処理の流れについて概説する。図２は、第１の実施形態の秘密計算システムの動作を示すシーケンス図である。
【０１２４】
図２を参照すると、まず、データｍを保有している各変換装置１０1〜１０Nが（ｓ，ｔ）を生成し（ステップ１０１）、ｓを秘密計算装置１１Ａに送信し（ステップ１０２）、ｔを秘密計算装置１１Ｂに送信する（ステップ１０３）。このステップ１０１〜１０３が上記第１のステップに相当する。
【０１２５】
次に、変換装置１０1〜１０Nからｔを受信した秘密計算装置１１Ｂが論理回路ｆを変換し（ステップ１０４）、論理回路ｆの変換データを秘密計算装置１１Ａに送信する（ステップ１０５）。このステップ１０４〜１０５が上記第２のステップに相当する。
【０１２６】
次に、秘密計算装置１１Ａは、秘密計算装置１１Ｂとの間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行し、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータを得る（ステップ１０６）。このステップ１０６が上記第３のステップに相当する。
【０１２７】
続いて、秘密計算装置１１Ａは、論理回路ｆのワイヤーの出力を得て、更に演算結果ｆ（ｍ1，・・・，ｍN）を得る（ステップ１０７）。このステップ１０７が上記第４および第５のステップに相当する。
【０１２８】
図３は、第１の実施形態の秘密計算装置１１Ｂの構成を示すブロック図である。図３を参照すると、秘密計算装置１１Ｂは、入力部２１、秘匿化部２２、出力部２３、および１−ｏｕｔ−ｏｆ−２  ＯＴ（Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒ）実行部２４を有している。
【０１２９】
入力部２１は、変換装置１０1〜１０Nから受信したデータｍの断片ｔを秘匿化部２２に入力する。また分割演算子が予め定められていない場合、入力部２１は、更に、変換装置１０1〜１０Nで用いられた分割演算子を秘匿化部２２に入力する。また論理回路ｆが予め定められていない場合、入力部２１は、更に、論理回路ｆを秘匿化部２２に入力する。
【０１３０】
秘匿化部２２は、断片ｔと論理回路ｆとから、断片ｓを入力として断片ｔを秘匿したままで演算結果ｆ（ｍ）を得ることが可能なデータＴgを算出する。
【０１３１】
出力部２３は、秘匿化部２２で算出されたデータＴgを秘密計算装置１１Ａに送信する。
【０１３２】
１−ｏｕｔ−ｏｆ−２  ＯＴ実行部２４は、秘密計算装置１１Ａとの間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行する。この処理は、上記第３のステップにおいて、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータを得る処理である。
【０１３３】
以上説明したように本実施形態では、変換装置１０1〜１０Nは、データｍをｓとｔに分割し、ｓを秘密計算装置１１Ａに送り、ｔを秘密計算装置１１Ｂに送る。秘密計算装置１１Ｂは、ｓを入力としてｆ（ｍ）を求めることのできる、論理回路ｆが秘匿化されたデータＴgを、論理回路ｆとｔとから算出し、秘密計算装置１１Ａに送信する。秘密計算装置１１Ａは、データＴgとｓを用いてｆ（ｍ）を算出する。したがって、本実施形態によれば、変換装置１０1〜１０Nは、保有しているデータｍをｓとｔに分割し、ｓを秘密計算装置１１Ａに送り、ｔを秘密計算装置１１Ｂに送るだけなので、非特許文献１および２に開示された方法に比べて、変換装置１０１〜１０Ｎの負荷が低減される。
【０１３４】
なお、本実施形態では、ＸＯＲを分割演算子としてデータｍを２つの断片ｓ，ｔに分割する例を示したが、本発明はこれに限定されるものではない。論理回路ｆに一方の断片（例えばｔ）を埋め込んでデータＴgを生成し、他方の断片（例えばｓ）を入力として論理回路内でｍを復元しつつ、データＴｇから論理回路ｆの演算結果を得られればよいので、加減算、乗算、その他どのような演算子を分割演算子としてもよい。
【０１３５】
また、本実施形態では、秘密計算装置１１Ａが秘密計算装置１１Ｂと１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行することにより、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータを得る例を示した。しかし、本発明は、これに限定されるものではない。他の例として、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを用いない方法について説明する。
【０１３６】
本例では、変換装置１０1〜１０Nは、入力値ｍの各ビットｂに対応したデータＷｂと、各ビットｂに対する（１−ｂ）に対応したデータＷ（１−ｂ）とを生成する。そして、変換装置１０1〜１０Nは、入力値ｍを分割した一方の断片としてデータＷｂを秘密計算装置１１Ａに送る。また、変換装置１０1〜１０Nは、ｂおよび（１−ｂ）との対応を特定せずにデータＷｂおよびデータＷ（１−ｂ）を含むデータＷ＝（Ｗ０，Ｗ１）を他方の断片として秘密計算装置１１Ｂに送る。
【０１３７】
秘密計算装置１１Ｂは、データＷを用いて、データＷｂを入力として演算結果ｆ（ｍ）を求めることのできる、論理回路関数ｆを秘匿化したデータＴを生成して、秘密計算装置１１Ａに送る。秘密計算装置１１Ａは、データＴとデータＷｂとを入力とし、演算結果ｆ（ｍ）を算出する。
【０１３８】
この方法では、上述した第１のステップ〜第３のステップの処理動作が以下に示す、第１′のステップ〜第３′のステップに変更される。
【０１３９】
（第１′のステップ）
各変換装置１０1〜１０Nは、ｍのビットｍw（ｍの下位ｗ番目のビット）が入力となるワイヤーｉに対して、ランダムビットｃiおよび固定長の乱数
【０１４０】
【数３９】
0005047198.tif 000040
【０１４１】
を生成する。そして、各変換装置１０1〜１０Nは、
【０１４２】
【数４０】
0005047198.tif 000041
【０１４３】
を秘密計算装置１１Ａに送信し、
【０１４４】
【数４１】
0005047198.tif 000042
【０１４５】
を秘密計算装置１１Ｂに送信する。
【０１４６】
（第２′のステップ）
秘密計算装置１１Ｂは、上述した第２のステップと同様に、（ａ）〜（ｄ）を実行することにより、論理回路ｆを変換する。ただし、ここでは（ｃ）において、ワイヤーｉがｍのビットを入力とする場合は、
【０１４７】
【数４２】
0005047198.tif 000043
【０１４８】
として、変換装置１０から受信した値を用いる。
【０１４９】
（第３′のステップ）
秘密計算装置１１Ａは、上述した第２のステップと同様に、ｓを用いて、
【０１５０】
【数４３】
0005047198.tif 000044
【０１５１】
を求める。ただし、ここでは、秘密計算装置１１Ａは、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行せず、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータとして、変換装置１０から受信した
【０１５２】
【数４４】
0005047198.tif 000045
【０１５３】
を用いる。
【０１５４】
この例によれば、１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行する必要が無いので、上述した例と比べて、秘密計算装置１１Ａ，１１Ｂの処理が軽減される。
【０１５５】
秘匿性について、各変換装置１０から秘密計算装置１１Ｂに送られる
【０１５６】
【数４５】
0005047198.tif 000046
【０１５７】
には、ｍに関する情報が含まれていない。また、各変換装置１０から秘密計算装置１１Ａに送られる
【０１５８】
【数４６】
0005047198.tif 000047
【０１５９】
においては、ｍwがランダムビットｃiでマスクされているため、ｍに関する有意な情報とはならない。したがって、秘密計算装置１１Ａ，１１Ｂは自身の受信した情報からだけでは、ｍに関する有意な情報を得ることができず、秘匿性が確保される。
【０１６０】
（第２の実施形態）
暗号応用技術では処理の正当性を検証できることが好ましい。第２の実施形態では、秘密計算装置による処理の正当性の検証を可能とした秘密計算システムを例示する。
【０１６１】
第２の実施形態による秘密計算システムの基本的な構成は図１に示した第１の実施形態と同様である。
【０１６２】
本実施形態の秘密計算システムは、変換装置１０1〜１１Nの保有するデータを基に、秘密計算装置１１Ａ、１１Ｂが連携動作することにより一連の処理を実行し、演算結果ｆ（ｍ1，．．．，ｍN）を求める。演算結果ｆ（ｍ1，．．．，ｍN）を求めるまでの手順は４つのステップからなる。なお記号を簡略化するため、ここではｍの添え字を省略する。
【０１６３】
（第１のステップ）
まず各変換装置１０1〜１１Nは、セキュリティパラメータｐ及び秘密計算装置１１Ａの暗号化鍵ＰＫを保有しており、保有データｍに対して
【０１６４】
【数４７】
0005047198.tif 000048
【０１６５】
（ｕ＝１，．．．，ｐ）を満たすｓu，ｔuをランダムに生成する。さらに、各変換装置１０1〜１１Nは、ＰＫを用いてｓuの暗号文Ｅ（ｓu）を計算し、Ｅ（ｓu），ｔu（ｕ＝１，．．．，ｐ）を秘密計算装置１１Ｂに送信する。
【０１６６】
（第２のステップ）
秘密計算装置１１Ｂは、ｕ＝１，．．．，ｐについて以下の（ａ）〜（ｅ）を実行することにより論理回路ｆを変換し、さらにそれらのコミットメントを生成する。
（ａ）  ｆのワイヤーｉに対して固定長の乱数
【０１６７】
【数４８】
0005047198.tif 000049
【０１６８】
を生成し、それぞれ０，１に対応させる。
（ｂ）  ランダムビットｃiを生成する。
（ｃ）
【０１６９】
【数４９】
0005047198.tif 000050
【０１７０】
をワイヤーｉに対応させる。ここで
【０１７１】
【数５０】
0005047198.tif 000051
【０１７２】
とする。ただし、ワイヤーｉがｍの下位ｗ番目のビットｍwを入力とする場合は、
【０１７３】
【数５１】
0005047198.tif 000052
【０１７４】
とする。ここで（ｔu）wはｔuの下位ｗ番目のビットとする。
（ｄ）  ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【０１７５】
【数５２】
0005047198.tif 000053
【０１７６】
を行単位でランダムな順番に並べたものをＴgとする。このＴgの集合が論理回路ｆの変換データｆ´uとなる。ここでコロンの左側をラベルとし、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力して固定長の乱数を出力する関数であるものとする。
（ｅ）  各ＴgについてコミットメントＣｏｍｍｉｔ＝Ｈａｓｈ（Ｔg）を計算し、秘密計算装置１１Ａに送信する。ここでＨａｓｈ（・）はハッシュ関数である。
【０１７７】
秘密計算装置１１Ｂは、このＴgの集合を論理回路の変換データとし、Ｃｏｍｍｉｔを各Ｔgのコミットメントとする。
【０１７８】
データ自体は明かさず変更不可能な状態にしておき、そのデータが変更されていないかを後に検証する手法をコミットメント方式と呼ぶ。コミットメントは、このコミットメント方式の処理に利用される。
【０１７９】
上記のように単純にはハッシュ関数を利用する手法は、コミットメント方式の一例である。この手法では、ハッシュ関数Ｈａｓｈ（・）で求めたＣｏｍｍｉｔ＝Ｈａｓｈ（Ｔg）のみを検証装置に送信しておき、その後、検証装置はＴgを受信し、ＣｏｍｍｉｔがＴgのハッシュ値であるかどうか検証すればよい。それにより、変換データＴgが変更されたものであるか否かを確認できる。本実施形態では、秘密計算装置１１Ａが検証装置として機能する。
【０１８０】
（第３のステップ）
秘密計算装置１１Ａは以下の（ｆ）〜（ｉ）を実行することにより、変換後の論理回路ｆ´u＝｛Ｔg｝の正当性を確認する。
（ｆ）  １以上ｐ以下の整数ａをランダムに選び秘密計算装置１１Ｂに送信する。
（ｇ）  その秘密計算装置１１Ｂから、ｕ≠ａについて、
ｆ´u、
【０１８１】
【数５３】
0005047198.tif 000054
【０１８２】
、およびｔuを受信する。
（ｈ）  ｆ´uが変更されていないことを、Ｃｏｍｍｉｔを用いて確認する。
（ｉ）  さらに、ｆ´uが論理回路ｆを正しく変換した論理回路であることを、（Ｗ0，Ｗ1），ｔuを用いて確認する。
【０１８３】
その際、秘密計算装置１１Ａは、（Ｗ0，Ｗ1），ｔuを用いて、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【０１８４】
【数５４】
0005047198.tif 000055
【０１８５】
を算出し、これを、秘密計算装置１１Ｂから取得したｆ´u＝｛Ｔg｝に含まれているものと比較する。Ｔgにおいて４つのラベル付きデータはランダムな順番に並んでいるので、これらについての比較においてデータの並んでいる順番は異なっていてもよい。
【０１８６】
上記検証処理において、Ｃｏｍｍｉｔまたはｆ´uが不正であると判断された場合、秘密計算装置１１Ｂはそれ以降の処理を中止する。
【０１８７】
ｆ´u（ｕ≠ａ）の少なくとも１つが不正なものであった場合、秘密計算装置１１Ａは、不正な変換があったことを検知する。ここで、ａはｆ´uがコミットメントされた後、すなわちＣｏｍｍｉｔが計算された後に生成された乱数であるため、秘密計算装置１１Ａは、（ｐ−１）／ｐ以上の確率で不正な変換を検知できる。
【０１８８】
（第４のステップ）
秘密計算装置１１Ａは、以下の（ｊ）〜（ｎ）を実行することにより演算結果ｆ（ｍ1，．．．，ｍN）を得る。
（ｊ）  ｆ´ａ及びＥ（ｓa）を秘密計算装置１１Ｂから受信する。
（ｋ）  Ｅ（ｓa）からｓaを復号する。
（ｌ）  ｓaを用いて、
【０１８９】
【数５５】
0005047198.tif 000056
【０１９０】
を求める。その際、秘密計算装置１１Ａは、秘密計算装置１１Ｂとの間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行し、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータ
【０１９１】
【数５６】
0005047198.tif 000057
【０１９２】
を得る。
（ｍ）  ｆ´a及び
【０１９３】
【数５７】
0005047198.tif 000058
【０１９４】
を用いて、論理回路ｆの最終段のワイヤーの出力
【０１９５】
【数５８】
0005047198.tif 000059
【０１９６】
を得る。ここでｂ＝ｍwとする。
（ｎ）
【０１９７】
【数５９】
0005047198.tif 000060
【０１９８】
から演算結果ｆ（ｍ1，．．．，ｍN）のビットｂ′を得る。その際、ｂ´を得るために、回路出力
【０１９９】
【数６０】
0005047198.tif 000061
【０２００】
においてｃk＝０とする。
【０２０１】
図４は、第２の実施形態の秘密計算システムの動作を示すシーケンス図である。
【０２０２】
図４を参照すると、まず、データｍを保有している各変換装置１０1〜１０Nがｓu，ｔuを生成し（ステップ２０１）、さらにｓuの暗号文Ｅ（ｓu）を計算し（ステップ２０２）、Ｅ（ｓu）とｔuとを秘密計算装置１１Ｂに送信する（ステップ２０３）。このステップ１０１〜１０３が上記第１のステップに相当する。
【０２０３】
次に、変換装置１０1〜１０NからＥ（ｓu）とｔuを受信した秘密計算装置１１Ｂが論理回路ｆを変換し（ステップ２０４）、さらにコミットメントＣｏｍｍｉｔを生成し（ステップ２０５）、コミットメントＣｏｍｍｉｔを秘密計算装置１１Ａに送信する（ステップ２０６）。このステップ２０４〜１０６が上記第２のステップに相当する。
【０２０４】
次に、秘密計算装置１１Ａがランダムに選択した１以上Ｐ以下の整数ａを秘密計算装置１１Ｂに通知する（ステップ２０７）。その後、ｕ（ｕ≠ａ）の各データに基づいて、秘密計算装置１１Ａが秘密計算装置１１Ｂによる論理回路ｆの変換の正当性を検証する（ステップ２０８）。このステップ２０７〜２０８が上記第３のステップに相当する。
【０２０５】
正当性が確認されたら、次に、秘密計算装置１１Ａは、Ｅ（ｓa）からｓaを復号し（ステップ２０９）、ｕ（ｕ＝ａ）のデータに基づき、秘密計算装置１１Ｂとの間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行し、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータを得る（ステップ２１０）。続いて、秘密計算装置１１Ａは、論理回路ｆのワイヤーの出力を得て、更に演算結果ｆ（ｍ1，・・・，ｍN）を得る（ステップ２１１）。このステップ２０９〜２１１が上記第４のステップに相当する。
【０２０６】
以上説明したように、本実施形態では、秘密計算装置１１Ａが、秘密計算装置１１Ｂから、ｆ´uと、ｔuと、ランダムに選択したａについてｕ≠ａである
【０２０７】
【数６１】
0005047198.tif 000062
【０２０８】
とを取得し、
【０２０９】
【数６２】
0005047198.tif 000063
【０２１０】
と、ｔuとを用いて、ｆ´uが正しく変換された論理回路であるか否か検証する。それ故、本実施形態によれば、秘密計算装置１１Ｂによる論理回路ｆの変換が正しく行われていないことを秘密計算装置１１Ａによって検知することができる。また、ｔuが正しい値であることを検証できるようにするために、変換装置１０1〜１０Nは、ｔuに電子署名を付与し、秘密計算装置１１Ｂは、当該電子署名をＣｏｍｍｉｔに含め、秘密計算装置１１Ａはｔuが改ざんされていないか検証できるようにしてもよい。
【０２１１】
以上、秘密計算装置１１Ｂによる論理回路ｆの変換の正当性を秘密計算装置１１Ａが検証する構成について説明したが、また、秘密計算装置１１Ａによる演算結果ｆ（ｍ1，．．．，ｍN）を秘密計算装置１１Ｂが検証することにしてもよい。
【０２１２】
秘密計算装置１１Ａが本来の演算結果ｆ（ｍ1，．．．，ｍN）とは異なる結果を返したとき、秘密計算装置１１Ｂは、以下のようにしてその不正を検知すればよい。
【０２１３】
・秘密計算装置１１Ｂは、論理回路ｆの変換データとして、本来の演算結果ｆ（ｍ1，．．．，ｍN）とともにσ＝ｕｆ（ｍ1，．．．，ｍN）＋ｖが出力されるようなＴｇを生成する。ここでｕ，ｖは適当な乱数とする。
【０２１４】
・秘密計算装置１１Ａは、ｆ（ｍ1，．．．，ｍN）とともにσを、秘密計算装置１１Ｂに返す。
【０２１５】
・秘密計算装置１１Ｂは、秘密計算装置１１Ａから返されたｆ（ｍ1，．．．，ｍN）とσを用い、σ＝ｕｆ（ｍ1，．．．，ｍN）＋ｖであるか否か確認する。もし、σ＝ｕｆ（ｍ1，．．．，ｍN）＋ｖでなければ、秘密計算装置１１Ａからの演算結果が不正なものであったと判断できる。
【０２１６】
秘密計算装置１１Ａは、演算結果ｆ（ｍ1，．．．，ｍN）を算出する際の一度しか論理回路ｆを実行できないため、ｆに対する二つの異なる演算結果を得ることができない。そのため、σ＝ｕｆ（ｍ1，．．．，ｍN）＋ｖという関数のｕ，ｖを得ることができない。したがって、秘密計算装置１１Ａは、本来とは異なる演算結果Ｒを出力する場合の正しいσ′＝ｕＲ＋ｖを算出できず、秘密計算装置１１Ｂによって、演算結果Ｒが本来のものとは異なることが検知される。
【０２１７】
また、秘密計算装置１１Ａが正しくｓuを用いたかどうか検証するために、複数の装置に同様の処理を行わせ、結果が一致するかどうか確認してもよい。
【０２１８】
なお、秘密計算装置１１Ａによる演算結果ｆ（ｍ1，．．．，ｍN）を検証するためのσとして、σ＝ｕｆ（ｍ1，．．．，ｍN）＋ｖを用いたが、本発明はこれに限定されるものではない。他の例として、秘密計算装置１１Ａは、演算結果ｆ（ｍ1，．．．，ｍN）にσとして電子署名を付加することにしてもよい。これによれば、秘密計算装置１１Ｂでなくても演算結果ｆ（ｍ1，．．．，ｍN）の正当性を検証することができる。
【０２１９】
（第３の実施形態）
第２の実施形態では、秘密計算装置１１Ｂによる論理回路ｆの変換の正当性を秘密計算装置１１Ａが検証する例を示したが、本発明はそれに限定されるものではない。他の例として、秘密計算装置１１Ａとは別に検証装置を設け、その検証装置が正当性を確認することにしてもよい。
【０２２０】
図５は、第３の実施形態による秘密計算システムの構成を示すブロック図である。図５を参照すると、秘密計算システムは、複数の変換装置１０1〜１０Nと秘密計算装置１１Ａ，１１Ｂに加え、検証装置１２を有している。第１の実施形態と同様に秘密計算装置１１Ａと秘密計算装置１１Ｂとで秘密計算装置群１１をなしている。
【０２２１】
本実施形態は、秘密計算装置１１Ｂによる変換結果の論理回路ｆ´uの正当性を、確認を秘密計算装置Ａとは異なる検証装置１２が検証する点で第１の実施形態と異なる。
【０２２２】
以下、本実施形態の秘密計算システムおよび各装置の動作について説明する。本実施形態の秘密計算システムは、一連の処理によって演算結果ｆ（ｍ1，・・・，ｍN）を求める。演算結果ｆ（ｍ1，・・・，ｍN）を求めるまでの手順は以下の第１〜４のステップからなる。なお、記号を簡略化するため、ここでは特に必要が無ければｍiの添え字を省略することにする。
【０２２３】
（第１のステップ）
まず各変換装置１０1〜１１Nは、保有データｍに対して、
【０２２４】
【数６３】
0005047198.tif 000064
【０２２５】
を満たす、ｓ，ｔをランダムに生成し、ｓを秘密計算装置１１Ａに、ｔを秘密計算装置１１Ｂにそれぞれ送信する。
【０２２６】
（第２のステップ）
秘密計算装置１１Ｂは、ｕ＝１，．．．，ｐについて、以下の（ａ）〜（ｅ）を実行することにより論理回路ｆを変換する。
（ａ）  ｆの各ワイヤーｉに対して固定長の乱数
【０２２７】
【数６４】
0005047198.tif 000065
【０２２８】
を生成し、それぞれ０，１に対応させる。
（ｂ）  ランダムビットｃiを生成する。
（ｃ）
【０２２９】
【数６５】
0005047198.tif 000066
【０２３０】
をワイヤーｉに対応させる。ここで
【０２３１】
【数６６】
0005047198.tif 000067
【０２３２】
とする。ただし、ワイヤーｉがｍの下位ｗ番目のビットｍwを入力とする場合は、
【０２３３】
【数６７】
0005047198.tif 000068
【０２３４】
とする。ここでｔwはｔの下位ｗ番目のビットとする。
（ｄ）  ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
【０２３５】
【数６８】
0005047198.tif 000069
【０２３６】
を行単位でランダムな順番に並べたものをＴgとする。このＴgの集合が論理回路ｆの変換データｆ´uとなる。ここでコロンの左側をラベルとし、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力して固定長の乱数を出力する関数であるものとする。
（ｅ）  ｔ及び各Ｔgを検証装置１２に送信する。
【０２３７】
また、秘密計算装置１１Ｂは、このＴgの集合を論理回路ｆの変換データとして保持する。
【０２３８】
（第３のステップ）
検証装置１２は、以下の（ｆ）〜（ｉ）を実行することにより、変換後の論理回路ｆ´u＝｛Ｔg｝の正当性を確認する。
（ｆ）  １以上ｐ以下の整数ａをランダムに選び秘密計算装置１１Ｂに送信する。
（ｇ）  秘密計算装置１１Ｂから、ｕ≠ａについて、
【０２３９】
【数６９】
0005047198.tif 000070
【０２４０】
を受信する。
（ｈ）  ｕ≠ａについて、（Ｗ0，Ｗ1），ｔを用いて、ｆ´uが正しくｆを変換した論理回路であることを確認する。
【０２４１】
上記処理において、ｆ´uが不正であると判断した場合、検証装置１２は以降の処理を中止する。検証装置１２は、ｆ´u（ｕ≠ａ）の少なくとも１つが不正なものであった場合、不正な変換があったことを検知する。ここで、ａは、検証装置１２がｆ´uを受信した後に生成した乱数であるため、（ｐ−１）／ｐ以上の確率で不正な変換を検知できる。
（ｉ）  ｆ´ｕが正当なものであることが確認されたら、秘密計算装置１１Ｂから秘密計算装置１１Ａにｆ´aを送信する。
【０２４２】
（第４のステップ）
秘密計算装置１１Ａは、以下の（ｊ）〜（ｍ）を実行することにより演算結果ｆ（ｍ1，．．．，ｍN）を得る。
（ｊ）  ｆ´aを秘密計算装置１１Ｂから受信する。
（ｋ）  ｓを用いて
【０２４３】
【数７０】
0005047198.tif 000071
【０２４４】
を求める。その際、秘密計算装置１１Ｂとの間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行し、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータ
【０２４５】
【数７１】
0005047198.tif 000072
【０２４６】
を得る。
（ｌ）  ｆ´a及び
【０２４７】
【数７２】
0005047198.tif 000073
【０２４８】
を用いて、論理回路ｆの最終段のワイヤーの出力
【０２４９】
【数７３】
0005047198.tif 000074
【０２５０】
を得る。ここでｂ＝ｍwとする。
（ｍ）
【０２５１】
【数７４】
0005047198.tif 000075
【０２５２】
から演算結果ｆ（ｍ1，．．．，ｍN）のビットｂ′を得る。
【０２５３】
図６は、第３の実施形態の秘密計算システムの動作を示すシーケンス図である。
【０２５４】
図６を参照すると、まず、データｍを保有している各変換装置１０1〜１０Nがｓ，ｔを生成し（ステップ３０１）、ｓを秘密計算装置１１Ａに送信し（ステップ３０２）、ｔを秘密計算装置１１Ｂに送信する（ステップ３０３）。このステップ３０１〜３０３が上記第１のステップに相当する。
【０２５５】
次に、変換装置１０1〜１０Nからｔを受信した秘密計算装置１１Ｂが論理回路ｆを変換する（ステップ３０４）。このステップ３０４が上記第２のステップに相当する。
【０２５６】
次に、検証装置１２がランダムに選択した１以上Ｐ以下の整数ａを秘密計算装置１１Ｂに通知する（ステップ３０５）。その後、ｕ（ｕ≠ａ）の各データに基づいて、検証装置１２が秘密計算装置１１Ｂによる論理回路ｆの変換の正当性を検証する（ステップ３０６）。このステップ３０５〜３０６が上記第３のステップに相当する。
【０２５７】
正当性が確認されたら、秘密計算装置１１Ｂがｆ´aを秘密計算装置１１Ａに送り（ステップ３０７）、秘密計算装置１１Ａは、ｕ（ｕ＝ａ）のデータに基づき、秘密計算装置１１Ｂとの間で１−ｏｕｔ−ｏｆ−２  Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒプロトコルを実行し、ｓの下位ｗ番目のビットｓwを入力とするワイヤーに対応するデータを得る（ステップ３０８）。続いて、秘密計算装置１１Ａは、論理回路ｆのワイヤーの出力を得て、更に演算結果ｆ（ｍ1，・・・，ｍN）を得る（ステップ３０９）。このステップ３０７〜３０９が上記第４のステップに相当する。
【０２５８】
図７は、第３の実施形態における検証装置の構成を示すブロック図である。図７を参照すると、検証装置１２は検証情報取得部３１と検証部３２を有している。
【０２５９】
検証情報取得部３１は、１以上Ｐ以下の整数ａをランダムに選択して秘密計算装置１１Ｂに送り、秘密計算装置１１Ｂから、ｕ（ｕ≠ａ）について、
【０２６０】
【数７５】
0005047198.tif 000076
【０２６１】
を取得する。
【０２６２】
検証部３２は、ｕ（ｕ≠ａ）について、（Ｗ0，Ｗ1），ｔを用いて、ｆ´uが正しくｆを変換した論理回路であるか否か確認する。
【０２６３】
以上説明したように、本実施形態では、検証装置１２を設けることで、秘密計算装置１１Ａの処理を低減している。しかし、秘密計算装置１１Ｂが検証装置１２の機能をも備える構成であってもよい。
【０２６４】
また、上述した各実施形態における各装置は、各部の動作を処理手順として規定したソフトウェアプログラムをコンピュータに実行させることにより実現することもできる。例えば、図３に示した秘密計算装置１１Ｂは、入力部２１、秘匿化部２２、出力部２３、および１−ｏｕｔ−ｏｆ−２  ＯＴ実行部２４の処理手順を規定したプログラムをコンピュータに実行させることにより実現することができる。
【０２６５】
以上、本発明の各実施形態について述べてきたが、本発明は、これらの実施形態だけに限定されるものではなく、本発明の技術思想の範囲内において、これらの実施形態を組み合わせて使用したり、一部の構成を変更したりしてもよい。
【符号の説明】
【０２６６】
１０1〜１０N    変換装置
１１    秘密計算装置群
１１Ａ，１１Ｂ    秘密計算装置
１２    検証装置
２１    入力部
２２    秘匿化部
２３    出力部
２４    １−ｏｕｔ−ｏｆ−２  ＯＴ実行部
３１    検証情報取得部
３２    検証部
【図１】
0005047198.tif 000077
【図２】
0005047198.tif 000078
【図３】
0005047198.tif 000079
【図４】
0005047198.tif 000080
【図５】
0005047198.tif 000081
【図６】
0005047198.tif 000082
【図７】
0005047198.tif 000083
【図８】
0005047198.tif 000084