TOP > 国内特許検索 > 動的検索可能暗号処理システム > 明細書

明細書 :動的検索可能暗号処理システム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2020-112773 (P2020-112773A)
公開日 令和2年7月27日(2020.7.27)
発明の名称または考案の名称 動的検索可能暗号処理システム
国際特許分類 G09C   1/00        (2006.01)
G06F  21/60        (2013.01)
G06F  16/901       (2019.01)
FI G09C 1/00 660D
G06F 21/60 320
G06F 16/901
請求項の数または発明の数 6
出願形態 OL
全頁数 16
出願番号 特願2019-111977 (P2019-111977)
出願日 令和元年6月17日(2019.6.17)
優先権出願番号 2019003908
優先日 平成31年1月11日(2019.1.11)
優先権主張国 日本国(JP)
発明者または考案者 【氏名】渡邉 洋平
【氏名】岩本 貢
【氏名】太田 和夫
出願人 【識別番号】301022471
【氏名又は名称】国立研究開発法人情報通信研究機構
【識別番号】504133110
【氏名又は名称】国立大学法人電気通信大学
個別代理人の代理人 【識別番号】100120868、【弁理士】、【氏名又は名称】安彦 元
審査請求 未請求
要約 【課題】効率性を向上させることができ、フォワード安全性を満たすようなことができる、動的検索可能暗号処理システムを提供する。
【解決手段】文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブルから、前記文書ファイルに含まれる前記キーワードを抽出キーワードとして抽出し、前記文書ファイルに対応する識別子を抽出識別子として抽出し、前記抽出手段により抽出された前記抽出キーワードと前記抽出識別子とを連結させ、1組としたアドレスと、前記アドレスに含まれる前記抽出識別子を格納部とした関係を示す第1テーブルを生成し、前記第1テーブルにおける前記アドレスを擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、前記変換アドレス手段により変換された前記変換アドレスと前記格納部との関係を示す第2テーブルを生成する。
【選択図】図1
特許請求の範囲 【請求項1】
端末とサーバがネットワークを介して接続され、暗号化されたデータテーブルを用いた動的検索可能暗号システムであって、
文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブルから、前記文書ファイルに含まれる前記キーワードを抽出キーワードとして抽出するとともに、前記文書ファイルに対応する識別子を抽出識別子として抽出する抽出手段と、
前記抽出手段により抽出された前記抽出キーワードと前記抽出識別子とを連結させ、1組としたアドレス情報と、前記アドレス情報に含まれる前記抽出識別子との関係を示す第1テーブルを生成する第1テーブル生成手段と、
前記第1テーブルにおける前記アドレスを擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、前記変換アドレスと前記抽出識別子との関係を示す第2テーブルを生成する第2テーブル生成手段と、
を備えること
を特徴とする動的検索可能暗号システム。
【請求項2】
前記第2テーブル生成手段は、
前記端末が保持する疑似乱数生成関数に関する鍵情報、前記端末が保持するステート情報に基づき、前記抽出識別子を初期化した第2テーブルを生成し、前記鍵情報と前記ステート情報の記憶後に、前記生成した前記第2テーブルを前記サーバに送信すること、
を特徴とする請求項1記載の動的検索可能暗号システム。
【請求項3】
前記端末は、
追加する文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブルから、前記文書ファイルに含まれる前記キーワードを抽出キーワードとして抽出するとともに、前記文書ファイルに対応する識別子を抽出識別子として抽出し、前記抽出した前記抽出キーワードと前記抽出識別子とを連結させ、1組としたアドレス情報と、前記アドレス情報に含まれる前記抽出識別子との関係を示す第1テーブルを生成し、前記アドレスを擬似乱数生成関数により乱数化情報に変換して変換追加アドレスを生成し、前記抽出識別子をステート情報に記憶し、前記変換アドレスと前記抽出識別子を前記サーバに送信し、
前記サーバは、
前記端末により送信された前記変換アドレスを受信し、前記変換アドレスの乱数化情報のそれぞれが示すアドレスに、前記受信した前記抽出識別子を格納し、前記第2テーブルを更新すること、
を特徴とする請求項1又は2のいずれかに記載の動的検索可能暗号システム。
【請求項4】
前記端末は、
削除する文書ファイルに対応する前記抽出識別子を、前記ステート情報から削除し、前記削除した前記抽出識別子を前記サーバに送信し、
前記サーバは、
前記端末により送信された前記抽出識別子を受信し、前記サーバの第2テーブルで前記抽出識別子に対応する全ての格納領域をNULLに変換し、前記第2テーブルを更新すること、
を特徴とする請求項1~3のいずれかに記載の動的検索可能暗号システム。
【請求項5】
前記第2テーブル生成手段は、
追加する文書ファイルと同じ大きさの文書ファイルのうち、最も多い抽出キーワードを含むことができる文書ファイルを特定し、前記追加文書ファイルに対応する変換アドレスの個数が、前記特定した文書ファイルに含まれる抽出キーワード数となるまで、ダミーフラグを示す識別情報と、カウンタ情報と、前期追加文書ファイルの抽出識別子とを連結させ、1組のダミーアドレス情報とし、前期ダミーアドレス情報を疑似乱数生成関数により乱数化情報に変換して変換ダミーアドレスを生成し、前記変換ダミーアドレス情報が指し示すアドレスに前記抽出識別子を格納すること、を繰り返し、前記第2テーブルを生成すること、を特徴とする請求項1~4のいずれかに記載の動的検索可能暗号システム。
【請求項6】
前記端末は、
検索するキーワードと前記ステート情報に含まれる各識別子を検索識別子として連結させ、1組としたアドレス情報と、前記アドレス情報を擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、前記変換アドレスを前記サーバに送信し、
前記サーバは、
前記端末により送信された前記変換アドレスを受信し、前記サーバの第2テーブルで前記変換アドレスに対応する全ての格納領域を参照し、前記格納領域がNULLではなく、所定の識別子が格納される格納先の抽出識別子を取得し、前記端末に送信すること、
を特徴とする請求項1~5のいずれかに記載の動的検索可能暗号システム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、端末とサーバがネットワークを介して接続され、暗号化されたデータテーブルを用いた動的検索可能暗号システムに関する。
【背景技術】
【0002】
近年、クラウドサービスの普及により、企業等はオンラインストレージ等の外部ストレージサービスを利用し、社内における膨大な文書ファイルを管理サーバ(クラウドサーバ)上で保存・管理させる事例が増加しつつある。管理サーバ上に保存・管理される文書ファイルは、管理サーバ上に保存される前に暗号化される。そして、暗号化された文書ファイルは、外部ストレージサービスで提供される管理サーバの暗号化データベースに保存される。暗号化された文書ファイルは、暗号化されたままの状態でキーワード検索することが可能であり、このような暗号化処理技術は検索可能暗号(Searchable Symmetric Encryption : SSE)として知られている。
【0003】
さらに、検索可能暗号の中でも、管理サーバ上の暗号化データベースに保存された暗号化文書ファイルに対して、任意のタイミングで暗号化文書ファイルを追加及び削除等の動的な更新を可能にする研究が進められており、動的検索可能暗号(Dynamic Searchable Symmetric Encryption : DSSE)として知られている。
【0004】
動的検索暗号では、管理サーバ上に保存された暗号化データベース上のファイルに対してキーワード検索を行えることができることに加え、プロトコルの途中であっても、ファイル及びそれに付随するキーワードの暗号化データベースへの追加や削除が可能となる。以前より、最も強い安全性(例えば、検索を何度実行しても、検索データベース上のファイルについて全く情報が漏れない)を満たすためには、理論的に非効率な方法でしか実現できないことが知られていたため、最低限満たすべき安全性(例えば、検索回数に応じて、多少の本質的ではない情報の漏洩を許す)を満たした上で効率的な方式の研究が行われ、さらに、最低限満たすべき安全性に加え、フォワード安全性(新たに追加されたファイルに、過去に検索されたキーワードが含まれていることが漏れない)を満たす方式が知られている(例えば、非特許文献1参照)。
【0005】
非特許文献1の開示技術では、端末側でキーワードに関する情報 (各キーワードのこれまでの検索回数、各キーワードを含むファイルの数) をステート情報として保持し、ステート情報を利用して、暗号化インデックステーブルのアドレス部を作成することを特徴としており、アドレス部の生成はサーバ側で行う。なお、暗号化インデックステーブルへのダミーエントリの追加方法については開示されていない。
【先行技術文献】
【0006】

