(57)【要約】  【課題】高度な安全性を有するマークル署名システムにおいて、伝送するデータサイズを小さくし、効率的に処理することのできる署名システムを提供すること。  【解決手段】  スマートカード１１０の処理部１１２は、署名するメッセージの先頭ビットから順に特定のビット毎のグループに分けて一方向関数処理部１１２ｃにおいて暗号化することで生成した当該グループ毎の部分ワンタイム署名を、順次、ＩＦ部１１３を介して検証装置に出力する処理を行う。【選択図】図２
2008103975.tif 000002
【特許請求の範囲】
【請求項１】
第一コンピュータで生成されたデジタル署名を第二コンピュータで検証する署名システムであって、
前記第一コンピュータの処理部は、デジタル署名をするデータを先頭ビットから順に特定のビット数毎のグループに分けて一方向関数に代入することで生成した当該グループ毎の部分署名を、順次、前記第二コンピュータに出力する処理を行うこと、
を特徴とする署名システム。
【請求項２】
請求項１に記載の署名システムであって、
前記第二コンピュータの処理部は、前記部分署名を圧縮関数で圧縮することによりワンタイム公開鍵を生成し、当該ワンタイム公開鍵からマスタ公開鍵を生成して、当該マスタ公開鍵を予め記憶部に記憶されているマスタ公開鍵と比較することで検証する処理を行うものであること、
を特徴とする署名システム。
【請求項３】
請求項１に記載の署名システムであって、
前記第一コンピュータの処理部は、前記グループに含まれるビットが示す値に応じて、前記グループ毎に一意に割り当てられた秘密情報を一方向関数に代入する回数が異なるようにして前記部分署名を生成する処理を行うこと、
を特徴とする署名システム。
【請求項４】
請求項３に記載の署名システムであって、
前記第二コンピュータの処理部は、予め定められた回数から前記第一コンピュータにおいて前記一方向関数に代入された回数を差し引いた回数だけ、前記部分署名を前記一方向関数に代入することで算出した算出値を全ての前記部分署名において特定し、特定した前記算出値を二つずつ圧縮関数で圧縮して算出した圧縮値をさらに二つずつ圧縮関数で圧縮する処理を繰り返すことにより、一つの前記マスタ公開鍵を生成する処理を行うこと、
を特徴とする署名システム。
【請求項５】
請求項１に記載の署名システムであって、
前記一方向関数は、ハッシュ関数であること、
を特徴とする署名システム。
【請求項６】
請求項２に記載の署名システムであって、
前記圧縮関数は、ハッシュ関数であること、
を特徴とする署名システム。
【請求項７】
請求項３に記載の署名システムであって、
前記一方向関数は、ブロック暗号を生成するものであり、
前記ブロック暗号は、前記秘密情報を鍵情報として入力して、ランダムに生成された初期ベクトルを暗号化するものであること、
を特徴とする署名システム。
【請求項８】
請求項６又は７に記載の署名システムであって、
前記ブロック暗号は、ＡＥＳ暗号であること、
を特徴とする署名システム。
【請求項９】
請求項４に記載の署名システムであって、
前記圧縮関数は、ブロック暗号を生成するものであり、
前記ブロック暗号は、ランダムに生成された初期ベクトルを第一鍵情報で暗号化することにより第一暗号化情報を生成し、当該第一暗号化情報を第二鍵情報で暗号化することにより第二暗号化情報を生成し、当該第二暗号化情報を前記第一鍵情報で暗号化することにより生成されるものであり、
前記第一鍵情報及び前記第二鍵情報は、前記算出値又は前記圧縮値であること、
を特徴とする署名システム。
【請求項１０】
請求項２に記載の署名システムであって、
前記第二コンピュータの処理部は、前記部分署名を圧縮関数で圧縮することによりワンタイム公開鍵を生成し、当該ワンタイム公開鍵から第一公開鍵を生成し、第一公開鍵からワンタイム署名を生成して、当該ワンタイム署名を圧縮関数で圧縮することによりワンタイム公開鍵を生成し、当該ワンタイム公開鍵から第二公開鍵を生成する処理を任意の第ｎ公開鍵（ｎは２以上の自然数）まで繰り返し行い、当該第ｎ公開鍵を予め記憶部に記憶されている第ｎ公開鍵と比較することで検証する処理を行うこと、
を特徴とする署名システム。
【請求項１１】
第一コンピュータで生成されたデジタル署名を第二コンピュータで検証する署名方法であって、
前記第一コンピュータの処理部において、デジタル署名をするデータを先頭ビットから順に特定のビット数毎のグループに分けて一方向関数に代入することで当該グループ毎の部分署名を生成する過程と、
前記第一コンピュータの処理部において、生成した当該グループ毎の部分署名を、順次、前記第二コンピュータに出力する過程と、
を備えることを特徴とする署名方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル署名を検証する署名システム及び署名方法に関する。
【背景技術】
【０００２】
デジタル署名とは、メッセージ送信者の身元及びこのメッセージの保全性を証明することができる暗号化されたデータである。
【０００３】
ここで、デジタル署名を具体化する一つの方法であるワンタイム署名のスケーラビリティの低さを大きく向上させる簡潔な解決策として、マークル署名が開発された。
【０００４】
特許文献１に記載されているように、マークル署名は、ワンタイム署名方式の複数のインスタンスを使用して、各ワンタイム公開鍵を単一のマスタ公開鍵に対して認証する方法を提供している。特に、２つのデータブロックを１つのデータブロックに圧縮する圧縮関数を使用して、ワンタイム公開鍵を葉とし、マスタ公開鍵をルートとする二進木を構築する。マスタ公開鍵は一度だけ配送され、システムによって生成されるすべての署名の検証に使用することができる。
【０００５】
また、公開鍵暗号システム及びデジタル署名の業界標準はＲＳＡである。ＲＳＡの安全性は、大きな整数を２つの素数の積に因数分解することの困難さに依拠している。現在のテクノロジー及びアルゴリズムは、整数が十分に大きい（通常、１０２４ビット）場合にこの問題を解くことができない。
【０００６】
しかし、非特許文献１に記載されているように、量子コンピュータと呼ばれる新種のコンピュータはこのような素因数を容易に見つけられることが分かっており、量子コンピュータを構築することが可能になれば、その結果として、広く使用されている公開鍵暗号システムは危殆化するものといわれている。
【０００７】
【特許文献１】米国特許第４３０９５６９号公報
【非特許文献１】J. Buchmann et al., 「Post-Quantum Signatures」, Cryptology ePrint Archive: Report 2004/297
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載されたマークル署名においては、署名サイズが非常に大きくなっており、大きな署名はネットワークの輻輳を発生させるだけでなく、特に、スマートカードを用いて署名を行う場合に帯域幅の小さなネットワークインタフェースを通して大量のデータを伝送する必要があるため、処理に時間がかかる。
【０００９】
また、量子コンピュータは近い将来に現実のものとなる可能性があるため、ＲＳＡ等の現在使用されている公開鍵暗号システムに対する代替技術を提供する必要がある。
【００１０】
そこで、本発明は、高度な安全性を有するマークル署名システムにおいて、伝送するデータサイズを小さくし、効率的に処理することのできる署名システムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
以上の課題を解決するため、本発明は、署名側の装置において署名するデータを特定の数のビット毎に署名して、順次、検証側の装置に送信し、検証側の装置では、受信した署名を順次処理して、全ての署名を受信することでワンタイム公開鍵を生成することができるようにする。
【００１２】
例えば、本発明は、第一コンピュータで生成されたデジタル署名を第二コンピュータで検証する署名システムであって、前記第一コンピュータの処理部は、デジタル署名をするデータを先頭ビットから順に特定のビット数毎のグループに分けて一方向関数に代入することで生成した当該グループ毎の部分署名を、順次、前記第二コンピュータに出力する処理を行うこと、を特徴とする。
【発明の効果】
【００１３】
以上のように、本発明によれば、高度な安全性を有するマークル署名を使用するが、伝送するデータサイズが小さく、効率的に処理することができる。
【発明を実施するための最良の形態】
【００１４】
図１は、本発明の第一の実施形態である署名システム１００の概略図である。
【００１５】
図示するように、署名システム１００は、スマートカード１１０と、読取装置１３０と、検証装置１４０と、を備えており、読取装置１３０と検証装置１４０とはネットワーク１６０を介して情報を送受信することができるようにされている。
【００１６】
スマートカード１１０は、図２（スマートカード１１０の概略図）に示されているように、記憶部１１１と、処理部１１２と、ＩＦ部１１３と、を備えている。
【００１７】
記憶部１１１は、鍵記憶部１１１ａと、ワンタイム情報記憶部１１１ｂと、マークル木情報記憶部１１１ｃと、一時情報記憶部１１１ｄと、を備えている。
【００１８】
鍵記憶部１１１ａには、ＡＥＳ（Advanced Encryption Standard）暗号化で使用される秘密シード及び公開シードを特定する情報が記憶される。
【００１９】
なお、秘密シード及び公開シードについては、公知の方法、例えば、処理部１１２にランダムな数を生成するランダム数生成部を設けておき、このランダム数生成部でランダムに生成した二つの数のうち、一方を秘密シード、他方を公開シードとして、鍵記憶部１１１ａに記憶すればよい。
【００２０】
ワンタイム情報記憶部１１１ｂには、各々のワンタイム署名毎に、各々のワンタイム署名で使用される秘密情報と、当該秘密情報に対応するインデックスと、が記憶される。なお、本実施形態においては、これらの情報が、各々のワンタイム署名を一意に識別するための識別情報であるワンタイム署名インデックス毎に記憶される。なお、ワンタイム署名インデックスについては、図６を用いて詳述する。
【００２１】
マークル木情報記憶部１１１ｃには、ワンタイム公開鍵からマスタ公開鍵を算出するために必要とされる認証パスを特定する情報が記憶される。ここで、認証パスについては、ワンタイム公開鍵を生成するためのワンタイム署名毎（ワンタイム署名インデックス毎）に記憶される。なお、認証パスについては、図６を用いて詳述する。
【００２２】
一時情報記憶部１１１ｄには、後述する処理部１１２において処理を行うために必要とされる情報を記憶する。
【００２３】
処理部１１２は、鍵処理部１１２ａと、乱数処理部１１２ｂと、一方向関数処理部１１２ｃと、圧縮関数処理部１１２ｄと、ハッシュ関数処理部１１２ｅと、署名生成部１１２ｆと、を備えている。
【００２４】
鍵処理部１１２ａは、ワンタイム署名で使用する秘密情報を生成する。秘密情報は、当該秘密情報の各々に割り振られたインデックスを鍵記憶部１１１ａに記憶されている秘密シードを鍵として用いてＡＥＳ暗号化することにより生成される。
【００２５】
ここで、ＡＥＳ暗号化の具体的な計算方法については、Joan Daemen and Vincent Rijmen, 「The Design of Rijndael: AES - The Advanced Encryption Standard.」 Springer-Verlag, 2002に詳しく記載されている。
【００２６】
なお、鍵処理部１１２ａで生成した秘密情報については、対応するインデックスと共にワンタイム情報記憶部１１１ｂに記憶される。
【００２７】
また、本実施形態においては、ＡＥＳ暗号化を行っているが、このような態様に限定されず、例えば、他のブロック暗号化方式やハッシュ関数に基づく暗号化方式を採用することも可能である。
【００２８】
乱数処理部１１２ｂは、あるカウンタ値を入力として鍵情報を用いてＡＥＳ暗号化を行う。
【００２９】
例えば、本実施形態においては、各関数に割り振られたインデックスをカウンタ値として入力し、鍵記憶部１１１ａに記憶されている公開シードを鍵として用いてＡＥＳ暗号化することで初期ベクトルを生成し、後述する一方向関数処理部１１２ｃ及び圧縮関数処理部１１２ｄに出力する。
【００３０】
なお、本実施形態においては、ＡＥＳ暗号化を行っているが、このような態様に限定されず、例えば、他のブロック暗号化方式やハッシュ関数に基づく暗号化方式を採用することも可能である。
【００３１】
一方向関数処理部１１２ｃは、乱数処理部１１２ｅで生成した初期ベクトルを入力し、鍵処理部１１２ａで生成した秘密情報を鍵情報として用いてＡＥＳ暗号化する。
【００３２】
なお、本実施形態においては、ＡＥＳ暗号化を行っているが、このような態様に限定されず、例えば、他のブロック暗号化方式やハッシュ関数に基づく暗号化方式を採用することも可能である。
【００３３】
圧縮関数処理部１１２ｄは、乱数処理部１１２ｅで生成した初期ベクトルを入力し、一方向関数処理部１１２ｃの出力値のうち、圧縮する一方の出力値を鍵情報として用いてＡＥＳ暗号化を施して暗号化値を算出する。次に、当該暗号化値を、圧縮する他方の出力値を鍵情報として用いてＡＥＳ暗号化を施して暗号化値を算出する。さらに、当該暗号化値を、前述の圧縮する一方の出力値を鍵情報として用いてＡＥＳ暗号化を施すことで圧縮値を算出する。
【００３４】
例えば、初期ベクトルをｖ、一方向関数の一方の出力値をａ、他方の出力値をｂ、とすると、圧縮関数処理部１１２ｄは、下記の（１）式のような計算を行う。
【００３５】
【数１】
2008103975.tif 000003
【００３６】
ここで、ｈは圧縮値、ＡＥＳａはａを鍵情報とするＡＥＳ暗号化、ＡＥＳｂはｂを鍵情報とするＡＥＳ暗号化を意味する。
【００３７】
現実では本実施形態独自のトリプルＡＥＳ構造は２鍵トリプル暗号化法（two-key triple-encryption method）に対応し、これは、圧縮関数ではなく純粋に暗号化関数として使用される場合にＤＥＳ等の弱い暗号の安全性を上げるために使用される。しかし実際には、純粋に暗号化を目的とする場合、３鍵トリプル暗号化が多くの場合に好ましい。この場合、第３の入力ｍ３を最後の暗号化ステップにおいて使用する。３鍵トリプル暗号化は暗号化の文脈の中では安全であるが、圧縮関数として使用される場合は完全に安全であるとはいえない。他方、２鍵トリプル暗号化はセキュアな圧縮関数である。２鍵トリプル暗号化を圧縮関数として使用することはこれまでしられていない。
【００３８】
ハッシュ関数処理部１１２ｅは、署名するメッセージのハッシュダイジェストを生成する。
【００３９】
署名生成部１１２ｆは、ハッシュ関数処理部１１２ｅで生成されたハッシュダイジェストからワンタイム署名を生成する。
【００４０】
ここで、本実施形態においては、ハッシュダイジェストの各ビットに、ハッシュダイジェストの先頭位置からインデックスを二つずつ割り振る。そして、各々のビットの値が「１」であれば割り振られた二つのインデックスのうち一番目のインデックスに対応する秘密情報と、二番目のインデックスに対応する秘密情報を一方向関数処理部１１２ｃでＡＥＳ暗号化した暗号化値と、を対応させることで部分ワンタイム署名を生成する。一方、各々のビットの値が「０」であれば割り振られた二つのインデックスのうち一番目のインデックスに対応する秘密情報を一方向関数処理部１１２ｃでＡＥＳ暗号化した暗号化値と、二番目のインデックスに対応する秘密情報と、を対応させることで部分ワンタイム署名を生成する。この具体例については、図６を用いて詳述する。
【００４１】
ＩＦ部１１３は、後述する読取装置１３０との間で情報の送受信を行うためのインタフェースである。なお、接続は接点なしであっても（この場合、データはアンテナを使用してワイヤレス送信される）、接点ありであってもよい。
【００４２】
以上に記載したスマートカードは、例えば、図１９に示すようなＩＣカード１７０で実現可能である。
【００４３】
ＩＣカード１７０は、アンテナ１７１と、アンテナ１７１に接続されたＩＣチップ１７２と、を備えている。
【００４４】
ここで、記憶部１１１については、ＩＣチップ１７２におけるＥＥＰＲＯＭ（Electronically Erasable and Programmable Read Only Memory）等の外部記憶装置１７２ａにより実現可能であり、処理部１１２については、ＩＣチップ１７２におけるＣＰＵ（Central Processing Unit）１７２ｂにおいて外部記憶装置１７２ａに記憶されている所定のプログラムを実行することで実現可能であり、ＩＦ部１１３については、アンテナ１７１により実現可能である。
【００４５】
なお、処理部１１２で行っている処理については、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよい。
【００４６】
図３は、読取装置１３０の概略図である。
【００４７】
図示するように、読取装置１３０は、ＩＦ部１３１と、処理部１３２と、送受信部１３３と、を備えている。
【００４８】
ＩＦ部１３１は、スマートカード１１０との間で情報の送受信を行うためのインタフェースである。
【００４９】
処理部１３２は、読取装置１３０全体の処理を制御する制御部である。
【００５０】
送受信部１３３は、ネットワーク１６０を介して情報の送受信を行うためのインタフェースであり、例えば、ＮＩＣ（Network Interface Card）を利用すればよい。
【００５１】
ここで、読取装置１３０については、例えば、図２０に示すいわゆるコンピュータ１８０により実現可能である。
【００５２】
コンピュータ１８０は、ＣＰＵ１８１と、メモリ１８２と、外部記憶装置１８３と、入力装置１８４と、出力装置１８５と、通信装置１８６と、リーダライタ１８７と、これらを接続するバス１８８と、を備えている。
【００５３】
そして、例えば、ＩＦ部１３１は、スマートカードに対して情報を読み書きすることのできるリーダライタ１８７により実現可能であり、処理部１３２は、外部記憶装置１８３に記憶されている所定のプログラムをメモリ１８２に読み出してＣＰＵ１８１で実行することにより実現可能であり、送受信部１３３は、ＮＩＣ等の通信装置１８６により実現可能である。
【００５４】
図４は、検証装置１４０の概略図である。
【００５５】
図示するように、検証装置１４０は、記憶部１４１と、処理部１４２と、送受信部１４３と、を備えている。
【００５６】
記憶部１４１は、検証情報記憶部１４１ａと、一時情報記憶部１４１ｂと、を備えている。
【００５７】
検証情報記憶部１４１ａには、スマートカード１１０から読み取られた部分ワンタイム署名を検証するための情報が記憶されている。
【００５８】
例えば、本実施形態においては、後述するマークル木のマスタ公開鍵と、乱数生成部１４２ａで初期ベクトルを算出するための公開シードと、が記憶される。
【００５９】
一時情報記憶部１４１ｂには、後述する処理部１４２において処理を行うために必要とされる情報を一時的に記憶する。
【００６０】
処理部１４２は、乱数生成部１４２ａと、一方向関数処理部１４２ｂと、圧縮関数処理部１４２ｃと、ハッシュ関数処理部１４２ｄと、署名検証部１４２ｅと、を備えている。
【００６１】
乱数処理部１４２ａは、スマートカード１１０における乱数処理部１１２ｂと同様の処理を行う。但し、乱数処理部１４２ａで使用する公開シードは、検証情報記憶部１４１ａに記憶されているものを使用する。
【００６２】
一方向関数処理部１４２ｂは、スマートカード１１０における一方向関数処理部１１２ｃと同様の処理を行う。
【００６３】
圧縮関数処理部１４２ｃは、スマートカード１１０における圧縮関数処理部１１２ｄと同様の処理を行う。
【００６４】
ハッシュ関数処理部１４２ｄは、スマートカード１１０から読み取られたメッセージのハッシュダイジェストを生成する。
【００６５】
署名検証部１４２ｅは、スマートカード１１０から読み取られた部分ワンタイム署名からワンタイム公開鍵を算出し、算出したワンタイム公開鍵とスマートカード１１０から読み取られた認証パスからマスタ公開鍵を算出し、検証情報記憶部１４１ａに記憶されているマスタ公開鍵と比較して、これらが一致する場合には承認を行い、一致しない場合には拒絶する。
【００６６】
送受信部１４３は、ネットワーク１６０を介して情報の送受信を行うためのインタフェースであり、例えば、ＮＩＣを利用すればよい。
【００６７】
なお、以上に記載した検証装置１４０については、図２１に示すような、いわゆるコンピュータ１９０により実現することが可能である。
【００６８】
例えば、記憶部１４１は、外部記憶装置１９３により実現可能であり、処理部１４２は、外部記憶装置１９３に記憶されている所定のプログラムをメモリ１９２に読み込み、ＣＰＵ１９１で実行することにより実現可能であり、送受信部１４３は、ＮＩＣ等の通信装置１９６により実現可能である。
【００６９】
図５は、本実施形態におけるワンタイム署名及びワンタイム公開鍵を説明するための概略図である。
【００７０】
本実施形態におけるワンタイム署名は一方向関数を組み合わせることにより算出され、ワンタイム公開鍵は圧縮関数を組み合わせることにより算出される。
【００７１】
ここで、本実施形態においては、ｎビットのメッセージ（ダイジェスト）ｍに署名するために、２ｎ個の秘密情報ｘ０，０、ｘ０，１、…、ｘ０，２ｎ−１を使用する。なお、この秘密情報については、スマートカード１１０の鍵処理部１１２ａが生成し、ワンタイム情報記憶部１１１ｂに記憶する。
【００７２】
また、秘密情報ｘ０，０、ｘ０，１、・・・、ｘ０，２ｎ−１の下付き文字（０，０）、（０，１）、・・・、（０，２ｎ−１）はインデックスを示し、当該インデックスの第一項目は秘密情報であることを示す識別子である「０」が割り当てられており、第二項目は各インデックスが割り当てられる順番が０から順に連番で割り当てられている。
【００７３】
なお、秘密情報に割り振られるインデックスはこのような態様に限定されるわけではなく、第一項目は秘密情報であることを識別することができるものであればよく、また、第二項目も秘密情報が割り当てられるメッセージ（ダイジェスト）の先頭からの位置を識別することができるものであればどのようなものであってもよい。
【００７４】
ワンタイム公開鍵は、一方向関数Ｏを使用して計算される値Ｏ（ｘ０，０）、Ｏ（ｘ０，１）、・・・、Ｏ（ｘ０，２ｎ−１）を葉として構築される二進木構造（ＯＴ）におけるルートであり、圧縮関数Ｋを使用してこれらの値を２つずつ再帰的に結合することで算出される。
【００７５】
なお、図５に示すように、二進木構造に配置されるノードで行われる計算を示す関数にもインデックスが付与される。即ち、一方向関数Ｏ１，０、Ｏ１，１、・・・、Ｏ１，７の下付き文字、および、圧縮関数Ｋ４，０、Ｋ３，０、Ｋ３，１、Ｋ２，０、Ｋ２，１、Ｋ２，２、Ｋ２，３の下付き文字、がインデックスである。
【００７６】
ここで、これらのノードにおける関数に割り振られるインデックスは、第一項目は葉からの高さ（距離）が１から順に連番で割り当てられており、第二項目は各高さ（距離）における位置（計算される順番）が０から順に連番で割り当てられている。
【００７７】
なお、これらの関数に割り振られるインデックスはこのような態様に限定されるわけではなく、二進木構造における葉からの高さ（距離）と、各高さ（距離）における位置（計算される順番）と、を特定することができるものであればどのようなものであってもよい。
【００７８】
まず、ワンタイム署名の生成方法について説明する。ワンタイム署名は、スマートカード１１０の署名生成部１１２ｆにおいて生成される。
【００７９】
ここで、本説明においては、簡易化のために４ビットのメッセージを署名する場合について説明するが、実際に多く使用されている１２８ビット又は２５６ビットのメッセージにも適用可能である。
【００８０】
４ビットのメッセージに署名するには、８個の秘密情報、すなわちｘ０，０、ｘ０，１、・・・、ｘ０，７が必要である。本発明による好ましい実施形態では、秘密情報は、鍵処理部１１２ａにおいて、鍵記憶部１１１ａに記憶されている秘密シードを鍵として用いて各インデックス（０，０）、（０，１）、・・・、（０，７）をＡＥＳ暗号化することにより生成される。即ち、下記の（２）式で計算される。
【００８１】
【数２】
2008103975.tif 000004
【００８２】
ここで、ｓｓは鍵記憶部１１１ａに記憶されている秘密シードであり、（０‖ｉ）はインデックスを周知の方法で結合させたものであり、ｉ＝０，１，２，３，・・・，７である。
【００８３】
次に、秘密情報ｘ０，０、ｘ０，１、・・・、ｘ０，７を一方向関数に入力することにより、二進木の葉ｘ１，０、ｘ１，１、ｘ１，２、ｘ１，３、ｘ１，４、ｘ１，５、ｘ１，６、及びｘ１，７を算出することができる。
【００８４】
この点、本実施形態においては、署名するメッセージ（ダイジェスト）の最初のビットから順に二つのインデックスを各々のビットに割り振り、署名するメッセージ（ダイジェスト）の各々の二つのインデックスに対応するビットの値が「０」であれば、付与されたインデックスのうち一番目の（左側に位置する）インデックスに対応する秘密情報と、二番目の（右側に位置する）インデックスに対応する秘密情報を一方向関数に入力して算出した葉と、をペアにして部分ワンタイム署名とする。
【００８５】
一方、署名するメッセージ（ダイジェスト）の二つのインデックスに対応するビットの値が「１」であれば、付与されたインデックスのうち一番目の（左側に位置する）インデックスに対応する秘密情報を一方向関数に入力して算出した葉と、二番目の（右側に位置する）インデックスに対応する秘密情報と、をペアにして部分ワンタイム署名とする。
【００８６】
例えば、図５において、署名するメッセージが「０１１０」の場合には、ワンタイム署名として、（（ｘ１，０，ｘ０，１），（ｘ０，２，ｘ１，３），（ｘ０，４，ｘ１，５），（ｘ１，６，ｘ０，７））が生成される。
【００８７】
なお、図５に示す二進木構造については、署名を行うメッセージ毎に異なるものを使用するため、使用する二進木構造を識別するために、ワンタイム署名インデックスが各々割り振られる。例えば、図６のＯＴ１，０、ＯＴ１，１、・・・、ＯＴ１，７の下付き文字（１，０）、（１，１）、・・・、（１，７）がワンタイム署名インデックスを示しているが、当該インデックスの第一項目はワンタイム署名であることを示す識別子である「１」が割り当てられており、第二項目は各ワンタイム署名（二進木構造）が使用される順番が０から順に連番で割り当てられている。
【００８８】
なお、ワンタイム署名インデックスはこのような態様に限定されるわけではなく、第一項目はワンタイム署名（二進木構造）であることを識別することができるものであればよく、また、第二項目も第二項目は各ワンタイム署名（二進木構造）が使用される順番を特定することができるものであればどのようなものであってもよい。
【００８９】
なお、スマートカード１１０の署名生成部１１２ｆは、生成した部分ワンタイム署名を順次、読取装置１３０を介して検証装置１４０に送信する。なお、部分ワンタイム署名を送信する場合には、ワンタイム公開鍵を算出するのに必要とされる二進木構造を特定することができるように、ワンタイム署名インデックス、または、各部分ワンタイム署名を生成した秘密情報に対応するインデックス、をともに送信する。
【００９０】
そして、スマートカード１１０から部分ワンタイム署名を受け取った検証装置１４０の署名検証部１４２ｅは、既に受け取っているメッセージの対応するビットの値から、受信した部分ワンタイム署名に含まれる秘密情報を特定し、当該秘密情報を一方向関数に入力して対応するインデックスから算出された初期ベクトルを用いることで、欠落している葉の値を計算して、図５に示す二進木構造の対応する圧縮関数Ｋに入力することで順次計算をおこない、全ての部分ワンタイム署名を受信することで、二進木のルートであるワンタイム公開鍵を算出する。
【００９１】
また、検証装置１４０の署名検証部１４２ｅは、算出したワンタイム公開鍵からマスタ公開鍵の算出を行う。
【００９２】
図６は、ワンタイム公開鍵からマスタ公開鍵の算出を行う処理を説明するための概略図である。
【００９３】
署名検証部１４２ｅは、ワンタイム公開鍵ｏｔｐ１，０、ｏｔｐ１，１、・・・、ｏｔｐ１，７を圧縮関数を用いることにより結合して一つのマスタ公開鍵ｐを算出する。
【００９４】
ここで、ワンタイム公開鍵ｏｔｐ１，０、ｏｔｐ１，１、・・・、ｏｔｐ１，７の下付き文字（１，０）、（１，１）、・・・、（１，７）は、ワンタイム署名インデックスを示している。
【００９５】
また、マークル木のノードを形成する圧縮関数Ｋに添付されている下付き文字（２，０）、（２，１）、・・・、（４，０）も、インデックスを示しているが、これは図５で説明したものと同様である。
【００９６】
そして、各圧縮関数で使用する初期ベクトルは、各圧縮関数のインデックスを周知の方法で結合した値を入力して検証情報記憶部１４１ａに記憶されている公開シードを鍵として用いてＡＥＳ暗号化することにより算出される。
【００９７】
なお、署名検証部１４２ｅでマスタ公開鍵ｐを実際に算出する場合には、全てのワンタイム公開鍵を圧縮関数で結合するのではなく、スマートカード１１０から送られてくる認証パスを用いて算出する。
【００９８】
例えば、図６に示されているように、署名するメッセージから算出されたワンタイム署名ｍ’からワンタイム公開鍵ｏｔｐ１，２が算出された場合、まず、ワンタイム公開鍵ｏｔｐ１，２とワンタイム公開鍵ｏｔｐ１，３とを圧縮関数Ｋ２，１で結合することにより、圧縮値ｈ２，１が算出される。そして、圧縮値ｈ２，１と圧縮値ｈ２，０とを圧縮関数Ｋ３，０で結合することにより圧縮値ｈ３，０が算出される。さらに、圧縮値ｈ３，０と圧縮値ｈ３，１とを圧縮関数Ｋ４，０で結合することにより、マスタ公開鍵ｐが算出される。
【００９９】
即ち、ワンタイム署名ｍ’に対応するワンタイム公開鍵ｏｔｐ１，２には、認証パスとして、ワンタイム公開鍵ｏｔｐ１，３、圧縮値ｈ２，０、および、圧縮値ｈ３，１、が必要となる。
【０１００】
従って、スマートカード１１０は、署名するメッセージからワンタイム署名ｍ’を算出するとともに、使用した秘密情報からワンタイム署名ｍ’に対応するワンタイム公開鍵ｏｔｐ１，２に必要となる認証パスをマークル木情報記憶部１１１ｃに記憶されている情報から特定して、特定した値を認証パスとして検証装置１４０に送信する。
【０１０１】
なお、マークル木情報記憶部１１１ｃには、このような認証パスを特定するために、各ノード間の関連を特定する情報（各ノードのインデックス）と、各ノードで算出される圧縮値と、を特定する情報が記憶されている。これらの情報は、署名システム１００のセットアップ時等において、マークル木及び当該マークル木に属する二進木構造を一度全て計算しておき、取得すればよい。
【０１０２】
そして、検証装置１４０の署名検証部１４２ｅは、受信したワンタイム署名ｍ’と認証パスとにより算出されるマスタ公開鍵ｐと、検証情報記憶部１４１ａに記憶されているマスタ公開鍵と、を比較してこれらが一致した場合には署名を承認する。
【０１０３】
以上のように構成される本実施形態における署名システム１００での処理を、図７に示すシーケンス図を用いて説明する。なお、本シーケンス図においてスマートカード１１０と検証装置１４０間での情報の送受信は、読取装置１３０を介して行われる。
【０１０４】
まず、スマートカード１１０において検証するメッセージｍの入力を受け付け、一時情報記憶部１１１ｄに記憶する（Ｓ１０）。なお、メッセージｍの受け付けは、例えば、読取装置１３０を介して受け付ければよい。
【０１０５】
そして、受け付けたメッセージｍのダイジェストＨ（ｍ）が、ハッシュ関数処理部１１２ｅにおいて所定のハッシュ関数Ｈを用いて計算される（Ｓ１１）。
【０１０６】
また、入力されたメッセージｍは、読取装置１３０の送受信部１３３を介して検証装置１４０に送信される（Ｓ１２）。
【０１０７】
そして、検証装置１４０のハッシュ関数処理部１４２ｄにおいても、受信したメッセージｍのダイジェストＨ（ｍ）が所定のハッシュ関数Ｈを用いて計算される（Ｓ１３）。
【０１０８】
次に、スマートカード１１０の署名生成部１１２ｆは、署名の計算に先立って、メッセージｍに使用するインデックスを含む署名側システムの状態を一時情報記憶部１１１ｄに記憶される（Ｓ１４）。なお、このような情報を記憶することにより、電源供給がなくなった場合にシステムが同じワンタイム署名を再び使用しないようにすることができる。
【０１０９】
次に、スマートカード１１１の署名生成部１１２ｆは、メッセージｍのダイジェストＨ（ｍ）の最初のビットから部分ワンタイム署名を生成し（Ｓ１５）、順次、検証装置１４０に送信する（Ｓ１６）。
【０１１０】
部分ワンタイム署名を受信した検証装置１４０では、ステップＳ１３で生成したダイジェストＨ（ｍ）から受信した部分ワンタイム署名に対応するビットを確認することで、一方向関数に入力する秘密情報を特定して、一方向関数処理部１４２ｃに入力して検証情報記憶部１４１ａに記憶されている公開シードを用いて二進木構造の欠落した葉を算出する（Ｓ１７）。
【０１１１】
ステップＳ１５〜Ｓ１７の処理をダイジェストＨ（ｍ）の全てのビットにつき繰り返し行い、二進木構造の全ての葉を算出し、これらの葉を圧縮関数処理部１４２ｃに入力して、ワンタイム公開鍵を生成する（Ｓ１８）。
【０１１２】
なお、スマートカード１１０では、検証装置１４０に送信する認証パスを生成して（Ｓ１９）、検証装置１４０に送信する（Ｓ２０）。
【０１１３】
認証パスを受信した検証装置１４０では、生成したワンタイム署名と受信した認証パスを用いてマスタ公開鍵を生成して、検証を行う（Ｓ２１）。
【０１１４】
そして、検証の結果、生成したマスタ公開鍵が検証情報記憶部１４１ａに記憶されているマスタ公開鍵と一致する場合には署名を承認し、これらが一致しない場合には署名を拒絶する（Ｓ２２）。
【０１１５】
以上のように、本実施形態においては、署名の生成と署名の検証とを並行して行うことができるため、処理時間を短縮することができるほか、一つの署名を行うために必要となる二進木に関する情報は一つに限られるため、情報の容量も少なくて済む。なお、他のメッセージに署名を行う場合には、そのメッセージに必要な情報をメモリに記憶すればよい。
【０１１６】
図８は、本発明の第二の実施形態である署名システムで使用されるスマートカード２１０の概略図である。
【０１１７】
本実施形態におけるスマートカード２１０は、第一の実施形態と比較して、記憶部２１１のマークル木情報記憶部２１１ｃに記憶される情報、および、処理部２１２の鍵処理部２１２ａ及び署名生成部２１２ｆでの処理が異なっているため、以下、これらの異なっている点に関連する事項について説明する。
【０１１８】
本実施形態においては、図１１を用いて後に詳述するように、下位のマークル木と、上位のマークル木の二つのマークル木が使用されるため、マークル木情報記憶部２１１ｃには、これらの二つのマークル木における認証パスを特定することができるように、各ノード間の関連を特定する情報（各ノードのインデックス）と、各ノードで算出される圧縮値と、を特定する情報が、下位のマークル木と上位のマークル木の各々について記憶される。
【０１１９】
また、本実施形態におけるマークル木情報記憶部２１１ｃには、下位側マークル木で使用されるインデックスを特定する情報を各々のマークル木毎に記憶する。
【０１２０】
さらに、本実施形態におけるマークル木情報記憶部２１１ｃには、上位側のマークル木のワンタイム署名が記憶される。なお、上位側のマークル木のワンタイム署名は、下位のマークル木のルートである下位側のマスタ公開鍵から生成する。
【０１２１】
また、本実施形態においては、図１０を用いて後に詳述するように、署名するメッセージ（またはそのダイジェスト）の任意の連続するビット（本実施形態では連続する２ビット）を組（クイット（quit）という）として、当該クイット毎に部分ワンタイム署名を生成するようにしているため、署名生成部２１２ｆは、メッセージの先頭ビットからクイット毎に部分ワンタイム署名を生成して検証装置２４０に送信するようにしている。
【０１２２】
また、本実施形態における鍵処理部２１２ａは、下位のマークル木のルートである下位側のマスタ公開鍵から図１０に示す方法でワンタイム署名を生成し、上位側のマークル木のワンタイム署名としてマークル木情報記憶部２１１ｃに記憶する。
【０１２３】
図９は、本発明の第二の実施形態である署名システムで使用される検証装置２４０の概略図である。
【０１２４】
本実施形態における検証装置２４０は、第一の実施形態と比較して、記憶部２４１の検証情報記憶部２４１ａに記憶される情報、および、処理部２４２の署名検証部２４２ｅでの処理が異なっているため、以下、これらの異なっている点に関連する事項について説明する。
【０１２５】
本実施形態においては、図１１を用いて後に詳述するように、下位のマークル木と、上位のマークル木の二つのマークル木が使用されるため、検証情報記憶部２４１ａには、これらの二つのマークル木におけるマスタ公開鍵を特定する情報が記憶される。
【０１２６】
なお、第一の実施形態と同様に、検証情報記憶部２４１ａには、乱数生成部１４２ａで初期ベクトルを算出するための公開シードも記憶される。
【０１２７】
また、本実施形態においては、図１０を用いて後に詳述するように、署名するメッセージの任意のビットをクイットとして、当該クイット毎に部分ワンタイム署名を生成するようにしており、署名検証部１４２ｅは、メッセージの先頭ビットから任意のビット毎に構成されるクイットから、当該クイットに対応する部分ワンタイム署名に含まれる要素を一方向関数に入力して処理する回数を特定し、下位のマークル木における葉を算出する。
【０１２８】
図１０は、本実施形態におけるワンタイム署名及びワンタイム公開鍵を説明するための概略図である。
【０１２９】
本実施形態における部分ワンタイム署名も、第一の実施形態と同様に、一方向関数を組み合わせることにより算出され、ワンタイム公開鍵は、圧縮関数を組み合わせることにより算出される。
【０１３０】
本実施形態においては、メッセージ（ダイジェスト）の先頭から２ビットずつの組を１クイット（以下、「ｑ」とする）とし、１ｑ毎に、部分ワンタイム署名を生成する。なお、本実施形態においては、１ｑに署名をするために２つの秘密情報が使用される。
【０１３１】
そして、１ｑ毎にワンタイム署名を生成するために、２ビットの組が（０，０）の場合にはｑ＝０、（０，１）の場合にはｑ＝１、（１，０）の場合にはｑ＝２、（１，１）の場合にはｑ＝３の値とし、秘密情報ｘ０，ｉを用いて以下の値を定義する。なお、Ｏは、一方向関数である。
【０１３２】
ｘ１，ｉ＝Ｏ１，ｉ（ｘ０，ｉ）
ｘ２，ｉ＝Ｏ２，ｉ（Ｏ１，ｉ（（ｘ０，ｉ））
ｘ３，ｉ＝Ｏ３，ｉ（Ｏ２，ｉ（Ｏ１，ｉ（（ｘ０，０）））
そして、部分ワンタイム署名に関しては、ｑの値に応じて以下の値を生成する。
【０１３３】
ｑ＝３の場合、ｘ０，０及びｘ３，１が部分ワンタイム署名となる。
【０１３４】
ｑ＝２の場合、ｘ１，０及びｘ２，１が部分ワンタイム署名となる。
【０１３５】
ｑ＝１の場合、ｘ２，０及びｘ１，１が部分ワンタイム署名となる。
【０１３６】
ｑ＝０の場合、ｘ３，０及びｘ０，１が部分ワンタイム署名となる。
【０１３７】
なお、これらの要素については一方向にのみ算出可能であり非対称となる。その理由は、以下の例から容易に理解することができる。メッセージの最初のクイットがｑ＝３であると仮定する。この場合、秘密ｘ０，０だけでなくｘ３，１＝Ｏ３，１（Ｏ２，１（Ｏ１，１（ｘ０，１）））も明らかにする。ここで、ある攻撃者が（ｘ０，０，ｘ３，１）を傍受し、このペアを使用して異なるクイットｑ’に署名しようとすると仮定する。攻撃者は、ｘ１，０＝Ｏ１，０（ｘ０，０）、ｘ２，０＝Ｏ２，０（Ｏ１，０（ｘ０，０））、又はｘ３，０＝Ｏ３，０（Ｏ２，０（Ｏ１，０（ｘ０，０）））を計算することができた場合であっても結果として失敗し、分かるのはｘ３，１だけであり、またＯは一方向であるため、メッセージｑ’＝０、１、又は２に署名するために必要であり得るｘ２，１、ｘ１，１、又はｘ０，１を計算することができない。
【０１３８】
例えば、メッセージの二進数表現がｍ＝（１１０１１０００）である場合、クイットで表すと、Ｍ＝（３１２０）になる。
【０１３９】
このメッセージに対応するワンタイム署名は（（ｘ０，０，ｘ３，１）、（ｘ２，２，ｘ１，３）、（ｘ１，４，ｘ２，５）、（ｘ３，６，ｘ０，７））となる。
【０１４０】
そして、本実施形態における署名生成部２１２ｆは、ワンタイム署名（（ｘ０，０，ｘ３，１）、（ｘ２，２，ｘ１，３）、（ｘ１，４，ｘ２，５）、（ｘ３，６，ｘ０，７））の各部分ワンタイム署名（ｘ０，０，ｘ３，１）、（ｘ２，２，ｘ１，３）、（ｘ１，４，ｘ２，５）、（ｘ３，６，ｘ０，７）を生成し、順次、検証装置２４０に送信する。
【０１４１】
そして、これらの部分ワンタイム署名を受信した検証装置２４０の署名検証部２４２ｅは、既に受け取っているメッセージの対応するビットの値から、受信した秘密情報を特定し、当該部分ワンタイム署名に含まれる要素を一方向関数に入力する回数を特定し、当該回数一方向関数に入力することで二進木構造の欠落している葉の値を計算し、全ての葉ｘ３，０、ｘ３，１、・・・、ｘ３，ｉの値が特定されると、圧縮関数を連続して適用して、二進木のルートであるワンタイム公開鍵を算出する。
【０１４２】
図１１は、ワンタイム公開鍵からマスタ公開鍵の算出を行う処理を説明するための概略図である。
【０１４３】
第一の実施形態においては、ワンタイム署名からワンタイム公開鍵を算出し、当該ワンタイム公開鍵を一つのマークル木に入力することで、一つのマスタ公開鍵ｐを算出している。
【０１４４】
これに対して、本実施形態においては、スマートカード２１０の署名生成部２１２ｆにおいて生成されたワンタイム署名から、検証装置２４０の署名検証部２４２ｅにおいて下位側のワンタイム公開鍵を算出し、当該下位側のワンタイム公開鍵を下位側のマークル木に入力することで、下位側のマスタ公開鍵ｐ’を算出して検証を行う。そして、この下位側のマスタ公開鍵ｐ’から上位側のワンタイム公開鍵を算出し、当該上位側のワンタイム公開鍵を上位側のマークル木に入力することで、上位側のマスタ公開鍵ｐを算出する。
【０１４５】
そして、このようにして算出した下位側のマスタ公開鍵ｐ’と上位側のマスタ公開鍵ｐをそれぞれ検証情報記憶部２４１ａに記憶されている下位側及び上位側のマスタ公開鍵と比較することで、これらが一致した場合に署名を認証するようにしている。
【０１４６】
なお、これらのマスタ公開鍵ｐ’、ｐの生成方法については、第一の実施形態における処理を上位側及び下位側の二回繰り返しているだけであるため、詳細な説明は省略する。
【０１４７】
このように、本実施形態においては、２つのレベルのマークル木を使用しているため、所与のトランザクションについて、下位のマークル木において記憶しなければならない情報は、一つのマークル木に関するものだけであるため、システムに必要な記憶容量は劇的に低減する。
【０１４８】
異なるマークル木で同じインデックスが使用されないように、マークル木のインデックスはその木内で使用されるあらゆるインデックスに添付される。たとえば、下位側のマークル木ＭＴ１，７のワンタイム署名ＯＴ１，５の４番目の秘密を計算するには、以下のインデックスが乱数生成モジュールと共に使用される：ｘ０，４＝ＡＥＳｓｓ（１‖７‖１‖５‖０‖４）。換言すれば、すべての構成要素のすべてのインデックスが連結される。なお、ここでは、簡易化のために、そのノードにおけるインデックスのみを記載している。
【０１４９】
なお、マークル木のインデックスについても、マークル署名インデックスと同様の方法で割り振ればよい。
【０１５０】
以上のように構成される第二の実施形態における署名システムでの処理を、図１２に示すシーケンス図を用いて説明する。なお、本シーケンス図においてスマートカード２１０と検証装置２４０間での情報の送受信は、読取装置１３０を介して行われる。
【０１５１】
まず、スマートカード２１０において検証するメッセージｍの入力を受け付け、一時情報記憶部１１１ｄに記憶する（Ｓ３０）。なお、メッセージｍの受け付けは、例えば、読取装置１３０を介して受け付ければよい。
【０１５２】
そして、受け付けたメッセージｍのダイジェストＨ（ｍ）が、ハッシュ関数処理部１１２ｅにおいて所定のハッシュ関数Ｈを用いて計算される（Ｓ３１）。
【０１５３】
また、入力されたメッセージｍは、読取装置１３０の送受信部１３３を介して検証装置２４０に送信される（Ｓ３２）。
【０１５４】
そして、検証装置２４０のハッシュ関数処理部１４２ｄにおいても、受信したメッセージｍのダイジェストＨ（ｍ）が所定のハッシュ関数Ｈを用いて計算される（Ｓ３３）。
【０１５５】
次に、スマートカード２１０の署名生成部２１２ｆは、署名の計算に先立って、メッセージｍに使用するインデックスを含む署名側システムの状態を一時情報記憶部１１１ｄに記憶する（Ｓ３４）。なお、このような情報を記憶することにより、電源供給がなくなった場合にシステムが同じワンタイム署名を再び使用しないようにすることができる。
【０１５６】
次に、スマートカード１１１の署名生成部２１２ｆは、メッセージｍのダイジェストＨ（ｍ）の最初のビットから順にクイットに分割して部分ワンタイム署名を生成し（Ｓ３５）、生成の終了したものから順に検証装置２４０に送信する（Ｓ３６）。
【０１５７】
部分ワンタイム署名を受信した検証装置２４０では、ステップＳ３３で生成したダイジェストＨ（ｍ）から受信した部分ワンタイム署名に対応するクイットを確認することで、部分ワンタイム署名に含まれる要素を一方向関数に入力する回数を特定して、一方向関数処理部１４２ｃに入力して検証情報記憶部２４１ａに記憶されている公開シードを用いて二進木の葉を算出する（Ｓ３７）。
【０１５８】
ステップＳ３５〜Ｓ３７の処理をダイジェストＨ（ｍ）の全てのビットにつき繰り返し行い、二進木の全ての葉が算出されることにより、これらの葉を圧縮関数処理部１４２ｃに入力して、ワンタイム公開鍵を生成する（Ｓ３８）。
【０１５９】
なお、スマートカード２１０では、検証装置２４０に送信する下位側の認証パスを生成して（Ｓ３９）、検証装置２４０に送信する（Ｓ４０）。
【０１６０】
そして、ステップＳ３８で生成したワンタイム公開鍵と、ステップＳ４０で受信した認証パスと、を用いて下位側のマスタ公開鍵ｐ’を算出して検証を行う（Ｓ４１）。検証の結果、署名が承認された場合には、次のステップに進み、署名が拒否された場合には、検証処理を終了するが、ここでは署名が承認されたものとして説明をつつける。
【０１６１】
次に、検証装置２４０の署名検証部２４２ｅは、送受信部１４３を介して検証の終了応答をスマートカード２１０に送信する（Ｓ４２）。
【０１６２】
終了応答を受信したスマートカード２１０の署名生成部２１２ｆにおいては、予め記憶している上位側のワンタイム署名を検証装置２４０に送信する（Ｓ４３）。
【０１６３】
また、スマートカード２１０の署名生成部２１２ｆは、上位側の認証パスを生成して（Ｓ４４）、検証装置２４０に送信する（Ｓ４５）。
【０１６４】
そして、検証装置２４０においては、ステップＳ４３で受信したワンタイム署名と、ステップＳ４５で受信した認証パスと、を用いて検証を行い（Ｓ４６）、検証の結果（承認又は拒絶）を終了応答としてスマートカード２１０に送信する（Ｓ４７）。
【０１６５】
なお、スマートカード２１０では、検証装置２４０に上位側の認証パスを送信してから（Ｓ４５）、鍵処理部２１２ａにおいて、次のメッセージに使用するための下位側のマークル木を生成し（Ｓ４８）、そのルートからワンタイム署名を生成して、上位側のマークル木のワンタイム署名としてマークル木情報記憶部２１１ｃに記憶する（Ｓ４９）。
【０１６６】
そして、スマートカード２１０の処理部２１２は、受信した終了応答を一時情報記憶部１１１ｄに記憶する（Ｓ５０）。
【０１６７】
以上のように、本実施形態においては、署名の生成と署名の検証とを並行して行うことができるため、処理時間を短縮することができるほか、一つの署名を行うために必要となる下位側マークル木も逐次生成されるため、記憶容量も少なくて済む。
【０１６８】
以上に記載した第二の実施形態においては、上位側のマークル木と下位側のマークル木の二つの階層を設けたが、このような態様に限定されず、より多くの階層を設けることも可能である。
【０１６９】
図１３は、本発明の第三の実施形態である署名システム３００の概略図である。
【０１７０】
図示するように、署名システム３００は、署名装置３１０と、検証装置３４０と、を備えており、署名装置３１０と検証装置３４０とはネットワーク１６０に接続されている。
【０１７１】
署名装置３１０は、図１４（署名装置３１０の概略図）に示されているように、記憶部３１１と、処理部３１２と、送受信部３１４と、を備えている。
【０１７２】
記憶部３１１は、鍵記憶部１１１ａと、ワンタイム情報記憶部３１１ｂと、一時情報記憶部１１１ｄと、を備えている。
【０１７３】
鍵記憶部１１１ａには、第一の実施形態と同様に、ＡＥＳ（Advanced Encryption Standard）暗号化で使用される秘密シード及び公開シードを特定する情報が記憶される。
【０１７４】
ワンタイム情報記憶部３１１ｂには、各々のワンタイム署名毎に、各々のワンタイム署名で使用されるインデックスと、当該インデックスに対応する秘密情報と、二進木のルートであるワンタイム公開鍵と、が記憶される。なお、本実施形態においては、これらの情報が、各々のワンタイム署名を一意に識別するための識別情報であるワンタイム署名インデックスに対応させて記憶される。
【０１７５】
一時情報記憶部１１１ｄには、後述する処理部１１２において処理を行うために必要とされる情報を一時的に記憶する。
【０１７６】
処理部３１２は、鍵処理部３１２ａと、乱数処理部１１２ｂと、一方向関数処理部１１２ｃと、圧縮関数処理部１１２ｄと、ハッシュ関数処理部１１２ｅと、署名生成部３１２ｆと、を備えている。
【０１７７】
鍵処理部１１２ａは、第一の実施形態と同様に、ワンタイム署名で使用する秘密情報を生成する。秘密情報は、ワンタイム署名で使用する各インデックスを鍵記憶部１１１ａに記憶されている秘密シードを鍵として用いてＡＥＳ暗号化することにより生成される。
【０１７８】
なお、鍵処理部１１２ａで生成した秘密情報については、対応するインデックスと共にワンタイム情報記憶部３１１ｂに記憶される。
【０１７９】
また、本実施形態においては、ＡＥＳ暗号化を行っているが、このような態様に限定されず、例えば、他のブロック暗号化方式やハッシュ関数に基づく暗号化方式を採用することも可能である。
【０１８０】
さらに、本実施形態においては、鍵処理部１１２ａは、署名するメッセージ毎に後述するノード（図１６参照）を生成して、生成したノードで使用するワンタイム公開鍵を、生成したノードに含まれる二進木構造に割り当てられたワンタイム署名インデックスに対応付けてワンタイム情報記憶部３１１ｂに記憶する。
【０１８１】
乱数処理部１１２ｂは、一方向関数処理部１１２ｃ、圧縮関数処理部１１２ｄ、および、ハッシュ関数処理部１１２ｅは、第一の実施形態と同様の処理を行う。
【０１８２】
署名生成部３１２ｆは、第二の実施形態と同様の処理により、ワンタイム署名を生成する。
【０１８３】
送受信部３１４は、ネットワーク１６０を介して情報の送受信を行うためのインタフェースであり、例えば、ＮＩＣを利用すればよい。
【０１８４】
なお、以上に記載した署名装置３１０については、図２１に示すような、いわゆるコンピュータ１９０により実現することが可能である。
【０１８５】
例えば、記憶部３１１は、外部記憶装置１９３により実現可能であり、処理部３１２は、外部記憶装置１９３に記憶されている所定のプログラムをメモリ１９２に読み込み、ＣＰＵ１９１で実行することにより実現可能であり、送受信部３１４は、ＮＩＣ等の通信装置１９６により実現可能である。
【０１８６】
図１５は、検証装置３４０の概略図である。
【０１８７】
図示するように、検証装置３４０は、記憶部３４１と、処理部３４２と、送受信部１４３と、を備えている。
【０１８８】
記憶部３４１は、検証情報記憶部３４１ａと、一時情報記憶部１４１ｂと、を備えている。
【０１８９】
本実施形態における検証情報記憶部１４１ａには、署名装置３１０から受信したワンタイム署名を検証するための情報が記憶されている。
【０１９０】
例えば、本実施形態においては、図１７に示す木構造を特定する情報が記憶される。
【０１９１】
一時情報記憶部１４１ｂには、後述する処理部１４２において処理を行うために必要とされる情報を一時的に記憶する。
【０１９２】
処理部３４２は、乱数生成部１４２ａと、一方向関数処理部１４２ｂと、圧縮関数処理部１４２ｃと、ハッシュ関数処理部１４２ｄと、署名検証部３４２ｅと、を備えている。
【０１９３】
乱数処理部１４２ａ、一方向関数処理部１４２ｂ、圧縮関数処理部１４２ｃ、および、ハッシュ関数処理部１４２ｄは、第一の実施形態と同様の処理を行う。
【０１９４】
署名検証部３４２ｅは、署名装置３１０から送信されたワンタイム署名からワンタイム公開鍵を算出し、また、署名装置３１０から送信された複数（本実施形態では２つ）のワンタイム公開鍵を圧縮関数で圧縮した圧縮値を算出して、算出したワンタイム公開鍵および圧縮値を圧縮関数で圧縮してノード毎の公開鍵を算出し、当該ノード毎の公開鍵からシステム全体のマスタ公開鍵を算出する。この処理の詳細は図１７を用いて説明する。
【０１９５】
送受信部１４３は、ネットワーク１６０を介して情報の送受信を行うためのインタフェースであり、例えば、ＮＩＣを利用すればよい。
【０１９６】
なお、以上に記載した検証装置１４０については、第一の実施形態と同様に、図２１に示すいわゆるコンピュータ１９０により実現することができる。
【０１９７】
なお、以上に記載した検証装置１４０については、図２１に示すような、いわゆるコンピュータ１９０により実現することが可能である。
【０１９８】
例えば、記憶部３４１は、外部記憶装置１９３により実現可能であり、処理部３４２は、外部記憶装置１９３に記憶されている所定のプログラムをメモリ１９２に読み込み、ＣＰＵ１９１で実行することにより実現可能であり、送受信部１４３は、ＮＩＣ等の通信装置１９６により実現可能である。
【０１９９】
図１６は、本実施形態で使用するノードＮｊ，ｉを説明するための概略図である。
【０２００】
ここで、ノードＮｊ，ｉに付けられた下付き文字（ｉ，ｊ）はノードのインデックスを示す。なお、ノードのインデックスについては図１７を用いて説明する。
【０２０１】
ノードＮｊ，ｉは、三つの二進木構造ＯＴ０、ＯＴ１、ＯＴ２と、二つの圧縮関数Ｋ０、Ｋ１と、を備えている。
【０２０２】
そして、各ノードＮｊ，ｉでは、他のノードＮｊ＋１，２ｉで算出された公開鍵Ｐｊ＋１，２ｉを二進木構造ＯＴ０に入力してワンタイム公開鍵ｏｐｔ０を算出し、また、他のノードＮｊ＋１，２ｉ＋１で算出された公開鍵Ｐｊ＋１，２ｉ＋１を二進木構造ＯＴ１に入力してワンタイム公開鍵ｏｐｔ１を算出して、これらのワンタイム公開鍵ｏｐｔ０、ｏｐｔ１を圧縮関数Ｋ０で圧縮することにより圧縮値を算出する。
【０２０３】
また、各ノードＮｊ，ｉでは、署名するメッセージｍｋを二進木構造ＯＴ２に入力してワンタイム署名を生成し、生成したワンタイム署名からワンタイム公開鍵ｏｐｔ２を算出する。
【０２０４】
そして、圧縮関数Ｋ０で圧縮することにより算出された圧縮値と、ワンタイム公開鍵ｏｐｔ２と、を圧縮関数Ｋ１で圧縮することにより、ノードＮｊ，ｉ毎の公開鍵Ｐｊ，ｉを算出する。
【０２０５】
例えば、メッセージｍｋを署名する場合、署名装置３１０の署名生成部３１２ｆにおいて、メッセージｍｋから部分ワンタイム署名を生成し、生成した部分ワンタイム署名を検証装置３４０に送信して、検証装置３４０が、部分ワンタイム署名をノードＮｊ，ｉに適用して、ノード毎の公開鍵Ｐｊ，ｉを算出する。
【０２０６】
なお、前述のように、乱数処理部１１２ｂは、入力として各圧縮関数、一方向関数のインデックスのみならずノードのインデックスも結合して初期ベクトルを算出する。たとえば、ノードＮ２，１１１３１内のＫ４の初期ベクトルは単にＡＥＳｓｐ（４）ではなく初期ＡＥＳｓｐ（２‖１‖４）として算出される。
【０２０７】
図１７は、本実施形態である署名システム３００において、検証を行うための処理を説明するための概略図である。
【０２０８】
まず、最初は、署名システム３００において、一つのノードＮ０，０が生成される。そして、このシステムのマスタ公開鍵はノードＮ０，０のルートであるｐとなる。
【０２０９】
一つのノードＮ０，０では、一つのメッセージｍ０しか署名することができないため、次のメッセージｍ１を署名するためには、マスタ公開鍵を算出するためのノードＮ０，０の下位のレベルに属する他のノードＮ１，１を生成する必要がある。
【０２１０】
なお、本実施形態においては、一つのノードに関連付けることができる子ノードは、二つであり、ノードＮ０，０には、ノードＮ１，０、Ｎ１，１が関連付けられている。
【０２１１】
そして、その次のメッセージｍ２にはノードＮ１，０が生成され、その次のメッセージｍ３にはノードＮ１，０の下位のレベルに属する他のノードＮ２，３が生成される。以上のようにルートとなるノードＮ０，０から子ノードを次々に生成することにより、本実施形態では、署名することのできるメッセージが無限となる。
【０２１２】
なお、使用するノードの選択は親子のレベルにおいてインタレースされ、一つのレベルでノードの選択が右から左に行われた場合には、次のレベルでは左から右に選択される葉にすることが望ましい。ノードの選択がインタレースされる理由は、所与のレベルの最後のノードから次のレベルの次のノードへの変化が、インタレースによる選択を使用する場合に最小となるためである。例えば、メッセージｍ６がノードＮ２，３を使用して署名された場合、ノードＮ３，７はノードＮ２，３の真下にあり、他方、ノードＮ３，０はノードＮ２，３の反対側にあるため、次のメッセージｍ７には、ノードＮ３，７を選択することにより、ノードＮ２，３を用いて署名の検証を行った際の公開鍵ｐへのパスをそのまま使用することができる。
【０２１３】
そして、例えば、検証装置３４０の署名検証部３４２ｅにおいて、図１７に示すメッセージｍ１２の署名を検証する場合には、メッセージｍ１２のワンタイム署名からワンタイム公開鍵を算出して、ノードＮ３，２の公開鍵ｐ３，２を算出する。そして、このようにして算出した公開鍵ｐ３，２をノードＮ３，２の親ノードＮ２，１に入力して、ノードＮ２，１の公開鍵ｐ２，１を算出する。このような処理をシステムのルートノードＮ０，０まで繰り返すことで、システムのマスタ公開鍵ｐを算出することができるようになる。このようにして算出したマスタ公開鍵ｐが検証情報記憶部３４１ａに記憶されているマスタ公開鍵と一致するか否かを比較することで、検証を行うことができる。
【０２１４】
このようなノード間の親子関係については、検証情報記憶部３４１ａに記憶しておく。
【０２１５】
以上のように構成される第三の実施形態における署名システム３００での処理を、図１８に示すシーケンス図を用いて説明する。
【０２１６】
まず、署名装置３１０において検証するメッセージｍ０の入力を受け付け、一時情報記憶部１１１ｄに記憶する（Ｓ６０）。なお、メッセージｍ０の受け付けは、例えば、キーボードなどの入力装置を介して受け付ければよい。
【０２１７】
そして、受け付けたメッセージｍ０のダイジェストＨ（ｍ０）が、ハッシュ関数処理部１１２ｅにおいて所定のハッシュ関数Ｈを用いて計算される（Ｓ６１）。
【０２１８】
また、入力されたメッセージｍ０は、送受信部３１４を介して検証装置３４０に送信される（Ｓ６２）。
【０２１９】
そして、検証装置３４０のハッシュ関数処理部１４２ｄにおいても、受信したメッセージｍ０のダイジェストＨ（ｍ０）が所定のハッシュ関数Ｈを用いて計算される（Ｓ６３）。
【０２２０】
次に、検証装置３４０の署名検証部３４２ｅは、メッセージｍ０に署名するためのノードＮ０，０を生成する（Ｓ６４）。
【０２２１】
次に、署名装置３１０の署名生成部３１２ｆは、メッセージｍ０のダイジェストＨ（ｍ０）の最初のビットから順にクイットに分割して部分ワンタイム署名を生成し（Ｓ６５）、生成の終了したものから順に検証装置３４０に送信する（Ｓ６６）。
【０２２２】
部分ワンタイム署名を受信した検証装置３４０では、ステップＳ６３で生成したダイジェストＨ（ｍ０）から受信した部分ワンタイム署名に対応するクイットを確認することで、一方向関数に入力する回数を特定して、一方向関数処理部１４２ｃに入力して検証情報記憶部２４１ａに記憶されている公開シードを用いて算出を行うことにより二進木の葉を算出する（Ｓ６７）
ステップＳ６５〜Ｓ６７の処理をダイジェストＨ（ｍ０）の全てのビットにつき繰り返し行い、二進木の全ての葉が算出されることにより、これらの葉を圧縮関数処理部１４２ｃに入力して、ワンタイム公開鍵を算出する（Ｓ６８）。
【０２２３】
そして、検証装置３４０の署名検証部３４２ｅは、ステップＳ６４で生成したノードＮ０，０にステップＳ６８で算出したワンタイム公開鍵を入力することで、ノードＮ０，０の公開鍵を算出し、検証を行う（Ｓ６９）。
【０２２４】
そして、検証装置３４０の署名検証部３４２ｅは、ステップＳ６９の検証で署名を承認することができる場合には、送受信部１４３を介して署名装置３１０に終了応答を送信する（Ｓ７０）。
【０２２５】
終了応答を受信した署名装置３１０では、新しいメッセージの入力を受け付け（Ｓ７１）、以下、ステップＳ６２〜ステップＳ７０までの処理を送信するメッセージがなくなるまで繰り返し行う。
【０２２６】
以上のように、本実施形態においては、署名するメッセージに応じて、順次、ノードを生成して署名を生成して検証することができるため、従来のＳＳＬ（Secure Socket Layer）と同様に、インターネットユーザがウェブサイトの認証を行う際に使用することができる。
【０２２７】
そして、本実施形態のように、マークル署名を利用することで、量子コンピュータを用いたとしても認証の安全性を確保することができる。
【図面の簡単な説明】
【０２２８】
【図１】第一の実施形態である署名システムの概略図。
【図２】スマートカードの概略図。
【図３】読取装置の概略図。
【図４】検証装置の概略図。
【図５】ワンタイム署名及びワンタイム公開鍵を説明するための概略図。
【図６】ワンタイム公開鍵からマスタ公開鍵の算出を行う処理を説明するための概略図。
【図７】第一の実施形態である署名システムでの処理を示すシーケンス図。
【図８】第二の実施形態である署名システムで使用されるスマートカードの概略図。
【図９】第二の実施形態である署名システムで使用される検証装置の概略図。
【図１０】ワンタイム署名及びワンタイム公開鍵を説明するための概略図。
【図１１】ワンタイム公開鍵からマスタ公開鍵の算出を行う処理を説明するための概略図。
【図１２】第二の実施形態における署名システムでの処理を示すシーケンス図。
【図１３】第三の実施形態である署名システムの概略図。
【図１４】署名装置の概略図。
【図１５】検証装置の概略図。
【図１６】ノードを説明するための概略図。
【図１７】第三の実施形態において検証を行うための処理を説明するための概略図。
【図１８】第三の実施形態における署名システムでの処理を示すシーケンス図。
【図１９】ＩＣカードの概略図。
【図２０】コンピュータの概略図。
【図２１】コンピュータの概略図。
【符号の説明】
【０２２９】
１００、３００  署名システム
１１０、２１０  スマートカード
１１１、２１１  記憶部
１１２、２１２  処理部
１１３  ＩＦ部
３１０  署名装置
３１１  記憶部
３１２  処理部
３１４  送受信部
１３０  読取装置
１４０、２４０、３４０  検証装置
１４１、２４１、３４１  記憶部
１４２、２４２、３４２  処理部
１４３  送受信部
【図１】
2008103975.tif 000005
【図２】
2008103975.tif 000006
【図３】
2008103975.tif 000007
【図４】
2008103975.tif 000008
【図５】
2008103975.tif 000009
【図６】
2008103975.tif 000010
【図７】
2008103975.tif 000011
【図８】
2008103975.tif 000012
【図９】
2008103975.tif 000013
【図１０】
2008103975.tif 000014
【図１１】
2008103975.tif 000015
【図１２】
2008103975.tif 000016
【図１３】
2008103975.tif 000017
【図１４】
2008103975.tif 000018
【図１５】
2008103975.tif 000019
【図１６】
2008103975.tif 000020
【図１７】
2008103975.tif 000021
【図１８】
2008103975.tif 000022
【図１９】
2008103975.tif 000023
【図２０】
2008103975.tif 000024
【図２１】
2008103975.tif 000025