修士論文 要旨

同種写像暗号 CSIDH の Edwards 曲線による構成と超特異曲線の信頼できる生成法
数理情報学専攻 48186207

守谷 共起

指導教員

高木 剛 教授

Montgomery 型と呼ばれる楕円曲線（Montgomery 曲1 はじめに線）の性質を使い，効率的な作用計算を実現している．

公開鍵暗号は通信の安全を保証する技術であり，現一方で，楕円曲線には Montgomery 曲線以外の型の在のインターネット社会において欠かすことのできな曲線が知られている．これは，楕円曲線暗号の効率化い技術となっている．公開鍵暗号としては，RSA 暗号や安全性の向上という目的で考えられてきたものであ[13] と，楕円曲線暗号 [10, 7] が広く使われている．とる．こうした Montgomery 曲線以外の曲線において，ころが，この二つの暗号方式には，量子コンピュータにCSIDH のアルゴリズムを実行する方法は知られていよって多項式時間で破られるという問題がある [14]．そない．のため，量子コンピュータに耐性のある公開鍵暗号（耐2.2

研究成果

量子暗号）の開発が急務の課題となっている．これに際

本研究では，Edwards 曲線と呼ばれる楕円曲線の上して，アメリカ国立標準技術研究所 (NIST) は 2016 年

で CSIDH を動かすアルゴリズムを提案した．アルゴに耐量子暗号の標準化に向けて公募を宣言した [11]．

リズムを実現するために，Edwards 曲線に関する新し同種写像暗号は楕円曲線暗号をある意味で拡張したい定理を 4 つ証明した．

暗号方式であり，耐量子暗号の候補として考えられてまた，提案アルゴリズムと従来の CSIDH のアルゴリいる．事実，同種写像暗号の鍵共有プロトコルであるズムの計算回数を，理論と実験両方で比較した．提案ア

SIDH をカプセル化した SIKE[1] は，NIST の耐量子暗ルゴリズムは，理論的にも実験的にも，従来のものと比号の候補として残っている．同種写像暗号は同種写像較して僅かながら高速なアルゴリズムとなった．

問題と呼ばれる数学問題の計算量的困難性に安全性の根拠を置いている．
本研究 では ，Montgomery 曲線上での み考 え ら れ

3 超特異楕円曲線の信頼できる生成法
3.1

研究背景ていた同種写像暗号の鍵共有プロトコル CSIDH を，同種写像暗号は，超特異楕円曲線と呼ばれる特殊な楕Edwards 曲線上のアルゴリズムに拡張した．また，同円曲線を使って計算を行うように設計されている．と

種写像暗号において用いられる超特異楕円曲線の信頼ころが，超特異楕円曲線には信頼できる生成が困難であできる生成法について提案を行った．

るという問題がある．

2 CSIDH の Edwards 曲線を用いた構成
2.1 研究背景

超特異楕円曲線は楕円曲線全体と比較すると，指数関数的に数が少なく，ランダムな楕円曲線は現実的なスケールでは超特異楕円曲線にはなり得ない．既に超特CSIDH[2] は有限可換群の超特異楕円曲線の同型類の異楕円曲線だと知られている特殊な楕円曲線も存在し集合への作用 [15] に基づいた同種写像暗号の鍵共有方ているが，これらの特殊な楕円曲線を使ったプロトコ式である．群作用における次の図式を作ることで鍵共ルは脆弱性があることがわかっている．したがって，脆有を実現する．

弱性のないような超特異楕円曲線を生成する手法が求[a]E/ [a] ∗ Eめられている．そうした方法の一つとして，CGL ハッシュ関数 [4] を用いてランダムな超特異楕円曲線を生成するという方法がある．ところが，この方法では特定の[b][b] ∗ E[b][a]/ [a][b] ∗ E[b][a] ∗ E

一般の楕円曲線については，この群作用の計算を効率的に行うのは困難である．CSIDH においては，人物のみが同種写像の情報を知ることができるという問題点があり，この手法で生成される超特異楕円曲線は信頼できる楕円曲線にはならない．信頼できる生成法として考えられるものに G-SIDH[6] がある．これはグ同種写像暗号 CSIDH の Edwards 曲線による構成と超特異曲線の信頼できる生成法 (守谷 共起)

ループ鍵共有方式であり，複数人の秘密鍵を合わせることで超特異楕円曲線が生成できるため，特定の人物が4 今後の課題多くの情報を得ることができない．ところが，G-SIDH

一つ目の研究では，単純な CSIDH のアルゴリズムをにも問題がある．G-SIDH は p のビット長を生成に関Edwards 曲線を用いたアルゴリズムに拡張した．一方

わる人数に比例したものを取る必要があるため，効率的で，CSIDH は秘密鍵によって計算時間が異なるため，な生成法にはならない．信頼できる方法で脆弱性のなアルゴリズムの実行時間を計測することで秘密鍵の情

い超特異楕円曲線を効率的に生成することは，同種写像報が漏れてしまう．そのため，定時間の CSIDH のアル全体にかかわる重要な課題であるが，有用な解決法につゴリズムを考えることは重要な課題である．現在知らいては提案がなされていない．

れている定時間アルゴリズムを Edwards 曲線に拡張す

3.2 研究成果：G-CSIDHることが今後の課題である．

初めに，CSIDH を複数人の鍵共有方式 G-CSIDH

