Batch Processing Algorithm for Elliptic Curve Operations and Its AVX-512 Implementation

SCIS2025 4B2-1
https://www.iwsec.org/scis/2025/program.html#4B2

Transcript

1. 楕円曲線演算のバッチ処理アルゴリズムと AVX-512を用いた実装評価 サイボウズ・ラボ 光成滋生 2025/1/31 4B2-1 SCIS2025 1 / 19
2. 背景 広く使われている楕円曲線暗号 TLSで使われる楕円DH鍵共有・ECDSAなど 数個の楕円曲線の点の演算が多い 楕円曲線を用いた高機能な暗号技術 zk-SNARK, BBS+署名, 集約署名, 複数のBLS署名をまとめて検証, 属性ベース暗号など ZKPや高機能署名はブロックチェーン・Verifiable Credentialsなどで多用されている 楕円Lifted ElGamal暗号を用いた二者間秘密計算 SCIS2021 （with 九州大学 縫田氏）, SCIS2022, SCIS2024 （with NTT上野氏） これらは多数（～数万）の楕円曲線の点の演算が必要 → 多数の楕円曲線の演算のバッチ処理の高速化が重要 EdMSM, arkmsmなどの既存手法を紹介しつつ改善 2 / 19
3. 今回ターゲットとする演算 スカラー倍算のバッチ処理 楕円曲線の点 と整数 に対して を計算する マルチスカラー倍算 (MSM : Multi-Scalar Multiplication) 楕円曲線の点 と整数 に対して を計算する この二つは似ているが が大きいと高速化手法が異なる 3 / 19
4. 楕円曲線のスカラー倍算 ( ) の基本 ビットウィンドウ法 与えられた に対して つまり を計算する ビット整数 を 進数で表現する : ( , ) 出力変数 を を初期値として 倍しながら を加算する SIMD (Single Instruction, Multiple Data) の要件 要素ごとに分岐するのは不得手なためNAFやループ数が可変する手法は使わない テーブルルックアップはgather命令を利用 演算コスト , where : 2倍算, : 加算 4 / 19
5. GLV法 2倍算のコストを半分にする手法 ビット位数の群 に対して ビット整数 と計算容易な を用意 整数 に対して となる ビット整数 , を選ぶ のスカラー倍算を のMSMに変換した BLS12-381曲線の場合 定義方程式は で の位数 の部分群を とする は381ビットで , は255ビット素数 を1の原始3乗根( )とし とする は の自己同型写像で、ある128ビット奇数 が存在し 5 / 19
6. GLV法の疑似コード input : と , output : a + b L = n となる a, b に分解する tbla, tblb 2^w 個の配列を用意する tbla[0] = tblb[0] = 0 for i from 1 to 2^w-1: tbla[i] = tbla[i-1] + P # tbla[i] = i P tblb[i] = L tbla[i] # tblb[i] = i L P Q = 0 for i from 0 to ⌈L/2/w⌉: Q = 2^w Q Q = Q + tblb[bのiwビットからwビットを取り出す] Q = Q + tbla[aのiwビットからwビットを取り出す] return Q 6 / 19
7. の分解 となる の選択 BLS12-381曲線においては , でOK Barrettリダクション : を事前計算して による除算を回避 提案方式 とすると は128ビット の上位 ビット , とすると , . なら , とする 128ビット同士の整数乗算x2, ビットシフトx1, 129ビット引き算x2 既存方式よりも条件分岐と減算回数を削減 7 / 19
8. Weierstrass曲線の加算 加算と2倍算の公式が異なる 加算 の中で の場合2倍算に移行しなければならない 分岐が発生 SIMDでは扱いづらい・遅い → で を避けたい 8 / 19
9. GLV法のループ内の挙動 疑似コードの後半を再掲 Q = 0 for i from 0 to ⌈L/2/w⌉: # Q = d P と表記すると d はループを通して単調増加 Q = 2^w Q Q = Q + d_b L P # -- (A1) 0 <= d_b < 2^w Q = Q + d_a P # -- (A2) 0 <= d_a < 2^w return Q 補題 : BLS12-381曲線で (A1), (A2) の加算値が同じ値になることはない (A1) において は奇数なので は と異なる (A2) において . → において を仮定できる（ は許容する） 9 / 19
10. 座標選択 2倍算の回数が加算回数より多い → ヤコビ座標を利用する バッチ処理におけるアフィン化のコストが低い 最初に をアフィン化する ウィンドウ法のためのテーブル作成は の繰り返し 「ヤコビ座標+アフィン座標」による混合座標を用いた加算を利用 テーブル作成後も再度アフィン化することで後半のループ内の加算も混合座標を利用可能 10 / 19
11. 逆元のバッチ処理 非SIMDの場合 楕円曲線の点 について が必要 入力 に対して を求めてから を求める（詳細は予稿集参照） 個の元の逆元のコストは （ : 逆元, : 乗算） SIMDの場合 逆元はループと分岐が多いためSIMDで実装するのは煩雑で難しい SIMDによる全体のバッチ処理 ＋「 個の逆元をスカラーの逆元のバッチ処理」 それぞれを SIMD処理 x 0 x 1 x 7 x 8 x 9 x 15 x 8n x 8n+1 x 8n+7 各⾏ごとの積に対して スカラーに対する 逆元のバッチ処理 11 / 19
12. 今回ターゲットとする環境 AVX-512 IFMA Intel CPUの52ビット乗算対応のSIMD命令 52ビット整数 , と64ビット整数 に対して をSIMDで計算できる 加減算・論理演算・シフト演算などは64ビット単位で 個並列のSIMDで処理する データの形 BLS12-381曲線では381ビット整数を52ビット単位に分割して64ビット整数8個で表現する 個の384ビット整数 を8個のSIMDレジスタに格納する SIMDレジスタ1個 X 00 X 01 X 02 zmm0 zmm1 zmm2 ... X 10 X 11 X 12 X 20 X 21 X 22 整数X 0 整数X 1 X 07 X 17 X 27 zmm7 12 / 19
13. Montgomery乗算 記号 : 素数, : 整数, , , に対して とする に対して を ビットMontgomery表現と呼ぶ , 変換の高速化 通常のスカラー64ビットMontgomery表現からSIMD 52ビットMontoegomery表現への変換 : スカラー版乗算8回+SIMD版乗算1回 : 改良後 SIMD版乗算1回 x i x i R 64 x i R 52 スカラーfromMont x8 SIMD toMont x1 SIMD mont(x i , 2 32 ) x1 13 / 19
14. ベンチマーク 環境 Intel Xeron w9-3495X (Sapphire Rapids), Ubuntu 24.04.1 LTS, gcc 13.2.0 (SIMD乗算はs_xbyak) https://github.com/herumi/mcl : BLS12-381曲線の で評価 バッチ処理+SIMDによる高速化率 基本演算 演算 非 SIMD SIMD SIMD 加算 273 118.36 (2.3x) 102.44 (2.66x) 2倍算 187 70.66 (2.6x) 64.38 (2.9x) SIMD演算を2個ずつ並べて （1024ビットSIMD相当） とすると1割ほど高速化 スカラー倍算のバッチ処理は3.23倍の高速化を達成 14 / 19
15. MSM ( ) が小さいときは素直に 個のウィンドウ法（大きいと逆に遅くなる） バケット法 として に対して が十分大きい時に効率的に を計算する手法 例 : のとき なので を それぞれのグループに分ける この処理をpartialSum( , )と書くことにする バケット法の疑似アルゴリズム b = getBucketSize(n) # x_i を何ビットずつ分割するかバケットサイズを決める Q = 0 for w from 0 to ⌈l/b⌉: Q = 2^b Q + partialSum(P_i, x_iのw*bビットからbビット切り出したもの) return z 15 / 19
16. 最適なバケットサイズ 演算コストの見積もり ビット取り出して を求めるコスト それぞれを求める全体のコストは . のコストは 全体のコストは : : のビット長 これを最小化する を求める - つまり として 近似解 where : のビット長 で厳密解との差は 以内 このとき全体のコストは GLV法を組み合わせると , なので のコストが 倍 が大きくなると効果が小さくなる 16 / 19
17. スカラー倍算のバッチ処理との違い 射影座標への変換 partialSum内の は を仮定できない ヤコビ座標を使えない 射影座標の完全加法公式を利用する（今回の対象がMontgomery曲線ではない） アフィン化によりによる混合座標の加法公式も利用できるが効果は小さい SIMDの並列数 バケット法で大きなテーブルルックアップ テーブルのサイズは よりも が速い（gatherがボトルネック?） 17 / 19
18. バケットサイズの理論値と実際の最良値とのずれ 横軸 に対するバケットサイズの理論値と実測値の比較 青丸(theoretic) : コスト最小の理論値, オレンジ四角(heuristic) : 速度最大となる実測値 緑三角はそのときの速度向上率 heuristicはd=16~19, 23~27で一定値 はL2キャッシュ (2MiB), はL3キャッシュ (105MiB) に収まるサイズ 18 / 19
19. まとめ スカラー倍算のバッチ処理, MSMのSIMD化により3.23x, 1.4~1.66x MSMは1個ずつスカラー倍算して加算した場合の8.3x (n=8192のとき) スカラー倍算のバッチ処理とMSMでの最適な選択 項目 スカラー倍算 MSM add( ) を仮定できる できない 座標 ヤコビ座標 射影座標 GLV法 重要 が大きいと重要度は低い SIMD処理単位 V=16 V=8（アンロールはメモリ圧迫） L2, L3キャッシュサイズ 考慮不要 バケットサイズに影響 AVX-512 IFMAによる高速化率 3.23x 1.4~1.66x (vs. arkmsm) 19 / 19