(57)【要約】【課題】多量のアイテムが複数のエンティティを通過する際、各エンティティがアイテム群の構成を自由に変えながらも個々のアイテムが辿ったエンティティとその順序を検証可能にする効率的なパス検証手法を提供する。【解決手段】署名装置は、一以上の業者から納入されたアイテムと自らが更に発生させたアイテムとを組み合わせたアイテム群の選択を受けるアイテム選択入力部と、納入されたアイテムに対する署名情報に含まれた納入経路を検証するためにパス検証用情報を更新するパス検証用情報更新部と、選択されたアイテム群に対して、自らの作成した署名と更新されたパス検証用情報とからあらたな署名情報を作成する署名情報作成部を署名検証装置に送信する署名情報送信部とを備える。署名検証装置は、あらたな署名情報を受信する署名情報受信部とあらたな署名情報から選択されたアイテム群に含まれる全アイテムの納入経路を検証する署名情報検証部とを備える。【選択図】        図１
2007013745.tif 000002
【特許請求の範囲】
【請求項１】
製品または商品であるアイテムの納品経路を検証する多重署名システムであって、
アイテムの署名情報を生成する署名装置と、受領したアイテムの署名情報を検証する署名検証装置とが通信可能に接続され、
前記署名装置は、一以上の業者から納入されたアイテムと自らが更に発生させたアイテムとを組み合わせたアイテム群の選択を受けるアイテム選択入力部と、前記納入されたアイテムに対する署名情報に含まれた納入経路を検証するためにパス検証用情報を更新するパス検証用情報更新部と、前記選択されたアイテム群に対して、自らの作成した署名と、前記更新されたパス検証用情報とからあらたな署名情報を作成する署名情報作成部と、前記あらたな署名情報を前記署名検証装置に送信する署名情報送信部とを備え、
前記署名検証装置は、前記あらたな署名情報を受信する署名情報受信部と、前記あらたな署名情報から前記選択されたアイテム群に含まれる全アイテムの納入経路を検証する署名情報検証部とを備える多重署名システム。
【請求項２】
前記署名情報作成部は、
マークル・ツリー手法を用いて、アイテムを葉ノードとする二分木ツリー構造の各ノードに対してハッシュ値の連接を繰り返し、ルートノードのハッシュ値を計算することによって署名を作成する請求項１の多重署名システム。
【請求項３】
前記署名装置は、
前記あらたな署名情報とともに前記選択されたアイテム群に含まれるすべてのアイテムのＩＤを前記署名検証装置に送るアイテムＩＤ送信部を備える請求項１の多重署名システム。
【請求項４】
製品または商品であるアイテムの署名情報を生成する署名装置と、受領したアイテムの署名情報を検証する署名検証装置とが通信可能に接続されたシステムにて、アイテムの納品経路を検証する多重署名方法であって、
前記署名装置が、一以上の業者から納入されたアイテムと自らが更に発生させたアイテムとを組み合わせたアイテム群の選択を受けるステップと、
前記署名装置が、前記納入されたアイテムに対する署名情報に含まれた納入経路を検証するためにパス検証用情報を更新するステップと、
前記署名装置が、前記選択されたアイテム群に対して、自らの作成した署名と、前記更新されたパス検証用情報とからあらたな署名情報を作成するステップと、
前記署名装置が、前記あらたな署名情報を前記署名検証装置に送信するステップと、
前記署名検証装置が、前記あらたな署名情報を受信するステップと、
前記署名検証装置が、前記あらたな署名情報から前記選択されたアイテム群に含まれる全アイテムの納入経路を検証するステップと、
を備える多重署名方法。
【請求項５】
前記署名情報を作成するステップは、
マークル・ツリー手法を用いて、アイテムを葉ノードとする二分木ツリー構造の各ノードに対してハッシュ値の連接を繰り返し、ルートノードのハッシュ値を計算することによって署名を作成することを特徴とする請求項４の多重署名方法。
【請求項６】
前記署名装置があらたな署名情報を前記署名検証装置に送信する際に、
前記選択されたアイテム群に含まれるすべてのアイテムのＩＤを前記署名検証装置に送るステップを備える請求項４の多重署名方法。
【請求項７】
製品または商品であるアイテムの署名情報を生成する署名装置と、受領したアイテムの署名情報を検証する署名検証装置とが通信可能に接続されたシステムにて、アイテムの納品経路を検証する多重署名プログラムであって、
前記署名装置が、一以上の業者から納入されたアイテムと自らが更に発生させたアイテムとを組み合わせたアイテム群の選択を受ける機能と、
前記署名装置が、前記納入されたアイテムに対する署名情報に含まれた納入経路を検証するためにパス検証用情報を更新する機能と、
前記署名装置が、前記選択されたアイテム群に対して、自らの作成した署名と、前記更新されたパス検証用情報とからあらたな署名情報を作成する機能と、
前記署名装置が、前記あらたな署名情報を前記署名検証装置に送信する機能と、
前記署名検証装置が、前記あらたな署名情報を受信する機能と、
前記署名検証装置が、前記あらたな署名情報から前記選択されたアイテム群に含まれる全アイテムの納入経路を検証する機能と、
をコンピュータに実現させるためのプログラム。
【請求項８】
前記署名装置は、
マークル・ツリー手法を用いて、アイテムを葉ノードとする二分木ツリー構造の各ノードに対してハッシュ値の連接を繰り返し、ルートノードのハッシュ値を計算することによって署名を作成する機能をコンピュータに実現させる請求項７の多重署名プログラム。
【請求項９】
請求項７、または８のプログラムを格納したプログラム記憶媒体
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トレーサビリティ署名システム、署名方法、プログラムに関する。さらに詳しくは、多量のアイテムに対して署名を作成し、そのアイテムの流通経路を検証するためのシステム装置、方法、それらを実現するプログラムに関する。
【背景技術】
【０００２】
近年、自動車のリコール問題や、商品偽装問題といった、消費者に提供される商品等の信頼性の問題が疑問視されている。これに対して、製品や商品（以下「アイテム」と呼ぶ。）のトレーサビリティを確立することが主要なソリューションとして注目を浴びている。ここで、トレーサビリティとは「考慮の対象となっているものの履歴、適用又は所在を適用できること」と定義されている（ISO9000:2000年版）。トレーサビリティ技術によって、例えば、ある製品が誰によって生産され、どのような流通経路を辿ってきたのかといった情報を取得することができる。しかし、この情報を信頼関係のないドメイン間で利用することを考慮すると、取得した情報の正当性を保証する仕組みが必要となる。そこで、情報の正当性を保証する仕組みとして、署名手法が一般に用いられている。
【０００３】
このようなトレーサビリティにおける情報の正当性の保証という問題に取り組んだ例として特許文献１が知られている。この例では、商品流通の際に利用される出荷帳票と仕入帳票に電子署名を含ませ、商品流通の経路を検証可能にするというもので、具体的には各帳票にバーコードや２次元コードを用いた改ざん防止機能付きラベル書込装置などが記載されている。
【０００４】
しかしながら、トレーサビリティがターゲットとするエリアにおいては、多量のアイテムが流通することが一般的であるため、各アイテムに対して個別に署名を行ってしまうと、署名やその検証にかかる計算コスト、署名自体のデータ量が非常に大きくなることが想定される。また、最終的に商品を受け取ったエンティティ（以下、アイテムが流通する経路を構成する実体を「エンティティ」と呼ぶ。）が、その商品の流通経路全体を検証するには、そのアイテムに関わった全てのエンティティの正当性を証明する機関に対して問い合わせを行い、その際の出荷帳票に記された署名を検証する必要が生じてしまう。結果として、エンティティに対する問い合わせが増大するため、検証時の利便性が課題となっていた。
【特許文献１】特開２００４−９４５１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
アイテムが複数のエンティティを通過したことを検証する単純な方法としては、各アイテムのＩＤ（ここでは各アイテムには一意なＩＤがつけられているとする）それぞれに対して、各エンティティが署名をし、続くエンティティがその署名に対して多重に署名をすることが考えられる。しかしながら、一般的に署名の計算および署名の検証は計算コストが高く、流通するアイテム数が多い場合にはこの方法は現実的ではない。
【０００６】
そこで単純な効率化として、あるエンティティから次のエンティティへ複数のアイテムを送る際に、アイテムをひとまとまりのアイテム群とし、そのアイテム群に対して各エンティティが多重に署名を行うことが想定される。こうすると、各エンティティにおける署名の計算は、複数のアイテムに対して１つでよく、検証者の署名検証もアイテム群が経てきたエンティティ数の分だけでよい（ここでは流通するアイテムの数に比べ、経由するエンティティの数が十分小さいとする）。
【０００７】
例えば、I１，I２，I３というＩＤの付いた３つのアイテムがＡ、Ｂ、Ｃという３つのエンティティを経由する状況を考える。ＡはＢにアイテムを送る際に、I１，I２，I３全てをまとめてSigＡ（I１，I２，I３）のような署名を行う。ここで、SigＡ（Ｍ）は、エンティティＡによるメッセージＭに対する一般的な署名スキーマを用いて行われる署名を表すものとする。それを受け取ったＢは、SigＢ（SigＡ（I１，I２，I３））のような署名を行い、Ａの署名とアイテムと共にそれをＣに送る。Ｃは受け取ったアイテムI１，I２，I３からＡの署名を検証することができ、検証されたＡの署名からＢの署名を検証することができるため、これらのアイテムが通過してきたエンティティのパスを検証することができる。
【０００８】
しかしながら、この方法では、例えばＢがＡから渡されたアイテム群のなかからいくつかのアイテムを選択し、新たにアイテムを足してＣに送るといったような、アイテム群を構成するアイテムの組み合わせを変更することができない。例えば、ＢからＣへと渡すアイテムの構成をI２，I３，I４に変更したいとしても、I１が無ければそれを受け取ったＣ（検証者）はＡの署名を検証できない。
【０００９】
そこで本発明では、多量のアイテムが複数のエンティティを通過する際、各エンティティがアイテム群の構成を自由に変えながらも、個々のアイテムが辿ったエンティティおよびその順序を検証可能にする効率的なパス検証手法を提案することを目的とする。
【課題を解決するための手段】
【００１０】
本発明では、以下のシステム、方法、プログラムを提供する。
【００１１】
製品または商品であるアイテムの納品経路を検証する多重署名システムであって、アイテムの署名情報を生成する署名装置と、受領したアイテムの署名情報を検証する署名検証装置とが通信可能に接続され、前記署名装置は、一以上の業者から納入されたアイテムと自らが更に発生させたアイテムとを組み合わせたアイテム群の選択を受けるアイテム選択入力部と、納入されたアイテムに対する署名情報に含まれた納入経路を検証するためにパス検証用情報を更新するパス検証用情報更新部と、選択されたアイテム群に対して、自らの作成した署名と、更新されたパス検証用情報とからあらたな署名情報を作成する署名情報作成部を署名検証装置に送信する署名情報送信部とを備え、前記署名検証装置は、あらたな署名情報を受信する署名情報受信部と、あらたな署名情報から選択されたアイテム群に含まれる全アイテムの納入経路を検証する署名情報検証部とを備える多重署名システム。
【００１２】
上記署名装置が、一以上の業者から納入されたアイテムと自らが更に発生させたアイテムを組み合わせたアイテム群の選択を受けるステップと、納入されたアイテムに対する署名情報に含まれた納入経路を検証するためにパス検証用情報を更新するステップと、選択されたアイテム群に対して、自らの作成した署名と、更新されたパス検証用情報とからあらたな署名情報を作成するステップと、あらたな署名情報を署名検証装置に送信するステップと、上記署名検証装置が、あらたな署名情報を受信するステップと、あらたな署名情報から選択されたアイテム群に含まれる全アイテムの納入経路を検証するステップと、を備える多重署名方法。
【００１３】
上記機能をコンピュータに実行させるプログラムおよびプログラムを格納する記録媒体。
【発明の効果】
【００１４】
本発明によれば、各エンティティは、送り出すアイテムにまとめて署名しながらも、続くエンティティは受け取った署名の検証可能性を維持しながら、受け取ったアイテムの組み合わせを自由に変更して送り出すことが可能である。本発明を利用することにより、サプライチェーンのような多数のアイテムが流通する環境において、そのアイテムがどのエンティを通過してきたかを効率的に検証することが可能である。
【発明を実施するための最良の形態】
【００１５】
以下、発明の実施形態を通じて本発明を説明する。なお、以下の実施形態は特許請求の範囲にかかる発明を限定するものではない。また、実施形態の中で説明されている構成要素の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１６】
図１は、本発明の実施形態である多重署名システムの機能ブロックを示す。本システムは、署名を生成する署名装置１０と、生成された署名を検証する署名検証装置２０が通信路３０によって接続されることによって構成される。署名装置１０と署名検証装置２０は、ＰＣや情報端末などコンピュータ・システム上で実現されてよいし、専用の装置として実現されてもよい。図１では簡略化のため、署名装置１０と署名検証装置２０は、それぞれ１つ示しているが、アイテムの流通経路を構成するエンティティごとに少なくとも１つの署名装置１０が存在する。いっぽう、検証装置２０はそれぞれのエンティティに必ずしも存在する必要はなく、検証を必要とするエンティティに存在すればよい。１つのエンティティが他のエンティティからの署名を検証し、自らの署名を行って、さらに別のエンティティにその署名を送ることがあり得る。したがって、１つのエンティティに署名装置１０と署名検証装置２０とが存在してもよい。また、通信路３０は、インターネットのような一般通信網であっても専用回線であってもよい。あるいは、通信路３０は通信回線そのものでなく、情報をアイテムに添付することによって、データを送付、受領できる手段であってもよい。
【００１７】
署名装置１０は、出荷するアイテム群に対してディジタル署名を生成し、署名検証装置２０に送信する機能を持つ。ここでアイテム群とはあるエンティティからあるエンティティに送られるアイテムの組である。署名装置１０は、他のエンティティから納品されたアイテムの情報を納入品データ記憶部１２に保持している。また、署名装置１０は、自らのエンティティが生成したアイテムの情報を含む自社品データ記憶部１３と、これから出荷するアイテム群のデータを保持する出荷品データ記憶部１４と、装置全体を制御する制御部１１とを備える。ここで、自らのエンティティが生成したアイテムとは、自らが生産したアイテムがなくても、納入された複数のアイテムから新たなアイテム・セットを構成する（組みつける）場合を含む。
【００１８】
制御部１１は、アイテム選択入力部１５を介して、出荷するアイテム群を構成する各アイテムの選択を受ける。各アイテムの選択は、ユーザーによって入力されてもよいし、各アイテムと出荷先のエンティティを対応付けるテーブルなどによって行われてもよい。さらに、制御部１１は、出荷するアイテム群に対する署名情報を作成するためのパス検証用情報更新部１６と署名情報作成部１７を備える。また、制御部１１は、作成された署名情報を署名検証装置２０へ送信するための署名情報送信部１８を備える。ここで、署名情報には、納品されたアイテムの過去の経路履歴であるパス検証用情報と出荷品に対する自らの署名とが含まれている。また、制御部１１は出荷品の個々のアイテムＩＤを署名検証装置２０に送信するアイテムＩＤ送信部１９を備えてもよい。制御部１１の中核であるパス検証用情報更新部１６と署名情報作成部１７の機能の詳細は、後述するパス検証用情報更新アルゴリズムと署名アルゴリズムによって説明する。
【００１９】
署名検証装置２０は、制御部２１、出力部２５、表示部２７、および検証結果データ記憶部２６を備える。表示部２７と検証結果データ記憶部２６は必須の構成要素でなく、少なくとも一方を備えていればよい。制御部２１は、署名情報受信部２３を介して、署名装置１０からアイテム群に対する署名情報を受信する。署名情報検証部２４は、受信した署名情報を、その各アイテムＩＤを用いて検証する。各アイテムＩＤはアイテムに添付されるか、署名装置１０から受信される。署名検証装置２０は受信した署名情報を検証することによって、その全てのアイテムが経由したパスを追跡できる。署名情報検証部２４が有する署名検証機能の詳細は、後述する署名検証アルゴリズムによって説明する。検証された結果は、液晶ディスプレーなどの表示部２７に表示されてもよいし、検証結果データ記憶部２６に保持されてもよい。
【００２０】
以下、上記署名装置１０が用いる署名アルゴリズム、および、署名検証装置２０が用いる検証アルゴリズムについて詳しく説明する。まず前提として、必要な定義、基礎概念であるAuthentification  Tree（またはマークル・トリー）について説明し、その後、それぞれのアルゴリズムについて説明する。
【００２１】
＜定義＞
あるエンティティから渡されたアイテムのそれぞれが辿ってきたエンティティの経路を検証する者を検証者（Verifier）と呼ぶ。検証者にアイテムを渡すエンティティは１つで、これを署名者（Signer）と呼ぶ。署名者から検証者に渡されるアイテムは、署名者以前の０個以上のエンティティを経由してきたものである。また、アイテムが経由する各エンティティは、全て以下説明する同じ手法で署名を行うとする。
【００２２】
図２は、エンティティ間のアイテムの流れを例示したものである。この図では、各エンティティＡ〜Ｅ（２１０〜２５０）が自分の保持しているアイテムのうちいくつかを選択し、それを次のエンティティに送り、その結果、エンティティＦ（２６０）がいくつかのアイテムを保持し、そこから４つのアイテムを選択してエンティティＧ（２７０）に送ろうとしている様子をあらわしている。この例ではエンティティＦが署名者で、エンティティＧが検証者である。署名者から検証者へは、IA２，ID１，ID２，IF１というＩＤのついた４つのアイテム（２１６）が渡されているが、それぞれのアイテムは署名者以前の０個以上のエンティティを経ている。このとき、あるエンティティからあるエンティティへと送られるアイテムの組をアイテム群と呼ぶ。図２の例では、エンティティＦからエンティティＧへ送られるアイテム群は、｛IA２，ID１，ID２，IF１｝（２１６）であり、以後、これをItemSet(F,G)とあらわす。
【００２３】
また、図２のように、以後アイテムの経由するエンティティが、アイテムを渡したエンティティを子、受け取ったエンティティを親とするトリー構造を形成するものとする。そして、あるエンティティＥの子ノードに当たるエンティティの集合をChi(E)、Ｅの子以下のノードに当たるエンティティ全体の集合をDes(E)、Ｅの親ノードに当たるエンティティをPar(E)と表す。また、Ｈを一方向ハッシュ関数、‖を文字列の連接、SigＥをエンティティＥによる任意の署名スキーマを用いた署名とする。
【００２４】
＜Authentication  Tree＞
以下では、後述する署名アルゴリズムと検証アルゴリズムについて、基礎概念であるAuthentication  Tree（R.  Merkle.  A  digital  signature  based  on  a  conventional  encryption  function.  In  Proceedings  of  Crypto  ’87,  1987.)について説明する。
Authentication  Tree（またはマークル・ツリー）とは、署名対象となるデータをツリー構造の葉ノードとして扱い、それぞれの中間ノードは、その子ノードの値の連接のハッシュを値として取り、署名者はこのルートノードに署名を行う方法をいう。こうすることで、この署名の検証者がある複数のデータ（葉ノードに相当）に対する署名を検証する際に、署名対象となる他の全てのデータがそろっていなくても、ルートノードからそのデータが該当する葉ノードに至るパス上の全ノードの兄弟ノード（パス上のノード自身は除く）があれば、その署名を検証することができる。ここでは、Authentication  Treeを、最も単純な二分木(Binary  Tree)として議論する（データが２ｎ個でない場合、完全二分木を構成できないが、不足分のデータは０として補う）。
【００２５】
上記の例を図３に示す。この図では、Ｄ１〜Ｄ８が署名の対象となるデータを表しており、署名者はAuthentication  Treeのルートノード（Ｈｒｏｏｔ）に署名を行っている。今、検証者が得ているデータは｛Ｄ１,Ｄ２,Ｄ５｝（３０１）であるとする。このとき、署名を検証するためにデータ自体以外に必要な情報は、Ｄ１,Ｄ２,Ｄ５のそれぞれのノードからルートノードへのパス（図３中の太線３０３）上のノードの全ての兄弟ノードのうち、そのパス上に存在しないノードとなる（０となるノードは除く）。図３では、３０２で示されたノード｛Ｈ３４，Ｄ６，Ｈ７８｝がそれに当たる。これらのノードがあれば、他の全てのノードの値は検証者自ら計算できるため、ルートノードの値を計算して署名を検証することで、得られたデータ（図３の例ではＤ１,Ｄ２,Ｄ５）の正当性を検証することができる。
【００２６】
以下では、データの集合Ｄに対して、その全ての要素を葉ノードとするAuthentication  TreeをAT(D)、そのルートノードの値をATR(D)とする。また、Ｌ⊆Ｄに対して、AT(D)において、Ｌの（AT(D)の葉ノードになっている）それぞれの要素からATR(D)へのパス上のノードの全ての兄弟ノードのうち、そのパス上に存在しないノードの（値の）集合をATN(L/D)と表すことにする。図３の例では、D＝｛Dｉ｜ｉ＝１，．．，８｝とすれば、ATN({D１，D２，D５}／D)＝｛H３４，D６，H７８｝となる。
【００２７】
上記の定義、概念をもとに、本発明の実施形態における署名アルゴリズムとその検証アルゴリズムを説明し、その後それぞれに必要な計算量について説明する。
【００２８】
＜署名アルゴリズム＞
以下では署名者をＳ、検証者をＶとする。また、本発明の実施形態におけるＳの署名は、｛Ｖｓ，SigＳ｝の形を取る。ＶＳはＳ以前のパスを検証するために必要な情報（パス検証用情報と呼ぶ）で、Ｃ∈Chi(S)となる全てのＣによる署名情報｛ＶＣ，SigＣ｝を含んでいる。定義より、全てのエンティティＥ∈Des(S)は、本発明の実施形態における署名手法による署名を行うので、あるエンティティＥの署名に含まれるＶＥには、階層的に全てのＧ∈Des(E)の署名｛ＶＧ，SigＧ｝が含まれているとする。
【００２９】
（ステップ１）アイテム選択
Ｓは全てのＣ∈Chi(S)に対して、アイテムItemSet(C,S)から、いくつかのアイテムを選び、更にＳから発生するアイテムと組み合わせてItemSet(S,V)を構成する。図４にアイテム選択のフローチャートを示す。
【００３０】
（ステップ２）パス検証用情報更新
Ｓは全てのＥ∈Des(S)に対して、ＶＥを以下のように更新する（前述のように、全てのＶＥはＶＣに含まれている）。Ｓは(Par(E)=S)∧(ItemSet(E,S)∩ItemSet(S,V)＝Ф)となるようなＥのＶＥおよびSigＥを消去する。上記のエンティティをＸとしたとき、Des(X)に該当しない全てのエンティティＥ∈Des(S)に対して、D={H(I)|I∈ItemSet(E,Par(E))｝として、
【数１】
2007013745.tif 000003
を計算し、これを新しいＶＥとする。ただし、この（ステップ２）では、ＶＥに含まれている｛ＶＣｈｉ（Ｅ），SigＣｈｉ（Ｅ）｝は何も変更せずにそのまま保持する。このとき、ItemSet(E,Par(E))∩ItemSet(S,V)＝Фとなる場合は、ＶＥ＝H(SigＥ)とし、SigＥをVpar(E)から削除する。この計算に際して、ＳはItemSet(E,Par(E))を直接得ることはできないが、新しいＶＥ自体は古いＶＥに含まれたハッシュ値から計算することができる。ここで、ＶＥに含まれるSigＣｈｉ（Ｅ）またはＨ（SigＣｈｉ（Ｅ））以外の値は、AT(D)のノードのいずれかに合致する。従って、ここでどの値がどのノードに対応したものか分かるような情報（ノードの位置情報など）を付記する。また、全てのＩ∈ItemSet(E,Par(E))∩ItemSet(S,V)に対して、各Ｉのハッシュ値Ｈ（Ｉ）が、AT(D)のどのノード（必ず葉ノードになる）に対応するかという情報も同様に付記する。これらの方法に関してはここでは特定しないが、トリー構造をエンコードする手法が適用可能である。図５にステップ２のパス検証用情報更新のフローチャートを示す。ただし、図５では簡略化のため、ＳがＶに送るアイテムが存在すること、すなわち、ItemSet(S,V)≠Фとしている。
【００３１】
（ステップ３）署名作成
Ｓは全てのItemSet(C,S)∩ItemSet(S,V)≠Фとなるような全てのＣ∈Chi(S)の署名のハッシュ値Ｈ（SigＣ）を全て連接した値、‖Ｈ(SigＣ)と、Ｖに送ろうとしているアイテムの集合ItemSet(S,V)に対して、
【数２】
2007013745.tif 000004
の形の署名をする。これをSigＳとする。
【００３２】
（ステップ４）アイテムおよび署名の送信
ＳはＶＳ＝{ＶＣ，SigＣ}（ＣはＣ∈Chi(S)なる全てのエンティティ）とし、Ｖにアイテム群IＳ＝ItemSet(S,V)および署名情報{ＶＳ，SigＳ｝を送る。図６に上記署名作成ステップ３と送信ステップ４のフローチャートを示す。
【００３３】
＜検証アルゴリズム＞
ＳからアイテムItemSet(S,V)および署名情報｛ＶＳ，SigＳ｝を受け取ったＶは、全てのＥ∈Des(S)に対して、ＶＥに含まれる情報およびItemSet(S,V)に含まれるアイテムのＩＤからSigＥを検証することにより、全てのアイテムのパスを検証することができる。
【００３４】
（ステップ１）
SigＥが存在し、SigＣｈｉ（Ｅ）がＶＥに属さないようなエンティティＥに対して、ＶＥからSigＥを検証する。このとき、ＶＥには、D={H(I)|I∈ItemSet(E,Par(E))}とおいて、ATN({H(I)｜I∈ItemSet(E,Par(E))∩ItemSet(S,V)}/D)が含まれており、AT(D)を検証するために必要な他の情報{H(I)｜I∈ItemSet(E,Par(E))∩ItemSet(S,V)｝は、ItemSet(S,V)に含まれるアイテムのＩＤから計算できるため、これらの情報を元に、ATR(D)を計算し、SigＥを検証することができる。
（ステップ２）
ステップ１のＥがＥ≠Ｓであるとき、全てのＥに対してＰ＝Par(E)とし、ステップ１と同様にSigＰを検証する。Ｅ＝ＳであればＰ＝Ｅとして（ステップ３）へ。このとき、ＶＰにはSigＣｈｉ（Ｐ）が含まれている。D=｛H(I)|I∈ItemSet(P,Par(P))｝とし、ATR(D)‖(‖(H(SigＣｈｉ（Ｐ）))
を計算することで、SigＰを検証することができる。このステップを、Ｐ＝Par(P)として繰り返す。
（ステップ３）
ステップ２を繰り返し、Ｐ＝Ｓとなり、SigＳの検証に成功した場合、全てのアイテムのパスが検証されたことになる。図７に検証アルゴリズムのフローチャートを示す。
【００３５】
以下では、本発明の実施形態における署名の計算、署名の検証それぞれにかかる計算量およびメモリ効率について説明する。ここでは簡単のため、任意のエンティティＥの|ItemSet(E,Par(E))|が２のべき乗個であるとする。
【００３６】
＜ＡＴＮ、ＡＴＲの計算量＞
ここでは、本発明の実施形態におけるアルゴリズムに利用されるＡＴＮおよびＡＴＲの計算量について述べる。図８に示すように、いくつかのアイテム（８０１）を取り除き、それ以外のアイテム（８０２）を次のエンティティに送る場合には、送らないアイテムのハッシュ値から、ＡＴＮを図８中の８０４のノードについて計算する必要がある。以下では、Authentication  Treeの各ノードの値の計算（２値の連接に対するハッシュ計算）とアイテムのＩＤのハッシュ値の計算が同じ計算コストであるとし、全アイテム（８０１と８０２）のハッシュ値を葉ノードとするAuthentication  TreeをＡＴと呼ぶことにする。
【００３７】
ＡＴＮの計算は、取り除いたアイテムのＩＤ(８０１)のハッシュ値を葉ノードとし、ＡＴのサブツリーとなるように構成される複数のAuthentication  Tree（図８中の三角８０３で表され、ここではSub  Authentication  Treeと呼ぶ）のルートノード（８０４）の値を計算することに等しい。葉ノードに抜けのない完全なAuthentication  Treeのルートノードの値の計算には、葉ノードの数をｎとすると、ｎ−１回のハッシュ計算が必要となる。従って、各Sub  Authentication  Treeの葉ノードの数をｎｉ、Sub  Authentication  Treeの数をｔとすると、アイテムのＩＤのハッシュ値の計算も含めたＡＴＮの計算量（ハッシュ計算の回数）は、
【数３】
2007013745.tif 000005
となる。取り除くアイテムの総数をｎ’とすれば、ハッシュ計算の回数のオーダーはＯ（ｎ’）となる。
【００３８】
次にＡＴＲの計算量について述べる。本発明の実施形態では図９に示すように、送られたアイテム（８０２）と、ＡＴＮによって出力されたノード８０４）からＡＴＲの計算を行う（ＡＴＮの出力が無い場合も以下の議論は同じである）。アイテムのＩＤのハッシュ値の計算も含めたＡＴＲの計算量（ハッシュ計算の回数）は、全ての葉ノードがそろったAuthentication  Treeのハッシュ計算回数から、現状のAuthentication  Treeを作り出すのに必要なＡＴＮのハッシュ計算回数を引いたものとなる。従って、ＡＴＲの計算量は、全ての葉ノードがそろったAuthentication  Treeの葉ノードの数をｎとすると、
【数４】
2007013745.tif 000006
となる。取り除かれているアイテムの総数をｎ’とすれば、ハッシュ計算の回数のオーダーはＯ（ｎ−ｎ’）となる。
【００３９】
＜署名計算量＞
本発明の実施形態における署名アルゴリズムの計算量について述べる。署名アルゴリズム、ステップ１は次のエンティティに送るアイテムを選択するだけなので、計算量には含めないものとする。署名アルゴリズム（ステップ２）では、パス検証用情報の更新が行われる。ここで、次のエンティティに送られるアイテムに関連する（ItemSet(E,Par(E))∩ItemSet(S,V)≠Фとなる）エンティティの数をｍとすると、ステップ２の計算は主にＡＴＮの計算であるため、その計算量（ハッシュ計算の回数）は、以下のような式になる。
【数５】
2007013745.tif 000007
このとき、ｔｊはエンティティＥｊのパス検証用情報ＶＥｊに含まれ、ＶＣｈｉ（Ｅｊ）に含まれないハッシュ値の数（このハッシュ値をルートノードとするSub  Authentication  Treeの数に一致する）、ｎｊｉは、ＶＥｊに含まれる上記ハッシュ値をルートノードとするSub  Authentication  Treeのインデックスをｉとし、インデックスｉを持つSub  Authentication
Treeの葉ノードの数を表す。
【００４０】
署名アルゴリズム（ステップ３）では、次のエンティティに送るアイテムに対して構成した、葉ノードに欠落のないAuthentication  Treeのルートノードの計算（ＡＴＲ）、直前のエンティティの署名のハッシュ値の計算、それらに対する署名値の計算が行われる。従って、（ステップ３）では（２ｎ−１＋ｐ）回のハッシュ計算と１回の署名計算が行われる。ここでｎは次のエンティティに送るアイテムの数(｜ItemSet(S,V)｜)、ｐはＥ∈Chi(S)とし、ItemSet(E,S)∩ItemSet(S,V)≠Фとなるエンティティの数である。
【００４１】
上記から、本署名アルゴリズムの計算量はハッシュ計算の回数のオーダーがＯ（ｍｎ’＋ｎ）、署名計算の回数のオーダーはＯ（１）となる。ただし、ｎ’は全てのＥ∈Des(S)に対する
|ItemSet(E,Par(E))|-|ItemSet(S,V)∩ItemSet(E,Par(E))|
の平均とする。
【００４２】
全てのアイテムに個別に署名を行う場合、ｎ回の署名計算を行わなければならないが、本発明の実施形態の手法では１回でよい。通常、署名計算はハッシュ計算より非常に重い処理であるため、ｎが大きい場合、本発明の実施形態における手法はより効率的であると言うことができる。
【００４３】
＜検証計算量＞
署名計算アルゴリズムは、ＡＴＲの計算と署名の検証のための計算からなる。Ｅ∈Des(S)、ItemSet(E,Par(E))∩ItemSet(S,V)≠Фなる各Ｅ（今このようなエンティティの数はｍであるとする）ごとに、｜ItemSet(E,Par(E))｜＝ｎＥ、ＶＥに含まれたハッシュ値により構成されたSub  Authentication  Treeの数をｔＥ、その中のｉ番目のSub  Authentication  Treeの葉ノードの数をｎＥｉとすると、ハッシュ計算の回数は、以下のような式になる。
【数６】
2007013745.tif 000008
【００４４】
各エンティティが次のエンティティに送るアイテムの数
（ItemSet(E,Par(E))）の平均をｎａｖｇとすれば、ハッシュ計算の回数のオーダーはＯ(ｍ(ｎａｖｇ−ｎ’))となる。また、署名検証の計算回数はｍ回である。ただし、ｎ’は全てのＥ∈Des(S)に対する|ItemSet(E,Par(E))|-|ItemSet(S,V)∩ItemSet(E,Par(E))|の平均とする。全てのアイテムに個別の署名を行う場合、検証回数はｍ’ｎＳ回となる。ここで、ｍ’は、送られたアイテムが通過したエンティティの数の平均、ｎＳ＝|ItemSet(S,V)｜とする。本発明が対象とするトレーサビリティなどにおいては、
【数７】
2007013745.tif 000009
である。通常、署名検証の計算はハッシュ計算より非常に重い処理であり、ここではｍ＜＜ｎＳとなる場合（本発明の適用対象には当てはまる条件であると仮定している）、本発明の実施形態における手法は効率的であると言うことができる。
【００４５】
＜データ量＞
ここでは、あるエンティティが本発明の実施形態における署名を行いアイテムを送った際に、それがどの程度のデータ量になるかについて述べる。本発明の実施形態における署名には、アイテムが経由した各エンティティＥに対してパス検証用情報ＶＥと署名値SigＥが含まれる。ある署名者Ｓが次のエンティティにアイテムを送ろうとする際、エンティティＥをDes(S)の一つであるとすると、ItemSet(E,Par(E))-(ItemSet(E,Par(E))∩ItemSet(S,Par(S)))のアイテムによって形成されるSub  Authentication  Treeの個数分のハッシュ値がＶＥに含まれることになる。従って、その平均の個数をｔ、|Des(S)|＝ｍとすると、ｍｔ個のハッシュ値を保持していることになる。ｔは、ItemSet(E,Par(E))の内、送られなくなるアイテムの組み合わせに依存して変わってくるが、｜ItemSet(E,Par(E))｜の平均をｎとすれば、０≦ｔ≦ｎとなる。更に、本発明の実施の形態における署名に含まれるパス検証用の情報には、各ハッシュ値がAuthentication  Treeのどのノードに対応するかという情報も含まれなければならない。
【００４６】
また、SigＥは各エンティティに一つであるため、ｍ個の通常の署名手法による署名値が存在することになる。全てのアイテムに個別の署名を行う場合、|ItemSet(S,V)|=ｎＳとし、各アイテムが経由したエンティティの数の平均をｍ‘と置けば、署名値の数はｎＳｍ’個となる。本発明では、用いるハッシュ関数、署名スキーマについては規定していないため、これらの実際の効率は選択されたハッシュ関数や署名スキーマに依存する。
【００４７】
上記アルゴリズムを実際の例を用いて説明する。この例では、各アイテムが図１に示すようにエンティティ間を移動するものとし、それぞれのエンティティが署名者、その次のエンティティが検証者であるとして、署名・検証アルゴリズムが実際にどのように適用されるのかを見ていく。
【００４８】
図１０は、ＡがＤにアイテムを送る際の署名は以下のように行われることを示している。
（ステップ１）
まずエンティティＡは、アイテムIA１，IA２，IA３をエンティティＤに送るアイテムとして選択する（アイテム群ＩＡ）。
（ステップ２）
次に、Des(A)＝Фであるため、Ｅ∈Des(A)に対するＶＥの更新は行わない。
（ステップ３）
ＡはATR({Ｈ(ＩＡ１)、Ｈ(ＩＡ２)，Ｈ(ＩＡ３)})＝ＨＲＡとし、ＨＲＡに対して署名SigＡ（ＨＲＡ）を生成する。これをSigＡとする。
（ステップ４）
Ａは署名｛null，SigＡ｝、アイテム群｛IA１，IA２，IA３｝をＤに送る。
【００４９】
図１０において、網掛けで示した箱（１０１〜１０６）は次のエンティティに送られる情報を表している。白抜きで示した箱（１０７〜１０９）は署名の計算および検証には必要な情報であるが、１０１〜１０６の箱で示された情報のみから計算可能な値であり、次のエンティティには送られない情報を表している。ＢがＤにアイテムを送る際の署名も全く同様に行われ、Ｂは署名｛null，SigＢ｝、アイテム群ＩＢ＝｛IB１，IB２，IB３｝をＤに送る。ＣがＥにアイテムを送る際も同様に、Ｃは署名｛null，SigＣ｝、アイテム群ＩＣ＝｛IC１，IC２，IC３｝をＥに送る。
【００５０】
Ａ、Ｂからアイテムを受け取ったＤは、これらの署名を検証する。例えばＡの署名の検証は以下のように行われる。
（ステップ１）
ここで、SigＣｈｉ（Ｅ）がＶＥに属さないようなエンティティＥはＡのみとなる。ＶＡ＝nullであるが、{H(I)|I∈ItemSet(A,D)｝はＩＡから計算できる。そこからＨＲＡを計算することで署名を検証することができる。
（ステップ２）
今、Ａは署名者であるので、次のステップへ。
（ステップ３）
ここで、SigＡが正しく検証されたとすれば、Ｄはアイテム群ＩＡおよびＡの署名を受け入れる。Ｂ、Ｃの署名の検証も、それぞれＤ、Ｅにより同様に行われる。
【００５１】
続いて、Ａ、Ｂからアイテムを受け取ったＤが、Ｆにアイテムを送る際の署名および検証の例を見てみる。
（ステップ１）
図１１に示すように、Ｄは、Ｆに送るアイテムとして、｛IA２，IA３，IA３，ID１,ID２｝＝ＩＤを選んだ。
（ステップ２）
今、Des(D)＝｛Ａ，Ｂ｝である。よってＶＡ、ＶＢを更新する。
まず、ＶＡの更新のために、
【数８】
2007013745.tif 000010
を得、これをＶＡに含める。この時この値は、図１１に示すようなトリー構造のどのノードであるかわかるようにしておく（対応するノード位置を付加する）。
同様に、ＶＢに以下のＡＴＮを含める。
【数９】
2007013745.tif 000011
【００５２】
（ステップ３）
次に、ATR({H(I)|I∈ＩＤ}＝HRＤを計算し、
【数１０】
2007013745.tif 000012
を計算し、これをSigＤとする。
【００５３】
（ステップ４）
ＶＤ＝｛｛ＶＡ，SigＡ｝，｛ＶＢ，SigＢ｝｝とし、｛ＶＤ，SigＤ｝，ＩＤをＦに送る。Ｅによる署名も同様に行われ、
【数１１】
2007013745.tif 000013
として、署名｛ＶＥ，SigＥ｝、アイテム群ＩＥがＦに送られる。ここで、これらを受け取ったＦは署名を検証するが、ここではこの手順の説明は省略し、より複雑な例を、次のＦがＧにアイテムを渡した際の署名の検証で見ていくこととする。
【００５４】
続いて、図１２のように、ＦがＧにアイテムを送る例をみる。この際、Ｆは以下のように署名を行う。
（ステップ１）
Ｆは、受け取ったアイテムのうち、｛IA２，ID１，ID２｝を選択し、自ら元々保持していたアイテムＩＦ１を付け足してＩＦ＝｛IA２，ID１，ID２，IF２｝というアイテム群をＧに送るものとする。
（ステップ２）
ここで、Des(F)＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝となる。ここで、(Par(X)=F)∧(ItemSet(X,F)∩ItemSet(F,G)＝Ф)となるエンティティにはＥが該当する。従って、｛ＶＥ，SigＥ｝は無視する（ここでＶＥに含まれる｛ＶＣ，SigＣ｝も無視される）。残るエンティティ｛Ａ，Ｂ，Ｄ｝について、各エンティティをＸとしたとき以下を計算してＶＸを更新する。
【数１２】
2007013745.tif 000014
ただし、ItemSet(X,Par(X))∩ItemSet(F,G)＝Фとなるエンティティに対しては、VＸ＝H（SigＸ）とし、SigＸは捨てる。その結果、VＡ＝{H（IA１）,HA２}、ＶＢ＝｛H(SigＢ)｝、ＶＤ＝{{VＡ,SigＡ},{VＢ},H(IA３),H(IB３)}のように更新される。
【００５５】
（ステップ３）
ＦはATR(H(IA２)，H(ID１)，H(ID２)，H(IF１))＝HRＦを計算し、SigＦ(HRＦ‖H（SigＤ）)のかたちの署名をする。これをSigＦとする。
（ステップ４）
ＶＦ＝｛ＶＤ，SigＤ｝とし、｛ＶＦ，SigＦ｝、ＩＦをＧに送る。
【００５６】
これらを受け取ったＧは、各アイテムの経路を以下のように検証する。
（ステップ１）
SigＸが存在し、SigＣｈｉ（Ｘ）がＶＸに属さないようなエンティティは、Ａのみとなる。従ってまず、SigＡをＶＡから検証する。ＶＡには、Ｈ（IA１）、HA２が含まれており、ＩＦに含まれるIA２を用いれば、HRＡを計算することができるため、SigＡを検証することができる。
（ステップ２）
ステップ１のＸに対して、Par(X)となるエンティティは、Ｄのみとなる。そこで同様に、ＨＲＤを得、Ｈ（SigＡ）、Ｈ（SigＢ）からSigＤを検証する。
（ステップ３）
SigＦをＩＦからHRＦを計算することで検証し、この検証が成功した場合、IA２は、Ａ→Ｄ→Ｆ，ID１，ID２はＤ→Ｆ，IF１はＦを辿ってきたことが分かる。
【実施例】
【００５７】
これまで説明してきたように、本発明の実施形態による署名手法を用いることにより、あるエンティティからあるエンティティへ大量のアイテムが送られ、その中のいくつかのアイテムがまた別のエンティティへと渡されるような状況において、その個々のアイテムがどのエンティティを実際に通過したのかという情報の正当性を保証することができる。また、同時に各エンティティは（SigＥに用いる署名手法が保証する範囲で）その正当性に関する否認ができなくなる。
【００５８】
例えば、サプライチェーンの中で商品が様々な経路で流通していく過程で、各商品に対して本発明の実施形態による署名手法を適用することができる。これはこれまで説明してきたエンティティを各業者、商品をアイテムと置き換えることにより、各商品が署名に含まれるエンティティを確実に通ってきたことを示すことができる。
【００５９】
サプライチェーンにおいては、例えば、多数の商品が一つの箱に入れられ、それが何箱という単位で流通する状況は一般的である。ある一まとまりの商品を受け取った業者が、それらの一部を（例えば最初の１０箱といった具合に）一まとまりとして取り扱い、それを更に次の業者に送ることも一般的な状況と推察される。本発明の実施形態による署名手法は、流通過程においてAuthentication  Treeの葉ノードに対応するアイテムがまとまって抜け落ちるほど効率的になる。従って、本発明の実施形態は上記のようにアイテムがまとまって抜け落ちる状況が発生しやすいサプライチェーンに適していると言うことができる。一方、仮にまとまりが崩れたとしても署名の検証可能性を損なうことは無く、柔軟な組み合わせにも対応することができる。
【００６０】
本発明の実施形態は、自動車工場のような部品を組みつけていく過程を含むような流通過程に対しても適用することができる。この様子を図１３に示す。図１３中のＡ（１３１）やＢ（１３２）のような部品のサプライヤーが、Ｃ（１３３）のような組みつけを行うエンティティに部品を提供し、Ｃではそれらの部品を組み付けてＩＣ１（１３４）として出荷する。このようなケースであっても、それぞれのアイテムが独立したものであると見なし本発明の実施形態をそのまま適用することで、組みつけ後のアイテムに対して、それがどのようなエンティティから供給されたアイテムを用いて構成されているものかと言うことを後に検証することができる。
【００６１】
またこの例のように、組みつけられて送られるものは、その後あるアイテムが送られない（違うエンティティに送られる）場合には、そのアイテムに含まれる全てのアイテムも送られないこととなる。一般に、仕入れた部材を組みつけに使用する際に、ほとんどの部材はシーケンシャルに消費されることが想定される（わざわざ仕入れた同種の部材の順序を入れ替えて使用することは想像し難い）。従ってそのような状況下では、多くの部品が組みつけられた部品（あるいは製品）が抜け落ちることで、Authentication  Treeの葉ノードがまとまって抜け落ちることになり、本発明の実施形態による署名が効率化されやすくなる。
【００６２】
また、上記例のようなアイテムの流通過程以外にも、各アイテムが必ず通過しなければならない複数のプロセス（例えば何らかの検査プロセスなど）が存在し、それを通過したかどうかを検証するような用途にも利用することができる。
【００６３】
上記説明した実施形態は、コンピュータ・システム上で実行されるプログラムにより実現可能である。上記プログラムは記録媒体に格納されて提供され得る。記録媒体としては、フロッピー（登録商標）ディスクなどの磁気記録媒体、ＣＤ−ＲＯＭ、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、上記プログラムはネットワークに接続されたサーバシステム内に設けたハードディスクまたはＲＡＭ等の記憶装置を媒介として、コンピュータ・システムに提供されてもよい。
【００６４】
以上、本発明を、実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に限定されない。上記実施形態に、多様な変更または改良を加えることができる。そのような変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００６５】
【図１】署名システムの実施形態の機能ブロック図である。
【図２】エンティティ間のアイテムの流れの例示図である。
【図３】２分木Authentication  Tree概念図である。
【図４】アイテム選択ステップのフローチヤート図である。
【図５】パス検証用情報更新ステップのフローチャート図である。
【図６】署名作成・送信ステップのフローチャート図である。
【図７】署名検証ステップのフローチャート図である。
【図８】ＡＴＮの計算量についてのサンプル図である。
【図９】ＡＴＲの計算量についてのサンプル図である。
【図１０】署名および検証例（１）を示す図である。
【図１１】署名および検証例（２）を示す図である。
【図１２】署名および検証例（３）を示す図である。
【図１３】実施例の概念図である。
【符号の説明】
【００６６】
１０    署名装置
１１    制御部
１２    納入品データ記憶部
１３    自社品データ記憶部
１４    出荷品データ記憶部
１５    アイテム選択入力部
１６    パス検証用情報更新部
１７    署名情報作成部
１８    署名情報送信部
１９    アイテムＩＤ送信部
２０    署名検証装置
２４    署名情報検証部
２５    表示部
２６    検証結果データ記憶部
３０    通信路
【図１】
2007013745.tif 000015
【図２】
2007013745.tif 000016
【図３】
2007013745.tif 000017
【図４】
2007013745.tif 000018
【図５】
2007013745.tif 000019
【図６】
2007013745.tif 000020
【図７】
2007013745.tif 000021
【図８】
2007013745.tif 000022
【図９】
2007013745.tif 000023
【図１０】
2007013745.tif 000024
【図１１】
2007013745.tif 000025
【図１２】
2007013745.tif 000026
【図１３】
2007013745.tif 000027