(57)【特許請求の範囲】
【請求項１】
認証（authentication）のために第１のデジタルドキュメントを登録する方法であって、
a.第１のデジタルドキュメントを登録するための第１のリクエストを、著者装置からサービス部位置にあるサービス部装置にネットワークで送信し、前記第１のリクエストは、第１のデジタルドキュメントの表示（representation）を含み、
b.前記サービス部装置において、前記第１のデジタルドキュメントを登録するための第１のリクエストを受け取り、
c.前記サービス部装置において、他のデジタルドキュメントを登録するための複数の他のリクエストを受け取り、これらの各リクエストは、当該複数の他のデジタルドキュメントの１つの表示を含み、
d.前記サービス部装置が、ソフトウエアにより、前記第１のリクエストを、前記複数の他のリクエストのうちの少なくとも１つと結合して、第１の値を形成し、
e.前記サービス部装置が、ソフトウエアにより、前記第１の値をハッシュして第１のハッシュ値を生成し、
f.前記サービス部装置が、ソフトウエアにより、前記第１のハッシュ値を含む複数のハッシュ値の保管庫（repository）を形成し、この保管庫は、前記第１のリクエストおよび複数の他のリクエストに応じたものであり、
g.前記サービス部装置が、ソフトウエアにより、前記保管庫内にある項目（item）にネットワークアクセスして前記項目を公開することにより、前記保管庫を保証し（securing）、前記項目は、少なくとも部分的にリクエストにより決定され、
h.前記サービス部装置が、ソフトウエアにより、前記第１のデジタルドキュメントのために、前記保管庫内のロケーションポインタを生成し、
i.前記サービス部装置が、ソフトウエアにより、前記ロケーションポインタを用いることにより、前記デジタルドキュメントに対して、自己検証する名前（self−verifying name）を与えること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記結合は、連結（concatenating）を含むこと
を特徴とするデジタルドキュメントを登録する方法。
【請求項３】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記ロケーションポインタを生成するステップは、さらに、前記第１のドキュメントの自己検証ハッシュ値（self−verifying hash values）および当該自己検証ハッシュ値の関連するロケーション値のリストを決定すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項４】
請求項３記載のデジタルドキュメントを登録する方法であって、
前記自己検証する名前を与えるステップは、さらに、前記公開された項目の識別子および前記ロケーション値によって、前記第１のドキュメントを名付け、前記第１のドキュメントに対して自己検証する名前を与えること
を特徴とするデジタルドキュメントを登録する方法。
【請求項５】
請求項３記載のデジタルドキュメントを登録する方法であって、
前記自己検証する名前を与えるステップは、さらに、前記関連するロケーション値と前記公開された項目の識別子との組み合わせに対して、圧縮符号化アルゴリズムを適用し、前記第１のドキュメントに対して簡略化された英数字の名前を与えること
を特徴とするデジタルドキュメントを登録する方法。
【請求項６】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記保管庫は木（tree）であり、
前記項目を公開するステップは、当該木のルートを公開すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項７】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記公開された項目は、その項目が算出された日または時刻の表示を含む識別子を有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項８】
請求項１記載のデジタルドキュメントを登録する方法であって、
ローカルエンティティに位置するローカルエンティティ装置も、前記ステップ（ｂ）および（ｃ）を実行することにより、保証されるべきローカル項目をもつローカル保管庫を形成し、その後に、前記ローカルエンティティ装置が、前記ローカル項目を含む第１のリクエストを、前記ステップ（ｂ）から（ｉ）を実行するサービス部装置に送ること
を特徴とするデジタルドキュメントを登録する方法。
【請求項９】
請求項８記載のデジタルドキュメントを登録する方法であって、
前記ステップ（ｃ）、（ｄ）、（ｅ）は前記サービス部装置により実行され、さらに、前記ローカル項目を他のハッシュ値と結合するステップを有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１０】
請求項８記載のデジタルドキュメントを登録する方法であって、
前記ローカル保管庫内に、複数の関連するドキュメントの内容のテーブルのハッシュ値を含めるステップをさらに有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１１】
請求項８記載のデジタルドキュメントを登録する方法であって、
前記ローカル保管庫内に、複数部分（multi−part）ドキュメントの複数の部分に対応する複数の項目を含めるステップをさらに有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１２】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記自己検証する名前を与えるステップは、リクエスト装置が前記第１のドキュメントを保証する（certifying）のための前記自己検証する名前の第１の部分をが与えるステップをさらに有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１３】
請求項12記載のデジタルドキュメントを登録する方法であって、
前記自己検証する名前の第１の部分を与えるステップは、さらに、前記第１のドキュメントに関連した情報を与えること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１４】
請求項12記載のデジタルドキュメントを登録する方法であって、
前記自己検証する名前の第１の部分は、前記第１のドキュメントの保証するために、前記リクエスト装置の位置についての情報を与えること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１５】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記保管庫は二分木（binary tree）であること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１６】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記保管庫は、リンクリスト（linked list）であること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１７】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記保管庫は、成長する有向非環状グラフ（growing directed acyclic graph）であること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１８】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記結合するステップは、さらに、頻繁に算出される木（tree）の複数のルートを結合することにより、比較的頻繁には算出されない木を生成するステップを含み、これらの木のルートは、リニアリンクリスト（linear linked list）に組み入れられること
を特徴とするデジタルドキュメントを登録する方法。
【請求項１９】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記自己検証する名前を含む前記第１のデジタルドキュメントための証明書を、前記サービス部装置が生成するステップをさらに有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２０】
請求項19記載のデジタルドキュメントを登録する方法であって、
前記証明書を生成するステップは、さらに、前記証明書に、自己検証ハッシュ値のリストを含めるステップを有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２１】
請求項19記載のデジタルドキュメントを登録する方法であって、
前記証明書を生成するステップは、実質的に、前記保管庫の項目が公開される時点より前に行われること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２２】
請求項19記載のデジタルドキュメントを登録する方法であって、
前記証明書が記憶設備に送られ、そして、前記自己検証する名前が前記著者装置に送られるステップをさらに有すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２３】
請求項19記載のデジタルドキュメントを登録する方法であって、
前記サービス部装置が前記証明書を著者装置へ送信すること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２４】
請求項１記載のデジタルドキュメントを登録する方法であって、
前記リクエストを受け取るステップは、さらに、複数の著者装置からのリクエストを受け取ること
を特徴とするデジタルドキュメントを登録する方法。
【請求項２５】
第１のデジタルドキュメントを、先に登録された第２のデジタルドキュメントの真正なコピーであることを意味するものと確証する（validating）、デジタルドキュメントを確認する方法であって、
第２のデジタルドキュメントは、自己検証する名前（self−verifying name）、自己検証ハッシュ値（self−verifying hash values）を含む前記第２のデジタルドキュメントのための証明書であって、前記自己検証ハッシュ値のためのロケーション値と関連する証明書を生成することにより登録されており、
前記自己検証する名前は、前記ロケーション値と保証ハッシュ値（secure hash value）の識別子との組み合わせからなり、
前記デジタルドキュメントを確認する方法は、ネットワーク装置が、ソフトウエアにより実行するステップ（ａ）〜（ｄ）であって、
（ａ）前記第２のデジタルドキュメントのハッシュ値によって、少なくとも部分的に決定される前記保証ハッシュ値を与え、
（ｂ）前記第１のデジタルドキュメントをハッシュして、第１のデジタルドキュメントハッシュ値を与え、
（ｃ）前記第１のデジタルドキュメントハッシュ値を、前記ロケーション値に従って、前記自己検証ハッシュ値と共にハッシュして結合し、
（ｄ）ステップ（ｃ）での結果得られたハッシュ値が、前記保証ハッシュ値と対応する（correspond）か否かを決定すること
を特徴とするデジタルドキュメントを確認する方法。
【請求項２６】
請求項25記載のデジタルドキュメントを確認する方法であって、
前記結合は、連結を含むこと
を特徴とするデジタルドキュメントを確認する方法。
【請求項２７】
請求項25記載のデジタルドキュメントを確認する方法であって、
前記保証ハッシュ値を与えるステップは、（１）直接的に項目を公開すること、または、（２）直接的に公開された他の項目に項目をリンクすることを含み、前記公開は、前記項目へのネットワークアクセスを可能にするネットワーク装置がソフトウエアにより行うこと
を特徴とするデジタルドキュメントを確認する方法。
【請求項２８】
請求項27記載のデジタルドキュメントを確認する方法であって、
前記公開されたハッシュ値は、前記第２のドキュメントが登録された後のある時点で公開されること
を特徴とするデジタルドキュメントを確認する方法。
【請求項２９】
請求項25記載のデジタルドキュメントを確認する方法であって、
前記保証ハッシュ値を、直接的に公開された他のハッシュ値にリンクする（linking）ステップをさらに有すること
を特徴とするデジタルドキュメントを確認する方法。
【請求項３０】
デジタルドキュメントを名付ける方法であって、
a.第１のデジタルドキュメントの命名のための第１のリクエストを、著者位置にある著者装置からサービス部位置にあるサービス部装置にネットワーク経由で送信し、前記第１のリクエストは、前記第１のデジタルドキュメントの表示（representation）を含み、
b.前記サービス部装置において、前記第１のリクエストを受け取り、
c.前記サービス部装置において、デジタルドキュメントの命名のための複数の他のリクエストを受け取り、これらの各リクエストは、複数の他のデジタルドキュメントの１つの表示を含み、
d.前記サービス部装置が、ソフトウエアにより、前記第１のリクエストを、前記複数の他のリクエストのうちの少なくとも１つと結合して、第１の値を形成し、
e.前記サービス部装置が、ソフトウエアにより、前記第１の値をハッシュして第１のハッシュ値を生成し、
f.前記サービス部装置が、ソフトウエアにより、前記第１のハッシュ値を含む複数のハッシュ値の保管庫（repository）を形成し、この保管庫は、複数のノードを有する有向非環状グラフ（directed acyclic graph）の形式であり、各ノードは、前記リクエストの少なくとも１つに依存したハッシュ値を有し、前記保管庫は、また、前記複数のリクエストに依存したハッシュ値を有する保証された項目を有し、
g.前記サービス部装置が、ソフトウエアにより、前記第１のデジタルドキュメントに対する前記保管庫内のロケーションポインタを生成し、
h.前記サービス部装置が、ソフトウエアにより、前記ロケーションポインタを用いて前記第１のデジタルドキュメントを名付けることにより、自己検証する名前（self−verifying name）を前記第１のデジタルドキュメントに与えること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３１】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記結合は、連結を含むこと
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３２】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記保管庫のある項目を公開することにより前記保管庫を保証するステップをさらに有し、前記項目は、少なくとも１つのリクエストにより少なくとも部分的に決定され、前記公開は、前記項目へのネットワークアクセスを可能にする前記サービス部装置がソフトウエアにより行うこと
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３３】
請求項32記載のデジタルドキュメントを名付ける方法であって、
前記ロケーションポインタを生成するステップは、前記第１のドキュメントのための自己検証ハッシュ値（self−verifying hash values）のリストを決定し、前記リストは、前記自己検証ハッシュ値のためのロケーション値と関連すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３４】
請求項33記載のデジタルドキュメントを名付ける方法であって、
前記名付けるステップは、前記公開された項目の識別子により、および、前記第１のドキュメントに名前を与えるための前記ロケーション値により、前記第１のドキュメントを名付けること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３５】
請求項34記載のデジタルドキュメントを名付ける方法であって、
前記第１のドキュメントを名付けるステップは、さらに、前記関連するロケーション値と前記公開された項目の識別子との組み合わせに対して圧縮符号アルゴリズムを適用することにより、前記第１のドキュメントに、簡単化した英数字の名前を与えること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３６】
請求項32記載のデジタルドキュメントを名付ける方法であって、
前記公開された項目は、その項目が算出された日または時刻の表示を含む識別子を有すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３７】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記保管庫は、木（tree）であり、
前記保証された項目は、前記木のルートであること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３８】
請求項30記載のデジタルドキュメントを名付ける方法であって、
ローカルエンティティ位置にあるローカルエンティティ装置も、前記ステップ（ｂ）から（ｆ）を実行することにより、保証されるべきローカル項目をもつローカル保管庫を形成し、その後、前記ローカルエンティティ装置が、前記ローカル項目を含む第２のリクエストを、前記ステップ（ｂ）から（ｈ）を実行する前記サービス部装置に送ること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項３９】
請求項38記載のデジタルドキュメントの名付ける方法であって、
前記ステップ（ｃ）から（ｆ）は、前記サービス部装置がソフトウエアにより実行し、さらに、前記サービス部装置がソフトウエアにより、前記ローカル項目を他のハッシュ値と結合すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４０】
請求項38記載のデジタルドキュメントを名付ける方法であって、
前記ローカル保管庫内に、複数の関連するドキュメントの内容のテーブルのハッシュ値を含めるステップを、さらに有すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４１】
請求項38記載のデジタルドキュメントを名付ける方法であって、
前記ローカル保管庫内に、複数の関連するドキュメントに対応する複数の項目を、名付けられた前記複数のドキュメント間の関係の論理的構造に対応する前記名前の第１の部分を与えるように符号化されたロケーション値と共に、含めるステップをさらに有すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４２】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記名付けるステップは、前記第１のドキュメントを名付けるために、前記名前の第１の部分を、リクエスト装置に与えるステップを有すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４３】
請求項42記載のデジタルドキュメントを名付ける方法であって、
前記与えるステップは、さらに、前記第１のドキュメントに関連した情報を提供するために、前記名前の第１の部分を与えること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４４】
請求項42記載のデジタルドキュメントを名付ける方法であって、
前記名前の第１の部分は、前記第１のドキュメントの命名のために著者位置についての情報を提供すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４５】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記保管庫は、二分木（binary tree）であること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４６】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記保管庫は、リンクリスト（linked list）であること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４７】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記結合するステップは、さらに、頻繁に算出される木（tree）の複数のルートを結合することにより、比較的頻繁には算出されない木を生成するステップを含み、これらの木のルートは、リニアリンクリスト（linearlinked list）に組み入れられること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４８】
請求項30記載のデジタルドキュメントを名付ける方法であって、
さらに、前記著者装置へ前記名前を送信するステップを有し、前記ステップ（ｈ）は、前記保管庫の１項目が公開させられる時点より実質的に前に行われること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項４９】
請求項30記載のデジタルドキュメントを名付ける方法であって、
さらに、前記サービス部装置が、ソフトウエアにより、前記自己検証する名前を含む前記第１のデジタルドキュメントの証明書を生成するステップを有すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項５０】
請求項30記載のデジタルドキュメントを名付ける方法であって、
さらに、前記証明書を著者装置に送信するステップを有すること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項５１】
請求項30記載のデジタルドキュメントを名付ける方法であって、
前記リクエストを受け取るステップは、さらに、複数の著者装置からのリクエストを受け取ること
を特徴とするデジタルドキュメントを名付ける方法。
【請求項５２】
デジタルドキュメントにタイムスタンプを施す方法であって、
ネットワーク装置が、ソフトウエアにより、
a.第１のデジタルドキュメントのタイムスタンプのリクエストを用意し、このリクエストは、第１のデジタルドキュメントのハッシュ値を含み、
b.前記第１のリクエストを、第２のハッシュ値と結合することにより複合デジタル値を生成し、前記第２のハッシュ値は、少なくとも部分的に第２のデジタルドキュメントに依存したものであり、
c.前記複合デジタル値をハッシュすることにより、第１の複合ハッシュ値を生成し、
d.前記第１の複合ハッシュ値を含むハッシュされたデジタル値の保管庫（repository）を形成し、前記保管庫は、複数のノードを有する有向非環状グラフ（directed acyclic graph）であり、各ノードは、少なくとも１つの受け取ったリクエストに依存するハッシュ値を有し、前記保管庫は、また、受け取ったリクエストの少なくとも１つに少なくとも部分的に依存したハッシュ値を含む保証された項目（item）を有し、
e.前記第１のデジタルドキュメントに対して、ユニークな自己検証する名前（self−verifying name）を、
i.前記保管庫内のある項目をネットワーク経由で入手可能にすることにより保証し、
ii.この保証された項目に対して識別子を生成し、
iii.この識別子と、前記保証された項目について前記第１のデジタルドキュメントのロケーションに関連したロケーション値とを用いて、与えること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５３】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記第１のリクエストを前記第２のハッシュ値と結合するステップの前に、タイムスタンプを施すべき第２のリクエストの１部として、前記第２のデジタルドキュメントを受け取ること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５４】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記結合は前記第１のリクエストと前記第２のハッシュ値との連結を含むことを特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５５】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記保管庫を形成するステップは、さらに、
a.複数のリクエストを受け取り、これらの各リクエストはデジタルドキュメントの表示（representation）を含み、そして、前記保管庫のノードを形成し、
b.少なくとも２つのリクエストを一緒に結合することにより、第２の複合デジタル値を形成し、
c.この第２の複合デジタル値をハッシュし、そして、
d.前記保管庫内に保証された項目が形成されるまで、前記結合および前記複合デジタル値のハッシュを継続すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５６】
請求項55記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記受け取るステップは、さらに、ネットワークに接続された複数のリクエスト装置からのリクエストを受け取ること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５７】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記第２のデジタルドキュメントは予め存在するハッシュ値であり、前記保管庫を形成するステップは、さらに
a.前記第１の複合ハッシュ値を第２のリクエストと結合することにより、第２の複合デジタル値を生成し、
b.この第２の複合デジタル値をハッシュすることにより、第２の複合ハッシュ値を生成し、
c.この第２の複合ハッシュ値を第３のリクエストに結合することにより、第３の複合デジタル値を生成し、
d.この第３の複合デジタル値をハッシュすることにより、第３の複合ハッシュ値を生成し、
e.前記リクエストと前記複合ハッシュ値の結合を継続することにより、結果として得られる複合デジタル値を生成するとともに、この結果として得られる複合デジタル値をハッシュすること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５８】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、
さらに、前記保管庫を形成するステップの後に、
a.前記保管庫内の１つの項目を、前記保証された項目であると決定し、
b.この項目を保証すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項５９】
請求項58記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記保証するステップは、さらに、少なくとも部分的に１つのリクエストに基づくハッシュ値を有する項目を公開すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６０】
請求項59記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記保証するステップは、さらに、前記選択された項目がリンクされる第２の項目を公開すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６１】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記保管庫を形成するステップの後に、さらに、証明書を生成すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６２】
請求項61記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記証明書を生成するステップは、さらに、前記第１のデジタルドキュメントを認証するハッシュ値を算出するステップを有すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６３】
請求項62記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記証明書を生成するステップは、さらに、前記第１のデジタル証明書を認証するハッシュ値のロケーション値を算出するステップを有すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６４】
請求項61記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記証明書は、前記保証された項目へのポインタを有すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６５】
請求項64記載のデジタルドキュメントにタイムスタンプを施す方法であって、
前記ポインタは、前記保証された項目が保証された時点の情報を有することを特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６６】
請求項52記載のデジタルドキュメントにタイムスタンプを施す方法であって、さらに、
a.リクエスト装置で前記リクエストを生成し、
b.この生成するステップの後、前記リクエスト装置が前記リクエストをネットワーク装置へ送信し、
c.前記結合するステップの前に、前記ネットワーク装置が前記リクエストを受け取り、
d.前記ネットワーク装置が、ソフトウエアにより、前記結合するステップ、前記ハッシュするステップ、および前記保管庫を形成するステップを実行すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６７】
請求項66記載のデジタルドキュメントにタイムスタンプを施す方法であって、さらに、
a.前記ネットワーク装置が、ソフトウエアにより、証明書を生成し、そして、
b.前記ネットワーク装置が、ソフトウエアにより、前記リクエスト装置へ前記証明書を送信すること
を特徴とするデジタルドキュメントにタイムスタンプを施す方法。
【請求項６８】
複数のデジタルドキュメントを処理する方法であって、
前記ネットワーク装置が、ソフトウエアンにより、電子的に、複数のノードを有する有向非環状グラフ（directed acyclic graph）の形式を持つ、ハッシュされたデジタル値の保管庫（repository）を生成し、ここで、各ノードは前記デジタルドキュメントの少なくとも１つに依存したハッシュ値を有し、また、前記保管庫は２つ以上の前記デジタルドキュメントから得られたハッシュ値を含む保証された値を有し、そして、複数のデジタルドキュメントの１つに対して前記保管庫内にロケーションポインタを生成し、前記ロケーションポインタを用いて前記１つのデジタルドキュメントを名付けることにより、前記１つのデジタルドキュメントに自己検証する名前（self−verifying name）を与えること
を特徴とする複数のデジタルドキュメントを処理する方法。
【発明の詳細な説明】
発明の背景
本発明は、ドキュメントをユニークに特定し認証する証明書を発行するデジタルドキュメント証明システムに関するものである。より具体的には、本発明は、認証証明書によって、ユニークでユーザーフレンドリーな暗号化された安全な名前をデジタルドキュメントに与えるタイムスタンプシステムに関するものである。
さまざまな状況において、ドキュメントが作成された日時を確立し、当該ドキュメントが作成後に改ざんされてないことを立証する必要が生じる。このような課題は、デジタルドキュメントにおいて、これらが極めて変更が容易であるために特に重要となる。デジタルドキュメントは、一般的に、過去の履歴を特定できない、変更容易なメディア上にデジタル形式で記録されているからである。しかし、一旦記録されると、デジタルドキュメントの完全なコピーが容易である。あまりに簡単で、ほとんどの場合、コンピュータベースのドキュメントの”オリジナルコピー”という言葉には意味がない。どのようなコピーも、メジャーな方法もしくはマイナーな方法で簡単に変更することができる。対照的に、無傷の紙のドキュメントは、より高い保証を与えてくれる。たとえば、どのようなものであれ紙のドキュメントに変更を行えば、それが小さな変更でも、物理的な法延証拠（forensic evidence）を残すことになる。
近年、いくつかのデジタルタイムスタンプシステムが提案されている。たとえば、本参照によってその内容を、ここに組入れる米国特許No.5,136,647と5,136,646は、このようなシステムを記述している。5,136,646特許に記述されたシステムは、追加的にトランザクションナンバー、クライアントナンバー、日時、証明書ナンバーを含む認証証明書を提供する。ドキュメントの真正さを確かめるために、タイムスタンプ「当局（authority）」の記録が、当該証明書ナンバーとの関連で検査される。
改良されたシステムが、"Improving the Efficiency and Reliability of Digital Time−Stamping,"D.Bayer,S.Haber,W.S.Stornetta（in Seaquences II:Methods in Communication,Security,and Computer Science,ed.R.M.Capocelli,A.DeSantis and U.Vaccaro,pp329−334,Springer−Verlag New York,1993）に記載されている。二分木を利用したシステムを用いて、タイムスタンプされたドキュメントの真正さを確かめるために、この記事では、公開された木のルート（root）に向かうパスに沿って（そのハッシュ値の“つながり（handedness）”とともに、）、問題のドキュメントのハッシュ値と、直接結合されたハッシュ値の組を保持しておくことを提案している。もし、Ｎ個のドキュメントの全てについて「信頼できる」証明が成されたならば、この、システムは、"How to Time−stamp a Digital document,"S,Harber,W.S.Stornetta,Journal of cryptography,Vol.3,No.2,pp99−111（1991）に記載されているような、リニアリンキングに基づいたシステムにおいて、Ｎからlog Nへ検査のコストを低減することができる。
前述したデジタルタイムスタンプシステムは、ユーザに、任意のデジタルドキュメントを”登録”する手段を与えるものである。”ドキュメント”は、もちろん、どのようなビットのどのようなシーケンスでもあり得る。たとえば、記述されたドキュメントの単語を表すものや、印刷されたテキストや、記録された音や、デジタル化されたビデオなどを表すものであり得る。このようにドキュメントを登録した結果、ユーザはその登録の時刻、およびドキュメントの内容を保証するタイムスタンプ“証明書”を手にする。ユーザがデジタルドキュメントとタイムスタンプ証明書を受け取ったとき、ユーザは、受け取った証明書が本当に受け取ったドキュメントから主張されている通りの時刻に計算されたものか確かめることができる。そうでない場合には、その組（ドキュメントと証明書）は、検証もしくは認証テストを通らない。
しかしながら、前述したシステムが意図通りの機能を果たしたとしても、更なる改良が必ず必要となる。たとえば、ユーザのデジタルドキュメントのニーズを簡易にするシステムは、常に、好ましい。具体的には、２組の当事者（party）が、彼らが作成し、修正し、送信し、デジタル形式で記録する異なる複数のバージョンのドキュメントを用いて作業している状況を考える。この当事者（party）は、記事を共同執筆している作家や科学者かもしれないし、会計記録を調べてるアナリシストや会社検査役かもしれないし、契約を交渉している弁護士かもしれないし、集中的にデジタルドキュメントを操作したり作成することを仕事に含む他の人かもしれない。このような当事者（party）は、記録をとったり、お互いに連絡をとるために、使っているドキュメントに言及する、便利な方法を必要としている。好ましくは、ドキュメントの名前は、短く、言及しやすいのが良い。また、名前は、少なくともそのドキュメントが利用される状況下においてあいまいなものであってはいけない。これには、名前とドキュメントの完全性に、何かしらの関連をつけることを必要とする。さらに、（１）異なるドキュメントや同じドキュメントの異なるパートとの関連や構造を反映する、（２）そのドキュメントについて便利だと思う、他の情報を含める方法で、制作者がドキュメントを名付けることができる、充分な柔軟性をもつことは、名前付け（命名）の体系上便利である。
一般的に、命名の体系は、（１）何らかの任意の決め事に従って名前を選択する、（２）関数的に（functionally）ドキュメントに依存して名前を選択する。関数的な依存性は他方の当事者（party）で検証することのできるものである。任意な命名体系の例は、刊行物のInternational Standard Book Numbering（ISBN）方式である。”検証することのできる”（または、自己証明する）命名体系の例は、特定の一方向ハッシュ関数（後に詳述する）によって、各ドキュメントにそのハッシュ値を、割り当てるものである。
任意の命名体系は、その体系がどのように確立され施行されるかによって変化する。通常のメカニズムは、特定のロケーション（物理的、または、論理的）で成される選択を含む。たとえば、パーソナルコンピュータ上でワードプロセッシングプログラムを使用して生成された新たなファイルの名前の、ユーザーの選択は、一般的に任意でありローカルである。パーソナルコンピュータ上のユーザの名前の選択は、彼もしくは彼女の都合によってなされる。ローカルでない中央的な命名体系に依存する、ISBNや国会図書館の分類方式も、同様に任意性がある。名前の選択が任意に過ぎない場合には、名前の、その名前の対象との関連は、本来的に検証できない。いいかえるならば、特定のドキュメントが、特定の名前のドキュメントと同じものであるか、人が検証する方法がない。
デジタルドキュメントの名前が”検証することができる”ことを保証する方法の一つは、ビット列を引数（arguments）とする一定の数学的関数を用い、特定のドキュメントについて求めた関数値を、そのドキュメントの”名前”とすることである。利便性のために、関数は、計算が簡単なものであるべきである。名前をユニークなものにするために、関数は、また、１対１に計算されるものでなければならない。さらに、ドキュメントの名前は、少なくともドキュメント自身の長さよりも短くなければならないという要請のために、関数はその引数を圧縮するものでなければならない。そのため、通常、このような関数として、一方向ハッシュ関数が選ばれる。
一方向ハッシュ関数は、計算が簡単で、任意長のビット列を入力し、固定長のビット列（”ハッシュ値”）を出力する。この関数は、次の条件を満たす。（１）同じハッシュ値出力を生成する二つの異なる入力を見つけることができない。（２）入力と、そのハッシュ値出力を与えられたときに、同じハッシュ値出力を伴う異なる入力を見つけることができない。これらの条件の結果、ハッシュ値からファイルのどのような情報も復元できない。
このような計算処理の実行不可能性は、このような関数を攻撃する数学的（アルゴリズム的）知識と、現在のコンピュータで用いることのできる計算スピードおよびメモリとの、双方の現在の技術水準に依存している。技術水準が進めば、この関数の一方向の安全性を打ち破ることは可能である。現在では、一方向ハッシュ関数は、128ビット以上の出力とすることが推奨されている。これ以下では、この関数は一般的に安全ではない（どのように設計されたものであれ）。技術水準の進歩に伴い、安全なハッシュ関数に推奨される長さは増加する。
一方向ハッシュ関数値によるドキュメントの命名体系は、本来的に”検証することができる”ものであるが、この体系に関連して、いくつかの不便な特徴もある。まず、第１に、人間のユーザにとって、思い出したり、他の人に簡単に伝えるには、名前の長さが長すぎることである。第２に、ドキュメントの作成者が、その名前の形式を制御できないことである。どのような一方向ハッシュ関数を用いた場合でも、ドキュメントのハッシュ値は、単純に、適正な長さの、ランダムに現れるビットの列である。このため、形式的もしくは内容的に関連するドキュメントの名前同士が関係を持たないという不便を作成者に与えるかもしれない。同様に、特定のドキュメントの名前は、基礎となった名付けられたドキュメントについての情報を何も与えない。第３に、技術の進歩に伴い、命名体系のためのどのような特定関数の選択も安全でなくなってきたために、長期間使用するドキュメントの名前は、安全のために、何度も変更する必要がある。
以上のことより、改良されたデジタルスタンプシステムを実現することが望まれる。
また、デジタルドキュメントを用いて作業する、改良された方法を実現することが望まれる。
また、ドキュメントの名前に関連して情報を提供することができ、本来的に検証することができ、言及しやすく、短く、ユーザフレンドリーな名前を割り当てることができる、命名システムを実現することが望まれる。
発明の概要
本発明は、改良したデジタルタイムスタンプシステムを提供することを目的とする。
また、本発明は、デジタルドキュメントを用いて作業する改良された方法を提供することを目的とする。
また、ドキュメントの名前に関連して情報を提供することができ、本来的に検証することができ、言及しやすく、短く、ユーザフレンドリーな名前を割り当てることができる、命名システムを提供することを目的とする。
本発明によれば、デジタルドキュメントのタイムスタンプを行う方法が提供される。この方法は、以下のステップを含む。（ａ）第１のドキュメントの登録のリクエストを受け取り、（ｂ）他の複数のリクエストを受け取り、結合して、ハッシュし、複数のリクエストに応じた複数のハッシュ値の保管庫（リポジトリ:repository）を形成し、（ｃ）第１ドキュメントに対する、保管庫中のロケーションポインタを生成し、（ｄ）ロケーションポインタによって前記第１のドキュメントを名付け、第１の名前を第１のドキュメントに与え、（ｅ）前記第１の名前を含む、前記第１のドキュメントの証明書を生成する。本発明によれば、後日、証明書をドキュメントの自己検証に用いることができるだけでなく、ユニークかつ便利よくタイムスタンプされたドキュメントに言及するのに、証明書の名前を用いることができる。本方法によれば、タイムスタンプシステムを、同時に命名システムとして、このような利便のためにサービス部やユーザに別のまたは並行するハードウエアを必要とすることなしに使用することができる。
同時にデジタルドキュメントのタイムスタンプと命名を行う方法に加えて、本発明は、デジタルドキュメントの命名方法をも含む。この方法は、以下のステップを含む。（ａ）第１のドキュメントの登録のリクエストを受け取り、（ｂ）他の複数のリクエストを受け取り、結合して、ハッシュし、複数のリクエストに応じたハッシュ値の保管庫を形成し、（ｃ）第１ドキュメントに対する、保管庫中のロケーションポインタを生成し、（ｄ）ロケーションポインタによって前記第１のドキュメントを名付け、第１のドキュメントに自己検証する名前を与える。本発明の、この態様によってデジタルドキュメントに与えられる名前は、本来的に検証可能であるのみならず、簡潔で使いやすい。さらに、この名前は、名付けたドキュメントと関連する情報を提供することができる。本発明の本態様の追加的な利点は、デジタルドキュメントのタイムスタンプに使う、新たな追加ハードウエアが必要ないことである。
【図面の簡単な説明】
前述した、また、その他の、本発明の目的と利点は、添付図面を参照した以下の詳細な説明を考慮して明らかとなる。各図面を通し、同様の参照番号は、同様部分を表している。図面において、
図１は、発明に係るタイムスタンププロセスのフローダイアグラムである。
図2Aは、証明のための、アルファベットと数字で表現したデジタルドキュメントＦを示したものである。
図2Bは、図2AのドキュメントＦの本発明に係る証明書の、タイムスタンプリクエストを図示したダイアグラムである。
図３は、二分木認証と名前保管庫の一部を図示したダイアグラムである。
図４は、図３の名前保管庫に関連して、ユニークに図2AのドキュメントＦを名付ける認証証明書を図示したダイアグラムである。
図５は、ドキュメントをユニークに名付ける、発明の他の処理のフローダイアグラムである。
図6A−6Cは、それぞれ、図５の処理に従った図2AのドキュメントＦの名前の第１、第２、第３の例を図示したダイアグラムである。
図７は、リニアリンクリスト（linear linked list）認証と名前保管庫を図示したダイアグラムである。
発明の詳細な説明
図１は、本発明に係るタイムスタンプ処理の第１の実施例のフローダイアグラムであり、以下で本発明の様々な特徴を図示した図２−４と関連して説明する。図１に示すように、本タイムスタンプ手順10は、デジタルドキュメントＦの証明のリクエストＲをユーザが用意するステップ11から始まる。このようなドキュメントＦのアルファベットと数字（英数）表現５の例を図2Aに示す。デジタルドキュメントＦは、デジタル形式でも、任意の英数のテキスト（図2Aに図示）や、ビデオや、オーディオや、絵画／写真を表現したものでも、その他の固定的データの形式でも良い。本処理は、任意長さのドキュメントに対して用いることができるが、図2Aの抜粋は、タイムスタンプを要求するドキュメントを充分に代表している。
図2Bは、ドキュメントＦ（図2A）の証明書の提供を求める、本発明に従ったタイムスタンプリクエストＲ（図１のステップ11でリクエスト発行者が用意する）の英数表現を図示したダイアグラムである。リクエストＲは、図2Aに示すドキュメントＦのハッシュ値21（a5）と、リクエスト発行者のファイルネーム22と、リクエスト発行者の識別番号23を含む。便宜上、この例は、ハッシュ値21（a5）は、MD5一方向ハッシュアルゴリズムの128ビットフォーマット（R.L.Rivestによって、"The MD5 Message−Digest Algolithm,"Requests for Comments（RFC）1321,Internet Activities Board,April,1992に記載されている）によって計算されたものとし、16進表現で表している。もちろん、他の一方向ハッシュアルゴリズムも同様に用いることができる（たとえば、MDアルゴリズム、または、Federal Information Processing Standard［FIPS］PUB180に規定されているNational Institute of Standard and Technology's Secure Hash Algorithm［SHA］を用いることができる。ここで、この例で使用した、英数表現や、他の数値の表現は、本発明の実施上、重要ではない。すなわち、他の表現も同様に用いることができる。
図2Bに示したように、リクエスト発行者は、リクエスト発行者のファイルネームより、リクエストの対象となっている特定のファイルを識別することができる。これは、一般的にいって、ユーザのドキュメントのサービス部（service bureau）による証明にとって重要ではないので、リクエストＲのオプションとなっている。リクエスト発行者の識別番号23より、サービス部は、ドキュメントの証明をリクエストした特定のリクエスト発行者を識別することができる。
図１に戻り、ステップ11で、デジタルドキュメントＦ（図2A）の証明のリクエストＲをユーザーが準備したら、ステップ12において、リクエスト20（図2B）をサービス部に送る。ステップ13では、サービス部が、リクエストを結合する。こうすることによって、サービス部は、ドキュメントＦのハッシュ値a5（図2B）をＲから取り出し、この値を、２番目の証明リクエストが対象とする２番目のドキュメントのハッシュ値a6と結合（たとえば連結）する。ステップ14では、サービス部は、組み合わせたものを一方向ハッシュ関数でハッシュし、ハッシュ値a5とa6にリンクした新たなハッシュ値を生成する。この様相は、本発明の原理に従った認証と命名の保管庫（たとえば、二分木）の部分を示した図３と、ドキュメントＦが図2Aのテキストで構成されている場合の図３の保管庫に対するMD5のハッシュ値の例を図示したテーブル（後掲の請求の範囲の前に添付している）に示した。図３に示したように、デジタルドキュメントＦは、ハッシュ値a5を含む、証明のリクエストＲの対象である。後掲のテーブル（サブツリーＡ）に示したように、a5（図2AのドキュメントＦに対する）は、値"b767290cff8c87194cf3061３08a9794a"を持っている。（例示のために、テーブル中のハッシュ値a1−a4,a6−a8,b1−b8,d1,d3−d6,d8に任意の値を割り当てた。）
図１のステップ13と14では、ハッシュ値a5は、ハッシュ値a6と結合（たとえば連結（concatenated）され、組み合わせたものは、図３のA5−６で示される新たなハッシュ値を生成するために、ハッシュされる。（ここで、下付きの"5−6"は、そのハッシュ値が、サブツリーＡの５番目と６番目の葉から、導かれた結果として生じたものであることを表している。）言い換えるならば、第１のビット列a5は、第２のビット列a6と結合され、その結果が、新たなビット列A5−６を形成するようハッシュされる。（たとえば、図３とテーブルに関連して、a5とa6を連結すると、"b767290cff8c87194cf3061３08a9794a15812318c8ec1d2cf94a79cb8952f3c2"となり、そのハッシュ値は、"9dad90bbef28047744a26865acbbf24ee"となる）図１のステップ15では、サービス部が、他の証明のリクエストを受け取り、組み合わせ、ハッシュし、結果として得られたハッシュ値（図３に図示）の保管庫（図３に図示した木）を形成する処理を継続する。具体的には、図３に示したように、ハッシュ値a7とa8が結合され、ハッシュされ、結果としてのハッシュ値A7−８を形成する。この後、ハッシュ値A5−６とA7−８は結合され、ハッシュされ、結果としてのハッシュ値A5−８を形成する。同様に、ハッシュ値a1,a2,a3,a4も、適切に結合され、一緒にハッシュされ、A1−2,A3−４を形成し、これらはさらに、相互に結合されてハッシュされ、A1−４を形成する。ここで、サブツリーＡは、A1−４とA5−８を組み合わせ、組み合わせたものをハッシュし、ハッシュ値A1−８を形成することにより、”閉鎖される”。（ここで、下付きの"1−8"は、そのハッシュ値が、サブツリーＡの１番目から８番目の葉から、導かれた結果として生じたものであることを表している。）言い換えるならば、ハッシュ値a1からa8で表されるドキュメントはサブツリーＡ中で相互にリンクされ、これらのハッシュ値の保管庫を形成する。この保管庫の要素は相互に、ハッシュ値Ai−ｊによって順番にリンクされている。
図３において、サービス部は、さらに、ドキュメントハッシュ値b1、b2、b3、b4、b5、b6、b7、b8を含むリクエストを受信しつづけ、ルートB1−８をもつサブツリーＢを形成する。サービス部は、さらに、ドキュメントハッシュ値d1、d3、d4、d5、d6、d8を含むリクエストを受信しつづけ、これらをハッシュ値d2、d7（それぞれ、ルートA1−８とルートB1−８から抽出する）と組み合わせ、ハッシュ値D1−2,D3−4,D5−6,D7−８と、その次のD1−4,D5−８から構成される、最終的な木Ｄを形成する。D1−4,D5−８は、相互に結合され、組み合わせたものはハッシュされ、D1−８となり、木Ｄのルートを形成する。
図１に戻り、処理10のステップ16は、保証すべき項目の決定を含む。（たとえば、図３のサブツリーA,B,D,は閉鎖されており、ルートD1−８が保証すべき項目となる。後述するように、その後、認証が行われる前、保証された項目は、（１）保証すべき項目を直接公開する（すなわち、広く証明され（witnessed）、広く利用できるようにする）、（２）保証すべき項目を、他の、直接公開されたハッシュ値にリンクすることにより保証される。ステップ17では、証明のリクエストＲについて、サービス部は、保証された項目D1−８について、”自己検証”ハッシュ値を計算する。”自己検証”ハッシュ値は、ドキュメントＦの認証に必要なハッシュ値として定義された、a6,A7−8,A1−4,d1,D3−4,D5−８となる。ステップ17は、また、自己検証ハッシュ値a6,A7−8,A1−4,d1,D3−4,D5−８のロケーション値（図３のつながり（handedness）値）を計算する。これは、それぞれ、R,R,L,L,R,Rとなる。（ここで、Ｌは左、Ｒは右を示している。）
このハッシュ値のリストと関連するロケーション値（たとえば、後に述べる認証証明書から得ることができる）を用いて、後日、当事者（party）は、保証された項目D1−８が計算されたときにサービス部によって受け取られ、登録されたものとしての、ドキュメントF'の真正さを調べたいとき（すなわち、F'がＦ′と同じものである）、次のステップが実行される。はじめに、ドキュメントF'のハッシュの右に自己検証ハッシュ値a6が結合され、結合されたものがハッシュされ、Ａ′５−６を形成する。第２にハッシュ値Ａ′５−６の右に自己検証ハッシュ値A7−８が結合され、結合されたものがハッシュされＡ′５−８を形成する。第３に、Ａ′５−８の左に自己検証ハッシュ値A1−４が結合され、結合されたものがハッシュされＡ′１−８を形成する。第４に、ハッシュ値A'1−８の左に自己検証ハッシュ値d1が結合され、結合されたものがハッシュされＤ′１−２を形成する。第５に、ハッシュ値Ｄ′１−２の右に自己検証ハッシュ値D3−４が結合され、結合されたものがハッシュされＤ′１−４を形成する。第６に、ハッシュ値Ｄ′１−４の右に自己検証ハッシュ値D5−８が結合され、結合されたものがハッシュされＤ′１−８を形成する。これによって、このドキュメントＦ′が真正であれば、公開された、または保証された記録から（たとえば、確認用記録を記憶した多様なサイトのいずれかから）得られるような正しいハッシュ値D1−８が、D'1−８から得られる（すなわち、Ｄ′１−８＝D1−８）。真正でなければ、変更されたドキュメントは、異なる値にハッシュされる。
本発明に係るタイムスタンプシステムの他の特徴は、確認用に急いで公開する必要なく、ドキュメントのすばやい登録を簡単にする点である。言い換えるならば、証明書が生成されたリクエスト発行者に送られる時点で、公開が行われていなくても、証明書を与えることができる。必要となるのは、ユーザが組（ドキュメント、証明書）の確認をを望む前に、何らかの種類の公開が行われることだけである。たとえば、図２において、やがてそれが保証されるかぎり（すなち、直接公開されるか、ハッシュ値に安全にリンクされるか）、ハッシュ値a1からa8のハッシュ値で表されるドキュメントの登録時に、ハッシュ値D1−８は“公開”される必要がない。他のタイムスタンプ方法とは対照的なことに、本発明の、この特徴は、登録のリクエストに対するすばやいレスポンスタイムを、これに対応するすばやい公開時を要求することなしに実現する。登録リクエスト処理を、公開プロセスと分離することにより、タイムスタンプシステムは、サービス部の保管庫マネージャーに費用のかかる頻繁な公開の負担をかけることなく、より多くの登録リクエスト（これらは迅速に処理される）に、よりよく対応することができる。
図１に戻り、処理はステップ18に進み、ここでは、サービス部が、ロケーション値（たとえば、つながり（handedness））と保証する項目の識別子（たとえば、ルート）D1−８を結合し、組み合わせたもの"RRLLRR｛D1−８識別子｝”を形成する。本発明の特徴によれば、この組み合わせ（連結）は、短くて圧縮されているばかりでなくユニークで自己認証する、ドキュメントＦの”名前”として用いることができる。たとえば、"RRLLRR｛D1−８識別子｝”という名前をもつドキュメントは世界に一つしかない。この名前は、一般的に128ビットかそれ以上である典型的な有用ハッシュ値に比べ、とても短い。さらに、固有のハッシュ値と関連した名前の使用は、それが示す特定のドキュメントが真正であることの検証に用いることができる。
本発明によれば、処理はオプションのステップ19に進み、ステップ18で生成されたユニークな名前を、短い”ニックネーム”の形式に略する。たとえば、名前"RRLLRR〔D1−８識別子〕”は、まず、２進数表現に変換し（たとえば、"001100〔２進数表現のD1−８識別子〕”そして、英数表現に変換することにより、英数の形式で表現することができる。この本発明の”ニックネーム”の特徴は、具体的には、人々に、たとえば、電話で、そのドキュメントを参照するときに、タイムスタンプされたドキュメントの名前を手早く書き留めることを可能とする。たとえば、128ビットかそれ以上のハッシュ値をもつドキュメントＦには、米国内の長距離の電話番号の長さもしくは10文字以下の、本発明に従った”ニックネーム”を持たせることができる。
図１において、処理はステップ20に進み、当該ステップにおいて、サービス部は、ドキュメントＦの自己検証ハッシュ値と、それらのハッシュ値のロケーション（たとえば、つながり（handedness））値、とユニークな名前もしくはニックネームを含む、ドキュメントＦの認証証明書を生成する。後掲するテーブルの値をとるサブツリーA,B,Cよりなる、図３の保管庫に対応する、図2AのドキュメントＦの認証証明書30を、図４に図示する。証明書30は、（ｉ）つながり（handedness）値を伴う自己検証ハッシュ値31、（ii）ルートD1−８へのポインタ（たとえば、図４のポインタ32−−2e5347f5−−は、英数表現で、ルートD1−８のユニークな識別子を図示したものであり、後述するように、D1−８が生成された時刻を表している）、（iii）ドキュメントＦのユニークな名前33、（iv）ドキュメントＦのユニークなニックネーム34の、４種類の情報を含んでいる。必要であれば、証明書30に、図2Bのリクエスト10の情報を含めることもできる。また、名前33は、見やすいように、証明書から削除してもよい。図１の処理10は、ステップ21に進み、証明書30が、サービス部からユーザに送り返される。
このように、図１−４は、ドキュメントＦにタイムスタンプし、認証証明書を提供し、後日疑わしいドキュメントF'の真正さの検証に使用できるのみならず、すばやく簡単な方法でドキュメントF'にユニークに言及することができる、本発明の実施例を図示している。この本発明のタイムスタンプシステムの、追加的な”名前付け”の特徴は、ユーザやサービス部に、追加的なまたはパラレルなハードウエアを必要とせずに、特別な”名前付け”の利便性をユーザに提供する。
本発明の他の態様によれば、本発明の処理は、証明書にドキュメントの自己検証ハッシュ値を含まない、ドキュメントにユニークで自己検証できる”名前”を与えるのい用いることができる。このような本発明の特徴を、本発明に係る処理の他の実施例のフローダイアグラムである図５に示す。処理40は、まず、ステップ41で、ユーザが、デジタルドキュメントＦの名前のリクエストRNを用意する。たとえば、リクエストRNは、図2BのタイムスタンプリクエストＲに表した情報を含むことができる。処理40の引き続くステップ42では、リクエスト発行者が、リクエストをサービス部に送る。ステップ43では、サービス部は、リクエストを結合（たとえば、連結）する。このようにして、サービス部は、前記図１と同様に、対象のドキュメントのハッシュ値を取り出し、この値を、第２の名前のリクエストの対象である第２のドキュメントのハッシュ値と結合（たとえば、連結）する。ここで、第２のリクエストは、サービス部システムによるタイムスタンプ証明書の提供を求めるリクエストであってもよい。サービス部の立場からみて、リクエストの種類は、一般的に重要ではない。
ステップ44において、サービス部は、結合結果をハッシュして、上述の図１のような新たなハッシュ値を生成する。ステップ45では、サービス部は、他の名前（または証明）のリクエストを受け取り、組み合わせ、ハッシュし、結果として得られたリンクされたハッシュ値（図３に図示）の保管庫（図３に図示した木）を形成する処理を継続する。ステップ46では、サービス部は、保証すべき項目（たとえば、ルートD1−８）を特定する。先に図１において説明したように、後日、認証の前、この項目は、（１）保証すべき項目を直接公開する（すなわち、広く証明され（witnessed）、広く利用できるようにする、（２）保証すべき項目を、他の、直接公開されたハッシュ値にリンクすることにより保証される。ステップ47において、名前のリクエストRNについて、サービス部は、対象となったドキュメントに対する”自己検証”ハッシュ値と、”自己検証”ハッシュ値のロケーション値（たとえば、つながり（handedness））を、図１のステップ17と同様に計算する。ステップ48において、サービス部は、図１と同様に、ロケーション値とルートD1−８の識別子を結合し、組み合わせたものを形成する。追加的なステップ49では、図１と同様に、ステップ48で生成したユニークな名前を、さらに、短い”ニックネーム”の形式に略する。
次のステップ50では、サービス部は、”名前”をリクエスト発行者に送り返す。図6A−6Cは、本発明の図５の処理40に従った名前の第１、第２、第３の例を、それぞれ図示したものである。図6Aに示すように、名前55は、ロケーション値（たとえば、つながり値（handedness values）とルート識別子（たとえば、公開された時刻"8/18/94 7:37:25 AM EDT"によって特定したルート）の組み合わせ（たとえば、連結）よりなる。図6Bにおいて、図6Aの名前55は、同じ時刻を用いたニ進数表現で表されている（たとえば、UNIXスタンダードの時刻：グリニッジ標準時刻における、1970の最初の秒からの秒数）。図6Cでは、図6Bの名前56を、英数形式で表すことにより、さらに簡略化している。図6A−図6Cでは、”時刻”をルートの識別子として用いているが、もちろん、他のユニークな識別子も同様に用いることもできる。たとえば、シーケンシャルな、ルートの公開番号、すなわち所定の公開からの公開されたルート数も、同様に用いることができる。このような、シーケンシャルなルートの公開番号も、ルートが公開された時刻と同じように、ルートを特定する。
特定のドキュメントＦの名前Ｎが計算された後、後日、当事者（party）が、提示された当該ドキュメントF'と名前Ｎとの関係を確かめたい場合には、当事者は、認証証明書Ｃのコピーを入手し（蓄積機能やその他の手段より）、次のような手順を行う必要がある。第１に当事者（party）は、Ｃに含まれる情報から、Ｎが正確に抽出されたことを検証する。次に、当事者（party）は、図１で説明した確証（validation）の手順を実行する。
このように、図５の処理によれば、本来的に検証可能なばかりでなく、短く、簡単で、すばやく、書いたり、言ったりすることのできる名前やニックネームがデンタルドキュメントに対して提供される。たとえば、図6Cに示したように、図５の処理は、128ビット以上の典型的なハッシュ値をもつドキュメントに対しても、40ビット（すなわち、16進数表現で10デジット以下）以下の名前を与えることができる。（しかし、16進数表現よりも、もっと、ビット列を圧縮する、英数の符号化もある。たとえば、UUCP印刷可能キャラクター符号化は、英数字の一文字あたり、４ビットではなく６ビットを使用する。このような符号化によれば、図6Cの名前は、たった７文字で表すことができる。これは、米国のローカルな電話番号の長さである。）さらに、ドキュメントの”名前”はユニークである。言い換えるならば、図５の処理を用いるシステムで名付けられた他のどのドキュメントも、同じ名前を持つことはない。これは、本発明の方法によって、本質的に保証される。さらに、名前を与えるハードウエアは、デジタルドキュメントのタイムスタンプにも用いることができる。
ハッシュ値を保証し結びつける保管庫として”二分”木を図示した図３を用いて発明を説明したが、本発明を実施する方法は他にもいろいろある。たとえば、本発明の”保管庫”は、二分木に代えて、３分、４分、ｋ分木や、これらの組み合わせを用いてもよい。もちろん。図３には、各々８つの葉をもつ３つのサブツリーA,B,C,を図示したが、他の木やサブツリーのアレンジや組み合わせも同様に用いることができる。必要なことは、保管庫中の項目が、公開によって保管庫を保証するハッシュ関数を介してリンクされていることだけである。数学的には、ときとして保管庫中の項目がグラフ中の全ての項目が一つの項目に方向付けるパスによってリンクし得る、成長する有向非環状グラフ（growing directed acyclic graph）を、保管庫中の項目が形成するといえる。
したがって、リニアリンクリストや、ハッシュ値のその他の種類の蓄積も、同様に用いることができる。たとえば、"How to Time−stamp a Degital document,"S,Haber,W.S.Stornetta,Journal of Cryptography,Vol.3,No.2,pp99−111（1991）に記載されたリニアリンクリストを、代わりに用いることができる。これは、本発明の命名処理の実施に用いるリニアリンクリストの一部のダイアグラムである図７に示されている。図７に示すように、命名リクエストR1,R2,R3は、それぞれ、デジタルドキュメントF1,F2,F3に関係する。リクエストR1,R2,R3は、図2Bを用いて示したものと同様であってよい。これらのリクエストは、サービス部に送られ、サービス部は、ドキュメントF1のドキュメントハッシュ値a1を取りだし、これを既に存在しているハッシュ値A0と結合し、組み合わせたものをハッシュし、新たなリンクハッシュ値A0−１を作る。この、新たなリンクハッシュ値A0−１は、ドキュメントF2のドキュメントハッシュ値a2と結合され、組み合わせたものをハッシュし、新たなリンクハッシュ値A1−２を作る。同様に、新たなリンクハッシュ値A1−２は、ドキュメントF3のドキュメントハッシュ値a3と結合され、組み合わせたものをハッシュし、新たなリンクハッシュ値A3−４を作る。
この処理は希望する限り、対応するデジタルドキュメントの無傷さ（integrity）を保証するリンクハッシュ値の保管庫または蓄積を形成するように継続される。リクエスト発行者がユニークな“名前”を含む証明書を用いることができるように、サービス部は、定期的に、保管庫の一部（たとえば、図７ではリンクハッシュ値A4−５）を公開することにより、保管庫を保証する。図１〜６と同様に、“名前”は、”公開された”リンクハッシュ値への第１のポインタ（たとえば、リンクハッシュ値A4−５へのポインタ）を表すものと、保管庫中で名付けられるべき特定のドキュメントから”公開された”リンクハッシュ値への第２のポインタを表すものとの組み合わせから導かれる。図７のリニアリンクリストの場合、この第２のポインタは、単純に、名付けられるべきドキュメントのリンクハッシュ値と”公開された”リンクハッシュ値との間のリンクハッシュ値の数を数えたものとなる。たとえば、図７のドキュメントF1,F2,F3に対する、この数は、それぞれ、４、３、２となる。この結果、ドキュメントF1,F2,F3の”名前”は、この例では、"4［リンクハッシュ値A4−５へのロケーションポインタ」”、"3［リンクハッシュ値A4−５へのロケーションポインタ」”、"2［リンクハッシュ値A4−５へのロケーションポインタ」”となる。本発明によれば、この名前は、短く、簡潔で、ユニークであるだけでなく、自己検証ができるものである。
本発明によれば、他のハッシュ値のリンク方法も、また、用いることができる。たとえば、頻繁に計算（毎秒または毎分）される木のルートを、そのルートがリニアリンクリストと結合した日毎の木に結合することができる。
要約すると、本発明は、デジタルドキュメントの命名に関連して上述した様々な制約を避けながら、そのハッシュ値のみによって命名するドキュメントの検証可能な安全性を保持するような、ドキュメントの命名方法を含む。本発明のこの特徴の本質は、多くのドキュメントに依存するハッシュ値の保管庫を保持し、名前を“リンクすることができる”保管庫中のロケーションの簡潔な表示によって名前を各ドキュメントに与えることである。
本発明の好適な実施例において、ビット列は、一方向ハッシュ関数を用いて”リンク”される。ハッシュ値の組または並べられたリストに対して、組織的に呼び出されるハッシュ関数によって、新しいハッシュ値が、古いものから計算され、リンクリスト、二分木、または、他の組み合わせの構造を形成する。このようにして、ドキュメントは保管庫にリンクされ、保管庫中の各要素は相互にリンクされる。
保管庫は、その一部を、様々な手段のいづれかにより広く証明され（witnessed）利用されるようにすることにより保証される。保管庫の残りの部分−−登録されたドキュメント−−は、このような部分と広く利用可能な部分にリンクすることにより保証される。
ハッシュ値の成長パターン（すなわち、directed acyclic graph）で形成された組み合わせの構造の正確な形式にかかわらず、ハッシュ値のリストと、これに伴う（とても簡潔な）構造的な“進行方向（driven directions）”またはロケーション情報は、保管庫中の、要約され広く利用可能とされたハッシュ値と特定のデジタルドキュメントをリンクするために用いられる。このハッシュ値のリストとロケーション情報は、ドキュメントの認証証明書に加えることができる。登録されたドキュメントの正確なコピーだけが、この証明書と保管庫中のロケーションにリンクすることができる。これは、一方向ハッシュ関数の特性と、保管庫の記録の広く証明され（witnessed）広く利用可能な性質によるものである。
したがって、このような認証証明書をもつドキュメントには、信頼できるロケーション情報を簡潔に符号化したものが、名前として与えられる。これ以外の組（ドキュメント、証明書）は、”この名前をもつ”ようには計算されない。
本発明によれば、命名方法は、異なる方法で実現できる。異なる組み合わせの構造は、異なるレベルの証明（witnessing）によって、異なる方法で結合できる。たとえば、保管庫の広く証明された組織（fabric）への直接のリンクも可能である。具体的には、保管庫マネージャーによって保持されている全ての記録を公開し、ロケーション情報を直接のポインタと同じように簡単にすることもできる。または、保管庫の記録の広く証明された部分にリンクするために、そのルートが定期的に保管庫マネージャーに送られる、ユーザが作った彼もしくは彼女自身の木（または、他の構造）による、ローカルな木でもよい。
本発明の、ある態様においては、この命名方法によって、ユーザは、彼または彼女のドキュメントの名前を選択、制御する個人的手段を得る。たとえば、ローカル木の態様を考えると、特定のドキュメントのローカル情報は、ローカル木中の位置と、この後ろにサービス部の木中の位置を記述したものとすることができる。ユーザは、適当なローカル木（または、他の構造）の連続した葉ノードに、各引き続く部分を置くことにより、複数部分のドキュメント（multi−part document）に名前をつけることができる。たとえば、図３の、８個のハッシュ値a1からa8は、本の８章を表すものとすることができる。これにより、このようなドキュメントの連続した部分は、ローカル木（または構造）中で連続したローカル位置を持つことができる。その後、ローカル保管庫のマネージャーが、このようなローカル木のルートをサービス部の保管庫のマネージャーに送った場合には、結果的に、このようなドキュメントの引き続く部分に、ローカル情報の適当な符号化によって連続した名前が、登録情報として与えられる。適当な符号化の例としては、単純な葉の番号付けによるものがある。さらに、これらの名前のローカルでない部分は等しく、これらが同じドキュメントの部分である事実を明示的に符号化している。たとえば、図３と後掲するテーブルを参照すると、ハッシュ値a1からa8は複数部分のドキュメントの連続した部分を表しており、"3e5347f5"はルートD1−８の識別子であり、ハッシュ値a1からa8によって表される、ドキュメントの“名前”は、次のようになる。a1:"1−LRR−2e5347f5";a2:"2−LRR−2e5347f5";a3:"3−LRR−2e5347f5";a4:"4−LRR−2e5347f5";a5:"5−LRR−2e5347f5";a6:"6−LRR−2e5347f5";a7:"7−LRR−2e5347f5";a8:"8−LRR−2e5347f5";  ドキュメントの部分を構造化する、もっと複雑な方法は、本発明の命名方法によって割り当てた自己証明する名前に符号化することである。たとえば、図３のd1からd8は本の８個の章の個々を表し、d2とd7で表される章は各々、ハッシュ値a1からa8とb1からb8で表される８個のセクションを持っている。このような状況に従い、図３のハッシュ値ai,bj,dkで表される、ドキュメントのさまざまな部分の”名前”は、たとえば、もし、ハッシュ値D1−８が、サービス部の保管庫マネージャーに送られ、ローカルな保管庫マネージャーが返答としてその名前Ｎを受け取るとして、次のようになる。a1:"1−２−N";a2:"2−２−N";3a:"3−２−N";a4:"4−２−N";a5:"5−２−N";a6:"6−２−N";a7:"7−２−N";a8:"8−２−N";b1:"1−７−N";b2:"2−７−N";b3:"3−７−N";b4:"4−７−N";b5:"5−７−N";b6:"6−７−N";b7:"7−７−N";b8:"8−７−N";d1:"1−N";d2:"2−N";d3:"3−N";d4:"4−N";d5:"5−N";d6:"6−N";d7:"7−N";d8:"8−N"
他の態様において、長いもしくは複雑な複数部分のドキュメントの内容のテーブルを、リクエストの、ある標準の位置に含めることもできる。たとえば、図３において、d1（１章）からd7（７章）で表される本の７個の章を持ち、d2とd7で表される章は各々、ハッシュ値a1（セクション１）からa8（セクション８）とb1（セクション１）からb8（セクション８）で表される８個のセクションを持っている本の内容のテーブルのドキュメントを、d8が表すものとすることができる。本発明のこの態様の特徴は、複数部分のドキュメントのうちの一つの自己検証できるドキュメント（すなわち、内容のテーブル）はドキュメントの全ての部分についての記述を含め、この一つのドキュメントを、ある特定のトピックに関係するドキュメントの各部分をリストするのに利用できるようにしていることである。後に、認証すべきドキュメントと、その申し立てられた証明書の収集と共に、このように認証されたリストを、（１）各ドキュメントが、内容のテーブルと共に登録された各ドキュメントの正確なコピーであるか、（２）このリスト中の、どのドキュメントも失っていないか、を調べるのに利用することができる。
ドキュメントの組織的構成を符号化するのに名前を使う、この方法は、本発明の自己確認できる（self−attesting）名前が、デジタルドキュメントのユーザーや人間の読者に有用であるいくつかの異なる方法のうちの一つでしかない。たとえば、ドキュメントがリンクしている保管庫中のロケーションを符号化する、利便性ある一つの方法は、日時−−簡単に理解できる何か−−によることである。例として、図6Aを参照されたい。
ユーザにとって、もっと有用で便利な、システムの名前を作成する他の方法は、次のように”個人化した”名前のリクエストをユーザに許可することである。サービス部の保管庫の記録が毎日、ある標準的な方法でフォーマットされる（たとえば、二分木を、毎分一度閉鎖することによって）とし、Ｆ（）が、ASC II符号化列から、保管庫記録の位置のリスト（たとえば、その日の分（minute）への）標準的な変換（マッピング）を表すとする。個人化した命名のリクエストは、ASC II符号化された文字列、たとえば、"ABC Corp."または"Jhone Smith's Ph.D.Dissertation"を伴う。毎日の個人化した命名のリクエストは、保管庫マネージャーによって、たとえばＦ（“ABC Corp."）またはＦ（“John Smith's Ph.D.Dissertation"）で示される分（minute）に根付いた木にリクエストをリンクすることによって、与えられたASC II符号列のＦ（）を評価することにより命名されたロケーションにリンクされる。この方法において、リクエスト発行者の、文字列−−−ドキュメントについて便利だと思う、どのような情報でもよい−−−の個人化的な選択は、名付けられたドキュメントの、自己確認できる名前の一部となるようになされる。もちろん、たとえば毎分ではなく毎時間といった他の時間スケールにおいても同様のテクニックを適用することができる。
さらに、1992年12月21日出願に記載され、参照によってすべてがここに組み入れられる、共に係属している米国特許出願シリアル番号No.07/992,883（"Improving the Efficiency and Reliability of Digital Time−Stamping,"D.Bayer,S.Haber,W.S.Stornetta（in Sequences II:Methods in Communication,Security,and Computer Science,eds.R.M.Capocelli,A.DeSantis and U.Vaccaro,pp329−334,Springer−Verlag,New York,1993）とともに）は、真正さの暗号的証明書を命名本発明の更新するためのものであり、方法による証明書に直接適用される。これにより、テクノロジーの進歩に伴い証明書が適正に更新される限り、本発明で与えた自己確認できる名前は、変更することなく、長期間、効力をもつ。
要約すれば、本発明の態様は、与えられる名前が（命名処理が、主としてローカルな操作によってなされていても）例外なく自己確認できるので、従来の命名方法を改良しているといえる。また、本発明のこの態様は、本方法によって割り当てる名前は、短く、意味があり、柔軟性があり、更新でき（これによって、長期間守られ）、ドキュメントに関連するようにリクエスト発行者が選択した情報を提供するので、現在のドキュメント固有の命名方法を改良している。さらに、この名前付けシステムは、大量の名前付けリクエストを扱う規模に拡大することができる。
当業者は、本発明より、限定するためでなく例示するために示した前記実施例以外の実施態様をとることができる。また、本発明は、以下のクレームによってのみに限定されるものである。
0003554765.tif 000002
0003554765.tif 000003
0003554765.tif 000004
【図２Ａ】
0003554765.tif 000005
【図６Ｃ】
0003554765.tif 000006
【図１】
0003554765.tif 000007
【図２Ｂ】
0003554765.tif 000008
【図４】
0003554765.tif 000009
【図６Ａ】
0003554765.tif 000010
【図６Ｂ】
0003554765.tif 000011
【図３】
0003554765.tif 000012
【図５】
0003554765.tif 000013
【図７】
0003554765.tif 000014