TOP > 国内特許検索 > 暗号検索システム、暗号検索方法および暗号検索プログラム

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

国内特許コード P140010748
整理番号 S2014-0231-N0
掲載日 2014年7月10日
出願番号 特願2013-255286
公開番号 特開2015-114432
出願日 平成25年12月10日(2013.12.10)
公開日 平成27年6月22日(2015.6.22)
発明者
  • 黒澤 馨
出願人
  • 国立大学法人茨城大学
発明の名称 暗号検索システム、暗号検索方法および暗号検索プログラム
発明の概要 【課題】検索式を秘匿し、検索フェーズを2-passとすること。
【解決手段】格納フェーズでは、キーワード暗号化部により暗号化された第1乃至第Nの暗号キーワードを列の欄とし、ファイル暗号化部により暗号化された第1乃至第Mの暗号ファイルを行の欄とし、索引暗号化部により暗号化されたM行N列のマトリックスの暗号化索引から成る表を、ユーザ端末がサーバへ送信してサーバへ保管する。検索フェーズでは、ユーザ端末が検索キーワード暗号化部により暗号化された第1及び第2の暗号検索キーワードと、カウンタ値を1だけ増加した新カウンタ値と、検索式暗号化部により暗号化された第1乃至第Mの暗号化検索式とをサーバへ送って、検索された暗号ファイルの集合を取得する。検索式暗号化部は、検索式を、第1及び第2の検索キーワードと暗号鍵と新カウンタ値とを使用してGarbled回路により第1乃至第Mの暗号化検索式に暗号化する。
【選択図】図12
従来技術、競合技術の概要



この技術分野において周知のように、Yahoo!データボックスなどのデータストレージ(データ保管)サービスにおいては、ユーザ端末は、写真などの多くのファイルを(Yahoo!データボックスなどの)サーバに格納し、保管することができる。また、ユーザ端末は、ファイル名についてキーワード検索を行って、サーバから所望のファイルの集合を取得することもできる。尚、ユーザ端末は、クライアントとも呼ばれる。





特許文献1は、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得する暗号検索システムを開示している。暗号検索システムの動作は、ユーザ端末が複数の暗号ファイルをサーバに格納する「格納フェーズ」と、ユーザ端末がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。





格納フェーズでは、ユーザ端末は、暗号化の秘密鍵を使い、複数のファイルを暗号化して、複数の暗号ファイルをサーバに保管する。また、ユーザ端末は、索引を生成し、生成した索引を暗号化して、サーバに保管する。





検索フェーズでは、ユーザ端末は、暗号化の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを送る。サーバは、検索キーワードを含むファイルの暗号文(暗号ファイル)の集合をユーザ端末へ返す。





しかしながら、特許文献1では、検索キーワードとして、1つのキーワードのみしか指定できない。





また、キーワード・フィールド毎に高々1つのキーワードを指定する暗号検索システムも知られている(例えば、非特許文献1~3参照)。しかしながら、非特許文献1~3では、特定の条件のANDを満たす文書の検索は可能であるが、それ以外のAND検索を行うことは不可能である。





そこで、キーワード・フィールドでキーワードを指定せずに、2つのキーワードのANDであるAND検索や、2つのキーワードのORであるOR検索を行うことが望まれている。





そのようなAND検索を2-passの検索フェーズで行う先行技術も知られている(例えば、非特許文献4参照)。しかしながら、非特許文献4では、AND検索しかできない。





一方、AND検索、OR検索を含む任意のブール関数の検索が行える先行技術も知られている(例えば、非特許文献5参照)。

産業上の利用分野



本発明は、暗号検索システム、暗号検索方法、および、暗号検索プログラムに関し、特に、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得する暗号検索システム、暗号検索方法、および、暗号検索プログラムに関する。

