楕円曲線の理論的及び実用的可能性 ―楕円曲線暗号から耐量子暗号まで―

全文

(1)楕円曲線の理論的及び実用的可能性 —楕円曲線暗号から耐量子暗号まで—. Theoretical and Practical Possibilities of Elliptic Curves. : From Elliptic Curve Cryptosystems to Post-Quantum Cryptosystems. 宮地充子 Atsuko MIYAJI. アブストラクト 1985 年に Miller と Koblitz は独立に公開鍵暗号の一種である楕円曲線暗号を提案した．楕円曲線暗号は楕円曲線が加法群になることを利用した暗号である．その後，楕円曲線は，楕円曲線上に存在する双線形写像を応用することで，はじめて ID ベース暗号を実現した．さらには，近年，楕円曲線上に存在する同種写像を用いた耐量子暗号も提案されている．まさに，暗号の各種問題を解決する数学の宝箱ともいえる．楕円曲線の活用はこのような情報セキュリティにおける理論的なブレークスルーのみにとどまらない．楕円曲線の魅力は高い実用性にある．ブロックチェーンの正しさの検証には楕円曲線上の署名方式 ECDSA が利用されるが，これはその短い署名サイズが理由である．更に，楕円曲線は耐量子暗号の一つである同種写像暗号を実現する．このような背景のもと，楕円曲線に基づく各種暗号の国際標準化も進められている．本稿では，楕円曲線の暗号理論における各種ブレークスルーについて紹介するとともに，国際標準化動向について紹介する．キーワード. 楕円曲線暗号，楕円曲線上の離散対数問題，同種写像暗号，標準化. Abstract In 1985, Miller and Koblitz independently introduced elliptic curve cryptosystems, a type of public key cryptosystem. Elliptic curve cryptosystems use the fact that elliptic curves become a group to realize an ID-based cryptosystem for the first time, by applying a bilinear map on an elliptic curve. Furthermore, in recent years, isogenies on elliptic curves have been used to realize post-quantum cryptosystems. Elliptic curves are indeed treasures for solving various cryptographic problems. Elliptic curves have been applied to resolve many theoretical problems and are merely a theoretical breakthrough. The charm of elliptic curves is that they are highly practical. To verify the correctness of a blockchain, the elliptic curve DSA signature (ECDSA) is used, since the signature size of ECDSA is very short. Furthermore, the elliptic curve realizes a post-quantum cryptosystem. In this paper, we discuss various breakthroughs achieved by using elliptic curves as well as international standardization related to elliptic curves. Key words elliptic curve cryptosystems, ECDLP, Iosgeny cryptosystems, standardization. ンパクトに実現できる．特に，現在広く用いられている RSA 暗. 1. はじめに. 号と比較して，1/10 以下の鍵サイズで同じ安全性を実現できる楕円曲線暗号は，IoT 機器の普及に伴い，ますますコンパクト. （2） 1985 年に楕円曲線に基づく公開鍵暗号が発表された（1），．. な暗号機能の装備が必須となるだろう．このときに，その役割. この公開鍵暗号は楕円曲線上の離散対数問題 (ECDLP) の難. は非常に大きい．IoT 向けに高速に楕円曲線暗号を実現するた. しさを安全性の根拠にする暗号である．一般に楕円曲線暗号と. めの研究が数多くなされている（3）．. は，ECDLP に基づく公開鍵暗号を指す．ECDLP は有限体上. 一方，現在広く用いられている RSA 暗号や楕円曲線暗号など. の離散対数問題 (DLP) に対する強力な解法である「指数計算法. の公開鍵暗号は，量子計算機が実現すると，解読される．そこ. (index calculus)」が直接適用できないことから，有望な公開鍵. で近年，耐量子暗号と呼ばれる量子計算機を用いた攻撃に強力. 暗号として盛んに研究されるようになった．このようにして整. な暗号の研究が盛んに行われている．現在，米国標準技術研究. 数論の長年の研究テーマの一つであった代数曲線が暗号分野に. 所 NIST は耐量子暗号の標準化に向けた取り組みを行っており，. 応用されるようになった．楕円曲線暗号は必要な安全性を小さ. 候補の一つである SIDH（4）は超特異楕円曲線間の同種写像を用. な鍵サイズで実現できるため，有限体上の暗号より高速かつコ. いて鍵共有を実現する．SIDH をはじめとする楕円曲線間の同種. 宮地充子正員大阪大学大学院工学研究科 E-mail miyaji@comm.eng.osaka-u.ac.jp 宮地充子正員北陸先端科学技術大学院大学 E-mail miyaji@jaist.ac.jp Atsuko Miyaji, Member (Graduate School of Engineering, Osaka University), Atsuko Miyaji, Member (Japan Advanced Institute of Science and Technology).. れた CSIDH（5）も同種写像暗号の一つであり，奇数次数の同種. 電子情報通信学会基礎・境界ソサイエティ Fundamentals Review Vol.14 No.4 pp.329–336 2021 年 4 月 c 電子情報通信学会 2021 . を繰り返し適用することで鍵共有を行うため，主にスカラー倍算. 写像を用いた暗号は同種写像暗号と呼ばれる．2018 年に提案さ. IEICE Fundamentals Review Vol.14 No.4. 写像を計算することで鍵共有を実現する．これらの暗号はほかの耐量子暗号に比べて公開鍵長が短いという特長をもつ一方で，実行速度面に課題がある．CSIDH は様々な奇数次数の同種写像と同種写像の計算によって構成される．高速化に関して，同種写. 329.

