特許ウォッチ

公開番号2025146106
公報種別公開特許公報(A)
公開日2025-10-03
出願番号2024046712
出願日2024-03-22
発明の名称通信システム、方法及びプログラム
出願人NTT株式会社,国立大学法人東京大学
代理人弁理士法人ITOH,個人,個人,個人
主分類G09C 1/00 20060101AFI20250926BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】データサイズと計算コストを抑えた同種写像に基づく公開鍵暗号を実現すること。
【解決手段】通信システムは、セキュリティパラメータλから決定される整数a'及びb'と、2^2λより大きく、かつ、平滑数でない整数d_A=2^a'+k・3^b'及びd₁=2^a'-k・3^b'(kは自然数)と、整数a=2a'、b=2b'、d₂=3^bと、素数p=2^a・3f-1(fは自然数)と、E₀[2^a]の生成元P₀、Q₀とをシステムパラメータとする同種写像暗号を利用した暗号化通信を実現する通信システムであって、Z/2aZ上のランダムな2×2の正則な対角行列Aを選択し、d_AとP₀、Q₀からRandIsogImagesによりd_A-同種写像φ_A:E₀→E_AとP_A=φ_A(P₀)とQ_A=φ_A(Q₀)を生成することにより、公開鍵pk=(E_A,R_A,S_A)(ただし、R_A及びS_Aは、(R_A,S_A)^Τ=A(P_A,Q_A)^Τを満たす値)と、秘密鍵sk=Aとを生成する鍵生成部、を有する。
【選択図】図8
特許請求の範囲【請求項１】
セキュリティパラメータλから決定される整数ａ'及びｂ'と、２
２λ
より大きく、かつ、平滑数でない整数ｄ
Ａ
＝２
ａ'
＋ｋ・３
ｂ'
及びｄ
１
＝２
ａ'
－ｋ・３
ｂ'
（ただし、ｋは自然数）と、整数ａ＝２ａ'、ｂ＝２ｂ'、ｄ
２
＝３
ｂ
と、素数ｐ＝２
ａ
・３ｆ－１（ただし、ｆは自然数）と、有限体Ｆ
ｐ＾２
上の所定の楕円曲線Ｅ
０
のねじれ部分群Ｅ
０
［２
ａ
］の生成元Ｐ
０
、Ｑ
０
とをシステムパラメータとする同種写像暗号を利用した暗号化通信を実現する通信システムであって、
Ｚ／２ａＺ上のランダムな２×２の正則な対角行列Ａを選択し、ｄ
Ａ
とＰ
０
、Ｑ
０
からＲａｎｄＩｓｏｇＩｍａｇｅｓアルゴリズムによりランダムなｄ
Ａ
－同種写像φ
Ａ
：Ｅ
０
→Ｅ
Ａ
とＰ
Ａ
＝φ
Ａ
（Ｐ
０
）とＱ
Ａ
＝φ
Ａ
（Ｑ
０
）を生成することにより、前記暗号化通信の暗号化に用いられる公開鍵ｐｋ＝（Ｅ
Ａ
，Ｒ
Ａ
，Ｓ
Ａ
）（ただし、Ｒ
Ａ
及びＳ
Ａ
は、（Ｒ
Ａ
，Ｓ
Ａ
）
Τ
＝Ａ（Ｐ
Ａ
，Ｑ
Ａ
）
Τ
を満たす値）と、前記公開鍵ｐｋにより暗号化された暗号文の復号に用いられる秘密鍵ｓｋ＝Ａとを生成する鍵生成部、
を有する通信システム。
続きを表示（約 4,300 文字）【請求項２】
平文ｍと、前記公開鍵ｐｋ＝（Ｅ
Ａ
，Ｒ
Ａ
，Ｓ
Ａ
）とに基づいて、ｓ
Ｂ
＝２ｍ＋１∈（Ｚ／２
ａ
Ｚ）
＊
を選択し、ｄ
１
とＰ
０
、Ｑ
０
から前記ＲａｎｄＩｓｏｇＩｍａｇｅｓアルゴリズムによりランダムなｄ
１
－同種写像φ
１
：Ｅ
０
→Ｅ
１
とＰ
１
＝φ
１
（Ｐ
０
）とＱ
１
＝φ
１
（Ｑ
０
）を生成し、ランダムなｄ
２
－同種写像φ
２
：Ｅ
Ａ
→Ｅ
２
を選択することにより、暗号文ｃｔ＝（Ｅ
１
，Ｒ
１
，Ｓ
１
，Ｅ
２
，Ｒ
２
，Ｓ
２
）（ただし、Ｒ
１
及びＳ
１
は（Ｒ
１
，Ｓ
１
）
Τ
＝Ｂ（Ｐ
１
，Ｑ
１
）
Τ
を満たす値、Ｒ
２
及びＳ
２
は（Ｒ
２
，Ｓ
２
）
Τ
＝Ｂ（φ
２
（Ｒ
Ａ
），φ
２
（Ｓ
Ａ
））
Τ
を満たす値、Ｂは２×２の正則な対角行列Ｂ＝ｄｉａｇ（ｓ
Ｂ
，ｓ
Ｂ
－１
））を生成する暗号化部、
【請求項３】
前記秘密鍵ｓｋ＝Ａと、前記暗号文ｃｔ＝（Ｅ
１
，Ｒ
１
，Ｓ
１
，Ｅ
２
，Ｒ
２
，Ｓ
２
）とに基づいて、ＳＩＤＨ攻撃を実行するアルゴリズムであるＡｔｋ
Ｎ_１,Ｎ_２
（Ｅ
１
，Ｅ
２
，Ｒ
１
，Ｓ
１
，Ｒ
２
'，Ｓ
２
'）（ただし、Ｒ
２
'及びＳ
２
'は（Ｒ
２
'，Ｓ
２
'）
Τ
＝ｋｄ
１
Ａ
－１
（Ｒ
２
，Ｓ
２
）
Τ
を満たす値、Ｎ
１
＝ｄ
Ａ
ｄ
１
、Ｎ
２
＝ｋ
２
ｄ
２
）により（ψ
１
，ψ
２
，Ｅ
Ａ
'）を生成し、Ｂ＝ｄｉａｇ（ｓ
Ｂ
，ｓ
Ｂ
－１
）かつｋ（Ｒ
２
，Ｓ
２
）
Τ
＝Ｂ（ψ
２
（Ｒ
Ａ
），ψ
２
（Ｓ
Ａ
））
Τ
となる２×２の正則な対角行列Ｂを求め、平文ｍ＝（ｓ
Ｂ
－１）／２（ただし、ｓ
Ｂ
＝ｍｉｎ｛ｓ
Ｂ
，２
ａ
－ｓ
Ｂ
｝）を生成する復号部、
を有する請求項２に記載の通信システム。
【請求項４】
前記ＲａｎｄＩｓｏｇＩｍａｇｅｓアルゴリズムは、次数Ｄと、前記楕円曲線Ｅ
０
上の任意の有限個の点の集合Ｘとを入力として、次数Ｄの同種写像τ：Ｅ
０
→Ｅ
Ａ
と、前記同種写像τに関する前記集合Ｘの像τ（Ｘ）とを出力するアルゴリズムである、請求項１乃至３の何れか一項に記載の通信システム。
【請求項５】
セキュリティパラメータλから決定される整数ａ'及びｂ'と、２
２λ
より大きく、かつ、平滑数でない整数ｄ
Ａ
＝２
ａ'
＋ｋ・３
ｂ'
及びｄ
１
＝２
ａ'
－ｋ・３
ｂ'
（ただし、ｋは自然数）と、整数ａ＝２ａ'、ｂ＝２ｂ'、ｄ
２
＝３
ｂ
と、素数ｐ＝２
ａ
・３ｆ－１（ただし、ｆは自然数）と、有限体Ｆ
ｐ＾２
上の所定の楕円曲線Ｅ
０
のねじれ部分群Ｅ
０
［２
ａ
］の生成元Ｐ
０
、Ｑ
０
とをシステムパラメータとする同種写像暗号を利用した暗号化通信を実現する通信システムに用いられる方法であって、
前記暗号化通信の受信者となる第１の装置が、
Ｚ／２ａＺ上のランダムな２×２の正則な対角行列Ａを選択し、ｄ
Ａ
とＰ
０
、Ｑ
０
からＲａｎｄＩｓｏｇＩｍａｇｅｓアルゴリズムによりランダムなｄ
Ａ
－同種写像φ
Ａ
：Ｅ
０
→Ｅ
Ａ
とＰ
Ａ
＝φ
Ａ
（Ｐ
０
）とＱ
Ａ
＝φ
Ａ
（Ｑ
０
）を生成することにより、前記暗号化通信の暗号化に用いられる公開鍵ｐｋ＝（Ｅ
Ａ
，Ｒ
Ａ
，Ｓ
Ａ
）（ただし、Ｒ
Ａ
及びＳ
Ａ
は、（Ｒ
Ａ
，Ｓ
Ａ
）
Τ
＝Ａ（Ｐ
Ａ
，Ｑ
Ａ
）
Τ
を満たす値）と、前記公開鍵ｐｋにより暗号化された暗号文の復号に用いられる秘密鍵ｓｋ＝Ａとを生成する鍵生成手順、
を実行する方法。
【請求項６】
前記暗号化通信の送信者となる第２の装置が、
平文ｍと、前記公開鍵ｐｋ＝（Ｅ
Ａ
，Ｒ
Ａ
，Ｓ
Ａ
）とに基づいて、ｓ
Ｂ
＝２ｍ＋１∈（Ｚ／２
ａ
Ｚ）
＊
を選択し、ｄ
１
とＰ
０
、Ｑ
０
から前記ＲａｎｄＩｓｏｇＩｍａｇｅｓアルゴリズムによりランダムなｄ
１
－同種写像φ
１
：Ｅ
０
→Ｅ
１
とＰ
１
＝φ
１
（Ｐ
０
）とＱ
１
＝φ
１
（Ｑ
０
）を生成し、ランダムなｄ
２
－同種写像φ
２
：Ｅ
Ａ
→Ｅ
２
を選択することにより、暗号文ｃｔ＝（Ｅ
１
，Ｒ
１
，Ｓ
１
，Ｅ
２
，Ｒ
２
，Ｓ
２
）（ただし、Ｒ
１
及びＳ
１
は（Ｒ
１
，Ｓ
１
）
Τ
＝Ｂ（Ｐ
１
，Ｑ
１
）
Τ
を満たす値、Ｒ
２
及びＳ
２
は（Ｒ
２
，Ｓ
２
）
Τ
＝Ｂ（φ
２
（Ｒ
Ａ
），φ
２
（Ｓ
Ａ
））
Τ
を満たす値、Ｂは２×２の正則な対角行列Ｂ＝ｄｉａｇ（ｓ
Ｂ
，ｓ
Ｂ
【請求項７】
前記第１の装置が、
前記秘密鍵ｓｋ＝Ａと、前記暗号文ｃｔ＝（Ｅ
１
，Ｒ
１
，Ｓ
１
，Ｅ
２
，Ｒ
２
，Ｓ
２
）とに基づいて、ＳＩＤＨ攻撃を実行するアルゴリズムであるＡｔｋ
Ｎ_１,Ｎ_２
（Ｅ
１
，Ｅ
２
，Ｒ
１
，Ｓ
１
，Ｒ
２
'，Ｓ
２
'）（ただし、Ｒ
２
'及びＳ
２
'は（Ｒ
２
'，Ｓ
２
'）
Τ
＝ｋｄ
１
Ａ
－１
（Ｒ
２
，Ｓ
２
）
Τ
を満たす値、Ｎ
１
＝ｄ
Ａ
ｄ
１
、Ｎ
２
＝ｋ
２
ｄ
２
）により（ψ
１
，ψ
２
，Ｅ
Ａ
'）を生成し、Ｂ＝ｄｉａｇ（ｓ
Ｂ
，ｓ
Ｂ
－１
）かつｋ（Ｒ
２
，Ｓ
２
）
Τ
＝Ｂ（ψ
２
（Ｒ
Ａ
），ψ
２
（Ｓ
Ａ
））
Τ
となる２×２の正則な対角行列Ｂを求め、平文ｍ＝（ｓ
Ｂ
－１）／２（ただし、ｓ
Ｂ
＝ｍｉｎ｛ｓ
Ｂ
，２
ａ
－ｓ
Ｂ
｝）を生成する復号手順、
を実行する請求項６に記載の方法。
【請求項８】
コンピュータに、請求項５乃至７の何れか一項に記載の方法を実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、通信システム、方法及びプログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
耐量子性を持つと考えられる暗号方式は耐量子計算機暗号等と呼ばれる。耐量子計算機暗号の候補の一つとして、同種写像暗号が知られている。同種写像に基づく公開鍵暗号方式の中でも代表的なものとしては、ＳＩＤＨ、ＳＩＫＥ、ＣＳＩＤＨ等がある。しかしながら、ＳＩＤＨとＳＩＫＥの安全性を破る攻撃手法が発見されたことにより、これらの方式はもはや安全ではなくなった。
【０００３】
ＳＩＤＨとＳＩＫＥの安全性を破る攻撃手法（以下、ＳＩＤＨ攻撃と呼ぶ。）の発見後、ＳＩＤＨ攻撃に耐性を持つＦＥＳＴＡと呼ばれる新たな暗号方式が提案された（非特許文献１）。ＦＥＳＴＡは復号にＳＩＤＨ攻撃を用いた公開鍵暗号方式であり、ＳＩＤＨ攻撃に耐性を持たせている。
【先行技術文献】
【非特許文献】
【０００４】
Andrea Basso, Luciano Maino, and Giacomo Pope. "FESTA: Fast Encryption from Supersingular Torsion Attacks." Cryptology ePrint Archive, 2023. https://eprint.iacr.org/2023/660
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＦＥＳＴＡはＳＩＤＨ攻撃への耐性が予想される一方で、公開鍵や暗号文といったデータのサイズがＳＩＤＨと比較してかなり大きい上、暗号化や復号に要する計算時間も大きいという課題がある。
【０００６】
本開示は、上記の点に鑑みてなされたもので、データサイズと計算コストを抑えた同種写像に基づく公開鍵暗号を実現することを目的とする。
【課題を解決するための手段】
【０００７】
本開示の一態様による通信システムは、セキュリティパラメータλから決定される整数ａ'及びｂ'と、２
２λ
より大きく、かつ、平滑数でない整数ｄ
Ａ
＝２
ａ'
＋ｋ・３
ｂ'
及びｄ
１
＝２
ａ'
－ｋ・３
ｂ'
（ただし、ｋは自然数）と、整数ａ＝２ａ'、ｂ＝２ｂ'、ｄ
２
＝３
ｂ
と、素数ｐ＝２
ａ
・３ｆ－１（ただし、ｆは自然数）と、有限体Ｆ
ｐ＾２
上の所定の楕円曲線Ｅ
０
のねじれ部分群Ｅ
０
［２
ａ
］の生成元Ｐ
０
、Ｑ
０
とをシステムパラメータとする同種写像暗号を利用した暗号化通信を実現する通信システムであって、Ｚ／２ａＺ上のランダムな２×２の正則な対角行列Ａを選択し、ｄ
Ａ
とＰ
０
、Ｑ
０
からＲａｎｄＩｓｏｇＩｍａｇｅｓアルゴリズムによりランダムなｄ
Ａ
－同種写像φ
Ａ
：Ｅ
０
→Ｅ
Ａ
とＰ
Ａ
＝φ
Ａ
（Ｐ
０
）とＱ
Ａ
＝φ
Ａ
（Ｑ
０
）を生成することにより、前記暗号化通信の暗号化に用いられる公開鍵ｐｋ＝（Ｅ
Ａ
，Ｒ
Ａ
，Ｓ
Ａ
）（ただし、Ｒ
Ａ
及びＳ
Ａ
は、（Ｒ
Ａ
，Ｓ
Ａ
）
Τ
＝Ａ（Ｐ
Ａ
，Ｑ
Ａ
）
Τ
を満たす値）と、前記公開鍵ｐｋにより暗号化された暗号文の復号に用いられる秘密鍵ｓｋ＝Ａとを生成する鍵生成部、を有する。
【発明の効果】
【０００８】
データサイズと計算コストを抑えた同種写像に基づく公開鍵暗号を実現することができる。
【図面の簡単な説明】
【０００９】
同種写像の可換図式の一例を示す図である。
ＦＥＳＴＡにおける楕円曲線と同種写像との関係の一例を示す図である。
ＦｕｌｌＲｅｐＩｎｔで得られた自己準同型とＳＩＤＨ攻撃で得られた同種写像との関係の一例を示す図である。
提案手法における楕円曲線と同種写像との関係の一例を示す図である。
本実施形態に係る暗号化通信システムの全体構成の一例を示す図である。
本実施形態に係る受信者装置の機能構成の一例を示す図である。
本実施形態に係る送信者装置の機能構成の一例を示す図である。
本実施形態に係る暗号化通信処理の一例を示すシーケンス図である。
コンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本発明の一実施形態について、図面を参照しながら詳細に説明する。
（【００１１】以降は省略されています）

関連特許