特許ウォッチ

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

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

関連特許