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