(57)【特許請求の範囲】
【請求項１】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置と、前記データベースの検索条件の入力および検索結果の出力を行う検索者装置とを備え、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、
前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数５】
0005975490.tif 000006
が閾値θn／θd（ただし、θn、θdはθn≦θdを満たす自然数）以上の数列データｐiが、前記データベースに含まれているかを調べる、以下のステップを有する検索方法。
（１）前記検索者装置が、加法準同型性を有する暗号の公開鍵及び秘密鍵を生成する。
（２）前記検索者装置が、クエリー数列データｑの入力を受け付ける。
（３）前記検索者装置が、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜を求め、当該要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化すると共に、前記クエリー数列データｑの各要素ｑj（ただし、ｊ＝１，・・・ｎ：ｎはクエリー数列ｑの長さ）の値を前記公開鍵で暗号化する。
（４）前記検索者装置が、前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を前記管理装置に対して出力する。
（５）前記管理装置が、前記検索者装置から出力された前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を受け取る。
（６）前記管理装置が、前記データベースから一の数列データｐiを読み出す。
（７）前記管理装置が、前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化する。
（８）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（９）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）に対して、平文において（｜ｐi∩ｑ｜）を｛γ（θd−θn）＋θn（μa＋μb）｝回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb））を求める。
（１０）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）に対して平文において（−｜ｑ｜）をμa回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜））を求めるとともに、前記暗号値Ｅｎｃ（−｜ｐi｜）に対して平文において（−｜ｐi｜）をμb回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μb（−｜ｐi｜））を求め、前記暗号値Ｅｎｃ（μa（−｜ｑ｜））と前記暗号値Ｅｎｃ（μb（−｜ｐi｜））に対して平文におけるμa（−｜ｑ｜）＋μb（−｜ｐi｜）に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））を求め、さらに、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対して平文において（μa（−｜ｑ｜）＋μb（−｜ｐi｜））をθn回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））を求める。
（１１）前記管理装置が、暗号の加法準同型性を利用して、上記（９）で求めた暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝と、上記（１０）で求めた暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））に対して、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）をスコアＴiの暗号値として求める。（１２）前記管理装置が、前記データベースに含まれる複数の数列データｐiのそれぞれについて、上記（６）から（１１）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（１３）前記管理装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
（１４）前記検索者装置が、前記管理装置から出力された前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を受け取る。
（１５）前記検索者装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を前記秘密鍵で復号する。
（１６）前記検索者装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの非負／負を判定する。
（１７）前記検索者装置が、判定結果を出力する。
【請求項２】
前記暗号は、確率暗号である請求項１に記載の検索方法。
【請求項３】
平文における加算に対応する計算は、暗号値における乗算である請求項１または２に記載の検索方法。
【請求項４】
前記管理装置は、暗号の加法準同型性を利用して、上記（１１）で求めたスコアＴiの暗号値に対して、平文において（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））をｒ回（ｒは乱数）加算する計算に対応する計算を行い、求められた暗号値Ｅｎｃ（［（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝］×ｒ）をスコアＴiの暗号値とするステップを有する請求項１〜３のいずれかに記載の検索方法。
【請求項５】
前記管理装置は、値（−ｓi）（ただし、ｓiはｒi＞ｓiを満たす自然数）を前記公開鍵によって暗号化して暗号値Ｅｎｃ（−ｓi）を求め、暗号の加法準同型性を利用して、暗号値Ｅｎｃ（（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）×ｒi）と前記暗号値Ｅｎｃ（−ｓi）に対して平文における［（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝］×ｒi＋（−ｓi）に対応する計算を行い、求めた暗号値Ｅｎｃ（［（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝］×ｒi）−ｓi）をスコアＴiの暗号値とするステップを有する請求項４に記載の検索方法。
【請求項６】
前記管理装置は、乱数ｒiを前記公開鍵で暗号化して暗号値Ｅｎｃ（ｒi）を求め、暗号の加法準同型性を利用して、上記（１１）で求めたスコアＴiの暗号値と前記暗号値Ｅｎｃ（ｒi）に対し、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））＋ｒiに対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝＋ｒ）をランダムシェアＲiの暗号値として求め、
上記（１６）の非負／負を判定するステップは、
（１６−１）前記検索者装置が、Secure Function Evaluationを利用して設計された秘匿回路に、前記ランダムシェアＲiを送信し、
（１６−２）前記管理装置が、前記秘匿回路に乱数ｒiを送信し、
（１６−３）前記秘匿回路が、前記ランダムシェアＲiから乱数ｒiを減算し、求められた値の非負／負を判定し、
（１６−４）前記秘匿回路が、前記検索者装置に非負／負の判定結果を送信する、請求項１〜３のいずれかに記載の検索方法。
【請求項７】
上記（１３）において、前記管理装置が前記データベースに記憶されたデータの順序と異なる順序で、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を出力する請求項１〜６のいずれかに記載の検索方法。
【請求項８】
前記検索者装置は、Ｔｖｅｒｓｋｙ係数Ｓiに含まれる係数μa／γ、μb／γないし値θn／θdのいずれかの入力を受け付けるステップと、入力された係数μa／γ、μb／γないし値θn／θdのいずれかを前記管理装置に対して出力するステップとを有する請求項１〜７のいずれかに記載の検索方法。
【請求項９】
前記管理装置が、ダミーのスコアＴｄ1，Ｔｄ2，…Ｔｄkを生成し、生成したダミーのスコアＴｄ1，Ｔｄ2，…Ｔｄkを、前記公開鍵によって暗号化するステップと、
前記管理装置が、ダミーのスコアＴｄ1，Ｔｄ2，…Ｔｄkの暗号値と前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値の出力順序をランダムに並び替えるステップと、
を備え、
上記（１３）において、前記管理装置が、ランダムに並び替えた暗号値と、ダミーのスコアに含まれる非負のダミーのスコアの個数と負のダミーのスコアの個数のデータとを前記検索者装置に送信する請求項１〜３のいずれかに記載の検索方法。
【請求項１０】
前記管理装置が、前記検索者装置から送信された前記クエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑｉ）が「１」または「０」を暗号化したものであるか否かを判定するステップを備え、前記クエリー数列データｑに「１」または「０」を暗号化したものでない暗号値が含まれている場合には、以降の処理を行わないで検索を終了する請求項１〜９のいずれかに記載の検索方法。
【請求項１１】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置と、前記データベースの検索条件の入力および検索結果の出力を行う検索者装置とを備え、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、
前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数６】
0005975490.tif 000007
が閾値θ（０＜θ≦１）以上の数列データｐiが前記データベースに含まれているかを調べる、以下のステップを有する検索方法。
（１）前記検索者装置が、乗法準同型性および加法準同型性を有する暗号の公開鍵及び秘密鍵を生成する。
（２）前記検索者装置が、クエリー数列データｑの入力を受け付ける。
（３）前記検索者装置が、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜を求め、当該要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化すると共に、前記クエリー数列データｑの各要素ｑj（ただし、ｊ＝１，・・・ｎ：ｎはクエリー数列ｑの長さ）の値を前記公開鍵で暗号化する。
（４）前記検索者装置が、前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を前記管理装置に対して出力する。
（５）前記管理装置が、前記検索者装置から出力された前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各値の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を受け取る。
（６）前記管理装置が、前記データベースから一の数列データｐiを読み出す。
（７）前記管理装置が、前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化し、暗号値Ｅｎｃ（−｜ｐi｜）を得る。
（８）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（９）前記管理装置が、値（１＋θα＋θβ−θ）を前記公開鍵によって暗号化して暗号値Ｅｎｃ（１＋θα＋θβ−θ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）と前記暗号値Ｅｎｃ（１＋θα＋θβ−θ）に対して平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）に対応する計算を行って暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））を求める。
（１０）前記管理装置が、値θαおよび値θβを前記公開鍵で暗号化して暗号値Ｅｎｃ（θα）と暗号値（θβ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）と前記暗号値Ｅｎｃ（θα）に対して平文における−｜ｑ｜×θαに対応する計算を行って暗号値Ｅｎｃ（−｜ｑ｜×θα）を求めると共に、前記暗号値Ｅｎｃ（−｜ｐi｜）と前記暗号値Ｅｎｃ（θβ）に対して平文における−｜ｐi｜×θβに対応する計算を行って暗号値Ｅｎｃ（−｜ｐi｜×θβ）を求め、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜×θα）と前記暗号値Ｅｎｃ（−｜ｐi｜×θβ）に対して平文における（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））を求める。
（１１）前記管理装置が、暗号の加法準同型性を利用して、上記（９）で求めた暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））と、上記（１０）で求めた暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））に対して、平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））をスコアＴiの暗号値として求める。
（１２）前記管理装置が、前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、上記（６）から（１１）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（１３）前記管理装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
（１４）前記検索者装置が、前記管理装置から出力された前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を受け取る。
（１５）前記検索者装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を前記秘密鍵で復号する。
（１６）前記検索者装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの非負／負を判定する。
（１７）前記検索者装置が、判定結果を出力する。
【請求項１２】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置が、検索者装置にて入力された検索条件に基づいて検索を行う方法であって、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数７】
0005975490.tif 000008
が閾値θn／θd（ただし、θn、θdはθn≦θdを満たす自然数）以上か否かを値の非負／負によって示したスコアＴiの暗号値を前記検索者装置に返す、以下のステップを有する検索方法。
（１）前記管理装置が、前記検索者装置にて生成された加法準同型性を有する暗号の公開鍵と、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化した暗号値Ｅｎｃ（−｜ｑ｜）と、前記クエリー数列データｑの各要素を前記公開鍵で暗号化した暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）とを受け取る。
（２）前記管理装置が、前記データベースから一の数列データｐiを読み出す。
（３）前記管理装置が、前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化する。
（４）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（５）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）に対して、平文において（｜ｐi∩ｑ｜）を｛γ（θd−θn）＋θn（μa＋μb）｝回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb））を求める。
（６）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）に対して平文において（−｜ｑ｜）をμa回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜））を求めるとともに、前記暗号値Ｅｎｃ（−｜ｐi｜）に対して平文において（−｜ｐi｜）をμb回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μb（−｜ｐi｜））を求め、前記暗号値Ｅｎｃ（μa（−｜ｑ｜））と前記暗号値Ｅｎｃ（μb（−｜ｐi｜））に対して平文におけるμa（−｜ｑ｜）＋μb（−｜ｐi｜）に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））を求め、さらに、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対して平文において（μa（−｜ｑ｜）＋μb（−｜ｐi｜））をθn回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））を求める。
（７）前記管理装置が、暗号の加法準同型性を利用して、上記（５）で求めた暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝と、上記（６）で求めた暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））に対して、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）をスコアＴiの暗号値として求める。
（８）前記管理装置が、前記データベースに含まれる複数の数列データｐiのそれぞれについて、上記（２）から（７）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（９）前記管理装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
【請求項１３】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置が、検索者装置にて入力された検索条件に基づいて検索を行う方法であって、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数８】
0005975490.tif 000009
が閾値θ（０＜θ≦１）以上か否かを値の非負／負によって示したスコアＴiの暗号値を前記検索者装置に返す、以下のステップを有する検索方法。
（１）前記管理装置が、前記検索者装置にて生成された乗法準同型性および加法準同型性を有する暗号の公開鍵と、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化した暗号値Ｅｎｃ（−｜ｑ｜）と、前記クエリー数列データｑの各要素を前記公開鍵で暗号化した暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）とを受け取る。
（２）前記管理装置が、前記データベースから一の数列データｐiを読み出す。
（３）前記管理装置が、前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化し、暗号値Ｅｎｃ（−｜ｐi｜）を得る。
（４）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｉ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（５）前記管理装置が、値（１＋θα＋θβ−θ）を前記公開鍵によって暗号化して暗号値Ｅｎｃ（１＋θα＋θβ−θ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）と前記暗号値Ｅｎｃ（１＋θα＋θβ−θ）に対して平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）に対応する計算を行って暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））を求める。
（６）前記管理装置が、値θαおよび値θβを前記公開鍵で暗号化して暗号値Ｅｎｃ（θα）と暗号値（θβ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）と前記暗号値Ｅｎｃ（θα）に対して平文における−｜ｑ｜×θαに対応する計算を行って暗号値Ｅｎｃ（−｜ｑ｜×θα）を求めると共に、前記暗号値Ｅｎｃ（−｜ｐi｜）と前記暗号値Ｅｎｃ（θβ）に対して平文における−｜ｐi｜×θβに対応する計算を行って暗号値Ｅｎｃ（−｜ｐi｜×θβ）を求め、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜×θα）と前記暗号値Ｅｎｃ（−｜ｐi｜×θβ）に対して平文における（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））を求める。
（７）前記管理装置が、暗号の加法準同型性を利用して、上記（５）で求めた暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））と、上記（６）で求めた暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））に対して、平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））をスコアＴの暗号値として求める。
（８）前記管理装置が、前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、上記（２）から（７）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（９）前記管理装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
【請求項１４】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置にて実行され、検索者装置にて入力された検索条件に基づいて検索を行うプログラムであって、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数９】
0005975490.tif 000010
が閾値θn／θd（ただし、θn、θdはθn≦θdを満たす自然数）以上か否かを値の非負／負によって示したスコアＴiの暗号値を前記検索者装置に返す、以下のステップを前記管理装置に実行させるプログラム。
（１）前記検索者装置にて生成された加法準同型性を有する暗号の公開鍵と、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化した暗号値Ｅｎｃ（−｜ｑ｜）と、前記クエリー数列データｑの各要素を前記公開鍵で暗号化した暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）とを受け取る。
（２）前記データベースから一の数列データｐiを読み出す。
（３）前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化する。
（４）前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（５）暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）に対して、平文において（｜ｐi∩ｑ｜）を｛γ（θd−θn）＋θn（μa＋μb）｝回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb））を求める。
（６）暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）に対して平文において（−｜ｑ｜）をμa回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜））を求めるとともに、前記暗号値Ｅｎｃ（−｜ｐi｜）に対して平文において（−｜ｐi｜）をμb回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μb（−｜ｐi｜））を求め、前記暗号値Ｅｎｃ（μa（−｜ｑ｜））と前記暗号値Ｅｎｃ（μb（−｜ｐi｜））に対して平文におけるμa（−｜ｑ｜）＋μb（−｜ｐi｜）に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））を求め、さらに、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対して平文において（μa（−｜ｑ｜）＋μb（−｜ｐi｜））をθn回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））を求める。
（７）暗号の加法準同型性を利用して、上記（５）で求めた暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝と、上記（６）で求めた暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））に対して、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）をスコアＴiの暗号値として求める。
（８）前記データベースに含まれる複数の数列データｐiのそれぞれについて、上記（２）から（７）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（９）前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
【請求項１５】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置にて実行され、検索者装置にて入力された検索条件に基づいて検索を行うプログラムであって、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数１０】
0005975490.tif 000011
が閾値θ（０＜θ≦１）以上か否かを値の非負／負によって示したスコアＴの暗号値を前記検索者装置に返す、以下のステップを前記管理装置に実行させるプログラム。
（１）前記検索者装置にて生成された乗法準同型性および加法準同型性を有する暗号の公開鍵と、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化した暗号値Ｅｎｃ（−｜ｑ｜）と、前記クエリー数列データｑの各要素を前記公開鍵で暗号化した暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）とを受け取る。
（２）前記データベースから一の数列データｐiを読み出す。
（３）前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化し、暗号値Ｅｎｃ（−｜ｐi｜）を得る。
（４）前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（５）値（１＋θα＋θβ−θ）を前記公開鍵によって暗号化して暗号値Ｅｎｃ（１＋θα＋θβ−θ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）と前記暗号値Ｅｎｃ（１＋θα＋θβ−θ）に対して平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）に対応する計算を行って暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））を求める。
（６）値θαおよび値θβを前記公開鍵で暗号化して暗号値Ｅｎｃ（θα）と暗号値（θβ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）と前記暗号値Ｅｎｃ（θα）に対して平文における−｜ｑ｜×θαに対応する計算を行って暗号値Ｅｎｃ（−｜ｑ｜×θα）を求めると共に、前記暗号値Ｅｎｃ（−｜ｐi｜）と前記暗号値Ｅｎｃ（θβ）に対して平文における−｜ｐi｜×θβに対応する計算を行って暗号値Ｅｎｃ（−｜ｐi｜×θβ）を求め、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜×θα）と前記暗号値Ｅｎｃ（−｜ｐi｜×θβ）に対して平文における（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））を求める。
（７）暗号の加法準同型性を利用して、上記（５）で求めた暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））と、上記（６）で求めた暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））に対して、平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））をスコアＴiの暗号値として求める。
（８）前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、上記（２）から（７）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（９）前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
【請求項１６】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置と、前記データベースの検索条件の入力および検索結果の出力を行う検索者装置とを備え、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、
前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数１１】
0005975490.tif 000012
が閾値θn／θd（ただし、θn、θdはθn≦θdを満たす自然数）以上の数列データｐiが、前記データベースに含まれているかを調べる検索システムであって、
前記検索者装置は、
加法準同型性を有する暗号の公開鍵及び秘密鍵を生成する手段と、
クエリー数列データｑの入力を受け付ける手段と、
前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜を求め、当該要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化すると共に、前記クエリー数列データｑの各要素ｑj（ただし、ｊ＝１，・・・ｎ：ｎはクエリー数列ｑの長さ）の値を前記公開鍵で暗号化する手段と、
前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を前記管理装置に対して出力する手段と、
前記管理装置から出力された前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を受け取る手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を前記秘密鍵で復号する手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの非を判定する手段と、
判定結果を出力する手段と、
を備え、
前記管理装置は、
前記検索者装置から出力された前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を受け取る手段と、
前記データベースから数列データｐiを読み出す手段と、
前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、スコアＴiの暗号値を求める演算手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する手段と、
を備え、
前記演算手段は、以下の処理を行う検索システム。
（１）前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化する。
（２）前記数列データｐiの各要素ｐi.j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（３）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）に対して、平文において（｜ｐi∩ｑ｜）を｛γ（θd−θn）＋θn（μa＋μb）｝回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb））を求める。
（４）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）に対して平文において（−｜ｑ｜）をμa回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜））を求めるとともに、前記暗号値Ｅｎｃ（−｜ｐi｜）に対して平文において（−｜ｐi｜）をμb回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μb（−｜ｐi｜））を求め、前記暗号値Ｅｎｃ（μa（−｜ｑ｜））と前記暗号値Ｅｎｃ（μb（−｜ｐi｜））に対して平文におけるμa（−｜ｑ｜）＋μb（−｜ｐi｜）に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））を求め、さらに、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対して平文において（μa（−｜ｑ｜）＋μb（−｜ｐi｜））をθn回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））を求める。
（５）前記管理装置が、暗号の加法準同型性を利用して、上記（３）で求めた暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝と、上記（４）で求めた暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））に対して、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）をスコアＴiの暗号値として求める。
（６）前記管理装置が、前記データベースに含まれる複数の数列データｐiのそれぞれについて、上記（１）から（５）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
【請求項１７】
物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置と、前記データベースの検索条件の入力および検索結果の出力を行う検索者装置とを備え、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データであり、
前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数１２】
0005975490.tif 000013
が閾値θ（０＜θ≦１）以上の数列データｐiが前記データベースに含まれているかを調べる検索システムであって、
前記検索者装置は、
乗法準同型性および加法準同型性を有する暗号の公開鍵及び秘密鍵を生成する手段と、
クエリー数列データｑの入力を受け付ける手段と、
前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜を求め、当該要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化すると共に、前記クエリー数列データｑの各要素ｑj（ただし、ｊ＝１，・・・ｎ：ｎはクエリー数列ｑの長さ）の値を前記公開鍵で暗号化する手段と、
前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を前記管理装置に対して出力する手段と、
前記管理装置から出力された前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を受け取る手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を前記秘密鍵で復号する手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの非負／負を判定する手段と、
判定結果を出力する手段と、
を備え、
前記管理装置は、
前記検索者装置から出力された前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各値の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を受け取る手段と、
前記データベースから一の数列データｐiを読み出す手段と、
前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、スコアＴiの暗号値を求める演算手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する手段と、
を備え、
前記演算手段は、以下の処理を行う検索システム。
（１）前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化し、暗号値Ｅｎｃ（−｜ｐi｜）を得る。
（２）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（３）前記管理装置が、値（１＋θα＋θβ−θ）を前記公開鍵によって暗号化して暗号値Ｅｎｃ（１＋θα＋θβ−θ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）と前記暗号値Ｅｎｃ（１＋θα＋θβ−θ）に対して平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）に対応する計算を行って暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））を求める。
（４）前記管理装置が、値θαおよび値θβを前記公開鍵で暗号化して暗号値Ｅｎｃ（θα）と暗号値（θβ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）と前記暗号値Ｅｎｃ（θα）に対して平文における−｜ｑ｜×θαに対応する計算を行って暗号値Ｅｎｃ（−｜ｑ｜×θα）を求めると共に、前記暗号値Ｅｎｃ（−｜ｐi｜）と前記暗号値Ｅｎｃ（θβ）に対して平文における−｜ｐi｜×θβに対応する計算を行って暗号値Ｅｎｃ（−｜ｐi｜×θβ）を求め、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜×θα）と前記暗号値Ｅｎｃ（−｜ｐi｜×θβ）に対して平文における（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））を求める。
（５）前記管理装置が、暗号の加法準同型性を利用して、上記（３）で求めた暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））と、上記（４）で求めた暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））に対して、平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））をスコアＴの暗号値として求める。
（６）前記管理装置が、前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、上記（１）から（５）を繰り返し行い、各数列データｐiに対するスコアＴi（ｉ＝１，２，・・・ｍ：ｍはスコアＴの計算を行ったデータ数）の暗号値を求める。
【請求項１８】
物の部分構造または性質を表すデータとして、物が予め定められた前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データを記憶したデータベースを有し、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数１３】
0005975490.tif 000014
が閾値θn／θd（ただし、θn、θdはθn≦θdを満たす自然数）以上か否かを値の非負／負によって示したスコアＴの暗号値を前記検索者装置に返す管理装置であって、
前記検索者装置にて生成された加法準同型性を有する暗号の公開鍵と、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化した暗号値Ｅｎｃ（−｜ｑ｜）と、前記クエリー数列データｑの各要素を前記公開鍵で暗号化した暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）とを受け取る手段と、
前記データベースから一の数列データｐiを読み出す手段と、
前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、スコアＴi（ｉ＝１，２，・・・ｍ：ｍはスコアＴの計算を行ったデータ数）の暗号値を求める演算手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する手段と、
を備え、
前記演算手段は、以下の処理を行う管理装置。
（１）前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化する。
（２）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（３）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）に対して、平文において（｜ｐi∩ｑ｜）を｛γ（θd−θn）＋θn（μa＋μb）｝回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb））を求める。
（４）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）に対して平文において（−｜ｑ｜）をμa回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜））を求めるとともに、前記暗号値Ｅｎｃ（−｜ｐi｜）に対して平文において（−｜ｐi｜）をμb回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μb（−｜ｐi｜））を求め、前記暗号値Ｅｎｃ（μa（−｜ｑ｜））と前記暗号値Ｅｎｃ（μb（−｜ｐi｜））に対して平文におけるμa（−｜ｑ｜）＋μb（−｜ｐi｜）に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））を求め、さらに、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対して平文において（μa（−｜ｑ｜）＋μb（−｜ｐi｜））をθn回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））を求める。
（５）前記管理装置が、暗号の加法準同型性を利用して、上記（３）で求めた暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝と、上記（４）で求めた暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））に対して、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）をスコアＴiの暗号値として求める。
（６）前記管理装置が、前記データベースに含まれる複数の数列データｐiのそれぞれについて、上記（１）から（５）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
【請求項１９】
物の部分構造または性質を表すデータとして、物が予め定められた前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データを記憶したデータベースを有し、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２，・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数１４】
0005975490.tif 000015
が閾値θ（０＜θ≦１）以上か否かを値の非負／負によって示したスコアＴiの暗号値を前記検索者装置に返す管理装置であって、
前記検索者装置にて生成された乗法準同型性および加法準同型性を有する暗号の公開鍵と、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化した暗号値Ｅｎｃ（−｜ｑ｜）と、前記クエリー数列データｑの各要素を前記公開鍵で暗号化した暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）とを受け取る手段と、
前記データベースから一の数列データｐiを読み出す手段と、
前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、スコアＴiの暗号値を求める演算手段と、
前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する手段と、
を備え、
前記演算手段は、以下の処理を行う管理装置。
（１）前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化し、暗号値Ｅｎｃ（−｜ｐi｜）を得る。
（２）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（３）前記管理装置が、値（１＋θα＋θβ−θ）を前記公開鍵によって暗号化して暗号値Ｅｎｃ（１＋θα＋θβ−θ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）と前記暗号値Ｅｎｃ（１＋θα＋θβ−θ）に対して平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）に対応する計算を行って暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））を求める。
（４）前記管理装置が、値θαおよび値θβを前記公開鍵で暗号化して暗号値Ｅｎｃ（θα）と暗号値（θβ）を求め、暗号の乗法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）と前記暗号値Ｅｎｃ（θα）に対して平文における−｜ｑ｜×θαに対応する計算を行って暗号値Ｅｎｃ（−｜ｑ｜×θα）を求めると共に、前記暗号値Ｅｎｃ（−｜ｐi｜）と前記暗号値Ｅｎｃ（θβ）に対して平文における−｜ｐi｜×θβに対応する計算を行って暗号値Ｅｎｃ（−｜ｐi｜×θβ）を求め、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜×θα）と前記暗号値Ｅｎｃ（−｜ｐi｜×θβ）に対して平文における（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））を求める。
（５）前記管理装置が、暗号の加法準同型性を利用して、上記（３）で求めた暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ））と、上記（４）で求めた暗号値Ｅｎｃ（（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））に対して、平文における（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ）に対応する計算を行って、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）×（１＋θα＋θβ−θ）＋（−｜ｑ｜×θα）＋（−｜ｐi｜×θβ））をスコアＴiの暗号値として求める。
（６）前記管理装置が、前記データベースに含まれる複数の物の数列データｐiのそれぞれについて、上記（１）から（５）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索条件およびデータベースの秘匿性を保持しつつ、データベース内に類似するデータがあるか調べる検索システムおよび検索方法に関する。
【背景技術】
【０００２】
今日における創薬は、ターゲット探索、ヒット化合物探索、リード化合物探索、薬候補の合成を経て、前臨床試験の医薬品開発プロセスに進む。ターゲット探索では、配列情報解析（データベースリサーチ）やマイクロアレイでの遺伝子発現情報の解析等により、病気の原因遺伝子（タンパク質等）を特定する。ヒット化合物探索では、計算機上のＤｏｃｋｉｎｇ、ＭＤ（シミュレーション）により候補を絞り込んだり、類似タンパク質から構造予測や機能予測を行ったりすることで、原因遺伝子に効きそうな化合物を探索する。リード化合物探索では、ヒット化合物の類似化合物を探して、より効果のあるリード化合物を探索する。薬候補の合成では、リード化合物の周辺で検証実験を行う。【０００３】
リード化合物を探索する際には、既知の化合物データベースから、ヒット化合物に類似する化合物を検索する必要がある。既知の化合物データベースの保有者としては、国立生物工学情報センター（ＮＣＢＩ）のような公的機関や、化合物を合成・販売するサプライヤー企業がある。【０００４】
さて、創薬においては、研究者は、自身が発見したヒット化合物のデータを外部に公開することを望まないという現状がある。特に、企業においては、このような傾向は顕著である。研究者は、公共の化合物データベースを検索する場合には、データをすべて自社のコンピュータにダウンロードする。しかし、有機化合物の探索空間は、１０の６０乗もの大きさがあるため、将来的にはデータ量が増大し、すべてのデータをダウンロードし、保持することが困難になる可能性がある。また、企業の化合物データベースを探索する場合には、秘密保持契約を締結した上で、データを購入することになる。しかし、購入したデータベースにヒット化合物に類似する化合物が含まれているかどうかをあらかじめ知ることはできないため、無駄な投資になるおそれがある。【０００５】
一方、化合物データベースを提供する企業においては、秘匿性の低いデータベースは無償で公開するが、秘匿性の高いいわゆるＦｏｃｕｓｅｄ  Ｌｉｂｒａｒｙは、販売するという形態をとっている。Ｆｏｃｕｓｅｄ  Ｌｉｂｒａｒｙは、企業がコストをかけて、特にヒットが出やすいと見込まれる有用な化合物を集めたデータベースである。一般的には、Ｆｏｃｕｓｅｄ  Ｌｉｂｒａｒｙは、特定の創薬ターゲット（例えば、ＧＰＣＲやキナーゼ等）に対して効果が高いと考えられる化合物を集約している。しかし、Ｆｏｃｕｓｅｄ  Ｌｉｂｒａｒｙの情報を一切開示しないとすれば、無駄な投資をおそれる研究者はデータの購入に消極的となり、企業側は、ビジネスチャンスを喪失するおそれがある。【０００６】
したがって、研究者は自身が発見した化合物を、データベース提供者はデータベースの内容を秘匿したまま、研究者が持っている化合物に類似する化合物がデータベースに存在しているか否かを知ることができれば、お互いにとってメリットがある。【０００７】
秘匿性を保ったまま化合物どうしの類似度を求める方法は、これまでほとんど研究されていない。本発明者らの知る限りでは、過去の先行研究としては、化合物どうしの類似度（Ｔａｎｉｍｏｔｏ係数）をセキュアに計算する非特許文献１だけである。非特許文献１が提案する方法では、研究者とデータベース保持者が化合物を表現したベクトルの要素を暗号化して第三者に送り、第三者において両者が一致しているかを判断するという処理を繰り返し行う。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M  D  Singh  et.al.「A  privacy  preserving  Jaccard  similarity  function  for  mining  encrypted  data」IEEE  TENCON  2009
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、非特許文献１に記載された方法は、検索条件となるヒット化合物を有する研究者と、データベースの保持者の他に、秘密情報を開示してもよい第三者の存在が必要である。また、ベクトルの要素数分の通信が発生するため、実用性に乏しい。【００１０】
本発明は、上記背景に鑑み、データベースの保持者およびデータベースの利用者の双方が、お互いに自らの情報を秘匿した状態で、検索条件に類似するデータがデータベースに含まれているかどうかを調べることができる検索システム及び検索方法を提供する。
【課題を解決するための手段】
【００１１】
本発明の検索システムは、物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置と、前記データベースの検索条件の入力および検索結果の出力を行う検索者装置とを備えている。ここで、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「１」、有しない場合に「０」を設定した数列データである。前記検索システムは、前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データｑと、前記データベースに記憶された物の数列データｐi（ｉ＝１，２、・・・ｍ：ｍは数列データの数）とのＴｖｅｒｓｋｙ係数Ｓi
【数１】
0005975490.tif 000002
が閾値θn／θd（ただし、θn、θdはθn≦θdを満たす自然数）以上となる数列データｐiが、前記データベースに含まれているかを調べるために以下のステップを実行する。
（１）前記検索者装置が、加法準同型性を有する暗号の公開鍵及び秘密鍵を生成する。
（２）前記検索者装置が、クエリー数列データｑの入力を受け付ける。
（３）前記検索者装置が、前記クエリー数列データｑを構成する要素のうちで値が「１」の要素数｜ｑ｜を求め、当該要素数｜ｑ｜に負号を付した値を前記公開鍵で暗号化すると共に、前記クエリー数列データｑの各要素ｑj（ただし、ｊ＝１，・・・ｎ：ｎはクエリー数列ｑの長さ）の値を前記公開鍵で暗号化する。
（４）前記検索者装置が、前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を前記管理装置に対して出力する。
（５）前記管理装置が、前記検索者装置から出力された前記公開鍵と前記暗号値Ｅｎｃ（−｜ｑ｜）とクエリー数列データｑの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を受け取る。
（６）前記管理装置が、前記データベースから一の数列データｐiを読み出す。
（７）前記管理装置が、前記数列データｐiを構成する要素のうちで値が「１」の要素数｜ｐi｜を求め、当該要素数｜ｐi｜に負号を付した値を前記公開鍵で暗号化する。
（８）前記管理装置が、前記数列データｐiの各要素ｐi,j（ただし、ｊ＝０，１，・・・ｎ：ｎは数列データｐiの長さ）を調べ、値が「１」を有する要素に対応するクエリー数列データｑのすべての要素ｑk（ｋはｐi,k＝１を満たす）の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Ｅｎｃ（ｑk）に対して行い、クエリー数列データｑと数列データｐiにおいて値がともに「１」の要素数｜ｐi∩ｑ｜の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を求める。
（９）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（｜ｐi∩ｑ｜）に対して、平文において（｜ｐi∩ｑ｜）をγ（θd−θn）＋θn（μa＋μb）回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb））を求める。
（１０）前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Ｅｎｃ（−｜ｑ｜）に対して平文において（−｜ｑ｜）をμa回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜））を求めるとともに、前記暗号値Ｅｎｃ（−｜ｐi｜）に対して平文において（−｜ｐi｜）をμb回加算する計算に対応する計算を行って暗号値Ｅｎｃ（μb（−｜ｐi｜））を求め、前記暗号値Ｅｎｃ（μa（−｜ｑ｜））と前記暗号値Ｅｎｃ（μb（−｜ｐi｜））に対して平文におけるμa（−｜ｑ｜）＋μb（−｜ｐi｜）に対応する計算を行って暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））を求め、さらに、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対して平文においてμa（−｜ｑ｜）＋μb（−｜ｐi｜）をθn回加算する計算に対応する計算を行って、暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））を求める。
（１１）前記管理装置が、暗号の加法準同型性を利用して、上記（９）で求めた暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝）と、上記（１０）で求めた暗号値Ｅｎｃ（θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜）））に対して、平文における（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））に対応する計算を行い、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）＋θn（μa（−｜ｑ｜）＋μb（−｜ｐi｜））｝）をスコアＴiの暗号値として求める。
（１２）前記管理装置が、前記データベースに含まれる複数の数列データｐiのそれぞれについて、上記（６）から（１１）を繰り返し行い、各数列データｐiに対するスコアＴiの暗号値を求める。
（１３）前記管理装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置に対して出力する。
（１４）前記検索者装置が、前記管理装置から出力された前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を受け取る。
（１５）前記検索者装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの暗号値を前記秘密鍵で復号する。
（１６）前記検索者装置が、前記スコアＴ1，Ｔ2，・・・Ｔmの非負／負を判定する。
（１７）前記検索者装置が、判定結果を出力する。【００１２】
本発明において、前記暗号は、確率暗号であってもよい。また、平文における加算に対応する計算は、暗号値における乗算であってもよい。これらの性質を有する暗号として、Ｐａｉｌｌｉｅｒ暗号を用いることができる。【００１３】
また、本発明は、ここで述べた加法準同型性を有する暗号を利用するほか、乗法準同型性および加法準同型性を有する暗号を利用することも可能である。
【発明の効果】
【００１４】
本発明によれば、管理装置は、クエリー数列データｑを暗号化した値を用いてＴｖｅｒｓｋｙ係数Ｓiを判定するためのスコアＴiを計算するので、クエリー数列データｑの秘匿性を保つことができる。また、スコアＴiは、データベースに記憶された物のデータが所定の閾値θn／θdより類似しているか否かを示すだけなので、データベースの内容が直接的に検索者に漏洩することがない。このようにクエリー数列データｑおよびデータベースの秘匿性を保ちつつ、データベースにクエリーに類似する物のデータが含まれているか否かの情報を得ることが可能である。
【図面の簡単な説明】
【００１５】
【図１】フィンガープリントについて説明する図である。
【図２Ａ】２つのフィンガープリントを比較した例を示す図である。
【図２Ｂ】Ｔｖｅｒｓｋｙ係数Ｓiを示す図である。
【図２Ｃ】Ｔｖｅｒｓｋｙ係数を説明するための図である。
【図３Ａ】加法準同型性について説明する図である。
【図３Ｂ】Ｐａｉｌｌｉｅｒ暗号の加法準同型性について説明するための図である。
【図３Ｃ】値Ａ×Ｂの暗号値Ｅｎｃ（Ａ×Ｂ）を暗号化された状態のまま計算する例を示す図である。
【図４】第１の実施の形態の検索システムの構成を示す図である。
【図５】管理装置および検索者装置のハードウェア構成を示す図である。
【図６】実施の形態の検索システムの動作を示すフローチャートである。
【図７】フィンガープリントの各要素を暗号化して暗号値を求める例を示す図である。
【図８】スコアＴiの暗号値の計算の動作を示すフローチャートである。
【図９Ａ】エントリｐiの各要素と、クエリーｑの各要素の例を示す図である。
【図９Ｂ】管理装置からみたエントリｐiの各要素とクエリーｑの各要素の例を示す図である。
【図１０】クエリーｑとエントリｐiとに共通する要素数の暗号値を求めるアルゴリズムを示すフローチャートである。
【図１１】暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝）を計算するアルゴリズムを示すフローチャートである。
【図１２】Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）を計算するアルゴリズムを示すフローチャートである。
【図１３】第２の実施の形態の検索システムの動作を示すフローチャートである。
【図１４】暗号値Ｅｎｃ（Ｔi×ｒi＋ｓi）を計算するアルゴリズムを示すフローチャートである。
【図１５】第３の実施の形態の検索システムの動作を示すフローチャートである。
【図１６】ランダムシェアＲiから、スコアＴiの非負／負の情報を取得する動作を示すフローチャートである。
【図１７】第４の実施の形態におけるスコア暗号値計算部の動作を示すフローチャートである。
【図１８】第５の実施の形態の検索システムの構成を示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態の検索システムおよび検索方法について図面を参照しながら説明する。以下では、構造をフィンガープリントによって表現した化合物を例として説明するが、本発明は、化合物の検索に限らず、物の構造または性質を「１」「０」の数列データで表現できるデータ（例えば、遺伝子を記憶したデータベース）に対して適用することが可能である。
【００１７】
検索システムの構成および動作の説明に先立って、フィンガープリントとＴｖｅｒｓｋｙ係数について説明する。
（フィンガープリント）
図１は、フィンガープリントの一例を示す図である。フィンガープリントは、化合物の表現方法の一つであり、化合物が所定の部分構造を有するか否かを「１」「０」を要素とする数列で表したものである。図１に示す例においては、先頭のビットから順に、「ピロール環」、「ベンゼン環」、「Ｏ」、「Ｎ」、「Ｎの二重結合」の有無を表している。要素の値が「０」の場合には該当の構造がないことを示し、値が「１」の場合には該当の構造があることを示す。化合物１は、２〜４番目のビットに「１」が立っているので、「ベンゼン環」、「Ｏ」、「Ｎ」を含み、１，５番目のビットが「０」なので、「ピロール環」、「Ｎの二重結合」を含まない。
【００１８】
このようなフィンガープリントによる表現方法としては、ＭＤＬ  ＭＡＣＣＳ  ｋｅｙ、Ｄａｙｌｉｇｈｔ  Ｆｉｎｇｅｒｐｒｉｎｔ、ＥＣＦＰ（Ｅｘｔｅｎｄｅｄ  Ｃｏｎｎｅｃｔｉｖｉｔｙ  ＦＰ）、ＦＣＦＰ（Ｆｕｎｃｔｉｏｎａｌ  Ｃｌａｓｓ  ＦＰ）、ファルマコフォアキー等がある。図１では、ＭＤＬ  ＭＡＣＣＳ  ｋｅｙの例を示した。
【００１９】
図１では、一例として５ビット分しかデータを示していないが、実際のフィンガープリントの長さはもっと長く、例えば、ＭＤＬ  ＭＡＣＣＳ  ｋｅｙでは、９６０ビットである。本発明は、いずれのフィンガープリントを用いた場合にも適用できる。
【００２０】
（Ｔｖｅｒｓｋｙ係数）
図２Ａに示すように、化合物Ａ，Ｂのフィンガープリントを比較することにより、化合物Ａ，Ｂに共通して含まれる部分構造と、化合物Ａ，Ｂのそれぞれにのみ含まれる部分構造の数が分かる。これに基づいて、化合物Ａ，Ｂの類似性を評価することができる。なお、化合物Ａ，Ｂの両方に含まれていない部分構造は、考慮する必要がない。
【００２１】
図２Ｂは、Ｔｖｅｒｓｋｙ係数Ｓを示す図である。図２Ｃは、Ｔｖｅｒｓｋｙ係数を説明するための図である。「ａ」は、化合物Ａのもつ部分構造の集合であり、図２Ｃに示す左側の円に相当する。「ｂ」は、化合物Ａのもつ部分構造の集合であり、図２Ｃに示す右側の円に相当する。「ｃ」は、化合物Ａ，Ｂが共通してもつ部分構造の集合（論理積）であり、図２Ｃに示す両円の重なり部分に相当する。
【００２２】
Ｔｖｅｒｓｋｙ係数に含まれる「α」及び「β」は、０以上の値をとる係数である。係数α、βを適切に設定することにより、異なる観点から、化合物Ａ，Ｂの類似度を測ることができる。α＝１、β＝１の場合には、Ｓ＝ｃ／（ａ＋ｂ−ｃ）となる。これはＴａｎｉｍｏｔｏ係数と呼ばれる係数であり、化合物Ａ，Ｂが持つすべての部分構造のうち、共通している部分構造の割合を表す。α＝１、β＝０の場合には、Ｓ＝ｃ／ａとなる。これは化合物Ｂが化合物Ａを部分構造として含む割合を表す。α＝１／２、β＝１／２の場合には、Ｓ＝ｃ／｛（ａ＋ｂ）／２｝となり、化合物Ａ，Ｂが共通してもつ部分構造の集合を化合物Ａのもつ部分構造の数と化合物Ｂのもつ部分構造の数の平均で割った値となる。これは、Ｄｉｃｅ係数と呼ばれる。いずれの場合にも、係数Ｓが大きくなればなるほど、化合物Ａと化合物Ｂが類似している割合が高いということになる。
【００２３】
（本実施の形態の概要）
本実施の形態の検索システムは、検索者装置にて入力された化合物のフィンガープリント（これを「クエリー」という）とのＴｖｅｒｓｋｙ係数が所定の閾値以上となる化合物、すなわち、クエリーに類似した化合物が、データベース内にどのくらいあるかを調べる。この際に、データベースを管理する管理装置に、クエリーを秘匿したまま検索を行う。これを実現するために、本実施の形態の検索システムでは、加法準同型性を有する確率暗号を用い、管理装置は、暗号値のまま演算を行う。ここで、加法準同型性について説明する。
【００２４】
図３Ａは、加法準同型性について説明する図である。なお、本明細書において「Ｅｎｃ（  ）」は、括弧内の値が暗号化された暗号値を示す。加法準同型性の暗号は、平文における加算に相当する計算を、暗号値を用いて行うことができる暗号である。すなわち、図３Ａに示すように、値Ａの暗号値Ｅｎｃ（Ａ）と値Ｂの暗号値Ｅｎｃ（Ｂ）を演算することにより、暗号化された状態のまま、値Ａ＋Ｂの暗号値Ｅｎｃ（Ａ＋Ｂ）を計算することができる性質である。暗号値Ｅｎｃ（Ａ）と暗号値Ｅｎｃ（Ｂ）に対して行う演算は、暗号の種類によって異なる。
【００２５】
図３Ｂは、Ｐａｉｌｌｉｅｒ暗号の加法準同型性について説明するための図である。Ｐａｉｌｌｉｅｒ暗号では、図３Ｂに示すように、値Ａ＋Ｂを暗号化した暗号値Ｅｎｃ（Ａ＋Ｂ）は、暗号値Ｅｎｃ（Ａ）と暗号値Ｅｎｃ（Ｂ）の乗算によって求めることができる。つまり、暗号化された値の乗算は、平文での加算に相当する。これを利用して、平文における整数倍の乗算も行える。
【００２６】
図３Ｃは、値Ａ×Ｂの暗号値Ｅｎｃ（Ａ×Ｂ）を暗号化された状態のまま計算する例を示す図である。Ａ×ＢはＡをＢ回加算することと同じなので、暗号値で計算をする場合には、暗号値Ｅｎｃ（Ａ）をＢ回乗算する（つまり、Ｅｎｃ（Ａ）をＢ乗する）ことにより、暗号値Ｅｎｃ（Ａ×Ｂ）を求めることができる。なお、暗号値Ｅｎｃ（Ｂ）をＡ回乗算してもよいことは言うまでもない。
【００２７】
本実施の形態で扱うデータはバイナリデータなので、平文に対して一意の暗号文が生成されると、「１」に対する暗号値と「０」に対する暗号値の２種類の暗号値しか生成されないことになり、クエリーのフィンガープリントが露呈してしまうおそれがある。このような不都合を防止するため、確率暗号を用いる。確率暗号では、暗号化の手続きが確率的に行われるため、暗号文からは平文のいかなる部分情報も漏洩しない。一般的には、同一の平文から生成される暗号文は異なる。第１〜第３の実施の形態では、加法準同型性を有する確率暗号として、Ｐａｉｌｌｉｅｒ暗号を用いる。
【００２８】
本実施の形態では、検索者装置から送信された暗号文を暗号文のまま取り扱って計算処理を行うため、データベースの管理者に対してクエリーが露呈しない構成としているが、加法準同型性を有する暗号においては、平文の加算に相当する演算しか行うことができないため、分数形式のＴｖｅｒｓｋｙ係数Ｓiを計算することはできない。そこで、本実施の形態では、Ｔｖｅｒｓｋｙ係数が所定の閾値θn／θd以上であるときに非負（負ではない、すなわち、正または０）の値をとる、以下のスコアＴを導入している。
【数２】
0005975490.tif 000003
なお、Ｐｉｌｌｉｅｒ暗号では加法準同型性を有するが、暗号化した状態で減算を行うことはできないので、負の値を加算する形になるように（−｜ｑ｜）、（−｜ｐi｜）を用いている。
【００２９】
スコアＴiは、Ｔｖｅｒｓｋｙ係数と閾値θn／θdとの不等式を変形して得られる。
【数３】
0005975490.tif 000004
なお、Ｐｉｌｌｉｅｒ暗号では小数を扱えないため、Ｔｖｅｒｓｋｙ係数Ｓiの係数α、βをμa／γ、μb／γとし、閾値をθn／θdで表す工夫をしている。
【００３０】
（第１の実施の形態）
［検索システムの構成］
図４は、第１の実施の形態の検索システムの構成を示す図である。検索システムは、化合物のフィンガープリントを記憶したデータベース１２を有する管理装置１０と、管理装置１０に対してクエリーを送信してデータベース１２の検索を依頼する検索者装置３０とを有している。管理装置１０と検索者装置３０とは、インターネット等のネットワーク５０によって接続されている。
【００３１】
管理装置１０は、化合物のデータベース１２と、クエリー受信部１６と、入力データチェック部１８と、スコア暗号値計算部２０と、送信順序入替部２４と、結果送信部２６とを有している。また、管理装置１０は、Ｔｖｅｒｓｋｙ係数で用いられる係数μa／γ、μb／γやＴｖｅｒｓｋｙ係数に基づく類似度の判定閾値θn／θdを記憶した設定値記憶部１４と、設定値記憶部１４に記憶された設定値を変更する設定値変更部２２とを有している。また、管理装置１０は、図４には図示していないが、クエリーｑと化合物のデータｐiとの類似度を計算する際に用いるＣＰＵや記憶部を有している。データベースのハードウェア構成については、後述する（図５参照）。
【００３２】
クエリー受信部１６は、検索者装置３０から送信されるクエリー（検索条件）を受信する機能を有する。クエリー受信部１６は、受信したデータを記憶部に記憶する。クエリーには、化合物のフィンガープリントの各要素の値を暗号化した暗号値Ｅｎｃ（ｑ1）、Ｅｎｃ（ｑ2）、・・・Ｅｎｃ（ｑn）と、フィンガープリントに含まれる「１」の個数の暗号値Ｅｎｃ（−｜ｑ｜）と、暗号化のための公開鍵が含まれる。なお、フィンガープリントの各値やフィンガープリントに含まれる「１」の個数は、いずれも暗号化されているので、管理装置１０においてその内容を知ることはできない。
【００３３】
入力データチェック部１８は、クエリー受信部１６にて受信したクエリーが適正であるか否かをチェックする機能を有する。例えば、フィンガープリントの各要素の値は「１」または「０」を暗号化したものであるところ、これ以外の数値の暗号値であれば、クエリーが適正ではないと判定し、後の処理を行わないようにできる。上述したとおり、管理装置１０は、暗号値から平文の内容を一切知ることはできないが、このようなチェックは、例えば、ゼロ知識証明（Practical  Private  Computation  and  Zero-Knowledge  Tools  for  Privacy-Preserving  Distributed  Data  Mining  SDM  2008:  pp.265-276,  Towards  restricting  plaintext  space  in  public  key  encryption,  in:  Proceedings  of  IWSEC  2011,  LNCS  7038,  2011,  pp.193−209.）等の技術を用いて実施することができる。なお、入力データチェックの構成は必須ではなく、省略することも可能である。
【００３４】
設定値記憶部１４は、Ｔｖｅｒｓｋｙ係数で用いられる係数μa／γ，μb／γと、Ｔｖｅｒｓｋｙスコアの計算に用いる閾値θd／θnを記憶している。設定値記憶部１４は、係数μa／γ，μb／γと閾値θd／θnを何パターンか記憶しておいてもよい。これにより、検索の種類（Ｔａｎｉｍｏｔｏ係数、部分構造検索、Ｄｉｃｅ係数等）に応じて係数μa／γ，μb／γを変えたり、求めたい類似の程度に応じて閾値θd／θnを変えることができる。
【００３５】
スコア暗号値計算部２０は、データベース１２内の化合物のデータｐi（ｉ＝１，２，・・・ｍ：ｍはデータ数）とクエリーｑとのＴｖｅｒｓｋｙ係数が所定の閾値θn／θd以上かそうでないかを示すスコアＴiの暗号値を計算する機能を有する。検索者装置３０では、スコアＴiが非負の値であるときにはＴｖｅｒｓｋｙ係数が閾値以上、負の値であるときにはＴｖｅｒｓｋｙ係数が閾値より小さいと判定される。スコア暗号値計算部２０は、データベース１２内のそれぞれの化合物について、スコアＴ1，Ｔ2，・・・Ｔmの暗号値を計算する。スコア暗号値計算部２０によるスコアＴの暗号値の計算処理は、後述する。
【００３６】
送信順序入替部２４は、複数のスコアＴ1，Ｔ2，・・・Ｔmの暗号値の送信順序をランダムに入れ替える機能を有する。具体的には、スコアＴ1，Ｔ2，・・・Ｔmの暗号値を計算した順に記憶部に記憶しておき、送信順序入替部２４が送信を行う際に、記憶部からランダムに読み出すことによって、送信順序を入れ替えることができる。
【００３７】
スコア暗号値計算部２０は、データベース１２から化合物のデータを順番に読み出してスコアＴ1，Ｔ2，・・・Ｔmの暗号値の計算を行う。毎回、スコアＴ1，Ｔ2，・・・Ｔmの暗号値を計算した順に送信すると、検索者装置３０の側でクエリーを適宜変えてスコアＴ1，Ｔ2，・・・Ｔmを得ることによって、データベース１２に含まれる化合物を予測されないとも限らない。送信順序入替部２４は、このような不都合を防止する。なお、この構成は、必須の構成ではなく、省略することも可能である。
結果送信部２６は、スコアＴ1，Ｔ2，・・・Ｔmの暗号値を検索者装置３０に送信する機能を有する。
【００３８】
次に、検索者装置３０の構成について説明する。検索者装置３０は、クエリー入力部３２と、暗号鍵生成部３４と、暗号化部３６と、クエリー送信部３８と、結果受信部４０と、復号化部４２と、判定部４４と、表示部４６と、記憶部４８とを有している。
【００３９】
クエリー入力部３２は、類似する化合物を探したい化合物のフィンガープリントのデータｑの入力を受け付ける機能を有する。クエリー入力部３２は、化合物の構造式の入力を受け付け、構造式からフィンガープリントへの変換を行ってもよい。クエリー入力部３２は、入力されたフィンガープリントのデータｑを記憶部４８に記憶する。また、クエリー入力部３２は、フィンガープリントに含まれる値が「１」の要素数を求め、求めた要素数｜ｑ｜も記憶部に記憶する。
【００４０】
暗号鍵生成部３４は、Ｐａｉｌｌｉｅｒ暗号により暗号化を行う公開鍵と、復号を行う秘密鍵を生成する機能を有する。暗号鍵生成部３４は、生成した公開鍵及び秘密鍵を記憶部に記憶する。暗号鍵生成部３４は、クエリーｑごとに新しい公開鍵及び秘密鍵を生成してもよいし、複数のクエリーｑに対して同じ公開鍵及び秘密鍵を用いてもよい。
【００４１】
暗号化部３６は、クエリーのフィンガープリントの各要素ｑ1，ｑ2，・・・ｑnの値と、値が「１」の要素数｜ｑ｜を記憶部４８から読み出し、フィンガープリントの各値ｑ1，ｑ2，・・・ｑnを暗号化すると共に、要素数｜ｑ｜に負号を付けた値（−｜ｑ｜）を暗号化する機能を有する。ここで、要素数｜ｑ｜に対して負号を付しているのは、Ｐａｉｌｌｉｅｒ暗号は加法準同型性を有するが、減算に対応する暗号値の計算を扱えないため、予め負号を付しておくことにより、負の値の加算として扱えるようにするためである。暗号化部３６は、フィンガープリントの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）と、値が「１」の要素数｜ｑ｜の暗号値Ｅｎｃ（−｜ｑ｜）をクエリー送信部３８に入力する。
【００４２】
クエリー送信部３８は、フィンガープリントの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）と、要素数｜ｑ｜の暗号値Ｅｎｃ（−｜ｑ｜）と、公開鍵を管理装置１０に送信する機能を有する。
【００４３】
結果受信部４０は、管理装置１０から送信されたスコアＴ1，Ｔ2，・・・Ｔmの暗号値を受信する機能を有する。結果受信部４０は、受信したスコアＴ1，Ｔ2，・・・Ｔmの暗号値を記憶部４８に記憶する。復号化部４２は、秘密鍵を用いて、結果受信部４０にて受信したスコアＴ1，Ｔ2，・・・Ｔmの暗号値を復号する機能を有する。復号化部４２は、復号により得られたスコアＴ1，Ｔ2，・・・Ｔmを判定部４４に入力する。
【００４４】
判定部４４は、スコアＴ1，Ｔ2，・・・Ｔmが非負の値を有するか否かを判定する。スコアＴ1，Ｔ2，・・・Ｔmが非負の場合には、Ｔｖｅｒｓｋｙ係数が所定の閾値θn／θd以上であることが分かる。非負の値を有するスコアＴiの数を集計することにより、管理装置１０のデータベース１２に類似する化合物がいくつあるか知ることができる。
【００４５】
表示部４６は、判定部４４による判定結果を表示する機能を有する。表示部４６は、Ｔｖｅｒｓｋｙ係数が閾値θn／θd以上の化合物が何個あったかを表示してもよいし、当該化合物があった割合を表示してもよい。
【００４６】
図５は、管理装置１０および検索者装置３０のハードウェア構成を示す図である。管理装置１０および検索者装置３０はともに、ＣＰＵ６０、ＲＡＭ６２、ＲＯＭ６４、通信インターフェース６８、ハードディスク７０、操作部７２、ディスプレイ７４がデータバス７６によって接続されたコンピュータによって構成される。管理装置１０と検索者装置３０とでは、ＲＯＭ６４に書き込まれているプログラム６６の内容が異なっている。管理装置１０のＲＯＭ６４に記憶されたプログラム６６は管理装置１０の機能を実現するためのプログラムであり、検索者装置３０のＲＯＭ６４に記憶されたプログラム６６は検索者装置３０の機能を実現するためのプログラムである。このような各プログラム６６は、本発明の範囲に含まれる。また、管理装置１０は、ハードディスクに化合物のフィンガープリントのデータが記憶されている。
【００４７】
［検索システムの動作］
図６は、本実施の形態の検索システムの動作を示すフローチャートである。まず、検索者装置３０にて、クエリーの化合物のフィンガープリントのデータｑを入力する（Ｓ１０）。検索者装置３０は、入力されたフィンガープリントのデータｑを記憶部４８に記憶する。次に、検索者装置３０は、Ｐａｉｌｌｅｒ暗号の公開鍵、秘密鍵のセットを生成し、記憶部４８に記憶する（Ｓ１２）。
【００４８】
検索者装置３０は、記憶部４８からクエリーのフィンガープリントのデータｑを読み出し、読み出したフィンガープリントの各要素ｑ1，ｑ2，・・・ｑnの値を公開鍵で暗号化する（Ｓ１４）。
【００４９】
図７は、フィンガープリントの各要素を暗号化して暗号値を求める例を示す図である。検索者装置３０は、各要素の値すなわち「１」または「０」を暗号化して暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を得る。本実施の形態で用いるＰａｉｌｌｉｅｒ暗号は確率暗号なので、同じ値を暗号化しても暗号値は同じにはならない。これにより、暗号値から平文の値を推測される不都合を防止できる。
【００５０】
また、検索者装置３０は、フィンガープリントに含まれる要素のうち値が「１」の要素数を求め、当該要素数｜ｑ｜に負号を付した値を暗号化し、暗号値Ｅｎｃ（−｜ｑ｜）を得る。検索者装置３０は、公開鍵と、値が「１」の要素数｜ｑ｜の暗号値Ｅｎｃ（−｜ｑ｜）と、クエリーの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を、管理装置１０に送信する（Ｓ１６）。
【００５１】
管理装置１０は、検索者装置３０から送信された公開鍵と、暗号値Ｅｎｃ（−｜ｑ｜）と、クエリーの各要素の暗号値Ｅｎｃ（ｑ1），Ｅｎｃ（ｑ2），・・・Ｅｎｃ（ｑn）を受信し（Ｓ１８）、受信したデータを記憶部に記憶する。管理装置１０は、受信したデータの正当性チェックを行う（Ｓ２０）。クエリーの各要素の暗号値は「１」「０」のいずれかを暗号化したものであるが、「１」「０」のいずれでもないと判定された場合には、クエリーの数列データｑが誤っているので、この時点で管理装置１０は処理を中断し、検索者装置３０にクエリーｑの入力誤りがあることを知らせる。また、この構成により、クエリーｑとして本来想定されている０や１以外の異常値を選ぶことで、管理装置１０のデータベース１２の情報をより多く引き出そうとする悪意の攻撃者（形式逸脱攻撃者）から、データベース１２の情報を保護することも可能となる。
【００５２】
続いて、管理装置１０は、データベース１２に記憶された化合物のフィンガープリントのデータ（個々のデータを「エントリ」という）ｐiとクエリーｑとに基づいて、スコアＴiの暗号値を計算する（Ｓ２２）。具体的な計算方法については、図８〜図１２を参照して説明する。
【００５３】
図８は、スコアＴiの暗号値の計算の動作を示すフローチャートである。管理装置１０は、まず、データベース１２から一つのエントリｐiを読み出す（Ｓ４０）。管理装置１０は、読み出したエントリｐiを記憶部に記憶する。
【００５４】
管理装置１０は、エントリｐiに含まれる要素のうち値が「１」の要素数を数え、要素数｜ｐi｜に負号を付した値を公開鍵で暗号化して暗号値Ｅｎｃ（−｜ｐi｜）を得る（Ｓ４２）。ここで、要素数｜ｐi｜に負号を付すのは、Ｐｉｌｌｉｅｒ暗号が暗号値の状態で平文の減算を行えないためである。続いて、管理装置１０は、クエリーｑとデータベース１２から読み出したエントリｐiに共通する部分構造の数（｜ｐi∩ｑ｜）を暗号値のまま計算する（Ｓ４４）。
【００５５】
図９Ａは、エントリｐiの各要素と、クエリーｑの各要素の例を示す図である。クエリーｑとエントリｐiが共通して有する部分構造は、両方に「１」が立っている要素である。図９Ａにおいて丸で囲んだように、両方に「１」が立っている要素の数を求めれば、共通する部分構造の数を求めることができる。
【００５６】
図９Ｂに示すように、管理装置１０は、エントリｐiの各要素の値は把握しているが、クエリーｑの各要素の値は暗号化されていて把握できない。しかし、エントリｐiにおいて「１」が立っている要素ｐi,kに対応するクエリーｑの要素ｑkの値を加算（暗号文においては乗算）していけば、エントリｐiの値が「１」でクエリーｑの値が「０」の要素はいくら足しても結果に影響を与えないから、クエリーｑとエントリｐiとが共通する要素数を求めることができる。
【００５７】
図１０は、クエリーｑとデータベース１２から読み出したエントリｐiとに共通する部分構造の数の暗号値を求めるアルゴリズムを示すフローチャートである。まず、管理装置１０は、変数Ｉ、カウンタｊのそれぞれに「１」を設定することにより、変数を初期化する（Ｓ６０）。変数Ｉは、共通する部分構造の要素数の暗号値が入る変数、変数ｊはカウンタである。なお、図１０のフローを行う際には、変数Ｉ，カウンタｊは、ＲＡＭ６２の一部に領域が割り当てられており、当該領域にデータを書き込むことにより、変数Ｉ，カウンタｊの値を記憶している。上記した変数Ｉ、カウンタｊの初期化は、割り当てられた所定の領域に「１」という値を書き込むことを意味する。なお、以下の説明においても、変数を初期化したり、変数の演算を行ったりする場合には、ＲＯＭ６４に記憶されたプログラム６６に従って、ＣＰＵ６０、ＲＡＭ６２等のコンピュータのハードウェア資源を利用して演算を行う。
【００５８】
エントリｐiの１番目の要素ｐi,1の値が「１」であるか否かを判定する（Ｓ６２）。「１」であった場合には（Ｓ６２でＹＥＳ）、対応するクエリーの要素の暗号値Ｅｎｃ（ｑj）を変数Ｉに掛け、求めた結果をＩに代入する（Ｓ６４）。具体的には、割り当てられた変数Ｉの領域に保存されたデータを読み出し、読み出したデータに暗号値Ｅｎｃ（ｑj）を乗じ、得られた結果を変数Ｉの領域に書き込む。
【００５９】
次に、カウンタｊ＝ｎ（ｎはフィンガープリントの長さ）になったか否かを判定する（Ｓ６６）。カウンタｊ＝ｎでない場合には（Ｓ６６でＮＯ）、ｊをインクリメントして（Ｓ６８）、エントリｐiの次の要素ｐi,2が「１」であるか否かを判定し（Ｓ６２）、上記した処理をカウンタｊの値がｎに等しくなるまで繰り返す。カウンタｊ＝ｎの場合には（Ｓ６６でＹＥＳ）、計算結果Ｉをクエリーｑとエントリｐiに共通する要素数の暗号値Ｅｎｃ（｜ｐi∩ｑ｜）とする（Ｓ７０）。
【００６０】
図８に戻る。管理装置１０は、クエリーｑとエントリｐiとで共通する部分構造の要素数｜ｐi∩ｑ｜に｛γ（θd−θn）＋θn（μa＋μb）｝を乗算した値の暗号値を求める。ここで、γ（θd−θn）＋θn（μa＋μb）はいずれも設定値であり、管理装置１０にとって既知の自然数である。図３Ｃを用いて説明したとおり、平文で整数倍した値の暗号値は、暗号値を冪乗することによって得られる。ここでは、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）をγ（θd−θn）＋θn（μa＋μb）回乗算する。
【００６１】
図１１は、暗号値Ｅｎｃ（（｜ｐi∩ｑ｜）×｛γ（θd−θn）＋θn（μa＋μb）｝）を計算するアルゴリズムを示すフローチャートである。まず、管理装置１０は、変数ｔｍｐＸ，ｊを暗号化する（Ｓ８０）。変数ｔｍｐＸは計算結果が入る変数、変数ｊはカウンタである。
【００６２】
管理装置１０は、変数ｔｍｐＸに暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を乗算し、その結果を変数ｔｍｐＸに代入する（Ｓ８２）。管理装置１０は、カウンタｊ＝γ（θd−θn）＋θn（μa＋μb）であるか否かを判定し（Ｓ８４）、カウンタｊ＝γ（θd−θn）＋θn（μa＋μb）でない場合には（Ｓ８４でＮＯ）、カウンタｊをインクリメントして（Ｓ８６）、変数ｔｍｐＸに暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を乗算し、その結果を変数ｔｍｐＸに代入する処理を行う（Ｓ８２）。カウンタｊ＝γ（θd−θn）＋θn（μa＋μb）の場合には（Ｓ８４でＹＥＳ）、求めた計算結果ｔｍｐＸを返す（Ｓ８８）。
【００６３】
図８に戻る。管理装置１０は、Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）を計算する。この計算には、クエリーｑに含まれる値が「１」の要素数｜ｑ｜の暗号値Ｅｎｃ（−｜ｑ｜）と、エントリｐiに含まれる値が「１」の要素数｜ｐi｜の暗号値Ｅｎｃ（−｜ｐi｜）を用いる。
【００６４】
図１２は、Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）を計算するアルゴリズムを示すフローチャートである。まず、管理装置１０は、変数ｔｍｐＹ，ｊのそれぞれに「１」を設定し、変数ｔｍｐＹ，ｊを初期化する（Ｓ９０）。変数ｔｍｐＹはＥｎｃ（μa（−｜ｑ｜））の計算結果が入る変数、変数ｊはカウンタである。管理装置１０は、ｔｍｐＹに暗号値Ｅｎｃ（−｜ｑ｜）を乗算し、その結果をｔｍｐＹに代入する（Ｓ９２）。管理装置１０は、カウンタｊ＝μaであるか否かを判定し（Ｓ９４）、カウンタｊ＝μaでない場合には（Ｓ９４でＮＯ）、カウンタｊをインクリメントして（Ｓ９６）、変数ｔｍｐＹに暗号値Ｅｎｃ（−｜ｑ｜）を乗算し、その結果を変数ｔｍｐＹに代入する処理を行う。カウンタｊ＝μaの場合には（Ｓ９４でＹＥＳ）、暗号値Ｅｎｃ（μa（−｜ｑ｜））の計算を終了し、暗号値Ｅｎｃ（μb（−｜ｐi｜））の計算処理に移る。
【００６５】
ここでも、まず、管理装置１０は、変数ｔｍｐＺ，ｊのそれぞれに「１」を設定し、変数ｔｍｐＺ，ｊを初期化する（Ｓ９８）。変数ｔｍｐＹは暗号値Ｅｎｃ（μb（−｜ｐi｜））の計算結果が入る変数、変数ｊはカウンタである。管理装置１０は、ｔｍｐＺに暗号値Ｅｎｃ（−｜ｐi｜）を乗算し、その結果をｔｍｐＺに代入する（Ｓ１００）。管理装置１０は、カウンタｊ＝μbであるか否かを判定し（Ｓ１０２）、カウンタｊ＝μbでない場合には（Ｓ１０２でＮＯ）、カウンタｊをインクリメントして（Ｓ１０４）、変数ｔｍｐＺに暗号値Ｅｎｃ（−｜ｐi｜）を乗算し、その結果を変数ｔｍｐＺに代入する処理を行う。カウンタｊ＝μbの場合には（Ｓ１０２でＹＥＳ）、暗号値Ｅｎｃ（μb（−｜ｐi｜））の計算処理を終了し、暗号値Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）の計算処理に移る。
【００６６】
暗号値Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）は、図３Ｃで説明したとおり、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））のθn乗によって計算することができる。また、暗号値Ｅｎｃ（μa（−｜ｑ｜）＋μb（−｜ｐi｜））は、暗号値Ｅｎｃ（μa（−｜ｑ｜））と暗号値Ｅｎｃ（μb（−｜ｐi｜））の乗算で計算できるから、ｔｍｐＹ×ｔｍｐＺによって求められる。したがって、ｔｍｐＹ×ｔｍｐＺをθn回乗算すれば、暗号値Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）を求めることができる。
【００６７】
管理装置１０は、変数ｔｍｐＷ，ｊのそれぞれに「１」を設定し、変数ｔｍｐＷ，ｊを初期化する（Ｓ１０６）。変数ｔｍｐＷは、Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）の計算結果が入る変数、変数ｊはカウンタである。管理装置１０は、ｔｍｐＷにｔｍｐＹ×ｔｍｐＺを乗算し、その結果をｔｍｐＷに代入する（Ｓ１０８）。管理装置１０は、カウンタｊ＝θnであるか否かを判定し（Ｓ１１０）、カウンタｊ＝θnでない場合には（Ｓ１１０でＮＯ）、カウンタｊをインクリメントして（Ｓ１１２）、変数ｔｍｐＷにｔｍｐＹ×ｔｍｐＺを乗算し、その結果を変数ｔｍｐＷに代入する処理を行う。カウンタｊ＝θnの場合には（Ｓ１１０でＹＥＳ）、Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）の計算処理を終了し、ｔｍｐＷの値を計算結果として返す（Ｓ１１４）。
【００６８】
図８に戻る。次に、管理装置１０は、ステップＳ４６で求めたＥｎｃ（｜ｐi∩ｑ｜×｛γ（θd−θn）＋θn（μa＋μb）｝）とステップＳ４８で求めた暗号値Ｅｎｃ（θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）を乗算し、暗号値Ｅｎｃ（｜ｐi∩ｑ｜×｛γ（θd−θn）＋θn（μa＋μb）｝＋θn｛μa（−｜ｑ｜）＋μb（−｜ｐi｜）｝）を求める。この値が、スコアＴiの暗号値である。管理装置１０は、求めたスコアＴiの暗号値を記憶部に記憶する。
【００６９】
管理装置１０は、データベース１２内の全エントリｐiについてスコアＴiの暗号値の計算を終了したか否かを判定する（Ｓ５２）。全エントリｐiについての計算が終了していない場合には（Ｓ５２でＮＯ）、管理装置１０は、データベース１２から次のエントリｐiを読み出し、読み出したエントリｐiとクエリーｑとのスコアＴiの暗号値を計算し、計算結果を記憶部に順番に記憶していく。全エントリｐi（ｉ＝１，２，・・・ｍ）についての計算が終了した場合には（Ｓ５２でＹＥＳ）、スコアＴiの計算を終了する。以上、スコアＴiの計算処理について詳しく説明した。
【００７０】
図６に戻って、検索システムの動作について説明する。管理装置１０は、データベース１２内の各エントリｐiについて求めたスコアＴ1，Ｔ2，・・・Ｔmの暗号値の順序を入れ替えた後（Ｓ２４）、検索者装置３０に対して送信する（Ｓ２６）。具体的には、送信順序入替部２４は、スコアＴiの暗号値をランダムに記憶部から読み出し、読み出したデータを結果送信部２６に入力することにより、送信順序を入れ替える。
【００７１】
検索者装置３０は、管理装置１０から送信されたスコアＴ1，Ｔ2，・・・Ｔmの暗号値を受信すると（Ｓ２８）、復号化部４２は、記憶部４８から秘密鍵を読み出し、秘密鍵を用いて、スコアＴ1，Ｔ2，・・・Ｔmの暗号値を復号化する（Ｓ３０）。検索者装置３０は、復号して求められた各スコアＴ1，Ｔ2，・・・Ｔmの非負／負を判定し、判定結果を表示する（Ｓ３２）。スコアＴ1，Ｔ2，・・・Ｔmが非負であるときには、Ｔｖｅｒｓｋｙ係数が所定の閾値θn／θd以上であることを意味する。したがって、スコアＴiが非負の化合物が多く含まれている場合には、クエリーの化合物と類似する化合物が多く含まれたデータベース１２であることが分かる。以上、第１の実施の形態の検索システムの構成および動作について説明した。
【００７２】
第１の実施の形態の検索システムによれば、検索者装置３０は、クエリーの化合物のフィンガープリントの暗号値を管理装置１０に送信するので、管理装置１０に対してクエリーの化合物の秘匿性を保ちつつ、データベース１２に類似する化合物がどれだけ含まれているかを調べることができる。また、管理装置１０にとっても、データベース１２が記憶している化合物を開示せずに、類似化合物の情報を知らせることができるという効果がある。
【００７３】
（第２の実施の形態）
次に、第２の実施の形態の検索システムについて説明する、第２の実施の形態の検索システムの基本的な構成は、第１の実施の形態と同じであるが、第２の実施の形態では、スコアＴiを撹乱してスコアＴiの絶対値が意味を持たないようにして、データベース１２の秘匿性をさらに高めている。
【００７４】
図１３は、第２の実施の形態の検索システムの動作を示すフローチャートである。第２の実施の形態の検索システムの動作は、第１の実施の形態と基本的に同じであるが、ステップＳ５０にて求めたスコアＴiの暗号値Ｅｎｃ（Ｔi）に対し、乱数ｒi，ｓi（ｒi＞ｓi）を用いて暗号値Ｅｎｃ（Ｔi×ｒi＋ｓi）を計算し、計算結果を新たなスコアＴiとしている（Ｓ５１）。
【００７５】
図１４は、暗号値Ｅｎｃ（Ｔi×ｒi＋ｓi）を計算するアルゴリズムを示すフローチャートである。管理装置１０は、まず、変数ｔ＿ｒｅｓ，ｊのそれぞれに「１」を代入して、変数ｔ＿ｒｅｓ，ｊを初期化する（Ｓ１２０）。変数ｔ−ｒｅｓはＥｎｃ（Ｔi×ｒi＋ｓi）の計算結果が入る変数、変数ｊはカウンタである。管理装置１０は、ｔ＿ｒｅｓに暗号値Ｅｎｃ（Ｔi）を乗算し、その結果をｔ＿ｒｅｓに代入する（Ｓ１２２）。
【００７６】
管理装置１０は、カウンタｊ＝ｒiであるか否かを判定し（Ｓ１２４）、カウンタｊ＝ｒでない場合には（Ｓ１２４でＮＯ）、カウンタｊをインクリメントして（Ｓ１２６）、変数ｔ＿ｒｅｓに暗号値Ｅｎｃ（Ｔi）を乗算し、その結果を変数ｔ＿ｒｅｓに代入する処理を行う。カウンタｊ＝ｒiになった場合には（Ｓ１２４でＹＥＳ）、管理装置１０は、ｔ＿ｒｅｓに乱数ｓiを公開鍵で暗号化して得られた暗号値Ｅｎｃ（ｓi）を乗算し、その結果を変数ｔ＿ｒｅｓに代入する（Ｓ１２８）。管理装置１０は、計算結果ｔ＿ｒｅｓを返す（Ｓ１３０）。
【００７７】
以上、第２の実施の形態の検索システムについて、第１の実施の形態と相違する点について説明した。第２の実施の形態においては、スコアＴiを乱数ｒi倍した後に乱数ｓiを加えた値を新たなスコアＴiとしている。したがって、類似の度合いとスコアＴiとの間に相関関係がなくなり、スコアＴiからデータベース１２に記憶されたデータの傾向を推測することができなくなる。したがって、データベース１２に記憶されたデータの秘匿性をいっそう高めることができる。
【００７８】
なお、スコアＴiは、非負のときにＴｖｅｒｓｋｙ係数が所定の閾値以上、負のときに所定の閾値より低いということを示すスコアであり、正負しか意味を持たない。したがって、ｒi倍しても正負は変わらないので、スコアＴiの判断基準に何ら変更はない。
【００７９】
ところで、スコアＴiが０であることは、Ｔｖｅｒｓｋｙ係数が閾値θn／θdに一致する化合物がデータベース１２内に存在することを意味する。上記Ｔｖｅｒｓｋｙ係数に一致する化合物が存在するという情報が漏れないようにするために乱数ｓiを加えている。上記した乱数ｒiを乗ずる撹乱では、スコアＴiが０の場合には意味を持たないからである。これにより、Ｔｖｅｒｓｋｙ係数が閾値θn／θdに一致する化合物のスコアＴiは必ず正の値となる。なお、乱数ｓiは、乱数ｒiより小さい値なので、乱数ｓiを加えることによって、スコアＴiの正負が入れ替わることはない。なぜなら、負のスコアＴiのうち絶対値が最小の「−１」を考えたとき、ｒi倍した値は−ｒiであり、これに絶対値がｒiより小さい乱数ｓiを加えても結果は負のままである。
【００８０】
（第３の実施の形態）
次に、第３の実施の形態の検索システムについて説明する、第３の実施の形態の検索システムの基本的な構成は、第１の実施の形態と同じであるが、第３の実施の形態では、スコアＴiを撹乱してランダムシェアＲiを生成することにより、データベース１２の秘匿性をさらに高めている。
【００８１】
図１５は、第３の実施の形態の検索システムの動作を示すフローチャートである。第３の実施の形態の検索システムの動作は、第１の実施の形態と基本的に同じであるが、ステップＳ５０にて求めたスコアＴiの暗号値Ｅｎｃ（Ｔi）に対し、乱数ｒiを用いて暗号値Ｅｎｃ（Ｔi＋ｒi）を計算し、計算結果をランダムシェアＲiの暗号値としている（Ｓ５１ａ）。ランダムシェアＲiは、スコアＴiに対して乱数ｒiを加えているので、Ｔｖｅｒｓｋｙ係数と閾値θn／θdとスコアＴiの正負の一致が保証されていない。
【００８２】
図１６は、ランダムシェアＲiから、スコアＴiの非負／負の情報を取得する動作を示すフローチャートである。検索者装置３０は、ランダムシェアＲiを秘匿回路に送信し（Ｓ１４０）、秘匿回路はランダムシェアＲiを受信する（Ｓ１４４）。ここで、「秘匿回路」は、計算内容を秘匿したまま計算を行える回路であり、Ｓｅｃｕｒｅ  Ｆｕｎｃｔｉｏｎ  Ｅｖａｌｕａｔｉｏｎにより設計される。
【００８３】
管理装置１０は、検索者装置３０が送信したランダムシェアＲiを生成する際に用いた乱数ｒiを秘匿回路に送信し（Ｓ１４２）、秘匿回路は乱数ｒiを受信する（Ｓ１４４）。秘匿回路は、ランダムシェアＲiから乱数ｒiを減算することによりスコアＴiを求め（Ｓ１４６）、その非負／負を判定する（Ｓ１４８）。
【００８４】
なお、ランダムシェアＲiおよび乱数ｒiの送信（Ｓ１４０〜Ｓ１４４）や、ランダムシェアＲiから乱数ｒiの減算（Ｓ１４６）、非負／負の判定（Ｓ１４８）は、Ｓｅｃｕｒｅ  Ｆｕｎｃｔｉｏｎ  Ｅｖａｌｕａｔｉｏｎにより行われる。
【００８５】
秘匿回路は、スコアＴiの非負／負の判定結果を検索者装置３０に送信し（Ｓ１５０）、検索者装置３０は判定結果を受信する（Ｓ１５２）。検索者装置３０は、全エントリについて計算を終了したか否かを判定し（Ｓ１５４）、全エントリについて計算が終了していない場合には（Ｓ１５４でＮＯ）、次のランダムシェアＲiについて上記と同じ処理を繰り返す。全エントリについて計算が終了した場合には（Ｓ１５４でＹＥＳ）、検索者装置３０は、判定結果を集計し（Ｓ１５６）、結果を表示する（Ｓ１５８）。
【００８６】
以上、第３の実施の形態の検索システムについて、第１の実施の形態との相違を中心に説明した。第３の実施の形態においては、検索者装置３０に対してスコアＴiではなくランダムシェアＲiを返し、検索者装置３０はランダムシェアＲiを秘匿回路に送信することによって、非負の判定結果のみを得る。類似の度合いとスコアＴiとの間には相関関係がないので、ランダムシェアＲiからデータベース１２に記憶されたデータの傾向を推測することができない。したがって、データベース１２に記憶されたデータの秘匿性をいっそう高めることができる。
【００８７】
（第４の実施の形態）
次に、第４の実施の形態の検索システムについて説明する。第１〜第３の実施の形態では、加法準同型性を有する暗号であるＰｉｌｌｉｅｒ暗号を用いる例について説明したが、第４の実施の形態では、加法準同型性に加え乗法準同型性を有する暗号を用いる。第４の実施の形態の検索システムの基本的な構成は、第１〜第３の実施の形態と同じである（図４等参照）。第４の実施の形態では、用いる暗号の性質が異なるので、管理装置１０におけるスコア暗号値計算部２０の処理が第１〜第３の実施の形態とは異なる。
【００８８】
図１７は、第４の実施の形態におけるスコア暗号値計算部２０の動作を示すフローチャートである。クエリーｑと読み出したエントリｐiとが共通して有する部分構造の要素数を求めるステップ（Ｓ４０〜Ｓ４４）までは、第１〜第３の実施の形態と同じである。
【００８９】
第４の実施の形態では、暗号は乗法準同型性を有しており、暗号値のままで、平文の乗算を行うことができるので、スコアＴiとして、以下の式を用いる。
【数４】
0005975490.tif 000005
【００９０】
第４の実施の形態では、スコア暗号値計算部２０は、暗号値Ｅｎｃ（｜ｐi∩ｑ｜×（１＋θα＋θβ−θ））を計算する（Ｓ１６０）。暗号は、乗法準同型性を有するので、平文における｜ｐi∩ｑ｜×（１＋θα＋θβ−θ）の計算に対応する計算を行うことにより求めることができる。第１〜第３の実施の形態のように、暗号値Ｅｎｃ（｜ｐi∩ｑ｜）を（１＋θα＋θβ−θ）回乗ずるという処理は不要であり、しかも、（１＋θα＋θβ−θ）が自然数でなくとも計算が可能である。
【００９１】
次に、スコア暗号値計算部２０は、暗号値Ｅｎｃ（θα（−｜ｑ｜）＋θβ（−｜ｐi｜））を計算する（Ｓ１６２）。まず、暗号値Ｅｎｃ（−｜ｑ｜）と、θαを公開鍵によって暗号化した暗号値Ｅｎｃ（θα）に対して、平文における（−｜ｑ｜）×θαに対応する計算を行って、Ｅｎｃ（θα（−｜ｑ｜））を求める。次に、暗号値Ｅｎｃ（−｜ｐi｜）と、θβを公開鍵によって暗号化した暗号値Ｅｎｃ（θβ）に対して、平文における（−｜ｐi｜）×θβに対応する計算を行って、Ｅｎｃ（θβ（−｜ｐi｜））を求める。続いて、暗号値Ｅｎｃ（θα（−｜ｑ｜））と暗号値Ｅｎｃ（θβ（−｜ｐi｜））に対して、平文における（θα（−｜ｑ｜））＋（θβ（−｜ｐi｜））に対応する計算を行ってＥｎｃ（θα（−｜ｑ｜）＋（θβ（−｜ｐi｜））を求める。
【００９２】
続いて、スコア暗号値計算部２０は、スコアＴiの暗号値Ｅｎｃ（｜ｐi∩ｑ｜×（１＋θα＋θβ−θ）＋θα（−｜ｑ｜）＋（θβ（−｜ｐi｜））を計算する（Ｓ１６４）。具体的には、暗号値Ｅｎｃ（｜ｐi∩ｑ｜×（１＋θα＋θβ−θ））と暗号値Ｅｎｃ（θα（−｜ｑ｜）＋（θβ（−｜ｐi｜））に対して、平文における｜ｐi∩ｑ｜×（１＋θα＋θβ−θ）＋θα（−｜ｑ｜）＋（θβ（−｜ｐi｜））に対応する計算を行う。以上により、データベース１２から読み出したエントリｐiとクエリーｑとのスコアＴiを求める。
【００９３】
スコア暗号値計算部２０は、データベース１２内の全エントリｐiについて、スコアＴiの計算が終了したか否かを判定し（Ｓ１６６）、全エントリＰiについての計算が終了していない場合には（Ｓ１６６でＮＯ）、未計算のエントリｐiをデータベース１２から読み出して、上記と同様の処理を行う。全エントリｐiについての計算が終了した場合には（Ｓ１６６でＹＥＳ）、処理を終了する。
【００９４】
以上、第４の実施の形態の検索システムについて、第１〜第３の実施の形態と相違する点を説明した。第４の実施の形態の検索システムでは、加法準同型性に加えて乗法準同型性を有する暗号を用いているので、スコアＴiを簡易に計算することができる。
【００９５】
なお、上記した実施の形態では暗号が小数を扱えることを前提として、係数α、βや閾値θをそのまま用いる例について説明したが、用いる暗号の性質として小数を扱えない場合には、第１〜第３の実施の形態と同様に、係数α、βを係数μa／γ、μb／γとし、閾値θをθn／θdと置き換え、第１〜第３の実施の形態と同様のスコアＴiを求めればよい。
【００９６】
（第５の実施の形態）
次に、第５の実施の形態の検索システムについて説明する。第５の実施の形態の検索システムは、管理装置１０から検索者装置３０に検索結果を送信する際に、データベース１２内のエントリＰｉのスコアＴｉ（ｉ＝１，２，・・・ｍ）の暗号値に加えて、ダミーのスコアＴｄｉ（ｉ＝１，２，・・・ｋ）の暗号値を混在させたデータを送信し、管理装置１０のデータベース１２の情報遺漏のリスクをさらに低減させる。
【００９７】
図１８は、第５の実施の形態の検索システムの構成を示す図である。第５の実施の形態においては、管理装置１０は、第１の実施の形態の検索システムの構成（図４参照）に加えて、ダミーデータを生成するダミーデータ生成部２８を備えている。
【００９８】
ダミーデータ生成部２８は、所定の確率分布にしたがって、ダミーのスコアＴｄｉを生成する。ダミーデータ生成部２８は、実際のスコアＴｉのデータに近いデータを生成する。ダミーデータ生成部２８は、生成したダミーのスコアＴｄｉを検索者装置３０から送信された公開鍵を用いて暗号化し、ダミーのスコアＴｄｉの暗号値を生成する。また、ダミーデータ生成部２８は、生成したダミーのスコアＴｄｉの中に、非負のダミースコアが何個含まれるか、負のダミースコアが何個含まれるかを求め、その値を結果送信部２６に渡す。
【００９９】
送信順序入替部２４は、データベース１２内のエントリＰｉのスコアＴｉの暗号値とダミーのスコアＴｄｉの暗号値の送信順序をランダムに並び替える（シャッフルする）。結果送信部２６は、スコアＴｉの暗号値とダミーのスコアＴｄｉの暗号値と共に、非負のダミースコアの個数、負のダミースコアの個数を検索者装置３０に送信する。
【０１００】
検索者装置３０は、管理装置１０から、ランダムな送信順序で送信されるスコアＴ1，Ｔ2，・・・Ｔmの暗号値とダミーのスコアＴｄ1，Ｔｄ2，・・・Ｔｄkを受信すると、復号化部４２は、記憶部４８から秘密鍵を読み出し、秘密鍵を用いて、受信した暗号値を復号化する。送信順序がランダムであるため、検索者装置３０は、どれがデータベース１２内のエントリＰｉに対応するスコアＴiでどれがダミーのスコアＴｄiであるかは分からない。検索者装置３０は、復号して求められた各スコアＴ1，Ｔ2，・・・Ｔm，Ｔｄ1，Ｔｄ2，・・・Ｔｄkの非負／負を判定し、非負および負のスコアがいくつずつ含まれているかを求める。次に、検索者装置３０は、求められた非負および負のスコアの個数から、管理装置１０から送信された非負のダミースコアの個数と、負のダミースコアの個数を減算することによって、データベース１２内に非負および負のＴｖｅｒｓｋｙ係数を有するエントリＰｉがそれぞれいくつずつ含まれているかを求める。例えば、受信したスコアを復号化した結果から非負のスコアが２０個、負のスコアが１００個含まれていると求められ、非負のダミーのスコアが５個、負のダミーのスコアが１０個であるとした場合、データベース１２には、非負のスコアを有するエントリが１５個、負のスコアを有するエントリが９０個であると判定することができる。以上、第５の実施の形態の検索システムの構成および動作について説明した。
【０１０１】
第５の実施の形態の検索システムにおいては、どれがデータベース１２内のエントリＰｉに基づくスコアＴｉであるかが、ダミーのスコアＴｄｉによって隠され、直ちにわからない状態となることから、検索者装置３０に漏れる情報量が削減できる。さらに、ダミーのスコアＴｄｉの個数を大きくすることにより、検索者装置３０に漏れる余分な情報量を限りなく０に近づけることができる。
【０１０２】
以上、本発明の検索システムおよび検索方法について実施の形態を挙げて詳細に説明したが、本発明は上記した実施の形態に限定されるものではない。
【０１０３】
上記した実施の形態では、管理装置１０と検索者装置３０とがインターネット等のネットワーク５０を介して接続されている例について説明したが、管理装置１０と検索者装置３０とを接続するネットワーク５０は何でもよい。また、管理装置１０と検索者装置３０とは必ずしもネットワーク５０で接続されている必要はなく、検索者装置３０にて出力したクエリーデータｑをＣＤ−ＲＯＭ等の記録媒体に記録して、管理装置１０の運用者に郵送し、運用者が管理装置１０にＣＤ−ＲＯＭを読み取らせてもよい。
【０１０４】
上記した実施の形態では、加法準同型性および確率暗号という特性を有する暗号方式としてＰａｉｌｌｉｅｒ暗号を用いる例について説明したが、暗号化方式は、加法準同型性および確率暗号という特性を満たせば、何であってもよい。
【０１０５】
なお、Ｐａｉｌｌｉｅｒ方式について補足すると、Ｐａｉｌｌｉｅｒ方式自体は、平文が負の場合に暗号化を行うことができないので、本発明に適用する際には、以下のような処理を行う。すなわち、Ｐａｉｌｌｉｅｒ暗号が扱える数値範囲０からｎを２分割し、０からｎ／２までをそのまま０からｎ／２に対応する正の値とし、ｎ／２＋１からｎまでを−１〜−ｎ／２に対応する負の値に読み替える。このような手法は、負号を扱えるようにするための常套手段である。
【０１０６】
上記した実施の形態では、類似する化合物がどれだけあるかを調べる例を挙げたが、化合物に限らず、本発明は、物の構造または性質の有無をバイナリデータで表現したデータベースに適用することができる。例えば、類似する遺伝子配列がどれだけあるかを調べるために、本発明を用いることが可能である。クエリーとして、個人の遺伝子情報を投げる場合には、個人情報を保護する観点から遺伝子情報を秘匿する必要があるので、そのような場合に、本発明は有用である。
【産業上の利用可能性】
【０１０７】
本発明によれば、データベースおよびクエリーの秘匿性を保ちつつ、クエリーに類似したデータがどれだけ含まれるかを調べることができ、創薬における新規化合物の類似化合物の検索や、遺伝子情報の検索等に有用である。
【符号の説明】
【０１０８】
１０  管理装置
１２  データベース
１４  記憶部
１６  クエリー受信部
１８  入力データチェック部
２０  スコア暗号値計算部
２２  設定値変更部
２４  送信順序入替部
２６  結果送信部
２８  ダミーデータ生成部
３０  検索者装置
３２  クエリー入力部
３４  暗号鍵生成部
３６  暗号化部
３８  クエリー送信部
４０  結果受信部
４２  復号化部
４４  判定部
４６  表示部
４８  記憶部
５０  ネットワーク
６０  ＣＰＵ
６２  ＲＡＭ
６４  ＲＯＭ
６６  プログラム
６８  通信インターフェース
７０  ハードディスク
７２  操作部
７４  ディスプレイ
【図１】
0005975490.tif 000016
【図２Ａ】
0005975490.tif 000017
【図２Ｂ】
0005975490.tif 000018
【図２Ｃ】
0005975490.tif 000019
【図３Ａ】
0005975490.tif 000020
【図３Ｂ】
0005975490.tif 000021
【図３Ｃ】
0005975490.tif 000022
【図４】
0005975490.tif 000023
【図５】
0005975490.tif 000024
【図６】
0005975490.tif 000025
【図７】
0005975490.tif 000026
【図８】
0005975490.tif 000027
【図９Ａ】
0005975490.tif 000028
【図９Ｂ】
0005975490.tif 000029
【図１０】
0005975490.tif 000030
【図１１】
0005975490.tif 000031
【図１２】
0005975490.tif 000032
【図１３】
0005975490.tif 000033
【図１４】
0005975490.tif 000034
【図１５】
0005975490.tif 000035
【図１６】
0005975490.tif 000036
【図１７】
0005975490.tif 000037
【図１８】
0005975490.tif 000038