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

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

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2015-114432 (P2015-114432A)
公開日 平成27年6月22日(2015.6.22)
発明の名称または考案の名称 暗号検索システム、暗号検索方法および暗号検索プログラム
国際特許分類 G09C   1/00        (2006.01)
G06F  17/30        (2006.01)
FI G09C 1/00 660D
G09C 1/00 610Z
G06F 17/30 120A
G06F 17/30 414Z
請求項の数または発明の数 10
出願形態 OL
全頁数 38
出願番号 特願2013-255286 (P2013-255286)
出願日 平成25年12月10日(2013.12.10)
発明者または考案者 【氏名】黒澤 馨
出願人 【識別番号】504203572
【氏名又は名称】国立大学法人茨城大学
個別代理人の代理人 【識別番号】100077838、【弁理士】、【氏名又は名称】池田 憲保
【識別番号】100082924、【弁理士】、【氏名又は名称】福田 修一
【識別番号】100129023、【弁理士】、【氏名又は名称】佐々木 敬
審査請求 未請求
テーマコード 5J104
Fターム 5J104JA03
5J104NA20
5J104PA14
要約 【課題】検索式を秘匿し、検索フェーズを2-passとすること。
【解決手段】格納フェーズでは、キーワード暗号化部により暗号化された第1乃至第Nの暗号キーワードを列の欄とし、ファイル暗号化部により暗号化された第1乃至第Mの暗号ファイルを行の欄とし、索引暗号化部により暗号化されたM行N列のマトリックスの暗号化索引から成る表を、ユーザ端末がサーバへ送信してサーバへ保管する。検索フェーズでは、ユーザ端末が検索キーワード暗号化部により暗号化された第1及び第2の暗号検索キーワードと、カウンタ値を1だけ増加した新カウンタ値と、検索式暗号化部により暗号化された第1乃至第Mの暗号化検索式とをサーバへ送って、検索された暗号ファイルの集合を取得する。検索式暗号化部は、検索式を、第1及び第2の検索キーワードと暗号鍵と新カウンタ値とを使用してGarbled回路により第1乃至第Mの暗号化検索式に暗号化する。
【選択図】図12
特許請求の範囲 【請求項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)と、
を実行させるための暗号検索プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、暗号検索システム、暗号検索方法、および、暗号検索プログラムに関し、特に、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得する暗号検索システム、暗号検索方法、および、暗号検索プログラムに関する。
【背景技術】
【0002】
この技術分野において周知のように、Yahoo!データボックスなどのデータストレージ(データ保管)サービスにおいては、ユーザ端末は、写真などの多くのファイルを(Yahoo!データボックスなどの)サーバに格納し、保管することができる。また、ユーザ端末は、ファイル名についてキーワード検索を行って、サーバから所望のファイルの集合を取得することもできる。尚、ユーザ端末は、クライアントとも呼ばれる。
【0003】
特許文献1は、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得する暗号検索システムを開示している。暗号検索システムの動作は、ユーザ端末が複数の暗号ファイルをサーバに格納する「格納フェーズ」と、ユーザ端末がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。
【0004】
格納フェーズでは、ユーザ端末は、暗号化の秘密鍵を使い、複数のファイルを暗号化して、複数の暗号ファイルをサーバに保管する。また、ユーザ端末は、索引を生成し、生成した索引を暗号化して、サーバに保管する。
【0005】
検索フェーズでは、ユーザ端末は、暗号化の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを送る。サーバは、検索キーワードを含むファイルの暗号文(暗号ファイル)の集合をユーザ端末へ返す。
【0006】
しかしながら、特許文献1では、検索キーワードとして、1つのキーワードのみしか指定できない。
【0007】
また、キーワード・フィールド毎に高々1つのキーワードを指定する暗号検索システムも知られている(例えば、非特許文献1~3参照)。しかしながら、非特許文献1~3では、特定の条件のANDを満たす文書の検索は可能であるが、それ以外のAND検索を行うことは不可能である。
【0008】
そこで、キーワード・フィールドでキーワードを指定せずに、2つのキーワードのANDであるAND検索や、2つのキーワードのORであるOR検索を行うことが望まれている。
【0009】
そのようなAND検索を2-passの検索フェーズで行う先行技術も知られている(例えば、非特許文献4参照)。しかしながら、非特許文献4では、AND検索しかできない。
【0010】
一方、AND検索、OR検索を含む任意のブール関数の検索が行える先行技術も知られている(例えば、非特許文献5参照)。
【先行技術文献】
【0011】

【特許文献1】特開2013-161154号公報(図15)
【0012】

【非特許文献1】Philippe Golle, Jessica Staddon, Brent R. Waters:“Secure Conjunctive Keyword Search over Encrypted Data” ACNS 2004, pp. 31-45 (2004)
【非特許文献2】Lucas Ballard, Seny Kamara, Fabian Monrose:“Achieving Efficient Conjunctive Keyword Searches over Encrypted Data” ICICS 2005, pp. 414-426 (2005)
【非特許文献3】J. W. Byun, D. H. Lee, and J. Lim:“Efficient conjunctive keyword search on encrypted data storage system” EuroPKI, pp. 184-196 (2006)
【非特許文献4】Peishun Wang, Huaxiong Wang, Josef Pieprzyk:“Keyword Field-Free Conjunctive Keyword Searches over Encrypted Data and Extension for Dynamic Groups” CANS 2008: pp. 178-195
【非特許文献5】David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel Rosu, Michael Steiner:“Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries” CRYPTO 2013
【発明の概要】
【発明が解決しようとする課題】
【0013】
しかしながら、非特許文献5に開示された先行技術では、その検索式が何なのかがサーバにわかってしまう。また、非特許文献5に開示された先行技術では、検索フェーズが2-passではなく、4-passであるという問題もある。
【0014】
したがって本発明の目的は、検索式を秘匿可能な、暗号検索システム、暗号検索方法、および暗号検索プログラムを提供することにある。
【0015】
本発明の他の目的は、検索フェーズが2-passである、暗号検索システム、暗号検索方法、および暗号検索プログラムを提供することにある。
【課題を解決するための手段】
【0016】
本発明の第1の態様に係る暗号検索システムは、ユーザ端末がサーバに第1乃至第M(Mは2以上の整数)の暗号ファイルと暗号化索引を保管し、ユーザ端末がキーワード検索によってサーバから検索された所望のファイルの集合を取得する暗号検索システムであって、ユーザ端末は、第1の秘密鍵を使って第1乃至第N(Nは2以上の整数)のキーワードをランダム化して、それぞれ、第1乃至第Nの暗号キーワードを生成するキーワード暗号化部と;第2の秘密鍵を使って第1乃至第Mのファイルを暗号化して、それぞれ、第1至第Mの暗号ファイルを生成するファイル暗号化部と;第1乃至第Nのキーワードを特定するキーワード番号n(1≦n≦N)を列とし、第1乃至第Mのファイルを特定するファイル番号m(1≦m≦M)を行として、第nのキーワードを含む第mのファイルの第m行第n列の原行列要素を1とし、それ以外を0としたM行N列のマトリックスから成る索引を、第1の秘密鍵を使って暗号化して、第m行第n列の暗号化行列要素の各々が所定ビット数から成るM行N列のマトリックスの暗号化索引を生成する索引暗号化部と;第1乃至第Nの暗号キーワードを列の欄とし、第1乃至第Mの暗号ファイルを行の欄とした、M行N列のマトリックスの暗号化索引から成る表をサーバへ送信してサーバへ保管させる表送信部と;初期値として0がセットされ、カウンタ値を出力するカウンタと;第1の秘密鍵と第2の秘密鍵とファイル数とカウンタ値とを保持する保持部と;第1乃至第Nのキーワードから選択された第1及び第2の検索キーワードを第1の秘密鍵を使ってランダム化して、それぞれ、第1及び第2の暗号検索キーワードを生成する検索キーワード暗号化部と;保持部に保持したカウンタ値をカウンタを使用して1だけ増加させて新カウンタ値を生成させ、各々が0又は1の値をとる第1のブール変数と第2のブール変数とのブール関数から成る検索式を、第1及び第2の検索キーワードと第1の秘密鍵と新カウンタ値とを使用してGarbled回路により暗号化し、第1乃至第Mのファイルにそれぞれ対応した第1乃至第Mの暗号化検索式を生成する検索式暗号化部と;第1及び第2の暗号検索キーワードと新カウンタ値と第1乃至第Mの暗号化検索式とをサーバへ送って、サーバから第1および第2の検索キーワードが検索式を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得部と;取得した検索された暗号ファイルの集合を第2の秘密鍵を使用して復号して検索された所望のファイルの集合を得るファイル解読部と:を備える。
【発明の効果】
【0017】
本発明では、ブール関数から成る検索式の真理値表を、第1及び第2の検索キーワードと第1の秘密鍵と新カウンタ値とを使用してGarbled回路により暗号化し、暗号化検索式を生成しているので、検索式を秘匿でき、検索フェーズを2-passとすることができる。
【図面の簡単な説明】
【0018】
【図1】本発明が利用する、Yao’s Garbeld Circuitの概略を説明するためのブロック図である。
【図2】ブール関数fの暗号文(暗号化検索式)ΓであるGarbled出力値pを示す図である。
【図3】lsb(v)=1,lsb(v)=0の場合のGarbled出力値p(10)を示す図である。
【図4】さらにlsb(v)=1,lsb(v)=1の場合のGarbled出力値p(11)を示す図である。
【図5】さらにlsb(v)=0,lsb(v)=0の場合のGarbled出力値p(00)を示す図である。
【図6】さらにlsb(v)=0,lsb(v)=1の場合のGarbled出力値p(01)を示す図である。
【図7】検索式f(x,x)がORである場合の暗号化検索式Γ’を示す図である。
【図8】本発明の実施形態に係る暗号検索システムの格納フェーズの動作を説明するための概略ブロック図である。
【図9】図8に示した暗号検索システムに使用される索引の一具体例を示す図である。
【図10】図9で表される索引を、第1の暗号鍵k’を使用して暗号化して得られる暗号化索引を含む表Tを示す図である。
【図11】本発明の実施形態に係る暗号検索システムのサーバでの検索フェーズの動作の一例を示す図である。
【図12】本発明の第1の実施例に係る暗号検索システムの構成を示すブロック図である。
【図13】図12に示した暗号検索システムのクライアントにおける格納フェーズのブロック図である。
【図14】図13に示したキーワード暗号化部の構成を示すブロック図である。
【図15】図13に示したファイル暗号化部の構成を示すブロック図である。
【図16】図13に示した索引暗号化部の構成を示すブロック図である。
【図17】図16に示した索引用ラベル生成部の構成を示すブロック図である。
【図18】図12に示した暗号検索システムのクライアントにおける検索フェーズのブロック図である。
【図19】図18に示した検索キーワード暗号化部の構成を示すブロック図である。
【図20】図18に示した検索式暗号化部の構成を示すブロック図である。
【図21】図20に示したGarbled回路生成部の処理を説明するためのブロック図である。
【図22】図12に示した暗号検索システムのサーバにおける検索フェーズのブロック図である。
【図23】図22に示したGarbled回路評価部の構成を示すブロック図である。
【図24】図12に示した暗号検索システムのクライアントにおける検索フェーズで使用されるファイル解読部の構成を示すブロック図である。
【発明を実施するための形態】
【0019】
[概要]
以下、本発明の実施形態の概要について説明する。