(2) 像の適用順や適切な組分けに着目することで必要なスカラー倍算の量を削減する研究や（6）∼（8），addition chain の最適化によりスカラー倍算自身を高速化する研究（9），twisted Edwards 曲線を用いることで同種写像のうち係数計算を高速化する研究（6）がある．また，同種写像の計算に必要な楕円曲線の元の個数を削減するというアプローチの研究もある（10）．またサイドチャネル攻撃の耐性をもたせるためにアルゴリズムの constant-time 化を目指す研究も盛んであり，dummy の同種写像の提案や（7），その利用方法の効率化（11），更にはより強い攻撃耐性に関する提案（9）が存在する．本稿では，楕円曲線暗号から同種写像暗号までの基本原理に図1. ついて簡単に述べる．楕円曲線暗号に関して，詳しく知りたい. 楕円曲線上の加算. 読者は文献（12）を，また，楕円曲線について興味をもたれた読者は，文献（13）を読まれることをお薦めする．. 2. 楕円曲線最初に本原稿で利用する記号について説明した後に，楕円曲線について簡単に述べる．. •. K: 体. •. K: 体 K の代数的閉体. •. L ⊂ K: 体 K の拡大体．体 K 上の多項式の根を付加した体. •. Z: 整数で生成される集合．環となる. •. E ，E/K: 楕円曲線，特に，係数が K に含まれるとき， K 上の楕円曲線. •. ように表される．なお，重要なことに二つの楕円曲線 E0 と E1. G, G: 楕円曲線 E の元. •. G, G: G と G で生成される群. •. は j(E0 ) = j(E1 ) となるとき，同型になる．E0 が E1 と同型なとき，E0 ∼ = E1 と表す．j-不変量は Fp の元であることから，. a ⊕ b: ビット列 a, b に対して，ビットごとの排他的論. j-不変量についてそれぞれ乗算や加算などの演算を定義するこ. 理和. とができる．j-不変量の乗算や加算などの演算は，同種写像暗. Z = Z/Z: 正素数に対して，Z のを法とした剰余群. 号で利用する．. •. 図2. 楕円曲線とは，a, b ∈ K に対して，. E/K : y 2 = x3 + ax + b. 楕円曲線の加算の利点は，幾何学的に定義された加算（図 1，. (1). で定まる曲線である．ここで 4a3 + 27b2 = | 0 とし，K の標数は. 5 以上とする．楕円曲線に対する j-不変量は以下で定義される． j(E) = 1728. 4a3. 4a3 ∈ K. − 27b2. 標数が 2 または 3 の場合の楕円曲線の標準形（14）は異なる．楕円. 2）が有理式で書き下せる点である．実際，P1 = | P2 に対して， R = (x3 , y3 ) = P1 + P2 は，以下の式で計算できる．. y3. と考えて，無限遠点 O = (∞, ∞) も E の点と考える．特に，楕. とする．楕円曲線のパラメータ a, b を含む体 K を楕円曲線の定義体と呼ぶ．楕円曲線には O が零元になるような加法が定義できる．楕円曲線上の 2 点 A = (x1 , y1 ) と B = (x2 , y2 ) に対し，A + B を，. A と B を結ぶ直線と楕円曲線とのもう一つの交点の x 軸に対称な点と定義する．K として実数体を用いたとき．加法は図 1 の. (2). P1 = P2 のとき，R = (x3 , y3 ) = 2P1 は，以下の式で計算できる．. x3 =. 円曲線の K-有理点の集合を，. E(K) = {(x, y) ∈ K 2 |y 2 = x3 + ax + b} ∪ {O}. y − y 2 2 1. − x1 − x2 x2 − x1 y2 − y1 = (x1 − x3 ) − y1 x2 − x1. x3 =. 曲線は (1) を満たす点の集合であるが，x → ∞ のとき y → ∞. 330. 楕円曲線上の 2 倍算. y3 =. 3x21 + a 2y1. 2 − 2x1. 3x21 + a (x1 − x3 ) − y1 2y1. (3). 式 (2)，(3) から，楕円曲線の係数に依存するのは，2 倍算のみで加算は依存しないことが分かる．楕円曲線は加法に関して群となるので，位数という概念を考えることが可能となる．ここで，正整数 m ∈ Z に対して，楕円曲線の元で位数 m となる元の集合を以下で定義する．. E[m] = {P ∈ E(K)|mP = O} IEICE Fundamentals Review Vol.14 No.4.

