(57)【特許請求の範囲】
【請求項１】
真正文書の保全性を検証する方法であって、
可能な将来の検証のために前記真正文書内のオリジナル情報を照合子化するときに、第１のユーザ端末装置が、
ａ）一方向ハッシュ関数を使用して前記オリジナル情報をオリジナル照合子にハッシングするステップと、
ｂ）前記オリジナル照合子を複数のｎ個のオリジナル照合子断片Ｓ１、Ｓ２、・・・、Ｓｎに符号化するステップであって、前記符号化は符号化関数を用いて行い、前記オリジナル照合子断片の夫々は前記オリジナル照合子と異なる、前記符号化するステップと、
ｃ）前記オリジナル照合子断片の各々をｎ個のロケーションＩ１、Ｉ２、・・・、Ｉｎに配布するステップであって、前記ロケーションの各々は前記オリジナル照合子断片の少なくとも１つを受信する、前記配布するステップと、
前記真正文書であるとされかつテスト文書の保全性を検証するときに、前記第１のユーザ端末装置又は前記第１のユーザ装置と異なる第２のユーザ端末装置が、
ｄ）前記オリジナル照合子断片であるとされる任意のｘ個のテスト照合子断片Ｓ’１、Ｓ’２、・・・、Ｓ’Ｘを複数のロケーションＩ１、Ｉ２、・・・、ＩＸ（ｎ／２＜ｘ≦ｎ）から検索するステップと、
ｅ）前記ｘ個のテスト照合子断片を第１のテスト照合子に復号化するステップであって、前記復号化は前記符号化関数の対である復号化関数を用いて行う、前記復号化するステップと、
ｆ）前記ハッシュ関数を使用して前記テスト文書内のテスト情報を第２のテスト照合子にハッシングするステップと、
ｇ）前記第１のテスト照合子を前記第２のテスト照合子と比較し、そして前記第１のテスト照合子が前記第２のテスト照合子に等しいときに、前記テスト文書を前記真正文書であるとして受諾するステップと、
を含む、方法。
【請求項２】
前記ロケーションの各々がメモリ・ロケーションである、請求項１に記載の方法。
【請求項３】
前記オリジナル照合子の前記符号化が、誤り訂正符号化プロシージャである、請求項１に記載の方法。
【請求項４】
真正文書の保全性を検証する装置であって、
可能な将来の検証のために前記真正文書内のオリジナル情報を照合子化するために、第１のユーザ端末装置が、
ａ）一方向ハッシュ関数を使用して前記オリジナル情報をオリジナル照合子にハッシングするハッシャと、
ｂ）前記オリジナル照合子を複数のｎ個のオリジナル照合子断片Ｓ１、Ｓ２、・・・、Ｓｎに符号化するエンコーダであって、前記符号化は符号化関数を用いて行い、前記オリジナル照合子断片の夫々は前記オリジナル照合子と異なる、前記エンコーダと、
ｃ）前記オリジナル照合子断片の各々を、前記第１の装置に接続されたｎ個のサーバＩ１、Ｉ２、・・・、Ｉｎに分散する手段であって、前記サーバの各々は前記オリジナル照合子断片の少なくとも１つを受信する、前記分散する手段と、
を含み、
前記真正文書であるとされかつテスト文書の保全性を検証するために、前記第１のユーザ端末装置又は前記第１のユーザ装置と異なる第２のユーザ端末装置が、
ｄ）前記オリジナル照合子断片であるとされる任意のｘ個のテスト照合子断片Ｓ’１、Ｓ’２、・・・、Ｓ’Ｘを複数の前記サーバＩ１、Ｉ２、・・・、ＩＸ（ｎ／２＜ｘ≦ｎ）から検索する手段と、
ｅ）前記ｘ個のテスト照合子断片を第１のテスト照合子に復号化する手段であって、前記復号化は前記符号化関数の対である復号化関数を用いて行う、前記復号化する手段と、
ｆ）前記ハッシュ関数を使用して前記テスト文書内のテスト情報を第２のテスト照合子にハッシングする手段と、
ｇ）前記第１のテスト照合子を前記第２のテスト照合子と比較し、そして前記第１のテスト照合子が前記第２のテスト照合子に等しいときに、前記テスト文書を前記真正文書であるとして受諾する比較手段と、
を含む、前記装置。
【請求項５】
複数のサーバと、前記サーバに接続された少なくとも１つのユーザ端末を有するコンピュータ・システムにおいて、真正文書の保全性を検証する方法であって、
可能な将来の検証のために前記真正文書内のオリジナル情報を照合子化するときに、第１のユーザ端末装置が、
ａ）一方向ハッシュ関数使用して前記オリジナル情報をオリジナル照合子にハッシングするステップと、
ｂ）前記オリジナル照合子を複数のｎ個のオリジナル照合子断片Ｓ１、Ｓ２、・・・、Ｓｎに符号化するステップであって、前記符号化は符号化関数を用いて行い、前記オリジナル照合子断片の夫々は前記オリジナル照合子と異なる、前記符号化するステップと、
ｃ）前記オリジナル照合子断片の各々をｎ個のサーバＩ１、Ｉ２、・・・、Ｉｎに配布するステップであって、前記サーバの各々は前記オリジナル照合子断片の少なくとも１つを受信する、前記配布するステップと、
前記真正文書であるとされかつテスト文書の保全性を検証するときに、前記第１のユーザ端末装置又は前記第１のユーザ装置と異なる第２のユーザ端末装置が、
ｄ）前記オリジナル照合子断片であるとされる任意のｘ個のテスト照合子断片Ｓ’１、Ｓ’２、・・・、Ｓ’Ｘを複数のサーバＩ１、Ｉ２、・・・、ＩＸ（ｎ／２＜ｘ≦ｎ）から検索するステップと、
ｅ）前記ｘ個のテスト照合子断片を第１のテスト照合子に復号化するステップであって、前記復号化は前記符号化関数の対である復号化関数を用いて行う、前記復号化するステップと、
ｆ）前記ハッシュ関数を使用して前記テスト文書内のテスト情報を第２のテスト照合子にハッシングするステップと、
ｇ）前記第１のテスト照合子を前記第２のテスト照合子と比較し、そして前記第１のテスト照合子が前記第２のテスト照合子に等しいときに、前記テスト文書を前記真正文書として受諾するステップと、
を含む、前記方法。
【請求項６】
前記オリジナル文書が前記サーバのメモリに記憶される、請求項５に記載の方法。
【請求項７】
前記文書がコンピュータ・プログラムである、請求項５に記載の方法。
【請求項８】
前記文書が実行可能なコンピュータ・コードである、請求項５に記載の方法。
【請求項９】
前記文書が複製されて、前記文書の多数のコピーが前記コンピュータ・システムの前記多数のユーザ端末内に記憶される、請求項５に記載の方法。
【請求項１０】
前記文書が多数のパーティションに区分化され、前記多数のパーティションの各々が前記多数のユーザ端末に各々記憶される、請求項５に記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、コンピュータに記憶されるまたはネットワークを通じて伝送されるオリジナル文書の保全性を検証する方法及び装置に関し、特に、オリジナル文書が変更されたかどうかを判断する方法及び装置に関する。
【０００２】
【従来の技術】
コンピュータに記憶される（または伝送される）情報は、例えばデータが不許可の（悪質な）パーティにより変更されうるなど、保全性侵害に晒される。多くの場合、こうした侵害は悲惨な結果をもたらす。こうした侵害には、プログラムまたは実行コードの悪質な変更（こうした変更は通常"コンピュータ・ウィルス"と呼ばれる）、行政、財政、司法、及び医療関係の情報などの慎重を要するデータの変更、ユーザ・パスワードまたはパブリック・キーなどの機密情報及び個人ユーザ情報の変更などが含まれる。
【０００３】
保全性検証方法は数年に渡り、物理的、非悪質なエラーに関して研究されてきた（文献［７］A．S．Tanenbaumによる"Computer Networks"、Prentice-Hall、Englewood Cliffs、NJ、１９８１年参照）。この場合には、敵は特定の保護方法には順応しないランダムまたは確率的なプロセスである。しかしながら、知能的及び悪質な敵の場合には保護はより困難となる。なぜなら、この敵は特定の保護方法を克服するべく、その振舞いを適応させるからである。後者のケースでは、こうした敵に対して保護するために暗号化手段が要求される。確かに暗号化は検出されることなく敵が情報を変更できないように、情報を照合子化（fingerprint）する多くの手法を生み出した。これらの方法は、（必要な照合子を生成する）情報所有者の敵に対する特定の"優位性"に頼るものであり、この優位性は通常、情報の正当な所有者またはユーザには知れるが、敵には知られない特定の秘密キーの形式を取る（文献［９］G．J．Simmonsによる"A Survey of Information Authentication"。Gustavos J．Simmons編集"Contemporary Cryptology、The Science of Information"、IEEE Press、１９９２年、pp．379-419参照）。
【０００４】
これらの照合子化方法は様々な状況において有効であるが、一方において達成が困難である。これらの方法の一般的適用の主な障害は、潜在的なユーザの間でどのように機密情報を共用するかである。特に、要求される機密情報がこれらのユーザの間で共用される場合、彼らの誰かが情報を変更する能力を有する悪質な敵となる可能性がありうる。正当なユーザまたはコンピュータがその所有者の個人的な興味、または外部の敵による攻撃または侵入により、改悪されることがありうる。この問題に対する部分的な解決は、機密の共用を要求しないパブリックキー暗号法により提供される（文献［１］J．Nechvatalによる"Public Key Cryptography"。G．Simmons編集"Contemporary Cryptology"、IEEE Press １９９２年。参照）が、これは保全性検証のために、異なるユーザに対応する異なる機密（個人キー）と、システム内の他のエンティティのパブリックキーの認可とを要求し、通常、信頼のおける第３者が必要となる。更にこれはタイム・スタンプ機構、発信元情報の知識及び高価なオペレーションの計算（例えば、ベキ乗法モジュロ大数（exponentiation modulo large number））を要求する。
【０００５】
（保全性検証とは反対に）ファイル保全性保護のための方法も、従来提案されてきた。簡単な解決策は、システム内の多くの地点でファイルを複製することである（例えば各プロセッサに対して１つのコピー）。これを回復するためには、単に全てのバージョンを収集し、ほとんどの場合に現れるバージョンを選択すればよい。大多数の正直な参加者にとって、これは情報の使用可能性を保証する。明らかに、この解決法は空間及び通信の観点から非常に非効率的である。故障停止障害（fail-stop faults）が許容される（すなわち幾つかのプロセッサがそれらの情報の断片を返却し損ね、返却された断片情報は常に変更されていない）状況において、この問題を軽減するために、Rabinは独自の情報分散アルゴリズム（Information Dispersal Algorithm）を発明した（文献［５］M．O．Rabinによる"Efficient Dispersal of information for Security、Load Balancing、and Fault Tolerance"、Jour．of ACM、Vol．36、No．2、１９８９年、pp335-348参照）。この方法は障害の故障停止モデルに関する上記問題に対して、空間効率のよい解決策を提供する。より一般的な障害に対する有効性を得るために、Rabinは情報の分散共用を照合子化することを提案した。しかしながら、従来の照合子化技術は、秘密キーもしくは信頼ある中央権限（central authority）、またはそれらの両者を必要とし、情報のアクセス性に対する制限及びシステムにとって好ましくない複雑化を招いた。
【０００６】
Li Gongは、情報の分散及びハッシング（hashing）を用いて機密を共用する方法を提案している（文献［８］L．Gongによる"Increasing Availability and Security of an Authentication Service"、IEEE Journal on Selected Areas in Communications、Vol．11、No．5、１９９３年６月、pp．657-662参照）。しかしながら、Gongは真正の文書をハッシングすることを教示していない。Gongによれば、情報のシェア（share）が生成され、それらのシェアの各々が真正の文書以上のサイズを有する。これらのシェアは次にハッシングされ、複数のロケーションに内密に分散される。Gongの目的は、文書が実際に変更されたかどうかの検証ではなく、真正の文書の回復及び機密保護であるので、Gongは非常に多くの計算、機密保護及び高帯域幅を要求する。
【０００７】
【発明が解決しようとする課題】
本発明は、コンピュータ・ウィルスの存在の検出に有用な情報の保全性検証のための方法を提供し、公衆または私用の記憶装置に内在したり、通信ネットワーク上で伝送される情報の信頼性（authenticity）を検証し、また異なるプロセッサまたはサーバから受信された情報の再構成の正当性をテストしたりする。本発明は機密保護を必要としない。本発明によれば、真正の文書を検出されることなく変更するためには、攻撃側（attacker）は、複数のロケーションに存在する情報またはコンピュータ・システムのエンティティを、同時に変更可能でなければならない。
【０００８】
【課題を解決するための手段】
従って、本発明は真正の文書の保全性を検証する方法及び装置を提供する。将来の検証のために文書を初期化するとき、真正文書内のオリジナル情報が一方向暗号化ハッシュ関数（one-way cryptographic hash function）を用いて照合子にハッシングされ、次に照合子が複数の照合子の断片に符号化され、最後に各照合子の断片が複数のロケーションに分散される。オリジナル文書と称され、テスト情報を有するテスト文書が検証されるとき、オリジナルの照合子の断片と称される所定最小数のテスト照合子断片が、第１のテスト照合子に復号化され、テスト文書内のテスト情報が一方向ハッシュ関数を用いて第２の照合子にハッシングされ、最後に、第１のテスト照合子が第２のテスト照合子と比較され、第１のテスト照合子と第２のテスト照合子が等しいと、テスト文書は真正の文書として受諾される。
【０００９】
本発明の背後にある仮定は、敵は断片が配置される全てのロケーションを読出すことが可能であるが、それらのフラクション（例えば少数）だけを変更することができるものとする。この仮定は多くのケースで当てはまるものである。こうしたロケーションの例に、別々のメモリ・ディスク、敵に対してハードウェア手段またはソフトウェア手段により（部分的に）保護されるメモリ・ロケーション、１つまたは複数のプロセッサのレジスタ、分散環境または並列環境内の異なるプロセッサ、ユーザまたはサーバのグループ、コンピュータ・プログラムまたはソフトウェア・パッケージのデータ領域及び実行可能コードなどが含まれる。サーバは、ワークステーションまたはメインフレームなどの任意のコンピュータまたはプロセッサである。一般に特定の実施例におけるロケーションの選択は、保護される情報の種類（例えば、記憶ファイル、コンピュータ・プログラム、実行可能コード、伝送メッセージなど）、情報をアクセスする必要のある対象（例えば、シングルユーザまたはマルチユーザ環境）、コンピュータ環境（例えば、集中化、分散または並列プロセッサ、クライアント−サーバ環境、通信ネットワークなど）、記憶媒体（メモリ階層、単一または複数ディスク、共用メモリまたは分散メモリ、送信メッセージまたはファイルなど）、コンピュータ・システムの異なる部分間の信頼関係（例えば、管理サーバは一般ユーザ・コンピュータよりも高い信頼性を有する）などに依存する。本発明はこれらの全ての状況において適用可能な解決策を提供する。説明の都合上、次に述べる例について考えることにする。
【００１０】
企業の本社のコンピュータ内に存在するファイルの場合：
この場合、照合子断片のためのロケーションとして、この企業の地理的に離れてはいるが、コンピュータ・ネットワークを介して通信可能な異なる地点のコンピュータを選択することができる。攻撃側がオリジナル・ファイルと、他のほとんどの照合子断片（距離的に離れて配置される）の両方を改悪するのは困難であると考えるのが妥当と言えよう。
パーティＡからパーティＢに伝送されるメッセージの場合：
ＡとＢとの間の回線に居座る敵は、メッセージ内の情報を変更することができる。本発明はメッセージだけでなく、照合子の断片を送信するためにも使用できる。これらの断片が主情報とは異なって経路指定されれば、検出されることなく情報を変更する敵の能力は、多大に低減される（敵がオリジナル・メッセージだけでなく、大多数の照合子断片を変更することが要求されるので）。本方法は、機密または認証された情報を以前に交換したことのないＡとＢとの間でも、良好に作用する。メッセージ確認のための全ての既存の方法は、ＡとＢとの間でのこうした従来の通信を要求する。
ソフトウェア・パッケージ（例えば、コンピュータ・プログラムの集合）の場合：
これらのプログラムでは、その情報（データまたは実行可能コード）が検出されることなく変更されると（例えばウィルスによる）、危険な結果を生じうる。慎重を要する情報に対して分散照合子を使用することにより、これらの変更に対する防御が可能である。すなわち、この場合、照合子の断片がソフトウェア・パッケージのオブジェクト・コード間の異なる（ランダムな）位置に配置される。敵すなわちウィルスが検出されないようにする唯一の方法は、これらのほとんどのロケーションをアクセスし、それらを変更することである。
【００１１】
本方法の高い柔軟性は、その機密性の無い性質、及び結果的な秘密キー及び機密性管理の不要性に由来する。更に暗号化される照合子のサイズは、敵に対して要求される機密のレベル（すなわちこの敵の計算資源）にだけ依存し、照合子化されるオリジナル情報の長さには依存しない。従って、異なるメモリ・ロケーションまたはコンピュータ・エンティティに分散される情報の量は小さい。これは、情報全体を分散または複製することにより保護を提供する方法とは対照的である。
【００１２】
【実施例】
図１は、本発明が実施される単純なネットワーク・トポロジを示す。図中、ユーザ端末１０、及びそれぞれがロケーションｌ1、ｌ2、．．．、ｌnに配置される複数のサーバ２０が示される。後述されるように、本発明は２つのフェーズ、すなわち照合子化または初期化フェーズと検証フェーズとを有する。
【００１３】
照合子化または初期化フェーズでは、端末１０は真正の文書Ｉを関数ｆにより照合子にハッシングする。次に端末１０のエンコーダ４（図３参照）が、照合子を照合子断片Ｓ1、Ｓ2、．．．、Ｓnに符号化する。これらの照合子断片は次に、図１に示されるように、端末１０からロケーションｌ1乃至ｌnに分散される。
【００１４】
図２は、本発明の検証フェーズを図式的に表す。この図では、端末１０'（端末１０と同じであっても異なってもよい）が、ｘ個（ｔ≦ｘ≦ｎ）の照合子断片をロケーションｌ1、ｌ2、．．．、ｌxから受信する。ここでパラメータｔについては後述する。
【００１５】
ロケーションｌ1、ｌ2、．．．、ｌxは説明の都合上選択されただけであって、実際には任意のｘロケーションを選択可能である。更にこの図では、仮のオリジナル文書Ｉ'がロケーションｌ3から受信されるように示される。後述されるように、受信された照合子断片は、次に第１のテスト照合子に復号化される。一方向ハッシュ関数が次に仮の真正文書Ｉ'に適用され、第２の照合子が生成される。２つのテスト照合子が比較され、これらの２つが等しいと、仮の真正文書が真の真正文書として受諾される。
【００１６】
再度図１を参照して、ここでＩをユーザ端末１０のメモリなどのコンピュータ記憶環境内に存在する情報または真正文書のストリームとする。本発明では、この情報を後の保全性検証のために照合子化するために、照合子化関数ｆ、１対の符号化／復号化関数Ｃ及びＤ、及び後の検証時に検索される（短い）断片情報を記憶するコンピュータ・システム内のｎロケーション（またはエンティティ）ｌ1、．．．、ｌnを使用する。これらのロケーションはメモリ・ロケーション、分散プロセッサ、一連のサーバまたはユーザ・グループなどに相当する（図２参照）。
【００１７】
照合子化関数ｆは通常、情報の生成または検証に関わるシステム内の全てのパーティにより知られる暗号化一方向ハッシュ関数である。大ざっぱに言えば、こうした照合子化関数ｆは任意のストリングｘに対して、ｆ（ｘ）＝ｆ（ｙ）なる別のストリングを見い出すことが困難な追加特性を有するハッシュ関数（長いストリングを短いストリングにマッピングする）である。
【００１８】
１対の符号化／復号化関数（またはプロシージャ）Ｃ及びＤは、次の特性を有する。これらは３つの値すなわちｎ、ｔ及びｋによりパラメータ化される。ここで、ｎ／２＜ｔ≦ｎであり、ｋは正の整数である。高々ｋの長さの任意のストリングＳに対して、Ｃ（Ｓ）はｎ個のストリングＳ1、Ｓ2、．．．、Ｓnのシーケンスであり、また復号化関数Ｄは、Ｓ'ij＝Ｓijなる少なくともｔ個の指標ｉjが存在すれば、ｘ（ｔ≦ｘ≦ｎ）個のストリングＳ'i1、Ｓ'i2、．．．、Ｓ'inの任意のセットからＳを再構成することができる。この機能対（Ｃ、Ｄ）は（ｎ、ｔ）誤り訂正コードと呼ばれる。境界ｋは暗黙的に仮定されるが、ｋよりも長い情報は長さｋの断片の連結として処理され、別々に符号化されるために、ここでの説明にはあまり関係しない。
【００１９】
照合子化フェーズ：
ユーザ端末１０に記憶される以前に、Ｉ（真正文書）は次のステップ（Ｆ１、Ｆ２及びＦ３）により照合子化される。
Ｆ１．ｆ（Ｉ）を計算する。ここでｆは上述の一方向ハッシュ関数である。例えば図３において、ハッシャ（hasher）２は公式ｆ（Ｉ）に従いファイルＩをハッシングする。
Ｆ２．Ｃ（ｆ（Ｉ））＝Ｓ1、Ｓ2、．．．、Ｓnを計算する。例えば図３では、これに対応してエンコーダが示される。
Ｆ３．システム内の各ロケーションｌiに、対応する断片Ｓiを分散する。例えば図３では、ハッシャ及び照合子化Ｓの出力がエンコーダ４に供給される。照合子断片Ｓ1、Ｓ2、．．．、Ｓnが、エンコーダの出力４−１、４−２、．．．、４−ｎ上に現れ、ロケーションｌ1、ｌ2、．．．、ｌnに配布される（図１参照）。
【００２０】
検証フェーズ：
後のステージでは、システム内のパーティがその情報の保全性を検証する必要がある度に、次のステップＶ１、Ｖ２及びＶ３が実行される。
Ｖ１．各ロケーションｌiから対応する照合子断片を検索する。ここで返却された断片をＳ'iで表す。図２及び図３を参照すると、Ｓ'1、Ｓ'2、．．．、Ｓ'xがそれぞれロケーションｌ1、ｌ2、．．．、ｌxから検索される。もちろん、ｎ個の照合子断片の内の任意のｘ個（ｔ≦ｘ≦ｎ）の照合子断片が検索される。Ｓ'1、Ｓ'2、．．．、Ｓ'xは説明の都合上選択されただけである。Ｉ'は検索された後に端末１０'に記憶されるものとする。
Ｖ２．Ｄ（Ｓ'1、Ｓ'2、．．．、Ｓ'x）及びｆ（Ｉ'）を計算する。ここでＩ'は真正文書Ｉとは異なりうる仮の真正文書である。図３ではテスト照合子断片Ｓ'1、Ｓ'2、．．．、Ｓ'xが、ロケーションｌ1、ｌ2、．．．、ｌxから受信されるように示される。また仮の真正文書Ｉ'がＳ3から受信されるように示される。検索されたテスト照合子断片は、次に、復号器３によりテスト照合子Ｓ'に復号化される。また仮の真正文書Ｉ'はハッシャ２に供給され、ここでテスト照合子に変換される。２つのテスト照合子が次に比較器６により比較される。この例では、ハッシャ、エンコーダ、復号器及び比較器は全てユーザ端末１０の１部である。
Ｖ３．比較器６によりＳ'とｆ（Ｉ'）とを比較し、両者が一致すると、仮の真正文書Ｉ'を真の真正文書Ｉとして受諾する。それ以外では、Ｉ'が改悪または変更されたものとして拒否する。
【００２１】
ここで、ｔ（またはそれ以上）個の検索断片Ｓ'が正しければ、ｆ（Ｉ）が正しく回復されることに気付かれよう。異なるＩ'によるＩの置換は、ｆの一方向特性により、Ｉと同一のハッシュ値を有するＩ'を見い出すことが極めて困難であるため、検出されることになる。
【００２２】
上述の本発明において使用される２つのコンポーネントは、一方向ハッシュ関数及び（ｎ、ｔ）誤り訂正コードである。本発明は、これらの関数の実現のために使用可能な任意の多数の実際的な方法を使用することができる。一方向ハッシュ関数には、ＭＤＣ関数（文献［３］B．O．Brachtal、D．Coppersmith、M．M．Hyden、S．M．Matyas、C．H．W．Meyer、 J．Oseas、S．Pilpel、M．Shillingによる米国特許第４９０８８６１号"Data authentication using modification detection codes based on a public one-way encryption function"（１９９０年３月１３日発行）。C．Meyer及びM．Schillingによる"Secure Program Load Using Manipulation Detection Code"、Proceedings of Securicom、１９８８年も参照のこと）、ＭＤ４（文献［６］R．L．Rivestによる"The MD4 Message Digest Algorithm"、Proc．Crypto'90参照）、及びデジタル署名標準（Digital Signature standard）に関連して使用される最近提案された"セキュア・ハッシュ標準（secure hash standard）"（文献［４］"Secure Hash Standard Draft"、NIST、１９９２年２月参照）などが含まれる。これらの関数の出力長は、情報Ｉの長さには依存しない。実際のアプリケーションでは、この長さは関数または要求される機密保護に依存して、６４または１２８ビットである。１２８ビット長は強力な一方向ハッシュ関数、すなわち、情報の作成者ですら以後その情報を改悪できない一方向ハッシュ関数で必要となる。上述の実際的な候補は、この種のものであると思われる。（一方向ハッシュ関数の強弱の違いについては、文献［１］を参照されたい）。
【００２３】
（ｎ、ｔ）誤り訂正コードに関しては、これらの関数は誤り訂正コードの理論から既知である（文献［２］R．Blahutによる"Theory and Practice of Error Control Codes"、Addison-Wesley、１９８４年、参照）。
【００２４】
本発明の提案された方法は、任意のコンピュータ・システムにおいて使用可能であるが、特に、情報が不許可の変更に対して保護されなければならず、同時にシステム内の多くのパーティによりアクセスされる必要のある分散コンピュータ・システムにおいて使用される。本方法はそれ自身では情報の変更を回避することはできないが、こうした変更を検出することができる。
【００２５】
図４は、上述の本発明の初期化フェーズを表す流れ図である。上述のように、ステップ３１乃至３４は、一方向ハッシュ関数の適用により真正文書をハッシングし、照合子を生成し、照合子をｎ個の照合子断片に符号化し、最後に照合子断片をｎロケーションに分散する様子を示す。
【００２６】
図５は、上述の本発明の検証フェーズを表す流れ図である。ステップ４１乃至４９は、仮の真正文書Ｉ'を受信し、後者の文書に一方向ハッシュ関数を適用し、ロケーションから少なくとも最小数の照合子断片を検索し、それらの照合子断片をテスト照合子に復号化し、テスト照合子ＳをＳ'と比較し、最後にその比較結果にもとづき、仮文書を真正文書として受諾または拒否する様子を示す。
【００２７】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００２８】
（１）  真正文書の保全性を検証する方法であって、
可能な将来の検証のために前記真正文書内のオリジナル情報を照合子化するときに、第１のユーザ端末装置が、
ａ）一方向ハッシュ関数を使用して前記オリジナル情報をオリジナル照合子にハッシングするステップと、
ｂ）前記オリジナル照合子を複数のｎ個のオリジナル照合子断片Ｓ１、Ｓ２、・・・、Ｓｎに符号化するステップであって、前記符号化は符号化関数を用いて行い、前記オリジナル照合子断片の夫々は前記オリジナル照合子と異なる、前記符号化するステップと、
ｃ）前記オリジナル照合子断片の各々をｎ個のロケーションＩ１、Ｉ２、・・・、Ｉｎに配布するステップであって、前記ロケーションの各々は前記オリジナル照合子断片の少なくとも１つを受信する、前記配布するステップと、
前記真正文書であるとされかつテスト文書の保全性を検証するときに、前記第１のユーザ端末装置又は前記第１のユーザ装置と異なる第２のユーザ端末装置が、
ｄ）前記オリジナル照合子断片であるとされる任意のｘ個のテスト照合子断片Ｓ’１、Ｓ’２、・・・、Ｓ’Ｘを複数のロケーションＩ１、Ｉ２、・・・、ＩＸ（ｎ／２＜ｘ≦ｎ）から検索するステップと、
ｅ）前記ｘ個のテスト照合子断片を第１のテスト照合子に復号化するステップであって、前記復号化は前記符号化関数の対である復号化関数を用いて行う、前記復号化するステップと、
ｆ）前記ハッシュ関数を使用して前記テスト文書内のテスト情報を第２のテスト照合子にハッシングするステップと、
ｇ）前記第１のテスト照合子を前記第２のテスト照合子と比較し、そして前記第１のテスト照合子が前記第２のテスト照合子に等しいときに、前記テスト文書を前記真正文書であるとして受諾するステップと、
を含む、方法。
（２）  前記ロケーションの各々がメモリ・ロケーションである、（１）に記載の方法。
（３）  前記オリジナル照合子の前記符号化が、誤り訂正符号化プロシージャである、（１）に記載の方法。
（４）  真正文書の保全性を検証する装置であって、
可能な将来の検証のために前記真正文書内のオリジナル情報を照合子化するために、第１のユーザ端末装置が、
ａ）一方向ハッシュ関数を使用して前記オリジナル情報をオリジナル照合子にハッシングするハッシャと、
ｂ）前記オリジナル照合子を複数のｎ個のオリジナル照合子断片Ｓ１、Ｓ２、・・・、Ｓｎに符号化するエンコーダであって、前記符号化は符号化関数を用いて行い、前記オリジナル照合子断片の夫々は前記オリジナル照合子と異なる、前記エンコーダと、
ｃ）前記オリジナル照合子断片の各々を、前記第１の装置に接続されたｎ個のサーバＩ１、Ｉ２、・・・、Ｉｎに分散する手段であって、前記サーバの各々は前記オリジナル照合子断片の少なくとも１つを受信する、前記分散する手段と、
を含み、
前記真正文書であるとされかつテスト文書の保全性を検証するために、前記第１のユーザ端末装置又は前記第１のユーザ装置と異なる第２のユーザ端末装置が、
ｄ）前記オリジナル照合子断片であるとされる任意のｘ個のテスト照合子断片Ｓ’１、Ｓ’２、・・・、Ｓ’Ｘを複数の前記サーバＩ１、Ｉ２、・・・、ＩＸ（ｎ／２＜ｘ≦ｎ）から検索する手段と、
ｅ）前記ｘ個のテスト照合子断片を第１のテスト照合子に復号化する手段であって、前記復号化は前記符号化関数の対である復号化関数を用いて行う、前記復号化する手段と、
ｆ）前記ハッシュ関数を使用して前記テスト文書内のテスト情報を第２のテスト照合子にハッシングする手段と、
ｇ）前記第１のテスト照合子を前記第２のテスト照合子と比較し、そして前記第１のテスト照合子が前記第２のテスト照合子に等しいときに、前記テスト文書を前記真正文書であるとして受諾する比較手段と、
を含む、前記装置。
（５）  複数のサーバと、前記サーバに接続された少なくとも１つのユーザ端末を有するコンピュータ・システムにおいて、真正文書の保全性を検証する方法であって、
可能な将来の検証のために前記真正文書内のオリジナル情報を照合子化するときに、第１のユーザ端末装置が、
ａ）一方向ハッシュ関数使用して前記オリジナル情報をオリジナル照合子にハッシングするステップと、
ｂ）前記オリジナル照合子を複数のｎ個のオリジナル照合子断片Ｓ１、Ｓ２、・・・、Ｓｎに符号化するステップであって、前記符号化は符号化関数を用いて行い、前記オリジナル照合子断片の夫々は前記オリジナル照合子と異なる、前記符号化するステップと、
ｃ）前記オリジナル照合子断片の各々をｎ個のサーバＩ１、Ｉ２、・・・、Ｉｎに配布するステップであって、前記サーバの各々は前記オリジナル照合子断片の少なくとも１つを受信する、前記配布するステップと、
前記真正文書であるとされかつテスト文書の保全性を検証するときに、前記第１のユーザ端末装置又は前記第１のユーザ装置と異なる第２のユーザ端末装置が、
ｄ）前記オリジナル照合子断片であるとされる任意のｘ個のテスト照合子断片Ｓ’１、Ｓ’２、・・・、Ｓ’Ｘを複数のサーバＩ１、Ｉ２、・・・、ＩＸ（ｎ／２＜ｘ≦ｎ）から検索するステップと、
ｅ）前記ｘ個のテスト照合子断片を第１のテスト照合子に復号化するステップであって、前記復号化は前記符号化関数の対である復号化関数を用いて行う、前記復号化するステップと、
ｆ）前記ハッシュ関数を使用して前記テスト文書内のテスト情報を第２のテスト照合子にハッシングするステップと、
ｇ）前記第１のテスト照合子を前記第２のテスト照合子と比較し、そして前記第１のテスト照合子が前記第２のテスト照合子に等しいときに、前記テスト文書を前記真正文書として受諾するステップと、
を含む、前記方法。
（６）  前記オリジナル文書が前記サーバのメモリに記憶される、（５）に記載の方法。
（７）  前記文書がコンピュータ・プログラムである、（５）に記載の方法。
（８）  前記文書が実行可能なコンピュータ・コードである、（５）に記載の方法。
（９）  前記文書が複製されて、前記文書の多数のコピーが前記コンピュータ・システムの前記多数のユーザ端末内に記憶される、（５）に記載の方法。
（１０）  前記文書が多数のパーティションに区分化され、前記多数のパーティションの各々が前記多数のユーザ端末に各々記憶される、（５）に記載の方法。
【００２９】
【発明の効果】
以上説明したように、本発明によれば、機密保護の必要がなく、より少ない資源において真正の文書の保全性を検証する方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】本発明による照合子断片の分散を示す単純なネットワーク・トポロジを表す図である。
【図２】本発明による複数の照合子断片の検索を示す単純なネットワーク・トポロジを表す図である。
【図３】本発明のハードウェアの実施例を表す図である。
【図４】本発明の初期化フェーズの表す流れ図である。
【図５】本発明の検証フェーズを表す流れ図である。
【符号の説明】
２  ハッシャ
３  復号器
４  エンコーダ
６  比較器
１０、１０'  ユーザ端末
２０  サーバ
【図１】
0003964941.tif 000002
【図２】
0003964941.tif 000003
【図３】
0003964941.tif 000004
【図４】
0003964941.tif 000005
【図５】
0003964941.tif 000006