【0020】
本発明の実施形態による暗号検索システムは、検索式を秘匿でき、検索フェーズを2-passとすることができる暗号検索システムである。

【0021】
本発明の実施形態に係る暗号検索システムは、ユーザ端末がファイルおよびキーワードを暗号化してサーバに保管する暗号検索システムである。ユーザ端末はクライアントとも呼ばれる。

【0022】
本実施形態に係る暗号検索システムでは、後述するように、ブール関数から成る検索式の真理値表を、第1及び第2の検索キーワードと第1の秘密鍵と新カウンタ値とを使用してGarbled回路により暗号化し、暗号化検索式を生成する。これにより、検索式を秘匿できるだけでなく、検索フェーズを2-passとすることができる。

【0023】
尚、暗号検索システムの動作は、ユーザ端末(クライアント)が暗号ファイルおよび暗号化索引をサーバに格納する「格納フェーズ」と、ユーザ端末(クライアント)がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。

【0024】
本発明では、アンドリュー・チーチー・ヤオが考案し1986年にIEEEの学会で発表したYao’s Garbeld Circuitを利用する。このGarbeld Circuitは、暗号プロトコルを設計する際の強力なフレームワークであり、暗号理論において今の中心的役割を担っている。しかし、暗号検索システムへの応用は自明ではなく、従来知られていない。

【0025】
次に、Yao’s Garbeld Circuitの概略について説明する。

【0026】
E(X)を入力X=(x,…,x)の暗号文とし、E(f)をブール関数fの暗号文とする。この場合、図1に示されるように、(f、X)を秘密にしたまま、f(X)を計算することができる。

【0027】
しかしながら、E(f)又はE(X)を再利用すると、(f、X)に関する何らかの情報が洩れてしまう。

【0028】
そこで、Goldwasser et al. は、再利用可能なGarbled Circuitを提案している(Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldvoich, “Reusable Garbled Circuits and Succintct Functional Encryption” STOC 2013, pp555-564参照)。

【0029】
Goldwasser et al.が提案した再利用可能なGarbled Circuitにおいては、ブール関数の暗号文E(f)を固定して、Garbled Circuitを再利用している。すなわち、入力X,X,・・・に対して、f(X),f(X),・・・を計算している。

【0030】
これに対して本発明では、入力Xの暗号文E(X)を固定して、Garbled Circuitを再利用する。すなわち、ブール関数f,f,・・・に対し、f(X),f(X),・・・を計算する。本発明では、このようなGarbled Circuitを考え、暗号検索システムに利用した。

【0031】
次に、本発明の実施形態の理解を容易にするために、検索式も秘匿可能な暗号検索システムの概略について説明する。

【0032】
本発明に係るGarbling schemeには、次に述べる3つのアルゴリズムがある。

【0033】
GenLabは、第1および第2のブール変数x,xのラベルベクトルVを計算するアルゴリズムである。

【0034】
GenGC(counter, f, V)は、ブール関数fの暗号文Γを計算するアルゴリズムである。尚、counterは初期値が0のカウンタのカウンタ値であって、1ずつ増加する。

【0035】
EvalGCは、ブール関数の検索式f(x、x)を計算するアルゴリズムである。

【0036】
最初に、GenLabのアルゴリズムについて説明する。

【0037】
i=1,2に対して、最下位ビットlsb(v)、lsb(v)が異なる(lsb(v)≠lsb(v)となる)、128ビットの乱数(v,v)を選ぶ。

【0038】
そして、ラベルベクトルV=((v,v),(v,v))を出力する。ここで、vは第1のブール変数x=0のときのラベルであり、vは第1のブール変数x=1のときのラベルであり、vは第2のブール変数x=0のときのラベルであり、vはブール変数x=1のときのラベルである。例えば、ラベルベクトルV=((v,v),(v,v))は次のように表される。
=(...1), v=(...0)
=(...0), v=(...1)

【0039】
次に、GenGC(counter, f, V)のアルゴリズムについて説明する。

【0040】
図2は、ブール関数fの暗号文(暗号化検索式)ΓであるGarbled出力値pを示す図である。ここで、Γ=[p(00),p(01),p(10),p(11)]である。

【0041】
Hを出力が1ビットのハッシュ関数とする。