また，最近，Hessian 曲線の同種写像の計算公式が新に拡張した．以下でプロトコルを述べる．パーティ

たに提案された [5, 8]．この曲線の上で CSIDH アルゴ

U1 , . . . , Uu が共通の超特異楕円曲線を生成しようとしリズムを動かす手法は発見されていない．この曲線にている．

CSIDH アルゴリズムを拡張することも今後の課題でセットアップ:
鍵生成:ある．

CSIDH と同じ設定とする．

二つ目の研究では，情報を分散させることで信頼できパーティ Uj の秘密鍵を [aj ] とする．

ステップ 1: Uj は [aj ] の E0 への作用を計算し，超特異楕円曲線 EA(j) = [aj ] ∗ E0 を得る．Uj1はこの曲線を Uj+1 に送る．
ステップ k (2 ≤ k ≤ u − 1):

Ujは[aj ]のEA(j−1) への作用を計算し，超特異楕円曲線る超特異楕円曲線を生成する手法を提案した．一方で，現実的な要求を考慮に入れると，純粋に超特異楕円曲線をランダムに生成する方が望ましい．このような手法は現在発見されておらず，このような手法の提案も今後の課題である．

k−1

EA(j) , = [aj ] ∗ EA(j−1) を得る．Uj はこの曲
kk−1

線を Uj+1 に送る．
鍵共有:

Uj は [aj ] の EA(j−1) への作用を計算し，超u−1

特異楕円曲線 EA(j) = [aj ] ∗ EA(j−1) を得る．この
u−1曲線を共有鍵とする．
このプロトコルにより，U1 , . . . , Uu は [a1 ] · · · [au ] ∗ E0を共有する．
さらに，G-CSIDH の安全性が CSSDDH 仮定に帰着されることを証明した．CSSDDH 仮定は，CSIDH の安全性を保証する仮定である．

3.3 研究成果：信頼できる超特異楕円曲線の生成法
秘密分散のアイディアを利用し，信頼できる超特異楕円曲線の生成法の定義を行った．具体的には，超特異楕円曲線の生成に関わった u 人のうち u − 1 人が共謀しても超特異楕円曲線の情報が割れないとき，この生成法を信頼できる生成法と呼ぶ．
この定義の下で，G-CSIDH が安全ならば，G-CSIDHが信頼できる超特異楕円曲線の生成法になっていることを証明した．

参考文献[1] Reza Azarderakhsh, Matthew Campagna, Craig Costello, LD Feo, BasilHess, A Jalali, D Jao, B Koziel, B LaMacchia, P Longa, et al. Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum
Standardization project, 2017.
[2] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, andJoost Renes. CSIDH: an efficient post-quantum commutative groupaction. In International Conference on the Theory and Application of Cryptologyand Information Security–ASIACRYPT 2018, pages 395–427. Springer, 2018.
[3] Daniel Cervantes-Vázquez,Mathilde Chenu,Jesús-Javier ChiDomı́nguez, Luca De Feo, Francisco Rodrı́guez-Henrı́quez, and Benjamin Smith. Stronger and faster side-channel protections for csidh.
In International Conference on Cryptology and Information Security in Latin
America–LATINCRYPT 2019, pages 173–193. Springer, 2019.
[4] Denis X Charles, Kristin E Lauter, and Eyal Z Goren. Cryptographic
hash functions from expander graphs. Journal of Cryptology, 22(1):93–113, 2009.
[5] Thinh Dang and Dustin Moody. Twisted hessian isogenies. IACR Cryptology ePrint Archive, 2019:1003, 2019. https://ia.cr/2019/1003.
[6] Satoshi Furukawa, Noboru Kunihiro, and Katsuyuki Takashima. Multiparty key exchange protocols from supersingular isogenies. In International Symposium on Information Theory and Its Applications–ISITA 2018, pages
208–212. IEEE, 2018.
[7] Neal Koblitz. Elliptic curve cryptosystems. Mathematics of computation,
pages 203–209, 1987.
[8] Perez Broon Fouazou Lontouo and Emmanuel Fouotsa. Analogue ofVélu’s formulas for computing isogenies over Hessian model of ellipticcurves.
[9] Michael Meyer, Fabio Campos, and Steffen Reith. On Lions and Elligators: An efficient constant-time implementation of CSIDH. In International Conference on Post–Quantum Cryptography–PQCrypto 2018, pages
307–325. Springer, 2019.
[10] Victor S Miller. Use of elliptic curves in cryptography. In Conference
on the theory and application of cryptographic techniques–CRYPTO 1985, pages
417–426. Springer, 1985.
[11] National Institute of Standards and Technology. Post–quantum cryptography standardization, December 2016. https://csrc.nist.gov/Projects/
Post-Quantum- Cryptography/Post- Quantum- Cryptography- Standardization.
[12] Hiroshi Onuki, Yusuke Aikawa, Tsutomu Yamazaki, and Tsuyoshi Takagi. A Faster Constant-time Algorithm of CSIDH keeping Two Points.
In Advances in Information and Computer Security–IWSEC 2019, pages 23–33.
Springer, 2019.
[13] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for
obtaining digital signatures and public-key cryptosystems. Communications of the ACM, pages 120–126, 1978.
[14] Peter W Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th annual symposium on foundationsof computer science, pages 124–134. Ieee, 1994.
[15] William C Waterhouse. Abelian varieties over finite fields. In Annales
scientifiques de l’École Normale Supérieure, pages 521–560, 1969.