セキュア集合関数システム、秘密集合関数装置、セキュア集合関数処理方法、セキュア集合関数プログラム
【課題】情報を秘匿しながら、計算量がデータ数のみに比例する集合関数演算を可能にする。
【解決手段】本発明のセキュア集合関数システムは、Ｎ個の秘密集合関数装置で構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）が秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。セキュア集合関数システムは、初期化手段と結合演算手段とを備える。初期化手段は、Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する。結合演算手段は、キーｋｉとキーｋｊとが等しいときにはｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）とし、等しくないときにはｚｊ＝ｚｊ，ｚｉ＝ｚｉとする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する。
【解決手段】本発明のセキュア集合関数システムは、Ｎ個の秘密集合関数装置で構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）が秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。セキュア集合関数システムは、初期化手段と結合演算手段とを備える。初期化手段は、Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する。結合演算手段は、キーｋｉとキーｋｊとが等しいときにはｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）とし、等しくないときにはｚｊ＝ｚｊ，ｚｉ＝ｚｉとする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータを秘匿しつつ集計等の集合関数と呼ばれる処理を、グループ化を伴って行うセキュア集合関数システム、秘密集合関数装置、セキュア集合関数処理方法、セキュア集合関数プログラムに関する。
【背景技術】
【０００２】
集合関数とは、単位元が存在し結合律と可換律の成り立つ演算（可換モノイド）をデータ群全体に行うことである。集合関数におけるグループ化とは、データ群を、キーとなる属性が等しいデータ群に分類し、分類した各データ群に対して集合関数を施すことである。
【０００３】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、例えば非特許文献１の秘密計算と呼ばれる方法がある。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定，論理積，論理和，排他的論理和）、データ形式変換（整数，二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。また、非特許文献２では、ソートの前後の値の対応を誰にも知られないように計算することを特徴とし、暗号化された複数のデータに対し、平文から計算される値でソートを行った結果の暗号文を計算する秘密ソート方法が提案されている。このような秘密計算を用いれば、集合関数演算も可能である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献２】濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “３パーティ秘匿関数計算上のランダム置換プロトコル”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
例えば、従来の秘密計算を用いた以下の処理で、グループ化して集合関数演算を行うことが可能と考える。なお、集合関数演算を行う対象を、キーｋｉと属性値ｖｉを含む情報（ｋｉ，ｖｉ）とする。
全てのキー属性値に対して以下を繰り返す。
１． ｉ番目のキー属性値ｋｉに対して、ｚｉ＝（０）とする。
２． 全データに対して以下を繰り返す。
ｊ番目のデータのキー属性がｋｉならば、ｚｉ＝ｚｉ（＋）ｖｊ
キー属性がｋｉでなければｚｉ＝ｚｉ
ただし、（０）は単位元、（＋）は当該集合関数の可換モノイド演算である。
【０００６】
しかしながら、上記の方法では、計算量が「キー属性値の数×データ数」に比例し、効率が悪い。
【０００７】
本発明は、情報を秘匿しながら、計算量がデータ数のみに比例し、キー属性値の数に依存しない集合関数演算を可能にする技術の提供を目的とする。
【課題を解決するための手段】
【０００８】
本発明のセキュア集合関数システムは、Ｎ個の秘密集合関数装置Ｒ１，…，ＲＮで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とする。
【０００９】
セキュア集合関数システムは、初期化手段と結合演算手段とを備える。初期化手段は、Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する。結合演算手段は、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する。
【発明の効果】
【００１０】
本発明のセキュア集合関数システムによれば、情報を秘匿しながら、計算量がデータ数のみに比例し、キー属性値の数に依存しない集合関数演算を実行できる。
【図面の簡単な説明】
【００１１】
【図１】実施例１と実施例２のセキュア集合関数システムの構成例を示す図。
【図２】実施例１のセキュア集合関数システムの処理フローを示す図。
【図３】実施例２のセキュア集合関数システムの処理フローを示す図。
【図４】実施例３のセキュア集合関数システムの構成例を示す図。
【図５】実施例３のセキュア集合関数システムの処理フローを示す図。
【図６】本発明に利用できる秘密分散装置１００ｎの機能構成例を詳しく示したセキュア集合関数システムを示す図。
【図７】ランダム置換の１つ目の処理フロー例を示す図。
【図８】ランダム置換の２つ目の処理フロー例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１３】
図１に実施例１のセキュア集合関数システムの構成例を示す。また、図２に実施例１のセキュア集合関数システムの処理フローを示す。実施例１のセキュア集合関数システムは、Ｎ個の秘密集合関数装置１０１，…，１０Ｎで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とする。（＋）の具体例としては、和（総和）、最小値、最大値などがある。
【００１４】
秘密集合関数装置１０ｎは、集合関数制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備える。秘密分散装置１００ｎは、集合関数制御部３００ｎの指示にしたがって実施例１の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、四則演算などがある。ただし、本発明は、これらの秘密計算を利用して効率よく集合関数演算を行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、１つの例であり、実施例１が利用できる秘密計算を限定するものではない。記録部１９０ｎは、秘密集合関数装置１０ｎの処理に必要な情報を記録する構成部である。図１に示した選択手段１０５は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。
【００１５】
各秘密集合関数装置１０ｎの集合関数制御部３００ｎは、初期化部３２０ｎ、結合演算部３３０ｎ、削除部３４０ｎを備える。そして、セキュア集合関数システムの初期化手段３２０（図示していない）は初期化部３２０１，…，３２０Ｎで構成され、結合演算手段３３０（図示していない）は結合演算部３３０１，…，３３０Ｎで構成され、削除手段３４０（図示していない）は削除部３４０１，…，３４０Ｎで構成される。
【００１６】
初期化手段３２０は、Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する（Ｓ３４０）。より具体的には、初期化部３２０１，…，３２０Ｎ（初期化手段３２０）は、秘密分散装置１００１，…，１００Ｎに属性値ｖｍの断片と同じ断片を持つデータｖｍの断片を作らせ、各断片を秘密分散させることで情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成させる。
【００１７】
結合演算手段３３０は、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理が、すべての等しいキーを持つ情報に対して実行されるまで、秘密計算で実行する（Ｓ３３０）。例えば、キーｋｉとキーｋｊとが等しいことを確認する論理回路は、従来技術として蓄積された論理回路の技術を用いれば、実現できる。キーｋｉとキーｋｊの２ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。
【００１８】
Ｃ＝１−｛（ｋｉＢ［∨］ｋｊＢ）∨・・・∨（ｋｉ１［∨］ｋｊ１）｝ （１）
ただし、［∨］は排他的論理和（ＸＯＲ）を示す記号、∨は論理和（ＯＲ）を示す記号、ｋｉｂは２ビット展開したときのキーｋｉの下からｂビット目の値、Ｂは２ビット展開したときのキーｋｉの桁数とする。式（１）では、Ｃ＝１ならばキーｋｉとキーｋｊとが等しく（真）、Ｃ＝０ならばキーｋｉとキーｋｊとが異なる（偽）。また、式（１）の個々の演算は後述の秘密計算の例に示されているので、式（１）の演算は秘密計算で実行でき、秘密分散された［Ｃ］が求められる。したがって、確認後の分岐も秘密にするのであれば、［Ｃ］を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、大小比較を比較する演算などの所望の演算を、後述する秘密計算の方法の組合せで実行できる。
【００１９】
さらに、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がランダムに並んだ情報の場合は、ｉ，ｊのすべての組合せに対して結合演算手段３３０の処理を行う必要がある。一方、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）が何らかの規則に従って並んでいれば、ｉ，ｊのすべての組合せまで実行する必要はない。例えば、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がキーｋｍに基づいてソートされている場合であれば、ｉを１からＭ−１まで順番に値を大きくしながら、ｊ＝ｉ＋１に対して、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とすればよい。もしくは、ｉをＭから２まで順番に値を小さくしながら、ｊ＝ｉ−１に対して、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とすればよい。このようにソート済みの情報であれば、隣り合う情報同士の比較を順番に行うだけで、同じ値のキーを持つすべての情報に対する集合関数演算を実行し、最後に結合したｚｊに集合関数演算の結果をまとめることができる。したがって、Ｏ（Ｍ）の計算量で処理ができる。
【００２０】
削除手段３４０は、結合演算手段３３０の処理後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを秘密計算で確認し、確認結果を復元する。つまり、式（１）でｚｍと（０）に対する［Ｃ］を求め、［Ｃ］を復元してＣを求める。そして、ｚｍ＝（０）の場合（式（１）であればＣ＝１の場合）には情報（［ｋｍ］，［ｚｍ］）を削除する（Ｓ３４０）。ステップＳ３４０の削除は、残りの情報の数が、情報（［ｋｍ］，［ｚｍ］）の数とキーの値の数の少ない方になるまで削除すればよい。なお、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がもともとランダムに並んでいる場合は、ランダム置換は必要ないので削除手段３４０を省略してもよい。情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がキーｋｍに基づいてソートされている場合は、ｚｍ＝（０）の確認結果を復元すると、キーの値が同じ情報が何個あるのか、何番目に境界があるのかなどのキーに関する情報が漏れてしまう。したがって、ランダム置換が必要となる。
【実施例２】
【００２１】
図１に実施例２のセキュア集合関数システムの構成例を示す。また、図３に実施例２のセキュア集合関数システムの処理フローを示す。実施例２のセキュア集合関数システムも、Ｎ個の秘密集合関数装置１０１，…，１０Ｎで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号、Ｔは（ｌｏｇ２Ｍ）−１以上の最小の整数、ｔは０以上Ｔ以下の整数、＾はべき乗を示す記号とする。また、実施例２では、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とする。
【００２２】
秘密集合関数装置１０ｎは、集合関数制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備え、秘密分散装置１００ｎ、記録部１９０ｎ、集合関数制御部３００ｎの初期化部３２０ｎ、削除部３４０ｎは実施例１と同じである。異なるのは、結合演算部３３０ｎである。つまり、初期化手段３２０と削除手段３４０は実施例１と同じであり、結合演算手段３３０が異なる。
【００２３】
実施例２の結合演算部３３０ｎは、第１結合部３３１ｎ、第２結合部３３２ｎ、第３結合部３３３ｎを備える。そして、第１結合手段３３１（図示していない）は第１結合部３３１１，…，３３１Ｎで構成され、第２結合手段３３２（図示していない）は第２結合部３３２１，…，３３２Ｎで構成され、第３結合手段３３３（図示していない）は第３結合部３３３１，…，３３３Ｎで構成される。また、結合演算手段３３０は、第１結合手段３３１、第２結合手段３３２、第３結合手段３３３を有する。
【００２４】
結合演算手段３３０は、ｔに０を代入する（Ｓ３３６）。第１結合手段３３１は、ｉ＝１，２，…，Ｍ−２＾ｔについて、ｋｉとｋｉ＋２＾ｔが等しいときには
ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔ
とし、等しくないときには
ｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔ
とする（Ｓ３３１）。より具体的には、第１結合部３３１１，…，３３１Ｎ（第１結合手段３３１）は、秘密分散装置１００１，…，１００Ｎに、ｉ＝１，２，…，Ｍ−２＾ｔについて、ｋｉとｋｉ＋２＾ｔが等しいかを、例えば式（１）の秘密計算で確認させる。そして、その結果に基づいて、ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔまたはｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔの秘密計算を実行させる。なお、ステップＳ３３１のｉ＝１，２，…，Ｍ−２＾ｔについての処理は、互いに影響しないため並列に処理できる。
【００２５】
第２結合手段３３２は、ｉ＝１，２，…，Ｍについて
ｚｉ＝ｚｉ’
とする（Ｓ３３２）。なお、ステップＳ３３２もｉ＝１，２，…，Ｍについての処理は互いに影響しないため、並列に処理できる。そして、結合演算手段３３０は、ｔ＝Ｔかを確認し（Ｓ３３７）、Ｙｅｓの場合にはステップＳ３３３に進み、Ｎｏの場合にはｔにｔ＋１を代入し（Ｓ３３８）、ステップＳ３３１に戻る。
【００２６】
ステップＳ３３３では、第３結合手段が、ｉ＝１，２，…，Ｍ−１について、ｋｉとｋｉ＋１が等しいときには
ｚｉ＝ｚｉ
とし、等しくないときには
ｚｉ＝（０）
とする（Ｓ３３３）。
【００２７】
なお、ステップＳ３２０とＳ３４０の処理は実施例１と同じである。
【００２８】
このように、結合演算手段３３０は、ｔ＝０，１，２，…，Ｔについて、第１結合手段３３１と第２結合手段３３２の処理（Ｓ３３１，Ｓ３３２）を繰返した後に第３結合手段３３３の処理（Ｓ３３３）を行う。また、ステップＳ３３１、Ｓ３３２は並列処理が可能なので、演算回数が多くなったとしても、繰返しの演算を順番に実行せざるを得ない実施例１の方法よりも高速の演算が可能である。より具体的に説明すると、実施例２のセキュア集合関数システムの計算量は、データ数Ｍに対しＯ（Ｍ ｌｏｇ Ｍ）となる。したがって、実施例１のＯ（Ｍ）よりも増加する。一方、実施例１は順番に処理する必要があるので、段数（直列に処理せざるを得ない計算数）もＯ（Ｍ）である。しかし、実施例２では大幅に並列度が上昇するので、段数はＯ（ｌｏｇ Ｍ）に減少する。
【実施例３】
【００２９】
図４に実施例３のセキュア集合関数システムの構成例を示す。また、図５に実施例３のセキュア集合関数システムの処理フローを示す。実施例３のセキュア集合関数システムも、Ｎ個の秘密集合関数装置１０１，…，１０Ｎで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号、ｓはあらかじめ定めたＭ以下の整数、Ｋはキーｋｍの取り得る値の数とする。また、実施例３では、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とする。
【００３０】
秘密集合関数装置１０ｎは、集合関数制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備え、秘密分散装置１００ｎ、記録部１９０ｎ、集合関数制御部３００ｎの初期化部３２０ｎ、結合演算手段３３０、削除部３４０ｎは実施例１または実施例２と同じである。異なるのは、事前処理部３１０ｎである。つまり、初期化手段３２０と結合演算手段３３０と削除手段３４０は、実施例１または実施例２と同じである。
【００３１】
事前処理部３１０ｎは、第１事前初期化部３１１ｎ、第２事前初期化部３１２ｎ、事前結合部３１３ｎ、保存部３１４ｎ、第２事前繰返部３１５ｎ、事前削除部３１６ｎ、第１事前繰返部３１７ｎを有する。そして、第１事前初期化手段３１１（図示していない）は第１事前初期化部３１１１，…，３１１Ｎで構成され、第２事前初期化手段３１２（図示していない）は第２事前初期化部３１２１，…，３１２Ｎで構成され、事前結合手段３１３（図示していない）は事前結合部３１３１，…，３１３Ｎで構成され、保存手段３１４（図示していない）は保存部３１４１，…，３１４Ｎで構成され、第２事前繰返手段３１５（図示していない）は第２事前繰返部３１５１，…，３１５Ｎで構成され、事前削除手段３１６（図示していない）は事前削除部３１６１，…，３１６Ｎで構成され、第１事前繰返手段３１７（図示していない）は第１事前繰返部３１７１，…，３１７Ｎで構成される。また、事前処理手段３１０は、第１事前初期化手段３１１、第２事前初期化手段３１２、事前結合手段３１３、保存手段３１４、第２事前繰返手段３１５、事前削除手段３１６、第１事前繰返手段３１７を有する。
【００３２】
第１事前初期化手段３１１は、Ｍ’＝Ｍとする（Ｓ３１１）。第２事前初期化手段３１２は、ｔ＝０、Ｍ”＝Ｍ’とする（Ｓ３１２）。事前結合手段３１３は、ｔにｔ＋１を代入し、１からＭ”／２以下の最大の整数までのｉについて、ｋ２ｉ−１とｋ２ｉが等しいときには
ｚ２ｉ＝ｚ２ｉ−１（＋）ｚ２ｉ，ｚ２ｉ−１＝（０）
とし、等しくないときには
ｚ２ｉ＝ｚ２ｉ， ｚ２ｉ−１＝ｚ２ｉ−１
とする（Ｓ３１３）。なお、ｋ２ｉ−１とｋ２ｉとの比較は、事前結合部３１３１，…，３１３Ｎ（事前結合手段３１３）が、秘密分散装置１００１，…，１００Ｎに、例えば式（１）の論理式を用いた秘密計算を実行させればよい。また、異なるｉに対する演算同士は互いに影響を与えないので、異なるｉに対する演算は並列で行うことができる。
【００３３】
保存手段３１４は、奇数番目の情報（［ｋｍ’］，［ｚｍ’］）を抜き取って保存し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数を新しいＭ”とする（Ｓ３１４）。第２事前繰返手段３１５は、Ｍ”が２Ｋ以下か（第２事前繰返条件）を確認し、第２事前繰返条件を満たすまで事前結合手段３１３の処理（Ｓ３１３）と保存手段３１４の処理（Ｓ３１４）を繰り返す（Ｓ３１５）。
【００３４】
事前削除手段Ｓ３１６は、保存手段３１４が保存したすべての情報（［ｋｍ’］，［ｚｍ’］）と残った情報（［ｋｍ］，［ｚｍ］）とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを秘密計算で確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数をＭ’とする（Ｓ３１６）。なお、新しい情報（残りの情報）の数Ｍ’が
ｔＫ＋（最後のステップＳ３１５で残った情報の数）
になるまでステップＳ３１６で情報を削除できる。
【００３５】
第１事前繰返手段Ｓ３１７は、Ｍ’がｓより小さいか（第１事前繰返条件）を確認し、第１事前繰返条件を満たすまで第２事前初期化手段３１２の処理（Ｓ３１２）、事前結合手段３１３の処理（Ｓ３１３）、保存手段３１４の処理（Ｓ３１４）、第２事前繰返手段３１５（Ｓ３１５）、事前削除手段３１６（Ｓ３１６）を繰り返す（Ｓ３１７）。
【００３６】
そして、セキュア集合関数システムは、Ｍを、事前処理手段３１０の処理（Ｓ３１０）後の情報（［ｋｍ］，［ｚｍ］）の数に変更し、事前処理手段３１０の処理（Ｓ３１０）後の情報（［ｋｍ］，［ｚｍ］）に対して、実施例１または実施例２に示した初期化手段３２０の処理（Ｓ３２０）、結合演算手段３３０の処理（Ｓ３３０）、を実行する。
【００３７】
実施例３の事前処理手段３１０の処理は、情報の数Ｍがキーの取り得る値の数Ｋに比べて非常に大きい場合に演算量を減らす効果がある。一方、ＭとＫの値が近くなると実施例１や実施例２の結合演算手段３３０の処理（Ｓ３３０）の方が演算量を少なくできる。したがって、ＭがＫに比べて非常に大きいときに、事前処理手段３１０を用いて情報の数Ｍを少なくし、ＭがＫに近づいたところで実施例１や実施例２の結合演算手段３３０に切り替えて処理すれば効率的である。より具体的には、実施例３のセキュア集合関数システムの計算量はＯ（Ｍ＋ Ｋ ｌｏｇ Ｍ）であり、段数はＯ（ｌｏｇ Ｍ）である。あらかじめ定めるｓは、どの程度ＭがＫに近づいたところで切り替えるのかを定める値であり、全体の演算量が少なくなるように適宜決めればよい。このように、実施例３のセキュア集合関数システムによれば、情報の数Ｍがキーの取り得る値の数Ｋに比べて非常に大きい場合に演算量を減らすことができる。
【００３８】
［演算量の具体例］
情報の数Ｍ＝１０００、キーの取り得る値の数Ｋ＝１０とする。実施例３のステップＳ３１４の１回目でＭ”＝５００、２回目でＭ”＝２５０となり、６回目でＭ”＝１６となる。そして、ここまでの結合演算の回数は９８５回であり、残りの情報の数は次のようになる。
【００３９】
ｔＫ＋（最後のステップＳ３１５で残った情報の数）＝６×１０＋１６＝７６
これをもう一度繰り返すと、ｔ＝２でＭ”＝１９、結合演算の回数は５７回増えて１０４２回、残りの情報の数の最大値（実際にはこの数以下となる数）は２×１０＋１９＝３９となる。例えばｓを４０に設定していれば、ステップＳ３１７は終了し、ステップＳ３２０に進む。ステップＳ３２０，Ｓ３３０，Ｓ３４０を実施例１の方法で実行すれば、結合演算の回数は１０８０回、段数は４６段である。ステップＳ３２０，Ｓ３３０，Ｓ３４０を実施例２の方法で実行すれば、結合演算の回数は１２１３回、段数は１４段である。比較として、最初から実施例１の方法にした場合は、結合演算の回数は９９９回、段数は９９９段、実施例２の方法の場合の結合演算の回数は８９７７回、段数は１０段となり、情報の数Ｍがキーの取り得る値の数Ｋよりかなり大きい場合、実施例３の方法は計算量と段数のバランスに優れることが分かる。なお、従来の方法の場合、結合演算の回数は９９９０回、段数は１０段である。
【００４０】
［秘密計算］
上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密集合関数装置１０１，…，１０Ｎが実行するランダム置換とその他の秘密計算について説明する。なお、以下の秘密計算に関する説明は、１つの例でありこれに限定されるものではない。本発明のセキュア集合関数システムでは他の秘密計算を用いてもよい。
【００４１】
ランダム置換１
図６に本発明に利用できる秘密分散装置１００ｎの機能構成例を詳しく示したセキュア集合関数システムを示す。図７にランダム置換の１つ目の処理フロー例を示す。この例では、セキュア集合関数システムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密集合関数装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密集合関数装置１０ｎが記録するｋ番目の断片とする。なお、数値Ａ１，…，ＡＫが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密集合関数装置の内部に配置されてもよいし、単独の装置であってもよい。
【００４２】
セキュア集合関数システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００４３】
選択手段１０５は、Ｎ未満の数の秘密集合関数装置１０ｎを選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密集合関数装置を選べばよい。
【００４４】
断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密集合関数装置１０ｉ（ただし、ｉは選択された秘密集合関数装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密集合関数装置１０ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（Ｓ１１０）。全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密集合関数装置１０ｉ間で生成してもよいし、選択された秘密集合関数装置１０ｉのうちの１つの秘密集合関数装置が生成して、選択された秘密集合関数装置１０ｉ間で共有してもよい。
【００４５】
再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）に対応する断片ａπ（ｋ）ｉ（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１，…，ｂｋＮを求め、数値Ｂｋの断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）＝Ｂｋの関係が成り立つが、選ばれなかった秘密集合関数装置は全単射πを知らないので、Ａπ（ｋ）＝Ｂｋであることを知らない。なお、各秘密集合関数装置１０ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密集合関数装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００４６】
本発明のセキュア集合関数システムによれば、限定された秘密集合関数装置間で断片をシャッフルする。したがって、選ばれなかった秘密集合関数装置は、全単射πを知らないので、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない。つまり、特定の秘密集合関数装置からは数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない状態にしたいのであれば、その秘密集合関数装置を選択手段１０５で選ばないように、選択する秘密集合関数装置をあらかじめ定めればよい。また、選択手段１０５が選ぶ秘密集合関数装置を変更しながらこの処理を繰り返し、全ての秘密集合関数装置が選ばれなかったことがある状態にすれば、全ての秘密集合関数装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。
【００４７】
ランダム置換２
次のランダム置換のためのセキュア集合関数システムの秘密分散装置１００ｎを詳細に示した機能構成例も図６に示す。図８にランダム置換の２つ目の処理フロー例を示す。この例でも、セキュア集合関数システムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密集合関数装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密集合関数装置１０ｎが記録する数値Ａｋの断片とする。
【００４８】
本発明のセキュア集合関数システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００４９】
選択手段１０５はランダム置換１と同じである。初期情報分散手段は、初期情報分散部１３０１，…，１３０Ｎで構成される。そして、選択手段１０５に選択された秘密集合関数装置１０ｉの初期情報分散部１３０ｉは、秘密集合関数装置１０１，…，１０Ｎのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１ｎ，…，ｐＫｎを秘密計算によって求め、記録部１９０ｎに記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密集合関数装置から、２つ以上の秘密集合関数装置を選定する。そして、選定された秘密集合関数装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密集合関数装置１０ｉ，１０ｊを選定し（ただし、ｉ≠ｊ）、秘密集合関数装置１０ｉが生成した数値の断片と、秘密集合関数装置１０ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密集合関数装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密集合関数装置を２つとしたが、２つ以上でもかまわない。
【００５０】
初期乗算手段は、初期乗算部１４０１，…，１４０Ｎで構成される。初期乗算部１４０１，…，１４０Ｎは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１４０）。
【００５１】
断片置換手段と再分散手段は、ランダム置換１と同じである。確認分散手段は、確認分散部１５０１，…，１５０Ｎで構成される。確認分散部１５０１，…，１５０Ｎは、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密集合関数装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密集合関数装置１０ｉが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密集合関数装置１０ｊが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密集合関数装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密集合関数装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。
【００５２】
確認乗算手段は、確認乗算部１６０１，…，１６０Ｎで構成される。確認乗算部１６０１，…，１６０Ｎは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１６０）。
【００５３】
改ざん検出手段は、改ざん検出部１７０１，…，１７０Ｎで構成される。改ざん検出部１７０１，…，１７０Ｎは、ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する（Ｓ１７０）。ｔｋｎ≠ｓπ（ｋ）ｎの場合には、改ざんがあったとして異常終了する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密集合関数装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００５４】
［その他の秘密計算］
ここでは、セキュア集合関数システムが３個の秘密集合関数装置で構成された場合の秘密計算の例を示す。また、秘密集合関数装置１０１，１０２，１０３の番号を固定する必要はないので、秘密集合関数装置１０α，１０β，１０γと表現することにする。つまり、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれかである。
【００５５】
以下の秘密計算では、秘密集合関数装置１０α，１０β，１０γが分散して記録する数値Ａの断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）、数値Ｂの断片を（ｂγα，ｂαβ）、（ｂαβ，ｂβγ）、（ｂβγ，ｂγα）、数値Ｃの断片を（ｃγα，ｃαβ）、（ｃαβ，ｃβγ）、（ｃβγ，ｃγα）とする。なお、以下の説明では、Ｗを２以上のあらかじめ定めた整数とし、計算結果はＷで除した余りである。言い換えると、以下の説明の計算式では“ｍｏｄ Ｗ”を省略している。
【００５６】
数値Ａの秘密分散
（１）乱数ａαβ，ａβγを生成する。
（２）ａγα＝Ａ−ａαβ−ａβγを計算し、断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）とし、秘密集合関数装置１０α，１０β，１０γに分散して記録する。
【００５７】
数値Ａの復元
（１）秘密集合関数装置１０αは秘密集合関数装置１０βにａγαを送信し、秘密集合関数装置１０γにａαβを送信する。秘密集合関数装置１０βは秘密集合関数装置１０γにａαβを送信し、秘密集合関数装置１０αにａβγを送信する。秘密集合関数装置１０γは秘密集合関数装置１０αにａβγを送信し、秘密集合関数装置１０βにａγαを送信する。
（２）秘密集合関数装置１０αは秘密集合関数装置１０βから受信したａβγと秘密集合関数装置１０γから受信したａβγとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密集合関数装置１０βは秘密集合関数装置１０γから受信したａγαと秘密集合関数装置１０αから受信したａγαとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密集合関数装置１０γは秘密集合関数装置１０αから受信したａαβと秘密集合関数装置１０βから受信したａαβとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。
【００５８】
Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγα＋ｂγα，ａαβ＋ｂαβ）を計算して記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）＝（ａαβ＋ｂαβ，ａβγ＋ｂβγ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγ＋ｂβγ，ａγα＋ｂγα）を計算して記録する。
【００５９】
Ｃ＝Ａ−Ｂの秘密計算
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγα−ｂγα，ａαβ−ｂαβ）を計算して記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）＝（ａαβ−ｂαβ，ａβγ−ｂβγ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγ−ｂβγ，ａγα−ｂγα）を計算して記録する。
【００６０】
Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγα＋Ｓ，ａαβ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγ，ａγα＋Ｓ）を計算して記録する。秘密集合関数装置１０βの処理はない。
【００６１】
Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγαＳ，ａαβＳ）を計算して記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）＝（ａαβＳ，ａβγＳ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγＳ，ａγαＳ）を計算して記録する。
【００６２】
Ｃ＝ＡＢの秘密計算
（１）秘密集合関数装置１０αは、乱数ｒ１，ｒ２，ｃγαを生成し、ｃαβ＝（ａγα＋ａαβ）（ｂγα＋ｂαβ）−ｒ１−ｒ２−ｃγαを計算する。そして、秘密集合関数装置１０αは、秘密集合関数装置１０βに（ｒ１，ｃαβ）を、秘密集合関数装置１０γに（ｒ２，ｃγα）を送信する。
（２）秘密集合関数装置１０βは、ｙ＝ａαβｂβγ＋ａβγｂαβ＋ｒ１を計算し、秘密集合関数装置１０γに送信する。
（３）秘密集合関数装置１０γは、ｚ＝ａβγｂγα＋ａγαｂβγ＋ｒ２を計算し、秘密集合関数装置１０αに送信する。
（４）秘密集合関数装置１０βと秘密集合関数装置１０γは、それぞれｃβγ＝ｙ＋ｚ＋ａβγｂβγを計算する。
（５）秘密集合関数装置１０αは（ｃγα，ｃαβ）を記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）を記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）を記録する。
【００６３】
ビットＡの否定（Ｃ＝１−Ａ）の秘密計算
秘密集合関数装置１０αは
（ｃγα，ｃαβ）＝（１−ａγα，−ａαβ ｍｏｄ Ｗ）
を計算して記録し、秘密集合関数装置１０βは
（ｃαβ，ｃβγ）＝（−ａαβ ｍｏｄ Ｗ，−ａβγ ｍｏｄ Ｗ）
を計算して記録し、秘密集合関数装置１０γは
（ｃβγ，ｃγα）＝（−ａβγ ｍｏｄ Ｗ，１−ａγα）
を計算して記録する。
【００６４】
ビットの論理積（Ｃ＝Ａ∧Ｂ＝ＡＢ）の秘密計算
秘密集合関数装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行う。
【００６５】
ビットの論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ）の秘密計算
（１）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密集合関数装置１０αが断片（ｃγα’，ｃαβ’）を、秘密集合関数装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密集合関数装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密集合関数装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密集合関数装置１０αが断片（ｃγα”，ｃαβ”）を、秘密集合関数装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密集合関数装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密集合関数装置１０α，１０β，１０γは、Ｓ＝−１として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）と同じ処理を行い、Ｃ’’’＝−Ｃ”の結果として、秘密集合関数装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密集合関数装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密集合関数装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密集合関数装置１０αが断片（ｃγα，ｃαβ）を、秘密集合関数装置１０βが断片（ｃαβ，ｃβγ）を、秘密集合関数装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００６６】
ビットの排他的論理和（Ｃ＝Ａ［∨］Ｂ＝Ａ＋Ｂ−２ＡＢ）の秘密計算
（１）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密集合関数装置１０αが断片（ｃγα’，ｃαβ’）を、秘密集合関数装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密集合関数装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密集合関数装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密集合関数装置１０αが断片（ｃγα”，ｃαβ”）を、秘密集合関数装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密集合関数装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密集合関数装置１０α，１０β，１０γは、Ｓ＝−２として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）の秘密計算と同じ処理を行い、Ｃ’’’＝−２Ｃ”の結果として、秘密集合関数装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密集合関数装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密集合関数装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密集合関数装置１０αが断片（ｃγα，ｃαβ）を、秘密集合関数装置１０βが断片（ｃαβ，ｃβγ）を、秘密集合関数装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００６７】
ビットＡ（ｎ），ｎ＝０，…，Ｎ−１の整数変換の秘密計算
ビットＡ（ｎ）の整数変換とは、
【００６８】
【数１】
【００６９】
を求めることである。また、秘密集合関数装置１０α，１０β，１０γが分散して記録するビットＡ（ｎ）の断片を（ａ（ｎ）γα，ａ（ｎ）αβ）、（ａ（ｎ）αβ，ａ（ｎ）βγ）、（ａ（ｎ）βγ，ａ（ｎ）γα）とする。秘密集合関数装置１０αは、
【００７０】
【数２】
【００７１】
を計算して記録し、秘密集合関数装置１０βは
【００７２】
【数３】
【００７３】
を計算して記録し、秘密集合関数装置１０γは
【００７４】
【数４】
【００７５】
を計算して記録する。
【００７６】
Ｎビットの整数Ａの二進数変換の秘密計算
ｘ（ｎ）は、ｘの下位ｎ＋１番目のビットを示すものとする。
（１）ｎ＝０からＮ−１について、秘密集合関数装置１０βが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）を秘密分散し、秘密集合関数装置１０α，１０β，１０γが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）の断片（ｂ（ｎ）γα，ｂ（ｎ）αβ）、（ｂ（ｎ）αβ，ｂ（ｎ）βγ）、（ｂ（ｎ）βγ，ｂ（ｎ）γα）を分散して記録する。ｎ＝０からＮ−１について、秘密集合関数装置１０γが（ａγα）（ｎ）を秘密分散し、秘密集合関数装置１０α，１０β，１０γが（ａγα）（ｎ）の断片（（ａγα）（ｎ）γα，（ａγα）（ｎ）αβ）、（（ａγα）（ｎ）αβ，（ａγα）（ｎ）βγ）、（（ａγα）（ｎ）βγ，（ａγα）（ｎ）γα）を分散して記録する。
（２）ｃγα＝０とし、ｎ＝０からＮ−１について（２−１）から（２−３）の処理を繰返し実行する。
（２−１）ｄｎ＝ｂ（ｎ）＋（ａγα）（ｎ）−２ｂ（ｎ）（ａγα）（ｎ）
の秘密計算を実行し、ｄｎの断片を分散して記録する。
（２−２）ａ（ｎ）＝ｄｎ＋ｃｎ−２ｄｎｃｎ
の秘密計算を実行し、ａ（ｎ）の断片を分散して記録する。
（２−３）ｎ＜Ｎ−１であれば、
ｃｎ＋１＝ｂ（ｎ）（ａγα）（ｎ）＋ｄｎｃｎ−ｂ（ｎ）（ａγα）（ｎ）ｄｎｃｎ
の秘密計算を実行し、ｃｎ＋１の断片を分散して記録する。
【００７７】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００８３】
１０１，…，１０Ｎ 秘密集合関数装置 １００１，…，１００Ｎ 秘密分散装置
１０５ 選択手段 １１０１，…，１１０Ｎ 断片置換部
１２０１，…，１２０Ｎ 再分散部 １３０１，…，１３０Ｎ 初期情報分散部
１４０１，…，１４０Ｎ 初期乗算部 １５０１，…，１５０Ｎ 確認分散部
１６０１，…，１６０Ｎ 確認乗算部 １７０１，…，１７０Ｎ 改ざん検出部
１９０１，…，１９０Ｎ 記録部 ３００１，…，３００Ｎ 集合関数制御部
３１０ 事前処理手段 ３１０１，…，３１０Ｎ 事前処理部
３１１ 第１事前初期化手段 ３１１１，…，３１１Ｎ 第１事前初期化部
３１２ 第２事前初期化手段 ３１２１，…，３１２Ｎ 第２事前初期化部
３１３ 事前結合手段 ３１３１，…，３１３Ｎ 事前結合部
３１４ 保存手段 ３１４１，…，３１４Ｎ 保存部
３１５ 第２事前繰返手段 ３１５１，…，３１５Ｎ 第２事前繰返部
３１６ 事前削除手段 ３１６１，…，３１６Ｎ 事前削除部
３１７ 第１事前繰返手段 ３１７１，…，３１７Ｎ 第１事前繰返部
３２０ 初期化手段 ３２０１，…，３２０Ｎ 初期化部
３３０ 結合演算手段 ３３０１，…，３３０Ｎ 結合演算部
３３１ 第１結合手段 ３３１１，…，３３１Ｎ 第１結合部
３３２ 第２結合手段 ３３２１，…，３３２Ｎ 第２結合部
３３３ 第３結合手段 ３３３１，…，３３３Ｎ 第３結合部
３４０ 削除手段 ３４０１，…，３４０Ｎ 削除部
１０００ ネットワーク
【技術分野】
【０００１】
本発明はデータを秘匿しつつ集計等の集合関数と呼ばれる処理を、グループ化を伴って行うセキュア集合関数システム、秘密集合関数装置、セキュア集合関数処理方法、セキュア集合関数プログラムに関する。
【背景技術】
【０００２】
集合関数とは、単位元が存在し結合律と可換律の成り立つ演算（可換モノイド）をデータ群全体に行うことである。集合関数におけるグループ化とは、データ群を、キーとなる属性が等しいデータ群に分類し、分類した各データ群に対して集合関数を施すことである。
【０００３】
暗号化された数値を復元すること無く特定の演算結果を得る方法として、例えば非特許文献１の秘密計算と呼ばれる方法がある。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算（否定，論理積，論理和，排他的論理和）、データ形式変換（整数，二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。また、非特許文献２では、ソートの前後の値の対応を誰にも知られないように計算することを特徴とし、暗号化された複数のデータに対し、平文から計算される値でソートを行った結果の暗号文を計算する秘密ソート方法が提案されている。このような秘密計算を用いれば、集合関数演算も可能である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, In CSS, 2010.
【非特許文献２】濱田浩気, 五十嵐大, 千田浩司, 高橋克巳, “３パーティ秘匿関数計算上のランダム置換プロトコル”, In CSS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
例えば、従来の秘密計算を用いた以下の処理で、グループ化して集合関数演算を行うことが可能と考える。なお、集合関数演算を行う対象を、キーｋｉと属性値ｖｉを含む情報（ｋｉ，ｖｉ）とする。
全てのキー属性値に対して以下を繰り返す。
１． ｉ番目のキー属性値ｋｉに対して、ｚｉ＝（０）とする。
２． 全データに対して以下を繰り返す。
ｊ番目のデータのキー属性がｋｉならば、ｚｉ＝ｚｉ（＋）ｖｊ
キー属性がｋｉでなければｚｉ＝ｚｉ
ただし、（０）は単位元、（＋）は当該集合関数の可換モノイド演算である。
【０００６】
しかしながら、上記の方法では、計算量が「キー属性値の数×データ数」に比例し、効率が悪い。
【０００７】
本発明は、情報を秘匿しながら、計算量がデータ数のみに比例し、キー属性値の数に依存しない集合関数演算を可能にする技術の提供を目的とする。
【課題を解決するための手段】
【０００８】
本発明のセキュア集合関数システムは、Ｎ個の秘密集合関数装置Ｒ１，…，ＲＮで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とする。
【０００９】
セキュア集合関数システムは、初期化手段と結合演算手段とを備える。初期化手段は、Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する。結合演算手段は、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する。
【発明の効果】
【００１０】
本発明のセキュア集合関数システムによれば、情報を秘匿しながら、計算量がデータ数のみに比例し、キー属性値の数に依存しない集合関数演算を実行できる。
【図面の簡単な説明】
【００１１】
【図１】実施例１と実施例２のセキュア集合関数システムの構成例を示す図。
【図２】実施例１のセキュア集合関数システムの処理フローを示す図。
【図３】実施例２のセキュア集合関数システムの処理フローを示す図。
【図４】実施例３のセキュア集合関数システムの構成例を示す図。
【図５】実施例３のセキュア集合関数システムの処理フローを示す図。
【図６】本発明に利用できる秘密分散装置１００ｎの機能構成例を詳しく示したセキュア集合関数システムを示す図。
【図７】ランダム置換の１つ目の処理フロー例を示す図。
【図８】ランダム置換の２つ目の処理フロー例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１３】
図１に実施例１のセキュア集合関数システムの構成例を示す。また、図２に実施例１のセキュア集合関数システムの処理フローを示す。実施例１のセキュア集合関数システムは、Ｎ個の秘密集合関数装置１０１，…，１０Ｎで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とする。（＋）の具体例としては、和（総和）、最小値、最大値などがある。
【００１４】
秘密集合関数装置１０ｎは、集合関数制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備える。秘密分散装置１００ｎは、集合関数制御部３００ｎの指示にしたがって実施例１の処理に必要な個々の秘密計算を行う。本発明の処理に必要な個々の秘密計算としては、秘密分散、復号、四則演算などがある。ただし、本発明は、これらの秘密計算を利用して効率よく集合関数演算を行うものであり、秘密計算自体に特徴がある発明ではない。そこで、秘密計算については、例を後述することとし、本発明のポイントを理解しやすくするためにここでの説明は省略する。なお、後述する秘密計算の方法は、１つの例であり、実施例１が利用できる秘密計算を限定するものではない。記録部１９０ｎは、秘密集合関数装置１０ｎの処理に必要な情報を記録する構成部である。図１に示した選択手段１０５は後述する秘密計算では利用するが、利用する秘密計算によっては備えなくてもよい。
【００１５】
各秘密集合関数装置１０ｎの集合関数制御部３００ｎは、初期化部３２０ｎ、結合演算部３３０ｎ、削除部３４０ｎを備える。そして、セキュア集合関数システムの初期化手段３２０（図示していない）は初期化部３２０１，…，３２０Ｎで構成され、結合演算手段３３０（図示していない）は結合演算部３３０１，…，３３０Ｎで構成され、削除手段３４０（図示していない）は削除部３４０１，…，３４０Ｎで構成される。
【００１６】
初期化手段３２０は、Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する（Ｓ３４０）。より具体的には、初期化部３２０１，…，３２０Ｎ（初期化手段３２０）は、秘密分散装置１００１，…，１００Ｎに属性値ｖｍの断片と同じ断片を持つデータｖｍの断片を作らせ、各断片を秘密分散させることで情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成させる。
【００１７】
結合演算手段３３０は、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理が、すべての等しいキーを持つ情報に対して実行されるまで、秘密計算で実行する（Ｓ３３０）。例えば、キーｋｉとキーｋｊとが等しいことを確認する論理回路は、従来技術として蓄積された論理回路の技術を用いれば、実現できる。キーｋｉとキーｋｊの２ビット展開した各ビットの排他的論理和の論理和の否定によって次のように確認してもよい。
【００１８】
Ｃ＝１−｛（ｋｉＢ［∨］ｋｊＢ）∨・・・∨（ｋｉ１［∨］ｋｊ１）｝ （１）
ただし、［∨］は排他的論理和（ＸＯＲ）を示す記号、∨は論理和（ＯＲ）を示す記号、ｋｉｂは２ビット展開したときのキーｋｉの下からｂビット目の値、Ｂは２ビット展開したときのキーｋｉの桁数とする。式（１）では、Ｃ＝１ならばキーｋｉとキーｋｊとが等しく（真）、Ｃ＝０ならばキーｋｉとキーｋｊとが異なる（偽）。また、式（１）の個々の演算は後述の秘密計算の例に示されているので、式（１）の演算は秘密計算で実行でき、秘密分散された［Ｃ］が求められる。したがって、確認後の分岐も秘密にするのであれば、［Ｃ］を用いた秘密計算をさらに組合せればよい。なお、後述する秘密計算は、数値の秘密分散、秘密分散された断片の復号、秘密分散された数値の四則計算、秘密分散されたビットごとの論理演算の基本的な計算方法を網羅して示している。したがって、従来技術として蓄積された論理回路の技術を用いれば、上述の等しいことを確認する方法のように、大小比較を比較する演算などの所望の演算を、後述する秘密計算の方法の組合せで実行できる。
【００１９】
さらに、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がランダムに並んだ情報の場合は、ｉ，ｊのすべての組合せに対して結合演算手段３３０の処理を行う必要がある。一方、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）が何らかの規則に従って並んでいれば、ｉ，ｊのすべての組合せまで実行する必要はない。例えば、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がキーｋｍに基づいてソートされている場合であれば、ｉを１からＭ−１まで順番に値を大きくしながら、ｊ＝ｉ＋１に対して、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とすればよい。もしくは、ｉをＭから２まで順番に値を小さくしながら、ｊ＝ｉ−１に対して、キーｋｉとキーｋｊとが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とすればよい。このようにソート済みの情報であれば、隣り合う情報同士の比較を順番に行うだけで、同じ値のキーを持つすべての情報に対する集合関数演算を実行し、最後に結合したｚｊに集合関数演算の結果をまとめることができる。したがって、Ｏ（Ｍ）の計算量で処理ができる。
【００２０】
削除手段３４０は、結合演算手段３３０の処理後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを秘密計算で確認し、確認結果を復元する。つまり、式（１）でｚｍと（０）に対する［Ｃ］を求め、［Ｃ］を復元してＣを求める。そして、ｚｍ＝（０）の場合（式（１）であればＣ＝１の場合）には情報（［ｋｍ］，［ｚｍ］）を削除する（Ｓ３４０）。ステップＳ３４０の削除は、残りの情報の数が、情報（［ｋｍ］，［ｚｍ］）の数とキーの値の数の少ない方になるまで削除すればよい。なお、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がもともとランダムに並んでいる場合は、ランダム置換は必要ないので削除手段３４０を省略してもよい。情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）がキーｋｍに基づいてソートされている場合は、ｚｍ＝（０）の確認結果を復元すると、キーの値が同じ情報が何個あるのか、何番目に境界があるのかなどのキーに関する情報が漏れてしまう。したがって、ランダム置換が必要となる。
【実施例２】
【００２１】
図１に実施例２のセキュア集合関数システムの構成例を示す。また、図３に実施例２のセキュア集合関数システムの処理フローを示す。実施例２のセキュア集合関数システムも、Ｎ個の秘密集合関数装置１０１，…，１０Ｎで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号、Ｔは（ｌｏｇ２Ｍ）−１以上の最小の整数、ｔは０以上Ｔ以下の整数、＾はべき乗を示す記号とする。また、実施例２では、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とする。
【００２２】
秘密集合関数装置１０ｎは、集合関数制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備え、秘密分散装置１００ｎ、記録部１９０ｎ、集合関数制御部３００ｎの初期化部３２０ｎ、削除部３４０ｎは実施例１と同じである。異なるのは、結合演算部３３０ｎである。つまり、初期化手段３２０と削除手段３４０は実施例１と同じであり、結合演算手段３３０が異なる。
【００２３】
実施例２の結合演算部３３０ｎは、第１結合部３３１ｎ、第２結合部３３２ｎ、第３結合部３３３ｎを備える。そして、第１結合手段３３１（図示していない）は第１結合部３３１１，…，３３１Ｎで構成され、第２結合手段３３２（図示していない）は第２結合部３３２１，…，３３２Ｎで構成され、第３結合手段３３３（図示していない）は第３結合部３３３１，…，３３３Ｎで構成される。また、結合演算手段３３０は、第１結合手段３３１、第２結合手段３３２、第３結合手段３３３を有する。
【００２４】
結合演算手段３３０は、ｔに０を代入する（Ｓ３３６）。第１結合手段３３１は、ｉ＝１，２，…，Ｍ−２＾ｔについて、ｋｉとｋｉ＋２＾ｔが等しいときには
ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔ
とし、等しくないときには
ｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔ
とする（Ｓ３３１）。より具体的には、第１結合部３３１１，…，３３１Ｎ（第１結合手段３３１）は、秘密分散装置１００１，…，１００Ｎに、ｉ＝１，２，…，Ｍ−２＾ｔについて、ｋｉとｋｉ＋２＾ｔが等しいかを、例えば式（１）の秘密計算で確認させる。そして、その結果に基づいて、ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔまたはｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔの秘密計算を実行させる。なお、ステップＳ３３１のｉ＝１，２，…，Ｍ−２＾ｔについての処理は、互いに影響しないため並列に処理できる。
【００２５】
第２結合手段３３２は、ｉ＝１，２，…，Ｍについて
ｚｉ＝ｚｉ’
とする（Ｓ３３２）。なお、ステップＳ３３２もｉ＝１，２，…，Ｍについての処理は互いに影響しないため、並列に処理できる。そして、結合演算手段３３０は、ｔ＝Ｔかを確認し（Ｓ３３７）、Ｙｅｓの場合にはステップＳ３３３に進み、Ｎｏの場合にはｔにｔ＋１を代入し（Ｓ３３８）、ステップＳ３３１に戻る。
【００２６】
ステップＳ３３３では、第３結合手段が、ｉ＝１，２，…，Ｍ−１について、ｋｉとｋｉ＋１が等しいときには
ｚｉ＝ｚｉ
とし、等しくないときには
ｚｉ＝（０）
とする（Ｓ３３３）。
【００２７】
なお、ステップＳ３２０とＳ３４０の処理は実施例１と同じである。
【００２８】
このように、結合演算手段３３０は、ｔ＝０，１，２，…，Ｔについて、第１結合手段３３１と第２結合手段３３２の処理（Ｓ３３１，Ｓ３３２）を繰返した後に第３結合手段３３３の処理（Ｓ３３３）を行う。また、ステップＳ３３１、Ｓ３３２は並列処理が可能なので、演算回数が多くなったとしても、繰返しの演算を順番に実行せざるを得ない実施例１の方法よりも高速の演算が可能である。より具体的に説明すると、実施例２のセキュア集合関数システムの計算量は、データ数Ｍに対しＯ（Ｍ ｌｏｇ Ｍ）となる。したがって、実施例１のＯ（Ｍ）よりも増加する。一方、実施例１は順番に処理する必要があるので、段数（直列に処理せざるを得ない計算数）もＯ（Ｍ）である。しかし、実施例２では大幅に並列度が上昇するので、段数はＯ（ｌｏｇ Ｍ）に減少する。
【実施例３】
【００２９】
図４に実施例３のセキュア集合関数システムの構成例を示す。また、図５に実施例３のセキュア集合関数システムの処理フローを示す。実施例３のセキュア集合関数システムも、Ｎ個の秘密集合関数装置１０１，…，１０Ｎで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求める。ここで、Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つような集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号、ｓはあらかじめ定めたＭ以下の整数、Ｋはキーｋｍの取り得る値の数とする。また、実施例３では、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とする。
【００３０】
秘密集合関数装置１０ｎは、集合関数制御部３００ｎ、秘密分散装置１００ｎ、記録部１９０ｎを備え、秘密分散装置１００ｎ、記録部１９０ｎ、集合関数制御部３００ｎの初期化部３２０ｎ、結合演算手段３３０、削除部３４０ｎは実施例１または実施例２と同じである。異なるのは、事前処理部３１０ｎである。つまり、初期化手段３２０と結合演算手段３３０と削除手段３４０は、実施例１または実施例２と同じである。
【００３１】
事前処理部３１０ｎは、第１事前初期化部３１１ｎ、第２事前初期化部３１２ｎ、事前結合部３１３ｎ、保存部３１４ｎ、第２事前繰返部３１５ｎ、事前削除部３１６ｎ、第１事前繰返部３１７ｎを有する。そして、第１事前初期化手段３１１（図示していない）は第１事前初期化部３１１１，…，３１１Ｎで構成され、第２事前初期化手段３１２（図示していない）は第２事前初期化部３１２１，…，３１２Ｎで構成され、事前結合手段３１３（図示していない）は事前結合部３１３１，…，３１３Ｎで構成され、保存手段３１４（図示していない）は保存部３１４１，…，３１４Ｎで構成され、第２事前繰返手段３１５（図示していない）は第２事前繰返部３１５１，…，３１５Ｎで構成され、事前削除手段３１６（図示していない）は事前削除部３１６１，…，３１６Ｎで構成され、第１事前繰返手段３１７（図示していない）は第１事前繰返部３１７１，…，３１７Ｎで構成される。また、事前処理手段３１０は、第１事前初期化手段３１１、第２事前初期化手段３１２、事前結合手段３１３、保存手段３１４、第２事前繰返手段３１５、事前削除手段３１６、第１事前繰返手段３１７を有する。
【００３２】
第１事前初期化手段３１１は、Ｍ’＝Ｍとする（Ｓ３１１）。第２事前初期化手段３１２は、ｔ＝０、Ｍ”＝Ｍ’とする（Ｓ３１２）。事前結合手段３１３は、ｔにｔ＋１を代入し、１からＭ”／２以下の最大の整数までのｉについて、ｋ２ｉ−１とｋ２ｉが等しいときには
ｚ２ｉ＝ｚ２ｉ−１（＋）ｚ２ｉ，ｚ２ｉ−１＝（０）
とし、等しくないときには
ｚ２ｉ＝ｚ２ｉ， ｚ２ｉ−１＝ｚ２ｉ−１
とする（Ｓ３１３）。なお、ｋ２ｉ−１とｋ２ｉとの比較は、事前結合部３１３１，…，３１３Ｎ（事前結合手段３１３）が、秘密分散装置１００１，…，１００Ｎに、例えば式（１）の論理式を用いた秘密計算を実行させればよい。また、異なるｉに対する演算同士は互いに影響を与えないので、異なるｉに対する演算は並列で行うことができる。
【００３３】
保存手段３１４は、奇数番目の情報（［ｋｍ’］，［ｚｍ’］）を抜き取って保存し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数を新しいＭ”とする（Ｓ３１４）。第２事前繰返手段３１５は、Ｍ”が２Ｋ以下か（第２事前繰返条件）を確認し、第２事前繰返条件を満たすまで事前結合手段３１３の処理（Ｓ３１３）と保存手段３１４の処理（Ｓ３１４）を繰り返す（Ｓ３１５）。
【００３４】
事前削除手段Ｓ３１６は、保存手段３１４が保存したすべての情報（［ｋｍ’］，［ｚｍ’］）と残った情報（［ｋｍ］，［ｚｍ］）とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを秘密計算で確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数をＭ’とする（Ｓ３１６）。なお、新しい情報（残りの情報）の数Ｍ’が
ｔＫ＋（最後のステップＳ３１５で残った情報の数）
になるまでステップＳ３１６で情報を削除できる。
【００３５】
第１事前繰返手段Ｓ３１７は、Ｍ’がｓより小さいか（第１事前繰返条件）を確認し、第１事前繰返条件を満たすまで第２事前初期化手段３１２の処理（Ｓ３１２）、事前結合手段３１３の処理（Ｓ３１３）、保存手段３１４の処理（Ｓ３１４）、第２事前繰返手段３１５（Ｓ３１５）、事前削除手段３１６（Ｓ３１６）を繰り返す（Ｓ３１７）。
【００３６】
そして、セキュア集合関数システムは、Ｍを、事前処理手段３１０の処理（Ｓ３１０）後の情報（［ｋｍ］，［ｚｍ］）の数に変更し、事前処理手段３１０の処理（Ｓ３１０）後の情報（［ｋｍ］，［ｚｍ］）に対して、実施例１または実施例２に示した初期化手段３２０の処理（Ｓ３２０）、結合演算手段３３０の処理（Ｓ３３０）、を実行する。
【００３７】
実施例３の事前処理手段３１０の処理は、情報の数Ｍがキーの取り得る値の数Ｋに比べて非常に大きい場合に演算量を減らす効果がある。一方、ＭとＫの値が近くなると実施例１や実施例２の結合演算手段３３０の処理（Ｓ３３０）の方が演算量を少なくできる。したがって、ＭがＫに比べて非常に大きいときに、事前処理手段３１０を用いて情報の数Ｍを少なくし、ＭがＫに近づいたところで実施例１や実施例２の結合演算手段３３０に切り替えて処理すれば効率的である。より具体的には、実施例３のセキュア集合関数システムの計算量はＯ（Ｍ＋ Ｋ ｌｏｇ Ｍ）であり、段数はＯ（ｌｏｇ Ｍ）である。あらかじめ定めるｓは、どの程度ＭがＫに近づいたところで切り替えるのかを定める値であり、全体の演算量が少なくなるように適宜決めればよい。このように、実施例３のセキュア集合関数システムによれば、情報の数Ｍがキーの取り得る値の数Ｋに比べて非常に大きい場合に演算量を減らすことができる。
【００３８】
［演算量の具体例］
情報の数Ｍ＝１０００、キーの取り得る値の数Ｋ＝１０とする。実施例３のステップＳ３１４の１回目でＭ”＝５００、２回目でＭ”＝２５０となり、６回目でＭ”＝１６となる。そして、ここまでの結合演算の回数は９８５回であり、残りの情報の数は次のようになる。
【００３９】
ｔＫ＋（最後のステップＳ３１５で残った情報の数）＝６×１０＋１６＝７６
これをもう一度繰り返すと、ｔ＝２でＭ”＝１９、結合演算の回数は５７回増えて１０４２回、残りの情報の数の最大値（実際にはこの数以下となる数）は２×１０＋１９＝３９となる。例えばｓを４０に設定していれば、ステップＳ３１７は終了し、ステップＳ３２０に進む。ステップＳ３２０，Ｓ３３０，Ｓ３４０を実施例１の方法で実行すれば、結合演算の回数は１０８０回、段数は４６段である。ステップＳ３２０，Ｓ３３０，Ｓ３４０を実施例２の方法で実行すれば、結合演算の回数は１２１３回、段数は１４段である。比較として、最初から実施例１の方法にした場合は、結合演算の回数は９９９回、段数は９９９段、実施例２の方法の場合の結合演算の回数は８９７７回、段数は１０段となり、情報の数Ｍがキーの取り得る値の数Ｋよりかなり大きい場合、実施例３の方法は計算量と段数のバランスに優れることが分かる。なお、従来の方法の場合、結合演算の回数は９９９０回、段数は１０段である。
【００４０】
［秘密計算］
上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下の説明では、秘密集合関数装置１０１，…，１０Ｎが実行するランダム置換とその他の秘密計算について説明する。なお、以下の秘密計算に関する説明は、１つの例でありこれに限定されるものではない。本発明のセキュア集合関数システムでは他の秘密計算を用いてもよい。
【００４１】
ランダム置換１
図６に本発明に利用できる秘密分散装置１００ｎの機能構成例を詳しく示したセキュア集合関数システムを示す。図７にランダム置換の１つ目の処理フロー例を示す。この例では、セキュア集合関数システムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密集合関数装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密集合関数装置１０ｎが記録するｋ番目の断片とする。なお、数値Ａ１，…，ＡＫが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密集合関数装置の内部に配置されてもよいし、単独の装置であってもよい。
【００４２】
セキュア集合関数システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００４３】
選択手段１０５は、Ｎ未満の数の秘密集合関数装置１０ｎを選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密集合関数装置を選べばよい。
【００４４】
断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密集合関数装置１０ｉ（ただし、ｉは選択された秘密集合関数装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密集合関数装置１０ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（Ｓ１１０）。全単射πは、１〜Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密集合関数装置１０ｉ間で生成してもよいし、選択された秘密集合関数装置１０ｉのうちの１つの秘密集合関数装置が生成して、選択された秘密集合関数装置１０ｉ間で共有してもよい。
【００４５】
再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）に対応する断片ａπ（ｋ）ｉ（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１，…，ｂｋＮを求め、数値Ｂｋの断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）＝Ｂｋの関係が成り立つが、選ばれなかった秘密集合関数装置は全単射πを知らないので、Ａπ（ｋ）＝Ｂｋであることを知らない。なお、各秘密集合関数装置１０ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密集合関数装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００４６】
本発明のセキュア集合関数システムによれば、限定された秘密集合関数装置間で断片をシャッフルする。したがって、選ばれなかった秘密集合関数装置は、全単射πを知らないので、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない。つまり、特定の秘密集合関数装置からは数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない状態にしたいのであれば、その秘密集合関数装置を選択手段１０５で選ばないように、選択する秘密集合関数装置をあらかじめ定めればよい。また、選択手段１０５が選ぶ秘密集合関数装置を変更しながらこの処理を繰り返し、全ての秘密集合関数装置が選ばれなかったことがある状態にすれば、全ての秘密集合関数装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。
【００４７】
ランダム置換２
次のランダム置換のためのセキュア集合関数システムの秘密分散装置１００ｎを詳細に示した機能構成例も図６に示す。図８にランダム置換の２つ目の処理フロー例を示す。この例でも、セキュア集合関数システムは選択手段１０５も備える。ここで、Ａ１，…，ＡＫを各秘密集合関数装置１０ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密集合関数装置１０ｎが記録する数値Ａｋの断片とする。
【００４８】
本発明のセキュア集合関数システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
【００４９】
選択手段１０５はランダム置換１と同じである。初期情報分散手段は、初期情報分散部１３０１，…，１３０Ｎで構成される。そして、選択手段１０５に選択された秘密集合関数装置１０ｉの初期情報分散部１３０ｉは、秘密集合関数装置１０１，…，１０Ｎのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１ｎ，…，ｐＫｎを秘密計算によって求め、記録部１９０ｎに記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密集合関数装置から、２つ以上の秘密集合関数装置を選定する。そして、選定された秘密集合関数装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密集合関数装置１０ｉ，１０ｊを選定し（ただし、ｉ≠ｊ）、秘密集合関数装置１０ｉが生成した数値の断片と、秘密集合関数装置１０ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密集合関数装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密集合関数装置を２つとしたが、２つ以上でもかまわない。
【００５０】
初期乗算手段は、初期乗算部１４０１，…，１４０Ｎで構成される。初期乗算部１４０１，…，１４０Ｎは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１４０）。
【００５１】
断片置換手段と再分散手段は、ランダム置換１と同じである。確認分散手段は、確認分散部１５０１，…，１５０Ｎで構成される。確認分散部１５０１，…，１５０Ｎは、ｋ＝１〜Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密集合関数装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密集合関数装置１０ｉが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密集合関数装置１０ｊが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密集合関数装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密集合関数装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。
【００５２】
確認乗算手段は、確認乗算部１６０１，…，１６０Ｎで構成される。確認乗算部１６０１，…，１６０Ｎは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、記録部１９０１，…，１９０Ｎに分散して記録する（Ｓ１６０）。
【００５３】
改ざん検出手段は、改ざん検出部１７０１，…，１７０Ｎで構成される。改ざん検出部１７０１，…，１７０Ｎは、ｋ＝１〜Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する（Ｓ１７０）。ｔｋｎ≠ｓπ（ｋ）ｎの場合には、改ざんがあったとして異常終了する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、選択手段で選択する秘密集合関数装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
【００５４】
［その他の秘密計算］
ここでは、セキュア集合関数システムが３個の秘密集合関数装置で構成された場合の秘密計算の例を示す。また、秘密集合関数装置１０１，１０２，１０３の番号を固定する必要はないので、秘密集合関数装置１０α，１０β，１０γと表現することにする。つまり、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれかである。
【００５５】
以下の秘密計算では、秘密集合関数装置１０α，１０β，１０γが分散して記録する数値Ａの断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）、数値Ｂの断片を（ｂγα，ｂαβ）、（ｂαβ，ｂβγ）、（ｂβγ，ｂγα）、数値Ｃの断片を（ｃγα，ｃαβ）、（ｃαβ，ｃβγ）、（ｃβγ，ｃγα）とする。なお、以下の説明では、Ｗを２以上のあらかじめ定めた整数とし、計算結果はＷで除した余りである。言い換えると、以下の説明の計算式では“ｍｏｄ Ｗ”を省略している。
【００５６】
数値Ａの秘密分散
（１）乱数ａαβ，ａβγを生成する。
（２）ａγα＝Ａ−ａαβ−ａβγを計算し、断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）とし、秘密集合関数装置１０α，１０β，１０γに分散して記録する。
【００５７】
数値Ａの復元
（１）秘密集合関数装置１０αは秘密集合関数装置１０βにａγαを送信し、秘密集合関数装置１０γにａαβを送信する。秘密集合関数装置１０βは秘密集合関数装置１０γにａαβを送信し、秘密集合関数装置１０αにａβγを送信する。秘密集合関数装置１０γは秘密集合関数装置１０αにａβγを送信し、秘密集合関数装置１０βにａγαを送信する。
（２）秘密集合関数装置１０αは秘密集合関数装置１０βから受信したａβγと秘密集合関数装置１０γから受信したａβγとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密集合関数装置１０βは秘密集合関数装置１０γから受信したａγαと秘密集合関数装置１０αから受信したａγαとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密集合関数装置１０γは秘密集合関数装置１０αから受信したａαβと秘密集合関数装置１０βから受信したａαβとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。
【００５８】
Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγα＋ｂγα，ａαβ＋ｂαβ）を計算して記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）＝（ａαβ＋ｂαβ，ａβγ＋ｂβγ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγ＋ｂβγ，ａγα＋ｂγα）を計算して記録する。
【００５９】
Ｃ＝Ａ−Ｂの秘密計算
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγα−ｂγα，ａαβ−ｂαβ）を計算して記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）＝（ａαβ−ｂαβ，ａβγ−ｂβγ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγ−ｂβγ，ａγα−ｂγα）を計算して記録する。
【００６０】
Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγα＋Ｓ，ａαβ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγ，ａγα＋Ｓ）を計算して記録する。秘密集合関数装置１０βの処理はない。
【００６１】
Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密集合関数装置１０αは（ｃγα，ｃαβ）＝（ａγαＳ，ａαβＳ）を計算して記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）＝（ａαβＳ，ａβγＳ）を計算して記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）＝（ａβγＳ，ａγαＳ）を計算して記録する。
【００６２】
Ｃ＝ＡＢの秘密計算
（１）秘密集合関数装置１０αは、乱数ｒ１，ｒ２，ｃγαを生成し、ｃαβ＝（ａγα＋ａαβ）（ｂγα＋ｂαβ）−ｒ１−ｒ２−ｃγαを計算する。そして、秘密集合関数装置１０αは、秘密集合関数装置１０βに（ｒ１，ｃαβ）を、秘密集合関数装置１０γに（ｒ２，ｃγα）を送信する。
（２）秘密集合関数装置１０βは、ｙ＝ａαβｂβγ＋ａβγｂαβ＋ｒ１を計算し、秘密集合関数装置１０γに送信する。
（３）秘密集合関数装置１０γは、ｚ＝ａβγｂγα＋ａγαｂβγ＋ｒ２を計算し、秘密集合関数装置１０αに送信する。
（４）秘密集合関数装置１０βと秘密集合関数装置１０γは、それぞれｃβγ＝ｙ＋ｚ＋ａβγｂβγを計算する。
（５）秘密集合関数装置１０αは（ｃγα，ｃαβ）を記録し、秘密集合関数装置１０βは（ｃαβ，ｃβγ）を記録し、秘密集合関数装置１０γは（ｃβγ，ｃγα）を記録する。
【００６３】
ビットＡの否定（Ｃ＝１−Ａ）の秘密計算
秘密集合関数装置１０αは
（ｃγα，ｃαβ）＝（１−ａγα，−ａαβ ｍｏｄ Ｗ）
を計算して記録し、秘密集合関数装置１０βは
（ｃαβ，ｃβγ）＝（−ａαβ ｍｏｄ Ｗ，−ａβγ ｍｏｄ Ｗ）
を計算して記録し、秘密集合関数装置１０γは
（ｃβγ，ｃγα）＝（−ａβγ ｍｏｄ Ｗ，１−ａγα）
を計算して記録する。
【００６４】
ビットの論理積（Ｃ＝Ａ∧Ｂ＝ＡＢ）の秘密計算
秘密集合関数装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行う。
【００６５】
ビットの論理和（Ｃ＝Ａ∨Ｂ＝Ａ＋Ｂ−ＡＢ）の秘密計算
（１）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密集合関数装置１０αが断片（ｃγα’，ｃαβ’）を、秘密集合関数装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密集合関数装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密集合関数装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密集合関数装置１０αが断片（ｃγα”，ｃαβ”）を、秘密集合関数装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密集合関数装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密集合関数装置１０α，１０β，１０γは、Ｓ＝−１として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）と同じ処理を行い、Ｃ’’’＝−Ｃ”の結果として、秘密集合関数装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密集合関数装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密集合関数装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密集合関数装置１０αが断片（ｃγα，ｃαβ）を、秘密集合関数装置１０βが断片（ｃαβ，ｃβγ）を、秘密集合関数装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００６６】
ビットの排他的論理和（Ｃ＝Ａ［∨］Ｂ＝Ａ＋Ｂ−２ＡＢ）の秘密計算
（１）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ’＝Ａ＋Ｂの結果として、秘密集合関数装置１０αが断片（ｃγα’，ｃαβ’）を、秘密集合関数装置１０βが断片（ｃαβ’，ｃβγ’）を、秘密集合関数装置１０γが断片（ｃβγ’，ｃγα’）を記録する。また、秘密集合関数装置１０α，１０β，１０γは、整数の乗算（Ｃ＝ＡＢ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ”＝ＡＢの結果として、秘密集合関数装置１０αが断片（ｃγα”，ｃαβ”）を、秘密集合関数装置１０βが断片（ｃαβ”，ｃβγ”）を、秘密集合関数装置１０γが断片（ｃβγ”，ｃγα”）を記録する。
（２）秘密集合関数装置１０α，１０β，１０γは、Ｓ＝−２として整数の乗算（Ｃ＝ＡＳ ｍｏｄ Ｗ）の秘密計算（ただし、Ｓは既知の定数）の秘密計算と同じ処理を行い、Ｃ’’’＝−２Ｃ”の結果として、秘密集合関数装置１０αが断片（ｃγα’’’，ｃαβ’’’）を、秘密集合関数装置１０βが断片（ｃαβ’’’，ｃβγ’’’）を、秘密集合関数装置１０γが断片（ｃβγ’’’，ｃγα’’’）を記録する。
（３）秘密集合関数装置１０α，１０β，１０γは、整数の加算（Ｃ＝Ａ＋Ｂ ｍｏｄ Ｗ）の秘密計算と同じ処理を行い、Ｃ＝Ｃ’＋Ｃ’’’の結果として、秘密集合関数装置１０αが断片（ｃγα，ｃαβ）を、秘密集合関数装置１０βが断片（ｃαβ，ｃβγ）を、秘密集合関数装置１０γが断片（ｃβγ，ｃγα）を記録する。
【００６７】
ビットＡ（ｎ），ｎ＝０，…，Ｎ−１の整数変換の秘密計算
ビットＡ（ｎ）の整数変換とは、
【００６８】
【数１】
【００６９】
を求めることである。また、秘密集合関数装置１０α，１０β，１０γが分散して記録するビットＡ（ｎ）の断片を（ａ（ｎ）γα，ａ（ｎ）αβ）、（ａ（ｎ）αβ，ａ（ｎ）βγ）、（ａ（ｎ）βγ，ａ（ｎ）γα）とする。秘密集合関数装置１０αは、
【００７０】
【数２】
【００７１】
を計算して記録し、秘密集合関数装置１０βは
【００７２】
【数３】
【００７３】
を計算して記録し、秘密集合関数装置１０γは
【００７４】
【数４】
【００７５】
を計算して記録する。
【００７６】
Ｎビットの整数Ａの二進数変換の秘密計算
ｘ（ｎ）は、ｘの下位ｎ＋１番目のビットを示すものとする。
（１）ｎ＝０からＮ−１について、秘密集合関数装置１０βが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）を秘密分散し、秘密集合関数装置１０α，１０β，１０γが（ａαβ＋ａβγ ｍｏｄ Ｗ）（ｎ）の断片（ｂ（ｎ）γα，ｂ（ｎ）αβ）、（ｂ（ｎ）αβ，ｂ（ｎ）βγ）、（ｂ（ｎ）βγ，ｂ（ｎ）γα）を分散して記録する。ｎ＝０からＮ−１について、秘密集合関数装置１０γが（ａγα）（ｎ）を秘密分散し、秘密集合関数装置１０α，１０β，１０γが（ａγα）（ｎ）の断片（（ａγα）（ｎ）γα，（ａγα）（ｎ）αβ）、（（ａγα）（ｎ）αβ，（ａγα）（ｎ）βγ）、（（ａγα）（ｎ）βγ，（ａγα）（ｎ）γα）を分散して記録する。
（２）ｃγα＝０とし、ｎ＝０からＮ−１について（２−１）から（２−３）の処理を繰返し実行する。
（２−１）ｄｎ＝ｂ（ｎ）＋（ａγα）（ｎ）−２ｂ（ｎ）（ａγα）（ｎ）
の秘密計算を実行し、ｄｎの断片を分散して記録する。
（２−２）ａ（ｎ）＝ｄｎ＋ｃｎ−２ｄｎｃｎ
の秘密計算を実行し、ａ（ｎ）の断片を分散して記録する。
（２−３）ｎ＜Ｎ−１であれば、
ｃｎ＋１＝ｂ（ｎ）（ａγα）（ｎ）＋ｄｎｃｎ−ｂ（ｎ）（ａγα）（ｎ）ｄｎｃｎ
の秘密計算を実行し、ｃｎ＋１の断片を分散して記録する。
【００７７】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００８３】
１０１，…，１０Ｎ 秘密集合関数装置 １００１，…，１００Ｎ 秘密分散装置
１０５ 選択手段 １１０１，…，１１０Ｎ 断片置換部
１２０１，…，１２０Ｎ 再分散部 １３０１，…，１３０Ｎ 初期情報分散部
１４０１，…，１４０Ｎ 初期乗算部 １５０１，…，１５０Ｎ 確認分散部
１６０１，…，１６０Ｎ 確認乗算部 １７０１，…，１７０Ｎ 改ざん検出部
１９０１，…，１９０Ｎ 記録部 ３００１，…，３００Ｎ 集合関数制御部
３１０ 事前処理手段 ３１０１，…，３１０Ｎ 事前処理部
３１１ 第１事前初期化手段 ３１１１，…，３１１Ｎ 第１事前初期化部
３１２ 第２事前初期化手段 ３１２１，…，３１２Ｎ 第２事前初期化部
３１３ 事前結合手段 ３１３１，…，３１３Ｎ 事前結合部
３１４ 保存手段 ３１４１，…，３１４Ｎ 保存部
３１５ 第２事前繰返手段 ３１５１，…，３１５Ｎ 第２事前繰返部
３１６ 事前削除手段 ３１６１，…，３１６Ｎ 事前削除部
３１７ 第１事前繰返手段 ３１７１，…，３１７Ｎ 第１事前繰返部
３２０ 初期化手段 ３２０１，…，３２０Ｎ 初期化部
３３０ 結合演算手段 ３３０１，…，３３０Ｎ 結合演算部
３３１ 第１結合手段 ３３１１，…，３３１Ｎ 第１結合部
３３２ 第２結合手段 ３３２１，…，３３２Ｎ 第２結合部
３３３ 第３結合手段 ３３３１，…，３３３Ｎ 第３結合部
３４０ 削除手段 ３４０１，…，３４０Ｎ 削除部
１０００ ネットワーク
【特許請求の範囲】
【請求項１】
Ｎ個の秘密集合関数装置Ｒ１，…，ＲＮで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求めるセキュア集合関数システムであって、
Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とし、
Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する初期化手段と、
キーｋｉとキーｋｊ（ただし、ｉ≠ｊ）とが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する結合演算手段と、
を備えるセキュア集合関数システム。
【請求項２】
請求項１記載のセキュア集合関数システムであって、
情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算手段の処理後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除手段
も備え、
前記結合演算手段は、
ｉを１からＭ−１まで順番に値を大きくしながら、ｊ＝ｉ＋１に対して前記結合処理を行う、または、ｉをＭから２まで順番に値を小さくしながら、ｊ＝ｉ−１に対して前記結合処理を行う
ことを特徴とするセキュア集合関数システム。
【請求項３】
請求項１記載のセキュア集合関数システムであって、
Ｔは（ｌｏｇ２Ｍ）−１以上の最小の整数、ｔは０以上Ｔ以下の整数、＾はべき乗を示す記号、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算手段の処理後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除手段
も備え、
前記結合演算手段は、
ｉ＝１，２，…，Ｍ−２＾ｔについて
ｋｉとｋｉ＋２＾ｔが等しいときには
ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔ
とし、等しくないときには
ｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔ
とする第１結合手段と、
ｉ＝１，２，…，Ｍについて
ｚｉ＝ｚｉ’
とする第２結合手段と、
ｉ＝１，２，…，Ｍ−１について、ｋｉとｋｉ＋１が等しいときには
ｚｉ＝ｚｉ
とし、等しくないときには
ｚｉ＝（０）
とする
とする第３結合手段と、
を有し、ｔ＝０，１，２，…，Ｔについて、前記第１結合手段と前記第２結合手段の処理を繰返した後に前記第３結合手段の処理を行う
ことを特徴とするセキュア集合関数システム。
【請求項４】
請求項２または３記載のセキュア集合関数システムであって、
ｓをあらかじめ定めたＭ以下の整数、Ｋはキーｋｍの取り得る値の数とし、
Ｍ’＝Ｍとする第１事前初期化手段と、
ｔ＝０、Ｍ”＝Ｍ’とする第２事前初期化手段と、
ｔにｔ＋１を代入し、
１からＭ”／２以下の最大の整数までのｉについて、ｋ２ｉ−１とｋ２ｉが等しいときには
ｚ２ｉ＝ｚ２ｉ−１（＋）ｚ２ｉ，ｚ２ｉ−１＝（０）
とし、等しくないときには
ｚ２ｉ＝ｚ２ｉ， ｚ２ｉ−１＝ｚ２ｉ−１
とする事前結合手段と、
奇数番目の情報（［ｋｍ’］，［ｚｍ’］）を抜き取って保存し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数を新しいＭ”とする保存手段と、
前記事前結合手段と前記保存手段の処理を、Ｍ”が２Ｋ以下になるまで繰り返す第２事前繰返手段と、
前記保存手段が保存したすべての情報（［ｋｍ’］，［ｚｍ’］）と残った情報（［ｋｍ］，［ｚｍ］）とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数をＭ’とする事前削除手段と、
前記第２事前初期化手段、前記事前結合手段、前記保存手段、前記第２事前繰返手段、前記事前削除手段の処理をＭ’がｓより小さくなるまで繰り返す第１事前繰返手段と
を有する事前処理手段も備え、
Ｍを、前記事前処理手段の処理後の情報（［ｋｍ］，［ｚｍ］）の数に変更し、前記事前処理手段の処理後の情報（［ｋｍ］，［ｚｍ］）に対して、前記初期化手段の処理を実行する
ことを特徴とするセキュア集合関数システム。
【請求項５】
キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求めるセキュア集合関数システムを構成するＮ個の秘密集合関数装置の中の秘密集合関数装置であって、
Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とし、
Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成するための初期化部と、
キーｋｉとキーｋｊ（ただし、ｉ≠ｊ）とが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行するための結合演算部と、
を備える秘密集合関数装置。
【請求項６】
Ｎ個の秘密集合関数装置Ｒ１，…，ＲＮを用いて、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求めるセキュア集合関数処理方法であって、
Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とし、
Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する初期化ステップと、
キーｋｉとキーｋｊ（ただし、ｉ≠ｊ）とが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する結合演算ステップと、
を有するセキュア集合関数処理方法。
【請求項７】
請求項６記載のセキュア集合関数処理方法であって、
情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算ステップ後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除ステップ
も有し、
前記結合演算ステップは、
ｉを１からＭ−１まで順番に値を大きくしながら、ｊ＝ｉ＋１に対して前記結合処理を行う、または、ｉをＭから２まで順番に値を小さくしながら、ｊ＝ｉ−１に対して前記結合処理を行う
ことを特徴とするセキュア集合関数処理方法。
【請求項８】
請求項６記載のセキュア集合関数処理方法であって、
Ｔは（ｌｏｇ２Ｍ）−１以上の最小の整数、ｔは０以上Ｔ以下の整数、＾はべき乗を示す記号、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算ステップ後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除ステップ
も有し、
前記結合演算ステップは、
ｉ＝１，２，…，Ｍ−２＾ｔについて
ｋｉとｋｉ＋２＾ｔが等しいときには
ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔ
とし、等しくないときには
ｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔ
とする第１結合サブステップと、
ｉ＝１，２，…，Ｍについて
ｚｉ＝ｚｉ’
とする第２結合サブステップと、
ｉ＝１，２，…，Ｍ−１について、ｋｉとｋｉ＋１が等しいときには
ｚｉ＝ｚｉ
とし、等しくないときには
ｚｉ＝（０）
とする
とする第３結合サブステップと、
を有し、ｔ＝０，１，２，…，Ｔについて、前記第１結合サブステップと前記第２結合サブステップを繰返した後に前記第３結合サブステップを行う
ことを特徴とするセキュア集合関数処理方法。
【請求項９】
請求項７または８記載のセキュア集合関数処理方法であって、
ｓをあらかじめ定めたＭ以下の整数、Ｋはキーｋｍの取り得る値の数とし、
Ｍ’＝Ｍとする第１事前初期化サブステップと、
ｔ＝０、Ｍ”＝Ｍ’とする第２事前初期化サブステップと、
ｔにｔ＋１を代入し、
１からＭ”／２以下の最大の整数までのｉについて、ｋ２ｉ−１とｋ２ｉが等しいときには
ｚ２ｉ＝ｚ２ｉ−１（＋）ｚ２ｉ，ｚ２ｉ−１＝（０）
とし、等しくないときには
ｚ２ｉ＝ｚ２ｉ， ｚ２ｉ−１＝ｚ２ｉ−１
とする事前結合サブステップと、
奇数番目の情報（［ｋｍ’］，［ｚｍ’］）を抜き取って保存し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数を新しいＭ”とする保存サブステップと、
前記事前結合サブステップと前記保存サブステップを、Ｍ”が２Ｋ以下になるまで繰り返す第２事前繰返サブステップと、
前記保存サブステップが保存したすべての情報（［ｋｍ’］，［ｚｍ’］）と残った情報（［ｋｍ］，［ｚｍ］）とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数をＭ’とする事前削除サブステップと、
前記第２事前初期化サブステップ、前記事前結合サブステップ、前記保存サブステップ、前記第２事前繰返サブステップ、前記事前削除サブステップをＭ’がｓより小さくなるまで繰り返す第１事前繰返サブステップと
を有する事前処理ステップも有し、
Ｍを、前記事前処理ステップ後の情報（［ｋｍ］，［ｚｍ］）の数に変更し、前記事前処理ステップ後の情報（［ｋｍ］，［ｚｍ］）に対して、前記初期化ステップの処理を実行する
ことを特徴とするセキュア集合関数処理方法。
【請求項１０】
請求項１から４のいずれかに記載のセキュア集合関数システムの各秘密集合関数装置としてコンピュータを機能させるためのセキュア集合関数プログラム。
【請求項１】
Ｎ個の秘密集合関数装置Ｒ１，…，ＲＮで構成され、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求めるセキュア集合関数システムであって、
Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とし、
Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する初期化手段と、
キーｋｉとキーｋｊ（ただし、ｉ≠ｊ）とが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する結合演算手段と、
を備えるセキュア集合関数システム。
【請求項２】
請求項１記載のセキュア集合関数システムであって、
情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算手段の処理後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除手段
も備え、
前記結合演算手段は、
ｉを１からＭ−１まで順番に値を大きくしながら、ｊ＝ｉ＋１に対して前記結合処理を行う、または、ｉをＭから２まで順番に値を小さくしながら、ｊ＝ｉ−１に対して前記結合処理を行う
ことを特徴とするセキュア集合関数システム。
【請求項３】
請求項１記載のセキュア集合関数システムであって、
Ｔは（ｌｏｇ２Ｍ）−１以上の最小の整数、ｔは０以上Ｔ以下の整数、＾はべき乗を示す記号、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算手段の処理後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除手段
も備え、
前記結合演算手段は、
ｉ＝１，２，…，Ｍ−２＾ｔについて
ｋｉとｋｉ＋２＾ｔが等しいときには
ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔ
とし、等しくないときには
ｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔ
とする第１結合手段と、
ｉ＝１，２，…，Ｍについて
ｚｉ＝ｚｉ’
とする第２結合手段と、
ｉ＝１，２，…，Ｍ−１について、ｋｉとｋｉ＋１が等しいときには
ｚｉ＝ｚｉ
とし、等しくないときには
ｚｉ＝（０）
とする
とする第３結合手段と、
を有し、ｔ＝０，１，２，…，Ｔについて、前記第１結合手段と前記第２結合手段の処理を繰返した後に前記第３結合手段の処理を行う
ことを特徴とするセキュア集合関数システム。
【請求項４】
請求項２または３記載のセキュア集合関数システムであって、
ｓをあらかじめ定めたＭ以下の整数、Ｋはキーｋｍの取り得る値の数とし、
Ｍ’＝Ｍとする第１事前初期化手段と、
ｔ＝０、Ｍ”＝Ｍ’とする第２事前初期化手段と、
ｔにｔ＋１を代入し、
１からＭ”／２以下の最大の整数までのｉについて、ｋ２ｉ−１とｋ２ｉが等しいときには
ｚ２ｉ＝ｚ２ｉ−１（＋）ｚ２ｉ，ｚ２ｉ−１＝（０）
とし、等しくないときには
ｚ２ｉ＝ｚ２ｉ， ｚ２ｉ−１＝ｚ２ｉ−１
とする事前結合手段と、
奇数番目の情報（［ｋｍ’］，［ｚｍ’］）を抜き取って保存し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数を新しいＭ”とする保存手段と、
前記事前結合手段と前記保存手段の処理を、Ｍ”が２Ｋ以下になるまで繰り返す第２事前繰返手段と、
前記保存手段が保存したすべての情報（［ｋｍ’］，［ｚｍ’］）と残った情報（［ｋｍ］，［ｚｍ］）とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数をＭ’とする事前削除手段と、
前記第２事前初期化手段、前記事前結合手段、前記保存手段、前記第２事前繰返手段、前記事前削除手段の処理をＭ’がｓより小さくなるまで繰り返す第１事前繰返手段と
を有する事前処理手段も備え、
Ｍを、前記事前処理手段の処理後の情報（［ｋｍ］，［ｚｍ］）の数に変更し、前記事前処理手段の処理後の情報（［ｋｍ］，［ｚｍ］）に対して、前記初期化手段の処理を実行する
ことを特徴とするセキュア集合関数システム。
【請求項５】
キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求めるセキュア集合関数システムを構成するＮ個の秘密集合関数装置の中の秘密集合関数装置であって、
Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とし、
Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成するための初期化部と、
キーｋｉとキーｋｊ（ただし、ｉ≠ｊ）とが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行するための結合演算部と、
を備える秘密集合関数装置。
【請求項６】
Ｎ個の秘密集合関数装置Ｒ１，…，ＲＮを用いて、キーｋｍと属性値ｖｍを含むＭ個の情報（ｋ１，ｖ１），…，（ｋＭ，ｖＭ）がそれぞれ秘密分散された情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）から、秘密分散された集計結果を求めるセキュア集合関数処理方法であって、
Ｍは２以上の整数、Ｎは３以上の整数、ｍ，ｉ，ｊは１以上Ｍ以下の整数、［］はカッコ内の情報が要素ごとに秘密分散された情報を示す記号、（＋）は単位元が存在し結合律と可換律が成り立つ前記集計結果を求めるための演算を示す記号、（０）は演算（＋）の単位元を示す記号とし、
Ｍ個のデータｚ１，…，ｚＭを、ｚｍ＝ｖｍのように設定し、情報（［ｋ１］，［ｚ１］），…，（［ｋＭ］，［ｚＭ］）を生成する初期化ステップと、
キーｋｉとキーｋｊ（ただし、ｉ≠ｊ）とが等しいときには
ｚｊ＝ｚｉ（＋）ｚｊ，ｚｉ＝（０）
とし、等しくないときには
ｚｊ＝ｚｊ，ｚｉ＝ｚｉ
とする結合処理を、すべての等しいキーを持つ情報に対して秘密計算で実行する結合演算ステップと、
を有するセキュア集合関数処理方法。
【請求項７】
請求項６記載のセキュア集合関数処理方法であって、
情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算ステップ後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除ステップ
も有し、
前記結合演算ステップは、
ｉを１からＭ−１まで順番に値を大きくしながら、ｊ＝ｉ＋１に対して前記結合処理を行う、または、ｉをＭから２まで順番に値を小さくしながら、ｊ＝ｉ−１に対して前記結合処理を行う
ことを特徴とするセキュア集合関数処理方法。
【請求項８】
請求項６記載のセキュア集合関数処理方法であって、
Ｔは（ｌｏｇ２Ｍ）−１以上の最小の整数、ｔは０以上Ｔ以下の整数、＾はべき乗を示す記号、情報（［ｋ１］，［ｖ１］），…，（［ｋＭ］，［ｖＭ］）はキーｋｍに基づいてソートされた情報とし、
前記結合演算ステップ後に、Ｍ個の情報（［ｋｍ］，［ｚｍ］）を秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除する削除ステップ
も有し、
前記結合演算ステップは、
ｉ＝１，２，…，Ｍ−２＾ｔについて
ｋｉとｋｉ＋２＾ｔが等しいときには
ｚｉ＋２＾ｔ’＝ｚｉ（＋）ｚｉ＋２＾ｔ
とし、等しくないときには
ｚｉ＋２＾ｔ’＝ｚｉ＋２＾ｔ
とする第１結合サブステップと、
ｉ＝１，２，…，Ｍについて
ｚｉ＝ｚｉ’
とする第２結合サブステップと、
ｉ＝１，２，…，Ｍ−１について、ｋｉとｋｉ＋１が等しいときには
ｚｉ＝ｚｉ
とし、等しくないときには
ｚｉ＝（０）
とする
とする第３結合サブステップと、
を有し、ｔ＝０，１，２，…，Ｔについて、前記第１結合サブステップと前記第２結合サブステップを繰返した後に前記第３結合サブステップを行う
ことを特徴とするセキュア集合関数処理方法。
【請求項９】
請求項７または８記載のセキュア集合関数処理方法であって、
ｓをあらかじめ定めたＭ以下の整数、Ｋはキーｋｍの取り得る値の数とし、
Ｍ’＝Ｍとする第１事前初期化サブステップと、
ｔ＝０、Ｍ”＝Ｍ’とする第２事前初期化サブステップと、
ｔにｔ＋１を代入し、
１からＭ”／２以下の最大の整数までのｉについて、ｋ２ｉ−１とｋ２ｉが等しいときには
ｚ２ｉ＝ｚ２ｉ−１（＋）ｚ２ｉ，ｚ２ｉ−１＝（０）
とし、等しくないときには
ｚ２ｉ＝ｚ２ｉ， ｚ２ｉ−１＝ｚ２ｉ−１
とする事前結合サブステップと、
奇数番目の情報（［ｋｍ’］，［ｚｍ’］）を抜き取って保存し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数を新しいＭ”とする保存サブステップと、
前記事前結合サブステップと前記保存サブステップを、Ｍ”が２Ｋ以下になるまで繰り返す第２事前繰返サブステップと、
前記保存サブステップが保存したすべての情報（［ｋｍ’］，［ｚｍ’］）と残った情報（［ｋｍ］，［ｚｍ］）とを一緒にした上で、秘密計算でランダム置換し、ランダム置換後のｚｍが（０）かを確認し、ｚｍ＝（０）の場合には情報（［ｋｍ］，［ｚｍ］）を削除し、残った情報を新しい情報（［ｋｍ］，［ｚｍ］）とし、新しい情報（［ｋｍ］，［ｚｍ］）の数をＭ’とする事前削除サブステップと、
前記第２事前初期化サブステップ、前記事前結合サブステップ、前記保存サブステップ、前記第２事前繰返サブステップ、前記事前削除サブステップをＭ’がｓより小さくなるまで繰り返す第１事前繰返サブステップと
を有する事前処理ステップも有し、
Ｍを、前記事前処理ステップ後の情報（［ｋｍ］，［ｚｍ］）の数に変更し、前記事前処理ステップ後の情報（［ｋｍ］，［ｚｍ］）に対して、前記初期化ステップの処理を実行する
ことを特徴とするセキュア集合関数処理方法。
【請求項１０】
請求項１から４のいずれかに記載のセキュア集合関数システムの各秘密集合関数装置としてコンピュータを機能させるためのセキュア集合関数プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１５４９６８（Ｐ２０１２−１５４９６８Ａ）
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願番号】特願２０１１−１１２３３（Ｐ２０１１−１１２３３）
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]