(57)【要約】【課題】  匿名性が要求される場合であっても、公平な署名交換を実現する。【解決手段】  署名生成装置ＳgＡが、第２検証式（ｈ1’＋ｈ2’＝…）のうち、第１公開鍵ｐAに関する第１署名者関連値ｐA{h’_2}を第１マスク値ｒ’に基づいて変形し、第１変形値Ｙ’を得ると、第２検証式の第１署名者関連値を第１変形値Ｙ’で置換した場合に当該第２検証式を成立させるように、第１マスク値ｒ’に基づいて第２仮署名値σBを修正し、第２署名値σB’を得る。これにより、第２検証式の第１署名者関連値を第１変形値Ｙ’で置換してなる第２署名検証式を有する署名検証装置に対し、第１署名者関連値に代えて第１変形値Ｙ’を渡すことにより、第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ，Ｙ’）が検証可能となる。このように、公平な署名交換方法において、第１署名者関連値に代えて第１変形値Ｙ’により署名を検証可能としたので、上記課題を解決できる。【選択図】      図３
2006217506.tif 000002
【特許請求の範囲】
【請求項１】
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置が第１署名対象文書ＭAを決定すると共に、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置が第２署名対象文書ＭBを決定し、
前記第１署名生成装置が生成した秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成し、この第１コミット情報ｈ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び前記第１秘密鍵ｓAに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第１仮署名値σAを生成し、得られた第１仮署名値σA、第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信し、
前記第２署名生成装置が、前記第１仮署名（σA，ｈ，ＭA）を受信した後に、第２コミット情報ｈ’＝ｈ、前記第１公開鍵ｐA、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第２仮署名値σBを生成し、得られた第２仮署名値σB、第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信し、
前記第１署名生成装置が、前記第２仮署名（σB，ｈ’，ＭB）を受信した後に、前記秘密情報ｋを第２署名生成装置に送信することにより、
前記第１及び第２署名生成装置がデジタル署名を交換する署名交換方法であって、
前記第１署名生成装置は、
前記秘密情報ｋを送信した後、第１マスク値ｒ’を生成又は選択する工程と、
前記第１マスク値ｒ’に基づいて前記第２仮署名値σBを修正し、前記第１公開鍵ｐAを用いずに前記第２公開鍵ｐBから正当性を検証可能な第２署名値σB’を得る工程と、
前記第２署名値σB’、前記第２コミット情報ｈ’、前記第２署名対象文書ＭB及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する工程とを備えており、
前記第２署名生成装置は、
前記秘密情報ｋを受信した後、第２マスク値ｒを生成又は選択する工程と、
前記第２マスク値ｒに基づいて前記第１仮署名値σAを修正し、前記第２公開鍵ｐBを用いずに前記第１公開鍵ｐAから正当性を検証可能な第１署名値σA’を得る工程と、
前記第１署名値σA’、前記第１コミット情報ｈ、前記第１署名対象文書ＭA及び前記秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する工程と
を備えたことを特徴とする署名交換方法。
【請求項２】
請求項１に記載の署名交換方法において、
前記第２署名値σB’を得る工程は、前記第１マスク値ｒ’としての第１乱数と、前記第１秘密鍵ｓAとに基づいて前記第２仮署名値σBを修正し、
前記第１署名値σA’を得る工程は、前記第２マスク値ｒとしての第２乱数と、前記第２秘密鍵ｓBとに基づいて第１署名値σA’を修正することを特徴とする署名交換方法。
【請求項３】
請求項１に記載の署名交換方法において、
前記第２署名値σB’を得る工程は、前記第１マスク値ｒ’としての第１固定値と、前記第１秘密鍵ｓAとに基づいて前記第２仮署名値σBを修正し、
前記第１署名値σA’を得る工程は、前記第２マスク値ｒとしての第２固定値と、前記第２秘密鍵ｓBとに基づいて第１署名値σA’を修正することを特徴とする署名交換方法。
【請求項４】
システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A} ｍｏｄ  ｐとを有する第１署名生成装置が第１署名対象文書ＭAを決定すると共に、前記システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B} ｍｏｄ  ｐとを有する第２署名生成装置が第２署名対象文書ＭBを決定し、
前記第１署名生成装置が生成した秘密情報ｋに第１ランダム関数Ｇを施して第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を生成し、この第２部分ｈ2、前記システムパラメータｇ、生成した乱数ｔ、前記第１署名対象文書ＭA及び前記第２公開鍵ｐBに第２ランダム関数Ｈを施して得られた値ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）と前記第２部分ｈ2とに基づいて第１コミット情報の第１部分ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑを得ると、この第１部分ｈ1、前記第２部分ｈ2、前記第１秘密鍵ｓA及び前記乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを生成し、得られた第１仮署名値σA、第１コミット情報ｈ1,ｈ2及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第２署名生成装置に送信し、
前記第２署名生成装置が、前記第１仮署名（σA，ｈ1，ｈ2，ＭA）と前記第１及び第２公開鍵ｐA,ｐBとを第１検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1 h_2}ｐB{h_2}，ＭA））に代入して第１仮署名を検証し、前記第１コミット情報の第２部分ｈ2を設定した第２コミット情報の第２部分ｈ2’＝ｈ2、前記システムパラメータｇ、生成した乱数ｔ’、前記第１公開鍵ｐA及び前記第２署名対象文書ＭBに第２ランダム関数Ｈを施して得られた値ｈ’＝Ｈ（ｇｔ’ｐA{h’_2}，ＭB）と前記第２部分ｈ2’とに基づいて第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑを得ると、この第１部分ｈ1’、前記第２部分ｈ2’、前記第２秘密鍵ｓB及び前記乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑを生成し、得られた第２仮署名値σB、第２コミット情報ｈ1’,ｈ2’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第１署名生成装置に送信し、
前記第１署名生成装置が、前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）と前記第１及び第２公開鍵ｐA,ｐBとを第２検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐA{h’_2}ｐB{h’_1 h’_2}，ＭB））に代入して第２仮署名を検証し、前記秘密情報ｋを第２署名生成装置に送信することにより、
前記第１及び第２署名生成装置がデジタル署名を交換する署名交換方法であって、
前記第１署名生成装置は、
前記秘密情報ｋを送信した後、第１マスク値ｒ’を生成又は選択する工程と、
前記第２検証式のうち、前記第１公開鍵ｐAに関する第１署名者関連値ｐA{h’_2}を前記第１マスク値ｒ’に基づいて変形し、第１変形値Ｙ’＝ｐA{h’_2+r’} ｍｏｄ  ｐを得る工程と、
前記第２検証式の第１署名者関連値を前記第１変形値Ｙ’で置換した場合に当該第２検証式を成立させるように、前記第１マスク値ｒ’及び前記第１秘密鍵ｓAに基づいて前記第２仮署名値σBを修正し、第２署名値σB’＝σB−ｒ’ｓA ｍｏｄ  ｑを得る工程と、
前記第２検証式の第１署名者関連値を第１変形値Ｙ’で置換してなる第２署名検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ’_B} Ｙ’ｐB{h’_1 h’_2}，ＭB））、及び前記秘密情報ｋの検証式（ｈ2’＝Ｇ（ｋ））を有する署名検証装置に向けて送信するための、前記第２署名値σB’、前記第２コミット情報ｈ1’,ｈ2’、前記第２署名対象文書ＭB、前記秘密情報ｋ及び前記第１変形値Ｙ’を含む第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ，Ｙ’）を出力する工程とを備えており、
前記第２署名生成装置は、
前記秘密情報ｋを受信した後、第２マスク値ｒを生成又は選択する工程と、
前記第１検証式のうち、前記第２公開鍵ｐBに関する第２署名者関連値ｐB{h_2}を前記第２マスク値ｒに基づいて変形し、第２変形値Ｙ＝ｐB{h_2+r} ｍｏｄ  ｐを得る工程と、
前記第１検証式の第２署名者関連値を前記第２変形値Ｙで置換した場合に当該第１検証式を成立させるように、前記第２マスク値ｒ及び前記第２秘密鍵ｓBに基づいて前記第１仮署名値σAを修正し、第１署名値σA’＝σA−ｒｓB ｍｏｄ  ｑを得る工程と、
前記第１検証式の第２署名者関連値を第２変形値Ｙで置換してなる第１署名検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A}ｐA{h_1 h_2} Ｙ，ＭA））、及び前記秘密情報ｋの検証式（ｈ2＝Ｇ（ｋ））を有する署名検証装置に向けて送信するための、前記第１署名値σA’、前記第１コミット情報ｈ1,ｈ2、前記第１署名対象文書ＭA、前記秘密情報ｋ及び前記第２変形値Ｙを含む第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ，Ｙ）を出力する工程と
を備えたことを特徴とする署名交換方法。
【請求項５】
請求項４に記載の署名交換方法において、
前記第１マスク値ｒ’は第１乱数であり、前記第２マスク値ｒは第２乱数であることを特徴とする署名交換方法。
【請求項６】
請求項４に記載の署名交換方法において、
前記第１マスク値ｒ’は第１固定値であり、前記第２マスク値ｒは第２固定値であることを特徴とする署名交換方法。
【請求項７】
請求項１又は請求項４に記載の署名交換方法において、
前記第１マスク値ｒ’は第１乱数又は複数の第１固定値のいずれかの値であり、
前記第２マスク値ｒは第２乱数又は複数の第２固定値のいずれかの値であり、
前記第１マスク値ｒ’を生成又は選択する工程は、
予め設定された前記第１乱数の使用確率と前記各第１固定値毎の使用確率とに基づいて、前記第１乱数又は各第１固定値のいずれを使用するかを決定する工程と、
この決定結果に基づいて前記第１マスク値ｒ’を得る工程とを備えており、
前記第２マスク値ｒを生成又は選択する工程は、
予め設定された前記第２乱数の使用確率と前記各第２固定値毎の使用確率とに基づいて、前記第２乱数又は各第２固定値のいずれを使用するかを決定する工程と、
この決定結果に基づいて前記第２マスク値ｒを得る工程と
を備えたことを特徴とする署名交換方法。
【請求項８】
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置と、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置とがデジタル署名を交換する署名交換方法であって、
前記第１署名生成装置が第１署名対象文書ＭAを決定すると共に、前記第２署名生成装置が第２署名対象文書ＭBを決定する工程と、
前記第１署名生成装置が秘密情報ｋを生成する工程と、
前記第１署名生成装置が前記秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成する工程と、
前記第１署名生成装置が、前記第１署名対象文書ＭA、前記第１コミット情報ｈ及び前記第１秘密鍵ｓAに基づいて、前記第１公開鍵ｐAから正当性を検証可能な第１仮署名値σAを生成する工程と、
前記第１署名生成装置が前記第１仮署名値σA、前記第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信する工程と、
前記第２署名生成装置が、前記第１仮署名（σA，ｈ，ＭA）を受信した後に、第２コミット情報ｈ’＝ｈ、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、前記第２公開鍵ｐBから正当性を検証可能な第２仮署名値σBを生成する工程と、
前記第２署名生成装置が、前記第２仮署名値σB、前記第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信する工程と、
前記第１署名生成装置が、前記第２仮署名（σB，ｈ’，ＭB）を受信した後に、前記秘密情報ｋを第２署名生成装置に送信する工程と、
前記第１署名生成装置が、前記第２仮署名（σB，ｈ’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する工程と、
前記第２署名生成装置が、前記秘密情報ｋを受けると、前記第１仮署名（σA，ｈ，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する工程と
を備えたことを特徴とする署名交換方法。
【請求項９】
システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A} ｍｏｄ  ｐとを有する第１署名生成装置と、前記システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B} ｍｏｄ  ｐとを有する第２署名生成装置とがデジタル署名を交換する署名交換方法であって、
前記第１署名生成装置が第１署名対象文書ＭAを決定すると共に、前記第２署名生成装置が第２署名対象文書ＭBを決定する工程と、
前記第１署名生成装置が秘密情報ｋを生成する工程と、
前記第１署名生成装置が前記秘密情報ｋに第１ランダム関数Ｇを施して第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を生成する工程と、
前記第１署名生成装置が乱数ｔを生成する工程と、
前記第１署名生成装置が、前記システムパラメータｇ、前記乱数ｔ及び前記第１署名対象文書ＭAに第２ランダム関数Ｈを施して第１コミット合計値ｈ＝Ｈ（ｇｔ，ＭA）を得る工程と、
前記第１署名生成装置が前記第１コミット合計値ｈと前記第２部分ｈ2とに基づいて第１コミット情報の第１部分ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑを得る工程と、
前記第１署名生成装置が前記第１部分ｈ1、前記第２部分ｈ2、前記第１秘密鍵ｓA及び前記乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを生成する工程と、
前記第１署名生成装置が前記第１仮署名値σA、前記第１コミット情報ｈ1,ｈ2及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第２署名生成装置に送信する工程と、
前記第２署名生成装置が、前記第１仮署名（σA，ｈ1，ｈ2，ＭA）及び前記第１公開鍵ｐAを第１検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1 h_2}，ＭA））に代入して第１仮署名を検証する工程と、
前記第１仮署名の検証結果が正当なとき、前記第２署名生成装置が、前記第１コミット情報の第２部分ｈ2を第２コミット情報の第２部分ｈ2’＝ｈ2と設定すると共に、乱数ｔ’を生成する工程と、
前記第２署名生成装置が、前記システムパラメータｇ、前記乱数ｔ’及び前記第２署名対象文書ＭBに第２ランダム関数Ｈを施して第２コミット合計値ｈ’＝Ｈ（ｇｔ’，ＭB）を得る工程と、
前記第２署名生成装置が前記第２コミット合計値ｈ’と前記第２部分ｈ2’とに基づいて第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑを得る工程と、
前記第２署名生成装置が、前記第１部分ｈ1’、前記第２部分ｈ2’、前記第２秘密鍵ｓB及び前記乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑを生成する工程と、
前記第２署名生成装置が、前記第２仮署名値σB、前記第２コミット情報ｈ1’,ｈ2’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第１署名生成装置に送信する工程と、
前記第１署名生成装置が、前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）及び前記第２公開鍵ｐBを第２検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐB{h’_1 h’_2}，ＭB））に代入して第２仮署名を検証する工程と、
前記第２仮署名の検証結果が正当なとき、前記第１署名生成装置が、前記秘密情報ｋを第２署名生成装置に送信する工程と、
前記第１署名生成装置が、前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ）を出力する工程と、
前記第２署名生成装置が、前記秘密情報ｋを受信した後に、前記第１仮署名（σA，ｈ1，ｈ2，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ）を出力する工程と
を備えたことを特徴とする署名交換方法。
【請求項１０】
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAをメモリに保持し、第１署名対象文書ＭAを決定すると共に、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置により第２署名対象文書ＭBが決定されると、
秘密情報ｋを生成し、この秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成し、この第１コミット情報ｈ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び前記第１秘密鍵ｓAに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第１仮署名値σAを生成し、得られた第１仮署名値σA、第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信し、
前記第１コミット情報ｈ、前記第１公開鍵ｐA及び第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ’，ＭB）を前記第２署名生成装置から受信すると（但し、ｈ’＝ｈである。σBは前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な値である）、前記秘密情報ｋを第２署名生成装置に送信することにより、
前記第２署名生成装置との間でデジタル署名を交換する第１署名生成装置であって、
前記秘密情報ｋを送信した後、第１マスク値ｒ’を生成又は選択する手段と、
前記第１マスク値ｒ’に基づいて前記第２仮署名値σBを修正し、前記第１公開鍵ｐAを用いずに第２公開鍵ｐBから正当性を検証可能な第２署名値σB’を得る手段と、
前記第２署名値σB’、前記第２コミット情報ｈ’、前記第２署名対象文書ＭB及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する手段と
を備えたことを特徴とする第１署名生成装置。
【請求項１１】
互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBをメモリに保持し、第２署名対象文書ＭBを決定すると共に、互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置により第１署名対象文書ＭAが決定された後、
秘密情報ｋ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び第１秘密鍵ｓAを基に各々生成された第１仮署名値σA及び第１コミット情報ｈと前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ，ＭA）を前記第１署名生成装置から受信すると（但し、σAは前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な値である）、
第２コミット情報ｈ’＝ｈ、前記第１公開鍵ｐA、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第２仮署名値σBを生成し、得られた第２仮署名値σB、第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信し、
前記秘密情報ｋを第１署名生成装置から受信することにより、
前記第１署名生成装置との間でデジタル署名を交換する第２署名生成装置であって、
前記秘密情報ｋを受信した後、第２マスク値ｒを生成又は選択する手段と、
前記第２マスク値ｒに基づいて前記第１仮署名値σAを修正し、前記第２公開鍵ｐBを用いずに第１公開鍵ｐAから正当性を検証可能な第１署名値σA’を得る手段と、
前記第１署名値σA’、前記第１コミット情報ｈ、前記第１署名対象文書ＭA及び前記秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する手段と
を備えたことを特徴とする第２署名生成装置。
【請求項１２】
システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A}ｍｏｄ  ｐとをメモリに保持し、第１署名対象文書ＭAを決定すると共に、前記システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B}ｍｏｄ  ｐとを有する第２署名生成装置により第２署名対象文書ＭBが決定されると、
秘密情報ｋを生成し、この秘密情報ｋに第１ランダム関数Ｇを施して第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を生成し、この第２部分ｈ2、前記システムパラメータｇ、生成した乱数ｔ、前記第１署名対象文書ＭA及び前記第２公開鍵ｐBに第２ランダム関数Ｈを施して得られた値ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）と前記第２部分ｈ2とに基づいて第１コミット情報の第１部分ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑを得ると、この第１部分ｈ1、前記第２部分ｈ2、前記第１秘密鍵ｓA及び前記乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを生成し、得られた第１仮署名値σA、第１コミット情報ｈ1,ｈ2及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第２署名生成装置に送信し、
前記第１コミット情報の第２部分ｈ2、前記第１公開鍵ｐA及び第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ1’,ｈ2’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第２署名生成装置から受信すると（但し、ｈ2’＝ｈ2、σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑ、ｔ’は乱数、ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑ、ｈ’＝Ｈ（ｇｔ’ｐA{h’_2}，ＭB））、
前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）と前記第１及び第２公開鍵ｐA,ｐBとを第２検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐA{h’_2}ｐB{h’_1 h’_2}，ＭB））に代入して第２仮署名を検証し、前記秘密情報ｋを第２署名生成装置に送信することにより、
前記第２署名生成装置との間でデジタル署名を交換する第１署名生成装置であって、
前記秘密情報ｋを送信した後、第１マスク値ｒ’を生成又は選択する手段と、
前記第２検証式のうち、前記第１公開鍵ｐAに関する第１署名者関連値ｐA{h’_2}を前記第１マスク値ｒ’に基づいて変形し、第１変形値Ｙ’＝ｐA{h’_2+r’} ｍｏｄ  ｐを得る手段と、
前記第２検証式の第１署名者関連値を前記第１変形値Ｙ’で置換した場合に当該第２検証式を成立させるように、前記第１マスク値ｒ’及び前記第１秘密鍵ｓAに基づいて前記第２仮署名値σBを修正し、第２署名値σB’＝σB−ｒ’ｓA ｍｏｄ  ｑを得る手段と、
前記第２検証式の第１署名者関連値を第１変形値Ｙ’で置換してなる第２署名検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ’_B} Ｙ’ｐB{h’_1 h’_2}，ＭB））、及び前記秘密情報ｋの検証式（ｈ2’＝Ｇ（ｋ））を有する署名検証装置に向けて送信するための、前記第２署名値σB’、前記第２コミット情報ｈ1’,ｈ2’、前記第２署名対象文書ＭB、前記秘密情報ｋ及び前記第１変形値Ｙ’を含む第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ，Ｙ’）を出力する手段と
を備えたことを特徴とする第１署名生成装置。
【請求項１３】
システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B}ｍｏｄ  ｐとをメモリに保持し、第２署名対象文書ＭBを決定すると共に、前記システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A}ｍｏｄ  ｐとを有する第１署名生成装置により第１署名対象文書ＭAが決定された後、
秘密情報ｋ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び第１秘密鍵ｓAを基に各々生成された第１仮署名値σA及び第１コミット情報ｈ1,ｈ2と前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第１署名生成装置から受信すると（但し、ｈ2＝Ｇ（ｋ）、Ｇは第１ランダム関数、σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑ、ｔは乱数、ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑ、ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）、Ｈは第２ランダム関数）、
前記第１仮署名（σA，ｈ1，ｈ2，ＭA）と前記第１及び第２公開鍵ｐA,ｐBとを第１検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1 h_2}ｐB{h_2}，ＭA））に代入して第１仮署名を検証し、前記第１コミット情報の第２部分ｈ2を設定した第２コミット情報の第２部分ｈ2’＝ｈ2、前記システムパラメータｇ、生成した乱数ｔ’、前記第１公開鍵ｐA及び前記第２署名対象文書ＭBに第２ランダム関数Ｈを施して得られた値ｈ’＝Ｈ（ｇｔ’ｐA{h’_2}，ＭB）と前記第２部分ｈ2’とに基づいて第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑを得ると、この第１部分ｈ1’、前記第２部分ｈ2’、前記第２秘密鍵ｓB及び前記乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑを生成し、得られた第２仮署名値σB、第２コミット情報ｈ1’,ｈ2’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第１署名生成装置に送信し、
前記秘密情報ｋを第１署名生成装置から受信することにより、
前記第１署名生成装置との間でデジタル署名を交換する第２署名生成装置であって、
前記秘密情報ｋを受信した後、第２マスク値ｒを生成又は選択する手段と、
前記第１検証式のうち、前記第２公開鍵ｐBに関する第２署名者関連値ｐB{h_2}を前記第２マスク値ｒに基づいて変形し、第２変形値Ｙ＝ｐB{h_2+r} ｍｏｄ  ｐを得る手段と、
前記第１検証式の第２署名者関連値を前記第２変形値Ｙで置換した場合に当該第１検証式を成立させるように、前記第２マスク値ｒ及び前記第２秘密鍵ｓBに基づいて前記第１仮署名値σAを修正し、第１署名値σA’＝σA−ｒｓB ｍｏｄ  ｑを得る手段と、
前記第１検証式の第２署名者関連値を第２変形値Ｙで置換してなる第１署名検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A}ｐA{h_1 h_2} Ｙ，ＭA））、及び前記秘密情報ｋの検証式（ｈ2＝Ｇ（ｋ））を有する署名検証装置に向けて送信するための、前記第１署名値σA’、前記第２変形値Ｙ、前記第１コミット情報ｈ1,ｈ2、前記第１署名対象文書ＭA及び前記秘密情報ｋを含む第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ，Ｙ）を出力する手段と
を備えたことを特徴とする第２署名生成装置。
【請求項１４】
互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置との間でデジタル署名を交換する第１署名生成装置であって、
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAが記憶される記憶手段と、
第１署名対象文書ＭAを決定する手段と、
秘密情報ｋを生成する手段と、
前記秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成する手段と、
前記第１署名対象文書ＭA、第１コミット情報ｈ及び前記第１秘密鍵ｓAに基づいて、第１仮署名値σAを生成する手段と、
前記第１仮署名値σA、前記第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信する手段と、
前記第２署名生成装置により前記第１コミット情報ｈ、前記第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ’，ＭB）を当該第２署名生成装置から受信する手段と（但し、ｈ’＝ｈ）、
前記第２仮署名（σB，ｈ’，ＭB）を受信した後に、前記秘密情報ｋを第２署名生成装置に送信する手段と、
前記第２仮署名（σB，ｈ’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する手段と
を備えたことを特徴とする第１署名生成装置。
【請求項１５】
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置との間でデジタル署名を交換する第２署名生成装置であって、
互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBが記憶される記憶手段と、
第２署名対象文書ＭBを決定する手段と、
秘密情報ｋ、第１署名対象文書ＭA及び第１秘密鍵ｓAを基に前記第１署名生成装置により各々生成された第１仮署名値σA及び第１コミット情報ｈと前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ，ＭA）を当該第１署名生成装置から受信する手段と、
前記第１仮署名（σA，ｈ，ＭA）を受信した後に、第２コミット情報ｈ’＝ｈ、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、第２仮署名値σBを生成する手段と、
前記第２仮署名値σB、前記第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信する手段と、
前記第１署名生成装置から前記秘密情報ｋを受信した後に、前記第１仮署名（σA，ｈ，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する手段と
を備えたことを特徴とする第２署名生成装置。
【請求項１６】
システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B} ｍｏｄ  ｐとを有する第２署名生成装置との間でデジタル署名を交換する第１署名生成装置であって、
前記システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A} ｍｏｄ  ｐとが記憶される記憶手段と、
第１署名対象文書ＭAを決定する手段と、
秘密情報ｋを生成する手段と、
前記秘密情報ｋに第１ランダム関数Ｇを施して第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を生成する手段と、
乱数ｔを生成する手段と、
前記記憶手段内のシステムパラメータｇ、前記乱数ｔ及び前記第１署名対象文書ＭAに第２ランダム関数Ｈを施して第１コミット合計値ｈ＝Ｈ（ｇｔ，ＭA）を得る手段と、
前記第１コミット合計値ｈと前記第２部分ｈ2とに基づいて第１コミット情報の第１部分ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑを得る手段と、
前記第１部分ｈ1、前記第２部分ｈ2、前記第１秘密鍵ｓA及び前記乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを生成する手段と、
前記第１仮署名値σA、前記第１コミット情報ｈ1,ｈ2及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第２署名生成装置に送信する手段と、
前記第２署名生成装置により前記第１コミット情報の第２部分ｈ2、前記第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ1’,ｈ2’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を当該第２署名生成装置から受信する手段と（但し、ｈ2’＝ｈ2、σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑ、ｔ’は乱数、ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑ、ｈ’＝Ｈ（ｇｔ’，ＭB））、
前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）及び前記第２公開鍵ｐBを第２検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐB{h’_1 h’_2}，ＭB））に代入して第２仮署名を検証する手段と、
前記第２仮署名の検証結果が正当なとき、前記秘密情報ｋを第２署名生成装置に送信する手段と、
前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ）を出力する手段と
を備えたことを特徴とする第１署名生成装置。
【請求項１７】
システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A} ｍｏｄ  ｐとを有する第１署名生成装置との間でデジタル署名を交換する第２署名生成装置であって、
前記システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B} ｍｏｄ  ｐとが記憶される記憶手段と、
第２署名対象文書ＭBを決定する手段と、
秘密情報ｋ、第１署名対象文書ＭA、前記第２公開鍵ｐB及び第１秘密鍵ｓAを基に前記第１署名生成装置により各々生成された第１仮署名値σA及び第１コミット情報ｈ1,ｈ2と前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を当該第１署名生成装置から受信する手段と（但し、ｈ2＝Ｇ（ｋ）、Ｇは第１ランダム関数、σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑ、ｔは乱数、ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑ、ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）、Ｈは第２ランダム関数）、
前記第１仮署名（σA，ｈ1，ｈ2，ＭA）及び前記第１公開鍵ｐAを第１検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1 h_2}，ＭA））に代入して第１仮署名を検証する手段と、
前記第１仮署名の検証結果が正当なとき、前記第１コミット情報の第２部分ｈ2を第２コミット情報の第２部分ｈ2’＝ｈ2と設定すると共に、乱数ｔ’を生成する手段と、
前記システムパラメータｇ、前記乱数ｔ’及び前記第２署名対象文書ＭBに第２ランダム関数Ｈを施して第２コミット合計値ｈ’＝Ｈ（ｇｔ’，ＭB）を得る手段と、
前記第２コミット合計値ｈ’と前記第２部分ｈ2’とに基づいて第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑを得る手段と、
前記第１部分ｈ1’、前記第２部分ｈ2’、前記第２秘密鍵ｓB及び前記乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑを生成する手段と、
前記第２仮署名値σB、前記第２コミット情報ｈ1’,ｈ2’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第１署名生成装置に送信する手段と、
前記第１署名生成装置から前記秘密情報ｋを受信した後に、前記第１仮署名（σA，ｈ1，ｈ2，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ）を出力する手段と
を備えたことを特徴とする第２署名生成装置。
【請求項１８】
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAをメモリに保持し、第１署名対象文書ＭAを決定すると共に、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置により第２署名対象文書ＭBが決定されると、
秘密情報ｋを生成し、この秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成し、この第１コミット情報ｈ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び前記第１秘密鍵ｓAに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第１仮署名値σAを生成し、得られた第１仮署名値σA、第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信し、
前記第１コミット情報ｈ、前記第１公開鍵ｐA及び第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ’，ＭB）を前記第２署名生成装置から受信すると（但し、ｈ’＝ｈである。σBは前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な値である）、前記秘密情報ｋを第２署名生成装置に送信することにより、
前記第２署名生成装置との間でデジタル署名を交換する第１署名生成装置に用いられるプログラムであって、
前記第１署名生成装置のコンピュータを、
前記秘密情報ｋを送信した後、第１乱数を生成する乱数生成器又は複数の第１固定値を保持する固定値メモリを用い、前記第１乱数又は第１固定値のいずれかの値としての第１マスク値ｒ’を得る手段、
前記第１マスク値ｒ’に基づいて前記第２仮署名値σBを修正し、前記第１公開鍵ｐAを用いずに第２公開鍵ｐBから正当性を検証可能な第２署名値σB’を得る手段、
前記第２署名値σB’、前記第２コミット情報ｈ’、前記第２署名対象文書ＭB及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する手段、
として機能させるためのプログラム。
【請求項１９】
互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBをメモリに保持し、第２署名対象文書ＭBを決定すると共に、対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置により第１署名対象文書ＭAが決定された後、
秘密情報ｋ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び第１秘密鍵ｓAを基に各々生成された第１仮署名値σA及び第１コミット情報ｈと前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第１署名生成装置から受信すると（但し、σAは前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な値である）、
第２コミット情報ｈ’＝ｈ、前記第１公開鍵ｐA、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第２仮署名値σBを生成し、得られた第２仮署名値σB、第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信し、
前記秘密情報ｋを第１署名生成装置から受信することにより、
前記第１署名生成装置との間でデジタル署名を交換する第２署名生成装置に用いられるプログラムであって、
前記第２署名生成装置のコンピュータを、
前記秘密情報ｋを受信した後、第２乱数を生成する乱数生成器又は複数の第２固定値を保持する固定値メモリを用い、前記第２乱数又は第２固定値のいずれかの値としての第２マスク値ｒを得る手段、
前記第２マスク値ｒに基づいて前記第１仮署名値σAを修正し、前記第２公開鍵ｐBを用いずに第１公開鍵ｐAから正当性を検証可能な第１署名値σA’を得る手段、
前記第１署名値σA’、前記第１コミット情報ｈ、前記第１署名対象文書ＭA及び前記秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する手段、
として機能させるためのプログラム。
【請求項２０】
システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A}ｍｏｄ  ｐとをメモリに保持し、第１署名対象文書ＭAを決定すると共に、前記システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B}ｍｏｄ  ｐとを有する第２署名生成装置により第２署名対象文書ＭBが決定されると、
秘密情報ｋを生成し、この秘密情報ｋに第１ランダム関数Ｇを施して第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を生成し、この第２部分ｈ2、前記システムパラメータｇ、生成した乱数ｔ、前記第１署名対象文書ＭA及び前記第２公開鍵ｐBに第２ランダム関数Ｈを施して得られた値ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）と前記第２部分ｈ2とに基づいて第１コミット情報の第１部分ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑを得ると、この第１部分ｈ1、前記第２部分ｈ2、前記第１秘密鍵ｓA及び前記乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを生成し、得られた第１仮署名値σA、第１コミット情報ｈ1,ｈ2及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第２署名生成装置に送信し、
前記第１コミット情報の第２部分ｈ2、前記第１公開鍵ｐA及び第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ1’,ｈ2’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第２署名生成装置から受信すると（但し、ｈ2’＝ｈ2、σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑ、ｔ’は乱数、ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑ、ｈ’＝Ｈ（ｇｔ’ｐA{h’_2}，ＭB））、
前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）と前記第１及び第２公開鍵ｐA,ｐBとを第２検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐA{h’_2}ｐB{h’_1 h’_2}，ＭB））に代入して第２仮署名を検証し、前記秘密情報ｋを第２署名生成装置に送信することにより、
前記第２署名生成装置との間でデジタル署名を交換する第１署名生成装置に用いられるプログラムであって、
前記第１署名生成装置のコンピュータを、
前記秘密情報ｋを送信した後、第１乱数を生成する乱数生成器又は複数の第１固定値を保持する固定値メモリを用い、前記第１乱数又は第１固定値のいずれかの値としての第１マスク値ｒ’を得る手段、
前記第２検証式のうち、前記第１公開鍵ｐAに関する第１署名者関連値ｐA{h’_2}を前記第１マスク値ｒ’に基づいて変形し、第１変形値Ｙ’＝ｐA{h’_2+r’} ｍｏｄ  ｐを得る手段、
前記第２検証式の第１署名者関連値を前記第１変形値Ｙ’で置換した場合に当該第２検証式を成立させるように、前記第１マスク値ｒ’及び第１秘密鍵ｓAに基づいて前記第２仮署名値σBを修正し、第２署名値σB’＝σB−ｒ’ｓA ｍｏｄ  ｑを得る手段、
前記第２検証式の第１署名者関連値を第１変形値Ｙ’で置換してなる第２署名検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ’_B} Ｙ’ｐB{h’_1 h’_2}，ＭB））、及び前記秘密情報ｋの検証式（ｈ2’＝Ｇ（ｋ））を有する署名検証装置に向けて送信するための、前記第２署名値σB’、前記第１変形値Ｙ’、前記第２コミット情報ｈ1’,ｈ2’、前記第２署名対象文書ＭB及び前記秘密情報ｋを含む第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ，Ｙ’）を出力する手段、
として機能させるためのプログラム。
【請求項２１】
システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B}ｍｏｄ  ｐとをメモリに保持し、第２署名対象文書ＭBを決定すると共に、前記システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A}ｍｏｄ  ｐとを有する第１署名生成装置により第１署名対象文書ＭAが決定された後、
秘密情報ｋ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び第１秘密鍵ｓAを基に各々生成された第１仮署名値σA及び第１コミット情報ｈ1,ｈ2と前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第１署名生成装置から受信すると（但し、ｈ2＝Ｇ（ｋ）、Ｇは第１ランダム関数、σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑ、ｔは乱数、ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑ、ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）、Ｈは第２ランダム関数）、
前記第１仮署名（σA，ｈ1，ｈ2，ＭA）と前記第１及び第２公開鍵ｐA,ｐBとを第１検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1 h_2}ｐB{h_2}，ＭA））に代入して第１仮署名を検証し、前記第１コミット情報の第２部分ｈ2を設定した第２コミット情報の第２部分ｈ2’＝ｈ2、前記システムパラメータｇ、生成した乱数ｔ’、前記第１公開鍵ｐA及び前記第２署名対象文書ＭBに第２ランダム関数Ｈを施して得られた値ｈ’＝Ｈ（ｇｔ’ｐA{h’_2}，ＭB）と前記第２部分ｈ2’とに基づいて第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑを得ると、この第１部分ｈ1’、前記第２部分ｈ2’、前記第２秘密鍵ｓB及び前記乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑを生成し、得られた第２仮署名値σB、第２コミット情報ｈ1’,ｈ2’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第１署名生成装置に送信し、
前記秘密情報ｋを第１署名生成装置から受信することにより、
前記第１署名生成装置との間でデジタル署名を交換する第２署名生成装置に用いられるプログラムであって、
前記第２署名生成装置のコンピュータを、
前記秘密情報ｋを受信した後、第２乱数を生成する乱数生成器又は複数の第２固定値を保持する固定値メモリを用い、前記第２乱数又は第２固定値のいずれかの値としての第２マスク値ｒを得る手段、
前記第１検証式のうち、前記第２公開鍵ｐBに関する第２署名者関連値ｐB{h_2}を前記第２マスク値ｒに基づいて変形し、第２変形値Ｙ＝ｐB{h_2+r} ｍｏｄ  ｐを得る手段、
前記第１検証式の第２署名者関連値を前記第２変形値Ｙで置換した場合に当該第１検証式を成立させるように、前記第２マスク値ｒ及び前記第２秘密鍵ｓBに基づいて前記第１仮署名値σAを修正し、第１署名値σA’＝σA−ｒｓB ｍｏｄ  ｑを得る手段、
前記第１検証式の第２署名者関連値を第２変形値Ｙで置換してなる第１署名検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A}ｐA{h_1 h_2} Ｙ，ＭA））、及び前記秘密情報ｋの検証式（ｈ2＝Ｇ（ｋ））を有する署名検証装置に向けて送信するための、前記第１署名値σA’、前記第２変形値Ｙ、前記第１コミット情報ｈ1,ｈ2、前記第１署名対象文書ＭA及び前記秘密情報ｋを含む第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ，Ｙ）を出力する手段、
として機能させるためのプログラム。
【請求項２２】
互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAがメモリに記憶されており、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置との間でデジタル署名を交換する第１署名生成装置に用いられるプログラムであって、
前記第１署名生成装置のコンピュータを、
第１署名対象文書ＭAを決定する手段、
秘密情報ｋを生成して前記メモリに書き込む手段、
前記メモリ内の秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成する手段、
前記第１署名対象文書ＭA、第１コミット情報ｈ及び前記第１秘密鍵ｓAに基づいて、第１仮署名値σAを生成する手段、
前記第１仮署名値σA、前記第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信する手段、
前記第２署名生成装置により前記第１コミット情報ｈ、前記第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ’，ＭB）を当該第２署名生成装置から受信する手段（但し、ｈ’＝ｈ）、
前記第２仮署名（σB，ｈ’，ＭB）を受信した後に、前記秘密情報ｋを第２署名生成装置に送信する手段、
前記第２仮署名（σB，ｈ’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する手段、
として機能させるためのプログラム。
【請求項２３】
互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBがメモリに記憶されており、互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置との間でデジタル署名を交換する第２署名生成装置に用いられるプログラムであって、
前記第２署名生成装置のコンピュータを、
第２署名対象文書ＭBを決定する手段、
秘密情報ｋ、第１署名対象文書ＭA及び第１秘密鍵ｓAを基に前記第１署名生成装置により各々生成された第１仮署名値σA及び第１コミット情報ｈと前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ，ＭA）を当該第１署名生成装置から受信する手段、
前記第１仮署名（σA，ｈ，ＭA）を受信した後に、第２コミット情報ｈ’＝ｈ、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、第２仮署名値σBを生成する手段、
前記第２仮署名値σB、前記第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信する手段、
前記第１署名生成装置から前記秘密情報ｋを受信した後に、前記第１仮署名（σA，ｈ，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する手段、
として機能させるためのプログラム。
【請求項２４】
システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A} ｍｏｄ  ｐとがメモリに記憶されており、前記システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B} ｍｏｄ  ｐとを有する第２署名生成装置との間でデジタル署名を交換する第１署名生成装置に用いられるプログラムであって、
前記第１署名生成装置のコンピュータを、
第１署名対象文書ＭAを決定する手段、
秘密情報ｋを生成する手段、
前記秘密情報ｋに第１ランダム関数Ｇを施して第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を生成する手段、
乱数ｔを生成する手段、
前記メモリ内のシステムパラメータｇ、前記乱数ｔ及び前記第１署名対象文書ＭAに第２ランダム関数Ｈを施して第１コミット合計値ｈ＝Ｈ（ｇｔ，ＭA）を得る手段、
前記第１コミット合計値ｈと前記第２部分ｈ2とに基づいて第１コミット情報の第１部分ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑを得る手段、
前記第１部分ｈ1、前記第２部分ｈ2、前記第１秘密鍵ｓA及び前記乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを生成する手段、
前記第１仮署名値σA、前記第１コミット情報ｈ1,ｈ2及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を前記第２署名生成装置に送信する手段、
前記第２署名生成装置により前記第１コミット情報の第２部分ｈ2、前記第２秘密鍵ｓBを基に各々生成された第２仮署名値σB及び第２コミット情報ｈ1’,ｈ2’と前記第２署名対象文書ＭBとを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を当該第２署名生成装置から受信する手段（但し、ｈ2’＝ｈ2、σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑ、ｔ’は乱数、ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑ、ｈ’＝Ｈ（ｇｔ’，ＭB））、
前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）及び前記第２公開鍵ｐBを第２検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐB{h’_1 h’_2}，ＭB））に代入して第２仮署名を検証する手段、
前記第２仮署名の検証結果が正当なとき、前記秘密情報ｋを第２署名生成装置に送信する手段、
前記第２仮署名（σB，ｈ1’，ｈ2’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ）を出力する手段、
として機能させるためのプログラム。
【請求項２５】
システムパラメータｇ及び素数ｐ，ｑと第２秘密鍵ｓB及び第２公開鍵ｐB＝ｇ{ｓ_B} ｍｏｄ  ｐとがメモリに記憶されており、前記システムパラメータｇ及び素数ｐ，ｑと第１秘密鍵ｓA及び第１公開鍵ｐA＝ｇ{ｓ_A} ｍｏｄ  ｐとを有する第１署名生成装置との間でデジタル署名を交換する第２署名生成装置に用いられるプログラムであって、
前記第２署名生成装置のコンピュータを、
第２署名対象文書ＭBを決定する手段、
秘密情報ｋ、第１署名対象文書ＭA、前記第２公開鍵ｐB及び第１秘密鍵ｓAを基に前記第１署名生成装置により各々生成された第１仮署名値σA及び第１コミット情報ｈ1,ｈ2と前記第１署名対象文書ＭAとを含む第１仮署名（σA，ｈ1，ｈ2，ＭA）を当該第１署名生成装置から受信する手段（但し、ｈ2＝Ｇ（ｋ）、Ｇは第１ランダム関数、σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑ、ｔは乱数、ｈ1＝ｈ−ｈ2 ｍｏｄ  ｑ、ｈ＝Ｈ（ｇｔｐB{h_2}，ＭA）、Ｈは第２ランダム関数）、
前記第１仮署名（σA，ｈ1，ｈ2，ＭA）及び前記第１公開鍵ｐAを第１検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1 h_2}，ＭA））に代入して第１仮署名を検証する手段、
前記第１仮署名の検証結果が正当なとき、前記第１コミット情報の第２部分ｈ2を第２コミット情報の第２部分ｈ2’＝ｈ2と設定すると共に、乱数ｔ’を生成する手段、
前記システムパラメータｇ、前記乱数ｔ’及び前記第２署名対象文書ＭBに第２ランダム関数Ｈを施して第２コミット合計値ｈ’＝Ｈ（ｇｔ’，ＭB）を得る手段、
前記第２コミット合計値ｈ’と前記第２部分ｈ2’とに基づいて第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’ ｍｏｄ  ｑを得る手段、
前記第１部分ｈ1’、前記第２部分ｈ2’、前記第２秘密鍵ｓB及び前記乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB ｍｏｄ  ｑを生成する手段、
前記第２仮署名値σB、前記第２コミット情報ｈ1’,ｈ2’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ1’，ｈ2’，ＭB）を前記第１署名生成装置に送信する手段、
前記第１署名生成装置から前記秘密情報ｋを受信した後に、前記第１仮署名（σA，ｈ1，ｈ2，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ）を出力する手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１及び第２署名生成装置のそれぞれが生成した署名を公平に交換するための署名交換方法、装置及びプログラムに係り、特に、匿名性が要求される場合であっても、公平な署名交換を実現し得る署名交換方法、装置及びプログラムに関する。
【背景技術】
【０００２】
情報化社会の発展に伴い、デジタル署名を添付したデジタルデータをネットワークを通じて取引きする電子取引が有用視されている。しかしながら、電子取引は、契約書などのデータや署名を二者間で同時に交換することが困難である。これに伴い、例えば署名者Ａ，Ｂの間で署名者Ｂが署名者Ａのデジタルデータを先に入手した場合、署名者Ｂにより、交換データが送信されず、入手データが持ち逃げされる可能性がある。
【０００３】
一方、係る持ち逃げを阻止し、署名者Ａ，Ｂに公平な署名交換のプロトコルが考えられている。例えば、署名を先に公開する署名者Ａに秘密情報を生成させ、秘密情報から計算されるコミット情報に基づいた仮署名を交換し、仮署名に秘密情報を添付して署名を生成する方式がある（非特許文献１参照）。この方法は、コミット情報の基となる秘密情報を署名者Ａに生成させ、署名者Ａの不利を防いでいる。具体的には、図１９及び図２０に示す署名生成処理と、図２１に示す署名検証処理とが実行される。
【０００４】
各処理では、素数ｐ，ｑ、ハッシュ関数Ｈ，Ｇ、署名者Ａ，Ｂの秘密鍵ｓA，ｓB、公開鍵ｐA，ｐB、署名対象文書ＭA，ＭB、秘密情報ｋ、コミット情報ｈ1,ｈ2，ｈ1’,ｈ2’、乱数ｔ，ｔ’、仮署名σA,σBを用いる。添字Ａ，Ｂは署名生成装置Ａ，Ｂに属する旨を表す。他には署名検証装置Ｃを用いる。
【０００５】
署名生成処理においては、署名生成装置Ａは、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐB及び署名対象文書ＭAに基づいて、コミット情報ｈ1，ｈ2と仮署名値σAを計算し、得られた仮署名（ＭA，ｈ1，ｈ2，σA）を署名生成装置Ｂに送信して待機する（ＳＴ１Ａ〜ＳＴ８Ａ）。
【０００６】
署名生成装置Ｂは、受信した仮署名を検証し、検証結果が正当なときにはコミット情報ｈ1’,ｈ2’及び仮署名値σBを計算し、得られた仮署名（ＭB,ｈ1’,ｈ2’,σB）を署名生成装置Ａに送信して待機する（ＳＴ１Ｂ〜ＳＴ１０Ｂ）。
【０００７】
署名生成装置Ａは、受信した仮署名を検証し、検証結果が正当なときには秘密情報ｋを署名生成装置Ｂに送信し、この秘密情報ｋ及び仮署名を署名（ＭB,ｈ1’,ｈ2’,σB,ｋ）として出力する（ＳＴ９Ａ〜ＳＴ１２Ａ）。
【０００８】
署名生成装置Ｂは、受信した秘密情報ｋを検証し、検証結果が正当なときには秘密情報ｋ及び仮署名を署名（ＭA,ｈ1,ｈ2,σA,ｋ）として出力する（ＳＴ１１Ｂ〜ＳＴ１３Ｂ）。以上により署名生成処理が完了する。
【０００９】
署名検証処理においては、署名検証装置Ｃは、署名生成装置Ｂから受信した署名（ＭA,ｈ1,ｈ2,σA,ｋ）を各装置Ａ，Ｂの公開鍵ｐA，ｐBに基づいて検証し（ＳＴ２１〜ＳＴ２３）、検証結果が正当であれば署名を受理し（ＳＴ２４）、不当であれば署名を棄却する（ＳＴ２５）。署名検証処理は署名生成装置Ａから署名を受けた場合も同様である。
【００１０】
次に、上述した署名交換プロトコルが公平である旨を（１）〜（３）の場合により説明する。（１）署名生成装置Ａ，Ｂが署名交換プロトコルを正しく実行する場合、公平に署名が交換されることは明らかである。
【００１１】
（２）署名生成装置Ｂが仮署名（ＭA，ｈ1，ｈ2，σA）を受信した後（ＳＴ３Ｂ）、仮署名を計算しない又は送信しない場合を考える。この場合、署名生成装置Ｂは秘密情報ｋを入手できない。秘密情報ｋはハッシュ関数Ｇの一方向性によりコミット情報ｈ2からの復元が困難である。従って、署名生成装置Ｂは正しい署名を生成できない。不正な署名は、署名検証処理により棄却される（ＳＴ２３，ＳＴ２５）。
【００１２】
（３）署名生成装置Ａが仮署名（ＭB,ｈ1’,ｈ2’,σB）を受信した後（ＳＴ９Ａ）、秘密情報ｋを送信しない場合を考える。この場合、署名生成装置Ａは各データに秘密情報ｋを添付し、正しい署名（ＭB,ｈ1’,ｈ2’,σB,ｋ）を署名検証装置Ｃに送信できる。署名生成装置Ｂは、署名生成装置Ａから秘密情報ｋを受信できないが、署名検証装置Ｃから署名の効力の問合せや、署名に基づく取引要求を受けた際には、署名検証装置Ｃから秘密情報ｋを入手可能となる。すなわち、署名生成装置Ｂは、署名生成装置Ａが署名を利用した際には、署名検証装置Ｃから秘密情報ｋを入手して正しい署名を生成可能となる。
【００１３】
従って、上述したプロトコルは（１）〜（３）に基づき、公平であると考えられる。係るプロトコルは、署名生成装置Ａ，Ｂの公開鍵ｐA，ｐBが必要であり、契約文書のように第三者に対しても二者を特定しつつ、文書を有効としたい場合に好適である。
【００１４】
一方、上述したプロトコルは、第三者に対して匿名性を保って署名を交換したい場合には不向きである。図２２に示す電子現金システムを例に挙げて述べる。金融機関装置１、利用者装置２及び商店装置３は、署名生成装置Ａ，Ｂ及び署名検証装置Ｃに対応する。
【００１５】
始めに、利用者装置２は電子現金の発行を依頼する。具体的には、利用者の口座から電子現金に相当する金額を引落す旨を承認する署名（承諾書）を金融機関装置１に送信する（Ｓ１）。金融機関装置１は、承諾書に基づき、口座から現金を引落すと共に、金融機関装置１の署名により価値が保証された電子現金を利用者装置２に送信する（Ｓ２）。なお、両者の署名（承諾書と電子現金）は公平に交換される必要がある。
【００１６】
利用者装置２は電子現金を利用して商品やサービスを商店装置３に要求する（Ｓ２，Ｓ３）。商店装置３は利用者装置２の公開鍵ｐBにより電子現金を検証し、要求された商品等を利用者装置２に送り（Ｓ４）、電子現金を金融機関装置１に還流する（Ｓ５）。
【００１７】
このように、上述したプロトコルは、電子現金の検証時に利用者装置２の公開鍵ｐBが必要であるため、利用者装置２の匿名性を保ちたい場合に不向きである。
【非特許文献１】L. Chen et al., “ Concurrent Signature ”, Advances in Cryptology, EUROCRYPT 2004, p287-305, 2004
【発明の開示】
【発明が解決しようとする課題】
【００１８】
以上説明したように、従来の署名交換方法は、署名検証時に署名者Ｂの公開鍵ｐBが必要なため、匿名性が要求される場合には不向きである。この場合、匿名性を保てないことから、署名者のプライバシが保護されないことになる。
【００１９】
本発明は上記実情を考慮してなされたもので、匿名性が要求される場合であっても、公平な署名交換を実現し得る署名交換方法、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
第１の発明は、互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置が第１署名対象文書ＭAを決定すると共に、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置が第２署名対象文書ＭBを決定し、前記第１署名生成装置が生成した秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成し、この第１コミット情報ｈ、前記第１署名対象文書ＭA、前記第２公開鍵ｐB及び前記第１秘密鍵ｓAに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第１仮署名値σAを生成し、得られた第１仮署名値σA、第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信し、前記第２署名生成装置が、前記第１仮署名（σA，ｈ，ＭA）を受信した後に、第２コミット情報ｈ’＝ｈ、前記第１公開鍵ｐA、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、前記第１及び第２公開鍵ｐA，ｐBから正当性を検証可能な第２仮署名値σBを生成し、得られた第２仮署名値σB、第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信し、前記第１署名生成装置が、前記第２仮署名（σB，ｈ’，ＭB）を受信した後に、前記秘密情報ｋを第２署名生成装置に送信することにより、前記第１及び第２署名生成装置がデジタル署名を交換する署名交換方法であって、前記第１署名生成装置としては、前記秘密情報ｋを送信した後、第１マスク値ｒ’を生成又は選択する工程と、前記第１マスク値ｒ’に基づいて前記第２仮署名値σBを修正し、前記第１公開鍵ｐAを用いずに前記第２公開鍵ｐBから正当性を検証可能な第２署名値σB’を得る工程と、前記第２署名値σB’、前記第２コミット情報ｈ’、前記第２署名対象文書ＭB及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する工程とを備えており、前記第２署名生成装置としては、前記秘密情報ｋを受信した後、第２マスク値ｒを生成又は選択する工程と、前記第２マスク値ｒに基づいて前記第１仮署名値σAを修正し、前記第２公開鍵ｐBを用いずに前記第１公開鍵ｐAから正当性を検証可能な第１署名値σA’を得る工程と、前記第１署名値σA’、前記第１コミット情報ｈ、前記第１署名対象文書ＭA及び前記秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する工程とを備えた署名交換方法である。
【００２１】
第２の発明は、互いに対応する第１秘密鍵ｓA及び第１公開鍵ｐAを有する第１署名生成装置と、互いに対応する第２秘密鍵ｓB及び第２公開鍵ｐBを有する第２署名生成装置とがデジタル署名を交換する署名交換方法であって、前記第１署名生成装置が第１署名対象文書ＭAを決定すると共に、前記第２署名生成装置が第２署名対象文書ＭBを決定する工程と、前記第１署名生成装置が秘密情報ｋを生成する工程と、前記第１署名生成装置が前記秘密情報ｋにランダム関数Ｇを施して第１コミット情報ｈを生成する工程と、前記第１署名生成装置が乱数ｔを生成する工程と、前記第１署名生成装置が、前記第１署名対象文書ＭA、前記第１コミット情報ｈ及び前記第１秘密鍵ｓAに基づいて、前記第１公開鍵ｐAから正当性を検証可能な第１仮署名値σAを生成する工程と、前記第１署名生成装置が前記第１仮署名値σA、前記第１コミット情報ｈ及び前記第１署名対象文書ＭAを含む第１仮署名（σA，ｈ，ＭA）を前記第２署名生成装置に送信する工程と、前記第２署名生成装置が、前記第１仮署名（σA，ｈ，ＭA）を受信した後に、第２コミット情報ｈ’、前記第２署名対象文書ＭB及び前記第２秘密鍵ｓBに基づいて、前記第２公開鍵ｐBから正当性を検証可能な第２仮署名値σBを生成する工程と、前記第２署名生成装置が、前記第２仮署名値σB、前記第２コミット情報ｈ’及び前記第２署名対象文書ＭBを含む第２仮署名（σB，ｈ’，ＭB）を前記第１署名生成装置に送信する工程と、前記第１署名生成装置が、前記第２仮署名（σB，ｈ’，ＭB）を受信した後に、前記秘密情報ｋを第２署名生成装置に送信する工程と、前記第１署名生成装置が、前記第２仮署名（σB，ｈ’，ＭB）及び前記秘密情報ｋを含む第２署名（σB’，ｈ’，ＭB，ｋ）を出力する工程と、前記第２署名生成装置が、前記秘密情報ｋを受けると、前記第１仮署名（σA，ｈ，ＭA）及び当該秘密情報ｋを含む第１署名（σA’，ｈ，ＭA，ｋ）を出力する工程とを備えた署名交換方法である。
【００２２】
第１及び第２の各発明は、第１署名生成装置、第２署名生成装置、又は各署名生成装置に用いられるプログラム等としても実現可能となっている。
【００２３】
（作用）
第１の発明においては、第１署名生成装置が、第１マスク値ｒ’に基づいて第２仮署名値σBを修正し、第１公開鍵ｐAを用いずに第２公開鍵ｐBから正当性を検証可能な第２署名値σB’を得る。
【００２４】
これにより、第１署名生成装置が署名検証装置に第２署名（σB’，ｈ’，ＭB，ｋ）を提示したとき、署名検証装置においては、第１署名生成装置の第１公開鍵ｐAを用いずに、第２署名生成装置の第２公開鍵ｐBに基づいて、第２署名（σB’，ｈ’，ＭB，ｋ）が検証可能となる。
【００２５】
一方、第２署名生成装置も同様に動作して、第２公開鍵ｐBを用いずに第１公開鍵ｐAから正当性を検証可能な第１署名値σA’を得る。これにより、第２署名生成装置が署名検証装置に第１署名（σA，ｈ，ＭA，ｋ）を提示したとき、署名検証装置においては、第２署名生成装置の第２公開鍵ｐBを用いずに、第１署名生成装置の第１公開鍵ｐAに基づいて、第１署名（σA’，ｈ，ＭA，ｋ）が検証可能となる。  
このように第１の発明は、公平な署名交換方法において、署名を提示する装置の公開鍵を用いずに、署名を検証可能としたので、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【００２６】
一方、第２の発明においては、第１及び第２公開鍵ｐA,ｐBを用いずに第１及び第２仮署名値σA，σBを得ることから、第１仮署名を検証するときには第２公開鍵ｐBが不要となり、第２仮署名を検証するときには第１公開鍵ｐAが不要となる。
【００２７】
すなわち、第２署名生成装置は、署名検証装置に対し、第２公開鍵ｐBを渡さずに署名の検証を依頼可能となる。同様に、第１署名生成装置は、署名検証装置に対し、第１公開鍵ｐAを渡さずに署名の検証を依頼可能となる。
【００２８】
このように第２の発明は、公平な署名交換方法において、第１又は第２公開鍵ｐA,ｐBを渡さずに各署名の検証を依頼可能としたので、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【発明の効果】
【００２９】
以上説明したように本発明によれば、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の各実施形態について図面を参照しながら説明するが、その前に非特許文献１による署名交換方法に署名変形ステップを追加した参考例を図２３及び図２４を用いて述べる。
【００３１】
署名生成装置Ａは、図２３に示すように、前述同様にステップＳＴ１Ａ〜ＳＴ１１Ａを実行し、署名生成装置Ｂから受信した仮署名（ＭB,ｈ1’,ｈ2’,σB）を検証した後、秘密情報ｋを送信する（ＳＴ１１Ａ）。次に、署名生成装置Ａは、変形情報Ｘ＝ｐA{h’_2}  ｍｏｄ  ｐを計算し（ＳＴ３０）、得られた変形情報Ｘを含む署名（ＭB,ｈ1’,ｈ2’,σB,ｋ,Ｘ）を出力する（ＳＴ３１）。なお、署名生成装置Ｂについても同様にして参考例の署名生成方法を構成可能である。
【００３２】
署名検証装置Ｃは、図２４に示すように、公開情報ｐ，ｑ，Ｈ，Ｇ，公開鍵ｐA、及び、署名生成装置Ｂが生成した署名（ＭB,ｈ1’,ｈ2’,σB,ｋ,Ｘ）を入手する（ＳＴ４１）。ステップＳＴ４１において、公開情報及び／又は公開鍵を予め署名検証装置Ｃの記憶領域に保存することも可能である。署名検証装置Ｃは、署名の成分が仮署名（ＭB,ｈ1’,ｈ2’,σB）、秘密情報ｋ及び変形情報Ｘから構成されているか否かを検査する（ＳＴ４２）。検査の結果、否を示す場合、署名交換が正しく行われていない、あるいは署名が流通される過程で情報にエラーが生じたと判断して署名を棄却する（ＳＴ４５）。ステップＳＴ４２の検査の結果、正しく構成されている旨を示す場合、署名検証装置Ｃは、ｈ2＝Ｇ（ｋ）及びｈ1＋ｈ2＝Ｈ（ｇ{σ_B}ＸｐB{h’_1}  ｍｏｄ  ｐ，ＭB）が成り立つか否かを検査する（ＳＴ４３）。検査の結果、成り立つ旨を示す場合には署名を受理し（ＳＴ４４）、否を示す場合には署名を棄却する（ＳＴ４５）。
【００３３】
ステップＳＴ４３の処理は、署名生成装置Ａの公開鍵ｐAを用いないため、プライバシ保護が実現されるように見える。しかしながら、変形情報Ｘが公開鍵ｐAに関連する数であり、変形情報Ｘから公開鍵ｐAを特定可能であるため、プライバシ保護は実現されていない。変形情報Ｘから公開鍵ｐAを特定する手法を以下に２通り示す。
【００３４】
第１の手法は、公開鍵に対する総当り法である。署名者Ｂと署名交換をしたと思われる署名者の範囲が署名者Ａ１から署名者Ａｍのｍ人に限定できる場合、各署名者Ａ１〜Ａｍの公開鍵ｐ{A_1}〜ｐ{A_m}に対し、署名に含まれるコミット情報ｈ2’に基づいて、変形情報Ｘの候補Ｘ１，…，Ｘｍ（＝ｐ{A_1}{h’_2}  ｍｏｄ  ｐ，…，ｐ{A_m}{h’_2}  ｍｏｄ  ｐ）を順次計算する。これにより、変形情報Ｘ＝ｐ{A_T}{h’_2}  ｍｏｄ  ｐに一致する候補ＸＴから、対応する公開鍵ｐ{A_T}を持つ署名者ＡＴを特定できる。
【００３５】
第２の手法は、変形情報Ｘとコミット情報ｈ2’から公開鍵ｐAを直接的に求める方法である。署名（ＭB,ｈ1’,ｈ2’,σB,ｋ,Ｘ）の成分に対し、ｑが素数であることから拡張ユークリッドの互除法を利用して(ｈ2’)-1  ｍｏｄ  ｑを計算可能である。このとき、Ｘ{(h’_2)＾{-1}}  ｍｏｄ  ｐを計算すれば、Ｘ{(h’_2)＾{-1}}  ｍｏｄ  ｐ＝（ｐA{h’_2}）{(h’_2)＾{-1}}  ｍｏｄ  ｐ  ＝(ｐA)1＝ｐA  ｍｏｄ  ｐ  により、公開鍵ｐAを特定できる。
【００３６】
以上に示した通り、公開鍵に関連する数ｐA{h’_2}を変形情報Ｘに置換するだけでは、匿名性が要求される場合には対応できない。そこで、以下の実施形態では、匿名性が要求される場合であっても、公平な署名交換を実現する技術を述べる。
【００３７】
（第１の実施形態）
始めに、本発明の第１の実施形態に係る署名生成装置及び署名検証装置に用いる関数と、関数の入出力データの長さとを説明する。
【００３８】
安全な署名交換システムを構成する観点から、安全性のパラメータＬ，Ｌ1，Ｌ2を以下のように選択する。Ｌは離散対数問題が計算困難とされるビット長である１０２４とし、Ｌ1はそのときの位数１０２３とし、Ｌ2は総当りによる探索が困難とされるビット長である８０などとする。ここで、Ｌビットの素数ｐと、ｐ−１を割り切るＬ1ビットの素数ｑとはセンタにより公開されている。任意のビット長の値をＬ1ビットの値に写像するハッシュ関数Ｈと、Ｌ2ビットの値をＬ1ビットの値に写像するハッシュ関数Ｇとは公開されている。
【００３９】
ハッシュ関数ＧやＨは、例えばＳＨＡなどのハッシュ関数であり、具体例がベラル（Bellare）らの文献(M. Bellare and P. Rogaway, “Optimal Asymmetric Encryption − How to encrypt with RSA” Advances in Cryptology − EUROCRYPT’94 LNCS, Springer−Verlag, 1995)に記載されている。
【００４０】
図１は本発明の第１の実施形態に係る署名生成装置の構成を示す模式図であり、図２は同実施形態における署名検証装置の構成を示す模式図である。  
署名生成装置ＳgＡ，ＳgＢは、図１に示すように、メモリ１１、秘密鍵メモリ１２、演算器１３、乱数生成部１４、乱数メモリ１５、入出力部１６、Ｇ関数演算部１７、Ｈ関数演算部１８、仮署名生成部１９、仮署名検証部２０、署名変形部２１及び制御部２２を備えている。秘密鍵メモリ１２及び乱数生成部１４を除く各要素１１，１３，１５〜２２は、互いにバスを介して接続されている。
【００４１】
なお、各署名生成装置ＳgＡ，ＳgＢは、互いに同一構成のため、ここでは署名生成装置ＳgＡを例に挙げて説明する。
【００４２】
メモリ１１は、各部１３，１６〜２２から読出／書込可能な記憶装置であり、例えばハードディスク及びＲＡＭが使用される。ＲＡＭには、例えば署名対象文書ＭA，ＭB、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐB、秘密情報ｋ、第１コミット情報ｈ，ｈ1，ｈ2、第１仮署名値σA、第２仮署名（ＭB，ｈ1’，ｈ2’，σB）、乱数ｒ’、第１変形値Ｙ’、第２署名値σB’第２署名（ＭB，ｈ1’，ｈ2’，σB’，ｋ，Ｙ’）といったデータが記憶される。ハードディスクには、例えば署名生成装置のプログラムがインストールされ、必要により、ＲＡＭ内のデータが保存される。
【００４３】
秘密鍵メモリ１２は利用者Ａの公開鍵暗号方式に関する秘密鍵ｓAを格納するメモリであり、仮署名生成部１９及び署名変形部２１から読出可能となっている。
【００４４】
演算器１３は、各部１７〜２２から制御されて多倍長の演算を実行する部分であり、具体的には排他的論理和の計算、ビット連結・分割、ビットの比較、などを行う。
【００４５】
乱数生成部１４は、制御部２２に制御され、署名生成時に必要な乱数を発生させる部分であり、生成された乱数は乱数メモリ１５に保存される。
【００４６】
乱数メモリ１５は、乱数生成部１４から乱数が書き込まれるメモリであり、バスを介して各部１７〜２２から読出可能となっている。
【００４７】
入出力部１６は、装置と外部の間で取り交わされるその他のデータの入出力を行う。また、入出力部１６は、予めコンピュータ読取り可能な記憶媒体から署名生成装置のプログラムを読み出してメモリ１１にインストールする機能をもっている。
【００４８】
Ｇ関数演算部１７は、制御部２２に制御され、Ｌ2ビットの値をＬ1ビットの値に写像するハッシュ関数Ｇを演算するものであり、ここでは第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）や秘密情報の検証式ｈ2’＝Ｇ（ｋ）の演算に用いられている。
【００４９】
Ｈ関数演算部１８は、制御部２２に制御され、任意のビット長の値をＬ1ビットの値に写像するハッシュ関数Ｈを演算するものであり、ここでは第１コミット情報の合計値ｈ＝Ｈ（ｇｔｐB{h_2}  ｍｏｄ  ｐ，ＭA）や第２検証式ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐA{h’_1}ｐB{h’_2}  ｍｏｄ  ｐ，ＭB）の演算に用いられている。
【００５０】
Ｇ，Ｈ関数演算部１７，１８は、ランダム関数Ｇ，Ｈの一例としてハッシュ関数Ｇ，Ｈを用いるが、これに限らず、任意のランダム関数Ｇ，Ｈを用いる構成としてもよい。また、Ｇ，Ｈ関数演算部１７，１８は、事前に取り決められたランダム関数Ｇ，Ｈを保存しておいてもよいし、署名者ごとに定められたランダム関数Ｇ，Ｈを入出力部１６を介して入手して保存してもよい。これは後述するＧ，Ｈ関数演算部３６，３７でも同様である。
【００５１】
仮署名生成部１９は、制御部２２に制御され、メモリ１１内の第１コミット情報の合計値ｈ及び第２部分ｈ2から第１コミット情報の第１部分ｈ1＝ｈ−ｈ2  ｍｏｄ  ｑを計算する機能と、メモリ１１内の第１部分ｈ1、第２部分ｈ2及び乱数ｔと秘密鍵メモリ１２内の秘密鍵ｓAとに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを計算し、計算結果ｈ1，σAをメモリ１１に書き込む機能とをもっている。
【００５２】
仮署名検証部２０は、制御部２２に制御され、入出力部１６から受け付けた署名者Ｂの第２仮署名（ＭB,ｈ1’,ｈ2’,σB）を、署名者Ｂの公開鍵ｐBを利用して検証するものであり、検証結果を制御部２２に出力する機能をもっている。具体的には、仮署名検証部２０は、Ｇ，Ｈ関数演算部１７，１８を用い、秘密情報の検証式ｈ2’＝ｈ2＝Ｇ（ｋ）及び第２検証式ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐA{h’_1}ｐB{h’_2}  ｍｏｄ  ｐ，ＭB）が成り立つか否かにより第２仮署名を検証する機能をもっている。
【００５３】
署名変形部２１は、署名者Ｂから受け付けた第２署名と乱数生成部１４で生成された乱数ｒ’及び秘密鍵メモリ１２に保存された秘密鍵ｓAを用いて、署名者Ｂの署名情報に変更を加えるものである。
【００５４】
具体的には、署名変形部２１は、第２検証式のうち、第１公開鍵ｐAに関する第１署名者関連値ｐA{h’_2}を乱数ｒ’に基づいて変形し、第１変形値Ｙ’＝ｐA{h’_2+r’} ｍｏｄ  ｐを計算し、計算結果Ｙ’をメモリ１１に書き込む機能をもっている。また、署名変形部２１は、乱数メモリ１５内の乱数ｒ’及び秘密鍵メモリ１２内の第１秘密鍵ｓAに基づいて第２仮署名値σBを修正し、第２署名値σB’＝σB−ｒ’ｓA ｍｏｄ  ｑを計算し、計算結果σBをメモリ１１に書き込む機能を持っている。
【００５５】
制御部２２は、図３に示す動作を実行するように、各部１１〜２１を制御する機能をもっている。なお、署名生成装置ＳgＢの場合、制御部２２は、図４に示す動作を実行するように各部１１〜２１を制御する。このような制御部２２は、予め制御機能を実現させるためのプログラムがコンピュータ読取り可能な記憶媒体から入出力部１６を介して装置のコンピュータにインストールされることにより実現される。
【００５６】
一方、署名検証装置ＶrＣは、図２に示すように、メモリ３１、演算器３２、入出力部３３、判定部３４、Ｇ関数演算部３５、Ｈ関数演算部３６、署名検証部３７及び制御部３８が互いにバスを介して接続されている。
【００５７】
メモリ３１は、各部３２〜３８から読出／書込可能な記憶装置であり、例えばハードディスク及びＲＡＭが使用される。
【００５８】
ＲＡＭには、例えば第１署名（ＭA，ｈ1，ｈ2，σA’，ｋ，Ｙ）、第２署名（ＭB，ｈ1’，ｈ2’，σB’，ｋ，Ｙ’）、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐA，ｐBといったデータが記憶される。
【００５９】
ハードディスクには、例えば署名検証装置のプログラムがインストールされ、必要により、ＲＡＭ内のデータが保存される。
【００６０】
演算器３２は、各部３３〜３８から制御されて多倍長の演算を実行する部分であり、具体的には排他的論理和の計算、ビット連結・分割、ビットの比較、などを行う。
【００６１】
入出力部３３は、装置と外部の間で取り交わされるその他のデータの入出力を行う。また、入出力部３３は、予めコンピュータ読取り可能な記憶媒体から署名検証装置のプログラムを読み出してメモリ３１にインストールする機能をもっている。
【００６２】
判定部３４は、制御部３８に制御され、入出力部３３から受け付けた署名者Ｂの署名に関し、仮署名（ＭB,ｈ1’,ｈ2’,σB’）及び変形データＹから構成されるか否かを判定し、判定結果を制御部３８に出力する機能をもっている。。
【００６３】
Ｇ関数演算部３５は、署名検証部３７に制御され、Ｌ2ビットの値をＬ1ビットの値に写像するハッシュ関数Ｇを演算するものであり、ここでは秘密情報の検証式ｈ2＝Ｇ（ｋ）の演算に用いられている。
【００６４】
Ｈ関数演算部３６は、署名検証部３７に制御され、任意のビット長の値をＬ1ビットの値に写像するハッシュ関数Ｈを演算するものであり、ここでは第１署名検証式ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A}ｐA{ｈ_1  ｈ_2}Ｙ  ｍｏｄ  ｐ，ＭA）の演算に用いられている。
【００６５】
署名検証部３７は、制御部３８に制御され、署名者Ｂの公開鍵ｐBを利用して署名を検証し、検証結果を制御部３８に出力する機能をもっている。具体的には、署名検証部３７は、Ｇ，Ｈ関数演算部３５，３６を用い、秘密情報の検証式ｈ2＝Ｇ（ｋ）及び第１署名検証式ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A}ｐA{ｈ_1  ｈ_2}Ｙ  ｍｏｄ  ｐ，ＭA）が成り立つか否かを検証する機能をもっている。
【００６６】
制御部３８は、図５又は図６に示す動作を実行するように各部３１〜３７を制御するものである。このような制御部３８は、予め制御機能を実現させるためのプログラムがコンピュータ読取り可能な記憶媒体から入出力部３３を介して装置のコンピュータにインストールされることにより実現される。
【００６７】
次に、以上のように構成された署名生成装置及び署名検証装置の動作を図３乃至図６のフローチャートを用いて説明する。
【００６８】
（署名生成処理）
署名生成装置ＳgＡには、予め０以上ｑ未満の整数の集合Ｚq＝｛０，１，…，ｑ−１｝から秘密裏に選ばれた秘密鍵ｓA及び秘密鍵ｓAから計算される公開鍵ｐA＝ｇ{ｓ_A}  ｍｏｄ  ｐが保存されている。
【００６９】
同様に、署名生成装置ＳgＢには、予め集合Ｚq＝｛０，１，…，ｑ−１｝から秘密裏に選ばれた秘密鍵ｓB及び秘密鍵ｓBから計算される公開鍵ｐB＝ｇ{ｓ_B}  ｍｏｄ  ｐが保存されている。
【００７０】
署名生成装置ＳgＡ，ＳgＢでは、それぞれ署名者Ａ，Ｂの操作により、署名対象文書ＭA，ＭBが決定される。署名対象文書ＭA，ＭBは複数回の通信による交渉の後に決定されてもよい。署名交換処理は、署名生成装置ＳgＡ，ＳgＢのいずれから開始してもよいが、ここでは署名生成装置ＳgＡから開始するものとする。
【００７１】
署名生成装置ＳgＡでは、図３に示すように、署名者Ａによる入出力部１６の操作により、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐBと、決定済みの署名対象文書ＭAとを受け付け（ＳＴ１Ａ）、各情報ｐ，ｑ，Ｈ，Ｇ，ｐB，ＭAをメモリ１１に書き込む。
【００７２】
。次に、署名生成装置ＳgＡでは、制御部２２がＬ2ビットの秘密情報ｋをランダムに選択し（ＳＴ２Ａ）、この秘密情報ｋをメモリ１１に書き込む。Ｇ関数演算部１７は、メモリ１１内の秘密情報ｋにハッシュ関数Ｇを施し、第１コミット情報の第２部分ｈ2＝Ｇ（ｋ）を計算して（ＳＴ３Ａ）、メモリ１１に書き込む。
【００７３】
署名生成装置ＳgＡでは、乱数生成部１４がＬ1ビットの乱数ｔを生成し（ＳＴ４Ａ）、この乱数ｔを乱数メモリ１５に書き込む。Ｈ関数演算部１８は、各メモリ１１，１５を参照し、この乱数ｔ、第１コミット情報の第２部分ｈ2、署名者Ｂの公開鍵ｐB、及び署名対象文書ＭA等にハッシュ関数Ｈを施し、第１コミット情報の合計値ｈ＝Ｈ（ｇｔｐB{h_2}  ｍｏｄ  ｐ，ＭA）を計算し（ＳＴ５Ａ）、合計値ｈを仮署名生成部１９に出力する。
【００７４】
仮署名生成部１９は、第１コミット情報の合計値ｈ及び第２部分ｈ2から第１コミット情報の第１部分ｈ1＝ｈ−ｈ2  ｍｏｄ  ｑを計算し、更に、この第１部分ｈ1、第２部分ｈ2、署名者Ａの秘密鍵ｓA及び乱数ｔに基づいて、第１仮署名値σA＝ｔ−ｈ1ｈ2ｓA ｍｏｄ  ｑを計算し（ＳＴ６Ａａ）、計算結果ｈ1，σAをメモリ１１に書き込む。
【００７５】
しかる後、署名生成装置ＳgＡでは、メモリ１１に記憶された第１仮署名値σA、第１コミット情報ｈ1,ｈ2及び第１署名対象文書ＭAを含む第１仮署名（ＭA, ｈ1, ｈ2, σA）を署名生成装置ＳgＢに送信し（ＳＴ７Ａ）、待機する（ＳＴ８Ａ）。
【００７６】
署名生成装置ＳgＢは、図４に示すように、署名者Ｂによる入出力部１６の操作により、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐAと、決定済みの署名対象文書ＭBとを受け付けた後（ＳＴ１Ｂ）、各情報ｐ，ｑ，Ｈ，Ｇ，ｐA，ＭBをメモリ１１に書き込んで待機する（ＳＴ２Ｂ）。
【００７７】
しかる後、署名者生成装置ＳgＢでは、署名生成装置ＳgＡから入出力部１６を介して第１仮署名（ＭA, ｈ1, ｈ2, σA）を受けると（ＳＴ３Ｂ）、仮署名検証部２０が、この第１仮署名と第１及び第２公開鍵ｐA,ｐBとを第１検証式ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1  h_2}ｐB{h_2}  ｍｏｄ  ｐ，ＭA）に代入して第１検証式が成り立つか否かにより（ＳＴ４Ｂｂ）、第１仮署名を検証する。
【００７８】
第１検証式が成り立たない場合は仮署名を棄却して処理を停止する。第１検証式が成り立つ場合には、署名生成装置ＳgＢでは、制御部２２が第１コミット情報の第２部分ｈ2を第２コミット情報の第２部分ｈ2’に設定し（ｈ2’＝ｈ2；ＳＴ５Ｂ）、乱数生成部１４がＬ1ビットの乱数ｔ’を生成し（ＳＴ６Ｂ）、乱数ｔ’を乱数メモリ１５に書き込む。
【００７９】
次に、署名生成装置ＳgＢでは、Ｈ関数演算部１９が、第２コミット情報の第２部分ｈ2’、乱数ｔ’、第１公開鍵ｐA及び第２署名対象文書ＭBに第２ランダム関数Ｈを施し、第２コミット情報の合計値ｈ’＝Ｈ（ｇｔ’ｐA{h’_2}  ｍｏｄ  ｐ，ＭB）を計算し（ＳＴ７Ｂ）、合計値ｈ’を仮署名生成部１９に出力する。
【００８０】
署名生成装置ＳgＢでは、仮署名生成部１９が、第２コミット情報の合計値ｈ’及び第２部分ｈ2’から第２コミット情報の第１部分ｈ1’＝ｈ’−ｈ2’  ｍｏｄ  ｑを計算する。更に、仮署名生成部１９は、この第１部分ｈ1’、第２部分ｈ2’、署名者Ｂの秘密鍵ｓB及び乱数ｔ’に基づいて、第２仮署名値σB＝ｔ’−ｈ1’ｈ2’ｓB  ｍｏｄ  ｑを計算し（ＳＴ８Ｂｂ）、計算結果ｈ1’，σBをメモリ１１に書き込む。
【００８１】
しかる後、署名生成装置ＳgＢでは、メモリ１１に記憶された第２仮署名値σB、第２コミット情報ｈ1’,ｈ2’及び第２署名対象文書ＭBを含む第２仮署名（ＭB, ｈ1’, ｈ2’, σB）を署名生成装置ＳgＡに送信し（ＳＴ９Ｂ）、待機する（ＳＴ１０Ｂ）。
【００８２】
署名生成装置ＳgＡでは、署名生成装置ＳgＢから入出力部１６を介して第２仮署名（ＭB,ｈ1’,ｈ2’,σB）を受けると（ＳＴ９Ａ）、仮署名検証部２０が、Ｇ，Ｈ関数演算部１７，１８を用い、秘密情報の検証式ｈ2’＝ｈ2＝Ｇ（ｋ）及び第２検証式ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐA{h’_1}ｐB{h’_1 h’_2}  ｍｏｄ  ｐ，ＭB）が成り立つか否かにより第２仮署名を検証し（ＳＴ１０Ａａ）、検証結果を制御部２２に出力する。
【００８３】
制御部２２は、この検証結果に基づいて、検証式が成り立たない場合には第２仮署名を棄却して処理を停止する。検証式が成り立つ場合には、秘密情報ｋを署名生成装置ＳgＢに送信する（ＳＴ１１Ａ）。
【００８４】
次に、署名生成装置ＳgＡでは、乱数生成部１４により第１マスク値ｒ’としての乱数ｒ’を生成し（ＳＴ５０Ａ）、この乱数ｒ’を乱数メモリ１４に書き込む。続いて、署名生成装置ＳgＡでは、署名変形部２１が、第２検証式のうち、第１公開鍵ｐAに関する第１署名者関連値ｐA{h’_2}を乱数ｒ’に基づいて変形し、第１変形値Ｙ’＝ｐA{h’_2+r’} ｍｏｄ  ｐを計算し、計算結果Ｙ’をメモリ１１に書き込む。
【００８５】
また、署名変形部２１は、乱数メモリ１５内の乱数ｒ’及び秘密鍵メモリ１２内の第１秘密鍵ｓAに基づいて第２仮署名値σBを修正し、第２署名値σB’＝σB−ｒ’ｓA ｍｏｄ  ｑを計算し（ＳＴ５１Ａ）、計算結果σBをメモリ１１に書き込む。なお、この修正は、第２検証式の第１署名者関連値を第１変形値Ｙ’で置換した場合に当該第２検証式を成立させるためのものである。
【００８６】
最後に、署名生成装置ＳgＡでは、第２署名対象文書ＭB、第２コミット情報ｈ1’,ｈ2’、第２署名値σB’、秘密情報ｋ及び第１変形値Ｙ’を含む第２署名（ＭB，ｈ1’，ｈ2’，σB’，ｋ，Ｙ’）を署名者Ｂから受け付けた署名として出力し（ＳＴ５２Ａ）、又はメモリ１１に保存する。
【００８７】
この第２署名は、署名者Ａによる署名生成装置ＳgＡの操作により、適宜、署名検証装置ＶrＣに向けて送信される。なお、署名検証装置ＶrＣは、第２検証式の第１署名者関連値を第１変形値Ｙ’で置換してなる第２署名検証式（ｈ1’＋ｈ2’＝Ｈ（ｇ{σ’_B} Ｙ’ｐB{h’_1 h’_2}，ＭB））、及び秘密情報ｋの検証式（ｈ2’＝Ｇ（ｋ））を有している。
【００８８】
一方、署名生成装置ＳgＢは、署名生成装置ＳgＡから入出力部１６を介して秘密情報ｋを受けた後（ＳＴ１１Ｂ）、仮署名検証部２０により秘密情報の検証式ｈ2＝Ｇ（ｋ）が成り立つか否かを検査し（ＳＴ１２Ｂ）、成り立たない場合は第１仮署名を棄却して処理を停止する。
【００８９】
検証式が成り立つ場合には、署名生成装置ＳgＢは、乱数生成部１４により第２マスク値ｒとしての乱数ｒを生成し（ＳＴ５０Ｂ）、この乱数ｒを乱数メモリ１５に書き込む。続いて、署名生成装置ＳgＢでは、署名変形部２１が、第１検証式のうち、第２公開鍵ｐBに関する第２署名者関連値ｐB{h_2}を乱数ｒに基づいて変形し、第２変形値Ｙ＝ｐB{h_2+r} ｍｏｄ  ｐを計算し、計算結果Ｙをメモリに書き込む。
【００９０】
また、署名変形部２１は、乱数メモリ１５内の乱数ｒ及び秘密鍵メモリ１２内の第２秘密鍵ｓBに基づいて第１仮署名値σAを修正し、第１署名値σA’＝σA−ｒｓB ｍｏｄ  ｑを計算し（ＳＴ５１Ｂ）、計算結果σA’をメモリ１１に書き込む。この修正は、第１検証式の第２署名者関連値を第２変形値Ｙで置換した場合に当該第１検証式を成立させるためのものである。
【００９１】
最後に、署名生成装置ＳgＢでは、第１署名対象文書ＭA、第１コミット情報ｈ1,ｈ2、第１署名値σA’、秘密情報ｋ及び第２変形値Ｙを含む第１署名（ＭA，ｈ1，ｈ2，σA’，ｋ，Ｙ）を署名者Ａから受け付けた署名として出力し（ＳＴ５２Ｂ）、又はメモリ１１に保存して、処理を停止する。
【００９２】
この第１署名は、署名者Ｂによる署名生成装置ＳgＢの操作により、適宜、署名検証装置ＶrＣに向けて送信される。なお、署名検証装置ＶrＣは、第１検証式の第２署名者関連値を第２変形値Ｙで置換してなる第１署名検証式（ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A} ｐA{h_1 h_2} Ｙ，ＭA））、及び秘密情報ｋの検証式（ｈ2＝Ｇ（ｋ））を有している。
【００９３】
（署名検証処理）
署名検証装置ＶrＣは、図５に示すように、例えば署名生成装置ＳgＢから第１署名（ＭA,ｈ1,ｈ2,σA’,ｋ,Ｙ）及び公開情報ｐ，ｑ，Ｈ，Ｇ，ｐAを入手し（ＳＴ６１）、署名（ＭA,ｈ1,ｈ2,σA’,ｋ,Ｙ）及び公開情報ｐ，ｑ，Ｈ，Ｇ，ｐAをメモリ１１に書き込む。ここで、署名検証装置ＶrＣは、第１署名を署名生成装置ＳgＢから直接受信してもよく、第三者を経由して受信してもよい。
【００９４】
ステップＳＴ６１において、署名検証装置ＶrＣは、予め公開情報及び／又は公開鍵ｐAをメモリ３１等の記憶領域に保存してもよい。署名検証装置ＶrＣでは、判定部３４が、第１署名が第１仮署名（ＭA, ｈ1, ｈ2, σA）と秘密情報ｋ及び第２変形値Ｙから構成されているか否かを判定し（ＳＴ６２）、判定結果を制御部３８に出力する。
【００９５】
制御部３８は、判定結果が否の場合、署名交換が正しく実行されていない、あるいは署名が流通される過程で情報にエラーが生じたため、署名を棄却する（ＳＴ６５）。
【００９６】
ステップＳＴ６２の判定の結果、正しく構成されている場合、制御部３８は署名検証部３７を起動する。署名検証部３７は、Ｇ，Ｈ関数演算部３５，３６を用い、秘密情報の検証式ｈ2＝Ｇ（ｋ）及び第１署名検証式ｈ1＋ｈ2＝Ｈ（ｇ{σ’_A}ｐA{ｈ_1  ｈ_2}Ｙ  ｍｏｄ  ｐ，ＭA）が成り立つか否かを検証し（ＳＴ６３）、検証結果を制御部３８に出力する。
【００９７】
なお、第１署名検証式は、第１検証式の第２署名者関連値ｐB{ｈ_2}を第２変形値Ｙ（＝ｐB{ｈ_2 + r}）で置換したものであり、署名生成装置ＳgＢの公開鍵ｐBを不要として、プライバシの保護を図っている。
【００９８】
ステップＳＴ６３の検証の結果、２つの検証式が成り立つ場合には、署名検証装置ＶrＣでは制御部３８が第１署名を受理し（ＳＴ６４）、否の場合には第１署名を棄却する（ＳＴ６５）。
【００９９】
なお、署名検証装置ＶrＣは、図６に示すように、署名生成装置ＳgＡから第２署名（ＭB,ｈ1’,ｈ2’,σB’,ｋ,Ｙ’）を受けた場合も同様に検証する。
【０１００】
上述したように本実施形態によれば、第１署名生成装置が、第２検証式のうち、第１公開鍵ｐAに関する第１署名者関連値ｐA{ｈ’_2}を乱数ｒ’に基づいて変形し、第１変形値Ｙ’を得ると、第２検証式の第１署名者関連値を第１変形値Ｙ’で置換した場合に当該第２検証式を成立させるように、乱数ｒ’に基づいて第２仮署名値σBを修正し、第２署名値σB’を得る。
【０１０１】
これにより、第２検証式の第１署名者関連値を第１変形値Ｙ’で置換してなる第２署名検証式を有する署名検証装置ＶrＣに対し、第１署名者関連値に代えて第１変形値Ｙ’を渡すことにより、第２署名（σB’，ｈ1’，ｈ2’，ＭB，ｋ，Ｙ’）が検証可能となる。
【０１０２】
一方、第２署名生成装置ＳgＢも同様に動作して、署名検証装置ＶrＣに対し、第２署名者関連値ｐB{ｈ_2}に代えて第２変形値Ｙを渡すことにより、第１署名（σA’，ｈ1，ｈ2，ＭA，ｋ，Ｙ）が検証可能となる。  
このように本実施形態によれば、公平な署名交換方法において、第１及び第２署名者関連値に代えて第１及び第２変形値Ｙ’，Ｙにより署名を検証可能としたので、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【０１０３】
また、本実施形態によれば、交換相手から入手した署名、該署名の受信者の秘密鍵を利用して、検証時に該署名の受信者の公開鍵を利用しない署名に変形させることで署名受信者のプライバシを保護できる。すなわち、図２２において金融機関装置１が発行した署名（電子現金）の正当性を検証するときに、利用者装置２の公開鍵は不要となり、利用者装置２はニックネームなどを利用して商店装置３との取引が可能となる。
【０１０４】
さらに、本実施形態によれば、署名者Ａと署名者Ｂのそれぞれが生成した署名を交換した後に、それぞれの署名者が署名交換相手から受け付けた署名を、乱数生成部１５により生成された乱数ｒ’，ｒと秘密鍵メモリ１２内の秘密鍵ｓA，ｓBを用いて変形する構成により、署名受信者の公開鍵ｐA，ｐBを用いずに検証できる署名へと変形し、署名受信者のプライバシ保護が実現可能な署名交換システムが構成される。
【０１０５】
（第２の実施形態）
次に、本発明の第２の実施形態に係る署名交換システムについて説明する。  
本実施形態は、第１の実施形態の変形例であり、第１及び第２マスク値として、乱数ｒ’，ｒに代えて、固定値ｒ0’，ｒ0を用いる構成となっている。
【０１０６】
以上のような構成によれば、固定値ｒ0’，ｒ0を利用している旨が解析者に未知の場合、固定値ｒ0’，ｒ0を利用していても、プライバシ保護を実現できる。
【０１０７】
本実施形態の効果について補足的に説明する。  
第１の実施形態の前に、第１及び第２の手法を述べ、公開鍵に関連する数ｐA{h’_2} を変形情報Ｘに置換するだけでは、匿名性が要求される場合には対応できないことを説明した。
【０１０８】
変形情報Ｘに置換する方法は、第１の実施形態において、乱数ｒを０としたときに一致する。同様に、第１の実施形態でも、乱数ｒに代えて固定値を利用した場合、その固定値が攻撃者に既知であれば上述の第１又は第２の手法によって公開鍵ｐAの復元が可能となる。
【０１０９】
例えば第１の手法である総当り法に関し、署名者Ｂと署名交換をしたと思われる署名者の範囲が署名者Ａ１から署名者Ａｍのｍ人に限定でき、ｒとして固定値ｒ0が利用されている場合を考える。
【０１１０】
この場合、ｍ人の署名者Ａ１,…,Ａｍの公開鍵ｐ{A_1},…,ｐ{A_m}に対し、署名に含まれるｈ2’に基づいて、それぞれ公開鍵に関連する数ｐ{A_1}{h’_2＋ｒ_0}  ｍｏｄ  ｐ,…,ｐ{A_m}{h’_2＋ｒ_0}  ｍｏｄ  ｐを計算する。
【０１１１】
これにより、変形情報Ｘ＝  ｐ{A_T}{h’_2＋ｒ_0}  ｍｏｄ  ｐ  に一致する計算結果に関連する公開鍵ｐ{A_T}をもつ署名者ＡＴが署名者Ｂと署名交換を行ったと特定できる。
【０１１２】
第２の手法である直接計算法に関し、乱数ｒに代えて固定値ｒ0が利用されていることが解析者に既知であるとする。このとき、変形情報Ｘと指数{ｈ2’＋ｒ0}から直接に公開鍵ｐAを求めることが可能となる。
【０１１３】
解析者はｑが素数であることから拡張ユークリッドの互除法を利用して（ｈ2’＋ｒ0）-1  ｍｏｄ  ｑを計算できる。また、解析者は、Ｘ{(h’_2＋ｒ_0)＾{-1}}  ｍｏｄ  ｐを計算し、Ｘ{(h’_2＋ｒ_0)＾{-1}}  ｍｏｄ  ｐ＝（ｐA{h’_2＋ｒ_0}）{(h’_2＋ｒ_0)＾{-1}}  ｍｏｄ  ｐ＝ｐA1  ｍｏｄ  ｐにより、公開鍵ｐAを特定できる。
【０１１４】
しかしながら、固定値ｒ0を利用している旨が解析者に未知の場合、たとえ固定値ｒ0を利用していても、プライバシ保護を実現できる。すなわち、第１の実施形態のように乱数ｒの利用が取り決められている場合に、固定値ｒ0を利用している旨を解析者に未知にしておくことで、乱数ｒに代えて固定値ｒ0とし、特に、固定値ｒ0＝０としてもプライバシの保護が可能となる。
【０１１５】
また、固定値ｒ0を用いることに加え、予め、ｓA ｒ  ｍｏｄ  ｑを計算して保存おくことで、署名変形に要する計算量を削減できる。特に固定値ｒ0＝０のときには事前計算や事前計算結果を保存する領域も不要となる。
【０１１６】
（第３の実施形態）
次に、本発明の第３の実施形態に係る署名交換システムについて説明する。  
本実施形態は、第２の実施形態の変形例であり、第１及び第２マスク値として、乱数ｒ’，ｒ又は固定値ｒ0’，ｒ0を使用することを確率的に選択する構成となっている。
【０１１７】
具体的には、メモリ１１は、前述した記憶内容に加え、予め選択テーブル情報が記憶されている。
【０１１８】
選択テーブル情報は、署名生成装置ＳgＡにおける第１マスク値ｒ’の場合を図７に示すように、０、固定値ｒ2’〜ｒn-1’、乱数のいずれかとその各々の使用確率βi（ｉ＝１，２，・・・，ｎ）との関係を示すものである。
【０１１９】
補足すると、選択テーブル情報は、第１マスク値ｒ’として、（１）０を用いる、（２）予め選択されたｎ−２個の固定値からランダムに選択する、又は（３）新たに生成した乱数を選択する、ことを示している。
【０１２０】
ここで、使用確率βi（ｉ＝１，２，・・・，ｎ）は、それぞれ［０，１］間の実数であり、β1＋β2＋・・・＋βn＝１を満たす関係にある。なお、署名生成装置ＳgＢでは、第２マスク値ｒに関し、同様に選択テーブル情報がメモリ１１に記憶されることは言うまでもない。
【０１２１】
具体的には署名生成装置ＳgＡでは、予めｎ−２個の値ｒ2，ｒ3，・・・，ｒn-1をランダムに選択し、秘密鍵ｓAを用いてそれぞれの値に対してｒ2ｓA，・・・，ｒn-1ｓAを計算して選択テーブル情報を生成し、この選択テーブル情報をメモリ１１に保存しておく。
【０１２２】
これにより、以後、署名生成要求を受ける毎に、署名生成装置ＳgＡでは、署名変形部２１が、メモリ１１内の選択テーブル情報を参照しながら、確率β1でｒ’＝０を選択するか、ｉ＝２，・・・，ｎ−１に対して確率βiでｒ’＝ｒiを選択するか、あるいは確率βnでｒ’として新たに乱数を生成する。
【０１２３】
マスク値ｒ’として新たに乱数を生成した場合には第１の実施形態と同一の処理を行う。それ以外の場合には（ｒ＝０の場合も含めて）、第２の実施形態と同一の処理を行い、事前計算の結果を利用することで計算量を削減可能となる。
【０１２４】
以上のような構成によれば、事前に選択しておく乱数の個数ｎ−２や確率βiを設計者が安全性を考慮して選択することにより、第２の実施形態に比べ、より一層、安全性を向上させることができる。
【０１２５】
（第４の実施形態）
次に、本発明の第４の実施形態に係る署名交換システムについて説明する。  
本実施形態は、第１の実施形態の変形例であり、仮署名の簡素化を図るため、署名生成装置ＳgＡでは、署名者Ｂの公開鍵ｐBを用いずに、コミット情報ｈ1,ｈ2と署名者Ａの秘密鍵ｓAから仮署名値σAを生成する構成となっている。
【０１２６】
同様に、署名生成装置ＳgＢでは、署名者Ａの公開鍵ｐAを用いずに、コミット情報ｈ1’,ｈ2’と署名者Ｂの秘密鍵ｓBから仮署名値σBを生成する構成となっている。
【０１２７】
これに伴い、署名検証装置ＶrＣでは、署名生成装置ＳgＡから受けた署名（ＭB, ｈ1’, ｈ2’, σB, ｋ）を検証する際に、署名生成装置ＳgＢの公開鍵ｐBが不要となる。同様に、署名検証装置ＶrＣでは、署名生成装置ＳgＢから受けた署名（ＭA, ｈ1, ｈ2, σA, ｋ）を検証する際に、署名生成装置ＳgＡの公開鍵ｐAが不要となる。
【０１２８】
ここで、署名生成装置ＳgＡは、図８に示すように、図１に示した構成から署名変形部２１を省略した構成要素からなる。但し、仮署名生成部１９は、図９に示すように、署名者Ｂの公開鍵ｐBを用いずにステップＳＴ５Ａａ１における第１コミット情報の合計値ｈを計算する機能をもっている。仮署名検証部２０は、図９に示すように、自己の公開鍵ｐAを用いずにステップＳＴ１０Ａａ１の仮署名σBの検証処理を実行する機能をもっている。
【０１２９】
同様に、署名生成装置ＳgＢは、図８に示したように、図１に示した構成から署名変形部２１を省略した構成要素からなる。但し、仮署名検証部２０は、図１０に示すように、自己の公開鍵ｐBを用いずにステップＳＴ４Ｂｂ１における仮署名σAの検証処理を実行する機能をもっている。仮署名生成部１９は、図１０に示すように、署名者Ａの公開鍵ｐAを用いずにステップＳＴ７Ｂｂ１の第２コミット情報の合計値ｈ’を計算する機能をもっている。
【０１３０】
一方、署名検証装置ＶrＣは、図２に示した構成要素からなる。但し、判定部３４は、後述する図１１又は図１２のステップＳＴ７２，７２’に示すように、署名の構成要素から第１及び第２変形値Ｙ’，Ｙを省略した判定処理を実行する機能をもっている。署名検証部３７は、ステップＳＴ７３，７３’に示すように、署名の検証式から第１及び第２変形値Ｙ’，Ｙを省略した検証処理を実行する機能をもっている。
【０１３１】
なお、署名生成装置ＳgＡ，ＳgＢ及び署名検証装置ＶrＣが使用する関数Ｇ，Ｈと、それら関数の入出力データの長さとは、第１実施形態と同一である。
【０１３２】
次に、以上のように構成された署名生成装置及び署名検証装置の動作を図９乃至図１２のフローチャートを用いて説明する。
【０１３３】
（署名生成処理）
署名生成装置ＳgＡでは、前述した通り、ステップＳＴ１Ａ〜ＳＴ４Ａの処理を実行し、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐB及び署名選択文書ＭAの受付、秘密情報ｋの選択、第１コミット情報の第２部分ｈ２の生成、乱数ｔの生成及びメモリ１１への書込までが完了したとする。
【０１３４】
このとき、署名生成装置ＳgＡでは、Ｈ関数演算部１８が、各メモリ１１，１５を参照し、システムパラメータｇのｔ乗及び署名対象文書ＭAに関し、ハッシュ関数Ｈを施して、第１コミット情報の合計値ｈ＝Ｈ（ｇｔ，ＭA）を計算し（ＳＴ５Ａ１）、合計値ｈを仮署名生成部１９に出力する。
【０１３５】
以下、前述同様に、署名生成装置ＳgＡでは、ステップＳＴ６Ａａ〜ＳＴ８Ａの処理を実行することにより、第１コミット情報の第１部分ｈ1と第１仮署名値σAとを算出し、得られる第１仮署名（ＭA,ｈ1,ｈ2,σA）を署名生成装置ＳgＢに送信して待機する。
【０１３６】
一方、署名生成装置ＳgＢでは、前述同様に、ステップＳＴ１Ｂ〜ＳＴ３Ｂまでの処理を実行し、公開情報ｐ，ｑ，Ｈ，Ｇ，ｐA及び署名選択文書ＭBの受付、待機、及び第１仮署名の受信までが完了しているとする。
【０１３７】
このとき、署名生成装置ＳgＢでは、仮署名検証部２０が、この第１仮署名と第１公開鍵ｐAとを第１検証式ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{h_1  h_2}  ｍｏｄ  ｐ，ＭA）に代入して第１検証式が成り立つか否かを検査することにより（ＳＴ４Ｂｂ１）、第１仮署名を検証する。
【０１３８】
第１検証式が成り立たない場合は仮署名を棄却して処理を停止する。第１検証式が成り立つ場合には、署名生成装置ＳgＢでは、前述したステップＳＴ５Ｂ，６Ｂを実行し、第２コミット情報の第２部分ｈ2’（＝ｈ2）及び乱数ｔ’を得る。
【０１３９】
しかる後、署名生成装置ＳgＢでは、Ｈ関数演算部１９が、各メモリ１１，１５を参照し、システムパラメータｇのｔ’乗及び署名対象文書ＭBに関し、ハッシュ関数Ｈを施して、第２コミット情報の合計値ｈ’＝Ｈ（ｇｔ’，ＭB）を計算し（ＳＴ７Ｂｂ１）、合計値ｈ’を仮署名生成部１９に出力する。
【０１４０】
以下、前述同様に、署名生成装置ＳgＢでは、ステップＳＴ８Ｂｂ〜ＳＴ１０Ｂの処理を実行することにより、第２コミット情報の第１部分ｈ1’と第２仮署名値σBとを算出し、得られる第２仮署名（ＭB,ｈ1’,ｈ2’,σB）を署名生成装置ＳgＡに送信して待機する。
【０１４１】
署名生成装置ＳgＡでは、署名生成装置ＳgＢから入出力部１６を介して第２仮署名（ＭB,ｈ1’,ｈ2’,σB）を受けると（ＳＴ９Ａ）、仮署名検証部２０が、秘密情報の検証式ｈ2’＝ｈ2＝Ｇ（ｋ）及び第２検証式ｈ1’＋ｈ2’＝Ｈ（ｇ{σ_B}ｐB{h’_1 h’_2}  ｍｏｄ  ｐ，ＭB）が成り立つか否かにより第２仮署名を検証する（ＳＴ１０Ａａ１）。各検証式が成り立たない場合は第２仮署名を棄却して処理を停止する。各検証式が成り立つ場合には、秘密情報ｋを署名生成装置ＳgＢに送信し、第２仮署名（ＭB,ｈ1’,ｈ2’,σB,ｋ）を署名者Ｂから受け付けた第２署名として出力し（ＳＴ１２Ａ）、又はメモリ１１に保存して、処理を停止する。
【０１４２】
署名生成装置ＳgＢは、署名生成装置から秘密情報ｋを受け取った後（ＳＴ１１Ｂ）、ｈ2＝Ｇ（ｋ）が成り立つか否かを検査し（ＳＴ１２Ｂ）、成り立たない場合は第１仮署名を棄却して処理を停止する。検証式が成り立つ場合には、第１仮署名（ＭA,ｈ1,ｈ2,σA,ｋ）を署名者Ｂから受け付けた第１署名として出力し（ＳＴ１３Ｂ）、又はメモリ１１に保存して、処理を停止する。
【０１４３】
（署名検証処理）
署名検証装置ＶrＣは、図１１に示すように、例えば署名生成装置ＳgＢから第１署名（ＭA,ｈ1,ｈ2,σA,ｋ）及び公開情報ｐ，ｑ，Ｈ，Ｇ，ｐAを入手し（ＳＴ７１）、署名（ＭA,ｈ1,ｈ2,σA,ｋ）及び公開情報ｐ，ｑ，Ｈ，Ｇ，ｐAをメモリ１１に書き込む。ここで、署名検証装置ＶrＣは、第１署名を署名生成装置ＳgＢから直接受信してもよく、第三者を経由して受信してもよい。
【０１４４】
ステップＳＴ７１において、署名検証装置ＶrＣは、予め公開情報及び／又は公開鍵ｐAをメモリ３１等の記憶領域に保存してもよい。署名検証装置ＶrＣでは、判定部３４が、第１署名が第１仮署名（ＭA, ｈ1, ｈ2, σA）と秘密情報ｋから構成されているか否かを判定する（ＳＴ７２）。判定の結果、否の場合、署名交換が正しく実行されていない、あるいは署名が流通される過程で情報にエラーが生じたため、署名を棄却する（ＳＴ７５）。
【０１４５】
ステップＳＴ７２の判定の結果、正しく構成されている場合、署名検証部３７は、Ｇ，Ｈ関数演算部３５，３６を用い、秘密情報の検証式ｈ2＝Ｇ（ｋ）及び第１署名検証式ｈ1＋ｈ2＝Ｈ（ｇ{σ_A}ｐA{ｈ_1  ｈ_2}  ｍｏｄ  ｐ，ＭA）が成り立つか否かを検証する（ＳＴ７３）。なお、第１署名検証式は、署名生成装置ＳgＢの公開鍵ｐBが不要であり、プライバシの保護が図られている。
【０１４６】
ステップＳＴ７３の検証の結果、２つの検証式が成り立つ場合には、署名検証装置ＶrＣは第１署名を受理し（ＳＴ７４）、否の場合には第１署名を棄却する（ＳＴ７５）。
【０１４７】
なお、署名検証装置ＶrＣは、図１２に示すように、署名生成装置ＳgＡから第２署名（ＭB,ｈ1’,ｈ2’,σB,ｋ）を受けた場合も同様に検証する。
【０１４８】
上述したように本実施形態によれば、第１及び第２コミット合計値ｈ，ｈ’を第１及び第２公開鍵ｐA,ｐBを用いずに得ることから、第１仮署名を検証する第１検証式では第２公開鍵ｐBが不要となり、第２仮署名を検証する第２検証式では第１公開鍵ｐAが不要となる。
【０１４９】
すなわち、署名生成装置ＳgＢは、第１検証式を有する署名検証装置ＶrＣに対し、第２公開鍵ｐBを渡さずに第１署名の検証を依頼可能となる。同様に、署名生成装置ＳgＡは、第２検証式を有する署名検証装置ＶrＣに対し、第１公開鍵ｐAを渡さずに第２署名の検証を依頼可能となる。
【０１５０】
このように本実施形態は、公平な署名交換方法において、第１及び第２コミット合計値ｈ，ｈ’を第１及び第２公開鍵ｐA,ｐBを用いずに得る構成により、第１又は第２公開鍵ｐA,ｐBを渡さずに各署名の検証を依頼可能としたので、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【０１５１】
次に、以上のような本実施形態の効果について補足的に説明する。  
第１の実施形態及び非特許文献１において、署名生成装置ＳgＡが署名生成時に署名者Ｂの公開鍵ｐBを用いる理由は、仮署名の持ち逃げを防ぐためである。
【０１５２】
具体的には、仮署名の生成にはリング署名の概念が利用される。リング署名では、複数の署名者Ｐ，Ｑがいる場合、署名者Ｐが署名者Ｐの秘密鍵と署名者Ｑの公開鍵を利用して署名を生成する。
【０１５３】
このとき、検証者Ｃは、署名者Ｐの公開鍵と署名者Ｑの公開鍵を用いて署名を検証するが、署名者Ｐ，Ｑのいずれか一方が署名を生成した旨を検証できるが、署名者Ｐ，Ｑのどちらが署名を生成したかを特定できない。
【０１５４】
第１の実施形態及び非特許文献１においては、署名生成装置ＳgＡが署名者Ａの秘密鍵ｓAと署名者Ｂの公開鍵ｐBを利用してリング署名を生成して仮署名とすることで、仮に署名者Ｂが署名者Ａの仮署名を持ち逃げして、第三者に提示しても署名としての効力を持たせることができない。
【０１５５】
理由は、署名生成装置ＳgＡが生成した仮署名は署名生成装置ＳgＡ又は署名生成装置ＳgＢのどちらかが署名を生成した事実のみを保証するだけであり、署名者Ａの仮署名を提示された検証者が、該仮署名を署名生成装置ＳgＡが生成した仮署名であるか署名生成装置ＳgＢが生成した仮署名であるかを区別できないためである。
【０１５６】
なお、第１の実施形態及び非特許文献１で示される方法では、秘密情報ｋを開示することで、仮署名が署名生成装置ＳgＡと署名生成装置ＳgＢのどちらで生成されたかを特定可能としている。
【０１５７】
ここで、上述のように署名者Ｂが署名者Ａの仮署名を第三者（検証者Ｃ）に提示する場面を考える。このとき、仮に検証者Ｃが仮署名を署名生成装置ＳgＡが生成したものであると信用しても、署名者Ｂが秘密情報ｋを提示できないため、第１の実施形態によれば署名が受理されない。
【０１５８】
従って、仮署名と秘密情報の組で署名を検証するように運用上の規程を入れれば、必ずしも仮署名にリング署名の概念を用いる必要はない。
【０１５９】
例えば、上述した例のように、電子現金の発行フェーズを考える。電子現金発行依頼者を署名者Ａとし、電子現金発行者を署名者Ｂとして、署名者Ａが発行した引落し同意に関する仮署名を署名者Ｂが持ち逃げして仮署名を担保に現金を引き落としたとする。
【０１６０】
後日、署名者Ａが署名者Ｂの不正を法的な機関に主張した場合、署名者Ｂは秘密情報ｋを知らないため、仮署名と秘密情報の組を提示できず、引落しの事実を正当化できない。
【０１６１】
このように、運用上の規程により仮署名の匿名性を必ずしも用いない場合には、第１の実施形態をより簡素化することが可能となる。例えば、署名生成装置ＳgＡは署名者Ｂの公開鍵ｐBを用いずに、秘密情報ｋから計算されるコミット情報ｈ２と自己の秘密鍵ｓAから仮署名を生成できる。また、署名者Ｂが署名者Ａから受けた第１署名を署名検証装置ＶrＣに渡した際に、署名検証装置ＶrＣは、署名者Ｂの公開鍵ｐBを用いずに、第１署名を検証することができる。
【０１６２】
（第５の実施形態）
次に、本発明の第５の実施形態に係る署名交換システムについて図１３乃至図１６を用いて説明する。  
本実施形態は、第１の実施形態の変形例であり、署名生成装置ＳgＡにおいては、図１３に示すように、前述した図３と比べ、ステップＳＴ６Ａａ及びＳＴ１０Ａａをそれぞれ従来のＳＴ６Ａ及びＳＴ１０Ａに戻すと共に、ステップＳＴ５１Ａの第１変形値Ｙ’をＹ’＝ｐA{1+r’/h’_2} ｍｏｄ  ｐとして算出するように当該ＳＴ５１Ａを変形してなるＳＴ５１Ａａ２を実行する構成となっている。
【０１６３】
同様に、署名生成装置ＳgＢにおいては、図１４に示すように、前述した図４と比べ、ステップＳＴ４Ｂｂ及びＳＴ８Ｂｂをそれぞれ従来のＳＴ４Ｂ及びＳＴ８Ｂに戻すと共に、ステップＳＴ５１Ｂの第２変形値ＹをＹ＝ｐB{1+r/h_2} ｍｏｄ  ｐとして算出するように当該ＳＴ５１Ｂを変形してなるＳＴ５１Ｂｂ２を実行する構成となっている。
【０１６４】
署名検証装置ＶrＣにおいては、図１５に示すように、前述した図５と比べ、ステップＳＴ６３の第１署名検証式ｈ1＋ｈ2をｈ1＋ｈ2＝Ｈ（ｇ{σ’_A} ｐA{h_1} Ｙ{h_2}，ＭA）とするように当該ＳＴ６３を変形したステップＳＴ６３ａ２を実行する構成となっている。
【０１６５】
また、署名検証装置ＶrＣにおいては、図１６に示すように、前述した図６と比べ、ステップＳＴ６３’の第２署名検証式ｈ1’＋ｈ2’をｈ1’＋ｈ2’＝Ｈ（ｇ{σ’_B} ｐB{h’_1} Ｙ{h’_2}，ＭB）とするように当該ＳＴ６３’を変形したステップＳＴ６３ｂ２’を実行する構成となっている。
【０１６６】
以上のような構成によれば、第１の実施形態と同様に、公平な署名交換方法において、第１及び第２署名者関連値に代えて第１及び第２変形値Ｙ’，Ｙにより署名を検証可能としたので、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【０１６７】
（第６の実施形態）
次に、本発明の第６の実施形態に係る署名交換システムについて図１７及び図１８を用いて説明する。  
本実施形態は、第１の実施形態の変形例であり、仮署名を変形し、各値Ｙ’，σB’及び各値Ｙ，σA’を得る際に、自らの秘密鍵ｓA，ｓBを利用しない構成となっている。
【０１６８】
これに伴い、秘密鍵ｓA，ｓBを知らない第三者も署名の変換が可能となり、署名変形部２１を独立させて第三者用署名変形装置を構成することも可能となる。但し、第三者による署名変形を許可しない場合、後述するが、署名を提示した装置に対し、ゼロ知識証明により、変形後の第１又は第２変形値Ｙ’，Ｙのｇに対する離散対数｛ｓA＋ｒ’｝又は｛ｓB＋ｒ｝を知っていることを証明させる。これにより、署名検証装置ＶrＣは、離散対数を知らない第三者から提示された署名を棄却すればよい。
【０１６９】
さて具体的には、署名生成装置ＳgＡにおいては、図１７に示すように、前述した図３と比べ、ステップＳＴ６Ａａ及びＳＴ１０Ａａをそれぞれ従来のＳＴ６Ａ及びＳＴ１０Ａに戻すと共に、ステップＳＴ５１Ａの第１変形値Ｙ’及び第２署名値σB’をそれぞれＹ’＝ｐAｇ{r’} ｍｏｄ  ｐ、及びσB’＝σB−ｒ’ｈ2’ ｍｏｄ  ｑとして算出するように当該ＳＴ５１Ａを変形してなるＳＴ５１Ａａ３を実行する構成となっている。
【０１７０】
同様に、署名生成装置ＳgＢにおいては、図１８に示すように、前述した図４と比べ、ステップＳＴ４Ｂｂ及びＳＴ８Ｂｂをそれぞれ従来のＳＴ４Ｂ及びＳＴ８Ｂに戻すと共に、ステップＳＴ５１Ｂの第２変形値Ｙ及び第１署名値σA’をそれぞれＹ＝ｐBｇ{r} ｍｏｄ  ｐ、及びσA’＝σA−ｒ ｈ2 ｍｏｄ  ｑとして算出するように当該ＳＴ５１Ｂを変形してなるＳＴ５１Ｂｂ３を実行する構成となっている。
【０１７１】
署名検証装置ＶrＣは、前述した図１５及び図１６に示した処理を実行する構成となっている。
【０１７２】
以上のような構成によれば、第１の実施形態と同様に、公平な署名交換方法において、第１及び第２署名者関連値に代えて第１及び第２変形値Ｙ’，Ｙにより署名を検証可能としたので、匿名性が要求される場合であっても、公平な署名交換を実現できる。
【０１７３】
また、前述した通り、署名者Ｂ以外の第三者であっても、署名生成装置ＳgＡが署名生成装置ＳgＢとの間で交換した署名を変形することにより、上述した署名検証に合格する署名を作成できる。なお、第三者による変形を許さない場合、署名検証装置ＶrＣは、変形された署名を提示した装置ＳgＸと通信し、該装置ＳgＸが第２変形値Ｙのｇに対する離散対数｛ｓB＋ｒ｝を知っているか否かをゼロ知識対話証明により判断する。これにより、該装置ＳgＸが離散対数を知っていると判断した場合、署名検証装置ＶrＣは、該装置ＳgＸが署名生成装置ＳgＢであることと、署名生成装置ＳgＢが署名変換をしたことを確認できる。
【０１７４】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１７５】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１７６】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１７７】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０１７８】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１７９】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１８０】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１８１】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１８２】
【図１】本発明の第１の実施形態に係る署名生成装置の構成を示す模式図である。
【図２】同実施形態における署名検証装置の構成を示す模式図である。
【図３】同実施形態における署名生成処理を説明するためのフローチャートである。
【図４】同実施形態における署名生成処理を説明するためのフローチャートである。
【図５】同実施形態における署名検証処理を説明するためのフローチャートである。
【図６】同実施形態における署名検証処理を説明するためのフローチャートである。
【図７】本発明の第３の実施形態に係る署名生成装置に保存される選択テーブルの構成を示す模式図である。
【図８】本発明の第４の実施形態に係る署名生成装置の構成を示す模式図である。
【図９】同実施形態における署名生成処理を説明するためのフローチャートである。
【図１０】同実施形態における署名生成処理を説明するためのフローチャートである。
【図１１】同実施形態における署名検証処理を説明するためのフローチャートである。
【図１２】同実施形態における署名検証処理を説明するためのフローチャートである。
【図１３】本発明の第５の実施形態における署名生成処理を説明するためのフローチャートである。
【図１４】同実施形態における署名生成処理を説明するためのフローチャートである。
【図１５】同実施形態における署名検証処理を説明するためのフローチャートである。
【図１６】同実施形態における署名検証処理を説明するためのフローチャートである。
【図１７】本発明の第６の実施形態における署名生成処理を説明するためのフローチャートである。
【図１８】同実施形態における署名生成処理を説明するためのフローチャートである。
【図１９】従来の署名生成処理を説明するためのフローチャートである。
【図２０】従来の署名生成処理を説明するためのフローチャートである。
【図２１】従来の署名検証処理を説明するためのフローチャートである。
【図２２】一般的な電子現金システムの構成例を示す模式図である。
【図２３】従来の署名生成処理に署名変形を加えた署名生成処理を説明するためのフローチャートである。
【図２４】図２３に示される処理で生成された署名の検証処理を説明するためのフローチャートである。
【符号の説明】
【０１８３】
１１，３１…メモリ、１２…秘密鍵メモリ、１３，３２…演算器、１４…乱数生成部、１５…乱数メモリ、１６，３３…入出力部、１７，３５…Ｇ関数演算部、１８，３６…Ｈ関数演算部、１９…仮署名生成部、２０…仮署名検証部、２１…署名変形部、２２，３８…制御部、ＳgＡ，ＳgＢ…署名生成装置、ＶrＣ…署名検証装置。
【図１】
2006217506.tif 000003
【図２】
2006217506.tif 000004
【図３】
2006217506.tif 000005
【図４】
2006217506.tif 000006
【図５】
2006217506.tif 000007
【図６】
2006217506.tif 000008
【図７】
2006217506.tif 000009
【図８】
2006217506.tif 000010
【図９】
2006217506.tif 000011
【図１０】
2006217506.tif 000012
【図１１】
2006217506.tif 000013
【図１２】
2006217506.tif 000014
【図１３】
2006217506.tif 000015
【図１４】
2006217506.tif 000016
【図１５】
2006217506.tif 000017
【図１６】
2006217506.tif 000018
【図１７】
2006217506.tif 000019
【図１８】
2006217506.tif 000020
【図１９】
2006217506.tif 000021
【図２０】
2006217506.tif 000022
【図２１】
2006217506.tif 000023
【図２２】
2006217506.tif 000024
【図２３】
2006217506.tif 000025
【図２４】
2006217506.tif 000026