Pat

J-GLOBAL ID：201603013644769637

検索システム、検索方法、およびプログラム

Inventor： 岩村 佳奈 ,  広川 貴次 ,  津田 宏治 ,  荒井 ひろみ ,  佐久間 淳 ,  浅井 潔 ,  浜田 道昭 ,  花岡 悟一郎 ,  縫田 光司
Applicant, Patent owner： 国立研究開発法人産業技術総合研究所 ,  国立大学法人 筑波大学 ,  国立大学法人 東京大学
Agent (6)： 大野 聖二 ,  森田 耕司 ,  田中 玲子 ,  鈴木 守 ,  加藤 真司 ,  津田 理
Gazette classification：特許公報
Application number (International application number)：2013533524
Patent number：5975490
Application date： Sep. 14, 2012
Claim (excerpt)：

【請求項1】 物の部分構造または性質を表すデータを記憶したデータベースを有する管理装置と、前記データベースの検索条件の入力および検索結果の出力を行う検索者装置とを備え、前記データは、予め定められた複数の部分構造または性質について物が前記部分構造または性質を有する場合に「1」、有しない場合に「0」を設定した数列データであり、 前記検索者装置にて検索条件として入力された物の部分構造または性質を表すクエリー数列データqと、前記データベースに記憶された物の数列データpi(i=1,2,・・・m:mは数列データの数)とのTversky係数Si が閾値θn/θd(ただし、θn、θdはθn≦θdを満たす自然数)以上の数列データpiが、前記データベースに含まれているかを調べる、以下のステップを有する検索方法。 (1)前記検索者装置が、加法準同型性を有する暗号の公開鍵及び秘密鍵を生成する。 (2)前記検索者装置が、クエリー数列データqの入力を受け付ける。 (3)前記検索者装置が、前記クエリー数列データqを構成する要素のうちで値が「1」の要素数|q|を求め、当該要素数|q|に負号を付した値を前記公開鍵で暗号化すると共に、前記クエリー数列データqの各要素qj(ただし、j=1,・・・n:nはクエリー数列qの長さ)の値を前記公開鍵で暗号化する。 (4)前記検索者装置が、前記公開鍵と前記暗号値Enc(-|q|)とクエリー数列データqの各要素の暗号値Enc(q1),Enc(q2),・・・Enc(qn)を前記管理装置に対して出力する。 (5)前記管理装置が、前記検索者装置から出力された前記公開鍵と前記暗号値Enc(-|q|)とクエリー数列データqの各要素の暗号値Enc(q1),Enc(q2),・・・Enc(qn)を受け取る。 (6)前記管理装置が、前記データベースから一の数列データpiを読み出す。 (7)前記管理装置が、前記数列データpiを構成する要素のうちで値が「1」の要素数|pi|を求め、当該要素数|pi|に負号を付した値を前記公開鍵で暗号化する。 (8)前記管理装置が、前記数列データpiの各要素pi,j(ただし、j=0,1,・・・n:nは数列データpiの長さ)を調べ、値が「1」を有する要素に対応するクエリー数列データqのすべての要素qk(kはpi,k=1を満たす)の平文における加算に対応する計算を、暗号の加法準同型性を利用して暗号値Enc(qk)に対して行い、クエリー数列データqと数列データpiにおいて値がともに「1」の要素数|pi∩q|の暗号値Enc(|pi∩q|)を求める。 (9)前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Enc(|pi∩q|)に対して、平文において(|pi∩q|)を{γ(θd-θn)+θn(μa+μb)}回加算する計算に対応する計算を行って、暗号値Enc((|pi∩q|)×{γ(θd-θn)+θn(μa+μb))を求める。 (10)前記管理装置が、暗号の加法準同型性を利用して、前記暗号値Enc(-|q|)に対して平文において(-|q|)をμa回加算する計算に対応する計算を行って暗号値Enc(μa(-|q|))を求めるとともに、前記暗号値Enc(-|pi|)に対して平文において(-|pi|)をμb回加算する計算に対応する計算を行って暗号値Enc(μb(-|pi|))を求め、前記暗号値Enc(μa(-|q|))と前記暗号値Enc(μb(-|pi|))に対して平文におけるμa(-|q|)+μb(-|pi|)に対応する計算を行って暗号値Enc(μa(-|q|)+μb(-|pi|))を求め、さらに、暗号値Enc(μa(-|q|)+μb(-|pi|))に対して平文において(μa(-|q|)+μb(-|pi|))をθn回加算する計算に対応する計算を行って、暗号値Enc(θn(μa(-|q|)+μb(-|pi|)))を求める。 (11)前記管理装置が、暗号の加法準同型性を利用して、上記(9)で求めた暗号値Enc((|pi∩q|)×{γ(θd-θn)+θn(μa+μb)}と、上記(10)で求めた暗号値Enc(θn(μa(-|q|)+μb(-|pi|)))に対して、平文における(|pi∩q|)×{γ(θd-θn)+θn(μa+μb)+θn(μa(-|q|)+μb(-|pi|))に対応する計算を行い、暗号値Enc((|pi∩q|)×{γ(θd-θn)+θn(μa+μb)+θn(μa(-|q|)+μb(-|pi|))})をスコアTiの暗号値として求める。(12)前記管理装置が、前記データベースに含まれる複数の数列データpiのそれぞれについて、上記(6)から(11)を繰り返し行い、各数列データpiに対するスコアTiの暗号値を求める。 (13)前記管理装置が、前記スコアT1,T2,・・・Tmの暗号値を検索者装置に対して出力する。 (14)前記検索者装置が、前記管理装置から出力された前記スコアT1,T2,・・・Tmの暗号値を受け取る。 (15)前記検索者装置が、前記スコアT1,T2,・・・Tmの暗号値を前記秘密鍵で復号する。 (16)前記検索者装置が、前記スコアT1,T2,・・・Tmの非負/負を判定する。 (17)前記検索者装置が、判定結果を出力する。

IPC (3)：

G09C 1/00 ( 200 6.01) ,  G06F 17/30 ( 200 6.01) ,  H04L 9/30 ( 200 6.01)

FI (5)：

G09C 1/00 660 D ,  G06F 17/30 120 A ,  H04L 9/00 663 A ,  G06F 17/30 350 C ,  G06F 17/30 170 F