📘
"How to Time-stamp a digital document"の和訳

2025/06/22に公開
原文はこちら→https://link.springer.com/article/10.1007/BF00196791
すべてのテキスト、音声、画像、映像の文書が、容易に変更可能なメディアにデジタル形式で保存される世界が到来するという見通しから、文書がいつ作成されたか、あるいは最後に変更されたかをどのように証明するかという問題が浮上する。

問題は、媒体ではなくデータにタイムスタンプを押すことである。

我々は、このような文書のデジタルタイムスタンプのための計算可能で実用的な手順を提案し、たとえタイムスタンプサービスの共謀があったとしても、ユーザーが自分の文書をバックデートすることも、フォワードデートすることも不可能にする。

我々の手順は、文書自体の完全なプライバシーを維持し、タイムスタンプサービスによる記録保持を必要としない。

キーワード タイムスタンプ、ハッシュ
虚偽を暴き、真実を明るみに出すこと。

年老いたものに時の刻印を押すこと。

朝を起こし、夜を見張ること。

過ちを犯した者が正しさを取り戻すまで、過ちを犯すこと。

『ルクレースの陵辱』941行
はじめに

多くの場面で、文書が作成された日や最後に変更された日を証明する必要がある。

例えば、知的財産権の問題では、発明者が特許取得可能なアイデアを最初に文書化した日付を確認することが、競合するクレームに対する優先権を確立するために極めて重要な場合がある。

科学的なアイデアのタイムスタンプを押す方法として認められているのは、実験ノートに毎日自分の作業内容を記入することである。

日付の記入は、空白のページを作らず、ノートに次々と記入していく。

ノートには連番が振られ、ページが縫い付けられているため、痕跡を残さずに記録を改ざんすることは困難である。

また、公証人が定期的に押印したり、会社の管理者が確認・署名したりすれば、クレームの有効性はさらに高まります。

発明者のアイデアの先行性が後に争われた場合、手帳という物的証拠と確立された手続きの両方が、ある日またはそれ以前にそのアイデアがあったという発明者の主張を立証するのに役立つ。

タイムスタンプを押す方法は他にもある。

例えば、自分宛ての手紙を未開封のまま郵送することができる。

こうすることで、同封された手紙が封筒に記された消印の時刻以前に作成されたことを確実にすることができる。企業は、社内文書の信頼性を高めるために、より手の込んだ手続きを通常の業務に組み込んでいる。

たとえば、記録を複数の担当者が扱うようにし、ある担当者による文書の改ざんが別の担当者に見破られるようにするなどの方法である。

しかし、これらの方法はすべて2つの前提の上に成り立っている。

第一に、改ざんの兆候を見つけるために記録を検査できること。第二に、文書を閲覧するもう一人の当事者がいて、その人物の完全性や公平性が主張を保証していると見なされることである。

私たちは、デジタル形式のみで作成・保存される文書の場合、こうした前提に重大な疑問が生じると考えている。

というのも、電子的なデジタル文書は改ざんが非常に容易であり、その変更が物理的媒体に痕跡を残す必要がないからである。

必要なのは、次の2つの性質を持つデジタル文書のタイムスタンプ方法である。

第一に、データが表示される媒体の特性に依存することなく、データそのものにタイムスタンプを押す方法を見つけなければならない。

第二に、実際のものとは異なる時刻とデータで文書にスタンプを押すことは不可能でなければならない。

本稿の目的は、タイムスタンプ問題に対する数学的に健全で、計算上実用的な解決策を紹介することである。

以下の節では、まず、この問題に対する素朴な解決策であるデジタル貸金庫について考える。

これは、従来のタイムスタンプ方法に見られるような、デジタルタイムスタンプに関連するさらなる困難を強調するという教育的な目的を果たすものである。

この素朴な解決策に改良を加えていくことで、最終的にデジタル・タイムスタンプを実装する実用的な方法が導き出される。
設定

この問題の設定は、個人、異なる会社、または会社内の部門を代表するユーザーの分散ネットワークである。

各クライアントは一意の識別番号を持つ。

タイムスタンプ問題の解決策にはいくつかの部分がある。

