(57)【特許請求の範囲】
【請求項１】
nを2以上の整数とし、
メッセージを共有するn台の端末と前記メッセージを暗号化した暗号化メッセージを記録するサーバとを含むメッセージ送受信システムにおいて、前記端末がメッセージ検索用文字列を用いて前記暗号化メッセージを検索する暗号化メッセージ検索方法であって、
前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、
前記n台の端末の記録部には、前記ルーム識別子と、セッション鍵とが記録されており、
前記端末が、ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、検索用秘密鍵として乱数を生成し、前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成し、前記暗号化検索用秘密鍵を前記サーバに送信する暗号化検索用秘密鍵送信ステップと、
前記端末が、前記ルーム識別子を用いて前記サーバから前記暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から前記検索用秘密鍵を復号する検索用秘密鍵復号ステップと、
前記端末が、メッセージを暗号化した暗号化メッセージを生成し、前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成し、前記インデックス集合と前記暗号化メッセージとを前記ルーム識別子とともに前記サーバに送信する暗号化メッセージ送信ステップと、
前記端末が、前記メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成し、前記クエリ集合を前記ルーム識別子とともに前記サーバに送信するクエリ送信ステップと、
前記サーバが、前記ルーム識別子と対応付けて管理しているインデックス集合と暗号化メッセージの中から前記クエリ集合の要素と一致するインデックス集合の要素がある暗号化メッセージを検索し、前記暗号化メッセージを前記端末に送信する暗号化メッセージ返信ステップと、
前記端末が、前記暗号化メッセージからメッセージを復号する暗号化メッセージ復号ステップと、
を含む暗号化メッセージ検索方法。
【請求項２】
請求項１に記載の暗号化メッセージ検索方法であって、
関数f, gは任意の(K, K1)∈KEY×KEY1に対し次式を満たすものとし、
【数１２】
0006770075.tif 000013
CRHFを任意長の文字列を入力とし、固定長の文字列を出力する衝突困難ハッシュ関数、Fを２つの任意長の文字列を入力とし、文字列を出力する関数とし、
前記暗号化検索用秘密鍵送信ステップでは、SearchKeyを検索用秘密鍵、R1をセッション鍵として、f(SearchKey, R1)を計算することにより、暗号化検索用秘密鍵CipherKeyを生成し、
前記検索用秘密鍵復号ステップでは、Temp=f(SearchKey, R1)とし、g(Temp, R1)を計算することにより、前記検索用秘密鍵SearchKeyを復号し、
前記暗号化メッセージ送信ステップでは、メッセージm1を暗号化するメッセージ、関数Gを任意長の文字列を入力として入力文字列に依存する濃度を有する文字列集合を出力する関数として、前記メッセージに関係する情報をG(m1)={s1, s2,.., sq,..}とし、前記インデックス集合{Index1, Index 2,.., Index q,..}の各要素を次式により計算し、
【数１３】
0006770075.tif 000014
前記クエリ送信ステップでは、前記メッセージ検索用文字列をm’とし、前記クエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}の各要素をQueryi=CRHF(F(m’, SearchKeyi)) (T1≦i≦T2、ただし、T1、T2は検索用秘密鍵の世代を示す１以上の整数)として計算する暗号化メッセージ検索方法。
【請求項３】
請求項１に記載の暗号化メッセージ検索方法であって、
前記n台の端末の記録部には、さらに前記サーバが前記ルームごとに生成した公開鍵pkroomIDと秘密鍵skroomIDとが記録されており、
関数f, gは任意の(K, K1)∈Mpk×KEY1に対し次式を満たすものとし、
【数１４】
0006770075.tif 000015
CRHFを任意長の文字列を入力とし、固定長の文字列を出力する衝突困難ハッシュ関数、Fを２つの任意長の文字列を入力とし、文字列を出力する関数とし、
前記暗号化検索用秘密鍵送信ステップでは、SearchKeyを検索用秘密鍵、R1をセッション鍵として、暗号化検索用秘密鍵CipherKey=Enc(pkroomID, f(SearchKey, R1))を生成し、
前記検索用秘密鍵復号ステップでは、g(Dec(skroomID, CipherKey), R1)を計算することにより、前記検索用秘密鍵SearchKeyを復号し、
前記暗号化メッセージ送信ステップでは、メッセージm1を暗号化するメッセージ、関数Gを任意長の文字列を入力として入力文字列に依存する濃度を有する文字列集合を出力する関数として、前記メッセージに関係する情報をG(m1)={s1, s2,.., sq,..}とし、前記インデックス集合{Index1, Index 2,.., Index q,..}の各要素を次式により計算し、
【数１５】
0006770075.tif 000016
前記クエリ送信ステップでは、前記メッセージ検索用文字列をm’とし、前記クエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}の各要素をQueryi=CRHF(F(m’, SearchKeyi)) (T1≦i≦T2、ただし、T1、T2は検索用秘密鍵の世代を示す１以上の整数)として計算する暗号化メッセージ検索方法。
【請求項４】
請求項２または３に記載の暗号化メッセージ検索方法であって、
前記関数Gは、メッセージm1を入力とし、メッセージm1内の連続するi個(i=1,..,P、ただし、P=min{L, lengthm_1}、Lは検索可能な文字列長の上限値、lengthm_1はメッセージm1の文字列長)の文字からなる文字列を列挙することにより生成される集合{s1(1), s2(1),.., sj(i),..}(ただし、j=1, 2,.., lengthm_1-i+1)を出力する関数である暗号化メッセージ検索方法。
【請求項５】
nを2以上の整数とし、
メッセージを共有するn台の端末と前記メッセージを暗号化した暗号化メッセージを記録するサーバとを含むメッセージ送受信システムであって、
前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、
前記サーバは、
前記ルーム識別子と、前記n台の端末が共有する検索用秘密鍵を暗号化した暗号化検索用秘密鍵と、暗号化メッセージと、メッセージ検索用のインデックス集合とを記録する記録部と、
前記ルーム識別子と対応付けて管理しているインデックス集合と暗号化メッセージの中から前記端末からのクエリ集合の要素と一致するインデックス集合の要素がある暗号化メッセージを検索するインデックス検索部と、
を含み、
前記端末は、
前記ルーム識別子と、前記n台の端末で共有するセッション鍵とを記録する記録部と、
ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、乱数を前記検索用秘密鍵として生成する検索用秘密鍵生成部と、
前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成する検索用秘密鍵暗号化部と、
前記ルーム識別子を用いて前記サーバから前記暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から前記検索用秘密鍵を復号する暗号化検索用秘密鍵復号部と、
メッセージを暗号化した暗号化メッセージを生成するメッセージ暗号化部と、
前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成するインデックス生成部と、
メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成するクエリ生成部と、
暗号化メッセージからメッセージを復号する暗号化メッセージ復号部と、
を含むメッセージ送受信システム。
【請求項６】
メッセージを暗号化した暗号化メッセージを記録するサーバを介して他の端末と前記メッセージを共有する端末であって、
前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、
前記ルーム識別子と、前記n台の端末で共有するセッション鍵とを記録する記録部と、
ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、乱数を検索用秘密鍵として生成する検索用秘密鍵生成部と、
前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成する検索用秘密鍵暗号化部と、
前記ルーム識別子を用いて前記サーバから暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から検索用秘密鍵を復号する暗号化検索用秘密鍵復号部と、
メッセージを暗号化した暗号化メッセージを生成するメッセージ暗号化部と、
前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成するインデックス生成部と、
メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成するクエリ生成部と、
暗号化メッセージからメッセージを復号する暗号化メッセージ復号部と、
を含む端末。
【請求項７】
請求項６に記載の端末としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は情報セキュリティ技術の応用に関し、特に、グループを形成する複数のユーザがメッセージを送受信するメッセージ送受信技術に関する。
【背景技術】
【０００２】
ビジネスでの利用を前提とするメッセージ送受信システムの中には、パソコンやスマートフォンなど端末の種別を問わないマルチデバイス対応なもので、ビジネス上の機密情報漏えいを考慮して端末にメッセージを含むデータを残さないような、クラウドベース型のメッセージ送受信システムが存在する。クラウドベース型のメッセージ送受信システムの例として、非特許文献１のような製品がある。【０００３】
このようなクラウドベース型のメッセージ送受信システムは、通信路を暗号化することにより盗聴を防止する機能や、既に述べたように端末にデータを残さないことにより端末の紛失や不正な持ち出しに起因する情報漏えいを防止する機能を備えている。このように現在のクラウドベース型のメッセージ送受信システムは、通信経路と端末に対する脅威については対応しているが、その一方でメッセージ送受信システムを構成するサーバに対する脅威については必ずしも対応が十分とは言えない状況である。ここでいうサーバに対する脅威には、例えば、サーバに対する外部からの攻撃、サーバ管理者等による内部からの不正アクセスなどがある。【０００４】
このサーバに対する脅威に対しては、サーバに保存するメッセージを暗号化するという対策が考えられる。しかし、サーバにおいて復号可能である場合は、上述の脅威に対してサーバからメッセージが漏えいする可能性が依然として存在する。したがって、メッセージがサーバに対して秘匿化されている、つまりサーバにおいて盗聴されないようになっていることが重要である。【０００５】
サーバにおいて盗聴されないようにする1つの方法としては、サーバに対してメッセージを秘匿化しつつ端末においてのみメッセージの復号が可能となるようなエンドツーエンドでの暗号化通信を実現する方法がある。このようなエンドツーエンドでの暗号化通信を実現するためには、端末で用いる共通鍵（以下、セッション鍵ともいう）を端末間でどのように共有するかが問題となる。その解決策として、中央に認証サーバを持つスター型のネットワークにおいて、認証サーバに対していかなる情報ももらさずに利用者間で共通鍵を共有するプロトコルが提案されている（非特許文献２）。非特許文献２のプロトコルにより、サーバに対しメッセージを秘匿化したまま端末間で送受信が可能となる。【０００６】
しかし、ビジネスでの利用を踏まえると、過去のメッセージのやりとりに関して効率よく処理する方法が必要になる。そのような手段として、メッセージの検索機能が考えられるが、非特許文献２のプロトコルによる利用者間でのセッション鍵共有技術を適用した場合、サーバに保存されているメッセージは暗号化されているため、サーバに保存されたメッセージを秘匿化したまま検索できるようにする必要がある。さらに、検索内容そのものや過去の検索に対する回答の傾向等から秘匿化した内容が推測されにくくすることも必要である。【０００７】
サーバに保存された暗号化メッセージを含む暗号化データを復号することなく検索する方法として、暗号化データに関する情報についてのハッシュ値をサーバに記録する方法がある（特許文献１）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】“ビジネス向けグループチャットTopicRoom”，［online］，［平成28年8月16日検索］，インターネット<URL: https://www.ntts.co.jp/products/topicroom/index.html>
【非特許文献２】小林鉄太郎，米山一樹，吉田麗生，川原祐人，冨士仁，山本具英：“スケーラブルな動的多者鍵配布プロトコル”，SCIS2016，4E2-3，2016．
【特許文献】
【０００９】
【特許文献１】特開2015-118603号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、特許文献１の検索技術では、同じ情報に対して常に同じハッシュ値が得られるため、一定期間通信路を盗聴することで得られるハッシュ値とレインボーテーブルを用いることにより検索しようとしている情報やその検索結果が推測されてしまうという問題がある。【００１１】
この発明の目的は、このような点に鑑みて、n台の端末で共有するメッセージを暗号化した暗号化メッセージを記録するサーバにおいて暗号化したままメッセージ検索をする際、検索内容や検索結果が推測されにくい暗号化メッセージ検索技術を提供することである。
【課題を解決するための手段】
【００１２】
本発明の一態様は、nを2以上の整数とし、メッセージを共有するn台の端末と前記メッセージを暗号化した暗号化メッセージを記録するサーバとを含むメッセージ送受信システムにおいて、前記端末がメッセージ検索用文字列を用いて前記暗号化メッセージを検索する暗号化メッセージ検索方法であって、前記n台の端末で共有するメッセージを前記サーバが管理する単位をルーム、その識別子をルーム識別子とし、前記n台の端末の記録部には、前記ルーム識別子と、セッション鍵とが記録されており、前記端末が、ルーム識別子共有後または最初の検索用秘密鍵を共有した後は事前に設定された更新間隔が経過する度、検索用秘密鍵として乱数を生成し、前記セッション鍵を用いて前記検索用秘密鍵から暗号化検索用秘密鍵を生成し、前記暗号化検索用秘密鍵を前記サーバに送信する暗号化検索用秘密鍵送信ステップと、前記端末が、前記ルーム識別子を用いて前記サーバから前記暗号化検索用秘密鍵を取得し、前記セッション鍵を用いて前記暗号化検索用秘密鍵から前記検索用秘密鍵を復号する検索用秘密鍵復号ステップと、前記端末が、メッセージを暗号化した暗号化メッセージを生成し、前記メッセージに関係する情報と、前記検索用秘密鍵のうち最新検索用秘密鍵を用いて、メッセージ検索用のインデックス集合を生成し、前記インデックス集合と前記暗号化メッセージとを前記ルーム識別子とともに前記サーバに送信する暗号化メッセージ送信ステップと、前記端末が、前記メッセージ検索用文字列と、前記検索用秘密鍵のうち１つ以上の検索用秘密鍵を用いて、クエリ集合を生成し、前記クエリ集合を前記ルーム識別子とともに前記サーバに送信するクエリ送信ステップと、前記サーバが、前記ルーム識別子と対応付けて管理しているインデックス集合と暗号化メッセージの中から前記クエリ集合の要素と一致するインデックス集合の要素がある暗号化メッセージを検索し、前記暗号化メッセージを前記端末に送信する暗号化メッセージ返信ステップと、前記端末が、前記暗号化メッセージからメッセージを復号する暗号化メッセージ復号ステップと、を含む。
【発明の効果】
【００１３】
この発明によれば、n台の端末で共有するメッセージを暗号化した暗号化メッセージを記録するサーバにおいて暗号化したままメッセージ検索をする際、検索内容や検索結果が推測されにくい検索を実現することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】メッセージ送受信システムの構成を例示する図である。
【図２】第一実施形態のサーバ１００の機能構成を例示する図である。
【図３】第一実施形態の端末２００の機能構成を例示する図である。
【図４】第一実施形態のメッセージ送受信方法の処理フロー（システムセットアップ）を例示する図である。
【図５】第一実施形態のメッセージ送受信方法の処理フロー（検索用秘密鍵の共有）を例示する図である。
【図６】第一実施形態のメッセージ送受信方法の処理フロー（暗号化メッセージの送信）を例示する図である。
【図７】第一実施形態のメッセージ送受信方法の処理フロー（暗号化メッセージの検索）を例示する図である。
【図８】第一実施形態のインデックス生成部２４５の動作の様子を例示する図である。
【図９】第一実施形態のメッセージ送受信方法の処理フロー（検索用秘密鍵の更新）を例示する図である。
【図１０】第二実施形態のサーバ５００の機能構成を例示する図である。
【図１１】第二実施形態の端末６００の機能構成を例示する図である。
【図１２】第二実施形態のメッセージ送受信方法の処理フロー（システムセットアップ）を例示する図である。
【発明を実施するための形態】
【００１５】
実施形態の説明に先立って、この明細書における表記方法等について説明する。
【００１６】
＜表記方法＞
_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【００１７】
ある集合Setについて、Setから要素mを一様ランダムに選ぶことを、m←U Setと表記する。
【００１８】
ある確率的多項式時間アルゴリズムALGについて、入力xに対してALG(x)を確率変数とみたとき、その確率分布に従ってランダムにy が出力されることを、y←R ALG(x)と表記する。
【００１９】
＜定義＞
Nを正の整数全体の集合とする。
【００２０】
関数CRHFを任意長の文字列を入力とし、固定長の文字列を出力する衝突困難ハッシュ関数とする。出力文字列の長さは固定であるが、その長さについては特に限定しない。
【００２１】
関数Fを２つの任意長の文字列を入力とし、文字列を出力する関数とする。出力文字列の長さについては特に限定しない。関数Fの例として、2つの入力文字列を結合する関数F(m, r)=m||rがある。
【００２２】
なお、以下説明する実施形態では、関数CRHF、関数Fとして任意の関数を用いることができる。ただし、関数Fの第２引数は、後述するように平文空間Mpkまたは鍵空間KEYの元となる。
【００２３】
以下、この発明の実施形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２４】
＜第一実施形態＞
第一実施形態のメッセージ送受信システムは、公開鍵暗号アルゴリズムを用いる。そこで、まず公開鍵暗号アルゴリズムについて説明する。
【００２５】
kをセキュリティパラメータとする。k1∈Nとし、k1ビット長の鍵空間をKEY1={0, 1}k_1とする。
【００２６】
公開鍵暗号方式は、３つのアルゴリズム(Gen, Enc, Dec)からなる。Genは、セキュリティパラメータkを入力とし、公開鍵pkと秘密鍵skの組(pk, sk)を出力する鍵生成アルゴリズムであり、(pk, sk)←R Gen(1k)と表すことにする。また、このとき平文空間Mpkが定まる。
【００２７】
Encは、公開鍵pkと平文m∈Mpkを入力とし、暗号文Cを出力する暗号化アルゴリズムであり、C←R Enc(pk, m)と表すことにする。
【００２８】
Decは、秘密鍵skと暗号文Cを入力とし、平文m’を出力する復号アルゴリズムであり、m’←R Dec(sk, C)と表すことにする。
【００２９】
また、上記３つのアルゴリズムは、任意のセキュリティパラメータk、任意の鍵ペア(pk,sk)←R Gen(1k)、任意の平文m∈Mpkに対し、Dec(sk,Enc(pk,m))=mを満たす。
【００３０】
次に、平文空間Mpkと鍵空間KEY1={0, 1}k_1の直積Mpk×KEY1を定義域、平文空間Mpkを値域とする関数f: Mpk×KEY1→Mpkに対し、関数g: Mpk×KEY1→Mpkが存在し、任意の(K, K1)∈Mpk×KEY1に対し、次式を満たす場合を考える。
【００３１】
【数１】
0006770075.tif 000002
【００３２】
RSA暗号や楕円ElGamal暗号については、上記条件（式(1)）を満たす関数f,gの例を挙げることができる。RSA暗号方式の場合、平文空間Mpkは、鍵生成アルゴリズム実行時に生成した２つの素数p,qの積をn=pqとしたとき、{1,…,n-1}のうち、nと互いに素である整数の集合に、次式で定義される演算・が入った乗法群である。
【００３３】
【数２】
0006770075.tif 000003
【００３４】
なお、右辺の×は整数同士の通常の積である。
【００３５】
このとき、KEY1=Mpk、つまり、関数f: Mpk×Mpk→Mpk、関数g: Mpk×Mpk→Mpkであり、任意の(K, K1)∈Mpk×Mpkに対し、式(1)を満たす(f,g)の例として、以下の関数の組が存在する。
【００３６】
【数３】
0006770075.tif 000004
【００３７】
なお、演算/は、演算・におけるx2の逆元をx2-1としたとき、x1/x2= x1・x2-1と定義される演算である。
【００３８】
また、楕円ElGamal暗号の場合、平文空間Mpkは、鍵生成アルゴリズム実行時に生成する楕円曲線上の点がなす加法群である。このとき、KEY1=Mpk、つまり、関数f: Mpk×Mpk→Mpk、関数g: Mpk×Mpk→Mpkであり、任意の(K, K1)∈Mpk×Mpkに対し、式(1)を満たす(f,g)の例として、以下の関数の組が存在する（ただし、+を上記加法群における加法とする）。
【００３９】
【数４】
0006770075.tif 000005
【００４０】
なお、演算-は、演算+におけるx2の逆元を-x2としたとき、x1-x2=x1+(-x2)と定義される演算である。
【００４１】
上記条件を満たす公開鍵暗号方式と関数(f,g)の例として、RSA暗号や楕円ElGamal暗号とそれに付随する関数(f,g)を挙げたが、これらの暗号に限られるものでなく、第一実施形態のメッセージ送受信システムの構成に、上記以外の公開鍵暗号方式とそれに付随する関数(f,g)を用いることができる。
【００４２】
［システム構成］
第一実施形態のメッセージ送受信システムは、図１に例示するように、サーバ１００と、n（≧2）台の端末２００を含む。この実施形態では、サーバ１００および端末２００1、…、端末２００nはそれぞれネットワーク３００へ接続される。ネットワーク３００は、サーバ１００、端末２００1、…、端末２００nがそれぞれ相互に通信可能なように構成されたネットワークであればよい。ネットワーク３００には、例えばインターネットなどを用いることができる。
【００４３】
サーバ１００は、図２に例示するように、記録部１１０と、ルーム生成部１２０と、鍵生成部１３０と、インデックス検索部１４０を含む。端末２００i(1≦i≦n)は、図３に例示するように、記録部２１０と、ルーム生成要求送信部２２０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含む。このサーバ１００および端末２００1、…、端末２００nが、図４から図９に例示する各ステップの処理を行うことにより実施形態のメッセージ送受信方法が実現される。
【００４４】
サーバ１００および端末２００iは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。各装置は、例えば、中央演算処理装置の制御のもとで各処理を実行する。各装置に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。各装置が備える各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００４５】
サーバ１００が備える記録部１１０および端末２００iが備える記録部２１０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。各記録部は秘密情報を記憶するため、（例えば、SIMカードなどのように）耐タンパ性を有する記憶装置であることが望ましい。
【００４６】
［システムセットアップ］
以下、サーバ１００を介してメッセージの送受信をする端末２００1、…、端末２００n（以下、グループともいう）に対して、当該グループで共有するメッセージを管理する単位をルームと呼ぶことにする。具体的には、サーバ１００の記録部１１０に当該グループで共有するメッセージを登録する記録領域（つまり、物理的なルーム）が確保される。このルームを識別するための識別子をルーム識別子という。
【００４７】
ここでは、ルーム識別子roomID、公開鍵pkroomID、秘密鍵skroomID、セッション鍵R1がグループに属する端末２００1、…、端末２００n間で共有される。図４を参照してシステムセットアップのフローについて説明する。
【００４８】
なお、端末２００iとサーバ１００との間は、例えば、TLS通信のように暗号化通信を用いてもよい。また、端末２００iは、パソコンやスマートフォンなどを想定しているが、これらに限られるものでなく、ユーザがメッセージを送受信するのに利用できるものであれば何でもよい。
【００４９】
ルーム生成の要求を出す端末２００iのことを代表端末ということにする。代表端末は端末２００1、…、端末２００nの中から任意に選定してよい。そこで、以下では端末２００1を代表端末とする。また、代表端末２００1以外の端末２００j(2≦j≦n)のことを一般端末２００jということにする。
【００５０】
代表端末２００1のルーム生成要求送信部２２０は、サーバ１００に対してルーム生成要求を送信する（Ｓ４−１０）。サーバ１００が当該要求を受信すると、サーバ１００のルーム生成部１２０は、ルーム識別子roomIDで識別されるルームを生成する（Ｓ４−２０）。その際、サーバ１００の鍵生成部１３０は、鍵生成アルゴリズムにより、roomIDで識別されるルームで暗号化・復号に用いる公開鍵pkroomIDと秘密鍵skroomIDを生成する（Ｓ４−３０）。なお、鍵生成アルゴリズム実行時に同時に平文空間Mpkが定まる。また、公開鍵pkroomIDと秘密鍵skroomIDを生成する公開鍵暗号アルゴリズム(Gen, Enc, Dec)は先述の条件（式(1)）を満たす関数(f,g)が存在すれば任意のアルゴリズムを用いることができる。サーバ１００は、ルーム識別子roomID、公開鍵pkroomID、秘密鍵skroomIDを記録部１１０に記録し、代表端末２００1にこれらのデータを送信する（Ｓ４−４０）。
【００５１】
なお、Ｓ４−１０〜Ｓ４−４０の処理は、次のようなフローで処理してもよい。ルーム生成部１２０がルーム生成要求に従いルームを生成、代表端末２００1にルーム識別子roomIDを送信する。その後、代表端末２００1がルーム識別子roomIDとともに鍵生成要求をサーバ１００に送信、鍵生成部１３０がroomIDで識別されるルーム用の公開鍵pkroomIDと秘密鍵skroomIDを生成、代表端末２００1に公開鍵pkroomIDと秘密鍵skroomIDを送信する。
【００５２】
一般端末２００jは、代表端末２００1からルームへの招待を示すルーム識別子roomIDを受信すると（Ｓ４−５０）、サーバ１００にルーム識別子roomIDを送信し（Ｓ４−５５）、公開鍵pkroomIDと秘密鍵skroomIDを受信する（Ｓ４−６０）。
【００５３】
各端末２００iは、ルーム識別子roomID、公開鍵pkroomID、秘密鍵skroomIDを記録部２１０に記録する。
【００５４】
また、各端末２００iは、セッション鍵R1を共有し、記録部２１０に記録する（Ｓ４−７０）。共有の方法については、例えば、非特許文献２に記載の技術を用いればよい。なお、セッション鍵R1はサーバ１００に対して秘匿化されているものとする。
【００５５】
［検索用秘密鍵の共有］
ここでは、ある端末２００i_0(1≦i0≦n)が生成した検索用秘密鍵SearchKeyがサーバ１００を介してグループに属するすべての端末２００iの間で共有される。図５を参照して検索用秘密鍵SearchKeyの共有のフローについて説明する。
【００５６】
なお、検索用秘密鍵SearchKeyを生成する端末２００i_0は、代表端末２００1であっても一般端末２００jであっても構わない。また、セッション経過に伴い途中で検索用秘密鍵SearchKeyを生成する端末２００i_0がグループから離脱することもありうる。この場合、グループに属するその他の端末２００i_1(i1はi0と異なる1以上n以下の整数)が検索用秘密鍵SearchKeyを生成する役割を引き継ぐものとする。つまり、検索用秘密鍵SearchKeyの生成は、現在グループに参加している端末２００iのいずれかが行うものとする。
【００５７】
端末２００i_0の検索用秘密鍵生成部２３０は、ルーム識別子共有後、ランダムに選択した平文空間Mpkの元rを検索用秘密鍵SearchKeyとして生成する（Ｓ５−１０）。つまり、SearchKey=rとなる。なお、rのことを乱数という。この検索用秘密鍵SearchKeyは、ルーム毎に生成されるものである。端末２００i_0は、検索用秘密鍵SearchKeyを記録部２１０に記録する。
【００５８】
端末２００i_0の検索用秘密鍵暗号化部２３３は、暗号化検索用秘密鍵CipherKey←R Enc(pkroomID, f(SearchKey, R1))を生成し（Ｓ５−２０）、暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDとともにサーバ１００に送信する（Ｓ５−３０）。サーバ１００は、受信した暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDと対応付けて記録部１１０に記録する。
【００５９】
端末２００i_0以外の端末２００i_1は、Ｓ４−５０で受信したルーム識別子roomIDをサーバ１００に送信し（Ｓ５−４０）、サーバ１００から暗号化検索用秘密鍵CipherKeyを受信する（Ｓ５−５０）。
【００６０】
Ｓ５−１０からＳ５−３０の処理は、代表端末２００1がＳ４−５０において一般端末２００jとルーム識別子roomIDを共有した後、いつ実行してもよい。したがって、端末２００i_0以外の端末２００i_1は、Ｓ５−４０の暗号化検索用秘密鍵CipherKeyの取得要求をサーバ１００にいつ送信してもよい。例えば、代表端末２００1からルームへの招待を受けた直後でなく、招待後初めてログインする際でもよい。
【００６１】
端末２００i_1の暗号化検索用秘密鍵復号部２３５は、Temp=Dec(skroomID, CipherKey)を計算、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(Temp, R1)を計算、検索用秘密鍵SearchKeyを復号する（Ｓ５−６０）。関数(f,g)が先述の条件（式(1)）を満たすことより、検索用秘密鍵SearchKeyを得ることができる。端末２００i_1は、Ｓ５−６０で得た検索用秘密鍵SearchKeyを記録部２１０に記録する。
【００６２】
端末２００i_0の検索用秘密鍵生成部２３０は、ルーム識別子共有後、検索用秘密鍵生成のため最初の乱数生成（つまり、平文空間Mpkの元rのランダム選択）を実行するが、後ほど詳述するように、以降は検索用秘密鍵更新のため、定期的に乱数を生成し、その都度検索用秘密鍵暗号化部２３３は、検索用秘密鍵から暗号化検索用秘密鍵を生成し、暗号化検索用秘密鍵をサーバ１００に送信する。また、端末２００i_1は更新された暗号化検索用秘密鍵をサーバ１００から適時に取得し、復号することで検索用秘密鍵を取得する。つまり、端末２００iの記録部２１０には、複数の検索用秘密鍵が記録されることになる。以下では、ルーム識別子共有後最初に生成される検索用秘密鍵を第一世代検索用秘密鍵SearchKey1、以降定期的に生成される検索用秘密鍵を順に第二世代検索用秘密鍵SearchKey2、第三世代検索用秘密鍵SearchKey3、…ということにする。また、検索用秘密鍵SearchKeyの中で最も世代が新しいものを最新検索用秘密鍵ということにする。
【００６３】
［暗号化メッセージの送信］
ここでは、端末２００iがルーム識別子roomIDで管理されるルームにメッセージを送信する。その際、メッセージは暗号化される。暗号化したメッセージ（暗号化メッセージ）はルーム識別子roomIDを有するルームと対応付けられてサーバ１００の記録部１１０に記録されるとともに、後ほど暗号化したままで検索ができるよう、検索に用いるインデックスの集合（インデックス集合）とメッセージIDの組も記録される。図６を参照して端末２００iによるメッセージの送信のフローについて説明する。
【００６４】
端末２００iのメッセージ暗号化部２４０は、グループ内で共有したいメッセージm1を暗号化し、暗号化メッセージEnc(m1)を生成する（Ｓ６−１０）。ここで、メッセージの暗号化に用いる鍵は、サーバ１００に秘匿化されている鍵であれば、共通鍵暗号アルゴリズムで生成されるものであっても、公開鍵暗号アルゴリズムで生成されるものであっても構わない。なお、当該鍵はグループ内の端末２００i間で共有されているものとする。また、メッセージを送信する端末２００iは、グループに属する任意の端末である。
【００６５】
メッセージm1を暗号化する際、端末２００iのメッセージID生成部２４３は、暗号化したメッセージEnc(m1)をルーム識別子roomIDで識別されるルーム内で一意に識別するためのメッセージ識別子IDm_1をあわせて生成する（Ｓ６−１５）。サーバ１００に対してメッセージm1を秘匿化したままにする、つまりEnc(m1)をサーバ１００に送信し記録部１１０に記録するので、メッセージ識別子IDm_1を生成する関数は逆像計算が困難である（メッセージ識別子IDm_1からメッセージm1が容易に推測できない）関数であることが好ましい。
【００６６】
更に、メッセージm1を暗号化する際、端末２００iのインデックス生成部２４５は、暗号化したメッセージEnc(m1)を検索するために用いるインデックスをあわせて生成する（Ｓ６−２０）。検索可能な文字列長については上限を設けても、設けなくてもよい。以下では、検索可能な文字列長の上限が定められているものとし、その値をLとし説明する。
【００６７】
以下、インデックスの生成方法について説明する（図７参照）。インデックスの生成では関数Gを用いる。関数Gは、任意長の文字列を入力とし、入力文字列に依存する濃度を有する文字列の集合（文字列集合）を出力する関数とする。なお、関数Gの入力がメッセージm1である場合、関数Gの出力である文字列集合のことをメッセージm1に関係する情報といい、G(m1)={s1, s2,.., sq,..}と表すことにする。このような関数Gの例としては、メッセージm1のメタ情報を出力する関数、メッセージm1内に含まれる文字列を出力する関数、Nグラム・インデキシングを活用したメッセージm1内の連続するN文字からなる文字列すべてを出力する関数などがある。Nグラム・インデキシングについては、参考文献１に詳しい。
（参考文献１：北研二，津田和彦，獅々堀正幹，“情報検索アルゴリズム”，共立出版，2002年）
【００６８】
ここでは、メッセージm1の文字列長をlengthm_1、P=min{L, lengthm_1}とし、i=1,..,Pに対して、次の処理を行い、文字列集合G(m1)を生成する。
【００６９】
インデックス生成部２４５は、メッセージm1内の連続するi個の文字からなる文字列（つまり、長さiの文字列）をすべて列挙する（Ｓ６−２０−１）。これを文字列集合{s1(1), s2(1),.., sj(i),..}(ただし、j=1, 2,.., lengthm_1-i+1)とする。文字列集合G(m1)={s1(1), s2(1),.., sj(i),..}は、メッセージm1に関係する情報である。
【００７０】
なお、メッセージ全体から当該文字列を列挙してもよいし、メッセージを文節ごとに区切り、各文節から当該文字列を列挙してもよい。また、列挙の方法については、例えば、メッセージや文節の左端からとってきた連続するi個の文字からなる文字列をs1(i)、左端から右に１つシフトして得た連続するi個の文字からなる文字列をs2(i)とするとよい。ただし、インデックスを用いたメッセージ検索に影響はないので、どのような列挙方法を用いてもよい。
【００７１】
次に、インデックス生成部２４５は、文字列集合G(m1)={s1(1), s2(1),.., sj(i),..}と記録部２１０から読み出した最新検索用秘密鍵SearchKeyを用いて、j=1, 2,.., lengthm_1-i+1に対し、インデックスを次式で計算する（Ｓ６−２０−２）。上述した通り、記録部２１０には一般に複数の検索用秘密鍵が記録されているが、ここで読み出す検索用秘密鍵SearchKeyは、最も新しい検索用秘密鍵、最新検索用秘密鍵であるとする。つまり、最新検索用秘密鍵SearchKeyを用いて各文字列sj(i)に対して、インデックスIndexj(i)を計算する。
【００７２】
【数５】
0006770075.tif 000006
【００７３】
なお、インデックス集合の各要素は長さL以下の文字列であるとする。式(2)で得られるP/2(2lengthm_1-P+1)個のインデックスを要素とするインデックス集合Indは次式のようにとなる。
【００７４】
【数６】
0006770075.tif 000007
【００７５】
例えば、検索可能な文字列長の上限Lを3以上の整数、メッセージm1を３文字からなるメッセージ“あいう”であるとすると、以下の6個のインデックスが計算される。
【００７６】
【数７】
0006770075.tif 000008
【００７７】
なお、一般には、メッセージm1に関係する情報G(m1)={s1, s2,.., sq,..}から、インデックス集合Ind={Index1, Index2,.., Indexq,..}は、各要素を次式で計算して求めることができる。
【００７８】
【数８】
0006770075.tif 000009
【００７９】
端末２００iは、暗号化メッセージEnc(m1)とともに、次式で表されるインデックス集合Indの各要素とメッセージ識別子の組をサーバ１００に送信する（Ｓ６−３０）。
【００８０】
【数９】
0006770075.tif 000010
【００８１】
サーバ１００は、暗号化メッセージEnc(m1)、各インデックスとメッセージ識別子の組(Index1(1),.., Indexj(i),.., Indexlengthm_1(P), IDm_1)を記録部１１０に記録する。
【００８２】
なお、検索可能な文字列長の上限が定めない場合、L=+∞と表現することにすると、P=lengthm_1となり、メッセージm1に対し、上記と同様の方法でインデックス集合Ind
【００８３】
【数１０】
0006770075.tif 000011
【００８４】
を生成することができる。
【００８５】
［暗号化メッセージの検索］
ここでは、端末２００iがルーム識別子roomIDを有するルームで管理されるメッセージを検索する。検索キーワードとなる文字列（以下、メッセージ検索用文字列という）からクエリを生成し、暗号化したままメッセージの検索を行う。図８を参照して端末２００iによるメッセージ検索のフローについて説明する。
【００８６】
端末２００iがルームに蓄積された暗号化メッセージから、メッセージ検索用文字列m’に合致するメッセージの検索を行うとする。端末２００iのクエリ生成部２５０は、記録部２１０から一般に複数の検索用秘密鍵を読出し、各検索用秘密鍵SearchKeyに対してメッセージ検索に用いるクエリQueryを、Query=CRHF(F(m’, SearchKey))として計算し、これらのクエリを要素とするクエリ集合を生成する（Ｓ７−１０）。T1、T2を検索用秘密鍵の世代を示す１以上の整数とし、T1≦i≦T2なる整数iについて第i世代検索用秘密鍵SearchKeyiについてクエリQueryi=CRHF(F(m’, SearchKeyi))を計算し、クエリ集合{QueryT_1,
QueryT_1+1,.., QueryT_2}を生成する。
【００８７】
例えば、現在からある過去の時点の間で送信されたメッセージに対して検索を行う場合、その間で更新された検索用秘密鍵に対してのみクエリを生成すればよい。つまり、必ずしも過去すべての検索用秘密鍵に対するクエリを生成する（T1=1である）必要はない。
【００８８】
なお、検索可能な文字列長の上限Lが定められている場合、最初にメッセージ検索用文字列m’の長さをLと比較し、Lよりも大きければエラーを返すようにしてもよい。このようにすることにより処理の効率化が図れる。
【００８９】
端末２００iのクエリ生成部２５０は、クエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}をサーバ１００に送信する（Ｓ７−２０）。
【００９０】
サーバ１００のインデックス検索部１４０は、記録部１１０に記録しているインデックス集合の各要素とメッセージ識別子の組(Index1(1),.., Indexj(i),.., IDm_1)のうち、受信したクエリ集合{QueryT_1, QueryT_1+1,.., QueryT_2}の各要素QueryiとインデックスIndexj(i)が一致するインデックスとメッセージ識別子の組(Indexj(i), IDm_1)をすべて抽出する（Ｓ７−３０）。サーバ１００のインデックス検索部１４０は、端末２００iに抽出したメッセージ識別子IDm_1に対応する暗号化メッセージEnc(m1)を送信する（Ｓ７−４０）。
【００９１】
端末２００iの暗号化メッセージ復号部２５５は、Ｓ７−４０で受信した暗号化メッセージ暗号化メッセージEnc(m1)を復号して、メッセージm1を検索結果として画面に表示する（Ｓ７−５０）。
【００９２】
なお、Ｓ７−４０で抽出したメッセージ識別子IDm_1に対応する暗号化メッセージEnc(m1)を送信する代わりに、メッセージ識別子IDm_1を送信してもよい。この場合、端末２００iは、受信したメッセージ識別子IDm_1をサーバ１００に送信し、当該メッセージ識別子IDm_1に対応する暗号化メッセージEnc(m1)をサーバ１００から取得し、暗号化メッセージ復号部２５５を用いて暗号化メッセージEnc(m1)を復号して、メッセージm1を検索結果として画面に表示することになる。
【００９３】
［検索用秘密鍵の更新］
ここでは、端末２００i_0が検索用秘密鍵SearchKeyを更新する。検索用秘密鍵SearchKeyの更新間隔はサーバ１００の記録部１１０に記録されているインデックスとそれに紐づくメッセージ識別子の個数（分布）からインデックスやメッセージ識別子に対応するメッセージを推測されることを防げる程度の頻度で定期的に行うとよい。例えば、1ヵ月毎、半年毎など考えられるが、更新間隔が短い方がより推測されることを防ぐことができる。図９を参照して端末２００i_0による検索用秘密鍵の更新のフローについて説明する。
【００９４】
端末２００i_0の検索用秘密鍵生成部２３０は、事前に設定された更新間隔が経過したことを検知すると、ランダムに選択した平文空間Mpkの元r’を更新後の検索用秘密鍵として生成する（Ｓ８−１０）。つまり、SearchKey=r’とする。更新した検索用秘密鍵をグループ内の端末２００i_1と共有するため、端末２００i_0の検索用秘密鍵暗号化部２３３は、暗号化検索用秘密鍵CipherKey←REnc(pkroomID,f(SearchKey, R1))を計算し（Ｓ８−２０）、暗号化検索用秘密鍵CipherKeyをサーバ１００に送信する（Ｓ８−３０）。サーバ１００は、受信した暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDと対応付けて記録部１１０に記録する。なお、サーバ１００は以前の暗号化検索用秘密鍵 CipherKeyも記録部１１０に記録しておく。端末２００i_1がサーバ１００から暗号化検索用秘密鍵CipherKeyを取得する場合（Ｓ８−４０）、過去の暗号化検索用秘密鍵{CipherKey1,.. ,CipherKeyi,..}も含め取得する（Ｓ８−５０）。ただし、暗号化検索用秘密鍵CipherKeyiは、第i世代検索用秘密鍵SearchKeyiから生成されたものを表す。
【００９５】
なお、過去の暗号化検索用秘密鍵すべてを取得する代わりに、最新検索用秘密鍵に対応する暗号化検索用秘密鍵のみを取得するようにしてもよい。このようにすることにより処理の効率化を図ることができる。
【００９６】
端末２００i_1が検索用秘密鍵の更新があったことを知るためには、端末２００i_0と更新間隔を共有しておいてもよいし、端末２００i_0が更新したことを端末２００i_1に通知してもよいし、端末２００i_1が自ら定期的に暗号化検索用秘密鍵を取得するようにしてもよい。
【００９７】
端末２００i_1の暗号化検索用秘密鍵復号部２３５は、取得した暗号化検索用秘密鍵Cip
herKey に対してTemp=Dec(skroomID, CipherKey)を計算、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(Temp, R1)を生成する（Ｓ８−６０）。この処理は、取得した暗号化検索用秘密鍵の数だけ繰り返される。
【００９８】
本実施形態の説明では、代表端末２００1と一般端末２００jはその役割が異なる。つまりルーム生成要求をサーバ１００に送信する役割を負っているか否かだけであるが、これらの端末の構成については図３に示すように同質なものとして説明した。しかし、必ずしもこのように構成する必要はない。つまり、代表端末２００1は、記録部２１０と、ルーム生成要求送信部２２０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含むものとして構成する一方、一般端末２００jは、記録部２１０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含むものとして構成する。
【００９９】
本実施形態によると、端末２００iは検索キーワードと端末間で共有された検索用秘密鍵から秘匿化されたクエリを生成し、サーバ１００に送信、サーバ１００はメッセージに関係する情報と検索用秘密鍵から生成される、秘匿化されたインデックスと受信したクエリを用いてメッセージを検索する。これによりサーバ１００はメッセージを暗号化したまま検索することができる。また、検索用秘密鍵を定期的に更新することにより、同じ検索キーワードに対して異なるクエリが生成されることになり、検索内容や検索結果が推測されるのを防ぐことができる。
【０１００】
＜第二実施形態＞
第一実施形態のメッセージ送受信システムでは公開鍵暗号方式を用いたが、本実施形態のメッセージ送受信システムは、公開鍵暗号方式を用いない。ただし、ここでは、平文空間Mpkの代わりに鍵空間KEYを定義し、関数f:KEY×KEY1→KEYと関数g:KEY×KEY1→KEYは第一実施形態における関数(f,g)が満たす条件（式(1)）と同一の条件を満たすものとする。
【０１０１】
このとき、例えば、KEY1=KEYであり、KEYに乗法群または加法群の構造が入っていれば、任意の(K, K1)∈KEY×KEYに対し、式(1)を満たす(f,g)の例として、以下の関数の組を挙げることができる。
【０１０２】
【数１１】
0006770075.tif 000012
【０１０３】
なお、演算/は、鍵空間KEYに乗法群としての構造が入っているときの乗法を・とし、この演算・におけるx2の逆元をx2-1としたとき、x1/x2=x1・x2-1と定義される演算である。また、演算-は、鍵空間KEYに加法群としての構造が入っているときの加法を+し、この演算+におけるx2の逆元を-x2としたとき、x1-x2=x1+(-x2)と定義される演算である。
【０１０４】
［システム構成］
第二実施形態のメッセージ送受信システムは、第一実施形態のメッセージ送受信システムと同様、サーバ５００と、n（≧2）台の端末６００を含む。また、第一実施形態と同様、サーバ５００および端末６００1、…、端末６００nはそれぞれネットワーク３００へ接続される。
【０１０５】
サーバ５００は、図１０に例示するように、記録部１１０と、ルーム生成部１２０と、インデックス検索部１４０を含む。つまり、サーバ５００は、鍵生成部１３０を有しない点でサーバ１００と異なる。端末６００i(1≦i≦n)は、図１１に例示するように、記録部２１０と、ルーム生成要求送信部２２０と、検索用秘密鍵生成部２３０と、検索用秘密鍵暗号化部６３３と、暗号化検索用秘密鍵復号部６３５と、メッセージ暗号化部２４０と、メッセージID生成部２４３と、インデックス生成部２４５と、クエリ生成部２５０と、暗号化メッセージ復号部２５５を含む。つまり、端末６００iは、検索用秘密鍵暗号化部２３３と、暗号化検索用秘密鍵復号部２３５の代わりに、検索用秘密鍵暗号化部６３３と、暗号化検索用秘密鍵復号部６３５を有する点で端末２００iと異なる。
【０１０６】
第一実施形態と第二実施形態のメッセージ送受信システムは公開鍵暗号アルゴリズムを用いるか用いないかの点においてのみ異なる。その結果、システムセットアップと検索用秘密鍵の共有のフローに違いが出てくる。そこで、この２つのフローについて以下では説明する。
【０１０７】
［システムセットアップ］
ここでは、ルーム識別子roomID、セッション鍵R1がグループに属する端末６００1、…、端末６００n間で共有される。図１２を参照してシステムセットアップのフローについて説明する。
【０１０８】
代表端末６００1のルーム生成要求送信部２２０は、サーバ５００に対してルーム生成要求を送信する（Ｓ４−１０）。サーバ５００が当該要求を受信すると、サーバ５００のルーム生成部１２０は、ルーム識別子roomIDで識別されるルームを生成する（Ｓ４−２０）。サーバ５００は、ルーム識別子roomIDを記録部１１０に記録し、代表端末６００1にルーム識別子roomIDを送信する（Ｓ４−４２）。
【０１０９】
一般端末６００jは、代表端末６００1からルームへの招待を示すルーム識別子roomIDを受信する（Ｓ４−５０）。
【０１１０】
各端末６００iは、ルーム識別子roomIDを記録部２１０に記録する。
【０１１１】
また、各端末６００iは、セッション鍵R1を共有し、記録部２１０に記録する（Ｓ４−７０）。なお、セッション鍵R1がサーバ５００に対して秘匿化されているのも、第一実施形態と同様である。
【０１１２】
［検索用秘密鍵の共有］
ここでは、第一実施形態と同様、ある端末６００i_0(1≦i0≦n)が生成した検索用秘密鍵SearchKeyがサーバ５００を介してグループに属するすべての端末６００iの間で共有される。図５を参照して検索用秘密鍵SearchKeyの共有のフローについて説明する。
【０１１３】
端末６００i_0の検索用秘密鍵生成部２３０は、ルーム識別子共有後、ランダムに選択した鍵空間KEYの元rを検索用秘密鍵SearchKeyとして生成する（Ｓ５−１０）。つまり、SearchKey=rとなる。なお、rのことを乱数という。この検索用秘密鍵SearchKeyは、第一実施形態同様、ルーム毎に生成されるものである。端末６００i_0は、検索用秘密鍵SearchKeyを記録部２１０に記録する。
【０１１４】
端末６００i_0の検索用秘密鍵暗号化部６３３は、暗号化検索用秘密鍵CipherKey=f(SearchKey, R1)を生成し（Ｓ５−２０）、暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDとともにサーバ５００に送信する（Ｓ５−３０）。つまり、暗号化検索用秘密鍵の生成に公開鍵を用いない点でのみ端末６００i_0は端末２００i_0と異なる。サーバ５００は、受信した暗号化検索用秘密鍵CipherKeyをルーム識別子roomIDと対応付けて記録部１１０に記録する。
【０１１５】
端末６００i_1は、Ｓ４−５０で受信したルーム識別子roomIDをサーバ５００に送信し（Ｓ５−４０）、サーバ５００から暗号化検索用秘密鍵CipherKeyを受信する（Ｓ５−５０）。
【０１１６】
端末６００i_1の暗号化検索用秘密鍵復号部６３５は、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(CipherKey, R1)を計算、検索用秘密鍵SearchKeyを復号する（Ｓ５−６０）。関数(f,g)が先述の条件（式(1)）を満たすことより、検索用秘密鍵SearchKeyを得ることができる。端末６００i_1はＳ５−６０で得た検索用秘密鍵SearchKeyを記録部２１０に記録する。
【０１１７】
なお、検索用秘密鍵の更新においても、検索用秘密鍵暗号化部６３３及び暗号化検索用秘密鍵復号部６３５が公開鍵・秘密鍵を用いないのは、検索用秘密鍵の共有と同じである。つまり、検索用秘密鍵暗号化部６３３は、暗号化検索用秘密鍵をCipherKey=f(SearchKey, R1)として生成し、暗号化検索用秘密鍵復号部６３５は、記録部２１０から読み出したセッション鍵R1を用いてSearchKey=g(CipherKey, R1)を計算、検索用秘密鍵SearchKeyを復号する。
【０１１８】
本実施形態によると、第一実施形態と同様、サーバ５００はメッセージを暗号化したまま検索することができる。また、検索用秘密鍵を定期的に更新することにより、同じ検索キーワードに対して異なるクエリが生成されることになり、検索内容や検索結果が推測されることを防ぐことができる。
【０１１９】
＜変形例＞
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１２０】
＜補記＞
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１２１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２２】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、
このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１２５】
上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。
【符号の説明】
【０１２６】
１００  サーバ
１１０  記録部
１２０  ルーム生成部
１３０  鍵生成部
１４０  インデックス検索部
２００  端末
２１０  記録部
２２０  ルーム生成要求送信部
２３０  検索用秘密鍵生成部
２３３  検索用秘密鍵暗号化部
２３５  暗号化検索用秘密鍵復号部
２４０  メッセージ暗号化部
２４３  メッセージID生成部
２４５  インデックス生成部
２５０  クエリ生成部
２５５  暗号化メッセージ復号部
３００  ネットワーク
５００  サーバ
６００  端末
６３３  検索用秘密鍵暗号化部
６３５  暗号化検索用秘密鍵復号部
【図１】
0006770075.tif 000017
【図２】
0006770075.tif 000018
【図３】
0006770075.tif 000019
【図４】
0006770075.tif 000020
【図５】
0006770075.tif 000021
【図６】
0006770075.tif 000022
【図７】
0006770075.tif 000023
【図８】
0006770075.tif 000024
【図９】
0006770075.tif 000025
【図１０】
0006770075.tif 000026
【図１１】
0006770075.tif 000027
【図１２】
0006770075.tif 000028