【非特許文献1】M.Etemad、A.Kupcu、C.Papamanthou、D.Evans、「Efficient dynamic searchable encryption with forward privacy」、In Proceedings of Privacy Enhancing Technologies (PoPETs)、2018年、p.5-20
【発明の概要】
【発明が解決しようとする課題】
【0007】
非特許文献1の開示技術では、端末側でキーワードに関する情報をステート情報として保持する必要があり、ステート情報は端末が保持するキーワード数に依存するため、対象データの大きさの効率性に問題があった。また、アドレス部の生成をサーバ側で行うため、フォワード安全性を達成するためには検索時にアドレス部の再登録が必要である。本来は検索の処理だけのところを、検索と再登録の2つの処理が必要となるため、再登録の操作や処理の分だけ操作が発生し、効率性を低下させることになる。さらに、暗号化インデックステーブルへのダミーエントリの追加方法は不明であり、より強い、現実的な状況に整合した安全性を達成できるか不明である。
【0008】
そこで、本発明は、上述した問題点に鑑みて案出されたものであり、その目的とするところは、効率性を向上させることができ、フォワード安全性を満たすようなことができる、動的検索可能暗号処理システムを提供することにある。
【課題を解決するための手段】
【0009】
第1発明に係る動的検索可能暗号処理システムは、端末とサーバがネットワークを介して接続され、暗号化されたデータテーブルを用いた動的検索可能暗号システムであって、文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブルから、前記文書ファイルに含まれる前記キーワードを抽出キーワードとして抽出するとともに、前記文書ファイルに対応する識別子を抽出識別子として抽出する抽出手段と、前記抽出手段により抽出された前記抽出キーワードと前記抽出識別子とを連結させ、1組としたアドレス情報と、前記アドレス情報に含まれる前記抽出識別子との関係を示す第1テーブルを生成する第1テーブル生成手段と、前記第1テーブルにおける前記アドレスを擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、前記変換アドレスと前記抽出識別子との関係を示す第2テーブルを生成する第2テーブル生成手段と、を備えることを特徴とする。
【0010】
第2発明に係る動的検索可能暗号処理システムは、第1発明において、前記第2テーブル生成手段は、前記端末が保持する疑似乱数生成関数に関する鍵情報、前記端末が保持するステート情報に基づき、前記抽出識別子を初期化した第2テーブルを生成し、前記鍵情報と前記ステート情報の記憶後に、前記生成した前記第2テーブルを前記サーバに送信すること、を特徴とする。
【0011】
第3発明に係る動的検索可能暗号処理システムは、第1発明又は第2発明において、前記端末は、追加する文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブルから、前記文書ファイルに含まれる前記キーワードを抽出キーワードとして抽出するとともに、前記文書ファイルに対応する識別子を抽出識別子として抽出し、前記抽出した前記抽出キーワードと前記抽出識別子とを連結させ、1組としたアドレス情報と、前記アドレス情報に含まれる前記抽出識別子との関係を示す第1テーブルを生成し、前記アドレスを擬似乱数生成関数により乱数化情報に変換して変換追加アドレスを生成し、前記抽出識別子をステート情報に記憶し、前記変換アドレスと前記抽出識別子を前記サーバに送信し、前記サーバは、前記端末により送信された前記変換アドレスを受信し、前記変換アドレスの乱数化情報のそれぞれが示すアドレスに、前記受信した前記抽出識別子を格納し、前記第2テーブルを更新すること、を特徴とする。
【0012】
第4発明に係る動的検索可能暗号処理システムは、第1発明~第3発明において、前記端末は、削除する文書ファイルに対応する前記抽出識別子を、前記ステート情報から削除し、前記削除した前記抽出識別子を前記サーバに送信し、前記サーバは、前記端末により送信された前記抽出識別子を受信し、前記サーバの第2テーブルで前記抽出識別子に対応する全ての格納領域をNULLに変換し、前記第2テーブルを更新すること、を特徴とする。
【0013】
第5発明に係る動的検索可能暗号処理システムは、第1発明~第4発明において、前記第2テーブル生成手段は、追加する文書ファイルと同じ大きさの文書ファイルのうち、最も多い抽出キーワードを含むことができる文書ファイルを特定し、前記追加文書ファイルに対応する変換アドレスの個数が、前記特定した文書ファイルに含まれる抽出キーワード数となるまで、ダミーフラグを示す識別情報と、カウンタ情報と、前期追加文書ファイルの抽出識別子とを連結させ、1組のダミーアドレス情報とし、前期ダミーアドレス情報を疑似乱数生成関数により乱数化情報に変換して変換ダミーアドレスを生成し、前記変換ダミーアドレス情報が指し示すアドレスに前記抽出識別子を格納すること、を繰り返し、前記第2テーブルを生成すること、を特徴とする。
【0014】
第6発明に係る動的検索可能暗号処理システムは、第1発明~第5発明において、前記端末は、検索するキーワードと前記ステート情報に含まれる各識別子を検索識別子として連結させ、1組としたアドレス情報と、前記アドレス情報を擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、前記変換アドレスとを前記サーバに送信し、前記サーバは、前記端末により送信された前記変換アドレスを受信し、前記サーバの第2テーブルで前記変換アドレスに対応する全ての格納領域を参照し、前記格納領域がNULLではなく、所定の識別子が格納される格納先の抽出識別子を取得し、前記端末に送信すること、を特徴とする。
【発明の効果】
【0015】
第1発明~第6発明によれば、動的検索可能システムは、参照テーブルから文書ファイルと検索キーワードとの対応を示すアドレス情報を抽出し、第1テーブルと第2テーブルとを生成する。これにより、端末が保持する全ての文書ファイルとキーワードの対応を識別子により操作することができ、識別子のみを保存すれば良く、端末側が保持する情報を小さくできる。これにより、端末とサーバにおける効率性を向上させることができる。
【0016】
特に、第1発明によれば、第1テーブル生成手段は、抽出された抽出キーワードと文書ファイルの識別子とを連結させ、1組としたアドレス情報と、アドレス情報に含まれる抽出識別子との関係を示す第1テーブルを生成する。このため、ステート情報はキーワード数に依存することがない。これにより、効率性を向上させることができる。
【0017】
特に、第1発明によれば、第2テーブル生成手段は、アドレス情報を端末が保持する擬似乱数生成関数により端末側で乱数化情報に変換する。このため、疑似乱数生成用の鍵をキーワードごとに生成、サーバに渡し、サーバ側で疑似乱数を生成させる必要がなくなる。これにより、第三者へ必要以上の情報が漏洩することを防ぎ、フォワード安全性を達成することができる。
【0018】
特に第2発明によれば、第2テーブル生成手段は、端末が保持する疑似乱数生成関数に関する鍵情報、端末が保持するステート情報により、初期化した第2テーブルを生成し、サーバに送信する。このため、端末とサーバで共通の初期化テーブルを介したやり取りが可能となる。
【0019】
特に、第3発明によれば、端末は、追加する文書ファイルに対応する抽出識別子と抽出キーワードとを連結させ、1組としたアドレス情報と、前記アドレス情報に含まれる前記抽出識別子との関係を示す第1テーブルを生成し、前記アドレスを擬似乱数生成関数により乱数化情報に変換して変換追加アドレスを生成し、前記抽出識別子をステート情報に記憶し、前記変換アドレスと前記抽出識別子を前記サーバに送信し、前記サーバは、前記端末により送信された前記変換アドレスを受信し、前記変換アドレスの乱数化情報のそれぞれが示すアドレスに、前記受信した前記抽出識別子を格納し、前記第2テーブルを更新する。このため、追加依頼された抽出識別子を適切な箇所に格納することができる。
【0020】
特に、第4発明によれば、端末は削除する文書ファイルに対応する抽出識別子をステート情報から削除し、抽出識別子をサーバに送信し、サーバは、抽出識別子を受信し、第2テーブルで抽出識別子に対応する全ての格納領域をNULLに変換し、前記第2テーブルを更新する。このため、削除依頼された抽出識別子が格納されている箇所を、全て空(NULL)に設定することができる。
【0021】
特に、第5発明によれば、第2テーブルに保存される変換アドレスの個数が、対象とする文書ファイルと同じ大きさの文書ファイルのうち、最も多い抽出キーワードを含む文書ファイルを特定する。このため、文書ファイルは、登録したい文書ファイルと同じ大きさの文書ファイルのうち、最も多くのキーワードを含むもののキーワード数と等しくなるようダミーエントリを容易に生成できる。これにより、サーバは、文書ファイルの候補を絞り込むことができなくなり、より強い安全性を実現させることができる。
【0022】
特に、第6発明によれば、端末は端末上に保存されている各識別子を用い、検索キーワードと各識別子を連結したものを元に疑似乱数生成関数により乱数化情報を生成し、それら全てをサーバに送信し、サーバは各乱数化情報がアドレス情報として指し示す第2テーブルの格納値を調べ、NULL以外の格納値を全て端末に送り返す。このため、端末とサーバ間においてやり取りされる情報に文書ファイルに関する情報は含まれない。これにより、フォワード安全性を満たすことができる。
【図面の簡単な説明】
【0023】
【図1】図1は、第1実施形態における動的検索可能暗号処理システムの全体構成を示すブロック図である。
【図2】図2(a)は、第1実施形態における動的検索可能暗号処理システム100の構成の一例を示す模式図であり、図2(b)は、動的検索可能暗号処理システム100の機能の一例を示す模式図である。
【図3】図3(a)は、第1実施形態におけるセットアップ処理における対応テーブルの一例を示す管理テーブルであり、図3(b)は、第1実施形態におけるセットアップ処理における第1テーブルの一例を示す管理テーブルであり、図3(c)は、第1実施形態におけるセットアップ処理における第2テーブルの一例を示す管理テーブルである。
【図4】図4は、第1実施形態における検索処理の対応を示す説明図である。
【図5】図5は、第1実施形態における検索処理の対応を示す説明図である。
【図6】図6は、第1実施形態における文書ファイルが含み得る最大のキーワード個数を示す説明図である。
【図7】図7(a)、(b)は、第1実施形態における動的検索可能暗号処理システムの動作の一例を示すフローチャートである。
【発明を実施するための形態】
【0024】
以下、本発明の実施形態における動的検索可能暗号処理システム100の一例について、図面を参照しながら説明する。