クライアントが文書にタイムスタンプを押すことを希望したときに、直ちに実行される手順がある。

この手続きが正しく行われたことをクライアントが検証する方法が必要である。

また、文書のタイムスタンプの有効性に対する第三者からの異議申し立てに対応する手続きも必要である。

あらゆる暗号問題と同様に、タイムスタンプ方式によって達成される安全性を正確に特徴付けることは微妙な問題である。

タイムスタンプ問題に対する良い解決策とは、スキームの利用者の計算能力、計算問題の複雑さ、そして場合によっては利用者の信頼性についての合理的な仮定の下で、偽のタイムスタンプを生成することが困難または不可能なものである。当然ながら、必要な仮定は弱ければ弱いほどよい。
素朴な解決策

素朴な解決策、「デジタル貸金庫」は次のように機能する。

タイムスタンプが必要な文書がある場合、クライアントはその文書をタイムスタンプサービス（TSS）に送信する。

TSSは、文書を受信した日時を記録し、文書のコピーを保管する。

クライアントの文書の完全性が問われることがあれば、TSSが保管するコピーと比較することができる。

両者が同一であれば、TSSの記録にある日付以降に文書が改ざんされていない証拠となる。

この手順は実際、デジタル文書のタイムスタンプに関する中心的な要件を満たしている。

しかし、この方法にはいくつかの懸念がある：

プライバシー。この方式では、2つの点で文書のプライバシーが損なわれる。つまり、文書が送信されている間に第三者が盗聴する可能性があることと、送信後はTSS自身が無期限に利用できることである。

したがって、クライアントは自分が直接管理している文書のセキュリティだけでなく、TSSにある文書のセキュリティについても心配しなければならない。

帯域幅とストレージ。タイムスタンプのために文書を送信するのに必要な時間と、TSSで必要なストレージの量は、タイムスタンプされる文書の長さに依存する。

したがって、大きな文書のタイムスタンプに必要な時間と費用は、法外なものになる可能性がある。

無能。文書のTSSコピーは、TSSへの送信中に破損する可能性があり、TSSに到着したときに誤ったタイムスタンプが押される可能性があり、あるいはTSSに保管されている間に破損したり完全に紛失したりする可能性がある。

このような事態が発生した場合、クライアントのタイムスタンプ請求は無効となります。

信頼。このスキームでは、TSSがクライアントと結託して、実際の日時とは異なる日時の文書にタイムスタンプを押したと主張することを防ぐことはできない。

次のセクションでは、上記の最初の3つの懸念に対処する解決策を説明する。

最後の問題である「信頼」については、次のセクションで個別に詳しく扱う。
信頼されたタイムスタンプサービス

本セクションでは、TSSが信頼されていると仮定し、上記の素朴な解決策に対する2つの改良点について述べる。

4.1. ハッシュ

最初の単純化は、暗号的に安全な無衝突ハッシュ関数群を利用することである。

これは関数hのファミリーである： 任意の長さのビット列を固定長lのビット列に圧縮する関数