(3) 楕円曲線の場合，m が体の標数と互いに素な場合，. E[m] ∼ = Z/mZ × Z/mZ 体の標数 p に対しては，. E[p] ∼ = Z/pZ or O. は秘密鍵暗号と呼ばれる公開鍵暗号の対の概念の暗号を利用する．このため，現実的な利用においては鍵共有法で十分である．ここでは，具体的に楕円曲線を利用した暗号プロトコルとして楕円曲線上の Diffie-Hellman 鍵共有法 (elliptic curve Diffie. Helman key exchange, ECDH) を説明する．以下 E/K を楕円曲線とし，G ∈ E(K) を位数 (lG = O となる最小の正整数 l) が大きな素数 l の元 (ベースポイント) とする．また E(K). となる．楕円曲線は ordinary 楕円曲線と超特異楕円曲線 (supersin-. gular) に分類できる．ここで，素数 p に対して，K の標数が p となる場合を考える（注 1）．このとき，E の位数が p となる元から生成される群が. 及び G はシステム内で公開する．. • ユーザ A の鍵生成 1. 乱数 xA ∈ Z∗ l を選ぶ． 2. PA = xA G を計算する． 3. xA を秘密鍵，PA を公開鍵として出力する．. E[p] = {P ∈ E(K)|pP = O} = {O} となるとき，E を超特異楕円曲線と定義する．また，超特異曲線でない楕円曲線は ordinary 楕円曲線と呼ばれる．. ユーザ B も同様に鍵 (xB , PB ) を生成する．. • 楕円 DH 鍵共有（ 1 ） A は公開ファイルから B の公開鍵 PB を用いて，E 上で. 3. 楕円曲線暗号. KA,B = xA PB = xA xB G を計算する．. 本章では，楕円曲線暗号の安全性の根拠となる楕円曲線上の離散対数問題について定義したのち，データ秘匿に必要となる. （ 2 ） B は公開ファイルから A の公開鍵 PA を用いて，E 上で. 楕円曲線上の鍵共有法，データの完全性に必要となる楕円曲線上のディジタル署名について説明する．. KB,A = xB PA = xB xA G. 楕円曲線暗号は，有限体 K = GF (q) = Fq (q = pr ,. を計算する．. p : 素数, r : 自然数) 上定義された楕円曲線を用いる．加算は，加算公式 (2), (3) を K 上計算するとよい．この加法に. （ 3 ） A と B は E(K) の元 KA,B = KB,A を鍵として共有する．. より E(K) は有限可換群になり，暗号に重要な離散対数問題. (ECDLP) が定義できる．ここで，ECDLP の定義について述べる．［定義 1］ p を素数，r を自然数，q = pr とし，有限体 Fq 上の楕円曲線 E/Fq ，E(Fq ) G, Y に対して，. Y = xG = G + · · · + G (G の x 回の和). 3. 2 楕円曲線上のディジタル署名楕円曲線を用いた署名方式には幾つかあるが，ここでは基本となる楕円 DSA 署名法 (ECDSA) について紹介する．署名方式では，鍵共有法で定義したシステムパラメータに，更に与. なる x が存在するなら，その x を求めよ．. えられた平文を適当な長さに圧縮するハッシュ関数 h が必要と. 離散対数問題は，任意の有限群とその群演算を用いて定義でき. なる．署名方式では，{E(K), G, l, h} がシステムパラメータと. る．有限体とその乗法に対する離散対数問題が DLP であり，楕. なる．. 円曲線とその加法に対する離散対数問題が ECDLP である．. • ユーザ A の鍵生成 1. 乱数 xA ∈ Z∗ l を選ぶ．. 3. 1 楕円曲線上の鍵共有法公開のネットワークを利用して，2 者間のデータ秘匿を可能とする暗号が公開鍵暗号である．公開鍵暗号とは，暗号化用の. 2. PA = xA G を計算する． 3. xA を秘密鍵，PA を公開鍵として出力する． • 署名生成 A が平文 M に署名を生成する．. 鍵を公開鍵として公開し，対応する復号鍵を秘密鍵として保管. 1. M のハッシュ値 f = h(M ) を計算する．. することで，公開のネットワークを利用して秘匿通信を可能と. 2. 乱数 k に対して，. する．鍵共有法は公開鍵暗号と同様に公開のネットワークを利用して秘匿通信を可能とする．公開鍵暗号がある一定の長さの任意のデータの秘匿が可能であるのに対し，鍵共有法では 2 者間である一定の長さの鍵を共有する方式である．鍵共有法だけではデータの秘匿通信はできないが，一般に，データの暗号化（注 1）：有限体 Fp の標数は p となる．. IEICE Fundamentals Review Vol.14 No.4. R = kG = (rx , ry ), r = rx (mod l), f + rxA s = (mod l) k を計算し，(r, s) を M の署名として出力する．. • 署名検証 331.

(4) 受信者は，平文 M の署名 (r, s) を検証する． ∗ 1. (r, s)