【0042】
第1及び第2のブール変数(x,x)の4つの組み合わせ(0,0),(1,0)、(1,0),(1,1)について、ラベルvx1、vx2の最下位ビットlsbを、それぞれ、下記の数式で表されるように、第1及び第2のGarbled変数a,aとする。
=lsb(vx1), a=lsb(vx2

【0043】
そして、次の式に従って、Garbled出力値p(a)を計算する。
p(a)=H(counter,vx1,vx2)+f(x,x
ここで、演算子“+”は排他的論理和である。

【0044】
図3は、lsb(v)=1,lsb(v)=0の場合のGarbled出力値p(10)を示す図である。

【0045】
すなわち、(x,x)=(0,0)について、a=lsb(v)=1,a=lsb(v)=0であったとする。この場合、Garbled出力値p(10)は、次式で表される。
p(10)=H(counter,v,v)+f(0,0)

【0046】
図4は、さらにlsb(v)=1,lsb(v)=1の場合のGarbled出力値p(11)を示す図である。

【0047】
すなわち、(x,x)=(0,1)について、a=lsb(v)=1,a=lsb(v)=1であったとする。この場合、Garbled出力値p(11)は、次式で表される。
p(11)=H(counter,v,v)+f(0,1)

【0048】
図5は、さらにlsb(v)=0,lsb(v)=0の場合のGarbled出力値p(00)を示す図である。

【0049】
すなわち、(x,x)=(1,0)について、a=lsb(v)=0,a=lsb(v)=0であったとする。この場合、Garbled出力値p(00)は、次式で表される。
p(00)=H(counter,v,v)+f(1,0)

【0050】
図6は、さらにlsb(v)=0,lsb(v)=1の場合のGarbled出力値p(01)を示す図である。

【0051】
すなわち、(x,x)=(1,1)について、a=lsb(v)=0,a=lsb(v)=1であったとする。この場合、Garbled出力値p(01)は、次式で表される。
p(01)=H(counter,v,v)+f(1,1)

【0052】
次に、EvalGCのアルゴリズムについて説明する。

【0053】
図6に示されたブール関数fの暗号文(暗号化検索式)Γは、ユーザ端末(クライアント)からサーバへ送られる。

【0054】
ラベルv、vの最下位ビットlsbを、それぞれ、下記の数式で表される、第1及び第2のGarbled変数α、βとする。
α=lsb(v), β=lsb(v

【0055】
そして、次式に従って、評価値Zを計算する。
Z=p(αβ)-H(counter,v,v
ここで、演算子“-”は排他的論理和である。したがって、演算子“-”の代わりに演算子“+”を使用してもよい。

【0056】
ここで、ラベル(v,v)が次式であるとする。
(v,v)=((...0),(...1))

【0057】
このとき、第1および第2のGarbled変数α、βは、それぞれ、次式で表される。
α=lsb(v)=0, β=lsb(v)=1

【0058】
したがって、評価値Zは、図6に示される暗号化検索式Γから、次式で表される。
Z=p(01)-H(counter,v,v)=f(1,1)
検索式f(x,x)がANDである場合、f(1,1)は1に等しいので、
Z=1
となる。

【0059】
次に、検索式f(x,x)がORであって、検索式f(x,x)=xORxで表される、OR検索を行うとする。

【0060】
この場合、次式で表されるように、まずカウンタ値counterを1だけインクリメントして、新カウンタ値counterを使用する。
counter=counter+1

【0061】
そして、図7に示されるような、暗号化検索式Γ’をクライアントからサーバへ送信すればよい。

【0062】
図7において、ラベルベクトルVを規定する4つのラベルv,v,v,vは、固定であって変化しないので、再利用することが可能であることがわかる。換言すれば、ラベルベクトルVについては、クライアントにおいて第1の秘密鍵k’を使用して一度暗号化して、サーバへ送ればよい。

【0063】
これにより、検索式を秘匿にしたままで、検索フェーズを2-passとすることができる。

【0064】
[実施形態]
次に、本発明の実施形態に係る暗号検索システムについて説明する。

【0065】
前述したように、暗号検索システムの動作は、ユーザ端末(クライアント)が暗号ファイルをサーバに格納する「格納フェーズ」と、ユーザ端末(クライアント)がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。

【0066】
最初に、「格納フェーズ」の動作について説明する。

【0067】
図8は、本発明の実施形態に係る暗号検索システムの格納フェーズの動作を説明するための概略ブロック図である。

【0068】
図8に示されるように、クライアント100は、サーバ200へ、第1乃至第M(Mは2以上の整数)の暗号ファイルC~Cと暗号化索引E(索引)とを送信する。

【0069】
ファイルの集合をD={D,・・・,D}とする。すなわち、ファイルの集合Dが第1乃至第MのファイルD~Dから成るとする。

【0070】
キーワードの集合をW={w,・・・,w}とする。すなわち、キーワードの集合Wが第1乃至第Nのキーワードw~wから成るとする。

【0071】
第1乃至第Nのキーワードw~wを特定するキーワード番号n(1≦n≦N)を列とし、第1乃至第MのファイルD~Dを特定するファイル番号m(1≦m≦M)を行とする第m行第n列の原行列要素emnを含む、M行N列のマトリックスから成る索引を生成する。

【0072】
ここで、もし第mのファイルDが第nのキーワードwを含むなら、emn=1とし、そうでなければ、emn=0とする。

【0073】
例えば、ファイルの集合Dが第1および第2のファイルDおよびDの2つから成り、キーワードの集合Wが第1乃至第3のキーワードw,w、およびwの3つから成っているとする。また、第1のキーワードwが「茨城」で、第2のキーワードwが「日立」で、第3のキーワードwが「大学」であるとする。そして、第1のファイルDが「茨城」の第1のキーワードwと「日立」の第2のキーワードwとを含み、第2のファイルD2が「茨城」の第1のキーワードwと「大学」の第3のキーワードwとを含むとする。

【0074】
この場合の索引は、図9のように表される。

【0075】
本実施形態では、索引として、キーワード番号nを列とし、ファイル番号mを行とした、M行N列のマトリックスから成る索引を使用しているが、列と行とを入れ替えても構わない。すなわち、索引は、キーワード番号nを行とし、ファイル番号mを列とした、N行M列のマトリックスから成る索引から成っていてもよい。

【0076】
Eを共通鍵暗号の暗号化アルゴリズムとし、kをその鍵(本例では、「第2の秘密鍵」と呼ぶ)とする。

【0077】
また、PRFを出力が128ビットの擬似ランダム関数とし、k’をその鍵(本例では、「第1の秘密鍵」と呼ぶ)とする。

【0078】
クライアント100は、ファイル番号m=1,・・・,Mに対して、第mのファイルDを第2の秘密鍵kを使って所定の暗号化アルゴリズムEncにより暗号化して、次式で表わされるような、第mの暗号ファイルCを計算する。
=Enck(D

【0079】
また、クライアント100は、キーワード番号n=1,・・・,Nに対して、第nのキーワードwを第1の秘密鍵k’を使用してランダム化して、次式で表されるような、第nの暗号キーワードkwを計算する。
kw=PRFk’(w

【0080】
そして、クライアント100は、第1乃至第Mの暗号ファイル(C,・・・,C)と、第1乃至第Nの暗号キーワード(kw,・・・,kw)とを、サーバ200へ送信してサーバ200に格納する。

【0081】
次に、クライアント100は、上記M行N列のマトリックスから成る索引を、第1の秘密鍵k’を使って暗号化して、第m行第n列の暗号化行列要素vmnの各々が所定ビット数(本例では、128ビット)から成るM行N列のマトリックスの暗号化索引E(索引)を生成する。

【0082】
詳述すると、ファイル番号m=1,・・・,Mおよびキーワード番号n=1,・・・,Nに対して、まず、クライアント100は、第1の秘密鍵k’を使用して、上記擬似ランダム関数RRFにより、それぞれ、第m行第n列の行列要素を0および1とした上付き文字を持つ、第1の暗号化索引候補vmnおよび第2の暗号化索引候補vmnを、次式に従って計算する。
mn=PRFk’(m,w,0)
mn=PRFk’(m,w,1)

【0083】
もし、第1の暗号化索引候補vmnの最下位ビットlsb(vmn)と、第2の暗号化索引候補vmnの最下位ビットlsb(vmn)とが等しければ、すなわち、
lsb(vmn)=lsb(vmn
であれば、クライアント100は、第2の暗号化索引候補vmnの最下位ビットlsbを反転したものを、第2の暗号化索引候補vmnとする。

【0084】
そして、クライアント100は、第m行第n列の暗号化行列要素vmnを、次式から求める。
mn=vmnemn

【0085】
すなわち、クライアント100は、第1及び第2の暗号化索引候補vmnおよびvmnから、上付き文字が第m行第n列の原行列要素emnに等しい方を、第m行第n列の暗号化行列要素vmnとして選択して出力する。

【0086】
ファイル番号m=1,・・・,Mに対して、クライアント100は、ベクトルYを次式とおく。
=(vm1,・・・,vmN

【0087】
そして、クライアント100は、M行N列のマトリックスの暗号化索引(Y,・・・,Y)をサーバ200に送信して、サーバ200に格納する。

【0088】
以上を纏めると、クライアント100は、第1乃至第Nの暗号キーワードkw~kwを列の欄とし、第1乃至第Mの暗号ファイルC~Cを行の欄とした、上記M行N列のマトリックスの暗号化索引から成る表Tを、サーバ200へ送信してサーバ200へ保管させる。

【0089】
クライアント100は、カウンタ値counterを、初期値を0にしてカウンタ(後述する)にセットする。

【0090】
図10は、図9で表される索引を、第1の暗号鍵k’を使用して暗号化して得られる暗号化索引を含む表Tを示す図である。図10において、(A)は図9に示した索引を示し、(B)はその索引を第1の暗号鍵k’を使用して暗号化して得られる暗号化索引を含む表Tを示す。

【0091】
以上で、本実施形態に係る暗号検索システムの格納フェーズの動作の説明を終える。

【0092】
次に、本実施形態に係る暗号検索システムの検索フェーズの動作について説明する。

【0093】
クライアント100は、第1乃至第Nのキーワードw~wの中から、第1及び第2の検索キーワード(w,w)を選択すると共に、各々が0又は1の値をとる第1のブール変数xと第2のブール変数xとのブール関数から成る検索式f(x,x)を選択する。検索式f(x,x)は、たとえば、AND又はORから成る。

【0094】
次に、クライアント100は、次式に従って、カウンタ値counterを1だけインクリメントとして、新カウンタ値conterを求める。
counter=counter+1

【0095】
引き続いて、クライアント100は、第1及び第2の検索キーワード(w,w)を第1の秘密鍵k’を使って上記擬似ランダム関数PRFによりランダム化して、それぞれ、次式で表される、第1及び第2の暗号検索キーワード(kw,kw)を計算する。
kw=PRFk’(w
kw=PRFk’(w

【0096】
ファイル番号m=1,・・・,Mに対して、クライアント100は、上述した格納フェーズと同様にして、次式で表される第mのラベルベクトルVを計算する。
V=((vma,vma),(vmb,vmb))

【0097】
そして、クライアント100は、検索式f(x,x)を、新カウンタ値counterと第mのラベルベクトルVとを使用してGarbeld回路より次式に従って暗号化して、第mのファイルDmに対応する第mの暗号化検索式Γを計算する。
Γ=GenGC(counter,f,V)

【0098】
換言すると、検索式f(x,x)の第1及び第2のブール変数(x,x)の4つの組み合わせ(0,0),(0,1),(1,0),(1,1)について、ラベルvx1及びvx2の最下位ビットをそれぞれ第1及び第2のGarbled変数(a,a)としたとき、クライアント100は、次式で表されるような、新カウンタ値counterとラベルvx1及びvx2との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vx1,vx2)の出力値と検索式f(x,x)との排他的論理和を計算する。
p(a)=H(counter,vx1,vx2)+f(x,x)mod2

【0099】
ここで、第mの暗号化検索式Γは、次式で表される。
Γ=[p(00),p(01),p(10),p(11)]

【0100】
そして、クライアント100は、新カウンタ値counterと第1及び第2の暗号検索キーワード(kw,kw)と第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とを、サーバ200に送る。

【0101】
ファイル番号m=1,・・・,Mに対して、サーバ200は、第1及び第2の暗号検索キーワード(kw,kw)を利用して、上記表Tから第1及び第2の探索した暗号化行列要素vma,vmbを探す。

【0102】
そして、サーバ200は、新カウンタ値counterを使用して、第mの暗号化検索式Γと第1及び第2の探索した暗号化行列要素vma,vmbとに基づいて、次式で表される第mの評価値Zを計算する。
=EvalGC(counter,Γ,(vma,vmb))

【0103】
換言すると、第1及び第2の探索した暗号化行列要素vma,vmbの最下位ビットlsbを、次式で表されるように、それぞれ、第1及び第2の探索したGarbled変数αおよびβとしたとき、
α=lsb(vma
β=lsb(vmb
サーバ200は、次式で表されるように、第1の探索したGarbeld変数αと第2の探索したGarbled変数βとを一対の変数値として持つGarbeld出力値p(αβ)と、新カウンタ値counterと第1及び第2の探索した暗号化行列要素vma,vmbとの組み合わせに対して1ビットを出力するハッシュ関数H(counter,vma,vmb)の出力値との排他的論理和を、第mの評価値Zとして計算する。
=p(αβ)+H(counter,vma,vmb)mod2

【0104】
尚、第mの評価値Zは、次式で表すこともできる。
=p(αβ)-H(counter,vma,vmb)mod2

【0105】
そして、サーバ200は、第mの評価値Zが1となる全ての第mの暗号ファイルCをクライアント100へ返す。

【0106】
図11は、サーバ200での検索フェーズの動作の一例を示す図である。

【0107】
図11に示されるように、サーバ200は、図10(B)で示される表Tを保管している。図11の例では、第1及び第2の暗号検索キーワードkw,kwが、それぞれ、第1及び第2の暗号キーワードkw,kwに等しい場合を示している。

【0108】
したがって、クライアント100からサーバ200へは、新カウンタ値counterと第1及び第2の暗号キーワードkw,kwと第1及び第2の暗号化検索式Γ,Γとが送られてくる。

【0109】
サーバ200は、次式に従って、第1及び第2の評価値Z,Zを計算する。
=EvalGC(counter,Γ,(v11,v12))=f(1,1)
=EvalGC(counter,Γ,(v21,v22))=f(1,0)

【0110】
ここで、検索式f(x,x)がANDであるとすると、f(1,1)=1であるので、サーバ200は、検索された暗号ファイルの集合として第1の暗号ファイルCをクライアント100へ返す。

【0111】
クライアント100では、第1の暗号ファイルCを第2の暗号鍵kを使って所定の復号アルゴリズムDecにより復号して、次式で表わされるような、第1のファイルDを計算する。
=Deck(C

【0112】
以上で、本実施形態に係る暗号検索システムの検索フェーズの動作の説明を終える。

【0113】
以上の説明から明らかなように、ブール関数から成る検索式f(x,x)の真理値表[f(0,0),・・・,f(1,1)]を、第1及び第2の検索キーワードw,wと第1の秘密鍵k’と新カウンタ値counterとを使用してGarbled回路により暗号化し、第1乃至第MのファイルD~Dに対応する第1乃至第Mの暗号化検索式Γ~Γを生成しているので、検索式を秘匿でき、検索フェーズを2-passとすることができる。
【実施例1】
【0114】
図12を参照して、本発明の第1の実施例に係る暗号検索システムについて説明する。図12は、本発明の第1の実施例に係る暗号検索システムの構成を示すブロック図である。図示の暗号検索システムは、クライアント100とサーバ200とから構成される。クライアント100は、ユーザ端末とも呼ばれる。
【実施例1】
【0115】
暗号検索システムは、クライアント(ユーザ端末)100がサーバ200に第1乃至第M(Mは2以上の整数)の暗号ファイルと暗号化索引を保管し、クライアント(ユーザ端末)100がキーワード検索によってサーバ200から検索された所望のファイルの集合を取得するシステムである。
【実施例1】
【0116】
クライアント100は、キーワード暗号化部110と、ファイル暗号化部120と、索引暗号化部130と、表送信部140と、カウンタ145と、保持部150と、検索キーワード暗号化部160と、検索式暗号化部170と、暗号ファイル取得部180と、ファイル解読部190と、から構成されている。
【実施例1】
【0117】
カウンタ145は、初期値として0がセットされ、後述するように1ずつ増加して、カウンタ値counterを出力する。
【実施例1】
【0118】
保持部150は、第1の秘密鍵k’と、第2の秘密鍵kと、ファイル数Mと、カウンタ値counterとを保持する。第1の秘密鍵k’は、キーワードを暗号化するために使用される鍵である。第2の秘密鍵kは、ファイルを暗号化したり、暗号ファイルを復号するために使用される鍵である。
【実施例1】
【0119】
キーワード暗号化部110は、第1の秘密鍵k’を使って後述するように第1乃至第N(Nは2以上の整数)のキーワードw~wをランダム化して、それぞれ、第1乃至第Nの暗号キーワードkw~kwを生成する。
【実施例1】
【0120】
ファイル暗号化部120は、第2の秘密鍵kを使って後述するように第1乃至第MのファイルD~Dを暗号化して、それぞれ、第1乃至第Mの暗号ファイルC~Cを生成する。
【実施例1】
【0121】
索引暗号化部130は、後述する索引を第1の秘密鍵k’を使って暗号化して、後述するようなM行N列のマトリックスの暗号化索引を生成する。
【実施例1】
【0122】
表送信部140は、第1乃至第Nの暗号キーワードkw~kwを列の欄とし、第1乃至第Mの暗号ファイルC~Cを行の欄とした、M行N列のマトリックスの暗号化索引からなる表Tをサーバ200へ送信してサーバ200へ保管させる。
【実施例1】
【0123】
検索キーワード暗号化部160は、第1乃至第Nのキーワードw~wから選択された第1及び第2の検索キーワードw,wを第1の秘密鍵k’を使って後述するようにランダム化して、それぞれ、第1及び第2の暗号検索キーワードkw,kwを生成する。
【実施例1】
【0124】
検索式暗号化部170は、保持部150に保持したカウンタ値counterをカウンタ145を使用して1だけ増加させて新カウンタ値counterを生成させ、その新カウンタ値counterを受ける。この新カウンタ値counterは、再び、保持部150に保持される。
【実施例1】
【0125】
検索式暗号化部170は、検索式f(x,x)と第2及び第2の検索キーワードw,wと第1の秘密鍵k’とを受ける。検索式f(x,x)は、各々が0又は1の値をとる第1のブール変数xと第2のブール変数xとのブール関数から成る。したがって、検索式f(x,x)は、例えば、ANDやORから成る。
【実施例1】
【0126】
検索式暗号部170は、検索式f(x,x)の真理値表[f(0,0),・・・,f(1,1)]を、第1及び第2の検索キーワードw,wと第1の秘密鍵k’と新カウンタ値counterとを使用してGarbled回路により後述するように暗号化し、第1乃至第MのファイルD~Dにそれぞれ対応する第1乃至第Mの暗号化検索式Γ,・・・,Γを生成する。
【実施例1】
【0127】
暗号ファイル取得部180は、第1及び第2の暗号検索キーワードkw,kwと新カウンタ値counterと第1乃至第Mの暗号化検索式Γ~Γとをサーバ200へ送って、サーバ200から第1及び第2の検索キーワードw,wが検索式f(x,x)を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する。
【実施例1】
【0128】
ファイル解読部190は、取得した検索された暗号ファイルの集合を第2の秘密鍵kを使用して後述のように復号して、上記検索された所望のファイルの集合を得る。
【実施例1】
【0129】
一方、サーバ200は、記憶領域210と、暗号検索部220と、から構成されている。
【実施例1】
【0130】
記憶領域210は、クライアント100から送られてくる暗号ファイルの集合および上記表Tを保持する。
【実施例1】
【0131】
暗号検索部220は、クライアント100から受信した、第1及び第2の暗号検索キーワードkw,kwと新カウンタ値counterと第1乃至第Mの暗号化検索式Γ~Γとに基づいて、表Tを参照して後述のように暗号ファイルの集合を検索し、上記検索された暗号ファイルの集合を生成する。
【実施例1】
【0132】
前述したように、暗号検索システムの動作は、ユーザ端末(クライアント)100が暗号ファイルおよび暗号化索引をサーバ200に格納する「格納フェーズ」と、ユーザ端末(クライアント)100がサーバ200から所望のファイルを検索する「検索フェーズ」と、に分けられる。
【実施例1】
【0133】
最初に、図13乃至図17を参照して、暗号検索システムの「格納フェーズ」の動作について説明する。
【実施例1】
【0134】
図13は、第1の実施例による暗号検索システムのクライアント100における格納フェーズのブロック図である。
【実施例1】
【0135】
キーワード暗号化部110には、キーワードの集合Wとして、第1乃至第Nのキーワード{w,・・・,w}が供給される。また、キーワード暗号化部110には、保持部150(図12参照)から第1の秘密鍵k’も供給される。キーワード暗号化部110は、第n(1≦n≦N)のキーワードwを第1の秘密鍵k’を使って後述のようにランダム化して、第nの暗号キーワードkwを生成する。nはキーワード番号である。ここで、第nのキーワードwはどのように長くても構わない。一方、第nの暗号キーワードkwは所定のビット長を持つ。本例では、第nの暗号キーワードkwは128ビットのビット長を持つ。
【実施例1】
【0136】
ファイル暗号化部120には、ファイルの集合Dとして、第1乃至第Mのファイル{D,・・・,D}が供給される。また、ファイル暗号化部120には、保持部150(図12参照)から第2の秘密鍵kも供給される。ファイル暗号化部120は、第m(1≦m≦M)のファイルDを第2の秘密鍵kを使って後述のように暗号化して、第mの暗号ファイルCを生成する。mはファイル番号である。
【実施例1】
【0137】
索引暗号化部130には、索引(後述する)とファイル数Mとキーワードの集合Wとが供給される。また、索引暗号化部130には、保持部150(図12参照)から第1の秘密鍵k’も供給される。
【実施例1】
【0138】
索引は、第1乃至第Nのキーワードw~wを特定するキーワード番号nを列とし、第1乃至第MのファイルD~Dを特定するファイル番号mを行とした、第m行第n列の原行列要素emnを含む、M行N列のマトリックスから成る。
【実施例1】
【0139】
第mのファイルDが第nのキーワードwを含むなら、第m行第n列の原行列要素emnは1に等しい(emn=1)。さもなければ、emn=0である。
【実施例1】
【0140】
索引暗号化部130は、M行N列のマトリックスから成る索引を、第1の秘密鍵k’を使用して後述のように暗号化して、第m行第n列の暗号化行列要素vmnの各々が所定ビット数から成るM行N列のマトリックスの暗号化索引を生成する。図示の例では、第m行第n列の暗号化行列要素vmnは、128ビットの乱数からなる。
【実施例1】
【0141】
表送信部140は、図13に示されるように、第1乃至第Nの暗号キーワードkw~kwを列の欄とし、第1乃至第Mの暗号ファイルC~Cを行の欄とした、M行N列のマトリックスの暗号化索引から成る表Tを、サーバ200へ送信してサーバ200の記憶領域210(図12参照)に保管させる。
【実施例1】
【0142】
上述したように、カウンタ145(図12参照)には初期値として0のカウンタ値counterがセットされている。
【実施例1】
【0143】
クライアントのメモリである保持部150(図12)は、第1の秘密鍵k’と第2の秘密鍵kとファイル数Mとカウンタ値counterとを保持している。
【実施例1】
【0144】
図14は、図13に示したキーワード暗号化部110の構成を示すブロック図である。
【実施例1】
【0145】
キーワード暗号化部110は、擬似ランダム関数発生器112から成る。擬似ランダム関数発生器112は、第nのキーワードwと第1の秘密鍵k’とから、所定の擬似ランダム関数PRFを使用して、第nの暗号キーワードkwを生成する。上述したように、本例では、第nの暗号キーワードkwは、128ビットのビット長を持つ。
【実施例1】
【0146】
図15は、図13に示したファイル暗号化部120の構成を示すブロック図である。
【実施例1】
【0147】
ファイル暗号化部120は、所定の暗号化アルゴリズムEncに従って暗号化を行なう暗号化器122から成る。暗号化器122は、第mのファイルDを第2の秘密鍵kを使って所定の暗号化アルゴリズムEncにより第mの暗号ファイルCに暗号化する。
【実施例1】
【0148】
図16は、図13に示した索引暗号化部130の構成を示すブロック図である。
【実施例1】
【0149】
索引暗号化部130は、索引用ラベル生成部132と、選択部134とから成る。
【実施例1】
【0150】
索引用ラベル生成部132は、ファイル番号mと第nのキーワードwとの組(m、w)に対して、第1の秘密鍵k’を使用して第1及び第2の暗号化索引候補vmn、vmnを生成する。第1及び第2の暗号化索引候補vmn、vmnは、それぞれ、第m行第n列の行列要素を0および1とした上付き文字を持ち、第m行第n列の暗号化行列要素用の最下位ビットが異なる候補から成る。
【実施例1】
【0151】
選択部134は、生成された第1及び第2の暗号化索引候補vmn、vmnから、上付き文字が第m行第n列の原行列要素emnに等しい方を第m行第n列の暗号化行列要素vmnとして選択し出力する。
【実施例1】
【0152】
図17は、図16に示した索引用ラベル生成部132の構成を示すブロック図である。
【実施例1】
【0153】
索引用ラベル生成部132は、第1の候補生成部1322と、第2の候補生成部1324と、反転部1326とから成る。
【実施例1】
【0154】
第1の候補生成部1322は、ファイル番号mと第nのキーワードwと0との組(m,w,0)に対して、第1の秘密鍵k’を使用して、所定の擬似ランダム関数PRFにより第1の暗号化索引候補vmnを生成する。
【実施例1】
【0155】
同様に、第2の候補生成部1324は、ファイル番号mと第nのキーワードwと1との組(m,w,1)に対して、第1の秘密鍵k’を使用して、所定の擬似ランダム関数PRFにより第2の暗号化索引候補vmnを生成する。
【実施例1】
【0156】
反転部1326は、生成した第1の暗号化索引候補vmnの最下位ビットlsb(vmn)と生成した第2の暗号化索引候補vmnの最下位ビットlsb(vmn)とが等しい(lsb(vmn)=lsb(vmn))場合、第2の暗号化索引候補vmnの最下位ビットlsb(vmn)を、次式に従って強制的に反転して、第2の暗号化索引候補vmnを得る。
mn:=vmn+(0・・・・01)
ここで、演算子“+”は排他的論理和である。
【実施例1】
【0157】
以上が、暗号検索システムの「格納フェーズ」の動作の説明である。
【実施例1】
【0158】
次に、図18乃至図24を参照して、暗号検索システムの「検索フェーズ」の動作について説明する。
【実施例1】
【0159】
図18は、第1の実施例による暗号検索システムのクライアント100における検索フェーズのブロック図である。
【実施例1】
【0160】
検索キーワード暗号化部160には、第1乃至第Nのキーワードw~wから選択された第1及び第2の検索キーワードw、wが供給される。また、検索キーワード暗号化部160には、保持部150(図12)から第1の秘密鍵k’も供給される。検索キーワード暗号化部160は、第1及び第2の検索キーワードw、wを第1の秘密鍵k’を使って後述のようにランダム化して、それぞれ、第1及び第2の暗号検索キーワードkw、kwを生成する。
【実施例1】
【0161】
カウンタ145(図12)は、保持部150(図12)に保持したカウンタ値counterを1だけ増加して、新カウンタ値counterを生成する。この新カウンタ値counterは、再び、クライアントの保持部150に保持される。
【実施例1】
【0162】
検索式暗号化部170には、この新カウンタ値counterと検索式f(x,x)と第1及び第2の検索キーワードw、wとが供給される。また、検索式暗号化部170には、ファイル数Mおよび第1の秘密鍵k’も供給される。
【実施例1】
【0163】
検索式f(x,x)は、上述したように、各々が0又は1の値をとる第1のブール変数xと第2のブール変数xとのブール関数から成る。検索式f(x,x)は、例えば、ANDやORから成る。
【実施例1】
【0164】
検索式暗号化部170は、検索式f(x,x)の真理値表[f(0,0),・・・,f(1,1)]を、第1及び第2の検索キーワードw、wと第1の秘密鍵k’と新カウンタ値counterとを使用してGarbled回路により後述のように暗号化し、第1乃至第MのファイルD~Dにそれぞれ対応する第1乃至第Mの暗号化検索式Γ~Γを生成する。
【実施例1】
【0165】
図19は、図18に示した検索キーワード暗号化部160の構成を示すブロック図である。
【実施例1】
【0166】
検索キーワード暗号化部160は、第1の検索キーワード暗号化器162と、第2の検索キーワード暗号化器164とから成る。
【実施例1】
【0167】
第1の検索キーワード暗号化器162は、第1の検索キーワードwと第1の秘密鍵k’とから、所定の擬似ランダム関数PRFを使用して、第1の暗号検索キーワードkwを生成する。
【実施例1】
【0168】
同様に、第2の検索キーワード暗号化器164は、第2の検索キーワードwと第1の秘密鍵k’とから、所定の擬似ランダム関数PRFを使用して、第2の暗号検索キーワードkwを生成する。
【実施例1】
【0169】
図20は、図18に示した検索式暗号化部170の構成を示すブロック図である。
【実施例1】
【0170】
検索式暗号化部170は、第1の検索式用ラベル生成部172と、第2の検索式用ラベル生成部174と、Garbled回路生成部176とから成る。
【実施例1】
【0171】
第1の検索式用ラベル生成部172は、ファイル番号mと第1の検索キーワードwとの組(m,w)に対して、第1の秘密鍵k’を使用して、0および1の上付き文字を持ち、第mのファイルD用の最下位ビットが異なる一組の第1のラベルv、vを生成する。
【実施例1】
【0172】
同様に、第2の検索式用ラベル生成部174は、ファイル番号mと第2の検索キーワードwとの組(m,w)に対して、第1の秘密鍵k’を使用して、0および1の上付き文字を持ち、第mのファイルD用の最下位ビットが異なる一組の第2のラベルv、vを生成する。
【実施例1】
【0173】
第1及び第2の検索式用ラベル生成部172、174の具体的な構成は、図17に図示した索引用ラベル生成部132と同様であるので、説明の重複を避けるためにそれらの説明については省略する。
【実施例1】
【0174】
Garbled回路生成部176は、検索式f(x,x)と一組の第1のラベルv、vと一組の第2のラベルv、vと新カウンタ値counterとから、後述のように第mの暗号化検索式Γを生成する。
【実施例1】
【0175】
図21は、図20に示したGarbled回路生成部176の処理を説明するためのブロック図である。
【実施例1】
【0176】
検索式f(x,x)の第1及び第2のブール変数(x,x)の4つの組み合わせ(0,0)、(0,1)、(1,0)、(1,1)について、ラベルvx1及びvx2の最下位ビットlsb(vx1)及びlsb(vx2)を、それぞれ、第1及び第2のGarbled変数a、aとする。
【実施例1】
【0177】
この場合、Garbled回路生成部176は、次式で示されるように、新カウンタ値counterとラベルvx1及びvx2との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vx1,vx2)の出力値と検索式f(x,x)との排他的論理和を、Garbeld出力値p(a)として計算する。
p(a)=H(counter,vx1,vx2)+f(x,x)mod2
【実施例1】
【0178】
第mの暗号化検索式Γは、次式で表される。
Γ=[p(00),p(01),p(10),p(11)]
【実施例1】
【0179】
図22は、第1の実施例による暗号検索システムのサーバ200における検索フェーズのブロック図である。
【実施例1】
【0180】
サーバ200の暗号検索部220は、クライアント100から、新カウンタ値conterと第1及び第2の暗号検索キーワードkw、kwと第1乃至第Mの暗号化検索式Γ~Γとを受信する。また、暗号検索部220は、サーバのメモリである記憶領域210(図12参照)に保管されている表Tを参照する。
【実施例1】
【0181】
暗号検索部220は、第1及び第2の暗号検索キーワードkw、kwと新カウンタ値counterと第1乃至第Mの暗号化検索式Γ~Γとに基づいて、表Tを参照して暗号ファイルの集合を検索し、検索された暗号ファイルの集合を生成する。
【実施例1】
【0182】
暗号検索部220は、暗号化要素探索部222と、Garbled回路評価部224と、暗号ファイル選択部226とから成る。
【実施例1】
【0183】
暗号化要素探索部222は、第mの暗号化検索式Γに対して、表Tから第1及び第2の暗号検索キーワードkw、kwの列を探して、当該列の一対の第m行の第1及び第2の探索した暗号化行列要素vma、vmbを生成する。
【実施例1】
【0184】
Garbled回路評価部224は、新カウンタ値conterを使用して、第mの暗号化検索式Γと第1及び第2の探索した暗号化行列要素vma、vmbとに基づいて、後述のように、0又は1の値をとる第mの評価値Zを生成する。
【実施例1】
【0185】
暗号ファイル選択部226は、第mの評価値Zが1であるときに、第mの暗号ファイルCを上記検索された暗号ファイルの集合の1つとして選択して出力する。
【実施例1】
【0186】
図23は、図22に示したGarbled回路評価部224の構成を示すブロック図である。
【実施例1】
【0187】
Garbled回路評価部224は、第1の変数生成部2242と、第2の変数生成部2244と、評価値生成部2246とから成る。
【実施例1】
【0188】
第1の変数生成部2242は、次式で示されるように、第1の探索した暗号化行列要素vmaの最下位ビットlsb(vma)を、第1の探索したGarbled変数αとして生成する。
α=lsb(vma
【実施例1】
【0189】
同様に、第2の変数生成部2244は、次式で示されるように、第2の探索した暗号化行列要素vmbの最下位ビットlsb(vmb)を、第2の探索したGarbled変数βとして生成する。
β=lsb(vmb
【実施例1】
【0190】
評価値生成部2246は、次式で表されるように、第1の探索したGarbled変数αと第2の探索したGarbled変数βとを一対の変数値として持つGarbled出力値p(αβ)と、新カウンタ値counterと第1及び第2の探索した暗号化行列要素vma、vmbとの組み合わせに対して1ビットを出力するハッシュ関数H(counter,vma,vmb)の出力値との排他的論理和を、第mの評価値Zとして計算し出力する。
=p(αβ)+H(counter,vma,vmb)mod2
【実施例1】
【0191】
尚、上式の代わりに、評価値生成部2246は、第mの評価値Zを次式に従って計算してもよい。
=p(αβ)-H(counter,vma,vmb)mod2
【実施例1】
【0192】
図24は、第1の実施例による暗号検索システムのクライアント100における検索フェーズで使用されるファイル解読部190の構成を示すブロック図である。
【実施例1】
【0193】
ここでは、サーバ200から、検索された暗号ファイルの集合として、第1乃至第Lの検索された暗号ファイル{C’,・・・,C’}が取得されたとする。
【実施例1】
【0194】
ファイル解読部190は、所定の復号アルゴリズムDecに従って復号を行なう復号器192から成る。
【実施例1】
【0195】
復号器192には、第l(1≦l≦L)の検索された暗号ファイルC’が供給される。復号器192には、クライアントのメモリである保持部150(図12参照)から、第2の秘密鍵kも供給される。復号器192は、第lの検索された暗号ファイルC’を、第2の秘密鍵kを使って所定の復号アルゴリズムDecにより第lの検索されたファイルD’に復号する。
【実施例1】
【0196】
これにより、ファイル解読部190は、検索された所望のファイルの集合として、第1乃至第Lの検索されたファイル{D’,・・・,D’}を生成する。
【実施例1】
【0197】
以上が、暗号検索システムの「検索フェーズ」の動作の説明である。
【実施例1】
【0198】
本発明の第1の実施例に係る暗号検索システムによれば、検索式f(x,x)を秘匿でき、検索フェーズを2-passとすることができる。その理由は、検索式f(x,x)の真理値表[f(0,0),・・・、f(1,1)]を、第1及び第2の検索キーワードw,wと第1の秘密鍵k’と新カウンタ値counterとを使用してGarbled回路により暗号化し、第1乃至第MのファイルD~Dに対応する第1乃至第Mの暗号化検索式Γ~Γを生成しているからである。
【実施例1】
【0199】
また、上記本発明の第1の実施例に係る暗号検索システムは、暗号検索方法として実現され得る。さらに、上記本発明の第1の実施例に係る暗号検索システムのうちのクライアント(ユーザ端末)100が実施する部分は、当該クライアント(ユーザ端末)100に含まれるメモリ(ROM等)に格納された暗号検索プログラムによって実行されるようにしてもよい。そして、上記本発明の第1の実施例に係る暗号検索システムのうちのサーバ200が実施する部分も、当該サーバ200に含まれるメモリ(ROM等)に格納された暗号検索プログラムによって実行されるようにしてもよい。
【実施例1】
【0200】
以上、実施形態(実施例)を参照して本発明を説明したが、本発明は上記実施形態(実施例)に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【実施例1】
【0201】
例えば、上記実施形態(実施例)では、第1乃至第Nの暗号キーワードkw~kwやM行N列のマトリックスの暗号化索引の第m行第n列の暗号化行列要素vmnの各々は、128ビットのビット長を有しているが、それ以外の所定のビット数からなってもよい。また、検索キーワードの個数を3個以上に拡張してもよい。
【実施例1】
【0202】
上記の実施形態(実施例)の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【実施例1】
【0203】
(付記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)と、
を有する暗号検索システム。
【実施例1】
【0204】
(付記2) 前記ファイル暗号化部(120)は、前記第mのファイル(D)を前記第2の秘密鍵(k)を使って所定の暗号化アルゴリズム(Enc)により第mの暗号ファイル(C)に暗号化する暗号化器(122)から成り、
前記ファイル解読部(190)は、前記取得した検索された暗号ファイルの集合を前記第2の秘密鍵(k)を使って所定の復号アルゴリズム(Dec)により前記検索された所望のファイルの集合に復号する復号器(192)から成る、
付記1に記載の暗号検索システム。
【実施例1】
【0205】
(付記3) 前記キーワード暗号化部(110)は、前記第nのキーワード(w)と前記第1の秘密鍵(k’)とから、所定の擬似ランダム関数(PRF)を使用して、第nの暗号キーワード(kw)を生成する擬似ランダム関数発生器(112)から成る、付記1又は2に記載の暗号検索システム。
【実施例1】
【0206】
(付記4) 前記索引暗号化部(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)と、
を有する、付記3に記載の暗号検索システム。
【実施例1】
【0207】
(付記5) 前記索引用ラベル生成部(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)と、
から成る、付記4に記載の暗号検索システム。
【実施例1】
【0208】
(付記6) 前記検索キーワード暗号化部(160)は、
前記第1の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第1の暗号検索キーワード(kw)を生成する第1の検索キーワード暗号化器(162)と、
前記第2の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第2の暗号検索キーワード(kw)を生成する第2の検索キーワード暗号化器(164)と、
から成る、付記3乃至5のいずれか1項に記載の暗号検索システム。
【実施例1】
【0209】
(付記7) 前記検索式暗号化部(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乃至6のいずれか1項に記載の暗号検索システム。
【実施例1】
【0210】
(付記8) 前記Garbled回路生成部(176)は、
前記検索式(f(x,x))の前記第1及び第2のブール変数(x,x)の4つの組み合わせ(0,0),(0,1),(1,0),(1,1)について、前記ラベル(vx1)及び(vx2)の最下位ビットをそれぞれ第1及び第2のGarbled変数(a,a)としたとき、前記新カウンタ値(counter)と前記ラベル(vx1)及び(vx2)との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vx1,vx2)の出力値と前記検索式(f(x,x))との排他的論理和をGarbled出力値p(a)として得られる4つの組み合わせ[p(00),p(01),p(10),p(11)]を、前記第mの暗号化検索式(Γ)として出力する、
付記7に記載の暗号検索システム。
【実施例1】
【0211】
(付記9) 前記サーバ(200)は、
前記ユーザ端末(100)から送られてくる前記表(T)を保持する記憶領域(210)と、
前記ユーザ端末(200)から受信した、前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とに基づいて、前記表(T)を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索部(220)と、
を有する、付記7又は8に記載の暗号検索システム。
【実施例1】
【0212】
(付記10) 前記暗号検索部(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)と、
から構成される付記9に記載の暗号検索システム。
【実施例1】
【0213】
(付記11) 前記Garbled回路評価部(224)は、
前記第1の探索した暗号化行列要素(vma)の最下位ビットを第1の探索したGarbled変数(α)として生成する第1の変数生成部(2242)と、
前記第2の探索した暗号化行列要素(vmb)の最下位ビットを第2の探索したGarbled変数(β)として生成する第2の変数生成部(2244)と、
前記第1の探索したGarbled変数(α)と前記第2の探索したGarbled変数(β)とを一対の変数値として持つGarbled出力値p(αβ)と、前記新カウンタ値(counter)と前記第1及び第2の探索した暗号化行列要素(vma,vmb)との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vma,vmb)の出力値との排他的論理和を、前記第mの評価値(Z)として出力する評価値生成部(2246)と、
から構成される付記10に記載の暗号検索システム。
【実施例1】
【0214】
(付記12) ユーザ端末(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)と、
を含む暗号検索方法。
【実施例1】
【0215】
(付記13) 前記ファイル暗号化ステップ(120)は、前記第mのファイル(D)を前記第2の秘密鍵(k)を使って所定の暗号化アルゴリズム(Enc)により第mの暗号ファイル(C)を生成する暗号化ステップ(122)を含み、
前記ファイル解読ステップ(190)は、前記取得した検索された暗号ファイルの集合を前記第2の秘密鍵(k)を使って所定の復号アルゴリズム(Dec)により前記検索された所望のファイルの集合を生成する復号ステップ(192)を含む、
付記12に記載の暗号検索方法。
【実施例1】
【0216】
(付記14) 前記キーワード暗号化ステップ(110)は、前記第nのキーワード(w)と前記第1の秘密鍵(k’)とから、所定の擬似ランダム関数(PRF)を使用して、第nの暗号キーワード(kw)を生成する擬似ランダム関数発生ステップ(112)を含む、付記12又は13に記載の暗号検索方法。
【実施例1】
【0217】
(付記15) 前記索引暗号化ステップ(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)と、
を含む、付記14に記載の暗号検索方法。
【実施例1】
【0218】
(付記16) 前記索引用ラベル生成ステップ(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)と、
を含む、付記15に記載の暗号検索方法。
【実施例1】
【0219】
(付記17) 前記検索キーワード暗号化ステップ(160)は、
前記第1の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第1の暗号検索キーワード(kw)を生成する第1の検索キーワード暗号化ステップ(162)と、
前記第2の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第2の暗号検索キーワード(kw)を生成する第2の検索キーワード暗号化ステップ(164)と、
を含む、付記14乃至16のいずれか1項に記載の暗号検索方法。
【実施例1】
【0220】
(付記18) 前記検索式暗号化ステップ(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)と、
を含む、付記12乃至17のいずれか1項に記載の暗号検索方法。
【実施例1】
【0221】
(付記19) 前記Garbled回路生成ステップ(176)は、
前記検索式(f(x,x))の前記第1及び第2のブール変数(x,x)の4つの組み合わせ(0,0),(0,1),(1,0),(1,1)について、前記ラベル(vx1)及び(vx2)の最下位ビットをそれぞれ第1及び第2のGarbled変数(a,a)としたとき、前記新カウンタ値(counter)と前記ラベル(vx1)及び(vx2)との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vx1,vx2)の出力値と前記検索式(f(x,x))との排他的論理和をGarbled出力値p(a)として得られる4つの組み合わせ[p(00),p(01),p(10),p(11)]を、前記第mの暗号化検索式(Γ)として出力する、
付記18に記載の暗号検索方法。
【実施例1】
【0222】
(付記20) 前記サーバ(200)が、前記ユーザ端末(100)から送られてくる前記表(T)を記憶領域(210)に保持するステップと、
前記サーバ(200)が、前記ユーザ端末(100)から受信した、前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とに基づいて、前記表(T)を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索ステップ(220)と、
を更に含む、付記18又は19に記載の暗号検索方法。
【実施例1】
【0223】
(付記21) 前記暗号検索ステップ(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)と、
を含む付記20に記載の暗号検索方法。
【実施例1】
【0224】
(付記22) 前記Garbled回路評価ステップ(224)は、
前記第1の探索した暗号化行列要素(vma)の最下位ビットを第1の探索したGarbled変数(α)として生成する第1の変数生成ステップ(2242)と、
前記第2の探索した暗号化行列要素(vmb)の最下位ビットを第2の探索したGarbled変数(β)として生成する第2の変数生成ステップ(2244)と、
前記第1の探索したGarbled変数(α)と前記第2の探索したGarbled変数(β)とを一対の変数値として持つGarbled出力値p(αβ)と、前記新カウンタ値(counter)と前記第1及び第2の探索した暗号化行列要素(vma,vmb)との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vma,vmb)の出力値との排他的論理和を、前記第mの評価値(Z)として出力する評価値生成ステップ(2246)と、
を含む付記21に記載の暗号検索方法。
【実施例1】
【0225】
(付記23) サーバ(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)を使用して復号して前記検索された所望のファイルの集合を得るファイル解読手順(1909)と、
を実行させるための暗号検索プログラム。
【実施例1】
【0226】
(付記24) 前記ファイル暗号化手順(120)は、前記第mのファイル(D)を前記第2の秘密鍵(k)を使って所定の暗号化アルゴリズム(Enc)により第mの暗号ファイル(C)を生成する暗号化手順(122)から成り、
前記ファイル解読手順(190)は、前記取得した検索された暗号ファイルの集合を前記第2の秘密鍵(k)を使って所定の復号アルゴリズム(Dec)により前記検索された所望のファイルの集合を生成する復号手順(192)から成る、
付記23に記載の暗号検索プログラム。
【実施例1】
【0227】
(付記25) 前記キーワード暗号化手順(110)は、前記第nのキーワード(w)と前記第1の秘密鍵(k’)とから、所定の擬似ランダム関数(PRF)を使用して、第nの暗号キーワード(kw)を生成する擬似ランダム関数発生手順(112)から成る、付記23又は24に記載の暗号検索プログラム。
【実施例1】
【0228】
(付記26) 前記索引暗号化手順(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)と、
から成る、付記25に記載の暗号検索プログラム。
【実施例1】
【0229】
(付記27) 前記索引用ラベル生成手順(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)と、
から成る、付記26に記載の暗号検索プログラム。
【実施例1】
【0230】
(付記28) 前記検索キーワード暗号化手順(160)は、
前記第1の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第1の暗号検索キーワード(kw)を生成する第1の検索キーワード暗号化手順(162)と、
前記第2の検索キーワード(w)と前記第1の秘密鍵(k’)とから、前記所定の擬似ランダム関数(PRF)を使用して、前記第2の暗号検索キーワード(kw)を生成する第2の検索キーワード暗号化手順(164)と、
から成る、付記25乃至27のいずれか1項に記載の暗号検索プログラム。
【実施例1】
【0231】
(付記29) 前記検索式暗号化手順(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)と、
から成る、付記23乃至28のいずれか1項に記載の暗号検索プログラム。
【実施例1】
【0232】
(付記30) 前記Garbled回路生成手順(176)は、
前記検索式(f(x,x))の前記第1及び第2のブール変数(x,x)の4つの組み合わせ(0,0),(0,1),(1,0),(1,1)について、前記ラベル(vx1)及び(vx2)の最下位ビットをそれぞれ第1及び第2のGarbled変数(a,a)としたとき、前記新カウンタ値(counter)と前記ラベル(vx1)及び(vx2)との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vx1,vx2)の出力値と前記検索式(f(x,x))との排他的論理和をGarbled出力値p(a)として得られる4つの組み合わせ[p(00),p(01),p(10),p(11)]を、前記第mの暗号化検索式(Γ)として出力する、
付記29に記載の暗号検索プログラム。
【実施例1】
【0233】
(付記31) 付記29又は30に記載の暗号検索プログラムと共に使用され、コンピュータである前記サーバ(200)に検索を実行させる暗号検索プログラムであって、前記コンピュータである前記サーバ(200)に、
前記ユーザ端末(100)から送られてくる前記表(T)を記憶領域(210)に保持する手順と、
前記ユーザ端末(100)から受信した、前記第1及び第2の暗号検索キーワード(kw,kw)と前記新カウンタ値(counter)と前記第1乃至第Mの暗号化検索式(Γ,・・・,Γ)とに基づいて、前記表(T)を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索手順(220)と、
を実行させる暗号検索プログラム。
【実施例1】
【0234】
(付記32) 前記暗号検索手順(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)と、
から成る付記31に記載の暗号検索プログラム。
【実施例1】
【0235】
(付記33) 前記Garbled回路評価手順(224)は、
前記第1の探索した暗号化行列要素(vma)の最下位ビットを第1の探索したGarbled変数(α)として生成する第1の変数生成手順(2242)と、
前記第2の探索した暗号化行列要素(vmb)の最下位ビットを第2の探索したGarbled変数(β)として生成する第2の変数生成手順(2244)と、
前記第1の探索したGarbled変数(α)と前記第2の探索したGarbled変数(β)とを一対の変数値として持つGarbled出力値p(αβ)と、前記新カウンタ値(counter)と前記第1及び第2の探索した暗号化行列要素(vma,vmb)との組み合わせに対して1ビットを出力するハッシュ関数H(counter,vma,vmb)の出力値との排他的論理和を、前記第mの評価値(Z)として出力する評価値生成手順(2246)と、
から成る付記32に記載の暗号検索プログラム。
【産業上の利用可能性】
【0236】
本発明は、ANDやORなどの任意のブール関数から成る検索式を秘匿しつつ、検索フェーズを2-passとする方式に利用可能である。
【符号の説明】
【0237】
100 クライアント(ユーザ端末)
110 キーワード暗号化部
112 擬似ランダム関数発生器
120 ファイル暗号化部
122 暗号化器
130 索引暗号化部
132 索引用ラベル生成部
1322 第1の候補生成部
1324 第2の候補生成部
1326 反転部
134 選択部
140 表送信部
145 カウンタ
150 保持部(クライアントのメモリ)
160 検索キーワード暗号化部
162 第1の検索キーワード暗号化器
164 第2の検索キーワード暗号化器
170 検索式暗号化部
172 第1の検索式用ラベル生成部
174 第2の検索式用ラベル生成部
176 Garbled回路生成部
180 暗号ファイル取得部
190 ファイル解読部
192 復号器
200 サーバ
210 記憶領域(サーバのメモリ)
220 暗号検索部
222 暗号化要素探索部
224 Garbled回路評価部
2242 第1の変数生成部
2244 第2の変数生成部
2246 評価値生成部
226 暗号ファイル選択部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22
【図24】
23