(57)【特許請求の範囲】
【請求項１】
クライアントに接続可能なサーバであって、前記サーバが保有する２以上の整数であるＮ個のメッセージのうち前記クライアントにより指定されたインデックスのメッセージを前記クライアントに取得させるサーバであって、
前記Ｎ個のメッセージのうち他と同一の内容のメッセージを除くことにより前記Ｎ個のメッセージを内容毎に１以上Ｎ未満の整数であるＭ個の分類済メッセージに分類する分類部と、
前記Ｍ個の分類済メッセージのそれぞれを暗号化するメッセージ暗号化部と、
前記Ｍ個の暗号化された分類済メッセージを前記クライアントへと供給するメッセージ供給部と、
前記クライアントにより指定されたインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、紛失通信により前記クライアントに送信する鍵送信部と、
を有するサーバ。
【請求項２】
前記クライアントは、
指定したインデックスのメッセージに対応する前記メッセージ鍵を紛失通信により前記サーバから受信する鍵受信部と、
受信した前記メッセージ鍵により、前記サーバから供給されたＭ個の暗号化された分類済メッセージのうち対応する分類済メッセージを復号するメッセージ復号部と、
を有する請求項１に記載のサーバ。
【請求項３】
前記鍵送信部は、前記Ｍ個の暗号化された分類済メッセージのうち前記クライアントに送信した前記メッセージ鍵により復号できる前記分類済メッセージを指し示すポインタを、前記メッセージ鍵とともに紛失通信により前記クライアントに送信する
請求項２に記載のサーバ。
【請求項４】
前記鍵受信部は、前記メッセージ鍵とともに前記ポインタを受信し、
前記メッセージ復号部は、受信した前記メッセージ鍵により、前記ポインタにより指し示される前記分類済メッセージを復号する
請求項３に記載のサーバ。
【請求項５】
前記メッセージ供給部は、前記Ｍ個の暗号化された分類済メッセージをネットワークを介して前記クライアントに送信する
請求項１に記載のサーバ。
【請求項６】
前記メッセージ供給部は、前記Ｍ個の暗号化された分類済メッセージを、前記クライアントによるインデックスの指定に先立って前記クライアントに送信する
請求項５に記載のサーバ。
【請求項７】
前記メッセージ供給部は、前記Ｍ個の暗号化された分類済メッセージをデータサイズの小さい順に並べて前記クライアントに供給する
請求項１に記載のサーバ。
【請求項８】
前記メッセージ供給部は、前記Ｍ個の暗号化された分類済メッセージを、前記Ｎ個のメッセージの順次に対してランダム化した順序に並べて前記クライアントに供給する
請求項１に記載のサーバ。
【請求項９】
前記クライアントは、前記Ｍ個の暗号化された分類済メッセージを、インデックスの指定の前に予め記憶している分類済メッセージ記憶部を更に有する
請求項１に記載のサーバ。
【請求項１０】
請求項１から９の何れか１項に記載のサーバおよびクライアントを備えるシステム。
【請求項１１】
サーバに接続可能なクライアントであって、前記サーバが保有する２以上の整数であるＮ個のメッセージのうち指定するインデックスのメッセージを前記サーバから取得するクライアントであって、
前記サーバにおいて、前記Ｎ個のメッセージのうち他と同一の内容のメッセージを除くことにより前記Ｎ個のメッセージを内容毎に分類し、暗号化された、１以上Ｎ未満の整数であるＭ個の分類済メッセージを、前記サーバから取得するメッセージ取得部と、
前記指定したインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵と、前記Ｍ個の暗号化された分類済メッセージのうち前記メッセージ鍵により復号できる前記分類済メッセージを指し示すポインタと、を紛失通信により前記サーバから受信する鍵受信部と、
受信した前記メッセージ鍵により、前記Ｍ個の暗号化された分類済メッセージのうち前記ポインタにより指し示される前記分類済メッセージを復号するメッセージ復号部と、
を有するクライアント。
【請求項１２】
サーバが保有する２以上の整数であるＮ個のメッセージのうちクライアントにより指定されたインデックスのメッセージを前記クライアントに取得させる方法であって、
前記サーバが、
前記Ｎ個のメッセージのうち他と同一の内容のメッセージを除くことにより前記Ｎ個のメッセージを内容毎に１以上Ｎ未満の整数であるＭ個の分類済メッセージに分類する分類ステップと、
前記Ｍ個の分類済メッセージのそれぞれを暗号化するメッセージ暗号化ステップと、
前記Ｍ個の暗号化された分類済メッセージを前記クライアントへと供給するメッセージ供給ステップと、
前記クライアントにより指定されたインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、紛失通信により前記クライアントに送信する鍵送信ステップと、
を実行する方法。
【請求項１３】
前記クライアントが、
指定したインデックスのメッセージに対応する前記メッセージ鍵を紛失通信により前記サーバから受信する鍵受信ステップと、
受信した前記メッセージ鍵により、前記サーバから供給されたＭ個の暗号化された分類済メッセージのうち対応する分類済メッセージを復号するメッセージ復号ステップと、
を実行する請求項１２に記載の方法。
【請求項１４】
コンピュータを請求項１から９の何れか１項に記載のサーバとして機能させるためのプログラム。
【請求項１５】
サーバが保有する２以上の整数であるＮ個のメッセージのうち指定したインデックスのメッセージを前記サーバから取得するクライアントとしてコンピュータを機能させるためのプログラムであって、前記コンピュータに、
前記Ｎ個のメッセージのうち他と同一の内容のメッセージを除くことにより前記Ｎ個のメッセージを内容毎に分類し、暗号化された１以上Ｎ未満の整数であるＭ個の分類済メッセージを、前記サーバから取得するメッセージ取得ステップと、
前記指定したインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵と、前記Ｍ個の暗号化された分類済メッセージのうち前記メッセージ鍵により復号できる前記分類済メッセージを指し示すポインタと、を紛失通信により前記サーバから受信する鍵受信ステップと、
受信した前記メッセージ鍵により、前記Ｍ個の暗号化された分類済メッセージのうち前記ポインタにより指し示される前記分類済メッセージを復号するメッセージ復号ステップと、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、紛失通信によりメッセージを送信するシステム、サーバ、クライアント、方法およびプログラムに関する。
【背景技術】
【０００２】
紛失通信と呼ばれるプロトコルが知られている（例えば、非特許文献１参照）。紛失通信は、指定したインデックス以外のメッセージを受信側装置が取得できず且つ指定されたインデックスを送信側装置に特定させずに、送信側装置が保有するＮ個のメッセージ（Ｘ１、…、ＸＮ）のうち受信側装置が指定したインデックスのメッセージを送信側装置から受信側装置へと送信するプロトコルである。
［先行技術文献］
［非特許文献］
非特許文献１  Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Volume 28, Issue 6, pg. 637-647, 1985
【発明の概要】
【発明が解決しようとする課題】
【０００３】
このような紛失通信での通信量は、送信側装置から受信側装置へと暗号化したＮ個のメッセージを送信することから、Ｎ個のメッセージの合計データ量にほぼ比例した量となる。従って、紛失通信では、Ｎ個のメッセージの合計データ量が大きいほど、通信量が多くなってしまう。
【０００４】
また、Ｎ個のメッセージの中には、内容が重複したメッセージが含まれている場合もある。しかし、紛失通信では、重複したメッセージのそれぞれを送信側装置から受信側装置へと送信しなければならなく、重複したメッセージが多い場合には通信の冗長性が高くなってしまっていた。
【課題を解決するための手段】
【０００５】
本発明の第１の態様においては、ライアントに接続可能なサーバであって、前記サーバが保有する２以上の整数であるＮ個のメッセージのうち前記クライアントにより指定されたインデックスのメッセージを前記クライアントに取得させるサーバであって、前記Ｎ個のメッセージを内容毎にＭ個の分類済メッセージに分類する分類部と、前記Ｍ個の分類済メッセージのそれぞれを暗号化するメッセージ暗号化部と、前記Ｍ個の暗号化された分類済メッセージを前記クライアントへと供給するメッセージ供給部と、前記クライアントにより指定されたインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、紛失通信により前記クライアントに送信する鍵送信部と、を有するサーバを提供する。また、このようなサーバおよびクライアントを備えるシステム、このシステムに備えられるクライアント、このようなサーバおよびクライアントとしてコンピュータを機能させるためのプログラム、並びに、このようなシステムに関連する方法を提供する。
【０００６】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではない。また、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【図面の簡単な説明】
【０００７】
【図１】本実施形態に係る情報提供システム１０の機能ブロック図を示す。
【図２】本実施形態に係る情報提供システム１０におけるサーバ２０からクライアント３０へのメッセージの受け渡し処理のフローを示す。
【図３】サーバ２０とクライアント３０との間におけるメッセージ鍵の紛失通信による受け渡し処理のフローを示す。
【図４】図３に続くフローを示す。
【図５】図４に続くフローを示す。
【図６】図６は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【発明を実施するための形態】
【０００８】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００９】
図１は、本実施形態に係る情報提供システム１０の機能ブロック図を示す。本実施形態に係る情報提供システム１０は、サーバ２０と、クライアント３０とを備える。
【００１０】
本実施形態に係る情報提供システム１０は、サーバ２０が保有するＮ個のメッセージのうち、クライアント３０により指定されたインデックスのメッセージをクライアント３０に取得させる。なお、Ｎは、２以上の整数である。
【００１１】
ここで、Ｎ個のメッセージのそれぞれは、例えば、テキストデータ、画像データ、音楽データおよびプログラムデータ等のどのようなデータおよびファイル等であってもよい。Ｎ個のメッセージには、それぞれに固有のインデックスが付けられている。従って、情報提供システム１０では、１つのインデックスが指定されることにより、Ｎ個のメッセージのうちの１つのメッセージが特定される。
【００１２】
サーバ２０は、メッセージ記憶部４０と、分類部４２と、メッセージ暗号化部４４と、メッセージ供給部４６と、鍵送信部４８とを有する。また、クライアント３０は、メッセージ取得部５２と、分類済メッセージ記憶部５４と、鍵受信部５６と、メッセージ復号部５８とを有する。
【００１３】
サーバ２０のメッセージ記憶部４０は、Ｎ個のメッセージを記憶する。Ｎ個のメッセージは、一例として、サーバ２０の管理者等により書き込まれる。
【００１４】
サーバ２０の分類部４２は、Ｎ個のメッセージを内容毎にＭ個の分類済メッセージに分類する。ここで、Ｍは、１以上Ｎ以下の整数である。分類部４２は、一例として、メッセージの重複を無くすように、Ｎ個のメッセージのうち他と同一の内容（例えば同一データ）のメッセージを削除してＭ個の分類済メッセージを生成する。
【００１５】
また、この場合において、分類部４２は、Ｎ個のメッセージのそれぞれが、Ｍ個の分類済メッセージの何れに対応するかを指し示すポインタも生成する。分類部４２は、Ｍ個の分類済メッセージをメッセージ暗号化部４４へと受け渡す。また、分類部４２は、ポインタを鍵送信部４８へと受け渡す。
【００１６】
サーバ２０のメッセージ暗号化部４４は、Ｍ個の分類済メッセージのそれぞれを暗号化する。メッセージ暗号化部４４は、Ｍ個の暗号化された分類済メッセージをメッセージ供給部４６へと受け渡す。また、メッセージ暗号化部４４は、Ｍ個の分類済メッセージのそれぞれを復号するためのＭ個のメッセージ鍵を鍵送信部４８へと受け渡す。
【００１７】
サーバ２０のメッセージ供給部４６は、Ｍ個の暗号化された分類済メッセージをクライアント３０へと供給する。メッセージ供給部４６は、一例として、クライアント３０によるインデックスの指定に先立って（オフラインで）、Ｍ個の暗号化された分類済メッセージをクライアント３０へと供給する。また、メッセージ供給部４６は、クライアント３０によるインデックスの指定がされたことに応じて（オンラインで）、Ｍ個の暗号化された分類済メッセージをクライアント３０へと供給してもよい。
【００１８】
クライアント３０のメッセージ取得部５２は、サーバ２０のメッセージ供給部４６から供給されたＭ個の暗号化された分類済メッセージを取得する。メッセージ取得部５２は、一例として、ユーザ等からのインデックスの指定に先立って、Ｍ個の暗号化された分類済メッセージを取得する。また、メッセージ取得部５２は、一例として、ユーザ等によるインデックスの指定がされたことに応じて、Ｍ個の暗号化された分類済メッセージを取得してもよい。
【００１９】
クライアント３０の分類済メッセージ記憶部５４は、メッセージ取得部５２により取得されたＭ個の暗号化された分類済メッセージを記憶する。クライアント３０は、インデックスの指定がされたことに応じてＭ個の暗号化された分類済メッセージを取得する場合には、分類済メッセージ記憶部５４を有さない構成であってもよい。
【００２０】
サーバ２０の鍵送信部４８は、Ｍ個のメッセージ鍵、および、Ｎ個のメッセージのそれぞれがＭ個の分類済メッセージの何れに対応するかを指し示すポインタを受け取る。また、クライアント３０の鍵受信部５６は、ユーザ等から、Ｎ個のメッセージのうちの取得を希望するメッセージのインデックスの指定を受ける。
【００２１】
そして、サーバ２０の鍵送信部４８は、Ｍ個のメッセージ鍵のうちクライアント３０により指定されたインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、紛失通信によりクライアント３０に送信する。また、クライアント３０の鍵受信部５６は、指定したインデックスのメッセージに対応するメッセージ鍵を紛失通信によりサーバ２０から受信する。
【００２２】
即ち、鍵送信部４８および鍵受信部５６は、指定されたインデックスに対応するメッセージ鍵以外のメッセージ鍵をクライアント３０が取得できず且つ指定されたインデックスをサーバ２０に特定させないプロトコルで、対応するメッセージ鍵をサーバ２０からクライアント３０へと受け渡す。なお、紛失通信での具体的な処理方法の一例については詳細を後述する。
【００２３】
また、鍵送信部４８は、メッセージ鍵とともに、指定されたインデックスに対応する分類済メッセージを指し示すポインタを紛失通信によりクライアント３０に送信してもよい。この場合において、鍵送信部４８は、メッセージ鍵の一部にポインタを含めて送信してもよい。
【００２４】
そして、鍵受信部５６は、ポインタを、メッセージ鍵とともに紛失通信により受信する。これにより、クライアント３０は、受信したメッセージ鍵を用いて、Ｍ個の暗号化された分類済メッセージのうち何れを復号できるかを特定することができる。
【００２５】
メッセージ復号部５８は、鍵受信部５６が受信したメッセージ鍵により、サーバ２０から供給されたＭ個の暗号化された分類済メッセージのうち、指定されたインデックスのメッセージに対応する分類済メッセージを復号する。この場合において、メッセージ復号部５８は、鍵受信部５６がメッセージ鍵とともにポインタを受信していれば、受信したポインタに指し示された分類済メッセージを復号する。また、メッセージ復号部５８は、鍵受信部５６がポインタを受信していない場合においては、Ｍ個の分類済メッセージの全てについて復号処理を実行してみて、復号できた１つの分類済メッセージを取得してもよい。
【００２６】
このように復号した分類済メッセージは、サーバ２０が保有するＮ個のメッセージのうちの指定されたインデックスのメッセージと同一である。従って、情報提供システム１０は、指定されたインデックスのメッセージ以外のメッセージをクライアント３０が取得できず且つ指定されたインデックスをサーバ２０に特定させずに、指定したインデックスのメッセージをクライアント３０に取得させることができる。
【００２７】
図２は、本実施形態に係る情報提供システム１０におけるサーバ２０からクライアント３０へのメッセージの受け渡し処理のフローを示す。まず、サーバ２０は、Ｎ個のメッセージを保有している。本例においては、サーバ２０は、１〜Ｎのインデックスが付けられたＮ個のメッセージであるＸ１、Ｘ２、Ｘ３、…、Ｘｉ、…、ＸＮを保有している。なお、Ｘはメッセージを表し、Ｘの下付けの数字はメッセージのインデックスを表す。また、ｉは、１以上、Ｎ以下の任意の整数を表す。
【００２８】
ステップＳ１１において、サーバ２０の分類部４２は、Ｎ個のメッセージを内容毎にＭ個の分類済メッセージに分類する。本例においては、分類部４２は、Ｎ個のメッセージであるＸ１、Ｘ２、Ｘ３、…、Ｘｉ、…、ＸＮから重複したメッセージ（例えば内容が同一であるメッセージ）を削除して、Ｍ個の分類済メッセージであるＣ１、Ｃ２、…、Ｃｊ、…、ＣＭを生成する。なお、Ｃは分類済メッセージを表し、Ｃの下付け数字は分類済メッセージのインデックス（分類インデックス）を表す。
【００２９】
また、ステップＳ１１において、サーバ２０の分類部４２は、Ｎ個のメッセージのそれぞれが、Ｍ個の分類済メッセージの何れに対応するのかを指し示すポインタを生成する。本例においては、Ｎ個のメッセージのうちのインデックスｉのメッセージＸｉが、分類インデックスｊの分類済メッセージＣｊに対応している。従って、サーバ２０の分類部４２は、インデックスｉのメッセージＸｉについては、分類インデックスｊの分類済メッセージＣｊに対応していることを指し示すポインタを生成する。
【００３０】
続いて、ステップＳ１２において、サーバ２０のメッセージ暗号化部４４は、Ｍ個の分類済メッセージＣ１、Ｃ２、…、Ｃｊ、…、ＣＭのそれぞれを暗号化してＭ個の暗号文を生成する。生成されたＭ個の暗号文のそれぞれは、互いに異なるＭ個のメッセージ鍵ｋ１〜ｋＭのそれぞれを用いて復号することができる。本例においては、サーバ２０のメッセージ暗号化部４４は、Ｍ個の暗号文であるＥ（ｋ１，Ｃ１）、Ｅ（ｋ２，Ｃ２）、…、Ｅ（ｋｊ，Ｃｊ）、…、Ｅ（ｋＭ，ＣＭ）を生成する。なお、Ｅ（ｋ、Ｃ）は、分類済メッセージＣをメッセージ鍵ｋにより暗号化した暗号文を表す。
【００３１】
続いて、ステップＳ１３において、サーバ２０のメッセージ供給部４６は、Ｍ個の暗号化された分類済メッセージをクライアント３０へと供給する。本例においては、メッセージ供給部４６は、Ｍ個の暗号化された分類済メッセージを、クライアント３０によるインデックスの指定に先立って（オフラインで）、クライアント３０へと供給する。
【００３２】
また、オフラインの場合において、サーバ２０のメッセージ供給部４６は、Ｍ個の暗号化された分類済メッセージをネットワークを介してクライアント３０へと送信してもよいし、Ｍ個の暗号化された分類済メッセージを記憶媒体に書き込んでクライアント３０に受け渡してもよい。また、この場合、サーバ２０のメッセージ供給部４６は、Ｍ個の暗号化された分類済メッセージを、Ｎ個のメッセージの順次に対してランダム化した順序でクライアント３０に供給してもよい。これにより、サーバ２０は、メッセージの位置をクライアント３０のユーザ等に推測させないことができる。
【００３３】
また、オフラインでの処理に代えて、サーバ２０のメッセージ供給部４６は、ユーザ等によるインデックスの指定がされたことに応じて（オンラインで）、Ｍ個の暗号化された分類済メッセージをネットワークを介してクライアント３０に送信してもよい。この場合、サーバ２０のメッセージ供給部４６は、Ｍ個の暗号化された分類済メッセージをデータサイズの小さい順に並べてクライアント３０に送信してもよい。これにより、クライアント３０は、指定されたインデックスのメッセージに対応する分類済メッセージが比較的に小さいデータサイズであれば、Ｍ個の暗号化された分類済メッセージの送信中における比較的に早い段階で目的のメッセージを取得することができる。
【００３４】
続いて、ステップＳ１４において、クライアント３０のメッセージ取得部５２は、サーバ２０のメッセージ供給部４６から供給されたＭ個の暗号化された分類済メッセージを取得する。クライアント３０のメッセージ取得部５２は、インデックスの指定に先立って（オフラインで）、Ｍ個の暗号化された分類済メッセージをネットワークを介してサーバ２０から取得してもよいし、サーバ２０により書き込まれたＭ個の暗号化された分類済メッセージを記録媒体から読み出して取得してもよい。そして、クライアント３０の分類済メッセージ記憶部５４は、取得したＭ個の暗号化された分類済メッセージを内部に記憶する。
【００３５】
なお、クライアント３０のメッセージ取得部５２は、オフラインでの処理に代えて、後述のステップＳ１５でインデックスの指定がされたことに応じて（オンラインで）、Ｍ個の暗号化された分類済メッセージをネットワークを介してサーバ２０から受信してもよい。
【００３６】
続いて、ステップＳ１５において、クライアント３０の鍵受信部５６は、例えばユーザから、サーバ２０が保有するＮ個のメッセージのうちの取得すべきメッセージのインデックスの指定を受ける。本例においては、サーバ２０の鍵受信部５６は、インデックスとして"ｉ"の指定を受ける。
【００３７】
そして、サーバ２０の鍵送信部４８およびクライアント３０の鍵受信部５６は、紛失通信をして、指定されたインデックスに対応するメッセージ鍵をサーバ２０からクライアント３０へと受け渡す。より具体的には、サーバ２０の鍵送信部４８は、Ｍ個のメッセージ鍵のうちクライアント３０により指定されたインデックスのメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、紛失通信によりクライアント３０に送信する。一方、クライアント３０の鍵受信部５６は、指定したインデックスのメッセージに対応するメッセージ鍵を紛失通信によりサーバ２０から受信する。これにより、鍵送信部４８および鍵受信部５６は、指定されたインデックスに対応するメッセージ鍵以外のメッセージ鍵をクライアント３０が取得できず且つ指定されたインデックスをサーバ２０に特定させずに、指定されたインデックスに対応するメッセージ鍵を受け渡すことができる。
【００３８】
本例においては、サーバ２０の鍵送信部４８およびクライアント３０の鍵受信部５６は、インデックスｉの指定を受けたことに応じて、インデックスｉのメッセージＸｉに対応する分類済メッセージＣｊを復号するためのメッセージ鍵ｋｊを、紛失通信により、サーバ２０からクライアント３０へと受け渡す。これにより、本例においては、鍵送信部４８および鍵受信部５６は、指定されたインデックスｉに対応するメッセージ鍵ｋｊ以外のメッセージ鍵をクライアント３０が取得できず且つ指定されたインデックスｉをサーバ２０に特定させずに、メッセージ鍵ｋｊを受け渡すことができる。
【００３９】
なお、サーバ２０の鍵送信部４８は、メッセージ鍵とともに、指定されたインデックスのメッセージに対応する分類済メッセージを指し示すポインタ（例えば分類インデックス）を紛失通信によりクライアント３０に送信してもよい。この場合において、サーバ２０の鍵送信部４８は、メッセージ鍵の一部に含めて送信してもよい。
【００４０】
そして、鍵受信部５６は、ポインタをメッセージ鍵とともに紛失通信により受信する。これにより、クライアント３０の鍵受信部５６は、Ｍ個の暗号化された分類済メッセージのうち、受信したメッセージ鍵により何れを復号できるかを特定することができる。
【００４１】
続いて、ステップＳ１６において、クライアント３０のメッセージ復号部５８は、鍵受信部５６が受信したメッセージ鍵により、サーバ２０から供給されたＭ個の暗号化された分類済メッセージのうち、指定されたインデックスのメッセージに対応する分類済メッセージを復号する。この場合において、クライアント３０のメッセージ復号部５８は、鍵受信部５６がメッセージ鍵とともにポインタを受信していれば、受信したポインタに示された分類済メッセージを復号する。また、クライアント３０のメッセージ復号部５８は、ポインタを受信していない場合においては、Ｍ個の分類済メッセージの全てについて復号処理を実行してみて、１つの分類済メッセージを復号してもよい。
【００４２】
本例においては、クライアント３０のメッセージ復号部５８は、分類済メッセージＣｊを復号することができる。ここで、分類済メッセージＣｊは、サーバ２０が保有するＮ個のメッセージのうちの指定されたインデックスｉのメッセージＸｉと同一である。従って、情報提供システム１０は、指定されたインデックスｉのメッセージＸｉ以外のメッセージをクライアント３０が取得できず且つ指定されたインデックスｉをサーバ２０に特定させずに、指定したインデックスｉのメッセージＸｉをクライアント３０に受け取らせることができる。
【００４３】
以上のように本実施形態に係る情報提供システム１０によれば、重複したメッセージをサーバ２０からクライアント３０へと供給しなくてもよいので、冗長性の低い紛失通信を実現することができる。これにより、情報提供システム１０は、Ｎ個のメッセージの紛失通信を実行する場合において、効率良く通信を行うことができる。
【００４４】
図３は、サーバ２０とクライアント３０との間におけるメッセージ鍵の紛失通信による受け渡し処理のフローを示す。図４は、図３に続くフローを示す。図５は、図４に続くフローを示す。
【００４５】
以下、図３、図４および図５を参照して、ステップＳ１５で実行される紛失通信の通信処理の一例を説明する。なお、本実施形態において行われる紛失通信は、以下に説明する処理に限らず、他の処理により実現してもよい。
【００４６】
まず、ステップＳ２１において、サーバ２０は、"ｒ"を生成する。続いて、ステップＳ２２において、サーバ２０は、"ｇ"に"ｒ"を冪乗して、"ｇｒ"を生成する。
【００４７】
ここで、"ｇ"は、位数"ｑ"の生成元を表す。なお、"ｑ"は、任意の素数である。また、"ｇ"は、サーバ２０およびクライアント３０の両者で共通に定められた値である。
【００４８】
また、"ｒ"は、位数"ｑ"の巡回群"Ｚｑ"からランダムに選択された値である。また、後述する"ｒ１"および"ｒ２"も、位数"ｑ"の巡回群Ｚｑからランダムに選択された値である。
【００４９】
続いて、ステップＳ２３において、サーバ２０は、"Ｔ２，Ｔ３，Ｔ４，…，ＴＮ"を生成する。Ｔ２，Ｔ３，Ｔ４，…，ＴＮ"は、（Ｎ−１）個の任意の整数であり、２からＮまでのインデックスが付けられている。続いて、ステップＳ２４において、サーバ２０は、"ｇｒ"および"Ｔ２，Ｔ３，Ｔ４，…，ＴＮ"をクライアント３０へと送信する。
【００５０】
なお、クライアント３０は、離散対数の性質から、"ｇｒ"から"ｒ"を算出することはきわめて困難である。従って、"ｒ"は、クライアント３０に対して秘匿されているといえる。
【００５１】
続いて、ステップＳ２５において、クライアント３０は、Ｎ個のメッセージのうちのユーザが取得を希望するメッセージを特定するためのインデックスの指定を受け取る。本例においては、クライアント３０は、インデックスとして"ｉ"の指定を受ける。ここで、"ｉ"は、１以上Ｎ以下の任意の整数である。
【００５２】
続いて、ステップＳ２６において、クライアント３０は、"Ｔ２，Ｔ３，Ｔ４，…，ＴＮ"の中から、ｉ番目のインデックスに対応する"Ｔｉ"を選択する。なお、指定されたインデックスｉが１の場合（ｉ＝１の場合）には、クライアント３０は、ステップＳ２６において値を選択しない。
【００５３】
続いて、ステップＳ２７において、クライアント３０は、"ｒ２"を生成する。続いて、ステップＳ２８において、クライアント３０は、"ｇ"に"ｒ２"を冪乗して、"ｇｒ２"を生成する。
【００５４】
続いて、ステップＳ２９において、クライアント３０は、"ＰＫ１"を算出する。具体的には、クライアント３０は、ｉ＝１の場合には、"ｇｒ２"を"ＰＫ１"とする（ＰＫ１＝ｇｒ２）。また、クライアント３０は、ｉ≠１の場合には、"Ｔｉ／ｇｒ２"を算出し、算出した"Ｔｉ／ｇｒ２"を"ＰＫ１"とする（ＰＫ１＝Ｔｉ／ｇｒ２）。
【００５５】
続いて、ステップＳ３０において、クライアント３０は、"ＰＫ１"をサーバ２０へと送信する。なお、サーバ２０は、離散対数の性質から、"ｇｒ２"から"ｒ２"を算出することはきわめて困難である。従って、"ｒ２"は、サーバ２０に対して秘匿されているといえる。
【００５６】
続いて、ステップＳ３１において、サーバ２０は、"ｒ"および"Ｔ２，Ｔ３，Ｔ４，…，ＴＮ"、並びに、受信した"ＰＫ１"に基づき、下記の式（１）のように、（ＰＫ１）ｒ、（ＰＫ２）ｒ、…、（ＰＫｉ）ｒ、…、（ＰＫＮ）ｒを算出する。
【００５７】
【数１】
0005737788.tif 000002
【００５８】
なお、ここで、（ＰＫｉ）ｒは、下記の式（２）のように、ｇ（ｒ２・ｒ）となる。
【００５９】
【数２】
0005737788.tif 000003
【００６０】
続いて、ステップＳ３２において、サーバ２０は、"ｒ１"を生成する。
【００６１】
続いて、ステップＳ３３において、サーバ２０は、下記の式（３）に示すように、Ｎ個の暗号鍵"Ｓ１，Ｓ２，…，Ｓｉ，…，ＳＮ"を生成する。なお、下記の式（３）において、Ｈ（ｘ，ｙ，ｚ）は、ｘ、ｙ、ｚを変数としたハッシュ関数を表す。
【００６２】
【数３】
0005737788.tif 000004
【００６３】
続いて、ステップＳ３４において、サーバ２０は、Ｍ個の分類済メッセージのそれぞれを復号するためのＭ個のメッセージ鍵"ｋ１，ｋ２，…，ｋＭ"を、Ｎ個のメッセージのインデックス順に再配置する。この場合において、サーバ２０は、Ｎ個のメッセージのそれぞれが、Ｍ個の分類済メッセージの何れに対応するのかを指し示すポインタを参照して、メッセージ鍵を再配置する。
【００６４】
続いて、ステップＳ３５において、サーバ２０は、Ｎ個のメッセージのインデックス順に再配置されたＮ個のメッセージ鍵のそれぞれを、ステップＳ３３で生成したＮ個の暗号鍵"Ｓ１，Ｓ２，…，Ｓｉ，…，ＳＮ"のそれぞれにより暗号化する。即ち、サーバ２０は、１番目のメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、１番目の暗号鍵"Ｓ１"により暗号化する。また、サーバ２０は、ｉ番目のメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、ｉ番目の暗号鍵"Ｓｉ"により暗号化する。また、サーバ２０は、Ｎ番目のメッセージに対応する分類済メッセージを復号するためのメッセージ鍵を、Ｎ番目の暗号鍵"ＳＮ"により暗号化する。これにより、サーバ２０は、下記の式（４）に示すようなＮ個の暗号文を生成することができる。
【００６５】
【数４】
0005737788.tif 000005
【００６６】
なお、この場合において、サーバ２０は、Ｎ個のメッセージ鍵のそれぞれとともに、当該メッセージ鍵により復号ができる分類済メッセージを指し示すポインタ（例えば、分類インデックス）を暗号化する。この場合において、サーバ２０は、メッセージ鍵の一部にポインタを含めてもよい。
【００６７】
続いて、ステップＳ３６において、サーバ２０は、生成したＮ個の暗号文をクライアント３０へと送信する。続いて、ステップＳ３７において、サーバ２０は、"ｒ１"をクライアント３０へと送信する。
【００６８】
一方、ステップＳ３８において、クライアント３０は、"ｇｒ"に"ｒ２"を冪乗した"（ｇｒ）ｒ２"を算出する。ここで、（ＰＫｉ）ｒは、式（２）で示したように、ｇ（ｒ２・ｒ）となる。即ち、ステップＳ３８でクライアント３０が算出した"（ｇｒ）ｒ２"は、"（ＰＫｉ）ｒ"を表す。
【００６９】
続いて、ステップＳ３９において、クライアント３０は、"（ＰＫｉ）ｒ"、"ｒ１"及び"ｉ"を用いて、インデックスｉに対応した暗号鍵"Ｓｉ"を生成する。なお、クライアント３０は、（ＰＫｉ）ｒ以外の値（例えば（ＰＫ１）ｒ、（ＰＫ２）ｒ、及び（ＰＫＭ）ｒ等）を生成することはできないので、インデックスｉに対応した暗号鍵"Ｓｉ"以外の暗号鍵を生成することはできない。従って、クライアント３０は、インデックスｉのメッセージに対応した分類済メッセージを復号するためのメッセージ鍵ｋｊ以外のメッセージ鍵を取得することはできない。
【００７０】
続いて、ステップＳ４０において、クライアント３０は、暗号文Ｅ（Ｓｉ，ｋｊ）から、ステップＳ３９で生成した暗号鍵"Ｓｉ"を用いてメッセージ鍵ｋｊを復号する。これにより、クライアント３０は、インデックスｉのメッセージＸｉに対応した分類済メッセージＣｊを復号するためのメッセージ鍵ｋｊを取得することができる。また、この場合において、クライアント３０は、暗号文（Ｓｉ，ｋｊ）にポインタが含まれていれば、ポインタも復号して取得する。
【００７１】
以上のように、サーバ２０およびクライアント３０は、指定されたインデックスｉに対応するメッセージ鍵ｋｊ以外のメッセージ鍵をクライアント３０が取得できず且つ指定されたインデックスｉをサーバ２０に特定させずに、指定されたインデックスｉに対応するメッセージ鍵ｋｊを受け渡すことができる。
【００７２】
図６は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【００７３】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００７４】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【００７５】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラム、及び／又は、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０を入出力コントローラ２０８４へと接続すると共に、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を入出力コントローラ２０８４へと接続する。
【００７６】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【００７７】
コンピュータ１９００にインストールされ、コンピュータ１９００を、サーバ２０として機能させるプログラムは、メッセージ記憶モジュールと、分類モジュールと、メッセージ暗号化モジュールと、メッセージ供給モジュールと、鍵送信モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、メッセージ記憶部４０、分類部４２、メッセージ暗号化部４４、メッセージ供給部４６および鍵送信部４８としてそれぞれ機能させる。
【００７８】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、メッセージ記憶部４０、分類部４２、メッセージ暗号化部４４、メッセージ供給部４６および鍵送信部４８として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のサーバ２０が構築される。
【００７９】
コンピュータ１９００にインストールされ、コンピュータ１９００を、クライアント３０として機能させるプログラムは、メッセージ取得モジュールと、分類済メッセージ記憶モジュールと、鍵受信モジュールと、メッセージ復号モジュールと、を備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、メッセージ取得部５２、分類済メッセージ記憶部５４、鍵受信部５６およびメッセージ復号部５８としてそれぞれ機能させる。
【００８０】
これらのプログラムに記述された情報処理は、コンピュータ１９００に読込まれることにより、ソフトウェアと上述した各種のハードウェア資源とが協働した具体的手段である、メッセージ取得部５２、分類済メッセージ記憶部５４、鍵受信部５６およびメッセージ復号部５８として機能する。そして、これらの具体的手段によって、本実施形態におけるコンピュータ１９００の使用目的に応じた情報の演算又は加工を実現することにより、使用目的に応じた特有のクライアント３０が構築される。
【００８１】
一例として、コンピュータ１９００と外部の装置等との間で通信を行う場合には、ＣＰＵ２０００は、ＲＡＭ２０２０上にロードされた通信プログラムを実行し、通信プログラムに記述された処理内容に基づいて、通信インターフェイス２０３０に対して通信処理を指示する。通信インターフェイス２０３０は、ＣＰＵ２０００の制御を受けて、ＲＡＭ２０２０、ハードディスクドライブ２０４０、フレキシブルディスク２０９０、又はＣＤ−ＲＯＭ２０９５等の記憶装置上に設けた送信バッファ領域等に記憶された送信データを読み出してネットワークへと送信し、もしくは、ネットワークから受信した受信データを記憶装置上に設けた受信バッファ領域等へと書き込む。このように、通信インターフェイス２０３０は、ＤＭＡ（ダイレクト・メモリ・アクセス）方式により記憶装置との間で送受信データを転送してもよく、これに代えて、ＣＰＵ２０００が転送元の記憶装置又は通信インターフェイス２０３０からデータを読み出し、転送先の通信インターフェイス２０３０又は記憶装置へとデータを書き込むことにより送受信データを転送してもよい。
【００８２】
また、ＣＰＵ２０００は、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０（ＣＤ−ＲＯＭ２０９５）、フレキシブルディスク・ドライブ２０５０（フレキシブルディスク２０９０）等の外部記憶装置に格納されたファイルまたはデータベース等の中から、全部または必要な部分をＤＭＡ転送等によりＲＡＭ２０２０へと読み込ませ、ＲＡＭ２０２０上のデータに対して各種の処理を行う。そして、ＣＰＵ２０００は、処理を終えたデータを、ＤＭＡ転送等により外部記憶装置へと書き戻す。このような処理において、ＲＡＭ２０２０は、外部記憶装置の内容を一時的に保持するものとみなせるから、本実施形態においてはＲＡＭ２０２０および外部記憶装置等をメモリ、記憶部、または記憶装置等と総称する。本実施形態における各種のプログラム、データ、テーブル、データベース等の各種の情報は、このような記憶装置上に格納されて、情報処理の対象となる。なお、ＣＰＵ２０００は、ＲＡＭ２０２０の一部をキャッシュメモリに保持し、キャッシュメモリ上で読み書きを行うこともできる。このような形態においても、キャッシュメモリはＲＡＭ２０２０の機能の一部を担うから、本実施形態においては、区別して示す場合を除き、キャッシュメモリもＲＡＭ２０２０、メモリ、及び／又は記憶装置に含まれるものとする。
【００８３】
また、ＣＰＵ２０００は、ＲＡＭ２０２０から読み出したデータに対して、プログラムの命令列により指定された、本実施形態中に記載した各種の演算、情報の加工、条件判断、情報の検索・置換等を含む各種の処理を行い、ＲＡＭ２０２０へと書き戻す。例えば、ＣＰＵ２０００は、条件判断を行う場合においては、本実施形態において示した各種の変数が、他の変数または定数と比較して、大きい、小さい、以上、以下、等しい等の条件を満たすかどうかを判断し、条件が成立した場合（又は不成立であった場合）に、異なる命令列へと分岐し、またはサブルーチンを呼び出す。
【００８４】
また、ＣＰＵ２０００は、記憶装置内のファイルまたはデータベース等に格納された情報を検索することができる。例えば、第１属性の属性値に対し第２属性の属性値がそれぞれ対応付けられた複数のエントリが記憶装置に格納されている場合において、ＣＰＵ２０００は、記憶装置に格納されている複数のエントリの中から第１属性の属性値が指定された条件と一致するエントリを検索し、そのエントリに格納されている第２属性の属性値を読み出すことにより、所定の条件を満たす第１属性に対応付けられた第２属性の属性値を得ることができる。
【００８５】
以上に示したプログラム又はモジュールは、外部の記録媒体に格納されてもよい。記録媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤ又はＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワーク又はインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【００８６】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００８７】
特許請求の範囲、明細書、および図面中において示した装置、システム、プログラム、および方法における動作、手順、ステップ、および段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り、任意の順序で実現しうることに留意すべきである。特許請求の範囲、明細書、および図面中の動作フローに関して、便宜上「まず、」、「次に、」等を用いて説明したとしても、この順で実施することが必須であることを意味するものではない。
【符号の説明】
【００８８】
１０  情報提供システム
２０  サーバ
３０  クライアント
４０  メッセージ記憶部
４２  分類部
４４  メッセージ暗号化部
４６  メッセージ供給部
４８  鍵送信部
５２  メッセージ取得部
５４  分類済メッセージ記憶部
５６  鍵受信部
５８  メッセージ復号部
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
0005737788.tif 000006
【図２】
0005737788.tif 000007
【図３】
0005737788.tif 000008
【図４】
0005737788.tif 000009
【図５】
0005737788.tif 000010
【図６】
0005737788.tif 000011