(57)【特許請求の範囲】
【請求項１】
Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqj に対してＧj（ｘ）はインデックスがｘであるようなＧjの元を表すものとし、秘密鍵ｘjに対してｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵としｆjを、或る環Ｇj上の落とし戸付き一方向性置換関数とし、ｆj-1を、ｆjの逆算とし、ｆjを公開鍵とし、ｆj-1を一方向性置換型の秘密鍵とし、
Ｌを、公開鍵（ｙj,Ｇj）或いは（ｆj,Ｇj）を合計ｎ個含む公開鍵のリストとし、リストに含まれる或る一つの公開鍵に対応する秘密鍵を使用して文書ｍに対する署名を生成する署名生成方法において、
離散対数型の公開鍵における各Ｇjは、ｙjに対して、
１.証明者はランダムなインデックスｗをＺqj から選んで、ｚj：＝Ｇj（ｗ）を検証者へ送り、
２.検証者はランダムなチャレンジｃjをＺqjから選んで、証明者へ送り、
３.証明者は回答ｓjを回答計算式ｓj＝Ｆ（ｗ,ｘj,ｃj,ｑj ）に沿って計算して検証者へ送り、
４.検証者は、検証値計算式Ｒj に対してｚj＝Ｒj（ｙj,ｓj,ｃj,Ｇj）が成り立つか否かを調べ、成り立つならば受理し、そうでなければ拒否する、
なる３交信ゼロ知識証明が存在する群とし、
二項演算ａ(+)jｂとａ(-)jｂはそれぞれＧj 上での加減算ａ＋ｂとａ−ｂの結果を表すものとし、ａ‖ｂはａとｂのビット結合演算とし、
Ｈj を一方向性ハッシュ関数とし、Ｌ中のｊ番目の公開鍵が離散対数型の場合には出力域がＺqj であり、一方向性置換型の場合には出力域がＧjであるものとし、
署名対象文書ｍ、公開鍵リストＬ、および、ｌに含まれるｎ個の公開鍵の内、或るｋ番目（但し、リスト中の公開鍵は番目０からｎ−１番目までとする）の公開鍵に対応する秘密鍵を入力とし、
リスト中の公開鍵が離散対数型か一方向性置換型かを判別する公開鍵判別手段と、乱数生成手段と、群要素計算手段と、一方向性置換計算手段と、一方向性置換逆算手段と、加減算手段と、検証値計算手段と、回答計算手段と、ハッシュ手段と、
ループ変数初期化手段、ループ変数更新手段、ループ終了判断手段とからなるループ制御手段とを備え、
Step１  ・ Ｌのｋ番目（但し、リスト中の公開鍵は番目０からｎ−１番目までとする）の公開鍵が離散対数型の時は乱数生成手段によりＺqkからαを選び、群要素計算手段によりβ＝Ｇk（α）を計算し、
・Ｌのｋ番目の公開鍵が一方向性置換型の時はＧkから乱数βを選び、ハッシュ手段によりｃk+1＝Ｈk+1（Ｌ‖ｍ‖β）を計算するステップと、
Step２  ｊ＝ｋ＋１,...,ｎ−１,０,....,ｋ−１について、
・Ｌのｊ番目の公開鍵が離散対数型のとき乱数生成手段によりｓj∈Ｚqjを生成し、検証値計算手段によりｚj＝Ｒj（ｓj,ｃj,ｙj,Ｇj）を計算し、
・Ｌのｊ番目の公開鍵が一方向性置換型のとき乱数生成手段によりｓj∈Ｇj を生成し、加減算手段によりｚj＝ｃj(+)jｆj（ｓj）を計算し、ハッシュ手段によりｃj+1 mod n：＝Ｈj+1 mod n（Ｌ‖ｍ‖ｚj ）を計算するステップと、
Step３  ・Ｌのｋ番目の公開鍵が離散対数型のとき回答計算手段によりｓk＝Ｆk（α,ｃk,ｘk,Ｇk）を計算し、
・Ｌのｋ番目の公開鍵が一方向性置換型のとき一方向性置換逆算手段によりｓk＝ｆk-1（β(-)kｃk）を計算するステップと、
Step４  ・署名（ｃ0,ｓ0,ｓ1,......,ｓn-1）を出力するステップ、
からなることを特徴とする署名生成方法。
【請求項２】
請求項１に記載される署名生成方法により生成された文書ｍ、公開鍵リストＬに対する署名（ｃ0,ｓ0,ｓ1,......,ｓn-1）を検証する署名検証方法において、
公開鍵判別手段と、一方向性置換計算手段と、加減算手段と、検証値計算手段と、ハッシュ手段と、
ループ変数初期化手段、ループ変数更新手段、ループ終了判断手段とからなるループ制御手段とを備え、
Step１  ループ変数初期化手段によりｊ＝０とし、ループ変数更新手段、ループ終了判断手段により、ｊ＝０,.....,ｎ−１について、
・Ｌのｊ番目の公開鍵が離散対数型のとき検証値計算手段によりｚj＝Ｒj（ｓj,ｃj,ｙj,Ｇj）を計算し、
・Ｌ のｊ番目の公開鍵が一方向性置換型のとき一方向性関数計算手段によりｆj（ｓj）を計算し、加減算手段によりｚj＝ｃj(+)jｆj（ｓj）を計算し、ハッシュ手段によりｃj+1＝Ｈj+1 mod n（Ｌ‖ｍ‖ｚj ）を順次計算する手順を繰り返すステップと、
Step２  ｃn、とｃ0を比較手段により比較し、これらが等しいならば、署名を合格とし、そうでなければ不合格とするステップ、
からなることを特徴とする署名検証方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、署名生成方法、および署名検証方法に関し、特に、公開鍵の種別を離散対数型或いは一方向性置換型の何れか一方に限定することなく両者が混在する署名生成方法、および署名検証方法に関する。
【０００２】
【従来の技術】
従来例を図を参照して説明する。
第１の従来の技術として、Cramer等による1-out-of-n離散対数型署名方法（Proofs  of  Partial  Knowledge  and  Simplified  Design  of  Witness  Hiding  Proofs"Crypto'94,LNCS839,pp.174-187,Springer-Verlag,1994）について説明する。
ｐi、ｑiをそれぞれ大きな素数とし、ｑiはｐiを割り切るものとする。ｇi をｐiの位数ｑiの部分群の生成源とする。ｘi∈Ｚqiを秘密鍵、ｙi＝ｇixi ｍｏｄ ｐiをｇi、ｑi、ｐiと共に公開鍵とする。
【０００３】
ｎ個の公開鍵（ｙj、ｇj、ｑj、ｐj）、ｊ＝０,......,ｎ−１の内、或るｙiに関して、対応する秘密鍵ｘi を知る署名者は、以下の手順で文書ｍに対する署名を生成する。ｌ（Ｌの小文字）はｎのｑj の内の最も大きいもののビット数を表すものとし、Ｈをｌビットの出力域を持つハッシュ関数とする。集合αから一つの元βをランダムに選ぶ行為をβ←αと書くことにする。
１.ｊ＝０,...,ｎ−１までのｊ≠ｉについて以下を繰り返す。
（ａ）ｓj←Ｚqj
（ｂ）ｃj←｛０,１｝l
（ｃ）ｚj：＝ｇjsjｙjcj ｍｏｄ ｐj
２.ｒi←Ｚqi
３.ｚi：＝ｇiri ｍｏｄ ｐi
４.ｃk+1＝Ｈk+1（ｚ0‖ｚ2‖・・・‖ｚn-1‖ｍ）
５.ｃi＝ｃ(XOR)ｃ0(XOR)・・・(XOR)ｃi-1(XOR)ｃi+1(XOR)・・・ｃn
６.ｓi：＝ｒi−ｃi・ｘi ｍｏｄ ｑi
７.（ｃ0,ｓ0,ｃ1,ｓ1,・・・,ｃn-1,ｓn-1）を出力。
【０００４】
文書ｍに対する署名（ｃ0,ｓ0,ｃ1,ｓ1,・・・・,ｃn-1,ｓn-1）は以下の式が成り立つとき、正しい署名と認める。
ｃ0(XOR)・・・(XOR)ｃn-1
＝Ｈ（ｇ0s0ｙ0c0 ｍｏｄ ｐ0‖・・・・・・‖ｇn-1sn-1ｙn-1cn-1 ｍｏｄ ｐn-1）
但し、(XOR)はビット毎の排他的論理和を表すものとする。
以上の従来例によれば、署名の受信者は、署名者がどの公開鍵に対応する秘密鍵を保持しているのかを見分けることはできない。従って、独立に生成された、他人の公開鍵と署名者自身の公開鍵に基づいて上記の方法で署名を生成すると、検証者にとっては、誰が生成した署名なのか判断できないことになり、署名者のプライバシーが守られ、グループの代表者としての署名を生成したことになる。
【０００５】
同様の特性を有する第２の従来の技術として、Rivest,Shamir,TaumanによるRing型署名（How to Leak a Secret.Asiacrypt 2001,LNCS 2248,pp552-565,  Springer-Verlag,2001）を説明する。
｛０,１｝lの入出力域を持つ落とし戸付き一方向性置換関数をｇ0,・・・,ｇn-1とする。ｌは充分に大きい例えば１０２４程度の数値とする。Ｈをハッシュ関数、Ｅ、Ｄをそれぞれ共通鍵暗号の暗号化関数、復号関数とし、(XOR)をビット毎の排他的論理和とする。署名者Ｐiはｇiに対する落とし戸情報（秘密鍵）を保持しており、ｇi-1を計算することができるものとする。
【０００６】
文書ｍに対する署名は、以下の手順で生成する。
１.Ｋ：＝Ｈ（ｍ）
２.ｌビットの乱数ｚ0を生成する。
３.ｊ＝０,・・・,ｉ−１まで以下を繰り返す。
（ａ）ｌビットの乱数ｒjを生成する。
（ｂ）ｙj：＝ｇj（ｒj）
（ｃ）ｚj′：＝ｚj(XOR)ｙj
（ｄ）ｚj+1：＝Ｅk（ｚj′）
４.ｚ′n-1＝Ｄk（ｚ0）
５.ｊ＝ｎ−１,・・・,ｉ＋１まで以下を繰り返す。
（ａ）ｌビットの乱数ｒjを生成する。
（ｂ）ｙj：＝ｇj（ｒj）
（ｃ）ｚj：＝ｚj′(XOR)ｙj
（ｄ）ｚ′j-1＝Ｄk（ｚj）
６.ｙi：＝ｚi(XOR)ｚi′
７.ｒi：＝ｇi-1（ｙi）
８.（ｚ0,ｒ0,ｒ1,・・・,ｒn-1）を出力。
【０００７】
文書ｍに対する署名（ｚ0,ｒ0,ｒ1,・・・,ｒn-1）は以下の手順で検証する。
１.Ｋ：＝Ｈ（ｍ）
２.ｊ＝０,・・・,ｎ−１まで以下を繰り返す。
（ａ）ｙj：＝ｇj（ｒj）
（ｂ）ｚj′：＝ｚj(XOR)ｙj
（ｃ）ｚj+1：＝Ｅk（ｚj′）
３.ｚn＝ｚ0ならば合格。
【０００８】
【発明が解決しようとする課題】
以上の従来例は、それぞれ、Schnorr 署名の様な離散対数型の鍵の集合或いはＲＳＡの様な一方向性置換型の鍵の集合のみを対象としているので、一般的に、これらの異なる種類の鍵が混在する様な鍵集合に対しては署名を構成することができない。
この発明は、離散対数問題と一方向性置換の何れの形式の鍵をも含めることのできる一般的な鍵集合に対して、1-out-of n型の署名をすることができる署名生成方法を提供するものである。
【０００９】
【課題を解決するための手段】
Ｇjを可換群とし、その位数をｑj とする。Ｇj(ｘ)はインデックスがｘ∈ＺqjであるようなＧjの元を表すものとする。また、Ｇj(ｘ)はｘからそのような元を計算する行為をも表すものとする。ｙj＝Ｇj（ｘj）とし、ｙj、Ｇj を公開鍵、ｘjを秘密鍵とする。可換群Ｇjに対して、以下に示す、ｘj の知識のゼロ知識証明を構成することができる。
１.証明者はランダムなインデックスｗをＺqjから選んで、ｚj：＝Ｇj（ｗ）を検証者へ送る。
２.検証者はランダムなチャレンジｃjをＺqjから選んで、証明者へ送る。
３.証明者は回答ｓjを回答計算式Ｆjに従ってｓj＝Ｆj（ｗ,ｃ,ｘj,Ｇj）と計算して検証者へ送る。
４.検証者は、検証値計算式Ｒj に対してｚj＝Ｒj（ｓ,ｃ,ｙj,Ｇj）が成り立つか否かを調べ、成り立つならば受理し、そうでなければ拒否する。
【００１０】
ｆjを落とし戸付き一方向性置換関数とし、その入出力域をＧj とする。ｆj-1をｆjの逆算とする。即ち、全てのｘ∈Ｇjに対して、ｆj-1（ｆj（ｘ））＝ｘが成り立つ。Ｇj は少なくとも環であるものとし、二項演算ａ(+)jｂとａ(-)jｂはそれぞれＧj 上での加減算ａ＋ｂとａ−ｂの結果を表すものとし、ａ‖ｂはａとｂのビット結合を示す。ｆjを公開鍵とし、ｆj-1を秘密鍵とする。
Ｌを、公開鍵（ｙj,Ｇj）および（ｆj,Ｇj）を合計ｎ個含む公開鍵のリストとする。それぞれ幾つづつ含むかは任意である。リストＬにおいては、０番目からｎ−１番目の公開鍵があるものとする。記号Ｌ［ｊ］は記号ＤまたはＴを表し、Ｌ［ｋ］＝Ｄの場合はリストＬ中のｊ番目の公開鍵が離散対数型のｙj であることを示し、Ｌ［ｋ］＝Ｔの場合はリストＬ中のｊ番目の公開鍵が一方向性置換型のｆjであることを示すものとする。
Ｈj を一方向性ハッシュ関数とし、Ｌ［ｋ］＝Ｄなるｊについては、出力域がＺqjであり、Ｌ［ｋ］＝Ｔなるｊについては、出力域がＧjであるものとする。
【００１１】
Ｌに含まれるｎ個の公開鍵の内、或るｋ番目の公開鍵に対応する秘密鍵を知る署名者は、以下の手順で文書ｍに対する署名を生成する。以下で、ｕ∈Uｖ は、集合ｖから要素をランダムに選択し、選択した要素をｕと呼ぶことを意味する。また、添え字は全て ｍｏｄ ｎを取るものとする。即ち、ｊ＋１がｎとなった場合は、これを０と見なす。
Step１  Ｌ［ｋ］＝Ｄのとき：α∈UＺqk、β＝Ｇk（α）
Ｌ［ｋ］＝Ｔのとき：β∈UＧk
とし、ｃk+1＝Ｈk+1（Ｌ‖ｍ‖β）を計算する。
Step２  ｊ＝ｋ＋１,...,ｎ−１,０,....,ｋ−１まで以下を繰り返す。
Ｌ［ｊ］＝Ｄのとき：ｓj∈UＺqj、ｚj＝Ｒj（ｓj,ｃj,ｙj,Ｇj）
Ｌ［ｊ］＝Ｔのとき：ｓj∈UＧj、ｚj＝ｃj(+)jｆj（ｓj）
とし、ｃj+1＝Ｈj+1（Ｌ‖ｍ‖ｚj）を計算する。
Step３  以下を計算する。
Ｌ［ｊ］＝Ｄのとき：ｓk＝Ｆ（α,ｃk,ｘk,Ｇk）
Ｌ［ｊ］＝Ｔのとき：ｓk＝ｆk-1（β−ｃk）
Step４  署名（ｃ0,ｓ0,ｓ1,・・・,ｓn-1）を出力。
【００１２】
文書ｍに対する署名（ｃ0,ｓ0,ｓ1,・・・,ｓn-1）は以下の手順で検証する。
Step１  ｊ＝０,....,ｎ−１まで以下を繰り返す。
Ｌ［ｊ］＝Ｄのとき：ｚj＝Ｒj（ｓj,ｃj,ｙj,Ｇj）
Ｌ［ｊ］＝Ｔのとき：ｚj＝ｃj(+)jｆj（ｓj）
ｃj+1：＝Ｈj+1（Ｌ‖ｍ‖ｚj）を計算する。
Step２  ｃn＝ｃ0ならば正当な署名と見なす。
上述の通りにして、前段の出力値ｚjから後段のチャレンジｃj+1を計算する際に、後段のチャレンジとして適切な出力域をもつハッシュ関数によりこれを計算するため、後段で使用する公開鍵が離散対数型か一方向性関数型に関わらず、適切な大きさのチャレンジを生成することができる。
【００１３】
【発明の実施の形態】
以下、この発明の実施の形態を図の実施例を参照して説明する。
図１を参照してこの発明の署名生成手順を説明するに、
公開鍵種別初期化手段１１と、公開鍵種別連鎖処理手段１２と、公開鍵種別リング接合手段１３と、
ループ変数初期化手段１４１、ループ変数更新手段１４２、ループ終了判断手段１４３とからなるループ制御手段１４とを備えて署名生成を実施する。
図２を参照するに、公開鍵種別初期化手段１１は、公開鍵判別手段１１１と、乱数生成手段１１２、１１２’と、群要素計算手段１１３と、ハッシュ手段１１４とを備える。
【００１４】
図３を参照するに、公開鍵種別連鎖処理手段１２は公開鍵判別手段１２１と、乱数生成手段１２２、１２２’と、検証値計算手段１２３と、一方向性置換計算手段１２４と、加減算手段１２５と、ハッシュ手段１２６を備える。
図４を参照するに、公開鍵種別リング接合手段１３は、公開鍵判別手段１３１と、回答計算手段１３２と、加減算手段１３３と、一方向性置換逆算計算手段１３４を備える。
図５を参照してこの発明の署名検証手順を説明するに、
図３の公開鍵種別連鎖処理手段１２と、比較手段１５と、ループ変数初期化手段１４１、ループ変数更新手段１４２、ループ終了判断手段１４３とからなるループ制御手段１４とを備えて署名検証を実施する。
【００１５】
（構成の説明）
離散対数を構成する群として、ｐi を素数とする乗法群Ｚpiをとり、落とし戸付き一方向性置換関数としてＲＳＡ関数を用いる場合の実施例を説明する。
ｐi、ｑiをそれぞれ大きな素数とし、ｑiはｐiを割り切るものとする。ｇi をｐiの位数ｑiの部分群の生成源とする。ｘi∈Ｚqiを秘密鍵、ｙi＝ｇixi ｍｏｄ ｐiをｇi、ｑi、ｐiと共に公開鍵とする。
（ｅj,Ｎj）をＲＳＡ暗号の公開鍵、ｄjを秘密鍵とする。即ち、すべてのα∈Ｚ*Njに対して、（αej）dj ｍｏｄ Ｎj＝αが成り立つ。
【００１６】
（動作の説明）
図６を参照して、署名生成手順の動作を説明する。図６は先の図１に対応する図であり、図６における図７、図８、図９はそれぞれ図２、図３、図４に対応する図である。
入力として、ｎ個の公開鍵を含むリストＬと、或る公開鍵に対応する秘密鍵および署名対象の文書ｍを得る。公開鍵の種別をＤとＴで表し、それぞれ離散対数型、一方向置換型を表わすものとする。リストＬ中のｊ番目の公開鍵の種別をＬ［ｊ］と表す。入力の秘密鍵に対応する公開鍵がリストＬ中でｋ番目に含まれているものとする。Ｌ［ｋ］＝Ｄの場合には秘密鍵はｘk であり、Ｌ［ｋ］＝Ｔの場合にはｄk である。入力に対して、先ず、図７に示す公開鍵種別初期化手順を実行する。次に、ループ変数初期化手段１４によりループ変数ｊをｋ＋１（ｍｏｄ ｎ） に設定する。次に、図８に示す公開鍵種別連鎖処理手順を実行し、ループ変数更新手順によりｊをｊ＋１（ｍｏｄ ｎ） に設定し、ループ終了判断手段により、ｊがｋと等しいか否かを判定する。等しくない場合には、公開鍵種別連鎖処理手順の実行に戻り、等しい場合には、図９に示す公開鍵種別リング接合手順を実行し、署名を出力して停止する。
【００１７】
以下、手順を図７〜図９を参照して具体的に説明する。図７の公開鍵種別初期化手順は、Ｌ、ｍおよびｋを入力とし、先ず、公開鍵判別手段１１１により、入力秘密鍵に対応する公開鍵がＤとＴの何れであるかを判別する。Ｄの場合には、乱数生成手段１１２により、Ｚqkからランダムにｗを選び、群要素計算手段１１３によりｚk＝ｇkw ｍｏｄ ｐkを計算する。Ｔの場合は、乱数生成手段１１２’により、Ｚ*Nk からランダムにｚkを選ぶ。得られたｚkを、Ｌ、ｍと共にハッシュ手段１１４によりハッシュし、その結果をｃk+1とする。
図８の公開鍵種別連鎖処理手順では、Ｌ、ｍ、ｊおよびｃjを入力とし、先ず、公開鍵判別手段１２１により、処理対象としているリストＬ中のｊ番目の公開鍵がＤとＴの何れであるかを判別する。Ｄの場合には、乱数生成手段１２２によりＺqjからランダムにｓj を選び、検証値計算手段１２３によりｚj＝ｇjsjｙjcj ｍｏｄ ｐj を計算する。Ｔの場合には、乱数生成手段１２２’により、Ｚ*Njからランダムにｓjを選び、これを一方向性置換計算手段１２４に入力してｙj＝ｓjej ｍｏｄ Ｎjを計算し、ｙj、ｃj、Ｎjを加減算手段１２５へ入力して、ｚj＝ｙj＋ｃj ｍｏｄ Ｎjを計算する。得られたｚjを、Ｌ、ｍと共にハッシュ手段１２６によりハッシュし、その結果をｃj+1とする。
【００１８】
図９の公開鍵種別リング接合手段では、Ｌ、ｃk 、ｋを入力とし、更に、入力秘密鍵に対応する公開鍵がＤの場合にはｗと秘密鍵ｘk を入力とし、Ｔの場合はｚkと秘密鍵ｄkを入力とする。先ず、公開鍵判別手段１３１により、入力秘密鍵に対応する公開鍵がＤとＴの何れであるかを判別する。Ｄの場合には、回答計算手段１３２によりｓk＝ｗ−ｃkｘk ｍｏｄ ｐkを計算する。Ｔの場合には、加減算手段１３３によりｙk＝ｚk−ｃk ｍｏｄ Ｎkを計算し、一方向性置換逆算計算手段１３４にｙkとｄk、Ｎkを入力してｓk＝ｙkdk ｍｏｄ Ｎkを計算する。
以上の手段により、文書ｍに対するリストＬ中の公開鍵による1-out-of-n署名が得られる。
【００１９】
次に、図１０を用いて署名検証手順の動作を説明する。図１０は図５に対応する図である。文書ｍ、公開鍵リストＬ、署名（ｃ0,ｓ0,ｓ1,・・・・・・,ｓn-1）を入力とする。
先ず、ループ変数初期化手段１４１により、ｊ＝０に設定する。次に、図８の公開鍵種別連鎖処理手順に従って、順次、ｃ1,・・・・・を計算する。最後のｃj+1をｃnとして出力し、ｃ0と共に比較手段１５へ入力する。ｃnとｃ0が一致する場合には、署名を合格とし、そうでなければ不合格とする。
【００２０】
【発明の効果】
以上の通りであって、この発明によれば、1-out-of-n署名に利用することができる公開鍵の種別を離散対数型、或いは一方向性置換型に限定することなく、両者が混在してもこれらを公開鍵判別手段を介して離散対数型の公開鍵であるか或いは一方向性置換型の公開鍵であるかを判別し、判別された種別に対応する処理を当該公開鍵に施して適切な1-out-of-n署名を生成し、なされた署名の署名を検証することができる。
そして、前段の出力値ｚjから後段のチャレンジｃj+1を計算するに際して、後段のチャレンジとして適切な出力域をもつハッシュ関数によりこれを圧縮計算することにより、後段で使用する公開鍵が離散対数型か一方向性関数型に関わらず適切な大きさのチャレンジを生成することができる。
【図面の簡単な説明】
【図１】署名手段の実施例を示す図。
【図２】公開鍵種別初期化手段を示す図。
【図３】公開鍵種別連鎖処理手段を示す図。
【図４】公開鍵種別リング接合手段を示す図。
【図５】署名検証手順の実施例を示す図。
【図６】実施例の署名手順の流れ図。
【図７】実施例の署名手順中の公開鍵種別初期化手順の流れ図。
【図８】実施例の署名手順中の公開鍵種別連鎖処理手順の流れ図。
【図９】実施例の署名手順中の公開鍵種別リング接合手順の流れ図。
【図１０】実施例の署名検証手順の流れ図。
【符号の説明】
１１  公開鍵種別初期化手段        １１１  公開鍵判別手段
１１２、１１２’乱数生成手段          １１３  群要素計算手段
１１４  ハッシュ手段                  １２  公開鍵種別連鎖処理手段
１２１  公開鍵判別手段      １２２、１２２’乱数生成手段
１２３  検証値計算手段              １２４  一方向性置換計算手段
１２５  加減算手段                  １２６  ハッシュ手段
１３  公開鍵種別リング接合手段    １３１  公開鍵判別手段
１３２  回答計算手段                １３３  加減算手段
１３４  一方向性置換逆算計算手段      １４  ループ制御手段
１４１  ループ変数初期化手段        １４２  ループ変数更新手段
１４３  ループ終了判断手段            １５  比較手段
【図１】
0003881274.tif 000002
【図２】
0003881274.tif 000003
【図３】
0003881274.tif 000004
【図４】
0003881274.tif 000005
【図５】
0003881274.tif 000006
【図６】
0003881274.tif 000007
【図７】
0003881274.tif 000008
【図８】
0003881274.tif 000009
【図９】
0003881274.tif 000010
【図１０】
0003881274.tif 000011