(5) ∈ Z∗ l × Zl のとき，署名を拒絶する．. 2. M のハッシュ値 f = h(M ) を計算する． 3. A の公開鍵 PA に対して， d = s−1. い（注 4）．ここでは，楕円曲線上の双線形写像に限定して話を進める．［定義 2］楕円曲線 E/K が位数の群 E[] を含むとする．ここで，は，体 K の標数と互いに素な素数である．E[] の生成元を E[] = G, G とし，E[] から定義体の拡大体の乗法群 L∗ への Weil-pairing を e とする．このとき，G, G, aG, bG, aG, cG. (mod l),. に対して，e(G, G)abc を求めよ．. R = df G + drPA = (rx , ry ), を計算する．. 4. 2 ID ベース暗号. 4. r = rx (mod l) が成り立つとき，署名を受理する．公開鍵暗号では，ユーザの公開鍵はランダムな点となる．例. 4. 双線形写像に基づく暗号. えば，ECDH で見られるように，楕円曲線を用いた場合には楕円曲線上のランダムな点 PA となる．ID ベース暗号とは，ラン. 楕円曲線暗号は，3. 章で述べたように，有限体上の離散対数問題を用いたプロトコルに対して，有限体の乗法群を楕円曲線の加法群に変換することで自然に構成されている．そういう意味では，プロトコル的には斬新な発想はないといえる．しかしながら，2000 年に楕円曲線の数学的特徴である非退化な双線形（16）写像を暗号プロトコルに応用する提案がされた（15），．双線形. ダムな点ではなく，ユーザの ID を公開鍵に設定することが可能となる暗号方式である．ただし，公開鍵暗号ではユーザが自分で秘密鍵を設定することが可能であったのに対し，秘密鍵はセンターが生成することになる．ここでは，BDHP を用いた ID （16）ベース暗号 (IBE) について説明する（15），．以下，楕円曲線. E/K が体 K の標数と互いに素な素数位数の群 E[] を含む. 写像に基づく暗号プロトコルは，有限体の乗法群からの自然な. とする．E[] の生成元を E[] = G, G とし，E[] から定義体. 拡張ではない初めての方式といえる．これにより，初めての現. の拡大体の乗法群 L∗ への Weil-pairing を e とする．更に任意. 実的な ID ベースプロトコル（注 2）が可能になり，また短い署名長の方式などの様々な応用が提案されている．ここでは，まずそれらの安全性の根拠となる bilinear DH problem について定義し，その後で ID ベース暗号方式について紹介する．. 4. 1 Bilinear Diffie-Hellman Problem 楕円曲線 E/K ，体 K の標数と互いに素である素数をとし，. E(K) を位数の群 E[] を含むとする．E[] の生成元を G, G とする．すなわち，E(K) ∪ E[] = G, G とする．このとき，. E[] から定義体 K の拡大体 L の乗法群 L∗ への Weil-pairing e，. のビット列を G に写像するハッシュ関数 H1 と Zl の元をメッセージ空間に写像するハッシュ関数 H2 を利用する．ここでメッセージ空間を {0, 1}n とする．{E(K), G, G, , e, H1 , H2 } がシステムパラメータとなる．. • センタによるユーザ A の鍵生成 1. 乱数 s0 ∈ Zl に対して，Y = s0 G を計算する． 2. Y をセンタの公開鍵，s0 を秘密鍵として出力する． • ユーザ A の鍵生成 1. ユーザの ID t を用いて iskt = s0 H1 (t) を計算する． 2. iskt をユーザ A の秘密鍵としてユーザに送信する． • メッセージ M の暗号化ユーザの ID t を用いて，メッセージ M を暗号化する．. 1. 乱数 r ∈ Zl を選ぶ．. ∗. e : E[] × E[] −→ L. 2. 受信者のユーザ ID t とメッセージ M を用いて，（注 3）. が定義される. ．e は以下の性質を満たす．. 双線形 (bilinear). ∀Q, R ∈ E[], ∀a, b ∈ Zl に対して， e(aQ, bR) = e(Q, R)ab ．. 非退化 (non-degenerate). e(G, G) = | 1 ∈ L∗ ∗. 上記の性質から e の像 e(E[]) は，L. U = rG1 V = M ⊕ H2 (e(Y, H1 (t))r ) C = [U, V ]. の位数の部分群. となる．以降，便宜上，e の値域を Zl と表す，すなわち，. を計算する．. e : E[] × E[] −→ Z とする．この Weil 対を用いて，bi-. 3. C を M の暗号文として送信する．. linear Diffie-Hellman problem (BDHP) が定義できる．一般的な双線形写像 (bilinear map) を用いた BDHP について文献（15）に書かれているので，興味がある読者は参考にされた. • 暗号文 C の復号秘密鍵 iskt を用いて，暗号文 C = [U, V ] を以下で復号する．. c = e(U, iskt ) = e(G1 , H1 (t))rs0 ,. （注 2）：ユーザの公開鍵にユーザの名前や住所，電話番号，メールアドレスという任意のビット列を利用する方式である．これにより公開鍵暗号方式で必要となる公開鍵証明書が不要になる．（注 3）：Tate-pairing も関数としては同じ性質を満たす．実用上は，Tate-pairing の方が高速に実現できるので，Tate-pairing を用いる．. 332. （注 4）：文献（15）では，楕円曲線上の Weil-pairing, Tate-paring, Ate-pairing を用いた問題を co-BDHP と呼び，一般の群上の双線形写像 (bilinear map) を用いた問題を BDHP と呼ぶ．. IEICE Fundamentals Review Vol.14 No.4.