特許請求の範囲 【請求項1】
ユーザ端末(100)がサーバ(200)に第1乃至第M(Mは2以上の整数)の暗号ファイルと暗号化索引を保管し、前記ユーザ端末(100)がキーワード検索によって前記サーバ(200)から検索された所望のファイルの集合を取得する暗号検索システムであって、前記ユーザ端末(100)は、
第1の秘密鍵(k’)を使って第1乃至第N(Nは2以上の整数)のキーワード(w,・・・,w)をランダム化して、それぞれ、第1乃至第Nの暗号キーワード(kw,・・・,kw)を生成するキーワード暗号化部(110)と、
第2の秘密鍵(k)を使って第1乃至第Mのファイル(D,・・・,D)を暗号化して、それぞれ、前記第1至第Mの暗号ファイル(C,・・・,C)を生成するファイル暗号化部(120)と、
前記第1乃至第Nのキーワード(w,・・・,w)を特定するキーワード番号n(1≦n≦N)を列とし、前記第1乃至第Mのファイル(D,・・・,D)を特定するファイル番号m(1≦m≦M)を行として、第nのキーワード(w)を含む第mのファイル(D)の第m行第n列の原行列要素(emn)を1とし、それ以外を0としたM行N列のマトリックスから成る索引を、前記第1の秘密鍵(k’)を使って暗号化して、第m行第n列の暗号化行列要素(vmn)の各々が所定ビット数から成るM行N列のマトリックスの暗号化索引を生成する索引暗号化部(130)と、
前記第1乃至第Nの暗号キーワード(kw,・・・,kw)を列の欄とし、前記第1乃至第Mの暗号ファイル(C,・・・,C)を行の欄とした、前記M行N列のマトリックスの暗号化索引から成る表(T)を前記サーバ(200)へ送信して前記サーバ(200)へ保管させる表送信部(140)と、
初期値として0がセットされ、カウンタ値(counter)を出力するカウンタ(145)と、
前記第1の秘密鍵(k’)と前記第2の秘密鍵(k)とファイル数(M)と前記カウンタ値(counter)とを保持する保持部(150)と、
前記第1乃至第Nのキーワード(w,・・・,w)から選択された第1及び第2の検索キーワード(w,w)を前記第1の秘密鍵(k’)を使ってランダム化して、それぞれ、第1及び第2の暗号検索キーワード(kw,kw)を生成する検索キーワード暗号化部(160)と、
前記保持部に保持した前記カウンタ値(counter)を前記カウンタ(145)を使用して1だけ増加させて新カウンタ値を生成させ、各々が0又は1の値をとる第1のブール変数(x)と第2のブール変数(x)とのブール関数から成る検索式(f(x,x))を、前記第1及び第2の検索キーワード(w,w)と前記第1の秘密鍵(k’)と前記新カウンタ値(counter)とを使用してGarbled回路により暗号化し、前記第1乃至第Mのファイル(D,・・・,D)にそれぞれ対応した第1乃至第Mの暗号化検索式(Γ,・・・,Γ)を生成する検索式暗号化部(170)と、
前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とを前記サーバへ送って、前記サーバから前記第1及び第2の検索キーワード(w,w)が前記検索式(f(x,x))を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得部(180)と、
前記取得した検索された暗号ファイルの集合を前記第2の秘密鍵(k)を使用して復号して前記検索された所望のファイルの集合を得るファイル解読部(190)と、
を有する暗号検索システム。

【請求項2】
前記キーワード暗号化部(110)は、前記第nのキーワード(w)と前記第1の秘密鍵(k’)とから、所定の擬似ランダム関数(PRF)を使用して、第nの暗号キーワード(kw)を生成する擬似ランダム関数発生器(112)から成る、請求項1に記載の暗号検索システム。

【請求項3】
前記索引暗号化部(130)は、
前記ファイル番号(m)と前記第nのキーワード(w)との組に対して、前記第1の秘密鍵(k’)を使用して、第m行第n列の行列要素を0および1とした上付き文字を持ち、第m行第n列の暗号化行列要素用の最下位ビットが異なる第1及び第2の暗号化索引候補(vmn,vmn)を生成する索引用ラベル生成部(132)と、
該生成された第1及び第2の暗号化索引候補(vmn,vmn)から、前記上付き文字が前記第m行第n列の原行列要素(emn)に等しい方を前記第m行第n列の暗号化行列要素(vmn)として選択し出力する選択部(134)と、
を有する、請求項2に記載の暗号検索システム。

【請求項4】
前記索引用ラベル生成部(132)は、
前記ファイル番号(m)と前記第nのキーワード(w)と0との組に対して、前記第1の秘密鍵(k’)を使用して、前記所定の擬似ランダム関数(PRF)により前記第1の暗号化索引候補(vmn)を生成する第1の候補生成部(1322)と、
前記ファイル番号(m)と前記第nのキーワード(w)と1との組に対して、前記第1の秘密鍵(k’)を使用して、前記所定の擬似ランダム関数(PRF)により第2の暗号化索引候補(vmn)を生成する第2の候補生成部(1324)と、
前記生成した第1の暗号化索引候補(vmn)の最下位ビットと前記生成した第2の暗号化索引候補(vmn)の最下位ビットとが等しい場合、前記生成した第2の暗号化索引候補(vmn)の最下位ビットを強制的に反転して、前記第2の暗号化索引候補(vmn)を得る反転部(1326)と、
から成る、請求項3に記載の暗号検索システム。

【請求項5】
前記検索キーワード暗号化部(160)は、
前記第1の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第1の暗号検索キーワード(kw)を生成する第1の検索キーワード暗号化器(162)と、
前記第2の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第2の暗号検索キーワード(kw)を生成する第2の検索キーワード暗号化器(164)と、
から成る、請求項2乃至4のいずれか1項に記載の暗号検索システム。

