(57)【特許請求の範囲】
【請求項１】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ｅを双線形写像、ψをＧ２からＧ１への同型写像とするときに、
署名生成装置の鍵生成手段が、少なくとも秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）を生成する秘密鍵生成ステップと、
前記鍵生成手段が、公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元）を生成する公開鍵生成ステップと、
前記署名生成装置の文書取得手段が、文書ｍを取得する文書取得ステップと、
前記署名生成装置の数値生成手段が、数値ｒとｓを生成する数値生成ステップと、
前記署名生成装置の署名生成手段が、σを、σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）により計算する署名生成ステップと、
前記署名生成装置の署名送信手段が、署名（σ，ｒ，ｓ）と文書ｍとを署名検証装置に送信する署名送信ステップと、
前記署名検証装置の署名受信手段が、署名（σ，ｒ，ｓ）と文書ｍとを前記署名生成装置から受信する署名受信ステップと、
前記署名検証装置の公開鍵取得手段が、前記署名生成装置の前記公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する公開鍵取得ステップと、
前記署名検証装置の署名検証手段が、ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）が成り立つことを確認する署名検証ステップと
を有す
ことを特徴とするデジタル署名方法。
【請求項２】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ｅを双線形写像、ψをＧ２からＧ１への同型写像とするときに、
署名生成装置の鍵生成手段が、少なくとも秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）を生成する秘密鍵生成ステップと、
前記鍵生成手段が、公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元）を生成する公開鍵生成ステップと、
前記署名生成装置の文書取得手段が、文書ｍを取得する文書取得ステップと、
前記署名生成装置の数値生成手段が、数値ｓを生成する第１の数値生成ステップと、
前記数値生成手段または前記署名生成装置の署名生成手段が、Ａを、Ａ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝により計算するＡ計算ステップと、
前記数値生成手段が、数値ｒを生成する第２の数値生成ステップと、
前記署名生成手段が、σを、σ＝Ａ１／（ｘ＋ｒ）により計算する署名生成ステップと、
前記署名生成装置の署名送信手段が、署名（σ，ｒ，ｓ）と文書ｍとを署名検証装置に送信する署名送信ステップと、
前記署名検証装置の署名受信手段が、署名（σ，ｒ，ｓ）と文書ｍとを前記署名生成装置から受信する署名受信ステップと、
前記署名検証装置の公開鍵取得手段が、前記署名生成装置の前記公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する公開鍵取得ステップと、
前記署名検証装置の署名検証手段が、ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）が成り立つことを確認する署名検証ステップと
を有す
ことを特徴とするデジタル署名方法。
【請求項３】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ψをＧ２からＧ１への同型写像とし、署名検証装置は、署名生成装置が生成する公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元、ｘは０からｐ−１の整数）を用いて、前記署名生成装置が文書ｍに付与した署名（σ，ｒ，ｓ）の有効性を検証するものとするときに、
前記署名生成装置の鍵生成手段が、少なくとも秘密鍵ｘを生成する秘密鍵生成ステップと、
前記鍵生成手段が、公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを生成する公開鍵生成ステップと、
前記署名生成装置の文書取得手段が、文書ｍを取得する文書取得ステップと、
前記署名生成装置の数値生成手段が、数値ｒとｓを生成する数値生成ステップと、
前記署名生成装置の署名生成手段が、σを、σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）により計算する署名生成ステップと、
前記署名生成装置の署名送信手段が、署名（σ，ｒ，ｓ）と文書ｍとを前記署名検証装置に送信する署名送信ステップと
を有すことを特徴とするデジタル署名生成方法。
【請求項４】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ψをＧ２からＧ１への同型写像とし、署名検証装置は、署名生成装置が生成する公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元、ｘは０からｐ−１の整数）を用いて、前記署名生成装置が文書ｍに付与した署名（σ，ｒ，ｓ）の有効性を検証するものとするときに、
前記署名生成装置の鍵生成手段が、少なくとも秘密鍵ｘを生成する秘密鍵生成ステップと、
前記鍵生成手段が、公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを生成する公開鍵生成ステップと、
前記署名生成装置の文書取得手段が、文書ｍを取得する文書取得ステップと、
前記署名生成装置の数値生成手段が、数値ｓを生成する第１の数値生成ステップと、
前記数値生成手段または前記署名生成装置の署名生成手段が、Ａを、Ａ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝により計算するＡ計算ステップと、
前記数値生成手段が、数値ｒを生成する第２の数値生成ステップと、
前記署名生成手段が、σを、σ＝Ａ１／（ｘ＋ｒ）により計算する署名生成ステップと、
前記署名生成装置の署名送信手段が、署名（σ，ｒ，ｓ）と文書ｍとを前記署名検証装置に送信する署名送信ステップと
を有すことを特徴とするデジタル署名生成方法。
【請求項５】
請求項１から４のいずれかに記載の方法であって、
前記秘密鍵生成ステップでは、秘密鍵ｙ、ｚ（ただし、ｙ、ｚは０からｐ−１の整数）も生成し、
前記公開鍵生成ステップでは、公開鍵ｕとｖを、ｕ＝ｇ２ｙ、ｖ＝ｇ２ｚの計算により生成する
ことを特徴とする方法。
【請求項６】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ｅを双線形写像とし、署名生成装置は、秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）と公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元）と数値ｒとｓを用いて、文書ｍに対し署名（σ，ｒ，ｓ）を付与するものとするときに、
署名検証装置の署名受信手段が、署名（σ，ｒ，ｓ）と文書ｍとを前記署名生成装置から受信する署名受信ステップと、
前記署名検証装置の公開鍵取得手段が、前記署名生成装置の公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する公開鍵取得ステップと、
前記署名検証装置の署名検証手段が、ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）が成り立つことを確認する署名検証ステップと
を有すことを特徴とするデジタル署名検証方法。
【請求項７】
請求項１から６のいずれかに記載の方法であって、
前記署名（σ，ｒ，ｓ）の代わりに、署名（σ，ｇ２ｒ，ｓ）を用いる
ことを特徴とする方法。
【請求項８】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ψをＧ２からＧ１への同型写像とし、署名検証装置は、署名生成装置が生成する公開鍵ｇ１、ｇ２、ｗ、ｕ（ただし、ｗ＝ｇ２ｘ、ｕはＧ２の元、ｘは０からｐ−１の整数）を用いて、前記署名生成装置が文書ｍに付与した署名（σ，ｒ）の有効性を検証するものとするときに、
前記署名生成装置の鍵生成手段が、少なくとも秘密鍵ｘを生成する秘密鍵生成ステップと、
前記鍵生成手段が、公開鍵ｇ１、ｇ２、ｗ、ｕを生成する公開鍵生成ステップと、
前記署名生成装置の文書取得手段が、文書ｍを取得する文書取得ステップと、
前記署名生成装置の数値生成手段が、数値ｒとｓを生成する数値生成ステップと、
前記署名生成装置の署名生成手段が、σを、σ＝｛ｇ１ｍψ（ｕ）｝１／（ｘ＋ｒ）により計算する署名生成ステップと、
前記署名生成装置の署名送信手段が、署名（σ，ｒ）と文書ｍとを前記署名検証装置に送信する署名送信ステップと
を有すことを特徴とするデジタル署名生成方法。
【請求項９】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ψをＧ２からＧ１への同型写像とし、署名検証装置は、署名生成装置が生成する公開鍵ｇ１、ｇ２、ｗ、ｕ（ただし、ｗ＝ｇ２ｘ、ｕはＧ２の元、ｘは０からｐ−１の整数）を用いて、前記署名生成装置が文書ｍに付与した署名（σ，ｒ）の有効性を検証するものとするときに、
前記署名生成装置の鍵生成手段が、少なくとも秘密鍵ｘを生成する秘密鍵生成ステップと、
前記鍵生成手段が、公開鍵ｇ１、ｇ２、ｗ、ｕを生成する公開鍵生成ステップと、
前記署名生成装置の文書取得手段が、文書ｍを取得する文書取得ステップと、
前記署名生成装置の数値生成手段が、数値ｓを生成する第１の数値生成ステップと、
前記数値生成手段または前記署名生成装置の署名生成手段が、Ａを、Ａ＝｛ｇ１ｍψ（ｕ）｝により計算するＡ計算ステップと、
前記数値生成手段が、数値ｒを生成する第２の数値生成ステップと、
前記署名生成手段が、σを、σ＝Ａ１／（ｘ＋ｒ）により計算する署名生成ステップと、
前記署名生成装置の署名送信手段が、署名（σ，ｒ）と文書ｍとを前記署名検証装置に送信する署名送信ステップと
を有すことを特徴とするデジタル署名生成方法。
【請求項１０】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ｅを双線形写像とし、署名生成装置は、秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）と公開鍵ｇ１、ｇ２、ｗ、ｕ（ただし、ｗ＝ｇ２ｘ、ｕはＧ２の元）と数値ｒとｓを用いて、文書ｍに対し署名（σ，ｒ）を付与するものとするときに、
署名検証装置の署名受信手段が、署名（σ，ｒ）と文書ｍとを前記署名生成装置から受信する署名受信ステップと、
前記署名検証装置の公開鍵取得手段が、前記署名生成装置の公開鍵ｇ１、ｇ２、ｗ、ｕを取得する公開鍵取得ステップと、
前記署名検証装置の署名検証手段が、ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕ）が成り立つことを確認する署名検証ステップと
を有すことを特徴とするデジタル署名検証方法。
【請求項１１】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ｅを双線形写像、ψをＧ２からＧ１への同型写像とするときに、
少なくとも秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）を生成するとともに、公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元）を生成する鍵生成手段と、
文書ｍを取得する文書取得手段と、
数値ｒまたはｓを生成する数値生成手段と、
σを、σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）を計算する署名生成手段と、
署名（σ，ｒ，ｓ）と文書ｍとを署名検証装置に送信する署名送信手段と
を備える署名生成装置と、
署名（σ，ｒ，ｓ）と文書ｍとを前記署名生成装置から受信する署名受信手段と、
前記署名生成装置の前記公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する公開鍵取得手段と、
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）が成り立つことを確認する署名検証手段と
を備える署名検証装置と
を有することを特徴とするデジタル署名システム。
【請求項１２】
デジタル署名生成装置であって、
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ψをＧ２からＧ１への同型写像とし、署名検証装置は、当該デジタル署名生成装置が生成する公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元、ｘは０からｐ−１の整数）を用いて、当該デジタル署名生成装置が文書ｍに付与した署名（σ，ｒ，ｓ）の有効性を検証するものとするときに、
少なくとも秘密鍵ｘを生成するとともに、公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを生成する鍵生成手段と、
文書ｍを取得する文書取得手段と、
数値ｒまたはｓを生成する数値生成手段と、
σを、σ＝ｇ１（ｍ＋ｙ＋ｓｚ）／（ｘ＋ｒ）を計算する署名生成手段と、
署名（σ，ｒ，ｓ）と文書ｍとを前記署名検証装置に送信する署名送信手段と
を備えることを特徴とするデジタル署名生成装置。
【請求項１３】
Ｇ１とＧ２を双線形群かつ位数ｐ（ｐは素数）の巡回群、ｇ１をＧ１の生成元、ｇ２をＧ２の生成元、ｅを双線形写像とし、署名生成装置は、秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）と公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元）と数値ｒとｓを用いて、文書ｍに対し署名（σ，ｒ，ｓ）を付与するものとするときに、
署名（σ，ｒ，ｓ）と文書ｍとを前記署名生成装置から受信する署名受信手段と、
前記署名生成装置の前記公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する公開鍵取得手段と、
σが１でないこと、およびｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）が成り立つことを確認する署名検証手段と
を備えるデジタル署名検証装置。
【請求項１４】
請求項３から１０のいずれかに記載の方法をコンピュータにより実行させるプログラム。
【請求項１５】
請求項１４記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
ハッシュ関数を利用しないデジタル署名方法、デジタル署名生成方法、デジタル署名検証方法、それらの方法を用いたシステム、装置、プログラム、および記録媒体に関する。
【背景技術】
【０００２】
従来から数多くのデジタル署名方式が提案されているが、ほとんどの署名方式はハッシュ関数を利用することで安全性を保証している（非特許文献１）。ハッシュ関数を利用しない署名方式としては、BonehとBoyenの署名方式（非特許文献２、pp.60-63）がある。BonehとBoyenの署名方式での署名生成処理フローを図１に、署名検証処理フローを図２に示す。Ｇ１とＧ２は巡回群であり、どちらも位数はｐである。また、ｇ１はＧ１の生成元、ｇ２はＧ２の生成元とする。署名検証装置は、｛０，１，・・・，ｐ−１｝からランダムに秘密鍵ｘとｙを生成し（Ｓ８１０）、公開鍵ｇ１、ｇ２、ｕ（＝ｇ２ｘ）、ｖ（＝ｇ２ｙ）を生成する（Ｓ８２０）。次に文書ｍを取得する（Ｓ８３０）。乱数ｒを｛０，１，・・・，ｐ−１｝から生成し（Ｓ８４０）、ｘ＋ｍ＋ｙｒが０かを確認する（Ｓ８５０）。ステップＳ８５０がＹｅｓの場合には、ステップＳ８４０に戻り、再度乱数ｒを生成する。ステップＳ８５０がＮｏの場合にはステップＳ８６０に進む。ステップＳ８６０では、
σ＝ｇ１１／（ｘ＋ｍ＋ｙｒ）
を計算する（Ｓ８６０）。最後に署名（σ，ｒ）を生成し、署名（σ，ｒ）と文書ｍを送信する（Ｓ８７０）。
【０００３】
署名検証装置では、署名（σ，ｒ）と文書ｍとを受信し（Ｓ９１０）、公開鍵ｇ１、ｇ２、ｕ、ｖを取得する（Ｓ９２０）。次に
ｅ（σ，ｕｇ２ｍｖｒ）＝ｅ（ｇ１，ｇ２）
を確認する（Ｓ９３０）。ここで、ｅは双線形写像であって、ＧＴを位数ｐの巡回群とすると、ｅ：Ｇ１×Ｇ２→ＧＴであり、次のような性質を有している。Ｇ１に属する全てのｕとＧ２に属する全てのｖ、｛０，１，・・・，ｐ−１｝の全ての元ａ、ｂに対して、
ｅ（ｕａ，ｖｂ）＝ｅ（ｕ，ｖ）ａｂ
が成り立つ。また、
ｅ（ｇ１，ｇ２）≠１
である。ステップＳ９３０がＹｅｓの場合、署名は有効と判断され（Ｓ９４０）、Ｎｏの場合、署名は無効と判断される（Ｓ９５０）。
【０００４】
BonehとBoyenの署名方式では、署名生成過程（ステップＳ８６０）で、文書情報ｍが署名作成式のべき乗部の分母にあるため、グループ署名やブラインド署名などに利用することが困難である。
【非特許文献１】Mihir Bellare and Phillip Rogaway, “The Exact Security of Digital Signatures - How to Sign with RSA and Rabin”, Proceeding of Eurocrypt’96, LNCS 1070, Springer-Verlag, pp.399-416 (1996).
【非特許文献２】Dan Boneh and Xavier Boyen, “Short Signatures Without Random Oracles”, Proceeding of Crypto’04, LNCS, Springer-Verlag, pp.56-73 (2004).
【発明の開示】
【発明が解決しようとする課題】
【０００５】
BonehとBoyenの署名方式は、ハッシュ関数を使わない署名方式であるが、
σ＝ｇ１１／（ｘ＋ｍ＋ｙｒ）
のように文書情報ｍが署名作成式のべき乗部の分母にある。このため、この署名方式を、他のタイプの署名（グループ署名やブラインド署名など）に利用することが困難である。本発明の目的は、ハッシュ関数を使わない署名方式であり、かつ他のタイプの署名（グループ署名やブラインド署名など）に利用できる署名方式を提供することである。
【課題を解決するための手段】
【０００６】
本発明の署名生成装置では、少なくとも秘密鍵ｘ（ただし、ｘは０からｐ−１の整数）と公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖ（ただし、ｗ＝ｇ２ｘ、ｕとｖはＧ２の元）を生成し、文書ｍを取得する。次に、乱数ｒ、ｓを生成し、
σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）
を計算し、署名（σ，ｒ，ｓ）と文書ｍとを署名検証装置に送信する。署名検証装置では、署名（σ，ｒ，ｓ）と文書ｍとを受信し、署名生成装置の公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する。次に、
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）
が成り立つことを確認し、真の場合には署名は有効、偽の場合には署名は無効と判断する。
【発明の効果】
【０００７】
本発明によれば、署名生成が
σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）
により行われる。したがって、文書ｍに依存した値Ａ（＝ｇ１ｍψ（ｕ）ψ（ｖ）ｓ）を、公開鍵を用いて（秘密鍵を用いないで）、
Ａ＝ｇ１ｍψ（ｕ）ψ（ｖ）ｓ
により計算しておき、その後に秘密鍵ｘを用いて
σ＝Ａ１／（ｘ＋ｒ）
を計算することができる。
【０００８】
この性質を用いると、Ａを変形した情報Ｂを、ｍを秘密にしたまま署名者に渡し、署名者にＢ１／（ｘ＋ｒ）を計算させ、その値から
σ＝Ａ１／（ｘ＋ｒ）
を取り出すようなブラインド署名が構成できる。また、同じ理由により、グループ署名などの様々な署名方式に柔軟に応用できる。
【発明を実施するための最良の形態】
【０００９】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。また、以下の説明ではＧ１とＧ２は次の性質を持つ双線形群とする。
（１）Ｇ１とＧ２は、それぞれ位数がｐ（ｐは素数）の巡回群である。
（２）ｇ１はＧ１の生成元であり、ｇ２はＧ２の生成元である。
（３）ψは、Ｇ２からＧ１への同型写像であり、ψ（ｇ２）＝ｇ１である。
（４）ｅは、双線形写像であり、ｅ：Ｇ１×Ｇ２→ＧＴである。ただし、ＧＴは位数ｐの巡回群である。つまり、ａ，ｂをＧ１の元、ｃ，ｄをＧ２の元とすると、
ｅ（ａｂ，ｃ）＝ｅ（ａ，ｃ）ｅ（ｂ，ｃ）
ｅ（ａ，ｃｄ）＝ｅ（ａ，ｃ）ｅ（ａ，ｄ）
が成り立つ。
【００１０】
（５）ｅ，ψおよびＧ１，Ｇ２，ＧＴの群演算は効率的に計算できる。
［第１実施形態］
本発明のデジタル署名方式のシステム構成例を図３に示す。また、署名生成装置１００の処理フローを図４に、署名検証装置２００の処理フローを図５に示す。本実施形態のデジタル署名システムは署名生成装置１００と署名検証装置２００とから構成される。署名生成装置１００は、鍵生成手段１１０、文書取得手段１２０、乱数生成手段１３０、署名生成手段１４０、署名送信手段１５０を有している。また署名検証装置２００は、署名受信手段２１０、公開鍵取得手段２２０、署名検証手段２３０、署名検証結果出力手段２４０を有している。
【００１１】
まず、署名生成について説明する。署名生成装置１００の鍵生成手段１１０は、｛０，１，・・・，ｐ−１｝から任意の元を選定することで、秘密鍵ｘ、ｙ、ｚを生成する（Ｓ１１０）。また、鍵生成手段１１０は、公開鍵ｇ１、ｇ２、ｗ（＝ｇ２ｘ）、ｕ（＝ｇ２ｙ）、ｖ（＝ｇ２ｚ）を生成する（Ｓ１１５）。文書取得手段１２０は、文書ｍを取得する（Ｓ１２０）。乱数生成手段１３０は、｛０，１，・・・，ｐ−１｝から乱数ｒ、ｓを生成する（Ｓ１３０）。次に、ｍ＋ｙ＋ｓｚが０、またはｘ＋ｒが０でないかを確認する（Ｓ１３５）。ステップＳ１３５がＹｅｓの場合には、乱数ｒ、ｓを再度生成するために、ステップＳ１３０に戻る。ステップＳ１３５がＮｏの場合には、ステップＳ１４０へ進む。署名生成手段１４０は、
σ＝ｇ１（ｍ＋ｙ＋ｓｚ）／（ｘ＋ｒ）
を計算し、署名（σ，ｒ，ｓ）を生成する（Ｓ１４０）。署名送信手段１５０は、署名（σ，ｒ，ｓ）と文書ｍを署名検証装置２００へ送信する（Ｓ１５０）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００１２】
次に署名検証について説明する。署名検証装置２００の署名受信手段２１０は、署名生成装置１００から署名（σ，ｒ，ｓ）と文書ｍを受信する（Ｓ２１０）。公開鍵取得手段２２０は、署名生成装置１００の公開鍵ｇ１、ｇ２、ｗ、ｕ、ｖを取得する（Ｓ２２０）。署名検証手段２３０は、
σ≠１
かつ
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）
を確認する（Ｓ２３０）。ここで、σ≠１の確認は省略することもできる。ステップＳ２３０がＹｅｓの場合、署名検証結果出力手段はＯＫを出力する（Ｓ２４０）。ステップＳ２３０がＮｏの場合、署名検証結果出力手段はＮＧを出力する（Ｓ２４５）。
【００１３】
ここで、署名検証が正しく行われることを証明する。ｅ（σ，ｗｇ２ｒ）は、
σ＝ｇ１（ｍ＋ｙ＋ｓｚ）／（ｘ＋ｒ）
と
ｗ＝ｇ２ｘ
から、ｅ（ｇ１（ｍ＋ｙ＋ｓｚ）／（ｘ＋ｒ），ｇ２ｘ＋ｒ）と表現できる。ここで、双線形写像ｅの性質から、
ｅ（ｇ１（ｍ＋ｙ＋ｓｚ）／（ｘ＋ｒ），ｇ２ｘ＋ｒ）＝ｅ（ｇ１（ｍ＋ｙ＋ｓｚ），ｇ２）
＝ｅ（ｇ１，ｇ２（ｍ＋ｙ＋ｓｚ））
となる。ｇ２ｙ＝ｕ、ｇ２ｚ＝ｖを代入すると、
ｅ（ｇ１，ｇ２（ｍ＋ｙ＋ｓｚ））＝ｅ（ｇ１，ｇ２ｍｕｖｓ）
となる。よって、
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）
である。したがって、署名検証（ステップＳ２３０）が正しく行われることになる。
【００１４】
このように署名、検証を行うことで、署名生成時に文書ｍをべき数の分子とすることができる。
［変形例１］
第１実施形態では、べき乗の分子と分母とを同時に計算したが、別々に計算する方法もある。本変形例では、図３に点線で示す記録手段１６０が、署名生成装置１００’に備えられる。また、署名生成装置１００’には、乱数生成手段１３０’、署名生成手段１４０’が備えられている点が、第１実施形態の署名生成装置１００と異なる。図６に本変形例での署名生成方法の処理フローを示す。なお、署名検証方法は第１実施形態と同じである。ステップＳ１１０、Ｓ１１５，Ｓ１２０は、第１実施形態（図４）と同じである。乱数生成手段１３０’は、｛０，１，・・・，ｐ−１｝から乱数ｓを生成し（Ｓ１３１）、
ｍ＋ｙ＋ｓｚ＝０
かを確認する（Ｓ１３２）。ステップＳ１３２がＹｅｓの場合には、再度乱数ｓを生成するためにステップＳ１３１に戻る。ステップＳ１３２がＮｏの場合には、ステップＳ１４１へ進む。署名生成手段１４０’は、
Ａ＝ｇ１ｍψ（ｕ）ψ（ｖ）ｓ
を計算し（Ｓ１４１）、記録手段１６０にＡを記録する（Ｓ１４２）。ここで、
ψ（ｕ）＝ψ（ｇ２ｙ）＝ψ（ｇ２）ｙ＝ｇ１ｙ
ψ（ｖ）＝ψ（ｇ２ｚ）＝ψ（ｇ２）ｚ＝ｇ１ｚ
であるから、Ａ（＝ｇ１ｍψ（ｕ）ψ（ｖ）ｓ）の計算は、秘密鍵ｙ、ｚを用いないで、Ａ（＝ｇ１（ｍ＋ｙ＋ｓｚ））を求めている。次に乱数生成手段１３０’は、｛０，１，・・・，ｐ−１｝から乱数ｒを生成し（Ｓ１３６）、
ｘ＋ｒ＝０
かを確認する（Ｓ１３７）。ステップＳ１３７がＹｅｓの場合には、再度乱数ｒを生成するためにステップＳ１３６に戻る。ステップＳ１３７がＮｏの場合には、ステップＳ１４３へ進む。署名生成手段１４０’は、
σ＝Ａ１／（ｘ＋ｒ）
を計算し、署名（σ，ｒ，ｓ）を生成する（Ｓ１４３）。第１実施形態と同じように、署名送信手段１５０は、署名（σ，ｒ，ｓ）と文書ｍを署名検証装置２００へ送信する（Ｓ１５０）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００１５】
このように署名生成過程のべき乗計算を分子と分母に分けることで、他のタイプの署名（ブラインド署名やグループ署名など）に本発明を利用することができる。
［変形例２］
変形例１では、単に署名生成過程でのべき乗計算を分子と分母に分けて計算したが、本変形例では、ブラインド署名に本発明を利用した例を示す。本変形例の署名生成装置は、図３の署名生成装置１００”である。署名生成装置１００”は、変形例１の署名生成装置１００’と署名生成手段１４０”のみが異なる。図７に本変形例の署名生成装置１００”の処理フローを示す。本変形例の処理フロー（図７）は、変形例１の処理フロー（図６）と、ステップＳ１４４、Ｓ１４５、Ｓ１４６が異なる。ステップＳ１４４では、署名生成手段１４０”が、ブラインド署名のために、Ａを変形してＢを生成し、署名者にＢを渡す（Ｓ１４４）。署名生成手段１４０”は、署名者からＢ１／（ｘ＋ｒ）を受け取る（Ｓ１４５）。そして、署名生成手段１４０”は、Ｂ１／（ｘ＋ｒ）から
σ＝Ａ１／（ｘ＋ｒ）
を取出し、署名（σ，ｒ，ｓ）を生成する（Ｓ１４６）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００１６】
このように本変形例では、Ａを変形した情報Ｂを、ｍを秘密にしたまま署名者に渡し、署名者にＢ１／（ｘ＋ｒ）を計算させ、その値から
σ＝Ａ１／（ｘ＋ｒ）
を取り出すようなブラインド署名が構成できる。
［第２実施形態］
本実施形態のデジタル署名システムは、図８の署名生成装置３００と署名検証装置２００から構成される。また、署名生成装置３００の処理フローを図９に示す。署名検証装置２００の処理フローは第１実施形態（図５）と同じである。署名生成装置３００は、鍵生成手段３１０、文書取得手段１２０、乱数生成手段３３０、署名生成手段３４０、署名送信手段１５０を有している。
【００１７】
署名生成装置３００の鍵生成手段３１０は、｛０，１，・・・，ｐ−１｝から任意の元を選定することで、秘密鍵ｘを生成する（Ｓ３１０）。また、鍵生成手段３１０は、公開鍵ｇ１、ｇ２、ｗ（＝ｇ２ｘ）、ｕ（巡回群Ｇ２の任意の元）、ｖ（巡回群Ｇ２の任意の元）を生成する（Ｓ３１５）。文書取得手段１２０は、文書ｍを取得する（Ｓ１２０）。乱数生成手段３３０は、｛０，１，・・・，ｐ−１｝から乱数ｒ、ｓを生成する（Ｓ１３０）。次に、ｇ１ｍψ（ｕ）ψ（ｖ）ｓが１、またはｘ＋ｒが０でないかを確認する（Ｓ３３５）。ステップＳ３３５がＹｅｓの場合には、乱数ｒ、ｓを再度生成するために、ステップＳ１３０に戻る。ステップＳ３３５がＮｏの場合には、ステップＳ３４０へ進む。署名生成手段３４０は、
σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）
を計算し、署名（σ，ｒ，ｓ）を生成する（Ｓ３４０）。署名送信手段１５０は、署名（σ，ｒ，ｓ）と文書ｍを署名検証装置２００へ送信する（Ｓ１５０）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００１８】
署名検証は、第１実施形態と同じであるが、本実施形態の場合にも署名検証が正しく行われることを証明する。ｅ（σ，ｗｇ２ｒ）は、
σ＝｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ）
と
ｗ＝ｇ２ｘ
から、ｅ（｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ），ｇ２ｘ＋ｒ）と表現できる。ここで、双線形写像ｅの性質から、
ｅ（｛ｇ１ｍψ（ｕ）ψ（ｖ）ｓ｝１／（ｘ＋ｒ），ｇ２ｘ＋ｒ）
＝ｅ（ｇ１ｍψ（ｕ）ψ（ｖ）ｓ，ｇ２）
＝ｅ（ｇ１ｍ，ｇ２）ｅ（ψ（ｕ），ｇ２）ｅ（ψ（ｖ）ｓ，ｇ２）
となる。また、ψはＧ２からＧ１への同型写像であるから、
ｅ（ｇ１ｍ，ｇ２）ｅ（ψ（ｕ），ｇ２）ｅ（ψ（ｖ）ｓ，ｇ２）
＝ｅ（ｇ１，ｇ２ｍ）ｅ（ｇ１，ｕ）ｅ（ｇ１，ｖｓ）
＝ｅ（ｇ１，ｇ２ｍｕｖｓ）
となる。よって、
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕｖｓ）
である。したがって、本実施形態の場合でも署名検証（ステップＳ２３０）が正しく行われることになる。
【００１９】
このように署名、検証を行うことで、署名生成時に文書ｍをべき数の分子とすることができる。なお、第１実施形態ではｕ＝ｇ２ｙ、ｖ＝ｇ２ｚとしているのに対して、本実施形態はｕとｖを任意の巡回群Ｇ２の元としている。したがって、本実施形態は第１実施形態の上位概念に相当する。
［変形例］
第２実施形態では、べき乗の分子と分母とを同時に計算したが、別々に計算する方法もある。本変形例では、図８に点線で示す記録手段１６０が、署名生成装置３００’に備えられる。また、署名生成装置３００’には、乱数生成手段３３０’、署名生成手段３４０’が備えられている点が、第２実施形態の署名生成装置３００と異なる。図１０に本変形例の署名生成装置３００’の処理フローを示す。なお、署名検証方法は第１、第２実施形態と同じである。ステップＳ３１０、Ｓ３１５，Ｓ１２０は、第２実施形態（図９）と同じである。乱数生成手段３３０’は、｛０，１，・・・，ｐ−１｝から乱数ｓを生成し（Ｓ１３１）、
Ａ＝ｇ１ｍψ（ｕ）ψ（ｖ）ｓ
を計算し（Ｓ３７１）、Ａ＝１かを確認する（Ｓ３３２）。なお、ステップＳ３７１のＡの計算は署名生成手段３４０’が行ってもよい。ステップＳ３３２がＹｅｓの場合には、再度乱数ｓを生成するためにステップＳ１３１に戻る。ステップＳ３３２がＮｏの場合には、ステップＳ３７２へ進む。ステップＳ３７２では、乱数生成手段３３０’または署名生成手段３４０’が、記録手段１６０にＡを記録する（Ｓ３７２）。次に乱数生成手段３３０’’は、｛０，１，・・・，ｐ−１｝から乱数ｒを生成し（Ｓ１３６）、
ｘ＋ｒ＝０
かを確認する（Ｓ１３７）。ステップＳ１３７がＹｅｓの場合には、再度乱数ｒを生成するためにステップＳ１３６に戻る。ステップＳ１３７がＮｏの場合には、ステップＳ１４３へ進む。署名生成手段３４０’は、
σ＝Ａ１／（ｘ＋ｒ）
を計算し、署名（σ，ｒ，ｓ）を生成する（Ｓ１４３）。第２実施形態と同じように、署名送信手段１５０は、署名（σ，ｒ，ｓ）と文書ｍを署名検証装置２００へ送信する（Ｓ１５０）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００２０】
このように署名生成過程のべき乗計算を分子と分母に分けることで、他のタイプの署名（ブラインド署名やグループ署名など）に本発明を利用することができる。
［第３実施形態］
本発明のデジタル署名方式のシステム構成例を図１１に示す。また、署名生成装置５００の処理フローを図１２に、署名検証装置２００’の処理フローを図１３に示す。本実施形態のデジタル署名システムは署名生成装置５００と署名検証装置２００’とから構成される。署名生成装置５００は、鍵生成手段５１０、文書取得手段１２０、乱数生成手段５３０、署名生成手段５４０、署名送信手段５５０を有している。また署名検証装置２００’は、署名受信手段２１０’、公開鍵取得手段２２０’、署名検証手段２３０’、署名検証結果出力手段２４０を有している。
【００２１】
まず、署名生成について説明する。署名生成装置５００の鍵生成手段５１０は、｛０，１，・・・，ｐ−１｝から任意の元を選定することで、秘密鍵ｘを生成する（Ｓ５１０）。また、鍵生成手段５１０は、公開鍵ｇ１、ｇ２、ｗ（＝ｇ２ｘ）、ｕ（巡回群Ｇ２の任意の元）を生成する（Ｓ５１５）。文書取得手段１２０は、文書ｍを取得する（Ｓ１２０）。乱数生成手段５３０は、｛０，１，・・・，ｐ−１｝から乱数ｒを生成する（Ｓ１３６）。次に、ｘ＋ｒが０でないかを確認する（Ｓ１３７）。ステップＳ１３７がＹｅｓの場合には、乱数ｒを再度生成するために、ステップＳ１３６に戻る。ステップＳ１３７がＮｏの場合には、ステップＳ５４０へ進む。署名生成手段５４０は、
σ＝｛ｇ１ｍψ（ｕ）｝１／（ｘ＋ｒ）
を計算し、署名（σ，ｒ）を生成する（Ｓ５４０）。署名送信手段５５０は、署名（σ，ｒ）と文書ｍを署名検証装置２００’へ送信する（Ｓ５５０）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００２２】
次に署名検証について説明する。署名検証装置２００’の署名受信手段２１０’は、署名生成装置５００から署名（σ，ｒ）と文書ｍを受信する（Ｓ２１０’）。公開鍵取得手段２２０’は、署名生成装置５００の公開鍵ｇ１、ｇ２、ｗ、ｕを取得する（Ｓ２２０’）。署名検証手段２３０’は、
σ≠１
かつ
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕ）
を確認する（Ｓ２３０’）。ここで、σ≠１の確認は省略することもできる。ステップＳ２３０’がＹｅｓの場合、署名検証結果出力手段はＯＫを出力する（Ｓ２４０）。ステップＳ２３０’がＮｏの場合、署名検証結果出力手段はＮＧを出力する（Ｓ２４５）。
【００２３】
ここで、署名検証が正しく行われることを証明する。ｅ（σ，ｗｇ２ｒ）は、
σ＝｛ｇ１ｍψ（ｕ）｝１／（ｘ＋ｒ）
と
ｗ＝ｇ２ｘ
から、ｅ（｛ｇ１ｍψ（ｕ）｝１／（ｘ＋ｒ），ｇ２ｘ＋ｒ）と表現できる。ここで、双線形写像ｅの性質から、
ｅ（｛ｇ１ｍψ（ｕ）｝１／（ｘ＋ｒ），ｇ２ｘ＋ｒ）
＝ｅ（ｇ１ｍψ（ｕ），ｇ２）
＝ｅ（ｇ１ｍ，ｇ２）ｅ（ψ（ｕ），ｇ２）
となる。また、ψはＧ２からＧ１への同型写像であるから、
ｅ（ｇ１ｍ，ｇ２）ｅ（ψ（ｕ），ｇ２）
＝ｅ（ｇ１，ｇ２ｍ）ｅ（ｇ１，ｕ）
＝ｅ（ｇ１，ｇ２ｍｕ）
となる。よって、
ｅ（σ，ｗｇ２ｒ）＝ｅ（ｇ１，ｇ２ｍｕ）
である。したがって、署名検証（ステップＳ２３０’）が正しく行われることになる。
【００２４】
このように署名、検証を行うことで、署名生成時に文書ｍをべき数の分子とすることができる。
［変形例］
第３実施形態では、べき乗の分子と分母とを同時に計算したが、別々に計算する方法もある。本変形例では、図１１に点線で示す記録手段１６０が、署名生成装置５００’に備えられる。また、署名生成装置５００’には、乱数生成手段５３０’、署名生成手段５４０’が備えられている点が、第３実施形態の署名生成装置５００と異なる。図１４に本変形例での署名生成方法の処理フローを示す。なお、署名検証方法は第３実施形態と同じである。ステップＳ５１０、Ｓ５１５，Ｓ１２０は、第３実施形態（図１２）と同じである。乱数生成手段５３０’または署名生成手段５４０’は、
Ａ＝ｇ１ｍψ（ｕ）
を計算し（Ｓ５７１）、記録手段１６０にＡを記録する（Ｓ５７２）。次に乱数生成手段５３０’は、｛０，１，・・・，ｐ−１｝から乱数ｒを生成し（Ｓ１３６）、
ｘ＋ｒ＝０
かを確認する（Ｓ１３７）。ステップＳ１３７がＹｅｓの場合には、再度乱数ｒを生成するためにステップＳ１３６に戻る。ステップＳ１３７がＮｏの場合には、ステップＳ５４３へ進む。署名生成手段５４０’は、
σ＝Ａ１／（ｘ＋ｒ）
を計算し、署名（σ，ｒ）を生成する（Ｓ５４３）。第３実施形態と同じように、署名送信手段５５０は、署名（σ，ｒ）と文書ｍを署名検証装置２００’へ送信する（Ｓ５５０）。なお、署名として署名（σ，ｇ２ｒ，ｓ）を用いても良い。
【００２５】
このように署名生成過程のべき乗計算を分子と分母に分けることで、他のタイプの署名（ブラインド署名やグループ署名など）に本発明を利用することができる。
なお、上記の各実施形態はコンピュータに、上記方法の各ステップを実行させるプログラムを読み込ませ、実施することもできる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【００２６】
【図１】従来の署名方式での署名生成処理フローを示す図。
【図２】従来の署名方式での署名検証処理フローを示す図。
【図３】第１実施形態のデジタル署名方式のシステム構成例を示す図。
【図４】署名生成装置１００の処理フローを示す図。
【図５】署名検証装置２００の処理フローを示す図。
【図６】署名生成装置１００’の処理フローを示す図。
【図７】署名生成装置１００”の処理フローを示す図。
【図８】第２実施形態のデジタル署名方式のシステム構成例を示す図。
【図９】署名生成装置３００の処理フローを示す図。
【図１０】署名生成装置３００’の処理フローを示す図。
【図１１】第３実施形態のデジタル署名方式のシステム構成例を示す図。
【図１２】署名生成装置５００の処理フローを示す図。
【図１３】署名検証装置２００’の処理フローを示す図。
【図１４】署名生成装置５００’の処理フローを示す図。
【図１】
0004634899.tif 000002
【図２】
0004634899.tif 000003
【図３】
0004634899.tif 000004
【図４】
0004634899.tif 000005
【図５】
0004634899.tif 000006
【図６】
0004634899.tif 000007
【図７】
0004634899.tif 000008
【図８】
0004634899.tif 000009
【図９】
0004634899.tif 000010
【図１０】
0004634899.tif 000011
【図１１】
0004634899.tif 000012
【図１２】
0004634899.tif 000013
【図１３】
0004634899.tif 000014
【図１４】
0004634899.tif 000015