(57)【要約】【課題】同一時刻の時刻値付ディジタル文書に対する部分ディジタル署名を、各ディジタル署名作成手段毎に１つずつ選択することができることを保証する。【解決手段】本発明は、標準時間からのずれ幅が一定の値以下であることが保証された複数の時刻を獲得し、時刻の標準時間からのずれ幅の範囲と時刻の刻み幅に応じて、該刻み幅で時刻値を生成するとき、部分ディジタル署名作成手段において、生成された時刻値とディジタル文書を結合する際に、時刻印付ディジタル文書に対して、部分ディジタル署名を作成し、該部分ディジタル署名の中に同一の時刻の時刻印付ディジタル文書に対するディジタル署名が、各部分ディジタル署名作成手段毎に、少なくとも１つはあるように、保証する。【選択図】　　図１
2004023190.tif 000002
【特許請求の範囲】
【請求項１】
分散ディジタル時刻署名作成システムにおける、複数の時刻獲得手段において取得した時刻を各部分ディジタル署名作成手段毎に１つに結合し、結合された時刻の刻み幅で１つあるいは複数の時刻値を生成し、与えられたディジタル文書に対して、１つあるいは、複数の時刻値を付与して、１つまたは、複数の時刻値付ディジタル文書に対する１つあるいは、複数の部分ディジタル署名を作成するための時刻付与方法において、
前記時刻獲得手段において、標準時間からのずれ幅が一定の値以下であることが保証された複数の時刻を獲得し、
前記時刻の標準時間からのずれ幅の範囲と時刻の刻み幅に応じて、該刻み幅で１つあるいは複数の時刻値を生成するとき、
前記部分ディジタル署名作成手段において、生成された前記時刻値と前記ディジタル文書を結合する際に、該ディジタル文書と該時刻値を結合した結果である１つあるいは、複数の時刻印付ディジタル文書に対して、１つあるいは、複数の部分ディジタル署名を作成し、該部分ディジタル署名の中に同一の時刻の時刻印付ディジタル文書に対するディジタル署名が、各部分ディジタル署名作成手段毎に、少なくとも１つはあるように、保証することを特徴とする時刻付与方法。
【請求項２】
時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、
複数ある前記部分ディジタル署名作成手段の各々が前記ディジタル文書に対するディジタル署名を作成するために付与する時刻値と前記基準時刻との差の大きさを、予め与えられた一定の値以下とする請求項１記載の時刻付与方法。
【請求項３】
時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、
複数ある部分ディジタル署名作成手段の各々が前記ディジタル文書に対するディジタル時刻署名を作成するために付与する時刻値を、基準時刻以降とする請求項１記載の時刻付与方法。
【請求項４】
前記１つあるいは複数の時刻値を生成するとき、
前記刻み幅で高々２つの時刻値を生成し、かつ複数の前記時刻獲得手段相互の誤差が小さいときには、高い確率で時刻値を１つのみ生成し、該時刻値とディジタル文書を結合する請求項１乃至３のうちいずれか１項記載の時刻付与方法。
【請求項５】
ディジタル文書を受け取るディジタル文書受取手段と、時刻を取得する複数の時刻取得手段と、該時刻取得手段から得られた１つあるいは複数の時刻を該ディジタル文書に付与する時刻値結合手段と、該時刻値結合手段から得られた時刻値が付与されたディジタル文書に対して、部分ディジタル署名を作成する複数の部分ディジタル時刻署名作成手段と、該複数の部分ディジタル時刻署名作成手段から付加情報付ディジタル文書と部分ディジタル署名の組を取得して、統合ディジタル署名を作成する統合ディジタル署名作成手段を有する分散ディジタル時刻署名作成システムであって、
前記時刻取得手段は、
標準時間からのずれ幅が一定値以下であること保証された時刻を獲得する手段を有し、
前記時刻値結合手段は、
前記部分ディジタル時刻署名作成手段毎に、複数の部分ディジタル署名を作成する際に、該部分ディジタル署名の中に同一の時刻の時刻付ディジタル文書に対するディジタル署名が少なくとも１つはあることを保証するように、前記時刻獲得手段から取得した前記時刻の標準時間からのずれ幅の範囲と該時刻の刻み幅に応じて、１つあるいは複数の時刻値を生成する時刻値生成手段と、
前記ディジタル文書受取手段により取得した前記ディジタル文書と前記時刻値生成手段で生成された前記時刻値を結合し、時刻等付与情報付ディジタル文書を生成する結合手段と、を有することを特徴とするディジタル時刻署名作成システム。
【請求項６】
前記時刻値結合手段の前記時刻値生成手段は、
時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、複数ある前記部分ディジタル署名作成手段の各々が前記ディジタル文書に対するディジタル署名を作成するために付与する時刻値と前記基準時刻との差の大きさを、予め与えられた一定の値以下とする手段を含む請求項５記載のディジタル時刻署名作成システム。
【請求項７】
前記時刻値結合手段の前記時刻値生成手段は、
時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、複数ある部分ディジタル署名作成手段の各々が前記ディジタル文書に対するディジタル時刻署名を作成するために付与する時刻値を基準時刻以降とする手段を含む請求項５記載のディジタル時刻署名作成システム。
【請求項８】
前記時刻値結合手段の前記時刻値生成手段は、
前記１つあるいは複数の時刻値を生成するとき、前記刻み幅で高々２つの時刻値を生成し、かつ複数の前記時刻獲得手段相互の誤差が小さいときには、高い確率で時刻値を１つのみ生成する手段を含む請求項５乃至７のうちいずれか１項記載のディジタル時刻署名作成システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、時刻付与方法及び及び装置に係り、特に、ディジタル文書に時刻印を押すサービスにおいて、ディジタル文書が時刻印を押された時点以降において変更されたことがなく、かつ時刻印が作成された時点で、対象とするディジタル文書が確かに存在していたことの証明を可能とする分散型の時刻署名作成システムにおいて、時刻印を付与する際の時刻値を決定するための時刻付与方法及び装置に関する。
【０００２】
【従来の技術】
従来の分散時刻署名システムの一例として、特開２００１−２１４２３９８号に示される方法がある。図１１に示すように、この従来の分散時刻署名システムは、受取手段１３０と、時刻取得手段１３３と、時刻値結合手段１３１と、ディジタル署名作成手段１３５と、統合ディジタル署名作成手段１３７と、送付手段１４１とから構成されている。このような構成を有する従来の分散時刻署名システムにおいては、受け取られたディジタル文書に対する時刻値の付与は、次のように動作する。
【０００３】
即ち、
（ａ１）　分散時刻署名システム内にある複数の時刻取得手段１３３のうち、各時刻取得手段において、時刻署名要求に応じて、他の時刻取得手段とは独立に、一定の刻み幅で与えられた時刻情報を順次取得する。
【０００４】
（ａ２）　分散時刻署名システム内のこれら複数の時刻取得手段１３３に対応して設けられた複数の時刻値結合手段１３１のうち、各結合手段において、他の結合手段とは独立に、対応する時刻取得手段１３３により順次取得された時刻情報を時刻署名の対象となるディジタル文書に順次結合して時刻値付ディジタル文書を作成する。
【０００５】
（ａ３）　分散時刻署名システム内のこれら複数の時刻値結合手段１３１に対応して設けられた複数のディジタル署名作成手段１３５のうちの各ディジタル署名作成手段において、他のディジタル署名作成手段とは独立に、対応する結合手段により作成された各時刻値付ディジタル文書に対するディジタル署名を作成する。
【０００６】
（ａ４）　統合ディジタル署名作成手段１３７は、複数のディジタル署名作成手段１３５によって生成された複数のディジタル署名から、複数のディジタル署名作成手段よって同一時刻の時刻値付ディジタル文書に対して生成された複数のディジタル署名を、各ディジタル署名作成手段１３５毎に１つずつ選択し、選択されたディジタル署名から統合ディジタル署名を作成する。
【０００７】
（ａ５）　ステップ（ａ４）により、作成された統合ディジタル署名と前述の同一時刻の時刻値付ディジタル文書から時刻証明書を作成する。
【０００８】
【発明が解決しようとする課題】
しかしながら、上記の従来の方法には、以下のような問題がある。
【０００９】
第１の問題点は、複数の部分ディジタル署名作成手段によって生成された複数の部分ディジタル署名から、同一時刻の時刻値付ディジタル文書に対して作成された部分ディジタル署名を、各ディジタル署名作成手段毎に１つずつ選択できることが保証されないということである。その理由は、複数のディジタル署名作成手段が付与する１つまたは複数の時刻値が共通部分を持つための時刻値の付与方法と条件が与えられていないためである。
【００１０】
第２の問題点は、複数のディジタル署名作成手段が付与する１つまたは、複数の時刻値と、受取手段がディジタル文書を受け取ったときの標準時刻との差の絶対値が、前以って定めた一定の値以下であることが保証されないということである。その理由は、複数のディジタル署名作成手段が付与する１つまたは、複数の時刻値と受取手段がディジタル文書を受け取ったときの標準時刻との差の絶対値が、前以って定められた一定以下のそれ以下であるための時刻値の付与方法と条件が与えられていないためである。
【００１１】
第３の問題点は、複数のディジタル署名作成手段が付与する１つまたは複数の時刻値が、受取手段がディジタル文書を受け取ったときの標準時刻を基準として、それ以降であることが保証されないということである。その理由は、複数のディジタル署名作成手段が付与する１つまたは、複数の時刻値が、受取手段がディジタル文書を受け取ったときの標準時刻を基準として、それ以降であるための時刻値の付与方法と条件が与えられていないためである。
【００１２】
第４の問題点は、各ディジタル署名作成手段が、必要最小限の数のディジタル署名のみ作成することが保証されないことである。その理由は、統合時刻署名を作成するために必要な、各ディジタル署名作成手段が作成するディジタル署名の数が明らかにされていないためである。
【００１３】
本発明は、上記の点に鑑みなされたもので、複数のディジタル署名作成手段によって生成された複数の部分ディジタル署名から、同一時刻の時刻値付ディジタル文書に対する部分ディジタル署名を、各ディジタル署名作成手段毎に１つずつ選択することができることを保証する分散時刻署名作成システムにおける時刻付与方法及び及び装置を提供することを目的とする。
【００１４】
また、本発明の目的は、複数のディジタル署名作成手段が付与する１つまたは複数の時刻値と、受取手段がディジタル文書を受け取ったときの標準時刻との差の絶対値が、前以って定められた一定の値以下であることを保証する分散時刻署名作成システムにおける時刻付与方法及び装置を提供することである。
【００１５】
また、本発明の更なる目的は、各ディジタル署名作成手段が、受信したディジタル文書に対する時刻署名を作成するために必要な最小限の数のディジタル署名のみ作成することを保証する分散時刻署名作成システムにおける時刻付与方法及び装置を提供することである。
【００１６】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
【００１７】
本発明は、分散ディジタル時刻署名作成システムにおける、複数の時刻獲得手段において取得した時刻を各部分ディジタル署名作成手段毎に１つに結合し、結合された時刻の刻み幅で１つあるいは複数の時刻値を生成し、与えられたディジタル文書に対して、１つあるいは、複数の時刻値を付与して、１つまたは、複数の時刻値付ディジタル文書に対する１つあるいは、複数の部分ディジタル署名を作成するための時刻付与方法において、
時刻獲得手段において、標準時間からのずれ幅が一定の値以下であることが保証された複数の時刻を獲得し（ステップ１）、
時刻の標準時間からのずれ幅の範囲と時刻の刻み幅に応じて、該刻み幅で１つあるいは複数の時刻値を生成するとき、
部分ディジタル署名作成手段において、生成された時刻値とディジタル文書を結合する際に、該ディジタル文書と該時刻値を結合した結果である１つあるいは、複数の時刻印付ディジタル文書に対して、１つあるいは、複数の部分ディジタル署名を作成し、該部分ディジタル署名の中に同一の時刻の時刻印付ディジタル文書に対するディジタル署名が、各部分ディジタル署名作成手段毎に、少なくとも１つはあるように、保証するように生成する（ステップ２）。
【００１８】
また、本発明の時刻付与方法は、時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、
複数ある部分ディジタル署名作成手段の各々がディジタル文書に対するディジタル署名を作成するために付与する時刻値と基準時刻との差の大きさを、予め与えられた一定の値以下とする。
【００１９】
また、本発明の時刻付与方法は、時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、
複数ある部分ディジタル署名作成手段の各々がディジタル文書に対するディジタル時刻署名を作成するために付与する時刻値を基準時刻以降とする。
【００２０】
また、本発明の時刻付与方法は、１つあるいは複数の時刻値を生成するとき、
刻み幅で高々２つの時刻値を生成し、かつ複数の時刻獲得手段相互の誤差が小さいときには、高い確率で時刻値を１つのみ生成し、該時刻値とディジタル文書を結合する。
【００２１】
図２は、本発明の原理構成図である。
【００２２】
本発明は、ディジタル文書を受け取るディジタル文書受取手段１０と、時刻を取得する複数の時刻取得手段１１と、該時刻取得手段１１から得られた１つあるいは複数の時刻を該ディジタル文書に付与する時刻値結合手段１２と、該時刻値結合手段から得られた時刻値が付与されたディジタル文書に対して、部分ディジタル署名を作成する複数の部分ディジタル時刻署名作成手段１３と、該複数の部分ディジタル時刻署名作成手段１３から付加情報付ディジタル文書と部分ディジタル署名の組を取得して、統合ディジタル署名を作成する統合ディジタル署名作成手段１４を有する分散ディジタル時刻署名作成システムであって、
時刻取得手段１１は、
標準時間からのずれ幅が一定値以下であること保証された時刻を獲得する手段を有し、
時刻値結合手段１２は、
部分ディジタル時刻署名作成手段１３毎に、複数の部分ディジタル署名を作成する際に、該部分ディジタル署名の中に同一の時刻の時刻付ディジタル文書に対するディジタル署名が少なくとも１つはあることを保証するように、時刻獲得手段１１から取得した時刻の標準時間からのずれ幅の範囲と該時刻の刻み幅に応じて、１つあるいは複数の時刻値を生成する時刻値生成手段と、
ディジタル文書受取手段により取得したディジタル文書と時刻値生成手段で生成された時刻値を結合し、時刻等付与情報付ディジタル文書を生成する結合手段と、を有する。
【００２３】
本発明の分散ディジタル時刻署名作成システムにおける、時刻値結合手段１２の時刻値生成手段は、
時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、複数ある部分ディジタル署名作成手段の各々がディジタル文書に対するディジタル署名を作成するために付与する時刻値と基準時刻との差の大きさを、予め与えられた一定の値以下とする手段を含む。
【００２４】
また、本発明の分散時刻署名システムにおける、時刻値結合手段１２の時刻値生成手段は、
時刻署名の対象となるディジタル文書を受け付けたときの標準時刻を基準時刻としたとき、複数ある部分ディジタル署名作成手段の各々がディジタル文書に対するディジタル時刻署名を作成するために付与する時刻値を基準時刻以降とする手段を含む。
【００２５】
また、本発明の分散時刻署名システムにおける、時刻値結合手段１２の時刻値生成手段は、
１つあるいは複数の時刻値を生成するとき、刻み幅で高々２つの時刻値を生成し、かつ複数の時刻獲得手段相互の誤差が小さいときには、高い確率で時刻値を１つのみ生成する手段を含む。
【００２６】
上記のように、本発明では、生成された複数のディジタル署名から、同一時刻の時刻付ディジタル文書を、１つずつ選択することができること保証するように動作する。
【００２７】
また、高々２つのディジタル署名のみを作成できるように処理手順を定めることにより、必要最小限の数のディジタル署名のみ作成すること保証するように動作する。
【００２８】
また、複数ある時刻値を結合する手段の各々が付与する高々２つの時刻値の各々が、ディジタル文書を受け取った時の標準時刻以降であることを保証するように動作する。
【００２９】
このように、本発明は、従来技術とは、複数の時刻取得手段の相互の誤差の大きさの上限に応じて、分散時刻署名に用いる時刻値の刻み幅を定め、各部分ディジタル署名作成手段が、この刻み幅で１つまたは、複数の時刻署名を作成する場合に、時刻値付与のための処理手順を適切に定めることにより、複数の時刻取得手段の相互の誤差の大きさの上限についての一定の条件のもとで、複数のディジタル署名作成手段によって生成された複数のディジタル署名から、同一時刻の時刻値付ディジタル文書に対する部分ディジタル署名を各ディジタル署名作成手段毎に１つずつ選択できることを保証するようにした点、及び、時刻値付与のための処理手順を別の方式で適切に定めることにより、複数のディジタル署名作成手段が付与する１つまたは、複数の時刻値の各々が、ディジタル文書を受け取ったときの標準時刻以降であることを保証するようにした点、さらに、部分ディジタル署名作成手段が受信したディジタル文書に対して高々２つの時刻署名を作成するように処理手順を定めることにより、受信したディジタル文書に対する統合時刻署名を最終的に作成するために必要となる最小限の数のディジタル署名のみを、各部分署名作成手段が作成するように処理手順を定めた点において異なる。
【００３０】
【発明の実施の形態】
以下、図面と共に本発明の実施の形態を説明する。
【００３１】
最初に、実施の形態の説明に出現する用語・前提等について説明する。
【００３２】
ディジタル文書に付与する時刻値の刻み幅をδとする。
【００３３】
マシンあるいは、プログラミング言語が提供する実装環境においては、時刻値は所定の基準時点（１９７０年１月１日０時０分０秒等）からの経過時間を最小単位ｕ（ミリ秒、マイクロ秒等）で割った非負整数として表される。
【００３４】
本発明においては、δはｕの整数倍の場合のみ扱う。
【００３５】
以下では、ｔ（ｎ）は、時間軸を（基準時点から）巾δで刻んだときの、ｎ番目の刻みを表すものとする。即ち、
ｔ（ｎ）＝ｎ・δ
とおく。
【００３６】
また、本発明においては、分数を含む計算式は、分母を払って整数計算に還元して評価するか、または、それと論理的に同値になるように評価するものとし、途中で端数切捨てを含むような分数式の評価は行わないものとする。
【００３７】
例えば、以下に現れる
ｔ（ｎ）−（１／４）・δ≦Ｔ（ｉ）≦ｔ（ｎ）＋（１／４）・δ
という条件は、次のように整数計算に還元する。
【００３８】
ｔ（ｎ）−（１／４）・δ≦Ｔ（ｉ）≦ｔ（ｎ）＋（１／４）・δ←→　４・ｔ（ｎ）−δ≦４・Ｔ（ｉ）≦ｔ・ｔ（ｎ）＋δ
また、以下では、Ｃｏｏｒｄｉｎａｔｅｄ　Ｕｎｉｖｅｒｓａｌ　Ｔｉｍｅ等の世界的に標準として認められた時刻を標準時刻と呼ぶ。
【００３９】
さらに、後述する図３に示されるディジタル文書Ｍが受取部に送られ、受取部が当該ディジタル文書を受け取ったときの標準時刻を「ディジタル文書Ｍの基準時刻」と呼び、各時刻値結合部が受取部からディジタル文書Ｍを受け取ったとき、時刻取得部から取得する時刻を「Ｔ（ｉ）」とする。
【００４０】
また、１≦ｉ≦ｍなる任意のｉについて、
｜Ｍの基準時刻−Ｔ（ｉ）｜＜（１／（４・ｋ））・δ
が成り立つ時、図３の分散時刻署名システムは、“強い意味で時刻精度パラメータｋを持つ”という。このとき、１≦ｉ，ｊ≦ｍなる任意のｉとｊについて、
｜Ｔ（ｉ）−Ｔ（ｊ）｜＜（１／（２・ｋ））・δ
となる。
【００４１】
また、１≦ｉ，ｊ≦ｍなる任意のｉとｊについて、
｜Ｔ（ｉ）−Ｔ（ｊ）｜＜（１／（２・ｋ））・δ
でかつ、１≦ｉ≦ｍなる任意のｉについて、
Ｍの基準時刻−（１／（４・ｋ））・δ＜Ｔ（ｉ）
が成り立つとき、図３の分散時刻署名システムは、“弱い意味で時刻精度パラメータｋを持つ”という。
【００４２】
明らかに、図３の分散時刻署名システムが、強い意味で時刻精度パラメータｋを持つならば、弱い意味で時刻精度パラメータｋを持つ。
【００４３】
図３は、本発明の一実施の形態における分散時刻署名システムの構成を示す。
同図に示す分散時刻署名システム１は、ディタル文書受取部１０、複数の時刻取得部１１１　〜１１ｍ　、複数の時刻値結合部１２１　〜１２ｍ　、複数の部分ディジタル時刻署名作成部１３１　〜１３ｍ　、及び統合ディジタル署名作成部１４から構成される。
【００４４】
ディジタル文書受取部１０は、時刻署名の対象となるディジタル文書を受け付ける。
【００４５】
時刻取得部１１は、標準時間からのずれ幅が一定の値以下であることが保証された時刻を獲得する。
【００４６】
時刻値結合部１２は、時刻取得部１１から得られる時刻値の標準時間からのずれ幅の範囲と刻み幅に応じて、その刻み幅で１つあるいは複数の時刻値を生成し、当該時刻時とディジタル文書を結合し、時刻等付加情報付ディジタル文書１８として、部分ディジタル時刻署名作成部１３に渡す。
【００４７】
部分ディジタル時刻署名作成部１３は、ディジタル文書と時刻値を結合した結果である１つあるいは複数の時刻付ディジタル文書について、１つあるいは複数の部分ディジタル署名を作成し、付加情報付ディジタル文書と部分ディジタル署名の組１９として、統合ディジタル署名作成部１４に渡す。
【００４８】
統合ディジタル署名作成部１４は、複数の付加情報付ディジタル文書と部分ディジタル署名の組１９を、部分ディジタル時刻署名作成部１３毎に１つずつ選択し、選択されたディジタル署名から統合ディジタル署名を作成する。
【００４９】
以下の各実施の形態では、時刻値結合部１２における動作を説明する。
【００５０】
［第１の実施の形態］
図４は、本発明の第１の実施の形態における時刻値結合部における直近方式による動作を説明するための図である。
【００５１】
同図において、各時刻値結合部１２ｉ　がディジタル文書（以下、メッセージＭと記す）を受信したとき、時刻取得部１１ｉ　から得られた時刻値に最も近い値を高々２つ選び、時刻値として付加する方式を記述している。この方式を「直近方式」という。同図では、直近方式の中で「強い意味での時刻精度パラメータｋ」が１の場合を記述している。
【００５２】
メッセージＭを受信したとき、ｉ番目の部分ディジタル時刻署名作成部１３ｉ　がｉ番目の時刻取得部１１ｉ　から取得する時刻をＴ（ｉ）とし、Ｍに対する時刻印に用いる時刻値の集合ＴＳ（ｉ）を次のように定める。
【００５３】
ｔ（ｎ）−（１／４）・δ≦Ｔ（ｉ）≦ｔ（ｎ）＋（１／４）・δ→ＴＳ（ｉ）＝｛ｔ（ｎ）｝
ｔ（ｎ）−（１／４）・δ＜Ｔ（ｉ）＜ｔ（ｎ）＋（３／４）・δ→ＴＳ（ｉ）＝｛ｔ（ｎ），ｔ（ｎ＋１）｝
図５は、本発明の第１の実施の形態における直近方式における「強い意味での時刻精度パラメータｋ」が任意の正整数である場合を説明するための図である。同図において、正整数ｋが与えられ、分散時刻署名システム１が、強い意味で時刻精度パラメータｋを持つものとする。
【００５４】
ｉ番目の部分署名作成部１２ｉ　がメッセージＭを受信したとき、ｉ番目の時刻取得部１１ｉ　から取得する時刻をＴ（ｉ）とし、メッセージＭに付ける時刻印に用いる時刻値の集合ＴＳ（ｉ）を次のように定める。
【００５５】
ｔ（ｎ）−（２・ｋ−１）・δ）／（４・ｋ）
≦Ｔ（ｉ）≦ｔ（ｎ）＋（（２・ｋ−１）・δ）／（４・ｋ）→ＴＳ（ｉ）＝｛ｔ（ｎ）｝
ｔ（ｎ）＋（（２・ｋ−１）・δ）／（４・ｋ）
＜Ｔ（ｉ）＜ｔ（ｎ）＋（（２・ｋ−１）・δ）／（４・ｋ）
→ＴＳ（ｉ）＝｛ｔ（ｎ），ｔ（ｎ＋１）｝
図６は、本発明の第１の実施の形態における時刻印に用いる時刻値の集合を求めるフローチャートである。
【００５６】
まず、時刻取得部１１ｉ　から時刻値Ｔ（ｉ）を取得する（ステップ４１）。次に、ｔ（ｎ）≦Ｔ（ｉ）となる最大のｎを決定する（ステップ４２）。
【００５７】
Ｔ（ｉ）＜ｔ（ｎ）＋（（２ｋ＋１）・δ／（４・ｋ）が成り立つかを判断し、成り立つ場合には、メッセージＭに付ける時刻印に用いる時刻値の集合ＴＳ（ｉ）＝｛ｔ（ｎ）｝とする（ステップ４３）。
【００５８】
成り立たない場合には、Ｔ（ｉ）＜ｔ（ｎ）＋（（２ｋ＋１）・δ／（４・ｋ）が成り立つかを判断し、成り立つ場合には、ＴＳ（ｉ）＝｛ｔ（ｎ），ｔ（ｎ＋１）｝とし、成り立たない場合には、ＴＳ（ｉ）＝｛ｔ（ｎ）＋１｝とする（ステップ４４）。
【００５９】
本実施の形態における直近方式においては、まず、２つの時刻値結合部１２に対して、共通時刻が存在することが以下のように保証される。
【００６０】
正整数ｋが与えられ、分散時刻署名システム１が強い意味で時刻精度パラメータｋを持つものとする。強い意味で時刻精度パラメータｋを持つから、１≦ｉ，ｊ≦ｍなる任意のｉとｊについて、
｜Ｔ（ｉ）−Ｔ（ｊ）｜＜（１／（２２・ｋ））・δ
従って、Ｔ（ｉ）とＴ（ｊ）は、図４の同一区間に含まれるか、あるいは、Ｔ（ｉ）の含まれる区間とＴ（ｊ）の含まれる区間は隣接する。従って、図５と図６のＴＳ（ｉ），ＴＳ（ｊ）の定義から、
ＴＳ（ｉ）∩ＴＳ（ｊ）≠｛　｝
となることが分かる。
【００６１】
次に、３つ以上の時刻値結合部に対する共通時刻の存在の保証について説明する。
【００６２】
正整数ｋが与えられ、分散時刻署名システム１が、強い意味で時刻精度パラメータｋを持つものとする。強い意味で時刻精度パラメータｋを持つことにより、１≦ｉ，ｊ≦ｍとなる任意のｉとｊについて、
｜Ｔ（ｉ）−Ｔ（ｊ）｜＜（１／（２・ｋ））・δ
となる。
【００６３】
ＴＳ（ｉ）の個数とＴＳ（ｊ）の個数が共に２のとき、図５と図６のＴＳ（ｉ）の定義から、ＴＳ（ｉ）＝ＴＳ（ｊ）となる。
【００６４】
１≦ｉ（１），…，ｉ（ｋ）≦ｍとなる任意のｉ（１），…，ｉ（ｋ）について、
Ｔ（ｉ（１））∩（（ｉ（２））∩・・∩Ｔ（ｉ（ｋ））≠｛　｝
となることが、以下のように保証される。
【００６５】
場合１）　Ｔ（ｉ（１）），Ｔ（ｉ（２））），…，Ｔ（ｉ（ｋ））の個数が全て２のとき、
ＴＳ（ｉ）＝ＴＳ（ｊ）
であるから、
Ｔ（ｉ（１））∩（（ｉ（２））∩・・∩Ｔ（ｉ（ｋ））＝Ｔ（ｉ（１））
となる。
【００６６】
場合２）　あるｊ∈［１．．ｋ］についてＴ（ｉ（ｊ））の個数が１のとき、２つの時刻値結合部の付与時刻の交わりの保証により、
Ｔ（ｉ（１））∩（（ｉ（２））∩・・∩Ｔ（ｉ（ｋ））＝Ｔ（ｉ（１））≠｛　｝
となる。
【００６７】
次に、付与時刻の誤差の限界について説明する。
【００６８】
この方式で、ＴＳ（ｉ）に含まれる全ての時刻が、基準時刻との差が、
（１／２＋１（２・ｋ））・δ
以下であること、すなわち、
∀ｔ∈ＴＳａ１（ｉ）［｜基準時刻ｔ｜≦（１／２＋１／２（２・ｋ））・δ
となることが、次のように保証される。
【００６９】
正整数ｋが与えられ、分散時刻署名システム１が強い意味で時刻精度パラメータｋを持つものとする。強い意味で時刻精度パラメータｋをもつことにより、
｜基準時刻−Ｔ（ｉ）｜＜δ／（４・ｋ）
となる。
【００７０】
このとき、ＴＳ（ｉ）の定義から、
∀ｔ∈ＴＳ（ｉ）［｜ｔ−Ｔ（１）｜≦（２・ｋ＋１）・δ／（４・ｋ）］
以上から、
∀ｔ∈ＴＳ（ｉ）［｜ｔ−基準時刻｜≦（１／２＋１／（２・ｋ））・δ
となる。
【００７１】
次に、署名数が１となる確率について説明する。
【００７２】
ＴＳ（ｉ）の個数が１となるようなＴ（ｉ）の属する区間（図５の網掛けした長方形の部分）の幅は、（（２・ｋ−１）・δ／（２・ｋ））となり、一方、ＴＳ（ｉ）の個数が２となるようなＴ（ｉ）の属する区間（図５の網掛けした台形の部分）の幅は、δ／（２・ｋ）となる。従って、ＴＳ（ｉ）の個数が１となる確率は、上記第１の区間の幅を上記２つの区間の幅の合計で割った値となり、
（（（２・ｋ−１）・δ）／（２／ｋ））／（（（２・ｋ−１）・δ／（２・ｋ）＋δ／（２・ｋ））＝１−１／（２・ｋ）
となる。この確率は、ｋが大きくなると、１に収束する。
【００７３】
［第２の実施の形態］
次に、本実施の形態では、直近方式を用いて、受け取られたディジタル文書に対して各時刻値結合部１２が付与する時刻値が当該ディジタル文書の基準時間以降となる時刻値の付与方式を以下のように定める。この方式を直後方式（１）と呼ぶ。
【００７４】
直後方式（１）の時刻値集合ＴＳａ１（ｉ）を、直近方式の時刻値集合ＴＳ（ｉ）に基づき、次のように定める。
【００７５】
ＴＳａ１（ｉ）＝［ｔ＋δ｜ｔ∈ＴＳ（ｉ）］
図７は、本発明の第２の実施の形態における時刻印に用いる時刻値の集合を求めるフローチャート（直後方式）である。
【００７６】
まず、時刻取得部１１ｉ　から時刻値Ｔ（ｉ）を取得する（ステップ５１）。
【００７７】
次に、ｔ（ｎ）≦Ｔ（ｉ）となる最大のｎを決定する（ステップ５２）。
【００７８】
次に、
Ｔ（ｉ）≦ｔ（ｎ）？（（２ｋ？１）・δ）／（４・ｋ）
が成り立つかを判定し、成り立つ場合には、
ＴＳａ１（ｉ）＝｛ｔ（ｎ＋１）｝
とする（ステップ５３）。成り立たない場合には、
Ｔ（ｉ）＜ｔ（ｎ）＋（（２ｋ＋１）・δ）／（４・ｋ）
が成り立つかを判定し、成り立つ場合には、
ＴＳａ１（ｉ）＝｛ｔ（ｎ＋１），ｔ（ｎ＋２）｝
とし、成り立たない場合には、
ＴＳａ１（ｉ）＝｛ｔ（ｎ＋２）｝
とする（ステップ５４）。
【００７９】
上記の実施の直後方式（１）により、共通時刻の存在が保証される。
【００８０】
まず、２つの時刻値結合部１２に対して、共通時刻が存在することが以下のように保証される。
【００８１】
正整数ｋが与えられ、分散時刻署名システムが弱い意味で時刻精度パラメータｋを持つものとする。このとき、１≦ｉ，ｊ≦ｍなる任意のｉ，ｊについて、
｜Ｔ（ｉ）−Ｔ（ｊ）｜＜δ／（２・ｋ）
となる。このとき、直近方式の共通時刻の存在の保証から、１≦ｉ，ｊ≦ｍなる任意のｉ，ｊについて、
ＴＳ（ｉ）∩ＴＳ（ｊ）≠｛　｝
これと、上記のＴＳａ１（ｉ）の定義から、
ＴＳａ１（ｉ）∩ＴＳａ１（ｊ）≠｛　｝
となることがわかる。
【００８２】
上記のことを用いて、３つ以上の時刻値結合部１２に対して共通時刻が存在することも、直近方式の場合と同様にして保証できる。
【００８３】
次に、非遡及性の保証について説明する。
【００８４】
本実施の形態の方式で、ＴＳａ１に含まれる全ての時刻が、基準時刻以後であること、即ち、
∀ｔ∈ＴＳａ１（ｉ）［基準時刻≦ｔ］
となることが、次のように保証される。
【００８５】
正整数ｋが与えられ、分散時刻署名システムが弱い意味で時刻精度パラメータｋを持つものとする。弱い意味で時刻精度パラメータｋが持つことにより、
基準時刻−δ／（４・ｋ）＜Ｔ（ｉ）
となる。従って、
基準時刻＜Ｔ（ｉ）＋δ／（４・ｋ）
このとき、ＴＳ（ｉ）の定義から、
∀ｔ∈ＴＳａ１（ｉ）［｜ｔ−Ｔ（ｉ）｜≦（（２・ｋ＋１）・δ）／（４・ｋ）］
従って、
∀ｔ∈ＴＳａ１（ｉ）［Ｔ（ｉ）−（（２・ｋ＋１）・δ）／（４・ｋ）≦ｔ］
さらに、
∀ｔ∈ＴＳａ１（ｉ）［Ｔ（ｉ）＋（（２・ｋ−１）・δ）／（４・ｋ）
≦ｔ＋δ］
このことから、図７のＴＳａ１（ｉ）の決め方から、
∀ｔ∈ＴＳａ１（ｉ）［Ｔ（ｉ）＋δ／（４・ｋ）≦ｔ］
以上から、
∀ｔ∈ＴＳａ１（ｉ）［基準時刻≦ｔ］
となる。
【００８６】
次に、署名数が１となる確率について説明する。
【００８７】
ＴＳａ１（ｉ）の個数が１となるようなＴ（ｉ）の属する区間（図５の網掛けした長方形の部分）の幅は、
（（２・ｋ−１）・δ）／（２・ｋ）
となり、一方、ＴＳａ１（ｉ）の個数が２となるようなＴ（ｉ）の属する区間（図５の網掛けした台形の部分）の幅は、
δ／（２・ｋ）
となる。従って、ＴＳａ１（ｉ）の個数が１となる確率は、上述の第１の区間の幅を上記の２つの区間の幅の合計で割った値となり、
（（２・ｋ−１）・δ）／（２・ｋ））／（（２・ｋ−１）・δ）／（２・ｋ）＋δ／（２・ｋ））＝１−１／（２・ｋ）
となる。この確率は、ｋが大きくなるとき、１に収束する。
【００８８】
直後方式（１）の問題点として、以下の式に示すように、付与される時刻値と時刻値取得部１１から得られる時刻値の差が比較的大きいということがある。任意の正整数ｋに対して、
ｍａｘ　｛ｔ−Ｔ（ｉ）｜ｔ∈ＴＳａ１（ｉ）｝≒（３／２＋１（２・ｋ））・δ
この近似式の誤差は、２・ｕ以内である。上式の右辺はｋが大きくなるとき、減少し、（３／２）・δに収束する。
【００８９】
図８、図９、図１０で示す直後方式（２）で採用する時刻値の集合ＴＳａ２（ｉ）を用いる場合は、ｋが大きくなるにつれて、
ｍａｘ　｛ｔ−Ｔ（ｉ）｜ｔ∈ＴＳａ２（ｉ）｝
は減少し、δに収束する。
【００９０】
［第３の実施の形態］
図８は、本発明の第３の実施の形態における直後方式の「弱い意味での時刻精度パラメータｋ＝１」である場合を説明するための図であり、図９は、本発明の第３の実施の形態における直後方式の「弱い意味での時刻精度パラメータｋ≧１」である場合を説明するための図である。
【００９１】
図８、図９は、分散時刻署名システムが、弱い意味での時刻精度パラメータｋを持つ場合に、時刻値結合部１２ｉがメッセージＭを受信した時、時刻取得部１１ｉから得られた時刻値（１／（４・ｋ））・δを加えた値以上で最も小さい値を高々２つ選び、時刻値として付加する方式を記述している。この方式を直後方式）（２）と記す。
【００９２】
図８に示す直後方式（２）において、弱い意味での時刻パラメータｋが１の場合につい説明する。
【００９３】
ｉ番目の部分署名作成部１２ｉが、メッセージＭを受信したとき、ｉ番目の時刻取得部１１ｉから取得する時刻をＴ（ｉ）とし、
Ｔ’（ｉ）＝Ｔ（ｉ）＋（１／４）・δ
と置く。メッセージＭに付ける時刻印に用いる時刻値の集合ＴＳａ２（ｉ）を次のように定める。
【００９４】
ｔ（ｎ−１）≦Ｔ’（ｉ）≦ｔ（ｎ）−（１／２）・δ→　ＴＳａ２（ｉ）＝｛ｔ（ｎ）｝
ｔ（ｎ）−（１／２）・δ＜Ｔ’（ｉ）＜ｔ（ｎ）→ＴＳａ２（ｉ）＝｛ｔ（ｎ），ｔ（ｎ＋１）｝
次に、図９に示す直後方式（２）において、弱い意味での時刻パラメータｋが任意の正整数であるような一般的な場合を説明する。
【００９５】
正整数ｋが与えられ、分散時刻署名システムが弱い意味で時刻精度パラメータｋを持つものとする。
【００９６】
ｉ番目の部分署名作成部１２ｉが、メッセージＭを受信したとき、ｉ番目の時刻取得部１１ｉから取得する時刻をＴ（ｉ）とし、
Ｔ’（ｉ）＝Ｔ（ｉ）＋（１／（４・ｋ））・δ
と置く。メッセージＭに付ける時刻印に用いる時刻値の集合ＴＳａ２（ｉ）を次のように定める。
【００９７】
ｔ（ｎ−１）≦Ｔ（ｉ）≦ｔ（ｎ）−（１／（２・ｋ））・δ→ＴＳａ２（ｉ）＝｛ｔ（ｎ）｝
図９は、本発明の第３の実施の形態における時刻印に用いる時刻値の集合を計算するフローチャートである。
【００９８】
時刻取得部１１ｉから時刻値Ｔ（ｉ）を取得する（ステップ８１）。
【００９９】
Ｔ’（ｉ）＝Ｔ（ｉ）＋δ／（４・ｋ）
とおく（ステップ８１）。
【０１００】
ｔ（ｎ）≦Ｔ’ｉとなる最大のｎを決定し、
Ｔ’（ｉ）≦ｔ（ｎ＋１）？δ／（２・ｋ）
が成り立つかを判定し、成り立つ場合には、
ＴＳａ２（ｉ）＝｛ｔ（ｎ＋１）｝
とし（ステップ８３）、成り立たない場合には、
ＴＳａ２（ｉ）＝｛ｔ（ｎ＋１），ｔ（ｎ＋２）｝
とする（ステップ８４）。
【０１０１】
次に、本実施の形態における共通時刻存在の保証について説明する。
【０１０２】
まず、２つの時刻値結合部１２に対して共通時刻が存在することが以下のように保証される。
【０１０３】
正整数ｋが与えられ、分散時刻署名システムが弱い意味で時刻精度パラメータｋを持つものとする。弱い意味で時刻精度パメータｋを持つから、１≦ｉ，ｊ≦ｍなる任意のｉとｊについて、
｜Ｔ（ｉ）−Ｔ（ｊ）｜＜（１／（２・ｋ））・δ
となる。
【０１０４】
従って、Ｔ’（ｉ）とＴ’（ｊ）は、図９の同一区間に含まれるか、あるいは、Ｔ’（ｉ）の含まれる区間とＴ’（ｊ）の含まれる区間は、隣接する。図９と図１０のＴＳａ２（ｉ），ＴＳａ２（ｊ）の定義から、
ＴＳａ２（ｉ）∩ＴＳａ２（ｊ）≠｛　｝
となることが分かる。
【０１０５】
上記のことを用いて、３つ以上の時刻値結合部１２に対して共通時刻が存在することも、直近方式の場合と同様にして保証できる。
【０１０６】
なお、ＴＳａ２（ｉ）に含まれるすべての時刻が基準時刻以後であることを保証しなくてもよいのであれば、
Ｔ’（ｉ）＝Ｔ（ｉ）
として、図１０の手順を適用することにより、共通時刻の存在が保証された時刻付与方式を得ることができる。
【０１０７】
次に、非遡及性の保証について説明する。
【０１０８】
本実施の形態による方式で、ＴＳａ２（ｉ）に含まれるすべての時刻が、基準時刻以後であること、即ち、
∀ｔ∈ＴＳａ２（ｉ）［基準時刻≦ｔ］
となることが、次のように保証される。
【０１０９】
正整数ｋが与えられ、分散時刻署名システムが弱い意味で時刻精度パラメータｋを持つものとする。図９のＴＳａ２（ｉ）の定義から、
∀ｔ∈ＴＳａ２（ｉ）［Ｔ’（ｉ）＜ｔ］
となる。
【０１１０】
一方、分散時刻署名システムが時刻精度パラメータｋを持つという前提から、
基準時刻−（１／（４・ｋ））・δ＜Ｔ（ｉ）
従って、
基準時刻＜Ｔ（ｉ）＋（１／（４・ｋ））・δ＝Ｔ’（ｉ）
以上から、
∀ｔ∈ＴＳａ２（ｉ）［基準時刻＜ｔ］
となることがわかる。
【０１１１】
次に、署名数が１となる確率について説明する。
【０１１２】
ＴＳａ２（ｉ）の個数が１となるようなＴ’（ｉ）の属する区間（図９の網掛けした長方形の部分）の幅は、
（（２・ｋ−１）・δ）／（２・ｋ）
となり、一方、ＴＳａ２（ｉ）の個数が２となるようなＴ（ｉ）の属する区間（図９の網掛けした台形の部分）の幅は、
δ／（２・ｋ）
となる。従って、ＴＳａ２（ｉ）の個数が１となる確率は、上記の第１の区間の幅を上記２つの区間の幅の合計で割った値となり、
（（２・ｋ−１）・δ）／（２／ｋ））／（（（２・１）・δ）／（２・ｋ）＋δ／（２・ｋ））＝１−１／（２・ｋ）
となる。この確率は、ｋが大きくなると、１に収束する。
【０１１３】
直後方式（２）の利点として、以下の式に示すように、付与される時刻値と時刻取得部１１から得られる時刻値の差が比較的小さいということがある。任意の正整数ｋに対して、
ｍａｘ　｛ｔ−Ｔ（ｉ）｜ｔ∈ＴＳａ２（ｉ）｝≒（１＋３／（４・ｋ））・δ
この近似式の誤差は、２・ｕ以内である。
【０１１４】
上式の右辺は、ｋが大きくなるとき、減少し、δに収束する。
【０１１５】
また、上記の実施の形態では、図３に示すシステムに基づいて説明しているが、特に、時刻取得部、時刻結合部の動作をプログラムとして構築し、当該装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
【０１１６】
また、構築されたプログラムを時刻取得部、時刻結合部を有するコンピュータに接続されるハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、当該コンピュータにインストールすることも可能である。
【０１１７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【０１１８】
【発明の効果】
上述のように、本発明によれは、生成された複数のディジタル署名から、同一時刻の時刻付ディジタル文書を、１つずつ選択することができる。
【０１１９】
また、本発明によれば、高々２つのディジタル署名のみを作成できるように処理手順を定めることにより、必要最小限の数のディジタル署名のみを作成することができる。
【０１２０】
また、本発明によれば、複数ある時刻値を結合する手段の各々が付与する高々２つの時刻値の各々が、ディジタル文書を受け取った時の標準時刻以降であることを保証するように動作する。
【０１２１】
また、本発明によれば、ディジタル文書を受け取った時の標準時刻との差が所定の値以下であることを保証されることにより、ディジタル文書に付与する時刻の誤差の限界が設定される。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における分散時刻署名システムの構成図である。
【図４】本発明の第１の実施の形態における時刻値結合部における直近方式による動作を説明するための図である。
【図５】本発明の第１の実施の形態における直近方式の「強い意味での時刻精度パラメータｋ」が任意の正整数である場合を説明するための図である。
【図６】本発明の第１の実施の形態における時刻印に用いる時刻値の集合を求めるフローチャート（直近方式）である。
【図７】本発明の第２の実施の形態における時刻印に用いる時刻値の集合を求めるフローチャート（直後方式）である。
【図８】本発明の第３の実施の形態における直後方式の「弱い意味での時刻精度パラメータｋ＝１」である場合を説明するための図である。
【図９】本発明の第３の実施の形態における直後方式の「弱い意味での時刻精度パラメータｋ≧１」である場合を説明するための図である。
【図１０】本発明の第３の実施の形態における時刻印に用いる時刻値の集合を計算するフローチャートである。
【図１１】従来の分散時刻署名システムの構成図である。
【符号の説明】
１　分散時刻署名システム
１０　ディジタル文書受取手段、ディジタル文書受取部
１１　時刻取得手段、時刻取得部
１２　時刻値結合手段、時刻値結合部
１３　部分ディジタル時刻署名作成手段、部分ディジタル時刻署名作成部
１４　統合ディジタル署名作成手段、統合ディジタル署名作成部
【図１】
2004023190.tif 000003
【図２】
2004023190.tif 000004
【図３】
2004023190.tif 000005
【図４】
2004023190.tif 000006
【図５】
2004023190.tif 000007
【図６】
2004023190.tif 000008
【図７】
2004023190.tif 000009
【図８】
2004023190.tif 000010
【図９】
2004023190.tif 000011
【図１０】
2004023190.tif 000012
【図１１】
2004023190.tif 000013