(57)【要約】  鍵生成装置は、偽造不能性を満たす電子署名方式の第１の公開鍵および第１の秘密鍵と、カメレオン・コミットメント方式の第２の公開鍵および第１の秘密鍵とを生成する。署名装置は、Ｃｏｍアルゴリズムでコミットメントおよび第１の乱数を生成し、第１の秘密鍵を用いて第１の署名を生成する。さらに、署名装置は、対象メッセージに第１の署名を付加したメッセージを用いてＣａｍアルゴリズムによって第２の乱数を生成し、第１の署名と第２の乱数を組み合わせて電子署名とする。検証装置は、電子署名に含まれている第１の署名を対象メッセージに付加した署名付加メッセージを入力としてＣｏｍＶｅｒアルゴリズムによってコミットメントを生成し、そのコミットメントと第１の署名を用いて検証を行う。
2008026345.tif 000002
【特許請求の範囲】
【請求項１】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムであって、
所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより第１の公開鍵および第１の秘密鍵を生成し、前記セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより第２の公開鍵および第２の秘密鍵を生成する鍵生成装置と、
前記鍵生成装置で生成された前記第２の公開鍵と任意のメッセージを入力として、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成し、前記鍵生成装置で生成された前記第１の秘密鍵を入力として、前記偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成し、前記対象メッセージに前記第１の署名を付加した署名付加メッセージ、前記第２の公開鍵、前記第２の秘密鍵、前記コミットメント、および前記第１の乱数を入力として、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、前記第１の署名と前記第２の乱数を含めて前記対象メッセージに対する前記電子署名を生成する署名装置と、
前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した署名付加メッセージ、前記電子署名に含まれている前記第２の乱数、および前記第２の公開鍵を入力として、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成し、生成された該コミットメント、前記第１の署名、および前記第１の公開鍵を入力として、前記偽造不能性を満たす電子署名方式の検証アルゴリズムによって該第１の署名の正当性を検証し、その検証結果を前記電子署名の検証結果とする検証装置と、を有する電子署名システム。
【請求項２】
前記鍵生成装置は、前記カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにおいて、セキュリパラメータをκとして、群Ｇ＿κから元ｇを選択し、群Ｇ＿κと位数が等しい巡回群Ｚ＿κから自然数ｎ個の元ｘ＿１，・・・，ｘ＿ｎをランダムに選択し、ｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝を算出し、前記第２の公開鍵にｇ，ｈ＿１，・・・，ｈ＿ｎを含め、前記第２の秘密鍵にｘ＿１，・・・，ｘ＿ｎを含め、
前記署名装置は、前記Ｃｏｍアルゴリズムにおいて、巡回群Ｚ＿κの元ｔ＿１，・・・，ｔ＿ｎを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ＿０）｝ｈ＿１＾｛ｔ＿１｝・・・ｈ＿ｎ＾｛ｔ＿ｎ｝を算出し、前記Ｃａｍアルゴリズムにおいて、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、Ｈ（ｍ＿０）＋ｔ＿１ｘ＿１＋・・・＋ｔ＿ｎｘ＿ｎ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含め、
前記検証装置は、前記ＣｏｍＶｅｒアルゴリズムにおいて、前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝を算出する、請求項１に記載の電子署名システム。
【請求項３】
前記鍵生成装置は、前記カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにおいて、セキュリパラメータをκとして、群Ｇ＿κから元ｇを選択し、群Ｇ＿κと位数が等しい巡回群Ｚ＿κから自然数ｎ個の元ｘ＿１，・・・，ｘ＿ｎをランダムに選択し、ｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝を算出し、前記第２の公開鍵にｇ，ｈ＿１，・・・，ｈ＿ｎを含め、前記第２の秘密鍵にｘ＿１，・・・，ｘ＿ｎを含め、
前記署名装置は、前記Ｃｏｍアルゴリズムにおいて、巡回群Ｚ＿κの元ｔを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾ｔを算出し、前記Ｃａｍアルゴリズムにおいて、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、ｔ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含め、
前記検証装置は、前記ＣｏｍＶｅｒアルゴリズムにおいて、前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝を算出する、請求項１に記載の電子署名システム。
【請求項４】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムの公開鍵と秘密鍵を生成する鍵生成装置であって、
所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより、前記公開鍵に含める第１の公開鍵と前記秘密鍵に含める第１の秘密鍵とを生成する生成部、
前記セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより、前記公開鍵に含める第２の公開鍵と前記秘密鍵に含める第２の秘密鍵とを生成するＧｅｎＣａｍ部と、を有する鍵生成装置。
【請求項５】
前記ＧｅｎＣａｍ部は、前記カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにおいて、セキュリパラメータをκとして、群Ｇ＿κから元ｇを選択し、群Ｇ＿κと位数が等しい巡回群Ｚ＿κから自然数ｎ個の元ｘ＿１，・・・，ｘ＿ｎをランダムに選択し、ｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝を算出し、前記第２の公開鍵にｇ，ｈ＿１，・・・，ｈ＿ｎを含め、前記第２の秘密鍵にｘ＿１，・・・，ｘ＿ｎを含める、請求項４に記載の鍵生成装置。
【請求項６】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムにおいて、請求項４に記載の鍵生成装置で生成された公開鍵および秘密鍵を用いて前記電子署名を生成する署名装置であって、
前記鍵生成装置で生成された前記公開鍵に含まれている前記第２の公開鍵と任意のメッセージを入力として、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成するＣｏｍ部と、
前記鍵生成装置で生成された前記秘密鍵に含まれている前記第１の秘密鍵を入力として、前記偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成する署名部と、
前記対象メッセージに前記第１の署名を付加した署名付加メッセージ、前記公開鍵に含まれている前記第２の公開鍵、前記秘密鍵に含まれている前記第２の秘密鍵、前記コミットメント、および前記第１の乱数を入力として、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、前記第１の署名と前記第２の乱数を含めて前記対象メッセージに対する前記電子署名を生成するＣａｍ部と、を有する署名装置。
【請求項７】
前記公開鍵および前記秘密鍵は、請求項５に記載の鍵生成装置によって生成され、
前記Ｃｏｍ部は、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成するとき、巡回群Ｚ＿κの元ｔ＿１，・・・，ｔ＿ｎを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ＿０）｝ｈ＿１＾｛ｔ＿１｝・・・ｈ＿ｎ＾｛ｔ＿ｎ｝を算出し、
前記Ｃａｍ部は、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成するとき、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、Ｈ（ｍ＿０）＋ｔ＿１ｘ＿１＋・・・＋ｔ＿ｎｘ＿ｎ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含める、
請求項６に記載の署名装置。
【請求項８】
前記公開鍵および前記秘密鍵は、請求項５に記載の鍵生成装置によって生成され、
前記Ｃｏｍ部は、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成するとき、巡回群Ｚ＿κの元ｔを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾ｔを算出し、
前記Ｃａｍ部は、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成するとき、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、ｔ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含める、
請求項６に記載の署名装置。
【請求項９】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムにおいて、請求項６に記載の署名装置で生成された電子署名を検証する検証装置であって、
前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した署名付加メッセージ、前記電子署名に含まれている前記第２の乱数、および前記第２の公開鍵を入力として、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成するＣｏｍＶｅｒ部と、
前記ＣｏｍＶｅｒ部で生成された該コミットメントと、前記第１の署名と、前記第１の公開鍵とを入力として、前記偽造不能性を満たす電子署名方式の検証アルゴリズムによって、該第１の署名の正当性を検証し、その検証結果を前記電子署名の検証結果とする検証部と、を有する検証装置。
【請求項１０】
前記電子署名は、請求項７または８に記載の署名装置によって生成され、
前記ＣｏｍＶｅｒ部は、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成するとき、前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝を算出する、請求項９に記載の検証装置。
【請求項１１】
鍵生成装置の生成した鍵を用いて署名装置が対象メッセージに対して生成した電子署名を検証装置が検証する電子署名システムにおける電子署名検証方法であって、
前記鍵生成装置において、
所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより第１の公開鍵および第１の秘密鍵を生成し、
前記セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより第２の公開鍵および第２の秘密鍵を生成し、
前記署名装置において、
前記鍵生成装置で生成された前記第２の公開鍵と任意のメッセージを入力として、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成し、
前記鍵生成装置で生成された前記第１の秘密鍵を入力として、前記偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成し、
前記対象メッセージに前記第１の署名を付加した署名付加メッセージ、前記第２の公開鍵、前記第２の秘密鍵、前記コミットメント、および前記第１の乱数を入力として、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、
前記第１の署名と前記第２の乱数を含めて前記対象メッセージに対する前記電子署名を生成し、
前記検証装置において、
前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した署名付加メッセージ、前記電子署名に含まれている前記第２の乱数、および前記第２の公開鍵を入力として、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成し、
生成された該コミットメント、前記第１の署名、および前記第１の公開鍵を入力として、前記偽造不能性を満たす電子署名方式の検証アルゴリズムによって該第１の署名の正当性を検証し、その検証結果を前記電子署名の検証結果とする、電子署名検証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的なメッセージに付加する電子署名の生成および検証に関する。
【背景技術】
【０００２】
電子署名方式は、紙媒体に対する印鑑の押印に相当する作業を電子的に行う技術であり、すなわち電子媒体に記憶されるような電子的なメッセージに電子的な署名（以下「電子署名」あるいは単に「署名」という）を添付する技術である。インターネットの普及に伴って電子署名方式の重要性が高まっている。【０００３】
電子商取引に代表されるような計算機上での契約や認証ではメッセージの内容が改ざんされていないことが重要である。電子署名方式によれば、電子署名を添付した後のメッセージの改ざんの有無を検証できる。【０００４】
電子署名方式には２つのエンティティが存在する。一方が署名者で、他方が検証者である。署名者はメッセージに対する電子署名を作成し、その電子署名をメッセージとともに出力する。それに対し検証者は、署名者により出力されたメッセージと電子署名を受け、電子署名の正当性を検証する。【０００５】
また、電子署名方式には２つのレベルの安全性概念がある。一方が偽造不能性であり、他方が強偽造不能性である。【０００６】
偽造不能性とは、正当な署名者が過去に署名したことの無いメッセージに対する電子署名を他者が偽造できないことをいう。したがって、偽造不能性では、正当な署名者が過去に署名したことのあるメッセージに対して、過去の電子署名と異なる電子署名を他者が偽造することはできてしまう可能性がある。これに対し、強偽造不能性は、それすらも不可能なことをいう。既存の電子署名方式の多くは偽造不能性を満たすことが知られている。しかし、それら既存の電子署名方式が強偽造不能性を満たすかどうかは不明である。【０００７】
このような状況に対して、近年、偽造不能性を満たす電子署名方式を強偽造不能性を満たす電子署名方式に変換する方法が提案された（“Ｓｔｒｏｎｇｌｙ  Ｕｎｆｏｒｇｅａｂｌｅ  Ｓｉｇｎａｔｕｒｅｓ  Ｂａｓｅｄ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ．”  Ｄａｎ  Ｂｏｎｅｈ，  Ｅｍｉｌｙ  Ｓｈｅｎ，  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ．  Ｉｎ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ−ＰＫＣ  ２００６，ＬＮＣＳ  ３９５８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００６．参照）。その方法によれば強偽造不能性を満たす電子署名方式を実現することができる。
【発明の開示】
【０００８】
しかし、上記文献に提案された方法は、元の電子署名方式がパーティションドと呼ばれる特殊な性質を持った方式である場合に限定される。そして、パーティションドな性質を有することが知られている電子署名方式は現在のところ１つしかない。しかも、その電子署名方式は効率が悪く、それを変換した強偽造不能性を満たす電子署名方式も効率が悪いため実用的とはいえなかった。
【０００９】
本発明の目的は、強偽造不能性を満たす電子署名方式を実現する電子署名システムを提供することである。
【００１０】
上記目的を達成するために、本発明の電子署名システムは、
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムであって、鍵生成装置、署名装置、および検証装置を有している。
【００１１】
鍵生成装置は、所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより第１の公開鍵および第１の秘密鍵を生成する。また、鍵生成装置は、セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより第２の公開鍵および第２の秘密鍵を生成する。
【００１２】
署名装置は、鍵生成装置で生成された第２の公開鍵と任意のメッセージを入力として、カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成する。また、署名装置は、鍵生成装置で生成された第１の秘密鍵を入力として、偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成する。さらに、署名装置は、対象メッセージに第１の署名を付加した署名付加メッセージ、第２の公開鍵、第２の秘密鍵、コミットメント、および第１の乱数を入力として、カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、第１の署名と第２の乱数を含めて対象メッセージに対する電子署名を生成する。
【００１３】
検証装置は、電子署名に含まれている第１の署名を対象メッセージに付加した署名付加メッセージ、電子署名に含まれている第２の乱数、および第２の公開鍵を入力として、カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成し、その生成されたコミットメント、第１の署名、および第１の公開鍵を入力として、偽造不能性を満たす電子署名方式の検証アルゴリズムによって第１の署名の正当性を検証し、その検証結果を電子署名の検証結果とする。
【００１４】
本発明によれば、偽造不能性を満たす任意の電子署名方式とカメレオン・コミットメント方式を組み合わせることにより強偽造不能性を満たす電子署名方式を実現することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態による電子署名システムの構成を示すブロック図である。
【図２】本実施形態による電子署名方式の処理の流れの概略を示すフローチャートである。
【図３】第１の実施例による各装置の構成を示すブロック図である。
【図４】第１の実施形態の鍵生成装置１１による鍵生成アルゴリズムＧｅｎの動作を示すフローチャートである。
【図５】第１の実施形態の署名装置１２による署名アルゴリズムＳｉｇの動作を示すフローチャートである。
【図６】第１の実施形態の検証装置１３による検証アルゴリズムＶｅｒの動作を示すフローチャートである。
【図７】第２の実施例の鍵生成装置１１によるＧｅｎＣａｍ＿ｎアルゴリズムの動作を示すフローチャートである。
【図８】第２の実施例の署名装置１２によるＣｏｍ＿ｎアルゴリズムの動作を示すフローチャートである。
【図９】第２の実施例の署名装置１２によるＣａｍ＿ｎアルゴリズムの動作を示すフローチャートである。
【図１０】第２の実施例の検証装置１３によるＣｏｍＶｅｒ＿ｎアルゴリズムの動作を示すフローチャートである。
【図１１】第３の実施例の署名装置１２によるＣｏｍ’＿ｎアルゴリズムの動作を示すフローチャートである。
【図１２】第３の実施例の署名装置１２によるＣａｍ’＿ｎアルゴリズムの動作を示すフローチャートである。
【発明を実施するための最良の形態】
【００１６】
本発明を実施するための形態について図面を参照して詳細に説明する。【００１７】
図１は、本実施形態による電子署名システムの構成を示すブロック図である。図１を参照すると、本実施形態の電子署名システムは、鍵生成装置１１、署名装置１２、および検証装置１３を有している。【００１８】
鍵生成装置１１は、鍵生成アルゴリズムが実装されており、そのアルゴリズムに基づいて鍵を生成する。鍵を生成する際、鍵生成装置１１にはセキュリティ・パラメータκが与えられる。鍵生成装置１１は、そのセキュリティ・パラメータκを入力として公開鍵ｐｋと秘密鍵ｓｋを出力する。【００１９】
署名装置１２は、署名アルゴリズムが実装されており、そのアルゴリズムに基づいて電子署名を生成する。署名装置１２には、鍵生成装置１１の生成した公開鍵ｐｋおよび秘密鍵ｓｋと、電子署名を添付すべきメッセージＭとが与えられる。署名装置１２は、それら公開鍵ｐｋ、秘密鍵ｓｋ、およびメッセージＭを入力として電子署名σを出力する。【００２０】
検証装置１３は、検証アルゴリズムが実装されており、そのアルゴリズムに基づいて電子署名を検証する。検証装置１３には、鍵生成装置１１の生成した公開鍵ｐｋと、署名装置１２の生成した電子署名σと、その電子署名σが添付されたメッセージＭとが与えられる。検証装置１３は、それら公開鍵ｐｋ、電子署名σ、およびメッセージＭを入力として電子署名σが正当なものであるか否か検証する。【００２１】
鍵生成装置１１、署名装置１２、および検証装置１３は全てハードウェア的には不図示の演算部、記憶部、および通信部を有する構成である。一般的に、演算部にはＣＰＵが用いられ、記憶部にはメモリやハードディスクが用いられる。また、一般的に、通信部はインターネット上の通信を可能にする構成である。ただし、演算部、記憶部、通信部はこれら一般的な構成に限定されるものではない。【００２２】
また、署名装置１２は鍵生成装置１１の出力を入力として動作するため、実際の運用では署名装置１２が鍵生成装置１１を兼ねる構成を採用することが多い。ただし、必ずしも署名装置１２が鍵生成装置１１を兼ねる必要はない。さらに署名装置１２が検証装置１３も兼ねる構成を採用することも多い。ただし、やはり署名装置１２が検証装置１３を兼ねる必要はない。【００２３】
本実施形態の電子署名方式の概要について説明する。【００２４】
ここで「署名者」という人物（または団体）が鍵生成装置１１および署名装置１２を所有しているとする。また、「検証者」という人物（または団体）が検証装置１３を所有しているとする。１台の署名装置１２を複数人で兼用していてもよいが、話を簡単にするため以下では１台の署名装置１２には１人の使用者しかいないと仮定する。
同様に、１台の鍵生成装置１１にも１人の使用者しかおらず、１台の検証装置１３にも１人の使用者しかいないと仮定する。ただし、複数人で装置を兼用する場合も同様に運用することができる。【００２５】
図２は、本実施形態による電子署名方式の処理の流れの概略を示すフローチャートである。図２を参照すると、まず署名者による「事前準備」の処理が行われる（ステップ１０１）。続いて、同じく署名者による実際の「署名」の処理が行われる（ステップ１０２）。最後に検証者による「検証」の処理が行われる（ステップ１０３）。【００２６】
署名者の行動として上述した「事前準備」と「署名」の２つがある。事前準備は一度だけ行えばよい。事前準備を一旦済ませれば、「署名」を行うことでいくつものメッセージに対して何度でも電子署名を作成することができる。【００２７】
署名者による「事前準備」について説明する。【００２８】
署名者は、まずセキュリティ・パラメータと呼ばれる値κを決定する。セキュリティ・パラメータκは、電子署名を偽造するのがどの程度難しいのかを示す尺度である。セキュリティ・パラメータκが大きければ大きいほど電子署名を偽造するのが困難になる。続いて、署名者は、セキュリティ・パラメータκを入力して鍵生成装置１１上で鍵生成アルゴリズムを動作させる。【００２９】
鍵生成装置１１は、セキュリティ・パラメータκを入力として鍵生成アルゴリズムを実行することで公開鍵と呼ばれるデータｐｋと秘密鍵と呼ばれるデータｓｋとを生成する。そして、鍵生成装置１１は生成した公開鍵ｐｋと秘密鍵ｓｋを署名装置１２に送る。署名装置１２は鍵生成装置１１から受けた公開鍵ｐｋと秘密鍵ｓｋを記憶部に保存する。【００３０】
さらに、鍵生成装置１１は公開鍵ｐｋを何らかの方法で他の装置に公開する。ここでは公開鍵ｐｋを公開する方法は特に限定されない。例えばＰＫＩ（Ｐｕｂｌｉｃ  Ｋｅｙ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）を用いて公開鍵ｐｋを公開してもよく、公開鍵ｐｋを公開掲示板に書き込むことにしてもよい。【００３１】
一方、秘密鍵ｓｋは他者に知られれば容易に電子署名が偽造されてしまう。そこで、署名装置１２はこれを秘密裏に保存する。ここでは秘密鍵ｓｋを秘密裏に保存する方法は特に限定されない。例えば署名装置１２にパスワードを設定することにより、パスワードを知らない者が署名装置１２を利用できないようにしてもよい。他の方法として、署名装置１２を安全な場所に保管することにしてもよく、秘密鍵ｓｋを耐タンパー装置に保管することにしてもよい。【００３２】
以上で署名者による「事前準備」が終了する。【００３３】
次に署名者による「署名」について説明する。【００３４】
署名者は署名装置１２に署名アルゴリズムを実行させる。署名装置１２は、記憶部から公開鍵ｐｋと秘密鍵ｓｋと署名対象のメッセージＭとを読み込み、これらのデータを使って電子署名σを作成し、記憶部に書き込む。更に、署名装置１２は、署名者の要求に応じ、通信部を使ってメッセージＭと電子署名σを他の装置に送信する。【００３５】
以上で署名者による「署名」が終了する。【００３６】
検証者はメッセージＭに対して生成された電子署名σを検証する。【００３７】
その際、検証者は、まず検証装置１３によって署名者の公開鍵ｐｋと、メッセージＭと、メッセージＭに対する電子署名σとを入手する。検証装置１３は、公開鍵ｐｋ、メッセージＭ、および電子署名σを通信部で入手し、記憶部に書き込む。ここでは公開鍵ｐｋを作成した署名者のＩＤがＳであるとする。検証者の意図するところは、電子署名σが署名者Ｓによって正当な方法で作成された電子署名であるか否かを検証することである。【００３８】
そこで、検証者は検証装置１３上で検証アルゴリズムを動作させる。検証装置１３は記憶部から公開鍵ｐｋ、メッセージＭ、および電子署名σを読み込み、電子署名σを検証する。検証装置１３からは検証結果としてａｃｃｅｐｔとｒｅｊｅｃｔの２種類のデータのうちいずれか一方が出力される。【００３９】
ａｃｃｅｐｔは「電子署名σは署名者Ｓが正当な方法で作成したメッセージＭに対する電子署名である」という意味である。ｒｅｊｅｃｔは「電子署名σは署名者Ｓが正当な方法で作成したメッセージＭに対する電子署名ではない」という意味である。【００４０】
本実施形態の鍵生成アルゴリズム、署名アルゴリズム、および検証アルゴリズムは、偽造不能性を満たす任意の電子署名方式とカメレオン・コミットメント方式とを融合させることで強偽造不能性を有する電子署名方式を実現するものである。【００４１】
カメレオン・コミットメント方式について説明する。【００４２】
カメレオン・コミットメント方式では一般にＧｅｎＣａｍ、Ｃｏｍ、Ｃａｍ、ＣｏｍＶｅｒという４つの関数（アルゴリズム）が用いられる。【００４３】
ＧｅｎＣａｍアルゴリズムは、セキュリティ・パラメータκを入力としてカメレオン・コミットメント方式の公開鍵ｐｋｃａｍと秘密鍵ｓｋｃａｍを生成する関数である。【００４４】
Ｃｏｍアルゴリズムは、公開鍵ｐｋｃａｍとメッセージｍ＿０を入力としてコミットメントと呼ばれるデータＣと乱数ｔとを生成する関数である。【００４５】
Ｃａｍアルゴリズムは、公開鍵ｐｋｃａｍと秘密鍵ｓｋｃａｍとメッセージｍとコミットメントＣと乱数ｔを入力として乱数ｒを生成する関数である。【００４６】
ＣｏｍＶｅｒアルゴリズムは、公開鍵ｐｋｃａｍとメッセージｍと乱数ｒとを入力としてコミットメントＣを生成する関数である。【００４７】
以下、既存のカメレオン・コミットメント方式の各関数のアルゴリズムについて説明する。【００４８】
ここでは｛Ｇ＿κ｝を群の属とする。Ｇ＿κとしてどのような群を選んでもかまわないが、公開鍵暗号方式を用いているので安全性の観点からＧ＿κ上の離散対数問題が困難であることが望ましい。ここでＧ＿κの位数をｑ＿κとし、位数ｑ＿κの巡回群をＺ＿κとする。【００４９】
また、以下の説明では、Ｇ＿κの元ｇをｘ乗する操作をｇ＾ｘもしくはｇ＾｛ｘ｝と書くことにする。また、Ｈは、値域がビット列であり、しかもそのビット列がｌｏｇ
ｑビット以下のハッシュ関数を示すものとする。【００５０】
まず、ＧｅｎＣａｍアルゴリズムについて説明する。ＧｅｎＣａｍアルゴリズムにはセキュリティ・パラメータκが入力される。ＧｅｎＣａｍアルゴリズムは、まずセキュリティ・パラメータκで定まる群Ｇ＿κから元ｇをランダムに選択し、巡回群Ｚ＿κから元ｘをランダムに選択する。そして、選択したｇ、ｘの値を用いてｈ＝ｇ＾ｘを算出し、公開鍵ｐｋｃａｍ＝（κ，ｇ，ｈ）と秘密鍵ｓｋｃａｍ＝ｘを出力する。【００５１】
次に、Ｃｏｍアルゴリズムについて説明する。Ｃｏｍアルゴリズムには、ＧｅｎＣａｍアルゴリズムから出力された公開鍵ｐｋｃａｍ＝（κ，ｇ，ｈ）と、任意のメッセージｍ＿０とが入力される。Ｃｏｍアルゴリズムは、巡回群Ｚ＿κから元ｔをランダムに選択し、そのｔの値と、公開鍵ｐｋｃａｍに含まれているｇ、ｈの値とを用いてコミットメントＣ＝ｇ＾｛Ｈ（ｍ＿０）｝ｈ＾ｔを算出する。Ｃｏｍアルゴリズムの出力は乱数ｔとコミットメントＣである。【００５２】
次に、Ｃａｍアルゴリズムについて説明する。Ｃａｍアルゴリズムには、ＧｅｎＣａｍアルゴリズムで生成された公開鍵ｐｋｃａｍおよび秘密鍵ｓｋｃａｍと、Ｃｏｍアルゴリズムで生成された乱数ｔおよびコミットメントＣと、メッセージｍとが入力される。関数Ｃａｍは、それら入力した値を用いて、Ｚ＿κの元の中から、Ｈ（ｍ＿０）＋ｔｘ＝Ｈ（ｍ）＋ｒｘｍｏｄｑ＿κを満たす元ｒを選択する。Ｃａｍアルゴリズムの出力は乱数ｒである。【００５３】
最後に、ＣｏｍＶｅｒアルゴリズムについて説明する。ＣｏｍＶｅｒアルゴリズムには、公開鍵ｐｋｃａｍ＝（κ，ｇ，ｈ）、メッセージｍ、および乱数ｒが入力される。ＣｏｍＶｅｒアルゴリズムは、それら入力された値を用いてコミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＾ｒを算出する。ＣｏｍＶｅｒアルゴリズムの出力はコミットメントＣである。【００５４】
以下、本実施形態の電子署名システムの実施例について説明する。【００５５】
（第１の実施例）
ここでは、偽造不能性を満たす任意の電子署名方式のシステムをΣ’とする。システムΣ’の鍵生成アルゴリズムをＧｅｎ’とし、署名アルゴリズムをＳｉｇ’とし、検証アルゴリズムをＶｅｒ’とする。【００５６】
また、カメレオン・コミットメント方式のシステムをΔとする。システムΔの各関数のアルゴリズムをＧｅｎＣａｍ、Ｃｏｍ、Ｃａｍ、ＣｏｍＶｅｒとする。【００５７】
また、第１の実施例によって実現される強偽造不能性を満たす電子署名方式のシステムをΣとする。システムΣの鍵生成アルゴリズムをＧｅｎとし、署名アルゴリズムをＳｉｇとし、検証アルゴリズムをＶｅｒとする。【００５８】
図３は、第１の実施例による各装置の構成を示すブロック図である。図３を参照すると、鍵生成装置１１はＧｅｎ’部２１およびＧｅｎＣａｍ部２２を有している。署名装置１２はＣｏｍ部３１、Ｓｉｇ’部３２、およびＣａｍ部３３を有している。また、検証装置１３はＣｏｍＶｅｒ部４１およびＶｅｒ’部４２を有している。【００５９】
鍵生成装置１１においてＧｅｎ’部２１は、セキュリティ・パラメータκを入力として、偽造不能性を満たす電子署名方式のシステムΣ’の鍵生成アルゴリズムＧｅｎ’を実行し、公開鍵ｐｋ’および秘密鍵ｓｋ’を生成する。ＧｅｎＣａｍ部２２は、セキュリティ・パラメータκを入力として、関数ＧｅｎＣａｍのアルゴリズムを実行し、公開鍵ｐｋｃａｍおよび秘密鍵ｓｋｃａｍを生成する。【００６０】
Ｇｅｎ’部２１の生成した公開鍵ｐｋ’とＧｅｎＣａｍ部２２の生成した公開鍵ｐｋｃａｍとの組が、鍵生成装置１１による鍵生成アルゴリズムＧｅｎの公開鍵ｐｋとして出力される。また、Ｇｅｎ’部２１の生成した秘密鍵ｓｋ’とＧｅｎＣａｍ部２２の生成した秘密鍵ｓｋｃａｍとの組が、鍵生成装置１１による鍵生成アルゴリズムＧｅｎの秘密鍵ｓｋとして出力される。【００６１】
署名装置１２においてＣｏｍ部３１は、公開鍵ｐｋに含まれている公開鍵ｐｋｃａｍと任意のメッセージｍ＿０とを入力として、関数Ｃｏｍのアルゴリズムを実行し、コミットメントＣおよび乱数ｔを生成する。Ｓｉｇ’部３２は、Ｃｏｍ部３１で生成されたコミットメントＣと、秘密鍵ｓｋに含まれている秘密鍵ｓｋ’とを入力として、偽造不能性を満たす電子署名方式のシステムΣ’の署名アルゴリズムＳｉｇ’を実行し、電子署名σ’を生成する。Ｃａｍ部３３は、電子署名を生成する対象であるメッセージＭと電子署名σ’とからなるメッセージｍと、Ｃｏｍ部３１で生成されたコミットメントＣおよび乱数ｔと、公開鍵ｐｋｃａｍおよび秘密鍵ｓｋｃａｍとを入力として、関数Ｃａｍのアルゴリズムを実行し、乱数ｒを生成する。【００６２】
Ｓｉｇ’部３２の生成した電子署名σ’とＣａｍ部３３の生成した乱数ｒとを含むビット例が、署名装置１２による署名アルゴリズムＳｉｇの電子署名σとして出力される。【００６３】
検証装置１３においてＣｏｍＶｅｒ部４１は、電子署名σに含まれている電子署名σ’および乱数ｒと、メッセージＭと電子署名σ’で作ったメッセージｍと、公開鍵ｐｋに含まれている公開鍵ｐｋｃａｍとを入力として、ＣｏｍＶｅｒアルゴリズムを実行し、コミットメントＣを生成する。Ｖｅｒ’部４２は、ＣｏｍＶｅｒ部４１で生成されたコミットメントＣと、公開鍵ｐｋに含まれている公開鍵ｐｋ’と、電子署名σに含まれている電子署名σ’とを入力として、偽造不能性を満たす電子署名方式のシステムΣ’の検証アルゴリズムＶｅｒ’を実行し、ａｃｃｅｐｔまたはｒｅｊｅｃｔの検証結果を出力する。【００６４】
第１の実施形態による電子署名システムの動作について説明する。【００６５】
図４は、第１の実施形態の鍵生成装置１１による鍵生成アルゴリズムＧｅｎの動作を示すフローチャートである。図４を参照すると、まず鍵生成装置１１は入力κを記憶部から読み込む（ステップ２０１）。続いて、鍵生成装置１１はＧｅｎ’（κ）を実行し、Ｇｅｎ’（κ）の出力（ｐｋ，ｓｋ）を算出する（ステップ２０２）。続いて、鍵生成装置１１はＧｅｎＣａｍ（κ）を実行し、ＧｅｎＣａｍ（κ）の出力（ｐｋｃａｍ，ｓｋｃａｍ）を算出する。（ステップ２０３）。続いて、鍵生成装置１１は公開鍵ｐｋ＝（ｐｋ’，ｐｋｃａｍ）と、秘密鍵ｓｋ＝（ｓｋ’，ｓｋｃａｍ）を生成する（ステップ２０４）。最後に、鍵生成装置１１は公開鍵ｐｋと秘密鍵ｓｋを記憶部に書き込む（ステップ２０５）。【００６６】
図５は、第１の実施形態の署名装置１２による署名アルゴリズムＳｉｇの動作を示すフローチャートである。ビット列Ｍとビット列σをつなげてできるビット列をＭ｜｜σと示す。図５を参照すると、署名装置１２は、公開鍵ｐｋ＝（ｐｋ’，ｐｋｃａｍ）、秘密鍵ｓｋ＝（ｓｋ’，ｓｋｃａｍ）、およびメッセージＭを記憶部から読み込む（ステップ３０１）。続いて、署名装置１２はＣｏｍ（ｐｋｃａｍ，ｍ＿０）を実行し、Ｃｏｍ（ｐｋｃａｍ，ｍ＿０）の出力（Ｃ，ｔ）を算出する（ステップ３０２）。続いて、署名装置１２はＳｉｇ’（ｓｋ’，Ｃ）を実行し、Ｓｉｇ’（ｓｋ’，Ｃ）の出力σ’を算出する（ステップ３０３）。続いて、署名装置１２はｍ＝Ｍ｜｜σ’とする（ステップ３０４）。続いて、署名装置１２はＣａｍ（ｐｋｃａｍ，ｓｋｃａｍ，ｍ，Ｃ，ｔ）を実行し、Ｃａｍ（ｐｋｃａｍ，ｓｋｃａｍ，ｍ，Ｃ，ｔ）の出力ｒを算出する（ステップ３０５）。続いて、署名装置１２はσ＝（σ’，ｒ）とする（ステップ３０６）。続いて、署名装置１２は電子署名σを記憶部に書き込む（ステップ３０７）。【００６７】
図６は、第１の実施形態の検証装置１３による検証アルゴリズムＶｅｒの動作を示すフローチャートである。図６を参照すると、検証装置１３は、まず公開鍵ｐｋ＝（ｐｋ’，ｐｋｃａｍ）、メッセージＭ、および電子署名σ＝（σ’，ｒ）を記憶部から読み込む（ステップ４０１）。続いて、検証装置１３はｍ＝Ｍ｜｜σ’とする（ステップ４０２）。続いて、検証装置１３はＣ＝ＣｏｍＶｅｒ（ｐｋｃａｍ，ｍ，ｒ）を計算する（ステップ４０３）。最後に、検証装置１３はＶｅｒ’（ｐｋ，Ｃ，σ’）＝ａｃｃｅｐｔならａｃｃｅｐｔを記憶部に書き込み、そうでなければｒｅｊｅｃｔを記憶部に書き込む（ステップ４０４）。【００６８】
以上説明したように、本実施例によれば、署名装置１２は、カメレオン・コミットメント方式のシステムΔの公開鍵ｐｋｃａｍを用いてシステムΔのＣｏｍアルゴリズムでコミットメントＣおよび乱数ｔを生成する。また、署名装置１２は、偽造不能性を満たすシステムΣ’の秘密鍵ｓｋ’を用いてシステムΣ’の署名アルゴリズムＳｉｇ’で電子署名σ’を生成する。さらに、署名装置１２は、メッセージＭに電子署名σ’を付加したメッセージｍと、コミットメントＣと、乱数ｔと、公開鍵ｐｋｃａｍと、秘密鍵ｓｋｃａｍとを用いてシステムΔのＣａｍアルゴリズムで乱数ｒを生成する。さらに、署名装置１２は、その電子署名σ’と乱数ｒを組み合わせて電子署名σとする。したがって、偽造不能性を満たす任意の電子署名方式とカメレオン・コミットメント方式を組み合わせることにより強偽造不能性を満たす電子署名方式を実現することができる。【００６９】
（第２の実施例）
第１の実施例では任意のカメレオン・コミットメント方式から強偽造不能性の電子署名を得る例を示したが、第２の実施例では第１の実施例の特殊な例を示す。【００７０】
第１の実施例における任意のカメレオン・コミットメント方式として既存の方式を用いてもよい。しかし、安全性の観点から言えば、以下に説明する第２の実施例のカメレオン・コミットメント方式（ＧｅｎＣａｍ＿ｎ，Ｃｏｍ＿ｎ，Ｃａｍ＿ｎ，ＣｏｍＶｅｒ＿ｎ）を用いた方がより安全性が高まる。【００７１】
第２の実施例のカメレオン・コミットメント方式は、ＧｅｎＣａｍ＿ｎ，Ｃｏｍ＿ｎ，Ｃａｍ＿ｎ，ＣｏｍＶｅｒ＿ｎの各アルゴリズムで実現されるものとする。ここでｎは整数であるとする。【００７２】
第２の実施例による電子署名システムは図３に示した第１の実施例と同様の構成を有している。第２の実施例は、鍵生成装置１１、署名装置１２、および検証装置１３で実行されるカメレオン・コミットメント方式のアルゴリズムだけが第１の実施例と異なる。【００７３】
以下、カメレオン・コミットメント方式のＧｅｎＣａｍ＿ｎ，Ｃｏｍ＿ｎ，Ｃａｍ＿ｎ，ＣｏｍＶｅｒ＿ｎのアルゴリズムについて説明をする。【００７４】
図７は、第２の実施例の鍵生成装置１１によるＧｅｎＣａｍ＿ｎアルゴリズムの動作を示すフローチャートである。図７を参照すると、鍵生成装置１１は、まず記憶部から入力κを読み込む（ステップ５０１）。続いて、鍵生成装置１１はＧ＿κの元ｇをランダムに選択する（ステップ５０２）。続いて、鍵生成装置１１はＺ＿κの元ｘ＿１，・・・，ｘ＿ｎをランダムに選択する（ステップ５０３）。続いて、鍵生成装置１１はｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝とする（ステップ５０４）。続いて、鍵生成装置１１はｐｋｃａｍ＝（κ，ｇ，ｈ＿１，・・・，ｈ＿ｎ）、ｓｋｃａｍ＝（ｘ＿１，・・・，ｘ＿ｎ）とする（ステップ５０５）。最後に、鍵生成装置１１は記憶部に出力（ｐｋｃａｍ，ｓｋｃａｍ）を書き込む（ステップ５０６）。【００７５】
図８は、第２の実施例の署名装置１２によるＣｏｍ＿ｎアルゴリズムの動作を示すフローチャートである。図８を参照すると、署名装置１２は、まず記憶部から入力ｐｋｃａｍ＝（κ，ｇ，ｈ＿１，・・・，ｈ＿ｎ）、ｍ＿０を読み込む（ステップ６０１）。続いて、署名装置１２はＺ＿κの元ｔ＿１，・・・，ｔ＿ｎを選択し、ｔ＝（ｔ＿１，・・・，ｔ＿ｎ）とする（ステップ６０２）。続いて、署名装置１２はＣ＝ｇ＾｛Ｈ（ｍ＿０）｝ｈ＿１＾｛ｔ＿１｝・・・ｈ＿ｎ＾｛ｔ＿ｎ｝とする（ステップ６０３）。続いて、署名装置１２は記憶部に出力（Ｃ，ｔ）を書き込む（ステップ６０４）。【００７６】
図９は、第２の実施例の署名装置１２によるＣａｍ＿ｎアルゴリズムの動作を示すフローチャートである。図９を参照すると、署名装置１２は、まず記憶部から入力ｐｋｃａｍ＝（κ，ｇ，ｈ＿１，・・・，ｈ＿ｎ）、ｓｋｃａｍ＝（ｘ＿１，・・・，ｘ＿ｎ）、ｍ、Ｃ、ｔ＝（ｔ＿１，・・・，ｔ＿ｎ）を読み込む（ステップ７０１）。続いて、署名装置１２はＺ＿κの元の中から、Ｈ（ｍ＿０）＋ｔ＿１ｘ＿１＋・・・＋ｔ＿ｎｘ＿ｎ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たすものを選択し、ｒ＝（ｒ＿１，・・・，ｒ＿ｎ）とする（ステップ７０２）。最後に、署名装置１２は記憶部に出力ｒを書き込む（ステップ７０３）。【００７７】
図１０は、第２の実施例の検証装置１３によるＣｏｍＶｅｒ＿ｎアルゴリズムの動作を示すフローチャートである。図１０を参照すると、検証装置１３は、まず記憶部から入力としてｐｋｃａｍ＝（κ，ｇ，ｈ＿１，・・・，ｈ＿ｎ）、ｍ、ｒ＝（ｒ＿１，・・・，ｒ＿ｎ）を読み込む（ステップ８０１）。続いて、検証装置１３はＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝とする（ステップ８０２）。最後に、検証装置１３は記憶部に出力Ｃを書き込む（ステップ８０３）。【００７８】
以上説明したように、第２の実施例によれば、拡張したカメレオン・コミットメント方式を用いているので、より安全性が高められている。【００７９】
（第３の実施例）
第３の実施例は、第２の実施例の演算量を低減した例である。第３の実施例による電子署名システムは図３に示した第１、第２の実施例と同様の構成を有している。第３の実施例は、第２の実施例におけるＣｏｍ＿ｎアルゴリズムの代わりに、演算を削減したＣｏｍ’＿ｎアルゴリズムを適用し、第２の実施例におけるＣａｍ＿ｎアルゴリズムの代わりに、演算を削減したＣａｍ’＿ｎアルゴリズムを適用している。【００８０】
図１１は、第３の実施例の署名装置１２によるＣｏｍ’＿ｎアルゴリズムの動作を示すフローチャートである。図１１を参照すると、署名装置１２は、まず記憶部から入力ｐｋｃａｍ＝（κ，ｇ，ｈ＿１，・・・，ｈ＿ｎ）、ｍ＿０を読み込む（ステップ９０１）。続いて、署名装置１２はＺ＿κの元ｔをランダムに選択する（ステップ９０２）。続いて、署名装置１２はＣ＝ｇ＾ｔする（ステップ９０３）。最後に、署名装置１２は記憶部に出力（Ｃ，ｔ）を書き込む（ステップ９０４）。【００８１】
図１２は、第３の実施例の署名装置１２によるＣａｍ’＿ｎアルゴリズムの動作を示すフローチャートである。図１２を参照すると、署名装置１２は、まず記憶部から入力ｐｋｃａｍ＝（κ，ｇ，ｈ＿１，・・・，ｈ＿ｎ）、ｓｋｃａｍ＝（ｘ＿１，・・・，ｘ＿ｎ）、ｍ、Ｃ、ｔを読み込む（ステップ１００１）。続いて、署名装置１２はＺ＿κの元ｒ＿１，・・・，ｒ＿ｎの中で、ｔ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たすものを選択し、ｒ＝（ｒ＿１，・・・，ｒ＿ｎ）とする（ステップ１００２）。最後に、署名装置１２は記憶部に出力ｒを書き込む（ステップ１００３）。【００８２】
以上説明したように、第３の実施例によれば、第２の実施例のアルゴリズムを単純化しているので演算量を低減することができる。
【図１】
2008026345.tif 000003
【図２】
2008026345.tif 000004
【図３】
2008026345.tif 000005
【図４】
2008026345.tif 000006
【図５】
2008026345.tif 000007
【図６】
2008026345.tif 000008
【図７】
2008026345.tif 000009
【図８】
2008026345.tif 000010
【図９】
2008026345.tif 000011
【図１０】
2008026345.tif 000012
【図１１】
2008026345.tif 000013
【図１２】
2008026345.tif 000014
【手続補正書】
【提出日】平成19年8月13日(2007.8.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムであって、
所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより第１の公開鍵および第１の秘密鍵を生成し、前記セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより第２の公開鍵および第２の秘密鍵を生成する鍵生成装置と、
前記鍵生成装置で生成された前記第２の公開鍵と任意のメッセージを入力として、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成し、前記鍵生成装置で生成された前記第１の秘密鍵を入力として、前記偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成し、前記対象メッセージに前記第１の署名を付加した署名付加メッセージ、前記第２の公開鍵、前記第２の秘密鍵、前記コミットメント、および前記第１の乱数を入力として、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、前記第１の署名と前記第２の乱数を含めて前記対象メッセージに対する前記電子署名を生成する署名装置と、
前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した署名付加メッセージ、前記電子署名に含まれている前記第２の乱数、および前記第２の公開鍵を入力として、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成し、生成された該コミットメント、前記第１の署名、および前記第１の公開鍵を入力として、前記偽造不能性を満たす電子署名方式の検証アルゴリズムによって該第１の署名の正当性を検証し、その検証結果を前記電子署名の検証結果とする検証装置と、を有する電子署名システム。
【請求項２】
前記鍵生成装置は、前記カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにおいて、セキュリパラメータをκとして、群Ｇ＿κから元ｇを選択し、群Ｇ＿κと位数が等しい巡回群Ｚ＿κから自然数ｎ個の元ｘ＿１，・・・，ｘ＿ｎをランダムに選択し、ｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝を算出し、前記第２の公開鍵にｇ，ｈ＿１，・・・，ｈ＿ｎを含め、前記第２の秘密鍵にｘ＿１，・・・，ｘ＿ｎを含め、
前記署名装置は、前記Ｃｏｍアルゴリズムにおいて、巡回群Ｚ＿κの元ｔ＿１，・・・，ｔ＿ｎを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ＿０）｝ｈ＿１＾｛ｔ＿１｝・・・ｈ＿ｎ＾｛ｔ＿ｎ｝を算出し、前記Ｃａｍアルゴリズムにおいて、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、Ｈ（ｍ＿０）＋ｔ＿１ｘ＿１＋・・・＋ｔ＿ｎｘ＿ｎ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含め、
前記検証装置は、前記ＣｏｍＶｅｒアルゴリズムにおいて、前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝を算出する、請求項１に記載の電子署名システム。
【請求項３】
前記鍵生成装置は、前記カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにおいて、セキュリパラメータをκとして、群Ｇ＿κから元ｇを選択し、群Ｇ＿κと位数が等しい巡回群Ｚ＿κから自然数ｎ個の元ｘ＿１，・・・，ｘ＿ｎをランダムに選択し、ｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝を算出し、前記第２の公開鍵にｇ，ｈ＿１，・・・，ｈ＿ｎを含め、前記第２の秘密鍵にｘ＿１，・・・，ｘ＿ｎを含め、
前記署名装置は、前記Ｃｏｍアルゴリズムにおいて、巡回群Ｚ＿κの元ｔを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾ｔを算出し、前記Ｃａｍアルゴリズムにおいて、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、ｔ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含め、
前記検証装置は、前記ＣｏｍＶｅｒアルゴリズムにおいて、前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝を算出する、請求項１に記載の電子署名システム。
【請求項４】
（削除）
【請求項５】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムの公開鍵と秘密鍵を生成する鍵生成装置であって、
所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより、前記公開鍵に含める第１の公開鍵と前記秘密鍵に含める第１の秘密鍵とを生成する生成部と、
前記セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより、前記公開鍵に含める第２の公開鍵と前記秘密鍵に含める第２の秘密鍵とを生成するＧｅｎＣａｍ部と、を有し、
前記ＧｅｎＣａｍ部は、前記カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにおいて、セキュリパラメータをκとして、群Ｇ＿κから元ｇを選択し、群Ｇ＿κと位数が等しい巡回群Ｚ＿κから自然数ｎ個の元ｘ＿１，・・・，ｘ＿ｎをランダムに選択し、ｈ＿１＝ｇ＾｛ｘ＿１｝，・・・，ｈ＿ｎ＝ｇ＾｛ｘ＿ｎ｝を算出し、前記第２の公開鍵にｇ，ｈ＿１，・・・，ｈ＿ｎを含め、前記第２の秘密鍵にｘ＿１，・・・，ｘ＿ｎを含める、鍵生成装置。
【請求項６】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムにおいて、請求項５に記載の鍵生成装置で生成された公開鍵および秘密鍵を用いて前記電子署名を生成する署名装置であって、
前記鍵生成装置で生成された前記公開鍵に含まれている前記第２の公開鍵と任意のメッセージを入力として、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成するＣｏｍ部と、
前記鍵生成装置で生成された前記秘密鍵に含まれている前記第１の秘密鍵を入力として、前記偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成する署名部と、
前記対象メッセージに前記第１の署名を付加した署名付加メッセージ、前記公開鍵に含まれている前記第２の公開鍵、前記秘密鍵に含まれている前記第２の秘密鍵、前記コミットメント、および前記第１の乱数を入力として、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、前記第１の署名と前記第２の乱数を含めて前記対象メッセージに対する前記電子署名を生成するＣａｍ部と、を有する署名装置。
【請求項７】
前記公開鍵および前記秘密鍵は、請求項５に記載の鍵生成装置によって生成され、
前記Ｃｏｍ部は、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成するとき、巡回群Ｚ＿κの元ｔ＿１，・・・，ｔ＿ｎを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ＿０）｝ｈ＿１＾｛ｔ＿１｝・・・ｈ＿ｎ＾｛ｔ＿ｎ｝を算出し、
前記Ｃａｍ部は、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成するとき、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、Ｈ（ｍ＿０）＋ｔ＿１ｘ＿１＋・・・＋ｔ＿ｎｘ＿ｎ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含める、
請求項６に記載の署名装置。
【請求項８】
前記公開鍵および前記秘密鍵は、請求項５に記載の鍵生成装置によって生成され、
前記Ｃｏｍ部は、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成するとき、巡回群Ｚ＿κの元ｔを選択し、前記任意のメッセージｍ＿０と前記ｔ＿１，・・・，ｔ＿ｎを用いて、前記コミットメントＣ＝ｇ＾ｔを算出し、
前記Ｃａｍ部は、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成するとき、前記対象メッセージに前記第１の署名を付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、巡回群Ｚ＿κの元の中から、ｔ＝Ｈ（ｍ）＋ｒ＿１ｘ＿１＋・・・＋ｒ＿ｎｘ＿ｎ  ｍｏｄ  ｑ＿κを満たす元ｒ＿１，・・・，ｒ＿ｎを選択し、前記第２の乱数に該ｒ＿１，・・・，ｒ＿ｎを含める、
請求項６に記載の署名装置。
【請求項９】
対象メッセージに対して生成した電子署名によって前記対象メッセージの正当性を検証する電子署名システムにおいて、請求項６に記載の署名装置で生成された電子署名を検証する検証装置であって、
前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した署名付加メッセージ、前記電子署名に含まれている前記第２の乱数、および前記第２の公開鍵を入力として、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成するＣｏｍＶｅｒ部と、
前記ＣｏｍＶｅｒ部で生成された該コミットメントと、前記第１の署名と、前記第１の公開鍵とを入力として、前記偽造不能性を満たす電子署名方式の検証アルゴリズムによって、該第１の署名の正当性を検証し、その検証結果を前記電子署名の検証結果とする検証部と、を有する検証装置。
【請求項１０】
前記電子署名は、請求項７または８に記載の署名装置によって生成され、
前記ＣｏｍＶｅｒ部は、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成するとき、前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した前記署名付加メッセージｍのハッシュ値Ｈ（ｍ）を算出し、前記コミットメントＣ＝ｇ＾｛Ｈ（ｍ）｝ｈ＿１＾｛ｒ＿１｝・・・ｈ＿ｎ＾｛ｒ＿ｎ｝を算出する、請求項９に記載の検証装置。
【請求項１１】
鍵生成装置の生成した鍵を用いて署名装置が対象メッセージに対して生成した電子署名を検証装置が検証する電子署名システムにおける電子署名検証方法であって、
前記鍵生成装置において、
所定のセキュリティ・パラメータを入力として、偽造不能性を満たす電子署名方式の鍵生成アルゴリズムにより第１の公開鍵および第１の秘密鍵を生成し、
前記セキュリティ・パラメータを入力として、カメレオン・コミットメント方式のＧｅｎＣａｍアルゴリズムにより第２の公開鍵および第２の秘密鍵を生成し、
前記署名装置において、
前記鍵生成装置で生成された前記第２の公開鍵と任意のメッセージを入力として、前記カメレオン・コミットメントのＣｏｍアルゴリズムによってコミットメントと第１の乱数を生成し、
前記鍵生成装置で生成された前記第１の秘密鍵を入力として、前記偽造不能性を満たす電子署名方式の署名アルゴリズムによって第１の署名を生成し、
前記対象メッセージに前記第１の署名を付加した署名付加メッセージ、前記第２の公開鍵、前記第２の秘密鍵、前記コミットメント、および前記第１の乱数を入力として、前記カメレオン・コミットメント方式のＣａｍアルゴリズムによって第２の乱数を生成し、
前記第１の署名と前記第２の乱数を含めて前記対象メッセージに対する前記電子署名を生成し、
前記検証装置において、
前記電子署名に含まれている前記第１の署名を前記対象メッセージに付加した署名付加メッセージ、前記電子署名に含まれている前記第２の乱数、および前記第２の公開鍵を入力として、前記カメレオン・コミットメント方式のＣｏｍＶｅｒアルゴリズムによってコミットメントを生成し、
生成された該コミットメント、前記第１の署名、および前記第１の公開鍵を入力として、前記偽造不能性を満たす電子署名方式の検証アルゴリズムによって該第１の署名の正当性を検証し、その検証結果を前記電子署名の検証結果とする、電子署名検証方法。
【国際調査報告】
2008026345.tif 000015
2008026345.tif 000016