(6) = e(Y, H1 (t))r ,. •. 同種写像は 0 写像か全射である，つまり，全ての E/K. から E への同種写像 φ は φ(E) = {O} あるいは全射写像. M = V ⊕ H2 (c). φ(E) = E である．. を計算して，メッセージ M を出力する．. •. 楕円曲線 E と E の有限部分群 Φ に対して，以下を満た. す楕円曲線 E と分離的な同種写像 φ が存在する．. . 5. 同種写像暗号近年，量子計算機の研究の進展に伴い，量子計算機に対しても強力な暗号の研究が盛んになっている．実際，楕円曲線を用いる 3. や 4. 章で記載された楕円曲線を用いる方式は，量子計算機では解読可能となる．本章では，楕円曲線上に定義される同種写像を用いた暗号について紹介する．同種写像を用いた耐量子鍵共有法には SIDH と CSIDH の二つがある．本章では簡単にどちらも紹介する．なお，SIDH は 2 人の鍵共有法であるが，これを一般に n 人に拡張した方法も提案されている（17）．本章では代数学に関するある程度の知識が必要になる．代数学について興味がある読者は文献（18）を参考にしてほしい．. φ:E. −→. E. ker φ. =. Φ. (5). ここで，E ∼ = E/Φ が成り立つ．. •. 同種写像 φ に対して，# ker(φ) = degs (φ), ここで，. degs (φ) は deg(φ) の分岐次数である．なお，同種写像については V´ elu の公式により explicitly に求めることが可能であり，文献（19）や文献（20）の pp. 392–393 を参考にされたい．. 5. 2 SIDH 本章では同種写像を用いた鍵共有法の一つである SIDH (su-. 5. 1 同種写像. persingular isogeny Diffie-Hellman)（21）について述べる．ここでは，素数 p 及び q = p2 とし，Fp 上の二次拡大体である Fq. ここでは同種写像に関する定義，及び数学的特徴について述べる．. 上の楕円曲線 E/Fq : y 2 = x3 + ax + b, a, b ∈ Fq を考える．厳密な定義は後ほど与えるが，同種写像問題 (isogeny finding. ［定義 3］（関数体） K 上の楕円曲線を E/K とする．K 上の多項式環 K[X] に対して，. problem) とは，同種な二つの楕円曲線が与えられたときに，その同種写像を見つけることである．楕円曲線が超特異楕円曲線であるときには，量子計算機を用いても，同種写像を効率的に. I(E) = {f ∈ K[X]|f (P ) = 0(∀P ∈ E)}. 見つけるアルゴリズムは現時点では構成されていない．. • システム設定. を E に関するイデアル，. I(E/K) = {f ∈ K[X]|f (P ) = 0(∀P ∈ E)} = I(E)∩K[X]. 素数 p を小さい正整数 f > 0，0 = 2，1 = 3 に対して，. p = f e00 e11 ± 1 かつ e00 ≈ e11 となるようにとる．次に，Fp2 上の超特異楕円曲線 E を #E(Fp2 ) = (p ± 1)2 となるようにラ. を K 上の E に関するイデアルと呼ぶ．［定義 4］（同種写像） K 上の二つの楕円曲線 E/K 及び E /K. e. ンダムに生成する．更に，{Pi , Qi } ∈ E を E[i i ] (i ∈ {0, 1}). に対して，同種写像 (isogeny) φ : E −→ E とは，φ(OE ) =. e のランダムな基底とする．すなわち，E[i i ]. OE となる E から E への morphism である．また，K 上の. システムパラメータは，(p, E, {P0 , Q0 }, {P1 , Q1 }) となる．. . 二つの楕円曲線 E と E に対して，同種写像が存在するとき，. = Pi , Qi である．. • ユーザ A の鍵生成 e. （ 1 ） A は r0 ∈ Z/00 Z に対して，R0 := P0 + [r0 ]Q0 を計. 二つの楕円曲線は互いに同種であるという．［定義 5］（分離，非分離） E/K から E /K への同種写像. (isogeny) φ : E −→ E に対して，それぞれの関数体の写像が自然に定義できる．. 算する．（ 2 ）核が ker(φ0 ) = R0 となる同種写像. φ0 : E −→ E0 ∼ = E/R0 . φ ∗ : K(E) −→ K(E ). を計算する．. f −→ f ◦ φ. （ 3 ） φ0 (P1 ) と φ0 (Q1 ) を求める．. このとき，K(E ) が φ(K(E)) の分離拡大体（注 5）であるとき，φ は分離的であるという．. （ 4 ） A の公開鍵 pk0 と秘密鍵 sk0 は以下となる．. pk0 := (E0 , φ0 (P1 ), φ0 (Q1 )), sk0 := r0. 次に，幾つか重要な同種写像の性質を列挙する．. •. 同種写像は準同型性を満たす．つまり，∀Q, R ∈ E に対. して，以下を満たす．. • ユーザ B の鍵生成 e. （ 1 ） B は r1 ∈ Z/11 Z に対して，R1 := P1 + [r1 ]Q1 を計算する．. φ(Q) + φ(R) = φ(Q + R). (4). （注 5）：体 K の拡大体 L が分離的であるとは，任意の元 L a の最小規約多項. （ 2 ）核が ker(φ1 ) = R1 となる同種写像. φ1 : E −→ E1 ∼ = E/R1 . 式 fa (X) が分離的である，つまり，fa (X) が K 上に重根をもたない．. IEICE Fundamentals Review Vol.14 No.4. 333.

