(57)【要約】【課題】他の暗号プリミティブに基づいた、一般的なタグ使い捨て署名の構成方法を実現する。【解決手段】署名生成装置１０は、相手認証方式の公開鍵ｐｋを検証鍵ＶＫ、秘密鍵ｓｋを署名鍵ＳＫとし、ｐｋによって決まる空間ＴｐｋからコミットメントＣｍｔを選び、これをタグｔａｇとし、Ｃｍｔおよび文書ｍからハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、ｐｋ、ｓｋ、およびＣｍｔから内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、ｐｋ、ｓｋ、Ｓｔａｔｅ、およびＣｈａからレスポンスＲｅｓを計算し、これを署名σとし、ＶＫ、ｔａｇ、σ、およびｍを署名検証装置２０に送信する。署名検証装置２０は、コミットメントＣｍｔおよび文書ｍからハッシュ値Ｃｈａを計算し、公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、検証結果に応じて署名σを受理または拒否する。【選択図】図４
2015216514.tif 000002
【特許請求の範囲】
【請求項１】
署名を生成する署名生成装置と、前記署名生成装置が生成した署名を検証する署名検証装置と、を有する署名システムであって、
前記署名生成装置は、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとし、該検証鍵ＶＫを前記署名検証装置に送信し、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとし、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとし、該タグｔａｇ、該文書ｍ、および該署名σを前記署名検証装置に送信し、
前記署名検証装置は、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、前記ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該署名σをレスポンスＲｅｓとし、該検証鍵ＶＫである公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する、
署名システム。
【請求項２】
署名を生成する署名生成装置であって、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとする鍵生成部と、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとするタグ生成部と、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとする署名生成部と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを署名検証装置に送信する送信部と、
を有する署名生成装置。
【請求項３】
署名を検証する署名検証装置であって、
署名生成装置から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信する受信部と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、該タグｔａｇをコミットメントＣｍｔとし、ハッシュ関数Ｈを用いて、該コミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該検証鍵ＶＫを公開鍵ｐｋとし、該署名σをレスポンスＲｅｓとし、該公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する検証部と、
を有する署名検証装置。
【請求項４】
署名を生成する署名生成装置と、前記署名生成装置が生成した署名を検証する署名検証装置と、を有する署名システムによる署名生成／検証方法であって、
前記署名生成装置が、セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとし、該検証鍵ＶＫを前記署名検証装置に送信し、
前記署名生成装置が、乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとし、
前記署名生成装置が、前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとし、該タグｔａｇ、該文書ｍ、および該署名σを前記署名検証装置に送信し、
前記署名検証装置が、前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、前記ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該署名σをレスポンスＲｅｓとし、該検証鍵ＶＫである公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する、
署名生成／検証方法。
【請求項５】
署名を生成する署名生成装置による署名生成方法であって、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとし、該検証鍵ＶＫを署名検証装置に送信し、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとし、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとし、該タグｔａｇ、該文書ｍ、および該署名σを前記署名検証装置に送信する、
署名生成方法。
【請求項６】
署名を検証する署名検証装置による署名検証方法であって、
署名生成装置から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信し、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、該タグｔａｇをコミットメントＣｍｔとし、ハッシュ関数Ｈを用いて、該コミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該検証鍵ＶＫを公開鍵ｐｋとし、該署名σをレスポンスＲｅｓとし、該公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する、
署名検証方法。
【請求項７】
署名を生成するコンピュータを、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとする鍵生成手段と、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとするタグ生成手段と、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとする署名生成手段と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを署名検証装置に送信する送信手段と、
として機能させるためのプログラム。
【請求項８】
署名を検証するコンピュータを、
署名生成装置から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信する受信手段と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、該タグｔａｇをコミットメントＣｍｔとし、ハッシュ関数Ｈを用いて、該コミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該検証鍵ＶＫを公開鍵ｐｋとし、該署名σをレスポンスＲｅｓとし、該公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する検証手段と、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムで用いられるディジタル署名方式に関し、特に、使い捨て署名方式に関する。
【背景技術】
【０００２】
従来の使い捨て署名の構成には、大きく分けて、以下の２つが存在する。
【０００３】
１．具体的な数論などに基づいた構成
２．他の暗号プリミティブに基づいた一般的構成
本発明は、２．の一般的構成に相当するので、以下、こちらに絞って説明をする。
【０００４】
これまでに提案されてきた一般的構成には、以下の２つが存在する。
【０００５】
１．通常の使い捨て署名（非特許文献１）
２．部分使い捨て署名（非特許文献２）
しかし、通常の使い捨て署名は、署名を生成するたびに鍵全体（全ての検証鍵および署名鍵）を更新する必要があるという欠点がある。また、部分使い捨て署名は、検証鍵および署名鍵のほとんどの部分は継続的に利用可能であるが、一部の検証鍵および署名鍵を更新する必要があるという欠点がある。
【０００６】
これに対して、通常の署名の派生であるタグ使い捨て署名は、使い捨て部分がタグだけであり、検証鍵および署名鍵を継続的に利用可能である。ただし、署名を生成するときには使い捨てのタグを必ず生成する。このタグは、部分使い捨て署名における使い捨ての検証鍵に相当する。タグ使い捨て署名は、使い捨ての署名鍵が必要ないところが、部分使い捨て署名と異なるところである。
【０００７】
これまでタグ使い捨て署名の一般的構成はあまり知られていなかったが、非特許文献３，４において、タグ使い捨て署名の具体的な構成方法が提案された。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】L. Lamport. Constructing Digital Signatures from a One Way Function. Technical report, SRI Intl., 1979. CSL 98.
【非特許文献２】M. Bellare and S. Shoup. Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles. In Public Key Cryptography, volume 4450 of Lecture Notes in Computer Science, pages 201{216. Springer, 2007.
【非特許文献３】M. Abe, M. Chase, B. David, M. Kohlweiss, R. Nishimaki, and M. Ohkubo. Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions. In ASIACRYPT, volume 7658 of Lecture Notes in Computer Science, pages 4{24. Springer, 2012.
【非特許文献４】M. Abe, B. David, M. Kohlweiss, R. Nishimaki, and M. Ohkubo. Tagged One-Time Signatures: Tight Security and Optimal Tag Size. In Public Key Cryptography, volume 7778 of Lecture Notes in Computer Science, pages 312{331. Springer, 2013.
【非特許文献５】V. Lyubashevsky. Lattice-Based Identi_cation Schemes Secure Under Active Attacks. In Public Key Cryptography, volume 4939 of Lecture Notes in Computer Science, pages 162{179. Springer, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述したように、非特許文献３，４において、タグ使い捨て署名の具体的な構成方法が提案されているが、他の暗号プリミティブに基づいた、一般的なタグ使い捨て署名の構成方法は知られていない。
【００１０】
そこで、本発明の目的は、他の暗号プリミティブに基づいた、一般的なタグ使い捨て署名の構成方法を実現することができる技術を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の署名システムは、
署名を生成する署名生成装置と、前記署名生成装置が生成した署名を検証する署名検証装置と、を有する署名システムであって、
前記署名生成装置は、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとし、該検証鍵ＶＫを前記署名検証装置に送信し、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとし、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとし、該タグｔａｇ、該文書ｍ、および該署名σを前記署名検証装置に送信し、
前記署名検証装置は、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、前記ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該署名σをレスポンスＲｅｓとし、該検証鍵ＶＫである公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する。
【００１２】
本発明の署名生成装置は、
署名を生成する署名生成装置であって、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとする鍵生成部と、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとするタグ生成部と、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとする署名生成部と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを署名検証装置に送信する送信部と、
を有する。
【００１３】
本発明の署名検証装置は、
署名を検証する署名検証装置であって、
署名生成装置から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信する受信部と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、該タグｔａｇをコミットメントＣｍｔとし、ハッシュ関数Ｈを用いて、該コミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該検証鍵ＶＫを公開鍵ｐｋとし、該署名σをレスポンスＲｅｓとし、該公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する検証部と、
を有する。
【００１４】
本発明の署名生成／検証方法は、
署名を生成する署名生成装置と、前記署名生成装置が生成した署名を検証する署名検証装置と、を有する署名システムによる署名生成／検証方法であって、
前記署名生成装置が、セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとし、該検証鍵ＶＫを前記署名検証装置に送信し、
前記署名生成装置が、乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとし、
前記署名生成装置が、前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとし、該タグｔａｇ、該文書ｍ、および該署名σを前記署名検証装置に送信し、
前記署名検証装置が、前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、前記ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該署名σをレスポンスＲｅｓとし、該検証鍵ＶＫである公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する。
【００１５】
本発明の署名生成方法は、
署名を生成する署名生成装置による署名生成方法であって、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとし、該検証鍵ＶＫを署名検証装置に送信し、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとし、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとし、該タグｔａｇ、該文書ｍ、および該署名σを前記署名検証装置に送信する。
【００１６】
本発明の署名検証方法は、
署名を検証する署名検証装置による署名検証方法であって、
署名生成装置から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信し、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、該タグｔａｇをコミットメントＣｍｔとし、ハッシュ関数Ｈを用いて、該コミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該検証鍵ＶＫを公開鍵ｐｋとし、該署名σをレスポンスＲｅｓとし、該公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する。
【００１７】
本発明の第１のプログラムは、
署名を生成するコンピュータを、
セキュリティパラメータλを入力として、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成し、該公開鍵ｐｋを検証鍵ＶＫ、該秘密鍵ｓｋを署名鍵ＳＫとする鍵生成手段と、
乱数を用いて前記検証鍵ＶＫを入力とし、該検証鍵ＶＫである公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、該コミットメントＣｍｔをタグｔａｇとするタグ生成手段と、
前記検証鍵ＶＫ、前記署名鍵ＳＫ、前記タグｔａｇ、および文書ｍを入力とし、ハッシュ関数Ｈを用いて、該タグｔａｇであるコミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、アルゴリズムＳｔＲｖを用いて、該検証鍵ＶＫである公開鍵ｐｋ、該署名鍵ＳＫである秘密鍵ｓｋ、および該コミットメントＣｍｔから、内部状態Ｓｔａｔｅを計算し、アルゴリズムＩｄ．Ｐを用いて、該公開鍵ｐｋ、該秘密鍵ｓｋ、該内部状態Ｓｔａｔｅ、および該ハッシュ値Ｃｈａから、レスポンスＲｅｓを計算し、該レスポンスＲｅｓを署名σとする署名生成手段と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを署名検証装置に送信する送信手段と、
として機能させるためのプログラムである。
【００１８】
本発明の第２のプログラムは、
署名を検証するコンピュータを、
署名生成装置から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信する受信手段と、
前記検証鍵ＶＫ、前記タグｔａｇ、前記文書ｍ、および前記署名σを入力とし、該タグｔａｇをコミットメントＣｍｔとし、ハッシュ関数Ｈを用いて、該コミットメントＣｍｔおよび該文書ｍから、ハッシュ値Ｃｈａを計算し、該検証鍵ＶＫを公開鍵ｐｋとし、該署名σをレスポンスＲｅｓとし、該公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証し、該検証結果に応じて該署名σを受理または拒否する検証手段と、
として機能させるためのプログラムである。
【発明の効果】
【００１９】
本発明によれば、他の暗号プリミティブに基づいた、一般的なタグ使い捨て署名の構成方法を実現することができるという効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】本実施形態の署名システムの構成を示す図である。
【図２】図１に示した署名生成装置の構成を示すブロック図である。
【図３】図１に示した署名検証装置の構成を示すブロック図である。
【図４】図１に示した署名システムの動作シーケンスを示すシーケンス図である。
【発明を実施するための形態】
【００２１】
（１）本明細書で利用する記法
本発明は、相手認証方式を利用してタグ使い捨て署名を実現する。
【００２２】
まず、本明細書で利用する記法を説明する。
【００２３】
本明細書では、λはセキュリティパラメータを表すものとする。ある有限集合Ｓについて、
【００２４】
【数１】
2015216514.tif 000003
【００２５】
と書いたとき、集合Ｓから要素ｒを一様ランダムに選んだことを表す。ある確率的多項式時間アルゴリズムＡについて、
【００２６】
【数２】
2015216514.tif 000004
【００２７】
と書いたとき、アルゴリズムＡは、ｘを入力にとり、乱数を用いて動作し、ａを出力したことを表す。入力ｘに対して乱数ｒを使用して動作し、ａを出力することを明示するときは、ａ：＝Ａ（ｘ；ｒ）と書くことにする。記号：＝に関して、ある値ａ，ｂについて、ａ：＝ｂと書いたとき、ａにｂを代入すること、または、ａをｂで定義することを表す。
（２）典型的な相手認証方式
次に、典型的な相手認証方式を説明する。この典型的な相手認証方式は、証明者と検証者との間で対話的通信をして行うものである。
【００２８】
鍵生成：
事前に証明者は、１λを入力にとり、公開鍵および秘密鍵の対（ｐｋ，ｓｋ）を生成する。ここでの処理は、
【００２９】
【数３】
2015216514.tif 000005
【００３０】
と表される。公開されるのは、公開鍵ｐｋのみである。
【００３１】
コミット：
証明者は、乱数Ｒを選び、乱数Ｒを用いて公開鍵ｐｋを入力し、コミットメント（Ｃｍｔ）を生成して検証者に送る。コミットメント生成時には同時に内部状態の情報（Ｓｔａｔｅ）も出力する。ここでの処理は、
【００３２】
【数４】
2015216514.tif 000006
【００３３】
と表される。
【００３４】
ただし、検証者に送られるのはコミットメントのみである。典型的には、内部状態はコミットメント生成時の乱数のことを指す。
【００３５】
チャレンジ：
検証者は、証明者からコミットメントを受け取ると、ランダムなチャレンジＣｈａを送る。このチャレンジとして選ぶ値は公開鍵ｐｋによって決まる空間（Ｃｐｋ）から一様ランダムに選ぶ。ここでの処理は、
【００３６】
【数５】
2015216514.tif 000007
【００３７】
と表される。ここで、
【００３８】
【数６】
2015216514.tif 000008
【００３９】
である。
【００４０】
レスポンス：
証明者は、検証者からチャレンジＣｈａを受け取ると、保持していた内部状態Ｓｔａｔｅと秘密鍵ｓｋを利用してレスポンス（Ｒｅｓ）を生成する。ここでの処理は、Ｒｅｓ：＝Ｐ（ｐｋ，ｓｋ，Ｓｔａｔｅ，Ｃｈａ）と表される。
【００４１】
検証：
検証者は、証明者からレスポンスＲｅｓを受け取ると、公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、これまでに生成された系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証する。ここでの処理は、Ｖ（ｐｋ，Ｃｍｔ，Ｃｈａ，Ｒｅｓ）→０／１で表される。検証者は、正当性を検証できれば（計算結果が１であれば）、通信している証明者を、公開鍵ｐｋに対応するパーティとして認証する。
【００４２】
以下、相手認証方式のアルゴリズムを（Ｉｄ．Ｇｅｎ，Ｉｄ．Ｐ，Ｉｄ．Ｖ）と書くことにする。
（３）本発明が典型的な相手認証方式に追加する性質
本発明では、上述した典型的な相手認証方式に、次の新たな性質を追加したものを考える。
【００４３】
コミットメント一様性：
コミットメントを正しく生成した時、コミットメントの値が、公開鍵ｐｋによって決まる空間Ｔｐｋ上に一様に分布している。
【００４４】
状態復元：
コミットメントの値Ｃｍｔおよび秘密鍵ｓｋが与えられた時、あるアルゴリズムＳｔＲｖによって、内部状態Ｓｔａｔｅを復元できる。つまり、Ｓｔａｔｅ：＝ＳｔＲｖ（ｐｋ，ｓｋ，Ｃｍｔ）である。
【００４５】
なお、コミットメント一様性および状態復元の性質を考慮した相手認証方式は、非特許文献５で提案されている。
（４）本発明の実施形態
（４−１）本実施形態の構成
図１に、本実施形態の署名システムの構成を示す。
【００４６】
図１に示すように、本実施形態の署名システムは、署名を生成する署名生成装置１０と、署名生成装置１０が生成した署名を検証する署名検証装置２０と、から構成される。
【００４７】
図２に、署名生成装置１０の構成を示す。
【００４８】
図２に示すように、署名生成装置１０は、鍵生成部１１と、乱数生成部１２と、タグ生成部１３と、署名生成部１４と、記憶部１５と、送信部１６と、を有している。
【００４９】
鍵生成部１１は、セキュリティパラメータλを入力として、相手認証方式を使って検証鍵ＶＫおよび署名鍵ＳＫの鍵対を生成する。
【００５０】
乱数生成部１２は、乱数を生成する。
【００５１】
タグ生成部１３は、乱数生成部１２が生成した乱数を用いて検証鍵ＶＫを入力として、タグｔａｇを生成する。
【００５２】
署名生成部１４は、タグ生成部１３が生成したタグｔａｇ、鍵生成部１１が生成した検証鍵ＶＫおよび署名鍵ＳＫ、および文書ｍを入力として、署名σを生成する。
【００５３】
記憶部１５は、検証鍵ＶＫ、署名鍵ＳＫ、およびタグｔａｇを記憶する。
【００５４】
送信部１６は、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを署名検証装置２０に送信する。
【００５５】
図３に、署名検証装置２０の構成を示す。
【００５６】
図３に示すように、署名検証装置２０は、受信部２１と、記憶部２２と、検証部２３と、を有している。
【００５７】
受信部２１は、署名生成装置１０から、検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを受信する。
【００５８】
記憶部２２は、受信部２１が受信した検証鍵ＶＫ、タグｔａｇ、文書ｍ、および署名σを記憶する。
【００５９】
検証部２３は、検証鍵ＶＫ、文書ｍ、タグｔａｇ、および署名σを入力とし、署名σを検証する。
（４−２）本実施形態の動作
図４に、本実施形態の署名システムの動作シーケンスを示す。
【００６０】
図４に示すように、まず、ステップＳ１において、署名生成装置１０の鍵生成部１１は、セキュリティパラメータλを入力とし、相手認証方式を使って検証鍵ＶＫおよび署名鍵ＳＫの鍵対を生成する。具体的には、まず、鍵生成部１１は、
【００６１】
【数７】
2015216514.tif 000009
【００６２】
を実行し、相手認証方式の公開鍵ｐｋおよび秘密鍵ｓｋを生成する。そして、鍵生成部１１は、ＶＫ：＝ｐｋを検証鍵として設定し、ＳＫ：＝ｓｋを署名鍵として設定する。検証鍵ＶＫおよび署名鍵ＳＫは記憶部１５に記憶される。
【００６３】
次に、ステップＳ２において、署名生成装置１０の送信部１６は、検証鍵ＶＫのみを署名検証装置２０に送信する。検証鍵ＶＫは、署名検証装置２０の受信部２１で受信され、記憶部２２に記憶される。
【００６４】
次に、ステップＳ３において、署名生成装置１０のタグ生成部１３は、乱数生成部１２が生成した乱数を用いて、検証鍵ＶＫ（＝ｐｋ）を入力とし、タグｔａｇを生成する。具体的には、タグ生成部１３は、相手認証方式の公開鍵ｐｋによって決まるコミットメントの空間ＴｐｋからコミットメントＣｍｔを一様ランダムに選び、このコミットメントＣｍｔをタグｔａｇとして出力する。つまり、タグ生成部１３は、ｔａｇ：＝Ｃｍｔを出力する。タグｔａｇは、記憶部１５に記憶される。
【００６５】
次に、ステップＳ４において、署名生成装置１０の署名生成部１４は、タグｔａｇ（＝Ｃｍｔ）、検証鍵ＶＫ（＝ｐｋ）、署名鍵ＳＫ（＝ｓｋ）、および文書ｍを入力とし、署名σを生成する。具体的には、署名生成部１４は、文書ｍに署名するために、ハッシュ関数Ｈを用いて、ハッシュ値Ｃｈａ：＝Ｈ（Ｃｍｔ，ｍ）を計算し、内部状態Ｓｔａｔｅ：＝ＳｔＲｖ（ｐｋ，ｓｋ，Ｃｍｔ）を計算し、レスポンスＲｅｓ：＝Ｉｄ．Ｐ（ｐｋ，ｓｋ，Ｓｔａｔｅ，Ｃｈａ）を計算する。そして、署名生成部１４は、σ：＝Ｒｅｓを署名として出力する。
【００６６】
次に、ステップＳ５において、署名生成装置１０の送信部１６は、タグｔａｇ、文書ｍ、および署名σを署名検証装置２０に送信する。タグｔａｇ、文書ｍ、および署名σは、署名検証装置２０の受信部２１で受信され、記憶部２２に記憶される。
【００６７】
次に、署名検証装置２０の検証部２３は、署名σを受信した後に、ステップＳ６において、署名σを検証する。具体的には、検証部２３は、検証鍵ＶＫ（＝ｐｋ）、タグｔａｇ（＝Ｃｍｔ）、文書ｍ、および署名σ（＝Ｒｅｓ）を入力とし、ハッシュ関数Ｈを用いて、ハッシュ値Ｃｈａ：＝Ｈ（Ｃｍｔ，ｍ）を計算し、相手認証方式の公開鍵ｐｋによって決まる検証式Ｖｒｆｙを用いて、系列（Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の正当性を検証する。つまり、検証部２３は、Ｉｄ．Ｖ（ｐｋ，Ｃｍｔ，Ｃｈａ，Ｒｅｓ）→０／１を計算する。
【００６８】
その後、ステップＳ７において、署名検証装置２０の検証部２３は、Ｉｄ．Ｖ（ｐｋ，Ｃｍｔ，Ｃｈａ，Ｒｅｓ）の計算結果が１であれば、署名σを受理して１を出力するが、そうでなければ、署名σを拒否して０を出力する。
【００６９】
以上の方式では、文書ｍを相手認証方式のチャレンジとみなしている。
（４−３）本実施形態の効果
本実施形態は、他の暗号プリミティブ（コミットメント一様性および状態復元の性質を考慮した相手認証方式を利用するもの）に基づいた、一般的なタグ使い捨て署名の構成方法を実現することができる。
【００７０】
また、コミットメント一様性および状態復元の性質を考慮した相手認証方式は、非特許文献５で提案されているため、非特許文献５で提案されたような既存の方式にも、本実施形態で提案した構成方法を利用できるという利点がある。
【００７１】
また、非特許文献３，４で提案された方式は、離散対数系の問題を利用しているため、量子コンピュータが実現した場合、安全でなくなる。これに対して本実施形態は、非同期攻撃に対して安全でかつコミットメント一様性および状態復元の性質を考慮した相手認証方式を利用している。この方式は、非特許文献５で提案された相手認証方式を用いて実現した場合、格子問題に基づいた方式となる。そのため、量子コンピュータが実現したとしても、安全なタグ使い捨て署名を実現することができる。非特許文献３，４で提案された、離散対数系の問題を利用する方式では量子コンピュータに対して安全ではない。
【００７２】
なお、本発明の署名生成装置１０および署名検証装置２０は、コンピュータとプログラムとによっても実現することができ、このプログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【符号の説明】
【００７３】
１０    署名生成装置
１１    鍵生成部
１２    乱数生成部
１３    タグ生成部
１４    署名生成部
１５    記憶部
１６    送信部
２０    署名検証装置
２１    受信部
２２    記憶部
２３    検証部
【図１】
2015216514.tif 000010
【図２】
2015216514.tif 000011
【図３】
2015216514.tif 000012
【図４】
2015216514.tif 000013