【0025】
(第1実施形態)
図1は、本実施形態における動的検索可能暗号処理システム100の全体構成を示すブロック図である。

【0026】
本実施形態の動的検索可能暗号処理システム100は、図1に示すように、例えば、社内の複数の端末2(登録端末2a、検索端末2b)と公衆通信網5(ネットワーク)を介して接続されるサーバ3により構成される。サーバ3は、暗号化データベース4を備え、暗号化された文書ファイル及び暗号化インデックステーブル (または第2テーブル)を保存する。

【0027】
登録端末2a及び検索端末2bは、例えば、パーソナルコンピュータ(PC)等の電子機器が用いられ、文書ファイルを暗号化し、サーバ3への登録操作や処理を行う。サーバ3は、例えば、オンラインストレージ等の外部ストレージサービスを運用するクラウドサーバ等の電子機器が用いられる。サーバ3は、暗号化データベース4に保管される暗号化文書ファイルの更新や検索(動的検索)を行う。

【0028】
図2は、本発明が適用される動的検索可能暗号処理システムの構成の一例を示すブロック図である。

【0029】
図2(a)は、第1実施形態における動的検索可能暗号処理システム100の構成の一例を示す模式図である。

【0030】
図2(a)に示すように、動的検索可能暗号処理システム100を構成する端末2は、筐体10と、CPU(Central Processing Unit)11と、ROM(Read Only Memory)12と、RAM(Random Access Memory)13と、記憶部分14と、I/F15~17とを備える。各々の構成であるI/F15~18は、内部バス18により接続される。

