(57)【要約】【課題】各人が使う署名の検証用の鍵として、その署名者のＩＤ情報から変換できる公開鍵を使うことが可能なものを構成できるような電子署名等、いくつかの電子署名方式について、その署名サイズを削減する電子署名方法を提供する。【解決手段】楕円曲線上のペアリングによる公開鍵を用いる署名生成の方式につき、ある種の場合に、楕円曲線の点の性質を用いて２点分のデータを１点分のサイズにできることを用いて署名サイズを削減する。解決手段は、楕円曲線上の点を選択し、これから署名者の公開鍵ペアを作成し、秘密鍵を署名者に配布する工程と、署名者がこれを用いて署名を生成する工程と、署名検証者が楕円曲線上のペアリングを用いた検査式の成立の検証を行う工程とを含む。【選択図】図３
2008219708.tif 000002
【特許請求の範囲】
【請求項１】
文書データＭに対する電子署名データを作成し、この電子署名データに基づいて署名生成
を行う署名装置であって、
有限体上の楕円曲線Ｅと、そのｎねじれ点Ｐ，Ｑと、署名者の秘密鍵ｄと、公開鍵Ｐｐｕ
Ｂを作成する手段と、
秘密鍵ｄと、文書データＭを用いて署名データを生成する手段と、
前記文書データＭと、署名データと、署名者の公開鍵ＰｐｕＢを用いて、前記署名データ
を検査する手段とを備え、
前記署名データがｎねじれ点Ｒ，Ｓのペアであって、Ｒが＜Ｐ＞に属する点で、Ｓが＜Ｑ
＞に属する点である場合に、前記署名データとして点Ｒ，Ｓのペアの代わりに点Ｔ＝Ｒ＋
Ｓを使用することを特徴とする署名生成装置。
【請求項２】
前記署名データを検査する手段は、前記文書データＭに対して生成された署名データが点
Ｔであった場合に、点Ｔからｎねじれ点Ｒ，Ｓのペアを生成し、前記署名データを検証す
る手段で前記文書データＭと、署名データと、署名者の公開鍵Ｑを用いて、前記署名デー
タを検査することを特徴とする請求項１記載の署名検証装置。
【請求項３】
点Ｔからｎねじれ点Ｒ、Ｓのペアを生成する際、φをＥ[ｎ]上定義されたフロベニウス写
像、λ1、λ2はφの固有値で、λ1、λ2は異なるものとするとき、μ=(φ-λ2)/(λ1-λ2
)として、
Ｓ＝μＴ，Ｒ＝Ｔ−ＳもしくはＲ＝μＴ，Ｓ＝Ｔ−Ｒとすることによって点Ｒ，Ｓのペア
を生成することを特徴とする請求項２記載の署名検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的な文書に対して署名を行う署名生成装置及び署名検証装置に関する。
【背景技術】
【０００２】
電子署名の作成法として様々な方法が考案されている。
【０００３】
近年、公開鍵とそれに対応する秘密鍵の所有者を結び付ける方法の一つとして、所有者の
ＩＤ情報から公開鍵を作成する方法が知られている。これを用いる場合は、通常ＰＫＩ（
ＰｕＢｌｉｃ Ｋｅｙ Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ：公開鍵認証基盤）等で用いられる
公開鍵証明書等は不用になり、より簡易なセキュリティシステムの構築が可能になる、と
いう利点がある。
【０００４】
ところで、暗号・署名技術においては、楕円曲線のペアリングを用いた方式が多数考案さ
れている。これによって、従来は困難であったＩＤ情報に基づく暗号・署名技術が実現さ
れた。例えば署名については、特許文献１、特許文献２、非特許文献１の方法がある。
【０００５】
一方、ペアリングを用いることによって、従来に比べて、より長さの短い署名データも生
成されるようになった。例えば非特許文献２の方法である。
【非特許文献１】Ｋ. Ｇ. Ｐａｔｅｒｓｏｎ, " ＩＤ-Ｂａｓｅｄ ｓｉｇｎａｔｕｒｅｓ ｆｒｏｍ ｐａｉｒｉｎｇｓ ｏｎ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅｓ, " Ｅｌｅｃｔｒｏｎｉｃｓ Ｌｅｔｔｅｒｓ 38(18)(2002), ｐｐ. 1025-1026.
【非特許文献２】Ｄ. Ｂｏｎｅｈ, Ｂ. Ｌｙｎｎ, Ｈ. Ｓｈａｃｈａｍ, "Ｓｈｏｒｔ ｓｉｇｎａｔｕｒｅｓ ｆｒｏｍ ｔｈｅ Ｗｅｉｌ ｐａｉｒｉｎｇ," Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ -- Ａｓｉａｃｒｙｐｔ'2001, Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｏｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ <http://www.springer.de/comp/lncs/index.html> 2248, Ｓｐｒｉｎｇｅｒ-Ｖｅｒｌａｇ (2002), ｐｐ. 514--532.
【非特許文献３】Ｊ.Ｍａｌｏｎｅ-Ｌｅｅ, " ＩＤｅｎｔｉｔｙ-Ｂａｓｅｄ Ｓｉｇｎｃｒｙｐｔｉｏｎ, "ＩＡＣＲ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ: Ｒｅｐｏｒｔ 2002/098.
【非特許文献４】Ａ.Ｂｏｌｄｙｒｅｖａ, Ａ. Ｐａｌａｃｉｏ ａｎｄ Ｂ.Ｗａｒｉｎｓｃｈｉ, "Ｓｅｃｕｒｅ Ｐｒｏｘｙ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅｓ ｆｏｒ Ｄｅｌｅｇａｔｉｏｎ ｏｆ ｓｉｇｎｉｎｇ ｒｉｇｈｔｓ, " ＩＡＣＲ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ: Ｒｅｐｏｒｔ 2003/096.
【特許文献１】特開２００４−２０１１２４号公報
【特許文献２】特開２００６−２０３８２５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、本発明の発明者によれば、上記した特許文献１、特許文献２、非特許文献１、非
特許文献２、非特許文献３及び非特許文献４に開示されている技術と比べて、ある楕円曲
線上のペアリングによる公開鍵を用いる署名方法については検討の余地がある。具体的に
は、楕円曲線上のペアリングによる公開鍵を用いる署名生成の方式については、上記各種
文献における署名生成の方式では署名の長さを著しく削減することはできない。署名の長
さができる限り短いことは一般に望まれており、このような署名の長さを短くすることの
できる技術が今後有望視されると判断できる。
【０００７】
かかる状況において、本発明の目的は、ペアリングを用いたある種の署名方式について、
署名データの長さをより削減できる署名生成装置及び署名検証装置を提供することである。
【課題を解決するための手段】
【０００８】
上記の目的を達成するための第１の発明は、文書データＭに対する電子署名データを作成
し、この電子署名データに基づいて署名生成を行う署名装置であって、有限体上の楕円曲
線Ｅと、そのｎねじれ点Ｐ,Ｑと、署名者の秘密鍵ｄと、公開鍵ＰｐｕＢを作成する工程
と、秘密鍵ｄと、文書データＭを用いて署名データを生成する工程と、前記文書データＭ
と、署名データと、署名者の公開鍵ＰｐｕＢを受け取って、署名を検査する工程を持つ署
名装置において、署名データがｎねじれ点Ｒ,Ｓのペアであって、Ｒが＜Ｐ＞に属する点
で、Ｓが＜Ｑ＞に属する点である場合に、署名データとして点Ｒ,Ｓのペアの代わりに点
Ｔ=Ｒ+Ｓを生成する工程と、点Ｔ からｎねじれ点Ｒ,Ｓのペアを生成し、署名検証工程で
このデータと、前記文書データＭと、署名データと、センターの公開情報Ｑ,ＰｐｕＢ,Ｑ
ｐｕＢと、署名者の公開鍵Ｑ_ＩＤを受け取って、署名を検査する工程を持つことを特徴
とする。
【０００９】
なお、第１の発明は、「装置」として表現されているが、これに限らず、「システム」、
「方法」、「プログラム」又は「記憶媒体」等として表現してもよいことは言うまでもな
い。
【発明の効果】
【００１０】
本発明によれば、ペアリングを用いたある種の署名方式について、署名データの長さをよ
り削減できる。
【発明を実施するための最良の形態】
【００１１】
本発明の各実施形態について図面を用いて説明する。
【００１２】
初めに本発明で用いるペアリング（ベイユペアリング）について説明する。有限体Ｆｑ
上の楕円曲線Ｅについて、楕円曲線のｎねじれ点の成す群Ｅ[ｎ]の２点Ｐ,Ｑをとる。ペ
アリングｅ( , )はＥ[ｎ]からＦｑ又はその拡大体に含まれる位数ｎの乗法群への写像で
あり、以下の性質がある。点は全て群Ｅ[ｎ]内で考える。
【００１３】
（非退化）
ある点Ｐが任意の点Ｑに対して、ｅ(Ｐ,Ｑ)=0を満たすとき、Ｐ=0である。
【００１４】
（反対称）
任意の点Ｐ.Ｑに対して、ｅ(Ｐ,Ｑ)=ｅ(Ｑ,Ｐ)^(-1)が成立する。
【００１５】
（双線型）
任意の点Ｐ.Ｑに対して、
ｅ(Ｐ+Ｑ,Ｒ)=ｅ(Ｐ,Ｒ)ｅ(Ｑ,Ｒ)
ｅ(Ｐ,Ｑ+Ｒ)=ｅ(Ｐ,Ｑ)ｅ(Ｐ,Ｒ)
が成立する。
【００１６】
以下、この性質を基にした実施形態について説明する。
【００１７】
（第１の実施形態）
以下は暗号・署名生成を同時に行う非特許文献３の方法に適用したものである。
【００１８】
まず準備として、センター１０１は、図１に示すように、楕円曲線パラメータと公開情
報である基点Ｇ,Ｐ,ＰｐｕＢ=ｓＰ,Ｑ,ＱｐｕＢ=ｓＱ及び秘密情報ｓを準備し、Ｉ番目の
署名者ＩＤｉが用いる署名装置Ｉ（Ｉ：１，２，・・・，ｎ）に対して、公開鍵Ｑ_ＩＤ
ｉ=Ｈ1(Ｑ_ＩＤ)｛Ｈ1は公開のハッシュ関数、秘密鍵Ｄ_ＩＤｉ=ｓＨ1(Ｑ_ＩＤ)｝を計算
し、秘密鍵Ｄ_ＩＤｉをＩ番目の署名者に秘密裏に配布しておく（図１参照）。
【００１９】
このとき次の工程で暗号と署名を同時に生成する。
【００２０】
Ｕ=ｘＰ、ｒ=Ｈ2(Ｕ||ｍ)、Ｗ=ｘＰｐｕＢ、Ｖ=ｒＳ_ＩＤＢ+Ｗ、ｙ=ｅ(Ｗ,Ｑ_ＩＤＢ)、
ｋ=Ｈ3(ｙ)、ｃ=ｋ(+)ｍ
非特許文献２ではｃが暗号、(Ｕ,Ｖ)が署名となっているが、本発明を適用してＴ=Ｕ+Ｖ
として、Ｔを署名とする（図３参照）。
【００２１】
復号工程では、復号者Ｂは、秘密鍵Ｄ_ＩＤＢを用いて復号する（図４参照）。
【００２２】
φをＥ[ｎ]上定義されたフロベニウス写像、λ1、λ2はφの固有値で、λ1、λ2は異なる
ものとするとき、μ=(φ-λ2)/(λ1-λ2)として、
点Ｔ より、Ｖ=μＴ, Ｕ=Ｔ-Ｖもしくは、Ｕ=μＴ, Ｖ=Ｔ-Ｕとする。
【００２３】
このとき次の計算によりｍが復号される。
【００２４】
ｙ=ｅ(Ｄ_ＩＤＢ,Ｕ)、ｋ=Ｈ_3(ｙ)、ｍ=ｋ(+)ｃ
署名検証工程では、
まずｒ=Ｈ_2(Ｕ||ｍ)を求め、
ｅ(Ｐ,Ｖ)=ｅ(Ｐ_ｐｕＢ,Ｑ_ＩＤａ)^ｒ ｅ(Ｑ_ｐｕＢ,Ｕ)
であるか、又はこれと等価な関係式が成立するかどうかを検査し、成立する場合は、署名
は正当なものと判断し、成立しない場合は、署名は正しくないと判断する（図４参照）。
【００２５】
（第２の実施形態）
非特許文献２の方法によって生成された短い署名２つについて、本発明を適用して署名を
１つに結合して署名サイズを短くする。
【００２６】
準備として、次のように鍵生成を行う。
【００２７】
まず、楕円曲線Ｅのパラメータ、基点Ｇ、Ｐ、Ｑを利用者間で共有する。この場合は必ず
しもセンターからの配布とする必要はない。
【００２８】
Ｆ_ｑの元ｘ_ａ,ｘ_Ｂをランダムに選んでそれぞれＡ,Ｂの秘密鍵、Ｅ[ｎ]の元Ｐに対し
て、Ｙ_ａ=ｘ_ａＰ、Ｙ_Ｂ=ｘ_ＢＰをそれぞれＡ,Ｂの公開鍵とする（図５参照）。
【００２９】
署名生成工程では、
Ｈを<Ｐ>に値を取るハッシュ関数とする。
【００３０】
メッセージＭ1に対するＡの署名はＳａ=ｘａＨ(Ｍ1)であり、
メッセージＭ2に対するＢの署名はＳＢ=ｘＢＨ(Ｍ2)となる。
【００３１】
ψをｄｉｓｔｏｒｓｉｏｎ ｍａｐと呼ばれるＥ[ｎ]上の自己同型写像として、ψ(Ｐ)=Ｑ
とする。このとき、Ｓ=Ｓａ+ψ(ＳＢ)をメッセージＭ1,Ｍ2の両方に対する署名とする（
図６の「署名生成」参照）。
【００３２】
署名検証工程では、
Ｍ1に対するＡの署名の検証は、ｅ(Ｓ,Ｑ)=ｅ(Ｈ(Ｍ1), ψ(Ｙ_ａ))であるか、又はこれ
と等価な関係式が成立するかどうかを検査し、成立する場合は、署名は正当なものと判断
し、成立しない場合は、署名は正しくないと判断する。
【００３３】
Ｍ2に対するＢの署名の検証は、ｅ(Ｐ,Ｓ)=ｅ(Ｙ_Ｂ, ψ(Ｈ(Ｍ2)))であるか、又はこれ
と等価な関係式が成立するかどうかを検査し、成立する場合は、署名は正当なものと判断
し、成立しない場合は、署名は正しくないと判断する（図６の「署名検証」参照）。
【００３４】
（第３の実施形態）
非特許文献４とは異なる次のようなｐｒｏｘｙ署名（代理署名）を構成できる。
【００３５】
準備として、次のように鍵生成を行う。
【００３６】
Ｆ_ｑの元ｘ_ａ,ｘ_Ｂをランダムに選んでそれぞれＡ,Ｂの秘密鍵、Ｅ[ｎ]の元Ｐに対し
て、Ｙ_ａ=ｘ_ａＰ、Ｙ_Ｂ=ｘ_ＢＰをそれぞれＡ,Ｂの公開鍵とする（図５参照）。
【００３７】
ｐｒｏｘｙ署名鍵生成工程では、
署名者Ａは、ｗａｒｅｎｔ ｗに対するｃｅｒｔをＷ=00||Ｙ_Ｂ||ｗに対する署名として
次のようにして生成する。
【００３８】
Ｓ_ｗ=ｘ_ａＨ(Ｗ)
Ｐｒｏｘｙ署名鍵ｓｋｐは、次のようになる（図７参照）。
【００３９】
ｓｋｐ=(ｘ_Ｂ,Ｙ_ａ,Ｙ_Ｂ||ｗ,Ｓ_ｗ)
ｐｒｏｘｙ署名生成工程では、
このｓｋｐを用いて署名者Ｂは、メッセージｍに対するｐｒｏｘｙ署名ＰＳ(ｓｋｐ,ｍ)
をＭ=01||Ｙａ||ｍに対する署名として次のようにして生成する（図８の「ｐｒｏｘｙ署
名生成」参照）。
【００４０】
Ｓ_ｓｋｐ=ｘＢＨ(Ｍ)+ ψ(Ｓ_ｗ)
署名検証工程では、
ｅ(Ｓｓｋｐ,Ｑ)=ｅ(Ｈ(Ｍ), ψ(Ｙ_Ｂ))、ｅ(Ｐ,Ｓｓｋｐ)=ｅ(Ｙ_ａ, ψ(Ｈ(Ｍ)))であ
るか、又はこれと等価な関係式が成立するかどうかを検査し、成立する場合は、署名は正
当なものと判断し、成立しない場合は、署名は正しくないと判断する（図８の「ｐｒｏｘ
ｙ署名検証」参照）。
【図面の簡単な説明】
【００４１】
【図１】第１の実施形態に係る暗号・署名生成を同時に行うためのシステム構成を示す模式図。
【図２】署名生成及び署名検証の流れを示したフローチャート。
【図３】暗号と署名の生成を同時に行う流れを示したフローチャート。
【図４】署名の復号及び署名の検証を行う流れを示したフローチャート。
【図５】第２の実施形態に係る暗号・署名生成を同時に行うためのシステム構成を示す模式図。
【図６】署名生成及び署名検証の流れを示したフローチャート。
【図７】第３の実施形態におけるＰｒｏｘｙ署名鍵の生成の流れを示すフローチャート。
【図８】Ｐｒｏｘｙ署名の生成及び検証の流れを示したフローチャート。
【符号の説明】
【００４２】
１０１…センター，１，２，３…署名装置
【図１】
2008219708.tif 000003
【図２】
2008219708.tif 000004
【図３】
2008219708.tif 000005
【図４】
2008219708.tif 000006
【図５】
2008219708.tif 000007
【図６】
2008219708.tif 000008
【図７】
2008219708.tif 000009
【図８】
2008219708.tif 000010