(57)【要約】      （修正有）【課題】複数の機関が保持している秘密入力データに対して、関数を適用したときの結果を、第三者の助けなしに無関係な情報になるよう他に知られることなく計算する。【解決手段】データ処理装置１００は、他の機関が生成した第１暗号データと自己の保有する秘密データに第１演算を適用し、自己の保有する暗号鍵で暗号化することで第２暗号データを生成し、他の機関が生成した第１加算暗号データを取得し、保有する暗号鍵で復号することで第１加算データを生成する。他の機関が生成した第３暗号データと保有する秘密データに第２演算を適用し、保有する暗号鍵で暗号化することで第４暗号データを生成し、相手機関が生成した第２加算暗号データを取得し、保有する暗号鍵で復号することで第２加算データを生成する。第１加算データと第２加算データより相手機関がもつ情報の推測を行い、推測情報に論理演算を適用し、結果を記憶部に記録する。【選択図】図６
2014048548.tif 000002
【特許請求の範囲】
【請求項１】
２以上のデータ処理装置で構成される秘匿計算システムであって、
前記データ処理装置はそれぞれ、秘密データを記憶する秘密データ記憶手段と、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶手段と、
撹乱データを記憶する撹乱データ記憶手段と、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶手段と、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶手段と、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理手段と、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のデータ処理装置へ前記第１係数暗号データを送信する第１暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信する第１暗号データ生成手段と、
他のデータ処理装置より送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のデータ処理装置へ送信する第１加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得手段と、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信する第２暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する第２暗号データ生成手段と、
他のデータ処理装置より送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のデータ処理装置へ送信する第２加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得手段と、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用手段と、
自己の前記論理演算適用手段により得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶手段と、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶手段と、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のデータ処理装置に送信し、送信したデータと他のデータ処理装置により送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出手段とを有する、
ことを特徴とする秘匿計算システム。
【請求項２】
前記データ処理装置は、
前記秘密データの二値配列表現である正順二値変数配列と前記正順二値変数配列と内容の格納順序が逆順である逆順二値変数配列を作成するデータ二値変数配列表現手段とをさらに有し、
前記第１暗号データ生成依頼手段では自己の保有する前記正順二値変数配列、または、前記撹乱データを自己の保有する暗号鍵で暗号化することで前記第１係数暗号データを生成し、前記第１係数暗号データを他のデータ処理装置へ送信し、
前記第１暗号データ生成手段では他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する正順二値変数配列に演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信し、
前記第２暗号データ生成依頼手段は前記撹乱データと前記逆順二値変数配列に演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信し、
前記第２暗号データ生成手段は他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する逆順二値変数配列に演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する、
ことを特徴とする請求項１に記載の秘匿計算システム。
【請求項３】
前記データ処理装置は、
前記秘匿論理関数の全体を１度に計算、または、２以上の部分関数の適用によって計算することができるよう前記秘匿論理関数、または、その部分関数の情報に基づいて撹乱データを作成する撹乱データ作成手段と、
前記秘匿論理関数を２以上の部分関数の適用によって計算するとき各部分関数の計算において前記第１暗号データ生成依頼手段と前記第１暗号データ生成手段において秘密データとして用いるデータを特定する情報を生成し、記憶する変数群更新情報作成手段と、
を有する請求項１または請求項２に記載の秘匿計算システム。
【請求項４】
前記撹乱データ記憶手段は、
前記撹乱データとして撹乱するために追加するビット群の撹乱後の二値変数配列での格納位置と値を記した撹乱ビット文字列と他のデータ処理装置もしくは自己が保有する秘密データである二値変数配列のすべての配列要素、または一部の配列要素の撹乱後の二値変数配列での格納位置を表現するビット列対応表として記憶する、
ことを特徴とする請求項２または請求項３に記載の秘匿計算システム。
【請求項５】
前記第１暗号生成依頼手段は、
秘密データ、もしくはその一部として前記撹乱データ記憶手段によって記憶されたデータを用い、
前記第２暗号生成依頼手段は秘密データ、もしくはその一部として前記撹乱データ記憶手段によって記憶されたデータを用いる、
ことを特徴とする請求項１乃至４のいずれか１項に記載の秘匿計算システム。
【請求項６】
前記第１暗号生成手段は、
秘密データとして２以上の正順二値変数配列を用い、
前記第２暗号生成手段は秘密データとして２以上の逆順二値変数配列を用いる、
ことを特徴とする請求項２乃至５のいずれか１項に記載の秘匿計算システム。
【請求項７】
前記秘匿計算システムは、
２以上のデータ処理装置がアクセス可能なデータ記憶装置をさらに有し、
２以上の前記データ処理装置はそれぞれ、自己の保有する前記演算結果を前記暗号鍵で暗号化した上で前記データ記憶装置に保存し、
他のデータ処理装置が保存した前記演算結果を前記データ記憶装置から取得して自己の保有する前記暗号鍵で復号し、その復号したデータを秘密データとして用い、
前記第１暗号データ生成依頼手段は他のデータ処理装置の撹乱データ記憶手段によって前記データ記憶装置に送信された撹乱データを前記データ記憶装置から取得し秘密データとして用い、
前記第１暗号データ生成手段は他のデータ処理装置の演算結果記録手段によって前記データ記憶装置に送信された演算結果を前記データ記憶装置から取得し秘密データとして用い、
前記第２暗号データ生成依頼手段は他のデータ処理装置の撹乱データ記憶手段によって前記データ記憶装置から送信された撹乱データをデータ記憶装置から取得し秘密データとして用い、
前記第２暗号データ生成手段は他のデータ処理装置によって前記データ記憶装置に送信された演算結果を前記データ記憶装置から取得し秘密データとして用いる、
ことを特徴とする請求項１乃至６のいずれか１項に記載の秘匿計算システム。
【請求項８】
他のデータ処理装置と連携してデータを処理するデータ処理装置であって、
秘密データを記憶する秘密データ記憶手段と、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶手段と、
撹乱データを記憶する撹乱データ記憶手段と、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶手段と、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶手段と、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理手段と、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のデータ処理装置へ前記第１係数暗号データを送信する第１暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信する第１暗号データ生成手段と、
他のデータ処理装置より送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のデータ処理装置へ送信する第１加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得手段と、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信する第２暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する第２暗号データ生成手段と、
他のデータ処理装置より送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のデータ処理装置へ送信する第２加算暗号データ生成手段と、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用手段と、他のデータ処理装置より送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得手段と、
自己の前記論理演算適用手段により得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶手段と、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶手段と、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のデータ処理装置に送信し、送信したデータと他のデータ処理装置により送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出手段とを有する、
ことを特徴とするデータ処理装置。
【請求項９】
他のデータ処理装置と連携してデータを処理するデータ処理装置により使用される秘匿計算方法であって、
秘密データを記憶する秘密データ記憶ステップと、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶ステップと、
撹乱データを記憶する撹乱データ記憶ステップと、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶ステップと、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶ステップと、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理ステップと、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のデータ処理装置へ前記第１係数暗号データを送信する第１暗号データ生成依頼ステップと、
他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信する第１暗号データ生成ステップと、
他のデータ処理装置より送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のデータ処理装置へ送信する第１加算暗号データ生成ステップと、
他のデータ処理装置より送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得ステップと、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信する第２暗号データ生成依頼ステップと、
他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する第２暗号データ生成ステップと、
他のデータ処理装置より送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のデータ処理装置へ送信する第２加算暗号データ生成ステップと、
他のデータ処理装置より送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得ステップと、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用ステップと、
自己の前記論理演算適用ステップで得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶ステップと、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶ステップと、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のデータ処理装置に送信し、送信したデータと他のデータ処理装置により送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出ステップとを有する、
ことを特徴とする秘匿計算方法。
【請求項１０】
他のコンピュータと連携してデータを処理するコンピュータにより使用される秘匿計算プログラムであって、
秘密データを記憶する秘密データ記憶ステップと、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶ステップと、
撹乱データを記憶する撹乱データ記憶ステップと、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶ステップと、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶ステップと、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理ステップと、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のコンピュータへ前記第１係数暗号データを送信する第１暗号データ生成依頼ステップと、
他のコンピュータより送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のコンピュータへ送信する第１暗号データ生成ステップと、
他のコンピュータより送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のコンピュータへ送信する第１加算暗号データ生成ステップと、
他のコンピュータより送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得ステップと、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のコンピュータへ前記第２係数暗号データを送信する第２暗号データ生成依頼ステップと、
他のコンピュータより送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のコンピュータへ送信する第２暗号データ生成ステップと、
他のコンピュータより送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のコンピュータへ送信する第２加算暗号データ生成ステップと、
他のコンピュータより送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得ステップと、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用ステップと、
自己の前記論理演算適用ステップで得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶ステップと、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶ステップと、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のコンピュータに送信し、送信したデータと他のコンピュータにより送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出ステップとを有する、
ことを特徴とする秘匿計算プログラム。
【請求項１１】
請求項１０に記載の秘匿計算プログラムが記録されていることを特徴とするコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数の機関がそれぞれ保持している秘密データに対して、関数を適用したときの結果を第三者の助けなしに計算するための秘匿計算システム、データ処理装置、秘匿計算方法、秘匿計算プログラム、および、記録媒体に関する。
【背景技術】
【０００２】
暗号関数を使った秘匿計算方法が知られている。ここで、暗号関数とはあるデータからそのデータの固有の数値（以下、「暗号値」という）を得る関数のことをいう。また、暗号値から暗号関数を適用する前の値である平文を得る関数を復号関数という。暗号関数と対応する復号関数の組を暗号方式と呼ぶ。（以下、暗号関数を用いて暗号値を得ることを「暗号化」、暗号値に復号関数を適用することを「復号」と呼ぶ。）この方法では暗号方式の秘匿性を利用して、関係のない情報を相手に知られることなく入力データ対する演算結果を計算する。
【０００３】
以下、ある地域内にある２つの医療機関Ｐ１、Ｐ２が暗号方式を使ってそれぞれがもつ入力の関数適用結果を求める例を図１９の概略図を参照して説明する。
【０００４】
機関Ｐ１とＰ２は図１２に示すような「住民番号表」を用意する。この表は機関Ｐ１とＰ２が事前の取り決めに基づいて、地域内の住民に１から開始する連続する番号をつけたものとする。ここで、住民番号の最大値をＭとする。機関Ｐ１とＰ２はこの住民番号表を使って、それぞれが担当したことのある住民の住民番号をリストした図３に示すような「住民番号リスト」を作成する。さらに、両機関はそれぞれ長さＭの二値変数の配列を用意し、自己のもつ「住民番号リスト」に番号ｉが含まれているならインデックスｉの配列変数を１に、そうでないなら０と記した二値変数配列Ｘ，Ｙを作成する。
【０００５】
次に、機関Ｐ１は自己の保有する暗号鍵を使って自身の二値変数配列Ｘの各要素を別々に暗号化し、暗号値リストＥＸを生成する。機関Ｐ１は生成した暗号値リストＥＸを機関Ｐ２に送信する。機関Ｐ２は自身の二値変数配列Ｙの要素の値が１であるインデックスをもつリストＥＸの暗号値のみ抜き出し、それらの暗号値を掛け合わせることで加算暗号値を得る。この加算暗号値を機関Ｐ２は機関Ｐ１に送ることで、機関Ｐ１は自身の秘密鍵で、加算暗号値を復号することで、機関Ｐ１とＰ２が共通に担当している住民の人数を求めることができる。ここで用いる暗号方式は加算準同型という性質をもち、暗号値どうしを乗算することで、元の平文どうしの加算を行うことができる。よって、機関Ｐ１は共通する担当者の数を知ることができるが、それらの共通の住民まではわからないし、ましてや、機関Ｐ２が何人住民を担当しているかなどの情報も知ることができない。共通に担当している人数を特定後、その人数がある閾値以上であれば、各機関は共通担当住民を特定し、共通担当住民の医療データを交換する。
【０００６】
理解を深めるため、図１９を参照して数値を具体的に追ってみる。まず、機関Ｐ１は自身の二値変数配列Ｘの各要素を自己が保有する暗号鍵を用いて暗号化する。ここでは、１つの値を複数の暗号値で表現でき、かつ、加法準同型を満たすような変形ＥｌＧａｍａｌ暗号方式を考える。０や１をおのおの異なる暗号値に変換して構成した暗号値リストをＥＸとする。ＥＸでは、例えば、二値変数配列の最右の配列要素‘１’の暗号値は‘（３４５６，５６７２）’で表現される。一方、Ｘの右から４番目の配列要素‘１’の暗号値は‘（７８６１、８４６０）’と表現される。次に機関Ｐ１は暗号値リストＥＸを機関Ｐ２に送信する。機関Ｐ２は受信した暗号値リストＥＸで自己のもつ二値変数配列Ｙの内容が‘１’であるインデックスと同じインデックスを持ったリストの暗号値を暗号的に加算する。ここでは、変数配列Ｙの最右の要素‘１’に対応する暗号値‘（３４５６，５６７２）’や変数配列Ｙの最左の要素‘１’に対応する暗号値‘（７１４５，３６１９）’を暗号的に加算する。図１９の例では、機関Ｐ２は加算を行ったことで得られた暗号値は‘（３３５４，５６５２）’である。機関Ｐ２は上記の加算暗号値‘（３３５４，５６５２）’を機関Ｐ１に送信し、機関Ｐ１は自己のもつ暗号鍵で加算暗号値を復号することで結果‘４’を得ることができる。
【０００７】
しかしながら、この方法には問題がある。ある閾値以上に達していれば情報を交換するが、そうでない場合にも共通に担当している人数が明確になってしまう。また、機関Ｐ１のみが先に人数を知ってしまう。そこで、共通に担当している人数を秘匿計算するのではなく、共通担当人数が閾値に達しているか否かを秘匿計算する必要がある。
【０００８】
上記の秘匿計算を実現するため、非特許文献１には、公開鍵暗号方式と秘匿計算回路を使った秘匿計算方法が開示されている。（以下、「従来手法」という）。秘匿計算回路とは任意の関数を秘匿計算するための回路の構成法に基づいて論理回路によって計算できる関数を秘匿計算するための一般的なフレームワークであり、提供されている部品化された手続きを組み合わせて任意の秘匿計算を実現できると理論的には言われている。非特許文献１では秘匿計算回路を共通に担当している人数が閾値より多いか以下かを判定し、かつ、その値を機関Ｐ１とＰ２が協力しないと求められないような値に変換し、出力する。これにより、機関Ｐ１、Ｐ２とも正確な共通担当人数の把握や、優先的に結果を知ることが可能でなくなる。以下、図２０の概略図を参照して非特許文献１の方法を具体的に説明する。
【０００９】
最初に機関Ｐ１は二値変数配列Ｘのそれぞれの要素を自分の公開鍵を使って暗号化し、それらを配列での並び順に機関Ｐ２に送信する。機関Ｐ２は自身の二値変数配列Ｙで１である配列要素のみに着目し、機関Ｐ１より送信された暗号値リストの同じインデックスをもつ暗号値のみ抜き出す。抜き出した暗号値を全て乗じた結果Ｅ＿ＡＤＤを求める。ここまでの手続きは図１９と同じであるので図２０では加算暗号値Ｅ＿ＡＤＤを求めた時点からの概略を示す。次に、機関Ｐ２は撹乱パラメータＲを選択し、Ｒを機関Ｐ１の公開鍵で暗号化し、暗号値Ｅ＿ＡＤＤにその値を乗じ、撹乱加算暗号値Ｅ＿Ｋを求める。その後、暗号値Ｅ＿Ｋを機関Ｐ１に送る。
【００１０】
次に機関Ｐ１は暗号値Ｅ＿Ｋを自身の復号鍵で暗号し、値Ｑを求める。最後に機関Ｐ１は値Ｑを機関Ｐ２は値Ｒと閾値ｋ、撹乱ビットパラメータＴを秘密入力として非特許文献２に記載の秘匿計算回路に入力し、値Ｑ−Ｒ≧ｋならＴと１の排他的論理和の値を出力させ、それ以外ならＴと０の排他的論理和の値Ｓを機関Ｐ１に対して出力させる。機関Ｐ１、Ｐ２は値Ｓと撹乱ビットＴを交換し、自身でＳとＴの排他的論理和を計算し、結果が１なら共通担当者数は閾値ｋを超えており、そうでなければ閾値ｋ以下であると判断する。
【００１１】
理解を深めるために、図２０を参照して数値を具体的に追ってみる。まず、機関Ｐ１は復号値Ｑとして‘７’を知るがこの値から機関Ｐ２の撹乱パラメータＲを減算しないと共通担当者数を求めることができないので、機関Ｐ１は共通担当者数の情報を得ることができない。また、秘匿計算回路からの出力を受け取ったときも、機関Ｐ１は出力Ｓの値‘０’からは共通担当者数が閾値を超えているかどうかを判断することはできず、機関Ｐ２と値を交換してはじめて閾値を超えなかったことを知ることができる。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Ｗｅｉ  Ｊｉａｎｇ  ａｎｄ  Ｃｈｒｉｓ  Ｃｌｉｆｔｏｎ，“Ａ  ｓｅｃｕｒｅ  ｄｉｓｔｒｉｂｕｔｅｄ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ａｃｈｉｅｖｉｎｇ  ｋ−ａｎｏｎｙｍｉｔｙ，”  Ｔｈｅ  ＶＬＤＢ  Ｊｏｕｒｎａｌ，Ｖｏｌ．１５，ｐｐ．３１６−３３３  （２００６）．
【非特許文献２】Ａｎｄｒｅｗ  Ｃｈｉ−Ｃｈｉｈ  Ｙａｏ，“Ｈｏｗ  ｔｏ  ｇｅｎｅｒａｔｅ  ａｎｄ  ｅｘｃｈａｎｇｅ  ｓｅｃｒｅｔｓ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ２７ｔｈ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  （ＦＯＣＳ），ｐｐ．１６２−１６７  （１９８６）．
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、非特許文献１の方法にも問題がある。それは暗号化にかかる回数である。特に地域住民の数が多い場合には暗号化のための時間が増大し、大規模なデータベースを扱うことが難しくなる。また、非特許文献２の秘匿計算回路によって、理論的には任意の秘匿計算を実現可能であることが広く知られているが、実際には非常に複雑なため規模の大きな入力に対して、その計算方法、実現の詳細は現時点で明らかでないという問題がある。以下、図１９、図２０を参照して、この問題を具体的に説明する。
【００１４】
図１９に示すように非特許文献１の方法では住民番号の最大値Ｍに比例した回数、暗号化を行わなければならない。また、加法準同型な暗号方式で扱える値域は、鍵の値域の大きさの対数程度の大きさであることが多く、大規模な入力を扱うには制約が大きい。また、非特許文献２の任意の関数の計算を行う秘匿計算回路の実現の詳細は実際には明らかでなく、特に規模の大きな入力に対しては実現が困難であるため、専用の計算を行う高速な秘匿計算回路を新たに設計する必要がある。
【００１５】
本発明はこれらの問題を鑑みてなされたものであり、入力の規模が大きい関数の秘匿計算を効率よく行うことができる秘匿計算システム、データ処理装置、秘匿計算方法、秘匿計算プログラム、および、該秘匿計算プログラムを記録した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１６】
上記目的を達成するため本発明の第１の観点にかかる秘匿計算システムは２以上のデータ処理装置で構成される秘匿計算システムであって、前記データ処理装置はそれぞれ、秘密データを記憶する秘密データ記憶手段と、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶手段と、
撹乱データを記憶する撹乱データ記憶手段と、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶手段と、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶手段と、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理手段と、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のデータ処理装置へ前記第１係数暗号データを送信する第１暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信する第１暗号データ生成手段と、
他のデータ処理装置より送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のデータ処理装置へ送信する第１加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得手段と、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信する第２暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する第２暗号データ生成手段と、
他のデータ処理装置より送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のデータ処理装置へ送信する第２加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得手段と、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用手段と、
自己の前記論理演算適用手段により得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶手段と、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶手段と、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のデータ処理装置に送信し、送信したデータと他のデータ処理装置により送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出手段とを有することを特徴とする。
【００１７】
前記データ処理装置は、前記秘密データの二値配列表現である正順二値変数配列と前記正順二値変数配列と内容の格納順序が逆順である逆順二値変数配列を作成するデータ二値変数配列表現手段とをさらに有し、
前記第１暗号データ生成依頼手段では自己の保有する前記正順二値変数配列、または、前記撹乱データを自己の保有する暗号鍵で暗号化することで前記第１係数暗号データを生成し、前記第１係数暗号データを他のデータ処理装置へ送信し、
前記第１暗号データ生成手段では他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する正順二値変数配列に演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信し、
前記第２暗号データ生成依頼手段は前記撹乱データと前記逆順二値変数配列に演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信し、
前記第２暗号データ生成手段は他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する逆順二値変数配列に演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信してもよい。
【００１８】
前記データ処理装置は、
前記秘匿論理関数の全体を１度に計算、または、２以上の部分関数の適用によって計算することができるよう前記秘匿論理関数、または、その部分関数の情報に基づいて撹乱データを作成する撹乱データ作成手段と、
前記秘匿論理関数を２以上の部分関数の適用によって計算するとき各部分関数の計算において前記第１暗号データ生成依頼手段と前記第１暗号データ生成手段において秘密データとして用いるデータを特定する情報を生成し、記憶する変数群更新情報作成手段とを有してもよい。
【００１９】
前記撹乱データ記憶手段は、
前記撹乱データとして撹乱するために追加するビット群の撹乱後の二値変数配列での格納位置と値を記した撹乱ビット文字列と他のデータ処理装置もしくは自己が保有する秘密データである二値変数配列のすべての配列要素、または一部の配列要素の撹乱後の二値変数配列での格納位置を表現するビット列対応表として記憶してもよい。
【００２０】
前記第１暗号生成依頼手段は秘密データ、もしくはその一部として前記撹乱データ記憶手段によって記憶されたデータを用い、
前記第２暗号生成依頼手段は秘密データ、もしくはその一部として前記撹乱データ記憶手段によって記憶されたデータを用いてもよい。
【００２１】
前記第１暗号生成手段は、
秘密データとして２以上の正順二値変数配列を用い、
前記第２暗号生成手段は秘密データとして２以上の逆順二値変数配列を用いてもよい。
【００２２】
前記秘匿計算システムは、
２以上のデータ処理装置がアクセス可能なデータ記憶装置をさらに有し、
２以上の前記データ処理装置はそれぞれ、自己の保有する前記演算結果を前記暗号鍵で暗号化した上で前記データ記憶装置に保存し、
他のデータ処理装置が保存した前記演算結果を前記データ記憶装置から取得して自己の保有する前記暗号鍵で復号し、その復号したデータを秘密データとして用い、
前記第１暗号データ生成依頼手段は他のデータ処理装置の撹乱データ記憶手段によって前記データ記憶装置に送信された撹乱データを前記データ記憶装置から取得し秘密データとして用い、
前記第１暗号データ生成手段は他のデータ処理装置の演算結果記録手段によって前記データ記憶装置に送信された演算結果を前記データ記憶装置から取得し秘密データとして用い、
前記第２暗号データ生成依頼手段は他のデータ処理装置の撹乱データ記憶手段によって前記データ記憶装置から送信された撹乱データをデータ記憶装置から取得し秘密データとして用い、
前記第２暗号データ生成手段は他のデータ処理装置によって前記データ記憶装置に送信された演算結果を前記データ記憶装置から取得し秘密データとして用いてもよい。
【００２３】
上記目的を達成するため、本発明の第２の観点にかかるデータ処理装置は、
他のデータ処理装置と連携してデータを処理するデータ処理装置であって、
秘密データを記憶する秘密データ記憶手段と、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶手段と、
撹乱データを記憶する撹乱データ記憶手段と、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶手段と、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶手段と、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理手段と、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のデータ処理装置へ前記第１係数暗号データを送信する第１暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信する第１暗号データ生成手段と、
他のデータ処理装置より送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のデータ処理装置へ送信する第１加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得手段と、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信する第２暗号データ生成依頼手段と、
他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する第２暗号データ生成手段と、
他のデータ処理装置より送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のデータ処理装置へ送信する第２加算暗号データ生成手段と、
他のデータ処理装置より送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得手段と、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用手段と、
自己の前記論理演算適用手段により得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶手段と、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶手段と、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のデータ処理装置に送信し、送信したデータと他のデータ処理装置により送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出手段とを有する、
ことを特徴とする。
【００２４】
上記目的を達成するため、本発明の第３の観点にかかる秘匿計算方法は、
他のデータ処理装置と連携してデータを処理するデータ処理装置により使用される秘匿計算方法であって、
秘密データを記憶する秘密データ記憶ステップと、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶ステップと、
撹乱データを記憶する撹乱データ記憶ステップと、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶ステップと、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶ステップと、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理ステップと、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のデータ処理装置へ前記第１係数暗号データを送信する第１暗号データ生成依頼ステップと、
他のデータ処理装置より送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のデータ処理装置へ送信する第１暗号データ生成ステップと、
他のデータ処理装置より送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のデータ処理装置へ送信する第１加算暗号データ生成ステップと、
他のデータ処理装置より送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得ステップと、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のデータ処理装置へ前記第２係数暗号データを送信する第２暗号データ生成依頼ステップと、
他のデータ処理装置より送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のデータ処理装置へ送信する第２暗号データ生成ステップと、
他のデータ処理装置より送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のデータ処理装置へ送信する第２加算暗号データ生成ステップと、
他のデータ処理装置より送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得ステップと、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用ステップと、
自己の前記論理演算適用ステップで得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶ステップと、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶ステップと、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のデータ処理装置に送信し、送信したデータと他のデータ処理装置により送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出ステップとを有する、
ことを特徴とする。
【００２５】
上記目的を達成するため、本発明の第４の観点にかかる秘匿計算プログラムは、
他のコンピュータと連携してデータを処理するコンピュータにより使用される秘匿計算プログラムであって、
秘密データを記憶する秘密データ記憶ステップと、
秘匿計算したい秘匿計算論理関数の表現を記憶する論理関数式記憶ステップと、
撹乱データを記憶する撹乱データ記憶ステップと、
前記秘密データまたは前記撹乱データの暗号化に使用する暗号鍵、および、その復号に利用する復号鍵を記憶する鍵記憶ステップと、
２つの加算データから元のデータを予測するために使用するビット予測表を記憶するビット予測表記憶ステップと、
秘匿計算の進度を記憶し、変数群に進度に応じた値を設定するループ回数管理ステップと、
前記撹乱データと前記秘密データを前記暗号鍵で暗号化し、第１係数暗号データを生成し、他のコンピュータへ前記第１係数暗号データを送信する第１暗号データ生成依頼ステップと、
他のコンピュータより送信された前記第１係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第１暗号データを生成し、前記第１暗号データを他のコンピュータへ送信する第１暗号データ生成ステップと、
他のコンピュータより送信された前記第１暗号データの暗号化したまま加算することで第１加算暗号データを生成し、前記第１加算暗号データを他のコンピュータへ送信する第１加算暗号データ生成ステップと、
他のコンピュータより送信された前記第１加算暗号データを取得し、自己の保有する復号鍵を用いて第１加算データを生成する第１加算暗号データ取得ステップと、
前記撹乱データと前記秘密データに演算を適用した後、前記暗号鍵で暗号化し、第２係数暗号データを生成し、他のコンピュータへ前記第２係数暗号データを送信する第２暗号データ生成依頼ステップと、
他のコンピュータより送信された前記第２係数暗号データと自己が保有する秘密データに演算を適用した後、前記暗号鍵で暗号化し第２暗号データを生成し、前記第２暗号データを他のコンピュータへ送信する第２暗号データ生成ステップと、
他のコンピュータより送信された前記第２暗号データの暗号化したまま加算することで第２加算暗号データを生成し、前記第２加算暗号データを他のコンピュータへ送信する第２加算暗号データ生成ステップと、
他のコンピュータより送信された前記第２加算暗号データを取得し、自己の保有する復号鍵を用いて第２加算データを生成する第２加算暗号データ取得ステップと、
自己の保有する第１加算データと第２加算データから前記ビット予測表を用いて秘密データの撹乱後のデータを予測することで予測データを作成し、前記予測データに対して論理積、論理和、排他的論理和などの論理演算を適用する論理演算適用ステップと、
自己の前記論理演算適用ステップで得られた論理演算適用結果にさらに前記秘匿計算論理関数の部分関数を適用した部分論理関数適用結果を記憶する演算結果記憶ステップと、
自己のもつ撹乱データに前記秘匿計算論理関数の部分関数を適用した撹乱データ演算結果を記憶する撹乱データ演算結果記憶ステップと、
自己のもつ前記部分論理関数適用結果、または、前記撹乱データ演算結果を他のコンピュータに送信し、送信したデータと他のコンピュータにより送信された前記撹乱データ演算結果、または、前記部分論理関数適用結果に前記秘匿計算論理関数の部分関数を適用し計算結果を算出する計算結果算出ステップとを有する、
ことを特徴とする。
【００２６】
上記目的を達成するため、本発明の第５の観点にかかる記録媒体は、
上記秘匿計算プログラムが記録されていることを特徴とする。
【発明の効果】
【００２７】
本発明によれば、大規模な入力サイズをもつ秘匿計算を効率的に実行することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施の形態１にかかる秘匿計算システムの構成例を示すブロック図である。
【図２】複数機関による事前の取り決めに基づいて、ある地域の住民に一意の番号を付した住民番号表を示す図である。
【図３】図２に示す住民番号表に基づいて、各機関が担当している住民の住民番号をリストした住民番号リストを示す図である。
【図４】図３に示す住民番号リストに基づいて、各機関が担当している住民の住民番号がリストに含まれているか否かを１と０で表現した二値変数配列を示す図である。
【図５】図１に示す制御部によって実現される秘匿計算（ビット推測）機能を示す機能ブロック図である。
【図６】図１に示す制御部によって実現される秘匿計算（暗号加算）機能を示す機能ブロック図である。
【図７】本発明の実施の形態１にかかる「秘匿計算処理」の概要の前半部分を説明するための処理（前半部分）概要図である。
【図８】本発明の実施の形態１にかかる「秘匿計算処理」の概要の後半部分を説明するための処理（後半部分）概要図である。
【図９】本発明の実施の形態１にかかる「秘匿計算処理」の「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」を説明するためのフローチャートである。
【図１０】図９に示す「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」で操作する入力二値変数配列である正順二値変数配列と内容をその逆順に格納した逆順二値変数配列を示す図である。
【図１１】図９に示す「秘匿計算（暗号加算）処理」において入力として与えられる撹乱情報を示す図である。
【図１２】図９に示す「秘匿計算（ビット推測）処理」の「第１暗号データ生成処理」と「秘匿計算（暗号加算）処理」の「第１暗号データ生成依頼処理」を説明するためのフローチャートである。
【図１３】図９に示す「秘匿計算（ビット推測）処理」の「第１加算暗号データ取得処理」と「秘匿計算（暗号加算）処理」の「第１加算暗号データ生成処理」を説明するためのフローチャートである。
【図１４】図９に示す「秘匿計算（ビット推測）処理」の「第２暗号データ生成処理」と「秘匿計算（暗号加算）処理」の「第２暗号データ生成依頼処理」を説明するためのフローチャートである。
【図１５】図９に示す「秘匿計算（ビット推測）処理」の「第２加算暗号データ取得処理」と「秘匿計算（暗号加算）処理」の「第２加算暗号データ生成処理」を説明するためのフローチャートである。
【図１６】図９に示す「秘匿計算（ビット推測）処理」の「論理演算処理」を説明するためのフローチャートである。
【図１７】図９に示す「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」の「ループ回数加算処理」を説明するためのフローチャートである。
【図１８】図９に示す「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」の「計算結果算出処理」を説明するためのフローチャートである。
【図１９】暗号方式を利用する従来の秘匿計算方法を説明するための概略図である。
【図２０】暗号方式と秘匿計算回路を利用する従来の秘匿計算方法を説明するための概略図である。
【図２１】本発明の実施の形態２にかかる秘匿計算システムの構成例を示すブロック図である。
【図２２】本発明の実施の形態２にかかる「秘匿計算処理」の「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」を説明するためのフローチャートである。
【図２３】図２２に示す「秘匿計算（ビット推測）処理」の「第１暗号データ生成処理」と「秘匿計算（暗号加算）処理」の「第１暗号データ生成依頼処理」を説明するためのフローチャートである。
【図２４】図２２に示す「秘匿計算（ビット推測）処理」の「第１加算暗号データ取得処理」と「秘匿計算（暗号加算）処理」の「第１加算暗号データ生成処理」を説明するためのフローチャートである。
【図２５】図２２に示す「秘匿計算（ビット推測）処理」の「第２暗号データ生成処理」と「秘匿計算（暗号加算）処理」の「第２暗号データ生成依頼処理」を説明するためのフローチャートである。
【図２６】図２２に示す「秘匿計算（ビット推測）処理」の「第２加算暗号データ取得処理」と「秘匿計算（暗号加算）処理」の「第２加算暗号データ生成処理」を説明するためのフローチャートである。
【図２７】図２２に示す「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」の「ループ回数加算処理」を説明するためのフローチャートである。
【図２８】図２２に示す「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」の「計算結果算出処理」を説明するためのフローチャートである。
【００２９】
【発明を実施するための形態】
【００３０】
（実施の形態１）
本実施の形態の秘匿計算システム１は機関Ｐ１もしくは機関Ｐ２の持つ秘密情報を秘密に保ったまま関数を計算するための秘匿計算システムである。以下、秘匿計算システムについて図面を参照しながら説明する。まず、図１を参照して秘匿計算システム１の構成について説明する。
【００３１】
秘匿計算システム１は図１に示すように機関Ｐ１と機関Ｐ２それぞれに設置された２台のデータ処理装置１００と、それらを接続する通信線２００とで構成される。２台のデータ処理装置１００は通信線を通じて互いにデータを送受信することで連携して１つの処理を実行する。
【００３２】
データ処理装置１００は、例えば、ＰＣなどで構成され、顧客データなどのプライバシ情報を含んだデータを格納している。データ処理装置１００は図１に示すよう、制御部１１０、通信部１３０、記憶部１４０、操作部１５０、インターフェース部１６０から構成される。
【００３３】
制御部１１０はＣＰＵなどで構成され、データ処理装置１００の各部を制御する。また、制御部１１０は操作部１５０から「秘匿計算開始通知」を受信すると、後述の「秘匿計算処理」を実行する。「秘匿計算処理」は「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」に分けられ、２台のデータ処理装置の一方が「秘匿計算（ビット推測）処理」を実行し、他方が「秘匿計算（暗号加算）処理」を実行する。したがって、制御部１１０は操作部から「秘匿計算処理」を実行するため、「秘匿計算（ビット推測）開始通知」または、「秘匿計算（暗号加算）開始通知」を受信するものとする。
【００３４】
通信部１３０はＬＡＮコネクタや送受信処理用のプロセッサなどから構成され、通信線２００を通じて外部の装置と通信する。
【００３５】
記憶部１４０はハードディスクやＲＡＭなどの記憶装置から構成され、データ処理装置１００の動作に必要なデータ（例えば「秘匿データ」や「暗号鍵」）などを記憶する。
【００３６】
ここで「秘匿データ」とは「住民リスト」や「住民情報」などのプライバシ情報に関連した情報とする。また、「住民リスト」とは、各機関が担当している住民の識別子リストであり、「住民情報」とは各機関の担当している住民の医療情報などである。（以下、機関Ｐ１と機関Ｐ２の担当している住民のリストをそれぞれ、「リストＰ１」、「リストＰ２」と呼ぶ。）住民は連続した整数等の番号によって一意に識別でき、それらの識別子を最大値Ｍとするとき、住民リスト「リストＰ１」、「リストＰ２」はＭ以下の整数列によって表現される。
【００３７】
また、「暗号鍵」とは、データの暗号化に使用するための鍵となる数値であり、「復号鍵」は暗号鍵で暗号化された暗号文を復号できる鍵となる数値であり、各機関それぞれが秘密に保管している。本実施形態では記憶部１４０に保存されている。
【００３８】
また、「暗号鍵」とはデータの暗号化、復号に使用するための鍵となる数値であり、それぞれの機関において任意に選択される。本実施の形態では、記憶部１４０に２以上の複数の暗号鍵が用意される。
【００３９】
操作部１５０はデータ処理装置１００の外面上に構成されている各種ボタンなどによって構成される。ユーザにより所定のボタンが押されると制御部１１０に対して「秘匿計算開始通知」の意味する「秘匿計算（ビット推測）開始通知」か「秘匿計算（暗号加算）開始通知」を送信する。
【００４０】
インターフェース部１６０は例えば、ビデオ出力端子などから構成され、外部の装置へ処理結果を送信する。
【００４１】
以上、秘匿計算システム１の構成について説明したが、次に、制御部１１０の備える機能について「秘匿計算（ビット推測）処理」を実行する場合の図５の機能ブロック図、「秘匿計算（暗号加算）処理」を実行する場合の図６の機能ブロック図、および、図７、図８の処理概略図、図９の二値変数配列説明図、図１０の撹乱データ説明図を参照しながら説明する。
【００４２】
制御部１１０は複数の機関で入力の秘匿情報を守ったままに所望の関数を計算するための「秘匿計算処理」を実行する。秘匿計算処理は「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」に分けられ、操作部１５０からの「秘匿計算（ビット推測）開始通知」または、「秘匿計算（暗号加算）開始通知」により開始される。以下に説明する各機能は秘匿計算処理を実現するための機能である。
【００４３】
記憶部では自己の住民番号リスト（「リストＰ１」、「リストＰ２」）を二値変数配列格納可能に表現したものを記憶している。ここでは、住民番号の最大値Ｍにより長さＭの二値変数配列を用意し、リストＰ１に住民番号ｉが存在していれば二値変数配列のｉ番目の内容を‘１’とする。そうでなければ、二値変数配列のｉ番目は‘０’とする。上記のようにリスト上に存在する住民番号と等しい配列位置に‘１’が格納されている二値変数配列を正順二値変数配列と呼ぶ。また、正順二値変数配列の逆順の二値変数配列を用意し、これを逆順二値変数配列とする。つまり、逆順二値変数配列のｉ番目の値は正順二値変数配列の（Ｍ−ｉ＋１）番目の値と等しい。
【００４４】
ループ回数管理部では、ループ回数を記憶する整数変数ＲＯＯＰを１に初期化し、記憶部より値を読み出し、正順二値変数配列と逆順二値変数配列に値を代入する。ここで、「秘匿計算（ビット推測）処理」を担当する場合には、正順二値変数配列をＸ（図９（ａ））、逆順二値変数配列をＸ’（図９（ｂ））とする。一方、「秘匿計算（暗号加算）処理」を担当する場合には、正順二値変数配列をＹ（図９（ｃ））、逆順二値変数配列をＹ’（図９（ｄ））とする。「秘匿計算（暗号加算）処理」担当の場合には、さらに、記憶部より撹乱データとして撹乱ビット文字列Ａ（図１０（ａ））、撹乱ビット文字列Ｂ（図１０（ｂ））、ビット列対応表ＴＡ（図１０（ｃ））、ビット列対応表ＴＢ（図１０（ｄ））に代入するデータを読み出す。撹乱ビット文字列Ａでは撹乱ビットとして正順二値変数配列Ｘに追加するビット群の撹乱後の二値変数配列での撹乱位置と値が記されている。例えば、図１０（ａ）の撹乱ビット文字列ＡではＡの長さＮより撹乱ビットが正順二値変数配列ＸにＮ−Ｍ個追加され、１番目、２番目、４番目、…に値‘１’、‘１’、‘１’、…の撹乱ビットが追加されることを示している。ここで、３番目の‘＊’は正順二値変数配列Ｘの要素が入ることを示している。Ｘの何番目の要素の値が撹乱後の二値変数配列に入るかは、図１０（ｃ）のビット列対応表ＴＡに記されている。図１０（ｃ）の表ＴＡでは撹乱後に３番目の配列要素の値は配列ＸのＭ番目の値となることを示している。撹乱ビット文字列Ｂ（図１０（ｂ））、ビット列対応表ＴＢ（図１０（ｄ））は正順二値変数配列Ｙに対するものである。
【００４５】
「秘匿計算（暗号加算）処理」と担当している制御部１１０の第１暗号データ生成依頼部１１９は、他の機関のデータ処理装置１００で「秘匿計算（ビット推測）処理」を担当している制御部１１０の第１暗号データ生成部１１２と連携して、自己のもつ撹乱データに基づき正順二値変数配列Ｘ，Ｙを撹乱する（図７（ｂ））。
【００４６】
さらに、「秘匿計算（ビット推測）処理」を担当している制御部１１０の第１加算暗号データ取得部１１３は、他の機関のデータ処理装置１００で「秘匿計算（暗号加算）処理」と担当している制御部１１０の第１加算暗号データ生成部１２０と連携して、正順二値変数配列Ｘ，Ｙの撹乱後の２つの二値変数配列をそれぞれ２つの整数の二進数表現とみなしたときの加算結果を求め、結果を二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）に格納する。この二値変数配列を正順加算二値変数配列と呼ぶ（図７（ｃ）、（ｄ））。
【００４７】
「秘匿計算（暗号加算）処理」と担当している制御部１１０の第２暗号データ生成依頼部１２１は、他の機関のデータ処理装置１００で「秘匿計算（ビット推測）処理」を担当している制御部１１０の第２暗号データ生成部１１４と連携して、自己のもつ撹乱データに基づき逆順二値変数配列Ｘ’，Ｙ’を撹乱する（図７（ｂ））。
【００４８】
さらに、「秘匿計算（ビット推測）処理」を担当している制御部１１０の第２加算暗号データ取得部１１５は、他の機関のデータ処理装置１００で「秘匿計算（暗号加算）処理」と担当している制御部１１０の第２加算暗号データ生成部１２１と連携して、逆順二値変数配列Ｘ’，Ｙ’の撹乱後の２つの二値変数配列をそれぞれ２つの整数の二進数表現とみなしたときの加算結果を求め、結果を二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）’に格納する。この二値変数配列を逆順加算二値変数配列と呼ぶ（図７（ｃ）、（ｄ））。
【００４９】
「秘匿計算（ビット推測）処理」を担当する制御部１１０の論理演算適用処理部１１６では自己の保有する正順加算二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）と逆順加算二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）’と記憶部１４０に格納しているビット推測表（表１）を用いて撹乱後の２つの二値変数配列をあいまいに推測し、推測結果を推測二値変数配列ＩＸとＩＹに格納する。その後、二値変数配列ＩＸ、ＩＹの各配列インデックスｉにおいて、それぞれの要素ＩＸ［ｉ］、ＩＹ［ｉ］に論理演算である論理和、論理積、排他的論理和を適用し、結果をそれぞれ二値変数配列Ｃ＿ＡＮＤ、Ｃ＿ＯＲ、Ｃ＿ＥＸＯRに格納する。
【表１】
2014048548.tif 000003
【００５０】
「秘匿計算（ビット推測）処理」を担当する制御部１１０の演算記録部１１７では自己のもつ論理演算適用結果Ｃ＿ＡＮＤ、Ｃ＿ＯR，Ｃ＿ＥＸＯＲに記録部１４０に格納されている関数名の関数を適用し、結果を二進法で表現し、二値変数配列Ｃ＿Ｆ１に格納し、記録部１４０にＣ＿Ｆ１の内容を記録する。演算結果記録部１１７で適用される関数としてはＣ＿ＡＮＤの‘１’の数を求めるなどがある（図８（ａ））。
【００５１】
「秘匿計算（暗号加算）処理」を担当する制御部１１０の撹乱データ記録部１２３では自己のもつ撹乱データに記録部１４０に格納されている関数名の関数を適用し、結果を二進法で表現し、二値変数配列Ｃ＿Ｆ２に格納し、記録部１４０にＣ＿Ｆ２の内容を記録する。撹乱データ記録部１２３で適用される関数としては、撹乱ビット文字列Ａと撹乱ビット文字列Ｂの各配列位置で配列内容の論理積を求め、その結果が‘１’となった回数を出力するなどがある（図８（ｂ））。
【００５２】
演算ループ回数管理部１１１では、整数変数Ｔの値が記録部１４０に格納されている最終ループ回数以上の値であるという条件を満たすか判定する。もし、条件が満たされない場合には、整数変数Ｔの値を１だけ加算し、記憶部１４０に記録されているループ回数がＲＯＯＰの内容のときに正順二値変数Ｘ，Ｙ、撹乱ビット文字列Ａ、Ｂ、ビット列対応表ＴＡ、ＴＢとして用いるべき情報の格納位置を読み出し、自身が「秘匿計算（ビット推測）処理」を担当しているなら、正順二値変数配列Ｘに指定された格納位置にある情報を読み出し格納し、さらにＸに対応するよう逆順二値変数配列Ｘ’を更新する（図８（ｃ））。また、自身が「秘匿計算（暗号加算）処理」を担当しているなら、正順二値変数配列Ｙ、撹乱ビット文字列Ａ、Ｂ、ビット列対応表ＴＡ，ＴＢにそれぞれ指定された格納位置にある情報を読み出し格納し、さらにＹに対応するよう逆順二値変数配列Ｙ’を更新する（図８（ｄ））。
【００５３】
計算結果算出部１１８では、記録部１４０に格納されている最終結果格納位置を読み出し、さらに最終結果格納位置に保存されている情報を読み出し二値変数配列Ｆ＿１かＦ＿２に保存する。その後、他の機関のデータ処理装置１００と二値変数配列Ｆ＿１、Ｆ＿２を交換し、記録部１４０に格納されている最終適用関数名を読み出し、読み出した名前の関数ｆ＿ＦｉｎａｌをＦ＿１、Ｆ＿２に対して適用することで最終結果を得る（図８（ｆ））。その後、インターフェース部１６０を通じて外部の装置へ最終結果を送信する。図８（ｆ）の例では最終関数としてＦ＿１とＦ＿２の排他的論理和が指定されていたとする。図７、図８の例では最終的に互いに共通して担当している住民が１人以上いることが秘匿判定できた。
【００５４】
以上、制御部の機能について説明したが、次にデータ処理装置１００で実行される「秘匿計算処理」について説明する。機関Ｐ１および機関Ｐ２に設置された２台のデータ処理装置１００は「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」という別々の処理を相互に情報を交換しながら実行することで、協力して「秘匿計算処理」を実行する。
【００５５】
制御部１１０は操作部１５０から「秘匿計算（ビット推測）開始通知」または「秘匿計算（暗号加算）開始通知」を受信すると図１１に示す「秘匿計算処理（ビット推測）処理」または「秘匿計算処理（暗号加算）処理」を実行する。以下、図１１の処理概略図を参照しながら説明する。「秘匿計算処理（ビット推測）処理」は大きく１０のステップからなり、「秘匿計算処理（暗号加算）処理」は大きく９つのステップから成る。なお、以下に説明する「秘匿計算処理（ビット推測）処理」の各ステップの内容は機関Ｐ１のデータ処理装置１００で実行され、「秘匿計算処理（暗号加算）処理」の各ステップの内容は機関Ｐ２のデータ処理装置１００で実行される。
【００５６】
最初にステップＳ１００のループ回数初期化処理について説明する。制御部１１０では、ループ回数を記憶する整数変数Ｔを１に初期化し、記憶部より値を読み出し、正順二値変数配列と逆順二値変数配列に値を代入する。ここで、「秘匿計算（ビット推測）処理」を担当する場合には、正順二値変数配列をＸ、逆順二値変数配列をＸ’とする。一方、「秘匿計算（暗号加算）処理」の場合には、正順二値変数配列をＹ、逆順二値変数配列をＹ’とする。「秘匿計算（暗号加算）処理」の場合には、さらに、記憶部より撹乱データとして撹乱ビット文字列Ａ、撹乱ビット文字列Ｂ、ビット列対応表ＴＡ、ビット列対応表ＴＢに代入するデータを読み出す。
【００５７】
「秘匿計算（暗号加算）処理」を担当している制御部１１０は次にステップＳ２００の第１暗号データ生成依頼処理を実行する。第１暗号生成依頼処理は、他の機関のデータ処理装置１００で「秘匿計算（ビット推測）処理」を担当している制御部１１０とステップＳ３００の第１暗号データ生成処理を連携して実行することにより、自己のもつ撹乱データに基づき正順二値変数配列Ｘ，Ｙを撹乱する（図７（ｂ））。その具体的な方法は後で詳しく述べる。
【００５８】
さらに、「秘匿計算（ビット推測）処理」を担当している制御部１１０はステップＳ５００の第１加算暗号データ取得ステップを、他の機関のデータ処理装置１００で「秘匿計算（暗号加算）処理」と担当している制御部１１０とステップＳ４００の第１加算暗号データ生成ステップを連携して実行することにより、正順二値変数配列Ｘ，Ｙの撹乱後の２つの二値変数配列をそれぞれ２つの整数の二進数表現とみなしたときの加算結果を求め、結果を二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）に格納する（図７（ｃ）、（ｄ））。
【００５９】
「秘匿計算（暗号加算）処理」を担当している制御部１１０はステップＳ６００の第２暗号データ生成依頼処理を実行する。制御部１１０は、他の機関のデータ処理装置１００で「秘匿計算（ビット推測）処理」を担当し、ステップＳ７００の第２暗号データ生成処理を実行している制御部１１０と連携して、自己のもつ撹乱データに基づき逆順二値変数配列Ｘ’，Ｙ’を撹乱する（図７（ｂ））。
【００６０】
さらに、「秘匿計算（ビット推測）処理」を担当している制御部１１０はステップＳ９００の第２加算暗号データ処理を、他の機関のデータ処理装置１００で「秘匿計算（暗号加算）処理」と担当し、ステップＳ８００を実行している制御部１１０と第２加算暗号データ生成処理と連携して実行することにより、逆順二値変数配列Ｘ’，Ｙ’の撹乱後の２つの二値変数配列をそれぞれ２つの整数の二進数表現とみなしたときの加算結果を求め、結果を二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）’に格納する（図７（ｃ）、（ｄ））。
【００６１】
次に「秘匿計算（ビット推測）処理」を担当する制御部１１０はステップＳ１０００の論理演算適用処理を実行することにより、自己の保有する正順加算二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）と逆順加算二値変数配列ＮＥＷ＿（Ｘ＋Ｙ）’と記憶部１４０に格納しているビット推測表（表１）を用いて撹乱後の２つの二値変数配列をあいまいに推測し、推測結果を推測二値変数配列ＩＸとＩＹに格納する。その後、二値変数配列ＩＸ、ＩＹの各配列インデックスｉにおいて、それぞれの要素ＩＸ［ｉ］、ＩＹ［ｉ］に論理演算である論理和、論理積、排他的論理和を適用し、結果をそれぞれ二値変数配列Ｃ＿ＡＮＤ、Ｃ＿ＯＲ、Ｃ＿ＥＸＯＲに格納する。
【００６２】
さらに「秘匿計算（ビット推測）処理」を担当する制御部１１０はステップＳ１２００の演算記録処理を実行し、自己のもつ論理演算適用結果Ｃ＿ＡＮＤ、Ｃ＿ＯR，Ｃ＿ＥＸＯＲに記録部１４０に格納されている関数名の関数を適用し、結果を二進法で表現し、二値変数配列Ｃ＿Ｆ１に格納し、記録部１４０にＣ＿Ｆ１の内容を記録する（図８（ａ））。
【００６３】
「秘匿計算（暗号加算）処理」を担当する制御部１１０はステップＳ１１００の撹乱データ記録ステップを実行し、自己のもつ撹乱データに記録部１４０に格納されている関数名の関数を適用し、結果を二進法で表現し、二値変数配列Ｃ＿Ｆ２に格納し、記録部１４０にＣ＿Ｆ２の内容を記録する（図８（ｂ））。
【００６４】
次に制御部１１０はステップＳ１３００のループ回数判定処理を実行し、整数変数Ｔの値が記録部１４０に格納されている最終ループ回数以上の値であるという条件を満たすか判定する。もし、条件が満たされない場合には、制御部１１０はステップＳ１４００のループ回数加算処理を実行し、整数変数Ｔの値を１だけ加算し、記憶部１４０に記録されているループ回数がＴの内容のときに正順二値変数Ｘ，Ｙ、撹乱ビット文字列Ａ、Ｂ、ビット列対応表ＴＡ、ＴＢとして用いるべき情報の格納位置を読み出し、自身が「秘匿計算（ビット推測）処理」を担当しているなら、正順二値変数配列Ｘに指定された格納位置にある情報を読み出し格納し、さらにＸに対応するよう逆順二値変数配列Ｘ’を更新する（図８（ｃ））。また、自身が「秘匿計算（暗号加算）処理」を担当しているなら、正順二値変数配列Ｙ、撹乱ビット文字列Ａ、Ｂ、ビット列対応表ＴＡ，ＴＢにそれぞれ指定された格納位置にある情報を読み出し格納し、さらにＹに対応するよう逆順二値変数配列Ｙ’を更新する（図８（ｄ））。
【００６５】
制御部１１０はステップＳ１３００でループ回数に関する条件は満たされていると判定した場合には、ステップＳ１５００の計算結果算出処理を実行し、記録部１４０に格納されている最終結果格納位置を読み出し、さらに最終結果格納位置に保存されている情報を読み出し二値変数配列Ｆ＿１かＦ＿２に保存する。その後、他の機関のデータ処理装置１００でステップＳ１５００の計算結果算出処理を実行している制御部１１０と連携し、二値変数配列Ｆ＿１、Ｆ＿２を交換し、記録部１４０に格納されている最終適用関数名を読み出し、読み出した名前の関数ｆ＿ＦｉｎａｌをＦ＿１、Ｆ＿２に対して適用することで最終結果を得る（図８（ｆ））。その後、インターフェース部１６０を通じて外部の装置へ最終結果を送信する。
【００６６】
以上、秘匿計算処理の概要について説明したが、次に秘匿計算処理を詳細に説明する。最初に、ステップＳ２００の「第１暗号データ生成依頼処理」とステップＳ３００の「第１暗号データ生成処理」について説明する。ステップＳ２００とステップＳ３００は図１２の「第１暗号データ生成依頼処理」と「第１暗号データ生成処理」にそれぞれ対応している。以下、図１２のフローチャートを参照して「第１暗号データ生成依頼処理」および「第１暗号データ生成処理」について説明する。なお、第１暗号データ生成依頼処理は第１暗号データ生成依頼部１１９で実行され、第１暗号データ生成処理は第１暗号データ生成部１１２で実行される。
【００６７】
第１暗号データ生成依頼部１１９は記憶部１４０に保存されている撹乱ビット列Ａとビット列対応表ＴＡに従って、その時点で機関Ｐ１がもっている正順二値変数配列Ｘの各ｉ番目の変数Ｘ［ｉ］をビット列対応表ＴＡの行ｉの内容ＴＡ［ｉ］に等しい順番に移動させるために正順二値変数配列Ｘを切断する回数Ｎと切断場所を指定する切断点リストＬＩＳＴ＿ＲＮ＝＜ｒ＿１，ｒ＿２，…，ｒ＿Ｎ＞を決定する（ステップＳ１０１）。例えば、Ｘの長さが４でビット列対応表ＴＡ［１］＝３、ＴＡ［２］＝６、ＴＡ［３］＝８、ＴＡ［４］＝４であったとき、各ビットを１つずつになるようＸを切断する必要がある。よって、切断回数を３、切断点リストを〈１，２，３〉とする。Ｘ［１］、Ｘ［２］、Ｘ［３］、 Ｘ［４］の４つの部分にＸを切断することを指定したことになる。
【００６８】
次に、第１暗号データ生成依頼部は切断点数Ｎと切断点リストＬＩＳＴ＿ＲＮを相手機関のデータ処理装置１００に送信する（ステップＳ１０２）。
【００６９】
第１暗号データ生成部１１２は相手機関から切断点数Ｎと、切断点リストＬＩＳＴ＿ＲＮが送られてくるのを待つ（ステップＳ２０１:Ｎｏ）。相手機関から切断点数Ｎと切断点リストＬＩＳＴ＿ＲＮが送られてきたら、ステップＳ２０２に進む（ステップＳ２０１:Ｙｅｓ）。
【００７０】
第１暗号データ生成部１１２は相手機関から送られてきた切断点リストＬＩＳＴ＿ＲＮに従い、二値変数配列ＸのＮ＋１個の変形を計算する。この変形方法は相手機関も事前に知っているものとする。計算した二値変数配列を整数化した値をＡ＿１、Ａ＿２、…、Ａ＿（Ｎ＋１）とする。さらにＡ＿（Ｎ＋２）にランダムな値αを設定し〈Ａ１、Ａ２、…ＡＮ＋1，ＡＮ＋２〉をリストＬＩＳＴ＿Ａとし、ステップＳ２０３に進む（ステップＳ２０２）。
【００７１】
第１暗号データ生成依頼部１１９では、さらに、切断部分をビット列対応表で指定されている位置に移動させるため、２の指数乗倍した後、加算する。例えば、先の指定例ではＸ［１］×２３−１＋Ｘ［２］×２６−１＋Ｘ［３］×２８−１＋Ｘ［４］×２４−１を計算し、その値を二進法で表現したときにビット列対応表のように移動させることができる。しかしながら、機関Ｐ２の第１暗号データ生成依頼部は機関Ｐ１のもつ正順二値変数配列Ｘの値を知ることができないため、実際に先の値を計算することはできない。一方、機関Ｐ１に各ビットにどれだけの値を乗算するかを示してしまえば、ビット列対応表ＴＡを機関Ｐ１が知るところとなる。そこで、本発明では、各切断後の切断部分に乗算したい係数を暗号化して機関Ｐ１に渡し、機関Ｐ１は暗号化したままの係数を乗じた切断部分の暗号値を作成する。
【００７２】
第１暗号データ生成依頼部１１９は事前に相手機関と取り決めているステップＳ２０２の正順二値変数配列の変形方法に従い、Ｃ＿１×Ａ＿１＋Ｃ＿２×Ａ＿２＋…＋Ｃ＿（Ｎ＋１）×Ａ＿（Ｎ＋１）＝Ｘ［１］×２ＴＡ［１］−１＋Ｘ［２］×２ＴＡ［２］−１＋…＋Ｘ［Ｍ］×２ＴＡ［Ｍ］−１を満たす係数Ｃ＿１、Ｃ＿２、…、Ｃ＿（Ｎ＋１）を求める。さらに、Ｎ＋２番目の係数Ｃ＿（Ｎ＋２）をＣ＿（Ｎ＋２）＝Ｃ＿１＋Ｃ＿２＋…＋Ｃ＿（Ｎ＋１）とする。ここで、各Ｃ＿ｉを各Ａ＿ｉの係数を定数倍（定数の値をＣＯＮＳＴとする）した値に設定してもよい（ステップＳ１０３）。係数の暗号化、送信方法については後に説明する。
【００７３】
次に、第１暗号データ生成依頼部１１９では記憶部１４０に格納している撹乱ビット列Ｂとビット列対応表ＴＢに従い、自身の正順二値変数配列Ｙを並び替え、かつ、撹乱ビット列を挿入する。新しい並び替えにより構成された二値変数配列をＮＥＷ＿Ｙと呼ぶとすると、１≦ｉ≦Ｍを満たす各整数ｉにおいて、ＮＥＷ＿Ｙ[ＴＢ[ｉ]]＝Ｙ[ｉ]となり、全てのｉでｊ≠ＴＢ[ｉ]を満たす整数ｊ（つまり、新しい配列のｊ番目の要素は正順二値変数配列の要素ではない）ではＮＥＷ＿Ｙ[ｊ]＝Ｂ[ｊ]を満たす。さらに、このＮＥＷ＿Ｙを整数化した値に撹乱ビット列Ａで＊を０とみなしたビット列が表現する整数値をＮＥＷ＿Ｙに加算した値をＮＥＷ＿Ｙ’とする。本発明では、Ｙのビット並び替え後、撹乱ビットを挿入した値に、Ｘのビット並び替え後に挿入したい撹乱ビットの値を加算した値としてＮＥＷ＿Ｙ’を計算する。さらに、このＮＥＷ＿Ｙ’を切断回数Ｎに２を加算した値Ｎ＋２個の整数に分割する。ここでは、分割後の値をＢ＿１、…、Ｂ＿（Ｎ＋２）としたとき、Ｂ＿１＋Ｂ＿２＋…＋Ｂ＿（Ｎ＋２）＝ＮＥＷ＿Ｙ’を満たすように整数Ｂ＿１、Ｂ＿２、…、Ｂ＿（Ｎ＋２）をランダムに設定する（ステップＳ１０４）。
【００７４】
さらに、第１暗号データ生成依頼部１１９は１≦ｉ≦Ｎ＋２を満たす整数ｉにおいて、（Ｃ＿ｉ，Ｂ＿ｉ）を記憶部１４０で記憶する暗号鍵ＫｅｙＰ２＿ｉで暗号化して暗号ペア（Ｌ＿ｉ，Ｑ＿ｉ）を生成し、Ｎ＋２個の暗号ペアをその作成順にリストした暗号ペアリストＬＩＳＴ＿ＬＱ＝＜（Ｌ＿１，Ｑ＿１）、（Ｌ＿２，Ｑ＿２）、…、（Ｌ＿（Ｎ＋２），Ｑ＿（Ｎ＋２））＞を生成する。第１暗号データ生成依頼部１１９は図１２に示すように、係数Ｃ＿ｉとＮＥＷ＿Ｙ’の部分Ｂ＿ｉを切断部分ごとに異なった暗号鍵ＫｅｙＰ２＿ｉを使用して暗号化する。そのため、記憶部１４０にはＮ＋２種類以上の鍵が記憶されている（ステップＳ１０５）。
【００７５】
続いて図１２のステップＳ１０６について説明する。第１暗号データ生成依頼部１１９は生成した暗号ペアリストＬＩＳＴ＿ＬＱを、通信部１３０を介して相手機関のデータ処理装置１００に送信する（ステップＳ１０６）。暗号ペアリストＬＩＳＴ＿ＬＱを送信した第１暗号データ生成依頼部１１９は図１１のフローに戻り、ステップＳ３００の第１加算暗号データ生成処理を開始する。
【００７６】
第１暗号データ生成部１１２は相手機関から暗号ペアリストＬＩＳＴ＿ＬＱが送信されるのを待つ（ステップＳ２０３：Ｎｏ）。相手機関から暗号ペアリストＬＩＳＴ＿ＬＱが送信されたら、ステップＳ２０４に進む。
【００７７】
相手機関より受け取った暗号ペアリストＬＩＳＴ＿ＬＱ＝＜（Ｌ＿１、Ｑ＿１）、（Ｌ＿２、Ｑ＿２）、…、（Ｌ＿（Ｎ＋２）、Ｑ＿（Ｎ＋２）＞に対して、第１暗号生成データ部１１２では１≦ｉ≦Ｎ＋１を満たす各整数ｉに対してＤ＿ｉ＝（Ａ＿ｉ＋Ａ＿（Ｎ＋２））×Ｌ＿ｉ＋Ｑ＿ｉを暗号的に計算し、また、Ｄ＿（Ｎ＋２）＝Ａ＿（Ｎ＋２）×Ｌ＿（Ｎ＋２）＋Ｑ＿（Ｎ＋２）を暗号的に計算する。各整数ｉ（１≦ｉ≦Ｎ＋２）における計算結果Ｄ＿ｉを記憶部１４０に格納している鍵ＫｅｙＰ１で暗号化し、暗号値ＥＤ＿ｉを得る。上記の計算、暗号化を１≦ｉ≦Ｎ＋２を満たす各整数ｉに対して実行する（ステップＳ２０４）。以上の処理により、第１暗号データ生成部１１２は、相手機関に自身のデータを知らせることなく、相手機関のデータとの加算結果を求めるために役立つ暗号データリストを生成したことになる。暗号データリストＬＩＳＴ＿ＥＤ＝＜ＥＤ＿１，ＥＤ＿２，…，ＥＤ＿（Ｎ＋２）＞の生成が完了すると、次に制御部１１０は図１１のフローに戻り、ステップＳ５００の第１加算暗号データ取得処理を開始する。第１加算暗号データ取得処理は第１加算暗号データ取得部１１３で実行される。
【００７８】
以上、「第１暗号データ生成依頼処理」、「第１暗号データ生成処理」について詳細に説明したが、次にステップＳ４００の「第１加算暗号データ生成処理」とステップＳ５００の「第１加算暗号データ取得処理」について図１３のフローチャートを参照して説明する。
【００７９】
第１加算暗号データ取得部１１３では第１暗号データ生成処理で生成した暗号データリストＬＩＳT＿ＥＤを通信部１３０を介し相手機関のデータ処理装置１００に送信し（ステップＳ３０１）、ステップＳ３０２に進む。なお、本ステップでのデータ送信に際しては、リスト中の暗号分の順番を変更してはならない。後の処理（ステップＳ４０２）において暗号鍵ＫｅｙＰ２＿ｉと要素との対応関係がとれなくなるからである。
【００８０】
第１加算暗号データ生成部１２０では、相手機関から暗号データリストＬＩＳＴ＿ＥＤが送信されるのを待つ（ステップＳ４０１：Ｎｏ）。相手機関から暗号リストＬＩＳＴ＿ＥＤが送信されたら、ステップＳ４０２に進む（ステップＳ４０１：Ｙｅｓ）。
【００８１】
第１加算暗号データ生成部１２０では暗号データリストＬＩＳＴ＿ＥＤ＝＜ＥＤ＿１、ＥＤ＿２，…，ＥＤ＿（Ｎ＋２）＞の各要素ＥＤ＿ｉ（１≦ｉ≦ｎ＋２）を記憶部１４０に格納してある暗号鍵ＫｅｙＰ２＿ｉ（もしくは暗号鍵ＫｅｙＰ２＿ｉに対応する復号鍵）で復号し、復号値Ｆ＿ｉを得る。ここで、暗号データリストＬＩＳＴ＿ＥＤを復号した結果のリストを「暗号データリストＦ」とする。Ｆを暗号データリストと呼ぶ理由は、機関Ｐ１のもつ暗号鍵で復号したが、各Ｆ＿ｉはまだ機関Ｐ１の暗号鍵ＫｅｙＰ１で暗号化されたままだからである（ステップＳ４０２）。
【００８２】
第１加算暗号データ生成部１２０では「暗号データリストＦ」のＮ＋２個の暗号値を暗号化したまま、暗号的に加算し、必要があれば記憶部１４０に格納している共通係数ＣＯＮＳＴを乗算し、第１加算暗号データＦ＿ＳＵＭを生成する（ステップＳ４０３）。
【００８３】
第１加算暗号データ生成部１２０は次に第１加算暗号データＦ＿ＳＵＭを通信部１３０を介して相手機関のデータ処理装置１００に送信する（ステップＳ４０４）。第１加算暗号データＦ＿ＳＵＭの送信が完了すると、次に制御部１１０は図１１のフローに戻り、ステップＳ６００の第２暗号データ生成依頼処理に進む。第２暗号データ生成依頼処理は第２暗号データ生成依頼処理部１２１で実行される。
【００８４】
第１加算暗号データ取得部１１３では第１加算暗号データＦ＿ＳＵＭが相手機関から送信されるのを待つ（ステップＳ３０２のＮｏ）。相手機関から第１加算暗号データＦ＿ＳＵＭが送信されたらステップＳ３０３へ進む（ステップＳ３０２のＹｅｓ）。
【００８５】
第１加算暗号データ取得部１１３では第１加算暗号データＦ＿ＳＵＭを自己が記憶部に格納している暗号鍵ＫｅｙＰ１（もしくは暗号鍵ＫｅｙＰ１に対応する復号鍵）で復号する。これにより得られたデータをＮＥＷ＿（Ｘ＋Ｙ）とし、第１加算データと呼ぶ。ＮＥＷ＿（Ｘ＋Ｙ）は正順二値変数配列ＸとＹを秘匿計算（暗号加算）処理担当の機関Ｐ２が各配列の並びの順序をビット列対応表ＴＡ，ＴＢに従い入れ替えた上、撹乱のためにビットを追加し、値を設定したうえで加算した値である。秘匿計算（暗号加算）処理担当の機関Ｐ２は相手機関の値を知ることができず、かつ、加算後の値も知ることがない。一方、秘匿計算（ビット推測）処理担当の機関Ｐ１は相手機関Ｐ２がどのように配列の順序を入れ替えたのか、また、相手機関の二値変数配列Ｙおよび、追加したビットがどのようなものであるかを知ることができない。第１加算データＮＥＷ＿（Ｘ＋Ｙ）を求めたら、制御部１１０は図１１のフローに戻り、第２暗号データ生成処理のステップＳ７００に進む。第２暗号データ生成処理は第２暗号データ生成部１１４が実行する。
【００８６】
以上、秘匿計算処理での正順二値変数配列Ｘ，Ｙに撹乱と加算を行った結果である第１加算データを構成するまでの処理を詳細に説明したが、次にステップＳ６００の第２暗号データ生成依頼処理、ステップＳ７００の第２暗号データ生成処理、ステップＳ８００の第２加算暗号データ生成処理、ステップＳ９００の第２加算データ取得処理の流れを図１４、図１５を参照し説明する。制御部１１０では相手機関のデータ処理装置１１０と連携してステップＳ６００、ステップＳ７００，ステップＳ８００、ステップＳ９００を実行することによって、逆順二値変数配列Ｘ’、Ｙ’に撹乱と加算を行った結果である第２加算データを構成する。第２加算暗号データ生成処理、第２加算データ取得処理はそれぞれ、第２加算暗号データ生成部１２２、第２加算データ取得部１１５が実行する。
【００８７】
第２暗号データ生成部１１４は、正順二値変数配列に対する撹乱データである撹乱ビット列Ａ、Ｂ、ビット列対応表ＴＡ、ＴＢに対応する逆順二値変数配列Ｘ’、Ｙ’に対する撹乱データである撹乱ビット列Ａ’、Ｂ’、ビット列対応表ＴＡ’、ＴＢ’を求める。具体的には撹乱ビット列Ａ、Ｂの長さがＮであるとき、各整数ｉ（１≦ｉ≦Ｎ）に対して、Ａ’［ｉ］＝Ａ［ｎ−ｉ＋１］、Ｂ’［ｉ］＝Ｂ［ｎ−ｉ＋１］、ＴＡ’［ｉ］＝ｎ−ＴＡ［ｉ］＋１、ＴＢ’［ｉ］＝ｎ−ＴＢ［ｉ］＋１とする（ステップＳ５０１）。次に、第２暗号データ生成依頼部１２１はステップＳ５０２に進む。
【００８８】
ステップＳ５０２以降の第２暗号データ生成依頼処理、第２暗号データ生成処理、第２加算暗号データ生成処理、第２加算暗号データ取得処理は図１４、図１５に示すように、それぞれ第１暗号データ生成依頼処理、第１暗号データ生成依頼処理、第１加算暗号データ生成処理、第１加算暗号データ処理の流れと同じである。ただ、対象とする二値変数配列が逆順二値変数配列Ｘ’、Ｙ’、撹乱データがＡ’、Ｂ’、ＴＡ’、ＴＢ’、暗号鍵がＫｅｙＰ１’、ＫｅｙＰ２＿ｉ’という点が異なる。よって、第２加算暗号データＦ’＿ＳＵＭを計算するステップＳ４０３までの詳細な説明は省く。
【００８９】
第２加算暗号データ生成部１２２は第２加算暗号データＦ’＿ＳＵＭを通信部１３０を介して相手機関のデータ処理装置１００に送信する（ステップＳ４０４）。第２加算暗号データＦ’＿ＳＵＭの送信が完了すると、次に制御部１１０は図１１のフローに戻り、ステップＳ１３００の判定を行う。ループ回数Ｔが記憶部に格納されている最終ループ回数Ｔ＿ＦＩＮＡＬと等しくなければ、ステップＳ１４００のループ回数加算処理に進む（ステップＳ１３００のＹｅｓ）。ループ回数Ｔが最終ループ回数Ｔ＿ＦＩＮＡＬと等しければ、ステップＳ１５００の計算結果算出処理に進む（ステップＳ１３００のＮｏ）。
【００９０】
第２加算暗号データ取得部１１５では第２加算暗号データＦ’＿ＳＵＭを自己が記憶部に格納している暗号鍵ＫｅｙＰ１’（もしくは暗号鍵ＫｅｙＰ１’に対応する復号鍵）で復号する。これにより得られたデータをＮＥＷ＿（Ｘ＋Ｙ）’とし、第２加算データと呼ぶ。ＮＥＷ＿（Ｘ＋Ｙ）’は逆順二値変数配列ＸとＹを秘匿計算（暗号加算）処理担当の機関Ｐ２が各配列の並びの順序をビット列対応表ＴＡ’，ＴＢ’に従い入れ替えた上、撹乱のためにビットを追加し、値を設定したうえで加算した値である。第２加算データＮＥＷ＿（Ｘ＋Ｙ）’を求めたら、制御部１１０は図１１のフローに戻り、論理演算適用処理のステップＳ１２００に進む。論理演算適用処理は論理演算適用部１１６が実行する。
【００９１】
論理演算適用部１１６ではまず第１加算データＮＥＷ＿（Ｘ＋Ｙ）と第２加算データＮＥＷ_（Ｘ＋Ｙ）’より表１のビット推測表を用いて、正順二値変数配列Ｘ，Ｙの撹乱後で、かつ、加算前の２つの二値変数配列を推測し、推測結果を二値変数配列ＩＸ、ＩＹに格納する。その後、ＩＸとＩＹの各要素に対して論理演算を適用する。以降ではまず、表１のビット推測表について説明し、次に論理演算適用部１１６が第１加算データ、第２加算データよりどのようにＩＸ、ＩＹに値を設定するか表２、表３、図１６を参照し説明する。
【００９２】
表１のビット推測表は長さｎのビット列ｘ、ｙの加算結果である長さｎ＋１のビット列ａ、ビット列ｘ、ｙの逆順ビット列ｘ’、ｙ’の加算結果である長さｎ＋１のビット列ｂが与えられたときに、元のビット列ｘ，ｙのｉ番目のビットｘ［ｉ］、ｙ［ｉ］を推測できることを示している。具体的にはｘ，ｙの加算時のキャリービットの列を表現する長さｎ＋１のビット列ｃ１とｘ’、ｙ’の加算時のキャリービットの列を表現する長さｎ＋１のビット列ｃ２の要素の値も表１より求められる。表１の構成法を説明する。ビット列ａ，ｂ，ｃ１，ｃ２，ｘ，ｙの各ｉ番目の要素をａ［ｉ］，ｂ［ｉ］，ｃ１［ｉ］，ｃ２［ｉ］，ｘ［ｉ］，ｙ［ｉ］で表現するとする。このとき、ａ，ｃ１の各要素は加算の定義より以下の式１を満たす。
【数１】
2014048548.tif 000004
また、ｂ，ｃ２の各要素は加算の定義より以下の式２を満たす。
【数２】
2014048548.tif 000005
このとき、式１よりビット列要素ａ［ｉ］，ｃ１［ｉ＋１］よりｘ［ｉ］，ｙ［ｉ］の要素がどのような値のペアだったか、また、１つ前のキャリービットｃ１［ｉ］の値を表２のようにあいまいに予測することができる。また、同様に式２より式１よりビット列要素ｂ［ｎ＋１−ｉ］，ｃ２［ｎ＋１−ｉ］よりｘ［ｉ］，ｙ［ｉ］の要素がどのような値のペアだったか、また、次のキャリービットｃ２［ｎ＋２−ｉ］の値を表３のようにあいまいに予測することができる。だが、各々の予測ではキャリーの値を一意に予測できていない。しかし、表２と表３を結合し、表１を構成することで、キャリービットｃ１［ｉ］、ｃ２［ｎ＋２−ｉ］の値を一意に決定でき、（ｘ［ｉ］，ｙ［ｉ］）の値もより正確に予測できる。
【表２】
2014048548.tif 000006
【表３】
2014048548.tif 000007
【００９３】
論理演算適用部１１６では表１を用いるため、ＮＥＷ＿（Ｘ＋Ｙ）の配列の大きさをｎとする。また、ａ［ｎ］＝ｃ１［ｎ＋１］＝ＮＥＷ＿（Ｘ＋Ｙ）［ｎ］とし、ａ［ｎ−１］＝ＮＥＷ＿（Ｘ＋Ｙ）［ｎ−１］、ａ［ｎ−２］＝ＮＥＷ＿（Ｘ＋Ｙ）［ｎ−２］、…、ａ［１］＝ＮＥＷ＿（Ｘ＋Ｙ）［１］とする。また、ｂ［ｎ］＝ＮＥＷ＿（Ｘ＋Ｙ）’［ｎ]とし、ｂ［ｎ−１］＝ＮＥＷ＿（Ｘ＋Ｙ）’［ｎ−１］、ｂ［ｎ−２］＝ＮＥＷ＿（Ｘ＋Ｙ）’［ｎ−２］、…、ｂ［１］＝ＮＥＷ＿（Ｘ＋Ｙ）’［１］、ｃ２［１］＝０とする。このとき、記憶部に格納している表１を用いてａ［ｎ−１］、ｃ１［ｎ−１］、ｂ［１］、ｃ２［１］からＸ［ｎ−１］、Ｙ［ｎ−１］、ｃ１［ｎ−１］、ｎ２［２］を予測し、ａ［ｎ−２］、ｃ１［ｎ−２］、ｂ［２］、ｃ２［２］からＸ［ｎ−２］、Ｙ［ｎ−２］、ｃ１［ｎ−３］、ｃ２［３］と予測を続けていき、Ｘ［１］、Ｙ［１］まで予測する。Ｘの予測により得られたビット列を二値変数配列ＩＸに格納し、Ｙの予測により得られたビット列を二値変数配列ＩＹに格納する（ステップＳ９０３、ステップＳ９０４、ステップＳ９０５）。
【００９４】
正順二値変数配列Ｘ，Ｙの撹乱後の状態の予測である二値変数配列ＩＸとＩＹはあいまいである。ここでのあいまいの意味は双方のｉ番目の要素が両方とも１、または、両方とも０の場合は、正確に断定するが、どちらかのビットが１で、他方が０の場合には１と０の組合せであったが、どちらが１であるか断定しないということである。つまり、あるｉにおいて、ＩＸ［ｉ］≠ＩＹ［ｉ］であった場合には、ＸとＹどちらが０でどちらが１であったか特定することはできない。なぜなら、どちらの場合にも加算結果は同じ値になるからである。よって、ＩＸ［ｉ］≠ＩＹ［ｉ］を満たす１≦ｉ≦ｎ−１なる識別子ｉの個数がｍだったとき同じ加算結果を導くＸ、Ｙの組合せは２ｍ個存在する。本当のＸ，Ｙの組合せは２ｍ個の中の１個である。よって、本発明ではＸ，Ｙをあいまいに予測することが可能となる。
【００９５】
次に、論理演算処理部１１６は１≦ｉ≦ｎ−１を満たす各整数ｉに対して、ＩＸ［ｉ］とＹ［ｉ］の論理和、ＩＸ［ｉ］とＩＹ［ｉ］の論理積、ＩＸ［ｉ］とＩＹ［ｉ］の排他的論理和を計算する。さらに、それぞれの計算結果を二値変数配列Ｃ＿ＯＲ、Ｃ＿ＡＮＤ、Ｃ＿ＥＸＯＲのｉ番目の要素として格納する（ステップＳ９０６）。
【００９６】
次に制御部１１０は図１１のフローに戻り、演算結果記録処理のステップＳ１２００に進む。演算結果記録処理は演算結果記録部１１７が実行する。
【００９７】
演算結果記録部１１７はループ回数記録変数Ｔを用いて、Ｔ回の演算結果としてＲ［Ｔ］.Ｃ＿ＡＮＤ＝Ｃ＿ＡＮＤ、Ｒ［Ｔ］.Ｃ＿ＯＲ＝Ｃ＿ＯＲ、Ｒ［Ｔ］.Ｃ＿ＥＸＯＲ＝Ｃ＿ＥＸＯＲとして記録部１４０に記録する。
【００９８】
記録が実行されたら、制御部１１０は図１１のフローに戻り、変数Ｔの値が記憶部に格納されている最終ループ回数と等しいか判定し、等しくなければ、ステップＳ１４００のループ回数加算処理に進む（ステップＳ１３００のＮｏ）。そうでなければ、ステップＳ１５００の計算結果算出処理に進む（ステップＳ１３００のＹｅｓ）。
【００９９】
ループ回数加算処理はループ回数管理部１１１が実行する。ループ回数管理部１１１は変数Ｔを１だけ加算し、自己の機関が秘匿計算（ビット推測）処理担当の場合には記憶部１４０に記録されているＴ回目に正順二値変数配列Ｘとして用いるべき配列名を読み出し、その配列の内容を記憶からさらに読み出し、新たに正順二値変数配列Ｘの内容とし、Ｘに対応するよう逆順二値変数配列Ｙ’の内容を更新する（ステップＳ１４０４）。
【０１００】
ステップＳ１４０４の終了後、制御部１１０は図１１のフローに戻りステップＳ３００の第１暗号データ生成処理を実行する。
【０１０１】
ループ回数管理部１１１は自己機関が秘匿計算（暗号加算）処理担当である場合にはＴ回目に正順二値変数配列Ｙとして用いるべき値、結果ビット列Ａ、ビット列対応表ＴＡ、結果ビット列Ｂ、ビット列対応表ＴＢとして用いるべき、ビット列、対応表を記憶部より読み出す（ステップＳ１４０５）。
【０１０２】
ステップＳ１４０５の終了後、制御部１１０は図１１のフローに戻り、ステップＳ２００の第１暗号データ生成依頼処理を実行する。
【０１０３】
制御部１１０はステップＳ１３００でループ回数Ｔが記憶部１４０に格納されている最終ループ回数と等しいなら、ステップＳ１５００の計算結果算出処理に進む、計算結果算出処理は計算結果算出処理部１１８が実行する。
【０１０４】
計算結果算出処理部１１８は記憶部１４０に格納してある最終結果とする情報の格納場所ｎａｍｅとそのビット数ＢＩＴを読み出し、ＢＩＴビットの二値変数配列ＦＩに情報を格納する（ステップＳ１５０１、Ｓ１５０２）。
【０１０５】
次に相手機関に最終結果格納の二値変数配列Ｆ＿１またはＦ＿２の内容を送信する（ステップＳ１５０３）。
【０１０６】
相手機関より最終結果が送信されるのを待ち（Ｓ１５０４ステップのＮｏ）、送信されたらステップＳ１５０５へ進む（Ｓ１５０４ステップのＹｅｓ）。
【０１０７】
計算結果算出処理部１１８は記憶部１４０に格納されている最終関数名ｆ＿ＦＩＮＡＬを読み出し、両機関の最終結果Ｆ＿１、Ｆ＿２を入力としてｆ＿ＦＩＮＡＬ（Ｆ＿１、Ｆ＿２）を計算し、変数ＦＩＮＡＬに格納する（ステップＳ１５０５）。
【０１０８】
ステップＳ１５０５の終了後、インターフェース部１６０を通じて最終結果ＦＩＮＡＬを外部の装置へ出力する（ステップＳ１５０６）。
【０１０９】
外部装置への出力が完了したら、制御部１１０は図１１のフローに戻り秘匿計算処理を終了する。
【０１１０】
本実施の形態によれば、多量の二値変数入力をもつ関数でも、正順二値変数配列ＸやＹに情報を記憶し、二値変数配列全体に対して暗号化を行うため、高速に暗号処理を実行でき、かつ、一度の加算で多量の二値変数入力ペア間の論理演算結果を得ることが可能となる。
【０１１１】
また、途中で得られる演算結果から元の二値変数を予測することは表１を用いてあいまいにしかできない。したがって、秘匿計算（ビット推測）処理担当の機関が暗号値計算途中の平文を推測することは困難となり、挿入した追加ビットの値や入れ替えの関係を推測することは困難である。
【０１１２】
一方、暗号加算処理担当の機関では、相手機関より途中で情報を受け取るのは暗号値の合計を算出する前の合計値のみである。しかし、合計値の暗号値にも、撹乱定数αが入っているため、合計前の元の値を推測することは困難である。
【０１１３】
さらに、得られた計算結果を秘匿したまま、再度処理の入力として用いることが可能な繰り返し構造が採用されていることにより、本発明は記憶部に格納可能であるような幅広い論理関数を秘匿したまま計算することが可能な汎用性を備える。
【０１１４】
このように、本実施の形態の方法は従来方法の弱点を克服した極めて汎用性が高く、かつ、高速な方法となっている。よって、本実施の形態の方法を使用すれば、多量の秘匿入力が存在しても、高速に複雑な論理関数値を安全に秘匿計算することが可能になる。
【０１１５】
（実施の形態２）
本実施の形態の秘匿計算システム１は図２１に示すように、複数のデータ処理装置１００を備えるシステムである。複数のデータ処理装置１００はデータ記憶装置３００を介してデータを送受信することで、複数の機関での秘匿計算を可能にする。以下、秘匿計算システム１について図面を参照しながら説明する。まず、図２１を参照して秘匿計算システム１の構成について説明する。
【０１１６】
秘匿計算システム１は図２１に示すように、複数のデータ処理装置とデータ処理装置１００それぞれと通信線２００で接続されたデータ記憶装置３００とを備える秘匿計算システムである。なお、以下の説明ではデータ処理装置１００が、機関Ｐ１、機関Ｐ２、機関Ｐ３それぞれに設置され、データをデータ記憶装置３００に格納するまえ暗号化するための各機関の公開鍵と復号するための公開鍵に対応する秘密鍵が用意されているものとして説明する。以下、秘匿計算システム１の構成について説明する。データ処理装置１００の記憶部１４０には実施の形態１で格納していた内容に加え、データ記憶部３００にデータを格納する前に特定の機関だけがデータを復号できるよう他の各機関の公開鍵と自己の公開鍵に対応する秘密鍵を格納している。なお、データ処理装置１００の構成と記憶部１４０以外の機能については、実施の形態１と同様であるので説明を省略する。
【０１１７】
データ記憶装置３００の内部の記憶装置には、機関ごとに専用のフォルダが用意されている。３つのデータ処理装置１００はそれぞれの機関に用意された上記のフォルダより暗号データ等を読み出し、他の機関の専用フォルダに暗号データ等を格納する。また、各フォルダ内部には、データ処理履歴を記録するための履歴ファイルが格納されている。各データ処理装置１００は暗号データを処理するたびに履歴ファイルに所定のデータを記録する。
【０１１８】
次に、秘匿計算システム１で実行される「秘匿計算処理」について説明する。制御部１１０は操作部１４０から「秘匿計算（ビット推測）開始通知」、または、「秘匿計算（暗号加算）開始通知」を受信すると、図２２に示す「秘匿計算（ビット推測）処理」または、「秘匿計算（暗号加算）処理」を開始する。ここで、図２２の機関Ｐ２のように「秘匿計算（ビット推測）開始通知」と「秘匿計算（暗号加算）開始通知」の両方を受信する場合がある。この場合、利用する記憶部１４０の領域を異なるものとして、並行して「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」をデータ処理装置１００の制御部１１０は実行する。以下、図２２、図２３、図２４、図２５、図２６、図２７、図２８のフローチャートを参照して「秘匿計算（ビット推測）処理」と「秘匿計算（暗号加算）処理」での実施の形態１の処理と異なる点について説明する。
【０１１９】
ループ回数管理部１１０はステップＳ１００にて記憶部１４０に記されている変数群の値を初期化するために用いるべき値の格納場所を読み出し、変数群の値を設定する。このとき、値の格納場所がデータ記憶装置３００である場合には自己のフォルダに他の機関のデータが格納されているか一定期間ごとにデータ記憶装置３００をモニタする。自己の専用フォルダにデータが格納されていたら、通信部１３０を介してデータを受信する。データ記憶装置３００に格納されていたデータは自身の公開鍵で暗号化されているものもあるため記憶部１４０に格納されている自身の秘密鍵にて復号してから復号値を用いる。
【０１２０】
第１暗号データ生成依頼部１１９はステップＳ１０２にて生成した切断点数Ｎ、切断点リストＬＩＳＴ＿ＲＮ，および、暗号ペアリストＬＩＳＴ＿ＬＱを通信部１３０を介して、データ記憶装置３００に送信する。データ記憶装置３００は切断点Ｎ、切断点リストＬＩＳＴ_ＲＮを受信して、指定のフォルダにデータを格納する。
【０１２１】
第１暗号データ生成部１１２は、ステップ２０１で他の機関のデータが格納されているか確認するため一定期間ごとにデータ記憶装置３００をモニタする。自己のフォルダに切断点Ｎ、切断点リストＬＩＳＴ_ＲＮが格納されていたら、ステップ２０２に進む。
【０１２２】
第１暗号データ生成依頼部１１９はステップＳ１０６にて生成した暗号ペアリストＬＩＳＴ＿ＬＱを通信部１３０を介して、データ記憶装置３００に送信する。データ記憶装置３００は暗号ペアリストＬＩＳＴ＿ＬＱを受信して、指定のフォルダにデータを格納する。
【０１２３】
第１暗号データ生成部１１２は、ステップＳ２０３では他の機関の暗号ペアリストＬＩＳＴ_ＬＱが格納されているか確認するため一定期間ごとにデータ記憶装置３００をモニタする。自己のフォルダに暗号ペアリストＬＩＳＴ＿ＬＱが格納されていたら、ステップＳ２０４に進む。
【０１２４】
第１加算暗号データ取得部１１３はステップＳ３０１にて暗号データリストＬＩＳＴ＿ＥＤを通信部１３０を介して、データ記憶部３００に送信する。
【０１２５】
第１加算暗号データ生成部１２１はステップＳ４０１にて他の機関の暗号データリストＬＩＳＴ＿ＥＤが格納されているか一定期間ごとにデータ記憶装置３００をモニタする。自己の専用フォルダにデータが格納されていたらステップＳ４０２に進む。さらに、ステップＳ４０４では、暗号正順加算データである第１加算暗号データＦ＿ＳＵＭを通信部１３０を介して、データ記憶装置３００に送信する。データ記憶装置３００は暗号データＦ＿ＳＵＭを受信して、指定のフォルダにデータを格納する。
【０１２６】
ステップＳ６００の第２暗号データ生成依頼処理、ステップＳ７００の第２暗号データ生成処理、ステップＳ８００の第２加算暗号データ生成処理、ステップＳ９００の第２加算暗号データ取得処理はそれぞれステップＳ２００、ステップＳ３００、ステップＳ４００、ステップＳ５００の第１暗号データ生成依頼処理、第１暗号データ生成処理、第１加算暗号データ生成処理、第１加算暗号データ取得処理と同様であるので説明を省略する。
【０１２７】
演算結果適用部１１６は、ステップＳ１２００にて演算結果Ｃ＿Ｆ１を記憶部１４０に記録されている格納位置に格納する。ここで、データ記憶装置３００の他の機関のフォルダが指定されている場合には、その機関の公開鍵で演算結果Ｃ＿Ｆ１を暗号化し暗号データＥ（Ｃ＿Ｆ１）を作成し、通信部１３０を介して、データ記憶装置３００に送信する。データ記憶装置３００は暗号データを受信して、指定のフォルダにデータを格納する。
【０１２８】
撹乱データ記録部１２３は、ステップＳ１１００にて撹乱データに演算を適用して得た演算結果Ｃ＿Ｆ２を記憶部１４０に記録されている格納位置に格納する。ここで、データ記憶装置３００の他の機関のフォルダが指定されている場合には、その機関の公開鍵で演算結果Ｃ＿Ｆ２を暗号化し暗号データＥ（Ｃ＿Ｆ２）を作成し、通信部１３０を介して、データ記憶装置３００に送信する。データ記憶装置３００は暗号データを受信して、指定のフォルダにデータを格納する。
【０１２９】
ループ回数管理部１１１はステップＳ１４００での変数群の値の更新において記録部１４０に記録されている更新に利用するよう指定されている格納場所がデータ記憶装置３００のフォルダである場合には、一定期間ごとにデータ記憶装置３００をモニタする。自己の専用フォルダにデータが格納されていたら、暗号データを通信部１３０を介して受信し、記憶部１４０に格納している自己の秘密鍵を用いて復号し、変数群に復号値を設定する。
【０１３０】
計算結果算出部１１８はステップＳ１５０２での結果Ｆ＿１の値を記録部１４０に記録されている格納場所に格納するため、データ記憶装置３００へ送信する。また、外の機関の値Ｆ＿２として利用するよう指定されている格納場所がデータ記憶装置３００のフォルダである場合には、一定期間ごとにデータ記憶装置３００をモニタする。自己の専用フォルダにデータが格納されていたら、暗号データを通信部１３０を介して受信し、記憶部１４０に格納している自己の秘密鍵を用いて復号し、変数Ｆ＿２に復号値を設定する。
【０１３１】
本実施の形態によれば、データ記憶装置３００を介してデータを送受信することで３つの機関での秘匿計算が可能になる。
【０１３２】
また、データ記憶装置３００に保存されているデータは暗号化されたデータであるので、暗号化に使用されている公開鍵に対応する秘密鍵を保持している機関以外の機関がデータを取得しても、そこから有意な情報を得ることができない。そのため、各機関は安心してこれらのデータをデータ記憶装置３００に保存しておくことができる。
【０１３３】
なお、秘匿計算システム１は４台以上のデータ処理装置１００を有していてもよい。４台以上のデータ処理装置１００がデータ記憶装置３００にアクセスできるように構成し、実施の形態２と同様の処理を実行することで、４つ以上の機関での秘匿計算が可能になる。
【０１３４】
また、データ処理装置１００はデータ記憶装置３００を介さずに、例えば、インターネットや専用回線等を使用して、複数のデータ処理装置１００間で直接データを送受信してもよい。
【符号の説明】
【０１３５】
１      秘匿計算システム
１００  データ処理装置
１１０  制御部
１１１  ループ回数管理部
１１２  第１暗号データ生成部
１１３  第１加算暗号データ取得部
１１４  第２暗号データ生成部
１１５  第２加算暗号データ取得部
１１６  論理演算適用部
１１７  演算結果記録部
１１８  計算結果算出部
１１９  第１暗号データ生成依頼部
１２０  第１加算暗号データ生成部
１２１  第２暗号データ生成依頼部
１２２  第２加算暗号データ生成部
１２３  撹乱データ記録部
１３０  通信部
１４０  記憶部
１５０  操作部
１６０  インターフェース部
２００  通信線
３００  データ記憶装置
【図１】
2014048548.tif 000008
【図２】
2014048548.tif 000009
【図３】
2014048548.tif 000010
【図４】
2014048548.tif 000011
【図５】
2014048548.tif 000012
【図６】
2014048548.tif 000013
【図７】
2014048548.tif 000014
【図８】
2014048548.tif 000015
【図９】
2014048548.tif 000016
【図１０】
2014048548.tif 000017
【図１１】
2014048548.tif 000018
【図１２】
2014048548.tif 000019
【図１３】
2014048548.tif 000020
【図１４】
2014048548.tif 000021
【図１５】
2014048548.tif 000022
【図１６】
2014048548.tif 000023
【図１７】
2014048548.tif 000024
【図１８】
2014048548.tif 000025
【図１９】
2014048548.tif 000026
【図２０】
2014048548.tif 000027
【図２１】
2014048548.tif 000028
【図２２】
2014048548.tif 000029
【図２３】
2014048548.tif 000030
【図２４】
2014048548.tif 000031
【図２５】
2014048548.tif 000032
【図２６】
2014048548.tif 000033
【図２７】
2014048548.tif 000034
【図２８】
2014048548.tif 000035