【0031】
CPU11は、動的検索可能暗号処理システム100全体を制御する。ROM12は、CPU11の動作コードを格納する。RAM13は、CPU11の動作時に使用される作業領域である。記憶部分14は、例えば、端末の属性情報、関連情報、登録端末2aに生成される各テーブル、擬似ランダム関数の他に、暗号共通鍵等の情報を記憶する。記憶部分14は、例えば、端末の操作者に関する情報、操作者に関する認証情報等の各種情報、その他、登録、更新、検索ログ等の各種情報が各々対応付けられて記憶されてもよい。なお、例えば、動的検索可能暗号処理システム100は、図示しないGPU(Graphics Processing Unit)を有してもよい。GPUを有することで、通常よりも高速演算処理が可能となる。

【0032】
I/F15は、公衆通信網5を介して端末2等との各種情報の送受信を行うためのインターフェースである。I/F16は、入力部分20との情報の送受信を行うためのインターフェースである。入力部分20として、例えば、キーボードが用いられ、動的検索可能暗号処理システム100の管理者等は、入力部分20を介して、各種情報又はサーバ3の制御コマンド等を入力する。I/F17は、出力部分19との各種情報の送受信を行うためのインターフェースである。出力部分19は、記憶部分14に保存された各種情報、又はサーバ3の処理状況等を出力する。出力部分19として、ディスプレイが用いられ、例えばタッチパネル式でもよい。

