(57)【要約】【課題】本発明は、計算時間及び記憶空間を減少させ、キー管理の手続を単純化させるバイリニアペアリングを用いた個人識別情報に基づくリング署名装置及び方法を提供する。【解決手段】ユーザー、署名者及び信頼機関を備える暗号化システムでバイリニアペアリングを用いる個人識別情報に基づくリング署名方式は、信頼機関がユーザー及び署名者により共有されるシステムパラメータの集合を生成し、システムパラメータの集合を用いてユーザー及び署名者の公開鍵及び秘密鍵を生成し、生成された公開鍵及び秘密鍵をユーザー及び署名者に安全なチャンネルを通して伝送する。ユーザーはメッセージの内容を隠し、署名者に前記内容が隠されたメッセージに対するリング署名を要請し、署名者により生成されたＩＤに基づくリング署名の有効性を検証する。署名者は、前記ユーザーの個人識別情報（ＩＤ）に基づいて前記リング署名を生成し、前記内容が隠されたメッセージに対するＩＤに基づくリング署名を生成する。【選択図】    図１
2004208262.tif 000002
【特許請求の範囲】
【請求項１】
ユーザー、署名者及び信頼機関を備える暗号化システムでバイリニアペアリングを用いて個人識別情報に基づくリング署名を生成する方法であって、
(a)前記信頼機関が前記ユーザー及び前記署名者により共有されるシステムパラメータの集合を生成し、前記ユーザー及び前記署名者のそれぞれのメモリに記憶するステップと、
(b)前記信頼機関が前記システムパラメータの集合を用いて、前記ユーザー及び前記署名者の公開鍵及び秘密鍵を生成し、生成された前記公開鍵及び前記秘密鍵を前記ユーザー及び前記署名者に安全なチャンネルを通して伝送するステップと、
(c)前記ユーザーがメッセージの内容を隠し、前記署名者に前記内容が隠されたメッセージに対するリング署名を要請するステップと、
(d)前記署名者が前記ユーザーの個人識別情報(ＩＤ)に基づいて前記リング署名を生成し、前記内容が隠されたメッセージに対するＩＤに基づくリング署名を生成するステップと、
(e)前記ユーザーが前記ＩＤに基づくリング署名の有効性を検証するステップとを含む個人識別情報に基づくリング署名生成方法。
【請求項２】
前記ステップ(a)は、
(a1)生成者Ｐにより、位数ｑを有する巡回群Ｇを生成し、前記巡回群Ｇが楕円または超楕円曲線ヤコビアンであるステップと、
(a2)バイリニアペアリングを用いて前記位数ｑを有する巡回乗法群Ｖを生成し、バイリニアペアリングeはe: G × G→Vで表現されるステップと、
(a3)暗号学的ハッシュ関数H: {0,1}* →Zq*及びH1: {0,1}* →Gを生成し、Zq*がVに対応する巡回乗法群であるステップと、
(a4)前記信頼機関のマスターキーｓを選び、前記マスターキーｓ及び前記生成者Ｐを用いて、前記信頼機関の公開鍵Ｐpub = s ・ Pを生成するステップとを含む請求項１に記載の個人識別情報に基づくリング署名生成方法。
【請求項３】
前記システムパラメータは、G、q、P、Ppub、H及びH1を含む請求項２に記載の個人識別情報に基づくリング署名生成方法。
【請求項４】
前記ユーザーの個人識別情報はＩＤiであり、「i」は1〜nの範囲にある整数であるユーザーインデックスである時、前記ユーザーの前記公開鍵QＩＤi = H1(ＩＤi)及び前記秘密鍵SＩＤi = s ・ QＩＤiを生成し、前記ユーザーのメモリに記憶する請求項３に記載の個人識別情報に基づくリング署名生成方法。
【請求項５】
前記ステップ(d)は、
(d1)ユーザーの個人識別情報の集合であるＩＤリストＬを選ぶステップと、
(d2)前記巡回群Ｇから任意の要素Ａを抽出し、前記ＩＤリストＬを用いて初期署名値を計算するステップと、
(d3)前記巡回群の任意の値を選び、前記ＩＤリストＬを用いて追加の署名値を計算するステップと、
(d4)前記署名者の前記秘密鍵を用いてリング署名値を生成するステップと、
(d5)前記追加の署名値の連結値（glue value）としてゼロを選び、リング署名値のリングを形成するステップと、
(d6)n+1個のリング署名値を有する前記ＩＤに基づくリング署名を前記ユーザーのメモリに記憶するステップとを含む請求項４に記載の個人識別情報に基づくリング署名生成方法。
【請求項６】
前記署名者は前記初期署名値ck+1 = H(L │m │e(A, P))を計算し、kは署名者のインデックスであり、mは前記内容が隠されたメッセージである請求項５に記載の個人識別情報に基づくリング署名生成方法。
【請求項７】
全てのモジュロn値（k+1、…、n-1、0、1、k-1）のうち1つに対応する「i」に対して追加の署名値ci+1 = H(L │m │e(Ti, P) e(ci H1(ＩＤi), Ppub))を計算して前記署名者のメモリに記憶し、Tiが前記巡回群Ｇの前記任意の値である請求項６に記載の個人識別情報に基づくリング署名生成方法。
【請求項８】
前記ＩＤに基づくリング署名値Tk = A - ck SＩＤkを計算して、前記署名者のメモリに記憶する請求項７に記載の個人識別情報に基づくリング署名生成方法。
【請求項９】
前記ＩＤに基づくリング署名がシーケンス(c0, T0, T1,・・・, Tn-1)であり、前記ユーザーのメモリに記憶される請求項８に記載の個人識別情報に基づくリング署名生成方法。
【請求項１０】
前記ＩＤに基づくリング署名の前記有効性を次の式で判断し、
ck+1 = H( L │m │ e(A, P))
ck+2 = H( L │m │ e(Tk+1, P) e(ck+1 H1(ＩＤk+1), Ppub))
……
cn = H( L │m │ e(Tn-1, P) e(cn-1 H1(ＩＤn-1), Ppub))
c1 = H( L │m │ e(T0, P) e(c0 H1(ＩＤ0), Ppub))
c2 = H( L │m │ e(T1, P) e(c1 H1(ＩＤ1), Ppub))
……                   ・・・
ck = H( L │m │e(Tk-1, P) e(ck-1 H1(ＩＤk-1), Ppub))
若し、i=0、1、・・・、n-1であり、cn＝c0であれば、前記ＩＤに基づくリング署名が有効であると決定し、そうでなければ拒否する請求項９に記載の個人識別情報に基づくリング署名生成方法。
【請求項１１】
バイリニアペアリングを用いて個人識別情報に基づくリング署名を生成する装置であって、
信頼機関と、
ユーザーと、
署名者とを含み、
前記信頼機関は、前記ユーザー及び前記署名者により共有されるシステムパラメータの集合を生成して、前記ユーザー及び前記署名者のそれぞれのメモリに記憶し、
前記信頼機関は、前記システムパラメータの集合を用いて前記ユーザー及び前記署名者の公開鍵及び秘密鍵を生成し、生成された前記公開鍵及び前記秘密鍵を前記ユーザー及び前記署名者に安全なチャンネルを通して伝送し、
前記ユーザーは、メッセージの内容を隠し、前記署名者に前記内容が隠されたメッセージに対するリング署名を要請し、
前記署名者は、前記ユーザーの個人識別情報（ＩＤ）に基づいて前記リング署名を生成し、前記内容が隠されたメッセージに対するＩＤに基づくリング署名を生成し、
前記ユーザーは、前記ＩＤに基づくリング署名の有効性を検証する個人識別情報に基づくリング署名生成装置。
【請求項１２】
前記システムパラメータは、
巡回群Ｇと、
前記巡回群Ｇの位数ｑと、
前記巡回群Ｇの生成者Ｐと、
前記信頼機関の公開鍵Ｐpubと、
ハッシュ関数H及びH1とを含み、
前記信頼機関の公開鍵はマスターキーｓを用いて鍵Ｐpub = s ・ Pで計算され、前記ハッシュ関数はH: {0,1}* → Zq*及びH1: {0,1}* → Gで計算され、前記Zq*は巡回乗法群であり、
前記バイリニアペアリングをe: G × G →Vに定義し、Vは位数ｑを有する巡回乗法群としてZq*を用い、
前記ユーザーの個人識別情報がＩＤiであり、「i」が1〜nの範囲にあるユーザーインデックスである時、前記ユーザーの前記公開鍵及び前記秘密鍵がそれぞれQＩＤi = H1(ＩＤi)及びSＩＤi = s ・ QＩＤiであり、
kは署名者インデックス、Lはユーザーの個人識別情報の集合、mはリング署名される内容が隠されたメッセージ、Aは巡回群Ｇの任意の一要素である場合、前記初期署名値ck+１は、cｋ+1 = H(L │m │ e(A, P))で計算し、Tiが前記巡回群Ｇの前記任意の値である場合、全てのモジュロn値（k+1、..、n-1、0、1及びk-1）のうち1つに対応する「i」に対して追加の署名値ci+1は、ci+1= H(L │m │e(Ti, P) e(ci H1(ＩＤi), Ppub))で計算し、
前記ＩＤに基づくリング署名値Tkは、Tk = A - ck SＩＤkで計算し、
前記ＩＤに基づくリング署名は、シーケンス(c0, T0, T1,・・・, Tn-1)から得られ、
前記ＩＤに基づくリング署名の前記有効性は次の式から判断され、
ck+1 = H( L │m │ e(A, P))
ck+2 = H( L │m │ e(Tk+1, P) e(ck+1 H1(ＩＤk+1), Ppub))
……
cn = H( L │m │ e(Tn-1, P) e(cn-1 H1(ＩＤn-1), Ppub))
c1 = H( L │m │ e(T0, P) e(c0 H1(ＩＤ0), Ppub))
c2 = H( L  │m │ e(T1, P) e(c1 H1(ＩＤ1), Ppub))
……
ck = H( L │m │ e(Tk-1, P) e(ck-1 H1(ＩＤk-1), Ppub))
若しi=0、1、…、n-1であり、cn＝c0であれば、前記ＩＤに基づくリング署名が有効なものであると決定し、そうではなければ拒否する請求項１１に記載の個人識別情報に基づくリング署名生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、リング署名に基づく暗号化システムに関し、特に、バイリニアペアリングを用いる個人識別情報に基づくリング署名システムに関する。
【０００２】
【従来の技術】
公開鍵暗号システムにおいて、各ユーザーは公開鍵及び秘密鍵の２つのキーを有する。ユーザーの公開鍵及び個人識別情報は、デジタル証明書（Digital Certificate）によりつながる。証明書に基づくシステム（certificate based system）において、ユーザーの公開鍵を用いる前、参加者は、まずユーザーの証明書を検証しなければならない。従って、ユーザーの数が急速に増加するに伴って、証明書に基づくシステムは多量の計算時間及び記憶空間を必要とする。
【０００３】
証明書に基づく公開鍵暗号システムにおいて、キー管理の手続を単純化するために、シャミア（Shamir）は1984年に個人識別情報に基づく暗号化技法及び署名技法を提案した（A. Shamir, ＩＤentity-based cryptosystems and signature schemes, Advances in Cryptology-Crypto 84, LNCS 196, pp.47-53, Springer-Verlag, 1984.）。その後、個人識別情報に基づく暗号化技法及び署名技法が数多く提案されてきた。
【０００４】
バイリニアペアリング（bilinear pairs）、例えば代数曲線のWeilペアリング及びTateペアリングは、代数幾何学研究において非常に重要な道具である。暗号システムにおいて、バイリニアペアリングの初期応用は、離散対数問題（Discrete Logarithm Problem）を評価するために用いられた。例えば、Weilペアリングを用いたMOV攻撃及びTateペアリングを用いたFR攻撃は、特定楕円曲線や超楕円曲線での離散対数問題を有限体での離散対数問題に縮小させた。近年、バイリニアペアリングが暗号学で多様に応用できることが明らかになった。さらに正確には、バイリニアペアリングは個人識別情報に基づく暗号システムの構築に用いることができる。バイリニアペアリングを用いた様々な個人識別情報に基づく暗号システムが提案された。例えば、Boneh及びFranklinの個人識別情報に基づく暗号システム（D. Boneh and M. Franklin, ＩＤentity-based encryption from the Weil pairing, Advances in Cryptology-Crypto 2001, LNCS 2139, pp.213-229, Springer-Verlag, 2001.）と、Smartの個人識別情報に基づく認証キー合意プロトコル（N.P. Smart, ＩＤentity-based authenticated key agreement protocol based on Weil pairing, Electron. Lett., Vol.38, No.13, pp.630-632,
2002.）と、幾つかの個人識別情報に基づく署名技法とがある。
【０００５】
特に、効率的なキー管理及び適度な保安が求められる場合、個人識別情報に基づく公開鍵暗号システムは、証明書に基づく公開鍵暗号システムの代案になれる。公開鍵暗号システムにおいて、証明者の匿名性はブラインド署名により保護され、一方、署名者の匿名性はリングデジタル署名（以下、リング署名と呼ぶ。）またはグループデジタル署名により保護される。
【０００６】
リング署名の概念は、Rivest、Shamir及びTauman(R.L. Rivest, A. Shamir and Y. Tauman, How to leak a secret, Advances in Cryptology-Asiacrypt 2001, LNCS 2248, pp.552-565, Springer-Verlag, 2001)により提案された。リング署名は、マネージャ無しに、ユーザーのみで構成された単純化されたグループ署名であるとみなされる。リング署名は、証明者が署名がリングの一構成員によりなされたことを知っているが、署名者が正確に誰なのかは知らないので、署名者の匿名性を保護することができる。また、署名者の匿名性を撤回する方法がない。リング署名は、臨時グループ（ad hoc subset format）を支援することができ、一般に特別な初期化作業を要求しない。Rivest-Shamir-Taumanのリング署名方式は、一般の公開鍵暗号システムに基づく。
【０００７】
一般のリング署名システムは、多量の計算時間及び記憶空間を必要とする。バイリニアペアリングを用いた個人識別情報に基づく暗号システムが多数提案されているが、バイリニアペアリングを用いた個人識別情報に基づくリング署名はまだ提案されていない。
【０００８】
【発明が解決しようとする課題】
従って、本発明の主目的は、計算時間及び記憶空間を減少させ、キー管理の手続を単純化させるバイリニアペアリングを用いた個人識別情報に基づくリング署名装置及び方法の提供にある。
【０００９】
【課題を解決するための手段】
上記の目的を達成するために、本発明の一態様に基づき、ユーザー、署名者及び信頼機関を備える暗号化システムでバイリニアペアリングを用いて個人識別情報に基づくリング署名を生成する方法であって、(a)前記信頼機関が前記ユーザー及び前記署名者により共有されるシステムパラメータの集合を生成し、前記ユーザー及び前記署名者のそれぞれのメモリに記憶するステップと、(b)前記信頼機関が前記システムパラメータの集合を用いて、前記ユーザー及び前記署名者の公開鍵及び秘密鍵を生成し、生成された前記公開鍵及び前記秘密鍵を前記ユーザー及び前記署名者に安全なチャンネルを通して伝送するステップと、(c)前記ユーザーがメッセージの内容を隠し、前記署名者に前記内容が隠されたメッセージに対するリング署名を要請するステップと、(d)前記署名者が前記ユーザーの個人識別情報(ＩＤ)に基づいて前記リング署名を生成し、前記内容が隠されたメッセージに対するＩＤに基づくリング署名を生成するステップと、(e)前記ユーザーが前記ＩＤに基づくリング署名の有効性を検証するステップとを含む。
【００１０】
前記目的を達成するために、本発明の別の態様に基づき、バイリニアペアリングを用いて個人識別情報に基づくリング署名を生成する装置であって、信頼機関と、ユーザーと、署名者とを含み、前記信頼機関が前記ユーザー及び前記署名者により共有されるシステムパラメータの集合を生成して、前記ユーザー及び前記署名者のそれぞれのメモリに記憶し、前記信頼機関は前記システムパラメータの集合を用いて前記ユーザー及び前記署名者の公開鍵及び秘密鍵を生成し、生成された前記公開鍵及び前記秘密鍵を前記ユーザー及び前記署名者に安全なチャンネルを通して伝送し、前記ユーザーはメッセージの内容を隠し、前記署名者に前記内容が隠されたメッセージに対するリング署名を要請し、前記署名者は前記ユーザーの個人識別情報（ＩＤ）に基づいて前記リング署名を生成し、前記内容が隠されたメッセージに対するＩＤに基づくリング署名を生成し、前記ユーザーは前記ＩＤに基づくリング署名の有効性を検証する。
【００１１】
【発明の実施の形態】
本発明による個人識別情報（ＩＤ）に基づくリング署名方式は、リング署名方式及びＩＤに基づく方式が組合わされたものであると見られる。また、本発明のＩＤに基づくリング署名方式は、バイリニアペアリングを用いる。
【００１２】
本発明のＩＤに基づくリング署名は、次のような4つの手順で構成される。
【００１３】
1．初期化：システムパラメータ（ＰＡＲＡＭＳ）及びマスターキーｓを生成する。
【００１４】
2．鍵生成：マスターキーｓ及び署名者の個人識別情報（ＩＤ）を取り、署名者の秘密鍵SＩＤ及び公開鍵QＩＤを生成する。
【００１５】
3．署名：ＰＡＲＡＭＳ、署名者の秘密鍵、ユーザーの個人識別情報の集合であるリストＬ及び内容が隠されたメッセージmを取り、mに対するＩＤに基づくリング署名σ(m)を出力する。
【００１６】
4．検証：リストＬ、内容が隠されたメッセージm及びＩＤに基づくリング署名σ(m)を取り、ＩＤに基づくリング署名σ(m)の有効性を判断する。
【００１７】
上述した本発明によるＩＤに基づくリング署名方式に基づいた装置及び方法を図１〜図５を参照して詳細に説明する。
【００１８】
署名者１００、ユーザー２００及び信頼機関３００は、ＩＤに基づくリング署名方式の参加者として動作する。ここで、各参加者はコンピューターシステムであり、いかなる通信網または他の技術により遠隔で通信することができる。参加者の間に伝送される情報は、多様な種類の記憶媒体に記憶及び/または維持することができる。
【００１９】
図１は、本発明によるＩＤに基づくリング署名の初期化及び鍵生成手順を示す概略図である。
【００２０】
信頼機関３００は、システムパラメータ（ＰＡＲＡＭＳ）を生成して署名者１００及びユーザー２００が用いることができるようにし、マスターキーを選ぶ。また、信頼機関３００は署名者１００及びユーザー２００の個人識別情報に基づいて彼等の公開鍵及び秘密鍵を生成した後、安全なチャンネルを通して署名者１００及びユーザー２００に提供する。信頼機関３００は初期化及び鍵生成手順には参加するが、以後の手順には参加しない。
【００２１】
図２は、本発明によるＩＤに基づくリング署名の署名手順を示す概略図である。
【００２２】
まず、ユーザー２００はメッセージの内容を隠してこの内容が隠されたメッセージを任意の署名者に提供し、メッセージに対するデジタル署名（さらに詳しくは、ＩＤに基づくリング署名）を要請する。
【００２３】
署名者１００が署名要請及び内容が隠されたメッセージを受信すると、署名者１００は内容が隠されたメッセージの内容は知らずに、ＰＡＲＡＭＳに基づき、自分の秘密鍵を用いて内容が隠されたメッセージに対するリング署名を生成する。
【００２４】
図３を参照すれば、ユーザー２００はｎ+１個の署名値、内容が隠されたメッセージ、ＰＡＲＡＭＳ、リストＬ及び署名者１００の公開鍵を用いて、署名者１００から提供されたリング署名の有効性を検証する。
【００２５】
本発明によるＩＤに基づくリング署名の方法を図４及び５の流れ図を参照しながら、詳細に説明する。図４及び５において、ＩＤに基づくリング署名に参加するユーザーの数が「n」であり、署名される内容が隠されたメッセージがデジタル形で伝送または記憶されると仮定する。
【００２６】
ステップ２０１において、その位数が各々「q」である２つの巡回群Ｇ及びVが生成される。
【００２７】
さらに詳しく説明すれば、生成者Ｐが選択され、巡回群Ｇを生成し、続いて他の巡回群Ｖがバイリニアペアリング「e」により生成されるが、巡回群Ｇは楕円または超楕円曲線ヤコビアン（Jacobian）であり、巡回群Ｖは通常Zq*に対応する巡回乗法群である。巡回群Ｇから巡回乗法群Ｖへのバイリニアペアリング「e」は、次のように与えられる。
【００２８】
e: G × G → V
ステップ２０２において、暗号学的ハッシュ関数H及びH1は、次のように決定される。
【００２９】
H: {0,1}* → Zq*及びH1: {0,1}* → G
ステップ２０３において、マスターキーとしてZq*の一要素である「s」を選び、マスターキーｓ及び巡回群Ｇの生成者Ｐを用いて信頼機関３００の公開鍵Ｐpubを次のように設定する。
【００３０】
Ppub = s ・ P
信頼機関３００の公開鍵Ｐpubは、暗号学的ハッシュ関数H及びH1の決定前、或いは決定と同時に設定することもできる。
【００３１】
ステップ２０４において、ＰＡＲＡＭＳのセット｛G, q, P, Ppub, H, H1｝が公開され、署名者１００及びユーザー２００のそれぞれのメモリに記憶される。
【００３２】
ステップ２０５において、署名者１００及びユーザー２００の公開鍵及び秘密鍵が生成される。若し、例えば、ユーザー２００が自分の個人識別情報ＩＤiを有すれば、ＩＤiを有するユーザー２００の公開鍵QＩＤi及び秘密鍵SＩＤiは、次のように生成される。
【００３３】
QＩＤi = H1(ＩＤi)及びSＩＤi = s ・ QＩＤi
ここで、「i」はユーザーインデックスであり、１〜nの間の整数である。
【００３４】
その後、ユーザーの公開鍵QＩＤi及び秘密鍵SＩＤiは、安全なチャンネルを通してＩＤiを有するユーザー２００のメモリに伝送及び記憶される。
【００３５】
続いて、署名手順が行われる。
【００３６】
ステップ２０６において、ユーザー２００はメッセージの内容を隠して任意の署名者にそのメッセージに対する署名（さらに正確には、ＩＤに基づくリング署名）を要請する。
【００３７】
ステップ２０７において、署名者１００はユーザー２００から内容が隠されたメッセージ及びこれに対するＩＤに基づくリング署名の要請を受信した後、ＩＤリストＬを取り、巡回群Ｇから任意の一要素Ａを抽出して、次のように初期署名値ck+1を計算する。
【００３８】
ck+1 = H(L │m │ e(A, P))
ここで、「m」は署名される内容が隠されたメッセージであり、ＩＤリストＬはユーザーの個人識別情報の集合である（即ち、L＝｛ＩＤi｝）。
【００３９】
以後、初期署名値ck+1は、署名者１００のメモリに記憶される。
【００４０】
ステップ２０８において、「Ti」が巡回群Ｇから任意に選ばれ、次のように追加の署名値ci+1が計算される。
【００４１】
ci+1 = H(L │m │ e(Ti, P) e(ci H1(ＩＤi), Ppub))
ここで、「i」はk+1、…、n-1、0、1、k-1（即ち、全モジュロ（modulo）n値のうち1つ）に対応する。
【００４２】
ステップ２０９において、リング署名値Tkは次のように計算される。
【００４３】
Tk = A - ck SＩＤk
ここで、SＩＤkはステップ２０５で生成された署名者１００の秘密鍵である。
【００４４】
リング署名値Tkが署名者１００のメモリに記憶される。
【００４５】
ステップ２１０において、追加の署名値の連結値（glue value、即ちn）としてゼロを選んでリングを形成し、n+1個のリング署名値からなる内容が隠されたメッセージmに対するＩＤに基づくリング署名が次のようなシーケンスで得られる。
【００４６】
(c0, T0, T1,・・・, Tn-1)
以後、ＩＤに基づくリング署名は、ユーザー２００のメモリに伝送及び記憶される。
【００４７】
最後に、検証手順が行われる。
【００４８】
ステップ２１１において、ユーザー２００が次の式に基づいてリング署名の有効性を検証する。
【００４９】
ci+1 = H(L │m │ e(Ti, P) e(ci H1(ＩＤi), Ppub))
さらに詳しく説明すれば、署名値シーケンス｛ci｝が次のように得られる。
【００５０】
ck+1 = H( L │m │ e(A, P))
ck+2 = H( L │m │ e(Tk+1, P) e(ck+1 H1(ＩＤk+1), Ppub))
……      
cn = H( L │m │ e(Tn-1, P) e(cn-1 H1(ＩＤn-1), Ppub))
c1 = H( L │m │ e(T0, P) e(c0 H1(ＩＤ0), Ppub))
c2 = H( L │m │ e(T1, P) e(c1 H1(ＩＤ1), Ppub))
……      
ck = H( L │m │ e(Tk-1, P) e(ck-1 H1(ＩＤk-1), Ppub))
ここで、iは0、1、…、n-1である。
【００５１】
このような署名値シーケンス｛ci｝は、ユーザー２００のメモリに記憶される。
【００５２】
一方、署名手順での初期署名値ck+1は、次のように計算できる。
【００５３】
ck+1
= H( L │m │ e(Tk, P) e(ck H1(ＩＤi), Ppub))
= H( L │m │ e(A - ck SＩＤk, P) e(ck H1(ＩＤi), Ppub))
= H( L │m │ e(A, P) e(-ck SＩＤk, P) e(ck H1(ＩＤi), Ppub))
= H( L │m │ e(A, P) e(-ck H1(ＩＤi) + ck H1(ＩＤi), Ppub))
= H( L │m │ e(A, P))
署名を正当にするためには、検証手順での署名値シーケンス｛ci｝が署名手順でのものと同じであるので、追加署名値の連結値がゼロでなければならない（即ち、cn＝c0）。従って、若しi＝0、1、…、n-1であり、cn＝c0であれば、ステップ２１２でリング署名が有効なものとして承認され、そうではなければステップ２１３で拒否される。
【００５４】
結論的に、本発明によるＩＤに基づくリング署名は、次のような特徴を表す。
【００５５】
I．正確性
検証手順での署名値シーケンス｛ci｝は、署名手順でのものと同一でなければならない。従って、生成されたＩＤに基づくリング署名が正当であるか否かについて検証することができる。
【００５６】
II．保安性
ＩＤに基づくリング署名は、Tkを除いた全てのTiがGから任意に取られるので、無条件で署名者-曖昧性を有する。実際に、AがGから任意に選択されるので、TkもGの全般に亘って均等に分布される。従って、固定されたL及びmに対する|G|n個のソリューション（T0、T1、…、Tn-1）は、全て同じ確率で署名手順で選択することができるので、署名者とは関係なく存在する。
【００５７】
また、本発明のＩＤに基づくリング署名は、次のc0の確率が1/qであるので、非偽造性を有すると見なされる。
【００５８】
C0 = H(L │m │ e(Tn-1, P) e(cn-1 H1(ＩＤn-1), Ppub))
III．効率性
本発明によるＩＤに基づくリング署名方式は、楕円曲線或いは超楕円曲線で行うことができ、バイリニアペアリングを採用する。また、２の因数による圧縮技術を用いて署名の長さを縮小させることができる。
【００５９】
ＩＤに基づくリング署名は、任意数より個人識別情報に基づいているので、公開鍵は電子メールアドレスのように、ユーザーを唯一に識別するユーザー情報を有する。いくつかの分野において、署名の長さが縮小できるので、公開鍵及び署名の長さも縮小できる。
【００６０】
上記において、本発明の好適な実施の形態について説明したが、本発明の精神及び請求範囲から逸脱することなく、種々の変更及び修正がなされてもよいことは当業者にはご理解いただけるであろう。
【００６１】
【発明の効果】
本発明による個人識別情報に基づくリング署名方式は、署名値が任意に取られるので、署名者が正確に誰なのか分からず、検証手順及び署名手順での署名値シーケンスの同一性要否から生成されたＩＤに基づくリング署名の正当性を判断することができる。また、バイリニアペアリングを用いることで、効率的にデジタル署名を行うことができる。
【図面の簡単な説明】
【図１】本発明の好適な実施の形態によるＩＤに基づくリング署名方式を説明する概略図である。
【図２】本発明の好適な実施の形態によるＩＤに基づくリング署名方式を説明する概略図である。
【図３】本発明の好適な実施の形態によるＩＤに基づくリング署名方式を説明する概略図である。
【図４】本発明の好適な実施の形態によるＩＤに基づくリング署名手順を説明する流れ図である。
【図５】本発明の好適な実施の形態によるＩＤに基づくリング署名手順を説明する流れ図である。
【図１】
2004208262.tif 000003
【図２】
2004208262.tif 000004
【図３】
2004208262.tif 000005
【図４】
2004208262.tif 000006
【図５】
2004208262.tif 000007