(7) に，P0 + [r0 ]Q0 の生成元 R0 を求める問題を computational. supersingular isogeny (CSSI) 問題という．［定義 8］（SSCDH 問題）素数 p，小さい正整数 f > 0，0 =. 2，1 = 3 に対して p = f e00 e11 ± 1 かつ e00 ≈ e11 とする． #E(Fp2 ) = (p ± 1)2 となる Fp2 上の超特異楕円曲線 E に対 e. して，{Pi , Qi } ∈ E を E[i i ] (i ∈ {0, 1}) のランダムな基 e 底とする．すなわち，E[i i ]. = Pi , Qi である．次に，核が. ker(φ0 ) = P0 + [r0 ]Q0 となる同種写像を φ0 : E −→ E0 と図3. する．次に，核が ker(φ1 ) = P1 + [r1 ]Q1 となる同種写像を. SIDH key exchange. φ1 : E −→ E1 とする．ここで，r0 ∈ Z/e00 Z，r1 ∈ Z/e11 Z を計算する．. とする．超特異楕円曲線 E0 , E1 と φ0 (P1 ), φ0 (Q1 ), φ1 (P0 ),. （ 3 ） φ1 (P0 ) と φ1 (Q0 ) を求める．. φ1 (Q0 ) が与えられたときに，E/P0 + [r0 ]Q0 , P1 + [r1 ]Q1 . （ 4 ） B の公開鍵 pk1 と秘密鍵 sk1 は以下となる．. と同型となる楕円曲線の j-不変量を求める問題を supersingular. pk1 := (E1 , φ1 (P0 ), φ1 (Q0 )), sk1 := r1. computational Diffie-Hellman (SSCDH) 問題という．［定義 9］（SSDDH 問題）素数 p，小さい正整数 f > 0，0 =. 2，1 = 3 に対して p = f e00 e11 ± 1 かつ e00 ≈ e11 とす. • SIDH 鍵共有法. る．Fp2 上の超特異楕円曲線 E を #E(Fp2 ) = (p ± 1)2 に対. ユーザ A は以下を実行する．. e. して，{Pi , Qi } ∈ E を E[i i ] (i ∈ {0, 1}) のランダムな基. （ 1 ） B の公開鍵 pk1 に対して，. e. 底とする．すなわち，E[i i ] = Pi , Qi である．次に，核が. φ0 : E1 −→ E1,0 ker(φ0 ) = φ1 (P0 ) + [r0 ]φ1 (Q0 ) = φ1 (R0 ). ker(φ0 ) = P0 + [r0 ]Q0 となる同種写像を φ0 : E −→ E0 とする．次に，核が ker(φ1 ) = P1 + [r1 ]Q1 となる同種写像を. φ1 : E −→ E1 とする．ここで，r0 ∈ Z/e00 Z，r1 ∈ Z/e11 Z と. となる同種写像 φ0 を計算する．（ 2 ）楕円曲線 E1,0 の j-不変量 K0 = j(E1,0 ) ∈ Fp2 を計算する．. する．次の二つの分布のどちらかから取られたサンプルに対して，どちらの分布から取られた元かを判定する問題を supersingular. decisional DH (SSDDH) 問題という．. ユーザ B は以下を実行する．. •. （ 1 ） A の公開鍵 pk0 に対して，. (E0 , E1 , φ0 (P1 ), φ0 (Q1 ), φ1 (P0 ), φ1 (Q0 ), E0,1 ),. E0,1 ∼ = E/P0 + [r0 ]Q0 , P1 + [r1 ]Q1 ,. φ1 : E0 −→ E0,1 ker(φ1 ) = φ0 (P1 ) + [r1 ]φ0 (Q1 ) = φ0 (R1 ). •. (E0 , E1 , φ0 (P1 ), φ0 (Q1 ), φ1 (P0 ), φ1 (Q0 ), Ex ),. Ex ∼ = E/P0 + [r0 ]Q0 , P1 + [r1 ]Q1 ,. となる同種写像 φ1 を計算する．（ 2 ）楕円曲線 E0,1 の j-不変量 K1 = j(E0,1 ) ∈ Fp2 を計算する．. e. e. ここで r0 と r1 はそれぞれ Z/00 Z と Z/11 Z の元とする．（21）. A と B は互いに同型な楕円曲線を生成し，その j-不変量は一致し，鍵共有が成功する（図 3）．. E1,0 = φ0 (φ1 (E)) ∼ = φ1 (φ0 (E)) = E0,1 ,. ［定理 1］（SIDH の安全性. ） SSDDH 問題が困難であると. いう仮定のもとで，SIDH は安全な鍵共有法となる．. 5. 3 CSIDH. K0 = j(E1,0 ) = j(E0,1 ) = K1 次に，SIDH 鍵共有法が利用する同種写像に基づく幾つかの安全性の定義（21）について記載する． e. ［定義 6］（DSSI 問題）素数 p，素数べき 00 及び Fp2 上の超 e. 特異楕円曲線 E と E0 に対して，E0 と E が 00 -同種であるか決定する問題を decisional supersingular isogeny (DSSI) 問題という．［定義 7］（CSSI 問題）素数 p を小さい正整数 f > 0，0 = 2，. 1 = 3 に対して p = f e00 e11 ± 1 かつ e00 ≈ e11 とする． #E(Fp2 ) = (p ± 1)2 となる Fp2 上の超特異楕円曲線 E に対 e. して，{Pi , Qi } ∈ E を E[i i ] (i ∈ {0, 1}) のランダムな基 e. 底とする．すなわち，E[i i ] = Pi , Qi である．次に，核が. ker(φ0 ) = P0 + [r0 ]Q0 となる同種写像を φ0 : E −→ E0 とする．このとき，E0 , φ0 (P1 ) と φ0 (Q1 ) が与えられたとき. 334. CSIDH は Couveignes-Rostovtev-Stolbunov 法（22）∼（24）に基づいて，Castryck, Lange, Martindale, Panny and Renes により 2018 年に提案された同種写像に基づく非対話型鍵共有法である（25）．なお，同種写像に基づく暗号では，超特異楕円曲線を用いる．p を素数とし，Fp 上定義された超特異楕円曲線を. E とする．このとき，超特異楕円曲線 E の自己準同型環は有 √ 理数体の二次拡大体の整数環 Z[ −p] と同型になる．次に，E √ √ と Fp -同型な楕円曲線の集合を Ep (Z[ −p]) とする．Z[ −p] √ √ のイデアル類群を Cl(Z[ −p]) とすると，Cl(Z[ −p]) は Fp √ 同型な楕円曲線の集合を Ep (Z[ −p]) 上に作用する．つまり， √ √ √ Cl(Z[ −p]) a は Ep (Z[ −p]) から Ep (Z[ −p]) への写像を定義する．. √ √ a : Ep (Z[ −p]) −→ Ep (Z[ −p]) IEICE Fundamentals Review Vol.14 No.4.