【請求項6】
前記検索式暗号化部(170)は、
前記ファイル番号(m)と前記第1の検索キーワード(w)との組に対して、前記第1の秘密鍵(k’)を使用して、0および1の上付き文字を持ち、前記第mのファイル(D)用の最下位ビットが異なる一組の第1のラベル(v,v)を生成する第1の検索式用ラベル生成部(172)と、
前記ファイル番号(m)と前記第2の検索キーワード(w)との組に対して、前記第1の秘密鍵(k’)を使用して、0および1の上付き文字を持ち、前記第mのファイル(D)用の最下位ビットが異なる一組の第2のラベル(v,v)を生成する第2の検索式用ラベル生成部(174)と、
前記検索式(f(x,x))と、前記一組の第1のラベル(v,v)と、前記一組の第2のラベル(v,v)と、前記新カウンタ値(counter)とから、前記第mの暗号化検索式(Γ)を生成するGarbled回路生成部(176)と、
から成る、請求項1乃至5のいずれか1項に記載の暗号検索システム。

【請求項7】
前記サーバ(200)は、
前記ユーザ端末(100)から送られてくる前記表(T)を保持する記憶領域(210)と、
前記ユーザ端末(200)から受信した、前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とに基づいて、前記表(T)を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索部(220)と、
を有する、請求項6に記載の暗号検索システム。

【請求項8】
前記暗号検索部(220)は、
前記第mの暗号化検索式(Γ)に対して、前記表(T)から前記第1及び第2の暗号検索キーワード(kw,kw)の列を探して、当該列の一対の第m行の第1及び第2の探索した暗号化行列要素(vma,vmb)を生成する暗号化要素探索部(222)と、
前記新カウンタ値(counter)を使用して、前記第mの暗号化検索式(Γ)と前記第1及び第2の探索した暗号化行列要素(vma,vmb)とに基づいて、0又は1の値をとる第mの評価値(Z)を生成するGarbled回路評価部(224)と、
前記第mの評価値(Z)が1であるときに、前記第mの暗号ファイル(C)を前記検索された暗号ファイルの集合の1つとして選択して出力する暗号ファイル選択部(226)と、
から構成される請求項7に記載の暗号検索システム。

【請求項9】
ユーザ端末(100)がサーバ(200)に第1乃至第M(Mは2以上の整数)の暗号ファイルと暗号化索引を保管し、前記ユーザ端末(100)がキーワード検索によって前記サーバ(200)から検索された所望のファイルの集合を取得する暗号検索方法であって、
前記ユーザ端末が、第1の秘密鍵(k’)を使って第1乃至第N(Nは2以上の整数)のキーワード(w,・・・,w)をランダム化して、それぞれ、第1乃至第Nの暗号キーワード(kw,・・・,kw)を生成するキーワード暗号化ステップ(110)と、
前記ユーザ端末が、第2の秘密鍵(k)を使って第1乃至第Mのファイル(D,・・・,D)を暗号化して、それぞれ、前記第1至第Mの暗号ファイル(C,・・・,C)を生成するファイル暗号化ステップ(120)と、
前記ユーザ端末が、前記第1乃至第Nのキーワード(w,・・・,w)を特定するキーワード番号n(1≦n≦N)を列とし、前記第1乃至第Mのファイル(D,・・・,D)を特定するファイル番号m(1≦m≦M)を行として、第nのキーワード(w)を含む第mのファイル(D)の第m行第n列の原行列要素(emn)を1とし、それ以外を0としたM行N列のマトリックスから成る索引を、前記第1の秘密鍵(k’)を使って暗号化して、第m行第n列の暗号化行列要素(vmn)の各々が所定ビット数から成るM行N列のマトリックスの暗号化索引を生成する索引暗号化ステップ(130)と、
前記ユーザ端末が、前記第1乃至第Nの暗号キーワード(kw,・・・,kw)を列の欄とし、前記第1乃至第Mの暗号ファイル(C,・・・,C)を行の欄とした、前記M行N列のマトリックスの暗号化索引から成る表(T)を前記サーバ(200)へ送信して前記サーバ(200)へ保管させる表送信ステップ(140)と、
前記ユーザ端末が、カウンタ(145)に初期値として0がセットされ、カウンタ値(counter)を出力するステップと、
前記ユーザ端末が、前記第1の秘密鍵(k’)と前記第2の秘密鍵(k)とファイル数(M)と前記カウンタ値(counter)とを保持部(150)に保持するステップと、
前記ユーザ端末が、前記第1乃至第Nのキーワード(w,・・・,w)から選択された第1及び第2の検索キーワード(w,w)を前記第1の秘密鍵(k’)を使ってランダム化して、それぞれ、第1及び第2の暗号検索キーワード(kw,kw)を生成する検索キーワード暗号化ステップ(160)と、
前記ユーザ端末が、前記保持部に保持した前記カウンタ値(counter)を前記カウンタ(145)を使用して1だけ増加させて新カウンタ値を生成させ、各々が0又は1の値をとる第1のブール変数(x)と第2のブール変数(x)とのブール関数から成る検索式(f(x,x))を、前記第1及び第2の検索キーワード(w,w)と前記第1の秘密鍵(k’)と前記新カウンタ値(counter)とを使用してGarbled回路により暗号化し、前記第1乃至第Mのファイル(D,・・・,D)にそれぞれ対応した第1乃至第Mの暗号化検索式(Γ,・・・,Γ)を生成する検索式暗号化ステップ(170)と、
前記ユーザ端末が、前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とを前記サーバへ送って、前記サーバから前記第1及び第2の検索キーワード(w,w)が前記検索式(f(x,x))を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得ステップ(180)と、
前記ユーザ端末が、前記取得した検索された暗号ファイルの集合を前記第2の秘密鍵(k)を使用して復号して前記検索された所望のファイルの集合を得るファイル解読ステップ(190)と、
を含む暗号検索方法。

