データ格納システム及び情報送信装置及びサーバ装置
【課題】サーバに保存された秘密情報をキーワードを指定して検索でき、その際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムにおいて、サーバの暗号化バッファ容量を低減する。
【解決手段】送信側演算部はサーバ装置から要素ａ１を受信すると暗号化バッファ２２２にａ１を暗号化したＥ（ａ１）を書き込む。次にａ２を受信すると同様にＥ（ａ２）を書き込む。インデックス３の格納領域にＥ（ａ２）を書き込もうとするときに既にＥ（ａ１）が書き込まれているとＥ（ａ１）をＥ（ａ１＋ａ２）と上書きする。情報検索装置は例えばインデックス３、５のＥ（ａ１＋ａ２）、Ｅ（ａ１）を取得すると復号してａ１＋ａ２、ａ１を得る。ａ１、ａ２等は部分和問題を解くことができる集合の要素なので情報検索装置４０１はａ１＋ａ２からａ１、ａ２を特定し、ａ１、ａ２とａ１との共通要素ａ１を特定し、ａ１に対応する秘密情報をサーバ装置から取得する。
【解決手段】送信側演算部はサーバ装置から要素ａ１を受信すると暗号化バッファ２２２にａ１を暗号化したＥ（ａ１）を書き込む。次にａ２を受信すると同様にＥ（ａ２）を書き込む。インデックス３の格納領域にＥ（ａ２）を書き込もうとするときに既にＥ（ａ１）が書き込まれているとＥ（ａ１）をＥ（ａ１＋ａ２）と上書きする。情報検索装置は例えばインデックス３、５のＥ（ａ１＋ａ２）、Ｅ（ａ１）を取得すると復号してａ１＋ａ２、ａ１を得る。ａ１、ａ２等は部分和問題を解くことができる集合の要素なので情報検索装置４０１はａ１＋ａ２からａ１、ａ２を特定し、ａ１、ａ２とａ１との共通要素ａ１を特定し、ａ１に対応する秘密情報をサーバ装置から取得する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、サーバに保存された秘密情報をキーワードを指定して検索でき、その際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムに関する。
【背景技術】
【０００２】
サーバに保存された秘密情報を、検索者がキーワードを指定して検索でき、かつその際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムは、秘密情報管理のアウトソーシングや、メールサーバにおける暗号化メールのフィルタリングへの応用が期待されている。この秘匿検索システムについては、種々の安全性要件を達成するための技術や、サーバや検索者のストレージ・通信オーバーヘッド・演算オーバーヘッドを削減するための様々な技術が提案されている。非特許文献１では、Ｂｌｏｏｍ Ｆｉｌｔｅｒをベースとした、キーワードに複数のハッシュ関数を作用させ、この出力が指定する複数の暗号化バッファに秘密情報を登録することで、秘匿されたキーワードからの秘密情報検索が可能となる方式が開示されている。また、特許文献１では、キーワードを暗号化したものにハッシュ関数を作用させ、生成されたインデックスを類似性に基づきグルーピングすることで、高速な検索を可能とする方式が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−０５２６９８号公報
【非特許文献】
【０００４】
【非特許文献１】Ｄ．Ｂｏｎｅｈ， Ｅ．Ｋｕｓｈｉｌｅｖｉｔｚ， Ｒ．Ｏｓｔｒｏｖｓｋｙ， ａｎｄ Ｗ．Ｓｋｅｉｔｈ， “Ｐｕｂｌｉｃ Ｋｅｙ Ｅｎｃｒｙｐｔｉｏｎ ｔｈａｔ Ａｌｌｏｗｓ ＰＩＲ Ｑｕｅｒｉｅｓ，” Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ − ＣＲＹＰＴＯ ２００７， ＬＮＣＳ ｖｏｌ．４６２２， ｐｐ．５０−６７， ２００７．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一般に、秘匿検索システムでは、複数の文書がサーバに格納され、これに伴いキーワード格納処理も繰り返し実行される。非特許文献１にて開示されている方式では、同一の暗号化バッファに複数の秘密情報が書き込まれるため、上書きによる情報の消失を防ぐために、各暗号化バッファのサイズを十分大きく確保する必要がある。この結果、サーバに必要なストレージが増大し、また通信オーバーヘッドも増大するという課題があった。
【０００６】
本発明は、暗号化バッファに書き込む情報として、部分和問題が解けるような特別な値を利用し、同一の暗号化バッファに複数の秘密情報が書き込まれた際にも各秘密情報が復元可能となるようにすることで、各暗号化バッファのサイズを削減し、サーバに必要なストレージや通信オーバーヘッドを小さく抑えることを目的とする。
【課題を解決するための手段】
【０００７】
この発明のデータ格納システムは、
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置と、前記情報送信装置から送信された暗号化キーワード付加データを受信して格納するサーバ装置とを備えたデータ格納システムにおいて、
前記情報送信装置は、
処理を実行する送信側演算部を備え、
前記サーバ装置は、
アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
所定の暗号化データを格納する格納領域であって暗号化データの格納箇所を示すインデックスが付与された格納領域を有するサーバ側暗号化バッファと、
処理を実行するサーバ側演算部と
を備え、
前記送信側演算部は、
前記暗号化キーワード付加データを前記サーバ装置に送信し、
前記サーバ側演算部は、
前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記情報送信装置に送信し、
前記送信側演算部は、
前記アドレス対応要素を受信すると、前記サーバ装置に送信した前記暗号化キーワード付加データのキーワードを、入力値に対して前記サーバ側暗号化バッファの前記インデックスの示す値の範囲のいずれかの値を出力値として出力する複数の関数であって少なくとも２つの関数は異なる出力値を出力する複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの前記サーバ側暗号化バッファの前記格納領域に前記サーバ装置から受信した前記アドレス対応要素を所定の暗号化方式により暗号化して暗号化データとして書き込むと共に、前記インデックスの示す前記格納領域に暗号化データを既に書き込んでいる場合には、前記暗号化方式を用いることにより、既に書き込んでいる前記暗号化データの平文の示す値に新たに格納しようとする前記アドレス対応要素の平文の示す値が加算され、かつ、暗号化された暗号化データを上書きすることを特徴とする。
【発明の効果】
【０００８】
この発明により、サーバ装置の備える暗号化バッファのサイズを削減し、サーバ装置に必要なストレージや通信オーバーヘッドを小さく抑えることができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１における秘匿検索システム１０００の構成図。
【図２】実施の形態１におけるサーバ装置２０１のブロック図。
【図３】実施の形態１における情報送信装置３０１のブロック図。
【図４】実施の形態１における情報検索装置４０１のブロック図。
【図５】実施の形態１におけるアドレス対応情報を示す図。
【図６】実施の形態１における秘密情報記憶領域２２１を示す図。
【図７】実施の形態１における暗号化バッファ２２２を示す図。
【図８】実施の形態１における秘匿検索システム１０００の動作概要のシーケンス。
【図９】実施の形態１におけるサーバ装置２０１の設定動作のフローチャート。
【図１０】実施の形態１におけるサーバ装置２０１の設定後の各記憶領域状態を示す図。
【図１１】実施の形態１における暗号化バッファ２２２を示す図。
【図１２】実施の形態１における情報送信装置３０１の動作を示すシーケンス。
【図１３】実施の形態１における暗号化バッファ２２２を示す図。
【図１４】実施の形態１における暗号化バッファ２２２を示す図。
【図１５】実施の形態１における暗号化バッファ２２２を示す図。
【図１６】実施の形態１における情報検索装置４０１の動作のシーケンス。
【図１７】実施の形態１における取得した暗号化データを示す図。
【図１８】実施の形態１における復号されたデータを示す図。
【図１９】実施の形態１における部分和として分解されたデータを示す図。
【図２０】実施の形態１における暗号化バッファ２２２の容量削減を示す図。
【図２１】実施の形態２におけるサーバ装置２０１の外観の一例。
【図２２】実施の形態１におけるサーバ装置２０１のハードウェア資源の例を示す図。
【発明を実施するための形態】
【００１０】
実施の形態１．
図１〜図２０を参照して実施の形態１を説明する。図１は、秘匿検索システム１０００（データ格納システム）の構成を示す図である。秘匿検索システム１０００は、サーバ装置２０１に保存された秘密情報を、検索者がキーワードｗを指定して検索でき、かつその際に秘密情報及びキーワードをサーバ装置２０１に対して秘匿可能な秘匿検索システムである。秘匿検索システム１０００は、サーバ装置２０１、複数の情報送信装置３０１、情報検索装置４０１から構成される。サーバ装置２０１、情報送信装置３０１、情報検索装置４０１は互いにネットワーク１０１を介して通信可能である。
【００１１】
図２は、秘密情報を保持し、および保持する秘密情報を検索されるサーバ装置２０１のブロック図である。
【００１２】
（サーバ装置２０１）
サーバ装置２０１は、処理を実行するサーバ側演算部２３２、サーバ側演算部２３２の制御により他の装置と通信を行うサーバ側通信部２３１、情報を記憶するサーバ側記憶部２５０を備えている。サーバ側記憶部２５０は、後述のハッシュ関数を格納するハッシュ関数記憶領域２１１、後述するアドレス対応情報を格納するアドレス対応記憶領域２１２（サーバ側対応情報格納部）、後述の秘密情報ｃ１等を格納する秘密情報記憶領域２２１（サーバ側格納部）、後述の暗号化データＥを格納する暗号化バッファ２２２（サーバ側暗号化バッファ）を備えている。
【００１３】
（サーバ側記憶部２５０）
（１）ハッシュ関数記憶領域２１１は、キーワードｗに作用させる複数のハッシュ関数ｈを記憶するデータ記憶手段であり、ここに記憶されるデータは公開情報として一般に公開される。このハッシュ関数ｈは、情報送信装置３０１、情報検索装置４０１が使用する。（２）アドレス対応記憶領域２１２は、秘密情報記憶領域２２１のアドレスρと、部分和問題の対象となる集合の要素ａ（アドレス対応要素）との対応付けを示すアドレス対応情報を記憶するデータ記憶手段であり、ここに記憶されるデータは公開情報として一般に公開される。アドレス対応情報は、サーバ装置２０１、情報検索装置４０１が利用する。図５は、アドレス対応記憶領域２１２が記憶するデータ（アドレス対応情報）を表す。
（３）秘密情報記憶領域２２１は、情報送信装置３０１から受信した秘密情報（後述のｃ１等）を記憶するデータ記憶手段である。図６は、秘密情報記憶領域２２１が記憶するデータを表している。図６は、情報送信装置３０１から送信された秘密情報ｃｉがアドレスρｉに格納された状態を示している。
（４）暗号化バッファ２２２は、キーワードと、部分和問題の対象となる集合の要素との対応付けを行うためのデータ記憶手段である。図７は、暗号化バッファ２２２が記憶するデータを表す。暗号化バッファ２２２には情報送信装置３０１によって後述の暗号化データＥ（ａ１）等が書き込まれる。
（５）サーバ側通信部２３１は、情報送信装置３０１や情報検索装置４０１と通信を行う手段である。
（６）サーバ側演算部２３２は、共通鍵・公開鍵暗号の鍵生成・暗号化・復号、及びハッシュ関数処理、集合生成、乱数生成などの演算を行う手段である。
【００１４】
（情報送信装置３０１）
図３は、秘匿検索システム１０００において、秘密情報をサーバ装置２０１に送信する情報送信装置３０１のブロック図である。情報送信装置３０１は、送信側通信部３３１、送信側演算部３３２を備えている。送信側通信部３３１は、送信側演算部３３２の制御により他の装置とネットワーク１０１を介して通信を行う。送信側演算部３３２は、共通鍵・公開鍵暗号の鍵生成・暗号化・復号、ハッシュ関数、乱数生成などの演算や処理を行う。
【００１５】
（情報検索装置４０１）
図４は、秘匿検索システム１０００において、サーバ装置２０１に格納された秘密情報を検索・取得する情報検索装置４０１のブロック図である。情報検索装置４０１は、検索側通信部４３１、検索側演算部４３２、検索側記憶部４２０を備えている。検索側記憶部４２０は、秘密鍵記憶領域４２１、検索側関数格納部４２２、検索側対応情報格納部４２３を備えている。
【００１６】
（１）図４において、秘密鍵記憶領域４２１は、自身（その情報検索装置４０１）が利用する公開鍵暗号の「秘密鍵」を記憶するデータ記憶手段である。
（２）検索側関数格納部４２２は、サーバ装置２０１から取得されたハッシュ関数（公開情報）を格納する記憶領域である。
（３）検索側対応情報格納部４２３は、サーバ装置２０１から取得されたアドレス対応情報（公開情報）を格納する記憶領域である。
【００１７】
検索側通信部４３１は、サーバ装置２０１と通信を行う手段である。検索側演算部４３２は、共通鍵・公開鍵暗号の鍵生成・暗号化・復号、ハッシュ関数、乱数生成などの演算を行う手段である。
【００１８】
（秘匿検索システム１０００の動作概要）
図８は秘匿検索システム１０００の動作概要を示すシーケンスである。図８に示すように、秘匿検索システム１０００のシステムの動作は、
（１）サーバ装置２０１の初期設定を行う部分（ステップＳ１０）、
（２）情報送信装置３０１が秘密情報をサーバ装置２０１に送信・格納する部分（ステップＳ２０）、
（３）情報検索装置４０１が秘密情報をサーバ装置２０１から検索・取得する部分（ステップＳ３０）に大別される。以下、それぞれの手続きについて説明する。
【００１９】
（Ｓ１０：サーバの初期設定）
図９は、サーバ装置２０１の初期設定を示すフローチャートである。また、図１０は、初期設定の終了後の各記憶領域の状態を示す図である。
これらを参照して説明する。
【００２０】
（Ｓ１１：ハッシュ関数ｈｉの定義）
Ｓ１１において、サーバ装置２０１は、キーワードｗを入力値とした場合に、１からｔのいずれかを出力値とする、ｋ個の独立なハッシュ関数ｈｉ（ｉ＝１、２、・・・ｋ）を定義し、ハッシュ関数記憶領域２１１に格納して公開情報とする。ハッシュ関数ｈｉ（ｉ＝１、２、・・・ｋ）のうち少なくとも２つの関数は、同一のキーワードｗを入力値とする場合、異なる出力値を出力するものとする。ここで「１からｔ」は、暗号化バッファ２２２のインデックスである。すなわち、同一のキーワードｗを入力とする場合、ハッシュ関数ｈｉ（ｉ＝１、２、・・・ｋ）のうち２つは、異なる２つのインデックス値を出力する。またキーワードｗとは、後述のように、情報送信装置３０１から送信されるデータに含まれるキーワードである。
【００２１】
（Ｓ１２：アドレス対応情報の生成）
次に、Ｓ１２において、サーバ側演算部２３２は、部分和問題が解けるような
集合Ａ＝｛ａ１，ａ２・・・・・・，ａｎ｝
を生成する。部分和問題とは、与えられたｎ個の整数ａ１，ａ２，・・・ａｎから部分集合を選び、その部分集合の和が与えられた整数Ｎに等しくなるようにする問題である。サーバ側演算部２３２は、図１０に示すように、秘密情報記憶領域２２１の
アドレス｛ρ１，ρ２，・・・，ρｎ｝
に集合Ａの要素ａｉ（アドレス対応要素）を対応付けたアドレス対応情報をアドレス対応記憶領域２１２に格納して公開情報とする。部分和問題が解ける集合の生成については後述する。
【００２２】
なお、これらの公開情報（複数のハッシュ関数、アドレス対応情報）は、別の場所で公開しても良いし、情報送信装置３０１や情報検索装置４０１とあらかじめ共有しておいても良い。
【００２３】
（Ｓ１３：初期値Ｅ（０）の設定）
最後に、Ｓ１３において、サーバ側演算部２３２は、情報検索装置４０１に対応する暗号化バッファ２２２の各インデックスに対し、情報検索装置４０１に対応する公開鍵で、０（ゼロ）を暗号化した結果Ｅ（０）を格納する。図１０の暗号化バッファ２２２（図１１そのもの）は、その状態を示している。
【００２４】
（部分和問題が解ける集合について）
部分和問題が解けるような集合としては、
（１）必ず解が一意に定まるように、例えば集合Ａを超増加列となるように取ることが可能である。
（２）また、実用上では、例えば「和がｍ個以下の要素からなる部分和であるという条件下で解が一意に定まる」ような集合Ａを利用することも可能である。このような集合Ａとしては、フィボナッチ数列やトリボナッチ数列をベースとする集合が利用できる。また、互いに素である値（例えばそれぞれ異なる素数）の離散対数をとったものを各要素とする集合も利用可能である。具体的には、
ｎ個の互いに素な数｛ｐ１，ｐ２，・・・，ｐｎ｝
を選び、この中から選んだ任意のｍ個の積よりも大きくなるような素数ｐを選ぶ。群Ｚ／ｐＺの生成元ｇを選び、
ｐｉ≡ｇ＾ａｉ（ｍｏｄ ｐ）
を満たすａｉを全てのｐｉについて求め、これを、
Ａ＝｛ａ１，ａ２，・・・，ａｎ｝
として利用する。部分和問題を解く際には、集合Ａの部分和ｕに対し、
ｒ＝ｇ＾ｕ（ｍｏｄ ｐ）
を求め、ｒがｐｉで割り切れた場合に限りａｉを部分集合の要素と判定すれば良い。
【００２５】
（Ｓ２０：サーバ装置２０１への秘密情報の格納）
図１２は、サーバ装置２０１への秘密情報の格納動作を示すシーケンスである。図１２、及び図１０を参照して秘密情報の格納動作を説明する。
【００２６】
情報送信装置３０１の送信側演算部３３２は、秘密情報にキーワードｗ１を追加したものを、情報検索装置４０１に対応する公開鍵で暗号化し、その結果である暗号化データｃ１（暗号化キーワード付加データ）を送信側通信部３３１を介してサーバ装置２０１に送信する（Ｓ２１）。次に、サーバ装置２０１のサーバ側演算部２３２は、図１０に示すように、受信した暗号文ｃ１を秘密情報記憶領域２２１に格納し（Ｓ２２）、格納したアドレスρｘ（この例ではρ１とする）をもとに、アドレス対応記憶領域２１２のアドレス対応情報から対応する集合Ａの要素ａｘを取得し、ａｘ（アドレス対応要素）をサーバ側通信部２３１を介して情報送信装置３０１に送信する（Ｓ２３）。図１０の例ではアドレスρ１には要素ａ１が対応するので、情報送信装置３０１には要素ａ１が送信される。以下、ａｘを要素ａ１として説明する。
【００２７】
情報送信装置３０１では要素ａ１を受信すると、送信側演算部３３２がサーバ装置２０１の暗号化バッファ２２２に要素ａ１の情報を書き込む（Ｓ２４）。具体的には、送信側演算部３３２がハッシュ関数ｈ１（ｗ１）の値を計算し、暗号化バッファ２２２のインデックスｈ１（ｗ１）の箇所にａ１の情報Ｅ（ａ１）を書き込む。なお情報送信装置３０１は、図示していない送信側記憶部にサーバ装置２０１から取得した公開情報であるハッシュ関数を格納している。Ｅ（ａ１）は所定の暗号化方式によってａ１を暗号化した暗号化データである。この際、非特許文献１にて開示されているＭｏｄｉｆｙプロトコル（所定の暗号化方式の一例）を用いることで、サーバ装置２０１が変更内容（どこの値がどう変わったか）を知ることなく、平文の値に要素ａｘを加算する変更を行うことができる。すなわちＥ（ａ１）が既に存在するような場合においてａ１にａ２を加算する場合は、サーバ装置２０１に変更内容を知られることなく、平文ａ１の値に平文ａ２を加算した暗号化データＥ（ａ１＋ａ２）をＥ（ａ１）を復号することなく得ることができる。
【００２８】
例えば、暗号化バッファ２２２が図１１のようにすべてＥ（０）の内容である場合に、インデックス３の箇所にａ１を暗号化した暗号化データＥ（ａ１）を書き込んだ場合（要素ａ１を受信し、ｈ１（ｗ１）＝３となった場合）、暗号化バッファ２２２の内容は図１３のように、インデックス３の格納領域にＥ（ａ１）が格納される。以上の書き込みをｋ個のハッシュ関数ｈｉのすべてについて行う（Ｓ２５）。例えば、単純な場合を例にとれば、要素ａ１を受信した場合において、
ｈ１（ｗ１）＝３、
ｈ２（ｗ１）＝ｔ、
ｈ３（ｗ１）＝５
である場合、
暗号化バッファ２２２の内容は図１４のようになる。ただし、ｈｉ（ｗ１）の値によって同一のインデックスが複数回指定された場合でも、同一インデックスの箇所への書き込みは一度だけとする。
例えば、
ｈ１（ｗ１）＝３、
ｈ２（ｗ１）＝３
となったような場合は、同一インデックス３の箇所へのＥ（ａ１）の書き込みは一度だけとする。この結果、暗号化バッファ２２２の内容は例えば図１３のようになる。
【００２９】
同様の書き込みは別の秘密情報およびキーワードｗ２についても行われる。例えば、暗号化バッファ２２２が図１４の内容である場合に、別のキーワードｗ２について上記Ｓ２１〜Ｓ２５を行い、ｋ個のハッシュ関数ｈｉについて要素ａ２の情報Ｅ（ａ２）を書き込んだ場合、暗号化バッファ２２２の内容は、例えば図１５のようになる。すなわち、図１２において、送信側演算部３３２が送信側通信部３３１を介してキーワードｗ２を含む暗号文ｃ２をサーバ装置２０１に送信し、サーバ装置２０１から要素ａ２を受信した場合である。この場合も同様にｈ１（ｗ２）等を計算する。例えば下記のようになったとする。
ｈ１（ｗ２）＝３、
ｈ２（ｗ２）＝６、
ｈ３（ｗ２）＝ｔ−１
となったとする。この場合、送信側演算部３３２は、暗号化バッファ２２２のインデックス３、６、ｔ−１に、Ｅ（ａ２）を格納する。図１５に示すように、インデックス３には既にＥ（ａ１）が書き込まれているが、送信側演算部３３２は、上記で述べたように、Ｍｏｄｉｆｙプロトコルに基づいて、サーバ装置２０１に変更内容を知られることなく、平文ａ１の値に平文ａ２を加算した暗号化データＥ（ａ１＋ａ２）をＥ（ａ１）を復号することなく生成して格納する。
【００３０】
（Ｓ３０：情報検索装置４０１による秘密情報の取得）
図１６は、情報検索装置４０１による秘密情報の取得を示すシーケンスである。次に図１６を参照して情報検索装置４０１による秘密情報の取得を説明する。情報検索装置４０１の目的は、あるキーワードｗｉに対し、これに関連する秘密情報をサーバ装置２０１から取得することである。これを達成するために、サーバ装置２０１の暗号化バッファ２２２から、「キーワードｗｉに関連する秘密情報が格納されたアドレスρｘに対応付けられた値ａｘ」の取得を行う。
【００３１】
以下の説明では、キーワードをｗ１とする。まず、検索側演算部４３２がｋ個のハッシュ関数ｈｉ（ｗ１）の値を計算し、暗号化バッファ２２２のインデックスｈｉ（ｗ１）の箇所に格納されている情報Ｅを取得する（ｈｉ（ｗ１）の値に同一のものが含まれる場合は、取得される情報はハッシュ関数の個数ｋ個よりも少なくなる）（Ｓ３１）。ハッシュ関数ｈｉは、公開情報としてサーバ装置２０１が生成したものである。この際、非特許文献１などで開示されているＰＩＲプロトコルを用いることで、サーバ装置２０１が取得内容（情報検索装置４０１がどの値を取得したか）を知ることなく、暗号化データＥを取得できる。例えば、暗号化バッファ２２２が図７の内容である場合には、インデックス３、５、ｔの暗号化データである、
Ｅ（ａ１＋ａ２），Ｅ（ａ１＋ａ４＋ａ５），Ｅ（ａ１＋ａ６）
を取得する。取得した内容は図１７のようになる。
【００３２】
次に、検索側演算部４３２は、秘密鍵記憶領域４２１が保持する秘密鍵を用いて、取得した暗号化データを復号する（Ｓ３２）。例えば、図１７の内容を復号した場合、結果は図１８のようになる。この結果、それぞれの値は部分和問題対象集合Ａの部分和となっている。このため、検索側演算部４３２は部分和問題を解くことで、部分和をＡの要素に分解することができる（Ｓ３３）。例えば、図１８の内容に対して部分和問題を解いた場合、結果は図１９のようになる。すなわち、検索側演算部４３２は部分和問題を解くことにより、例えば、図１８の「ａ１＋ａ２」については、この値を、要素ａ１と要素ａ２とに分解する。
【００３３】
この結果に対し、検索側演算部４３２が共通部分を計算することで、「キーワードｗ１に関連する秘密情報が格納されたアドレスρｘに対応付けられた値ａｘ」が取得できる（Ｓ３４）。例えば、図１９の内容からは、「ａ１、ａ２」、「ａ１、ａ４、ａ５」、「ａ１、ａ６」の共通部分（共通要素）としてａ１が取得される。
【００３４】
その後、情報検索装置４０１は、取得した値ａ１をもとに、サーバ装置２０１のアドレス対応記憶領域２１２から対応するアドレスρ１を取得する（Ｓ３５）。すなわち、情報検索装置４０１は、検索側対応情報格納部４２３にサーバ装置２０１のアドレス対応記憶領域２１２に格納されているアドレス対応情報と同一のアドレス対応情報（検索側アドレス対応情報という）を保有している。検索側演算部４３２は、検索側アドレス対応情報を参照して「ａ１」から「ρ１」を特定する。アドレス対応記憶領域２１２のアドレス対応情報は公開情報であるが、検索側アドレス対応情報は、前もって取得しておき検索側対応情報格納部４２３に格納してもよいし、「ａ１」を特定したときに、サーバ装置２０１から取得して格納しても構わない。
【００３５】
最後に、検索側通信部４３１と検索側演算部４３２がＰＩＲプロトコルを実行し、サーバ装置２０１の秘密情報記憶領域２２１のアドレスρ１に格納されている情報ｃ１を（サーバ装置２０１に内容を知られることなく）取得し、秘密鍵記憶領域４２１が保持する秘密鍵で復号することで目的の（キーワードｗ１に関連する）秘密情報を得ることができる（Ｓ３６）。
【００３６】
非特許文献１にて開示されている方式では、情報送信装置が暗号化バッファへ書き込みを行う際に、上書きによる情報の消失を防ぐために、暗号化バッファの各インデックスに対し、複数個の格納場所を確保する必要があり、結果的に暗号化バッファのサイズを十分大きく確保する必要があった。この結果、サーバに必要なストレージが増大し、またＭｏｄｉｆｙプロトコルにおける通信オーバーヘッドが非常に大きくなるという課題もあった。本実施の形態１のように、部分和問題が解けるような特別な値ａｘを書き込むことで、上書きによる情報の消失を防ぐことができ、暗号化バッファのサイズ、およびＭｏｄｉｆｙプロトコルなどでの通信オーバーヘッドを大幅に削減することが可能となる。
【００３７】
図２０を参照してこの効果を簡単に説明する。図２０は暗号化バッファ２２２を示す図である。実施の形態１の方式（部分和問題対象集合）を採用しない場合は、暗号化バッファ２２２には、インデックスごとに１〜ｑの格納領域を用意する必要があった。そして、情報送信装置３０１は、要素ａにキーワードｗ１が対応する場合において、
ｈ１（ｗ１）＝２、
ｈ２（ｗ１）＝ｔ、
ｈｋ（ｗ１）＝１
である場合、Ｅ（ａ）をインデックス１に複数個書き込み、インデックス２にも複数個書き込み、インデックスｔにも複数個書き込んだ。そして、情報送信装置３０１は、要素ｂにキーワードｗ２が対応する場合において、
ｈ１（ｗ２）＝２
である場合、例えば、インデックス２のｑ列の格納領域に書き込まれているＥ（ａ）をＥ（ａ＋ｂ）と上書きしたが、Ｅ（ａ＋ｂ）からは要素ａ，ｂを取り出すことはできず、Ｅ（ａ＋ｂ）のデータは使用できなかった。言い換えれば、Ｅ（ａ＋ｂ）のように使用できないデータが発生したとしても他の格納領域にＥ（ｂ）が書き込めるようにするため、インデックスごとに１〜ｑの格納領域を用意することで、Ｅ（ａ＋ｂ）のようなデータの発生の手当をしていた。このため暗号化バッファのサイズを十分大きく確保する必要があった。しかし、実施の形態１の方式では要素ａ，ｂは部分和問題対象集合Ａの要素であるので、上記のように、情報検索装置４０１はＥ（ａ＋ｂ）を要素ａ，ｂに分解することが可能である。このため、図２０の暗号化バッファにおいて、インデックスごとに２〜ｑの格納領域は不要となるので、暗号化バッファのサイズを削減できる。
【００３８】
なお、本実施の形態１では、各秘密情報に対し一つのキーワードを対応付けているが、複数のキーワードを対応付けるようにしても良い。
【００３９】
また、本実施の形態１では、各暗号化バッファは値を一つだけ格納できるものとなっているが、複数個の格納場所を確保したうえで、非特許文献１の内容と組み合わせることも可能である。
【００４０】
実施の形態２．
図２１、図２２を参照して実施の形態２を説明する。
【００４１】
実施の形態２は、サーバ装置２０１、情報送信装置３０１、あるいは情報検索装置４０１をコンピュータで実現する具体的な実施形態を示す。サーバ装置２０１、情報送信装置３０１、情報検索装置４０１はずれもコンピュータで実現可能であるので、サーバ装置２０１を想定して説明する。
【００４２】
図２１は、サーバ装置２０１の外観の一例を示す図である。図２１において、サーバ装置２０１は、システムユニット８３０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置８１３、キーボード８１４（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス８１５、ＦＤＤ８１７（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・ Ｄｒｉｖｅ）、コンパクトディスク装置８１８（ＣＤＤ：Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｄｒｉｖｅ）、プリンタ装置８１９などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
【００４３】
図２２は、コンピュータで実現されるサーバ装置２０１のハードウェア資源の一例を示す図である。図２２において、サーバ装置２０１は、プログラムを実行するＣＰＵ８１０（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）を備えている。ＣＰＵ８１０は、バス８２５を介してＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）８１１、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）８１２、表示装置８１３、キーボード８１４、マウス８１５、通信ボード８１６、ＦＤＤ８１７、ＣＤＤ８１８、プリンタ装置８１９、磁気ディスク装置８２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置８２０の代わりに、光ディスク装置、フラッシュメモリなどの記憶装置でもよい。
【００４４】
ＲＡＭ８１２は、揮発性メモリの一例である。ＲＯＭ８１１、ＦＤＤ８１７、ＣＤＤ８１８、磁気ディスク装置８２０等の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部、格納部、バッファの一例である。通信ボード８１６、キーボード８１４、ＦＤＤ８１７などは、入力部、入力装置の一例である。また、通信ボード８１６、表示装置８１３、プリンタ装置８１９などは、出力部、出力装置の一例である。
【００４５】
通信ボード８１６（通信部の一例）は、ネットワーク（ＬＡＮ等）に接続されている。通信ボード８１６は、ＬＡＮに限らず、インターネット、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。
【００４６】
磁気ディスク装置８２０には、オペレーティングシステム８２１（ＯＳ）、ウィンドウシステム８２２、プログラム群８２３、ファイル群８２４が記憶されている。プログラム群８２３のプログラムは、ＣＰＵ８１０、オペレーティングシステム８２１、ウィンドウシステム８２２により実行される。
【００４７】
上記プログラム群８２３には、以上の実施の形態の説明において「〜部」として説明した機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ８１０により読み出され実行される。
【００４８】
ファイル群８２４には、以上の実施の形態の説明において、「ハッシュ関数」、「アドレス対応情報」、「秘密情報」、「暗号化データ」として説明した情報や、「〜の判定結果」、「〜の算出結果」、「〜の抽出結果」、「〜の生成結果」、「〜の処理結果」として説明した情報や、データや信号値や変数値やパラメータなどが、「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ８１０によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００４９】
また、以上に述べた実施の形態の説明において、データや信号値は、ＲＡＭ８１２のメモリ、ＦＤＤ８１７のフレキシブルディスク、ＣＤＤ８１８のコンパクトディスク、磁気ディスク装置８２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス８２５や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００５０】
また、以上の実施の形態の説明において、「〜部」として説明したものは、「〜手段」、「〜回路」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明したものは、ＲＯＭ８１１に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ８１０により読み出され、ＣＰＵ８１０により実行される。すなわち、プログラムは、以上に述べた「〜部」としてコンピュータを機能させるものである。あるいは、以上に述べた「〜部」の手順や方法をコンピュータに実行させるものである。
【００５１】
以上の実施の形態１では、サーバ装置２０１、情報送信装置３０１、情報検索装置４０１として装置を説明したが、実施の形態２のように、サーバ装置２０１等の動作をコンピュータに実行させるプログラムとして把握することも可能である。あるいは、プログラムを記録したコンピュータ読み取り可能な記録媒体として把握することも可能である。さらに、サーバ装置２０１、情報送信装置３０１、情報検索装置４０１の動作をサーバ装置２０１等の行う方法として把握することも可能である。
【００５２】
以上の実施の形態１では、
（１）サーバに保存された秘密情報を、検索者がキーワードを指定して検索でき、かつその際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムにおいて、検索対象の値をＢｌｏｏｍ Ｆｉｌｔｅｒを利用して格納する際、格納する値の集合を、部分和問題が解けるような集合とすることで、複数の値が同一の箇所に格納された場合でもそれぞれの値が得られるようにし、結果としてバッファサイズや通信量を削減する方式を説明した。
（２）また（１）において、部分和問題として、解が一意に定まるものを利用する方式を説明した。
（３）また、（１）において、部分和問題として、ある条件のもとで解が一意に定まるものを利用する方式を説明した。
なお、部分和問題として、ある条件のもとで解が一意に定まるものを利用する具体例としては、次のような場合がある。
ｍ＝２の場合、すなわち２個までの要素の和であれば解ける場合を例に挙げる。例えばフィボナッチ数列をベースとした集合として以下の集合Ａを考える。集合Ａは、通常のフィボナッチ数列の各項から１を引いた数列である。
Ａ＝｛１，２，４，７，１２，２０，３３，５４，．．．｝
このように集合Ａを定めると、与えられた部分和に対し、これを２個までの要素の部分和に分解する方法が高々１とおりに定まる。
例えば、
１１＝７＋４、
１２＝１２、
１３＝１２＋１、
１４＝１２＋２、
１５＝（解なし）、
１６＝１２＋４、
となる。
従って、検索側演算部４３２は、「部分和が２個までの要素からなることを仮定して」、上記のような分解（＝部分和問題を解くこと）を行う。
なお、実際には、情報格納時に（確率は低いながら）３個以上の衝突が生じ、例えば以下のようなケースが生じることが考えられる。
（ａ）同一箇所に２，４，７を書き込んだ場合。
復号して得られる部分和は１３となるため、上記に従い、「１，１２」が書き込まれたと判断してそのまま処理を続行する（誤り）。
（１３＝１２＋１＝７＋４＋２）
（ｂ）同一箇所に１，２，１２を書き込んだ場合。
復号して得られる部分和は１５となり、２個までの要素の部分和で表すことができないため、処理を終了する（失敗）。
３個以上の衝突が生じたことは検出できる。
いずれの場合も本来期待する結果を得ることはできないが、これは３個以上の衝突が生じた場合に限られる。これらの場合には解けないことを犠牲にしながら、衝突が２個までの場合は正しい結果が得られ、また集合Ａの増加スピードを緩やかにできるのが本方式（部分和問題として、ある条件のもとで解が一意に定まるものを利用する場合）の特徴である。
（４）また（３）において、部分和問題として、互いに素である値の離散対数をとったものを各要素とする集合を考えるものを利用する方式を説明した。
【符号の説明】
【００５３】
２０１ サーバ装置、２３１ サーバ側通信部、２３２ サーバ側演算部、２１１ ハッシュ関数記憶領域、２１２ アドレス対応記憶領域、２２１ 秘密情報記憶領域、２２２ 暗号化バッファ、２５０ サーバ側記憶部、３０１ 情報送信装置、３３１ 送信側通信部、３３２ 送信側演算部、４０１ 情報検索装置、３１ 検索側通信部、４３２ 検索側演算部、４２０ 検索側記憶部、４２１ 秘密鍵記憶領域、４２２ 検索側関数格納部、４２３ 検索側対応情報格納部、１０００ 秘匿検索システム。
【技術分野】
【０００１】
この発明は、サーバに保存された秘密情報をキーワードを指定して検索でき、その際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムに関する。
【背景技術】
【０００２】
サーバに保存された秘密情報を、検索者がキーワードを指定して検索でき、かつその際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムは、秘密情報管理のアウトソーシングや、メールサーバにおける暗号化メールのフィルタリングへの応用が期待されている。この秘匿検索システムについては、種々の安全性要件を達成するための技術や、サーバや検索者のストレージ・通信オーバーヘッド・演算オーバーヘッドを削減するための様々な技術が提案されている。非特許文献１では、Ｂｌｏｏｍ Ｆｉｌｔｅｒをベースとした、キーワードに複数のハッシュ関数を作用させ、この出力が指定する複数の暗号化バッファに秘密情報を登録することで、秘匿されたキーワードからの秘密情報検索が可能となる方式が開示されている。また、特許文献１では、キーワードを暗号化したものにハッシュ関数を作用させ、生成されたインデックスを類似性に基づきグルーピングすることで、高速な検索を可能とする方式が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−０５２６９８号公報
【非特許文献】
【０００４】
【非特許文献１】Ｄ．Ｂｏｎｅｈ， Ｅ．Ｋｕｓｈｉｌｅｖｉｔｚ， Ｒ．Ｏｓｔｒｏｖｓｋｙ， ａｎｄ Ｗ．Ｓｋｅｉｔｈ， “Ｐｕｂｌｉｃ Ｋｅｙ Ｅｎｃｒｙｐｔｉｏｎ ｔｈａｔ Ａｌｌｏｗｓ ＰＩＲ Ｑｕｅｒｉｅｓ，” Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ − ＣＲＹＰＴＯ ２００７， ＬＮＣＳ ｖｏｌ．４６２２， ｐｐ．５０−６７， ２００７．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
一般に、秘匿検索システムでは、複数の文書がサーバに格納され、これに伴いキーワード格納処理も繰り返し実行される。非特許文献１にて開示されている方式では、同一の暗号化バッファに複数の秘密情報が書き込まれるため、上書きによる情報の消失を防ぐために、各暗号化バッファのサイズを十分大きく確保する必要がある。この結果、サーバに必要なストレージが増大し、また通信オーバーヘッドも増大するという課題があった。
【０００６】
本発明は、暗号化バッファに書き込む情報として、部分和問題が解けるような特別な値を利用し、同一の暗号化バッファに複数の秘密情報が書き込まれた際にも各秘密情報が復元可能となるようにすることで、各暗号化バッファのサイズを削減し、サーバに必要なストレージや通信オーバーヘッドを小さく抑えることを目的とする。
【課題を解決するための手段】
【０００７】
この発明のデータ格納システムは、
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置と、前記情報送信装置から送信された暗号化キーワード付加データを受信して格納するサーバ装置とを備えたデータ格納システムにおいて、
前記情報送信装置は、
処理を実行する送信側演算部を備え、
前記サーバ装置は、
アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
所定の暗号化データを格納する格納領域であって暗号化データの格納箇所を示すインデックスが付与された格納領域を有するサーバ側暗号化バッファと、
処理を実行するサーバ側演算部と
を備え、
前記送信側演算部は、
前記暗号化キーワード付加データを前記サーバ装置に送信し、
前記サーバ側演算部は、
前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記情報送信装置に送信し、
前記送信側演算部は、
前記アドレス対応要素を受信すると、前記サーバ装置に送信した前記暗号化キーワード付加データのキーワードを、入力値に対して前記サーバ側暗号化バッファの前記インデックスの示す値の範囲のいずれかの値を出力値として出力する複数の関数であって少なくとも２つの関数は異なる出力値を出力する複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの前記サーバ側暗号化バッファの前記格納領域に前記サーバ装置から受信した前記アドレス対応要素を所定の暗号化方式により暗号化して暗号化データとして書き込むと共に、前記インデックスの示す前記格納領域に暗号化データを既に書き込んでいる場合には、前記暗号化方式を用いることにより、既に書き込んでいる前記暗号化データの平文の示す値に新たに格納しようとする前記アドレス対応要素の平文の示す値が加算され、かつ、暗号化された暗号化データを上書きすることを特徴とする。
【発明の効果】
【０００８】
この発明により、サーバ装置の備える暗号化バッファのサイズを削減し、サーバ装置に必要なストレージや通信オーバーヘッドを小さく抑えることができる。
【図面の簡単な説明】
【０００９】
【図１】実施の形態１における秘匿検索システム１０００の構成図。
【図２】実施の形態１におけるサーバ装置２０１のブロック図。
【図３】実施の形態１における情報送信装置３０１のブロック図。
【図４】実施の形態１における情報検索装置４０１のブロック図。
【図５】実施の形態１におけるアドレス対応情報を示す図。
【図６】実施の形態１における秘密情報記憶領域２２１を示す図。
【図７】実施の形態１における暗号化バッファ２２２を示す図。
【図８】実施の形態１における秘匿検索システム１０００の動作概要のシーケンス。
【図９】実施の形態１におけるサーバ装置２０１の設定動作のフローチャート。
【図１０】実施の形態１におけるサーバ装置２０１の設定後の各記憶領域状態を示す図。
【図１１】実施の形態１における暗号化バッファ２２２を示す図。
【図１２】実施の形態１における情報送信装置３０１の動作を示すシーケンス。
【図１３】実施の形態１における暗号化バッファ２２２を示す図。
【図１４】実施の形態１における暗号化バッファ２２２を示す図。
【図１５】実施の形態１における暗号化バッファ２２２を示す図。
【図１６】実施の形態１における情報検索装置４０１の動作のシーケンス。
【図１７】実施の形態１における取得した暗号化データを示す図。
【図１８】実施の形態１における復号されたデータを示す図。
【図１９】実施の形態１における部分和として分解されたデータを示す図。
【図２０】実施の形態１における暗号化バッファ２２２の容量削減を示す図。
【図２１】実施の形態２におけるサーバ装置２０１の外観の一例。
【図２２】実施の形態１におけるサーバ装置２０１のハードウェア資源の例を示す図。
【発明を実施するための形態】
【００１０】
実施の形態１．
図１〜図２０を参照して実施の形態１を説明する。図１は、秘匿検索システム１０００（データ格納システム）の構成を示す図である。秘匿検索システム１０００は、サーバ装置２０１に保存された秘密情報を、検索者がキーワードｗを指定して検索でき、かつその際に秘密情報及びキーワードをサーバ装置２０１に対して秘匿可能な秘匿検索システムである。秘匿検索システム１０００は、サーバ装置２０１、複数の情報送信装置３０１、情報検索装置４０１から構成される。サーバ装置２０１、情報送信装置３０１、情報検索装置４０１は互いにネットワーク１０１を介して通信可能である。
【００１１】
図２は、秘密情報を保持し、および保持する秘密情報を検索されるサーバ装置２０１のブロック図である。
【００１２】
（サーバ装置２０１）
サーバ装置２０１は、処理を実行するサーバ側演算部２３２、サーバ側演算部２３２の制御により他の装置と通信を行うサーバ側通信部２３１、情報を記憶するサーバ側記憶部２５０を備えている。サーバ側記憶部２５０は、後述のハッシュ関数を格納するハッシュ関数記憶領域２１１、後述するアドレス対応情報を格納するアドレス対応記憶領域２１２（サーバ側対応情報格納部）、後述の秘密情報ｃ１等を格納する秘密情報記憶領域２２１（サーバ側格納部）、後述の暗号化データＥを格納する暗号化バッファ２２２（サーバ側暗号化バッファ）を備えている。
【００１３】
（サーバ側記憶部２５０）
（１）ハッシュ関数記憶領域２１１は、キーワードｗに作用させる複数のハッシュ関数ｈを記憶するデータ記憶手段であり、ここに記憶されるデータは公開情報として一般に公開される。このハッシュ関数ｈは、情報送信装置３０１、情報検索装置４０１が使用する。（２）アドレス対応記憶領域２１２は、秘密情報記憶領域２２１のアドレスρと、部分和問題の対象となる集合の要素ａ（アドレス対応要素）との対応付けを示すアドレス対応情報を記憶するデータ記憶手段であり、ここに記憶されるデータは公開情報として一般に公開される。アドレス対応情報は、サーバ装置２０１、情報検索装置４０１が利用する。図５は、アドレス対応記憶領域２１２が記憶するデータ（アドレス対応情報）を表す。
（３）秘密情報記憶領域２２１は、情報送信装置３０１から受信した秘密情報（後述のｃ１等）を記憶するデータ記憶手段である。図６は、秘密情報記憶領域２２１が記憶するデータを表している。図６は、情報送信装置３０１から送信された秘密情報ｃｉがアドレスρｉに格納された状態を示している。
（４）暗号化バッファ２２２は、キーワードと、部分和問題の対象となる集合の要素との対応付けを行うためのデータ記憶手段である。図７は、暗号化バッファ２２２が記憶するデータを表す。暗号化バッファ２２２には情報送信装置３０１によって後述の暗号化データＥ（ａ１）等が書き込まれる。
（５）サーバ側通信部２３１は、情報送信装置３０１や情報検索装置４０１と通信を行う手段である。
（６）サーバ側演算部２３２は、共通鍵・公開鍵暗号の鍵生成・暗号化・復号、及びハッシュ関数処理、集合生成、乱数生成などの演算を行う手段である。
【００１４】
（情報送信装置３０１）
図３は、秘匿検索システム１０００において、秘密情報をサーバ装置２０１に送信する情報送信装置３０１のブロック図である。情報送信装置３０１は、送信側通信部３３１、送信側演算部３３２を備えている。送信側通信部３３１は、送信側演算部３３２の制御により他の装置とネットワーク１０１を介して通信を行う。送信側演算部３３２は、共通鍵・公開鍵暗号の鍵生成・暗号化・復号、ハッシュ関数、乱数生成などの演算や処理を行う。
【００１５】
（情報検索装置４０１）
図４は、秘匿検索システム１０００において、サーバ装置２０１に格納された秘密情報を検索・取得する情報検索装置４０１のブロック図である。情報検索装置４０１は、検索側通信部４３１、検索側演算部４３２、検索側記憶部４２０を備えている。検索側記憶部４２０は、秘密鍵記憶領域４２１、検索側関数格納部４２２、検索側対応情報格納部４２３を備えている。
【００１６】
（１）図４において、秘密鍵記憶領域４２１は、自身（その情報検索装置４０１）が利用する公開鍵暗号の「秘密鍵」を記憶するデータ記憶手段である。
（２）検索側関数格納部４２２は、サーバ装置２０１から取得されたハッシュ関数（公開情報）を格納する記憶領域である。
（３）検索側対応情報格納部４２３は、サーバ装置２０１から取得されたアドレス対応情報（公開情報）を格納する記憶領域である。
【００１７】
検索側通信部４３１は、サーバ装置２０１と通信を行う手段である。検索側演算部４３２は、共通鍵・公開鍵暗号の鍵生成・暗号化・復号、ハッシュ関数、乱数生成などの演算を行う手段である。
【００１８】
（秘匿検索システム１０００の動作概要）
図８は秘匿検索システム１０００の動作概要を示すシーケンスである。図８に示すように、秘匿検索システム１０００のシステムの動作は、
（１）サーバ装置２０１の初期設定を行う部分（ステップＳ１０）、
（２）情報送信装置３０１が秘密情報をサーバ装置２０１に送信・格納する部分（ステップＳ２０）、
（３）情報検索装置４０１が秘密情報をサーバ装置２０１から検索・取得する部分（ステップＳ３０）に大別される。以下、それぞれの手続きについて説明する。
【００１９】
（Ｓ１０：サーバの初期設定）
図９は、サーバ装置２０１の初期設定を示すフローチャートである。また、図１０は、初期設定の終了後の各記憶領域の状態を示す図である。
これらを参照して説明する。
【００２０】
（Ｓ１１：ハッシュ関数ｈｉの定義）
Ｓ１１において、サーバ装置２０１は、キーワードｗを入力値とした場合に、１からｔのいずれかを出力値とする、ｋ個の独立なハッシュ関数ｈｉ（ｉ＝１、２、・・・ｋ）を定義し、ハッシュ関数記憶領域２１１に格納して公開情報とする。ハッシュ関数ｈｉ（ｉ＝１、２、・・・ｋ）のうち少なくとも２つの関数は、同一のキーワードｗを入力値とする場合、異なる出力値を出力するものとする。ここで「１からｔ」は、暗号化バッファ２２２のインデックスである。すなわち、同一のキーワードｗを入力とする場合、ハッシュ関数ｈｉ（ｉ＝１、２、・・・ｋ）のうち２つは、異なる２つのインデックス値を出力する。またキーワードｗとは、後述のように、情報送信装置３０１から送信されるデータに含まれるキーワードである。
【００２１】
（Ｓ１２：アドレス対応情報の生成）
次に、Ｓ１２において、サーバ側演算部２３２は、部分和問題が解けるような
集合Ａ＝｛ａ１，ａ２・・・・・・，ａｎ｝
を生成する。部分和問題とは、与えられたｎ個の整数ａ１，ａ２，・・・ａｎから部分集合を選び、その部分集合の和が与えられた整数Ｎに等しくなるようにする問題である。サーバ側演算部２３２は、図１０に示すように、秘密情報記憶領域２２１の
アドレス｛ρ１，ρ２，・・・，ρｎ｝
に集合Ａの要素ａｉ（アドレス対応要素）を対応付けたアドレス対応情報をアドレス対応記憶領域２１２に格納して公開情報とする。部分和問題が解ける集合の生成については後述する。
【００２２】
なお、これらの公開情報（複数のハッシュ関数、アドレス対応情報）は、別の場所で公開しても良いし、情報送信装置３０１や情報検索装置４０１とあらかじめ共有しておいても良い。
【００２３】
（Ｓ１３：初期値Ｅ（０）の設定）
最後に、Ｓ１３において、サーバ側演算部２３２は、情報検索装置４０１に対応する暗号化バッファ２２２の各インデックスに対し、情報検索装置４０１に対応する公開鍵で、０（ゼロ）を暗号化した結果Ｅ（０）を格納する。図１０の暗号化バッファ２２２（図１１そのもの）は、その状態を示している。
【００２４】
（部分和問題が解ける集合について）
部分和問題が解けるような集合としては、
（１）必ず解が一意に定まるように、例えば集合Ａを超増加列となるように取ることが可能である。
（２）また、実用上では、例えば「和がｍ個以下の要素からなる部分和であるという条件下で解が一意に定まる」ような集合Ａを利用することも可能である。このような集合Ａとしては、フィボナッチ数列やトリボナッチ数列をベースとする集合が利用できる。また、互いに素である値（例えばそれぞれ異なる素数）の離散対数をとったものを各要素とする集合も利用可能である。具体的には、
ｎ個の互いに素な数｛ｐ１，ｐ２，・・・，ｐｎ｝
を選び、この中から選んだ任意のｍ個の積よりも大きくなるような素数ｐを選ぶ。群Ｚ／ｐＺの生成元ｇを選び、
ｐｉ≡ｇ＾ａｉ（ｍｏｄ ｐ）
を満たすａｉを全てのｐｉについて求め、これを、
Ａ＝｛ａ１，ａ２，・・・，ａｎ｝
として利用する。部分和問題を解く際には、集合Ａの部分和ｕに対し、
ｒ＝ｇ＾ｕ（ｍｏｄ ｐ）
を求め、ｒがｐｉで割り切れた場合に限りａｉを部分集合の要素と判定すれば良い。
【００２５】
（Ｓ２０：サーバ装置２０１への秘密情報の格納）
図１２は、サーバ装置２０１への秘密情報の格納動作を示すシーケンスである。図１２、及び図１０を参照して秘密情報の格納動作を説明する。
【００２６】
情報送信装置３０１の送信側演算部３３２は、秘密情報にキーワードｗ１を追加したものを、情報検索装置４０１に対応する公開鍵で暗号化し、その結果である暗号化データｃ１（暗号化キーワード付加データ）を送信側通信部３３１を介してサーバ装置２０１に送信する（Ｓ２１）。次に、サーバ装置２０１のサーバ側演算部２３２は、図１０に示すように、受信した暗号文ｃ１を秘密情報記憶領域２２１に格納し（Ｓ２２）、格納したアドレスρｘ（この例ではρ１とする）をもとに、アドレス対応記憶領域２１２のアドレス対応情報から対応する集合Ａの要素ａｘを取得し、ａｘ（アドレス対応要素）をサーバ側通信部２３１を介して情報送信装置３０１に送信する（Ｓ２３）。図１０の例ではアドレスρ１には要素ａ１が対応するので、情報送信装置３０１には要素ａ１が送信される。以下、ａｘを要素ａ１として説明する。
【００２７】
情報送信装置３０１では要素ａ１を受信すると、送信側演算部３３２がサーバ装置２０１の暗号化バッファ２２２に要素ａ１の情報を書き込む（Ｓ２４）。具体的には、送信側演算部３３２がハッシュ関数ｈ１（ｗ１）の値を計算し、暗号化バッファ２２２のインデックスｈ１（ｗ１）の箇所にａ１の情報Ｅ（ａ１）を書き込む。なお情報送信装置３０１は、図示していない送信側記憶部にサーバ装置２０１から取得した公開情報であるハッシュ関数を格納している。Ｅ（ａ１）は所定の暗号化方式によってａ１を暗号化した暗号化データである。この際、非特許文献１にて開示されているＭｏｄｉｆｙプロトコル（所定の暗号化方式の一例）を用いることで、サーバ装置２０１が変更内容（どこの値がどう変わったか）を知ることなく、平文の値に要素ａｘを加算する変更を行うことができる。すなわちＥ（ａ１）が既に存在するような場合においてａ１にａ２を加算する場合は、サーバ装置２０１に変更内容を知られることなく、平文ａ１の値に平文ａ２を加算した暗号化データＥ（ａ１＋ａ２）をＥ（ａ１）を復号することなく得ることができる。
【００２８】
例えば、暗号化バッファ２２２が図１１のようにすべてＥ（０）の内容である場合に、インデックス３の箇所にａ１を暗号化した暗号化データＥ（ａ１）を書き込んだ場合（要素ａ１を受信し、ｈ１（ｗ１）＝３となった場合）、暗号化バッファ２２２の内容は図１３のように、インデックス３の格納領域にＥ（ａ１）が格納される。以上の書き込みをｋ個のハッシュ関数ｈｉのすべてについて行う（Ｓ２５）。例えば、単純な場合を例にとれば、要素ａ１を受信した場合において、
ｈ１（ｗ１）＝３、
ｈ２（ｗ１）＝ｔ、
ｈ３（ｗ１）＝５
である場合、
暗号化バッファ２２２の内容は図１４のようになる。ただし、ｈｉ（ｗ１）の値によって同一のインデックスが複数回指定された場合でも、同一インデックスの箇所への書き込みは一度だけとする。
例えば、
ｈ１（ｗ１）＝３、
ｈ２（ｗ１）＝３
となったような場合は、同一インデックス３の箇所へのＥ（ａ１）の書き込みは一度だけとする。この結果、暗号化バッファ２２２の内容は例えば図１３のようになる。
【００２９】
同様の書き込みは別の秘密情報およびキーワードｗ２についても行われる。例えば、暗号化バッファ２２２が図１４の内容である場合に、別のキーワードｗ２について上記Ｓ２１〜Ｓ２５を行い、ｋ個のハッシュ関数ｈｉについて要素ａ２の情報Ｅ（ａ２）を書き込んだ場合、暗号化バッファ２２２の内容は、例えば図１５のようになる。すなわち、図１２において、送信側演算部３３２が送信側通信部３３１を介してキーワードｗ２を含む暗号文ｃ２をサーバ装置２０１に送信し、サーバ装置２０１から要素ａ２を受信した場合である。この場合も同様にｈ１（ｗ２）等を計算する。例えば下記のようになったとする。
ｈ１（ｗ２）＝３、
ｈ２（ｗ２）＝６、
ｈ３（ｗ２）＝ｔ−１
となったとする。この場合、送信側演算部３３２は、暗号化バッファ２２２のインデックス３、６、ｔ−１に、Ｅ（ａ２）を格納する。図１５に示すように、インデックス３には既にＥ（ａ１）が書き込まれているが、送信側演算部３３２は、上記で述べたように、Ｍｏｄｉｆｙプロトコルに基づいて、サーバ装置２０１に変更内容を知られることなく、平文ａ１の値に平文ａ２を加算した暗号化データＥ（ａ１＋ａ２）をＥ（ａ１）を復号することなく生成して格納する。
【００３０】
（Ｓ３０：情報検索装置４０１による秘密情報の取得）
図１６は、情報検索装置４０１による秘密情報の取得を示すシーケンスである。次に図１６を参照して情報検索装置４０１による秘密情報の取得を説明する。情報検索装置４０１の目的は、あるキーワードｗｉに対し、これに関連する秘密情報をサーバ装置２０１から取得することである。これを達成するために、サーバ装置２０１の暗号化バッファ２２２から、「キーワードｗｉに関連する秘密情報が格納されたアドレスρｘに対応付けられた値ａｘ」の取得を行う。
【００３１】
以下の説明では、キーワードをｗ１とする。まず、検索側演算部４３２がｋ個のハッシュ関数ｈｉ（ｗ１）の値を計算し、暗号化バッファ２２２のインデックスｈｉ（ｗ１）の箇所に格納されている情報Ｅを取得する（ｈｉ（ｗ１）の値に同一のものが含まれる場合は、取得される情報はハッシュ関数の個数ｋ個よりも少なくなる）（Ｓ３１）。ハッシュ関数ｈｉは、公開情報としてサーバ装置２０１が生成したものである。この際、非特許文献１などで開示されているＰＩＲプロトコルを用いることで、サーバ装置２０１が取得内容（情報検索装置４０１がどの値を取得したか）を知ることなく、暗号化データＥを取得できる。例えば、暗号化バッファ２２２が図７の内容である場合には、インデックス３、５、ｔの暗号化データである、
Ｅ（ａ１＋ａ２），Ｅ（ａ１＋ａ４＋ａ５），Ｅ（ａ１＋ａ６）
を取得する。取得した内容は図１７のようになる。
【００３２】
次に、検索側演算部４３２は、秘密鍵記憶領域４２１が保持する秘密鍵を用いて、取得した暗号化データを復号する（Ｓ３２）。例えば、図１７の内容を復号した場合、結果は図１８のようになる。この結果、それぞれの値は部分和問題対象集合Ａの部分和となっている。このため、検索側演算部４３２は部分和問題を解くことで、部分和をＡの要素に分解することができる（Ｓ３３）。例えば、図１８の内容に対して部分和問題を解いた場合、結果は図１９のようになる。すなわち、検索側演算部４３２は部分和問題を解くことにより、例えば、図１８の「ａ１＋ａ２」については、この値を、要素ａ１と要素ａ２とに分解する。
【００３３】
この結果に対し、検索側演算部４３２が共通部分を計算することで、「キーワードｗ１に関連する秘密情報が格納されたアドレスρｘに対応付けられた値ａｘ」が取得できる（Ｓ３４）。例えば、図１９の内容からは、「ａ１、ａ２」、「ａ１、ａ４、ａ５」、「ａ１、ａ６」の共通部分（共通要素）としてａ１が取得される。
【００３４】
その後、情報検索装置４０１は、取得した値ａ１をもとに、サーバ装置２０１のアドレス対応記憶領域２１２から対応するアドレスρ１を取得する（Ｓ３５）。すなわち、情報検索装置４０１は、検索側対応情報格納部４２３にサーバ装置２０１のアドレス対応記憶領域２１２に格納されているアドレス対応情報と同一のアドレス対応情報（検索側アドレス対応情報という）を保有している。検索側演算部４３２は、検索側アドレス対応情報を参照して「ａ１」から「ρ１」を特定する。アドレス対応記憶領域２１２のアドレス対応情報は公開情報であるが、検索側アドレス対応情報は、前もって取得しておき検索側対応情報格納部４２３に格納してもよいし、「ａ１」を特定したときに、サーバ装置２０１から取得して格納しても構わない。
【００３５】
最後に、検索側通信部４３１と検索側演算部４３２がＰＩＲプロトコルを実行し、サーバ装置２０１の秘密情報記憶領域２２１のアドレスρ１に格納されている情報ｃ１を（サーバ装置２０１に内容を知られることなく）取得し、秘密鍵記憶領域４２１が保持する秘密鍵で復号することで目的の（キーワードｗ１に関連する）秘密情報を得ることができる（Ｓ３６）。
【００３６】
非特許文献１にて開示されている方式では、情報送信装置が暗号化バッファへ書き込みを行う際に、上書きによる情報の消失を防ぐために、暗号化バッファの各インデックスに対し、複数個の格納場所を確保する必要があり、結果的に暗号化バッファのサイズを十分大きく確保する必要があった。この結果、サーバに必要なストレージが増大し、またＭｏｄｉｆｙプロトコルにおける通信オーバーヘッドが非常に大きくなるという課題もあった。本実施の形態１のように、部分和問題が解けるような特別な値ａｘを書き込むことで、上書きによる情報の消失を防ぐことができ、暗号化バッファのサイズ、およびＭｏｄｉｆｙプロトコルなどでの通信オーバーヘッドを大幅に削減することが可能となる。
【００３７】
図２０を参照してこの効果を簡単に説明する。図２０は暗号化バッファ２２２を示す図である。実施の形態１の方式（部分和問題対象集合）を採用しない場合は、暗号化バッファ２２２には、インデックスごとに１〜ｑの格納領域を用意する必要があった。そして、情報送信装置３０１は、要素ａにキーワードｗ１が対応する場合において、
ｈ１（ｗ１）＝２、
ｈ２（ｗ１）＝ｔ、
ｈｋ（ｗ１）＝１
である場合、Ｅ（ａ）をインデックス１に複数個書き込み、インデックス２にも複数個書き込み、インデックスｔにも複数個書き込んだ。そして、情報送信装置３０１は、要素ｂにキーワードｗ２が対応する場合において、
ｈ１（ｗ２）＝２
である場合、例えば、インデックス２のｑ列の格納領域に書き込まれているＥ（ａ）をＥ（ａ＋ｂ）と上書きしたが、Ｅ（ａ＋ｂ）からは要素ａ，ｂを取り出すことはできず、Ｅ（ａ＋ｂ）のデータは使用できなかった。言い換えれば、Ｅ（ａ＋ｂ）のように使用できないデータが発生したとしても他の格納領域にＥ（ｂ）が書き込めるようにするため、インデックスごとに１〜ｑの格納領域を用意することで、Ｅ（ａ＋ｂ）のようなデータの発生の手当をしていた。このため暗号化バッファのサイズを十分大きく確保する必要があった。しかし、実施の形態１の方式では要素ａ，ｂは部分和問題対象集合Ａの要素であるので、上記のように、情報検索装置４０１はＥ（ａ＋ｂ）を要素ａ，ｂに分解することが可能である。このため、図２０の暗号化バッファにおいて、インデックスごとに２〜ｑの格納領域は不要となるので、暗号化バッファのサイズを削減できる。
【００３８】
なお、本実施の形態１では、各秘密情報に対し一つのキーワードを対応付けているが、複数のキーワードを対応付けるようにしても良い。
【００３９】
また、本実施の形態１では、各暗号化バッファは値を一つだけ格納できるものとなっているが、複数個の格納場所を確保したうえで、非特許文献１の内容と組み合わせることも可能である。
【００４０】
実施の形態２．
図２１、図２２を参照して実施の形態２を説明する。
【００４１】
実施の形態２は、サーバ装置２０１、情報送信装置３０１、あるいは情報検索装置４０１をコンピュータで実現する具体的な実施形態を示す。サーバ装置２０１、情報送信装置３０１、情報検索装置４０１はずれもコンピュータで実現可能であるので、サーバ装置２０１を想定して説明する。
【００４２】
図２１は、サーバ装置２０１の外観の一例を示す図である。図２１において、サーバ装置２０１は、システムユニット８３０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置８１３、キーボード８１４（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス８１５、ＦＤＤ８１７（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・ Ｄｒｉｖｅ）、コンパクトディスク装置８１８（ＣＤＤ：Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｄｒｉｖｅ）、プリンタ装置８１９などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
【００４３】
図２２は、コンピュータで実現されるサーバ装置２０１のハードウェア資源の一例を示す図である。図２２において、サーバ装置２０１は、プログラムを実行するＣＰＵ８１０（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）を備えている。ＣＰＵ８１０は、バス８２５を介してＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）８１１、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）８１２、表示装置８１３、キーボード８１４、マウス８１５、通信ボード８１６、ＦＤＤ８１７、ＣＤＤ８１８、プリンタ装置８１９、磁気ディスク装置８２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置８２０の代わりに、光ディスク装置、フラッシュメモリなどの記憶装置でもよい。
【００４４】
ＲＡＭ８１２は、揮発性メモリの一例である。ＲＯＭ８１１、ＦＤＤ８１７、ＣＤＤ８１８、磁気ディスク装置８２０等の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部、格納部、バッファの一例である。通信ボード８１６、キーボード８１４、ＦＤＤ８１７などは、入力部、入力装置の一例である。また、通信ボード８１６、表示装置８１３、プリンタ装置８１９などは、出力部、出力装置の一例である。
【００４５】
通信ボード８１６（通信部の一例）は、ネットワーク（ＬＡＮ等）に接続されている。通信ボード８１６は、ＬＡＮに限らず、インターネット、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。
【００４６】
磁気ディスク装置８２０には、オペレーティングシステム８２１（ＯＳ）、ウィンドウシステム８２２、プログラム群８２３、ファイル群８２４が記憶されている。プログラム群８２３のプログラムは、ＣＰＵ８１０、オペレーティングシステム８２１、ウィンドウシステム８２２により実行される。
【００４７】
上記プログラム群８２３には、以上の実施の形態の説明において「〜部」として説明した機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ８１０により読み出され実行される。
【００４８】
ファイル群８２４には、以上の実施の形態の説明において、「ハッシュ関数」、「アドレス対応情報」、「秘密情報」、「暗号化データ」として説明した情報や、「〜の判定結果」、「〜の算出結果」、「〜の抽出結果」、「〜の生成結果」、「〜の処理結果」として説明した情報や、データや信号値や変数値やパラメータなどが、「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ８１０によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００４９】
また、以上に述べた実施の形態の説明において、データや信号値は、ＲＡＭ８１２のメモリ、ＦＤＤ８１７のフレキシブルディスク、ＣＤＤ８１８のコンパクトディスク、磁気ディスク装置８２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス８２５や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００５０】
また、以上の実施の形態の説明において、「〜部」として説明したものは、「〜手段」、「〜回路」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明したものは、ＲＯＭ８１１に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ８１０により読み出され、ＣＰＵ８１０により実行される。すなわち、プログラムは、以上に述べた「〜部」としてコンピュータを機能させるものである。あるいは、以上に述べた「〜部」の手順や方法をコンピュータに実行させるものである。
【００５１】
以上の実施の形態１では、サーバ装置２０１、情報送信装置３０１、情報検索装置４０１として装置を説明したが、実施の形態２のように、サーバ装置２０１等の動作をコンピュータに実行させるプログラムとして把握することも可能である。あるいは、プログラムを記録したコンピュータ読み取り可能な記録媒体として把握することも可能である。さらに、サーバ装置２０１、情報送信装置３０１、情報検索装置４０１の動作をサーバ装置２０１等の行う方法として把握することも可能である。
【００５２】
以上の実施の形態１では、
（１）サーバに保存された秘密情報を、検索者がキーワードを指定して検索でき、かつその際に秘密情報・キーワードをサーバに対して秘匿する秘匿検索システムにおいて、検索対象の値をＢｌｏｏｍ Ｆｉｌｔｅｒを利用して格納する際、格納する値の集合を、部分和問題が解けるような集合とすることで、複数の値が同一の箇所に格納された場合でもそれぞれの値が得られるようにし、結果としてバッファサイズや通信量を削減する方式を説明した。
（２）また（１）において、部分和問題として、解が一意に定まるものを利用する方式を説明した。
（３）また、（１）において、部分和問題として、ある条件のもとで解が一意に定まるものを利用する方式を説明した。
なお、部分和問題として、ある条件のもとで解が一意に定まるものを利用する具体例としては、次のような場合がある。
ｍ＝２の場合、すなわち２個までの要素の和であれば解ける場合を例に挙げる。例えばフィボナッチ数列をベースとした集合として以下の集合Ａを考える。集合Ａは、通常のフィボナッチ数列の各項から１を引いた数列である。
Ａ＝｛１，２，４，７，１２，２０，３３，５４，．．．｝
このように集合Ａを定めると、与えられた部分和に対し、これを２個までの要素の部分和に分解する方法が高々１とおりに定まる。
例えば、
１１＝７＋４、
１２＝１２、
１３＝１２＋１、
１４＝１２＋２、
１５＝（解なし）、
１６＝１２＋４、
となる。
従って、検索側演算部４３２は、「部分和が２個までの要素からなることを仮定して」、上記のような分解（＝部分和問題を解くこと）を行う。
なお、実際には、情報格納時に（確率は低いながら）３個以上の衝突が生じ、例えば以下のようなケースが生じることが考えられる。
（ａ）同一箇所に２，４，７を書き込んだ場合。
復号して得られる部分和は１３となるため、上記に従い、「１，１２」が書き込まれたと判断してそのまま処理を続行する（誤り）。
（１３＝１２＋１＝７＋４＋２）
（ｂ）同一箇所に１，２，１２を書き込んだ場合。
復号して得られる部分和は１５となり、２個までの要素の部分和で表すことができないため、処理を終了する（失敗）。
３個以上の衝突が生じたことは検出できる。
いずれの場合も本来期待する結果を得ることはできないが、これは３個以上の衝突が生じた場合に限られる。これらの場合には解けないことを犠牲にしながら、衝突が２個までの場合は正しい結果が得られ、また集合Ａの増加スピードを緩やかにできるのが本方式（部分和問題として、ある条件のもとで解が一意に定まるものを利用する場合）の特徴である。
（４）また（３）において、部分和問題として、互いに素である値の離散対数をとったものを各要素とする集合を考えるものを利用する方式を説明した。
【符号の説明】
【００５３】
２０１ サーバ装置、２３１ サーバ側通信部、２３２ サーバ側演算部、２１１ ハッシュ関数記憶領域、２１２ アドレス対応記憶領域、２２１ 秘密情報記憶領域、２２２ 暗号化バッファ、２５０ サーバ側記憶部、３０１ 情報送信装置、３３１ 送信側通信部、３３２ 送信側演算部、４０１ 情報検索装置、３１ 検索側通信部、４３２ 検索側演算部、４２０ 検索側記憶部、４２１ 秘密鍵記憶領域、４２２ 検索側関数格納部、４２３ 検索側対応情報格納部、１０００ 秘匿検索システム。
【特許請求の範囲】
【請求項１】
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置と、前記情報送信装置から送信された暗号化キーワード付加データを受信して格納するサーバ装置とを備えたデータ格納システムにおいて、
前記情報送信装置は、
処理を実行する送信側演算部を備え、
前記サーバ装置は、
アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
所定の暗号化データを格納する格納領域であって暗号化データの格納箇所を示すインデックスが付与された格納領域を有するサーバ側暗号化バッファと、
処理を実行するサーバ側演算部と
を備え、
前記送信側演算部は、
前記暗号化キーワード付加データを前記サーバ装置に送信し、
前記サーバ側演算部は、
前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記情報送信装置に送信し、
前記送信側演算部は、
前記アドレス対応要素を受信すると、前記サーバ装置に送信した前記暗号化キーワード付加データのキーワードを、入力値に対して前記サーバ側暗号化バッファの前記インデックスの示す値の範囲のいずれかの値を出力値として出力する複数の関数であって少なくとも２つの関数は異なる出力値を出力する複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの前記サーバ側暗号化バッファの前記格納領域に前記サーバ装置から受信した前記アドレス対応要素を所定の暗号化方式により暗号化して暗号化データとして書き込むと共に、前記インデックスの示す前記格納領域に暗号化データを既に書き込んでいる場合には、前記暗号化方式を用いることにより、既に書き込んでいる前記暗号化データの平文の示す値に新たに格納しようとする前記アドレス対応要素の平文の示す値が加算され、かつ、暗号化された暗号化データを上書きすることを特徴とするデータ格納システム。
【請求項２】
前記データ格納システムは、さらに、
前記サーバ装置と通信することにより前記サーバ装置に格納されている暗号化キーワード付加データを検索して取得する情報検索装置を備え、
前記情報検索装置は、
前記情報送信装置が使用する前記複数の関数と同一の複数の関数を格納する検索側関数格納部と、
前記サーバ側格納部に格納された前記アドレス対応情報と同一の情報である検索側アドレス対応情報を格納する検索側対応情報格納部と、
取得対象の暗号化キーワード付加データのキーワードを前記検索側関数格納部の前記複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの格納領域に格納されている暗号化データを前記サーバ側暗号化バッファからすべて取得し、取得されたすべての暗号化データを復号し、復号された各暗号化データの値を対象として部分和問題を解くことにより復号後の暗号化データを部分和をなす要素に分解し、復号後のどの暗号化データにも共通して存在するアドレス対応要素を共通要素として特定し、特定された共通要素に対応するアドレスを前記検索側対応情報格納部の検索側アドレス対応情報を参照することにより特定し、特定されたアドレスに格納されている暗号化キーワード付加データを前記サーバ側格納部から取得し、取得された前記暗号化キーワード付加データを復号する検索側演算部と
を備えたことを特徴とする請求項１記載のデータ格納システム。
【請求項３】
前記部分和問題対象集合は、
部分和問題として解が一意に定まる集合と、部分和問題として所定の条件のもとで解が一意に定まる集合とのいずかであることを特徴とする請求項１または２のいずれかに記載のデータ格納システム。
【請求項４】
前記部分和問題対象集合は、
部分和問題として、互いに素である値の離散対数をとった値を各要素とすることを特徴とする請求項１または２のいずれかに記載のデータ格納システム。
【請求項５】
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置を送信する情報送信装置において、
前記暗号化キーワード付加データを受信するサーバ装置であって、
前記アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
所定の暗号化データを格納する格納領域であって暗号化データの格納箇所を示すインデックスが付与された格納領域を有するサーバ側暗号化バッファと、
前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記暗号化キーワード付加データの送信元に送信するサーバ側演算部と
を備えたサーバ装置から、
前記アドレス対応要素を受信すると、前記サーバ装置に送信した前記暗号化キーワード付加データのキーワードを、入力値に対して前記サーバ側暗号化バッファの前記インデックスの示す値の範囲のいずれかの値を出力値として出力する複数の関数であって少なくとも２つの関数は異なる出力値を出力する複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの前記サーバ側暗号化バッファの前記格納領域に前記サーバ装置から受信した前記アドレス対応要素を所定の暗号化方式により暗号化して暗号化データとして書き込むと共に、前記インデックスの示す前記格納領域に暗号化データを既に書き込んでいる場合には、前記暗号化方式を用いることにより、既に書き込んでいる前記暗号化データの平文の示す値に新たに格納しようとする前記アドレス対応要素の平文の示す値が加算され、かつ、暗号化された暗号化データを上書きする送信側演算部
を備えたことを特徴とする情報送信装置。
【請求項６】
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置から暗号化キーワード付加データを受信して格納するサーバ装置において、
アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
前記情報送信装置から前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記情報送信装置に送信するサーバ側演算部と、
前記アドレス対応要素を受信した前記情報送信装置によって暗号化データが格納されるサーバ側暗号化バッファと
を備えたことを特徴とするサーバ装置。
【請求項１】
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置と、前記情報送信装置から送信された暗号化キーワード付加データを受信して格納するサーバ装置とを備えたデータ格納システムにおいて、
前記情報送信装置は、
処理を実行する送信側演算部を備え、
前記サーバ装置は、
アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
所定の暗号化データを格納する格納領域であって暗号化データの格納箇所を示すインデックスが付与された格納領域を有するサーバ側暗号化バッファと、
処理を実行するサーバ側演算部と
を備え、
前記送信側演算部は、
前記暗号化キーワード付加データを前記サーバ装置に送信し、
前記サーバ側演算部は、
前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記情報送信装置に送信し、
前記送信側演算部は、
前記アドレス対応要素を受信すると、前記サーバ装置に送信した前記暗号化キーワード付加データのキーワードを、入力値に対して前記サーバ側暗号化バッファの前記インデックスの示す値の範囲のいずれかの値を出力値として出力する複数の関数であって少なくとも２つの関数は異なる出力値を出力する複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの前記サーバ側暗号化バッファの前記格納領域に前記サーバ装置から受信した前記アドレス対応要素を所定の暗号化方式により暗号化して暗号化データとして書き込むと共に、前記インデックスの示す前記格納領域に暗号化データを既に書き込んでいる場合には、前記暗号化方式を用いることにより、既に書き込んでいる前記暗号化データの平文の示す値に新たに格納しようとする前記アドレス対応要素の平文の示す値が加算され、かつ、暗号化された暗号化データを上書きすることを特徴とするデータ格納システム。
【請求項２】
前記データ格納システムは、さらに、
前記サーバ装置と通信することにより前記サーバ装置に格納されている暗号化キーワード付加データを検索して取得する情報検索装置を備え、
前記情報検索装置は、
前記情報送信装置が使用する前記複数の関数と同一の複数の関数を格納する検索側関数格納部と、
前記サーバ側格納部に格納された前記アドレス対応情報と同一の情報である検索側アドレス対応情報を格納する検索側対応情報格納部と、
取得対象の暗号化キーワード付加データのキーワードを前記検索側関数格納部の前記複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの格納領域に格納されている暗号化データを前記サーバ側暗号化バッファからすべて取得し、取得されたすべての暗号化データを復号し、復号された各暗号化データの値を対象として部分和問題を解くことにより復号後の暗号化データを部分和をなす要素に分解し、復号後のどの暗号化データにも共通して存在するアドレス対応要素を共通要素として特定し、特定された共通要素に対応するアドレスを前記検索側対応情報格納部の検索側アドレス対応情報を参照することにより特定し、特定されたアドレスに格納されている暗号化キーワード付加データを前記サーバ側格納部から取得し、取得された前記暗号化キーワード付加データを復号する検索側演算部と
を備えたことを特徴とする請求項１記載のデータ格納システム。
【請求項３】
前記部分和問題対象集合は、
部分和問題として解が一意に定まる集合と、部分和問題として所定の条件のもとで解が一意に定まる集合とのいずかであることを特徴とする請求項１または２のいずれかに記載のデータ格納システム。
【請求項４】
前記部分和問題対象集合は、
部分和問題として、互いに素である値の離散対数をとった値を各要素とすることを特徴とする請求項１または２のいずれかに記載のデータ格納システム。
【請求項５】
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置を送信する情報送信装置において、
前記暗号化キーワード付加データを受信するサーバ装置であって、
前記アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
所定の暗号化データを格納する格納領域であって暗号化データの格納箇所を示すインデックスが付与された格納領域を有するサーバ側暗号化バッファと、
前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記暗号化キーワード付加データの送信元に送信するサーバ側演算部と
を備えたサーバ装置から、
前記アドレス対応要素を受信すると、前記サーバ装置に送信した前記暗号化キーワード付加データのキーワードを、入力値に対して前記サーバ側暗号化バッファの前記インデックスの示す値の範囲のいずれかの値を出力値として出力する複数の関数であって少なくとも２つの関数は異なる出力値を出力する複数の関数の各関数に入力値として入力して出力値を取得し、取得された前記出力値の示すインデックスの前記サーバ側暗号化バッファの前記格納領域に前記サーバ装置から受信した前記アドレス対応要素を所定の暗号化方式により暗号化して暗号化データとして書き込むと共に、前記インデックスの示す前記格納領域に暗号化データを既に書き込んでいる場合には、前記暗号化方式を用いることにより、既に書き込んでいる前記暗号化データの平文の示す値に新たに格納しようとする前記アドレス対応要素の平文の示す値が加算され、かつ、暗号化された暗号化データを上書きする送信側演算部
を備えたことを特徴とする情報送信装置。
【請求項６】
データに検索用のキーワードが付加され暗号化された暗号化キーワード付加データを送信する情報送信装置から暗号化キーワード付加データを受信して格納するサーバ装置において、
アドレスが付与されたそれぞれの格納領域を有するサーバ側格納部と、
前記サーバ側格納部の各アドレスに対して、集合の要素のうち互いに異なる要素の和からその和をなす要素を特定する部分和問題が解ける集合を示す部分和問題対象集合の要素をアドレス対応要素として対応付けたアドレス対応情報を格納するサーバ側対応情報格納部と、
前記情報送信装置から前記暗号化キーワード付加データを受信すると、受信された前記暗号化キーワード付加データを前記サーバ側格納部のいずれかの格納領域に格納し、前記暗号化キーワード付加データが格納された格納領域のアドレスに対応する前記アドレス対応要素を前記アドレス対応情報から特定し、特定された前記アドレス対応要素を前記情報送信装置に送信するサーバ側演算部と、
前記アドレス対応要素を受信した前記情報送信装置によって暗号化データが格納されるサーバ側暗号化バッファと
を備えたことを特徴とするサーバ装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１０−１６５２７５（Ｐ２０１０−１６５２７５Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−８６０９（Ｐ２００９−８６０９）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【出願人】（５０４１３３１１０）国立大学法人電気通信大学 (383)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【出願人】（５０４１３３１１０）国立大学法人電気通信大学 (383)
【Ｆターム（参考）】
[ Back to top ]