暗号化装置、復号化装置、および経路探索システム
【課題】利用者ごとに適切な経路探索を行うことができる暗号化装置、復号化装置、および経路探索システムを提供する。
【解決手段】地図上の位置を示すノードおよびノードとノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと経路探索用データに対応した地図を表示するための表示用データとが対応付けられた地図データと、ノードと表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報と、経路探索用データを暗号化するための暗号化鍵を格納する記憶部と、経路探索用データと、暗号化鍵と、暗号化定義情報とに基づいて、利用者ごとに、暗号化すべきノードを特定し、特定したノードおよび特定したノードに隣接するノードの経路探索用データを暗号化し、暗号化した経路探索用データと表示用データとを対応付けた暗号化地図データを生成する暗号化処理部と、
を備える。
【解決手段】地図上の位置を示すノードおよびノードとノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと経路探索用データに対応した地図を表示するための表示用データとが対応付けられた地図データと、ノードと表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報と、経路探索用データを暗号化するための暗号化鍵を格納する記憶部と、経路探索用データと、暗号化鍵と、暗号化定義情報とに基づいて、利用者ごとに、暗号化すべきノードを特定し、特定したノードおよび特定したノードに隣接するノードの経路探索用データを暗号化し、暗号化した経路探索用データと表示用データとを対応付けた暗号化地図データを生成する暗号化処理部と、
を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化された経路探索用データを利用した暗号化装置、復号化装置、および経路探索システムに関するものである。
【背景技術】
【０００２】
地理情報システムでは地図表示や経路探索など様々な機能が提供される。こられのうち経路探索では、ノードとリンクから構成される経路探索用データを用いて、ダイクストラ法などの経路探索アルゴリズムを用いて、出発点と目的地の経路探索が行われる。
【０００３】
ところで地図情報には、例えば、軍事基地や個人所有の敷地、或は、企業の工場など、一般に開示しないことが望ましい情報が多数含まれる。従来、地理情報配信システムでは、屋外の地図情報を提供するサービスが多かったが、近年の情報サービス産業の発展に伴い、地下街や駅構内など、屋内の地図情報を提供するサービスも増えてきている。これら屋内の地図情報には、例えば、店舗における従業員の作業エリアやオフィス内の間取図など、一般に公開すべきでない情報が含まれる。また、例えばオフィス内の間取図では、機密文書の保管場所など、地図情報の利用者に応じて適切に開示する情報を制限する必要がある。従って、経路探索についても、利用者の開示範囲に応じて適切な範囲内での経路探索を行うことが望まれる。
【０００４】
従来の技術では、ネットワークや放送により地図情報を車両に配信する場合に配信先の車両に応じて適切な情報のみが開示されるよう、車両別に地図情報を管理し、それぞれの地図情報を個別の鍵で暗号化することによって、車両の種別に応じた地図情報の開示制限を行う技術が知られている（例えば、特許文献１）。
【０００５】
また、経路探索用データに対しては、利用者が経路探索用データを編集し、経路探索用データの改ざんを、暗号を用いて保護する方法が知られている（例えば特許文献２）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−１２１７１９号公報
【特許文献２】特開２０００−１９３４７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１では、種別に応じた地図情報の開示において、暗号化した地図情報を送信先の車両種別ごとに準備し、車には種別ごとに秘密鍵を事前に格納しておく。これによって、暗号化された地図情報を配信し、特定の車両種別のみが暗号化された地図を復号することができ、車両の種別に応じた開示制限が可能となる。
【０００８】
しかしながら、特許文献１で開示された方法では、地図を構成する地物の形状、及び、それに付随した名称等の属性情報を対象としており、経路探索用データの暗号化については開示されていない。また、経路探索では、任意の出発点から目的地までの経路を探索する必要があり、利用者ごとの要求に応じて経路探索を実行することが必要となる。特許文献１のように、事前に暗号化データを用意して一斉配信する方法では、利用者の種別ごと、或いは、出発地・目的地ごとの経路探索結果を個別に暗号化して管理すること必要となる。そのため、管理するデータサイズの増加や、事前に用意した地点間の経路探索結果しか提供できず、利用者ごとに適切な経路探索を行うことができないという問題が生じる。
【０００９】
また、特許文献２に開示された方法では、経路探索用データの改ざんを防止する方法が述べられているが、経路探索用データの開示先を利用者、或いは、利用者種別ごとに制限する方法については開示されておらず、特許文献１と同様に、利用者ごとに適切な経路探索を行うことができないという問題がある。
【００１０】
本発明は、上記に鑑みてなされたものであって、利用者ごとに適切な経路探索を行うことができる暗号化装置、復号化装置、および経路探索システムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した目的を達成するために、本発明にかかる暗号化装置は、地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと前記検索用データに対応した地図を表示させるための表示用データとが対応付けられた地図データと、前記ノードと前記表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報と、前記経路探索用データを暗号化するための暗号化鍵を格納する記憶部と、前記経路探索用データと、前記暗号化鍵と、前記暗号化定義情報とに基づいて、前記利用者ごとに、暗号化すべき前記ノードを特定し、特定した前記ノードおよび特定した前記ノードに隣接するノードの前記経路探索用データを暗号化し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する暗号化処理部と、を備えることを特徴とする。
【００１２】
また、本発明にかかる復号化装置は、利用者から地図上の位置のある地点から他の地点までの経路を探索するための経路探索要求を受けた場合に、暗号化された地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データを復号化する復号化鍵に基づいて、前記経路探索用データと、前記ノードにある地物を表示させるための表示用データとが対応付けられた暗号化地図データを復号化する復号処理部と、前記ある地点から前記他の地点までの経路を、前記暗号化地図データに対応する前記経路探索用データに含まれる前記ノードと前記リンク情報とに基づいて前記復号処理部を用いて暗号化地図データの復号を行い、復号結果を用いて前記ノードと前記リンク情報とに基づいて、繰り返し探索する経路探索部と、を備えることを特徴とする。
【００１３】
また、本発明は、上記暗号化装置および復号化装置を備えた経路探索システムである。
【発明の効果】
【００１４】
本発明によれば、利用者ごとに適切な経路探索を行うことができる暗号化装置、復号化装置、および経路探索システムを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態における地図データ配信システムの概略を示す構成図である。
【図２】図１に示した地図データ配信システムを構成する各装置の構成図である。
【図３】地図データ配信システムにおいて行われる処理のシーケンス図である（登録処理）。
【図４】地図データ配信システムにおいて行われる処理のシーケンス図である。経路探索の処理フローの概略を表す図である（経路処理）。
【図５】平文地図データのデータ構造の一部とその表示イメージを示す図である。
【図６】暗号化定義情報の一例を示す図である。
【図７】第１の実施の形態における暗号化処理の処理手順を示すフローチャートである。
【図８】第１の実施の形態における復号化処理の処理手順を示すフローチャートである。第一の実施例における経路探索用データの復号処理の概略を示す処理フロー図である。
【図９】経路探索用データ格納部の例を示す図である。
【図１０】暗号化定義情報を生成するためのアプリケーション画面の一例を示す図である。
【図１１】第２の実施の形態における暗号化処理の処理手順を示すフローチャートである。
【図１２】第２の実施の形態における復号化処理の処理手順を示すフローチャートである。
【図１３】第２の実施の形態における暗号化処理前後でのデータ構造の変化の一例を示す図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して、この発明にかかる暗号化装置、復号化装置、および経路探索システムの実施の形態を詳細に説明する。
（第１の実施の形態）
図１は、第１の実施の形態における地図データ配信システム１の概略を示す構成図である。図１において、点線はデータの流れの概略を表している。地図データ配信システム１は、地図暗号化装置１０１、地図格納装置１０２と、鍵管理装置１０３と、地図配信装置１０４と、地図閲覧装置１０５と、地図復号装置１０６とを含んで構成され、これらの各装置がネットワーク１００を介して接続されている。
【００１７】
地図暗号化装置１０１は、暗号化定義情報生成部１１０と、暗号化処理部１１１とを含んで構成されている。暗号化定義情報生成部１１０は、暗号化される前の地図データである平文地図データ１２０から暗号化定義情報１２１を生成し、暗号化処理部１１１は、暗号化定義情報１２１、平文地図データ１２０と暗号化鍵１２２から、暗号化地図データ１２４を生成するものである。なお、暗号化定義情報１２１の具体的な内容については後述する。
【００１８】
地図格納装置１０２は、データベース処理部１１２を有し、暗号化地図データ１２４を格納する。ここで、データベース処理部１１２は、例えば、ＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ Ｑｕｅｒｙ Ｌａｎｇａｇｅ）やＧＩＳ製品（Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ）のＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ Ｐｒｏｇｒａｍ Ｉｎｔｅｒｆａｃｅ）を用いて、地図配信装置１０４からの要求に応じて、検索や登録、削除、変更など、暗号化地図データ１２４に関する種々の処理を行う。
【００１９】
鍵管理装置１０３は、鍵生成部１１３を含んで構成される。鍵生成部１１３は、暗号化に利用する暗号化鍵１２２と対応する復号鍵１２３を生成する。ここで、鍵生成部１１１３が生成する暗号化鍵１２２、復号鍵１２３は、ＲＳＡなどの公開鍵暗号技術における公開鍵、秘密鍵であってもよいし、ＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）などの共通鍵暗号技術における共有鍵であってもよい。
【００２０】
地図配信装置１０４は、クエリ処理部１１７を含んで構成されている。クエリ処理部１１７は、地図閲覧装置１０５内のクエリ要求部１１５からの要求を受け付け、クエリの解析を行い、地図復号装置１０６の表示用イメージ生成部１１４２が生成した表示用地図データを受けると、地図閲覧装置１０５へ返信して表示させるための地図データを作成する。
【００２１】
地図閲覧装置１０５は、クエリ要求部１１５と、表示処理部１１８とを含んで構成されている。ここで、クエリ要求部１１５は、地図配信装置１０４へ、地図データの検索などのクエリを送信し、地図配信装置１０４から返信された地図データを受信して、表示処理部１１８が地図データを表示する。地図閲覧装置１０５が受信した地図データは、後述するように、地図復号装置１０６の復号処理部１１６が復号鍵１２３を用いて復号処理を行ったものである。
【００２２】
地図復号装置１０６は、経路探索処理部１１４１と、表示用地図イメージ生成部１１４２と、復号処理部１１６とを含んで構成される。表示用地図イメージ生成部１１４２は、復号処理部１１６が地図配信装置１０４のクエリ処理部１１７から表示用地図データを復号する要求を受けて復号した表示用地図データを送る。経路探索処理部１１４２は、地図配信装置１０４から経路探索用データを受信した場合に、経路探索を行う。経路探索の具体的な処理については後述する。復号処理部１１６は、復号鍵１２３を用いて、暗号化地図データ１２４の復号を行う。なお、以下の説明では、地図復号装置１０６を単独の装置として説明を行うが、地図復号装置１０６は地図配信装置１０４の一部であってもよいし、地図復号装置１０６は、地図閲覧装置１０５の一部として構成されていてもよい。
【００２３】
図２は、図１に示した地図データ配信システム１を構成する各装置の構成図である。図２に示すように、図１に示した地図データ配信システム１を構成する各装置は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｏｒ Ｕｎｉｔ）２０１、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）２０２、入力装置２０３、表示装置２０４、通信装置２０５、読書装置２０６、及び、外部記憶装置２０７がインターフェイス２０５を介して接続された、一般的な構成を有するコンピュータ（電子計算機）２００として構成される。
【００２４】
入力装置２０３は、例えば、キーボードやマウスなどであり、表示装置２０４は、表示用ディスプレイ、外部記憶装置２０７は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）などである。また、通信装置２０５はネットワークを介して他の装置と通信を行うための通信インターフェイスである。さらに、読書装置２０６は、ＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）やＵＳＢメモリ、或いは、ＣＤ−Ｒといった外部記憶媒体２０８から、データの読込み、或いは、書込みを行うための装置である。
【００２５】
ＣＰＵ２０１は、ＲＡＭ２０２上にロードしたプログラムを実行することによって、図１に示した各装置の各処理部(暗号化処理部１１１など）をプロセスとして具現化する。また、インターフェイス２０９は、装置内の各構成要素間のデータを送受信する内部パスである。
【００２６】
図３および図４は、地図データ配信システム１において行われる処理のシーケンス図である。まず、図３について説明する。図３は、地図閲覧装置１０５から経路探索要求があった場合に、利用者の種別に応じて経路探索を行って、その種別に応じた地図データを地図閲覧装置１０５に表示させるための暗号化地図データ１２４を登録する処理（以下、登録処理と呼ぶ。）の処理手順を示すフローチャートである。
【００２７】
この登録処理は、地図データ配信システム１が行う処理のうち、地図閲覧装置１０５に地図データを配信する前に、例えば、地図データ配信システム１を利用するユーザを登録するタイミングで、あらかじめ管理者等によって行われるものである。登録処理では、鍵管理装置１０３での鍵生成と、地図暗号化装置１０１、地図閲覧装置１０５への送信、及び、平文地図データの暗号化、暗号化された地図データの地図格納装置１０２での格納までの処理を行う。
【００２８】
図３に示すように、登録処理が開始されると（ステップＳ３００）、鍵管理装置１０３は、利用者に応じた暗号化鍵１２２、復号鍵１２３を生成し（ステップＳ３０１）、生成した復号鍵１２３を地図復号装置１０６に送信する（ステップＳ３０２）。
【００２９】
地図復号装置１０６は、復号鍵１２３を受信すると、受信したその復号鍵１２３を、外部記憶装置２０７等の記憶装置に格納し（ステップＳ３０３）、その後、鍵管理装置１０３は、暗号化鍵１２２を地図暗号化装置１０１に送信する（ステップＳ３０４）。
【００３０】
暗号化鍵１２２を受信すると、地図暗号化装置１０１は、受信した暗号化鍵１２２を外部記憶装置２０７等の記憶装置に格納し（ステップＳ３０５）、暗号化定義情報生成部１１０は、平文地図データ１２０を用いて、暗号化定義情報１２１を生成する（ステップＳ３０６）。
【００３１】
ここで、暗号化定義情報１２１とは、後述するノード、およびノード間の関係を表すリンクから構成される経路探索用データを、開示対象となる利用者（あるいは利用者の種別）を、ノードと対応付けて記憶するものである。
【００３２】
なお、この暗号化定義情報１２１は、地図データ配信システム１が取り扱う平文地図データ１２０に対して作成されるものであり、具体的な内容については図６を用いて後述する。また、暗号化定義情報１２１として記述されるデータの内容（例えば、どのノードをどの利用者に対して開示させるのか）については、あらかじめ管理者等によって定められ、その設定にしたがって暗号化定義情報１２１が生成されるものとする。
【００３３】
そして、地図暗号化装置１０１の暗号化処理部１１１は、暗号化定義情報１２１と平文地図データ１２０、暗号化鍵１２２から暗号化地図データ１２４を生成し、生成した暗号化地図データ１２４を地図格納装置１０２に送信する（ステップＳ３０７）。このステップＳ３０７の具体的な処理（暗号化処理）については、図７を用いて後述する。
【００３４】
地図格納装置１０２は、地図暗号化装置１０１から暗号化地図データ１２４を受信して、その暗号化地図データ１２４を格納し（ステップＳ３０８）、図３に示す登録処理が終了する（ステップＳ３０９）。この登録処理が終了すると、利用者毎の暗号化鍵１２２および復号鍵１２３と、暗号化地図データ１２４と、暗号化定義情報１２１とが生成される。
【００３５】
ここで、ステップＳ３０２において、鍵管理装置１０３が復号鍵１２３を地図復号装置１０６に送信する場合、および暗号化鍵１２２、復号鍵１２３として共通鍵暗号技術における共有鍵を用いたこれらの鍵を生成し、ステップＳ３０４において、鍵管理装置１０３が地図暗号化装置１０１に暗号化鍵１２２を送信する場合、外部記憶媒体を利用して直接配送するか、あるいは暗号化通信を用いて送信することが望ましい。また、公開鍵暗号技術における秘密鍵や共通鍵暗号技術における共有鍵は、例えばＩＣカードやＨＳＭ（Ｈａｒｄｗａｒｅ Ｓｅｃｕｒｉｔｙ Ｍｏｄｕｌｅ）などの耐タンパ性を有するデバイス内に格納しておくことが望ましい。
【００３６】
一方、公開鍵暗号技術における公開鍵は、一般に公開することが可能であるので、ＨＴＴＰ（Ｈｙｐｅｒ Ｔｅｘｔ Ｔｒａｎｓｆｅｒ Ｐｒｏｔｏｃｏｌ）などの一般的な通信路を用いてもよい。ただし、例えば、鍵管理装置１０３が公開鍵に対して公開鍵証明書を発行し、暗号化装置１０１で使用する暗号化鍵１２２に誤りや改ざんがないことを、公開鍵証明書を用いて確認することが望ましい。
【００３７】
図４は、地図データ配信システム１が、利用者から地図の経路探索要求を受け付けて、その結果を利用者に表示するための処理（以下、経路処理と呼ぶ。）の処理手順を示すフローチャートである。図４では、地図配信装置１０４から地図閲覧装置１０５に地図データを配信し、地図閲覧装置１０５で表示するまでの処理フローを表している。なお、本処理フローにおいては、主に、地図閲覧装置１０５からの経路探索要求の送信、地図配信装置１０４でのクエリ解析、地図格納装置１０２を利用した検索の実行と地図閲覧装置１０５への送信、及び、地図閲覧装置１０５での復号、表示処理が行われる。
【００３８】
図４に示すように、地図データ配信システム１が、利用者から地図データの経路探索要求を受け付け、経路処理が開始されると（ステップＳ４００）、地図閲覧装置１０５のクエリ要求部１１５は、地図配信装置１０４に、受け付けられた経路探索要求を送信する（ステップＳ４０１）。
【００３９】
そして、地図配信装置１０４のクエリ処理部１１７は、地図閲覧装置１０５から送信された経路探索要求を構成しているクエリを解析し、解析した結果に従って、地図格納装置１０２に対して経路探索用データの検索要求を送信する（ステップＳ４０２）。
【００４０】
地図格納装置１０２のデータベース処理部１１２は、地図配信装置１０４から検索要求を受信し、その検索要求に従って、図３に示した登録処理によって登録された暗号化地図データ１２４あるいは地図暗号化装置１０１の平文地図データ１２０にアクセスして検索処理を実行し、検索結果（例えば、出発地、目的地、および途中のノードの座標データやノードＩＤを含む情報）を経路探索用データとして地図配信装置１０４に返信する（ステップＳ４０３）。
【００４１】
続いて、地図配信装置１０４のクエリ処理部１１７は、地図格納装置１０２から経路探索用データを受信し、受信した経路探索用データを、地図復号装置１０６に送信し（ステップＳ４０４）、地図復号装置１０６の経路探索処理部１１４１および復号処理部１１６は、受信した経路探索用データを参照して経路探索を実行し、経路探索結果を地図配信装置１０４に送信する（ステップＳ４０５）。なお、ステップＳ４０５の具体的な処理（復号化処理）については、図８を用いて後述する
そして、地図配信装置１０４のクエリ処理部１１７は、経路探索結果を受信し、受信した経路探索結果を参照して表示用地図データの検索要求を地図格納装置１０２に送信し（ステップＳ４０６）、地図格納装置１０２のデータベース処理部１１２は、表示用地図データの検索要求にしたがって表示用地図データの検索を行い、その検索結果を地図配信装置１０４に送信する（ステップＳ４０７）。
【００４２】
地図配信装置１０４のクエリ処理部１１７は、表示用地図データの生成要求を地図復号装置１０６に送信し（ステップＳ４０８）、地図復号装置１０６の表示用地図イメージ生成部１１４２および復号処理部１１６が暗号化地図データ１２４を復号化した表示用地図イメージを生成し、地図配信装置１０４に送信する（ステップＳ４０９）。
【００４３】
その後、地図配信装置１０４のクエリ処理部１１７は、表示用地図イメージを地図閲覧装置１０５に送信し（ステップＳ４１０）、地図閲覧装置１０５のクエリ要求部１１５は、表示用地図イメージを受信し、表示処理部１１８が、地図閲覧装置１０５の表示装置２０４に表示用地図イメージを表示させ(ステップＳ４１１)、図４に示す検索処理が終了する（ステップＳ４１２）。
る。
【００４４】
ステップＳ４０１において、地図閲覧装置１０５から地図配信装置１０４への経路探索要求の送信に先立ち、後述するように、暗号化鍵１２２と復号鍵１２３とが利用者ごとに定められているため、利用者とこれらの鍵とを対応させるため、地図配信装置１０４は地図閲覧装置１０５のユーザ認証を行うことが望ましい。このため、地図配信装置１０４のクエリ処理部１１７が、地図閲覧装置１０５の装置固有の装置ＩＤ（例えば、ＭＡＣアドレス（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ Ａｄｄｒｅｓｓ）等）を利用し、地図閲覧装置１０５からの認証用の情報を受け付けることによってユーザ認証を行えばよい。或いは、地図閲覧装置１０５を利用するユーザのＩＤ／ＰＷ（Ｐａｓｓｗｏｒｄ）の入力を求め、これを利用してユーザ認証を行ってもよいし、ＳＳＬ（Ｓｅｃｕｒｅ Ｓｏｃｋｅｔｓ Ｌａｙｅｒ）などの暗号技術を用いた認証や生体情報を利用したユーザ認証を利用してもよい。
【００４５】
また、上記のユーザ認証の結果、地図閲覧装置１０５に開示すべきでない情報が明らかな場合（ある利用者に対して非開示とする範囲が明らかな場合）には、ステップＳ４０２における地図格納装置１０２への経路探索用データの検索要求において、開示すべきでない情報を含む範囲を除いた検索要求を行い、開示可能な範囲のみの検索要求を行ってもよい。例えば、上記のユーザ認証の結果、ユーザが非開示領域すべてに対して閲覧権限を持たない場合には、ステップＳ４０３の地図格納装置１０２からの検索結果の送信には、開示範囲のみの経路探索用データを含めればよい。
【００４６】
ステップＳ４０１における経路探索要求の送信では、例えば、現在位置（出発地）と目的地の座標情報（以下、単に位置情報と呼ぶこともある。）が地図配信装置１０４に送信される。ステップＳ４０２およびＳ４０３においては、地図配信装置１０４のクエリ処理部１１７は、その位置情報を元に地図格納装置１０２に対し検索処理を行い、現在位置および目的地に最も近いノードを出発地ノードおよび目的地ノードとし、経路探索に必要な経路探索用データと対応する暗号化データを地図格納装置１０２から取得する。このとき、経路探索に必要なデータは、例えば、探索範囲が建物の１階のみや町内など、限られた範囲であることが明らかである場合には、特定の範囲のみを探索に用いる経路探索用データとして取得すればよい。
【００４７】
また、ステップＳ４０２およびＳ４０３の処理は対話的に行ってもよい。例えば、ステップＳ４０１から送信された経路探索要求の出発地や目的地が地名や部屋の名称などである場合には、地図配信装置１０４が地図格納装置１０２に問い合わせを行い、名称から地物を特定し、地物に関連づけられたノード、或いは、地物の位置からノードを特定すればよい。
【００４８】
或いは、出発地ノード、または、目的地ノードが暗号化されている場合には、地図配信装置１０４が、経路探索要求に含まれる位置情報から地物を特定し、特定された地物に関連する暗号化データを地図格納装置１０２から取得し、地図配信装置１０４が地図復号装置１０６にその暗号化データを送信し、地図復号装置１０６が暗号化データを復号して地物のノードを取得すればよい。なお、経路探索用データの詳細については後述する。
【００４９】
或いは、上記の地名や部屋名称から出発地、或いは、目的地を特定する場合においても、地物そのもの、或いは、地物の属性情報が暗号化されている等の理由により、直接地物を特定できない場合がある。この場合には、例えば、地図格納装置１０２が、暗号化地図データ１２４以外に、上記地名や部屋の名称等を含むキーワードリストを、暗号化された地物、或いは属性情報に対応付けて記憶し、これらを管理するようにしてもよい。このようなキーワードリストを作成することによって、上記の地名や部屋名称といったキーワード検索に対応することが可能となる。
【００５０】
また、キーワードリストには、キーワードそのものを保管するのではなく、例えば、ＳＨＡ−１などの暗号学的ハッシュ関数を用いることによって、ハッシュ値を生成し、これを保管してもよい。暗号学的ハッシュ関数の一方向性の性質から、キーワードリストに格納されたハッシュ値からもとのキーワードを知ることが困難になる。さらに、各キーワードは、上述したようなユーザ認証によって利用可能なキーワードを制限することが望ましい。なお、キーワードリストの作成方法については、上記に限らず、他の方法を利用してもよい。
【００５１】
また、地図復号装置１０６の復号処理において、暗号化データが復号できなかった等の理由により、以上に示したいずれかの方法で、出発地ノード、目的地ノードが得られなかった場合には、「目的地が見つかりません」などのエラーを地図閲覧装置１０５に送信し、処理を終了する。
【００５２】
なお、ステップＳ４０５までの処理によって経路探索が終了する。経路探索の結果は、上述したノードとリンクの集合である。ステップＳ４０６では、経路探索結果によって得られるノードの座標情報、或いは、関連付けられた地物を元に再度地図格納装置１０２に検索要求を送信し、経路探索結果を記載した周辺地図画像を作成する。なお、ステップＳ４０７から検索結果に暗号化データが含まれている（経路探索用データ以外の地図データそのものが暗号化されている）場合には、ステップＳ４０９内で復号処理を行い、地図データの復元を行ってもよい。
【００５３】
上記のステップＳ４０２からステップＳ４０５の処理は、繰り返し行ってもよい。例えば、経路探索の範囲が大きい場合や地図送信装置１０５からの経路探索要求の送信（ステップＳ４０１）が経由地を指定している場合には、経由地を目的地ノード、或いは、出発地ノードとして、ステップＳ４０２からステップＳ４０５までの処理を複数回繰り返して処理を行ってもよい。
【００５４】
ステップＳ４１０の地図閲覧装置１０５への表示用地図イメージの送信においては、上記ステップＳ４０９で生成された経路探索結果を表示した周辺地図画像だけではなく、例えば、タイトルやコスト（例えば、移動時間や料金）などをＨＴＭＬ（Ｈｙｐｅｒｔｅｘｔ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）で成形して送信してもよい。なお、この処理は、ステップＳ４０９内で行ってもよい。
【００５５】
次に、地図暗号化装置１０１が記憶する平文地図データ１２０のデータ構造について説明する。図５は、平文地図データ１２０のデータ構造の一部とその表示イメージ５１０を示す図である。
【００５６】
図５に示すように、平文地図データ１２０は、地図データ格納部５００と、経路探索用データ格納部５０１とを含んで構成され、経路探索用データ格納部５０１には、ノード格納部５０２およびリンク格納部５０３が格納されている。ここで、ノード格納部５０２とリンク格納部５０３は、経路探索の際に用いられるデータを格納しており、ノード格納部５０２には経路探索用データのノードと各ノードの地図上の対応位置座標、或いは、対応地物の情報が格納される。また、リンク格納部５０３には、ノード格納部５０２内に格納されたノード間を接続するリンク情報とその移動コストの情報が格納される。ここで、移動コストとは移動に要する時間、直線距離、或いは、経費などである。なお、ノード格納部５０２とリンク格納部５０３のデータ構造については、図９を用いて後述する。
【００５７】
図５に示したように、地図データ格納部５００には地図上の各地物の種類、名称などの属性情報とその地物の地図上での位置（座標）、形状を表すジオメトリが対応付けて構成される。なお、属性情報のうち、地図データ格納部５００のＦＩＤ（Feature ID）は、各地物を一意に識別するための識別子である。
【００５８】
また、図５の下部には、経路探索の結果、地図閲覧装置１０５に表示される表示イメージ５１０を示している。表示イメージ５１０は、地図データ格納部５００内に格納された地物のオメトリ、属性情報、および、ノード格納部５０２、リンク格納部５０３内に格納された位置情報とノード間の接続情報にしたがって作成される。
【００５９】
なお、図５に示した平文地図データ１２０の地図データ格納部５００は、上述した各種のデータが表形式で表現されているが、これに限らずともよい。例えば、ＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ）には、単純な表形式ではなく、例えば地物を最小単位（オブジェクト、フィーチャなどと呼ぶ）とし、同一の性質、或いは、場所に存在する複数のフィーチャをまとめてコンテナと呼ばれる単位にまとめ、管理し、コンテナを地図の構造（例えば、建物の構造等）に応じて配置することによって、木構造を用いて表現するものもある。このような場合でも、図５の表の各行を上記のフィーチャとして扱うことによって、同様に適用可能である。
【００６０】
続いて、暗号化定義情報１２１について説明する。図６は、暗号化定義情報１２１の一例を示す図である。図６に示すように、暗号化定義情報１２１には、暗号化対象となるノードと、経路探索要求を行う利用者とが対応付けて記述されている。なお、以下では、これらの情報がＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）をもちいて記述されているものとして説明している。
【００６１】
暗号化定義情報１２１は、経路を検索するための要素として、暗号化対象ノード要素から構成される。暗号化対象ノード要素内には、暗号化対象となるノードを指定するノードリスト要素と、開示先を設定するための開示先リスト要素がある。ノード要素には暗号化対象となるノードＩＤを記述し、開示先要素に開示先の利用者、或いは、利用者の種別を一意に特定する識別子等を記述することによって、それぞれ、ノード、利用者を特定する。図６に示した例では、暗号化対象ノードとして、ノードＩＤ（ＮＩＤ）が「Ｎ０１」および「Ｎ０２」のノードが記述され、開示先リストとして、「ユーザＡ」および「ユーザＢ」が記述され、これらのノードは、ユーザＡおよびユーザＢにのみ開示することを示している。
【００６２】
ここで、利用者を一意に識別するための識別子とは、例えば、社員番号や会員番号、ｅ−ｍａｉｌアドレス等を用いればよい。なお、ノード要素、開示先要素を同一の暗号化対象ノード要素内で複数指定する理由は、開示先が同一であるノードをまとめ、開示先を複数指定可能とするためである。このように、暗号化対象ノードを複数指定することで、開示先の異なる複数のノードリストを設定することが可能である。
【００６３】
本実施例では、暗号技術、すなわち、復号鍵１２３の有無に応じて開示先の制限を行うため、開示先要素には利用者、或いは、利用者の種別を特定する識別子ではなく、復号鍵に対応する暗号化鍵１２２の識別子、或いは、参照先を記述するようにしてもよい。上記の開示先要素に利用者、或いは、利用者の識別子を記述した場合には、記述された識別子から暗号化鍵１２２、或いは、その参照先を特定し、暗号化処理時に暗号化鍵１２２を利用する。
【００６４】
なお、図６に示した暗号化定義情報１２１は、開示先リストや開示先などの要素名は異なるものであってもよい。また、ＡＳＮ．１など、ＸＭＬ以外の他のデータ表現を用いてもよい。また、例えば地物そのもの、或いは、地物の属性情報、ジオメトリなど、経路探索用データ以外のデータの開示先を制限する場合には、暗号化定義情報要素内に暗号化対象ノードとは異なる子要素を追加し、開示先の設定を行えばよい。
【００６５】
続いて、図３に示したステップＳ３０７（暗号化処理）、図４に示したステップＳ４０５（復号化処理）、および暗号化処理前後でのデータ構造の変化について説明する。まず、暗号化処理の前後におけるデータ構造の変化を、図９を用いて説明する。なお、図９は、図５に例示した表示イメージ５１０の経路探索用データ格納部５０１の一部を例示した図である。前述の通り、経路探索用データ格納部５０１は、経路探索用データを構成するノードとリンクのうち、ノードに関する情報を格納するノード格納部５０２と、リンクに関する情報を格納するリンク格納部５０３から構成される。
【００６６】
図９は経路探索用データ格納部５０１の例を示す図である。図９に示すように、経路探索用データ格納部５０１ａのノード格納部５０２ａには、各ノード情報を格納するため、ノードを一意に識別する識別子であるＮＩＤと、ノードの地図上の位置情報を表す座標と、暗号化処理後に隣接ノードが暗号化されているか否かを表す復号フラグと、を含んで構成される。また、リンク格納部５０３ａは、リンクを一意に識別するための識別子、接続関係のうち始点側のノードを特定するための始点ＮＩＤと、終点側のノードを特定するための終点ＮＩＤと、ノード間の移動コストを表すコストと、を含んで構成される。
【００６７】
なお、始点ＮＩＤおよび終点ＮＩＤは、ノード間の一方向への移動を表すためのものであり、ノード間の接続関係が全て両方向である場合には、始点ＮＩＤ、終点ＮＩＤの区別は不要である。また、始点ＮＩＤ、終点ＮＩＤの区別がある場合に、双方向での移動コストを表現する場合には、始点ＮＩＤと終点ＮＩＤを入れ替えたデータを別途入力する、或いは、リンク格納部５０３ａに双方向であることを表すためのデータを新たに追加するなどすればよい。また、図９に示したリンク格納部５０３ａは、コストの一例として移動時間のみを格納しているが、これ以外にも複数のコストを格納してもよい。例えば、車や自転車、徒歩など利用者の移動方法などに応じて、移動距離や時間等の複数のコストを格納するようにしてもよい。以下では、コストがひとつである場合について説明を行うが、複数格納されている場合でも、同様の手順で暗号化を行うことが可能である。
【００６８】
図９に示したノード格納部５０２ａ、リンク格納部５０３ａには、例えば、名称や補足説明、或いは、関連する地物のＦＩＤなどの情報を含んでもよい。なお、ノード格納部５０２ａ内の復号フラグは暗号化後に必要となるデータであるため、経路探索用データ格納部５０１ａにはなくてもよい。
【００６９】
暗号化経路探索用データ５０４ａは、経路探索用データ５０１ａのうち、ＮＩＤがＮ５のノードを暗号化した場合の暗号化結果を表している。暗号化経路探索用データ５０４ａは、ノード格納部５０２ａと、リンク格納部５０３ａと、暗号化データ部５０５ａと、を含んで構成されている。
【００７０】
暗号化データ部５０５ａは、ノード、及びリンクを暗号化した結果を格納する暗号化データと、暗号化データを一意に識別するための識別子であるＣＩＤと、復号時に復号すべき暗号化データを特定するためのＦＩＤとＮＩＤとを含む関連データと、を含んで構成される。
【００７１】
本実施例で説明するように、地図暗号化装置１０１の暗号化処理部１１１が行う経路探索データの暗号化では、暗号化対象となるノード、及びそのノードに接続された全てのリンク（例えば、図９に示した太枠部分）を、暗号化後のノード格納部５０２ａ、およびリンク格納部５０３ａから削除し、暗号化対象のノードの全ての隣接ノードの復号フラグをＴ（ＴＲＵＥ）に設定する。なお、復号フラグがＴでないノードには、Ｆ（ＦＡＬＳＥ）を設定する。
【００７２】
暗号化対象となるノードとそれに接続された全リンク（以下、これら暗号化を行うデータを暗号化対象データと呼ぶ。）は、暗号化定義情報１２１の開示先要素の設定に従い暗号化を行い、その暗号化結果のＢＡＳＥ６４符号化した結果を暗号化データに格納する。なお、暗号化データには、ノードとリンクに関する全てのデータの暗号化結果を格納することが必要となるが、これには例えばＸＭＬなどを用いてＮＩＤ、座標などの各データを構造化した結果をＢＡＳＥ６４符号化した結果を格納すればよい。
【００７３】
上記の暗号化対象データの暗号化にあたっては、暗号化対象データを開示先ごとに暗号化鍵１２２を用いて個別に暗号化し、その結果を、ＸＭＬなどを用いて整形し、暗号化データ部５０５ａに書き込んでもよいし、例えば、以下のようにしてもよい。
【００７４】
まず、鍵管理装置１０３の鍵生成部１１３が共通鍵暗号技術におけるランダムな共有鍵（以下、セッション鍵と呼ぶ。）を暗号化対象ノードごとに別々に生成し、地図暗号化装置１０１に送信する。次に、地図暗号化装置１０１の暗号化処理部１１１は、暗号化対象ノードごとに生成されたセッション鍵を暗号化定義情報１２１内の開示先ごとに以下のように暗号化する。
【００７５】
まず、各暗号化対象ノードに設定された開示先に、現在処理を行っている開示先と一致する開示先が存在すれば、現在処理を行っている暗号化対象ノードのセッション鍵をセッション鍵暗号化リストに加える。これを全ての暗号化対象ノードに対して繰り返すことにより、現在処理中の開示先が復号可能な暗号化対象ノードのセッション鍵のセッション鍵暗号化リストが作成される。次に生成されたセッション鍵暗号化リストを集約し、その開示先の暗号化鍵１２２を用いて暗号化する。以下、同様の処理を全ての開示先に対して繰り返し、その結果を、ＸＭＬなどを用いて整形し、暗号化データ部５０５ａに書き込めばよい。上記では、暗号化対象ノードごと暗号化しているが、前述のようにノード格納部５０３ａが複数のコストを含む場合には、個々のコストごとにセッション鍵を割り当てるようにしてもよい。
【００７６】
なお、上記のセッション鍵暗号化リストの暗号化鍵１２２による暗号化において、復号時に暗号化対象ノードの完全性を保証するための暗号化対象ノードのハッシュ値や、ＭＡＣ（Ｍｅｓｓａｇｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｃｏｄｅ）などを含めてもよい。上記の暗号化処理は、選択的開示型暗号と呼ばれ、特開２００９−４９９７３１などで公開されているものである。
【００７７】
経路探索では、ダイクストラ法、或いはダイクストラ法を改良した経路探索アルゴリズムが用いられる。これらの経路探索アルゴリズムでは、あるノードを起点（起点ノードと呼ぶ）として、その隣接ノードを探索し、出発地ノードから隣接ノードへの合計コストの評価を繰り返すことによって、目的地ノードまでの合計コストを求め、最終的な出発点から目的地への経路探索が行われる。ダイクストラ法は、出発地ノードから目的地ノードまでの経路を、上記の手順を中核処理として、これを繰り返して探索を行う幅優先探索の経路探索アルゴリズムである。ダイクストラ法におけるコスト評価や探索の打切り条件等を改良することによって効率的な経路探索を行うアルゴリズムが知られている（例えばＡ＊法など）。
【００７８】
そして、地図復号装置１０６の復号処理部１１６が復号化処理を行う際には、上記の隣接ノードの探索の際に、まず復号すべきデータの有無を起点ノードの復号フラグによって判断する。そして、復号フラグがＴであった場合には、暗号化データ部５０５ａの関連データを参照し、復号すべき暗号化データを取得する。次に、復号処理を実行し、暗号化データが復号された場合には、復号データからノード、リンクを復元し、経路探索を継続する。
【００７９】
以下に、上述した暗号化処理、復号化処理の具体的な処理手順を図７、図８を用いて説明する。本実施例では、上記のダイクストラ法の中核処理の中で復号処理を行う方法を説明するが、経路探索アルゴリズムはダイクストラ法に限定されるものではなく、ダイクストラ法を拡張した他の経路探索アルゴリズムにも適用可能である。
【００８０】
本実施例における暗号化後には、暗号化対象ノードの全ての隣接ノードの復号フラグにはＴが設定されている。経路探索アルゴリズム内で、起点ノードの復号フラグがＴに設定されている場合には、暗号化データ部５０５ａ内から復号すべき暗号化データを検索し、復号処理部１１６に与えられた復号鍵１２３を用いて暗号化データを復号する。この復号によって暗号化データが復号できた場合には、ノード格納部５０２ａ、リンク格納部５０３ａに復号されたデータを復元する。なお、暗号化データ部５０５ａ内からの復号すべき暗号化データの検索には、暗号化データ部５０５ａの関連データを利用する。
【００８１】
以下、本実施例における具体的な暗号化処理、復号化処理について説明する。図７は、本実施例における暗号化処理の処理手順を示すフローチャートである。
【００８２】
図７に示すように、暗号化処理が開始されると（ステップＳ７００）、地図暗号化装置１０１の暗号化処理部１１１は、平文地図データ１２０を構成している経路探索用データ格納部５０１ａを暗号化経路探索用データ格納部５０４ａにコピーし、一度、復号フラグをＦにセットする（ステップＳ７０１）。
【００８３】
そして、暗号化処理部１１１は、暗号化定義情報１２１を参照し、暗号化すべき暗号化対象ノードの有無を判定する（ステップＳ７０２）。そして、暗号化処理部１１１は、暗号化すべき暗号化対象ノードがあると判定した場合（ステップＳ７０２；Ｙｅｓ）、ステップＳ７０３に進み、暗号化すべき暗号化対象ノードがないと判定した場合（ステップＳ７０２；Ｎｏ）、図７に示す暗号化処理を終了させる（ステップＳ７１０）。
【００８４】
暗号化すべき暗号化対象ノードがあると判定すると（ステップＳ７０２；Ｙｅｓ）、暗号化処理部１１１は、暗号化定義情報１２１に記述されている暗号化対象ノードを取得し（ステップＳ７０３）、リンク格納部５０３ａを参照し、取得した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあるか否かを判定する（ステップＳ７０４）。
【００８５】
そして、暗号化処理部１１１は、取得した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあると判定した場合（ステップＳ７０４；Ｙｅｓ）、その接続リンクを関連リンクとして取得し（ステップＳ７０５）、取得した暗号化対象ノードに接続された接続リンクから暗号化対象ノードの隣接ノードを特定し、復号フラグをＴに変更する（ステップＳ７０６）。そして、暗号化処理部１１１は、ステップＳ７０４〜Ｓ７０６までの処理を繰り返し行う。
【００８６】
一方、暗号化対象ノードに接続された接続リンク内に未操作のリンクがないと判定した場合（ステップＳ７０４；Ｎｏ）、暗号化処理部１１１は、暗号化対象ノード、及びステップＳ７０５で取得した関連リンクを暗号化し（ステップＳ７０７）、暗号化対象ノード、及びステップＳ７０５で取得した関連リンクを暗号化経路探索用データ５０４ａ内のノード格納部５０２ａ、リンク格納部５０３ａから削除する（ステップＳ７０８）。
【００８７】
その後、暗号化処理部１１１は、ステップＳ７０７の暗号化結果を暗号化データ格納部５０４ａに格納し（ステップＳ７０９）、ステップＳ７０２へ戻る。そして、暗号化処理部１１１は、暗号化定義情報１２１に記述された全ての暗号化対象ノードについて、繰り返しステップＳ７０２〜Ｓ７０９までの処理を行う。
【００８８】
なお、上記の暗号化処理におけるステップ７０２では、例えば図６に例示した暗号化定義情報１２１の暗号化対象ノード要素を逐次処理し、暗号化対象ノードがなくなるまで繰り返せばよい。このような逐次処理は、例えばＸＭＬのＳＡＸ（Ｓｉｍｐｌｅ ＡＰＩ ｆｏｒ ＸＭＬ）を用いて実現すればよい。
【００８９】
また、図９の例では、暗号化対象ノード（Ｎ５）に接続されているノードは一つ（Ｎ６、リンクはＬ１４）のみであるが（表示イメージは図５参照）、ステップＳ７０４〜Ｓ７０６に示した通り、暗号化対象ノードに隣接ノードが複数ある場合には、これら全ての隣接ノードに対して同様の処理を行う。
【００９０】
なお、ステップＳ７０８における暗号化処理はノード一つずつ行うのではなく、複数のノードをまとめて処理してもよい。この場合には、ステップＳ７０９における暗号化データの暗号化データ部５０５ａへの書き込みは、これらをまとめて暗号化した１つの暗号化データとして行い、関連データに関連した地物、隣接ノードのＮＩＤを全て書き込むようにしてもよい。
【００９１】
また、複数のノードをまとめて処理する場合において、暗号化対象となるノードが同一の領域内にある場合には、領域内の境界線にあるノードの隣接ノードに対してのみステップＳ７０５、ステップＳ７０６を実行すればよい。その理由は、暗号化データの復号によってノード、リンクが復元された場合、領域の中にあるノード、リンクがまとめて復号されるため、領域内の境界以外にあるノード、リンクに対して復号すべきか否かを調べる必要がないためである。
【００９２】
上記の暗号化処理によって、暗号化対象のノード、及びそれに接続されるリンク情報は、すべて暗号化経路探索用データ５０４ａのノード格納部５０２ａ、リンク格納部５０３ａから削除され、その暗号化結果が関連データとともに暗号化データ部５０５ａに格納される。
【００９３】
なお、経路探索では、始点ノードから隣接ノードまでの検索を行ってコストを算出し、算出したコストから出発地ノードからのコスト評価を行うが、上記の暗号化処理では、暗号化されたノードの隣接ノード全ての復号フラグがＴに設定される。従って、経路探索の隣接ノードの検索時に復号フラグがＴであるかどうかを調べることによって、復号すべき暗号化データの有無を知ることができ、経路探索アルゴリズム内の必要箇所で復号することが可能となる。続いて、復号化処理について説明する。
【００９４】
図８は、本実施例における復号化処理の処理手順を示すフローチャートである。図８は、経路探索アルゴリズムにおける復号化処理を行うための処理フローを示したものであり、経路探索アルゴリズムそのものの処理については、その手順の概略のみを示している。なお、図８内の点線内が経路探索アルゴリズムの中核処理である。以下、図８に示す復号化処理について説明する。
【００９５】
図８に示すように、復号化処理が開始されると（ステップＳ８００）、地図復号装置１０６の復号処理部１１６は、まず、出発地ノードを始点ノードに設定する（ステップＳ８０１）。
【００９６】
そして、復号処理部１１６は、経路探索が終了しているか否かを判定し（ステップＳ８０２）、経路探索が終了していると判定した場合（ステップＳ８０２；Ｙｅｓ）、図８に示す復号化処理を終了させる（ステップＳ８１０）。
【００９７】
一方、復号処理部１１６は、経路探索が終了していないと判定した場合（ステップＳ８０２；Ｎｏ）、始点ノードの復号フラグがＴであるか否かを判定し（ステップＳ８０３）、始点ノードの復号フラグがＴであると判定した場合（ステップＳ８０３；Ｙｅｓ）、暗号化データ部５０５ａから暗号化データを取得し、取得した暗号化データを復号する（ステップＳ８０４）。一方、復号処理部１１６は、始点ノードの復号フラグがＴではない（Ｆである）と判定した場合（ステップＳ８０３；Ｎｏ）、ステップＳ８０７に進む。
【００９８】
復号処理部１１６は、ステップＳ８０４で取得した暗号化データの復号に成功したか否かを判定し（ステップＳ８０５）、復号に成功したと判定した場合（ステップＳ８０５；Ｙｅｓ）、ステップＳ８０４における復号結果からノード、リンクを復元し、復元したノード、リンクをノード格納部５０２ａ、リンク格納部５０３ａに追加する（ステップＳ８０６）。一方、復号処理部１１６は、復号に成功していない（失敗した）と判定した場合（ステップＳ８０５；Ｎｏ）、ステップＳ８０７に進む。
【００９９】
そして、復号処理部１１６は、ノード格納部５０２ａとリンク格納部５０３ａとを参照し、始点ノードの接続リンク（隣接ノード）を検索し（ステップＳ８０７）、未探索の隣接ノードがあるか否かを判定する（ステップＳ８０８）。
【０１００】
復号処理部１１６は、未探索の隣接ノードがあると判定した場合（ステップＳ８０８；Ｙｅｓ）、リンク格納部５０３ａ内のコスト欄を参照し、始点ノードから隣接ノードまでのコストを算出し、出発地ノードから隣接ノードまでのコスト評価を行う（ステップＳ８０９）。
【０１０１】
一方、復号処理部１１６は、未探索の隣接ノードがないと判定した場合（ステップＳ８０８；Ｎｏ）、ステップＳ８０２に戻る。そして、復号処理部１１６は、ステップＳ８０２からＳ８１０の処理を経路探索が終了するまで繰り返し行う。
【０１０２】
なお、上記のステップＳ８０４において、例えば、復号結果が正しいノードやリンクではないなどの復号が異常停止した場合には処理を停止することが望ましい。また、経路探索の過程において、目的地ノードにたどりつかないなど、経路探索が一定時間以上終了しない場合や非現実的なコスト（例えば、徒歩での移動に１００年以上かかるなど）であった場合には、ステップＳ８０２において処理を停止してもよい。
【０１０３】
上記のステップＳ８０４における復号、ステップＳ８０６におけるノードおよびリンクの復元は、単一のノードに対してではなく、複数のノード、リンクに対して行ってもよい。例えば、前述の暗号化処理時に複数のノードをまとめて暗号化した場合には、ステップＳ８０４における復号の結果には、複数のノードおよびリンクが含まれるため、ステップＳ８０６は復号されたノードおよびリンクを全て復元することになる。
【０１０４】
なお、上記の復号処理では、経路探索アルゴリズム内で逐次復号を行っているが、事前に復号すべきデータが少ない場合（例えば、ステップ４０３における地図格納装置１０２からの応答に暗号化データが一つしか含まれていない場合など）には、図８の処理の前に復号処理をまとめて実施してもよい。
【０１０５】
また、経路探索においては、データ管理、或いは、経路探索を効率に行うため、ビルのフロア等の階層、或いは領域ごとにデータ管理を行っている場合がある。この場合、経路探索についても、領域ごと、或いは階層別に経路探索アルゴリズムを実行し、これらの結果を繋ぎ合わせることで経路探索を実行し、図８の処理を階層、或いは領域ごとに経路探索してもよい。
【０１０６】
このように、記憶部（あるいは地図格納装置１０２）が、地図上の位置を示すノードおよびノードとノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データ格納部５０１が格納するデータ（経路探索用データ）とノードにある地物を表示させるための地図データ格納部５００が格納するデータ（表示用データ）とが対応付けられた平文地図データ１２０と、ノードと表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報１２１と、経路探索用データを暗号化するための暗号化鍵１２２を格納し、暗号化処理部１１１が、経路探索用データと、暗号化鍵１２２と、暗号化定義情報１２１とに基づいて、利用者ごとに、暗号化すべきノードを特定し、特定したノードおよび特定したノードに隣接するノードの経路探索用データを暗号化し、暗号化した経路探索用データと表示用データとを対応付けた暗号化地図データ１２４を生成する。
【０１０７】
また、復号処理部１１６が、利用者から地図上の位置のある地点から他の地点までの経路を探索するを実行する場合に、暗号化された地図上の位置を示すノードおよびノードとノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データ格納部５０１が格納するデータ（経路探索用データ）を復号化する復号化鍵１２３に基づいて、経路探索用データと、ノードにある地物を表示させるための地図データ格納部５００が格納するデータ（表示用データ）とが対応付けられた暗号化地図データ１２４を復号化し、経路探索部処理部１１４１が、ある地点から他の地点までの経路を、復号処理部１１６による暗号化地図データ１２４の復号化結果を用いて、経路探索用データに含まれるノードとリンク情報とに基づいて繰り返し探索する。
【０１０８】
したがって、利用者ごとに適切な経路探索を行うことができる。すなわち、利用者の種別に応じて開示可能な経路探索データのみを利用した経路探索を行い、利用者の種別ごとに適切な経路探索結果を提供することができる。
【０１０９】
なお、経路探索においては、データ管理、或いは、経路探索を効率に行うため、ビルのフロア等の階層、或いは領域ごとにデータ管理を行っている場合がある。この場合、経路探索についても、領域ごと、或いは階層別に経路探索アルゴリズムを実行し、これらの結果を繋ぎ合わせることで経路探索を実行する場合がある。その場合には、図８の処理を階層、或いは、領域ごとの経路探索を行い、これらの探索結果を組み合わせて、最終的な出発地ノードから目的地ノードまでの経路探索を行ってもよい。
【０１１０】
続いて、地図データ配信システム１の管理者等からの操作を受け付けて、地図暗号化装置１０１が暗号化定義情報１２１の登録や変更等を行う場合について説明する。
【０１１１】
図１０は、暗号化定義情報１２１を生成するためのアプリケーション画面（ＧＵＩ：Ｇｒａｐｈｉｃ Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅ）の実現イメージの一例を示す図である。なお、以下では、図１０を用いて経路探索用データを暗号化する場合のＧＵＩについて説明を行うが、地物そのものの、或いは、その属性、ジオメトリを暗号化する場合には、本ＧＵＩを拡張し、これらもまとめて暗号化できるようにしてもよい。
【０１１２】
図１０に示すように、本ＧＵＩは地図表示エリア１と、設定エリア１００１と、を含んで構成される。なお、ＧＵＩ上部のファイルメニュー１００２、データベースメニュー１００３、鍵読込メニュー１００４は、アプリケーション画面に対する操作を切り替えるためのメニュータグを表す。それぞれのメニュータグが選択された場合、以下の操作を行う（図１０では、「メニュー」は省略した）。
【０１１３】
地図暗号化装置１０１は、ファイルメニュー１００２がアクティブになっている場合、作成済みの暗号化定義情報１２１の読込、或は、作成途中の暗号化定義情報１２１の保存を行う。また、地図暗号化装置１０１は、データベースメニュー１００３がアクティブになっている場合、平文地図データ１２０を格納してあるデータベースへの接続を行い、平文地図データ１２０の読み込み、および、格納先の暗号化地図データ１２４の指定を行う。また、開示設定を終了し、暗号化定義情報１２１を生成する。さらに、地図暗号化装置１０１は、鍵読込メニュー１００４がアクティブになっている場合、暗号化定義情報１２１の設定に必要な暗号化鍵１２２を読み込む。
【０１１４】
なお、上記ではメニューとして、データベースメニュー１００３を配置し、平文地図データ１２０、および暗号化地図データ１２４が、データベースシステム上にあることを想定しているが、必ずしも、地図データ１２０や暗号化地図データ１２４は、データベースシステム上にある必要はなく、例えば、ＣＳＶ（Ｃｏｍｍａ Ｓｅｐａｒｅｔｅｄ Ｖａｌｕｅｓ）などの形式で、ファイルとして存在してもよい。
【０１１５】
図１０に示すＧＵＩにおいて、地図表示エリア１０００は、平文地図データ１２０を描画した結果を表示し、マウスなどの入力装置２０３からの入力に従い、暗号化対象となるノードを指定する。なお、指定にあたっては、図１０に例示したようにマウスの入力に従い矩形領域内に含まれるすべてのノードを暗号化対象ノードとしてもよいし、多角形や円などを利用してもよい。或は、マウスを用いてノードを直接を選択し、選択されたノードを暗号化対象ノードとしてもよいし、マウスによって地物を選択し、地物内に含まれる前ノードを暗号化対象ノードとしてもよい。
【０１１６】
以下では、図１０に示したマウスカーソル１００５で選択された領域の開示先を制限し、領域内に含まれるノードを設定する場合を例として、図１０に例示したＧＵＩの動作を説明する。
【０１１７】
設定エリア１００１は、平文地図データ１２０を非開示とする領域を指定するための非開示エリアと、非開示エリアに含まれる地物を示す関連地物と、非開示エリアに含まれるノードを示す対象ノードと、開示先のユーザを示す開示先と、を含んでいる。
【０１１８】
管理者等によってマウスカーソル１００５で領域が選択されると、設定エリア１００１の非開示エリア項目に新たな項目（図１０内のエリア２とする）が登録される。また、エリア２内に含まれる地物の一覧が関連する地物の一覧が、また、対象ノード欄にエリア２内に含まれるノードの一覧が表示される（図１０に示す例では、Ｎ５（機械室））。
【０１１９】
次に、管理者等によってマウスなどの入力装置２０３を用いて対象地物一覧の中から設定を行う地物やエリアが選択されると（図１０ではエリアを選択している）、選択した地物内の全ての属性がサブ画面（不図示）に表示される。また、このとき、選択された地物が地図上のどの地物であるかを明示するため、地図表示エリア９０６の対応する地物の表示色を変更する、或は、境界線を太くするなどしてもよい。
【０１２０】
次に、開示先を設定するノードを、対象ノードから、あるは関連地物欄内の地物を選択することによって指定する。そして、地図暗号化装置１０１は、開示先欄から開示先として指定するユーザの選択を受け付け、開示先設定ボタンの押下を受け付けると、一つのエリアに対する設定を完了する。このように設定された情報（例えば、図６に示したＡの部分）が、暗号化定義情報１２１として出力される。なお、地物内に含まれる全ノードを選択するために、関連地物欄内の地物を選択するようにしてもよい。上記によって、同一の開示先を持つ複数のノードが設定される。さらに、異なる開示先を持つノードを設定する場合には、上記の処理を繰り返せばよい。
【０１２１】
このように、地図暗号化装置１０１が、ＧＵＩによって暗号化定義情報１２１の設定や変更を受け付けるので、地図データ配信システム１の図管理者等は、その設定や変更を容易に行うことができる。
（第２の実施の形態）
第１の実施の形態では、暗号化対象ノードと暗号化対象ノードに接続された接続リンクを、暗号化後にノード格納部５０２とリンク格納部５０３から削除する方法について述べた。第２の実施の形態では、暗号化対象ノードと接続ノード内のデータを変更することによって暗号化、復号を行う方法について述べる。第１の実施の形態と比較し、第２の実施の形態では、経路探索用データの構造を崩す必要がないという特徴がある。
【０１２２】
第１の実施の形態と第２の実施の形態との違いは暗号処理と復号化処理のみであるため、以下では暗号化処理、復号化処理について、第１の実施の形態におけるとの違いを説明する。
【０１２３】
図１１および図１２は、第２の実施の形態における暗号化処理、復号化処理の処理手順を示すフローチャートである。また、図１３は、暗号化処理前後でのデータ構造の変化の一例を示す図である。以下に、これらの図面を参照して、暗号化処理および復号化処理について説明する。
【０１２４】
まず、暗号化処理の前後におけるデータ構造の変化を、図１３を用いて説明する。なお、図１３は、図９と同様、図５に例示した表示イメージ５１０の経路探索用データ格納部５０１の一部を例示した図である。
【０１２５】
第１の実施の形態の場合と同様、暗号化経路探索用データ格納部５０４ｂは、ノード格納部５０２ｂと、リンク格納部５０３ｂと、暗号化データ部５０５ｂと、を含んで構成される。ノード格納部５０２ｂは、ノードを一意に識別するための識別子であるＮＩＤと、ノードの地図上の位置を表す座標を含み、リンク格納部５０３ｂは、リンクを一意に識別する識別子であるＬＩＤと、ノードの始点と終点のノードを表す始点ＮＩＤと、終点ＮＩＤと、リンクを移動するために必要となるコストとを含んでいる。
【０１２６】
なお、リンク格納部５０３ｂが始点ＮＩＤと終点ＮＩＤから構成されている理由は、移動経路が一方向であることを表すためであり、第１の実施の形態の場合と同様に、双方向のデータ構造を用いてもよい。また、第１の実施の形態と同様に、ノード格納部５０２ｂ、リンク格納部５０３ｂは、上記以外の項目を含んでもよい。
【０１２７】
第１の実施の形態では、暗号化対象ノードとそれに接続した接続リンクをノード格納部５０２ａ、リンク格納部５０３ａから削除し、隣接ノードの暗号化フラグをＴ（ＴＲＵＥ）と設定することによって、経路探索時に復号すべきデータの特定を行った。第２の実施の形態では、図１３に示した通り、ノード格納部５０２ｂ、リンク格納部５０３ｂからデータの削除は行わず、代わりに各格納部に格納された情報を、他のノードやリンクとは区別しうる属性や値となるような情報に書き換えを行う。
【０１２８】
図１３に示した例では、第１の実施の形態と同様、暗号化対象ノードとしてＮ５のノードを暗号化した場合について示している。図１３に示した通り、暗号化対象となるノード（Ｎ５)の座標情報を、暗号化されていることを表す記号「ＥＮＣ」で書き換え、さらに暗号化対象ノード（Ｎ５）の接続リンクのコストを最大値（図１３に示す例では「９９」）に設定する。暗号化対象ノードのもとの座標情報と接続リンクのコストは、第１の実施の形態と同様の方法で暗号化を行い、暗号化データ部５０５ｂに格納する。
【０１２９】
なお、データベース、或いはＧＩＳ製品の制約上の問題で座標情報に座標以外の情報を格納することができない場合には、上記の「ＥＮＣ」への書き換えは、「ＥＮＣ」を意味する代替値であってもよいし、座標情報を別の座標に書き換えてもよい。なお、ノードの位置そのものを非開示にするためには、ランダムな座標位置を用いてもよいが、暗号化後の地図データ（暗号化地図データ１２４）の利用に影響を与えないようにするためは、平文地図データ１２０内の管理外の座標情報を格納する方が望ましい。
【０１３０】
また、例えば、同一の地物内に複数のノードが存在する場合には、地物の中心座標などで座標情報を置き換えてもよい。これによって、本来のノードの座標位置をある程度非開示にすることができる。また、複数のノードを暗号化する場合には、第１の実施の形態のように、代表点のみ残し、後のノード、リンクは、ノード格納部５０２ｂ、リンク格納部５０３ｂから削除してもよい。なお、座標情報を書き変えなくてもよいが、この場合には、コストのみが暗号化され、ノードが地図上のどの位置に配置されているかがわかってしまうため、注意が必要である。
【０１３１】
復号時には、復号処理部１１６が、ノード格納部５０２ｂの座標情報が「ＥＮＣ」である場合、或いは、リンク格納部５０３ｂのコストが最大値である場合に暗号化データ部５０５ｂの関連データを基に復号すべき暗号化データを取得、復号する。この復号処理によって、ノード、リンクが復号された場合には、復号結果からノードの座標、及び、リンクのコストを復元することにより、元の地図データ（平文地図データ１２０）を用いた経路探索が実行できる。一方で、復号できなかった場合にはコストは最大値のままとなっているため、経路探索のコスト評価の際、他の最適な経路と比較した場合に削除可能、或いは、非現実的な経路として削除することができる。
【０１３２】
以下、図１１および図１２を用いて、第２の実施の形態における暗号化、復号化処理の具体的な処理手順を説明する。まず、第２の実施の形態における暗号化処理について説明する。図１１は、第２の実施の形態における暗号化処理の処理手順を示すフローチャートである。
【０１３３】
図１１に示すように、第２の実施の形態における暗号化処理が開始されると（ステップＳ１１００）、暗号化処理部１１１は、経路探索用データ格納部５０１ａを暗号化経路探索用データ格納部５０４ａにコピーする（ステップＳ１１０１）。
【０１３４】
そして、暗号化処理部１１１は、暗号化定義情報１２１を参照し、暗号化すべき暗号化対象ノードの有無を判定する（ステップＳ１１０２）。そして、暗号化処理部１１１は、暗号化すべき暗号化対象ノードがあると判定した場合（ステップＳ１１０２；Ｙｅｓ）、暗号化定義情報１２１に記述されている暗号化対象ノードを取得し（ステップＳ１１０３）、その暗号化対象ノードを変更する（ステップＳ１１０４）。一方、暗号化処理部１１１は、暗号化すべき暗号化対象ノードがないと判定した場合（ステップＳ１１０２；Ｎｏ）、図１１に示す暗号化処理を終了させる（ステップＳ１１１０）。
【０１３５】
そして、暗号化処理部１１１は、変更した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあるか否かを判定し（ステップＳ１１０５）、変更した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあると判定した場合（ステップＳ１１０５；Ｙｅｓ）、その接続リンクのコストを取得し（ステップＳ１１０６）、取得したコストを最大値に設定する（ステップＳ１０７）。そして、暗号化処理部１１１は、ステップＳ１１０５〜Ｓ１１０７までの処理を繰り返し行う。
【０１３６】
一方、暗号化処理部１１１は、暗号化対象ノードに接続された接続リンク内に未操作のリンクがないと判定した場合（ステップＳ１１０５；Ｎｏ）、ステップＳ１１０３において取得した座標情報と、ステップＳ１１０６において取得したコストとを暗号化し（ステップＳ１１０８）、その暗号化結果を暗号化データ格納部５０４ａに格納し（ステップＳ１１０９）、ステップＳ１１０２へ戻る。そして、暗号化処理部１１１は、暗号化定義情報１２１に記述された全ての暗号化対象ノードについて、繰り返しステップＳ１１０２〜Ｓ１１０９までの処理を行う。
【０１３７】
なお、ステップＳ１１０２では、例えば、図６に例示した暗号化定義情報１２１の暗号化対象ノード要素を逐次処理し、暗号化対象ノード要素がなくなるまで繰り返せばよい。また、図９に示した例では、暗号化対象ノード（Ｎ５）に接続されているノードは一つ（Ｎ６、リンクはＬ１４）のみであるが、ステップＳ１１０５〜Ｓ１１０７に示した通り、接続リンクが複数ある場合には、全ての接続リンクに対して同様の処理を行う。
【０１３８】
第１の実施の形態と同様、ステップＳ１１０８における暗号化処理は、ノードを一つずつ行うのではなく、複数のノードをまとめて暗号化してもよい。また、複数ノードを暗号化する場合には、以下のようにしてもよい。例えば、座標情報の書き換えに際して「ＥＮＣ」の代わりに、暗号化対象となるノードが同一の領域内にある場合には、ステップ１１０４の処理を領域の中心座標などを格納するようにしてもよい。また、この場合に第１の実施の形態と同様に、代表点となるノードのみを残し、他のノードリンクをノード格納部５０２ｂ、リンク格納部５０３ｂから削除してもよい。なお、この場合、削除したノードに合わせて、リンク格納部５０３ｂの始点ＮＩＤ、終点ＮＩＤも書き換える必要があることに注意が必要である。
【０１３９】
続いて、第２の実施の形態における復号化処理について説明する。図１２は、第２の実施の形態における復号化処理の処理手順を示すフローチャートである。なお、第１の実施の形態と同様、図１２は、経路探索アルゴリズムにおける復号処理を行うための処理フローを示したものであり、経路探索アルゴリズムそのものの処理は、その手順の概略のみを示している。経路探索アルゴリズムの中核処理は、図１２内の点線で示した部分である。以下、図１２に示す復号化処理について説明する。
【０１４０】
図１２に示すように、復号化処理が開始されると（ステップＳ１２００）、地図復号装置１０６の復号処理部１１６は、まず、出発地ノードを始点ノードに設定する（ステップＳ１２０１）。
【０１４１】
そして、復号処理部１１６は、経路探索が終了しているか否かを判定し（ステップＳ１２０２）、経路探索が終了していると判定した場合（ステップＳ１２０２；Ｙｅｓ）、図８に示す復号化処理を終了させる（ステップＳ１２１０）。
【０１４２】
一方、復号処理部１１６は、経路探索が終了していないと判定した場合（ステップＳ１２０２；Ｎｏ）、ノード格納部５０２ａとリンク格納部５０３ａとを参照し、始点ノードの接続リンク（隣接ノード）を検索し（ステップＳ１２０３）、未探索の隣接ノードがあるか否かを判定する（ステップＳ１２０４）。
【０１４３】
そして、復号処理部１１６は、未探索の隣接ノードがあると判定した場合（ステップＳ１２０４；Ｙｅｓ）、さらにその未探索の隣接ノードを関連データとして有する暗号化データが暗号化データ部５０５ｂにあるか否かを判定し（ステップＳ１２０５）、暗号化データが暗号化データ部５０５ｂにあると判定した場合（ステップＳ１２０５；Ｙｅｓ）、暗号化データ部５０５ａから暗号化データを取得し、取得した暗号化データを復号する（ステップＳ１２０６）。一方、復号処理部１１６は、暗号化データが暗号化データ部５０５ｂにないと判定した場合（ステップＳ１２０５；Ｎｏ）、ステップＳ１２０９に進む。
【０１４４】
復号処理部１１６は、ステップＳ１２０６で取得した暗号化データの復号に成功したか否かを判定し（ステップＳ１２０７）、復号に成功したと判定した場合（ステップＳ１２０７；Ｙｅｓ）、ステップＳ１２０６における復号結果からノード、リンクを復元し、復元したノード、リンクをノード格納部５０２ｂ、リンク格納部５０３ｂに追加する（ステップＳ１２０８）。一方、復号処理部１１６は、復号に成功していない（失敗した）と判定した場合（ステップＳ１２０７；Ｎｏ）、ステップＳ１２０９に進む。
【０１４５】
そして、復号処理部１１６は、ステップＳ１２０５またはステップＳ１２０７またはステップＳ１２０８のいずれかの処理が終了すると、リンク格納部５０３ａ内のコスト欄を参照し、始点ノードから隣接ノードまでのコストを算出し、出発地ノードから隣接ノードまでのコスト評価を行い（ステップＳ１２０９）、ステップＳ１２０２に戻る。そして、復号処理部１１６は、ステップＳ１２０２からＳ１２０９までの処理を経路探索が終了するまで繰り返し行う。
【０１４６】
第２の実施の形態では、暗号化時に暗号化対象ノードの接続リンクのコストを最大にする。これにより、暗号化データが復号できなかった場合には、ステップＳ１２０９において、コスト最大として出発点ノードから該当ノードまでのコスト評価が行われるため、非現実的なコストとなり、他の最適なコストを有する経路があった場合に、暗号化ノードを含む経路を排除することができる。したがって、図５に示したように、最終的に利用者には、そのような経路を含まない表示イメージ５１０が表示されることとなる。
【０１４７】
なお、上記のステップＳ１２０６において、例えば復号結果がノード、リンクでないなどの復号が異常停止した場合には処理を停止することが望ましい。また、経路探索の家庭において、目的地ノードにたどりつかないなど、経路探索が一定時間以上終了しない場合や非現実的なコスト（例えば、徒歩での移動に１００年以上かかるなど）であった場合には、ステップＳ１２０２において処理を停止してもよい。
【０１４８】
上記のステップＳ１２０６における復号、ステップＳ１２０８におけるノード、リンクの復元は、単一のノードに対してではなく、複数のノード、リンクに対して行ってもよい。例えば、前述の暗号化処理時に複数のノードをまとめて暗号化した場合には、ステップＳ１２０６における復号の結果には、複数のノード、リンクが含まれるため、ステップＳ１２０８は復号されたノード、リンクを全て復元することになる。
【０１４９】
なお、上記の復号処理では、経路探索アルゴリズム内で逐次復号を行っているが、事前に復号すべきデータが少ない場合（例えば、ステップＳ４０３における地図格納装置１０２からの応答に暗号化データが一つしか含まれていない場合など）には、復号処理部１１６は、図１２の処理の前に復号処理をまとめて実施してもよい。
【０１５０】
また、第１の実施の形態と同様、経路探索においては、データ管理、或いは、経路探索を効率に行うため、ビルのフロア等の階層、或いは領域ごとにデータ管理を行っている場合がある。この場合、経路探索についても、領域ごと、或いは階層別に経路探索アルゴリズムを実行し、これらの結果を繋ぎ合わせることで経路探索を実行する場合がある。その場合には、図１２の処理を階層、或いは、領域ごとの経路探索を行い、これらの探索結果を組み合わせて、最終的な出発地ノードから目的地ノードまでの経路探索を行ってもよい。
【０１５１】
なお、本発明は、上記実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【０１５２】
１：地図データ配信システム、１００：ネットワーク、１０１：地図暗号化装置、１０２：地図格納装置、１０３：鍵管理装置、１０４：地図配信装置、１０５：地図閲覧装置、１０６：地図復号装置、１１０：暗号化情報生成部、１１１：暗号化処理部、１１２：データベース処理部、１１３：鍵生成部、１１４：経路探索処理部、１１５：クエリ要求部、１１６：復号処理部、１１７：クエリ処理部、１１８：表示処理部、１２０：平文地図データ、１２１：暗号化定義情報、１２２：暗号化鍵、１２３：復号鍵、１２４：暗号化地図データ、２００：計算機、２０１：ＣＰＵ、２０２：ＲＡＭ、２０３：入力装置、２０４：表示装置、２０５：通信装置、２０６：読書装置、２０７：外部記憶装置、２０８：外部記憶媒体、２０９：インターフェイス、５００：地図データ格納部、５０１：経路探索用データ格納部、５０２：ノード格納部、５０３：リンク格納部、５１０：表示イメージ５１０、５０１ａ：経路探索用データ格納部、５０２ａ：ノード格納部、５０３ａ：リンク格納部、５０４ａ：暗号化経路探索用データ格納部、５０５ａ：暗号化データ部、１０００：地図表示エリア、１００１：設定エリア、１００２：ファイル、１００３：データベース、１００４：鍵読込、１００５：マウスカーソル、５０１ｂ：経路探索用データ格納部、５０２ｂ：ノード格納部、５０３ｂ：リンク格納部、５０４ｂ：暗号化経路探索用データ格納部、５０５ｂ：暗号化データ部。
【技術分野】
【０００１】
本発明は、暗号化された経路探索用データを利用した暗号化装置、復号化装置、および経路探索システムに関するものである。
【背景技術】
【０００２】
地理情報システムでは地図表示や経路探索など様々な機能が提供される。こられのうち経路探索では、ノードとリンクから構成される経路探索用データを用いて、ダイクストラ法などの経路探索アルゴリズムを用いて、出発点と目的地の経路探索が行われる。
【０００３】
ところで地図情報には、例えば、軍事基地や個人所有の敷地、或は、企業の工場など、一般に開示しないことが望ましい情報が多数含まれる。従来、地理情報配信システムでは、屋外の地図情報を提供するサービスが多かったが、近年の情報サービス産業の発展に伴い、地下街や駅構内など、屋内の地図情報を提供するサービスも増えてきている。これら屋内の地図情報には、例えば、店舗における従業員の作業エリアやオフィス内の間取図など、一般に公開すべきでない情報が含まれる。また、例えばオフィス内の間取図では、機密文書の保管場所など、地図情報の利用者に応じて適切に開示する情報を制限する必要がある。従って、経路探索についても、利用者の開示範囲に応じて適切な範囲内での経路探索を行うことが望まれる。
【０００４】
従来の技術では、ネットワークや放送により地図情報を車両に配信する場合に配信先の車両に応じて適切な情報のみが開示されるよう、車両別に地図情報を管理し、それぞれの地図情報を個別の鍵で暗号化することによって、車両の種別に応じた地図情報の開示制限を行う技術が知られている（例えば、特許文献１）。
【０００５】
また、経路探索用データに対しては、利用者が経路探索用データを編集し、経路探索用データの改ざんを、暗号を用いて保護する方法が知られている（例えば特許文献２）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−１２１７１９号公報
【特許文献２】特開２０００−１９３４７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１では、種別に応じた地図情報の開示において、暗号化した地図情報を送信先の車両種別ごとに準備し、車には種別ごとに秘密鍵を事前に格納しておく。これによって、暗号化された地図情報を配信し、特定の車両種別のみが暗号化された地図を復号することができ、車両の種別に応じた開示制限が可能となる。
【０００８】
しかしながら、特許文献１で開示された方法では、地図を構成する地物の形状、及び、それに付随した名称等の属性情報を対象としており、経路探索用データの暗号化については開示されていない。また、経路探索では、任意の出発点から目的地までの経路を探索する必要があり、利用者ごとの要求に応じて経路探索を実行することが必要となる。特許文献１のように、事前に暗号化データを用意して一斉配信する方法では、利用者の種別ごと、或いは、出発地・目的地ごとの経路探索結果を個別に暗号化して管理すること必要となる。そのため、管理するデータサイズの増加や、事前に用意した地点間の経路探索結果しか提供できず、利用者ごとに適切な経路探索を行うことができないという問題が生じる。
【０００９】
また、特許文献２に開示された方法では、経路探索用データの改ざんを防止する方法が述べられているが、経路探索用データの開示先を利用者、或いは、利用者種別ごとに制限する方法については開示されておらず、特許文献１と同様に、利用者ごとに適切な経路探索を行うことができないという問題がある。
【００１０】
本発明は、上記に鑑みてなされたものであって、利用者ごとに適切な経路探索を行うことができる暗号化装置、復号化装置、および経路探索システムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した目的を達成するために、本発明にかかる暗号化装置は、地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと前記検索用データに対応した地図を表示させるための表示用データとが対応付けられた地図データと、前記ノードと前記表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報と、前記経路探索用データを暗号化するための暗号化鍵を格納する記憶部と、前記経路探索用データと、前記暗号化鍵と、前記暗号化定義情報とに基づいて、前記利用者ごとに、暗号化すべき前記ノードを特定し、特定した前記ノードおよび特定した前記ノードに隣接するノードの前記経路探索用データを暗号化し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する暗号化処理部と、を備えることを特徴とする。
【００１２】
また、本発明にかかる復号化装置は、利用者から地図上の位置のある地点から他の地点までの経路を探索するための経路探索要求を受けた場合に、暗号化された地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データを復号化する復号化鍵に基づいて、前記経路探索用データと、前記ノードにある地物を表示させるための表示用データとが対応付けられた暗号化地図データを復号化する復号処理部と、前記ある地点から前記他の地点までの経路を、前記暗号化地図データに対応する前記経路探索用データに含まれる前記ノードと前記リンク情報とに基づいて前記復号処理部を用いて暗号化地図データの復号を行い、復号結果を用いて前記ノードと前記リンク情報とに基づいて、繰り返し探索する経路探索部と、を備えることを特徴とする。
【００１３】
また、本発明は、上記暗号化装置および復号化装置を備えた経路探索システムである。
【発明の効果】
【００１４】
本発明によれば、利用者ごとに適切な経路探索を行うことができる暗号化装置、復号化装置、および経路探索システムを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態における地図データ配信システムの概略を示す構成図である。
【図２】図１に示した地図データ配信システムを構成する各装置の構成図である。
【図３】地図データ配信システムにおいて行われる処理のシーケンス図である（登録処理）。
【図４】地図データ配信システムにおいて行われる処理のシーケンス図である。経路探索の処理フローの概略を表す図である（経路処理）。
【図５】平文地図データのデータ構造の一部とその表示イメージを示す図である。
【図６】暗号化定義情報の一例を示す図である。
【図７】第１の実施の形態における暗号化処理の処理手順を示すフローチャートである。
【図８】第１の実施の形態における復号化処理の処理手順を示すフローチャートである。第一の実施例における経路探索用データの復号処理の概略を示す処理フロー図である。
【図９】経路探索用データ格納部の例を示す図である。
【図１０】暗号化定義情報を生成するためのアプリケーション画面の一例を示す図である。
【図１１】第２の実施の形態における暗号化処理の処理手順を示すフローチャートである。
【図１２】第２の実施の形態における復号化処理の処理手順を示すフローチャートである。
【図１３】第２の実施の形態における暗号化処理前後でのデータ構造の変化の一例を示す図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して、この発明にかかる暗号化装置、復号化装置、および経路探索システムの実施の形態を詳細に説明する。
（第１の実施の形態）
図１は、第１の実施の形態における地図データ配信システム１の概略を示す構成図である。図１において、点線はデータの流れの概略を表している。地図データ配信システム１は、地図暗号化装置１０１、地図格納装置１０２と、鍵管理装置１０３と、地図配信装置１０４と、地図閲覧装置１０５と、地図復号装置１０６とを含んで構成され、これらの各装置がネットワーク１００を介して接続されている。
【００１７】
地図暗号化装置１０１は、暗号化定義情報生成部１１０と、暗号化処理部１１１とを含んで構成されている。暗号化定義情報生成部１１０は、暗号化される前の地図データである平文地図データ１２０から暗号化定義情報１２１を生成し、暗号化処理部１１１は、暗号化定義情報１２１、平文地図データ１２０と暗号化鍵１２２から、暗号化地図データ１２４を生成するものである。なお、暗号化定義情報１２１の具体的な内容については後述する。
【００１８】
地図格納装置１０２は、データベース処理部１１２を有し、暗号化地図データ１２４を格納する。ここで、データベース処理部１１２は、例えば、ＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ Ｑｕｅｒｙ Ｌａｎｇａｇｅ）やＧＩＳ製品（Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ）のＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ Ｐｒｏｇｒａｍ Ｉｎｔｅｒｆａｃｅ）を用いて、地図配信装置１０４からの要求に応じて、検索や登録、削除、変更など、暗号化地図データ１２４に関する種々の処理を行う。
【００１９】
鍵管理装置１０３は、鍵生成部１１３を含んで構成される。鍵生成部１１３は、暗号化に利用する暗号化鍵１２２と対応する復号鍵１２３を生成する。ここで、鍵生成部１１１３が生成する暗号化鍵１２２、復号鍵１２３は、ＲＳＡなどの公開鍵暗号技術における公開鍵、秘密鍵であってもよいし、ＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）などの共通鍵暗号技術における共有鍵であってもよい。
【００２０】
地図配信装置１０４は、クエリ処理部１１７を含んで構成されている。クエリ処理部１１７は、地図閲覧装置１０５内のクエリ要求部１１５からの要求を受け付け、クエリの解析を行い、地図復号装置１０６の表示用イメージ生成部１１４２が生成した表示用地図データを受けると、地図閲覧装置１０５へ返信して表示させるための地図データを作成する。
【００２１】
地図閲覧装置１０５は、クエリ要求部１１５と、表示処理部１１８とを含んで構成されている。ここで、クエリ要求部１１５は、地図配信装置１０４へ、地図データの検索などのクエリを送信し、地図配信装置１０４から返信された地図データを受信して、表示処理部１１８が地図データを表示する。地図閲覧装置１０５が受信した地図データは、後述するように、地図復号装置１０６の復号処理部１１６が復号鍵１２３を用いて復号処理を行ったものである。
【００２２】
地図復号装置１０６は、経路探索処理部１１４１と、表示用地図イメージ生成部１１４２と、復号処理部１１６とを含んで構成される。表示用地図イメージ生成部１１４２は、復号処理部１１６が地図配信装置１０４のクエリ処理部１１７から表示用地図データを復号する要求を受けて復号した表示用地図データを送る。経路探索処理部１１４２は、地図配信装置１０４から経路探索用データを受信した場合に、経路探索を行う。経路探索の具体的な処理については後述する。復号処理部１１６は、復号鍵１２３を用いて、暗号化地図データ１２４の復号を行う。なお、以下の説明では、地図復号装置１０６を単独の装置として説明を行うが、地図復号装置１０６は地図配信装置１０４の一部であってもよいし、地図復号装置１０６は、地図閲覧装置１０５の一部として構成されていてもよい。
【００２３】
図２は、図１に示した地図データ配信システム１を構成する各装置の構成図である。図２に示すように、図１に示した地図データ配信システム１を構成する各装置は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｏｒ Ｕｎｉｔ）２０１、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）２０２、入力装置２０３、表示装置２０４、通信装置２０５、読書装置２０６、及び、外部記憶装置２０７がインターフェイス２０５を介して接続された、一般的な構成を有するコンピュータ（電子計算機）２００として構成される。
【００２４】
入力装置２０３は、例えば、キーボードやマウスなどであり、表示装置２０４は、表示用ディスプレイ、外部記憶装置２０７は、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）などである。また、通信装置２０５はネットワークを介して他の装置と通信を行うための通信インターフェイスである。さらに、読書装置２０６は、ＦＤ（Ｆｌｏｐｐｙ（登録商標） Ｄｉｓｋ）やＵＳＢメモリ、或いは、ＣＤ−Ｒといった外部記憶媒体２０８から、データの読込み、或いは、書込みを行うための装置である。
【００２５】
ＣＰＵ２０１は、ＲＡＭ２０２上にロードしたプログラムを実行することによって、図１に示した各装置の各処理部(暗号化処理部１１１など）をプロセスとして具現化する。また、インターフェイス２０９は、装置内の各構成要素間のデータを送受信する内部パスである。
【００２６】
図３および図４は、地図データ配信システム１において行われる処理のシーケンス図である。まず、図３について説明する。図３は、地図閲覧装置１０５から経路探索要求があった場合に、利用者の種別に応じて経路探索を行って、その種別に応じた地図データを地図閲覧装置１０５に表示させるための暗号化地図データ１２４を登録する処理（以下、登録処理と呼ぶ。）の処理手順を示すフローチャートである。
【００２７】
この登録処理は、地図データ配信システム１が行う処理のうち、地図閲覧装置１０５に地図データを配信する前に、例えば、地図データ配信システム１を利用するユーザを登録するタイミングで、あらかじめ管理者等によって行われるものである。登録処理では、鍵管理装置１０３での鍵生成と、地図暗号化装置１０１、地図閲覧装置１０５への送信、及び、平文地図データの暗号化、暗号化された地図データの地図格納装置１０２での格納までの処理を行う。
【００２８】
図３に示すように、登録処理が開始されると（ステップＳ３００）、鍵管理装置１０３は、利用者に応じた暗号化鍵１２２、復号鍵１２３を生成し（ステップＳ３０１）、生成した復号鍵１２３を地図復号装置１０６に送信する（ステップＳ３０２）。
【００２９】
地図復号装置１０６は、復号鍵１２３を受信すると、受信したその復号鍵１２３を、外部記憶装置２０７等の記憶装置に格納し（ステップＳ３０３）、その後、鍵管理装置１０３は、暗号化鍵１２２を地図暗号化装置１０１に送信する（ステップＳ３０４）。
【００３０】
暗号化鍵１２２を受信すると、地図暗号化装置１０１は、受信した暗号化鍵１２２を外部記憶装置２０７等の記憶装置に格納し（ステップＳ３０５）、暗号化定義情報生成部１１０は、平文地図データ１２０を用いて、暗号化定義情報１２１を生成する（ステップＳ３０６）。
【００３１】
ここで、暗号化定義情報１２１とは、後述するノード、およびノード間の関係を表すリンクから構成される経路探索用データを、開示対象となる利用者（あるいは利用者の種別）を、ノードと対応付けて記憶するものである。
【００３２】
なお、この暗号化定義情報１２１は、地図データ配信システム１が取り扱う平文地図データ１２０に対して作成されるものであり、具体的な内容については図６を用いて後述する。また、暗号化定義情報１２１として記述されるデータの内容（例えば、どのノードをどの利用者に対して開示させるのか）については、あらかじめ管理者等によって定められ、その設定にしたがって暗号化定義情報１２１が生成されるものとする。
【００３３】
そして、地図暗号化装置１０１の暗号化処理部１１１は、暗号化定義情報１２１と平文地図データ１２０、暗号化鍵１２２から暗号化地図データ１２４を生成し、生成した暗号化地図データ１２４を地図格納装置１０２に送信する（ステップＳ３０７）。このステップＳ３０７の具体的な処理（暗号化処理）については、図７を用いて後述する。
【００３４】
地図格納装置１０２は、地図暗号化装置１０１から暗号化地図データ１２４を受信して、その暗号化地図データ１２４を格納し（ステップＳ３０８）、図３に示す登録処理が終了する（ステップＳ３０９）。この登録処理が終了すると、利用者毎の暗号化鍵１２２および復号鍵１２３と、暗号化地図データ１２４と、暗号化定義情報１２１とが生成される。
【００３５】
ここで、ステップＳ３０２において、鍵管理装置１０３が復号鍵１２３を地図復号装置１０６に送信する場合、および暗号化鍵１２２、復号鍵１２３として共通鍵暗号技術における共有鍵を用いたこれらの鍵を生成し、ステップＳ３０４において、鍵管理装置１０３が地図暗号化装置１０１に暗号化鍵１２２を送信する場合、外部記憶媒体を利用して直接配送するか、あるいは暗号化通信を用いて送信することが望ましい。また、公開鍵暗号技術における秘密鍵や共通鍵暗号技術における共有鍵は、例えばＩＣカードやＨＳＭ（Ｈａｒｄｗａｒｅ Ｓｅｃｕｒｉｔｙ Ｍｏｄｕｌｅ）などの耐タンパ性を有するデバイス内に格納しておくことが望ましい。
【００３６】
一方、公開鍵暗号技術における公開鍵は、一般に公開することが可能であるので、ＨＴＴＰ（Ｈｙｐｅｒ Ｔｅｘｔ Ｔｒａｎｓｆｅｒ Ｐｒｏｔｏｃｏｌ）などの一般的な通信路を用いてもよい。ただし、例えば、鍵管理装置１０３が公開鍵に対して公開鍵証明書を発行し、暗号化装置１０１で使用する暗号化鍵１２２に誤りや改ざんがないことを、公開鍵証明書を用いて確認することが望ましい。
【００３７】
図４は、地図データ配信システム１が、利用者から地図の経路探索要求を受け付けて、その結果を利用者に表示するための処理（以下、経路処理と呼ぶ。）の処理手順を示すフローチャートである。図４では、地図配信装置１０４から地図閲覧装置１０５に地図データを配信し、地図閲覧装置１０５で表示するまでの処理フローを表している。なお、本処理フローにおいては、主に、地図閲覧装置１０５からの経路探索要求の送信、地図配信装置１０４でのクエリ解析、地図格納装置１０２を利用した検索の実行と地図閲覧装置１０５への送信、及び、地図閲覧装置１０５での復号、表示処理が行われる。
【００３８】
図４に示すように、地図データ配信システム１が、利用者から地図データの経路探索要求を受け付け、経路処理が開始されると（ステップＳ４００）、地図閲覧装置１０５のクエリ要求部１１５は、地図配信装置１０４に、受け付けられた経路探索要求を送信する（ステップＳ４０１）。
【００３９】
そして、地図配信装置１０４のクエリ処理部１１７は、地図閲覧装置１０５から送信された経路探索要求を構成しているクエリを解析し、解析した結果に従って、地図格納装置１０２に対して経路探索用データの検索要求を送信する（ステップＳ４０２）。
【００４０】
地図格納装置１０２のデータベース処理部１１２は、地図配信装置１０４から検索要求を受信し、その検索要求に従って、図３に示した登録処理によって登録された暗号化地図データ１２４あるいは地図暗号化装置１０１の平文地図データ１２０にアクセスして検索処理を実行し、検索結果（例えば、出発地、目的地、および途中のノードの座標データやノードＩＤを含む情報）を経路探索用データとして地図配信装置１０４に返信する（ステップＳ４０３）。
【００４１】
続いて、地図配信装置１０４のクエリ処理部１１７は、地図格納装置１０２から経路探索用データを受信し、受信した経路探索用データを、地図復号装置１０６に送信し（ステップＳ４０４）、地図復号装置１０６の経路探索処理部１１４１および復号処理部１１６は、受信した経路探索用データを参照して経路探索を実行し、経路探索結果を地図配信装置１０４に送信する（ステップＳ４０５）。なお、ステップＳ４０５の具体的な処理（復号化処理）については、図８を用いて後述する
そして、地図配信装置１０４のクエリ処理部１１７は、経路探索結果を受信し、受信した経路探索結果を参照して表示用地図データの検索要求を地図格納装置１０２に送信し（ステップＳ４０６）、地図格納装置１０２のデータベース処理部１１２は、表示用地図データの検索要求にしたがって表示用地図データの検索を行い、その検索結果を地図配信装置１０４に送信する（ステップＳ４０７）。
【００４２】
地図配信装置１０４のクエリ処理部１１７は、表示用地図データの生成要求を地図復号装置１０６に送信し（ステップＳ４０８）、地図復号装置１０６の表示用地図イメージ生成部１１４２および復号処理部１１６が暗号化地図データ１２４を復号化した表示用地図イメージを生成し、地図配信装置１０４に送信する（ステップＳ４０９）。
【００４３】
その後、地図配信装置１０４のクエリ処理部１１７は、表示用地図イメージを地図閲覧装置１０５に送信し（ステップＳ４１０）、地図閲覧装置１０５のクエリ要求部１１５は、表示用地図イメージを受信し、表示処理部１１８が、地図閲覧装置１０５の表示装置２０４に表示用地図イメージを表示させ(ステップＳ４１１)、図４に示す検索処理が終了する（ステップＳ４１２）。
る。
【００４４】
ステップＳ４０１において、地図閲覧装置１０５から地図配信装置１０４への経路探索要求の送信に先立ち、後述するように、暗号化鍵１２２と復号鍵１２３とが利用者ごとに定められているため、利用者とこれらの鍵とを対応させるため、地図配信装置１０４は地図閲覧装置１０５のユーザ認証を行うことが望ましい。このため、地図配信装置１０４のクエリ処理部１１７が、地図閲覧装置１０５の装置固有の装置ＩＤ（例えば、ＭＡＣアドレス（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ Ａｄｄｒｅｓｓ）等）を利用し、地図閲覧装置１０５からの認証用の情報を受け付けることによってユーザ認証を行えばよい。或いは、地図閲覧装置１０５を利用するユーザのＩＤ／ＰＷ（Ｐａｓｓｗｏｒｄ）の入力を求め、これを利用してユーザ認証を行ってもよいし、ＳＳＬ（Ｓｅｃｕｒｅ Ｓｏｃｋｅｔｓ Ｌａｙｅｒ）などの暗号技術を用いた認証や生体情報を利用したユーザ認証を利用してもよい。
【００４５】
また、上記のユーザ認証の結果、地図閲覧装置１０５に開示すべきでない情報が明らかな場合（ある利用者に対して非開示とする範囲が明らかな場合）には、ステップＳ４０２における地図格納装置１０２への経路探索用データの検索要求において、開示すべきでない情報を含む範囲を除いた検索要求を行い、開示可能な範囲のみの検索要求を行ってもよい。例えば、上記のユーザ認証の結果、ユーザが非開示領域すべてに対して閲覧権限を持たない場合には、ステップＳ４０３の地図格納装置１０２からの検索結果の送信には、開示範囲のみの経路探索用データを含めればよい。
【００４６】
ステップＳ４０１における経路探索要求の送信では、例えば、現在位置（出発地）と目的地の座標情報（以下、単に位置情報と呼ぶこともある。）が地図配信装置１０４に送信される。ステップＳ４０２およびＳ４０３においては、地図配信装置１０４のクエリ処理部１１７は、その位置情報を元に地図格納装置１０２に対し検索処理を行い、現在位置および目的地に最も近いノードを出発地ノードおよび目的地ノードとし、経路探索に必要な経路探索用データと対応する暗号化データを地図格納装置１０２から取得する。このとき、経路探索に必要なデータは、例えば、探索範囲が建物の１階のみや町内など、限られた範囲であることが明らかである場合には、特定の範囲のみを探索に用いる経路探索用データとして取得すればよい。
【００４７】
また、ステップＳ４０２およびＳ４０３の処理は対話的に行ってもよい。例えば、ステップＳ４０１から送信された経路探索要求の出発地や目的地が地名や部屋の名称などである場合には、地図配信装置１０４が地図格納装置１０２に問い合わせを行い、名称から地物を特定し、地物に関連づけられたノード、或いは、地物の位置からノードを特定すればよい。
【００４８】
或いは、出発地ノード、または、目的地ノードが暗号化されている場合には、地図配信装置１０４が、経路探索要求に含まれる位置情報から地物を特定し、特定された地物に関連する暗号化データを地図格納装置１０２から取得し、地図配信装置１０４が地図復号装置１０６にその暗号化データを送信し、地図復号装置１０６が暗号化データを復号して地物のノードを取得すればよい。なお、経路探索用データの詳細については後述する。
【００４９】
或いは、上記の地名や部屋名称から出発地、或いは、目的地を特定する場合においても、地物そのもの、或いは、地物の属性情報が暗号化されている等の理由により、直接地物を特定できない場合がある。この場合には、例えば、地図格納装置１０２が、暗号化地図データ１２４以外に、上記地名や部屋の名称等を含むキーワードリストを、暗号化された地物、或いは属性情報に対応付けて記憶し、これらを管理するようにしてもよい。このようなキーワードリストを作成することによって、上記の地名や部屋名称といったキーワード検索に対応することが可能となる。
【００５０】
また、キーワードリストには、キーワードそのものを保管するのではなく、例えば、ＳＨＡ−１などの暗号学的ハッシュ関数を用いることによって、ハッシュ値を生成し、これを保管してもよい。暗号学的ハッシュ関数の一方向性の性質から、キーワードリストに格納されたハッシュ値からもとのキーワードを知ることが困難になる。さらに、各キーワードは、上述したようなユーザ認証によって利用可能なキーワードを制限することが望ましい。なお、キーワードリストの作成方法については、上記に限らず、他の方法を利用してもよい。
【００５１】
また、地図復号装置１０６の復号処理において、暗号化データが復号できなかった等の理由により、以上に示したいずれかの方法で、出発地ノード、目的地ノードが得られなかった場合には、「目的地が見つかりません」などのエラーを地図閲覧装置１０５に送信し、処理を終了する。
【００５２】
なお、ステップＳ４０５までの処理によって経路探索が終了する。経路探索の結果は、上述したノードとリンクの集合である。ステップＳ４０６では、経路探索結果によって得られるノードの座標情報、或いは、関連付けられた地物を元に再度地図格納装置１０２に検索要求を送信し、経路探索結果を記載した周辺地図画像を作成する。なお、ステップＳ４０７から検索結果に暗号化データが含まれている（経路探索用データ以外の地図データそのものが暗号化されている）場合には、ステップＳ４０９内で復号処理を行い、地図データの復元を行ってもよい。
【００５３】
上記のステップＳ４０２からステップＳ４０５の処理は、繰り返し行ってもよい。例えば、経路探索の範囲が大きい場合や地図送信装置１０５からの経路探索要求の送信（ステップＳ４０１）が経由地を指定している場合には、経由地を目的地ノード、或いは、出発地ノードとして、ステップＳ４０２からステップＳ４０５までの処理を複数回繰り返して処理を行ってもよい。
【００５４】
ステップＳ４１０の地図閲覧装置１０５への表示用地図イメージの送信においては、上記ステップＳ４０９で生成された経路探索結果を表示した周辺地図画像だけではなく、例えば、タイトルやコスト（例えば、移動時間や料金）などをＨＴＭＬ（Ｈｙｐｅｒｔｅｘｔ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）で成形して送信してもよい。なお、この処理は、ステップＳ４０９内で行ってもよい。
【００５５】
次に、地図暗号化装置１０１が記憶する平文地図データ１２０のデータ構造について説明する。図５は、平文地図データ１２０のデータ構造の一部とその表示イメージ５１０を示す図である。
【００５６】
図５に示すように、平文地図データ１２０は、地図データ格納部５００と、経路探索用データ格納部５０１とを含んで構成され、経路探索用データ格納部５０１には、ノード格納部５０２およびリンク格納部５０３が格納されている。ここで、ノード格納部５０２とリンク格納部５０３は、経路探索の際に用いられるデータを格納しており、ノード格納部５０２には経路探索用データのノードと各ノードの地図上の対応位置座標、或いは、対応地物の情報が格納される。また、リンク格納部５０３には、ノード格納部５０２内に格納されたノード間を接続するリンク情報とその移動コストの情報が格納される。ここで、移動コストとは移動に要する時間、直線距離、或いは、経費などである。なお、ノード格納部５０２とリンク格納部５０３のデータ構造については、図９を用いて後述する。
【００５７】
図５に示したように、地図データ格納部５００には地図上の各地物の種類、名称などの属性情報とその地物の地図上での位置（座標）、形状を表すジオメトリが対応付けて構成される。なお、属性情報のうち、地図データ格納部５００のＦＩＤ（Feature ID）は、各地物を一意に識別するための識別子である。
【００５８】
また、図５の下部には、経路探索の結果、地図閲覧装置１０５に表示される表示イメージ５１０を示している。表示イメージ５１０は、地図データ格納部５００内に格納された地物のオメトリ、属性情報、および、ノード格納部５０２、リンク格納部５０３内に格納された位置情報とノード間の接続情報にしたがって作成される。
【００５９】
なお、図５に示した平文地図データ１２０の地図データ格納部５００は、上述した各種のデータが表形式で表現されているが、これに限らずともよい。例えば、ＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ）には、単純な表形式ではなく、例えば地物を最小単位（オブジェクト、フィーチャなどと呼ぶ）とし、同一の性質、或いは、場所に存在する複数のフィーチャをまとめてコンテナと呼ばれる単位にまとめ、管理し、コンテナを地図の構造（例えば、建物の構造等）に応じて配置することによって、木構造を用いて表現するものもある。このような場合でも、図５の表の各行を上記のフィーチャとして扱うことによって、同様に適用可能である。
【００６０】
続いて、暗号化定義情報１２１について説明する。図６は、暗号化定義情報１２１の一例を示す図である。図６に示すように、暗号化定義情報１２１には、暗号化対象となるノードと、経路探索要求を行う利用者とが対応付けて記述されている。なお、以下では、これらの情報がＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）をもちいて記述されているものとして説明している。
【００６１】
暗号化定義情報１２１は、経路を検索するための要素として、暗号化対象ノード要素から構成される。暗号化対象ノード要素内には、暗号化対象となるノードを指定するノードリスト要素と、開示先を設定するための開示先リスト要素がある。ノード要素には暗号化対象となるノードＩＤを記述し、開示先要素に開示先の利用者、或いは、利用者の種別を一意に特定する識別子等を記述することによって、それぞれ、ノード、利用者を特定する。図６に示した例では、暗号化対象ノードとして、ノードＩＤ（ＮＩＤ）が「Ｎ０１」および「Ｎ０２」のノードが記述され、開示先リストとして、「ユーザＡ」および「ユーザＢ」が記述され、これらのノードは、ユーザＡおよびユーザＢにのみ開示することを示している。
【００６２】
ここで、利用者を一意に識別するための識別子とは、例えば、社員番号や会員番号、ｅ−ｍａｉｌアドレス等を用いればよい。なお、ノード要素、開示先要素を同一の暗号化対象ノード要素内で複数指定する理由は、開示先が同一であるノードをまとめ、開示先を複数指定可能とするためである。このように、暗号化対象ノードを複数指定することで、開示先の異なる複数のノードリストを設定することが可能である。
【００６３】
本実施例では、暗号技術、すなわち、復号鍵１２３の有無に応じて開示先の制限を行うため、開示先要素には利用者、或いは、利用者の種別を特定する識別子ではなく、復号鍵に対応する暗号化鍵１２２の識別子、或いは、参照先を記述するようにしてもよい。上記の開示先要素に利用者、或いは、利用者の識別子を記述した場合には、記述された識別子から暗号化鍵１２２、或いは、その参照先を特定し、暗号化処理時に暗号化鍵１２２を利用する。
【００６４】
なお、図６に示した暗号化定義情報１２１は、開示先リストや開示先などの要素名は異なるものであってもよい。また、ＡＳＮ．１など、ＸＭＬ以外の他のデータ表現を用いてもよい。また、例えば地物そのもの、或いは、地物の属性情報、ジオメトリなど、経路探索用データ以外のデータの開示先を制限する場合には、暗号化定義情報要素内に暗号化対象ノードとは異なる子要素を追加し、開示先の設定を行えばよい。
【００６５】
続いて、図３に示したステップＳ３０７（暗号化処理）、図４に示したステップＳ４０５（復号化処理）、および暗号化処理前後でのデータ構造の変化について説明する。まず、暗号化処理の前後におけるデータ構造の変化を、図９を用いて説明する。なお、図９は、図５に例示した表示イメージ５１０の経路探索用データ格納部５０１の一部を例示した図である。前述の通り、経路探索用データ格納部５０１は、経路探索用データを構成するノードとリンクのうち、ノードに関する情報を格納するノード格納部５０２と、リンクに関する情報を格納するリンク格納部５０３から構成される。
【００６６】
図９は経路探索用データ格納部５０１の例を示す図である。図９に示すように、経路探索用データ格納部５０１ａのノード格納部５０２ａには、各ノード情報を格納するため、ノードを一意に識別する識別子であるＮＩＤと、ノードの地図上の位置情報を表す座標と、暗号化処理後に隣接ノードが暗号化されているか否かを表す復号フラグと、を含んで構成される。また、リンク格納部５０３ａは、リンクを一意に識別するための識別子、接続関係のうち始点側のノードを特定するための始点ＮＩＤと、終点側のノードを特定するための終点ＮＩＤと、ノード間の移動コストを表すコストと、を含んで構成される。
【００６７】
なお、始点ＮＩＤおよび終点ＮＩＤは、ノード間の一方向への移動を表すためのものであり、ノード間の接続関係が全て両方向である場合には、始点ＮＩＤ、終点ＮＩＤの区別は不要である。また、始点ＮＩＤ、終点ＮＩＤの区別がある場合に、双方向での移動コストを表現する場合には、始点ＮＩＤと終点ＮＩＤを入れ替えたデータを別途入力する、或いは、リンク格納部５０３ａに双方向であることを表すためのデータを新たに追加するなどすればよい。また、図９に示したリンク格納部５０３ａは、コストの一例として移動時間のみを格納しているが、これ以外にも複数のコストを格納してもよい。例えば、車や自転車、徒歩など利用者の移動方法などに応じて、移動距離や時間等の複数のコストを格納するようにしてもよい。以下では、コストがひとつである場合について説明を行うが、複数格納されている場合でも、同様の手順で暗号化を行うことが可能である。
【００６８】
図９に示したノード格納部５０２ａ、リンク格納部５０３ａには、例えば、名称や補足説明、或いは、関連する地物のＦＩＤなどの情報を含んでもよい。なお、ノード格納部５０２ａ内の復号フラグは暗号化後に必要となるデータであるため、経路探索用データ格納部５０１ａにはなくてもよい。
【００６９】
暗号化経路探索用データ５０４ａは、経路探索用データ５０１ａのうち、ＮＩＤがＮ５のノードを暗号化した場合の暗号化結果を表している。暗号化経路探索用データ５０４ａは、ノード格納部５０２ａと、リンク格納部５０３ａと、暗号化データ部５０５ａと、を含んで構成されている。
【００７０】
暗号化データ部５０５ａは、ノード、及びリンクを暗号化した結果を格納する暗号化データと、暗号化データを一意に識別するための識別子であるＣＩＤと、復号時に復号すべき暗号化データを特定するためのＦＩＤとＮＩＤとを含む関連データと、を含んで構成される。
【００７１】
本実施例で説明するように、地図暗号化装置１０１の暗号化処理部１１１が行う経路探索データの暗号化では、暗号化対象となるノード、及びそのノードに接続された全てのリンク（例えば、図９に示した太枠部分）を、暗号化後のノード格納部５０２ａ、およびリンク格納部５０３ａから削除し、暗号化対象のノードの全ての隣接ノードの復号フラグをＴ（ＴＲＵＥ）に設定する。なお、復号フラグがＴでないノードには、Ｆ（ＦＡＬＳＥ）を設定する。
【００７２】
暗号化対象となるノードとそれに接続された全リンク（以下、これら暗号化を行うデータを暗号化対象データと呼ぶ。）は、暗号化定義情報１２１の開示先要素の設定に従い暗号化を行い、その暗号化結果のＢＡＳＥ６４符号化した結果を暗号化データに格納する。なお、暗号化データには、ノードとリンクに関する全てのデータの暗号化結果を格納することが必要となるが、これには例えばＸＭＬなどを用いてＮＩＤ、座標などの各データを構造化した結果をＢＡＳＥ６４符号化した結果を格納すればよい。
【００７３】
上記の暗号化対象データの暗号化にあたっては、暗号化対象データを開示先ごとに暗号化鍵１２２を用いて個別に暗号化し、その結果を、ＸＭＬなどを用いて整形し、暗号化データ部５０５ａに書き込んでもよいし、例えば、以下のようにしてもよい。
【００７４】
まず、鍵管理装置１０３の鍵生成部１１３が共通鍵暗号技術におけるランダムな共有鍵（以下、セッション鍵と呼ぶ。）を暗号化対象ノードごとに別々に生成し、地図暗号化装置１０１に送信する。次に、地図暗号化装置１０１の暗号化処理部１１１は、暗号化対象ノードごとに生成されたセッション鍵を暗号化定義情報１２１内の開示先ごとに以下のように暗号化する。
【００７５】
まず、各暗号化対象ノードに設定された開示先に、現在処理を行っている開示先と一致する開示先が存在すれば、現在処理を行っている暗号化対象ノードのセッション鍵をセッション鍵暗号化リストに加える。これを全ての暗号化対象ノードに対して繰り返すことにより、現在処理中の開示先が復号可能な暗号化対象ノードのセッション鍵のセッション鍵暗号化リストが作成される。次に生成されたセッション鍵暗号化リストを集約し、その開示先の暗号化鍵１２２を用いて暗号化する。以下、同様の処理を全ての開示先に対して繰り返し、その結果を、ＸＭＬなどを用いて整形し、暗号化データ部５０５ａに書き込めばよい。上記では、暗号化対象ノードごと暗号化しているが、前述のようにノード格納部５０３ａが複数のコストを含む場合には、個々のコストごとにセッション鍵を割り当てるようにしてもよい。
【００７６】
なお、上記のセッション鍵暗号化リストの暗号化鍵１２２による暗号化において、復号時に暗号化対象ノードの完全性を保証するための暗号化対象ノードのハッシュ値や、ＭＡＣ（Ｍｅｓｓａｇｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ Ｃｏｄｅ）などを含めてもよい。上記の暗号化処理は、選択的開示型暗号と呼ばれ、特開２００９−４９９７３１などで公開されているものである。
【００７７】
経路探索では、ダイクストラ法、或いはダイクストラ法を改良した経路探索アルゴリズムが用いられる。これらの経路探索アルゴリズムでは、あるノードを起点（起点ノードと呼ぶ）として、その隣接ノードを探索し、出発地ノードから隣接ノードへの合計コストの評価を繰り返すことによって、目的地ノードまでの合計コストを求め、最終的な出発点から目的地への経路探索が行われる。ダイクストラ法は、出発地ノードから目的地ノードまでの経路を、上記の手順を中核処理として、これを繰り返して探索を行う幅優先探索の経路探索アルゴリズムである。ダイクストラ法におけるコスト評価や探索の打切り条件等を改良することによって効率的な経路探索を行うアルゴリズムが知られている（例えばＡ＊法など）。
【００７８】
そして、地図復号装置１０６の復号処理部１１６が復号化処理を行う際には、上記の隣接ノードの探索の際に、まず復号すべきデータの有無を起点ノードの復号フラグによって判断する。そして、復号フラグがＴであった場合には、暗号化データ部５０５ａの関連データを参照し、復号すべき暗号化データを取得する。次に、復号処理を実行し、暗号化データが復号された場合には、復号データからノード、リンクを復元し、経路探索を継続する。
【００７９】
以下に、上述した暗号化処理、復号化処理の具体的な処理手順を図７、図８を用いて説明する。本実施例では、上記のダイクストラ法の中核処理の中で復号処理を行う方法を説明するが、経路探索アルゴリズムはダイクストラ法に限定されるものではなく、ダイクストラ法を拡張した他の経路探索アルゴリズムにも適用可能である。
【００８０】
本実施例における暗号化後には、暗号化対象ノードの全ての隣接ノードの復号フラグにはＴが設定されている。経路探索アルゴリズム内で、起点ノードの復号フラグがＴに設定されている場合には、暗号化データ部５０５ａ内から復号すべき暗号化データを検索し、復号処理部１１６に与えられた復号鍵１２３を用いて暗号化データを復号する。この復号によって暗号化データが復号できた場合には、ノード格納部５０２ａ、リンク格納部５０３ａに復号されたデータを復元する。なお、暗号化データ部５０５ａ内からの復号すべき暗号化データの検索には、暗号化データ部５０５ａの関連データを利用する。
【００８１】
以下、本実施例における具体的な暗号化処理、復号化処理について説明する。図７は、本実施例における暗号化処理の処理手順を示すフローチャートである。
【００８２】
図７に示すように、暗号化処理が開始されると（ステップＳ７００）、地図暗号化装置１０１の暗号化処理部１１１は、平文地図データ１２０を構成している経路探索用データ格納部５０１ａを暗号化経路探索用データ格納部５０４ａにコピーし、一度、復号フラグをＦにセットする（ステップＳ７０１）。
【００８３】
そして、暗号化処理部１１１は、暗号化定義情報１２１を参照し、暗号化すべき暗号化対象ノードの有無を判定する（ステップＳ７０２）。そして、暗号化処理部１１１は、暗号化すべき暗号化対象ノードがあると判定した場合（ステップＳ７０２；Ｙｅｓ）、ステップＳ７０３に進み、暗号化すべき暗号化対象ノードがないと判定した場合（ステップＳ７０２；Ｎｏ）、図７に示す暗号化処理を終了させる（ステップＳ７１０）。
【００８４】
暗号化すべき暗号化対象ノードがあると判定すると（ステップＳ７０２；Ｙｅｓ）、暗号化処理部１１１は、暗号化定義情報１２１に記述されている暗号化対象ノードを取得し（ステップＳ７０３）、リンク格納部５０３ａを参照し、取得した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあるか否かを判定する（ステップＳ７０４）。
【００８５】
そして、暗号化処理部１１１は、取得した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあると判定した場合（ステップＳ７０４；Ｙｅｓ）、その接続リンクを関連リンクとして取得し（ステップＳ７０５）、取得した暗号化対象ノードに接続された接続リンクから暗号化対象ノードの隣接ノードを特定し、復号フラグをＴに変更する（ステップＳ７０６）。そして、暗号化処理部１１１は、ステップＳ７０４〜Ｓ７０６までの処理を繰り返し行う。
【００８６】
一方、暗号化対象ノードに接続された接続リンク内に未操作のリンクがないと判定した場合（ステップＳ７０４；Ｎｏ）、暗号化処理部１１１は、暗号化対象ノード、及びステップＳ７０５で取得した関連リンクを暗号化し（ステップＳ７０７）、暗号化対象ノード、及びステップＳ７０５で取得した関連リンクを暗号化経路探索用データ５０４ａ内のノード格納部５０２ａ、リンク格納部５０３ａから削除する（ステップＳ７０８）。
【００８７】
その後、暗号化処理部１１１は、ステップＳ７０７の暗号化結果を暗号化データ格納部５０４ａに格納し（ステップＳ７０９）、ステップＳ７０２へ戻る。そして、暗号化処理部１１１は、暗号化定義情報１２１に記述された全ての暗号化対象ノードについて、繰り返しステップＳ７０２〜Ｓ７０９までの処理を行う。
【００８８】
なお、上記の暗号化処理におけるステップ７０２では、例えば図６に例示した暗号化定義情報１２１の暗号化対象ノード要素を逐次処理し、暗号化対象ノードがなくなるまで繰り返せばよい。このような逐次処理は、例えばＸＭＬのＳＡＸ（Ｓｉｍｐｌｅ ＡＰＩ ｆｏｒ ＸＭＬ）を用いて実現すればよい。
【００８９】
また、図９の例では、暗号化対象ノード（Ｎ５）に接続されているノードは一つ（Ｎ６、リンクはＬ１４）のみであるが（表示イメージは図５参照）、ステップＳ７０４〜Ｓ７０６に示した通り、暗号化対象ノードに隣接ノードが複数ある場合には、これら全ての隣接ノードに対して同様の処理を行う。
【００９０】
なお、ステップＳ７０８における暗号化処理はノード一つずつ行うのではなく、複数のノードをまとめて処理してもよい。この場合には、ステップＳ７０９における暗号化データの暗号化データ部５０５ａへの書き込みは、これらをまとめて暗号化した１つの暗号化データとして行い、関連データに関連した地物、隣接ノードのＮＩＤを全て書き込むようにしてもよい。
【００９１】
また、複数のノードをまとめて処理する場合において、暗号化対象となるノードが同一の領域内にある場合には、領域内の境界線にあるノードの隣接ノードに対してのみステップＳ７０５、ステップＳ７０６を実行すればよい。その理由は、暗号化データの復号によってノード、リンクが復元された場合、領域の中にあるノード、リンクがまとめて復号されるため、領域内の境界以外にあるノード、リンクに対して復号すべきか否かを調べる必要がないためである。
【００９２】
上記の暗号化処理によって、暗号化対象のノード、及びそれに接続されるリンク情報は、すべて暗号化経路探索用データ５０４ａのノード格納部５０２ａ、リンク格納部５０３ａから削除され、その暗号化結果が関連データとともに暗号化データ部５０５ａに格納される。
【００９３】
なお、経路探索では、始点ノードから隣接ノードまでの検索を行ってコストを算出し、算出したコストから出発地ノードからのコスト評価を行うが、上記の暗号化処理では、暗号化されたノードの隣接ノード全ての復号フラグがＴに設定される。従って、経路探索の隣接ノードの検索時に復号フラグがＴであるかどうかを調べることによって、復号すべき暗号化データの有無を知ることができ、経路探索アルゴリズム内の必要箇所で復号することが可能となる。続いて、復号化処理について説明する。
【００９４】
図８は、本実施例における復号化処理の処理手順を示すフローチャートである。図８は、経路探索アルゴリズムにおける復号化処理を行うための処理フローを示したものであり、経路探索アルゴリズムそのものの処理については、その手順の概略のみを示している。なお、図８内の点線内が経路探索アルゴリズムの中核処理である。以下、図８に示す復号化処理について説明する。
【００９５】
図８に示すように、復号化処理が開始されると（ステップＳ８００）、地図復号装置１０６の復号処理部１１６は、まず、出発地ノードを始点ノードに設定する（ステップＳ８０１）。
【００９６】
そして、復号処理部１１６は、経路探索が終了しているか否かを判定し（ステップＳ８０２）、経路探索が終了していると判定した場合（ステップＳ８０２；Ｙｅｓ）、図８に示す復号化処理を終了させる（ステップＳ８１０）。
【００９７】
一方、復号処理部１１６は、経路探索が終了していないと判定した場合（ステップＳ８０２；Ｎｏ）、始点ノードの復号フラグがＴであるか否かを判定し（ステップＳ８０３）、始点ノードの復号フラグがＴであると判定した場合（ステップＳ８０３；Ｙｅｓ）、暗号化データ部５０５ａから暗号化データを取得し、取得した暗号化データを復号する（ステップＳ８０４）。一方、復号処理部１１６は、始点ノードの復号フラグがＴではない（Ｆである）と判定した場合（ステップＳ８０３；Ｎｏ）、ステップＳ８０７に進む。
【００９８】
復号処理部１１６は、ステップＳ８０４で取得した暗号化データの復号に成功したか否かを判定し（ステップＳ８０５）、復号に成功したと判定した場合（ステップＳ８０５；Ｙｅｓ）、ステップＳ８０４における復号結果からノード、リンクを復元し、復元したノード、リンクをノード格納部５０２ａ、リンク格納部５０３ａに追加する（ステップＳ８０６）。一方、復号処理部１１６は、復号に成功していない（失敗した）と判定した場合（ステップＳ８０５；Ｎｏ）、ステップＳ８０７に進む。
【００９９】
そして、復号処理部１１６は、ノード格納部５０２ａとリンク格納部５０３ａとを参照し、始点ノードの接続リンク（隣接ノード）を検索し（ステップＳ８０７）、未探索の隣接ノードがあるか否かを判定する（ステップＳ８０８）。
【０１００】
復号処理部１１６は、未探索の隣接ノードがあると判定した場合（ステップＳ８０８；Ｙｅｓ）、リンク格納部５０３ａ内のコスト欄を参照し、始点ノードから隣接ノードまでのコストを算出し、出発地ノードから隣接ノードまでのコスト評価を行う（ステップＳ８０９）。
【０１０１】
一方、復号処理部１１６は、未探索の隣接ノードがないと判定した場合（ステップＳ８０８；Ｎｏ）、ステップＳ８０２に戻る。そして、復号処理部１１６は、ステップＳ８０２からＳ８１０の処理を経路探索が終了するまで繰り返し行う。
【０１０２】
なお、上記のステップＳ８０４において、例えば、復号結果が正しいノードやリンクではないなどの復号が異常停止した場合には処理を停止することが望ましい。また、経路探索の過程において、目的地ノードにたどりつかないなど、経路探索が一定時間以上終了しない場合や非現実的なコスト（例えば、徒歩での移動に１００年以上かかるなど）であった場合には、ステップＳ８０２において処理を停止してもよい。
【０１０３】
上記のステップＳ８０４における復号、ステップＳ８０６におけるノードおよびリンクの復元は、単一のノードに対してではなく、複数のノード、リンクに対して行ってもよい。例えば、前述の暗号化処理時に複数のノードをまとめて暗号化した場合には、ステップＳ８０４における復号の結果には、複数のノードおよびリンクが含まれるため、ステップＳ８０６は復号されたノードおよびリンクを全て復元することになる。
【０１０４】
なお、上記の復号処理では、経路探索アルゴリズム内で逐次復号を行っているが、事前に復号すべきデータが少ない場合（例えば、ステップ４０３における地図格納装置１０２からの応答に暗号化データが一つしか含まれていない場合など）には、図８の処理の前に復号処理をまとめて実施してもよい。
【０１０５】
また、経路探索においては、データ管理、或いは、経路探索を効率に行うため、ビルのフロア等の階層、或いは領域ごとにデータ管理を行っている場合がある。この場合、経路探索についても、領域ごと、或いは階層別に経路探索アルゴリズムを実行し、これらの結果を繋ぎ合わせることで経路探索を実行し、図８の処理を階層、或いは領域ごとに経路探索してもよい。
【０１０６】
このように、記憶部（あるいは地図格納装置１０２）が、地図上の位置を示すノードおよびノードとノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データ格納部５０１が格納するデータ（経路探索用データ）とノードにある地物を表示させるための地図データ格納部５００が格納するデータ（表示用データ）とが対応付けられた平文地図データ１２０と、ノードと表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報１２１と、経路探索用データを暗号化するための暗号化鍵１２２を格納し、暗号化処理部１１１が、経路探索用データと、暗号化鍵１２２と、暗号化定義情報１２１とに基づいて、利用者ごとに、暗号化すべきノードを特定し、特定したノードおよび特定したノードに隣接するノードの経路探索用データを暗号化し、暗号化した経路探索用データと表示用データとを対応付けた暗号化地図データ１２４を生成する。
【０１０７】
また、復号処理部１１６が、利用者から地図上の位置のある地点から他の地点までの経路を探索するを実行する場合に、暗号化された地図上の位置を示すノードおよびノードとノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データ格納部５０１が格納するデータ（経路探索用データ）を復号化する復号化鍵１２３に基づいて、経路探索用データと、ノードにある地物を表示させるための地図データ格納部５００が格納するデータ（表示用データ）とが対応付けられた暗号化地図データ１２４を復号化し、経路探索部処理部１１４１が、ある地点から他の地点までの経路を、復号処理部１１６による暗号化地図データ１２４の復号化結果を用いて、経路探索用データに含まれるノードとリンク情報とに基づいて繰り返し探索する。
【０１０８】
したがって、利用者ごとに適切な経路探索を行うことができる。すなわち、利用者の種別に応じて開示可能な経路探索データのみを利用した経路探索を行い、利用者の種別ごとに適切な経路探索結果を提供することができる。
【０１０９】
なお、経路探索においては、データ管理、或いは、経路探索を効率に行うため、ビルのフロア等の階層、或いは領域ごとにデータ管理を行っている場合がある。この場合、経路探索についても、領域ごと、或いは階層別に経路探索アルゴリズムを実行し、これらの結果を繋ぎ合わせることで経路探索を実行する場合がある。その場合には、図８の処理を階層、或いは、領域ごとの経路探索を行い、これらの探索結果を組み合わせて、最終的な出発地ノードから目的地ノードまでの経路探索を行ってもよい。
【０１１０】
続いて、地図データ配信システム１の管理者等からの操作を受け付けて、地図暗号化装置１０１が暗号化定義情報１２１の登録や変更等を行う場合について説明する。
【０１１１】
図１０は、暗号化定義情報１２１を生成するためのアプリケーション画面（ＧＵＩ：Ｇｒａｐｈｉｃ Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅ）の実現イメージの一例を示す図である。なお、以下では、図１０を用いて経路探索用データを暗号化する場合のＧＵＩについて説明を行うが、地物そのものの、或いは、その属性、ジオメトリを暗号化する場合には、本ＧＵＩを拡張し、これらもまとめて暗号化できるようにしてもよい。
【０１１２】
図１０に示すように、本ＧＵＩは地図表示エリア１と、設定エリア１００１と、を含んで構成される。なお、ＧＵＩ上部のファイルメニュー１００２、データベースメニュー１００３、鍵読込メニュー１００４は、アプリケーション画面に対する操作を切り替えるためのメニュータグを表す。それぞれのメニュータグが選択された場合、以下の操作を行う（図１０では、「メニュー」は省略した）。
【０１１３】
地図暗号化装置１０１は、ファイルメニュー１００２がアクティブになっている場合、作成済みの暗号化定義情報１２１の読込、或は、作成途中の暗号化定義情報１２１の保存を行う。また、地図暗号化装置１０１は、データベースメニュー１００３がアクティブになっている場合、平文地図データ１２０を格納してあるデータベースへの接続を行い、平文地図データ１２０の読み込み、および、格納先の暗号化地図データ１２４の指定を行う。また、開示設定を終了し、暗号化定義情報１２１を生成する。さらに、地図暗号化装置１０１は、鍵読込メニュー１００４がアクティブになっている場合、暗号化定義情報１２１の設定に必要な暗号化鍵１２２を読み込む。
【０１１４】
なお、上記ではメニューとして、データベースメニュー１００３を配置し、平文地図データ１２０、および暗号化地図データ１２４が、データベースシステム上にあることを想定しているが、必ずしも、地図データ１２０や暗号化地図データ１２４は、データベースシステム上にある必要はなく、例えば、ＣＳＶ（Ｃｏｍｍａ Ｓｅｐａｒｅｔｅｄ Ｖａｌｕｅｓ）などの形式で、ファイルとして存在してもよい。
【０１１５】
図１０に示すＧＵＩにおいて、地図表示エリア１０００は、平文地図データ１２０を描画した結果を表示し、マウスなどの入力装置２０３からの入力に従い、暗号化対象となるノードを指定する。なお、指定にあたっては、図１０に例示したようにマウスの入力に従い矩形領域内に含まれるすべてのノードを暗号化対象ノードとしてもよいし、多角形や円などを利用してもよい。或は、マウスを用いてノードを直接を選択し、選択されたノードを暗号化対象ノードとしてもよいし、マウスによって地物を選択し、地物内に含まれる前ノードを暗号化対象ノードとしてもよい。
【０１１６】
以下では、図１０に示したマウスカーソル１００５で選択された領域の開示先を制限し、領域内に含まれるノードを設定する場合を例として、図１０に例示したＧＵＩの動作を説明する。
【０１１７】
設定エリア１００１は、平文地図データ１２０を非開示とする領域を指定するための非開示エリアと、非開示エリアに含まれる地物を示す関連地物と、非開示エリアに含まれるノードを示す対象ノードと、開示先のユーザを示す開示先と、を含んでいる。
【０１１８】
管理者等によってマウスカーソル１００５で領域が選択されると、設定エリア１００１の非開示エリア項目に新たな項目（図１０内のエリア２とする）が登録される。また、エリア２内に含まれる地物の一覧が関連する地物の一覧が、また、対象ノード欄にエリア２内に含まれるノードの一覧が表示される（図１０に示す例では、Ｎ５（機械室））。
【０１１９】
次に、管理者等によってマウスなどの入力装置２０３を用いて対象地物一覧の中から設定を行う地物やエリアが選択されると（図１０ではエリアを選択している）、選択した地物内の全ての属性がサブ画面（不図示）に表示される。また、このとき、選択された地物が地図上のどの地物であるかを明示するため、地図表示エリア９０６の対応する地物の表示色を変更する、或は、境界線を太くするなどしてもよい。
【０１２０】
次に、開示先を設定するノードを、対象ノードから、あるは関連地物欄内の地物を選択することによって指定する。そして、地図暗号化装置１０１は、開示先欄から開示先として指定するユーザの選択を受け付け、開示先設定ボタンの押下を受け付けると、一つのエリアに対する設定を完了する。このように設定された情報（例えば、図６に示したＡの部分）が、暗号化定義情報１２１として出力される。なお、地物内に含まれる全ノードを選択するために、関連地物欄内の地物を選択するようにしてもよい。上記によって、同一の開示先を持つ複数のノードが設定される。さらに、異なる開示先を持つノードを設定する場合には、上記の処理を繰り返せばよい。
【０１２１】
このように、地図暗号化装置１０１が、ＧＵＩによって暗号化定義情報１２１の設定や変更を受け付けるので、地図データ配信システム１の図管理者等は、その設定や変更を容易に行うことができる。
（第２の実施の形態）
第１の実施の形態では、暗号化対象ノードと暗号化対象ノードに接続された接続リンクを、暗号化後にノード格納部５０２とリンク格納部５０３から削除する方法について述べた。第２の実施の形態では、暗号化対象ノードと接続ノード内のデータを変更することによって暗号化、復号を行う方法について述べる。第１の実施の形態と比較し、第２の実施の形態では、経路探索用データの構造を崩す必要がないという特徴がある。
【０１２２】
第１の実施の形態と第２の実施の形態との違いは暗号処理と復号化処理のみであるため、以下では暗号化処理、復号化処理について、第１の実施の形態におけるとの違いを説明する。
【０１２３】
図１１および図１２は、第２の実施の形態における暗号化処理、復号化処理の処理手順を示すフローチャートである。また、図１３は、暗号化処理前後でのデータ構造の変化の一例を示す図である。以下に、これらの図面を参照して、暗号化処理および復号化処理について説明する。
【０１２４】
まず、暗号化処理の前後におけるデータ構造の変化を、図１３を用いて説明する。なお、図１３は、図９と同様、図５に例示した表示イメージ５１０の経路探索用データ格納部５０１の一部を例示した図である。
【０１２５】
第１の実施の形態の場合と同様、暗号化経路探索用データ格納部５０４ｂは、ノード格納部５０２ｂと、リンク格納部５０３ｂと、暗号化データ部５０５ｂと、を含んで構成される。ノード格納部５０２ｂは、ノードを一意に識別するための識別子であるＮＩＤと、ノードの地図上の位置を表す座標を含み、リンク格納部５０３ｂは、リンクを一意に識別する識別子であるＬＩＤと、ノードの始点と終点のノードを表す始点ＮＩＤと、終点ＮＩＤと、リンクを移動するために必要となるコストとを含んでいる。
【０１２６】
なお、リンク格納部５０３ｂが始点ＮＩＤと終点ＮＩＤから構成されている理由は、移動経路が一方向であることを表すためであり、第１の実施の形態の場合と同様に、双方向のデータ構造を用いてもよい。また、第１の実施の形態と同様に、ノード格納部５０２ｂ、リンク格納部５０３ｂは、上記以外の項目を含んでもよい。
【０１２７】
第１の実施の形態では、暗号化対象ノードとそれに接続した接続リンクをノード格納部５０２ａ、リンク格納部５０３ａから削除し、隣接ノードの暗号化フラグをＴ（ＴＲＵＥ）と設定することによって、経路探索時に復号すべきデータの特定を行った。第２の実施の形態では、図１３に示した通り、ノード格納部５０２ｂ、リンク格納部５０３ｂからデータの削除は行わず、代わりに各格納部に格納された情報を、他のノードやリンクとは区別しうる属性や値となるような情報に書き換えを行う。
【０１２８】
図１３に示した例では、第１の実施の形態と同様、暗号化対象ノードとしてＮ５のノードを暗号化した場合について示している。図１３に示した通り、暗号化対象となるノード（Ｎ５)の座標情報を、暗号化されていることを表す記号「ＥＮＣ」で書き換え、さらに暗号化対象ノード（Ｎ５）の接続リンクのコストを最大値（図１３に示す例では「９９」）に設定する。暗号化対象ノードのもとの座標情報と接続リンクのコストは、第１の実施の形態と同様の方法で暗号化を行い、暗号化データ部５０５ｂに格納する。
【０１２９】
なお、データベース、或いはＧＩＳ製品の制約上の問題で座標情報に座標以外の情報を格納することができない場合には、上記の「ＥＮＣ」への書き換えは、「ＥＮＣ」を意味する代替値であってもよいし、座標情報を別の座標に書き換えてもよい。なお、ノードの位置そのものを非開示にするためには、ランダムな座標位置を用いてもよいが、暗号化後の地図データ（暗号化地図データ１２４）の利用に影響を与えないようにするためは、平文地図データ１２０内の管理外の座標情報を格納する方が望ましい。
【０１３０】
また、例えば、同一の地物内に複数のノードが存在する場合には、地物の中心座標などで座標情報を置き換えてもよい。これによって、本来のノードの座標位置をある程度非開示にすることができる。また、複数のノードを暗号化する場合には、第１の実施の形態のように、代表点のみ残し、後のノード、リンクは、ノード格納部５０２ｂ、リンク格納部５０３ｂから削除してもよい。なお、座標情報を書き変えなくてもよいが、この場合には、コストのみが暗号化され、ノードが地図上のどの位置に配置されているかがわかってしまうため、注意が必要である。
【０１３１】
復号時には、復号処理部１１６が、ノード格納部５０２ｂの座標情報が「ＥＮＣ」である場合、或いは、リンク格納部５０３ｂのコストが最大値である場合に暗号化データ部５０５ｂの関連データを基に復号すべき暗号化データを取得、復号する。この復号処理によって、ノード、リンクが復号された場合には、復号結果からノードの座標、及び、リンクのコストを復元することにより、元の地図データ（平文地図データ１２０）を用いた経路探索が実行できる。一方で、復号できなかった場合にはコストは最大値のままとなっているため、経路探索のコスト評価の際、他の最適な経路と比較した場合に削除可能、或いは、非現実的な経路として削除することができる。
【０１３２】
以下、図１１および図１２を用いて、第２の実施の形態における暗号化、復号化処理の具体的な処理手順を説明する。まず、第２の実施の形態における暗号化処理について説明する。図１１は、第２の実施の形態における暗号化処理の処理手順を示すフローチャートである。
【０１３３】
図１１に示すように、第２の実施の形態における暗号化処理が開始されると（ステップＳ１１００）、暗号化処理部１１１は、経路探索用データ格納部５０１ａを暗号化経路探索用データ格納部５０４ａにコピーする（ステップＳ１１０１）。
【０１３４】
そして、暗号化処理部１１１は、暗号化定義情報１２１を参照し、暗号化すべき暗号化対象ノードの有無を判定する（ステップＳ１１０２）。そして、暗号化処理部１１１は、暗号化すべき暗号化対象ノードがあると判定した場合（ステップＳ１１０２；Ｙｅｓ）、暗号化定義情報１２１に記述されている暗号化対象ノードを取得し（ステップＳ１１０３）、その暗号化対象ノードを変更する（ステップＳ１１０４）。一方、暗号化処理部１１１は、暗号化すべき暗号化対象ノードがないと判定した場合（ステップＳ１１０２；Ｎｏ）、図１１に示す暗号化処理を終了させる（ステップＳ１１１０）。
【０１３５】
そして、暗号化処理部１１１は、変更した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあるか否かを判定し（ステップＳ１１０５）、変更した暗号化対象ノードに接続された接続リンク内に未操作のリンクがあると判定した場合（ステップＳ１１０５；Ｙｅｓ）、その接続リンクのコストを取得し（ステップＳ１１０６）、取得したコストを最大値に設定する（ステップＳ１０７）。そして、暗号化処理部１１１は、ステップＳ１１０５〜Ｓ１１０７までの処理を繰り返し行う。
【０１３６】
一方、暗号化処理部１１１は、暗号化対象ノードに接続された接続リンク内に未操作のリンクがないと判定した場合（ステップＳ１１０５；Ｎｏ）、ステップＳ１１０３において取得した座標情報と、ステップＳ１１０６において取得したコストとを暗号化し（ステップＳ１１０８）、その暗号化結果を暗号化データ格納部５０４ａに格納し（ステップＳ１１０９）、ステップＳ１１０２へ戻る。そして、暗号化処理部１１１は、暗号化定義情報１２１に記述された全ての暗号化対象ノードについて、繰り返しステップＳ１１０２〜Ｓ１１０９までの処理を行う。
【０１３７】
なお、ステップＳ１１０２では、例えば、図６に例示した暗号化定義情報１２１の暗号化対象ノード要素を逐次処理し、暗号化対象ノード要素がなくなるまで繰り返せばよい。また、図９に示した例では、暗号化対象ノード（Ｎ５）に接続されているノードは一つ（Ｎ６、リンクはＬ１４）のみであるが、ステップＳ１１０５〜Ｓ１１０７に示した通り、接続リンクが複数ある場合には、全ての接続リンクに対して同様の処理を行う。
【０１３８】
第１の実施の形態と同様、ステップＳ１１０８における暗号化処理は、ノードを一つずつ行うのではなく、複数のノードをまとめて暗号化してもよい。また、複数ノードを暗号化する場合には、以下のようにしてもよい。例えば、座標情報の書き換えに際して「ＥＮＣ」の代わりに、暗号化対象となるノードが同一の領域内にある場合には、ステップ１１０４の処理を領域の中心座標などを格納するようにしてもよい。また、この場合に第１の実施の形態と同様に、代表点となるノードのみを残し、他のノードリンクをノード格納部５０２ｂ、リンク格納部５０３ｂから削除してもよい。なお、この場合、削除したノードに合わせて、リンク格納部５０３ｂの始点ＮＩＤ、終点ＮＩＤも書き換える必要があることに注意が必要である。
【０１３９】
続いて、第２の実施の形態における復号化処理について説明する。図１２は、第２の実施の形態における復号化処理の処理手順を示すフローチャートである。なお、第１の実施の形態と同様、図１２は、経路探索アルゴリズムにおける復号処理を行うための処理フローを示したものであり、経路探索アルゴリズムそのものの処理は、その手順の概略のみを示している。経路探索アルゴリズムの中核処理は、図１２内の点線で示した部分である。以下、図１２に示す復号化処理について説明する。
【０１４０】
図１２に示すように、復号化処理が開始されると（ステップＳ１２００）、地図復号装置１０６の復号処理部１１６は、まず、出発地ノードを始点ノードに設定する（ステップＳ１２０１）。
【０１４１】
そして、復号処理部１１６は、経路探索が終了しているか否かを判定し（ステップＳ１２０２）、経路探索が終了していると判定した場合（ステップＳ１２０２；Ｙｅｓ）、図８に示す復号化処理を終了させる（ステップＳ１２１０）。
【０１４２】
一方、復号処理部１１６は、経路探索が終了していないと判定した場合（ステップＳ１２０２；Ｎｏ）、ノード格納部５０２ａとリンク格納部５０３ａとを参照し、始点ノードの接続リンク（隣接ノード）を検索し（ステップＳ１２０３）、未探索の隣接ノードがあるか否かを判定する（ステップＳ１２０４）。
【０１４３】
そして、復号処理部１１６は、未探索の隣接ノードがあると判定した場合（ステップＳ１２０４；Ｙｅｓ）、さらにその未探索の隣接ノードを関連データとして有する暗号化データが暗号化データ部５０５ｂにあるか否かを判定し（ステップＳ１２０５）、暗号化データが暗号化データ部５０５ｂにあると判定した場合（ステップＳ１２０５；Ｙｅｓ）、暗号化データ部５０５ａから暗号化データを取得し、取得した暗号化データを復号する（ステップＳ１２０６）。一方、復号処理部１１６は、暗号化データが暗号化データ部５０５ｂにないと判定した場合（ステップＳ１２０５；Ｎｏ）、ステップＳ１２０９に進む。
【０１４４】
復号処理部１１６は、ステップＳ１２０６で取得した暗号化データの復号に成功したか否かを判定し（ステップＳ１２０７）、復号に成功したと判定した場合（ステップＳ１２０７；Ｙｅｓ）、ステップＳ１２０６における復号結果からノード、リンクを復元し、復元したノード、リンクをノード格納部５０２ｂ、リンク格納部５０３ｂに追加する（ステップＳ１２０８）。一方、復号処理部１１６は、復号に成功していない（失敗した）と判定した場合（ステップＳ１２０７；Ｎｏ）、ステップＳ１２０９に進む。
【０１４５】
そして、復号処理部１１６は、ステップＳ１２０５またはステップＳ１２０７またはステップＳ１２０８のいずれかの処理が終了すると、リンク格納部５０３ａ内のコスト欄を参照し、始点ノードから隣接ノードまでのコストを算出し、出発地ノードから隣接ノードまでのコスト評価を行い（ステップＳ１２０９）、ステップＳ１２０２に戻る。そして、復号処理部１１６は、ステップＳ１２０２からＳ１２０９までの処理を経路探索が終了するまで繰り返し行う。
【０１４６】
第２の実施の形態では、暗号化時に暗号化対象ノードの接続リンクのコストを最大にする。これにより、暗号化データが復号できなかった場合には、ステップＳ１２０９において、コスト最大として出発点ノードから該当ノードまでのコスト評価が行われるため、非現実的なコストとなり、他の最適なコストを有する経路があった場合に、暗号化ノードを含む経路を排除することができる。したがって、図５に示したように、最終的に利用者には、そのような経路を含まない表示イメージ５１０が表示されることとなる。
【０１４７】
なお、上記のステップＳ１２０６において、例えば復号結果がノード、リンクでないなどの復号が異常停止した場合には処理を停止することが望ましい。また、経路探索の家庭において、目的地ノードにたどりつかないなど、経路探索が一定時間以上終了しない場合や非現実的なコスト（例えば、徒歩での移動に１００年以上かかるなど）であった場合には、ステップＳ１２０２において処理を停止してもよい。
【０１４８】
上記のステップＳ１２０６における復号、ステップＳ１２０８におけるノード、リンクの復元は、単一のノードに対してではなく、複数のノード、リンクに対して行ってもよい。例えば、前述の暗号化処理時に複数のノードをまとめて暗号化した場合には、ステップＳ１２０６における復号の結果には、複数のノード、リンクが含まれるため、ステップＳ１２０８は復号されたノード、リンクを全て復元することになる。
【０１４９】
なお、上記の復号処理では、経路探索アルゴリズム内で逐次復号を行っているが、事前に復号すべきデータが少ない場合（例えば、ステップＳ４０３における地図格納装置１０２からの応答に暗号化データが一つしか含まれていない場合など）には、復号処理部１１６は、図１２の処理の前に復号処理をまとめて実施してもよい。
【０１５０】
また、第１の実施の形態と同様、経路探索においては、データ管理、或いは、経路探索を効率に行うため、ビルのフロア等の階層、或いは領域ごとにデータ管理を行っている場合がある。この場合、経路探索についても、領域ごと、或いは階層別に経路探索アルゴリズムを実行し、これらの結果を繋ぎ合わせることで経路探索を実行する場合がある。その場合には、図１２の処理を階層、或いは、領域ごとの経路探索を行い、これらの探索結果を組み合わせて、最終的な出発地ノードから目的地ノードまでの経路探索を行ってもよい。
【０１５１】
なお、本発明は、上記実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【０１５２】
１：地図データ配信システム、１００：ネットワーク、１０１：地図暗号化装置、１０２：地図格納装置、１０３：鍵管理装置、１０４：地図配信装置、１０５：地図閲覧装置、１０６：地図復号装置、１１０：暗号化情報生成部、１１１：暗号化処理部、１１２：データベース処理部、１１３：鍵生成部、１１４：経路探索処理部、１１５：クエリ要求部、１１６：復号処理部、１１７：クエリ処理部、１１８：表示処理部、１２０：平文地図データ、１２１：暗号化定義情報、１２２：暗号化鍵、１２３：復号鍵、１２４：暗号化地図データ、２００：計算機、２０１：ＣＰＵ、２０２：ＲＡＭ、２０３：入力装置、２０４：表示装置、２０５：通信装置、２０６：読書装置、２０７：外部記憶装置、２０８：外部記憶媒体、２０９：インターフェイス、５００：地図データ格納部、５０１：経路探索用データ格納部、５０２：ノード格納部、５０３：リンク格納部、５１０：表示イメージ５１０、５０１ａ：経路探索用データ格納部、５０２ａ：ノード格納部、５０３ａ：リンク格納部、５０４ａ：暗号化経路探索用データ格納部、５０５ａ：暗号化データ部、１０００：地図表示エリア、１００１：設定エリア、１００２：ファイル、１００３：データベース、１００４：鍵読込、１００５：マウスカーソル、５０１ｂ：経路探索用データ格納部、５０２ｂ：ノード格納部、５０３ｂ：リンク格納部、５０４ｂ：暗号化経路探索用データ格納部、５０５ｂ：暗号化データ部。
【特許請求の範囲】
【請求項１】
地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと前記経路探索用データに対応した地図を表示するための表示用データとが対応付けられた地図データと、前記ノードと前記表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報と、前記経路探索用データを暗号化するための暗号化鍵を格納する記憶部と、
前記経路探索用データと、前記暗号化鍵と、前記暗号化定義情報とに基づいて、前記利用者ごとに、暗号化すべき前記ノードを特定し、特定した前記ノードおよび特定した前記ノードに隣接するノードとのリンク情報の前記経路探索用データを暗号化し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する暗号化処理部と、
を備えることを特徴とする暗号化装置。
【請求項２】
前記暗号化処理部は、特定した前記ノードと前記ノードに隣接するノードとのリンク情報を前記経路探索用データとして暗号化した後、削除し、さらに前記隣接するノードに特定したノードを暗号化したことを示す復号フラグを設定し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する、
ことを特徴とする請求項１に記載の暗号化装置。
【請求項３】
前記ノードには座標情報を含み、前記リンク情報には前記ノードから前記ノードに隣接するノードまでに要するコスト情報を含み、
前記暗号化処理部は、特定した前記ノードに含まれる前記座標情報と前記リンク情報に含まれる前記コスト情報とを暗号化した後、特定した前記ノードに座標情報とは異なる情報を設定し、特定した前記コスト情報に、コストが最大となる値を設定することによって更新し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する、
ことを特徴とする請求項１に記載の暗号化装置。
【請求項４】
利用者から地図上の位置のある地点から他の地点までの経路を探索するための経路探索要求を受けた場合に、地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データを復号化する復号化鍵に基づいて、前記経路探索用データと、経路探索用データに対応した地図を表示するための表示用データとが対応付けられた暗号化地図データを復号化する復号処理部と、
前記ある地点から前記他の地点までの経路を、前記暗号化地図データに対応する前記経路探索用データに含まれる前記ノードと前記リンク情報とに基づいて前記復号処理部を用いて暗号化地図データの復号を行い、復号結果を用いて前記ノードと前記リンク情報とに基づいて繰り返し探索する経路探索部と、
を備えることを特徴とする復号化装置。
【請求項５】
利用者からの要求に応じて地図上の位置のある地点から他の地点までの経路を探索する経路探索システムであって、
地図閲覧装置は、
前記利用者から要求された前記経路を探索する要求をネットワークを介して送信する要求部と、
前記要求部が要求した前記経路を探索した結果を表示する表示処理部と、を備え、
地図格納装置は、
暗号化鍵によって暗号化された地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと前記経路探索用データに対応した地図を表示するための表示用データとを対応付けた暗号化地図データを記憶する記憶部と、
前記暗号化鍵によって暗号化された前記暗号化地図データから前記経路探索用データを検索し、検索した検索結果を前記ネットワークを介して送信する検索処理部と、を備え、
復号化装置は、
前記地図格納装置が前記検索を行った場合に、前記暗号化鍵に対応する復号鍵に基づいて前記暗号化地図データを復号化する復号処理部と、
前記経路を、前記暗号化地図データに対応する前記経路探索用データに含まれる前記ノードと前記リンク情報とに基づいて前記復号処理部を用いて暗号化地図データの復号を行い、復号結果を用いて前記ノードと前記リンク情報とに基づいて、繰り返し探索し、探索した探索結果を前記ネットワークを介して送信する経路探索部と、を備え、
地図配信装置は、
前記地図閲覧装置から前記要求を受信した場合に、前記地図格納装置に前記ネットワークを介して前記検索を行うよう要求して前記検索結果を受信し、受信した前記検索結果を前記復号装置に送信して前記探索を行うように要求し、前記復号化装置から前記探索結果を受信した場合に、前記探索結果を前記ネットワークを介して前記地図閲覧装置に送信するクエリ処理部、
を備えることを特徴とする経路探索システム。
【請求項６】
前記地図配信装置は、
前記クエリ処理部が、前記地図格納装置から前記検索結果として前記検索用データと前記表示用データとを受信し、前記復号化装置から受信した前記表示用データに基づいて、前記地図閲覧装置に表示させるための地図データを生成し、生成した前記地図データを前記地図閲覧装置に送信し、
前記復号化装置は、
前記地図配信装置から受信した前記検索用データに基づいて復号化された前記暗号化データに対応する前記表示用データを生成し、生成した前記表示用データを前記地図配信装置に送信するイメージ生成部をさらに備える、
ことを特徴とする請求項５に記載の経路探索システム。
【請求項１】
地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと前記経路探索用データに対応した地図を表示するための表示用データとが対応付けられた地図データと、前記ノードと前記表示用データを開示させる利用者である開示先ユーザとが対応付けられた暗号化定義情報と、前記経路探索用データを暗号化するための暗号化鍵を格納する記憶部と、
前記経路探索用データと、前記暗号化鍵と、前記暗号化定義情報とに基づいて、前記利用者ごとに、暗号化すべき前記ノードを特定し、特定した前記ノードおよび特定した前記ノードに隣接するノードとのリンク情報の前記経路探索用データを暗号化し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する暗号化処理部と、
を備えることを特徴とする暗号化装置。
【請求項２】
前記暗号化処理部は、特定した前記ノードと前記ノードに隣接するノードとのリンク情報を前記経路探索用データとして暗号化した後、削除し、さらに前記隣接するノードに特定したノードを暗号化したことを示す復号フラグを設定し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する、
ことを特徴とする請求項１に記載の暗号化装置。
【請求項３】
前記ノードには座標情報を含み、前記リンク情報には前記ノードから前記ノードに隣接するノードまでに要するコスト情報を含み、
前記暗号化処理部は、特定した前記ノードに含まれる前記座標情報と前記リンク情報に含まれる前記コスト情報とを暗号化した後、特定した前記ノードに座標情報とは異なる情報を設定し、特定した前記コスト情報に、コストが最大となる値を設定することによって更新し、暗号化した前記経路探索用データと前記表示用データとを対応付けた暗号化地図データを生成する、
ことを特徴とする請求項１に記載の暗号化装置。
【請求項４】
利用者から地図上の位置のある地点から他の地点までの経路を探索するための経路探索要求を受けた場合に、地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データを復号化する復号化鍵に基づいて、前記経路探索用データと、経路探索用データに対応した地図を表示するための表示用データとが対応付けられた暗号化地図データを復号化する復号処理部と、
前記ある地点から前記他の地点までの経路を、前記暗号化地図データに対応する前記経路探索用データに含まれる前記ノードと前記リンク情報とに基づいて前記復号処理部を用いて暗号化地図データの復号を行い、復号結果を用いて前記ノードと前記リンク情報とに基づいて繰り返し探索する経路探索部と、
を備えることを特徴とする復号化装置。
【請求項５】
利用者からの要求に応じて地図上の位置のある地点から他の地点までの経路を探索する経路探索システムであって、
地図閲覧装置は、
前記利用者から要求された前記経路を探索する要求をネットワークを介して送信する要求部と、
前記要求部が要求した前記経路を探索した結果を表示する表示処理部と、を備え、
地図格納装置は、
暗号化鍵によって暗号化された地図上の位置を示すノードおよび前記ノードと前記ノードに隣接するノードとの関連性を示すリンク情報を含む経路探索用データと前記経路探索用データに対応した地図を表示するための表示用データとを対応付けた暗号化地図データを記憶する記憶部と、
前記暗号化鍵によって暗号化された前記暗号化地図データから前記経路探索用データを検索し、検索した検索結果を前記ネットワークを介して送信する検索処理部と、を備え、
復号化装置は、
前記地図格納装置が前記検索を行った場合に、前記暗号化鍵に対応する復号鍵に基づいて前記暗号化地図データを復号化する復号処理部と、
前記経路を、前記暗号化地図データに対応する前記経路探索用データに含まれる前記ノードと前記リンク情報とに基づいて前記復号処理部を用いて暗号化地図データの復号を行い、復号結果を用いて前記ノードと前記リンク情報とに基づいて、繰り返し探索し、探索した探索結果を前記ネットワークを介して送信する経路探索部と、を備え、
地図配信装置は、
前記地図閲覧装置から前記要求を受信した場合に、前記地図格納装置に前記ネットワークを介して前記検索を行うよう要求して前記検索結果を受信し、受信した前記検索結果を前記復号装置に送信して前記探索を行うように要求し、前記復号化装置から前記探索結果を受信した場合に、前記探索結果を前記ネットワークを介して前記地図閲覧装置に送信するクエリ処理部、
を備えることを特徴とする経路探索システム。
【請求項６】
前記地図配信装置は、
前記クエリ処理部が、前記地図格納装置から前記検索結果として前記検索用データと前記表示用データとを受信し、前記復号化装置から受信した前記表示用データに基づいて、前記地図閲覧装置に表示させるための地図データを生成し、生成した前記地図データを前記地図閲覧装置に送信し、
前記復号化装置は、
前記地図配信装置から受信した前記検索用データに基づいて復号化された前記暗号化データに対応する前記表示用データを生成し、生成した前記表示用データを前記地図配信装置に送信するイメージ生成部をさらに備える、
ことを特徴とする請求項５に記載の経路探索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１１−２１１３８２（Ｐ２０１１−２１１３８２Ａ）
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願番号】特願２０１０−７５５２９（Ｐ２０１０−７５５２９）
【出願日】平成２２年３月２９日（２０１０．３．２９）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２１年度 総務省「ユビキタス・プラットフォーム技術の研究開発（ユビキタス空間情報基盤技術）」委託研究、産業技術力強化法第１９条の適用を受ける特許出願）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願日】平成２２年３月２９日（２０１０．３．２９）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２１年度 総務省「ユビキタス・プラットフォーム技術の研究開発（ユビキタス空間情報基盤技術）」委託研究、産業技術力強化法第１９条の適用を受ける特許出願）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]