(8) E0 −→ aE0. の審議が開始し，2002 年に国際規格になった．2000 年から，. √ 重要なことは，Cl(Z[ −p]) は可換群であることから，上記の二つの写像は可換性を満たす．次に，CSIDH について紹介する．. • システム設定 p を素数とし，Fp 上定義された超特異楕円曲線を E0 とし，超 √ 特異楕円曲線 E の自己準同型環を Z[ −p], E と Fp -同型な楕 √ 円曲線の集合を Ep (Z[ −p]) とする． • ユーザ A の鍵生成 √ A は Cl(Z[ −p]) a を秘密鍵とし，E0 に作用させた楕円曲線を計算する，. Digital signatures giving message recovery (メッセージ復元型署名) の規格（15946-4）の審議が開始し，2004 年に国際規格となった．しかし，楕円曲線暗号の概念は，離散対数問題に基づく暗号の概念から一般化できることから，15946-2, 15946-. 3, 15946-4 の各パートはそれぞれ，ディジタル署名，鍵管理，メッセージ復元型署名のパート，14888-3, 11770-3, 9796-3 に吸収されて，規格化されている．更に，2006 年に elliptic curve. generation (楕円曲線生成，15946-5) の審議が開始し，2009 年に規格化されている．なお，ISO のドラフトは技術の更新に沿って，定期的に改訂され，2021 年，現在で，15946-5 の 3 回めの. Ea = aE0 .. 改訂が審議されている．現在，楕円曲線に基づく暗号手法の国際. (6). 規格は，15946-1 と 15946-5 の 2 規格になる．15946-1 は楕円. ここで，Ea が A の公開鍵である．. • ユーザ B の鍵生成 √ B は Cl(Z[ −p]) b を秘密鍵とし，E0 に作用させた楕円曲線を計算する，. 曲線暗号を実現する際に必要になる要素，楕円曲線のパラメータの生成方法やその検証方法，楕円曲線の元を整数に変換する方法などの規格である．付録として，楕円曲線の各種加算公式も記載されている．一方，15946-5 は楕円曲線暗号を利用する. Eb = bE0 .. 際に必要となる楕円曲線の生成方法となる．本規格は現時点では耐量子暗号を考慮しておらず，同種写像暗号以外，つまり，楕. ここで，Eb が A の公開鍵である．. 円曲線暗号と双線形写像に基づく暗号に利用する楕円曲線の生. • CSIDH 鍵共有法 • ユーザ A は B の公開鍵 Eb に対して，a を作用させ，共. 成を対象とする．. 有鍵 EK = aEb を求める．. 7. おわりに. • ユーザ B は A の公開鍵 Ea に対して，b を作用させ，共有鍵 EK = bEa を求める．. 整数論の長年の研究テーマであった楕円曲線が，暗号理論に. ここで，式 (6) の計算は，実際には，同種写像で成り立つ性質. (5) を利用する．つまり，E の部分群. おいても重要な位置を占めるようになった．楕円曲線暗号は提案から 30 年が過ぎ，実用化及び標準化という新たな局面を迎えた．今後より一層の活発な研究が，理論面においても実用面に. Φ = E[a] = ∩α∈a ker(α). おいてもなされることと思われる．に対して，定義される同種写像. 楕円曲線暗号は必要な安全性を小さな鍵サイズで実現できるため，有限体上の暗号より高速かつコンパクトに実現できる．今. φ : E −→ E/E[a] となる．CSIDH では奇素数 i ’ で表される素数 p = 4. 後，IoT 機器の普及に伴い，ますますコンパクトな暗号機能の. n. − i=1 i. 1 を利用する．この結果，各素数で生成されるイデアル (i ) √ は Z[ −p] 上で分解する．つまり，(i ) = li li と分解され √ る．CSIDH の秘密鍵はこの Z[ −p] 上のイデアル {li } と ei ∈ Z．を用いて，a =. . lei i で生成される．実際 CSIDH-. 装備は必須となるだろう．このとき楕円曲線暗号の役割は非常に大きい．本稿により，楕円曲線という数論のテーマがセキュリティに大きな影響を与えることについて多くの読者に興味をもって頂けると幸いである．. 512 では，p + 1 は 74 個の小さい奇素数から順に利用さ. 謝辞本稿の執筆に際し，白勢政明氏には数多くの助言を頂. れて，1 = 3, 2 = 5, . . . , 73 = 373, 74 = 587 から. いた．心からお礼を申し上げたい．南條由紀氏に頂いたコメン. − 1 で構成され，各ユーザの秘密鍵は ei は i=1 74. トは，本稿の内容を分かりやすくしたと思う．心からお礼を申. p = 4. n. [−5, . . . , 5] の範囲から生成される整数を用いて，a =. . lei i. で. し上げたい．. 表される．CSIDH の性能は連続した同種写像の計算方法に依存する．. 6. 国際規格 15946 (楕円曲線に基づく暗号手法) について楕円曲線に基づく暗号手法の国際規格を定める 15946 は 1998 年から審議が始まった．1998 年から，General (楕円曲線全般) の規格（15946-1），Digital signatures (付録型署名) の規格（15946-2），Key establishment (鍵確立) の規格（15946-3）. IEICE Fundamentals Review Vol.14 No.4. 文. 献. （1） N. Koblitz, “Elliptic curve cryptosystems,” Math. Comput., vol. 48, no. 177, pp. 203–209, 1987. （2） V.S. Miller, “Use of elliptic curves in cryptography,” Proc. Advances in Cryptology (CRYPTO ’85), Lecture Notes in Computer Science, vol. 218, pp. 417–426, Santa Barbara, California, USA, 1985. （3） Y. Jin and A. Miyaji, “Compact elliptic curve scalar multiplication with a secure generality,” J. Inf. Process., vol. 28, pp. 464–472, 2020.. 335.