【0033】
図2(b)は、動的検索可能暗号処理システム100の機能の一例を示す模式図である。動的検索可能暗号処理システム100を構成する端末2とサーバ3の機能を示す。

【0034】
端末2は、例えば、端末2の全体を制御する制御部21、文書ファイルに含まれるキーワードの抽出、文書ファイルに対応する識別子を抽出識別子として抽出する抽出部22、第1テーブルの生成を行う第1テーブル生成部23、第2テーブルの生成を行う第2テーブル生成部24、公衆通信網5を介してサーバ3とデータのやり取りを行う送受信部25、文書ファイル、キーワード、各テーブル、擬似乱数生成関数、鍵情報、ステータス情報、各種アプリケーション等のデータ及び情報を記憶する記憶部26を少なくとも備える。

【0035】
サーバ3は、例えば、サーバ3の全体及び暗号化データベース4を制御する制御部31、端末2から受信した第2テーブルの初期化、追加、削除等を行う更新部32、端末2からの検索を実行し、検索結果を出力する検索部33、公衆通信網5を介して複数の端末2とデータのやり取りを行う送受信部35、暗号化文書ファイル、第2テーブル、擬似乱数生成関数、鍵情報、各種アプリケーション等のデータ及び情報を記憶する記憶部35を少なくとも備える。

【0036】
図2(b)に示した端末2及びサーバ3の機能は、CPU11が、RAM13を作業領域として、記憶部分14等に記憶されたプログラムを実行することにより実現される。

【0037】
記憶部26及び記憶部35として、例えばHDDのほか、SSD等のデータ保存装置が用いられ、例えば、暗号化データベース4と一体に具現化されてもよい。記憶部26及び記憶部35には、例えば、RAM及びROMを含み、各々で実行されるプログラム等が記憶される。なお、端末2及びサーバ3により実行される各機能は、各制御部が、RAMを作業領域として、各々の記憶部に記憶されたプログラムを実行することにより実現することができる。

【0038】
図3は、動的検索可能暗号処理システム100のセットアップ処理における各テーブルの一例を示す管理テーブルである。

【0039】
図3(a)は、例えば、端末2に保持される参照テーブル40aであり、文書ファイル(fn)と各々の文書ファイル対応する識別子(idn)と各文書ファイル(fn)に対応するキーワードとの関係を対応付けて格納される。図3(b)は、端末2で生成される第1テーブル40bであり、参照テーブル40aから抽出部22により抽出され、抽出キーワード(wd)と抽出識別子(idn)とを連結させ、1組としたアドレス情報と、アドレス情報に含まれる抽出識別子(idn)とが各々対応付けて格納される。図3(c)は、第1テーブル40bにおけるアドレスを擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、変換アドレスと抽出識別子(idn)とが各々対応付けられて格納される。

