(57)【要約】【課題】効率的に符号化キャッシュの正当性を検証できる認証符生成装置、検証装置、認証符生成方法及び認証符生成プログラムを提供すること。【解決手段】送信ノード１０は、鍵行列Ａ及び公開されたブランチ行列Ｍを入力とする第１乗算部１０１と、第１乗算部１０１による演算結果の行列ＭＡの中から互いに異なる行を、中継ノード２０のそれぞれへ固有の配布鍵ｋｉとして送信する送信部１０２と、送信元データを示す行列Ｃ及び鍵行列Ａを入力とする第２乗算部１０３と、第２乗算部１０３による演算結果を、送信元データの認証符ａｃとして公開する公開部１０４と、を備える。【選択図】図２
2015041880.tif 000002
【特許請求の範囲】
【請求項１】
送信元データに基づくネットワーク内の符号化キャッシュの正当性を検証ノードにおいて検証するための認証符生成装置であって、
鍵行列及び公開されたブランチ行列を入力とする第１乗算部と、
前記第１乗算部による演算結果の行列の中から互いに異なる部分を、前記検証ノードのそれぞれへ固有の配布鍵として送信する送信部と、
前記送信元データを示す行列及び前記鍵行列を入力とする第２乗算部と、
前記第２乗算部による演算結果を、前記送信元データの認証符として公開する公開部と、を備える認証符生成装置。
【請求項２】
前記送信部は、前記第１乗算部による行列演算の方向に応じて、演算結果の行又は列のいずれかを前記配布鍵として送信する請求項１に記載の認証符生成装置。
【請求項３】
前記鍵行列は、前記送信元データを示す行列の大きさ、及び安全性要件に基づいて、大きさが設定される請求項１又は請求項２に記載の認証符生成装置。
【請求項４】
前記ブランチ行列は、前記鍵行列の大きさ、及び前記検証ノードの数に基づいて、大きさが設定される請求項３に記載の認証符生成装置。
【請求項５】
請求項１から請求項４のいずれかに記載の認証符生成装置により生成された前記認証符及び前記配布鍵を用いて、前記検証ノードにおいて前記符号化キャッシュの正当性を検証する検証装置であって、
前記検証ノードに至るまでの符号化を表すネットワーク符号化行列、前記認証符、及び前記ブランチ行列の中の前記配布鍵に対応する部分を入力とする第３乗算部と、
前記符号化キャッシュ及び前記配布鍵を入力とする第４乗算部と、
前記第３乗算部による演算結果と前記第４乗算部による演算結果とを比較し、同一でない場合に前記符号化キャッシュが正当でないとの検証結果を出力する比較部と、を備える検証装置。
【請求項６】
送信元データに基づくネットワーク内の符号化キャッシュの正当性を検証ノードにおいて検証するための認証符生成方法であって、
鍵行列及び公開されたブランチ行列を入力とする第１乗算ステップと、
前記第１乗算ステップによる演算結果の行列の中から互いに異なる部分を、前記検証ノードのそれぞれへ固有の配布鍵として送信する送信ステップと、
前記送信元データを示す行列及び前記鍵行列を入力とする第２乗算ステップと、
前記第２乗算ステップによる演算結果を、前記送信元データの認証符として公開する公開ステップと、をコンピュータが実行する認証符生成方法。
【請求項７】
送信元データに基づくネットワーク内の符号化キャッシュの正当性を検証ノードにおいて検証するための認証符生成プログラムであって、
鍵行列及び公開されたブランチ行列を入力とする第１乗算ステップと、
前記第１乗算ステップによる演算結果の行列の中から互いに異なる部分を、前記検証ノードのそれぞれへ固有の配布鍵として送信する送信ステップと、
前記送信元データを示す行列及び前記鍵行列を入力とする第２乗算ステップと、
前記第２乗算ステップによる演算結果を、前記送信元データの認証符として公開する公開ステップと、をコンピュータに実行させるための認証符生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク符号化における符号化キャッシュの正当性を検証するための認証符生成装置、検証装置、認証符生成方法及び認証符生成プログラムに関する。
【背景技術】
【０００２】
従来、インターネットに代わって、より効率的なデータ伝送及び拡散を実現する情報ネットワークであるＩＣＮ（Ｉｎｆｏｒｍａｔｉｏｎ−Ｃｅｎｔｒｉｃ  Ｎｅｔｗｏｒｋ）が提案されている（例えば、非特許文献１参照）。ＩＣＮでは、ネットワークを構成する中継ノードに、中継したデータをキャッシュする機能を持たせることにより、効率的なデータ転送を実現している。
【０００３】
また、ＩＣＮに限らず、ネットワークの中継ノード（例えば、ルータ又はスイッチ）に数学的な演算機能（符号化機能）を持たせることにより、伝送レート及びスループットの向上、並びに消費エネルギの低減を実現するネットワーク符号化の技術が提案されている（例えば、非特許文献２参照）。さらに、このネットワーク符号化をＩＣＮの構成に取り入れることが提案されている（例えば、非特許文献３参照）。ネットワーク符号化されたＩＣＮでは、符号化されたデータが中継ノードにキャッシュされる。
【０００４】
ところで、ネットワーク符号化では、転送される符号化データが一度汚染されると、この汚染がネットワーク上で伝送される他の符号化データにも急速に広まる。ここで、汚染とは、符号化データに誤りが発生したり、攻撃者によって書き換えられたりした状態をいう。ネットワーク符号化により符号化されたデータが汚染されているか否かを検証する情報理論的に安全な認証手法が提案されている（例えば、非特許文献４参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｂ．  Ａｈｌｇｅｎ，  Ｃ．  Ｄａｎｎｅｗｉｔｚ，  Ｃ．  Ｉｍｂｒｅｎｄａ，  Ｄ．  Ｋｕｔｓｃｈｅｒ，  ａｎｄ  Ｂ．  Ｏｈｌｍａｎ，  “Ａ  ｓｕｒｖｅｙ  ｏｆ  ｉｎｆｏｒｍａｔｉｏｎ−ｃｅｎｔｒｉｃ  ｎｅｔｗｏｒｋｉｎｇ”，  ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｍａｇａｚｉｎｅ，  ｖｏｌ．  ５０，  ｎｏ．  ７，  ｐｐ．  ２６−３６，  ２０１２．
【非特許文献２】Ｒ．  Ａｈｌｓｗｅｄｅ，  Ｎ．  Ｃａｉ，  Ｓ．−Ｙ．  Ｒ．  Ｌｉ，  ａｎｄ  Ｒ．  Ｗ．  Ｙｅｕｎｇ，  “Ｎｅｔｗｏｒｋ  ｉｎｆｏｒｍａｔｉｏｎ  ｆｌｏｗ，”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  ｖｏｌ．  ４６，  ｎｏ．  ４，  ｐｐ．１２０４−１２１６，  ２０００．
【非特許文献３】Ｍ．  Ｍｏｎｔｐｅｔｉｔ，  Ｃ．  Ｗｅｓｔｐｈａｌ，  ａｎｄ  Ｄ．  Ｔｒｏｓｓｅｎ，  “Ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ  ｍｅｅｔｓ  ｉｎｆｏｒｍａｔｉｏｎ−ｃｅｎｔｒｉｃ  ｎｅｔｗｏｒｋｉｎｇ：  ａｎ  ａｒｃｈｉｔｅｃｔｕｒａｌ  ｃａｓｅ  ｆｏｒ  ｉｎｆｏｒｍａｔｉｏｎ  ｄｉｓｐｅｒｓｉｏｎ  ｔｈｒｏｕｇｈ  ｎａｔｉｖｅ  ｎｅｔｗｏｒｋ  ｃｏｄｉｎｇ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＮｏＭ  ２０１２，  ｐｐ．  ３１−３６，  ２０１２．
【非特許文献４】Ｆ．  Ｏｇｇｉｅｒ，  ａｎｄ  Ｈ．  Ｆａｔｈｉ，  “Ａｎ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ  ａｇａｉｎｓｔ  Ｐｏｌｌｕｔｉｏｎ  Ａｔｔａｃｋｓ  ｉｎ  Ｎｅｔｗｏｒｋ  Ｃｏｄｉｎｇ”，  ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，  ｖｏｌ．  １９，  ｎｏ．  ６，  ｐｐ．  １５８７−１５９６，  ２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の認証手法は、元のデータに対して数倍の非常に大きな認証符が必要であり、さらに、有限体の拡大体上でべき乗演算を行うため計算量が非常に大きかった。
【０００７】
本発明は、効率的に符号化キャッシュの正当性を検証できる認証符生成装置、検証装置、認証符生成方法及び認証符生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る認証符生成装置は、送信元データに基づくネットワーク内の符号化キャッシュの正当性を検証ノードにおいて検証するために認証符を生成する装置であって、鍵行列及び公開されたブランチ行列を入力とする第１乗算部と、前記第１乗算部による演算結果の行列の中から互いに異なる部分を、前記検証ノードのそれぞれへ固有の配布鍵として送信する送信部と、前記送信元データを示す行列及び前記鍵行列を入力とする第２乗算部と、前記第２乗算部による演算結果を、前記送信元データの認証符として公開する公開部と、を備える。
【０００９】
前記送信部は、前記第１乗算部による行列演算の方向に応じて、演算結果の行又は列のいずれかを前記配布鍵として送信してもよい。
【００１０】
前記鍵行列は、前記送信元データを示す行列の大きさ、及び安全性要件に基づいて、大きさが設定されてもよい。
【００１１】
前記ブランチ行列は、前記鍵行列の大きさ、及び前記検証ノードの数に基づいて、大きさが設定されてもよい。
【００１２】
本発明に係る検証装置は、請求項１から請求項４のいずれかに記載の認証符生成装置により生成された前記認証符及び前記配布鍵を用いて、前記検証ノードにおいて前記符号化キャッシュの正当性を検証する装置であって、前記検証ノードに至るまでの符号化を表すネットワーク符号化行列、前記認証符、及び前記ブランチ行列の中の前記配布鍵に対応する部分を入力とする第３乗算部と、前記符号化キャッシュ及び前記配布鍵を入力とする第４乗算部と、前記第３乗算部による演算結果と前記第４乗算部による演算結果とを比較し、同一でない場合に前記符号化キャッシュが正当でないとの検証結果を出力する比較部と、を備える。
【００１３】
本発明に係る認証符生成方法は、送信元データに基づくネットワーク内の符号化キャッシュの正当性を検証ノードにおいて検証するための方法であって、鍵行列及び公開されたブランチ行列を入力とする第１乗算ステップと、前記第１乗算ステップによる演算結果の行列の中から互いに異なる部分を、前記検証ノードのそれぞれへ固有の配布鍵として送信する送信ステップと、前記送信元データを示す行列及び前記鍵行列を入力とする第２乗算ステップと、前記第２乗算ステップによる演算結果を、前記送信元データの認証符として公開する公開ステップと、をコンピュータが実行する。
【００１４】
本発明に係る認証符生成プログラムは、送信元データに基づくネットワーク内の符号化キャッシュの正当性を検証ノードにおいて検証するためのプログラムであって、鍵行列及び公開されたブランチ行列を入力とする第１乗算ステップと、前記第１乗算ステップによる演算結果の行列の中から互いに異なる部分を、前記検証ノードのそれぞれへ固有の配布鍵として送信する送信ステップと、前記送信元データを示す行列及び前記鍵行列を入力とする第２乗算ステップと、前記第２乗算ステップによる演算結果を、前記送信元データの認証符として公開する公開ステップと、をコンピュータに実行させる。
【発明の効果】
【００１５】
本発明によれば、効率的に符号化キャッシュの正当性が検証される。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る認証システムの構成を示す図である。
【図２】実施形態に係る送信ノードの構成を示す図である。
【図３】実施形態に係る中継ノードの構成を示す図である。
【図４】実施形態に係る認証符生成処理を示すフローチャートである。
【図５】実施形態に係る検証処理を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について説明する。
本実施形態では、ＩＣＮに対してネットワーク符号化が適用される。この場合、送信元のデータに対して施される電子署名は、中継ノードにおいては利用できなくなるため、符号化されたキャッシュの汚染への対策が必要になる。通常のネットワーク符号化ではキャッシュが考慮されないため、汚染の影響はデータを受信するノードに限られる。ところが、ＩＣＮにおけるネットワーク符号化では、キャッシュされたデータが中継ノードに拡散されるため、汚染は深刻な問題となる。
本実施形態の認証システム１は、中継ノード２０（検証ノード）において、符号化キャッシュの認証処理を行うが、ＩＣＮでは、高速かつ効率的なデータ伝送を実現することを目的としているため、効率的かつ高速な認証手法を行う。
【００１８】
図１は、本実施形態に係る認証システム１の構成を示す図である。
送信ノード１０から送信されるコンテンツ等のデータは、ネットワーク内の複数の中継ノードを経由して、受信ノード３０で受信される。中継ノードでは、所定の符号化処理により符号化されたデータがキャッシュ２１に記憶される。このキャッシュ２１は、受信ノード３０からのダウンロード要求に応じて参照される。
キャッシュ２１内の符号化キャッシュは、中継ノード２０により汚染の有無が検証され、正当性が認証されたデータのみが保持される。
【００１９】
図２は、本実施形態に係る送信ノード１０の構成を示す図である。
送信ノード１０（認証符生成装置）は、送信元データＣに基づくネットワーク内の符号化キャッシュの正当性を中継ノード２０において検証するための認証符及び検証用の鍵（配布鍵）を生成する装置である。
【００２０】
送信ノード１０は、第１乗算部１０１と、送信部１０２と、第２乗算部１０３と、公開部１０４とを備える。
また、送信ノード１０は、秘密情報であるオリジナルの鍵行列「Ａ∈Ｆｔ×ｍ」を有する。なお、Ｆは、有限体（基礎体）を表す。
【００２１】
第１乗算部１０１は、基礎体上の行列乗算器であり、鍵行列Ａに対して、公開されたブランチ行列「Ｍ∈ＦＶ×ｔ」を乗じ、
【数１】
2015041880.tif 000003
を得る。
【００２２】
送信部１０２は、第１乗算部１０１による演算結果の行列ＭＡの中から互いに異なる部分を、検証を行う中継ノード２０のそれぞれへ、固有の配布鍵として送信する。
具体的には、送信部１０２は、演算結果の行列ＭＡの各行を配布鍵として送信する。なお、鍵行列Ａ及びブランチ行列Ｍが転置され、それぞれ「Ａ∈Ｆｍ×ｔ」、「Ｍ∈Ｆｔ×V」である場合には、上記乗算の演算方向は逆になる。この場合、送信部１０２は、演算結果の行列ＡＭの各列を配布鍵として送信する。
以下、第１乗算部１０１は、ＭＡを算出し、送信部１０２は、ＭＡの各行「ｋｉ＝［ｋｉ，１，…，ｋｉ，ｍ］∈Ｆｍ」（ｉ＝１，・・・，Ｖ）を、検証機能を有する各中継ノード２０へ配布するものとする。ここで、Ｖは、検証機能を有する中継ノード２０の数である。
【００２３】
なお、配布鍵ｋｉは、基礎体Ｆのｍ次拡大体の要素とみなしてもよい。
また、パラメータｔは、値が大きいほど安全性が高い。したがって、鍵行列Ａの大きさ（ｔ×ｍ）は、送信元データを示す行列「Ｃ∈Ｆｍ×ｎ」の大きさ（ｍ×ｎ）、及び安全性要件に基づいて設定される。ここで、データＣは、基礎体Ｆのｍ次拡大体上のｎ次元行ベクトルであってもよい。
さらに、ブランチ行列Ｍの大きさ（Ｖ×ｔ）は、鍵行列の大きさ（ｔ×ｍ）、及び検証機能を有する中継ノード２０の数（Ｖ）に基づいて設定される。
【００２４】
第２乗算部１０３は、基礎体上の行列乗算器であり、送信元データを示す行列Ｃに対して、鍵行列Ａを乗じ、認証符「ａｃ＝ＡＣ∈Ｆｔ×ｎ」を得る。
なお、認証符ａｃは、基礎体Ｆのｎ次拡大体上のｔ次元列ベクトルとみなしてもよい。
【００２５】
公開部１０４は、第２乗算部１０３による演算結果ａｃを、送信元データＣの認証符として公開する。なお、公開部１０４は、認証符ａｃを、データＣのテイラー等に付加して中継ノード２０へ送信してもよい。
【００２６】
図３は、本実施形態に係る中継ノード２０の構成を示す図である。
中継ノード２０は、送信ノード１０により生成された認証符ａｃ及び配布鍵ｋｉを用いて、キャッシュ２１に記憶されている符号化キャッシュｂの正当性を検証する装置である。
【００２７】
中継ノード２０は、第３乗算部２０１と、第４乗算部２０２と、比較部２０３とを備える。
また、中継ノード２０は、符号化キャッシュ「ｂ＝ＣＢ∈Ｆｍ×ｌ」をキャッシュ２１に保存している。
【００２８】
ここで、基礎体上の行列「Ｂ∈Ｆｎ×ｌ」は、中継ノード２０に至るまでに施された符号化を表すネットワーク符号化行列であり、公開されているか、又は中継ノード２０にとって既知のものである。なお、パラメータｌは、キャッシュの保存数によって異なる整数である。
符号化キャッシュｂは、データＣが拡大体上のベクトルとして表されている場合、基礎体Ｆのｍ次拡大体上のｌ次元列ベクトルとみなしてもよい。
【００２９】
第３乗算部２０１は、基礎体上の行列乗算器であり、ネットワーク符号化行列Ｂ、認証符ａｃ、及びブランチ行列Ｍの中の配布鍵ｋｉに対応するｉ行目「ｍｉ∈Ｆｔ」を入力とし、「ｍｉａｃＢ∈Ｆｌ」を出力する。
【００３０】
第４乗算部２０２は、基礎体上の行列乗算器であり、符号化キャッシュｂ及び配布鍵ｋｉを入力とし、「ｋｉｂ∈Ｆｌ」を出力する。
【００３１】
比較部２０３は、第３乗算部２０１による演算結果と第４乗算部２０２による演算結果とを比較し、比較結果を出力する。両者が同一でない場合、符号化キャッシュｂは汚染されており、正当でないと判定される。
中継ノード２０は、符号化キャッシュｂが正当でない場合、この符号化キャッシュｂを破棄することにより、汚染の拡散を防止する。
【００３２】
図４は、本実施形態に係る認証符生成処理を示すフローチャートである。
ステップＳ１において、送信ノード１０は、送信対象であるデータＣを生成する。
【００３３】
ステップＳ２において、送信ノード１０は、データＣの大きさ及び安全性要件に対応した鍵行列Ａを生成する。
【００３４】
ステップＳ３において、送信ノード１０は、鍵行列Ａの大きさ及び検証機能を有する中継ノード２０の数に対応したブランチ行列Ｍを生成して公開する。
【００３５】
ステップＳ４において、送信ノード１０は、第１乗算部１０１により、ブランチ行列Ｍと鍵行列Ａとを乗算し、行列ＭＡを算出する。
【００３６】
ステップＳ５において、送信ノード１０は、送信部１０２により、行列ＭＡのｉ行目ｋｉを、検証機能を有するｉ番目の中継ノード２０へ配布鍵として送信する。
【００３７】
ステップＳ６において、送信ノード１０は、第２乗算部１０３により、鍵行列ＡとデータＣとを乗算して認証符ａｃを生成する。そして、送信ノード１０は、公開部１０４により、認証符ａｃを公開する。
【００３８】
ステップＳ７において、送信ノード１０は、認証符ａｃ及び配布鍵ｋｉを中継ノード２０へ提供して符号化キャッシュｂの検証を可能としたので、データＣを送信する。
【００３９】
図５は、本実施形態に係る検証処理を示すフローチャートである。
ステップＳ１１において、中継ノード２０は、送信ノード１０から配布鍵ｋｉを受信する。
【００４０】
ステップＳ１２において、中継ノード２０は、公開されているデータＣの認証符ａｃを取得する。
【００４１】
ステップＳ１３において、中継ノード２０は、公開されているブランチ行列のｉ行目ｍｉを取得する。
【００４２】
ステップＳ１４において、中継ノード２０は、第３乗算部２０１により、認証符ａｃ及びブランチ行列のｉ行目ｍｉを、符号化行列Ｂに乗じ、ｍｉａｃＢを算出する。
【００４３】
ステップＳ１５において、中継ノード２０は、第４乗算部２０２により、配布鍵ｋｉを符号化キャッシュｂに乗じ、ｋｉｂを算出する。
【００４４】
ステップＳ１６において、中継ノード２０は、比較部２０３により、ステップＳ１４の演算結果と、ステップＳ１５の演算結果とを比較し、同一か否かを判定する。この判定がＹＥＳの場合、中継ノード２０は、符号化キャッシュｂが正当であると判断して処理を終了する。一方、判定がＮＯの場合、中継ノード２０は、符号化キャッシュｂが正当でないと判断し、処理はステップＳ１７に移る。
【００４５】
ステップＳ１７において、中継ノード２０は、汚染されて正当でないと判断した符号化キャッシュｂを破棄する。
【００４６】
以上のように、本実施形態によれば、認証システム１は、送信ノード１０において行列の乗算のみにより認証符ａｃ及び配布鍵ｋｉを出力できる。また、中継ノード２０において、ネットワーク符号化行列Ｂ及び符号化キャッシュに対して、行列の乗算を行うのみで比較検証が行える。
したがって、認証システム１は、認証に必要な全ての演算を基礎体上で行うことができる。さらに、認証システム１は、認証符ａｃを送信元データＣと同等、又は最小で１／ｎに小さくすることができる。このように、認証システム１は、効率的に符号化キャッシュｂの正当性を検証できる。
【００４７】
また、認証システム１は、ブランチ行列によって鍵行列Ａを変換し、その一部を中継ノードに提供するので、中継ノード２０からオリジナルの鍵行列Ａが漏洩することがない。さらに、本認証手法は、計算の複雑さに依存しない情報理論的な安全性を有する。
したがって、認証システム１は、高速性の求められるネットワーク符号化を用いたＩＣＮにおいて、信頼度の高いデータ伝送を実現できる。
【００４８】
また、送信ノード１０では、鍵行列Ａに対してブランチ行列の乗算方向が限定されず、この乗算方向に応じて配布鍵ｋｉが行ベクトル又は列ベクトルとなる。このため、認証のための計算手法の自由度が高い。なお、配布鍵ｋｉが行ベクトルの場合、第３乗算部２０１は、ブランチ行列Ｍのｉ行目を用い、配布鍵ｋｉが列ベクトルの場合、第３乗算部２０１は、ブランチ行列Ｍのｉ列目を用いる。
【００４９】
また、認証システム１は、送信元データＣの大きさ及び安全性の要件に基づいて、鍵行列Ａを適宜設定できる。さらに、ブランチ行列Ｍは、この鍵行列Ａ及び検証機能を有する中継ノード２０の数に基づいて、容易に大きさが設定される。
【００５０】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００５１】
本実施形態では、認証符生成方法及び検証方法における演算は基礎体上で行われたが、これには限られない。ネットワーク符号化において標準的な手法に則して、拡大体上で処理されてもよい。
【００５２】
また、本実施形態では、ＩＣＮにネットワーク符号化を適用した場合を説明したが、本発明は、種々のネットワークにおける、データセンタサービス又はクラウドサービス等に適用可能である。
【００５３】
送信ノード１０の認証符生成方法、及び中継ノード２０の検証方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【００５４】
１  認証システム
１０  送信ノード
２０  中継ノード
２１  キャッシュ
３０  受信ノード
１０１  第１乗算部
１０２  送信部
１０３  第２乗算部
１０４  公開部
２０１  第３乗算部
２０２  第４乗算部
２０３  比較部
【図１】
2015041880.tif 000004
【図２】
2015041880.tif 000005
【図３】
2015041880.tif 000006
【図４】
2015041880.tif 000007
【図５】
2015041880.tif 000008