【手続補正書】
【提出日】平成18年8月4日(2006.8.4)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
時刻証明装置1は、コンピュータネットワーク4を介して時刻情報提供装置2、クライアント装置3ｉ、および監査装置5とデータを送受信する送受信部11、複数のクライアント装置3ｉからの時刻証明要求として送信されたメッセージ・ダイジェスト（デジタル・データから作成されるハッシュ値）を二分木を用いてまとめる時刻証明要求まとめ部12、受理証明書を作成する際に時刻情報提供装置2から時刻情報を取得する時刻情報取得部13、時刻証明要求まとめ部12でまとめられたメッセージ・ダイジェストに対して時刻情報取得部13で取得した時刻情報を付して受理証明書を作成する時刻証明作成部14、定期的にメディア等40に受理証明書に関する情報を公表する時刻証明公表部15、時刻証明作成部14で作成された受理証明書を記憶する受理証明書記憶部16、および監査装置5に送信する監査情報を作成する監査情報作成部17を具備している。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
あるクライアント装置3ｉから送信されたメッセージ・ダイジェストがh(0,5)であるとき、このリーフに割り当てられるハッシュ値h (0,5)からルート値H(＝h(4,0))を求めるには、h(0,5)にh(0,4)を左から連接して、ハッシュ値h1を計算し、該ハッシュ値h1にh(1,3)を右側から連接してハッシュ値h2を計算し、該ハッシュ値h2にh(2,0)を左側から連接してハッシュ値h3を計算し、さらに該ハッシュ値h3にh(3,1)を右側から連接してハッシュ値h4（＝H）を計算すればよい。即ち、H＝h(h(h(2,0)‖h(h(h(0,4)‖h(0,5))‖h(1,3)))‖h(3,1))である。ここで、例えば、h(0,4)を左（右）側から連接する場合を（L（R）,h(0,4)）のように表し、h(0,5)の値から二分木のルート値Hを計算するのに、必要なデータの集合を連接する方向、および連接する順序も含めて表すと、（（L, h(0,4)）、（R, h(1,3)）、（L, h(2,0)）、（R, h(3,1)））となるが、以後、このデータの集合を、第１次二分木におけるh(0,5)の１次補完情報とよぶ。ここで、補完情報とは、二分木のルート値を計算するのに必要な自己の値以外のノード値の集合（ノードの位置情報も含む）をいい、第１次二分木における補完情報を１次補完情報、第２次二分木における補完情報を２次補完情報という。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
このようにして、第１次二分木が構成され、ルート値 H が計算されると、次に各ラウンドで計算されたルート値Hをもとに第２次二分木が構成される。図3に示す第２次二分木は、予め定められた一定期間（上述したように例えば、1週間など）に1つ用意されるものであり、第２次二分木のリーフ（レベル0）には、第１次二分木のルート値 H を経時的に順次左側から割り当てるようになっている。尚、第１次二分木とは異なり、第２次二分木は固定的な構成となっているが（例えば、1ラウンドが1秒、公表サイクルが1週間の場合には、約60万個（60×60×24×7）のリーフを有する第２次二分木が構成される）、以下においては、図3に示すように、16のリーフを有する第２次二分木の場合について説明する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
時刻証明作成部14は、このようにして作成された第１次二分木のルート値H、第１次二分木のルート値Hの識別番号（第２次二分木のリーフを一意に特定できる番号）、それぞれのラウンドに付与される時刻（例えば、1秒間隔で付される）ｔ、１次補完情報 HK1、および２次補完情報 HK2 を含む受理証明書 TSC(H,t)を作成し、クライアント装置3ｉに送信するようになっている。尚、２次補完情報 HK2 に関しては、即時に取得できる２次補完情報（以後、即時２次補完情報という）と対象となる一定期間が終了後に取得できる２次補完情報（以後、後付２次補完情報という）の双方があるが、受理証明書 TSC(H,t) が作成される段階においては、即時２次補完情報だけが送信されるものであり、後付２次補完情報は、対象となる一定期間が終了後に送信されるものである。例えば、図3の具体例においては、M(0,5)にとって、M(2,0)、M(0,4)は即時２次補完情報であるが、M(1,3)、M(3,1)は後付２次補完情報である。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８３
【補正方法】変更
【補正の内容】
【００８３】
時刻証明公表部15は、時刻証明要求まとめ部12で作成された第２次二分木のルート値 RH を定期的（上述した一定期間ごと）にメディア等40に公表するものである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１０６
【補正方法】変更
【補正の内容】
【０１０６】
以上の検証それぞれにおいて、検証に成功すれば、受理証明書TSC(H,t)が改ざんされていないことに加えて、当該の受理証明書TSC(H,t)に付された時刻の真正性についても確認することができる（ステップＳ52）。一方、いずれかの検証に失敗すれば、受理証明書 TSC(H,t) が改ざんされていること、もしくは受理証明書TSC(H,t)に付された時刻が不正であることを確認することができる（ステップＳ53）。そして、時刻証明検証部53は、この検証結果を送受信部51を介してクライアント装置3ｉに送信する（ステップS54,Ｓ55）。これにより、メディア等公表前においても、時刻証明装置1が発行した受理証明書 TSC(H,t) を的確に検証でき、時刻情報やデータの真正性を明確にすることができる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１５９
【補正方法】変更
【補正の内容】
【０１５９】
監査装置6は、コンピュータネットワーク4を介して時刻証明装置1およびクライアント装置203ｉとデータを送受信する送受信部51、時刻証明装置1から送信された監査情報を記憶する監査情報記憶部52、およびこの監査情報をWeb上に公開する監査情報公開部63を具備している。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１７４
【補正方法】変更
【補正の内容】
【０１７４】
時刻証明装置7は、コンピュータネットワーク4を介して監査装置8、クライアント装置303ｉ、および時刻タグシステム800とデータを送受信する送受信部11、受理証明書に使用する時刻タグτを時刻タグシステム800から取得する時刻タグ情報取得部73、複数のクライアント装置303ｉからの時刻証明要求として送信されたメッセージ・ダイジェスト（デジタル・データから作成されるハッシュ値）および時刻タグ情報取得部73で取得した時刻タグτを二分木を用いてまとめる時刻証明要求まとめ部72、受理証明書を作成する際に時刻情報提供装置2から時刻情報を取得する時刻情報取得部13、時刻証明要求まとめ部72でまとめられたメッセージ・ダイジェストに対して時刻情報取得部13で取得した時刻情報を付して受理証明書を作成する時刻証明作成部14、定期的にメディア等40にデータを公表する時刻証明公表部15、時刻証明作成部14で作成された受理証明書を記憶する受理証明書記憶部16、および監査装置8に送信する監査情報（監査用受理証明書）を作成する監査情報作成部77を具備している。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１８９
【補正方法】変更
【補正の内容】
【０１８９】
次に、監査装置8の検証動作について説明する。監査装置8が、送受信部81を介して監査用受理証明書TSC'(H',t') を受信すると、時刻証明公表部83は、この監査用受理証明書TSC'(H',t') を受信したときの時刻 t1を取得する（ステップＳ81，Ｓ82）。尚、この時刻 t1は、監査装置8が参照する時計から取得するものであるが、この時計はある一定程度の正確性が保たれているものである。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０２２９
【補正方法】変更
【補正の内容】
【０２２９】
図40に監査用受理証明書 TSC'(H,t)の構成を示す。図40に示すように監査用受理証明書 TSC'(H', t')は、受理証明書TSC(H, t)と同様に構成されるが、受理証明書においては当該のクライアント装置303aiから送信されたメッセージ・ダイジェストを置くフィールドに、時刻タグτを置く点が受理証明書とは異なる点である。尚、図40は第１次二分木のリーフに割り付ける値として、クライアント装置303aiから送られたメッセージ・ダイジェストあるいは取得した時刻タグをそのまま用いた場合の監査用受理証明書TSC'(H, t)の構成示すものであるが、受理証明書TSC(H,t)の場合と同様に、第１次二分木のリーフに、クライアント装置303a iから送られたメッセージ・ダイジェストあるいは時刻タグのキー付ハッシュ値を割り付けることも可能であり、この場合の監査用受理証明書TSC'(H,t)の構成は、図41に示す通りである。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０２５０
【補正方法】変更
【補正の内容】
【０２５０】
まず、監査装置9の検証動作について説明する。監査装置9が、送受信部81を介して監査用受理証明書TSC'(H',t')を受信すると、時刻証明検証部93は、この監査用受理証明書TSC'(H',t')を受信したときの時刻 t1を取得する（ステップＳ101、Ｓ102）。尚、この時刻 t1は、監査装置9が参照する時計から取得するものであるが、この時計はある一定程度の正確性が保たれているものである。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０２６９
【補正方法】変更
【補正の内容】
【０２６９】
尚、公表装置の機能を、監査装置に組み込んで、監査装置が定期的に受理証明書に関する情報を公表するようにしてもよい。この場合においては、監査装置を利用すれば、いかなるときにおいても、利用者装置は受理証明書の検証をすることが可能となる。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０２７２
【補正方法】変更
【補正の内容】
【０２７２】
高さｋの二分木は、レベル0からレベルｋまでのノードで構成されるが、レベルｊ（ｊ＝0,1,…,k）のノードの数は、2(k-j)であるので、レベルｊ、番号ｉのノードを（ｊ,ｉ）と表すことにすると、ｉ＝0,1,…,2(k-j)-1となる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０２７６
【補正方法】変更
【補正の内容】
【０２７６】
このとき、高さｋの二分木のノード(j，i)（0≦ｉ＜2(k-j)）のルートパス rtPath(k, j, i) (ノード(j,i)からルートに至るノード(j,i)の列をいう)は、 rtPath(k,j,i)＝（（j,r(j)），…, (k,r(k))）と表せる。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０２７８
【補正方法】変更
【補正の内容】
【０２７８】
また、高さｋの二分木のノード（ｊ，ｉ）（0≦ｉ＜2(k-j)）の認証パスauthPath(ノード(j,i)からルート値を計算するのに必要なノード(j,i)の集合。但し、該ノードを連接する方向（左又は右）の情報も含んでいる)は、rtPath(k,j,i）を用いて次のように表せる。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０２８３
【補正方法】変更
【補正の内容】
【０２８３】
単位時間（1ラウンドの時間であり，例えば，1秒）に受け付けた時刻証明要求の数をｎとすると、高さｋは，ｋ＝ceiling(log2(n))である。高さｋの二分木のリーフ数は最大で2kであるので、ｄ＝2k−ｎとして、レベル0のノードのうち、2ｄ個を消去すれば、時刻証明要求の数ｎをダミーノードなしでリーフに割り当てることが可能となる。これは、レベル0のリーフが2ｄ個減ると、レベル1のリーフが新たにｄ個できるので、合計でｄ個減り、リーフの数は結局，2k−ｄ＝ｎとなるからである。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０２８４
【補正方法】変更
【補正の内容】
【０２８４】
以下、L1W＝2(k-1)（レベル1のノードの個数）、L1L＝2(k-1)−ｄ（子を有するレベル1のノードの個数）の，L0L＝2（2(k-1)−ｄ）（レベル0のノードの個数）とおくと、ｎ個の時刻証明要求のうち、初めのL0L個をレベル0に配置し、残りをレベル1に配置するとき、ｉ番目の時刻証明要求の配置先を表す関数place(i)は次式で表すことができる。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０２８６
【補正方法】変更
【補正の内容】
【０２８６】
図28は、第１の動的な第１次二分木の構成方法のｎ＝10の場合の具体例を示すものである。この場合においては、図28に示す通り、ｋ＝ceiling(log2(10))＝4となり、高さは4である。そして，ｄ＝24−10＝6であるので、6×2＝12個のレベル0のリーフを消去する。この結果、L1W＝23＝8、L1L＝8−6＝2、L0L＝2×2＝4となる。従って、レベル0のリーフが4個、レベル1のリーフが6個で、リーフの合計数はｎ＝10となる。この結果，図28に示すような第１次二分木を動的に作成することができる。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０２８８
【補正方法】変更
【補正の内容】
【０２８８】
単位時間（1ラウンドの時間であり、例えば、1秒）に受け付けた時刻証明要求の数をｎとすると、高さｋは、ｋ＝ceiling(log2(n))である。高さｋの二分木のリーフ数は最大で2k であるので、0からｎ−1までのｎ個の時刻証明要求をレベル0のノード（0,0）からノード（0, n-1）に割り当てる。ここで、レベル0に割り当てられた、最も右のノード（0, n-1）に対して、ルートパス rtPath(k, 0, n-1)を計算する。次に、各レベルｊ（ｊ＝0, …，k-1）においては、以下の手順を実行するものとする。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】０２９０
【補正方法】変更
【補正の内容】
【０２９０】
r(j)+1＜ｉ＜2(k-j)となる各ｉに対して、ノード（ｊ，ｉ）は消去される。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】０２９１
【補正方法】変更
【補正の内容】
【０２９１】
r(j)が奇数のとき、r(j)+1＜ｉ＜2(k-j)となる各ｉに対して、ノード（ｊ，ｉ）は消去される。また、ルートにあるレベルｋについては、何も行わない。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】０２９４
【補正方法】変更
【補正の内容】
【０２９４】
ここで、ノード（0,8）のルートパス rtPath(4,0,8)は rtPath(4,0,8)＝（(0,8)，(1,4)，(2,3) ，(3,1)，(4,0)） となる。これにより，各レベルでの手順は、以下の通りになる。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０２９５
【補正方法】変更
【補正の内容】
【０２９５】
レベル0では、（0,9）がダミーノードになり、番号10以降が消去される。レベル1では、（1,5）がダミーノードとなり、5＜ｉ＜23＝8であれば、ノード（ｊ，ｉ）は削除される。レベル2では、ノード（2,3）がダミーノードになる。レベル3および4においては、ダミーノードも消去されるノードもない。この結果，図29に示すような第１次二分木を動的に作成することができる。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】０３０３
【補正方法】変更
【補正の内容】
【０３０３】
・（K+1）個の配列の列を、A(0), …, A(K)とする。各配列は、2(k-j)の長さをもち、レベルjのノードに割り付けられる値を保持する（j=0, …,K）。ノード(j,i)に対して、A(j,i)は，A(j)[i]を表すものとする。ノード(j,i)の左側の子が(j’, i’)のとき、A（leftChild(j,i)）はA(j’)[i’]を表す。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】０３３１
【補正方法】変更
【補正の内容】
【０３３１】
1,7,7a  時刻証明装置
2  時刻情報提供装置
3,203,303,303a,403  クライアント装置
4  コンピュータネットワーク
5,6,8,8a,9  監査装置
10  ＴＳＡ
11  送受信部
12,72,72a  時刻証明要求まとめ部
13  時刻情報取得部
14,14a  時刻証明作成部
15  時刻証明公表部
16  受理証明書記憶部
17,77,77a  監査情報作成部
20  ＴＡ
30  利用者
31  送受信部
32  メッセージ記憶部
33  時刻証明要求部
34  受理証明書記憶部
35,36,37,38  時刻証明検証部
40  メディア等
41,42  ファイル
51,81  送受信部
52,82,92  監査情報記憶部
53,93  時刻証明検証部
63  監査情報公開部
73  時刻タグ情報取得部
83,83a  時刻証明公表部
100,200,300,310,400,900,910  タイムスタンプ・システム
800  時刻タグシステム
801  時刻タグ作成業者
802  デジタル放送業者
803  時刻タグ認証業者