【0040】
ここで、文書ファイルは、文書ファイルの集合をFで表し、各文書ファイルfid∈Fには、それぞれ対応する識別子id∈{0,1}l(lはkの多項式)が付され、文書ファイルfidを単にidと書く。Λ:={0,1}λ(λはkの多項式)をあり得る全てのキーワードの集合とし、例えば、ビット列ではなく文字列として表現されてもよい。また、識別子idiである文書ファイルに含まれるキーワードの集合をWiとする。

【0041】
動的検索可能暗号処理システム100は、セットアップ(Setup)の実行時に、タイムスタンプt:=0として初期化し、登録端末2aまたは検索端末2bは、検索(Search)及び更新(Update)の各操作を行うごとに、タイムスタンプをインクリメントされるようにしてもよい。

【0042】
図3(a)は、第1実施形態における参照テーブル40aの一例を示す参照テーブルである。参照テーブル40aは、暗号化対象の文書ファイルとその文書ファイルが含むキーワードの集合(id,Wid) として対応付けられる。参照テーブル40aは、例えば、t時点での文書ファイルf1(識別子id1)~文書ファイルfn(識別子idn)に含まれる全てのキーワードw1~wdが各々対応付ける。文書ファイルf1にキーワードw1が含まれている場合は、例えば、参照テーブル40aの対応する箇所にフラグ(例えば、×)が付されて記憶される。

【0043】
図3(b)は、第1実施形態における第1テーブル40bの一例を示す管理テーブルである。インデックステーブル40bは、対応テーブル40aから各文書ファイルにキーワードが含まれている対応箇所のみ(フラグ×の箇所)が抽出される。

【0044】
次に、第1テーブル40bは、アドレス情報(部)と抽出識別子(例えば、文書管理番号)の組み(対)の関係により構成される。アドレス情報は、例えば、キーワードwiと文書ファイルの文書番号idの連結(wi||id)であり、抽出識別子は、例えば、文書ファイルfidの抽出識別子idとなる。

【0045】
図3(c)は、第1実施形態における第2テーブルの一例を示す管理テーブルである。第2テーブル40cは、第1テーブル40bのアドレス情報(部)と抽出識別子(例えば、文書管理番号)の対の関係性を隠すため、例えば、ユーザのみが知る擬似乱数生成関数πを用いて、変換された関係性の対として生成される。

【0046】
第2テーブル40cは、第1テーブル40bのキーワードwiと文書ファイルの文書番号idの連結(wi||id)を、擬似乱数生成関数πを用いて乱数化される。アドレスは、例えば、π(k,wi||id)として変換され、識別子は、例えば、文書ファイルfidの識別子idがアドレスπ(k,wi||id)と関連付けられて記憶される。

【0047】
図4は、第1実施形態における検索処理の対応を示す説明図である。検索端末2bから入力される検索キーワードqを用いて、サーバ3の暗号化データベース4に記憶されている暗号化文書ファイルの検索を行う。

【0048】
第2テーブル40cは、第2テーブル生成部24により、 第1テーブル40bの検索キーワードqと文書ファイルの文書番号idの 連結(q||id)を、擬似乱数生成関数πを用いて乱数化し、 検索端末2bは、変換アドレスをサーバ3に送信し、 サーバ3は、検索端末2bにより送信された変換アドレスを受信する。サーバ3の第2テーブル40cで変換アドレスに 対応する全ての格納領域を参照し、格納領域がNULLではなく、 所定の識別子が格納される格納先の抽出識別子を取得する。

【0049】
図5は、第1実施形態における検索処理の対応を示す説明図である。暗号化サーバ3は、例えば、検索端末2bから送信された変換アドレスを受信し、第2テーブル40cを参照し、検索依頼のあったアドレス情報のうち、π(k,q||id1)及びアドレス情報π(k,q||id3)と対になる検索識別子で関連付けられる文書ファイルが登録されているため、該当する検索識別子id1及びid3を、検索端末2bに送信する。

【0050】
図6は、文書ファイルfidが含み得る最大のキーワード数を示す説明図である。文書ファイルfidはwidに含まれるキーワードの組み合わせからなるファイルとみなすが、maxidをfidが含むことのできるキーワードの最大個数(例えば、10個)とする。文書ファイルの最大キーワードの個数は、最も小さいキーワードw∈Λから順にそのサイズを加算し、|fid|を超える手前までに加算したキーワードwjの合計個数となる。

【0051】
文書ファイルの最大キーワードの個数、例えば、μid個のエントリを登録すると同時に、(maxid — μid) 個のダミーエントリを追加してもよく、これにより、idを格納しているアドレスの個数を|fid|個に常に統一することが可能となる。そのため、サーバは文書ファイルfidの候補を絞り込むことができない。

【0052】
次に、図7(a)、(b)は、第1実施形態における動的検索可能暗号処理システムの動作の一例を示すフローチャートである。

