(57)【要約】【課題】楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減する。【解決手段】楕円曲線上のペアリングに基づく署名方式において、鍵生成センター装置１０が、楕円曲線Ｅのｎねじれ群Ｅ[ｎ]を構成する固有空間＜Ｐ＞，＜Ｑ＞からそれぞれ点Ｐ，Ｑを選択することを含むセットアップ処理を実行する。電子署名生成装置２０は、電子署名σ’＝（Ｒ，Ｓ）を圧縮して電子署名σ＝（Ｔ）を得ることを含む署名処理を実行する。電子署名検証装置３０は、電子署名σ＝（Ｔ）から点データＲ，Ｓを取得することを含む検証処理を実行する。このように、電子署名σ’＝（Ｒ，Ｓ）をσ＝（Ｔ）に圧縮する構成により、電子署名のデータ長を削減できる。【選択図】      図１
2008178035.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、互いに通信可能な鍵生成センター装置、電子署名生成装置及び電子署名検証装置を備えた電子署名システムであって、
前記鍵生成センター装置は、
鍵生成センター用秘密鍵Lとしての乱数を生成する手段と、
楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞に関し、それぞれ巡回群＜Ｐ＞から点Ｐを選択し、巡回群＜Ｑ＞から点Ｑを選択する手段と、
前記鍵生成センター用秘密鍵L及び点Ｑに基づいて、点Ｑpub＝LＱを計算する手段と、
前記点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報が記憶される第１公開情報記憶手段と、
前記鍵生成センター用秘密鍵Lが記憶される第１秘密鍵記憶手段と、
前記電子署名生成装置又は前記電子署名検証装置から署名者ＩＤ情報IDAを含む公開情報要求を受信すると、前記署名者ＩＤ情報IDA、前記点Ｐ及び前記一方向性関数ｈ（ ）に基づいて、署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算する手段と、
前記署名者公開鍵ＰA及び前記公開情報を前記公開情報要求の送信元に返信する手段と、
前記電子署名生成装置から秘密鍵要求を受信すると、前記署名者公開鍵ＰA及び前記鍵生成センター用秘密鍵Lに基づいて、署名者秘密鍵ＫA＝LＰAを計算する手段と、
前記署名者秘密鍵ＫAを前記電子署名生成装置に返信する手段とを備えており、
前記電子署名生成装置は、
前記鍵生成センター装置から受信した署名者公開鍵ＰA及び公開情報が記憶される第２公開情報記憶手段と、
前記鍵生成センター装置から受信した署名者秘密鍵ＫAが記憶される第２秘密鍵記憶手段と、
電子署名生成用の乱数ｋを生成する手段と、
前記乱数ｋ及び前記公開情報内の点Ｑに基づいて、点Ｒ＝ｋＱを計算する手段と、
電子署名対象データｍに対し、前記乱数ｋ、前記署名者秘密鍵ＫA、前記署名者公開鍵ＰA、前記公開情報内の一方向性関数ｈ（ ）及び前記点Ｒのｘ座標値ｘに基づいて、点Ｓ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA を計算する手段と、
前記点Ｒ，Ｓを互いに加算して点Ｔ（＝Ｒ＋Ｓ）に圧縮する手段と、
前記点Ｔからなる電子署名σ＝（Ｔ）及び前記電子署名対象データｍを前記電子署名検証装置に送信する手段とを備えており、
前記電子署名検証装置は、
前記鍵生成センター装置から受信した署名者公開鍵ＰA及び公開情報が記憶される第３公開情報記憶手段と、
前記電子署名生成装置から電子署名σ＝（Ｔ）及び電子署名対象データｍを受信すると、前記公開情報内の射影Ψに基づいて、点Ｒ＝Ψ（Ｔ）を計算する手段と、
得られた点Ｒ及び前記電子署名σ＝（Ｔ）に基づいて、点Ｓ＝Ｔ−Ｒを計算する手段と、
前記電子署名σ＝（Ｔ）から得られた点Ｓ，Ｒに関し、前記署名者公開鍵ＰA及び公開情報を用いて、楕円曲線上のペアリングに基づく判定式ｅn（Ｓ，Ｒ）＝ｅn（ＰA，Ｑ）h(m)ｅn（ＰA，Ｑpub）x が成立するか否かを判定する手段と、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（Ｔ）を受け入れる手段と
を備えたことを特徴とする電子署名システム。
【請求項２】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、電子署名生成装置及び電子署名検証装置に通信可能な鍵生成センター装置であって、
鍵生成センター用秘密鍵Lとしての乱数を生成する手段と、
楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞に関し、それぞれ巡回群＜Ｐ＞から点Ｐを選択し、巡回群＜Ｑ＞から点Ｑを選択する手段と、
前記鍵生成センター用秘密鍵L及び点Ｑに基づいて、点Ｑpub＝LＱを計算する手段と、
前記点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報が記憶される第１公開情報記憶手段と、
前記鍵生成センター用秘密鍵Lが記憶される第１秘密鍵記憶手段と、
前記電子署名生成装置又は前記電子署名検証装置から署名者ＩＤ情報IDAを含む公開情報要求を受信すると、前記署名者ＩＤ情報IDA、前記点Ｐ及び前記一方向性関数ｈ（ ）に基づいて、署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算する手段と、
前記署名者公開鍵ＰA及び前記公開情報を前記公開情報要求の送信元に返信する手段と、
前記電子署名生成装置から秘密鍵要求を受信すると、前記署名者公開鍵ＰA及び前記鍵生成センター用秘密鍵Lに基づいて、署名者秘密鍵ＫA＝LＰAを計算する手段と、
前記署名者秘密鍵ＫAを前記電子署名生成装置に返信する手段とを備えており、
前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和を前記ｎねじれ群Ｅ[ｎ]としたことにより、前記点Ｐから計算される点Ｒと、前記点Ｑから計算される点Ｓとから前記電子署名生成装置により生成される電子署名σ’＝（Ｒ，Ｓ）を各点Ｒ，Ｓ同士の加算により点Ｔ（＝Ｒ＋Ｓ）からなる電子署名σ＝（Ｔ）に圧縮可能とし、且つ、前記電子署名検証装置に送信される電子署名σ＝（Ｔ）から、前記射影Ψに基づく点Ｒ＝Ψ（Ｔ）の計算と当該点Ｒに基づく点Ｓ＝Ｔ−Ｒの計算とにより、圧縮前の電子署名σ’＝（Ｒ，Ｓ）内の点Ｒ，Ｓを取得可能としたことを特徴とする鍵生成センター装置。
【請求項３】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置であって、
自己の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した「署名者公開鍵ＰA＝ｈ（IDA）Ｐ」及び「点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記点Ｑpubは鍵生成センター用秘密鍵Lと点Ｑとの積（点Ｑpub＝LＱ）である）」が記憶される第２公開情報記憶手段と、
前記鍵生成センター装置に秘密鍵要求を送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＫA＝LＰAが記憶される第２秘密鍵記憶手段と、
電子署名生成用の乱数ｋを生成する手段と、
前記乱数ｋ及び前記公開情報内の点Ｑに基づいて、点Ｒ＝ｋＱを計算する手段と、
電子署名対象データｍに対し、前記乱数ｋ、前記署名者秘密鍵ＫA、前記署名者公開鍵ＰA、前記公開情報内の一方向性関数ｈ（ ）及び前記点Ｒのｘ座標値ｘに基づいて、点Ｓ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA を計算する手段と、
前記点Ｒ，Ｓを互いに加算して点Ｔ（＝Ｒ＋Ｓ）に圧縮する手段と、
前記点Ｔからなる電子署名σ＝（Ｔ）及び前記電子署名対象データｍを前記電子署名検証装置に送信する手段とを備えており、
前記電子署名σ＝（Ｔ）は、前記射影Ψに基づく点Ｒ＝Ψ（Ｔ）の計算と当該点Ｒに基づく点Ｓ＝Ｔ−Ｒの計算とにより、圧縮前の電子署名σ’＝（Ｒ，Ｓ）内の点Ｒ，Ｓを取得可能であることを特徴とする電子署名生成装置。
【請求項４】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名生成装置に通信可能な電子署名検証装置であって、
前記電子署名生成装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した「署名者公開鍵ＰA＝ｈ（IDA）Ｐ」及び「点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記点Ｑpubは鍵生成センター用秘密鍵Lと点Ｑとの積（点Ｑpub＝LＱ）である）」が記憶される第３公開情報記憶手段と、
前記電子署名生成装置から電子署名対象データｍ及び電子署名σ＝（Ｔ）を受信する手段（但し、点ＴはＴ＝Ｒ＋Ｓに圧縮されており、点ＲはＲ＝ｋＱであり（ｋ：乱数）、点ＳはＳ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA）であり、ｘは点Ｒのｘ座標値であり、ＫAは署名者秘密鍵ＫA＝LＱである（L：乱数））と、
前記受信した電子署名σ＝（Ｔ）及び前記公開情報内の射影Ψに基づいて、点Ｒ＝Ψ（Ｔ）を計算する手段と、
得られた点Ｒ及び前記電子署名σ＝（Ｔ）に基づいて、点Ｓ＝Ｔ−Ｒを計算する手段と、
前記電子署名σ＝（Ｔ）から得られた点Ｓ，Ｒに関し、前記署名者公開鍵ＰA及び公開情報を用いて、楕円曲線上のペアリングに基づく判定式ｅn（Ｓ，Ｒ）＝ｅn（ＰA，Ｑ）h(m)ｅn（ＰA，Ｑpub）x が成立するか否かを判定する手段と、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（Ｔ）を受け入れる手段と
を備えたことを特徴とする電子署名検証装置。
【請求項５】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置であって、
前記電子署名検証装置の検証者ＩＤ情報IDBを含む公開情報要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した「検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」が記憶される第２公開情報記憶手段と、
署名者ＩＤ情報IDAを含む秘密鍵要求を前記鍵生成センター装置に送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＰsID_A＝s(IDA)-1Ｐが記憶される第２秘密鍵記憶手段と、
電子署名生成用の乱数ｘを生成する手段と、
前記乱数ｘ及び前記点ｇに基づいて、点Ｒ＝ｇｘを計算する手段と、
電子署名対象データｍに対し、前記点Ｒ、前記関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｒ）（＋）ｍを計算する手段（但し、（＋）は排他的論理和）と、
前記値ｃ、前記点Ｒ及び前記関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する手段と、
前記値ｈ、前記乱数ｘ及び前記署名者秘密鍵ＰsID_Aに基づいて、点Ｓ＝（ｘ＋ｈ）ＰsID_Aを計算する手段と、
前記乱数ｘ及び前記検証者公開鍵ＰID_Bに基づいて、点Ｔ＝ｘＰID_Bを計算する手段と、
前記点Ｔ及び前記同型写像ξに基づいて、点ξ（Ｔ）を計算する手段と、
前記点Ｓ，ξ（Ｔ）を互いに加算して点Ｘ（＝Ｓ＋ξ（Ｔ））に圧縮する手段と、
前記点Ｘ及び前記値ｃからなる電子署名σ＝（ｃ，Ｘ）を前記電子署名検証装置に送信する手段とを備えており、
前記電子署名σ＝（ｃ，Ｘ）は、前記射影Ψに基づく点Ｓ＝Ψ（Ｘ）の計算と当該点Ｓに基づく点Ｔ＝ξ-1（Ｘ−Ｓ）の計算とにより、圧縮前の電子署名σ’＝（ｃ，Ｓ，Ｔ）内の点Ｓ，Ｔを取得可能であることを特徴とする電子署名生成装置。
【請求項６】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名生成装置に通信可能な電子署名検証装置であって、
前記電子署名生成装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した「署名者公開鍵ＱsID_A＝s(IDA)Ｑ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」が記憶される第３公開情報記憶手段と、
前記電子署名検証装置の検証者ＩＤ情報IDBを含む秘密鍵要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した検証者秘密鍵ＱsID_B＝s(IDB)-1Ｑが記憶される第３記憶鍵記憶手段と、
前記電子署名生成装置から電子署名σ＝（ｃ，Ｘ）を受信する手段（但し、点ＸはＸ＝Ｓ＋ξ（Ｔ）に圧縮されており、点ＴはＴ＝ｘＰID_Bであり、ｘは乱数であり、ＰID_Bは検証者公開鍵ＰID_B＝s(IDB)Ｐであり、点ＳはＳ＝（ｘ＋ｈ）ＰsID_Aであり、ＰsID_Aは署名者秘密鍵ＰsID_A＝s(IDA)-1Ｐであり、値ｈはｈ＝Ｈ2（Ｒ，ｃ）であり、点ＲはＲ＝ｇｘであり、値ｃはｃ＝Ｈ1（Ｒ）（＋）ｍ（但し、（＋）は排他的論理和）であり、ｍは電子署名対象データである）と、
前記受信した電子署名σ＝（ｃ，Ｘ）及び前記公開情報内の射影Ψに基づいて、点Ｓ＝Ψ（Ｘ）を計算する手段と、
得られた点Ｓ及び前記電子署名σ＝（ｃ，Ｘ）内の点Ｘに基づいて、点Ｔ＝ξ-1（Ｘ−Ｓ）を計算する手段と、
得られた点Ｔ及び前記検証者秘密鍵ＱsID_Bに関し、楕円曲線上のペアリングに基づく点Ｒ＝ｅn（Ｔ，ＱsID_B）を計算する手段と、
得られた点Ｒ、前記値ｃ及び前記関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する手段と、
前記点Ｒ、前記値ｃ及び前記関数Ｈ2に基づいて、電子署名対象データｍ＝Ｈ1（Ｒ）（＋）ｃを計算する手段と、
前記点Ｓ及び前記署名者公開鍵ＱID_Aに関し、楕円曲線上のペアリングに基づく点Ｖ＝ｅn（Ｓ，ＱID_A）を計算する手段と、
得られた点Ｖ、前記点Ｒ、前記点ｇ及び値ｈに関する判定式Ｖ＝Ｒｇｈ が成立するか否かを判定する手段と、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（ｃ，Ｘ）を受け入れる手段と
を備えたことを特徴とする電子署名検証装置。
【請求項７】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置であって、
署名者ＩＤ情報IDA及び検証者ＩＤ情報IDBを含む公開情報要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した「署名者公開鍵ＰID_A＝s(IDA)Ｐ（但し、s(ID)は秘密鍵生成関数）」、「検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、IDBは検証者ＩＤ情報）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，Ｈ3’，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、前記関数Ｈ3’は巡回群＜Ｐ＞からなるｎねじれ群の点と巡回群＜Ｐ＞からなるｎねじれ群の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」が記憶される第２公開情報記憶手段と、
署名者ＩＤ情報IDAを含む秘密鍵要求を前記鍵生成センター装置に送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＱsID_A＝s(IDA)-1Ｑが記憶される第２秘密鍵記憶手段と、
電子署名生成用の乱数ｘを生成する手段と、
前記乱数ｘ及び前記点ｇに基づいて、点Ｎ＝ｇ＾ｘ-1を計算する手段（但し、＾は、べき乗を表す）と、
前記乱数ｘ及び前記署名者公開鍵ＰID_Aに基づいて、点Ｒ＝ｘＰID_Aを計算する手段と、
前記乱数ｘ及び前記検証者公開鍵ＰID_Bに基づいて、点Ｓ＝ｘ-1ＰID_Bを計算する手段と、
電子署名対象データｍに対し、前記点Ｎ、前記関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｎ）（＋）ｍを計算する手段（但し、（＋）は排他的論理和）と、
得られた値ｃ、前記点Ｒ、前記点Ｓ及び前記関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する手段と、
得られた値ｈ、前記乱数ｘ及び前記署名者秘密鍵ＱsID_Aに基づいて、点Ｔ＝（ｘ＋ｈ）-1ＱsID_Aを計算する手段と、
前記点Ｓ及び前記点Ｔを互いに加算して点Ｘ（＝Ｓ＋Ｔ）に圧縮する手段と、
前記点Ｘ、前記点Ｒ及び前記値ｃからなる電子署名σ＝（ｃ，Ｒ，Ｘ）を前記電子署名検証装置に送信する手段とを備えており、
前記電子署名σ＝（ｃ，Ｒ，Ｘ）は、前記射影Ψに基づく点Ｓ＝Ψ（Ｘ）の計算と当該点Ｓに基づく点Ｔ＝Ｘ−Ｓの計算とにより、圧縮前の電子署名σ’＝（ｃ，Ｒ，Ｓ，Ｔ）内の点Ｓ，Ｔを取得可能であることを特徴とする電子署名生成装置。
【請求項８】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名生成装置に通信可能な電子署名検証装置であって、
前記電子署名生成装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した「署名者公開鍵ＰsID_A＝s(IDA)Ｐ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，Ｈ3’，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、前記関数Ｈ3’は巡回群＜Ｐ＞からなるｎねじれ群の点と巡回群＜Ｐ＞からなるｎねじれ群の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」が記憶される第３公開情報記憶手段と、
前記電子署名検証装置の検証者ＩＤ情報IDBを含む秘密鍵要求を前記鍵生成センター装置に送信する手段と、
前記鍵生成センター装置から受信した検証者秘密鍵ＱsID_B＝s(IDB)-1Ｑが記憶される第３記憶鍵記憶手段と、
前記電子署名生成装置から電子署名σ＝（ｃ，Ｒ，Ｘ）を受信する手段（但し、点ＸはＸ＝Ｓ＋Ｔに圧縮されており、点ＴはＴ＝（ｘ＋ｈ）-1ＱsID_Aであり、ｘは乱数であり、ＱsID_Aは署名者秘密鍵ＰsID_A＝s(IDA)-1Ｑであり、値ｈはｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）であり、点ＳはＳ＝ｘ-1ＰID_Bであり、ＰID_Bは検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、IDBは検証者ＩＤ情報）であり、点ＲはＲ＝ｘＰID_Aであり、ＰID_Aは署名者公開鍵ＰID_A＝s(IDA)Ｐであり、値ｃはｃ＝Ｈ1（Ｒ）（＋）ｍ（但し、（＋）は排他的論理和）であり、ｍは電子署名対象データである）と、
前記受信した電子署名σ＝（ｃ，Ｒ，Ｘ）及び前記公開情報内の射影Ψに基づいて、点Ｓ＝Ψ（Ｘ）を計算する手段と、
得られた点Ｓ及び前記電子署名σ＝（ｃ，Ｒ，Ｘ）内の点Ｘに基づいて、点Ｔ＝Ｘ−Ｓを計算する手段と、
前記点Ｒ、前記点Ｓ、前記値ｃ及び前記関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する手段と、
得られた値ｈ、前記点Ｒ、前記点Ｔ及び前記署名者公開鍵ＰID_Aに関し、楕円曲線上のペアリングに基づく点Ｖ＝ｅn（Ｒ＋ｈＰID_A，Ｔ）を計算する手段と、
前記点Ｓ及び前記検証者秘密鍵ＱsID_Bに関し、楕円曲線上のペアリングに基づく点Ｎ＝ｅn（Ｓ，ＱsID_B）を計算する手段と、
得られた点Ｎ、前記値ｃ及び前記関数Ｈ1に基づいて、電子署名対象データｍ＝Ｈ1（Ｎ）（＋）ｃを計算する手段と、
前記点Ｖ及び前記点ｇに関する判定式Ｖ＝ｇが成立するか否かを判定する手段と、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（ｃ，Ｒ，Ｘ）を受け入れる手段と
を備えたことを特徴とする電子署名検証装置。
【請求項９】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、電子署名生成装置及び電子署名検証装置に通信可能な鍵生成センター装置のプログラムであって、
前記鍵生成センター装置のコンピュータを、
鍵生成センター用秘密鍵Lとしての乱数を生成する手段、
楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞に関し、それぞれ巡回群＜Ｐ＞から点Ｐを選択し、巡回群＜Ｑ＞から点Ｑを選択する手段、
前記鍵生成センター用秘密鍵L及び点Ｑに基づいて、点Ｑpub＝LＱを計算する手段と、
前記点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報を前記コンピュータの記憶装置に書き込む手段、
前記鍵生成センター用秘密鍵Lを前記コンピュータの記憶装置に書き込む手段、
前記電子署名生成装置又は前記電子署名検証装置から署名者ＩＤ情報IDAを含む公開情報要求を受信すると、前記署名者ＩＤ情報IDA、前記点Ｐ及び前記一方向性関数ｈ（ ）に基づいて、署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算する手段、
前記署名者公開鍵ＰA及び前記公開情報を前記公開情報要求の送信元に返信する手段、
前記電子署名生成装置から秘密鍵要求を受信すると、前記署名者公開鍵ＰA及び前記鍵生成センター用秘密鍵Lに基づいて、署名者秘密鍵ＫA＝LＰAを計算する手段、
前記署名者秘密鍵ＫAを前記電子署名生成装置に返信する手段、として機能させ、
前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和を前記ｎねじれ群Ｅ[ｎ]としたことにより、前記点Ｐから計算される点Ｒと、前記点Ｑから計算される点Ｓとから前記電子署名生成装置により生成される電子署名σ’＝（Ｒ，Ｓ）を各点Ｒ，Ｓ同士の加算により点Ｔ（＝Ｒ＋Ｓ）からなる電子署名σ＝（Ｔ）に圧縮可能とし、且つ、前記電子署名検証装置に送信される電子署名σ＝（Ｔ）から、前記射影Ψに基づく点Ｒ＝Ψ（Ｔ）の計算と当該点Ｒに基づく点Ｓ＝Ｔ−Ｒの計算とにより、圧縮前の電子署名σ’＝（Ｒ，Ｓ）内の点Ｒ，Ｓを取得可能としたプログラム。
【請求項１０】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置のプログラムであって、
前記電子署名生成装置のコンピュータを、
自己の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した「署名者公開鍵ＰA＝ｈ（IDA）Ｐ」及び「点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記点Ｑpubは鍵生成センター用秘密鍵Lと点Ｑとの積（点Ｑpub＝LＱ）である）」を前記コンピュータの記憶装置に書き込む手段、
前記鍵生成センター装置に秘密鍵要求を送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＫA＝LＰAを前記コンピュータの記憶装置に書き込む手段、
電子署名生成用の乱数ｋを生成する手段、
前記乱数ｋ及び前記公開情報内の点Ｑに基づいて、点Ｒ＝ｋＱを計算する手段、
電子署名対象データｍに対し、前記乱数ｋ、前記署名者秘密鍵ＫA、前記署名者公開鍵ＰA、前記公開情報内の一方向性関数ｈ（ ）及び前記点Ｒのｘ座標値ｘに基づいて、点Ｓ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA を計算する手段、
前記点Ｒ，Ｓを互いに加算して点Ｔ（＝Ｒ＋Ｓ）に圧縮する手段、
前記点Ｔからなる電子署名σ＝（Ｔ）及び前記電子署名対象データｍを前記電子署名検証装置に送信する手段、として機能させ、
前記電子署名σ＝（Ｔ）は、前記射影Ψに基づく点Ｒ＝Ψ（Ｔ）の計算と当該点Ｒに基づく点Ｓ＝Ｔ−Ｒの計算とにより、圧縮前の電子署名σ’＝（Ｒ，Ｓ）内の点Ｒ，Ｓを取得可能であるようにしたプログラム。
【請求項１１】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名生成装置に通信可能な電子署名検証装置のプログラムであって、
前記電子署名検証装置のコンピュータを、
前記電子署名生成装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した「署名者公開鍵ＰA＝ｈ（IDA）Ｐ」及び「点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記点Ｑpubは鍵生成センター用秘密鍵Lと点Ｑとの積（点Ｑpub＝LＱ）である）」を前記電子署名検証装置の記憶装置に書き込む手段、
前記電子署名生成装置から電子署名対象データｍ及び電子署名σ＝（Ｔ）を受信する手段（但し、点ＴはＴ＝Ｒ＋Ｓに圧縮されており、点ＲはＲ＝ｋＱであり（ｋ：乱数）、点ＳはＳ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA）であり、ｘは点Ｒのｘ座標値であり、ＫAは署名者秘密鍵ＫA＝LＱである（L：乱数））、
前記受信した電子署名σ＝（Ｔ）及び前記公開情報内の射影Ψに基づいて、点Ｒ＝Ψ（Ｔ）を計算する手段、
得られた点Ｒ及び前記電子署名σ＝（Ｔ）に基づいて、点Ｓ＝Ｔ−Ｒを計算する手段、
前記電子署名σ＝（Ｔ）から得られた点Ｓ，Ｒに関し、前記署名者公開鍵ＰA及び公開情報を用いて、楕円曲線上のペアリングに基づく判定式ｅn（Ｓ，Ｒ）＝ｅn（ＰA，Ｑ）h(m)ｅn（ＰA，Ｑpub）x が成立するか否かを判定する手段、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（Ｔ）を受け入れる手段、
として機能させるためのプログラム。
【請求項１２】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置のプログラムであって、
前記電子署名生成装置のコンピュータを、
前記電子署名検証装置の検証者ＩＤ情報IDBを含む公開情報要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した「検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」を前記コンピュータの記憶装置に書き込む手段、
署名者ＩＤ情報IDAを含む秘密鍵要求を前記鍵生成センター装置に送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＰsID_A＝s(IDA)-1Ｐを前記コンピュータの記憶装置に書き込む手段、
電子署名生成用の乱数ｘを生成する手段、
前記乱数ｘ及び前記点ｇに基づいて、点Ｒ＝ｇｘを計算する手段、
電子署名対象データｍに対し、前記点Ｒ、前記関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｒ）（＋）ｍを計算する手段（但し、（＋）は排他的論理和）、
前記値ｃ、前記点Ｒ及び前記関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する手段、
前記値ｈ、前記乱数ｘ及び前記署名者秘密鍵ＰsID_Aに基づいて、点Ｓ＝（ｘ＋ｈ）ＰsID_Aを計算する手段、
前記乱数ｘ及び前記検証者公開鍵ＰID_Bに基づいて、点Ｔ＝ｘＰID_Bを計算する手段、
前記点Ｔ及び前記同型写像ξに基づいて、点ξ（Ｔ）を計算する手段、
前記点Ｓ，ξ（Ｔ）を互いに加算して点Ｘ（＝Ｓ＋ξ（Ｔ））に圧縮する手段、
前記点Ｘ及び前記値ｃからなる電子署名σ＝（ｃ，Ｘ）を前記電子署名検証装置に送信する手段、として機能させ、
前記電子署名σ＝（ｃ，Ｘ）は、前記射影Ψに基づく点Ｓ＝Ψ（Ｘ）の計算と当該点Ｓに基づく点Ｔ＝ξ-1（Ｘ−Ｓ）の計算とにより、圧縮前の電子署名σ’＝（ｃ，Ｓ，Ｔ）内の点Ｓ，Ｔを取得可能であるようにしたプログラム。
【請求項１３】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名生成装置に通信可能な電子署名検証装置のプログラムであって、
前記電子署名検証装置のコンピュータを、
前記電子署名生成装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した「署名者公開鍵ＱsID_A＝s(IDA)Ｑ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」を前記コンピュータの記憶装置に書き込む手段、
前記電子署名検証装置の検証者ＩＤ情報IDBを含む秘密鍵要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した検証者秘密鍵ＱsID_B＝s(IDB)-1Ｑを前記コンピュータの記憶装置に書き込む手段、
前記電子署名生成装置から電子署名σ＝（ｃ，Ｘ）を受信する手段（但し、点ＸはＸ＝Ｓ＋ξ（Ｔ）に圧縮されており、点ＴはＴ＝ｘＰID_Bであり、ｘは乱数であり、ＰID_Bは検証者公開鍵ＰID_B＝s(IDB)Ｐであり、点ＳはＳ＝（ｘ＋ｈ）ＰsID_Aであり、ＰsID_Aは署名者秘密鍵ＰsID_A＝s(IDA)-1Ｐであり、値ｈはｈ＝Ｈ2（Ｒ，ｃ）であり、点ＲはＲ＝ｇｘであり、値ｃはｃ＝Ｈ1（Ｒ）（＋）ｍ（但し、（＋）は排他的論理和）であり、ｍは電子署名対象データである）、
前記受信した電子署名σ＝（ｃ，Ｘ）及び前記公開情報内の射影Ψに基づいて、点Ｓ＝Ψ（Ｘ）を計算する手段、
得られた点Ｓ及び前記電子署名σ＝（ｃ，Ｘ）内の点Ｘに基づいて、点Ｔ＝ξ-1（Ｘ−Ｓ）を計算する手段、
得られた点Ｔ及び前記検証者秘密鍵ＱsID_Bに関し、楕円曲線上のペアリングに基づく点Ｒ＝ｅn（Ｔ，ＱsID_B）を計算する手段、
得られた点Ｒ、前記値ｃ及び前記関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する手段、
前記点Ｒ、前記値ｃ及び前記関数Ｈ2に基づいて、電子署名対象データｍ＝Ｈ1（Ｒ）（＋）ｃを計算する手段、
前記点Ｓ及び前記署名者公開鍵ＱID_Aに関し、楕円曲線上のペアリングに基づく点Ｖ＝ｅn（Ｓ，ＱID_A）を計算する手段、
得られた点Ｖ、前記点Ｒ、前記点ｇ及び値ｈに関する判定式Ｖ＝Ｒｇｈ が成立するか否かを判定する手段、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（ｃ，Ｘ）を受け入れる手段、
として機能させるためのプログラム。
【請求項１４】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置のプログラムであって、
前記電子署名生成装置のコンピュータを、
自装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した「署名者公開鍵ＰID_A＝s(IDA)Ｐ（但し、s(ID)は秘密鍵生成関数）」、「検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、IDBは検証者ＩＤ情報）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，Ｈ3’，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、前記関数Ｈ3’は巡回群＜Ｐ＞からなるｎねじれ群の点と巡回群＜Ｐ＞からなるｎねじれ群の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」を前記コンピュータの記憶装置に書き込む手段、
署名者ＩＤ情報IDAを含む秘密鍵要求を前記鍵生成センター装置に送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＱsID_A＝s(IDA)-1Ｑを前記コンピュータの記憶装置に書き込む手段、
電子署名生成用の乱数ｘを生成する手段、
前記乱数ｘ及び前記点ｇに基づいて、点Ｎ＝ｇ＾ｘ-1を計算する手段（但し、＾は、べき乗を表す）、
前記乱数ｘ及び前記署名者公開鍵ＰID_Aに基づいて、点Ｒ＝ｘＰID_Aを計算する手段、
前記乱数ｘ及び前記検証者公開鍵ＰID_Bに基づいて、点Ｓ＝ｘ-1ＰID_Bを計算する手段、
電子署名対象データｍに対し、前記点Ｎ、前記関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｎ）（＋）ｍを計算する手段（但し、（＋）は排他的論理和）、
得られた値ｃ、前記点Ｒ、前記点Ｓ及び前記関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する手段、
得られた値ｈ、前記乱数ｘ及び前記署名者秘密鍵ＱsID_Aに基づいて、点Ｔ＝（ｘ＋ｈ）-1ＱsID_Aを計算する手段、
前記点Ｓ及び前記点Ｔを互いに加算して点Ｘ（＝Ｓ＋Ｔ）に圧縮する手段、
前記点Ｘ、前記点Ｒ及び前記値ｃからなる電子署名σ＝（ｃ，Ｒ，Ｘ）を前記電子署名検証装置に送信する手段、として機能させ、
前記電子署名σ＝（ｃ，Ｒ，Ｘ）は、前記射影Ψに基づく点Ｓ＝Ψ（Ｘ）の計算と当該点Ｓに基づく点Ｔ＝Ｘ−Ｓの計算とにより、圧縮前の電子署名σ’＝（ｃ，Ｒ，Ｓ，Ｔ）内の点Ｓ，Ｔを取得可能であるようにしたプログラム。
【請求項１５】
楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名生成装置に通信可能な電子署名検証装置のプログラムであって、
前記電子署名検証装置のコンピュータを、
前記電子署名生成装置の署名者ＩＤ情報IDAを含む公開情報要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した「署名者公開鍵ＰsID_A＝s(IDA)Ｐ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，Ｈ3’，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、前記関数Ｈ3’は巡回群＜Ｐ＞からなるｎねじれ群の点と巡回群＜Ｐ＞からなるｎねじれ群の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」を前記コンピュータの記憶装置に書き込む手段、
前記電子署名検証装置の検証者ＩＤ情報IDBを含む秘密鍵要求を前記鍵生成センター装置に送信する手段、
前記鍵生成センター装置から受信した検証者秘密鍵ＱsID_B＝s(IDB)-1Ｑを前記コンピュータの記憶装置に書き込む手段、
前記電子署名生成装置から電子署名σ＝（ｃ，Ｒ，Ｘ）を受信する手段（但し、点ＸはＸ＝Ｓ＋Ｔに圧縮されており、点ＴはＴ＝（ｘ＋ｈ）-1ＱsID_Aであり、ｘは乱数であり、ＱsID_Aは署名者秘密鍵ＰsID_A＝s(IDA)-1Ｑであり、値ｈはｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）であり、点ＳはＳ＝ｘ-1ＰID_Bであり、ＰID_Bは検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、IDBは検証者ＩＤ情報）であり、点ＲはＲ＝ｘＰID_Aであり、ＰID_Aは署名者公開鍵ＰID_A＝s(IDA)Ｐであり、値ｃはｃ＝Ｈ1（Ｒ）（＋）ｍ（但し、（＋）は排他的論理和）であり、ｍは電子署名対象データである）、
前記受信した電子署名σ＝（ｃ，Ｒ，Ｘ）及び前記公開情報内の射影Ψに基づいて、点Ｓ＝Ψ（Ｘ）を計算する手段、
得られた点Ｓ及び前記電子署名σ＝（ｃ，Ｒ，Ｘ）内の点Ｘに基づいて、点Ｔ＝Ｘ−Ｓを計算する手段、
前記点Ｒ、前記点Ｓ、前記値ｃ及び前記関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する手段、
得られた値ｈ、前記点Ｒ、前記点Ｔ及び前記署名者公開鍵ＰID_Aに関し、楕円曲線上のペアリングに基づく点Ｖ＝ｅn（Ｒ＋ｈＰID_A，Ｔ）を計算する手段、
前記点Ｓ及び前記検証者秘密鍵ＱsID_Bに関し、楕円曲線上のペアリングに基づく点Ｎ＝ｅn（Ｓ，ＱsID_B）を計算する手段、
得られた点Ｎ、前記値ｃ及び前記関数Ｈ1に基づいて、電子署名対象データｍ＝Ｈ1（Ｎ）（＋）ｃを計算する手段、
前記点Ｖ及び前記点ｇに関する判定式Ｖ＝ｇが成立するか否かを判定する手段、
前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（ｃ，Ｒ，Ｘ）を受け入れる手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上のペアリングに基づく電子署名システム、装置及びプログラムに係り、例えば、署名者と検証者との間で送受信する電子署名のデータ長を削減し得る電子署名システム、装置及びプログラムに関する。
【背景技術】
【０００２】
インターネットの普及に伴い、様々なオンラインサービスが提供され始めている。これに伴い、個人情報を保護する暗号技術の必要性はますます高まっており、ネットワークを介して安全に多数の相手との暗号通信を行う暗号技術が求められている。
【０００３】
最初に鍵を用いる暗号方式として共通鍵暗号方式が考案された。共通鍵暗号方式は、暗号通信に先立って送受信者間で鍵を秘密に共有する必要があり、鍵が第三者に漏えいした場合には暗号情報を解読される危険性が高い技術である。そのため、送受信者間で鍵をどのように秘密に配送するのか、という問題がある。
【０００４】
この鍵配送の問題を解決する公開鍵暗号方式は、ディフィー(Diffie)、ヘルマン(Hellman)によって考案された。ディフィー-ヘルマンの方式は、鍵配送の問題を解決すると共に、電子署名を可能にした画期的な技術である。
【０００５】
しかしながら、ディフィー-ヘルマンの方式では、公開鍵の正当性を認証機関が証明する必要があるため、利用者が予め認証機関へ公開鍵を登録しておく必要がある。一方、予め鍵を秘密に通信する必要がなく、受信者のＩＤ情報を用いて暗号通信や電子署名を可能としたＩＤ情報に基づく暗号方式がシャミア(Shamir)により考案された。
【０００６】
シャミアの方式は、ディフィー-ヘルマンの方式と比べ、公開鍵の正当性を証明する必要がないため、認証機関への登録が不要であり、また新しい利用者が増えても公開鍵リストを更新する必要がないという利点がある。
【０００７】
しかしながら、シャミアの方式の暗号システムを効率的に構成する技術は知られていない。すなわち、シャミアの方式の暗号システムは、計算量が非常に多く、現実的でないという不都合がある。
【０００８】
近年、計算量が比較的少なく、現実的な暗号方式として、楕円曲線を用いた暗号方式が研究されてきている。これに伴い、楕円曲線上で定義されるペアリングと呼ばれる写像に基づいて、ＩＤ情報に基づく暗号方式をより効率的に構成することが可能となった。このため、ＩＤ情報に基づく暗号方式は、楕円曲線のペアリングに基づく多数の暗号方式が提案されている。
【０００９】
（ＩＤ情報に基づく暗号方式の構成について）
楕円曲線のペアリングについて簡単に説明する。
【００１０】
有限体Ｆq上で定義される楕円曲線Ｅ/Ｆqの有理点のなす群Ｅ/Ｆqkに含まれる元Ｐについて、楕円スカラー倍ｎＰ＝Ｏを満たす元の集合をｎねじれ点と呼び、Ｅ[ｎ]と記述する(Ｅ[ｎ]⊂Ｅ（Ｆqk）)。ここでＯは無限遠点を意味する。Ｅ[ｎ]はランク(rank)２の自由アーベル(Abel)群であることが知られている。ここで、自由群とは、群の基本定義のみを満たし、それ以外の条件を持たない群を意味する。このとき、楕円曲線上のペアリングｅn（，）は、Ｅ[ｎ]×Ｅ[ｎ]から有限体Ｆqkの乗法群Ｆ*qkへの写像ｅn：Ｅ[ｎ]×Ｅ[ｎ]→Ｆqkであって、以下のような非退化性、反対称性、双線型性、といった性質を有する。
【００１１】
［非退化性］
∀Ｑ∈Ｅ[ｎ]に対して、ｅn（Ｐ，Ｑ）＝１が成立するとき、Ｐ＝Ｏである。
【００１２】
［反対称性］
∀Ｐ,∀Ｑ ∈ Ｅ[ｎ]に対して、ｅn（Ｐ，Ｑ）＝ｅn（Ｑ，Ｐ）-1 
［双線形性］
∀Ｐ,∀Ｑ,∀Ｒ ∈ Ｅ[ｎ]に対して、
ｅn（Ｐ＋Ｑ，Ｒ）＝ｅn（Ｐ，Ｒ）ｅn（Ｑ，Ｒ）、
ｅn（Ｐ，Ｑ＋Ｒ）＝ｅn（Ｐ，Ｑ）ｅn（Ｐ，Ｒ）
が成立する。
【００１３】
また、ペアリングは双線形性を満たすことから、任意の整数ｍに対して以下の性質を持つことが知られている。
【００１４】
ｅn（ｍＰ，Ｑ）＝ｅn（Ｐ，ｍＱ）＝ｅn（Ｐ，Ｑ）m 
楕円曲線上のペアリングを暗号に応用する場合は、以下のような条件（i）〜（iii）を満たすように楕円曲線Ｅとｎねじれ群Ｅ[ｎ]を選ぶ必要がある。
【００１５】
（i）ｎの最大素因子は１６０ビット以上
（ii）ｑk ＞ ２1024 
【数１】
2008178035.tif 000003
【００１６】
以下、これらの条件（i）〜（iii）を満たす楕円曲線を「ペアリングの計算が可能な安全な楕円曲線」と呼ぶ。
【００１７】
（ＩＤ情報に基づく暗号方式における署名方式）
従来のＩＤ情報に基づく暗号方式における署名方式は以下の通りである（例えば、非特許文献１又は特許文献１参照。）。
【００１８】
ここで、ＩＤ情報に基づく署名方式とは、センターにより公開されている情報と署名者のＩＤ情報があれば、署名者の電子署名の検証が可能となる方式である。
【００１９】
［パラメータ準備］
センターは、ペアリングの計算が可能な安全な楕円曲線を生成すると共に、パラメータＰU（Ｕ＝Ａ，Ｂ，…），Ｑ，Ｑpub，ｈ（ｘ）を準備する。  
ＰU：利用者ＵのＩＤ情報ｕを楕円曲線上のｎねじれ点に変換した点ＰU＝Ｅ[ｎ]  
Ｑ：ｎねじれ点Ｑ∈Ｅ[ｎ]  
Ｑpub：センターの秘密鍵L∈Ｚnを用いて表されるｎねじれ点Ｑpub＝LＱ  
ｈ（ｘ）：バイナリ値のデータｘから乗法群Ｚn*のデータへ変換する一方向性関数
なお、必ずしもペアリングの計算が可能な安全な楕円曲線を生成する必要はないが、セキュリティ上推奨するため、ここでは生成することにしている。
【００２０】
また、センターは、利用者ＵのＩＤ情報ｕに対応する秘密鍵ＫU＝LＰUを計算し、得られた秘密鍵ＫUを安全な方法で利用者Ｕに配布しておく。
【００２１】
［署名生成］
署名者Ａは、電子署名対象データをｍとする。
【００２２】
署名者Ａは、乱数ｋ∈Ｚn*を生成する。
【００２３】
署名者Ａは、点Ｒ＝ｋＱを算出する。
【００２４】
署名者Ａは、点Ｒのｘ座標をｘとし、点Ｓを次式のように計算する。
【００２５】
点Ｓ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA 
＝［ｈ(ｍ)/ｋ］ＰA＋［ｘL/ｋ］ＰA 
＝［（ｈ(ｍ)＋ｘL）/ｋ］ＰA 
署名者Ａは電子署名σ＝（Ｒ，Ｓ）及び電子署名対象データｍを検証者に送信する。
【００２６】
［署名検証］
検証者は、σ＝（Ｒ，Ｓ）及びｍを受けると、次式により署名者Ａの電子署名σを検証する。検証の結果、次式を満たす場合に電子署名σを受入れ(accept)、満たさない場合に電子署名σを拒否(reject)する。
【数２】
2008178035.tif 000004
【非特許文献１】境隆一, 笠原正雄, “楕円曲線上のペアリングに基づく二、三の暗号方式（その２）”, コンピュータセキュリティシンポジウム(CSS2002), pp. 275-282, 2002
【特許文献１】特開２００４−２０１１２４号公報
【非特許文献２】N.McCullagh, P.Barreto, ”Efficient and Forward-Secure Identity-Based Signcryption”, Cryptology ePrint Archive, Report 2004/117, 2004
【発明の開示】
【発明が解決しようとする課題】
【００２７】
しかしながら、以上のようなペアリングに基づく署名方式は、通常は特に問題は無いが、本発明者の検討によれば、電子署名のデータ長を削減したい観点から改良の余地があると考えられる。
【００２８】
補足すると、署名方式としては特に問題がないが、回線の細いネットワークで実行される場合のように、利用者のネットワーク環境によっては、署名者と検証者との間で電子署名の送受信が遅くなり、利用に適さなくなる可能性が残っている。
【００２９】
このため、ペアリングに基づく署名方式では、電子署名のデータ長を削減する必要があると考えられる。
【００３０】
本発明は上記実情を考慮してなされたもので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減し得る電子署名システム、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００３１】
第１の発明は、楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、互いに通信可能な鍵生成センター装置、電子署名生成装置及び電子署名検証装置を備えた電子署名システムであって、前記鍵生成センター装置としては、鍵生成センター用秘密鍵Lとしての乱数を生成する手段と、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞に関し、それぞれ巡回群＜Ｐ＞から点Ｐを選択し、巡回群＜Ｑ＞から点Ｑを選択する手段と、前記鍵生成センター用秘密鍵L及び点Ｑに基づいて、点Ｑpub＝LＱを計算する手段と、前記点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報が記憶される第１公開情報記憶手段と、前記鍵生成センター用秘密鍵Lが記憶される第１秘密鍵記憶手段と、前記電子署名生成装置又は前記電子署名検証装置から署名者ＩＤ情報IDAを含む公開情報要求を受信すると、前記署名者ＩＤ情報IDA、前記点Ｐ及び前記一方向性関数ｈ（ ）に基づいて、署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算する手段と、前記署名者公開鍵ＰA及び前記公開情報を前記公開情報要求の送信元に返信する手段と、前記電子署名生成装置から秘密鍵要求を受信すると、前記署名者公開鍵ＰA及び前記鍵生成センター用秘密鍵Lに基づいて、署名者秘密鍵ＫA＝LＰAを計算する手段と、前記署名者秘密鍵ＫAを前記電子署名生成装置に返信する手段とを備えており、前記電子署名生成装置としては、前記鍵生成センター装置から受信した署名者公開鍵ＰA及び公開情報が記憶される第２公開情報記憶手段と、前記鍵生成センター装置から受信した署名者秘密鍵ＫAが記憶される第２秘密鍵記憶手段と、電子署名生成用の乱数ｋを生成する手段と、前記乱数ｋ及び前記公開情報内の点Ｑに基づいて、点Ｒ＝ｋＱを計算する手段と、電子署名対象データｍに対し、前記乱数ｋ、前記署名者秘密鍵ＫA、前記署名者公開鍵ＰA、前記公開情報内の一方向性関数ｈ（ ）及び前記点Ｒのｘ座標値ｘに基づいて、点Ｓ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA を計算する手段と、前記点Ｒ，Ｓを互いに加算して点Ｔ（＝Ｒ＋Ｓ）に圧縮する手段と、前記点Ｔからなる電子署名σ＝（Ｔ）及び前記電子署名対象データｍを前記電子署名検証装置に送信する手段とを備えており、前記電子署名検証装置としては、前記鍵生成センター装置から受信した署名者公開鍵ＰA及び公開情報が記憶される第３公開情報記憶手段と、前記電子署名生成装置から電子署名σ＝（Ｔ）及び電子署名対象データｍを受信すると、前記公開情報内の射影Ψに基づいて、点Ｒ＝Ψ（Ｔ）を計算する手段と、得られた点Ｒ及び前記電子署名σ＝（Ｔ）に基づいて、点Ｓ＝Ｔ−Ｒを計算する手段と、前記電子署名σ＝（Ｔ）から得られた点Ｓ，Ｒに関し、前記署名者公開鍵ＰA及び公開情報を用いて、楕円曲線上のペアリングに基づく判定式ｅn（Ｓ，Ｒ）＝ｅn（ＰA，Ｑ）h(m)ｅn（ＰA，Ｑpub）x が成立するか否かを判定する手段と、前記判定の結果、前記判定式が成立する場合には前記電子署名σ＝（Ｔ）を受け入れる手段とを備えた電子署名システムである。
【００３２】
第２の発明は、楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置であって、前記電子署名検証装置の検証者ＩＤ情報IDBを含む公開情報要求を前記鍵生成センター装置に送信する手段と、前記鍵生成センター装置から受信した「検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、s(ID)は秘密鍵生成関数）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」が記憶される第２公開情報記憶手段と、署名者ＩＤ情報IDAを含む秘密鍵要求を前記鍵生成センター装置に送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＰsID_A＝s(IDA)-1Ｐが記憶される第２秘密鍵記憶手段と、電子署名生成用の乱数ｘを生成する手段と、前記乱数ｘ及び前記点ｇに基づいて、点Ｒ＝ｇｘを計算する手段と、電子署名対象データｍに対し、前記点Ｒ、前記関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｒ）（＋）ｍを計算する手段（但し、（＋）は排他的論理和）と、前記値ｃ、前記点Ｒ及び前記関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する手段と、前記値ｈ、前記乱数ｘ及び前記署名者秘密鍵ＰsID_Aに基づいて、点Ｓ＝（ｘ＋ｈ）ＰsID_Aを計算する手段と、前記乱数ｘ及び前記検証者公開鍵ＰID_Bに基づいて、点Ｔ＝ｘＰID_Bを計算する手段と、前記点Ｔ及び前記同型写像ξに基づいて、点ξ（Ｔ）を計算する手段と、前記点Ｓ，ξ（Ｔ）を互いに加算して点Ｘ（＝Ｓ＋ξ（Ｔ））に圧縮する手段と、前記点Ｘ及び前記値ｃからなる電子署名σ＝（ｃ，Ｘ）を前記電子署名検証装置に送信する手段とを備えており、前記電子署名σ＝（ｃ，Ｘ）は、前記射影Ψに基づく点Ｓ＝Ψ（Ｘ）の計算と当該点Ｓに基づく点Ｔ＝ξ-1（Ｘ−Ｓ）の計算とにより、圧縮前の電子署名σ’＝（ｃ，Ｓ，Ｔ）内の点Ｓ，Ｔを取得可能である電子署名生成装置である。
【００３３】
第３の発明は、楕円曲線上のペアリングｅn（ ， ）に基づく電子署名方式に用いられ、鍵生成センター装置及び電子署名検証装置に通信可能な電子署名生成装置であって、署名者ＩＤ情報IDA及び検証者ＩＤ情報IDBを含む公開情報要求を前記鍵生成センター装置に送信する手段と、前記鍵生成センター装置から受信した「署名者公開鍵ＰID_A＝s(IDA)Ｐ（但し、s(ID)は秘密鍵生成関数）」、「検証者公開鍵ＰID_B＝s(IDB)Ｐ（但し、IDBは検証者ＩＤ情報）」及び「点Ｐ，点Ｑ，点ｇ＝ｅn（Ｐ，Ｑ）、関数Ｈ1，Ｈ2，Ｈ3’，楕円曲線上の射影Ψ，同型写像ξを含む公開情報（但し、前記点Ｐは、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞のうちの巡回群＜Ｐ＞から選択された点であり、前記点Ｑは前記巡回群＜Ｑ＞から選択された点であり、前記２つの巡回群＜Ｐ＞，＜Ｑ＞の直和は前記ｎねじれ群Ｅ[ｎ]であり、前記関数Ｈ1はｎねじれ群Ｅ[ｎ]の点をバイナリ値に変換する関数であり、前記関数Ｈ2はｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、前記関数Ｈ3’は巡回群＜Ｐ＞からなるｎねじれ群の点と巡回群＜Ｐ＞からなるｎねじれ群の点とバイナリ値とを連結したデータを乗法群Ｚn*に変換する関数であり、同型写像ξは＜Ｐ＞から＜Ｑ＞への同型写像である）」が記憶される第２公開情報記憶手段と、署名者ＩＤ情報IDAを含む秘密鍵要求を前記鍵生成センター装置に送信した後、前記鍵生成センター装置から受信した署名者秘密鍵ＱsID_A＝s(IDA)-1Ｑが記憶される第２秘密鍵記憶手段と、電子署名生成用の乱数ｘを生成する手段と、前記乱数ｘ及び前記点ｇに基づいて、点Ｎ＝ｇ＾ｘ-1を計算する手段（但し、＾は、べき乗を表す）と、前記乱数ｘ及び前記署名者公開鍵ＰID_Aに基づいて、点Ｒ＝ｘＰID_Aを計算する手段と、前記乱数ｘ及び前記検証者公開鍵ＰID_Bに基づいて、点Ｓ＝ｘ-1ＰID_Bを計算する手段と、電子署名対象データｍに対し、前記点Ｎ、前記関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｎ）（＋）ｍを計算する手段（但し、（＋）は排他的論理和）と、得られた値ｃ、前記点Ｒ、前記点Ｓ及び前記関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する手段と、得られた値ｈ、前記乱数ｘ及び前記署名者秘密鍵ＱsID_Aに基づいて、点Ｔ＝（ｘ＋ｈ）-1ＱsID_Aを計算する手段と、前記点Ｓ及び前記点Ｔを互いに加算して点Ｘ（＝Ｓ＋Ｔ）に圧縮する手段と、前記点Ｘ、前記点Ｒ及び前記値ｃからなる電子署名σ＝（ｃ，Ｒ，Ｘ）を前記電子署名検証装置に送信する手段とを備えており、前記電子署名σ＝（ｃ，Ｒ，Ｘ）は、前記射影Ψに基づく点Ｓ＝Ψ（Ｘ）の計算と当該点Ｓに基づく点Ｔ＝Ｘ−Ｓの計算とにより、圧縮前の電子署名σ’＝（ｃ，Ｒ，Ｓ，Ｔ）内の点Ｓ，Ｔを取得可能である電子署名生成装置である。
【００３４】
なお、第１の発明においては各装置の集合体を「システム」として表現し、第２及び第３の発明においては各装置のうちの「電子署名生成装置」として表現したが、これに限らず、第１乃至第３の各発明は、各装置の集合体又は装置毎に、「装置」、「プログラム」、「プログラムを記憶したコンピュータ読取り可能な記憶媒体」、「方法」として表現してもよいことは言うまでもない。
【００３５】
（作用）
第１の発明によれば、鍵生成センター装置において、楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]を２つの巡回群＜Ｐ＞，＜Ｑ＞の直和とし、＜Ｐ＞から選択した点Ｐと、＜Ｑ＞から選択した点Ｑと、楕円曲線上の射影Ψとを公開した構成により、電子署名生成装置では、点Ｑに基づく点Ｒと、点Ｐに基づく点Ｓとを互いに加算して点Ｔ＝Ｒ＋Ｓに圧縮し、電子署名σ＝（Ｔ）を生成して送信することができる。
【００３６】
また、電子署名検証装置では、受信した電子署名σ＝（Ｔ）の射影Ψを求めることにより、点Ｒ＝Ψ（Ｔ）及び点Ｓ＝Ｔ−Ｒを取得することができる。
【００３７】
このように、点Ｒ，Ｓからなる電子署名を点Ｔからなる電子署名に圧縮して送受信可能としたので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減することができる。
【００３８】
第２の発明によれば、鍵生成センター装置において、楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]を２つの巡回群＜Ｐ＞，＜Ｑ＞の直和とし、＜Ｐ＞から選択した点Ｐと、＜Ｑ＞から選択した点Ｑと、楕円曲線上の射影Ψと、＜Ｐ＞から＜Ｑ＞への同型写像である同型写像ξとを公開した構成により、電子署名生成装置では、＜Ｐ＞に属する点Ｓと、＜Ｑ＞に属する点ξ（Ｔ）とを互いに加算して点Ｘ＝Ｓ＋ξ（Ｔ）に圧縮し、電子署名σ＝（ｃ，Ｘ）を生成して送信することができる。
【００３９】
また、電子署名検証装置では、受信した電子署名σ＝（ｃ，Ｘ）内の点Ｘの射影Ψを求めることにより、点Ｓ＝Ψ（Ｘ）及び点Ｔ＝ξ-1（Ｘ−Ｓ）を取得することができる。
【００４０】
このように、電子署名内の点Ｓ，Ｔを点Ｘに圧縮して送受信可能としたので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減することができる。
【００４１】
第３の発明によれば、鍵生成センター装置において、楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]を２つの巡回群＜Ｐ＞，＜Ｑ＞の直和とし、＜Ｐ＞から選択した点Ｐと、＜Ｑ＞から選択した点Ｑと、楕円曲線上の射影Ψと、＜Ｐ＞から＜Ｑ＞への同型写像である同型写像ξとを公開した構成により、電子署名生成装置では、＜Ｐ＞に属する点Ｓと、＜Ｑ＞に属する点Ｔとを互いに加算して点Ｘ＝Ｓ＋Ｔに圧縮し、電子署名σ＝（ｃ，Ｒ，Ｘ）を生成して送信することができる。
【００４２】
また、電子署名検証装置では、受信した電子署名σ＝（ｃ，Ｒ，Ｘ）内の点Ｘの射影Ψを求めることにより、点Ｓ＝Ψ（Ｘ）及び点Ｔ＝Ｘ−Ｓを取得することができる。
【００４３】
このように、電子署名内の点Ｓ，Ｔを点Ｘに圧縮して送受信可能としたので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減することができる。
【発明の効果】
【００４４】
以上説明したように本発明によれば、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減できる。
【発明を実施するための最良の形態】
【００４５】
以下、本発明の各実施形態について図面を用いて説明するが、その前に、各実施形態の前提となる、楕円曲線から得られる射影について述べる。
【００４６】
（射影の構成法）
ある特殊な楕円曲線においては、前述したペアリングｅn及び次のような同型写像ξを持つ巡回群の組Ｇ1，Ｇ2，Ｇ3を作れることが知られている。
【００４７】
双線形写像ｅn：Ｇ1×Ｇ2→Ｇ3 
同型写像ξ：Ｇ2→Ｇ1 
ここで、Ｇ1の生成元をｇ1∈Ｇ1とし、Ｇ2の生成元をｇ2∈Ｇ2とすると、ｇ1＝ξ(ｇ2)である。
【００４８】
以下、本明細書では、この同型写像ξについて、その一形態であるディストーションマップ(distortion map)を用い、本実施形態においてはディストーションマップをξとして説明する。なお、ディストーションマップξについては、文献（I.F.Blake, G.Seroussi, N.P.Smart, "Advances in Elliptic Curve Cryptography" LMS Lecture Note Series No.317）に詳しい。  
続いて、ディストーションマップξの構成法について説明する。
【００４９】
（楕円曲線のなす群の性質）
有限体Ｆq上で定義される楕円曲線Ｅ/Ｆqの有理点のなす群Ｅ（Ｆqk）に含まれるｎねじれ群Ｅ[ｎ]は、ｎとｑが互いに素なら、２つの独立な固有空間の集合の直和で表されることが知られている（次式を参照）。
【数３】
2008178035.tif 000005
【００５０】
ペアリングに用いる楕円曲線としては、次の条件１，２を同時に満たし、ｑやｍがなるべく小さくなる楕円曲線を選択すると都合が良い。
【００５１】
条件１：＃Ｅ(Ｆq)[ｎ]＝ｎで、ｎは、＃Ｅ(Ｆq)[ｎ]上の離散対数が困難なほど大きい。  
条件２：＃Ｅ(Ｆqm)[ｎ]＝ｎ2で、ｍは、Ｆqm上の位数ｎの部分群上の離散対数が困難なほどに大きい。
【００５２】
（フロベニウス写像φとディストーションマップξ）
楕円曲線Ｅ/Ｆqのｑ乗フロベニウス写像(Frobenius map)φは次のように定義される。
【数４】
2008178035.tif 000006
【００５３】
ここで、φは楕円加算及び楕円スカラー倍と可換なＥ[ｎ]上の自己準同型写像であり、フロベニウス自己準同型写像(Frobenius endomorphism)とも呼ばれる。すなわち、フロベニウス写像φは、Ｚ/ｎＺ上線形空間Ｅ[ｎ]上の線形写像となる。楕円曲線Ｅ/Ｆqのトレースｔとフロベニウス写像φは、次の特性方程式を満たす。
【００５４】
φ2−ｔφ＋ｑ＝０（mod ｎ）
ここで、フロベニウス写像φによるＥ[ｎ]の固有空間分解を考える。暗号でペアリングを用いるとき、（楕円曲線のなす群の性質）で述べた条件１の場合には、Ｅ/Ｆq上にＥ[ｎ]の非自明な部分群が存在している。Ｅ(Ｆq)上でφが恒等写像であることから、Ｅ(Ｆq)[ｎ]がφの１つの固有空間であり、その固有値はλ1＝１である。従って、特性方程式より、もう１つの固有値はλ2＝ｑ  mod ｎである。
【００５５】
一般的に、このφによって満たされる特性方程式を用いることで、固有値λ1に対応する固有空間の点を、固有値λ2に対応する固有空間の点へ写像するディストーションマップξを定義することができる。
【００５６】
（固有空間への射影）
簡単のためｎを素数の場合を考える。このときｔ＝λ1＋λ2≠２mod ｎであり、固有値λ2に対応する固有空間が、Ｅ[ｎ]＼Ｅ(Ｆq)[ｎ]の中に存在する。その生成元をＱとし、Ｅ(Ｆq)[ｎ]の生成元をＰとする。このとき
Ｅ[ｎ]＝＜Ｐ＞（＋）＜Ｑ＞
と表すことができる。従って、Ｅ[ｎ]上の任意の点Ｒはα，β∈Ｚ/ｎＺを用いて必ず
Ｒ＝αＰ＋βＱ
と書け、図２９のように考えることができる。
【００５７】
図２９からＥ[ｎ]上の任意の点ＲはＦq有理点からなる固有空間上の点とＦqk有理点からなる固有空間上の点の和で表されることが分かる。
【００５８】
α≠０かつβ≠０の任意のＲを生成元とする巡回群＜Ｒ＞を考える。ここで、φを用いた固有空間への射影ΨやΨ’によれば、図３０に示すように、巡回群＜Ｒ＞から＜Ｐ＞や＜Ｑ＞への同型写像を構成できる。例えば射影
【数５】
2008178035.tif 000007
【００５９】
なお、ディストーションマップξは、図３１に示すように、前述した通り、固有値λ1に対応する固有空間の点Ｐを、固有値λ2に対応する固有空間の点Ｑへ写像する。ξ-1はξの逆写像である。
【００６０】
次に、以上のことを前提として各実施形態を説明する。
【００６１】
（第１の実施形態）
本発明の第１の実施形態は、非特許文献１及び特許文献１記載の署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減するものである。
【００６２】
図１は本発明の第１の実施形態に係る電子署名システムの全体構成図である。この電子署名システムは、インターネット１を介して互いに通信可能な鍵生成センター装置１０、電子署名生成装置２０及び電子署名検証装置３０を備えている。
【００６３】
なお、電子署名生成装置２０は複数存在していても良いし、同様に電子署名検証装置３０も複数存在していても良い。さらに電子署名生成装置２０と電子署名検証装置３０は同一の装置に含まれていても良い。
【００６４】
また、各装置１０，２０，３０はインターネット１を介さずに接続されていても良い。各装置１０，２０，３０は、装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。これは以下の各実施形態でも同様である。
【００６５】
次に、各装置１０，２０，３０について具体的に説明する。
【００６６】
鍵生成センター装置１０は、電子署名・検証を行うための種々のパラメータを準備するものである。具体的には、図２に示すように、通信部１１、制御部１２、鍵情報生成部１３、選択データ記憶部１４、乱数生成部１５、秘密鍵記憶部１６、公開情報記憶部１７、及びＩＤ対応秘密鍵生成部１８を備えている。
【００６７】
ここで、通信部１１は、インターネット１を介して電子署名生成装置２０と電子署名検証装置３０との間で公開情報や鍵等のデータを送受信する機能をもっている。
【００６８】
制御部１２は、公開情報や鍵等のデータを準備し、要求に応じて他の装置２０，３０に送信するように各部１１，１３〜１８を制御するものであり、具体的には図６、図７及び図９に示す処理を実行するように、各部１１，１３〜１８を制御する機能をもっている。
【００６９】
鍵情報生成部１３は、ＩＤ情報に基づく暗号方式を構成するための楕円曲線を生成するなどの処理を行い種々のパラメータを生成すると共に、パラメータに従い公開鍵などの情報を生成するものである。鍵情報生成部１３は、具体的には、選択データ記憶部１４を参照し、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞に関し、それぞれ巡回群＜Ｐ＞から点Ｐを選択し、巡回群＜Ｑ＞から点Ｑを選択する機能と、鍵生成センター用秘密鍵L及び点Ｑに基づいて、点Ｑpub＝LＱを計算する機能と、点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含む公開情報を公開情報記憶部１７に書き込む機能と、鍵生成センター用秘密鍵Lを秘密鍵記憶部１６に書き込む機能と、電子署名生成装置２０又は電子署名検証装置３０から署名者ＩＤ情報IDAを含む公開情報要求を通信部１１及び制御部１２を介して受信すると、署名者ＩＤ情報IDA、点Ｐ及び一方向性関数ｈ（ ）に基づいて、署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算する機能と、署名者公開鍵ＰA及び公開情報を制御部１２及び通信部１１を介して公開情報要求の送信元に返信する機能とを備えている。
【００７０】
選択データ記憶部１４は、鍵情報生成部１３から読出可能な記憶装置であり、予め楕円曲線Ｅ、及び楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]のデータを保持するものである。ここで、ｎねじれ群Ｅ[ｎ]のデータは、２つの巡回群＜Ｐ＞，＜Ｑ＞の元Ｐ，Ｑのデータを含んでいる。
【００７１】
乱数生成部１５は、鍵情報生成部１３に制御され、鍵生成センター用の秘密鍵Lとしての乱数Lを生成する機能をもっている。
【００７２】
秘密鍵記憶部１６は、鍵情報生成部１３から読出／書込可能でＩＤ対応秘密鍵生成部１８から読出可能な記憶装置であり、鍵生成センター用の秘密鍵Lを保存するものである。
【００７３】
公開情報記憶部１７は、鍵情報生成部１３から読出／書込可能で制御部１２から読出可能な記憶装置であり、ＩＤ情報に基づく暗号方式を構成する種々のパラメータやそれらパラメータから生成された公開情報を保存する。ここで、公開情報は、点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含んでいる。
【００７４】
ＩＤ対応秘密鍵生成部１８は、電子署名生成装置２０から秘密鍵要求を通信部１１及び制御部１２を介して受信すると、鍵情報生成部１３により生成された署名者公開鍵ＰA及び秘密鍵記憶部１６内の鍵生成センター用秘密鍵Lに基づいて、署名者秘密鍵ＫA＝LＰAを計算する機能と、署名者秘密鍵ＫAを制御部１２及び通信部１１を介して電子署名生成装置２０に返信する機能とをもっている。
【００７５】
一方、電子署名生成装置２０は、鍵生成センター装置１０から受けた鍵を用いて電子署名を生成するものである。具体的には、図３に示すように、通信部２１、制御部２２、公開情報記憶部２３、秘密鍵記憶部２４、電子署名生成部２５、乱数生成部２６及び電子署名圧縮部２７を備えている。
【００７６】
通信部２１は、インターネット１を介して鍵生成センター装置１０と電子署名検証装置３０との間で公開情報や鍵、電子署名等のデータを送受信する機能をもっている。
【００７７】
制御部２２は、鍵生成センター装置１０から受けたデータに基づき、電子署名を生成して電子署名検証装置３０に送信するように各部２１，２３〜２７を制御するものであり、具体的には図７及び図８に示す処理を実行するように、各部２１，２３〜２７を制御する機能をもっている。
【００７８】
公開情報記憶部２３は、制御部２２から書込み可能で電子署名生成部２５及び電子署名圧縮部２７から読出可能な記憶装置であり、鍵生成センター装置１０から通信部２１により受信して制御部２２により書き込まれた署名者公開鍵ＰA及び公開情報を保存する。ここで、公開情報は、点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含んでいる。
【００７９】
秘密鍵記憶部２４は、制御部２２から書込み可能で電子署名生成部２５から読出可能な記憶装置であり、鍵生成センター装置１０から通信部２１により受信して制御部２２により書き込まれた署名者秘密鍵ＫAを保存する。秘密鍵は、適宜、暗号化等により保護された状態で鍵生成センター装置１０から受信する。
【００８０】
電子署名生成部２５は、公開情報・秘密鍵・乱数を用いて電子署名を生成するものである。電子署名生成部２５は、具体的には、乱数ｋ及び公開情報内の点Ｑに基づいて、点Ｒ＝ｋＱを計算する機能と、入力された電子署名対象データｍに対し、乱数ｋ、署名者秘密鍵ＫA、署名者公開鍵ＰA、公開情報内の一方向性関数ｈ（ ）及び点Ｒのｘ座標値ｘに基づいて、点Ｓ＝［ｈ(ｍ)/ｋ］ＰA＋［ｘ/ｋ］ＫA を計算する機能をもっている。
【００８１】
乱数生成部２６は、電子署名生成部２５に制御され、電子署名生成用の乱数ｋを生成する機能をもっている。
【００８２】
電子署名圧縮部２７は、電子署名生成部２５で生成された電子署名を圧縮し、その電子署名長を削減するものである。電子署名圧縮部２７は、具体的には、電子署名生成部２５で生成された点Ｒ，Ｓを互いに加算して点Ｔ（＝Ｒ＋Ｓ）に圧縮する機能と、点Ｔからなる電子署名σ＝（Ｔ）及び電子署名対象データｍを制御部２２及び通信部２１を介して電子署名検証装置３０に送信する機能とをもっている。
【００８３】
他方、電子署名検証装置３０は、鍵生成センター装置１０から受けた公開情報及び鍵を用い、電子署名生成装置２０から受けた電子署名を検証するものである。具体的には、図４に示すように、通信部３１、制御部３２、公開情報記憶部３３、電子署名検証情報取得部３４、電子署名検証部３５及び公開鍵計算部３６を備えている。
【００８４】
通信部３１は、インターネット１を介して鍵生成センター装置１０と電子署名生成装置２０との間で公開情報や鍵、電子署名等のデータを送受信する機能をもっている。
【００８５】
制御部３２は、鍵生成センター装置１０から受けたデータに基づき、電子署名生成装置２０から受信した電子署名を検証するように各部３１，３３〜３６を制御するものであり、具体的には図９及び図１０に示す処理を実行するように、各部３１，３３〜３６を制御する機能をもっている。
【００８６】
公開情報記憶部３３は、制御部３２から書込み可能で電子署名検証部３５及び公開鍵計算部３６から読出可能な記憶装置であり、鍵生成センター装置１０から通信部２１により受信して制御部２２により書き込まれた署名者公開鍵ＰA及び公開情報を保存する。ここで、公開情報は、点Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ ）と楕円曲線上の射影Ψとを含んでいる。
【００８７】
電子署名検証情報取得部３４は、電子署名生成装置１０から通信部３１及び制御部３２を介して受信した電子署名から、検証に必要なデータを取得するものである。電子署名検証情報取得部３４は、具体的には、電子署名生成装置２０から通信部３１及び制御部３２を介して電子署名σ＝（Ｔ）及び電子署名対象データｍを受信すると、公開情報記憶部３３内の射影Ψに基づいて、点Ｒ＝Ψ（Ｔ）を計算する機能と、得られた点Ｒ及び電子署名σ＝（Ｔ）に基づいて、点Ｓ＝Ｔ−Ｒを計算する機能と、得られた点Ｓ，Ｒ及び電子署名対象データｍを電子署名検証部３５に送出する機能とをもっている。
【００８８】
電子署名検証部３５は、電子署名生成装置２０から通信部３１及び制御部３２を介して受信した電子署名が正当な署名であるか否かを検証するものである。電子署名検証部３５は、具体的には、電子署名検証情報取得部３４から点Ｓ，Ｒ及び電子署名対象データｍを受けると、点Ｓ，Ｒに関し、公開情報記憶部３３内の署名者公開鍵ＰA及び公開情報を用いて、楕円曲線上のペアリングに基づく判定式ｅn（Ｓ，Ｒ）＝ｅn（ＰA，Ｑ）h(m)ｅn（ＰA，Ｑpub）x が成立するか否かを判定する機能と、判定の結果、判定式が成立する場合には電子署名σ＝（Ｔ）を受け入れる機能と、判定の結果、判定式が成立しない場合には電子署名σ＝（Ｔ）を拒否する機能とをもっている。
【００８９】
公開鍵計算部３６は、２回目以降の検証処理にて鍵生成センター装置１０に公開情報を要求せずに、公開鍵情報記憶部３３内の公開情報に基づいて、鍵生成センター装置１０と同様の処理を行い、署名者公開鍵ＰAなどの情報を計算するものである。
【００９０】
次に、以上のように構成された電子署名システムの動作を図５乃至図１０を用いて説明する。以下の説明は、全体動作（図５）、セットアップ処理（図６）、署名処理（図７）、署名処理内の電子署名生成処理（図８）、検証処理（図９）及び検証処理内の電子署名検証処理（図１０）、の順に行う。
【００９１】
（全体動作：図５）
鍵生成センター装置１０は、ＩＤ情報に基づく暗号方式を構成するための種々のパラメータを生成するためのセットアップ処理を実行する（ＳＴ１１〜ＳＴ１５）。
【００９２】
続いて、電子署名検証装置３０は、電子署名生成装置２０に対し、電子メール等の任意の方法で電子署名対象データと電子署名を要求する（ＳＴ２０）。
【００９３】
電子署名生成装置２０は、この要求を表示した後、署名者Ａの操作に基づき、電子署名対象データに対して署名処理を実行し（ＳＴ２１〜ＳＴ３１）、電子署名対象データの電子署名を得る。
【００９４】
しかる後、電子署名生成装置２０は、電子署名対象データと電子署名を電子署名検証装置３０に送信する（ＳＴ４０）。
【００９５】
電子署名検証装置３０は、受信した電子署名対象データと電子署名を、署名者ＡのＩＤ情報を基に検証する検証処理を実行する（ＳＴ４１〜ＳＴ４９）。
【００９６】
また、この後、検証者Ｂは、電子メール等の任意の通知方法により、署名者Ａに対して署名が正当であったことを通知しても良いし、しなくてもよい。同様に、署名者Ａは、電子メール等の任意の確認方法により、署名の正当性を検証者Ｂに確認しても良い。また、検証者Ｂは存在せず、電子署名検証装置３０が受信した電子署名の正当性を検証しても良い。さらに電子署名は要求に対して必ず生成しなければならないものではなく、要求が無くても署名者Ａの意思で電子署名を生成しても良い。
【００９７】
続いて、セットアップ処理、署名処理及び検証処理について詳細に説明する。
【００９８】
（セットアップ処理：図６）
鍵生成センター装置１０においては、鍵情報生成部１３が、選択データ記憶部１４を参照しながら、ペアリングの計算が可能な安全な楕円曲線Ｅとｎねじれ群Ｅ[ｎ]を選択すると共に（ＳＴ１１）、楕円曲線上の射影Ψを準備する。また、平文などのバイナリ値で表されるデータを乗法群Ｚｎ*へ変換する一方向性関数ｈ（ｘ）を準備する。
【００９９】
乱数生成部１５は、鍵生成センター装置１０の秘密鍵Lを生成する（ＳＴ１２）。
【０１００】
鍵情報生成部１３は、楕円曲線Ｅのｎねじれ群Ｅ[ｎ]を構成する固有空間について、固有空間＜Ｐ＞から点Ｐを選択し、固有空間＜Ｑ＞から点Ｑを選択する（ＳＴ１３）
鍵情報生成部１３は、秘密鍵Lと点Ｑから点Ｑpub＝LＱを計算する（ＳＴ１４）。
【０１０１】
しかる後、鍵情報生成部１３は、Ｐ，Ｑ，Ｑpub及び一方向性関数ｈ（ｘ），楕円曲線上の射影Ψを公開情報記憶部１７に保存し、秘密鍵Lを秘密鍵記憶部１６に保存する（ＳＴ１５）。
【０１０２】
以上により、鍵生成センター装置１０は、セットアップ処理を終了する。なお、セットアップ処理はＩＤ情報に基づく暗号方式によるシステムを構築する際に最初に行われるものであり、システムにおける基盤となる情報を生成する。
【０１０３】
（署名処理：図７）
電子署名生成装置２０では、署名者Ａの操作により、電子署名生成要求が入力されると（ＳＴ２１）、公開情報を取得するため、公開情報要求を鍵生成センター装置１０に送信する（ＳＴ２２）。
【０１０４】
鍵生成センター装置１０は、公開情報要求を受けると、一方向性関数ｈ（ｘ）を用い、署名者ＡのＩＤ情報IDAに対応する署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算し、この署名者公開鍵ＰAと共に公開情報を電子署名生成装置２０に送信する（ＳＴ２３）。
【０１０５】
また、電子署名生成装置２０は、秘密鍵を取得するため、秘密鍵要求を鍵生成センター装置１０に送信する（ＳＴ２４）。
【０１０６】
鍵生成センター装置１０は、秘密鍵要求を受けると、署名者ＡのＩＤ情報IDAに対応する署名者秘密鍵ＫA＝LＰAを計算し、この署名者秘密鍵ＫAを電子署名生成装置２０に送信する（ＳＴ２５）。
【０１０７】
電子署名生成装置２０は、署名者秘密鍵ＫAを受けると、以下のように、電子署名対象データから電子署名を生成する電子署名生成処理を実行する（ＳＴ２６〜ＳＴ３１）。
【０１０８】
［電子署名生成処理：図８］
電子署名生成装置２０においては、署名者Ａの操作により、電子署名対象データｍが入力されたとする（ＳＴ２６）。
【０１０９】
続いて、電子署名生成装置２０においては、電子署名生成部２５が乱数生成部２６を用いて乱数ｋ∈Ｚｎ*を生成する（ＳＴ２７）。
【０１１０】
また、電子署名生成部２５は、点Ｒ＝ｋＱを計算する（ＳＴ２７）。
【０１１１】
さらに、電子署名生成部２５は、点Ｒのｘ座標をｘとし、次式に示すように、点Ｓを計算する（ＳＴ２９）。
【数６】
2008178035.tif 000008
【０１１２】
これにより、電子署名生成部２５は、２つの点データＲ，Ｓからなる電子署名σ’＝（Ｒ，Ｓ）を取得し、この電子署名σ’を電子署名圧縮部２７に送出する。
【０１１３】
電子署名圧縮部２７は、この電子署名σ’に含まれる２つの点データＲ，Ｓを互いに加算して圧縮した点Ｔ＝Ｒ＋Ｓを求め（ＳＴ３０）、この点Ｔのデータを電子署名σ＝（Ｔ）として制御部２２に出力する（ＳＴ３１）。
【０１１４】
以上の署名処理においては、ステップＳＴ２３及びＳＴ２５で受けた公開鍵、公開情報及び秘密鍵は、公開情報記憶部２３及び秘密鍵記憶部２４に格納される。また秘密鍵記憶部は、秘密鍵を何らかの方式で保護することが望ましいが、具体的な保護方法（例、暗号化して保存する方法、耐タンパーデバイスを用いる方法など）については特に限定しない。
【０１１５】
さらにステップＳＴ２５で送信される署名者秘密鍵ＫAも何らかの方式で保護されていることが望まれるが、具体的な保護方法（例、暗号化通信など）については限定しない。
【０１１６】
ＩＤは署名者に関するユニークなＩＤ情報であり、ユニークなＩＤ情報から一方向性関数を用いて署名者ＩＤに対応する公開鍵を生成している。
【０１１７】
また、署名処理においては、公開情報要求及び秘密鍵要求の処理（ＳＴ２２，ＳＴ２４）を同時に実行しても良く、これに伴い、公開情報送信及び秘密鍵送信の処理（ＳＴ２３，ＳＴ２５）を同時に実行しても良い。
【０１１８】
また、ステップＳＴ２２〜ＳＴ２５は毎回行う処理ではなく、初回の署名生成時にのみ行えば良い。従って２回目以降に署名生成を行う場合は、ステップＳＴ２１（電子署名生成要求）とＳＴ２６〜３１（電子署名生成処理）とを実行すれば、電子署名を生成することができる。
【０１１９】
（検証処理：図９）
電子署名検証装置３０では、検証者Ｂの操作により、電子署名σ＝（Ｔ）を含む電子署名検証要求が入力されると（ＳＴ４１）、署名者Ａの公開鍵及び公開情報を取得するため、公開情報要求を鍵生成センター装置１０に送信する（ＳＴ４２）。
【０１２０】
鍵生成センター装置１０は、公開情報要求を受けると、一方向性関数ｈ（ｘ）を用い、署名者ＡのＩＤ情報IDAに対応する署名者公開鍵ＰA＝ｈ（IDA）Ｐを計算し、この署名者公開鍵ＰAと共に公開情報を電子署名検証装置３０に送信する（ＳＴ４３）。
【０１２１】
電子署名検証装置３０は、署名者公開鍵ＰA及び公開情報を受けると、以下のように、電子署名対象データ及び電子署名を用いて電子署名を検証する電子署名検証処理を実行する（ＳＴ４４〜ＳＴ４９）。
【０１２２】
［電子署名検証処理：図１０］
電子署名検証装置３０においては、受信した電子署名対象データｍ及び電子署名σ＝（Ｔ）が電子署名検証情報取得部３４に入力されたとする（ＳＴ４４）。
【０１２３】
電子署名検証情報取得部３４は、電子署名σ＝（Ｔ）から楕円曲線上の射影Ψを用いて点Ｒ＝Ψ（Ｔ）を取得する（ＳＴ４５）。
【０１２４】
また、電子署名検証情報取得部３４は、電子署名σ＝（Ｔ）及び点Ｒから点Ｓ＝Ｔ−Ｒを取得し（ＳＴ４６）、これら２つの点データＳ，Ｒを電子署名検証部３５に送出する。
【０１２５】
電子署名検証部３５は、２つの点データＳ，Ｒ及び公開情報に基づいて、次の判定式の両辺を計算し、判定式が成立するか否かを判定する（ＳＴ４７）
【数７】
2008178035.tif 000009
【０１２６】
ステップＳＴ４７の結果、判定式が成立する場合に電子署名σを正当であるとして、受け入れを示す検証結果を制御部３２に出力する（ＳＴ４８）また、判定式が成立しない場合には電子署名σを不正であるとして、拒否を示す検証結果を制御部３２に出力する（ＳＴ４９）。
【０１２７】
以上の検証処理においては、公開情報要求及び公開情報送信の処理（ＳＴ４２〜４３）は、毎回鍵生成センター装置１０に問い合わせても良いが、公開情報である一方向性関数ｈ（ｘ）及び図４の公開鍵計算部３６を用いて署名者Ａの公開鍵ＰAを計算してもよく、この場合、ネットワークに接続することなく、電子署名を検証することができる。従って初回の検証時には公開情報を取得しなければならないが、２回目以降の検証時には、ネットワークに接続することなく電子署名を検証することができる。また、鍵生成センター装置１０は予め生成した鍵を保存しておき、検証者からの要求に対して鍵を生成せずに保存している鍵を配布しても良い。
【０１２８】
上述したように本実施形態によれば、楕円曲線上のペアリングに基づく署名方式において、楕円曲線Ｅのｎねじれ群Ｅ[ｎ]を構成する固有空間＜Ｐ＞，＜Ｑ＞からそれぞれ点Ｐ，Ｑを選択するステップＳＴ１３を含むセットアップ処理と、電子署名σ’＝（Ｒ，Ｓ）を圧縮して電子署名σ＝（Ｔ）を得るステップＳＴ３０を含む署名処理と、電子署名σ＝（Ｔ）から点データＲ，Ｓを取得するステップＳＴ４５，４６を含む検証処理とを実行する構成により、電子署名のデータ長を削減することができる。
【０１２９】
詳しくは、鍵生成センター装置１０において、楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]を２つの巡回群＜Ｐ＞，＜Ｑ＞の直和とし、＜Ｐ＞から選択した点Ｐと、＜Ｑ＞から選択した点Ｑと、楕円曲線上の射影Ψとを公開した構成により、電子署名生成装置２０では、点Ｑに基づく点Ｒと、点Ｐに基づく点Ｓとを互いに加算して点Ｔ＝Ｒ＋Ｓに圧縮し、電子署名σ＝（Ｔ）を生成して送信することができる。
【０１３０】
また、電子署名検証装置３０では、受信した電子署名σ＝（Ｔ）の射影Ψを求めることにより、点Ｒ＝Ψ（Ｔ）及び点Ｓ＝Ｔ−Ｒを取得することができる。
【０１３１】
このように、点Ｒ，Ｓからなる電子署名を点Ｔからなる電子署名に圧縮して送受信可能としたので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名のデータ長を削減することができる。
【０１３２】
（第２の実施形態）
本発明の第２の実施形態は、非特許文献２記載のサインクリプション(Signcryption)方式において、署名者と検証者との間で送受信する電子署名としてのサインクリプションデータのデータ長を削減するものである。なお、サインクリプション方式は、暗号化と署名を同時に行う方式である。
【０１３３】
図１１は本発明の第２の実施形態に係る電子署名システムとして機能するサインクリプションシステムの全体構成図である。サインクリプションシステムは、互いにインターネット１を介して通信可能な鍵生成センター装置４０、電子署名生成装置としてのサインクリプション生成装置５０、及び電子署名検証装置としてのサインクリプション検証装置６０を備えている。
【０１３４】
なお、サインクリプション生成装置５０は複数存在していても良いし、同様にサインクリプション検証装置６０も複数存在していても良い。さらにサインクリプション生成装置５０とサインクリプション検証装置６０は同一の装置に含まれていても良い。これらの変形例は以下の各実施形態でも同様である。
【０１３５】
次に、各装置４０，５０，６０について具体的に説明する。
【０１３６】
鍵生成センター装置４０は、図１２に示すように、通信部４１、制御部４２、鍵情報生成部４３、選択データ記憶部４４、乱数生成部４５、秘密鍵記憶部４６、公開情報記憶部４７、及びＩＤ対応秘密鍵生成部４８を備えている。
【０１３７】
ここで、通信部４１は、インターネット１を介してサインクリプション生成装置５０とサインクリプション検証装置６０との間で公開情報や鍵等のデータを送受信する機能をもっている。
【０１３８】
制御部４２は、公開情報や鍵等のデータを準備し、要求に応じて他の装置５０，６０に送信するように各部４１，４３〜４８を制御するものであり、具体的には図１６、図１７及び図１９に示す処理を実行するように、各部４１，４３〜４８を制御する機能をもっている。
【０１３９】
鍵情報生成部４３は、ＩＤ情報に基づく暗号方式を構成するための楕円曲線を生成するなどの処理を行い種々のパラメータを生成すると共に、パラメータに従い公開鍵などの情報を生成するものである。鍵情報生成部４３は、具体的には、選択データ記憶部４４を参照し、楕円曲線Ｅ上でなすｎねじれ群Ｅ[ｎ]を構成する２つの巡回群＜Ｐ＞，＜Ｑ＞に関し、それぞれ巡回群＜Ｐ＞から点Ｐを選択し、巡回群＜Ｑ＞から点Ｑを選択する機能と、点Ｐ及び点Ｑに基づいてペアリングｅn（Ｐ，Ｑ）＝ｇを計算する機能と、公開情報ＰID＝s(ID)Ｐ，ＱID＝s(ID)Ｑを計算する機能と、点Ｐ，ＰID，Ｑ，ＱID，ｇ及び関数ＨP，ＨQ，Ｈ0，Ｈ1，Ｈ2，Ｈ2’，Ｈ3，Ｈ3’と、楕円曲線上の射影Ψ，ディストーションマップξを含む公開情報を公開情報記憶部４７に書き込む機能と、鍵生成センター用秘密鍵生成関数s(ID)を秘密鍵記憶部４６に書き込む機能と、サインクリプション生成装置５０から検証者ＩＤ情報IDBを含む公開情報要求を通信部４１及び制御部４２を介して受信すると、検証者ＩＤ情報IDB、点Ｐ及び秘密鍵生成関数s(ID)に基づいて、検証者公開鍵ＰID_B＝s(IDB)Ｐを計算する機能と、検証者公開鍵ＰID_B及び公開情報を制御部４２及び通信部４１を介してサインクリプション生成装置５０に返信する機能と、サインクリプション検証装置６０から署名者ＩＤ情報IDAを含む公開情報要求を通信部４１及び制御部４２を介して受信すると、署名者ＩＤ情報IDA、点Ｑ及び秘密鍵生成関数s(ID)に基づいて、署名者公開鍵ＰID_A＝s(IDA)Ｑを計算する機能と、署名者公開鍵ＰID_A及び公開情報を制御部４２及び通信部４１を介してサインクリプション検証装置６０に返信する機能とを備えている。
【０１４０】
なお、「ID_B」は「IDB」を表す。すなわち「_B」は下付添字の下付添字Bを表す。この表記法は、後述する「ID_A」でも同様である。また、この表記法は本明細書中で同様に用いられる。
【０１４１】
選択データ記憶部４４は、鍵情報生成部４３から読出可能な記憶装置であり、予め楕円曲線Ｅ、及び楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]のデータを保持するものである。ここで、ｎねじれ群Ｅ[ｎ]のデータは、２つの巡回群＜Ｐ＞，＜Ｑ＞の元Ｐ，Ｑのデータを含んでいる。
【０１４２】
乱数生成部４５は、鍵情報生成部４３に制御され、秘密鍵生成関数S(ID)の係数に用いられる乱数を生成する機能をもっている。ここで、秘密鍵生成関数s(ID)は、係数を乱数とし、変数をIDとするＩＤの多項式表現によって表される。また、s(ID)とs(ID)-1とは、逆元の関係にあり、互いに掛け合わせると単位元（ここでは１）になって打ち消される関係がある。このことに関連して、後述する検証処理の判定式（Ｖ＝Ｒｇh）が得られている。このs(ID)とs(ID)-1との関係は、以下の各実施形態でも同様である。
【０１４３】
秘密鍵記憶部４６は、鍵情報生成部４３から読出／書込可能でＩＤ対応秘密鍵生成部４８から読出可能な記憶装置であり、鍵生成センター用の秘密鍵生成関数s(ID)を保存するものである。
【０１４４】
公開情報記憶部４７は、鍵情報生成部４３から読出／書込可能で制御部４２から読出可能な記憶装置であり、ＩＤ情報に基づく暗号方式を構成する種々のパラメータやそれらパラメータから生成された公開情報を保存する。ここで、公開情報は、Ｐ，ＰID，Ｑ，ＱID，ｇ及び関数ＨP，ＨQ，Ｈ0，Ｈ1，Ｈ2，Ｈ2’，Ｈ3，Ｈ3’と、楕円曲線上の射影Ψ，ディストーションマップξを含んでいる。但し、公開情報としては、必ずしもここで述べた全ての情報を含む必要は無い。例えば、本実施形態の動作で用いない関数ＨP，ＨQ，Ｈ0，Ｈ2’，Ｈ3，Ｈ3’については、省略してもよい。但し、後述する第３の実施形態においては、関数Ｈ3’を省略しない。
【０１４５】
関数ＨPは、バイナリ値を、＜Ｐ＞からなるｎねじれ群Ｅ[ｎ]の点に変換するものである。関数ＨQは、バイナリ値を、＜Ｑ＞からなるｎねじれ群Ｅ[ｎ]の点に変換するものである。
【０１４６】
関数Ｈ0は、バイナリ値を乗法群Ｚｎ*に変換するものである。関数Ｈ1は、＜Ｐ＞と＜Ｑ＞からなるｎねじれ群Ｅ[ｎ]の点からバイナリ値に変換するものである。
【０１４７】
関数Ｈ2は、＜Ｐ＞と＜Ｑ＞からなるｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚｎ*に変換するものである。関数Ｈ2’は、＜Ｐ＞からなるｎねじれ群Ｅ[ｎ]の点とバイナリ値とを連結したデータを乗法群Ｚｎ*に変換するものである。
【０１４８】
関数Ｈ3は、＜Ｐ＞からなるｎねじれ群Ｅ[ｎ]の点と、＜Ｐ＞と＜Ｑ＞からなるｎねじれ群Ｅ[ｎ]の点と、バイナリ値とを連結したデータを乗法群Ｚｎ*に変換するものである。関数Ｈ3’は、＜Ｐ＞からなるｎねじれ群Ｅ[ｎ]の点と、＜Ｐ＞からなるｎねじれ群Ｅ[ｎ]の点と、バイナリ値とを連結したデータを乗法群Ｚｎ*に変換するものである。
【０１４９】
ＩＤ対応秘密鍵生成部４８は、サインクリプション生成装置５０から署名者ＩＤ情報IDAを含む秘密鍵要求を通信部４１及び制御部４２を介して受信すると、公開鍵情報記憶部４７内の点Ｐ及び秘密鍵記憶部４６内の秘密鍵生成関数s(ID)に基づいて、署名者秘密鍵ＰsID_A＝S(IDA)-1Ｐを計算する機能と、署名者秘密鍵ＰsID_Aを制御部４２及び通信部４１を介してサインクリプション生成装置５０に返信する機能と、サインクリプション検証装置６０から検証者ＩＤ情報IDBを含む秘密鍵要求を通信部４１及び制御部４２を介して受信すると、公開鍵情報記憶部４７内の点Ｑ及び秘密鍵記憶部４６内の秘密鍵生成関数s(ID)に基づいて、検証者秘密鍵ＱsID_B＝S(IDB)-1Ｑを計算する機能と、検証者秘密鍵ＱsID_Bを制御部４２及び通信部４１を介してサインクリプション検証装置６０に返信する機能と、をもっている。
【０１５０】
一方、サインクリプション生成装置５０は、図１３に示すように、通信部５１、制御部５２、公開情報記憶部５３、秘密鍵記憶部５４、サインクリプション生成部５５、乱数生成部５６及びサインクリプション圧縮部５７を備えている。
【０１５１】
通信部５１は、インターネット１を介して鍵生成センター装置４０とサインクリプション検証装置６０との間で公開情報や鍵、サインクリプション（電子署名）等のデータを送受信する機能をもっている。
【０１５２】
制御部５２は、鍵生成センター装置４０から受けたデータに基づき、サインクリプションを生成してサインクリプション検証装置６０に送信するように各部５１，５３〜５７を制御するものであり、具体的には図１７及び図１８に示す処理を実行するように、各部５１，５３〜５７を制御する機能をもっている。また、制御部５２は、署名者Ａの操作により、サインクリプション検証装置６０の検証者ＩＤ情報IDBを含む公開情報要求を通信部５１を介して鍵生成センター装置４０に送信する手段と、鍵生成センター装置４０から受信した検証者公開鍵ＰID_B及び公開情報を公開情報記憶部５３に書き込む機能と、署名者ＩＤ情報IDAを含む秘密鍵要求を鍵生成センター装置４０に送信した後、鍵生成センター装置４０から受信した署名者秘密鍵ＰsID_Aを秘密鍵記憶部５４に書き込む機能とをもっている。
【０１５３】
公開情報記憶部５３は、制御部５２から書込み可能でサインクリプション生成部５５及びサインクリプション圧縮部５７から読出可能な記憶装置であり、鍵生成センター装置４０から通信部５１により受信して制御部５２により書き込まれた検証者公開鍵ＰID_B及び公開情報を保存する。ここで、公開情報は、Ｐ，ＰID，Ｑ，ＱID，ｇ及び関数ＨP，ＨQ，Ｈ0，Ｈ1，Ｈ2，Ｈ2’，Ｈ3，Ｈ3’と、楕円曲線上の射影Ψ，ディストーションマップξを含んでいる。
【０１５４】
秘密鍵記憶部５４は、制御部４２から書込み可能でサインクリプション生成部４５から読出可能な記憶装置であり、鍵生成センター装置４０から通信部５１により受信して制御部５２により書き込まれた署名者秘密鍵ＰsID_Aを保存する。秘密鍵は、適宜、暗号化等により保護された状態で鍵生成センター装置４０から受信する。
【０１５５】
サインクリプション生成部５５は、公開情報・秘密鍵・乱数を用いてサインクリプションデータを生成するものである。サインクリプション生成部５５は、具体的には、乱数ｘ及び点ｇに基づいて、点Ｒ＝ｇｘを計算する機能と、電子署名対象データｍに対し、点Ｒ、関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｒ）（＋）ｍを計算する機能（但し、（＋）は排他的論理和）と、値ｃ、点Ｒ及び関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する機能と、値ｈ、乱数ｘ及び署名者秘密鍵ＰsID_Aに基づいて、点Ｓ＝（ｘ＋ｈ）ＰsID_Aを計算する機能と、乱数ｘ及び検証者公開鍵ＰID_Bに基づいて、点Ｔ＝ｘＰID_Bを計算する機能と、得られた値ｃ，点Ｓ，Ｔをサインクリプション圧縮部５７に送出する機能とをもっている。
【０１５６】
乱数生成部５６は、サインクリプション生成部５５に制御され、サインクリプション生成用の乱数ｘを生成する機能をもっている。
【０１５７】
サインクリプション圧縮部５７は、サインクリプション生成部５５で生成されたサインクリプションの署名に関するデータを圧縮し、そのデータ長を削減するものである。サインクリプション圧縮部５７は、具体的には、点Ｔ及びディストーションマップξに基づいて、点ξ（Ｔ）を計算する機能と、点Ｓ，ξ（Ｔ）を互いに加算して点Ｘ（＝Ｓ＋ξ（Ｔ））に圧縮する機能と、点Ｘ及び値ｃからなる電子署名σ＝（ｃ，Ｘ）を制御部５２及び通信部５１を介してサインクリプション検証装置６０に送信する機能とをもっている。
【０１５８】
他方、サインクリプション検証装置６０は、図１４に示すように、通信部６１、制御部６２、公開情報記憶部６３、秘密鍵記憶部６４、サインクリプション検証情報取得部６５、サインクリプション検証部６６及び公開鍵計算部６７を備えている。
【０１５９】
通信部６１は、インターネット１を介して鍵生成センター装置４０とサインクリプション生成装置５０との間で公開情報や鍵、サインクリプション等のデータを送受信する機能をもっている。
【０１６０】
制御部６２は、鍵生成センター装置４０から受けたデータに基づき、サインクリプション生成装置５０から受信したサインクリプションを検証するように各部６１，６３〜６７を制御するものであり、具体的には図１９及び図２０に示す処理を実行するように、各部６１，６３〜６７を制御する機能をもっている。また、制御部６２は、検証者Ｂの操作により、サインクリプション生成装置５０の署名者ＩＤ情報IDAを含む公開情報要求を通信部６１を介して鍵生成センター装置４０に送信する機能と、鍵生成センター装置４０から受信した署名者公開鍵ＱsID_A及び公開情報を公開情報記憶部６３に書き込む機能と、検証者ＩＤ情報IDBを含む秘密鍵要求を通信部６１を介して鍵生成センター装置４０に送信する機能と、鍵生成センター装置４０から通信部６１を介して受信した検証者秘密鍵ＱsID_Bを秘密鍵記憶部６４に書き込む機能とをもっている。
【０１６１】
公開情報記憶部６３は、制御部６２から書込み可能で各部６５〜６７から読出可能な記憶装置であり、鍵生成センター装置４０から通信部６１により受信して制御部６２により書き込まれた署名者公開鍵ＱID_A及び公開情報を保存する。ここで、公開情報は、Ｐ，ＰID，Ｑ，ＱID，ｇ及び関数ＨP，ＨQ，Ｈ0，Ｈ1，Ｈ2，Ｈ2’，Ｈ3，Ｈ3’と、楕円曲線上の射影Ψ，ディストーションマップξを含んでいる。
【０１６２】
秘密鍵記憶部６４は、制御部６２から書込み可能で各部６６，６７から読出可能な記憶装置であり、鍵生成センター装置４０から通信部６１により受信して制御部６２により書き込まれた検証者秘密鍵ＱsID_Bを保存する。
【０１６３】
サインクリプション検証情報取得部６５は、サインクリプション生成装置５０から通信部６１及び制御部６２を介して受信したサインクリプションから、検証に必要なデータを取得するものである。サインクリプション検証情報取得部６５は、具体的には、サインクリプション生成装置５０から通信部６１及び制御部６２を介してサインクリプションσ＝（ｃ，Ｘ）を受信すると、このサインクリプションσ＝（ｃ，Ｘ）及び公開情報内の射影Ψに基づいて、点Ｓ＝Ψ（Ｘ）を計算する機能と、得られた点Ｓ及びサインクリプションσ＝（ｃ，Ｘ）内の点Ｘに基づいて、点Ｔ＝ξ-1（Ｘ−Ｓ）を計算する機能と、得られた点Ｔ，Ｓ及び値ｃをサインクリプション検証部６６に送出する機能とをもっている。
【０１６４】
サインクリプション検証部６６は、サインクリプション生成装置５０から通信部６１及び制御部６２を介して受信したサインクリプションが正当であるか否かを検証するものである。サインクリプション検証部６６は、具体的には、サインクリプション検証情報取得部６５から点Ｔ，Ｓ及び値ｃを受けると、得られた点Ｔ及び検証者秘密鍵ＱsID_Bに関し、楕円曲線上のペアリングに基づく点Ｒ＝ｅn（Ｔ，ＱsID_B）を計算する機能と、得られた点Ｒ、値ｃ及び関数Ｈ2に基づいて、値ｈ＝Ｈ2（Ｒ，ｃ）を計算する機能と、点Ｒ、値ｃ及び関数Ｈ2に基づいて、電子署名対象データｍ＝Ｈ1（Ｒ）（＋）ｃを計算する機能と、点Ｓ及び署名者公開鍵ＱID_Aに関し、楕円曲線上のペアリングに基づく点Ｖ＝ｅn（Ｓ，ＱID_A）を計算する機能と、得られた点Ｖ、点Ｒ、点ｇ及び値ｈに関する判定式Ｖ＝Ｒｇｈ が成立するか否かを判定する機能と、判定の結果、判定式が成立する場合にはサインクリプションσ＝（ｃ，Ｘ）を受け入れる機能と、判定の結果、判定式が成立しない場合にはサインクリプションσ＝（ｃ，Ｘ）を拒否する機能とをもっている。
【０１６５】
公開鍵計算部６７は、２回目以降の検証処理にて鍵生成センター装置４０に公開情報を要求せずに、公開鍵情報記憶部６３内の公開情報に基づいて、鍵生成センター装置４０と同様の処理を行い、署名者公開鍵ＱID_Aなどの情報を計算するものである。
【０１６６】
次に、以上のように構成されたサインクリプションシステムの動作を図１５乃至図２０を用いて説明する。以下の説明は、全体動作（図１５）、セットアップ処理（図１６）、サインクリプション(Signcryption)処理（図１７）、サインクリプション処理内のサインクリプション生成処理（図１８）、アンサインクリプション(Unsigncryption)処理（図１９）及びアンサインクリプション処理内のサインクリプション検証処理（図２０）、の順に行う。なお、サインクリプション処理は、前述した署名処理に対応し、アンサインクリプション処理は、前述した検証処理に対応する。
【０１６７】
（全体動作：図１５）
鍵生成センター装置４０は、ＩＤ情報に基づく暗号方式を構成するための種々のパラメータを生成するためのセットアップ処理を実行する（ＳＴ５１〜ＳＴ５５）。
【０１６８】
続いて、サインクリプション検証装置６０は、サインクリプション生成装置５０に対し、電子メール等の任意の方法でサインクリプションデータを要求する（ＳＴ６０）。
【０１６９】
サインクリプション生成装置５０は、この要求を表示した後、署名者の操作に基づき、電子署名対象データに対してサインクリプション処理を実行し（ＳＴ６１〜ＳＴ７４）、電子署名対象データのサインクリプションデータを得る。
【０１７０】
しかる後、サインクリプション生成装置５０は、サインクリプションデータをサインクリプション検証装置６０に送信する（ＳＴ８０）。
【０１７１】
サインクリプション検証装置６０は、受信したサインクリプションデータを、署名者のＩＤ情報を基に検証するアンサインクリプション処理を実行する（ＳＴ８１〜ＳＴ９５）。
【０１７２】
また、この後、検証者Ｂは、電子メール等の任意の通知方式により、署名者Ａに対して、サインクリプションの署名が正当であったことを通知しても良いし、しなくてもよい。同様に、署名者Ａは、電子メール等の任意の確認方法により、サインクリプションの署名の正当性を検証者Ｂに確認しても良い。また、検証者Ｂは存在せず、サインクリプション検証装置６０が受信したサインクリプションデータの正当性を検証しても良い。さらにサインクリプションデータは要求に対して必ず生成しなければならないものではなく、要求が無くても署名者Ａの意思でサインクリプションデータを生成しても良い。
【０１７３】
続いて、セットアップ処理、サインクリプション処理及びアンサインクリプション処理について詳細に説明する。
【０１７４】
（セットアップ処理：図１６）
鍵生成センター装置４０においては、鍵情報生成部４３が、選択データ記憶部４４を参照しながら、ペアリングの計算が可能な安全な楕円曲線Ｅとｎねじれ群Ｅ[ｎ]を選択すると共に、楕円曲線上の射影Ψ及びディストーションマップξを準備する（ＳＴ５１）。
【０１７５】
乱数生成部４５は、署名者のＩＤに対応する秘密鍵を生成する秘密鍵生成関数s(ID)を乱数を生成して作成する。ここでs(ID)は、乱数を係数とするＩＤの多項式表現によって表される。
【０１７６】
鍵情報生成部４３は、選択データ記憶部４４を参照し、楕円曲線Ｅのｎねじれ群Ｅ[ｎ]を構成する固有空間について、固有空間＜Ｐ＞から点Ｐを選択し、固有空間＜Ｑ＞から点Ｑを選択する。そしてペアリングｅn（Ｐ，Ｑ）＝ｇを計算する（ＳＴ５３）。
【０１７７】
また、鍵情報生成部４３は、公開情報ＰID＝s(ID)Ｐ，ＱID＝s(ID)Ｑを計算する（ＳＴ５４）。このＰID＝s(ID)Ｐ，ＱID＝s(ID)Ｑは、ＩＤ情報IDを鍵情報ＰID，ＱIDに変換する関数であり、サインクリプション検証装置６０が次回からの検証時に公開鍵計算部６７を使用しない場合があるので、必ずしも公開する必要はない。これは以下の各実施形態でも同様である。
【０１７８】
さらに、鍵情報生成部４３は、Ｐ，ＰID，Ｑ，ＱID及び関数Ｈ1，Ｈ2，楕円曲線上の射影Ψと、ディストーションマップξを公開情報記憶部４７に保存し、秘密鍵生成関数s(ID)を秘密鍵記憶部４６に保存する（ＳＴ５５）。
【０１７９】
以上により、鍵生成センター装置４０はセットアップ処理を終了する。なお、セットアップ処理は、ＩＤ情報に基づく暗号方式によるシステムを構築する際に最初に行われるものであり、システムにおける基盤となる情報を生成する。
【０１８０】
（サインクリプション処理：図１７）
サインクリプション生成装置５０では、署名者Ａの操作により、サインクリプション生成要求が入力されると（ＳＴ６１）、公開情報を取得するため、公開情報要求を鍵生成センター装置４０に送信する（ＳＴ６２）。
【０１８１】
鍵生成センター装置４０は、公開情報要求を受けると、検証者ＢのＩＤ情報IDBに対応する検証者公開鍵ＰID_B＝s(IDB)Ｐを計算し、この検証者公開鍵ＰID_Bと共に公開情報をサインクリプション生成装置５０に送信する（ＳＴ６３）。
【０１８２】
また、サインクリプション生成装置５０は、秘密鍵を取得するため、秘密鍵要求を鍵生成センター装置４０に送信する（ＳＴ６４）。
【０１８３】
鍵生成センター装置４０は、秘密鍵要求を受けると、署名者ＡのＩＤ情報IDAに対応する署名者秘密鍵ＰsID_A＝s(IDA)-1Ｐを計算し、この署名者秘密鍵ＰsID_Aをサインクリプション生成装置５０に送信する（ＳＴ６５）。
【０１８４】
サインクリプション生成装置５０は、署名者秘密鍵ＰsID_Aを受けると、以下のように、サインクリプションデータを生成するサインクリプション生成処理を実行する（ＳＴ６６〜ＳＴ７４）。
【０１８５】
［サインクリプション生成処理：図１８］
サインクリプション生成装置５０においては、署名者Ａの操作により、サインクリプション対象データｍが入力されたとする（ＳＴ６６）。
【０１８６】
続いて、サインクリプション生成装置５０においては、サインクリプション生成部５５が乱数生成部５６を用いて乱数ｘ∈Ｚｎ*を生成する（ＳＴ６７）。
【０１８７】
また、サインクリプション生成部５５は、点Ｒ＝ｇｘを計算し（ＳＴ６８）、さらに、値ｃ＝Ｈ1（Ｒ）（＋）ｍを計算する（ＳＴ６９）。
【０１８８】
また、サインクリプション生成部５５は、値ｈ＝Ｈ2（Ｒ，ｃ）を計算し（ＳＴ７０）、さらに、値Ｓ＝（ｘ＋ｈ）ＰsID_A を計算する（ＳＴ７１）。
【０１８９】
しかる後、サインクリプション生成部５５は、点Ｔ＝ｘＰID_B を計算し（ＳＴ７２）、１つのバイナリ値ｃと、２つの点データＳ，Ｔとからなるサインクリプションデータσ’＝（ｃ，Ｓ，Ｔ）を取得し、このサインクリプションデータσ’をサインクリプション圧縮部５７に送出する。
【０１９０】
サインクリプション圧縮部５７は、このサインクリプションデータσ’を受けると、サインクリプションデータσ’に含まれる点データＴのディストーションマップξ（Ｔ）を求める。次に、サインクリプション圧縮部５７は、このディストーションマップξ（Ｔ）と、サインクリプションデータσ’内の別の点データＳとを加算して圧縮した点Ｘ＝Ｓ＋ξ（Ｔ）を求める（ＳＴ７３）。
【０１９１】
これにより、サインクリプション圧縮部５７は、この点Ｘのデータと、サインクリプションデータσ’内のバイナリ値ｃとからなるサインクリプションデータσ＝（ｃ，Ｘ）を取得し、このサインクリプションデータσ＝（ｃ，Ｘ）を制御部５２に出力する（ＳＴ７４）。
【０１９２】
以上のサインクリプション処理においては、公開情報要求及び秘密鍵要求の処理（ＳＴ６２，ＳＴ６４）を同時に実行しても良く、これに伴い、公開情報送信及び秘密鍵送信の処理（ＳＴ６３，ＳＴ６５）を同時に実行しても良い。
【０１９３】
（アンサインクリプション処理：図１９）
アンサインクリプション検証装置６０では、検証者Ｂの操作により、サインクリプションデータσ＝（ｃ，Ｘ）を含むサインクリプション検証要求が入力されると（ＳＴ８１）、署名者Ａの公開鍵及び公開情報を取得するため、公開情報要求を鍵生成センター装置４０に送信する（ＳＴ８２）。
【０１９４】
鍵生成センター装置４０は、公開情報要求を受けると、署名者ＡのＩＤ情報IDAに対応する署名者公開鍵ＱID_A＝s(IDA)Ｑを計算し、この署名者公開鍵ＱID_Aと共に公開情報をサインクリプション検証装置６０に送信する（ＳＴ８３）。
【０１９５】
また、サインクリプション検証装置６０は、検証者ＩＤの秘密鍵を取得するため、秘密鍵要求を鍵生成センター装置４０に送信する（ＳＴ８４）。
【０１９６】
鍵生成センター装置４０は、秘密鍵要求を受けると、検証者ＢのＩＤ情報IDBに対応する検証者秘密鍵ＱsID_B＝s(IDB)-1Ｑを計算し、この検証者秘密鍵ＱsID_Bをサインクリプション検証装置６０に送信する（ＳＴ８５）。
【０１９７】
サインクリプション検証装置６０は、署名者公開鍵ＱsID_A、公開情報及び検証者秘密鍵ＱsID_Bを受けると、以下のように、サインクリプションデータを検証するサインクリプション検証処理を実行する（ＳＴ８６〜ＳＴ９５）。
【０１９８】
［電子署名検証処理フロー：図２０］
サインクリプション検証装置６０においては、受信したサインクリプションデータσ＝（ｃ，Ｘ）がサインクリプション検証情報取得部６５に入力されたとする（ＳＴ８６）。
【０１９９】
サインクリプション検証情報取得部６５は、サインクリプションデータσ＝（ｃ，Ｘ）の電子署名Ｘから楕円曲線上の射影Ψを用いて点Ｓ＝Ψ（Ｘ）を取得する（ＳＴ８７）。
【０２００】
また、サインクリプション検証情報取得部６５は、電子署名Ｘ及び点Ｓから点Ｔ＝ξ-1（Ｘ−Ｓ）を求め（ＳＴ８８）、２つの点データＴ，Ｓ及びσ内のバイナリ値ｃをサインクリプション検証部６６に送出する。
【０２０１】
サインクリプション検証部６６は、点データＴ，Ｓ及びバイナリ値ｃを受けると、公開情報に基づいて、点Ｒ＝ｅn（Ｔ，ＱsID_B）を計算する（ＳＴ８９）。
【０２０２】
続いて、サインクリプション検証部６６は、値ｈ＝Ｈ2（Ｒ，ｃ）を計算すると共に（ＳＴ９０）、値ｍ＝Ｈ1（Ｒ）（＋）ｃを計算する（ＳＴ９１）。
【０２０３】
さらに、サインクリプション検証部６６は、点Ｖ＝ｅn（Ｓ，ＱID_A）を計算する（ＳＴ９２）。しかる後、サインクリプション検証部６６は、次の判定式の右辺を計算し、判定式が成立するか否かを判定する（ＳＴ９３）。
【数８】
2008178035.tif 000010
【０２０４】
ステップＳＴ９３の結果、判定式が成立する場合にサインクリプションデータσを正当であるとして、受け入れを示す検証結果を制御部６２に出力する（ＳＴ９４）また、判定式が成立しない場合にはサインクリプションデータσを不正であるとして、拒否を示す検証結果を制御部６２に出力する（ＳＴ９５）。
【０２０５】
以上のアンサインクリプション処理においては、公開情報要求及び秘密鍵要求の処理（ＳＴ８２，ＳＴ８４）を同時に実行しても良く、これに伴い、公開情報送信及び秘密鍵送信の処理（ＳＴ８３，ＳＴ８５）を同時に実行しても良い。
【０２０６】
上述したように本実施形態によれば、楕円曲線上のペアリングに基づく署名方式において、電子署名としてのサインクリプションデータσ’＝（ｃ，Ｓ，Ｔ）内の２つの点データＳ，Ｔを圧縮してサインクリプションデータσ＝（ｃ，Ｘ）を得るステップＳＴ７３を含むサインクリプション生成処理と、サインクリプションデータσ＝（ｃ，Ｘ）内の点データＸから２つの点データＳ，Ｔを取得するステップＳＴ８７，８８を含むサインクリプション検証処理とを実行する構成により、電子署名のデータ長を削減することができる。
【０２０７】
詳しくは、鍵生成センター装置４０において、楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]を２つの巡回群＜Ｐ＞，＜Ｑ＞の直和とし、＜Ｐ＞から選択した点Ｐと、＜Ｑ＞から選択した点Ｑと、楕円曲線上の射影Ψと、＜Ｐ＞から＜Ｑ＞への同型写像であるディストーションマップξとを公開した構成により、サインクリプション生成装置５０では、＜Ｐ＞に属する点Ｓと、＜Ｑ＞に属する点ξ（Ｔ）とを互いに加算して点Ｘ＝Ｓ＋ξ（Ｔ）に圧縮し、サインクリプションデータσ＝（ｃ，Ｘ）を生成して送信することができる。
【０２０８】
また、サインクリプション検証装置６０では、受信したサインクリプションデータσ＝（ｃ，Ｘ）内の点Ｘの射影Ψを求めることにより、点Ｓ＝Ψ（Ｘ）及び点Ｔ＝ξ-1（Ｘ−Ｓ）を取得することができる。
【０２０９】
このように、サインクリプション内の点Ｓ，Ｔを点Ｘに圧縮して送受信可能としたので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名としてのサインクリプションのデータ長を削減することができる。
【０２１０】
（第３の実施形態）
本発明の第３の実施形態は、第２の実施形態の変形例であり、具体的には、指定した検証者が、電子署名としてのサインクリプションを検証する第２の実施形態とは異なり、任意の検証者がサインクリプションを検証可能とし、且つ前述同様にサインクリプションのデータ長を削減するものである。
【０２１１】
図２１は本発明の第３の実施形態に係る電子署名システムとして機能するサインクリプションシステムの全体構成図である。サインクリプションシステムは、互いにインターネット１を介して通信可能な鍵生成センター装置４０、サインクリプション生成装置７０及びサインクリプション検証装置８０を備えている。ここで、鍵生成センター装置４０は第２の実施形態と同様のものであるが、送受信先がサインクリプション生成装置５０に代えてサインクリプション生成装置７０であり、同様に、送受信先がサインクリプション検証装置６０に代えてサインクリプション検証装置８０となっている。サインクリプション生成装置７０及びサインクリプション検証装置８０は、それぞれ本実施形態に対応した構成となっている。
【０２１２】
次に、各装置７０，８０について具体的に説明する。
【０２１３】
サインクリプション生成装置７０は、図２２に示すように、通信部７１、制御部７２、公開情報記憶部７３、秘密鍵記憶部７４、サインクリプション生成部７５、乱数生成部７６及びサインクリプション圧縮部７７を備えている。
【０２１４】
通信部７１は、インターネット１を介して鍵生成センター装置４０とサインクリプション検証装置８０との間で公開情報や鍵、サインクリプション（電子署名）等のデータを送受信する機能をもっている。
【０２１５】
制御部７２は、鍵生成センター装置４０から受けたデータに基づき、サインクリプションを生成してサインクリプション検証装置８０に送信するように各部７１，７３〜７７を制御するものであり、具体的には図２５及び図２６に示す処理を実行するように、各部７１，７３〜７７を制御する機能をもっている。また、制御部７２は、署名者Ａの操作により、署名者ＩＤ情報IDA及び検証者ＩＤ情報IDBを含む公開情報要求を通信部７１を介して鍵生成センター装置４０に送信する手段と、鍵生成センター装置４０から受信した署名者公開鍵ＰID_A、検証者公開鍵ＰID_B及び公開情報を公開情報記憶部７３に書き込む機能と、署名者ＩＤ情報IDAを含む秘密鍵要求を鍵生成センター装置４０に送信した後、鍵生成センター装置４０から受信した署名者秘密鍵ＱsID_Aを秘密鍵記憶部７４に書き込む機能とをもっている。
【０２１６】
公開情報記憶部７３は、制御部７２から書込み可能でサインクリプション生成部７５及びサインクリプション圧縮部７７から読出可能な記憶装置であり、鍵生成センター装置４０から通信部７１により受信して制御部７２により書き込まれた署名者公開鍵ＰID_A、検証者公開鍵ＰID_B及び公開情報を保存する。ここで、公開情報は、Ｐ，ＰID，Ｑ，ＱID，ｇ及び関数ＨP，ＨQ，Ｈ0，Ｈ1，Ｈ2，Ｈ2’，Ｈ3，Ｈ3’と、楕円曲線上の射影Ψ，ディストーションマップξを含んでいる。
【０２１７】
秘密鍵記憶部７４は、制御部７２から書込み可能でサインクリプション生成部７５から読出可能な記憶装置であり、鍵生成センター装置４０から通信部７１により受信して制御部７２により書き込まれた署名者秘密鍵ＱsID_Aを保存する。秘密鍵は、適宜、暗号化等により保護された状態で鍵生成センター装置４０から受信する。
【０２１８】
サインクリプション生成部７５は、公開情報・秘密鍵・乱数を用いてサインクリプションデータを生成するものである。サインクリプション生成部７５は、具体的には、乱数ｘ及び点ｇに基づいて、点Ｎ＝ｇ＾ｘ-1を計算する機能（但し、＾は、べき乗を表す）と、乱数ｘ及び署名者公開鍵ＰID_Aに基づいて、点Ｒ＝ｘＰID_Aを計算する機能と、乱数ｘ及び検証者公開鍵ＰID_Bに基づいて、点Ｓ＝ｘ-1ＰID_Bを計算する機能と、電子署名対象データｍに対し、点Ｎ、関数Ｈ1に基づいて、値ｃ＝Ｈ1（Ｎ）（＋）ｍを計算する機能（但し、（＋）は排他的論理和）と、得られた値ｃ、点Ｒ、点Ｓ及び関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する機能と、得られた値ｈ、乱数ｘ及び署名者秘密鍵ＱsID_Aに基づいて、点Ｔ＝（ｘ＋ｈ）-1ＱsID_Aを計算する機能と、得られた値ｃ，点Ｓ，Ｔをサインクリプション圧縮部７７に送出する機能とをもっている。
【０２１９】
乱数生成部７６は、サインクリプション生成部７５に制御され、サインクリプション生成用の乱数ｘを生成する機能をもっている。
【０２２０】
サインクリプション圧縮部７７は、サインクリプション生成部５５で生成されたサインクリプションの署名に関するデータを圧縮し、そのデータ長を削減するものである。サインクリプション圧縮部７７は、具体的には、点Ｓ及び点Ｔを互いに加算して点Ｘ（＝Ｓ＋Ｔ）に圧縮する機能と、点Ｘ、点Ｒ及び値ｃからなるサインクリプションσ＝（ｃ，Ｒ，Ｘ）を制御部７２及び通信部７１を介してサインクリプション検証装置８０に送信する機能とをもっている。
【０２２１】
一方、サインクリプション検証装置８０は、図２３に示すように、通信部８１、制御部８２、公開情報記憶部８３、秘密鍵記憶部８４、サインクリプション検証情報取得部８５、サインクリプション検証部８６及び公開鍵計算部８７を備えている。
【０２２２】
通信部８１は、インターネット１を介して鍵生成センター装置４０とサインクリプション生成装置７０との間で公開情報や鍵、サインクリプション等のデータを送受信する機能をもっている。
【０２２３】
制御部８２は、鍵生成センター装置４０から受けたデータに基づき、サインクリプション生成装置７０から受信したサインクリプションを検証するように各部８１，８３〜８７を制御するものであり、具体的には図２７及び図２８に示す処理を実行するように、各部８１，８３〜８７を制御する機能をもっている。また、制御部８２は、検証者Ｂの操作により、サインクリプション生成装置５０の署名者ＩＤ情報IDAを含む公開情報要求を通信部８１を介して鍵生成センター装置４０に送信する機能と、鍵生成センター装置４０から受信した署名者公開鍵ＰID_A及び公開情報を公開情報記憶部８３に書き込む機能と、検証者ＩＤ情報IDBを含む秘密鍵要求を通信部８１を介して鍵生成センター装置４０に送信する機能と、鍵生成センター装置４０から通信部８１を介して受信した検証者秘密鍵ＱsID_Bを秘密鍵記憶部８４に書き込む機能とをもっている。
【０２２４】
公開情報記憶部８３は、制御部８２から書込み可能で各部８５〜８７から読出可能な記憶装置であり、鍵生成センター装置４０から通信部８１により受信して制御部８２により書き込まれた署名者公開鍵ＰID_A及び公開情報を保存する。ここで、公開情報は、Ｐ，ＰID，Ｑ，ＱID，ｇ及び関数ＨP，ＨQ，Ｈ0，Ｈ1，Ｈ2，Ｈ2’，Ｈ3，Ｈ3’と、楕円曲線上の射影Ψ，ディストーションマップξを含んでいる。
【０２２５】
秘密鍵記憶部８４は、制御部８２から書込み可能で各部８６，８７から読出可能な記憶装置であり、鍵生成センター装置４０から通信部８１により受信して制御部８２により書き込まれた検証者秘密鍵ＱsID_Bを保存する。
【０２２６】
サインクリプション検証情報取得部８５は、サインクリプション生成装置７０から通信部８１及び制御部８２を介して受信したサインクリプションから、検証に必要なデータを取得するものである。サインクリプション検証情報取得部８５は、具体的には、サインクリプション生成装置５０から通信部６１及び制御部６２を介してサインクリプションσ＝（ｃ，Ｒ，Ｘ）を受信すると、このサインクリプションσ＝（ｃ，Ｒ，Ｘ）及び公開情報内の射影Ψに基づいて、点Ｓ＝Ψ（Ｘ）を計算する機能と、得られた点Ｓ及びサインクリプションσ＝（ｃ，Ｒ，Ｘ）内の点Ｘに基づいて、点Ｔ＝Ｘ−Ｓを計算する機能と、得られた点Ｔ，Ｓ，Ｒ及び値ｃをサインクリプション検証部８６に送出する機能とをもっている。
【０２２７】
サインクリプション検証部８６は、サインクリプション生成装置７０から通信部８１及び制御部８２を介して受信したサインクリプションが正当であるか否かを検証するものである。サインクリプション検証部８６は、具体的には、サインクリプション検証情報取得部８５から点Ｔ，Ｓ，Ｒ及び値ｃを受けると、点Ｒ、点Ｓ、値ｃ及び関数Ｈ3’に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算する機能と、得られた値ｈ、点Ｒ、点Ｔ及び署名者公開鍵ＰID_Aに関し、楕円曲線上のペアリングに基づく点Ｖ＝ｅn（Ｒ＋ｈＰID_A，Ｔ）を計算する機能と、点Ｓ及び検証者秘密鍵ＱsID_Bに関し、楕円曲線上のペアリングに基づく点Ｎ＝ｅn（Ｓ，ＱsID_B）を計算する機能と、得られた点Ｎ、値ｃ及び関数Ｈ1に基づいて、電子署名対象データｍ＝Ｈ1（Ｎ）（＋）ｃを計算する機能と、点Ｖ及び点ｇに関する判定式Ｖ＝ｇが成立するか否かを判定する機能と、判定の結果、判定式が成立する場合にはサインクリプションσ＝（ｃ，Ｒ，Ｘ）を受け入れる機能と、
判定の結果、判定式が成立しない場合にはサインクリプションσ＝（ｃ，Ｒ，Ｘ）を拒否する機能とをもっている。
【０２２８】
公開鍵計算部８７は、２回目以降の検証処理にて鍵生成センター装置４０に公開情報を要求せずに、公開鍵情報記憶部８３内の公開情報に基づいて、鍵生成センター装置４０と同様の処理を行い、署名者公開鍵ＰID_Aなどの情報を計算するものである。
【０２２９】
次に、以上のように構成されたサインクリプションシステムの動作を図２４乃至図２８を用いて説明する。なお、以下の説明は、全体動作（図２４）、セットアップ処理、サインクリプション処理（図２５）、サインクリプション処理内のサインクリプション生成処理（図２６）、アンサインクリプション処理（図２７）及びアンサインクリプション処理内のサインクリプション検証処理（図２８）、の順に行う。
【０２３０】
（全体動作：図２４）
サインクリプションシステムの全体動作は、前述同様に、セットアップ処理（ＳＴ５１〜ＳＴ５５）、サインクリプションデータ要求（ＳＴ１００）、サインクリプション処理（ＳＴ１０１〜ＳＴ１１５）、サインクリプションデータ送付（ＳＴ１２０）及びアンサインクリプション処理（ＳＴ１２１〜ＳＴ１３５）の順に、実行される。
【０２３１】
以下、セットアップ処理、サインクリプション処理、アンサインクリプション処理、の順に説明する。
【０２３２】
（セットアップ処理）
セットアップ処理は、図１６を用いて前述した通りに実行される。  
（サインクリプション処理：図２５）
サインクリプション生成装置７０では、署名者Ａの操作により、サインクリプション生成要求が入力されると（ＳＴ１０１）、公開情報を取得するため、公開情報要求を鍵生成センター装置４０に送信する（ＳＴ１０２）。
【０２３３】
鍵生成センター装置４０は、公開情報要求を受けると、署名者ＡのＩＤ情報IDAに対応する署名者公開鍵ＰID_A＝s(IDA)Ｐ、検証者ＢのＩＤ情報に対応する検証者公開鍵ＰID_B＝s(IDB)Ｐを計算し、各公開鍵ＰID_A，ＰID_Bと共に公開情報をサインクリプション生成装置７０に送信する（ＳＴ１０３）。
【０２３４】
また、サインクリプション生成装置７０は、秘密鍵を取得するため、秘密鍵要求を鍵生成センター装置４０に送信する（ＳＴ１０４）。
【０２３５】
鍵生成センター装置４０は、秘密鍵要求を受けると、署名者ＡのＩＤ情報IDAに対応する署名者秘密鍵ＱsID_A＝s(IDA)-1Ｑを計算し、この署名者秘密鍵ＱsID_Aをサインクリプション生成装置７０に送信する（ＳＴ１０５）。
【０２３６】
サインクリプション生成装置７０は、署名者秘密鍵ＱsID_Aを受けると、以下のように、サインクリプションデータを生成するサインクリプション生成処理を実行する（ＳＴ１０６〜ＳＴ１１５）。
【０２３７】
［サインクリプション生成処理：図２６］
サインクリプション生成装置７０においては、署名者Ａの操作により、サインクリプション対象データｍが入力されたとする（ＳＴ１０６）。
【０２３８】
続いて、サインクリプション生成装置７０においては、サインクリプション生成部７５が乱数生成部７６を用いて乱数ｘ∈Ｚｎ*を生成する（ＳＴ１０７）。
【０２３９】
また、サインクリプション生成部７５は、点Ｎ＝ｇ＾ｘ-1（但し、＾はべき乗を表す記号）を計算し（ＳＴ１０８）、さらに、点Ｒ＝ｘＰID_Aを計算する（ＳＴ１０９）。
【０２４０】
続いて、サインクリプション生成部７５は、点Ｓ＝ｘ-1ＰID_Bを計算し（ＳＴ１１０）、値ｃ＝Ｈ1（Ｎ）（＋）ｍを計算する（ＳＴ１１１）。
【０２４１】
また、サインクリプション生成部５５は、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を計算し（ＳＴ１１２）、点Ｔ＝（ｘ＋ｈ）-1ＱsID_Aを計算する（ＳＴ１１３）。
【０２４２】
しかる後、サインクリプション生成部７５は、１つのバイナリ値ｃと、３つの点データＲ，Ｓ，Ｔとからなるサインクリプションデータσ’＝（ｃ，Ｒ，Ｓ，Ｔ）を取得し、このサインクリプションデータσ’をサインクリプション圧縮部７７に送出する。
【０２４３】
サインクリプション圧縮部７７は、このサインクリプションデータσ’を受けると、サインクリプションデータσ’内の２つの点データＳ，Ｔを互いに加算して圧縮した点Ｘ＝Ｓ＋Ｔを求める（ＳＴ１１４）。
【０２４４】
これにより、サインクリプション圧縮部５７は、この点Ｘのデータと、サインクリプションデータσ’内のバイナリ値ｃと残りの点データＲとからなるサインクリプションデータσ＝（ｃ，Ｒ，Ｘ）を取得し、このサインクリプションデータσ＝（ｃ，Ｒ，Ｘ）を制御部７２に出力する（ＳＴ１１５）。
【０２４５】
以上のサインクリプション処理においては、公開情報要求及び秘密鍵要求の処理（ＳＴ１０２，ＳＴ１０４）を同時に実行しても良く、これに伴い、公開情報送信及び秘密鍵送信の処理（ＳＴ１０３，ＳＴ１０５）を同時に実行しても良い。
【０２４６】
（アンサインクリプション処理：図２７）
アンサインクリプション検証装置８０では、検証者Ｂの操作により、サインクリプションデータσ＝（ｃ，Ｒ，Ｘ）を含むサインクリプション検証要求が入力されると（ＳＴ１２１）、署名者Ａの公開鍵及び公開情報を取得するため、公開情報要求を鍵生成センター装置４０に送信する（ＳＴ１２２）。
【０２４７】
鍵生成センター装置４０は、公開情報要求を受けると、署名者ＡのＩＤ情報IDAに対応する公開鍵ＰID_A＝s(IDA)Ｐを計算し、この公開鍵ＰID_Aと共に公開情報をサインクリプション検証装置８０に送信する（ＳＴ１２３）。
【０２４８】
また、サインクリプション検証装置８０は、検証者ＩＤの秘密鍵を取得するため、秘密鍵要求を鍵生成センター装置４０に送信する（ＳＴ１２４）。
【０２４９】
鍵生成センター装置４０は、秘密鍵要求を受けると、検証者ＢのＩＤ情報IDBに対応する検証者秘密鍵ＱsID_B＝s(IDB)-1Ｑを計算し、この検証者秘密鍵ＱsID_Bをサインクリプション検証装置８０に送信する（ＳＴ１２５）。
【０２５０】
サインクリプション検証装置８０は、署名者公開鍵ＰsID_A、公開情報及び検証者秘密鍵ＱsID_Bを受けると、以下のように、サインクリプションデータを検証するサインクリプション検証処理を実行する（ＳＴ１２６〜ＳＴ１３５）。
【０２５１】
［サインクリプション検証処理：図２８］
サインクリプション検証装置８０においては、受信したサインクリプションデータσ＝（ｃ，Ｒ，Ｘ）がサインクリプション検証情報取得部８５に入力されたとする（ＳＴ１２６）。
【０２５２】
サインクリプション検証情報取得部８５は、サインクリプションデータσ＝（ｃ，Ｒ，Ｘ）の電子署名Ｘから楕円曲線上の射影Ψを用いて点Ｓ＝Ψ（Ｘ）を取得する（ＳＴ１２７）。
【０２５３】
また、サインクリプション検証情報取得部８５は、電子署名Ｘ及び点Ｓから点Ｔ＝Ｘ−Ｓを求め（ＳＴ１２８）、３つの点データＲ，Ｔ，Ｓ及びσ内のバイナリ値ｃをサインクリプション検証部８６に送出する。
【０２５４】
サインクリプション検証部８６は、点データＲ，Ｔ，Ｓ及びバイナリ値ｃを受けると、公開情報に基づいて、値ｈ＝Ｈ3’（Ｒ，Ｓ，ｃ）を求める（ＳＴ１２９）。
【０２５５】
続いて、サインクリプション検証部８６は、点Ｖ＝ｅn（Ｒ＋ｈＰID_A，Ｔ）を計算すると共に（ＳＴ１３０）、点Ｎ＝ｅn（Ｓ，ＱsID_B）（＋）ｃを計算する（ＳＴ１３１）。
【０２５６】
さらに、サインクリプション検証部８６は、値ｍ＝Ｈ1（Ｎ）（＋）ｃを計算する（ＳＴ１３２）。しかる後、サインクリプション検証部８６は、計算した点Ｖと公開情報内の点ｇを用い、次の判定式が成立するか否かを判定する（ＳＴ１３３）。
【数９】
2008178035.tif 000011
【０２５７】
ステップＳＴ１３３の結果、判定式が成立する場合にサインクリプションデータσを正当であるとして、受け入れを示す検証結果を制御部８２に出力する（ＳＴ１３４）また、判定式が成立しない場合にはサインクリプションデータσを不正であるとして、拒否を示す検証結果を制御部６２に出力する（ＳＴ１３５）。
【０２５８】
以上のアンサインクリプション処理においては、公開情報要求及び秘密鍵要求の処理（ＳＴ１２２，ＳＴ１２４）を同時に実行しても良く、これに伴い、公開情報送信及び秘密鍵送信の処理（ＳＴ１２３，ＳＴ１２５）を同時に実行しても良い。
【０２５９】
また、アンサインクリプション処理においては、秘密鍵要求及び秘密鍵送信の処理（ＳＴ１２４，ＳＴ１２５）の処理を行わず、かつサインクリプション検証処理の点Ｎの計算処理及び値ｍの計算処理（ＳＴ１３１，ＳＴ１３２）を行わない場合は、任意の検証者がサインクリプションの電子署名の正当性を検証することができる。当然この際には暗号データｃを復号することはできない。
【０２６０】
上述したように本実施形態によれば、楕円曲線上のペアリングに基づく署名方式において、電子署名としてのサインクリプションデータσ’＝（ｃ，Ｒ，Ｓ，Ｔ）内の２つの点データＳ，Ｔを圧縮してサインクリプションデータσ＝（ｃ，Ｒ，Ｘ）を得るステップＳＴ１１４を含むサインクリプション生成処理と、サインクリプションデータσ＝（ｃ，Ｒ，Ｘ）内の点データＸから２つの点データＳ，Ｔを取得するステップＳＴ１２７，１２８を含むサインクリプション検証処理とを実行する構成により、電子署名のデータ長を削減することができる。
【０２６１】
詳しくは、鍵生成センター装置４０において、楕円曲線Ｅ上のｎねじれ群Ｅ[ｎ]を２つの巡回群＜Ｐ＞，＜Ｑ＞の直和とし、＜Ｐ＞から選択した点Ｐと、＜Ｑ＞から選択した点Ｑと、楕円曲線上の射影Ψと、＜Ｐ＞から＜Ｑ＞への同型写像であるディストーションマップξとを公開した構成により、サインクリプション生成装置７０では、＜Ｐ＞に属する点Ｓと、＜Ｑ＞に属する点Ｔとを互いに加算して点Ｘ＝Ｓ＋Ｔに圧縮し、サインクリプションデータσ＝（ｃ，Ｒ，Ｘ）を生成して送信することができる。
【０２６２】
また、サインクリプション検証装置８０では、受信したサインクリプションデータσ＝（ｃ，Ｒ，Ｘ）内の点Ｘの射影Ψを求めることにより、点Ｓ＝Ψ（Ｘ）及び点Ｔ＝Ｘ−Ｓを取得することができる。
【０２６３】
このように、サインクリプションデータ内の点Ｓ，Ｔを点Ｘに圧縮して送受信可能としたので、楕円曲線上のペアリングに基づく署名方式において、署名者と検証者との間で送受信する電子署名としてのサインクリプションのデータ長を削減することができる。
【０２６４】
なお、本発明は、上記各実施形態の方式への適用に限らず、署名の連結や、プロキシー(proxy)署名など、その他の方式においても、同様に楕円曲線上の射影を用いることで、各方式における署名長を削減することができる。すなわち、楕円曲線上の複数の点データを含む電子署名を送受信する方式であれば、任意の方式においても同様に、複数の点データを１つの点データに圧縮して送信した後に、受信先でこの圧縮された点データから射影により複数の点データを取得できるので、各方式における署名長を削減することができる。
【０２６５】
また、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０２６６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０２６７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０２６８】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０２６９】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０２７０】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０２７１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０２７２】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０２７３】
【図１】本発明の第１の実施形態に係る電子署名システムの全体構成図である。
【図２】同実施形態における鍵生成センター装置の構成を示す模式図である。
【図３】同実施形態における電子署名生成装置の構成を示す模式図である。
【図４】同実施形態における電子署名検証装置の構成を示す模式図である。
【図５】同実施形態における全体動作を示すシーケンス図である。
【図６】同実施形態におけるセットアップ処理を示すフローチャートである。
【図７】同実施形態における署名処理を示すシーケンス図である。
【図８】同実施形態における電子署名生成処理を示すフローチャートである。
【図９】同実施形態における検証処理を示すシーケンス図である。
【図１０】同実施形態における電子署名検証処理を示すフローチャートである。
【図１１】本発明の第２の実施形態に係るサインクリプションシステムの全体構成図である。
【図１２】同実施形態における鍵生成センター装置の構成を示す模式図である。
【図１３】同実施形態におけるサインクリプション生成装置の構成を示す模式図である。
【図１４】同実施形態におけるサインクリプション検証装置の構成を示す模式図である。
【図１５】同実施形態における全体動作を示すシーケンス図である。
【図１６】同実施形態におけるセットアップ処理を示すフローチャートである。
【図１７】同実施形態におけるサインクリプション処理を示すシーケンス図である。
【図１８】同実施形態におけるサインクリプション生成処理を示すフローチャートである。
【図１９】同実施形態におけるアンサインクリプション処理を示すシーケンス図である。
【図２０】同実施形態におけるサインクリプション検証処理を示すフローチャート図である。
【図２１】本発明における第３の実施形態に係るサインクリプションシステムの全体構成図である。
【図２２】同実施形態におけるサインクリプション生成装置の構成を示す模式図である。
【図２３】同実施形態におけるサインクリプション検証装置の構成を示す模式図である。
【図２４】同実施形態における全体動作を示すシーケンス図である。
【図２５】同実施形態におけるサインクリプション処理を示すシーケンス図である。
【図２６】同実施形態におけるサインクリプション生成処理を示すフローチャートである。
【図２７】同実施形態におけるアンサインクリプション処理を示すシーケンス図である。
【図２８】同実施形態におけるサインクリプション検証処理を示すフローチャートである。
【図２９】楕円曲線上のｎねじれ点Ｅ[ｎ]の構成を説明するための模式図である。
【図３０】楕円曲線上の射影Ψ，Ψ’を説明するための模式図である。
【図３１】楕円曲線上のディストーションマップξを説明するための模式図である。
【符号の説明】
【０２７４】
１…インターネット、１０，４０…鍵生成センター装置、１１，２１，３１，４１，５１，６１，７１，８１…通信部、１２，２２，３２，４２，５２，６２，７２，８２…制御部、１３，４３…鍵情報生成部、１４，４４…選択データ記憶部、１５，４５…乱数生成部、１６，２４，４６，５４，６４，７４，８４…秘密鍵記憶部、１７，２３，３３，４７，５３，６３，７３，８７…公開情報記憶部、１８，４８…ＩＤ対応秘密鍵生成部、２０…電子署名生成装置、２５…電子署名生成部、２６，５６，７６…乱数生成部、２７…電子署名圧縮部、３０…電子署名検証装置、３４…電子署名検証情報取得部、３５…電子署名検証部、３６，６７，８７…公開鍵計算部、５０，７０…サインクリプション生成装置、５５，７５…サインクリプション生成部、５７，７７…サインクリプション圧縮部、６０，８０…サインクリプション検証装置、６５，８５…サインクリプション検証情報取得部、６６，８６…サインクリプション検証部。
【図１】
2008178035.tif 000012
【図２】
2008178035.tif 000013
【図３】
2008178035.tif 000014
【図４】
2008178035.tif 000015
【図５】
2008178035.tif 000016
【図６】
2008178035.tif 000017
【図７】
2008178035.tif 000018
【図８】
2008178035.tif 000019
【図９】
2008178035.tif 000020
【図１０】
2008178035.tif 000021
【図１１】
2008178035.tif 000022
【図１２】
2008178035.tif 000023
【図１３】
2008178035.tif 000024
【図１４】
2008178035.tif 000025
【図１５】
2008178035.tif 000026
【図１６】
2008178035.tif 000027
【図１７】
2008178035.tif 000028
【図１８】
2008178035.tif 000029
【図１９】
2008178035.tif 000030
【図２０】
2008178035.tif 000031
【図２１】
2008178035.tif 000032
【図２２】
2008178035.tif 000033
【図２３】
2008178035.tif 000034
【図２４】
2008178035.tif 000035
【図２５】
2008178035.tif 000036
【図２６】
2008178035.tif 000037
【図２７】
2008178035.tif 000038
【図２８】
2008178035.tif 000039
【図２９】
2008178035.tif 000040
【図３０】
2008178035.tif 000041
【図３１】
2008178035.tif 000042