(57)【特許請求の範囲】
【請求項１】
複数個の秘密計算装置を有し、
前記秘密計算装置のそれぞれは、
秘密計算の対象となる対象データの秘密分散値を格納する記憶部と、
前記秘密計算を要求するクエリまたは前記クエリの秘密分散値が入力される入力部と、
前記対象データの秘密分散値の整合性検証および前記クエリまたは前記クエリの秘密分散値の整合性検証を行う整合性検証部と、
整合性検証に合格した前記対象データの秘密分散値を用い、整合性検証に合格した前記クエリまたは前記クエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得る秘密計算部と、
前記演算結果の秘密分散値を出力する出力部と、
を有し、
前記複数個の秘密計算装置のうち整合性検証に合格した前記対象データの秘密分散値を格納するものを要素とする第１集合と、前記複数個の秘密計算装置のうち整合性検証に合格した前記クエリまたは前記クエリの秘密分散値が入力されたものを要素とする第２集合と、の共通部分に属する前記秘密計算装置の前記出力部が前記演算結果の秘密分散値を出力し、
前記第１集合および前記第２集合の少なくとも一方が、前記複数個の秘密計算装置を要素とする全体集合の真部分集合であり、
前記共通部分に属する前記秘密計算装置は、前記共通部分の補集合に属する秘密計算装置の前記対象データの秘密分散値および前記クエリまたは前記クエリの秘密分散値の少なくとも一方を復元する復元部を有する、秘密計算システム。
【請求項２】
請求項１の秘密計算システムであって、
前記共通部分に属する前記秘密計算装置の前記出力部は、前記共通部分の要素数が前記演算結果を復元するために必要な秘密分散値の個数以上である場合に、前記演算結果の秘密分散値を出力する、秘密計算システム。
【請求項３】
複数個の秘密計算装置を有し、
前記秘密計算装置のそれぞれは、
秘密計算の対象となる対象データの秘密分散値を格納する記憶部と、
前記秘密計算を要求するクエリまたは前記クエリの秘密分散値が入力される入力部と、
前記対象データの秘密分散値の整合性検証および前記クエリまたは前記クエリの秘密分散値の整合性検証を行う整合性検証部と、
整合性検証に合格した前記対象データの秘密分散値を用い、整合性検証に合格した前記クエリまたは前記クエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得る秘密計算部と、
前記演算結果の秘密分散値を出力する出力部と、
を有し、
前記複数個の秘密計算装置のうち整合性検証に合格した前記対象データの秘密分散値を格納するものを要素とする第１集合と、前記複数個の秘密計算装置のうち整合性検証に合格した前記クエリまたは前記クエリの秘密分散値が入力されたものを要素とする第２集合と、の共通部分に属する前記秘密計算装置の前記出力部が前記演算結果の秘密分散値を出力し、
前記第１集合および前記第２集合の少なくとも一方が、前記複数個の秘密計算装置を要素とする全体集合の真部分集合であり、
前記整合性検証部が、前記全体集合の第１部分集合での前記対象データの秘密分散値の整合性検証が不合格であった場合、前記第１部分集合の真部分集合を前記第１部分集合として前記対象データの秘密分散値の整合性検証を行う第１再帰処理を行う、および／または、前記全体集合の第２部分集合での前記クエリまたは前記クエリの秘密分散値の整合性検証が不合格であった場合、前記第２部分集合の真部分集合を前記第２部分集合として前記クエリまたは前記クエリの秘密分散値の整合性検証を行う第２再帰処理を行う、秘密計算システム。
【請求項４】
複数個の秘密計算装置を有し、
前記秘密計算装置のそれぞれは、
秘密計算の対象となる対象データの秘密分散値を格納する記憶部と、
前記秘密計算を要求するクエリまたは前記クエリの秘密分散値が入力される入力部と、
前記対象データの秘密分散値の整合性検証および前記クエリまたは前記クエリの秘密分散値の整合性検証を行う整合性検証部と、
整合性検証に合格した前記対象データの秘密分散値を用い、整合性検証に合格した前記クエリまたは前記クエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得る秘密計算部と、
前記演算結果の秘密分散値を出力する出力部と、
を有し、
前記複数個の秘密計算装置のうち整合性検証に合格した前記対象データの秘密分散値を格納するものを要素とする第１集合と、前記複数個の秘密計算装置のうち整合性検証に合格した前記クエリまたは前記クエリの秘密分散値が入力されたものを要素とする第２集合と、の共通部分に属する前記秘密計算装置の前記出力部が前記演算結果の秘密分散値を出力し、
前記第１集合および前記第２集合の少なくとも一方が、前記複数個の秘密計算装置を要素とする全体集合の真部分集合であり、
前記整合性検証部が、前記全体集合の第３部分集合での前記対象データの秘密分散値の整合性検証が不合格であった場合、前記第３部分集合の真部分集合と前記第３部分集合の補集合の部分集合との和集合を前記第３部分集合として前記対象データの秘密分散値の整合性検証を行う第３再帰処理を行う、および／または、前記全体集合の第４部分集合での前記クエリまたは前記クエリの秘密分散値の整合性検証が不合格であった場合、前記第４部分集合の真部分集合と前記第４部分集合の補集合の部分集合との和集合を前記第４部分集合として前記クエリまたは前記クエリの秘密分散値の整合性検証を行う第４再帰処理を行う、秘密計算システム。
【請求項５】
請求項１から４の何れかの秘密計算システムであって、
前記整合性検証部は、前記対象データの秘密分散値および前記クエリまたは前記クエリの秘密分散値の整合性検証をまとめて行う、秘密計算システム。
【請求項６】
請求項５の秘密計算システムであって、
前記整合性検証部は、前記対象データの秘密分散値および前記クエリまたは前記クエリの秘密分散値を含む情報を撹乱させた情報の整合性検証を行う、秘密計算システム。
【請求項７】
複数個の秘密計算装置を有し、
前記秘密計算装置のそれぞれは、
秘密計算の対象となる対象データの秘密分散値を格納する記憶部と、
前記秘密計算を要求するクエリまたは前記クエリの秘密分散値が入力される入力部と、
前記対象データの秘密分散値の整合性検証および前記クエリまたは前記クエリの秘密分散値の整合性検証を行う整合性検証部と、
整合性検証に合格した前記対象データの秘密分散値を用い、整合性検証に合格した前記クエリまたは前記クエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得る秘密計算部と、
前記演算結果の秘密分散値を出力する出力部と、
を有し、
前記整合性検証部は、
前記複数個の秘密計算装置を要素とする全体集合の部分集合で得られた複数個の任意値の合成値ｓを得る合成部と、
前記合成値ｓの関数値を係数とし、前記対象データの秘密分散値および前記クエリまたは前記クエリの秘密分散値の少なくとも一方を含む値の線形結合値［ｃ］ｉを得る線形結合部と、
前記線形結合値［ｃ］ｉに応じた秘密分散値［ｄ］ｉを他の秘密計算装置に配送して整合性検証を行う検証部と、を含む、秘密計算システム。
【請求項８】
請求項７の秘密計算システムであって、
前記整合性検証部は、
乱数秘密分散値［Ｒ］ｉを得る撹乱値設定部と、
前記乱数秘密分散値［Ｒ］ｉで前記線形結合値［ｃ］ｉを撹乱させた前記秘密分散値［ｄ］ｉを得る撹乱部と、を含む、秘密計算システム。
【請求項９】
請求項１から８の何れかの前記秘密計算システムが有する秘密計算装置。
【請求項１０】
請求項９の秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術を応用した情報セキュリティ技術に関し、特に、秘密計算技術に関する。
【背景技術】
【０００２】
秘密分散値の改ざんを検知する技術として、検証可能秘密分散法（VSS: Verifiable secret sharing）がある（例えば、非特許文献１）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】岡本龍明，山本博資，「現代暗号−シリーズ／情報科学の数学」，産業図書株式会社，１９９８年６月３０日，第２刷，ｐｐ．２１７−２１９．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、秘密計算装置に秘密計算の対象となる対象データの秘密分散値が格納され、秘密計算装置がこれらの対象データの秘密分散値を用い、入力されたクエリまたはクエリの秘密分散値に応じた秘密計算を行う場合に、改ざんによる不正を防止する方法は知られていない。
【０００５】
本発明の課題は、秘密計算装置に秘密計算の対象となる対象データの秘密分散値が格納され、秘密計算装置がこれらの対象データの秘密分散値を用い、入力されたクエリまたはクエリの秘密分散値に応じた秘密計算を行う場合に、改ざんによる不正を防止することである。
【課題を解決するための手段】
【０００６】
秘密計算装置には、秘密計算の対象となる対象データの秘密分散値が格納され、秘密計算を要求するクエリまたはクエリの秘密分散値が入力される。秘密計算装置は、対象データの秘密分散値の整合性検証およびクエリまたはクエリの秘密分散値の整合性検証を行い、整合性検証に合格した対象データの秘密分散値を用い、整合性検証に合格したクエリまたはクエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得、演算結果の秘密分散値を出力する。
【発明の効果】
【０００７】
これにより、秘密計算装置に秘密計算の対象となる対象データの秘密分散値が格納され、秘密計算装置がこれらの対象データの秘密分散値を用い、入力されたクエリまたはクエリの秘密分散値に応じた秘密計算を行う場合に、改ざんによる不正を防止できる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態の秘密計算システムの機能構成を例示したブロック図である。
【図２】図２Ａは、実施形態の秘密計算装置の機能構成を例示したブロック図である。図２Ｂは、実施形態の整合性検証部の機能構成を例示したブロック図である。
【図３】図３は、実施形態の分析装置の機能構成を例示したブロック図である。
【図４】図４は、実施形態の処理を例示したシーケンス図である。
【図５】図５は、実施形態の整合性検証処理を例示したフロー図である。
【図６】図６Ａおよび図６Ｂは、実施形態の処理を例示したフロー図である。
【図７】図７Ａおよび図７Ｂは、実施形態の処理を例示するための概念図である。
【図８】図８Ａおよび図８Ｂは、実施形態の処理を例示するための概念図である。
【図９】図９Ａおよび図９Ｂは、実施形態の処理を例示するための概念図である。
【図１０】図１０Ａおよび図１０Ｂは、実施形態の処理を例示するための概念図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［概要］
まず、実施形態の概要を説明する。
実施形態の秘密計算システムは、秘密計算の対象となる対象データの秘密分散値を出力する登録装置、複数個の秘密計算装置、およびクエリまたはクエリの秘密分散値を用いて秘密計算を要求する分析装置を有する。秘密計算装置のそれぞれには、登録装置から送られた対象データの秘密分散値が格納され、さらに分析装置から送られたクエリまたはクエリの秘密分散値が入力される。秘密計算装置は、対象データの秘密分散値の整合性検証およびクエリまたはクエリの秘密分散値の整合性検証を行い、整合性検証に合格した対象データの秘密分散値を用い、整合性検証に合格したクエリまたはクエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得、演算結果の秘密分散値を出力する。これにより、登録装置、登録装置から秘密計算装置までの間、または秘密計算装置で対象データの秘密分散値が改ざんされたり、分析装置、または分析装置から秘密計算装置までの間でクエリまたはクエリの秘密分散値が改ざんされたりしても、その改ざんによって秘密計算装置から不正な結果が出力されることを防止できる。
【００１０】
何れかの整合性検証が不合格であった場合、すべての対象データの秘密分散値の秘密計算装置への格納、および／または、すべてのクエリまたはクエリの秘密分散値の秘密計算装置への入力をやり直してもよい。あるいは、対象データの秘密分散値およびクエリまたはクエリの秘密分散値の両方の整合性検証が合格であった一部の秘密計算装置のみが演算結果の秘密分散値を出力してもよい。後者の場合、複数個の秘密計算装置のうち整合性検証に合格した対象データの秘密分散値を格納するものを要素とする「第１集合」と、複数個の秘密計算装置のうち整合性検証に合格したクエリまたはクエリの秘密分散値が入力されたものを要素とする「第２集合」と、の「共通部分」に属する秘密計算装置が演算結果の秘密分散値を出力する。「第１集合」および「第２集合」の少なくとも一方は、複数個の秘密計算装置を要素とする「全体集合」の真部分集合であってもよい。これにより、整合性検証が不合格であった場合の処理量を削減できる。
【００１１】
「第１集合」および「第２集合」の少なくとも一方が「全体集合」の真部分集合である場合、「共通部分」も「全体集合」の真部分集合である。秘密計算の内容によっては「全体集合」の真部分集合の秘密計算装置のみで秘密計算を実行できる場合（ケース１）もあれば、「全体集合」の秘密計算装置が協力しなければ秘密計算を実行できない場合（ケース２）もある。「ケース１」の場合には「共通部分」のみで秘密計算を行うことができるが、「ケース２」の場合には「共通部分」のみで秘密計算を行うことができず、整合性検証が不合格であった秘密計算装置と協力して秘密計算を行ったのでは、不正な結果が得られる可能性がある。そのため、「共通部分」に属する秘密計算装置が、「共通部分」の「補集合」（「全体集合」から「共通部分」を取り除いた集合）に属する秘密計算装置の対象データの秘密分散値およびクエリまたはクエリの秘密分散値の少なくとも一方を復元してもよい。秘密計算の内容に応じ、対象データの秘密分散値およびクエリまたはクエリの秘密分散値が復元されてもよいし、対象データの秘密分散値およびクエリまたはクエリの秘密分散値の何れかのみが復元されてもよい。これにより、「ケース２」の場合であっても「共通部分」のみで秘密計算を行うことができる。
【００１２】
「共通部分」の要素数が演算結果を復元するために必要な秘密分散値の個数以上である場合に、「共通部分」に属する秘密計算装置が演算結果の秘密分散値を出力してもよい。これにより、演算結果を復元するために必要な個数の「演算結果の秘密分散値」が得られないにもかかわらず、演算結果の秘密分散値の計算および通信が行われることと防止できる。「共通部分」に属する秘密計算装置が「共通部分」の要素数が演算結果を復元するために必要な秘密分散値の個数未満である場合には、対象データの秘密分散値の格納、および／または、クエリまたはクエリの秘密分散値の入力をやり直すか、エラー終了してもよい。
【００１３】
複数の秘密計算装置で行った整合性検証が不合格であった場合、それらの何れかの秘密計算装置の「データ」（対象データの秘密分散値、または、クエリもしくはクエリの秘密分散値）に改ざんがあったことは分かるが、どの「データ」が改ざんされたかは分からない。そのため、「全体集合」の「第１部分集合」での対象データの秘密分散値の整合性検証が不合格であった場合、「第１部分集合」の真部分集合を新たな「第１部分集合」として対象データの秘密分散値の整合性検証を行う再帰処理を行ってもよい。例えば、「第１部分集合」を複数の真部分集合に分割し、各真部分集合をそれぞれ新たな「第１部分集合」としてもよいし、「第１部分集合」の何れかの真部分集合のみを新たな「第１部分集合」としてもよい。同様に、「全体集合」の「第２部分集合」でのクエリまたはクエリの秘密分散値の整合性検証が不合格であった場合、「第２部分集合」の真部分集合を新たな「第２部分集合」としてクエリまたはクエリの秘密分散値の整合性検証を行う再帰処理を行ってもよい。例えば、「第２部分集合」を複数の真部分集合に分割し、各真部分集合をそれぞれ新たな「第２部分集合」としてもよいし、「第２部分集合」の何れかの真部分集合のみを新たな「第２部分集合」としてもよい。これにより、上述の「第１集合」および／または「第２集合」を効率的に特定できる。
【００１４】
「全体集合」の「第３部分集合」での対象データの秘密分散値の整合性検証が不合格であった場合、「第３部分集合」の真部分集合と「第３部分集合」の補集合（「全体集合」から「第３部分集合」を取り除いた集合）の部分集合との和集合を新たな「第３部分集合」として対象データの秘密分散値の整合性検証を行う再帰処理を行ってもよい。同様に、「全体集合」の「第４部分集合」でのクエリまたはクエリの秘密分散値の整合性検証が不合格であった場合、「第４部分集合」の真部分集合と「第４部分集合」の補集合（「全体集合」から「第４部分集合」を取り除いた集合）の部分集合との和集合を新たな「第４部分集合」としてクエリまたはクエリの秘密分散値の整合性検証を行う再帰処理を行ってもよい。これによっても、上述の「第１集合」および／または「第２集合」を効率的に特定できる。特に、「第３部分集合」で整合性検証が不合格であるが、新たな「第３部分集合」で整合性検証が合格であった場合、更新前の「第３部分集合」には含まれるが新たな「第３部分集合」には含まれない秘密計算装置の「データ」に改ざんがあることが分かる。そのため、この秘密計算装置を除いた集合で新たに整合性検証を行い、それが合格であれば、その集合を「第１集合」および／または「第２集合」としてもよい。これにより、「第１集合」および／または「第２集合」の要素数を増加させ、「共通部分」に属する秘密計算装置の数を増加させることができる。
【００１５】
秘密計算装置が、対象データの秘密分散値およびクエリまたはクエリの秘密分散値の整合性検証をまとめて行ってもよい。例えば、対象データの秘密分散値およびクエリまたはクエリの秘密分散値を含む情報を対象として整合性検証が行われてもよい。これにより、整合性検証の処理を効率化できる。この場合、対象データの秘密分散値およびクエリまたはクエリの秘密分散値を含む情報を撹乱させた情報の整合性検証を行ってもよい。これにより、整合性検証の過程で、対象データおよびクエリの少なくとも一方が漏洩することを防止できる。
【００１６】
整合性検証方式に限定はない。例えば、非特許文献１に開示された方式が用いられてもよいし、その他の方式が用いられてもよい。例えば、秘密計算装置が「全体集合」の部分集合（全体集合またはその真部分集合）で得られた複数個の任意値の合成値ｓを得、合成値ｓの関数値を係数とし、対象データの秘密分散値およびクエリまたはクエリの秘密分散値の少なくとも一方を含む値の線形結合値［ｃ］ｉを得、線形結合値［ｃ］ｉに応じた秘密分散値［ｄ］ｉを他の秘密計算装置に配送して整合性検証を行ってもよい。これにより、複数のデータの整合性検証をまとめて実行できるため、処理を効率化できる。この際、秘密計算装置が乱数秘密分散値［Ｒ］ｉを得、乱数秘密分散値［Ｒ］ｉで線形結合値［ｃ］ｉを撹乱させた秘密分散値［ｄ］ｉを得てもよい。これにより、整合性検証の過程で、対象データおよびクエリの少なくとも一方が漏洩することを防止できる。
【００１７】
以降、図面を参照しつつ、各実施形態を説明する。
［第１実施形態］
第１実施形態を説明する。
【００１８】
＜構成＞
図１に例示するように、本形態の秘密計算システム１は、登録装置１１、Ｎ個の秘密計算装置１２−１，…，１２−（Ｎ−１）、および分析装置１３を有する。ただし、Ｎは２以上の整数であり、例えば３以上の整数である。登録装置１１と秘密計算装置１２−１，…，１２−（Ｎ−１）とは、インターネット等の安全ではないネットワークを通じて通信可能に構成されている。同様に、秘密計算装置１２−１，…，１２−（Ｎ−１）と分析装置１３とは、安全ではないネットワークを通じて通信可能に構成されている。なお、説明の便宜上、登録装置１１および分析装置１３がそれぞれ１個存在する例を示すが、これらの少なくとも一方が複数個存在していてもよい。
【００１９】
図２Ａに例示するように、本形態の秘密計算装置１２−ｎ（ただし、ｎ＝０，…，（Ｎ−１））は、例えば、制御部１２０−ｎ、入力部１２１−ｎ、記憶部１２２−ｎ、整合性検証部１２３−ｎ、秘密計算部１２４−ｎ、および出力部１２５−ｎを有する。図２Ｂに例示するように、整合性検証部１２３−ｎは、例えば、任意値設定部１２３１−ｎ、合成部１２３２−ｎ、線形結合部１２３３−ｎ、および検証部１２３６−ｎを有する。整合性検証部１２３−ｎは、さらに撹乱値設定部１２３４−ｎおよび撹乱部１２３５−ｎを有していてもよい。秘密計算装置１２−ｎは、制御部１２０−ｎの制御のもとで各処理を実行する。秘密計算装置１２−ｎの各部で得られたデータは、図示していない一時メモリに格納され、必要に応じて読み出されて各処理に利用される。図３に例示するように、分析装置１３は、制御部１３０、分析依頼部１３１、出力部１３２、入力部１３３、記憶部１３４、および改ざん検知復元部１３５を有する。各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００２０】
＜処理＞
本形態の処理は「登録処理」「保管処理」「分析処理」からなる。以下、図４を用いて本形態の処理を説明する。
【００２１】
「登録処理」
登録処理では、登録装置１１が、秘密計算の対象となる対象データｂ０，…，ｂＭ−１のそれぞれを秘密分散し、Ｎ個ずつの秘密分散値［ｂ０］０，…，［ｂ０］Ｎ−１，…，［ｂＭ−１］０，…，［ｂＭ−１］Ｎ−１を生成する。ただし、Ｍは１以上の整数であり、対象データｂｍ（ただし、ｍ＝０，…，Ｍ−１）のＮ個の秘密分散値を［ｂｍ］０，…，［ｂｍ］Ｎ−１と表記する。本形態の秘密分散は（Ｋ，Ｎ）しきい値秘密分散方式に則って行われる。（Ｋ，Ｎ）しきい値秘密分散方式では、Ｋ個以上の秘密分散値を集めれば元データ（平文）を完全に復元できるが、Ｋ−１以下の秘密分散値からは元データの情報が全く得られない。（Ｋ，Ｎ）しきい値秘密分散方式の具体例は、Shamirの秘密分散方式（例えば、参考文献１「A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.」等参照）、またはその変形方式である。対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎ（ただし、ｎ＝０，…，Ｎ−１）は、それぞれ秘密計算装置１２−ｎに送られる。対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎは、秘密計算装置１２−ｎ（図２Ａ）の入力部１２１−ｎに入力され、記憶部１２２−ｎに格納される（ステップＳ１１）。
【００２２】
対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎに格納されると、Ｎ個の秘密計算装置１２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部１２３−ｎが互いに通信し、対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎの整合性検証を行う。整合性検証は非特許文献１その他の公知方式によって行われてもよいし、後述する方式によって行われてもよい。これにより、登録装置１１、または登録装置１１から秘密計算装置１２−ｎまでの間で行われた対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎの改ざんが検知される。この整合性検証が合格であった場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎに保持される。一方、この整合性検証が不合格であった場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎから削除され、処理をステップＳ１１に戻すか、エラー終了させる（ステップＳ１２）。
【００２３】
「保管処理」
保管処理では、各秘密計算装置１２−ｎが対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎを記憶部１２２−ｎに保持する。この間、定期的または所定の契機で、Ｎ個の秘密計算装置１２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部１２３−ｎが互いに通信し、対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎの整合性検証を行ってもよい。これにより、秘密計算装置１２−ｎで行われた対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎの改ざんが検知される。この整合性検証が合格であった場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎに保持される。一方、この整合性検証が不合格であった場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎから削除され、処理をステップＳ１１に戻すか、エラー終了させる（ステップＳ１３）。
【００２４】
「分析処理」
分析処理では、まず分析装置１３の分析依頼部１３１が、秘密計算を要求するクエリまたはクエリの秘密分散値を生成して出力する。クエリは秘密計算を要求する演算内容を表してもよいし、演算対象のデータを表してもよい。本形態では、分析依頼部１３１が出力するクエリまたはクエリの秘密分散値を［ｑ０］ｎ，…，［ｑＪ−１］ｎ（ただし、ｎ＝０，…，Ｎ−１）と表現する。ただし、Ｊは１以上の整数である。［ｑｊ］ｎ（ただし、ｊ＝０，…，Ｊ−１）がクエリそのもの（元データ）である場合、［ｑｊ］０＝…＝［ｑｊ］Ｎ−１である。［ｑｊ］ｎ（ただし、ｊ＝０，…，Ｊ−１）がクエリの秘密分散値である場合、［ｑｊ］０，…，［ｑｊ］Ｎ−１は、クエリｑｊのＮ個の秘密分散値である。出力部１３２は、クエリまたはクエリの秘密分散値［ｑ０］ｎ，…，［ｑＪ−１］ｎ（ただし、ｎ＝０，…，Ｎ−１）を出力し、これらはそれぞれ秘密計算装置１２−ｎに送られる。［ｑ０］ｎ，…，［ｑＪ−１］ｎは、秘密計算装置１２−ｎ（図２Ａ）の入力部１２１−ｎに入力され、記憶部１２２−ｎに格納される（ステップＳ１４）。
【００２５】
クエリまたはクエリの秘密分散値［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎに格納されると、Ｎ個の秘密計算装置１２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部１２３−ｎが互いに通信し、クエリまたはクエリの秘密分散値［ｑ０］ｎ，…，［ｑＪ−１］ｎの整合性検証を行う。ここで、［ｑｊ］ｎがクエリそのものであったとしても、［ｑｊ］ｎを秘密分散値とみなして整合性検証を行うことができる。これにより、分析装置１３、または分析装置１３から秘密計算装置１２−ｎまでの間で行われた［ｑ０］ｎ，…，［ｑＪ−１］ｎの改ざんが検知される。この整合性検証が合格である場合、［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎに保持される。一方、この整合性検証が不合格である場合、［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎから削除され、処理をステップＳ１４に戻すか、エラー終了させる（ステップＳ１５）。
【００２６】
［ｑ０］ｎ，…，［ｑＪ−１］ｎの整合性検証が合格の場合、秘密計算装置１２−ｎの秘密計算部１２４−ｎは、記憶部１２２−ｎから、整合性検証に合格した［ｂ０］ｎ，…，［ｂＭ−１］ｎおよび［ｑ０］ｎ，…，［ｑＪ−１］ｎを読み込む。秘密計算部１２４−ｎは、整合性検証に合格した［ｂ０］ｎ，…，［ｂＭ−１］ｎを用い、整合性検証に合格した［ｑ０］ｎ，…，［ｑＪ−１］ｎに応じた秘密計算を行って演算結果の秘密分散値［ｒ０］ｎ，…，［ｒＷ−１］ｎを得る。ただし、Ｗは１以上の整数である。本形態では、改ざん検知付秘密計算（例えば、参考文献２「五十嵐大, 千田浩司, 濱田浩気, 菊池亮, “非常に高効率なn≧2k-1 malicious モデル上秘密分散ベースマルチパーティ計算の構成法”， In SCIS2013, 2013.」等参照）によって秘密計算を行って演算結果の秘密分散値［ｒ０］ｎ，…，［ｒＷ−１］ｎを得る。この計算過程でのＫ−１個以下の秘密計算装置１２−ｎによる改ざんは、ここで検知できる。改ざんが検知された場合、この秘密計算を再び実行させるか、処理をエラー終了させる。改ざんが検知されなかった場合、演算結果の秘密分散値［ｒ０］ｎ，…，［ｒＷ−１］ｎが出力部１２５−ｎに送られる（ステップＳ１６）。出力部１２５−ｎ（ただし、ｎ＝０，…，Ｎ−１）は、演算結果の秘密分散値［ｒ０］ｎ，…，［ｒＷ−１］ｎを出力し、これらは分析装置１３に送られる（ステップＳ１７）。
【００２７】
演算結果の秘密分散値［ｒ０］ｎ，…，［ｒＷ−１］ｎは、分析装置１３（図３）の入力部１３３に入力され、記憶部１３４に格納される。演算結果の秘密分散値［ｒ０］ｎ，…，［ｒＷ−１］ｎ（ただし、ｎ＝０，…，Ｎ−１）は改ざん検知復元部１３５に送られる。改ざん検知復元部１３５はこれらの改ざん検知復元を行い（例えば、参考文献２参照）、演算結果ｒ０，…，ｒＷ−１を復元して出力する。秘密計算装置１２−ｎまたは秘密計算装置１２−ｎから分析装置１３までの間での改ざんはここで検知される。改ざんが検知された場合、このステップＳ１６以降の処理を再び実行させるか、処理をエラー終了させる。改ざんが検知されなかった場合、演算結果ｒ０，…，ｒＷ−１が出力される（ステップＳ１８）。
【００２８】
＜整合性検証の具体例＞
図５を用いて整合性検証の具体例を示す。以下では、Ｉ個の秘密計算装置１２−０〜１２−（Ｉ−１）が協力し、［ａ０］ｉ，…，［ａＹ−１］ｉ（ただし、ｉ＝０，…，Ｉ−１）の整合性検証を行う場合に一般化して説明する。ただし、Ｙは１以上の整数であり、ＩはＫよりも大きく、Ｎ以下の整数であり（Ｎ≧Ｉ＞Ｋ。例えば、Ｎ≧Ｉ≧２）、｛０，…，Ｉ−１｝⊆｛０，…，Ｎ−１｝を満たす。［ａ０］ｉ，…，［ａＹ−１］ｉの例は、対象データの秘密分散値［ｂ０］ｉ，…，［ｂＭ−１］ｉ、クエリまたはクエリの秘密分散値［ｑ０］ｉ，…，［ｑＪ−１］ｉである。
【００２９】
まず、秘密計算装置１２−ｉ（図２Ｂ）の整合性検証部１２３−ｉの任意値設定部１２３１−ｉが、任意値ｓｉを選択する。任意値ｓｉの例は、擬似乱数、乱数、または定数である。任意値ｓｉは記憶部１２２−ｉに格納されるとともに、出力部１２５−ｉに送られる（ステップＳ１２０１）。任意値ｓｉは出力部１２５−ｉから出力され、他の秘密計算装置１２−ｉ’（ただし、ｉ’∈｛０，…，Ｉ−１｝かつｉ’≠ｉ）に配送される（ステップＳ１２０２）。他の秘密計算装置１２−ｉ’から配送された任意値ｓｉ’は入力部１２１−ｉに入力され、記憶部１２２−ｉに格納される（ステップＳ１２０３）。合成部１２３２−ｉは、記憶部１２２−ｉから任意値ｓ０，…，ｓＩ−１を読み込み、任意値ｓ０，…，ｓＩ−１の合成値ｓ：＝ｇ（ｓ０，…，ｓＩ−１）を得る。ただし、「α：＝β」は、αをβと定義することを意味する。ｇ（・）は（・）の関数を表す。任意値ｓ０，…，ｓＩ−１に対して合成値ｓが一義的に定まるのであれば、どのようなｇ（・）が用いられてもよい。例えば、ｓ：＝ｓ０＋…＋ｓＩ−１などの任意値ｓ０，…，ｓＩ−１の線形結合を合成値ｓとしてもよいし、ｓ：＝ｓ０×…×ｓＩ−１などの任意値ｓ０，…，ｓＩ−１の積を合成値ｓとしてもよい。合成値ｓは記憶部１２２−ｉに格納される（ステップＳ１２０４）。
【００３０】
線形結合部１２３３−ｉは、記憶部１２２−ｉから合成値ｓおよび［ａ０］ｉ，…，［ａＹ−１］ｉを読み込み、合成値ｓの関数値を係数ｚｙ（ただし、ｙ＝０，…，Ｙ−１）とし、［ａ０］ｉ，…，［ａＹ−１］ｉ（ただし、ｉ＝０，…，Ｉ−１）の線形結合値［ｃ］ｉ：＝ｚ０［ａ０］ｉ＋…＋ｚＹ−１［ａＹ−１］ｉを得る。係数ｚｙは合成値ｓとｙとによって定まる値ｚｙ：＝ｈ（ｓ，ｙ）であってもよいし、合成値ｓのみに対して定まる値ｚｙ：＝ｈ（ｓ）であってもよい。ただし、ｈ（・）は（・）の関数を表す。例えば、ｚｙ：＝ｓｙ＋１であってもよいし、ｚｙ：＝ｓ２ｙ＋１であってもよいし、ｚｙ：＝ｓであってもよい。線形結合値［ｃ］ｉは記憶部１２２−ｉに格納される（ステップＳ１２０５）。
【００３１】
検証部１２３６−ｉは、記憶部１２２−ｉから読み込んだ線形結合値［ｃ］ｉに応じた秘密分散値［ｄ］ｉを出力する。例えば、線形結合値［ｃ］ｉをそのまま秘密分散値［ｄ］ｉとしてもよいし、［ｃ］ｉの関数値を秘密分散値［ｄ］ｉとしてもよい。整合性検証部１２３−ｉが撹乱値設定部１２３４−ｉおよび撹乱部１２３５−ｉを含む場合、撹乱値設定部１２３４−ｉが乱数秘密分散値［Ｒ］ｉを得、撹乱部１２３５−ｉが乱数秘密分散値［Ｒ］ｉおよび線形結合値［ｃ］ｉを入力とし、乱数秘密分散値［Ｒ］ｉで線形結合値［ｃ］ｉを撹乱させた秘密分散値［ｄ］ｉを得てもよい。例えば、撹乱値設定部１２３４−ｉが、生成した擬似乱数または乱数を乱数秘密分散値［Ｒ］ｉとし、秘密計算によって［ｄ］ｉ：＝［ｃ−Ｒ］ｉを得てもよい。ただし、［ｃ−Ｒ］ｉは（Ｋ，Ｎ）しきい値秘密分散方式に則ったｃ−Ｒの秘密分散値である。秘密分散値［ｄ］ｉは記憶部１２２−ｉに格納されるとともに、出力部１２５−ｉに送られる（ステップＳ１２０６）。
【００３２】
秘密分散値［ｄ］ｉは出力部１２５−ｉから出力され、他の秘密計算装置１２−ｉ’（ただし、ｉ’∈｛０，…，Ｉ−１｝かつｉ’≠ｉ）に配送される（ステップＳ１２０７）。他の秘密計算装置１２−ｉ’から配送された秘密分散値［ｄ］ｉ’は入力部１２１−ｉに入力され、記憶部１２２−ｉに格納される（ステップＳ１２０８）。
【００３３】
検証部１２３６−ｎは、記憶部１２２−ｉからＫ個の秘密分散値［ｄ］ｆ（０），…，［ｄ］ｆ（Ｋ−１）を読み込み、ラグランジュ（Lagrange）補間によって他のＩ−Ｋ個の秘密分散値Ｄｆ（Ｋ）：＝［ｄ］ｆ（Ｋ），…，Ｄｆ（Ｉ−１）：＝［ｄ］ｆ（Ｉ−１）を復元し、記憶部１２２−ｉに格納する。なお、｛ｆ（０），…，ｆ（Ｉ−１）｝＝｛０，…，Ｉ−１｝を満たし、例えば、ｆ（ｉ）＝ｉである（ステップＳ１２０９）。
【００３４】
検証部１２３６−ｎは、記憶部１２２−ｉから、ステップＳ１２０８で入力された［ｄ］ｆ（Ｋ），…，［ｄ］ｆ（Ｎ−１）と、ステップＳ１２０９で復元されたＤｆ（Ｋ），…，Ｄｆ（Ｎ−１）とを読み込み、これらを比較する。ここで、すべてのｐ＝Ｋ，…，Ｉ−１についてＤｆ（ｐ）＝［ｄ］ｆ（ｐ）であるならば、検証部１２３６−ｎは、［ａ０］ｉ，…，［ａＹ−１］ｉの整合性検証が合格である旨の結果を出力する（ステップＳ１２１１）。一方、何れかのｐについてＤｆ（ｐ）≠［ｄ］ｆ（ｐ）であるならば、検証部１２３６−ｎは、［ａ０］ｉ，…，［ａＹ−１］ｉの整合性検証が不合格である旨の結果を出力する（ステップＳ１２１２）。
【００３５】
この整合性検証の具体例では、［ａ０］ｉ，…，［ａＹ−１］ｉの整合性検証をまとめて実行できるため効率がよい。また、乱数秘密分散値［Ｒ］ｉで線形結合値［ｃ］ｉを撹乱させた秘密分散値［ｄ］ｉを用いる場合には、ステップＳ１２０９で［ａ０］ｉ，…，［ａＹ−１］ｉの復元値の情報が漏洩することを防止できる。
【００３６】
［第２実施形態］
第２実施形態では、前述の「第１集合」と「第２集合」との「共通部分」に属する秘密計算装置が演算結果の秘密分散値を出力する。「第１集合」および「第２集合」の少なくとも一方は、複数個の秘密計算装置を要素とする「全体集合」の真部分集合であってもよい。以下では、既に説明した事項との相違点を中心に説明し、説明済みの事項についてはそれと同じ参照番号を流用して説明を簡略化する。
【００３７】
＜構成＞
図１に例示するように、本形態の秘密計算システム２は、登録装置１１、Ｎ個の秘密計算装置２２−１，…，２２−（Ｎ−１）、および分析装置１３を有する。図２Ａに例示するように、本形態の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，（Ｎ−１））は、例えば、制御部１２０−ｎ、入力部１２１−ｎ、記憶部１２２−ｎ、整合性検証部２２３−ｎ、秘密計算部２２４−ｎ、および出力部１２５−ｎを有する。
【００３８】
＜処理＞
本形態の処理も「登録処理」「保管処理」「分析処理」からなる。以下、図４を用いて本形態の処理を説明する。
【００３９】
「登録処理」
まず、登録装置１１と秘密計算装置２２−ｎとが、第１実施形態で説明したステップＳ１１の処理を実行する。次に、第１実施形態のステップＳ１２で説明したように、Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部２２３−ｎが互いに通信し、対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎの整合性検証を行う。ただし、本形態では、この整合性検証が不合格であっても、記憶部１２２−ｎから［ｂ０］ｎ，…，［ｂＭ−１］ｎが削除されない。代わりに、Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）からなる集合の真部分集合Ｓ１が選択され、真部分集合Ｓ１に属するＮＳ１個（ただし、ＮＳ１＞Ｋ）の秘密計算装置２２−ｖ（η）（ただし、η＝０，…，ＮＳ１−１）の整合性検証部２２３−ｖ（η）が互いに通信し、対象データの秘密分散値［ｂ０］ｖ（η），…，［ｂＭ−１］ｖ（η）の整合性検証を行う。なお、｛ｖ（０），…，ｖ（ＮＳ１−１）｝＝｛０，…，ＮＳ１−１｝を満たし、例えば、ｖ（η）＝ηである。この真部分集合Ｓ１での整合性検証方法にも限定はない。例えば、非特許文献１の方法で整合性検証が行われてもよいし、Ｉ：＝ＮＳ１とし、ｉ：＝ｖ（η）とし、（［ａ０］ｉ，…，［ａＹ−１］ｉ）：＝（［ｂ０］ｖ（η），…，［ｂＭ−１］ｖ（η））とし、前述のステップＳ１２０１〜Ｓ１２１２の方法で整合性検証が行われてもよい。真部分集合Ｓ１に属するＮＳ１個の秘密計算装置２２−ｖ（η）（ただし、η＝０，…，ＮＳ１−１）での整合性検証が不合格である場合、別の真部分集合Ｓ１が選択され、選択された真部分集合Ｓ１での整合性検証が実行される。真部分集合Ｓ１は、予め定められた基準に従って選択される。真部分集合Ｓ１の真部分集合が新たな真部分集合Ｓ１とされてもよいし、真部分集合Ｓ１の補集合が新たな真部分集合Ｓ１とされてもよいし、真部分集合Ｓ１の真部分集合と補集合との和集合が新たな真部分集合Ｓ１とされてもよい。この具体例は後述する。Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）からなる全体集合Ｕでの整合性検証が合格であった場合、その旨の情報が記憶部１２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）に格納される。真部分集合Ｓ１での整合性検証が合格であった場合、その旨の情報が記憶部１２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）に格納される。全体集合Ｕまたは真部分集合Ｓ１での整合性検証が合格であった場合、対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎに保持される。一方、真部分集合Ｓ１を所定回数更新しても整合性検証が合格にならなかった場合、所定の真部分集合Ｓ１について整合性検証を行ってすべて不合格であった場合、または合格となった真部分集合Ｓ１の要素数がＫ未満であった場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎから削除され、処理をステップＳ１１に戻すか、エラー終了させる（ステップＳ２２）。
【００４０】
「保管処理」
保管処理でも、定期的または所定の契機で、ステップＳ２２と同じ整合性検証が行われてもよい。Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）からなる全体集合Ｕでの整合性検証が合格であった場合、その旨の情報が記憶部１２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）に格納される。真部分集合Ｓ１での整合性検証が合格であった場合、その旨の情報が記憶部１２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）に格納される。全体集合Ｕまたは真部分集合Ｓ１での整合性検証が合格であった場合、対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎに保持される。一方、真部分集合Ｓ１を所定回数更新しても整合性検証が合格にならなかった場合、所定の真部分集合Ｓ１について整合性検証を行ってすべて不合格であった場合、または合格となった真部分集合Ｓ１の要素数がＫ未満であった場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎが記憶部１２２−ｎから削除され、処理をステップＳ１１に戻すか、エラー終了させる（ステップＳ２３）。
【００４１】
「分析処理」
まず、分析装置１３と秘密計算装置２２−ｎとが、第１実施形態で説明したステップＳ１４の処理を実行する。次に、第１実施形態のステップＳ１５で説明したように、Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部２２３−ｎが互いに通信し、クエリまたはクエリの秘密分散値を［ｑ０］ｎ，…，［ｑＪ−１］ｎの整合性検証を行う。ただし、本形態では、この整合性検証が不合格であっても、記憶部１２２−ｎから［ｑ０］ｎ，…，［ｑＪ−１］ｎが削除されない。代わりに、Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）からなる集合の真部分集合Ｓ２が選択され、真部分集合Ｓ２に属するＮＳ２個（ただし、ＮＳ２＞Ｋ）の秘密計算装置２２−ｕ（ι）（ただし、ι＝０，…，ＮＳ２−１）が互いに通信し、［ｑ０］ｕ（ι），…，［ｑＪ−１］ｕ（ι）の整合性検証を行う。なお、｛ｕ（０），…，ｕ（ＮＳ２−１）｝＝｛０，…，ＮＳ２−１｝を満たし、例えば、ｕ（ι）＝ιである。この真部分集合Ｓ１での整合性検証方法にも限定はない。例えば、非特許文献１の方法で整合性検証が行われてもよいし、Ｉ＝ＮＳ２とし、ｉ＝ｕ（ι）とし、（［ａ０］ｉ，…，［ａＹ−１］ｉ）＝（［ｑ０］ｕ（ι），…，［ｑＪ−１］ｕ（ι））とし、前述のステップＳ１２０１〜Ｓ１２１２の方法で整合性検証が行われてもよい。真部分集合Ｓ２に属するＮＳ２個の秘密計算装置２２−ｕ（ι）（ただし、ι＝０，…，ＮＳ２−１）での整合性検証が不合格である場合、別の真部分集合Ｓ２が選択され、選択された真部分集合Ｓ２での整合性検証が実行される。真部分集合Ｓ２は、予め定められた基準に従って選択される。真部分集合Ｓ２の真部分集合が新たな真部分集合Ｓ２とされてもよいし、真部分集合Ｓ２の補集合が新たな真部分集合Ｓ２とされてもよいし、真部分集合Ｓ２の真部分集合と補集合との和集合が新たな真部分集合Ｓ２とされてもよい。Ｎ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）からなる全体集合Ｕでの整合性検証が合格であった場合、その旨の情報が記憶部１２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）に格納される。真部分集合Ｓ２での整合性検証が合格であった場合、その旨の情報が記憶部１２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）に格納される。全体集合Ｕまたは真部分集合Ｓ２での整合性検証が合格であった場合、クエリまたはクエリの秘密分散値を［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎに保持される。一方、真部分集合Ｓ２を所定回数更新しても整合性検証が合格にならなかった場合、所定の真部分集合Ｓ２について整合性検証を行ってすべて不合格であった場合、または、合格となった真部分集合Ｓ２の要素数がＫ未満であった場合、［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎから削除され、処理をステップＳ１４に戻すか、エラー終了させる（ステップＳ２５）。
【００４２】
全体集合Ｕまたは真部分集合Ｓ２での整合性検証が合格であった場合、Ｎ個の秘密計算装置２２−０，…，２２−（Ｎ−１）のうち、ステップＳ２２，２３での整合性検証に合格した対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎを格納する秘密計算装置を要素とする「第１集合（ＵまたはＳ１）」と、ステップＳ２５での整合性検証に合格したクエリまたはクエリの秘密分散値［ｑ０］ｎ，…，［ｑＪ−１］ｎが入力された秘密計算装置を要素とする「第２集合（ＵまたはＳ２）」と、の「共通部分（Ｓ１２）」に属する秘密計算装置２２−κ（ただし、κ∈｛０，…，Ｎ−１｝）が秘密計算を行う。例えば、ステップＳ２２，２３，２５で全体集合Ｕでの整合性検証が合格であった場合、Ｕ＝Ｓ１２となり、Ｎ個の秘密計算装置２２−０，…，２２−（Ｎ−１）が第１実施形態で説明したステップＳ１６と同一の処理を行う（図７Ａ）。例えば、ステップＳ２２，２３で真部分集合Ｓ１での整合性検証が合格であり、ステップＳ２５で真部分集合Ｓ２での整合性検証が合格であったのであれば、真部分集合Ｓ１と真部分集合Ｓ２との「共通部分（Ｓ１２）」に属する秘密計算装置２２−κ（ただし、κ∈｛０，…，Ｎ−１｝）の秘密計算部２２４−κが、整合性検証に合格した［ｂ０］κ，…，［ｂＭ−１］κを用い、整合性検証に合格した［ｑ０］κ，…，［ｑＪ−１］κに応じた秘密計算を行って演算結果の秘密分散値［ｒ０］κ，…，［ｒＷ−１］κを得る。本形態でも、改ざん検知付秘密計算（例えば、参考文献２）が用いられる（ステップＳ２６）。その後、分析装置１３と秘密計算装置２２−ｎとが、第１実施形態で説明したステップＳ１７およびＳ１８と同じ処理を実行する。ただし、「共通部分（Ｓ１２）」の要素数が演算結果を復元するために必要な秘密分散値の個数Ｋ以上である場合のみにステップＳ２６，Ｓ１７，Ｓ１８の処理が実行され、そうでない場合に処理をエラー終了させてもよい。
【００４３】
＜整合性検証対象となる真部分集合の更新例＞
ステップＳ２２，Ｓ２３，Ｓ２５で説明した整合性検証対象となる真部分集合の更新例を説明する。更新例１では、「全体集合（Ｕ）」の「第１部分集合（ＵまたはＳ１）」での対象データの秘密分散値［ｂ０］ｖ（η），…，［ｂＭ−１］ｖ（η）の整合性検証が不合格であった場合、「第１部分集合（ＵまたはＳ１）」の真部分集合を新たな「第１部分集合（Ｓ１）」として対象データの秘密分散値［ｂ０］ｖ（η），…，［ｂＭ−１］ｖ（η）の整合性検証を行う再帰処理を行う。また、「全体集合（Ｕ）」の「第２部分集合（ＵまたはＳ２）」でのクエリまたはクエリの秘密分散値［ｑ０］ｕ（ι），…，［ｑＪ−１］ｕ（ι）の整合性検証が不合格であった場合、「第２部分集合（ＵまたはＳ２）」の真部分集合を新たな「第２部分集合（Ｓ２）」としてクエリまたはクエリの秘密分散値の整合性検証を行う再帰処理を行う。更新例２では、「全体集合（Ｕ）」の「第３部分集合（ＵまたはＳ１）」での対象データの秘密分散値［ｂ０］ｖ（η），…，［ｂＭ−１］ｖ（η）の整合性検証が不合格であった場合、「第３部分集合（ＵまたはＳ１）」の真部分集合と「第３部分集合（ＵまたはＳ１）」の補集合の部分集合との和集合を新たな「第３部分集合Ｓ１」として対象データの秘密分散値［ｂ０］ｖ（η），…，［ｂＭ−１］ｖ（η）の整合性検証を行う再帰処理を行う。「全体集合（Ｕ）」の「第４部分集合（ＵまたはＳ２）」でのクエリまたはクエリの秘密分散値［ｑ０］ｕ（ι），…，［ｑＪ−１］ｕ（ι）の整合性検証が不合格であった場合、「第４部分集合（ＵまたはＳ２）」の真部分集合と「第４部分集合（ＵまたはＳ２）」の補集合の部分集合との和集合を新たな「第４部分集合Ｓ２」としてクエリまたはクエリの秘密分散値［ｑ０］ｕ（ι），…，［ｑＪ−１］ｕ（ι）の整合性検証を行う再帰処理を行う。以下では、Ｓ１およびＳ２を部分集合Ｓに一般化して説明する。
【００４４】
≪更新例１≫
図６Ａに例示するように、更新例１では、まずＮ個の秘密計算装置２２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部２２３−ｎが、Ｎ個の秘密計算装置２２−ｎの全体集合Ｕを集合系ＳＥＴの元として設定する（ＳＥＴ：＝｛Ｕ｝）（ステップＳ２２０１）。集合系ＳＥＴの元である部分集合Ｓ∈ＳＥＴ（初期値は全体集合Ｕ）に属するＮＳ個（ただし、ＮＳ＞Ｋ）個の秘密計算装置２２−ｅ（ν）（ただし、ν＝０，…，ＮＳ−１）の整合性検証部２２３−ｅ（ν）が互いに通信し、データ（対象データの秘密分散値、またはクエリもしくはクエリの秘密分散値）の整合性検証を行う。なお、｛ｅ（０），…，ｅ（ＮＳ−１）｝＝｛０，…，ＮＳ−１｝を満たし、例えば、ｅ（ν）＝νである（ステップＳ２２０２）。ここで、整合性検証に合格する部分集合Ｓが存在しないならば（ステップＳ２２０３）、整合性検証部２２３−ｅ（ν）は整合性検証の継続条件を満たすかを判定する（ステップＳ２２０４）。継続条件の例は、「部分集合Ｓの更新回数が所定数以下である」「所定の部分集合の整合性検証が終了していない」などである。ここで、整合性検証の継続条件を満たさない場合、整合性検証部２２３−ｅ（ν）は処理をエラー終了させる（ステップＳ２２０８）。一方、整合性検証の継続条件を満たす場合、整合性検証部２２３−ｅ（ν）は、部分集合Ｓをその真部分集合に置換して集合系ＳＥＴを更新する。例えば、図８Ａの例では、ＳＥＴ：＝｛ＳＳ１−１｝のときに、部分集合Ｓ＝ＳＳ１−１がその真部分集合ＳＳ１−２およびＳＳ１−３に置換され、ＳＥＴ：＝｛ＳＳ１−２，ＳＳ１−３｝に更新される。図８Ｂの例では、ＳＥＴ：＝｛ＳＳ１−２，ＳＳ１−３｝のときに、ＳＳ１−２がその真部分集合ＳＳ１−４およびＳＳ１−５に置換され、ＳＳ１−３がその真部分集合ＳＳ１−６およびＳＳ１−７に置換される。集合系ＳＥＴの更新後、ステップＳ２２０２に戻る（ステップＳ２２０５）。一方、ステップＳ２２０２で整合性検証に合格した部分集合Ｓが存在したならば（ステップＳ２２０３）、整合性検証部２２３−ｅ（ν）は整合性検証に合格した部分集合Ｓの要素数｜Ｓ｜＝ＮＳがＫ以上かを判定する（ステップＳ２２０６）。整合性検証に合格した何れかの部分集合Ｓの要素数｜Ｓ｜がＫ以上であれば、整合性検証部２２３−ｅ（ν）はその部分集合Ｓを表す情報を出力する（ステップＳ２２０７）。そうでなければ、整合性検証部２２３−ｅ（ν）は処理をエラー終了させる（ステップＳ２２０８）。
【００４５】
≪更新例２≫
図６Ｂに例示するように、更新例２では、図６Ａの処理のステップＳ２２０５がステップＳ２２１５に置換される。ステップＳ２２１５では、整合性検証部２２３−ｅ（ν）が、部分集合ＳをＳの真部分集合Ａ⊂Ｓと、Ｓの補集合ＣＳの真部分集合Ｂ⊂ＣＳと、の和集合Ａ＋Ｂに置換する。例えば、和集合Ａ＋Ｂは部分集合Ｓをシフトさせた集合である。例えば、図９Ａおよび図９Ｂの例では、ＳＥＴ：＝｛ＳＳ１−２，ＳＳ１−３｝のときに、ＳＳ１−２が和集合ＳＳ１−４に置換され、ＳＳ１−３が和集合ＳＳ１−５に置換される。図９Ａおよび図９Ｂの例では、ＳＥＴ：＝｛ＳＳ１−４，ＳＳ１−５，ＳＳ１−６，ＳＳ１−７｝のときに、ＳＳ１−４が和集合ＳＳ１−８に置換され、ＳＳ１−５が和集合ＳＳ１−９に置換され、ＳＳ１−６が和集合ＳＳ１−１０に置換され、ＳＳ１−７が和集合ＳＳ１−１１に置換される。
【００４６】
［第３実施形態］
第２実施形態では、「第１集合」と「第２集合」との「共通部分」に属する秘密計算装置が、「共通部分」の補集合に属する秘密計算装置の対象データの秘密分散値およびクエリまたはクエリの秘密分散値の少なくとも一方を復元し、秘密計算を行う。
【００４７】
＜構成＞
図１に例示するように、本形態の秘密計算システム３は、登録装置１１、Ｎ個の秘密計算装置３２−１，…，３２−（Ｎ−１）、および分析装置１３を有する。図２Ａに例示するように、本形態の秘密計算装置３２−ｎ（ただし、ｎ＝０，…，（Ｎ−１））は、例えば、制御部１２０−ｎ、入力部１２１−ｎ、記憶部１２２−ｎ、整合性検証部２２３−ｎ、秘密計算部３２４−ｎ、出力部１２５−ｎ、および分散値復元部３２６−ｎ、を有する。
【００４８】
＜処理＞
本形態の処理も「登録処理」「保管処理」「分析処理」からなる。以下、図４を用いて本形態の処理を説明する。
【００４９】
「登録処理」
登録装置１１と秘密計算装置３２−ｎとが、第１実施形態で説明したステップＳ１１の処理を実行する。次に、秘密計算装置３２−ｎが、第２実施形態で説明したステップＳ２２の処理を実行する。
【００５０】
「保管処理」
秘密計算装置３２−ｎが、第２実施形態で説明したステップＳ２３の処理を実行する。
【００５１】
「分析処理」
まず、分析装置１３と秘密計算装置２２−ｎとが、第１実施形態で説明したステップＳ１４の処理を実行する。次に、秘密計算装置３２−ｎが、第２実施形態で説明したステップＳ２５の処理を実行する。
【００５２】
全体集合Ｕまたは真部分集合Ｓ２での整合性検証が合格であった場合、前述の「第１集合（ＵまたはＳ１）」と「第２集合（ＵまたはＳ２）」との「共通部分（Ｓ１２）」に属する秘密計算装置３２−κ（ただし、κ∈｛０，…，Ｎ−１｝）の分散値復元部３２６−κが互いに通信を行い、「共通部分（Ｓ１２）」の補集合に属する秘密計算装置３２−θ（ただし、θ∈｛０，…，Ｎ−１｝かつθ≠κ）の対象データの秘密分散値［ｂ０］θ，…，［ｂＭ−１］θおよびクエリまたはクエリの秘密分散値［ｑ０］θ，…，［ｑＪ−１］θを復元する。この復元は、例えばラグランジュ補間によって行われる。例えば、「共通部分（Ｓ１２）」に属する信頼できる特定の秘密計算装置３２−κ’の分散値復元部３２６−κ’に対し、「共通部分（Ｓ１２）」に属するその他の秘密計算装置３２−κの分散値復元部３２６−κが［ｂ０］κ，…，［ｂＭ−１］κおよび［ｑ０］κ，…，［ｑＪ−１］κを送る。秘密計算装置３２−κ’は、これらを用い、ラグランジュ補間によって、［ｂ０］θ，…，［ｂＭ−１］θおよび［ｑ０］θ，…，［ｑＪ−１］θを復元し、記憶部１２２−κ’に格納する（ステップＳ３５）。
【００５３】
「共通部分（Ｓ１２）」に属する秘密計算装置３２−κ（ただし、κ∈｛０，…，Ｎ−１｝）は、整合性検証に合格した［ｂ０］κ，…，［ｂＭ−１］κを用い、整合性検証に合格した［ｑ０］κ，…，［ｑＪ−１］κに応じた秘密計算を行って演算結果の秘密分散値［ｒ０］κ，…，［ｒＷ−１］κを得る。復元された［ｂ０］θ，…，［ｂＭ−１］θおよび［ｑ０］θ，…，［ｑＪ−１］θを保持する秘密計算装置３２−κは、さらに、復元された［ｂ０］θ，…，［ｂＭ−１］θを用い、復元された［ｑ０］κ，…，［ｑＪ−１］κに応じた秘密計算を行って演算結果の秘密分散値［ｒ０］θ，…，［ｒＷ−１］θを得る。本形態でも、改ざん検知付秘密計算（例えば、参考文献２）が用いられる（ステップＳ２６）。その後、分析装置１３と秘密計算装置３２−ｎとが、第１実施形態で説明したステップＳ１７およびＳ１８と同じ処理を実行する。ただし、［ｒ０］θ，…，［ｒＷ−１］θは、分析装置１３に送られてもよいし、送られなくてもよい。「共通部分（Ｓ１２）」の要素数が演算結果を復元するために必要な秘密分散値の個数Ｋ以上である場合のみにステップＳ３５，Ｓ３６，Ｓ１７，Ｓ１８の処理が実行され、そうでない場合に処理をエラー終了させてもよい。
【００５４】
［第４実施形態］
第４実施形態では、対象データの秘密分散値およびクエリまたはクエリの秘密分散値の整合性検証をまとめて行う。
【００５５】
＜構成＞
図１に例示するように、本形態の秘密計算システム４は、登録装置１１、Ｎ個の秘密計算装置４２−１，…，４２−（Ｎ−１）、および分析装置１３を有する。図２Ａに例示するように、本形態の秘密計算装置４２−ｎ（ただし、ｎ＝０，…，（Ｎ−１））は、例えば、制御部１２０−ｎ、入力部１２１−ｎ、記憶部１２２−ｎ、整合性検証部４２３−ｎ、秘密計算部１２４−ｎ、および出力部１２５−ｎを有する。
【００５６】
＜処理＞
本形態の処理も「登録処理」「保管処理」「分析処理」からなる。以下、図４を用いて本形態の処理を説明する。
【００５７】
「登録処理」
登録装置１１と秘密計算装置４２−ｎとが、第１実施形態で説明したステップＳ１１およびＳ１２の処理を実行する。ただし、本形態ではステップＳ１２の処理が省略されてもよい。
【００５８】
「保管処理」
秘密計算装置４２−ｎが、第１実施形態で説明したステップＳ１３の処理を実行する。ただし、本形態ではステップＳ１３での整合性検証の処理が省略されてもよい。
【００５９】
「分析処理」
まず、分析装置１３と秘密計算装置４２−ｎとが、第１実施形態で説明したステップＳ１４の処理を実行する。次に、Ｎ個の秘密計算装置４２−ｎ（ただし、ｎ＝０，…，Ｎ−１）の整合性検証部４２３−ｎが互いに通信し、対象データの秘密分散値［ｂ０］ｎ，…，［ｂＭ−１］ｎおよびクエリまたはクエリの秘密分散値を［ｑ０］ｎ，…，［ｑＪ−１］ｎの整合性検証をまとめて行う。すなわち、整合性検証部４２３−ｎは、［ｂ０］ｎ，…，［ｂＭ−１］ｎ，［ｑ０］ｎ，…，［ｑＪ−１］ｎを対象として整合性検証をまとめて行う。例えば、整合性検証部４２３−ｎは、Ｉ：＝Ｎとし、ｉ：＝ｎとし、Ｙ：＝Ｍ＋Ｊとし、（［ａ０］ｉ，…，［ａＹ−１］ｉ）：＝（［ｂ０］ｎ，…，［ｂＭ−１］ｎ，［ｑ０］ｎ，…，［ｑＪ−１］ｎ）とし、前述のステップＳ１２０１〜Ｓ１２１２の方法で整合性検証を行う。この場合も、対象データの秘密分散値およびクエリまたはクエリの秘密分散値を含む情報（［ｂ０］ｎ，…，［ｂＭ−１］ｎ，［ｑ０］ｎ，…，［ｑＪ−１］ｎ）を撹乱させた情報の整合性検証が行われてもよい。この整合性検証が合格である場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎ，［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎに保持される。一方、この整合性検証が不合格である場合、［ｂ０］ｎ，…，［ｂＭ−１］ｎ，［ｑ０］ｎ，…，［ｑＪ−１］ｎが記憶部１２２−ｎから削除され、ステップＳ１１の処理に戻すか、処理をエラー終了させる（ステップＳ４５）。その後、第１実施形態のステップＳ１６〜Ｓ１８の処理が実行される。
【００６０】
なお、第２実施形態または第３実施形態のステップＳ２５の整合性検証に代え、対象データの秘密分散値およびクエリまたはクエリの秘密分散値の整合性検証がまとめて行われてもよい。すなわち、Ｎ個の秘密計算装置４２−ｎの整合性検証部４２３−ｎでの整合性検証が不合格であった場合、Ｎ個の秘密計算装置４２−ｎ（ただし、ｎ＝０，…，Ｎ−１）からなる集合の真部分集合Ｓに属する秘密計算装置４２−ｕ（ι）の整合性検証部４２３−ｕ（ι）が、［ｂ０］ｕ（ι），…，［ｂＭ−１］ｕ（ι），［ｑ０］ｕ（ι），…，［ｑＪ−１］ｕ（ι）を対象として整合性検証を行ってもよい。
【００６１】
［その他の変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。また、上述した各演算は有限体上の演算であってもよいし、拡大体上の演算であってもよいし、環上の演算であってもよいし、その他の代数系上での演算であってもよい。また、改ざん検知付秘密計算に代えて、改ざん検知機能を持たない秘密計算が行われてもよい。
【００６２】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６３】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００６４】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００６６】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００６７】
１〜４  秘密計算システム
１１  登録装置
１２−ｎ〜４２−ｎ  秘密計算装置
１３  分析装置
【要約】
【課題】秘密計算装置に秘密計算の対象となる対象データの秘密分散値が格納され、秘密計算装置がこれらの対象データの秘密分散値を用い、入力されたクエリまたはクエリの秘密分散値に応じた秘密計算を行う場合に、改ざんによる不正を防止する。
【解決手段】秘密計算装置には、秘密計算の対象となる対象データの秘密分散値が格納され、秘密計算を要求するクエリまたはクエリの秘密分散値が入力される。秘密計算装置は、対象データの秘密分散値の整合性検証およびクエリまたはクエリの秘密分散値の整合性検証を行い、整合性検証に合格した対象データの秘密分散値を用い、整合性検証に合格したクエリまたはクエリの秘密分散値に応じた秘密計算を行って演算結果の秘密分散値を得、演算結果の秘密分散値を出力する。
【選択図】図４【図１】
0006034927.tif 000002
【図２】
0006034927.tif 000003
【図３】
0006034927.tif 000004
【図４】
0006034927.tif 000005
【図５】
0006034927.tif 000006
【図６】
0006034927.tif 000007
【図７】
0006034927.tif 000008
【図８】
0006034927.tif 000009
【図９】
0006034927.tif 000010
【図１０】
0006034927.tif 000011