h: \{0, 1\}^* \to \{0, 1\}^tの族であり、以下の性質を持つ：
関数hは計算が容易であり、ランダムにファミリーのメンバーを選ぶことは容易である。
これらの関数hが与えられたとき、h(x) = h(x’)を満たす異なる文字列x, x’の組を見つけることは計算上不可能である。(このような組をhの衝突と呼ぶ）。

このような関数の実用的な重要性は以前から知られており、研究者たちは多くのスキームでこの関数を使用してきた；例えば、[7]、[15]、[16]を参照。

Damgardは、一方向の 「爪のない 」順列が存在するという仮定に基づいて、最初の正式な定義とその存在の構成的証明を行った[4]。

このためには、どのような「一方向グループ作用」でも十分である [3]。

NaorとYungは「普遍的一方向ハッシュ関数」という同様の概念を定義した。この関数は、上記の2つ目の条件の代わりに、文字列xが与えられたときに、ランダムに選ばれたhに対してh(x)=h(x')を満たす別の文字列x' ≠ xを計算することが計算上不可能であるという少し弱い条件を満たす。

彼らは、1対1の一方向関数が存在するという仮定のもとで、このような関数を構成することができた[17]。

Rompelは最近、もし一方向性関数が存在するならば、そのような関数が存在することを示した[20]。

これら2種類の暗号ハッシュ関数の違いについては、以下のセクション6.3を参照のこと。

ハッシュ関数の実用的な実装もあり、例えばRivestの実装[19]はそれなりに安全だと思われる。

ハッシュ関数は次のように使う。

クライアントは文書xをTSSに送信する代わりに、ハッシュ値h(x) = yを送信する。

これにより、帯域幅の問題とストレージ要件が大幅に削減され、プライバシーの問題も解決される。

タイムスタンプの実装の設計目標によっては、全員が使用する単一のハッシュ関数があるかもしれないし、ユーザーごとに異なるハッシュ関数があるかもしれない。

本稿の残りの部分では、タイムスタンプのハッシュ値y--固定長のランダムに見えるビット列--について述べる。

タイムスタンプを検証する手順の一部は、h(x) = yを満たす前画像文書xを作成することである。

4.2. 署名

2つ目の改良点は、デジタル署名を利用することである。非公式には、署名スキームとは、当事者（署名者）が署名者を一意に識別する方法でメッセージにタグを付けるためのアルゴリズムである。

デジタル署名はRabin [18]とDiffie and Hellman [7]によって提案された。

多くの著者による長い一連の論文の後、Rompel [20]は、Goldwasserら [10]によって最初に定義された非常に強い安全性の概念を満たす署名スキームを設計するために、一方向性関数の存在を利用できることを示した。

安全な署名スキームが利用できる場合、TSSはハッシュ値を受け取ると、日付と時刻を付加し、この複合文書に署名してクライアントに送信する。

署名をチェックすることで、クライアントは、TSSが実際にリクエスト を処理したこと、ハッシュが正しく受信されたこと、正しい時刻が含まれているこ とを保証される。

これにより、TSS側の現在および将来の無能の問題に対処でき、TSSが 記録を保存する必要性を減らすことができる。
2つのタイムスタンプ方式
しかし、誰が衛兵自身を守るのか？

Juvenal, c. I00 A.D.

しかし、誰が衛兵自身を守るのか？
これまで説明してきたことは、任意の長さのデジタル文書にタイムスタンプを押すための実用的な方法だと考えている。しかし、署名もハッシュ関数の使用も、タイムスタンプ・サービスが偽のタイムスタンプを発行することを防ぐものではありません。

理想的には、TSSがどんなに不誠実であっても、TSSが証明する時刻は常に正しいものであり、誤ったタイムスタンプを発行しようとしても発行できないことを保証するメカニズムが望ましい。

偽のタイムスタンプを作成できないように、タイムスタンプの手順を指定するのは難しいように思えるかもしれない。

結局のところ、文書xとあるタイミング情報\tauを入力として与えられたアルゴリズムAの出力が、xの正当なタイムスタンプとなるビット列c = A(x,\tau)であった場合、ある時間後に偽造者が同じタイミング情報\tauを計算し、同じ証明書cを生成するためにAを実行することを、何が防ぐのだろうか？

この疑問は、たとえAが確率的アルゴリズムであっても同じである。

私たちの課題は、一般的に信頼された当事者が存在しない場合に、信頼されたTSSの行動をシミュレートする問題とみなすことができる。

2つの異なるアプローチがあり、それぞれが解決策を導く。

第一のアプローチは、中央集権的だが信頼できない可能性のあるTSSに、偽のタイムスタンプを生成するのが困難なように、本物のタイムスタンプを生成するよう制約することである。

第二のアプローチは、サービスの利用者間で必要な信頼を分散させることである。

このどちらかがまったく可能であることは明らかではない。

5.1. リンク

最初の解決策は、タイムスタンプを要求するクライアントのシーケンスと、彼らが提出するハッシュは、事前に知ることができないことを観察することから始まる。

従って、もし署名された証明書に以前の一連のクライアントの要求のビットが含まれていれば、タイムスタンプがこれらの要求の後に発生したことがわかる。

しかし、証明書に以前の文書からのビットを含めるという要件は、別の方向で時間を制約するという問題を解決するために使用することもできる。なぜなら、タイムスタンプを発行する会社は、現在の要求が手元にない限り、後の証明書を発行することができないからである。

このリンクスキームの2つの変形を説明する。1つ目は少し単純で、私たちの主要なアイデアを強調するもので、2つ目は実際には好ましいかもしれないものである。

どちらの亜種でも、TSSは衝突のないハッシュ関数(Hと表記する)を利用する。

これは、クライアントがタイムスタンプを押したいドキュメントのハッシュ値を生成するために、クライアントがハッシュ関数を利用することに加えて行われる。

具体的には、タイムスタンプ要求は、lビット文字列y(おそらく文書のハッシュ値)とクライアント識別番号IDで構成される。

TSSが使用する署名手順を表すためにσ(.)を使用する。

TSSは、署名された連番のタイムスタンプ証明書を発行する。

クライアントからのリクエスト(Y_n, ID_n)に対して、TSSは以下の2つの処理を行う：

1.TSSはクライアントに署名付き証明書s = σ(C_n)を送る。

C_n=(n,t_n,ID_n,y_n; L_n)は、シーケンス番号n、時刻t_n、クライアント番号ID_n、リクエストのハッシュ値y_n、および以前に発行された証明書に由来する特定のリンク情報から構成される： L_n = (t_{n-1}, ID_{n-1}, Y_{n-1}, H(L_{n-1}))。

2.次のリクエストが処理されると、TSSはクライアントに、その次のリク エストの識別番号ID_{n+1}を送る。

TSSからsとID_{n+1}を受け取った挑戦者は、sが正しい証明書の有効な署名であること、すなわち、正しい時刻tを含む正しい形式(n, t, ID_n, y_n; L_n)の署名であることを確認する。

自分のタイムスタンプが押された文書xが後でチャレンジされた場合、挑戦者は まずタイムスタンプ(s, ID_{n+1})が正しい形式(sが確かにxのハッシュを含む証明書の 署名である)であることを確認する。

クライアントがTSSと結託していないことを確認するため、挑戦者はクライアントID_{n+1}を呼び出し、タイムスタンプ(s', ID_{n+2})を生成するよう求めることができる。

これには、リンク情報L_{n+1}に彼女のハッシュ値y_nのコピーを含む証明書の署名

s' = \sigma(n + 1, t_{n+1}, ID_{n+1}, y_{n+1}; L_{n+1})が含まれる。このリンク情報は、彼女のリンク情報L_nのイメージH(L_n)を含むことでさらに認証される。

特に疑わしい挑戦者は、クライアントID_{n+2}を呼び出し、次のタイムスタンプを検証することができる。同様に、挑戦者はタイムスタンプの連鎖を遡り、クライアントID_{n-1}から始めることもできる。

なぜこのようにTSSが不正なタイムスタンプを作れないようにするのでしょうか？

まず、署名を使用することで、タイムスタンプを偽造する唯一の方法は TSSの協力を得ることである、という効果があることに注意。

しかし、TSSは文書をフォワードデートすることはできない。なぜなら、証明書には希望する時刻の直前のリクエストのビットが含まれていなければならないが、TSSはそれを受け取っていないからである。

TSSは、以前の時刻の偽のタイムスタンプを用意することで、文書をバックデイトすることは実行不可能である。なぜなら、問題の文書からのビットは、その以前の時刻の直後の証明書に埋め込まれなければならないが、これらの証明書はすでに発行されているからである。

さらに、新しい文書をすでに存在するタイムスタンプ証明書のストリームに正しく埋め込むには、ハッシュ関数Hの衝突を計算する必要がある。

したがって、唯一可能ななりすましは、予想される最も疑わしいチャレンジャーを使い果たすのに十分な長さの、偽のタイムスタンプの連鎖を用意することである。

今説明した方式では、クライアントはすべての証明書を保持しなければならない。この要件を緩和するために、このスキームの2つ目の変形では、各リクエスト を次のリクエストにリンクするだけでなく、次のk個のリクエストにリンクする。

TSSはn番目のリクエストに以下のように応答する：

1.上記と同様に、証明書C_nはC_n=(n,t_n,ID_n,y_n; L_n)の形式であり、ここでリンク情報

L_nはL_n=[(t_{n-k},ID_{n-k},Y_{n-k},H(L_{n-k})) ......(t_{n-1},ID_{n-1},Y_{n-1},H(L_{n-1}))]の形式である。

2.次のk個のリクエストが処理された後、TSSはクライアントにリスト(ID_{n+1}, ..., ID_{n+k})を送る。

このクライアントのタイムスタンプが正しい形式であることを確認した後、 疑わしい挑戦者は、次のk人のクライアントID_{n+i}のうちの誰かにタイムスタンプを作 成するよう求めることができる。

上記のように、彼のタイムスタンプは、チャレンジされたクライアントのリンク情報L_nのHによるハッシュを含むことによって認証された、チャレンジされたタイムスタンプ証明書C_nの関連部分のコピーをそのリンク情報L_{n+i}に含む証明書の署名を含む。

彼のタイムスタンプは、クライアント番号（ID_{n+i+1},...... ID_{n+i+k}）も含む。

挑戦者はこれらのクライアントにタイムスタンプを尋ねることができ、これは挑戦者が望む限り続けることができる。

クライアントがすべての証明書を保存するという要件を緩和するだけでなく、この第二の変形は、タイムスタンプ証明書の既存のストリームに新しいドキュメントを正しく埋め込むには、ハッシュ関数Hに対して、単なるペアワイズコリジョンではなく、同時にkワイズコリジョンの計算を必要とするという特性も持っている。

5.2. 分散信頼

このスキームでは、各ユーザーがメッセージに署名できるような安全な署名スキームがあり、 標準的な安全な擬似ランダム生成器Gがすべてのユーザーが利用可能であると仮定する。

擬似ランダム生成器とは、短い入力シードを任意の実行可能なアルゴリズムでランダムシーケンスと区別できない出力シーケンスに引き伸ばすアルゴリズムである。

このような生成器は、BlumとMicali [2]とYao [22]によって最初に研究された。

もう一度、クライアントがタイムスタンプしたいハッシュ値yを考える。

クライアントはyを擬似乱数生成器のシードとして使用し、その出力は標準的な方法でクライアント識別番号のkタプルとしてインタープリットすることができる：

G(y) = (ID_1, ID_2, ..., ID_k)。

クライアントは自分のリクエスト(y, ID)をこれらのクライアントに送る。

彼女はクライアントID_jから、時刻tを含む署名付きメッセージs_j = \sigma_j(t, ID, y)を受け取る。

彼女のタイムスタンプは[(y, ID), (s_1 . ... s_k)]からなる。

k 個の署名 s_j は、我々のクライアントや、挑戦者になりうる者によって簡単にチェックできる。

後のチャレンジに対応するために、それ以上の通信は必要ない。

なぜこのような署名のリストが、信憑性のあるタイムスタンプとなるのだろうか？

その理由は、このような状況では、不正な時刻のタイムスタンプ付き文書を作成する唯一の方法は、G(y)がタイムスタンプを偽造することに協力するk個のクライアントを挙げるように、ハッシュ値yを使用することだからである。

どの時点でも、不正を行う可能性のあるクライアントの割合が最大でも一定\epsilonである場合、この割合の中から協力者のみを含むk個のタプルG(y)を見つけるまでに試さなければならないシードyの期待数は\epsilon^{-k}となる。

さらに、Gが安全な擬似ランダム生成器であると仮定しているので、そのような都合の良い種yを見つけるのに、ランダムに選ぶより速い方法はない。

これは、ほとんどの実世界のシナリオにおいて、便利な値yにハッシュするもっともらしい文書を見つけるという、敵のさらなる問題を無視している。

この計算が実行不可能になるように、システム設計時にパラメータkを選択する必要がある。

破損しやすいクライアントの割合を非常に悲観的に見積もっても（\epsilonは9 0%）、kが法外に大きくなることはない。

この方式では、集中型TSSを使用する必要は全くない。

唯一の要件は、他のクライアントを任意に呼び出し、彼らから必要な署名を受け取ることが可能であることと、G(y)の出力をクライアントのkタプルとして標準的な方法で解釈できるように、クライアントの公開ディレクトリが存在することである。この方法の実用的な実装には、タイムスタンプ要求時にコンタクトできない クライアントに対するプロトコルの規定が必要である。

例えば、適切なk’<kの場合、システムは、G(y)で指定されたk個のクライアントのうちの任意のk’からの署名された応答を、yの有効なタイムスタンプとして受け入れるかもしれない(この場合、ランダムに協力者のセットを見つけるのと同じ低確率を達成するために、パラメータkのより大きな値が必要になるだろう)。

6. 備考

6.1. *トレードオフ

2つのスキームにはトレードオフがいくつかある。分散信頼スキームには、リクエストが行われたときにすべての処理が行われるという利点がある。

一方、リンクスキームでは、クライアントは証明書の第2部 を待つ間に短い遅延が発生する。

リンクスキームの関連する欠点は、少なくとも一部の当事者（クライアント、 あるいは、おそらくサーバー）に依存することである。

(クライアントまたはおそらくTSS)が証明書を保管することに依存することである。

分散信頼スキームは、システムに対してより大きな技術的要求をすることになる。

リンク方式は、前の要求と次の要求の時間の間で文書の時間を特定するだけなので、 タイミングが重要になる規模と比較して、比較的多くの文書がタイムスタンプのために 提出される設定に最も適している。

リンキングスキームの時間制約特性は、デジタル技術の使用に依存しないことは注目に値する。

6.2. *時間の制約

私たちの方式は、タイムスタンプのイベントを時間的に前方にも後方にも制約することを指摘したい。しかし、文書が作成されてからタイムスタンプが押されるまでの間にいくらかの時間が経過してもよいのであれば、どの方式も文書自体が作成された時間を前方に制約する以上のことはできない。

したがって、一般的に、タイムスタンプは、文書がバックデートされていないことの証拠としてのみ考慮されるべきである。

一方、タイムスタンプイベントを文書作成イベントの一部とすることができれば、この制約は双方向で成立する。

例えば、あるスイッチを通過する一連の電話会話を考えてみる。

このスイッチで次の呼び出しを処理するために、前の呼び出しからリンク情報を提供することを要求できる。同様に、通話が終了すると、リンク情報は次の通話に渡される。

このように、ドキュメント作成イベント(電話)には、タイムスタンプイベントが含まれるため、電話の時間を双方向で固定することができる。

同じ考え方が、株式取引や通貨交換などの連続した金融取引や、特定の物理的接続を介して行われる電子的相互作用のシーケンスにも適用できる。

6.3. 理論的考察

ここでは行わないが、Goldwasser and Micali I-9]、Goldwasser et al.[10]、Galil et al.[8]が様々な暗号タスクに対して行った定義に沿って、可能な限り強いタイムスタンプの安全性の正確な複雑性理論的定義を行うことを提案する。

タイムスタンプ方式は、偽のタイムスタンプを作ろうとする多項式に束縛された敵対者の成功確率が、十分に大きなpに対して1/pの任意の多項式よりも小さい場合、多項式的に安全である。

一方向のクローフリー置換が存在するという仮定の下で、リンク方式が多項式的に安全であることを証明できる。

また、一方向性関数が存在する（したがって、擬似ランダム生成器と安全な署名スキームが存在する）と仮定すれば、分散信頼スキームが多項式的に安全であることを証明できる。

セクション4.1では、「無衝突 」ハッシュ関数と 「普遍的一方向ハッシュ関数 」の違いについて述べた。

普遍的な一方向ハッシュ関数は、一方向関数の存在だけで十分である。

しかし、我々のタイムスタンプ方式の安全性を証明するためには、無衝突ハッシュ関数の定義によって提供される、ハッシュの衝突が起こりにくいという、より強力な保証が必要である。

現在知られている限りでは、これらの関数の存在を証明するためには、より強い複雑さの仮定--すなわち、クローフリー置換対の存在--が必要である。(暗号ハッシュ関数の理論的性質については、[5]と[6]も参照のこと）。

ユニバーサルな一方向ハッシュ関数は、安全な署名スキームを構築するために使用されたツールである。

より強力な前提が必要であることは、署名とタイムスタンプの違い、おそらく本質的な違いを示唆している。

安全な署名スキームの指示に従って正しく行動することは、署名者自身の利益となる（例えば、ある集合からランダムにハッシュ関数を選択するなど）。

一方、タイムスタンプの場合、不正な利用者や結託したTSSは、標準的な指示に従わない方が都合が良いと考えるかもしれない（例えば、衝突が発見しやすいようにハッシュ関数を選ぶなど）。

もし可能であれば、安全なタイムスタンプに必要な仮定を、一方向性関数が存在するという単純な仮定まで減らしたい。

複雑性に基づく暗号はすべて一方向性関数の存在を必要とする [121 [13]。

6.4. 実用的な考察

複雑性理論の領域から実用的な暗号システムの領域へと移行すると、新たな問題が発生する。

ある意味で、タイムスタンプは、他のアプリケーションよりも一方向性関数に重要な要求を課すことになる。

例えば、電子送金システムが認証のために一方向性関数に依存しており、その関数が破られた場合、破られる前に行われた送金はすべて有効である。

しかし、タイムスタンプの場合、ハッシュ関数が破られると、それ以前に発行されたタイムスタンプがすべて疑われることになる。

この問題に対する部分的な答えは、タイムスタンプは更新できるという観察から得られる。

タイムスタンプの実装が2つあり、最初の実装がまもなく破られると信じるに足る理由があるとする。

古い実装を使って発行された証明書は、新しい実装を使って更新できる。

古い実装を使用して作成されたタイムスタンプ証明書が、古い実装が壊れる前に新しい実装でタイムスタンプされることを考える。

古い実装が破られる前は、証明書を作成する唯一の方法は正当な手段によるものだった。

したがって、証明書自体に新しい実装でタイムスタンプを押すことで、その文書が新しいタイムスタンプが押された時点より前に存在していたという証拠だけでなく、元の証明書に記載された時点に存在していたという証拠も手に入れることができる。

考慮すべきもう一つの問題は、ハッシュの衝突を起こすだけでは、タイムスタンプ方式を破るには十分ではないということである。

むしろ、衝突につながる意味のある文書を見つけなければならない。

したがって、文書クラスの形式を指定することで、意味のある衝突を見つける作業を複雑にすることができる。

例えば、長さNバイトのすべての可能なビット列のうち、ASCIIのみのテキストの密度は(2^7/2^8)^ N、つまり1/2^Nである。

さらに悪いことに、許容可能な英語テキストの密度は、ネイティブスピーカーが判断する英語のエントロピーの推定値[21]によって上記のように制限される可能性がある。

この値はASCII文字あたりおよそ1ビットであり、(2^1/2^8)^N、つまり1/128^ Nの密度を与える。

有効な文書が入力空間にまばらに、そしておそらくランダムに分布している場合に、 衝突計算の難易度が増すことを定式化できるかどうかは、今後の研究に委ねたい。

同様に、k-wayリンクスキームが敵対者に衝突ペアではなくk-way衝突を計算することを要求するという事実は、ハッシュ関数に対する要求を緩和することに利用できるかもしれない。

また、入力空間の適切に制限された部分集合内の文字列間でk-way衝突が存在しないハッシュ関数が存在する場合、そのようなシステムの安全性は、もはや複雑性の仮定に依存しない。

7. 応用例

理論的に最良の（暗号的に安全な）ハッシュ関数、署名スキーム、および擬似ランダム ジェネレータを使用して、理論的に望ましい特性を持つタイムスタンプ・スキームを設計した。

これらの暗号ツールの実用的な実装が存在するため、我々のタイムスタンプ方式はいずれも、説明したように安価に実装することができる。

Rivestのような実用的なハッシュ関数は非常に高速で、ローエンドのPCでさえ動作する[19]。

どのような文書が安全なデジタルタイムスタンプの恩恵を受けるだろうか？

発明やアイデアの先行性を立証する文書にとって、タイムスタンプは明確な価値を持つ。

デジタル・タイムスタンプの特に望ましい特徴は、その内容を開示することなく知的財産の先行性を立証することを可能にすることである。

これは著作権法や特許法に大きな影響を与える可能性があり、ソフトウェアからコカ・コーラの秘法まで、あらゆるものに適用できる。

しかし、日付が、単に文書が改ざんされているか否かほど重要でない文書についてはどうだろうか。

このような文書も、次のような状況下では、タイムスタンプの恩恵を受けることができる。

ある文書を改ざんするのに必要な知識や動機が、その文書が作成されたずっと後まで存在しなかったことを立証できるとする。

例えば、毎日大量の文書を扱う会社があり、そのうちの何枚かが後に犯罪につながることが判明したとする。

その会社のすべての文書が、作成時に定期的にタイムスタンプが押されていたとすると、どの文書が犯罪につながり、どのように修正する必要があるかが明らかになったときには、その文書を改ざんするには遅すぎる。

私たちはこのような文書を「改ざん予測不可能文書」と呼んでいる。

多くのビジネス文書が改ざん予測不可能であることは明らかなようだ。

したがって、もしタイムスタンプがビジネスの確立された秩序に組み込まれるならば、多くの文書の信頼性を高めることができるだろう。

ビジネス文書に特に有用なバリエーションは、各文書に個別にタイムスタンプを押すのではなく、文書のログにタイムスタンプを押すことである。

例えば、1日に作成された各企業文書はハッシュ化され、そのハッシュ値が企業の日々の文書ログに追加される。

そして、営業日の終わりに、ログだけをタイムスタンプのために提出することができる。

こうすることで、各文書に個別にタイムスタンプを押す手間を省くことができ、しかも各文書の改ざんを検知することができる。

もちろん、デジタルのタイムスタンプはテキスト文書に限らない。

デジタル音声記録、写真、フルモーションビデオなど、あらゆるビット列にタイムスタンプを押すことができる。

これらの文書のほとんどは、改ざんが予測できない。

したがって、タイムスタンプは、オリジナルの写真とレタッチされた写真を区別するのに役立つ。

実際、写真、ビデオ、オーディオ録音にタイムスタンプ以上の信頼性を付加できるアルゴリズムによる「修正」を他に考えることは難しい。

8. まとめ

本稿では、デジタル形式のテキスト、オーディオ、ビデオ文書の利用が増加し、そのような文書が簡単に変更できるようになったことで、文書がいつ作成されたか、あるいは最後に変更されたかをどのように証明するかという新たな問題が生じていることを示した。

文書がいつ作成されたのか、あるいは最後に変更されたのかを証明するにはどうすればいいのだろうか？

第一に、文書が記録されている物理的媒体を前提とせず、文書の実際のビットにタイムスタンプを押さなければならない。第二に、タイムスタンプの日時は偽造可能であってはならない。

我々はこの問題に対して2つの解決策を提案した。

どちらも一方向性ハッシュ関数を使うもので、その出力は実際の文書の代わりに処理される。

これらの解決策は、日付と時刻を偽造できないようにする方法だけが異なる。

前者では、TSSに提出された文書のハッシュがリンクされ、ある文書のリンクを記録した証明書が、その文書の上流と下流の両方で他のクライアントに配布される。

2つ目の解決策では、クライアントプールの複数のメンバーがハッシュをタイムスタンプしなければならない。

このメンバーは、文書自体のハッシュをシードとして使用する擬似ランダム生成器によって選ばれる。

このため、与えられたハッシュをタイムスタンプするクライアントとしないクライアントを意図的に選択することは不可能である。

二つ目の方法は、集中型TSSを全く必要とせずに実装できる。

最後に、タイムスタンプを、作成時刻そのものが重要な問題ではない文書の真正性を高めるために拡張できるかどうかを検討した。

これは、我々が 「改ざん予測不可能 」と呼ぶ大規模な文書クラスの場合である。

さらに、純粋にアルゴリズム的なスキームでは、タイムスタンプが提供する以上の信頼性を文書に付加することはできないと推測する。

謝辞

Donald Beaver、Shimon Even、George Furnas、Burt Kaliski、Ralph Merkle、Jeff Shrager、Peter Winkler、Yacov Yacobi、Moti Yungとの有益な議論に感謝する。

参考文献

省略
Discussion