【0053】
先ず、動的検索可能暗号処理システム100の登録端末2aは、抽出ステップS110~第2テーブル生成ステップS130を実行する。

【0054】
<抽出ステップS110>
登録端末2aの抽出部22は、文書ファイルと抽出キーワードの抽出を行う(抽出ステップS110)。抽出ステップS110では、文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブルから、文書ファイルに含まれるキーワードを抽出キーワードとして抽出する。そして、文書ファイルに対応する識別子を抽出識別子として抽出する。

【0055】
<第1テーブル生成ステップS120>
次に、第1テーブル生成部23は、抽出ステップS110により抽出されたアドレス情報と識別子に対して、アドレス情報と識別子との対応を第1テーブル40bとして生成する(第1テーブル生成ステップS120)。第1テーブル生成部は、抽出ステップS110により抽出された抽出キーワードと抽出識別子とを連結させ、1組としたアドレス情報と、アドレス情報に含まれる前記抽出識別子との関係を示す第1テーブルを生成する。

【0056】
また、第1テーブル生成部23は、抽出ステップS110により抽出された全てのアドレス情報及び識別子に、更新があるかを判別する。そして、追加または削除の変更がある場合は、アドレス情報に含まれる文書ファイルを特定する抽出識別子を変更に応じて、暗号化文書ファイルの追加または削除する変更を行う。

【0057】
<第2テーブル生成ステップS130>
第2テーブル生成部24は、第1テーブルの各アドレス情報を乱数化情報に変換して第2テーブルを生成する(第2テーブル生成ステップS130)。第2テーブル生成部24は、第1テーブル40bに含まれる各アドレス情報を、登録端末2aの記憶部26に記憶される擬似乱数生成関数及びその鍵により乱数化情報に変換し、第2テーブル40cとして生成する。

【0058】
(第2実施形態)
図7(b)は、動的検索可能暗号処理システム100のサーバ3における検索処理について、受信ステップS210~結果送信ステップS230を実行する。

【0059】
まず、検索端末2bは、検索するキーワードとステート情報に含まれる各識別子を検索識別子として連結させ、1組としたアドレス情報を生成する。

【0060】
次に、アドレスを擬似乱数生成関数により乱数化情報に変換して変換アドレスを生成し、変換アドレスをサーバ3に送信する。

【0061】
<受信ステップS210>
サーバ3の送受信部34は、検索端末2bから送信された変換アドレスを受信する(受信ステップS210)。

【0062】
<更新ステップS220>
検索部33は、暗号化データベース4に格納される第2テーブルを参照し、第2テーブル40cで変換アドレスに対応する全ての格納領域を参照し、格納領域がNULLではなく、所定の識別子が格納される格納先の抽出識別子を取得する。(検索ステップS220)。判別の結果に応じて、Xq(t)に加え、送られてきた値の全ての変換アドレスをチェックする。ここで、tは現時点での時刻を表す。

【0063】
<結果送信ステップS230>
送受信部34は、検索依頼のあった検索端末2bに、検索結果である検索識別子を送信する。(送信ステップS230)。検索結果である各文書ファイルfid∈Fは、共通鍵暗号で暗号化され(図示せず)、サーバ3の暗号化データベース4に保存される。なお、全ての暗号化文書ファイルは、文書ファイルの識別子idと併せて、サーバ3の暗号化データベース4に保存される。

【0064】
これにより、本実施形態における動的検索可能暗号処理システム100の動作が終了する。

【0065】
(第3実施形態)
次に、端末2(登録端末2a)における第2テーブルの初期化処理について説明する。端末2は、第2テーブル生成ステップS130において、端末2aが保持する 疑似乱数生成関数に関する鍵情報、端末2aが保持するステート情報に基づき、抽出識別子を初期化した第2テーブル40cを生成し、鍵情報とステート情報の端末2bの記憶部26に記憶させる。その後に、生成した第2テーブル40cをサーバ3に送信する。

【0066】
本実施例によれば、検索端末2bは検索依頼の対象となる検索キーワードと端末に保存されたステート情報に含まれる全ての検索識別子idに応じて生成された変換アドレスを生成し、送信する。サーバ3は、受信した変換アドレスから、第2テーブルの変換アドレスが指し示すアドレスに格納された値を確認する。そのため、サーバ3はステート情報に含まれる識別子に関する変換アドレスに対応する格納領域のみを参照する。これにより、検索端末2bとサーバ3との間で、その時点の検索に必要なだけの情報がやり取りされ、検索後のアドレスの再登録が不要となり、フォワード安全性を達成することができるとともに、効率性を向上させることができる。

【0067】
(第4実施形態)
次に、動的検索可能暗号処理システム100における、端末2とサーバ3における文書ファイルの追加の処理について説明する。

【0068】
まず、登録端末2aは、追加する文書ファイルに対応する識別子とキーワードとの関係を示す参照テーブル40aから、文書ファイルに含まれる前記キーワードを抽出キーワードとして抽出する。そして、文書ファイルに対応する識別子を抽出識別子として抽出し、抽出した抽出キーワードと抽出識別子とを連結させ、1組としたアドレス情報と、アドレス情報に含まれる抽出識別子との関係を示す第1テーブルを生成する。

