特許ウォッチ

公開番号2025146115
公報種別公開特許公報(A)
公開日2025-10-03
出願番号2024046726
出願日2024-03-22
発明の名称電子署名システム、方法及びプログラム
出願人NTT株式会社,国立大学法人東京大学
代理人弁理士法人ITOH,個人,個人,個人
主分類G09C 1/00 20060101AFI20250926BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】データサイズと計算コストとを抑えた同種写像に基づく電子署名を実現すること。
【解決手段】電子署名システムは、セキュリティパラメータλから決定される整数a及びbと、素数p=2^a3^bf-1(ただし、fは整数)と、有限体F_p^2上の所定の楕円曲線E₀と、前記楕円曲線E₀に対応する極大整環O₀とをシステムパラメータとする同種写像暗号を利用した電子署名を実現する電子署名システムであって、前記楕円曲線E₀の2^a3^bのねじれ部分群E₀[2^a3^b]の基底P₀,Q₀を選択し、前記素数pに応じた素数Nをランダムに選択し、ランダムなN-同種写像τ:E₀→E_Aの点像τ(P₀),τ(Q₀)及び値域E_Aと、前記同種写像τに対応するイデアルI_τとを求めることにより、電子署名を作成するための秘密鍵sk=(τ,τ(P₀),τ(Q₀),I_τ,N)と、前記電子署名を検証するための検証鍵vk=E_Aとを生成する鍵生成部、を有する。
【選択図】図4
特許請求の範囲【請求項１】
セキュリティパラメータλから決定される整数ａ及びｂと、素数ｐ＝２
ａ
３
ｂ
ｆ－１（ただし、ｆは整数）と、有限体Ｆ
ｐ＾２
上の所定の楕円曲線Ｅ
０
と、前記楕円曲線Ｅ
０
に対応する極大整環Ｏ
０
とをシステムパラメータとする同種写像暗号を利用した電子署名を実現する電子署名システムであって、
前記楕円曲線Ｅ
０
の２
ａ
３
ｂ
のねじれ部分群Ｅ
０
［２
ａ
３
ｂ
］の基底Ｐ
０
，Ｑ
０
を選択し、前記素数ｐに応じた素数Ｎをランダムに選択し、ランダムなＮ－同種写像τ：Ｅ
０
→Ｅ
Ａ
の点像τ（Ｐ
０
），τ（Ｑ
０
）及び値域Ｅ
Ａ
と、前記同種写像τに対応するイデアルＩ
τ
とを求めることにより、電子署名を作成するための秘密鍵ｓｋ＝（τ，τ（Ｐ
０
），τ（Ｑ
０
），Ｉ
τ
，Ｎ）と、前記電子署名を検証するための検証鍵ｖｋ＝Ｅ
Ａ
とを生成する鍵生成部、
を有する電子署名システム。
続きを表示（約 2,600 文字）【請求項２】
ランダムな３
２ｂ
－同種写像ψ：Ｅ
０
→Ｅ
１
に対応するイデアルＩ
ψ
と、ハッシュ値Ｈ（ｍ，ｊ（Ｅ
１
））（ただし、ｍは電子文書、ｊ（Ｅ
１
）は楕円曲線Ｅ
１
のｊ－不変量）から一意に定まる３
ｂ
－同種写像φ：Ｅ
１
→Ｅ
２
に対応するイデアルＩ
φ
とを求め、前記イデアルＩ
τ
の共役と前記イデアルＩ
ψ
と前記イデアルＩ
φ
との積を表すイデアルＩと同値なイデアルＪをランダムに選択し、前記イデアルＪに対応する同種写像σ：Ｅ
Ａ
→Ｅ
２
と、楕円曲線Ｅ
２
の２
ａ
のねじれ部分群Ｅ
２
［２
ａ
］の基底Ｐ，Ｑとを選択し、ランダムな２
ａ
－ｑ（ただし、ｑ＝ｄｅｇσ）次の同種写像ωの点像ω（＾σ（Ｐ）），ω（＾σ（Ｑ））（ただし、＾σは同種写像σの双対同種写像）及び値域Ｆを求めることにより、署名ｓｉｇ＝（ｑ，ω（＾σ（Ｐ）），ω（＾σ（Ｑ）），Ｆ，Ｅ
１
）を作成する署名作成部、
を有する請求項１に記載の電子署名システム。
【請求項３】
前記同種写像ωの点像ω（＾σ（Ｐ）），ω（＾σ（Ｑ））から２次元の同種写像計算によりｑ－同種写像σを求め、前記同種写像σがＥ
Ａ
からＥ
２
への同種写像であるか否かを確認することにより、前記同種写像σがＥ
Ａ
からＥ
２
への同種写像である場合は検証成功、前記同種写像σがＥ
Ａ
からＥ
２
への同種写像でない場合は検証失敗を示す情報を出力する署名検証部、
を有する請求項２に記載の電子署名システム。
【請求項４】
前記署名作成部は、
ＲａｎｄＩｓｏｇＩｍａｇｅｓを一般化したアルゴリズムにより、前記同種写像ωの点像ω（＾σ（Ｐ）），ω（＾σ（Ｑ））及び値域Ｆを求める、請求項２又は３に記載の電子署名システム。
【請求項５】
セキュリティパラメータλから決定される整数ａ及びｂと、素数ｐ＝２
ａ
３
ｂ
ｆ－１（ただし、ｆは整数）と、有限体Ｆ
ｐ＾２
上の所定の楕円曲線Ｅ
０
と、前記楕円曲線Ｅ
０
に対応する極大整環Ｏ
０
とをシステムパラメータとする同種写像暗号を利用した電子署名を実現する電子署名システムに用いられる方法であって、
前記電子署名の作成者となる第１の装置が、
前記楕円曲線Ｅ
０
の２
ａ
３
ｂ
のねじれ部分群Ｅ
０
［２
ａ
３
ｂ
］の基底Ｐ
０
，Ｑ
０
を選択し、前記素数ｐに応じた素数Ｎをランダムに選択し、ランダムなＮ－同種写像τ：Ｅ
０
→Ｅ
Ａ
の点像τ（Ｐ
０
），τ（Ｑ
０
）及び値域Ｅ
Ａ
と、前記同種写像τに対応するイデアルＩ
τ
とを求めることにより、電子署名を作成するための秘密鍵ｓｋ＝（τ，τ（Ｐ
０
），τ（Ｑ
０
），Ｉ
τ
，Ｎ）と、前記電子署名を検証するための検証鍵ｖｋ＝Ｅ
Ａ
とを生成する鍵生成手順、
を実行する方法。
【請求項６】
前記電子署名の検証者となる第２の装置が、
ランダムな３
２ｂ
－同種写像ψ：Ｅ
０
→Ｅ
１
に対応するイデアルＩ
ψ
と、ハッシュ値Ｈ（ｍ，ｊ（Ｅ
１
））（ただし、ｍは電子文書、ｊ（Ｅ
１
）は楕円曲線Ｅ
１
のｊ－不変量）から一意に定まる３
ｂ
－同種写像φ：Ｅ
１
→Ｅ
２
に対応するイデアルＩ
φ
とを求め、前記イデアルＩ
τ
の共役と前記イデアルＩ
ψ
と前記イデアルＩ
φ
との積を表すイデアルＩと同値なイデアルＪをランダムに選択し、前記イデアルＪに対応する同種写像σ：Ｅ
Ａ
→Ｅ
２
と、楕円曲線Ｅ
２
の２
ａ
のねじれ部分群Ｅ
２
［２
ａ
］の基底Ｐ，Ｑとを選択し、ランダムな２
ａ
－ｑ（ただし、ｑ＝ｄｅｇσ）次の同種写像ωの点像ω（＾σ（Ｐ）），ω（＾σ（Ｑ））（ただし、＾σは同種写像σの双対同種写像）及び値域Ｆを求めることにより、署名ｓｉｇ＝（ｑ，ω（＾σ（Ｐ）），ω（＾σ（Ｑ）），Ｆ，Ｅ
１
）を作成する署名作成手順、
を実行する請求項５に記載の方法。
【請求項７】
前記第１の装置が、
前記同種写像ωの点像ω（＾σ（Ｐ）），ω（＾σ（Ｑ））から２次元の同種写像計算によりｑ－同種写像σを求め、前記同種写像σがＥ
Ａ
からＥ
２
への同種写像であるか否かを確認することにより、前記同種写像σがＥ
Ａ
からＥ
２
への同種写像である場合は検証成功、前記同種写像σがＥ
Ａ
からＥ
２
への同種写像でない場合は検証失敗を示す情報を出力する署名検証部、
を実行する請求項６に記載の方法。
【請求項８】
コンピュータに、請求項５乃至７の何れか一項に記載の方法を実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、電子署名システム、方法及びプログラムに関する。
続きを表示（約 1,700 文字）【背景技術】
【０００２】
耐量子性を持つと考えられる暗号方式は耐量子計算機暗号等と呼ばれる。耐量子計算機暗号の候補の一つとして、同種写像暗号が知られている。同種写像に基づく電子署名の中でも代表的なものとしては、ＳｅａＳｉｇｎ、ＳＱＩＳｉｇｎ等がある。特に、ＳＱＩＳｉｇｎは、秘密鍵、検証鍵、署名のデータサイズがいずれも他の方式と比べて小さいため注目されている。
【０００３】
また、近年、ＳＩＤＨへの攻撃で用いられた高次元の同種写像を利用した新たな方式が多数提案されている。その中でもＳＱＩｓｉｇｎＨＤ（非特許文献１）は、ＳＱＩｓｉｇｎよりも更に短い署名長を持つことで注目されている。
【先行技術文献】
【非特許文献】
【０００４】
Pierrick Dartois, Antonin Leroux, Damien Robert, BenjaminWesolowski. "SQIsignHD: New Dimensions in Cryptography." Cryptology ePrint Archive. https://eprint.iacr.org/2023/436. (2023).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＳＱＩｓｉｇｎＨＤはデータサイズが小さい一方で、署名検証の際に４次元の同種写像を計算する必要があるため、多くの計算時間を要するという課題がある。
【０００６】
本開示は、上記の点に鑑みてなされたもので、データサイズと計算コストとを抑えた同種写像に基づく電子署名を実現することを目的とする。
【課題を解決するための手段】
【０００７】
本開示の一態様による電子署名システムは、セキュリティパラメータλから決定される整数ａ及びｂと、素数ｐ＝２
ａ
３
ｂ
ｆ－１（ただし、ｆは整数）と、有限体Ｆ
ｐ＾２
上の所定の楕円曲線Ｅ
０
と、前記楕円曲線Ｅ
０
に対応する極大整環Ｏ
０
とをシステムパラメータとする同種写像暗号を利用した電子署名を実現する電子署名システムであって、前記楕円曲線Ｅ
０
の２
ａ
３
ｂ
のねじれ部分群Ｅ
０
［２
ａ
３
ｂ
］の基底Ｐ
０
，Ｑ
０
を選択し、前記素数ｐに応じた素数Ｎをランダムに選択し、ランダムなＮ－同種写像τ：Ｅ
０
→Ｅ
Ａ
の点像τ（Ｐ
０
），τ（Ｑ
０
）及び値域Ｅ
Ａ
と、前記同種写像τに対応するイデアルＩ
τ
とを求めることにより、電子署名を作成するための秘密鍵ｓｋ＝（τ，τ（Ｐ
０
），τ（Ｑ
０
），Ｉ
τ
，Ｎ）と、前記電子署名を検証するための検証鍵ｖｋ＝Ｅ
Ａ
とを生成する鍵生成部、を有する。
【発明の効果】
【０００８】
データサイズと計算コストとを抑えた同種写像に基づく電子署名を実現することができる。
【図面の簡単な説明】
【０００９】
本実施形態に係る電子署名システムの全体構成の一例を示す図である。
本実施形態に係る署名者装置の機能構成の一例を示す図である。
本実施形態に係る検証者装置の機能構成の一例を示す図である。
本実施形態に係る署名作成・検証処理の一例を示すシーケンス図である。
コンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の一実施形態について、図面を参照しながら詳細に説明する。
（【００１１】以降は省略されています）

関連特許