(57)【要約】【課題】検索式を秘匿し、検索フェーズを２−ｐａｓｓとすること。【解決手段】格納フェーズでは、キーワード暗号化部により暗号化された第１乃至第Ｎの暗号キーワードを列の欄とし、ファイル暗号化部により暗号化された第１乃至第Ｍの暗号ファイルを行の欄とし、索引暗号化部により暗号化されたＭ行Ｎ列のマトリックスの暗号化索引から成る表を、ユーザ端末がサーバへ送信してサーバへ保管する。検索フェーズでは、ユーザ端末が検索キーワード暗号化部により暗号化された第１及び第２の暗号検索キーワードと、カウンタ値を１だけ増加した新カウンタ値と、検索式暗号化部により暗号化された第１乃至第Ｍの暗号化検索式とをサーバへ送って、検索された暗号ファイルの集合を取得する。検索式暗号化部は、検索式を、第１及び第２の検索キーワードと暗号鍵と新カウンタ値とを使用してGarbled回路により第１乃至第Ｍの暗号化検索式に暗号化する。【選択図】図１２
2015114432.tif 000002
【特許請求の範囲】
【請求項１】
ユーザ端末（１００）がサーバ（２００）に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、前記ユーザ端末（１００）がキーワード検索によって前記サーバ（２００）から検索された所望のファイルの集合を取得する暗号検索システムであって、前記ユーザ端末（１００）は、
第１の秘密鍵（ｋ’）を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワード（ｗ１，・・・，ｗＮ）をランダム化して、それぞれ、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を生成するキーワード暗号化部（１１０）と、
第２の秘密鍵（ｋ）を使って第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を暗号化して、それぞれ、前記第１至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を生成するファイル暗号化部（１２０）と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）を特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワード（ｗｎ）を含む第ｍのファイル（Ｄｍ）の第ｍ行第ｎ列の原行列要素（ｅｍｎ）を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、前記第１の秘密鍵（ｋ’）を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化部（１３０）と、
前記第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を列の欄とし、前記第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を行の欄とした、前記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表（Ｔ）を前記サーバ（２００）へ送信して前記サーバ（２００）へ保管させる表送信部（１４０）と、
初期値として０がセットされ、カウンタ値（counter）を出力するカウンタ（１４５）と、
前記第１の秘密鍵（ｋ’）と前記第２の秘密鍵（ｋ）とファイル数（Ｍ）と前記カウンタ値（counter）とを保持する保持部（１５０）と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）から選択された第１及び第２の検索キーワード(ｗａ，ｗｂ)を前記第１の秘密鍵（ｋ’）を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を生成する検索キーワード暗号化部（１６０）と、
前記保持部に保持した前記カウンタ値（counter）を前記カウンタ（１４５）を使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数（ｘ１）と第２のブール変数（ｘ２）とのブール関数から成る検索式（ｆ（ｘ１，ｘ２））を、前記第１及び第２の検索キーワード(ｗａ，ｗｂ)と前記第１の秘密鍵（ｋ’）と前記新カウンタ値（counter）とを使用してGarbled回路により暗号化し、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）にそれぞれ対応した第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）を生成する検索式暗号化部（１７０）と、
前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを前記サーバへ送って、前記サーバから前記第１及び第２の検索キーワード(ｗａ，ｗｂ)が前記検索式（ｆ（ｘ１，ｘ２））を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得部（１８０）と、
前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使用して復号して前記検索された所望のファイルの集合を得るファイル解読部（１９０）と、
を有する暗号検索システム。
【請求項２】
前記キーワード暗号化部（１１０）は、前記第ｎのキーワード（ｗｎ）と前記第１の秘密鍵（ｋ’）とから、所定の擬似ランダム関数（ＰＲＦ）を使用して、第ｎの暗号キーワード（ｋｗｎ）を生成する擬似ランダム関数発生器（１１２）から成る、請求項１に記載の暗号検索システム。
【請求項３】
前記索引暗号化部（１３０）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、第ｍ行第ｎ列の行列要素を０および１とした上付き文字を持ち、第ｍ行第ｎ列の暗号化行列要素用の最下位ビットが異なる第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）を生成する索引用ラベル生成部（１３２）と、
該生成された第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）から、前記上付き文字が前記第ｍ行第ｎ列の原行列要素（ｅｍｎ）に等しい方を前記第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）として選択し出力する選択部（１３４）と、
を有する、請求項２に記載の暗号検索システム。
【請求項４】
前記索引用ラベル生成部（１３２）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と０との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により前記第１の暗号化索引候補（ｖｍｎ０）を生成する第１の候補生成部（１３２２）と、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と１との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により第２の暗号化索引候補（ｖｍｎ１）を生成する第２の候補生成部（１３２４）と、
前記生成した第１の暗号化索引候補（ｖｍｎ０）の最下位ビットと前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットとが等しい場合、前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットを強制的に反転して、前記第２の暗号化索引候補（ｖｍｎ１）を得る反転部（１３２６）と、
から成る、請求項３に記載の暗号検索システム。
【請求項５】
前記検索キーワード暗号化部（１６０）は、
前記第１の検索キーワード(ｗａ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第１の暗号検索キーワード（ｋｗａ）を生成する第１の検索キーワード暗号化器（１６２）と、
前記第２の検索キーワード(ｗｂ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第２の暗号検索キーワード（ｋｗｂ）を生成する第２の検索キーワード暗号化器（１６４）と、
から成る、請求項２乃至４のいずれか１項に記載の暗号検索システム。
【請求項６】
前記検索式暗号化部（１７０）は、
前記ファイル番号（ｍ）と前記第１の検索キーワード（ｗａ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第１のラベル（ｖａ０，ｖａ１）を生成する第１の検索式用ラベル生成部（１７２）と、
前記ファイル番号（ｍ）と前記第２の検索キーワード（ｗｂ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第２のラベル（ｖｂ０，ｖｂ１）を生成する第２の検索式用ラベル生成部（１７４）と、
前記検索式（ｆ（ｘ１，ｘ２））と、前記一組の第１のラベル（ｖａ０，ｖａ１）と、前記一組の第２のラベル（ｖｂ０，ｖｂ１）と、前記新カウンタ値（counter）とから、前記第ｍの暗号化検索式（Γｍ）を生成するGarbled回路生成部（１７６）と、
から成る、請求項１乃至５のいずれか１項に記載の暗号検索システム。
【請求項７】
前記サーバ（２００）は、
前記ユーザ端末（１００）から送られてくる前記表（Ｔ）を保持する記憶領域（２１０）と、
前記ユーザ端末（２００）から受信した、前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とに基づいて、前記表（Ｔ）を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索部（２２０）と、
を有する、請求項６に記載の暗号検索システム。
【請求項８】
前記暗号検索部（２２０）は、
前記第ｍの暗号化検索式（Γｍ）に対して、前記表（Ｔ）から前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）の列を探して、当該列の一対の第ｍ行の第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）を生成する暗号化要素探索部（２２２）と、
前記新カウンタ値（counter）を使用して、前記第ｍの暗号化検索式（Γｍ）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）とに基づいて、０又は１の値をとる第ｍの評価値（Ｚｍ）を生成するGarbled回路評価部（２２４）と、
前記第ｍの評価値（Ｚｍ）が１であるときに、前記第ｍの暗号ファイル（Ｃｍ）を前記検索された暗号ファイルの集合の１つとして選択して出力する暗号ファイル選択部（２２６）と、
から構成される請求項７に記載の暗号検索システム。
【請求項９】
ユーザ端末（１００）がサーバ（２００）に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、前記ユーザ端末（１００）がキーワード検索によって前記サーバ（２００）から検索された所望のファイルの集合を取得する暗号検索方法であって、
前記ユーザ端末が、第１の秘密鍵（ｋ’）を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワード（ｗ１，・・・，ｗＮ）をランダム化して、それぞれ、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を生成するキーワード暗号化ステップ（１１０）と、
前記ユーザ端末が、第２の秘密鍵（ｋ）を使って第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を暗号化して、それぞれ、前記第１至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を生成するファイル暗号化ステップ（１２０）と、
前記ユーザ端末が、前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）を特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワード（ｗｎ）を含む第ｍのファイル（Ｄｍ）の第ｍ行第ｎ列の原行列要素（ｅｍｎ）を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、前記第１の秘密鍵（ｋ’）を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化ステップ（１３０）と、
前記ユーザ端末が、前記第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を列の欄とし、前記第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を行の欄とした、前記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表（Ｔ）を前記サーバ（２００）へ送信して前記サーバ（２００）へ保管させる表送信ステップ（１４０）と、
前記ユーザ端末が、カウンタ（１４５）に初期値として０がセットされ、カウンタ値（counter）を出力するステップと、
前記ユーザ端末が、前記第１の秘密鍵（ｋ’）と前記第２の秘密鍵（ｋ）とファイル数（Ｍ）と前記カウンタ値（counter）とを保持部（１５０）に保持するステップと、
前記ユーザ端末が、前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）から選択された第１及び第２の検索キーワード(ｗａ，ｗｂ)を前記第１の秘密鍵（ｋ’）を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を生成する検索キーワード暗号化ステップ（１６０）と、
前記ユーザ端末が、前記保持部に保持した前記カウンタ値（counter）を前記カウンタ（１４５）を使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数（ｘ１）と第２のブール変数（ｘ２）とのブール関数から成る検索式（ｆ（ｘ１，ｘ２））を、前記第１及び第２の検索キーワード(ｗａ，ｗｂ)と前記第１の秘密鍵（ｋ’）と前記新カウンタ値（counter）とを使用してGarbled回路により暗号化し、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）にそれぞれ対応した第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）を生成する検索式暗号化ステップ（１７０）と、
前記ユーザ端末が、前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを前記サーバへ送って、前記サーバから前記第１及び第２の検索キーワード(ｗａ，ｗｂ)が前記検索式（ｆ（ｘ１，ｘ２））を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得ステップ（１８０）と、
前記ユーザ端末が、前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使用して復号して前記検索された所望のファイルの集合を得るファイル解読ステップ（１９０）と、
を含む暗号検索方法。
【請求項１０】
サーバ（２００）に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、キーワード検索によって前記サーバ（２００）から検索された所望のファイルの集合を取得する処理を、コンピュータであるユーザ端末（１００）に実行させる暗号検索プログラムであって、前記コンピュータである前記ユーザ端末（１００）に、
第１の秘密鍵（ｋ’）を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワード（ｗ１，・・・，ｗＮ）をランダム化して、それぞれ、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を生成するキーワード暗号化手順（１１０）と、
第２の秘密鍵（ｋ）を使って第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を暗号化して、それぞれ、前記第１至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を生成するファイル暗号化手順（１２０）と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）を特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワード（ｗｎ）を含む第ｍのファイル（Ｄｍ）の第ｍ行第ｎ列の原行列要素（ｅｍｎ）を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、前記第１の秘密鍵（ｋ’）を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化手順（１３０）と、
前記第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を列の欄とし、前記第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を行の欄とした、前記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表（Ｔ）を前記サーバ（２００）へ送信して前記サーバ（２００）へ保管させる表送信手順（１４０）と、
カウンタ（１４５）に初期値として０がセットされ、カウンタ値（counter）を出力する手順と、
前記第１の秘密鍵（ｋ’）と前記第２の秘密鍵（ｋ）とファイル数（Ｍ）と前記カウンタ値（counter）とを保持部（１５０）に保持する手順と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）から選択された第１及び第２の検索キーワード(ｗａ，ｗｂ)を前記第１の秘密鍵（ｋ’）を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を生成する検索キーワード暗号化手順（１６０）と、
前記保持部（１５０）に保持した前記カウンタ値（counter）を前記カウンタ（１４５）を使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数（ｘ１）と第２のブール変数（ｘ２）とのブール関数から成る検索式（ｆ（ｘ１，ｘ２））を、前記第１及び第２の検索キーワード(ｗａ，ｗｂ)と前記第１の秘密鍵（ｋ’）と前記新カウンタ値（counter）とを使用してGarbled回路により暗号化し、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）にそれぞれ対応した第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）を生成する検索式暗号化手順（１７０）と、
前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを前記サーバ（２００）へ送って、前記サーバ（２００）から前記第１及び第２の検索キーワード(ｗａ，ｗｂ)が前記検索式（ｆ（ｘ１，ｘ２））を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル手順（１８０）と、
前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使用して復号して前記検索された所望のファイルの集合を得るファイル解読手順（１９０）と、
を実行させるための暗号検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号検索システム、暗号検索方法、および、暗号検索プログラムに関し、特に、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得する暗号検索システム、暗号検索方法、および、暗号検索プログラムに関する。
【背景技術】
【０００２】
この技術分野において周知のように、Yahoo!データボックスなどのデータストレージ（データ保管）サービスにおいては、ユーザ端末は、写真などの多くのファイルを（Yahoo!データボックスなどの）サーバに格納し、保管することができる。また、ユーザ端末は、ファイル名についてキーワード検索を行って、サーバから所望のファイルの集合を取得することもできる。尚、ユーザ端末は、クライアントとも呼ばれる。
【０００３】
特許文献１は、ユーザ端末がサーバに複数の暗号ファイルを保管し、ユーザ端末がキーワード検索によってサーバから所望のファイルの集合を取得する暗号検索システムを開示している。暗号検索システムの動作は、ユーザ端末が複数の暗号ファイルをサーバに格納する「格納フェーズ」と、ユーザ端末がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。
【０００４】
格納フェーズでは、ユーザ端末は、暗号化の秘密鍵を使い、複数のファイルを暗号化して、複数の暗号ファイルをサーバに保管する。また、ユーザ端末は、索引を生成し、生成した索引を暗号化して、サーバに保管する。
【０００５】
検索フェーズでは、ユーザ端末は、暗号化の秘密鍵を使って検索キーワードを暗号化して得られる暗号検索キーワードを送る。サーバは、検索キーワードを含むファイルの暗号文（暗号ファイル）の集合をユーザ端末へ返す。
【０００６】
しかしながら、特許文献１では、検索キーワードとして、１つのキーワードのみしか指定できない。
【０００７】
また、キーワード・フィールド毎に高々１つのキーワードを指定する暗号検索システムも知られている（例えば、非特許文献１〜３参照）。しかしながら、非特許文献１〜３では、特定の条件のＡＮＤを満たす文書の検索は可能であるが、それ以外のＡＮＤ検索を行うことは不可能である。
【０００８】
そこで、キーワード・フィールドでキーワードを指定せずに、２つのキーワードのＡＮＤであるＡＮＤ検索や、２つのキーワードのＯＲであるＯＲ検索を行うことが望まれている。
【０００９】
そのようなＡＮＤ検索を２−ｐａｓｓの検索フェーズで行う先行技術も知られている（例えば、非特許文献４参照）。しかしながら、非特許文献４では、ＡＮＤ検索しかできない。
【００１０】
一方、ＡＮＤ検索、ＯＲ検索を含む任意のブール関数の検索が行える先行技術も知られている（例えば、非特許文献５参照）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２０１３−１６１１５４号公報（図１５）
【非特許文献】
【００１２】
【非特許文献１】Philippe Golle, Jessica Staddon, Brent R. Waters:“Secure Conjunctive Keyword Search over Encrypted Data” ACNS 2004, pp. 31-45 (2004)
【非特許文献２】Lucas Ballard, Seny Kamara, Fabian Monrose:“Achieving Efficient Conjunctive Keyword Searches over Encrypted Data” ICICS 2005, pp. 414-426 (2005)
【非特許文献３】J. W. Byun, D. H. Lee, and J. Lim:“Efficient conjunctive keyword search on encrypted data storage system” EuroPKI, pp. 184-196 (2006)
【非特許文献４】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
【非特許文献５】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
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、非特許文献５に開示された先行技術では、その検索式が何なのかがサーバにわかってしまう。また、非特許文献５に開示された先行技術では、検索フェーズが２−ｐａｓｓではなく、４−ｐａｓｓであるという問題もある。
【００１４】
したがって本発明の目的は、検索式を秘匿可能な、暗号検索システム、暗号検索方法、および暗号検索プログラムを提供することにある。
【００１５】
本発明の他の目的は、検索フェーズが２−ｐａｓｓである、暗号検索システム、暗号検索方法、および暗号検索プログラムを提供することにある。
【課題を解決するための手段】
【００１６】
本発明の第１の態様に係る暗号検索システムは、ユーザ端末がサーバに第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、ユーザ端末がキーワード検索によってサーバから検索された所望のファイルの集合を取得する暗号検索システムであって、ユーザ端末は、第１の秘密鍵を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワードをランダム化して、それぞれ、第１乃至第Ｎの暗号キーワードを生成するキーワード暗号化部と；第２の秘密鍵を使って第１乃至第Ｍのファイルを暗号化して、それぞれ、第１至第Ｍの暗号ファイルを生成するファイル暗号化部と；第１乃至第Ｎのキーワードを特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、第１乃至第Ｍのファイルを特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワードを含む第ｍのファイルの第ｍ行第ｎ列の原行列要素を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、第１の秘密鍵を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化部と；第１乃至第Ｎの暗号キーワードを列の欄とし、第１乃至第Ｍの暗号ファイルを行の欄とした、Ｍ行Ｎ列のマトリックスの暗号化索引から成る表をサーバへ送信してサーバへ保管させる表送信部と；初期値として０がセットされ、カウンタ値を出力するカウンタと；第１の秘密鍵と第２の秘密鍵とファイル数とカウンタ値とを保持する保持部と；第１乃至第Ｎのキーワードから選択された第１及び第２の検索キーワードを第１の秘密鍵を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワードを生成する検索キーワード暗号化部と；保持部に保持したカウンタ値をカウンタを使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数と第２のブール変数とのブール関数から成る検索式を、第１及び第２の検索キーワードと第１の秘密鍵と新カウンタ値とを使用してGarbled回路により暗号化し、第１乃至第Ｍのファイルにそれぞれ対応した第１乃至第Ｍの暗号化検索式を生成する検索式暗号化部と；第１及び第２の暗号検索キーワードと新カウンタ値と第１乃至第Ｍの暗号化検索式とをサーバへ送って、サーバから第１および第２の検索キーワードが検索式を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得部と；取得した検索された暗号ファイルの集合を第２の秘密鍵を使用して復号して検索された所望のファイルの集合を得るファイル解読部と：を備える。
【発明の効果】
【００１７】
本発明では、ブール関数から成る検索式の真理値表を、第１及び第２の検索キーワードと第１の秘密鍵と新カウンタ値とを使用してGarbled回路により暗号化し、暗号化検索式を生成しているので、検索式を秘匿でき、検索フェーズを２−ｐａｓｓとすることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明が利用する、Yao’s Garbeld Circuitの概略を説明するためのブロック図である。
【図２】ブール関数ｆの暗号文（暗号化検索式）ΓであるGarbled出力値ｐを示す図である。
【図３】ｌｓｂ（ｖ１０）＝１，ｌｓｂ（ｖ２０）＝０の場合のGarbled出力値ｐ（１０）を示す図である。
【図４】さらにｌｓｂ（ｖ１０）＝１，ｌｓｂ（ｖ２１）＝１の場合のGarbled出力値ｐ（１１）を示す図である。
【図５】さらにｌｓｂ（ｖ１１）＝０，ｌｓｂ（ｖ２０）＝０の場合のGarbled出力値ｐ（００）を示す図である。
【図６】さらにｌｓｂ（ｖ１１）＝０，ｌｓｂ（ｖ２１）＝１の場合のGarbled出力値ｐ（０１）を示す図である。
【図７】検索式ｆ（ｘ１，ｘ２）がＯＲである場合の暗号化検索式Γ’を示す図である。
【図８】本発明の実施形態に係る暗号検索システムの格納フェーズの動作を説明するための概略ブロック図である。
【図９】図８に示した暗号検索システムに使用される索引の一具体例を示す図である。
【図１０】図９で表される索引を、第１の暗号鍵ｋ’を使用して暗号化して得られる暗号化索引を含む表Ｔを示す図である。
【図１１】本発明の実施形態に係る暗号検索システムのサーバでの検索フェーズの動作の一例を示す図である。
【図１２】本発明の第１の実施例に係る暗号検索システムの構成を示すブロック図である。
【図１３】図１２に示した暗号検索システムのクライアントにおける格納フェーズのブロック図である。
【図１４】図１３に示したキーワード暗号化部の構成を示すブロック図である。
【図１５】図１３に示したファイル暗号化部の構成を示すブロック図である。
【図１６】図１３に示した索引暗号化部の構成を示すブロック図である。
【図１７】図１６に示した索引用ラベル生成部の構成を示すブロック図である。
【図１８】図１２に示した暗号検索システムのクライアントにおける検索フェーズのブロック図である。
【図１９】図１８に示した検索キーワード暗号化部の構成を示すブロック図である。
【図２０】図１８に示した検索式暗号化部の構成を示すブロック図である。
【図２１】図２０に示したGarbled回路生成部の処理を説明するためのブロック図である。
【図２２】図１２に示した暗号検索システムのサーバにおける検索フェーズのブロック図である。
【図２３】図２２に示したGarbled回路評価部の構成を示すブロック図である。
【図２４】図１２に示した暗号検索システムのクライアントにおける検索フェーズで使用されるファイル解読部の構成を示すブロック図である。
【発明を実施するための形態】
【００１９】
［概要］
以下、本発明の実施形態の概要について説明する。
【００２０】
本発明の実施形態による暗号検索システムは、検索式を秘匿でき、検索フェーズを２−ｐａｓｓとすることができる暗号検索システムである。
【００２１】
本発明の実施形態に係る暗号検索システムは、ユーザ端末がファイルおよびキーワードを暗号化してサーバに保管する暗号検索システムである。ユーザ端末はクライアントとも呼ばれる。
【００２２】
本実施形態に係る暗号検索システムでは、後述するように、ブール関数から成る検索式の真理値表を、第１及び第２の検索キーワードと第１の秘密鍵と新カウンタ値とを使用してGarbled回路により暗号化し、暗号化検索式を生成する。これにより、検索式を秘匿できるだけでなく、検索フェーズを２−ｐａｓｓとすることができる。
【００２３】
尚、暗号検索システムの動作は、ユーザ端末（クライアント）が暗号ファイルおよび暗号化索引をサーバに格納する「格納フェーズ」と、ユーザ端末（クライアント）がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。
【００２４】
本発明では、アンドリュー・チーチー・ヤオが考案し１９８６年にＩＥＥＥの学会で発表したYao’s Garbeld Circuitを利用する。このGarbeld Circuitは、暗号プロトコルを設計する際の強力なフレームワークであり、暗号理論において今の中心的役割を担っている。しかし、暗号検索システムへの応用は自明ではなく、従来知られていない。
【００２５】
次に、Yao’s Garbeld Circuitの概略について説明する。
【００２６】
Ｅ（Ｘ）を入力Ｘ＝（ｘ１，…，ｘｎ）の暗号文とし、Ｅ（ｆ）をブール関数ｆの暗号文とする。この場合、図１に示されるように、（ｆ、Ｘ）を秘密にしたまま、ｆ（Ｘ）を計算することができる。
【００２７】
しかしながら、Ｅ（ｆ）又はＥ（Ｘ）を再利用すると、（ｆ、Ｘ）に関する何らかの情報が洩れてしまう。
【００２８】
そこで、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参照）。
【００２９】
Goldwasser et al.が提案した再利用可能なGarbled Circuitにおいては、ブール関数の暗号文Ｅ（ｆ）を固定して、Garbled Circuitを再利用している。すなわち、入力Ｘ１，Ｘ２，・・・に対して、ｆ（Ｘ１），ｆ（Ｘ２），・・・を計算している。
【００３０】
これに対して本発明では、入力Ｘの暗号文Ｅ（Ｘ）を固定して、Garbled Circuitを再利用する。すなわち、ブール関数ｆ１，ｆ２，・・・に対し、ｆ１（Ｘ），ｆ２（Ｘ），・・・を計算する。本発明では、このようなGarbled Circuitを考え、暗号検索システムに利用した。
【００３１】
次に、本発明の実施形態の理解を容易にするために、検索式も秘匿可能な暗号検索システムの概略について説明する。
【００３２】
本発明に係るGarbling schemeには、次に述べる３つのアルゴリズムがある。
【００３３】
GenLabは、第１および第２のブール変数ｘ１，ｘ２のラベルベクトルＶを計算するアルゴリズムである。
【００３４】
GenGC(counter, f, V)は、ブール関数ｆの暗号文Γを計算するアルゴリズムである。尚、counterは初期値が０のカウンタのカウンタ値であって、１ずつ増加する。
【００３５】
EvalGCは、ブール関数の検索式ｆ（ｘ１、ｘ２）を計算するアルゴリズムである。
【００３６】
最初に、GenLabのアルゴリズムについて説明する。
【００３７】
ｉ＝１，２に対して、最下位ビットｌｓｂ（ｖｉ０）、ｌｓｂ（ｖｉ１）が異なる（ｌｓｂ（ｖｉ０）≠ｌｓｂ（ｖｉ１）となる)、１２８ビットの乱数（ｖｉ０，ｖｉ１）を選ぶ。
【００３８】
そして、ラベルベクトルＶ＝（（ｖ１０，ｖ１１），（ｖ２０，ｖ２１））を出力する。ここで、ｖ１０は第１のブール変数ｘ１＝０のときのラベルであり、ｖ１１は第１のブール変数ｘ１＝１のときのラベルであり、ｖ２０は第２のブール変数ｘ２＝０のときのラベルであり、ｖ２１はブール変数ｘ２＝１のときのラベルである。例えば、ラベルベクトルＶ＝（（ｖ１０，ｖ１１），（ｖ２０，ｖ２１））は次のように表される。 
ｖ１０＝（．．．１），  ｖ１１＝（．．．０）
ｖ２０＝（．．．０），  ｖ２１＝（．．．１）
【００３９】
次に、GenGC(counter, f, V)のアルゴリズムについて説明する。
【００４０】
図２は、ブール関数ｆの暗号文（暗号化検索式）ΓであるGarbled出力値ｐを示す図である。ここで、Γ＝［ｐ（００），ｐ（０１），ｐ（１０），ｐ（１１）］である。
【００４１】
Ｈを出力が１ビットのハッシュ関数とする。
【００４２】
第１及び第２のブール変数（ｘ１，ｘ２）の４つの組み合わせ（０，０），（１，０）、（１，０），（１，１）について、ラベルｖ１ｘ１、ｖ２ｘ２の最下位ビットｌｓｂを、それぞれ、下記の数式で表されるように、第１及び第２のGarbled変数ａ１，ａ２とする。 
ａ１＝ｌｓｂ（ｖ１ｘ１），  ａ２＝ｌｓｂ（ｖ２ｘ２）
【００４３】
そして、次の式に従って、Garbled出力値ｐ（ａ１ａ２）を計算する。 
ｐ（ａ１ａ２）＝Ｈ（counter，ｖ１ｘ１，ｖ２ｘ２）＋ｆ（ｘ１，ｘ２）
ここで、演算子“＋”は排他的論理和である。
【００４４】
図３は、ｌｓｂ（ｖ１０）＝１，ｌｓｂ（ｖ２０）＝０の場合のGarbled出力値ｐ（１０）を示す図である。
【００４５】
すなわち、（ｘ１，ｘ２）＝（０，０）について、ａ１＝ｌｓｂ（ｖ１０）＝１，ａ２＝ｌｓｂ（ｖ２０）＝０であったとする。この場合、Garbled出力値ｐ（１０）は、次式で表される。 
ｐ（１０）＝Ｈ（counter，ｖ１０，ｖ２０）＋ｆ（０，０）
【００４６】
図４は、さらにｌｓｂ（ｖ１０）＝１，ｌｓｂ（ｖ２１）＝１の場合のGarbled出力値ｐ（１１）を示す図である。
【００４７】
すなわち、（ｘ１，ｘ２）＝（０，１）について、ａ１＝ｌｓｂ（ｖ１０）＝１，ａ２＝ｌｓｂ（ｖ２１）＝１であったとする。この場合、Garbled出力値ｐ（１１）は、次式で表される。 
ｐ（１１）＝Ｈ（counter，ｖ１０，ｖ２１）＋ｆ（０，１）
【００４８】
図５は、さらにｌｓｂ（ｖ１１）＝０，ｌｓｂ（ｖ２０）＝０の場合のGarbled出力値ｐ（００）を示す図である。
【００４９】
すなわち、（ｘ１，ｘ２）＝（１，０）について、ａ１＝ｌｓｂ（ｖ１１）＝０，ａ２＝ｌｓｂ（ｖ２０）＝０であったとする。この場合、Garbled出力値ｐ（００）は、次式で表される。 
ｐ（００）＝Ｈ（counter，ｖ１１，ｖ２０）＋ｆ（１，０）
【００５０】
図６は、さらにｌｓｂ（ｖ１１）＝０，ｌｓｂ（ｖ２１）＝１の場合のGarbled出力値ｐ（０１）を示す図である。
【００５１】
すなわち、（ｘ１，ｘ２）＝（１，１）について、ａ１＝ｌｓｂ（ｖ１１）＝０，ａ２＝ｌｓｂ（ｖ２１）＝１であったとする。この場合、Garbled出力値ｐ（０１）は、次式で表される。 
ｐ（０１）＝Ｈ（counter，ｖ１１，ｖ２１）＋ｆ（１，１）
【００５２】
次に、EvalGCのアルゴリズムについて説明する。
【００５３】
図６に示されたブール関数ｆの暗号文（暗号化検索式）Γは、ユーザ端末（クライアント）からサーバへ送られる。
【００５４】
ラベルｖ１、ｖ２の最下位ビットｌｓｂを、それぞれ、下記の数式で表される、第１及び第２のGarbled変数α、βとする。 
α＝ｌｓｂ（ｖ１），  β＝ｌｓｂ（ｖ２）
【００５５】
そして、次式に従って、評価値Ｚを計算する。 
Ｚ＝ｐ（αβ）−Ｈ（counter，ｖ１，ｖ２）
ここで、演算子“−”は排他的論理和である。したがって、演算子“−”の代わりに演算子“＋”を使用してもよい。
【００５６】
ここで、ラベル（ｖ１，ｖ２）が次式であるとする。 
（ｖ１，ｖ２）＝（（．．．０），（．．．１））
【００５７】
このとき、第１および第２のGarbled変数α、βは、それぞれ、次式で表される。 
α＝ｌｓｂ（ｖ１）＝０，  β＝ｌｓｂ（ｖ２）＝１
【００５８】
したがって、評価値Ｚは、図６に示される暗号化検索式Γから、次式で表される。 
Ｚ＝ｐ（０１）−Ｈ（counter，ｖ１，ｖ２）＝ｆ（１，１）
検索式ｆ（ｘ１，ｘ２）がＡＮＤである場合、ｆ（１，１）は１に等しいので、
Ｚ＝１
となる。
【００５９】
次に、検索式ｆ（ｘ１，ｘ２）がＯＲであって、検索式ｆ（ｘ１，ｘ２）＝ｘ１ＯＲｘ２で表される、ＯＲ検索を行うとする。
【００６０】
この場合、次式で表されるように、まずカウンタ値counterを１だけインクリメントして、新カウンタ値counterを使用する。 
counter＝counter＋１
【００６１】
そして、図７に示されるような、暗号化検索式Γ’をクライアントからサーバへ送信すればよい。
【００６２】
図７において、ラベルベクトルＶを規定する４つのラベルｖ１０，ｖ１１，ｖ２０，ｖ２１は、固定であって変化しないので、再利用することが可能であることがわかる。換言すれば、ラベルベクトルＶについては、クライアントにおいて第１の秘密鍵ｋ’を使用して一度暗号化して、サーバへ送ればよい。
【００６３】
これにより、検索式を秘匿にしたままで、検索フェーズを２−ｐａｓｓとすることができる。
【００６４】
［実施形態］
次に、本発明の実施形態に係る暗号検索システムについて説明する。
【００６５】
前述したように、暗号検索システムの動作は、ユーザ端末（クライアント）が暗号ファイルをサーバに格納する「格納フェーズ」と、ユーザ端末（クライアント）がサーバから所望のファイルを検索する「検索フェーズ」と、に分けられる。
【００６６】
最初に、「格納フェーズ」の動作について説明する。
【００６７】
図８は、本発明の実施形態に係る暗号検索システムの格納フェーズの動作を説明するための概略ブロック図である。
【００６８】
図８に示されるように、クライアント１００は、サーバ２００へ、第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルＣ１〜ＣＭと暗号化索引Ｅ（索引）とを送信する。
【００６９】
ファイルの集合をＤ＝{Ｄ１，・・・，ＤＭ}とする。すなわち、ファイルの集合Ｄが第１乃至第ＭのファイルＤ１〜ＤＭから成るとする。
【００７０】
キーワードの集合をＷ＝{ｗ１，・・・，ｗＮ}とする。すなわち、キーワードの集合Ｗが第１乃至第Ｎのキーワードｗ１〜ｗＮから成るとする。
【００７１】
第１乃至第Ｎのキーワードｗ１〜ｗＮを特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、第１乃至第ＭのファイルＤ１〜ＤＭを特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行とする第ｍ行第ｎ列の原行列要素ｅｍｎを含む、Ｍ行Ｎ列のマトリックスから成る索引を生成する。
【００７２】
ここで、もし第ｍのファイルＤｍが第ｎのキーワードｗｎを含むなら、ｅｍｎ＝１とし、そうでなければ、ｅｍｎ＝０とする。
【００７３】
例えば、ファイルの集合Ｄが第１および第２のファイルＤ１およびＤ２の２つから成り、キーワードの集合Ｗが第１乃至第３のキーワードｗ１，ｗ２、およびｗ３の３つから成っているとする。また、第１のキーワードｗ１が「茨城」で、第２のキーワードｗ２が「日立」で、第３のキーワードｗ３が「大学」であるとする。そして、第１のファイルＤ１が「茨城」の第１のキーワードｗ１と「日立」の第２のキーワードｗ２とを含み、第２のファイルＤ２が「茨城」の第１のキーワードｗ１と「大学」の第３のキーワードｗ３とを含むとする。
【００７４】
この場合の索引は、図９のように表される。
【００７５】
本実施形態では、索引として、キーワード番号ｎを列とし、ファイル番号ｍを行とした、Ｍ行Ｎ列のマトリックスから成る索引を使用しているが、列と行とを入れ替えても構わない。すなわち、索引は、キーワード番号ｎを行とし、ファイル番号ｍを列とした、Ｎ行Ｍ列のマトリックスから成る索引から成っていてもよい。
【００７６】
Ｅを共通鍵暗号の暗号化アルゴリズムとし、ｋをその鍵（本例では、「第２の秘密鍵」と呼ぶ）とする。
【００７７】
また、ＰＲＦを出力が１２８ビットの擬似ランダム関数とし、ｋ’をその鍵（本例では、「第１の秘密鍵」と呼ぶ）とする。
【００７８】
クライアント１００は、ファイル番号ｍ＝１，・・・，Ｍに対して、第ｍのファイルＤｍを第２の秘密鍵ｋを使って所定の暗号化アルゴリズムＥｎｃにより暗号化して、次式で表わされるような、第ｍの暗号ファイルＣｍを計算する。 
Ｃｍ＝Ｅｎｃｋ（Ｄｍ）
【００７９】
また、クライアント１００は、キーワード番号ｎ＝１，・・・，Ｎに対して、第ｎのキーワードｗｎを第１の秘密鍵ｋ’を使用してランダム化して、次式で表されるような、第ｎの暗号キーワードｋｗｎを計算する。 
ｋｗｎ＝ＰＲＦｋ’（ｗｎ）
【００８０】
そして、クライアント１００は、第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）と、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）とを、サーバ２００へ送信してサーバ２００に格納する。
【００８１】
次に、クライアント１００は、上記Ｍ行Ｎ列のマトリックスから成る索引を、第１の秘密鍵ｋ’を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素ｖｍｎの各々が所定ビット数（本例では、１２８ビット）から成るＭ行Ｎ列のマトリックスの暗号化索引Ｅ（索引）を生成する。
【００８２】
詳述すると、ファイル番号ｍ＝１，・・・，Ｍおよびキーワード番号ｎ＝１，・・・，Ｎに対して、まず、クライアント１００は、第１の秘密鍵ｋ’を使用して、上記擬似ランダム関数ＲＲＦにより、それぞれ、第ｍ行第ｎ列の行列要素を０および１とした上付き文字を持つ、第１の暗号化索引候補ｖｍｎ０および第２の暗号化索引候補ｖｍｎ１を、次式に従って計算する。 
ｖｍｎ０＝ＰＲＦｋ’（ｍ，ｗｎ，０）
ｖｍｎ１＝ＰＲＦｋ’（ｍ，ｗｎ，１）
【００８３】
もし、第１の暗号化索引候補ｖｍｎ０の最下位ビットｌｓｂ（ｖｍｎ０）と、第２の暗号化索引候補ｖｍｎ１の最下位ビットｌｓｂ（ｖｍｎ１）とが等しければ、すなわち、
ｌｓｂ（ｖｍｎ０）＝ｌｓｂ（ｖｍｎ１）  
であれば、クライアント１００は、第２の暗号化索引候補ｖｍｎ１の最下位ビットｌｓｂを反転したものを、第２の暗号化索引候補ｖｍｎ１とする。
【００８４】
そして、クライアント１００は、第ｍ行第ｎ列の暗号化行列要素ｖｍｎを、次式から求める。 
ｖｍｎ＝ｖｍｎｅｍｎ
【００８５】
すなわち、クライアント１００は、第１及び第２の暗号化索引候補ｖｍｎ０およびｖｍｎ１から、上付き文字が第ｍ行第ｎ列の原行列要素ｅｍｎに等しい方を、第ｍ行第ｎ列の暗号化行列要素ｖｍｎとして選択して出力する。
【００８６】
ファイル番号ｍ＝１，・・・，Ｍに対して、クライアント１００は、ベクトルＹｍを次式とおく。 
Ｙｍ＝（ｖｍ１，・・・，ｖｍＮ）
【００８７】
そして、クライアント１００は、Ｍ行Ｎ列のマトリックスの暗号化索引（Ｙ１，・・・，ＹＭ）をサーバ２００に送信して、サーバ２００に格納する。
【００８８】
以上を纏めると、クライアント１００は、第１乃至第Ｎの暗号キーワードｋｗ１〜ｋｗＮを列の欄とし、第１乃至第Ｍの暗号ファイルＣ１〜ＣＮを行の欄とした、上記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表Ｔを、サーバ２００へ送信してサーバ２００へ保管させる。
【００８９】
クライアント１００は、カウンタ値counterを、初期値を０にしてカウンタ（後述する）にセットする。
【００９０】
図１０は、図９で表される索引を、第１の暗号鍵ｋ’を使用して暗号化して得られる暗号化索引を含む表Ｔを示す図である。図１０において、（Ａ）は図９に示した索引を示し、（Ｂ）はその索引を第１の暗号鍵ｋ’を使用して暗号化して得られる暗号化索引を含む表Ｔを示す。
【００９１】
以上で、本実施形態に係る暗号検索システムの格納フェーズの動作の説明を終える。
【００９２】
次に、本実施形態に係る暗号検索システムの検索フェーズの動作について説明する。
【００９３】
クライアント１００は、第１乃至第Ｎのキーワードｗ１〜ｗＮの中から、第１及び第２の検索キーワード（ｗａ，ｗｂ）を選択すると共に、各々が０又は１の値をとる第１のブール変数ｘ１と第２のブール変数ｘ２とのブール関数から成る検索式ｆ（ｘ１，ｘ２）を選択する。検索式ｆ（ｘ１，ｘ２）は、たとえば、ＡＮＤ又はＯＲから成る。
【００９４】
次に、クライアント１００は、次式に従って、カウンタ値counterを１だけインクリメントとして、新カウンタ値conterを求める。 
counter＝counter＋１
【００９５】
引き続いて、クライアント１００は、第１及び第２の検索キーワード（ｗａ，ｗｂ）を第１の秘密鍵ｋ’を使って上記擬似ランダム関数ＰＲＦによりランダム化して、それぞれ、次式で表される、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を計算する。
ｋｗａ＝ＰＲＦｋ’（ｗａ）
ｋｗｂ＝ＰＲＦｋ’（ｗｂ）
【００９６】
ファイル番号ｍ＝１，・・・，Ｍに対して、クライアント１００は、上述した格納フェーズと同様にして、次式で表される第ｍのラベルベクトルＶを計算する。 
Ｖ＝（（ｖｍａ０，ｖｍａ１），（ｖｍｂ０，ｖｍｂ１））
【００９７】
そして、クライアント１００は、検索式ｆ（ｘ１，ｘ２）を、新カウンタ値counterと第ｍのラベルベクトルＶとを使用してGarbeld回路より次式に従って暗号化して、第ｍのファイルＤｍに対応する第ｍの暗号化検索式Γｍを計算する。 
Γｍ＝GenGC（counter，ｆ，Ｖ）
【００９８】
換言すると、検索式ｆ（ｘ１，ｘ２）の第１及び第２のブール変数（ｘ１，ｘ２）の４つの組み合わせ（０，０），（０，１），（１，０），（１，１）について、ラベルｖａｘ１及びｖａｘ２の最下位ビットをそれぞれ第１及び第２のGarbled変数（ａ１，ａ２）としたとき、クライアント１００は、次式で表されるような、新カウンタ値counterとラベルｖａｘ１及びｖａｘ２との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖａｘ１，ｖａｘ２）の出力値と検索式ｆ（ｘ１，ｘ２）との排他的論理和を計算する。 
ｐ（ａ１ａ２）＝Ｈ（counter，ｖａｘ１，ｖａｘ２）＋ｆ（ｘ１，ｘ２）ｍｏｄ２
【００９９】
ここで、第ｍの暗号化検索式Γｍは、次式で表される。 
Γｍ＝［ｐ（００），ｐ（０１），ｐ（１０），ｐ（１１）］  
【０１００】
そして、クライアント１００は、新カウンタ値counterと第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを、サーバ２００に送る。
【０１０１】
ファイル番号ｍ＝１，・・・，Ｍに対して、サーバ２００は、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を利用して、上記表Ｔから第１及び第２の探索した暗号化行列要素ｖｍａ，ｖｍｂを探す。
【０１０２】
そして、サーバ２００は、新カウンタ値counterを使用して、第ｍの暗号化検索式Γｍと第１及び第２の探索した暗号化行列要素ｖｍａ，ｖｍｂとに基づいて、次式で表される第ｍの評価値Ｚｍを計算する。 
Ｚｍ＝EvalGC（counter，Γｍ，（ｖｍａ，ｖｍｂ））
【０１０３】
換言すると、第１及び第２の探索した暗号化行列要素ｖｍａ，ｖｍｂの最下位ビットｌｓｂを、次式で表されるように、それぞれ、第１及び第２の探索したGarbled変数αおよびβとしたとき、
α＝ｌｓｂ（ｖｍａ）
β＝ｌｓｂ（ｖｍｂ）
サーバ２００は、次式で表されるように、第１の探索したGarbeld変数αと第２の探索したGarbled変数βとを一対の変数値として持つGarbeld出力値ｐ（αβ）と、新カウンタ値counterと第１及び第２の探索した暗号化行列要素ｖｍａ，ｖｍｂとの組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖｍａ，ｖｍｂ）の出力値との排他的論理和を、第ｍの評価値Ｚｍとして計算する。 
Ｚｍ＝ｐ（αβ）＋Ｈ（counter，ｖｍａ，ｖｍｂ）ｍｏｄ２
【０１０４】
尚、第ｍの評価値Ｚｍは、次式で表すこともできる。
Ｚｍ＝ｐ（αβ）−Ｈ（counter，ｖｍａ，ｖｍｂ）ｍｏｄ２
【０１０５】
そして、サーバ２００は、第ｍの評価値Ｚｍが１となる全ての第ｍの暗号ファイルＣｍをクライアント１００へ返す。
【０１０６】
図１１は、サーバ２００での検索フェーズの動作の一例を示す図である。
【０１０７】
図１１に示されるように、サーバ２００は、図１０（Ｂ）で示される表Ｔを保管している。図１１の例では、第１及び第２の暗号検索キーワードｋｗａ，ｋｗｂが、それぞれ、第１及び第２の暗号キーワードｋｗ１，ｋｗ２に等しい場合を示している。
【０１０８】
したがって、クライアント１００からサーバ２００へは、新カウンタ値counterと第１及び第２の暗号キーワードｋｗ１，ｋｗ２と第１及び第２の暗号化検索式Γ１，Γ２とが送られてくる。
【０１０９】
サーバ２００は、次式に従って、第１及び第２の評価値Ｚ１，Ｚ２を計算する。 
Ｚ１＝EvalGC（counter，Γ１，（ｖ１１，ｖ１２））＝ｆ（１，１）
Ｚ２＝EvalGC（counter，Γ２，（ｖ２１，ｖ２２））＝ｆ（１，０）
【０１１０】
ここで、検索式ｆ（ｘ１，ｘ２）がＡＮＤであるとすると、ｆ（１，１）＝１であるので、サーバ２００は、検索された暗号ファイルの集合として第１の暗号ファイルＣ１をクライアント１００へ返す。
【０１１１】
クライアント１００では、第１の暗号ファイルＣ１を第２の暗号鍵ｋを使って所定の復号アルゴリズムＤｅｃにより復号して、次式で表わされるような、第１のファイルＤ１を計算する。 
Ｄ１＝Ｄｅｃｋ（Ｃ１）
【０１１２】
以上で、本実施形態に係る暗号検索システムの検索フェーズの動作の説明を終える。
【０１１３】
以上の説明から明らかなように、ブール関数から成る検索式ｆ（ｘ１，ｘ２）の真理値表［ｆ（０，０），・・・，ｆ（１，１）］を、第１及び第２の検索キーワードｗａ，ｗｂと第１の秘密鍵ｋ’と新カウンタ値counterとを使用してGarbled回路により暗号化し、第１乃至第ＭのファイルＤ１〜ＤＭに対応する第１乃至第Ｍの暗号化検索式Γ１〜ΓＭを生成しているので、検索式を秘匿でき、検索フェーズを２−ｐａｓｓとすることができる。
【実施例１】
【０１１４】
図１２を参照して、本発明の第１の実施例に係る暗号検索システムについて説明する。図１２は、本発明の第１の実施例に係る暗号検索システムの構成を示すブロック図である。図示の暗号検索システムは、クライアント１００とサーバ２００とから構成される。クライアント１００は、ユーザ端末とも呼ばれる。
【０１１５】
暗号検索システムは、クライアント（ユーザ端末）１００がサーバ２００に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、クライアント（ユーザ端末）１００がキーワード検索によってサーバ２００から検索された所望のファイルの集合を取得するシステムである。
【０１１６】
クライアント１００は、キーワード暗号化部１１０と、ファイル暗号化部１２０と、索引暗号化部１３０と、表送信部１４０と、カウンタ１４５と、保持部１５０と、検索キーワード暗号化部１６０と、検索式暗号化部１７０と、暗号ファイル取得部１８０と、ファイル解読部１９０と、から構成されている。
【０１１７】
カウンタ１４５は、初期値として０がセットされ、後述するように１ずつ増加して、カウンタ値counterを出力する。
【０１１８】
保持部１５０は、第１の秘密鍵ｋ’と、第２の秘密鍵ｋと、ファイル数Ｍと、カウンタ値counterとを保持する。第１の秘密鍵ｋ’は、キーワードを暗号化するために使用される鍵である。第２の秘密鍵ｋは、ファイルを暗号化したり、暗号ファイルを復号するために使用される鍵である。
【０１１９】
キーワード暗号化部１１０は、第１の秘密鍵ｋ’を使って後述するように第１乃至第Ｎ（Ｎは２以上の整数）のキーワードｗ１〜ｗＮをランダム化して、それぞれ、第１乃至第Ｎの暗号キーワードｋｗ１〜ｋｗＮを生成する。
【０１２０】
ファイル暗号化部１２０は、第２の秘密鍵ｋを使って後述するように第１乃至第ＭのファイルＤ１〜ＤＭを暗号化して、それぞれ、第１乃至第Ｍの暗号ファイルＣ１〜ＣＭを生成する。
【０１２１】
索引暗号化部１３０は、後述する索引を第１の秘密鍵ｋ’を使って暗号化して、後述するようなＭ行Ｎ列のマトリックスの暗号化索引を生成する。
【０１２２】
表送信部１４０は、第１乃至第Ｎの暗号キーワードｋｗ１〜ｋｗＮを列の欄とし、第１乃至第Ｍの暗号ファイルＣ１〜ＣＭを行の欄とした、Ｍ行Ｎ列のマトリックスの暗号化索引からなる表Ｔをサーバ２００へ送信してサーバ２００へ保管させる。
【０１２３】
検索キーワード暗号化部１６０は、第１乃至第Ｎのキーワードｗ１〜ｗＮから選択された第１及び第２の検索キーワードｗａ，ｗｂを第１の秘密鍵ｋ’を使って後述するようにランダム化して、それぞれ、第１及び第２の暗号検索キーワードｋｗａ，ｋｗｂを生成する。
【０１２４】
検索式暗号化部１７０は、保持部１５０に保持したカウンタ値counterをカウンタ１４５を使用して１だけ増加させて新カウンタ値counterを生成させ、その新カウンタ値counterを受ける。この新カウンタ値counterは、再び、保持部１５０に保持される。
【０１２５】
検索式暗号化部１７０は、検索式ｆ（ｘ１，ｘ２）と第２及び第２の検索キーワードｗａ，ｗｂと第１の秘密鍵ｋ’とを受ける。検索式ｆ（ｘ１，ｘ２）は、各々が０又は１の値をとる第１のブール変数ｘ１と第２のブール変数ｘ２とのブール関数から成る。したがって、検索式ｆ（ｘ１，ｘ２）は、例えば、ＡＮＤやＯＲから成る。
【０１２６】
検索式暗号部１７０は、検索式ｆ（ｘ１，ｘ２）の真理値表［ｆ（０，０），・・・，ｆ（１，１）］を、第１及び第２の検索キーワードｗａ，ｗｂと第１の秘密鍵ｋ’と新カウンタ値counterとを使用してGarbled回路により後述するように暗号化し、第１乃至第ＭのファイルＤ１〜ＤＭにそれぞれ対応する第１乃至第Ｍの暗号化検索式Γ１，・・・，ΓＭを生成する。
【０１２７】
暗号ファイル取得部１８０は、第１及び第２の暗号検索キーワードｋｗａ，ｋｗｂと新カウンタ値counterと第１乃至第Ｍの暗号化検索式Γ１〜ΓＭとをサーバ２００へ送って、サーバ２００から第１及び第２の検索キーワードｗａ，ｗｂが検索式ｆ（ｘ１，ｘ２）を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する。
【０１２８】
ファイル解読部１９０は、取得した検索された暗号ファイルの集合を第２の秘密鍵ｋを使用して後述のように復号して、上記検索された所望のファイルの集合を得る。
【０１２９】
一方、サーバ２００は、記憶領域２１０と、暗号検索部２２０と、から構成されている。
【０１３０】
記憶領域２１０は、クライアント１００から送られてくる暗号ファイルの集合および上記表Ｔを保持する。
【０１３１】
暗号検索部２２０は、クライアント１００から受信した、第１及び第２の暗号検索キーワードｋｗａ，ｋｗｂと新カウンタ値counterと第１乃至第Ｍの暗号化検索式Γ１〜ΓＭとに基づいて、表Ｔを参照して後述のように暗号ファイルの集合を検索し、上記検索された暗号ファイルの集合を生成する。
【０１３２】
前述したように、暗号検索システムの動作は、ユーザ端末（クライアント）１００が暗号ファイルおよび暗号化索引をサーバ２００に格納する「格納フェーズ」と、ユーザ端末（クライアント）１００がサーバ２００から所望のファイルを検索する「検索フェーズ」と、に分けられる。
【０１３３】
最初に、図１３乃至図１７を参照して、暗号検索システムの「格納フェーズ」の動作について説明する。
【０１３４】
図１３は、第１の実施例による暗号検索システムのクライアント１００における格納フェーズのブロック図である。
【０１３５】
キーワード暗号化部１１０には、キーワードの集合Ｗとして、第１乃至第Ｎのキーワード{ｗ１，・・・，ｗＮ}が供給される。また、キーワード暗号化部１１０には、保持部１５０（図１２参照）から第１の秘密鍵ｋ’も供給される。キーワード暗号化部１１０は、第ｎ（１≦ｎ≦Ｎ）のキーワードｗｎを第１の秘密鍵ｋ’を使って後述のようにランダム化して、第ｎの暗号キーワードｋｗｎを生成する。ｎはキーワード番号である。ここで、第ｎのキーワードｗｎはどのように長くても構わない。一方、第ｎの暗号キーワードｋｗｎは所定のビット長を持つ。本例では、第ｎの暗号キーワードｋｗｎは１２８ビットのビット長を持つ。
【０１３６】
ファイル暗号化部１２０には、ファイルの集合Ｄとして、第１乃至第Ｍのファイル{Ｄ１，・・・，ＤＭ}が供給される。また、ファイル暗号化部１２０には、保持部１５０（図１２参照）から第２の秘密鍵ｋも供給される。ファイル暗号化部１２０は、第ｍ（１≦ｍ≦Ｍ）のファイルＤｍを第２の秘密鍵ｋを使って後述のように暗号化して、第ｍの暗号ファイルＣｍを生成する。ｍはファイル番号である。
【０１３７】
索引暗号化部１３０には、索引（後述する）とファイル数Ｍとキーワードの集合Ｗとが供給される。また、索引暗号化部１３０には、保持部１５０（図１２参照）から第１の秘密鍵ｋ’も供給される。
【０１３８】
索引は、第１乃至第Ｎのキーワードｗ１〜ｗＮを特定するキーワード番号ｎを列とし、第１乃至第ＭのファイルＤ１〜ＤＭを特定するファイル番号ｍを行とした、第ｍ行第ｎ列の原行列要素ｅｍｎを含む、Ｍ行Ｎ列のマトリックスから成る。
【０１３９】
第ｍのファイルＤｍが第ｎのキーワードｗｎを含むなら、第ｍ行第ｎ列の原行列要素ｅｍｎは１に等しい（ｅｍｎ＝１）。さもなければ、ｅｍｎ＝０である。
【０１４０】
索引暗号化部１３０は、Ｍ行Ｎ列のマトリックスから成る索引を、第１の秘密鍵ｋ’を使用して後述のように暗号化して、第ｍ行第ｎ列の暗号化行列要素ｖｍｎの各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する。図示の例では、第ｍ行第ｎ列の暗号化行列要素ｖｍｎは、１２８ビットの乱数からなる。
【０１４１】
表送信部１４０は、図１３に示されるように、第１乃至第Ｎの暗号キーワードｋｗ１〜ｋｗＮを列の欄とし、第１乃至第Ｍの暗号ファイルＣ１〜ＣＭを行の欄とした、Ｍ行Ｎ列のマトリックスの暗号化索引から成る表Ｔを、サーバ２００へ送信してサーバ２００の記憶領域２１０（図１２参照）に保管させる。
【０１４２】
上述したように、カウンタ１４５（図１２参照）には初期値として０のカウンタ値counterがセットされている。
【０１４３】
クライアントのメモリである保持部１５０（図１２）は、第１の秘密鍵ｋ’と第２の秘密鍵ｋとファイル数Ｍとカウンタ値counterとを保持している。
【０１４４】
図１４は、図１３に示したキーワード暗号化部１１０の構成を示すブロック図である。
【０１４５】
キーワード暗号化部１１０は、擬似ランダム関数発生器１１２から成る。擬似ランダム関数発生器１１２は、第ｎのキーワードｗｎと第１の秘密鍵ｋ’とから、所定の擬似ランダム関数ＰＲＦを使用して、第ｎの暗号キーワードｋｗｎを生成する。上述したように、本例では、第ｎの暗号キーワードｋｗｎは、１２８ビットのビット長を持つ。
【０１４６】
図１５は、図１３に示したファイル暗号化部１２０の構成を示すブロック図である。
【０１４７】
ファイル暗号化部１２０は、所定の暗号化アルゴリズムＥｎｃに従って暗号化を行なう暗号化器１２２から成る。暗号化器１２２は、第ｍのファイルＤｍを第２の秘密鍵ｋを使って所定の暗号化アルゴリズムＥｎｃにより第ｍの暗号ファイルＣｍに暗号化する。
【０１４８】
図１６は、図１３に示した索引暗号化部１３０の構成を示すブロック図である。
【０１４９】
索引暗号化部１３０は、索引用ラベル生成部１３２と、選択部１３４とから成る。
【０１５０】
索引用ラベル生成部１３２は、ファイル番号ｍと第ｎのキーワードｗｎとの組（ｍ、ｗｎ）に対して、第１の秘密鍵ｋ’を使用して第１及び第２の暗号化索引候補ｖｍｎ０、ｖｍｎ１を生成する。第１及び第２の暗号化索引候補ｖｍｎ０、ｖｍｎ１は、それぞれ、第ｍ行第ｎ列の行列要素を０および１とした上付き文字を持ち、第ｍ行第ｎ列の暗号化行列要素用の最下位ビットが異なる候補から成る。
【０１５１】
選択部１３４は、生成された第１及び第２の暗号化索引候補ｖｍｎ０、ｖｍｎ１から、上付き文字が第ｍ行第ｎ列の原行列要素ｅｍｎに等しい方を第ｍ行第ｎ列の暗号化行列要素ｖｍｎとして選択し出力する。
【０１５２】
図１７は、図１６に示した索引用ラベル生成部１３２の構成を示すブロック図である。
【０１５３】
索引用ラベル生成部１３２は、第１の候補生成部１３２２と、第２の候補生成部１３２４と、反転部１３２６とから成る。
【０１５４】
第１の候補生成部１３２２は、ファイル番号ｍと第ｎのキーワードｗｎと０との組（ｍ，ｗｎ，０）に対して、第１の秘密鍵ｋ’を使用して、所定の擬似ランダム関数ＰＲＦにより第１の暗号化索引候補ｖｍｎ０を生成する。
【０１５５】
同様に、第２の候補生成部１３２４は、ファイル番号ｍと第ｎのキーワードｗｎと１との組（ｍ，ｗｎ，１）に対して、第１の秘密鍵ｋ’を使用して、所定の擬似ランダム関数ＰＲＦにより第２の暗号化索引候補ｖｍｎ１を生成する。
【０１５６】
反転部１３２６は、生成した第１の暗号化索引候補ｖｍｎ０の最下位ビットｌｓｂ（ｖｍｎ０）と生成した第２の暗号化索引候補ｖｍｎ１の最下位ビットｌｓｂ（ｖｍｎ１）とが等しい（ｌｓｂ（ｖｍｎ０）＝ｌｓｂ（ｖｍｎ１））場合、第２の暗号化索引候補ｖｍｎ１の最下位ビットｌｓｂ（ｖｍｎ１）を、次式に従って強制的に反転して、第２の暗号化索引候補ｖｍｎ１を得る。 
ｖｍｎ１：＝ｖｍｎ１＋（０・・・・０１）
ここで、演算子“＋”は排他的論理和である。
【０１５７】
以上が、暗号検索システムの「格納フェーズ」の動作の説明である。
【０１５８】
次に、図１８乃至図２４を参照して、暗号検索システムの「検索フェーズ」の動作について説明する。
【０１５９】
図１８は、第１の実施例による暗号検索システムのクライアント１００における検索フェーズのブロック図である。
【０１６０】
検索キーワード暗号化部１６０には、第１乃至第Ｎのキーワードｗ１〜ｗＮから選択された第１及び第２の検索キーワードｗａ、ｗｂが供給される。また、検索キーワード暗号化部１６０には、保持部１５０（図１２）から第１の秘密鍵ｋ’も供給される。検索キーワード暗号化部１６０は、第１及び第２の検索キーワードｗａ、ｗｂを第１の秘密鍵ｋ’を使って後述のようにランダム化して、それぞれ、第１及び第２の暗号検索キーワードｋｗａ、ｋｗｂを生成する。
【０１６１】
カウンタ１４５（図１２）は、保持部１５０（図１２）に保持したカウンタ値counterを１だけ増加して、新カウンタ値counterを生成する。この新カウンタ値counterは、再び、クライアントの保持部１５０に保持される。
【０１６２】
検索式暗号化部１７０には、この新カウンタ値counterと検索式ｆ（ｘ１，ｘ２）と第１及び第２の検索キーワードｗａ、ｗｂとが供給される。また、検索式暗号化部１７０には、ファイル数Ｍおよび第１の秘密鍵ｋ’も供給される。
【０１６３】
検索式ｆ（ｘ１，ｘ２）は、上述したように、各々が０又は１の値をとる第１のブール変数ｘ１と第２のブール変数ｘ２とのブール関数から成る。検索式ｆ（ｘ１，ｘ２）は、例えば、ＡＮＤやＯＲから成る。
【０１６４】
検索式暗号化部１７０は、検索式ｆ（ｘ１，ｘ２）の真理値表［ｆ（０，０），・・・，ｆ（１，１）］を、第１及び第２の検索キーワードｗａ、ｗｂと第１の秘密鍵ｋ’と新カウンタ値counterとを使用してGarbled回路により後述のように暗号化し、第１乃至第ＭのファイルＤ１〜ＤＭにそれぞれ対応する第１乃至第Ｍの暗号化検索式Γ１〜ΓＭを生成する。
【０１６５】
図１９は、図１８に示した検索キーワード暗号化部１６０の構成を示すブロック図である。
【０１６６】
検索キーワード暗号化部１６０は、第１の検索キーワード暗号化器１６２と、第２の検索キーワード暗号化器１６４とから成る。
【０１６７】
第１の検索キーワード暗号化器１６２は、第１の検索キーワードｗａと第１の秘密鍵ｋ’とから、所定の擬似ランダム関数ＰＲＦを使用して、第１の暗号検索キーワードｋｗａを生成する。
【０１６８】
同様に、第２の検索キーワード暗号化器１６４は、第２の検索キーワードｗｂと第１の秘密鍵ｋ’とから、所定の擬似ランダム関数ＰＲＦを使用して、第２の暗号検索キーワードｋｗｂを生成する。
【０１６９】
図２０は、図１８に示した検索式暗号化部１７０の構成を示すブロック図である。
【０１７０】
検索式暗号化部１７０は、第１の検索式用ラベル生成部１７２と、第２の検索式用ラベル生成部１７４と、Garbled回路生成部１７６とから成る。
【０１７１】
第１の検索式用ラベル生成部１７２は、ファイル番号ｍと第１の検索キーワードｗａとの組（ｍ，ｗａ）に対して、第１の秘密鍵ｋ’を使用して、０および１の上付き文字を持ち、第ｍのファイルＤｍ用の最下位ビットが異なる一組の第１のラベルｖａ０、ｖａ１を生成する。
【０１７２】
同様に、第２の検索式用ラベル生成部１７４は、ファイル番号ｍと第２の検索キーワードｗｂとの組（ｍ，ｗｂ）に対して、第１の秘密鍵ｋ’を使用して、０および１の上付き文字を持ち、第ｍのファイルＤｍ用の最下位ビットが異なる一組の第２のラベルｖｂ０、ｖｂ１を生成する。
【０１７３】
第１及び第２の検索式用ラベル生成部１７２、１７４の具体的な構成は、図１７に図示した索引用ラベル生成部１３２と同様であるので、説明の重複を避けるためにそれらの説明については省略する。
【０１７４】
Garbled回路生成部１７６は、検索式ｆ（ｘ１，ｘ２）と一組の第１のラベルｖａ０、ｖａ１と一組の第２のラベルｖｂ０、ｖｂ１と新カウンタ値counterとから、後述のように第ｍの暗号化検索式Γｍを生成する。
【０１７５】
図２１は、図２０に示したGarbled回路生成部１７６の処理を説明するためのブロック図である。
【０１７６】
検索式ｆ（ｘ１，ｘ２）の第１及び第２のブール変数（ｘ１，ｘ２）の４つの組み合わせ（０，０）、（０，１）、（１，０）、（１，１）について、ラベルｖａｘ１及びｖｂｘ２の最下位ビットｌｓｂ（ｖａｘ１）及びｌｓｂ（ｖｂｘ２）を、それぞれ、第１及び第２のGarbled変数ａ１、ａ２とする。
【０１７７】
この場合、Garbled回路生成部１７６は、次式で示されるように、新カウンタ値counterとラベルｖａｘ１及びｖｂｘ２との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖａｘ１，ｖｂｘ２）の出力値と検索式ｆ（ｘ１，ｘ２）との排他的論理和を、Garbeld出力値ｐ（ａ１ａ２）として計算する。 
ｐ（ａ１ａ２）＝Ｈ（counter，ｖａｘ１，ｖｂｘ２）＋ｆ（ｘ１，ｘ２）ｍｏｄ２
【０１７８】
第ｍの暗号化検索式Γｍは、次式で表される。 
Γｍ＝［ｐ（００），ｐ（０１），ｐ（１０），ｐ（１１）］  
【０１７９】
図２２は、第１の実施例による暗号検索システムのサーバ２００における検索フェーズのブロック図である。
【０１８０】
サーバ２００の暗号検索部２２０は、クライアント１００から、新カウンタ値conterと第１及び第２の暗号検索キーワードｋｗａ、ｋｗｂと第１乃至第Ｍの暗号化検索式Γ１〜ΓＭとを受信する。また、暗号検索部２２０は、サーバのメモリである記憶領域２１０（図１２参照）に保管されている表Ｔを参照する。
【０１８１】
暗号検索部２２０は、第１及び第２の暗号検索キーワードｋｗａ、ｋｗｂと新カウンタ値counterと第１乃至第Ｍの暗号化検索式Γ１〜ΓＭとに基づいて、表Ｔを参照して暗号ファイルの集合を検索し、検索された暗号ファイルの集合を生成する。
【０１８２】
暗号検索部２２０は、暗号化要素探索部２２２と、Garbled回路評価部２２４と、暗号ファイル選択部２２６とから成る。
【０１８３】
暗号化要素探索部２２２は、第ｍの暗号化検索式Γｍに対して、表Ｔから第１及び第２の暗号検索キーワードｋｗａ、ｋｗｂの列を探して、当該列の一対の第ｍ行の第１及び第２の探索した暗号化行列要素ｖｍａ、ｖｍｂを生成する。
【０１８４】
Garbled回路評価部２２４は、新カウンタ値conterを使用して、第ｍの暗号化検索式Γｍと第１及び第２の探索した暗号化行列要素ｖｍａ、ｖｍｂとに基づいて、後述のように、０又は１の値をとる第ｍの評価値Ｚｍを生成する。
【０１８５】
暗号ファイル選択部２２６は、第ｍの評価値Ｚｍが１であるときに、第ｍの暗号ファイルＣｍを上記検索された暗号ファイルの集合の１つとして選択して出力する。
【０１８６】
図２３は、図２２に示したGarbled回路評価部２２４の構成を示すブロック図である。
【０１８７】
Garbled回路評価部２２４は、第１の変数生成部２２４２と、第２の変数生成部２２４４と、評価値生成部２２４６とから成る。
【０１８８】
第１の変数生成部２２４２は、次式で示されるように、第１の探索した暗号化行列要素ｖｍａの最下位ビットｌｓｂ（ｖｍａ）を、第１の探索したGarbled変数αとして生成する。 
α＝ｌｓｂ（ｖｍａ）
【０１８９】
同様に、第２の変数生成部２２４４は、次式で示されるように、第２の探索した暗号化行列要素ｖｍｂの最下位ビットｌｓｂ（ｖｍｂ）を、第２の探索したGarbled変数βとして生成する。 
β＝ｌｓｂ（ｖｍｂ）
【０１９０】
評価値生成部２２４６は、次式で表されるように、第１の探索したGarbled変数αと第２の探索したGarbled変数βとを一対の変数値として持つGarbled出力値ｐ（αβ）と、新カウンタ値counterと第１及び第２の探索した暗号化行列要素ｖｍａ、ｖｍｂとの組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖｍａ，ｖｍｂ）の出力値との排他的論理和を、第ｍの評価値Ｚｍとして計算し出力する。 
Ｚｍ＝ｐ（αβ）＋Ｈ（counter，ｖｍａ，ｖｍｂ）ｍｏｄ２
【０１９１】
尚、上式の代わりに、評価値生成部２２４６は、第ｍの評価値Ｚｍを次式に従って計算してもよい。 
Ｚｍ＝ｐ（αβ）−Ｈ（counter，ｖｍａ，ｖｍｂ）ｍｏｄ２
【０１９２】
図２４は、第１の実施例による暗号検索システムのクライアント１００における検索フェーズで使用されるファイル解読部１９０の構成を示すブロック図である。
【０１９３】
ここでは、サーバ２００から、検索された暗号ファイルの集合として、第１乃至第Ｌの検索された暗号ファイル{Ｃ１’，・・・，ＣＬ’}が取得されたとする。
【０１９４】
ファイル解読部１９０は、所定の復号アルゴリズムＤｅｃに従って復号を行なう復号器１９２から成る。
【０１９５】
復号器１９２には、第ｌ（１≦ｌ≦Ｌ）の検索された暗号ファイルＣｌ’が供給される。復号器１９２には、クライアントのメモリである保持部１５０（図１２参照）から、第２の秘密鍵ｋも供給される。復号器１９２は、第ｌの検索された暗号ファイルＣｌ’を、第２の秘密鍵ｋを使って所定の復号アルゴリズムＤｅｃにより第ｌの検索されたファイルＤｌ’に復号する。
【０１９６】
これにより、ファイル解読部１９０は、検索された所望のファイルの集合として、第１乃至第Ｌの検索されたファイル{Ｄ１’，・・・，ＤＬ’}を生成する。
【０１９７】
以上が、暗号検索システムの「検索フェーズ」の動作の説明である。
【０１９８】
本発明の第１の実施例に係る暗号検索システムによれば、検索式ｆ（ｘ１，ｘ２）を秘匿でき、検索フェーズを２−ｐａｓｓとすることができる。その理由は、検索式ｆ（ｘ１，ｘ２）の真理値表［ｆ（０，０），・・・、ｆ（１，１）］を、第１及び第２の検索キーワードｗａ，ｗｂと第１の秘密鍵ｋ’と新カウンタ値counterとを使用してGarbled回路により暗号化し、第１乃至第ＭのファイルＤ１〜ＤＭに対応する第１乃至第Ｍの暗号化検索式Γ１〜ΓＭを生成しているからである。
【０１９９】
また、上記本発明の第１の実施例に係る暗号検索システムは、暗号検索方法として実現され得る。さらに、上記本発明の第１の実施例に係る暗号検索システムのうちのクライアント（ユーザ端末）１００が実施する部分は、当該クライアント（ユーザ端末）１００に含まれるメモリ（ＲＯＭ等）に格納された暗号検索プログラムによって実行されるようにしてもよい。そして、上記本発明の第１の実施例に係る暗号検索システムのうちのサーバ２００が実施する部分も、当該サーバ２００に含まれるメモリ（ＲＯＭ等）に格納された暗号検索プログラムによって実行されるようにしてもよい。
【０２００】
以上、実施形態（実施例）を参照して本発明を説明したが、本発明は上記実施形態（実施例）に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０２０１】
例えば、上記実施形態（実施例）では、第１乃至第Ｎの暗号キーワードｋｗ１〜ｋｗＮやＭ行Ｎ列のマトリックスの暗号化索引の第ｍ行第ｎ列の暗号化行列要素ｖｍｎの各々は、１２８ビットのビット長を有しているが、それ以外の所定のビット数からなってもよい。また、検索キーワードの個数を３個以上に拡張してもよい。
【０２０２】
上記の実施形態（実施例）の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０２０３】
（付記１） ユーザ端末（１００）がサーバ（２００）に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、前記ユーザ端末（１００）がキーワード検索によって前記サーバ（２００）から検索された所望のファイルの集合を取得する暗号検索システムであって、前記ユーザ端末（１００）は、
第１の秘密鍵（ｋ’）を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワード（ｗ１，・・・，ｗＮ）をランダム化して、それぞれ、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を生成するキーワード暗号化部（１１０）と、
第２の秘密鍵（ｋ）を使って第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を暗号化して、それぞれ、前記第１至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を生成するファイル暗号化部（１２０）と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）を特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワード（ｗｎ）を含む第ｍのファイル（Ｄｍ）の第ｍ行第ｎ列の原行列要素（ｅｍｎ）を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、前記第１の秘密鍵（ｋ’）を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化部（１３０）と、
前記第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を列の欄とし、前記第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を行の欄とした、前記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表（Ｔ）を前記サーバ（２００）へ送信して前記サーバ（２００）へ保管させる表送信部（１４０）と、
初期値として０がセットされ、カウンタ値（counter）を出力するカウンタ（１４５）と、
前記第１の秘密鍵（ｋ’）と前記第２の秘密鍵（ｋ）とファイル数（Ｍ）と前記カウンタ値（counter）とを保持する保持部（１５０）と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）から選択された第１及び第２の検索キーワード(ｗａ，ｗｂ)を前記第１の秘密鍵（ｋ’）を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を生成する検索キーワード暗号化部（１６０）と、
前記保持部に保持した前記カウンタ値（counter）を前記カウンタ（１４５）を使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数（ｘ１）と第２のブール変数（ｘ２）とのブール関数から成る検索式（ｆ（ｘ１，ｘ２））を、前記第１及び第２の検索キーワード(ｗａ，ｗｂ)と前記第１の秘密鍵（ｋ’）と前記新カウンタ値（counter）とを使用してGarbled回路により暗号化し、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）にそれぞれ対応した第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）を生成する検索式暗号化部（１７０）と、
前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを前記サーバへ送って、前記サーバから前記第１及び第２の検索キーワード(ｗａ，ｗｂ)が前記検索式（ｆ（ｘ１，ｘ２））を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得部（１８０）と、
前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使用して復号して前記検索された所望のファイルの集合を得るファイル解読部（１９０）と、
を有する暗号検索システム。
【０２０４】
（付記２）  前記ファイル暗号化部（１２０）は、前記第ｍのファイル（Ｄｍ）を前記第２の秘密鍵（ｋ）を使って所定の暗号化アルゴリズム（Ｅｎｃ）により第ｍの暗号ファイル（Ｃｍ）に暗号化する暗号化器（１２２）から成り、
前記ファイル解読部（１９０）は、前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使って所定の復号アルゴリズム（Ｄｅｃ）により前記検索された所望のファイルの集合に復号する復号器（１９２）から成る、
付記１に記載の暗号検索システム。
【０２０５】
（付記３）  前記キーワード暗号化部（１１０）は、前記第ｎのキーワード（ｗｎ）と前記第１の秘密鍵（ｋ’）とから、所定の擬似ランダム関数（ＰＲＦ）を使用して、第ｎの暗号キーワード（ｋｗｎ）を生成する擬似ランダム関数発生器（１１２）から成る、付記１又は２に記載の暗号検索システム。
【０２０６】
（付記４）  前記索引暗号化部（１３０）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、第ｍ行第ｎ列の行列要素を０および１とした上付き文字を持ち、第ｍ行第ｎ列の暗号化行列要素用の最下位ビットが異なる第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）を生成する索引用ラベル生成部（１３２）と、
該生成された第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）から、前記上付き文字が前記第ｍ行第ｎ列の原行列要素（ｅｍｎ）に等しい方を前記第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）として選択し出力する選択部（１３４）と、
を有する、付記３に記載の暗号検索システム。
【０２０７】
（付記５）  前記索引用ラベル生成部（１３２）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と０との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により前記第１の暗号化索引候補（ｖｍｎ０）を生成する第１の候補生成部（１３２２）と、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と１との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により第２の暗号化索引候補（ｖｍｎ１）を生成する第２の候補生成部（１３２４）と、
前記生成した第１の暗号化索引候補（ｖｍｎ０）の最下位ビットと前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットとが等しい場合、前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットを強制的に反転して、前記第２の暗号化索引候補（ｖｍｎ１）を得る反転部（１３２６）と、
から成る、付記４に記載の暗号検索システム。
【０２０８】
（付記６）  前記検索キーワード暗号化部（１６０）は、
前記第１の検索キーワード(ｗａ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第１の暗号検索キーワード（ｋｗａ）を生成する第１の検索キーワード暗号化器（１６２）と、
前記第２の検索キーワード(ｗｂ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第２の暗号検索キーワード（ｋｗｂ）を生成する第２の検索キーワード暗号化器（１６４）と、
から成る、付記３乃至５のいずれか１項に記載の暗号検索システム。
【０２０９】
（付記７）  前記検索式暗号化部（１７０）は、
前記ファイル番号（ｍ）と前記第１の検索キーワード（ｗａ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第１のラベル（ｖａ０，ｖａ１）を生成する第１の検索式用ラベル生成部（１７２）と、
前記ファイル番号（ｍ）と前記第２の検索キーワード（ｗｂ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第２のラベル（ｖｂ０，ｖｂ１）を生成する第２の検索式用ラベル生成部（１７４）と、
前記検索式（ｆ（ｘ１，ｘ２））と、前記一組の第１のラベル（ｖａ０，ｖａ１）と、前記一組の第２のラベル（ｖｂ０，ｖｂ１）と、前記新カウンタ値（counter）とから、前記第ｍの暗号化検索式（Γｍ）を生成するGarbled回路生成部（１７６）と、
から成る、付記１乃至６のいずれか１項に記載の暗号検索システム。
【０２１０】
（付記８）  前記Garbled回路生成部（１７６）は、
前記検索式（ｆ（ｘ１，ｘ２））の前記第１及び第２のブール変数（ｘ１，ｘ２）の４つの組み合わせ（０，０），（０，１），（１，０），（１，１）について、前記ラベル（ｖａｘ１）及び（ｖｂｘ２）の最下位ビットをそれぞれ第１及び第２のGarbled変数（ａ１，ａ２）としたとき、前記新カウンタ値（counter）と前記ラベル（ｖａｘ１）及び（ｖｂｘ２）との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter,ｖａｘ１，ｖｂｘ２）の出力値と前記検索式（ｆ（ｘ１，ｘ２））との排他的論理和をGarbled出力値ｐ（ａ１ａ２）として得られる４つの組み合わせ［ｐ（００），ｐ（０１），ｐ（１０），ｐ（１１）］を、前記第ｍの暗号化検索式（Γｍ）として出力する、
付記７に記載の暗号検索システム。
【０２１１】
（付記９）  前記サーバ（２００）は、
前記ユーザ端末（１００）から送られてくる前記表（Ｔ）を保持する記憶領域（２１０）と、
前記ユーザ端末（２００）から受信した、前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とに基づいて、前記表（Ｔ）を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索部（２２０）と、
を有する、付記７又は８に記載の暗号検索システム。
【０２１２】
（付記１０）  前記暗号検索部（２２０）は、
前記第ｍの暗号化検索式（Γｍ）に対して、前記表（Ｔ）から前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）の列を探して、当該列の一対の第ｍ行の第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）を生成する暗号化要素探索部（２２２）と、
前記新カウンタ値（counter）を使用して、前記第ｍの暗号化検索式（Γｍ）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）とに基づいて、０又は１の値をとる第ｍの評価値（Ｚｍ）を生成するGarbled回路評価部（２２４）と、
前記第ｍの評価値（Ｚｍ）が１であるときに、前記第ｍの暗号ファイル（Ｃｍ）を前記検索された暗号ファイルの集合の１つとして選択して出力する暗号ファイル選択部（２２６）と、
から構成される付記９に記載の暗号検索システム。
【０２１３】
（付記１１）  前記Garbled回路評価部（２２４）は、
前記第１の探索した暗号化行列要素（ｖｍａ）の最下位ビットを第１の探索したGarbled変数（α）として生成する第１の変数生成部（２２４２）と、
前記第２の探索した暗号化行列要素（ｖｍｂ）の最下位ビットを第２の探索したGarbled変数（β）として生成する第２の変数生成部（２２４４）と、
前記第１の探索したGarbled変数（α）と前記第２の探索したGarbled変数（β）とを一対の変数値として持つGarbled出力値ｐ（αβ）と、前記新カウンタ値（counter）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖｍａ，ｖｍｂ）の出力値との排他的論理和を、前記第ｍの評価値（Ｚｍ）として出力する評価値生成部（２２４６）と、
から構成される付記１０に記載の暗号検索システム。
【０２１４】
（付記１２）  ユーザ端末（１００）がサーバ（２００）に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、前記ユーザ端末（１００）がキーワード検索によって前記サーバ（２００）から検索された所望のファイルの集合を取得する暗号検索方法であって、
前記ユーザ端末が、第１の秘密鍵（ｋ’）を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワード（ｗ１，・・・，ｗＮ）をランダム化して、それぞれ、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を生成するキーワード暗号化ステップ（１１０）と、
前記ユーザ端末が、第２の秘密鍵（ｋ）を使って第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を暗号化して、それぞれ、前記第１至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を生成するファイル暗号化ステップ（１２０）と、
前記ユーザ端末が、前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）を特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワード（ｗｎ）を含む第ｍのファイル（Ｄｍ）の第ｍ行第ｎ列の原行列要素（ｅｍｎ）を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、前記第１の秘密鍵（ｋ’）を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化ステップ（１３０）と、
前記ユーザ端末が、前記第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を列の欄とし、前記第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を行の欄とした、前記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表（Ｔ）を前記サーバ（２００）へ送信して前記サーバ（２００）へ保管させる表送信ステップ（１４０）と、
前記ユーザ端末が、カウンタ（１４５）に初期値として０がセットされ、カウンタ値（counter）を出力するステップと、
前記ユーザ端末が、前記第１の秘密鍵（ｋ’）と前記第２の秘密鍵（ｋ）とファイル数（Ｍ）と前記カウンタ値（counter）とを保持部（１５０）に保持するステップと、
前記ユーザ端末が、前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）から選択された第１及び第２の検索キーワード(ｗａ，ｗｂ)を前記第１の秘密鍵（ｋ’）を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を生成する検索キーワード暗号化ステップ（１６０）と、
前記ユーザ端末が、前記保持部に保持した前記カウンタ値（counter）を前記カウンタ（１４５）を使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数（ｘ１）と第２のブール変数（ｘ２）とのブール関数から成る検索式（ｆ（ｘ１，ｘ２））を、前記第１及び第２の検索キーワード(ｗａ，ｗｂ)と前記第１の秘密鍵（ｋ’）と前記新カウンタ値（counter）とを使用してGarbled回路により暗号化し、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）にそれぞれ対応した第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）を生成する検索式暗号化ステップ（１７０）と、
前記ユーザ端末が、前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを前記サーバへ送って、前記サーバから前記第１および第２の検索キーワード(ｗａ，ｗｂ)が前記検索式（ｆ（ｘ１，ｘ２））を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル取得ステップ（１８０）と、
前記ユーザ端末が、前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使用して復号して前記検索された所望のファイルの集合を得るファイル解読ステップ（１９０）と、
を含む暗号検索方法。
【０２１５】
（付記１３）  前記ファイル暗号化ステップ（１２０）は、前記第ｍのファイル（Ｄｍ）を前記第２の秘密鍵（ｋ）を使って所定の暗号化アルゴリズム（Ｅｎｃ）により第ｍの暗号ファイル（Ｃｍ）を生成する暗号化ステップ（１２２）を含み、
前記ファイル解読ステップ（１９０）は、前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使って所定の復号アルゴリズム（Ｄｅｃ）により前記検索された所望のファイルの集合を生成する復号ステップ（１９２）を含む、
付記１２に記載の暗号検索方法。
【０２１６】
（付記１４）  前記キーワード暗号化ステップ（１１０）は、前記第ｎのキーワード（ｗｎ）と前記第１の秘密鍵（ｋ’）とから、所定の擬似ランダム関数（ＰＲＦ）を使用して、第ｎの暗号キーワード（ｋｗｎ）を生成する擬似ランダム関数発生ステップ（１１２）を含む、付記１２又は１３に記載の暗号検索方法。
【０２１７】
（付記１５）  前記索引暗号化ステップ（１３０）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、第ｍ行第ｎ列の行列要素を０および１とした上付き文字を持ち、第ｍ第ｎの暗号化行列要素用の最下位ビットが異なる第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）を生成する索引用ラベル生成ステップ（１３２）と、
該生成された第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）から、前記上付き文字が前記第ｍ行第ｎ列の原行列要素（ｅｍｎ）に等しい方を前記第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）として選択し出力する選択ステップ（１３４）と、
を含む、付記１４に記載の暗号検索方法。
【０２１８】
（付記１６）  前記索引用ラベル生成ステップ（１３２）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と０との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により前記第１の暗号化索引候補（ｖｍｎ０）を生成する第１の候補生成ステップ（１３２２）と、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と１との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により第２の暗号化索引候補（ｖｍｎ１）を生成する第２の候補生成ステップ（１３２４）と、
前記生成した第１の暗号化索引候補（ｖｍｎ０）の最下位ビットと前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットとが等しい場合、前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットを強制的に反転して、前記第２の暗号化索引候補（ｖｍｎ１）を得る反転ステップ（１３２６）と、
を含む、付記１５に記載の暗号検索方法。
【０２１９】
（付記１７）  前記検索キーワード暗号化ステップ（１６０）は、
前記第１の検索キーワード(ｗａ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第１の暗号検索キーワード（ｋｗａ）を生成する第１の検索キーワード暗号化ステップ（１６２）と、
前記第２の検索キーワード(ｗｂ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第２の暗号検索キーワード（ｋｗｂ）を生成する第２の検索キーワード暗号化ステップ（１６４）と、
を含む、付記１４乃至１６のいずれか１項に記載の暗号検索方法。
【０２２０】
（付記１８）  前記検索式暗号化ステップ（１７０）は、
前記ファイル番号（ｍ）と前記第１の検索キーワード（ｗａ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第１のラベル（ｖａ０，ｖａ１）を生成する第１の検索式用ラベル生成ステップ（１７２）と、
前記ファイル番号（ｍ）と前記第２の検索キーワード（ｗｂ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第２のラベル（ｖｂ０，ｖｂ１）を生成する第２の検索式用ラベル生成ステップ（１７４）と、
前記検索式（ｆ（ｘ１，ｘ２））と、前記一組の第１のラベル（ｖａ０，ｖａ１）と、前記一組の第２のラベル（ｖｂ０，ｖｂ１）と、前記新カウンタ値（counter）とから、前記第ｍの暗号化検索式（Γｍ）を生成するGarbled回路生成ステップ（１７６）と、
を含む、付記１２乃至１７のいずれか１項に記載の暗号検索方法。
【０２２１】
（付記１９）  前記Garbled回路生成ステップ（１７６）は、
前記検索式（ｆ（ｘ１，ｘ２））の前記第１及び第２のブール変数（ｘ１，ｘ２）の４つの組み合わせ（０，０），（０，１），（１，０），（１，１）について、前記ラベル（ｖａｘ１）及び（ｖｂｘ２）の最下位ビットをそれぞれ第１及び第２のGarbled変数（ａ１，ａ２）としたとき、前記新カウンタ値（counter）と前記ラベル（ｖａｘ１）及び（ｖｂｘ２）との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter,ｖａｘ１，ｖｂｘ２）の出力値と前記検索式（ｆ（ｘ１，ｘ２））との排他的論理和をGarbled出力値ｐ（ａ１ａ２）として得られる４つの組み合わせ［ｐ（００），ｐ（０１），ｐ（１０），ｐ（１１）］を、前記第ｍの暗号化検索式（Γｍ）として出力する、
付記１８に記載の暗号検索方法。
【０２２２】
（付記２０）  前記サーバ（２００）が、前記ユーザ端末（１００）から送られてくる前記表（Ｔ）を記憶領域（２１０）に保持するステップと、
前記サーバ（２００）が、前記ユーザ端末（１００）から受信した、前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とに基づいて、前記表（Ｔ）を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索ステップ（２２０）と、
を更に含む、付記１８又は１９に記載の暗号検索方法。
【０２２３】
（付記２１）  前記暗号検索ステップ（２２０）は、
前記第ｍの暗号化検索式（Γｍ）に対して、前記表（Ｔ）から前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）の列を探して、当該列の一対の第ｍ行の第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）を生成する暗号化要素探索ステップ（２２２）と、
前記新カウンタ値（counter）を使用して、前記第ｍの暗号化検索式（Γｍ）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）とに基づいて、０又は１の値をとる第ｍの評価値（Ｚｍ）を生成するGarbled回路評価ステップ（２２４）と、
前記第ｍの評価値（Ｚｍ）が１であるときに、前記第ｍの暗号ファイル（Ｃｍ）を前記検索された暗号ファイルの集合の１つとして選択して出力する暗号ファイル選択ステップ（２２６）と、
を含む付記２０に記載の暗号検索方法。
【０２２４】
（付記２２）  前記Garbled回路評価ステップ（２２４）は、
前記第１の探索した暗号化行列要素（ｖｍａ）の最下位ビットを第１の探索したGarbled変数（α）として生成する第１の変数生成ステップ（２２４２）と、
前記第２の探索した暗号化行列要素（ｖｍｂ）の最下位ビットを第２の探索したGarbled変数（β）として生成する第２の変数生成ステップ（２２４４）と、
前記第１の探索したGarbled変数（α）と前記第２の探索したGarbled変数（β）とを一対の変数値として持つGarbled出力値ｐ（αβ）と、前記新カウンタ値（counter）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖｍａ，ｖｍｂ）の出力値との排他的論理和を、前記第ｍの評価値（Ｚｍ）として出力する評価値生成ステップ（２２４６）と、
を含む付記２１に記載の暗号検索方法。
【０２２５】
（付記２３）  サーバ（２００）に第１乃至第Ｍ（Ｍは２以上の整数）の暗号ファイルと暗号化索引を保管し、キーワード検索によって前記サーバ（２００）から検索された所望のファイルの集合を取得する処理を、コンピュータであるユーザ端末（１００）に実行させる暗号検索プログラムであって、前記コンピュータである前記ユーザ端末（１００）に、
第１の秘密鍵（ｋ’）を使って第１乃至第Ｎ（Ｎは２以上の整数）のキーワード（ｗ１，・・・，ｗＮ）をランダム化して、それぞれ、第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を生成するキーワード暗号化手順（１１０）と、
第２の秘密鍵（ｋ）を使って第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を暗号化して、それぞれ、前記第１至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を生成するファイル暗号化手順（１２０）と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）を特定するキーワード番号ｎ（１≦ｎ≦Ｎ）を列とし、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）を特定するファイル番号ｍ（１≦ｍ≦Ｍ）を行として、第ｎのキーワード（ｗｎ）を含む第ｍのファイル（Ｄｍ）の第ｍ行第ｎ列の原行列要素（ｅｍｎ）を１とし、それ以外を０としたＭ行Ｎ列のマトリックスから成る索引を、前記第１の秘密鍵（ｋ’）を使って暗号化して、第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）の各々が所定ビット数から成るＭ行Ｎ列のマトリックスの暗号化索引を生成する索引暗号化手順（１３０）と、
前記第１乃至第Ｎの暗号キーワード（ｋｗ１，・・・，ｋｗＮ）を列の欄とし、前記第１乃至第Ｍの暗号ファイル（Ｃ１，・・・，ＣＭ）を行の欄とした、前記Ｍ行Ｎ列のマトリックスの暗号化索引から成る表（Ｔ）を前記サーバ（２００）へ送信して前記サーバ（２００）へ保管させる表送信手順（１４０）と、
カウンタ（１４５）に初期値として０がセットされ、カウンタ値（counter）を出力する手順と、
前記第１の秘密鍵（ｋ’）と前記第２の秘密鍵（ｋ）とファイル数（Ｍ）と前記カウンタ値（counter）とを保持部（１５０）に保持する手順と、
前記第１乃至第Ｎのキーワード（ｗ１，・・・，ｗＮ）から選択された第１及び第２の検索キーワード(ｗａ，ｗｂ)を前記第１の秘密鍵（ｋ’）を使ってランダム化して、それぞれ、第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）を生成する検索キーワード暗号化手順（１６０）と、
前記保持部（１５０）に保持した前記カウンタ値（counter）を前記カウンタ（１４５）を使用して１だけ増加させて新カウンタ値を生成させ、各々が０又は１の値をとる第１のブール変数（ｘ１）と第２のブール変数（ｘ２）とのブール関数から成る検索式（ｆ（ｘ１，ｘ２））を、前記第１及び第２の検索キーワード(ｗａ，ｗｂ)と前記第１の秘密鍵（ｋ’）と前記新カウンタ値（counter）とを使用してGarbled回路により暗号化し、前記第１乃至第Ｍのファイル（Ｄ１，・・・，ＤＭ）にそれぞれ対応した第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）を生成する検索式暗号化手順（１７０）と、
前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とを前記サーバ（２００）へ送って、前記サーバ（２００）から前記第１および第２の検索キーワード(ｗａ，ｗｂ)が前記検索式（ｆ（ｘ１，ｘ２））を満たすファイルの集合に対応する、検索された暗号ファイルの集合を取得する暗号ファイル手順（１８０）と、
前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使用して復号して前記検索された所望のファイルの集合を得るファイル解読手順（１９０９）と、
を実行させるための暗号検索プログラム。
【０２２６】
（付記２４）  前記ファイル暗号化手順（１２０）は、前記第ｍのファイル（Ｄｍ）を前記第２の秘密鍵（ｋ）を使って所定の暗号化アルゴリズム（Ｅｎｃ）により第ｍの暗号ファイル（Ｃｍ）を生成する暗号化手順（１２２）から成り、
前記ファイル解読手順（１９０）は、前記取得した検索された暗号ファイルの集合を前記第２の秘密鍵（ｋ）を使って所定の復号アルゴリズム（Ｄｅｃ）により前記検索された所望のファイルの集合を生成する復号手順（１９２）から成る、
付記２３に記載の暗号検索プログラム。
【０２２７】
（付記２５）  前記キーワード暗号化手順（１１０）は、前記第ｎのキーワード（ｗｎ）と前記第１の秘密鍵（ｋ’）とから、所定の擬似ランダム関数（ＰＲＦ）を使用して、第ｎの暗号キーワード（ｋｗｎ）を生成する擬似ランダム関数発生手順（１１２）から成る、付記２３又は２４に記載の暗号検索プログラム。
【０２２８】
（付記２６）  前記索引暗号化手順（１３０）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、第ｍ行第ｎ列の行列要素を０および１とした上付き文字を持ち、第ｍ第ｎの暗号化行列要素用の最下位ビットが異なる第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）を生成する索引用ラベル生成手順（１３２）と、
該生成された第１及び第２の暗号化索引候補（ｖｍｎ０，ｖｍｎ１）から、前記上付き文字が前記第ｍ行第ｎ列の原行列要素（ｅｍｎ）に等しい方を前記第ｍ行第ｎ列の暗号化行列要素（ｖｍｎ）として選択し出力する選択手順（１３４）と、
から成る、付記２５に記載の暗号検索プログラム。
【０２２９】
（付記２７）  前記索引用ラベル生成手順（１３２）は、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と０との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により前記第１の暗号化索引候補（ｖｍｎ０）を生成する第１の候補生成手順（１３２２）と、
前記ファイル番号（ｍ）と前記第ｎのキーワード（ｗｎ）と１との組に対して、前記第１の秘密鍵（ｋ’）を使用して、前記所定の擬似ランダム関数（ＰＲＦ）により第２の暗号化索引候補（ｖｍｎ１）を生成する第２の候補生成手順（１３２４）と、
前記生成した第１の暗号化索引候補（ｖｍｎ０）の最下位ビットと前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットとが等しい場合、前記生成した第２の暗号化索引候補（ｖｍｎ１）の最下位ビットを強制的に反転して、前記第２の暗号化索引候補（ｖｍｎ１）を得る反転手順（１３２６）と、
から成る、付記２６に記載の暗号検索プログラム。
【０２３０】
（付記２８）  前記検索キーワード暗号化手順（１６０）は、
前記第１の検索キーワード(ｗａ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第１の暗号検索キーワード（ｋｗａ）を生成する第１の検索キーワード暗号化手順（１６２）と、
前記第２の検索キーワード(ｗｂ)と前記第１の秘密鍵（ｋ’）とから、前記所定の擬似ランダム関数（ＰＲＦ）を使用して、前記第２の暗号検索キーワード（ｋｗｂ）を生成する第２の検索キーワード暗号化手順（１６４）と、
から成る、付記２５乃至２７のいずれか１項に記載の暗号検索プログラム。
【０２３１】
（付記２９）  前記検索式暗号化手順（１７０）は、
前記ファイル番号（ｍ）と前記第１の検索キーワード（ｗａ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第１のラベル（ｖａ０，ｖａ１）を生成する第１の検索式用ラベル生成手順（１７２）と、
前記ファイル番号（ｍ）と前記第２の検索キーワード（ｗｂ）との組に対して、前記第１の秘密鍵（ｋ’）を使用して、０および１の上付き文字を持ち、前記第ｍのファイル（Ｄｍ）用の最下位ビットが異なる一組の第２のラベル（ｖｂ０，ｖｂ１）を生成する第２の検索式用ラベル生成手順（１７４）と、
前記検索式（ｆ（ｘ１，ｘ２））と、前記一組の第１のラベル（ｖａ０，ｖａ１）と、前記一組の第２のラベル（ｖｂ０，ｖｂ１）と、前記新カウンタ値（counter）とから、前記第ｍの暗号化検索式（Γｍ）を生成するGarbled回路生成手順（１７６）と、
から成る、付記２３乃至２８のいずれか１項に記載の暗号検索プログラム。
【０２３２】
（付記３０）  前記Garbled回路生成手順（１７６）は、
前記検索式（ｆ（ｘ１，ｘ２））の前記第１及び第２のブール変数（ｘ１，ｘ２）の４つの組み合わせ（０，０），（０，１），（１，０），（１，１）について、前記ラベル（ｖａｘ１）及び（ｖｂｘ２）の最下位ビットをそれぞれ第１及び第２のGarbled変数（ａ１，ａ２）としたとき、前記新カウンタ値（counter）と前記ラベル（ｖａｘ１）及び（ｖｂｘ２）との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter,ｖａｘ１，ｖｂｘ２）の出力値と前記検索式（ｆ（ｘ１，ｘ２））との排他的論理和をGarbled出力値ｐ（ａ１ａ２）として得られる４つの組み合わせ［ｐ（００），ｐ（０１），ｐ（１０），ｐ（１１）］を、前記第ｍの暗号化検索式（Γｍ）として出力する、
付記２９に記載の暗号検索プログラム。
【０２３３】
（付記３１）  付記２９又は３０に記載の暗号検索プログラムと共に使用され、コンピュータである前記サーバ（２００）に検索を実行させる暗号検索プログラムであって、前記コンピュータである前記サーバ（２００）に、
前記ユーザ端末（１００）から送られてくる前記表（Ｔ）を記憶領域（２１０）に保持する手順と、
前記ユーザ端末（１００）から受信した、前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）と前記新カウンタ値（counter）と前記第１乃至第Ｍの暗号化検索式（Γ１，・・・，ΓＭ）とに基づいて、前記表（Ｔ）を参照して暗号ファイルの集合を検索し、前記検索された暗号ファイルの集合を生成する暗号検索手順（２２０）と、
を実行させる暗号検索プログラム。
【０２３４】
（付記３２）  前記暗号検索手順（２２０）は、
前記第ｍの暗号化検索式（Γｍ）に対して、前記表（Ｔ）から前記第１及び第２の暗号検索キーワード（ｋｗａ，ｋｗｂ）の列を探して、当該列の一対の第ｍ行の第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）を生成する暗号化要素探索手順（２２２）と、
前記新カウンタ値（counter）を使用して、前記第ｍの暗号化検索式（Γｍ）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）とに基づいて、０又は１の値をとる第ｍの評価値（Ｚｍ）を生成するGarbled回路評価手順（２２４）と、
前記第ｍの評価値（Ｚｍ）が１であるときに、前記第ｍの暗号ファイル（Ｃｍ）を前記検索された暗号ファイルの集合の１つとして選択して出力する暗号ファイル選択手順（２２６）と、
から成る付記３１に記載の暗号検索プログラム。
【０２３５】
（付記３３）  前記Garbled回路評価手順（２２４）は、
前記第１の探索した暗号化行列要素（ｖｍａ）の最下位ビットを第１の探索したGarbled変数（α）として生成する第１の変数生成手順（２２４２）と、
前記第２の探索した暗号化行列要素（ｖｍｂ）の最下位ビットを第２の探索したGarbled変数（β）として生成する第２の変数生成手順（２２４４）と、
前記第１の探索したGarbled変数（α）と前記第２の探索したGarbled変数（β）とを一対の変数値として持つGarbled出力値ｐ（αβ）と、前記新カウンタ値（counter）と前記第１及び第２の探索した暗号化行列要素（ｖｍａ，ｖｍｂ）との組み合わせに対して１ビットを出力するハッシュ関数Ｈ（counter，ｖｍａ，ｖｍｂ）の出力値との排他的論理和を、前記第ｍの評価値（Ｚｍ）として出力する評価値生成手順（２２４６）と、
から成る付記３２に記載の暗号検索プログラム。
【産業上の利用可能性】
【０２３６】
本発明は、ＡＮＤやＯＲなどの任意のブール関数から成る検索式を秘匿しつつ、検索フェーズを２−ｐａｓｓとする方式に利用可能である。
【符号の説明】
【０２３７】
１００    クライアント（ユーザ端末）
１１０    キーワード暗号化部
１１２    擬似ランダム関数発生器
１２０    ファイル暗号化部
１２２    暗号化器
１３０    索引暗号化部
１３２    索引用ラベル生成部
１３２２    第１の候補生成部
１３２４    第２の候補生成部
１３２６    反転部
１３４    選択部
１４０    表送信部
１４５    カウンタ
１５０    保持部（クライアントのメモリ）
１６０    検索キーワード暗号化部
１６２    第１の検索キーワード暗号化器
１６４    第２の検索キーワード暗号化器
１７０    検索式暗号化部
１７２    第１の検索式用ラベル生成部
１７４    第２の検索式用ラベル生成部
１７６    Garbled回路生成部
１８０    暗号ファイル取得部
１９０    ファイル解読部
１９２    復号器
２００    サーバ
２１０    記憶領域（サーバのメモリ）
２２０    暗号検索部
２２２    暗号化要素探索部
２２４    Garbled回路評価部
２２４２    第１の変数生成部
２２４４    第２の変数生成部
２２４６    評価値生成部
２２６    暗号ファイル選択部
【図１】
2015114432.tif 000003
【図２】
2015114432.tif 000004
【図３】
2015114432.tif 000005
【図４】
2015114432.tif 000006
【図５】
2015114432.tif 000007
【図６】
2015114432.tif 000008
【図７】
2015114432.tif 000009
【図８】
2015114432.tif 000010
【図９】
2015114432.tif 000011
【図１０】
2015114432.tif 000012
【図１１】
2015114432.tif 000013
【図１２】
2015114432.tif 000014
【図１３】
2015114432.tif 000015
【図１４】
2015114432.tif 000016
【図１５】
2015114432.tif 000017
【図１６】
2015114432.tif 000018
【図１７】
2015114432.tif 000019
【図１８】
2015114432.tif 000020
【図１９】
2015114432.tif 000021
【図２０】
2015114432.tif 000022
【図２１】
2015114432.tif 000023
【図２２】
2015114432.tif 000024
【図２３】
2015114432.tif 000025
【図２４】
2015114432.tif 000026