【請求項10】
サーバ(200)に第1乃至第M(Mは2以上の整数)の暗号ファイルと暗号化索引を保管し、キーワード検索によって前記サーバ(200)から検索された所望のファイルの集合を取得する処理を、コンピュータであるユーザ端末(100)に実行させる暗号検索プログラムであって、前記コンピュータである前記ユーザ端末(100)に、
第1の秘密鍵(k’)を使って第1乃至第N(Nは2以上の整数)のキーワード(w,・・・,w)をランダム化して、それぞれ、第1乃至第Nの暗号キーワード(kw,・・・,kw)を生成するキーワード暗号化手順(110)と、
第2の秘密鍵(k)を使って第1乃至第Mのファイル(D,・・・,D)を暗号化して、それぞれ、前記第1至第Mの暗号ファイル(C,・・・,C)を生成するファイル暗号化手順(120)と、
前記第1乃至第Nのキーワード(w,・・・,w)を特定するキーワード番号n(1≦n≦N)を列とし、前記第1乃至第Mのファイル(D,・・・,D)を特定するファイル番号m(1≦m≦M)を行として、第nのキーワード(w)を含む第mのファイル(D)の第m行第n列の原行列要素(emn)を1とし、それ以外を0としたM行N列のマトリックスから成る索引を、前記第1の秘密鍵(k’)を使って暗号化して、第m行第n列の暗号化行列要素(vmn)の各々が所定ビット数から成るM行N列のマトリックスの暗号化索引を生成する索引暗号化手順(130)と、
前記第1乃至第Nの暗号キーワード(kw,・・・,kw)を列の欄とし、前記第1乃至第Mの暗号ファイル(C,・・・,C)を行の欄とした、前記M行N列のマトリックスの暗号化索引から成る表(T)を前記サーバ(200)へ送信して前記サーバ(200)へ保管させる表送信手順(140)と、
カウンタ(145)に初期値として0がセットされ、カウンタ値(counter)を出力する手順と、
前記第1の秘密鍵(k’)と前記第2の秘密鍵(k)とファイル数(M)と前記カウンタ値(counter)とを保持部(150)に保持する手順と、
前記第1乃至第Nのキーワード(w,・・・,w)から選択された第1及び第2の検索キーワード(w,w)を前記第1の秘密鍵(k’)を使ってランダム化して、それぞれ、第1及び第2の暗号検索キーワード(kw,kw)を生成する検索キーワード暗号化手順(160)と、
前記保持部(150)に保持した前記カウンタ値(counter)を前記カウンタ(145)を使用して1だけ増加させて新カウンタ値を生成させ、各々が0又は1の値をとる第1のブール変数(x)と第2のブール変数(x)とのブール関数から成る検索式(f(x,x))を、前記第1及び第2の検索キーワード(w,w)と前記第1の秘密鍵(k’)と前記新カウンタ値(counter)とを使用してGarbled回路により暗号化し、前記第1乃至第Mのファイル(D,・・・,D)にそれぞれ対応した第1乃至第Mの暗号化検索式(Γ,・・・,Γ)を生成する検索式暗号化手順(170)と、
前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とを前記サーバ(200)へ送って、前記サーバ(200)から前記第1及び第2の検索キーワード(w,w)が前記検索式(f(x,x))を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル手順(180)と、
前記取得した検索された暗号ファイルの集合を前記第2の秘密鍵(k)を使用して復号して前記検索された所望のファイルの集合を得るファイル解読手順(190)と、
を実行させるための暗号検索プログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2013255286thum.jpg
出願権利状態 公開
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください


PAGE TOP

close
close
close
close
close
close
close