(9) （4） D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L.D. Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, G. Pereira, J. Renes, V. Soukharev, and D. Urbanik, “Supersingular isogeny key encapsulation,” the NIST Post- Quantum Cryptography Standardization project; https://sike.org. （5） W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes, “CSIDH: an efficient post-quantum commutative group action,” Proc. 24th International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science, vol. 11274, pp. 395–427, Brisbane, QLD, Australia, 2018. （6） M. Meyer and S. Reith, “A faster way to the CSIDH,” Proc. 19th International Conference on Cryptology in India, Lecture Notes in Computer Science, vol. 11356, pp. 137–152, New Delhi, India, 2018. （7） M. Meyer, F. Campos, and S. Reith, “On lions and elligators: An efficient constant-time implementation of CSIDH,” Proc. 10th International Conference (PQCrypto 2019), Lecture Notes in Computer Science, vol. 11505, pp. 307–325, Chongqing, China, 2019. （8） A. Hutchinson, J.T. LeGrow, B. Koziel, and R. Azarderakhsh, “Further optimizations of CSIDH: A systematic approach to efficient strategies, permutations, and bound vectors,” IACR Cryptol. ePrint Arch., vol. 2019, p. 1121, 2019. （9） D. Cervantes-V´ azquez, M. Chenu, J. Chi-Dom´ınguez, L.D. Feo, F. Rodr´ıguez-Henr´ıquez, and B. Smith, “Stronger and faster side-channel protections for CSIDH,” Proc. 6th International Conference on Cryptology and Information Security in Latin America, Lecture Notes in Computer Science, vol. 11774, pp. 173– 193, Santiago de Chile, Chile, 2019. （10） K. Kodera, C. Cheng, and A. Miyaji, “Efficient algorithm for computing odd-degree isogenies on montgomery curves,” Proc. 21st International Conference (WISA 2020), Lecture Notes in Computer Science, vol. 12583, pp. 258–275, 2020. （11） H. Onuki, Y. Aikawa, T. Yamazaki, and T. Takagi, “A faster constant-time algorithm of CSIDH keeping two points,” Proc. 14th International Workshop on Security (IWSEC 2019), Lecture Notes in Computer Science, vol. 11689, pp. 23–33, Tokyo, Japan, 2019. （12）宮地充子，代数学から学ぶ暗号理論，日本評論社，1995. （13）山本芳彦，現代数学への入門—数論入門 2，岩波書店，1996. （14） J.H. Silverman, The Arithmetic of Elliptic Curves, Springer, 1986. （15） D. Boneh and M.K. Franklin, “Identity-based encryption from the weil pairing,” SIAM J. Comput., vol. 32, no. 3, pp. 586–615, 2003. （16）境隆一，大岸聖史，笠原正雄，“楕円曲線上のペアリングを ” 暗号と情報セキュリティシンポジウム予稿集用いた暗号方式，（SCIS2001），7B-2, 2001. （17） H.B. Hougaard and A. Miyaji, “SIT: supersingular isogeny tree-based group key exchange,” Proc. 15th Asia Joint Conference on Information Security (AsiaJCIS 2020), pp. 46–53, 2020. （18）永尾汎，代数学，朝倉書店，1983. （19） J. V´ elu, “Isog` enies entre courbes elliptiques,” C.R. Acad. Sci. Paris S´ er. A-B, vol. 273, pp. A238–A241, 1971. （20） L.C. Washington, Elliptic Curves: Number Theory and Cryptography, 2nd edition, Chapman & Hall/CRC, 2008. （21） L.D. Feo, D. Jao, and J. Plˆ ut, “Towards quantumresistant cryptosystems from supersingular elliptic curve isogenies,” J. Math. Cryptol., vol. 8, no. 3, pp. 209–247, 2014. （22） J.M. Couveignes, “Hard homogeneous spaces,” IACR Cryptol. ePrint Arch., vol. 2006, p. 291, 2006. （23） A. Rostovtsev and A. Stolbunov, “Public-key cryp-. 336. tosystem based on isogenies,” IACR Cryptol. ePrint Arch., vol. 2006, p. 145, 2006. （24） A. Stolbunov, “Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves,” Adv. Math. Comm., vol. 4, no. 2, pp. 215–235, 2010. （25） W. Castryck, T. Lange, C. Martindale, L. Panny, and J. Renes, “CSIDH: an efficient post-quantum commutative group action,” Proc. ASIACRYPT 2018, Lecture Notes in Computer Science, vol. 11274, pp. 395–427, 2018. （ISEC 研究会提案，2020 年 12 月 7 日受付， 2021 年 1 月 29 日再受付）. 宮地充子（正員） 1990 パナソニック（株）入社．1998 北陸先端科学技術大学院大学准教授．2007 北陸先端科学技術大学院大学教授．2015 大阪大学大学院教授．2016 （独行）情報処理推進機構監事．現在に至る．情報セキュリティの研究に従事．博士（理学）．SCIS93 若手論文賞，科学技術庁注目発明賞，平成 13 年度坂井記念特別賞（情報処理学会），平成 14 年度標準化貢献賞（情報処理学会），平成 17 年度功労感謝状（電子情報通信学会），平成. 18 年度情報セキュリティ文化賞，平成 19 年度国際規格開発賞（情報処理学会），平成 19 年度国際標準化奨励者表彰（産業技術環境局長表彰），平成 19 年度編集活動感謝状（電子情報通信学会），平成 20 年度国際規格開発賞（情報処理学会），平成 20 年度ドコモ・モバイル・サイエンス賞，平成 21 年度国際規格開発賞（情報処理学会），平成 22 年度国際規格開発賞（情報処理学会），ADMA 2010 Best Paper Award，平成 24 年度国際規格開発賞（情報処理学会），平成 24 年度基礎・境界ソサイエティ功労賞（電子情報通信学会），平成 28 年度国際規格開発賞（情報処理学会），ATIS. 2016 Best Paper Award, 平成 29 年度電子情報通信学会マイルストーン認定証，TrustCom 2017 Best Paper Award，AsiaJCIS 2019 Best Paper Award，WISA 2020 Best Paper Gold Award，各受賞．電子情報通信学会，情報処理学会，IACR，日本数学会各会員．. IEICE Fundamentals Review Vol.14 No.4.

(10)