【0069】
次に、登録端末2aの記憶部26に記憶される擬似乱数生成関数により、アドレス情報を乱数化情報に変換して、変換追加アドレスを生成する。登録端末2aは、抽出識別子をステート情報に記憶し、その後に、変換アドレスと抽出識別子をサーバ3に送信する。

【0070】
登録端末2aにおける文書ファイルの更新(追加)は、例えば、以下の処理で実行される。

【0071】
<<時刻tにおける文書ファイル(id,Wid) の追加>>
端末2(登録端末2a)は記憶部26に登録されるアプリケーション(Updateアルゴリズム:図示せず)により、全てのw∈Wid に対してπ(k,w||id) を計算する。ダミーアドレスではないことを示すため、π(k,0||w||id)としてもよい。ここで計算された値が、第2テーブル40cのアドレスとなる。登録端末2aは、計算した値全て及びidをサーバ3に送信し、登録端末2aに記憶されるステート情報σ(t)にidを追加し、ステート情報σ(t+1)とする。

【0072】
サーバ3は、登録端末2aにより送信された変換アドレス及び抽出識別子を受信し、第2テーブル40cの変換アドレスの乱数化情報のそれぞれが示すアドレスに、受信した抽出識別子を格納し、第2テーブル40cを更新し、EDB(t+1)とする。

【0073】
(第5実施形態)
次に、動的検索可能暗号処理システム100における、端末2とサーバ3における文書ファイルの削除の処理について説明する。

【0074】
本実施形態によれば、idが格納値として第2テーブルに含まれる数μidを、対応する文書ファイルfidが含み得るキーワードの最大数maxidに合わせるため、 (maxidid) 個のダミーアドレスとして、π(k,1||1||id)~π(k,1|| maxidid ||id)を生成し、それぞれが指し示す第2テーブル中のアドレスにidを格納してもよい。このため、文書ファイルfidが含むことのできる最大数のキーワード(maxid個)になるまでidのダミーエントリを追加することができる。これにより、より強い安全性を備えることが可能となる。

【0075】
登録端末2aは、削除する文書ファイルに対応する抽出識別子を、記憶部26に記憶されるステート情報から削除し、削除した抽出識別子をサーバ3に送信する。

【0076】
<<時刻tにおけるidに対応する文書ファイルの削除>>
登録端末2aは、サーバ3に操作の対象となる抽出識別子(id)を送信する。そして記憶部26に記憶されるステート情報σ(t)から対象の抽出識別子(id)を削除し、ステート情報σ(t+1)とする。

【0077】
サーバ3は、削除対象となる抽出識別子を受信し、第2テーブル40cの格納されている値が抽出識別子(id)の部分を、全てNULLに置き換える処理を繰り返し、全て置き換えた第2テーブル40cを更新し、EDB(t+1)とする。

【0078】
さらに、本実施形態によれば、動的検索可能暗号処理システム100は、例えば、複数の医療機関をまたがったデータベースにおける検索サービスに適用することが可能である。これにより、病院のデータベースに記憶される個人情報が、患者カルテ(ファイル)の更新、または検索される際に、必要以上に漏洩することを防ぐことが可能となる。

【0079】
さらに、本実施形態によれば、動的検索可能暗号処理システム100は、例えば、クラウドサーバを介してやり取りされるメールサービス等において、ユーザは過去にやり取りしたメールやアーカイブしたメール等を暗号化したまま検索が可能となる。そのため、クラウド側にメールの内容が漏洩することを防ぐことが可能となる。

【0080】
動的検索可能暗号処理システム100において、ステート情報は必ずしも端末に保存される必要はなく、また、端末が保持するステート情報を公開しても良い。そのため、前記ステート情報を端末ではなくサーバに保存したとしても、それによって安全性が損なわれることはない。

【0081】
本発明の実施形態を説明したが、各実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【0082】
10 :筐体
11 :CPU
12 :ROM
13 :RAM
14 :記憶部分
15 :I/F
16 :I/F
17 :I/F
18 :内部バス
19 :出力部分
100 :動的検索可能暗号処理システム
2 :端末
2a :登録端末
2b :検索端末
20 :入力部分
21 :制御部
22 :抽出部
23 :第1テーブル生成部
24 :第2テーブル生成部
25 :送受信部
26 :記憶部
3 :サーバ
31 :制御部
32 :更新部
33 :検索部
34 :送受信部
35 :記憶部
4 :暗号化データベース
40a :参照テーブル
40b :第1テーブル
40c :第2テーブル
5 :公衆通信網
S110 :抽出ステップ
S120 :第1テーブル生成ステップ
S130 :第2テーブル生成ステップ
S210 :受信ステップ
S220 :更新ステップ
S230 :結果送信ステップ
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6