暗号技術の実装と数学
Download as PDF, PPTX8 likes13,140 views
九州大学談話会「IMI Colloquium」 https://www.imi.kyushu-u.ac.jp/seminars/view/3001
![• 楕円曲線の準備
• 有限体𝔽𝑝上の楕円曲線𝐸を固定する
• 素数𝑟を固定し𝐺 = 𝐸 𝑟 = {𝑃 ∈ 𝐸(𝔽𝑝)|𝑟𝑃 = 0}とする
• 𝑃を𝐺の生成元とすると𝐺 = {0, 𝑃, 2𝑃, … , 𝑟 − 1 𝑃}
• アリスとボブのDH鍵共有
• アリスは𝑎 ∈ [0, 𝑟 − 1]をランダムに選び𝐴 = 𝑎𝑃をボブに送る
• ボブは𝑏 ∈ [0, 𝑟 − 1]をランダムに選び𝐵 = 𝑏𝑃をアリスに送る
• アリスは𝑎𝐵 = 𝑎𝑏𝑃, ボブは𝑏𝐴 = 𝑏𝑎𝑃を計算し共有情報とする
• DLPとDHP
• DLP : 𝑄 ∈ 𝐺がgivenの下で𝑄 = 𝑎𝑃となる𝑎を求める問題
• DHP : 𝑎𝑃, 𝑏𝑃がgivenの下で𝑎𝑏𝑃を求める問題（𝑎, 𝑏は未知）
• 現在最良のアルゴリズムは𝑂( 𝑟) （on 非量子計算機）
• 𝑟~2256の大きさなら十分安全
楕円DH鍵共有
7 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-7-320.jpg)
![• 𝑛ビット整数𝑎と楕円曲線の点𝑃に対して𝑎𝑃を求める
• ナイーブな方法
• 𝑃, 𝑃 + 𝑃 = 2𝑃, 2𝑃 + 𝑃 = 3𝑃, … ; 𝑎~2256だと計算が終わらない
• バイナリ法
• 𝑎 = σ𝑖=0
𝑛−1
𝑎𝑖2𝑖と2進数展開(𝑎𝑖 ∈ {0,1})
• 𝑎 = 𝑎0 + 2(𝑎1 + … + 2(𝑎𝑛−3+2(𝑎𝑛−2 + 2𝑎𝑛−1)) … )なので
• 𝑏0 = 𝑎𝑛−1, 𝑏𝑖 = 𝑎𝑛−1−𝑖 + 2𝑏𝑖−1とすると𝑏𝑛−1 = 𝑎
• 𝑏0𝑃, 𝑏1𝑃, … , 𝑏𝑛−1𝑃 = 𝑎𝑃を計算（高々2𝑛回）
• ウィンドウ法
• 𝑎 = σ𝑖 𝑎𝑖 2𝑤 𝑖, 𝑎𝑖 ∈ [0,2𝑤 − 1]として同様の計算
• 𝑡𝑃(𝑡 ∈ [0,2𝑤
− 1])は事前計算（コストは2𝑤
+
𝑛
𝑤
+ 𝑛）
• 𝑛~256なら𝑤 = 4が最小, 𝑃が固定なら大きくしてもよい
スカラー倍算
8 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-8-320.jpg)
![• NAF (Non Adjacent Form)
• 楕円曲線の点𝑃 = (𝑥, 𝑦)に対して−𝑃 = (𝑥, −𝑦)
• [0,2𝑤 − 1]のテーブルではなく[−2𝑤−1, 2𝑤−1 − 1]とする
• − 𝑎𝑃 = −𝑎 𝑃なのでテーブルサイズを半分にできる
• テーブルの偶数倍番目を除去
• 𝑎𝑖が偶数なら𝑄 = 2𝑤
𝑄 + 𝑎𝑖𝑃 = 2 2𝑤−1
𝑄 +
𝑎𝑖
2
𝑃
• 「2倍してから加算」の代わりに「加算してから2倍」
• 𝑎𝑖が奇数になるまで繰り返す
• テーブルは奇数番目だけでよい
• 𝑤 = 6にしても最初の𝑤 = 4と同じ事前計算コスト
ウィンドウ法の事前計算の削減
𝑄 ∶ 途中までの加算結果
𝑄 ← 2𝑤𝑄 : 2𝑤倍
𝑄 ← 𝑄 + 𝑎𝑖𝑃 : 𝑎𝑖𝑃は事前計算のテーブル引き
10 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-10-320.jpg)
![• 楕円曲線を用いた署名アルゴリズムの一つ
• TLSやSSH, ビットコインなど広く使われている
• 事前準備
• 楕円曲線𝐸/𝔽𝑝と𝐺 = ⟨𝑃⟩, 𝑃 ∈ 𝐸[𝑟]を共通パラメータとする
• 鍵生成
• 乱数𝑠 ∈ 𝔽𝑟を署名鍵, 𝑆 = 𝑠𝑃を検証鍵とする
• 署名
• 𝑚 ∈ 𝑋に対して乱数𝑘 ∈ 𝔽𝑟をとり𝑘𝑃の𝑥座標を𝑟とする
• 𝜎 = (𝑟, (𝐻 𝑚 + 𝑠𝑟)/𝑘)が署名
• 検証
• 𝑚, 𝜎 = (𝑟, 𝑡)に対して𝑅 = (𝐻 𝑚 𝑃 + 𝑟𝑆)/𝑡を計算して
𝑅の𝑥座標が𝑟なら受理、そうでなければ拒否する
ECDSA
12 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-12-320.jpg)
![• 𝐺 = 𝐸[𝑟], 𝑃, 𝑄 ∈ 𝐺をfix
• ECDLP : 𝑎𝑃, 𝑃 : givenに対して𝑎 ∈ 𝔽𝑟を求める
• 𝑢 ≔ 𝑒 𝑎𝑃, 𝑄 = 𝑒 𝑃, 𝑄 𝑎
• もし𝑢と𝑒(𝑃, 𝑄)に対するDLPが解ければECDLPが解ける
• ECDLPをDLPに帰着するためにペアリングを利用
• MOV(Menezes-Okamoto-Vanstone) reduction, 1990
• 帰着後のDLPが解けなければ暗号に利用可能 1999~
DLPとペアリングの関係
19 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-19-320.jpg)
![• 現在128bitセキュリティ相当で一番利用されている
• 曲線 : 𝑦2 = 𝑥3 + 4 /𝔽𝑝 （𝑝は381bit素数で𝑝 mod 6 ≡ 1）
• 𝐺1 = 𝐸[𝑟] （𝑝は255bit素数）
• 𝜑: 𝐸 ∋ 𝑥, 𝑦 ↦ 𝑥′, 𝑦′ =
𝑥
𝑤2 ,
𝑦
𝑤3 ∈ 𝐸′ = 𝑦′2 = 𝑥′3 + 4𝜉
• 𝜉 = 1 + 𝑖, 𝑣3
= 𝜉, 𝑤2
= 𝑣, 𝐺2 = 𝐸′
𝔽𝑝2 𝑟
• 𝐺𝑇 = {𝑥 ∈ 𝔽𝑝12|𝑥12 = 1}, 𝔽𝑝12 = 𝔽𝑝6[𝑤], 𝔽𝑝6 = 𝔽𝑝3[𝑣]
• 𝑒 𝑃, 𝑄 = 𝐹𝐸 𝑀𝐿 𝑃, 𝑄
• 𝑀𝐿 : 双線型性を持つMiller Loop関数, 𝐹𝐸 𝑥 = 𝑥𝑟0 : 固定べき
• 安全性仮定（用途に応じていろいろ提案されている）
• DDH(Decisional DH)仮定
• 𝐺𝑖 ∋ 𝑃, 𝑎𝑃, 𝑏𝑃, 𝑐𝑃に対し𝑎𝑏𝑃 =
?
𝑐𝑃を判定困難
• co-DHP*仮定 :𝑎𝑃1, 𝑄 ∈ 𝐺1, 𝑎𝑃2 ∈ 𝐺2に対して𝑎𝑄は計算困難
BLS12-381曲線(Barreto-Lynn-Scott)
21 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-21-320.jpg)
![• 𝔽𝑝2 = 𝔽𝑝[𝑖] where 𝑖2 = −1 in 𝔽𝑝
• 𝑥 = 𝑎 + 𝑏𝑖, 𝑦 = 𝑐 + 𝑑𝑖の乗算
• 𝑥𝑦 = 𝑎 + 𝑏𝑖 𝑐 + 𝑑𝑖 = 𝑎𝑐 − 𝑏𝑑 + 𝑎𝑑 + 𝑏𝑐 𝑖
• 𝑎𝑑 + 𝑏𝑐 = 𝑎 + 𝑏 𝑐 + 𝑑 − 𝑎𝑐 − 𝑏𝑑
• 𝑋 = 𝑎𝑐, 𝑌 = 𝑏𝑑, 𝑍 = (𝑎 + 𝑏)(𝑐 + 𝑑)の乗算3回(Karatsuba)
• 𝔽𝑝の乗算=𝑝ビット整数同士の乗算 + mod p
• 本当はMontgomery乗算を使うがここでは省略
• コストは乗算よりmod pがやや重たい
• 𝑋, 𝑌, 𝑍をmod pなしで計算(Mitsunari, et al. Pairing2010)
• 𝑎𝑐 − 𝑏𝑑 = (𝑋 − 𝑌) mod p
• 𝑎𝑑 + 𝑏𝑐 = (𝑍 − 𝑋 − 𝑌) mod p
• mod pの処理が3回から2回に減る
𝔽𝑝2の演算の効率化
22 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-22-320.jpg)
![• 𝑓 𝑥 = 𝑓0 + 𝑓1𝑥 + ⋯ + 𝑓𝑘−1𝑥𝑘−1 ∈ 𝔽𝑟[𝑥] : 𝑘 − 1次多項式
• 𝑛個の相異なる𝑥1, … , 𝑥𝑛に対して𝑦𝑖 = 𝑓(𝑥𝑖)とする
• ここから任意の相異なる𝑘個のペア 𝑥𝑖𝑎
, 𝑦𝑖𝑎
1 ≤ 𝑎 ≤ 𝑘 を取る
•
𝑦𝑖1
⋮
𝑦𝑖𝑘
=
1 ⋯ 𝑥𝑖1
𝑘−1
⋮ ⋱ ⋮
1 ⋯ 𝑥𝑖𝑘
𝑘−1
𝑓0
⋮
𝑓𝑘−1
= 𝐴
𝑓0
⋮
𝑓𝑘−1
• 𝐴 = 𝑥𝑖𝑎
𝑏
はdet 𝐴 ≠ 0なので (𝑦𝑖𝑎
)から(𝑓𝑖)が求まる
• 秘密分散
• 𝑓0を秘密とする
• 𝑓1, … , 𝑓𝑘−1をランダムに選び𝑛個のペア 𝑥𝑖𝑎
, 𝑦𝑖𝑎
= 𝑓(𝑥𝑖𝑎
) を作る
• そのうち𝑘個のペアで𝑓0を復元できる
• 𝑘 − 1以下なら不可能（𝑓0の取り得る可能性は𝔽𝑟全て）
Lagrange補間
27 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-27-320.jpg)
![• 𝑧 ← σ𝑖=0
𝑛−1
𝑥𝑖𝑃𝑖の擬似コード
• 𝐿 : max 𝑙𝑒𝑛 𝑥𝑖
• 𝑐 : まとめるテーブルのビット長
• 𝑁 = 2𝑐 : テーブルT[𝑁]のサイズ, 𝑀 =
𝐿
𝑐
: 区切った個数
• 𝑇 𝑖 ← 0 for all 𝑖
• for 𝑤 from 0 to 𝑀 − 1
• for 𝑖 from 0 to 𝑛 − 1
• 𝑣 ← 𝑥𝑖の𝑐𝑤から𝑐ビットの値
• T[𝑣] ← 𝑇 𝑣 + 𝑃𝑖 // 𝑣倍される𝑃𝑖を集める
• 𝑠𝑢𝑚 ← 0, 𝑊[𝑤] ← 0
• for 𝑖 from 0 to 𝑁
• 𝑠𝑢𝑚 ← 𝑠𝑢𝑚 + 𝑇[𝑁 − 𝑖]
• 𝑊 𝑤 ← 𝑊 𝑤 + 𝑠𝑢𝑚
MULSUMの概要(1/2)
𝑥𝑖
𝑐
𝑣
𝑊 𝑤
= ⋯ + 𝑇 𝑁 − 2 + 𝑇 𝑁 − 1 + 𝑇 𝑁
+ 𝑇 𝑁 − 1 + 𝑇 𝑁 + 𝑇 𝑁
= 𝑇[1] + 2𝑇[2] + 3𝑇 3 + ⋯
← 𝑤番目
32 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-32-320.jpg)
![• 続き
• 𝑊 𝑤 = 𝑤番目の𝑥𝑖達の𝑃𝑖のスカラー倍の和
• 𝑍 ← 0
• for 𝑤 from 0 to 𝑀 − 1
• 𝑍 ← 2𝑐𝑍 + 𝑊[𝑀 − 1 − 𝑤]
• 演算コスト
• 𝐿 : 𝑥𝑖の最大ビット(e.g., 256), 𝑁 = 2𝑐
, 𝑀 = 𝐿/𝑐
• ADD : 𝑀 𝑛 + 2𝑁 + 𝑀 = Τ
𝐿(𝑛 + 2𝑐+1 + 1) 𝑐, DBL : 𝐿
• ADDのコストが最小になる𝑐
• （適当に見つけた）近似値𝑐min = 𝑖𝑛𝑡(log2 𝑛 − log2(log2 𝑛))
• 𝑛~229ぐらいまでで誤差±1ぐらい
• 余談 : int(log2 𝑛)は𝑛の2進数表記の左から初めて1がある位置
• 𝑛 = 1024なら𝑐 = 8（𝑛 ≈ 64(GLV適用前)が速度の分岐点）
MULSUMの概要(2/2)
𝑥𝑖
𝑐
𝑣
← 𝑤番目
33 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-33-320.jpg)
![• 楕円曲線の加算𝑃 + 𝑄
• 片方の点がAffine座標と分かっていれば加算を効率よくできる
• [𝑥: 𝑦: 𝑧]の𝑧を1にできる
• しかしJacobi/Proj→Affineは除算が入るので遅い
• mul : div = 1:100
• 複数の逆数をまとめて処理
• 𝑎, 𝑏の逆数 Τ
1 𝑎 , Τ
1 𝑏は Τ
𝑏 𝑎𝑏, Τ
𝑎 𝑎𝑏なので1/𝑎𝑏の逆数1回で計算
• {𝑥1, 𝑥2, 𝑥3, 𝑥4}に対して
• 𝑇[] = {𝑥1, 𝑥1𝑥2, 𝑥1𝑥2𝑥3, 𝑥1𝑥2𝑥3𝑥4}, 𝑟 ← 𝑥1𝑥2𝑥3𝑥4
−1
• Τ
1 𝑥4 = 𝑥1𝑥2𝑥3 𝑟, 𝑟 ← 𝑟𝑥4 = 𝑥1𝑥2𝑥3
−1
Τ
1 𝑥3 = 𝑥1𝑥2 𝑟, 𝑟 ← 𝑟𝑥3 = 𝑥1𝑥2
−1
Τ
1 𝑥2 = 𝑥1 𝑟, 𝑟 ← 𝑟𝑥1 = 𝑥1
−1
• 𝑛回逆数が「 2(𝑛 − 1)回の乗算+1回除算」になる
複数の除算とAffine化の高速化
34 /35](https://image.slidesharecdn.com/imi-kyusyu-20220608-220608111227-a330daa2/85/-34-320.jpg)
暗号技術の実装と数学
- 2. • 自己紹介 • 暗号技術の概説 • TLS • 楕円曲線 • DH鍵共有 • 署名 • スカラー倍算 • ペアリング • BLS署名 • マルチスカラー倍算 目次 2 /35
- 3. • サイボウズ・ラボで暗号や最適化に関するR&D • OSS(Open Source Software)の開発 • Xbyak • x86/x64用JITアセンブラ • 高速な暗号ライブラリを開発するために開発 • IntelのoneDNN （AIフレームワーク）などで利用されている • スーパーコンピュータ富岳用のXbyak/oneDNNにも関わる • mcl/bls • ペアリング暗号ライブラリ • BLS署名ライブラリ • Ethereumなどのブロックチェーン系ソフトで利用されている 自己紹介 3 /35
- 4. • 安全な通信をするために必要な性質 • 機密性 : 通信内容を他人が盗聴しても内容が分からない • 完全性 : 通信内容を他人が改竄すると分かる・改竄できない • 真正性 : 通信相手が本当にその人であること • 機密性だけでは安全ではない • 共通暗号（機密性） • 秘密鍵𝑠で平文（ひらぶん）𝑚を暗号化（Encrypt） • 𝑐 = 𝐸𝑛𝑐(𝑠, 𝑚) ; 𝑐は暗号文 • 秘密鍵𝑠で𝑐を復号する（Decrypt）と元に戻る • 𝑚 = 𝐷𝑒𝑐(𝑠, 𝑐) • 認証付き暗号AEAD（機密性+完全性） • 暗号文𝑐が秘密鍵𝑠で作られたものでなければエラー • 通常の共通鍵暗号は問答無用で「復号する」 安全な通信と暗号技術 4 /35
- 5. • ある人があるデータを生成したことを検証する仕組み • 鍵生成 : アリスは署名鍵𝑠と検証鍵𝑆の組を生成する • 検証鍵𝑆を検証者に渡す（署名鍵は誰にも見せない） • 署名 : アリスはデータ𝑚と署名鍵𝑠から署名𝜎を生成する • 𝜎 = 𝑆𝑖𝑔𝑛(𝑠, 𝑚) • 検証 : 検証者は検証鍵𝑆, データ𝑚, 署名𝜎の組が正しければ1, そうでなければ0を返す • 𝑉𝑒𝑟𝑖𝑓𝑦 𝑆, 𝑚, 𝜎 ∈ {0,1} • 「偽造できない」 • 署名鍵𝑠無しで、アリスが生成した 正しい組 𝑚𝑖, 𝜎𝑖 以外の𝑉𝑒𝑟𝑖𝑓𝑦 𝑆, 𝑚, 𝜎 = 1 となる署名は作れない 署名（真正性） 署名σ アリス 署名鍵𝑠 ボブ 検証鍵𝑆 鍵生成 署名 データ𝑚 受理（1） 拒否（0） 検証 検証鍵𝑆 5 /35
- 6. • 安全な通信をするためのプロトコル • DH鍵共有+AEAD+公開鍵証明書+署名 TLS アリス ボブ（サーバ） 値A 値B DH鍵共有により 秘密の値を共有 AEADの秘密鍵 公開鍵証明書X ボブのサーバ情報とボブの検証鍵の ペアに認証局CAによる署名をつけたもの 送信データに対するボブの署名鍵による署名 CAの検証鍵で Xの正しさを確認 ボブの検証鍵で データの正しさを確認 安全な秘密の通信 CA （信頼できる第三者機関） 6 /35
- 7. • 楕円曲線の準備 • 有限体𝔽𝑝上の楕円曲線𝐸を固定する • 素数𝑟を固定し𝐺 = 𝐸 𝑟 = {𝑃 ∈ 𝐸(𝔽𝑝)|𝑟𝑃 = 0}とする • 𝑃を𝐺の生成元とすると𝐺 = {0, 𝑃, 2𝑃, … , 𝑟 − 1 𝑃} • アリスとボブのDH鍵共有 • アリスは𝑎 ∈ [0, 𝑟 − 1]をランダムに選び𝐴 = 𝑎𝑃をボブに送る • ボブは𝑏 ∈ [0, 𝑟 − 1]をランダムに選び𝐵 = 𝑏𝑃をアリスに送る • アリスは𝑎𝐵 = 𝑎𝑏𝑃, ボブは𝑏𝐴 = 𝑏𝑎𝑃を計算し共有情報とする • DLPとDHP • DLP : 𝑄 ∈ 𝐺がgivenの下で𝑄 = 𝑎𝑃となる𝑎を求める問題 • DHP : 𝑎𝑃, 𝑏𝑃がgivenの下で𝑎𝑏𝑃を求める問題（𝑎, 𝑏は未知） • 現在最良のアルゴリズムは𝑂( 𝑟) （on 非量子計算機） • 𝑟~2256の大きさなら十分安全 楕円DH鍵共有 7 /35
- 8. • 𝑛ビット整数𝑎と楕円曲線の点𝑃に対して𝑎𝑃を求める • ナイーブな方法 • 𝑃, 𝑃 + 𝑃 = 2𝑃, 2𝑃 + 𝑃 = 3𝑃, … ; 𝑎~2256だと計算が終わらない • バイナリ法 • 𝑎 = σ𝑖=0 𝑛−1 𝑎𝑖2𝑖と2進数展開(𝑎𝑖 ∈ {0,1}) • 𝑎 = 𝑎0 + 2(𝑎1 + … + 2(𝑎𝑛−3+2(𝑎𝑛−2 + 2𝑎𝑛−1)) … )なので • 𝑏0 = 𝑎𝑛−1, 𝑏𝑖 = 𝑎𝑛−1−𝑖 + 2𝑏𝑖−1とすると𝑏𝑛−1 = 𝑎 • 𝑏0𝑃, 𝑏1𝑃, … , 𝑏𝑛−1𝑃 = 𝑎𝑃を計算（高々2𝑛回） • ウィンドウ法 • 𝑎 = σ𝑖 𝑎𝑖 2𝑤 𝑖, 𝑎𝑖 ∈ [0,2𝑤 − 1]として同様の計算 • 𝑡𝑃(𝑡 ∈ [0,2𝑤 − 1])は事前計算（コストは2𝑤 + 𝑛 𝑤 + 𝑛） • 𝑛~256なら𝑤 = 4が最小, 𝑃が固定なら大きくしてもよい スカラー倍算 8 /35
- 9. • Weierstrass方程式 𝑦2 = 𝑥3 + 𝑎𝑥 + 𝑏 • アフィン座標 • 一般の点𝑃𝑖 = (𝑥𝑖, 𝑦𝑖)に対して𝑃1 + 𝑃2 = (𝑥3, 𝑦3) • 𝑥3 = 𝜆2 − 𝑥1 + 𝑥2 , 𝑦3 = −𝜆 𝑥3 − 𝑥1 − 𝑦1 • 𝜆 = Τ (𝑦1 − 𝑦2) (𝑥1 − 𝑥2) if 𝑥1 ≠ 𝑥2 else Τ (3𝑥1 2 + 𝑎) (2𝑦1) • ADD : 𝑃 + 𝑄(𝑃 ≠ 𝑄)の計算, DBL : 2𝑃の計算 • 有限体𝔽𝑝の四則演算のおおよそのコスト • 除算はとても重たい add : mul : div = 1 : 7.3 : 940(BLS12-381) • 射影座標 𝑃 = 𝑋: 𝑌: 𝑍 = (𝑥, 𝑦), 𝑥 = 𝑋/𝑍, 𝑦 = 𝑌/𝑍 • 加算・乗算回数は増えるが除算が無くなる • Jacobi座標 𝑃 = 𝑋: 𝑌: 𝑍 = (𝑥, 𝑦), 𝑥 = 𝑋/𝑍2,𝑦 = 𝑌/𝑍3 • 射影座標よりADDは少し重たいがDBLが少し軽い 楕円曲線の座標選択 9 /35
- 10. • NAF (Non Adjacent Form) • 楕円曲線の点𝑃 = (𝑥, 𝑦)に対して−𝑃 = (𝑥, −𝑦) • [0,2𝑤 − 1]のテーブルではなく[−2𝑤−1, 2𝑤−1 − 1]とする • − 𝑎𝑃 = −𝑎 𝑃なのでテーブルサイズを半分にできる • テーブルの偶数倍番目を除去 • 𝑎𝑖が偶数なら𝑄 = 2𝑤 𝑄 + 𝑎𝑖𝑃 = 2 2𝑤−1 𝑄 + 𝑎𝑖 2 𝑃 • 「2倍してから加算」の代わりに「加算してから2倍」 • 𝑎𝑖が奇数になるまで繰り返す • テーブルは奇数番目だけでよい • 𝑤 = 6にしても最初の𝑤 = 4と同じ事前計算コスト ウィンドウ法の事前計算の削減 𝑄 ∶ 途中までの加算結果 𝑄 ← 2𝑤𝑄 : 2𝑤倍 𝑄 ← 𝑄 + 𝑎𝑖𝑃 : 𝑎𝑖𝑃は事前計算のテーブル引き 10 /35
- 11. • 𝑋を任意のビット列からなる集合𝑋 = 0,1 ∗ • 𝑌を𝑛ビット列からなる集合𝑌 = 0,1 𝑛 • 𝑛ビットのハッシュ関数𝐻: 𝑋 → 𝑌とは次を満たすもの • 一方向性 • ℎ ∈ 𝑌に対して𝐻 𝑥 = ℎとなる𝑥を求めるのは困難(𝑂(2𝑛)) • 第二原像計算困難性 • 𝑥 ∈ 𝑋に対して𝐻 𝑥 = 𝐻(𝑥′)となる𝑥′(𝑥 ≠ 𝑥)を求めるのは困難 • 𝑂(2𝑛 ) • 衝突困難性 • 𝐻 𝑥1 = 𝐻(𝑥2)となる𝑥1, 𝑥2 ∈ 𝑋(𝑥1 ≠ 𝑥2)で求めるのは困難 • 𝑂(2 Τ 𝑛 2) ハッシュ関数 11 /35
- 12. • 楕円曲線を用いた署名アルゴリズムの一つ • TLSやSSH, ビットコインなど広く使われている • 事前準備 • 楕円曲線𝐸/𝔽𝑝と𝐺 = ⟨𝑃⟩, 𝑃 ∈ 𝐸[𝑟]を共通パラメータとする • 鍵生成 • 乱数𝑠 ∈ 𝔽𝑟を署名鍵, 𝑆 = 𝑠𝑃を検証鍵とする • 署名 • 𝑚 ∈ 𝑋に対して乱数𝑘 ∈ 𝔽𝑟をとり𝑘𝑃の𝑥座標を𝑟とする • 𝜎 = (𝑟, (𝐻 𝑚 + 𝑠𝑟)/𝑘)が署名 • 検証 • 𝑚, 𝜎 = (𝑟, 𝑡)に対して𝑅 = (𝐻 𝑚 𝑃 + 𝑟𝑆)/𝑡を計算して 𝑅の𝑥座標が𝑟なら受理、そうでなければ拒否する ECDSA 12 /35
- 13. • ECDSAの証明の検証では「𝑥1𝑃1 + 𝑥2𝑃2」の計算が必要 • 𝑃は固定なのでウィンドウ法の𝑤を大きく取れる • テーブルサイズは大きくなるのでメモリが必要 • 𝑄 = 𝑥1𝑃1 + 𝑥2𝑃2 • 𝑥𝑖𝑃𝑖をしてから足すのではなく同時にする • 𝑃1, 𝑃2それぞれのウィンドウ法の事前計算をする • 𝑄 ← 2𝑤𝑄の処理が半分になる • 𝑄 = 𝑥1𝑃1 + ⋯ + 𝑥𝑛𝑃𝑛の場合2倍算は1/𝑛になる • ただし必要なテーブルは𝑛倍なので逆に遅くなることも マルチスカラー倍算 𝑄 ∶ 途中までの加算結果 𝑄 ← 2𝑤𝑄 : 2𝑤倍 𝑄 ← 𝑄 + 𝑎𝑖𝑃1 : 𝑎𝑖𝑃1は事前計算のテーブル引き 𝑄 ← 𝑄 + 𝑏𝑖𝑃2 : 𝑏𝑖𝑃2は事前計算のテーブル引き 13 /35
- 14. • Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms (Gallant, Lambert, Vanstone) • https://www.iacr.org/archive/crypto2001/21390189.pdf • 𝑙𝑒𝑛(𝑥)を𝑥のビット長とする • （𝑥の分解）次の様な𝐿があるとする • ∀𝑃 ∈ 𝐺について𝐿𝑃が高速計算可能 • ∀𝑥 ∈ 𝔽𝑟について 𝑥 = 𝑎1 + 𝑎2𝐿で𝑙𝑒𝑛 𝑎𝑖 ~𝑙𝑒𝑛(𝑥)/2となる𝑎𝑖を高速に求められる • 𝑥𝑃 = 𝑎1 + 𝑎2𝐿𝑃 = 𝑎1𝑃 + 𝑎2(𝐿𝑃) • 𝑃と𝐿𝑃に関するマルチスカラー倍算を適用 • DBLの回数は1/2 • ADDの回数はほぼ変わらず スカラー倍算をマルチスカラー倍算に 14 /35
- 15. • ビットコインで利用される楕円曲線 • 𝑦2 = 𝑥3 + 7 • 𝑝=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f • 𝑟 = #𝐸(𝔽𝑝) = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 • 𝑤3 − 1 = 0 𝑖𝑛 𝔽𝑝の非自明な解𝑤 = −1+ −3 2 ∈ 𝔽𝑝, (𝑝 + 1 ≡ 0(𝑚𝑜𝑑 4)) • 𝜑 𝑥, 𝑦 = (𝑤𝑥, 𝑦)とすると𝜑: 𝐸 𝔽𝑝 → 𝐸(𝔽𝑝)は有理写像 • 準同型写像でもある • 𝜑 𝑃 = 𝐿𝑃となる𝐿 ∈ 𝔽𝑟が存在する(𝐿3 = 1) • 𝐿𝑃 = (𝑤𝑥, 𝑦)なので𝐿倍は高速に計算できる secp256k1と自己同型写像 15 /35
- 16. • 𝑣 = 𝑎1, 𝑎2 ∈ 𝔽𝑝に対して𝑓 𝑣 = 𝑎1 + 𝑎2𝐿 mod 𝑟とする • 2行2列の整数係数行列𝐵 = (𝑏𝑖𝑗)で • det 𝐵 ≠ 0 • 𝑓 𝑣1 = 𝑓 𝑣2 = 0 for 𝑣𝑖 = (𝑏𝑖1, 𝑏𝑖2) • 𝑙𝑒𝑛 𝑣𝑖 ~𝑙𝑒𝑛(𝑛)/2 • 𝑥の分解方法 • 𝛾1, 𝛾2 = 𝑥, 0 𝐵−1 in ℚとする • 𝑐𝑖 = 𝐼𝑛𝑡(𝛾𝑖) ; 𝛾𝑖に一番近い整数とすると 𝑐1, 𝑐2 𝐵は(𝑥, 0)に近い • 𝑎1, 𝑎2 = 𝑥, 0 − 𝑐1, 𝑐2 𝐵とすると概ね𝑙𝑒𝑛 𝑎𝑖 は小さい • 𝑓 𝑎1, 𝑎2 = 𝑎1 + 𝑎2𝐿 = 𝑥 + 0𝐿 − 𝑐1, 𝑐2 𝐵 1 𝐿 = 𝑥 − 𝑐1, 𝑐2 𝑏11 + 𝑏12𝐿 𝑏12 + 𝑏22𝐿 ≡ 𝑥 mod 𝑟 𝑥の分解 16 /35
- 17. • 拡張Euclid互除法を使う • 𝑟と𝐿について𝑠𝑖𝑟 + 𝑡𝑖𝐿 = 𝑟𝑖 • 𝑠0𝑟 + 𝑡0𝐿 = 𝑟0 : (1 ⋅ 𝑟 + 0 ⋅ 𝐿 = 𝑟) • 𝑠1𝑟 + 𝑡1𝐿 = 𝑟1 : (0 ⋅ 𝑟 + 1 ⋅ 𝐿 = 𝐿) • 𝑟𝑖 > 𝑟𝑖+1 > ⋯ , 𝑟𝑖−1 𝑡𝑖 + 𝑟𝑖 𝑡𝑖−1 = 𝑟 • 𝑚を𝑟𝑚 > 𝑟となる最大の𝑚として 𝑣1 = 𝑟𝑚+1, −𝑡𝑚+1 , 𝑣2 = (𝑟𝑚, −𝑡𝑚)が望みのもの • 詳細は論文参照 行列𝐵の構築方法 17 /35
- 18. • Weilペアリング • 𝐸/𝔽𝑝 : 楕円曲線, 𝐺 = 𝐸 𝑟 = 𝑃 ∈ 𝐸 𝔽𝑝 𝑟𝑃 = 0 = Τ ℤ 𝑟ℤ 2 • 𝑒: 𝐺 × 𝐺 → 𝜇𝑟 ≔ {𝑥 ∈ 𝔽𝑝|𝑥𝑟 = 1}で次の性質を満たす • 𝑒 𝑃1 + 𝑃2, 𝑄 = 𝑒 𝑃1, 𝑄 𝑒(𝑃2, 𝑄) for 𝑃, 𝑃1, 𝑃2, 𝑄 ∈ 𝐺 • 𝑒 𝑃, 𝑃 = 1, 𝑒 𝑃, 𝑄 = 𝑒 𝑄, 𝑃 −1 • 注意 : 𝑃, 𝑄 ∈ 𝐺に対して適当な点𝑋, 𝑌 ∈ 𝐺をとり 𝑑𝑖𝑣 𝑓 = 𝑚 𝑋 + 𝑃 − 𝑚 𝑋 𝑑𝑖𝑣 𝑔 = 𝑚 𝑌 + 𝑄 − 𝑚 𝑌 となる関数𝑓, 𝑔 ∈ 𝔽𝑝(𝐸)をとると𝑒 𝑃, 𝑄 = 𝑓 𝑌+𝑄 𝑔 𝑋+𝑃 ⋅ 𝑔 𝑋 𝑓 𝑌 とかける • See "The Arithmetic of Elliptc Curves", Silverman • 𝑓(𝑌 + 𝑄)などの計算方法(Millerアルゴリズム)は今回は省略 ペアリング 18 /35
- 19. • 𝐺 = 𝐸[𝑟], 𝑃, 𝑄 ∈ 𝐺をfix • ECDLP : 𝑎𝑃, 𝑃 : givenに対して𝑎 ∈ 𝔽𝑟を求める • 𝑢 ≔ 𝑒 𝑎𝑃, 𝑄 = 𝑒 𝑃, 𝑄 𝑎 • もし𝑢と𝑒(𝑃, 𝑄)に対するDLPが解ければECDLPが解ける • ECDLPをDLPに帰着するためにペアリングを利用 • MOV(Menezes-Okamoto-Vanstone) reduction, 1990 • 帰着後のDLPが解けなければ暗号に利用可能 1999~ DLPとペアリングの関係 19 /35
- 20. • 暗号で使うには𝑓: 𝐺1 × 𝐺2 → 𝐺𝑇で • 𝑓 𝑃1 + 𝑃2, 𝑄 = 𝑓 𝑃1, 𝑄 𝑓 𝑃2, 𝑄 • 𝑓 𝑃, 𝑄1 + 𝑄2 = 𝑓 𝑃, 𝑄1 𝑓 𝑃, 𝑄2 を満たし、𝐺1, 𝐺2, 𝐺𝑇のDLPが困難なら概ね利用可能 • 𝐺1, 𝐺2は加法巡回群, 𝐺𝑇は乗法巡回群表記とする • Weilペアリングよりも計算効率がよいもの • Tateペアリング, ateペアリング, etc. • 𝐺𝑇の拡大次数がなるべく小さいもの • 有限体のDLPを解くコストとECDLPを解くコストの兼ね合い • 𝐺1 = 𝐺2 : 対称ペアリング • 𝐺1 ≠ 𝐺2 : 非対称ペアリング : より計算効率がよい • type 2 : 𝐺1と𝐺2の同型写像が計算しやすいもの • type 3 : 簡単に計算できる同型写像が知られていないもの ペアリングの亜種 20 /35
- 21. • 現在128bitセキュリティ相当で一番利用されている • 曲線 : 𝑦2 = 𝑥3 + 4 /𝔽𝑝 （𝑝は381bit素数で𝑝 mod 6 ≡ 1） • 𝐺1 = 𝐸[𝑟] （𝑝は255bit素数） • 𝜑: 𝐸 ∋ 𝑥, 𝑦 ↦ 𝑥′, 𝑦′ = 𝑥 𝑤2 , 𝑦 𝑤3 ∈ 𝐸′ = 𝑦′2 = 𝑥′3 + 4𝜉 • 𝜉 = 1 + 𝑖, 𝑣3 = 𝜉, 𝑤2 = 𝑣, 𝐺2 = 𝐸′ 𝔽𝑝2 𝑟 • 𝐺𝑇 = {𝑥 ∈ 𝔽𝑝12|𝑥12 = 1}, 𝔽𝑝12 = 𝔽𝑝6[𝑤], 𝔽𝑝6 = 𝔽𝑝3[𝑣] • 𝑒 𝑃, 𝑄 = 𝐹𝐸 𝑀𝐿 𝑃, 𝑄 • 𝑀𝐿 : 双線型性を持つMiller Loop関数, 𝐹𝐸 𝑥 = 𝑥𝑟0 : 固定べき • 安全性仮定（用途に応じていろいろ提案されている） • DDH(Decisional DH)仮定 • 𝐺𝑖 ∋ 𝑃, 𝑎𝑃, 𝑏𝑃, 𝑐𝑃に対し𝑎𝑏𝑃 = ? 𝑐𝑃を判定困難 • co-DHP*仮定 :𝑎𝑃1, 𝑄 ∈ 𝐺1, 𝑎𝑃2 ∈ 𝐺2に対して𝑎𝑄は計算困難 BLS12-381曲線(Barreto-Lynn-Scott) 21 /35
- 22. • 𝔽𝑝2 = 𝔽𝑝[𝑖] where 𝑖2 = −1 in 𝔽𝑝 • 𝑥 = 𝑎 + 𝑏𝑖, 𝑦 = 𝑐 + 𝑑𝑖の乗算 • 𝑥𝑦 = 𝑎 + 𝑏𝑖 𝑐 + 𝑑𝑖 = 𝑎𝑐 − 𝑏𝑑 + 𝑎𝑑 + 𝑏𝑐 𝑖 • 𝑎𝑑 + 𝑏𝑐 = 𝑎 + 𝑏 𝑐 + 𝑑 − 𝑎𝑐 − 𝑏𝑑 • 𝑋 = 𝑎𝑐, 𝑌 = 𝑏𝑑, 𝑍 = (𝑎 + 𝑏)(𝑐 + 𝑑)の乗算3回(Karatsuba) • 𝔽𝑝の乗算=𝑝ビット整数同士の乗算 + mod p • 本当はMontgomery乗算を使うがここでは省略 • コストは乗算よりmod pがやや重たい • 𝑋, 𝑌, 𝑍をmod pなしで計算(Mitsunari, et al. Pairing2010) • 𝑎𝑐 − 𝑏𝑑 = (𝑋 − 𝑌) mod p • 𝑎𝑑 + 𝑏𝑐 = (𝑍 − 𝑋 − 𝑌) mod p • mod pの処理が3回から2回に減る 𝔽𝑝2の演算の効率化 22 /35
- 23. • BLS12-381でのFrobenius写像 • 𝐹: 𝔽𝑝2 ∋ 𝑎 + 𝑏𝑖 ↦ 𝑎 + 𝑏𝑖 𝑝 = 𝑎 − 𝑏𝑖 because 𝑝 mod 4 = 3 • 𝐺2 = 𝐸′ 𝔽𝑝2 𝑟 に対するFrobenius写像 • 𝐹′ 𝑥′, 𝑦′ ≔ 𝜑𝐹𝜑−1 𝑥′, 𝑦′ = 𝜑𝐹 𝑥′/𝑤2, 𝑦′/𝑤3 = 𝜑൫ ൯ ( ) 𝑥′/ 𝑤2 𝑝 , 𝑦′ /𝑤3 𝑝 = 𝑥′𝑝 /𝑤2𝑝−2 , 𝑦′𝑝 /𝑤3𝑝−3 = (𝐹 𝑥′ 𝑔−2, 𝐹 𝑦′ 𝑔−3) where 𝑔 ≔ 𝑤 6 𝑝−1 6 = 𝜉 𝑝−1 6 • 𝐹′12 = 𝑖𝑑𝐺2 , 𝐹′ 𝑃 = 𝑧𝑃 where 𝑧 = -0xd201000000010000 • 𝑡 ∈ 𝔽𝑟（𝑙𝑒𝑛(𝑟)は256bit程度）に対して • 𝑡 = 𝑢0 + 𝑢1𝑧 + 𝑢2𝑧2 + 𝑢3𝑧3とすると𝑙𝑒𝑛 𝑢𝑖 ~64𝑏𝑖𝑡 • 𝑢0 ≔ 𝑡 mod 𝑧, 𝑢1 ≔ 𝑡−𝑢0 𝑧 mod 𝑧, ...で計算可能 • 𝑡𝑃 = 𝑢0𝑃 + 𝑢1𝐹′ 𝑃 + 𝑢2𝐹′2 𝑃 + 𝑢3𝐹′3(𝑃) 𝐺2のスカラー倍算(GLV method) 23 /35
- 24. • 𝐻𝑖: 0,1 ∗ → 𝐺𝑖をハッシュ関数とする • 𝑃𝑖を𝐺𝑖の生成元を共有 • 𝑒 ≔ 𝑒 𝑃1, 𝑃2 ∈ 𝐺𝑇とすると 𝑒 = 𝐺𝑇 • 鍵生成 • 𝑠 ∈ 𝔽𝑟を署名鍵として𝑆 = 𝑠𝑃2 ∈ 𝐺2を検証鍵とする • 検証鍵は検証者に配布する（公開鍵） • 署名 • メッセージ𝑚に対して𝜎 = 𝑠𝐻1 𝑚 ∈ 𝐺1が署名 • 検証 • メッセージ𝑚と署名𝜎と検証鍵𝑆に対して • 𝑒(𝐻1 𝑚 , 𝑆) = ? 𝑒(𝜎, 𝑃2)を確認する • validなら左辺=𝑒 𝐻1 𝑚 , 𝑠𝑃2 = 𝑒 𝑠𝐻1 𝑚 , 𝑃2 =右辺 BLS署名(Boneh–Lynn–Shacham) 24 /35
- 25. • 攻撃者が知り得るもの • 公開パラメータ𝑃1, 𝑃2 • 検証鍵𝑆 = 𝑠𝑃2 • 過去の署名 𝑚に対する𝜎 = 𝑠𝐻1(𝑚) • 偽造したいもの • 𝑚′ ≠ 𝑚で𝜎′ = 𝑠𝐻1(𝑚′) • それを作れたとしたら • 𝐻1 𝑚′ = 𝑡𝐻1(𝑚)となる𝑡は分からない • ECDLPとハッシュ関数の"ランダムさ" • 𝑠𝐻1 𝑚 , 𝑠𝑃2, 𝐻1(𝑚′) から𝜎′ = 𝑠𝐻1(𝑚′)が作れたことになる • co-DHP*の困難さを破れることになる BLS署名の安全性の根拠（の雰囲気） 25 /35
- 26. • 𝑒(𝐻1 𝑚 , 𝑆) = ? 𝑒(𝜎, 𝑃2) • 𝑒 𝑃, 𝑄 = 𝑀𝐿 𝑃, 𝑄 𝑟0 : 𝑀𝐿は双線型性を持つ • 𝑒 𝐻1 𝑚 , 𝑆 = 𝑒 𝜎, 𝑃2 ⇔ 𝑒 𝐻1 𝑚 , 𝑆 𝑒 𝜎, −𝑃2 = 1 ⇔ 𝐹𝐸 𝑀𝐿 𝐻1 𝑚 , 𝑆 𝑀𝐿 𝜎, −𝑃2 = 1 • 演算コスト𝑀𝐿 ∶ 𝐹𝐸 = 1: 1.4なので40%の高速化 検証部分 26 /35
- 27. • 𝑓 𝑥 = 𝑓0 + 𝑓1𝑥 + ⋯ + 𝑓𝑘−1𝑥𝑘−1 ∈ 𝔽𝑟[𝑥] : 𝑘 − 1次多項式 • 𝑛個の相異なる𝑥1, … , 𝑥𝑛に対して𝑦𝑖 = 𝑓(𝑥𝑖)とする • ここから任意の相異なる𝑘個のペア 𝑥𝑖𝑎 , 𝑦𝑖𝑎 1 ≤ 𝑎 ≤ 𝑘 を取る • 𝑦𝑖1 ⋮ 𝑦𝑖𝑘 = 1 ⋯ 𝑥𝑖1 𝑘−1 ⋮ ⋱ ⋮ 1 ⋯ 𝑥𝑖𝑘 𝑘−1 𝑓0 ⋮ 𝑓𝑘−1 = 𝐴 𝑓0 ⋮ 𝑓𝑘−1 • 𝐴 = 𝑥𝑖𝑎 𝑏 はdet 𝐴 ≠ 0なので (𝑦𝑖𝑎 )から(𝑓𝑖)が求まる • 秘密分散 • 𝑓0を秘密とする • 𝑓1, … , 𝑓𝑘−1をランダムに選び𝑛個のペア 𝑥𝑖𝑎 , 𝑦𝑖𝑎 = 𝑓(𝑥𝑖𝑎 ) を作る • そのうち𝑘個のペアで𝑓0を復元できる • 𝑘 − 1以下なら不可能（𝑓0の取り得る可能性は𝔽𝑟全て） Lagrange補間 27 /35
- 28. • 単なる秘密分散は一度しか使えない • BLS署名の検証鍵𝑠𝑃2, 署名𝑠𝐻1(𝑚) • BLS署名の署名鍵𝑠を秘密分散する • 𝑓 𝑥 = 𝑠 + 𝑓1𝑥 + ⋯ + 𝑓𝑘−1𝑥𝑘−1 : 𝑘次多項式（𝑓𝑖はランダム） • 𝑥1, … , 𝑥𝑛に対して署名鍵𝑠𝑖 = 𝑓(𝑥𝑖)をユーザ𝑥𝑖に配布する • 検証鍵𝑠𝑃も公開 • 𝑠𝑖𝑃2が各自の検証鍵 • 𝑚に対する各自の署名𝑠𝑖𝐻1(𝑚) • 𝑛人が署名𝑠𝑖𝐻1(𝑚)を公開 • 検証して𝑘個集まれば𝐴−1 𝑠𝑖𝑎 𝐻1 𝑚 により𝑠𝐻1(𝑚)を復元 • 𝑠𝑃で検証可能 • 「多数決」に利用可能 BLS署名と秘密分散 28 /35
- 29. • 複数の署名を一つにまとめる • 検証コストを下げる • 検証に必要な署名のデータ量を減らす • BLS multi-signatures with public-key aggregation, 2018 • https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html • 𝐻2: 𝐺2 𝑛 → 𝔽𝑟 𝑛 : 𝑛個ハッシュ関数 • 鍵生成 : 𝑠𝑖 ∈ 𝔽𝑟 ; 署名鍵, 𝑆𝑖 = 𝑠𝑖𝑃1 ∈ 𝐺1 ; 検証鍵 • 署名 : 𝜎𝑖 = 𝑠𝑖𝐻1(𝑚) • 𝑛個の𝑚に対する署名{𝑆𝑖, 𝜎𝑖}を集約する • 𝑡1, … , 𝑡𝑛 ← 𝐻2(𝑆1, … , 𝑆𝑛), 𝜎 ≔ σ𝑖 𝑡𝑖𝜎𝑖 • 𝑆𝑖 , 𝑚, 𝜎に対する検証 • 𝑡1, … , 𝑡𝑛 ← 𝐻2(𝑆1, … , 𝑆𝑛), 𝑒 𝑃1, 𝜎 = 𝑒(σ𝑖 𝑡𝑖𝑆𝑖 , 𝐻1 𝑚 ) 集約署名 29 /35
- 30. • 𝑛個のメッセージ𝑚𝑖に対する検証鍵𝑆𝑖と署名𝜎𝑖 • 𝐹𝐸 𝑀𝐿 𝐻1 𝑚𝑖 , 𝑆𝑖 𝑀𝐿 𝜎𝑖, −𝑃2 = 1 for all 𝑛 ※ • 普通にやると 2𝑀𝐿 + 1𝐹𝐸 × 𝑛の検証コスト • 乱数を使うトリック • 𝑟1, … , 𝑟𝑛を乱数として1/|𝑟𝑖|の確率を除いて※が成立する ⇔ 𝐹𝐸 ෑ 𝑖 𝑀𝐿 𝐻1 𝑚𝑖 , 𝑆𝑖 𝑟𝑖𝑀𝐿 𝜎𝑖, −𝑃2 𝑟𝑖 = 1 ⇔ 𝐹𝐸 ෑ 𝑖 (𝑀𝐿 𝐻1 𝑚𝑖 , 𝑟𝑖𝑆𝑖 𝑀𝐿 𝑖 𝑟𝑖𝜎𝑖, −𝑃2 = 1 • 検証コスト 𝑛 + 1 𝑀𝐿 + 1𝐹𝐸 + 𝑛𝑀𝑈𝐿2+𝑛𝑀𝑈𝐿𝑆𝑈𝑀1 • 𝑟𝑖 ~264程度だとFE>(G1-mul + G2-mul)なので速くなる 複数の署名をまとめて検証する 30 /35
- 31. • 𝑄 = σ𝑖 𝑥𝑖𝑃𝑖の形の演算が割と出てくる • ここではMULSUMと呼ぶことにする • マルチスカラー倍算の考察からコストはDBL+(n/const)ADD • もう少し改善したい • {𝑥𝑖}が小さいときを考える • 例 : 2𝑃1 + 𝑃2 + 3𝑃3 + 2𝑃4 + 2𝑃5 + 3𝑃6 + ⋯ = 𝑃2 + ⋯ + 2 𝑃1 + 𝑃4 + 𝑃5 + ⋯ + 3 𝑃3 + 𝑃6 + ⋯ + 4(… • 𝑥𝑖が同じものをグルーピングする • 𝑛が大きくなるほど効果が高くなる MULSUMの高速化 31 /35
- 32. • 𝑧 ← σ𝑖=0 𝑛−1 𝑥𝑖𝑃𝑖の擬似コード • 𝐿 : max 𝑙𝑒𝑛 𝑥𝑖 • 𝑐 : まとめるテーブルのビット長 • 𝑁 = 2𝑐 : テーブルT[𝑁]のサイズ, 𝑀 = 𝐿 𝑐 : 区切った個数 • 𝑇 𝑖 ← 0 for all 𝑖 • for 𝑤 from 0 to 𝑀 − 1 • for 𝑖 from 0 to 𝑛 − 1 • 𝑣 ← 𝑥𝑖の𝑐𝑤から𝑐ビットの値 • T[𝑣] ← 𝑇 𝑣 + 𝑃𝑖 // 𝑣倍される𝑃𝑖を集める • 𝑠𝑢𝑚 ← 0, 𝑊[𝑤] ← 0 • for 𝑖 from 0 to 𝑁 • 𝑠𝑢𝑚 ← 𝑠𝑢𝑚 + 𝑇[𝑁 − 𝑖] • 𝑊 𝑤 ← 𝑊 𝑤 + 𝑠𝑢𝑚 MULSUMの概要(1/2) 𝑥𝑖 𝑐 𝑣 𝑊 𝑤 = ⋯ + 𝑇 𝑁 − 2 + 𝑇 𝑁 − 1 + 𝑇 𝑁 + 𝑇 𝑁 − 1 + 𝑇 𝑁 + 𝑇 𝑁 = 𝑇[1] + 2𝑇[2] + 3𝑇 3 + ⋯ ← 𝑤番目 32 /35
- 33. • 続き • 𝑊 𝑤 = 𝑤番目の𝑥𝑖達の𝑃𝑖のスカラー倍の和 • 𝑍 ← 0 • for 𝑤 from 0 to 𝑀 − 1 • 𝑍 ← 2𝑐𝑍 + 𝑊[𝑀 − 1 − 𝑤] • 演算コスト • 𝐿 : 𝑥𝑖の最大ビット(e.g., 256), 𝑁 = 2𝑐 , 𝑀 = 𝐿/𝑐 • ADD : 𝑀 𝑛 + 2𝑁 + 𝑀 = Τ 𝐿(𝑛 + 2𝑐+1 + 1) 𝑐, DBL : 𝐿 • ADDのコストが最小になる𝑐 • （適当に見つけた）近似値𝑐min = 𝑖𝑛𝑡(log2 𝑛 − log2(log2 𝑛)) • 𝑛~229ぐらいまでで誤差±1ぐらい • 余談 : int(log2 𝑛)は𝑛の2進数表記の左から初めて1がある位置 • 𝑛 = 1024なら𝑐 = 8（𝑛 ≈ 64(GLV適用前)が速度の分岐点） MULSUMの概要(2/2) 𝑥𝑖 𝑐 𝑣 ← 𝑤番目 33 /35
- 34. • 楕円曲線の加算𝑃 + 𝑄 • 片方の点がAffine座標と分かっていれば加算を効率よくできる • [𝑥: 𝑦: 𝑧]の𝑧を1にできる • しかしJacobi/Proj→Affineは除算が入るので遅い • mul : div = 1:100 • 複数の逆数をまとめて処理 • 𝑎, 𝑏の逆数 Τ 1 𝑎 , Τ 1 𝑏は Τ 𝑏 𝑎𝑏, Τ 𝑎 𝑎𝑏なので1/𝑎𝑏の逆数1回で計算 • {𝑥1, 𝑥2, 𝑥3, 𝑥4}に対して • 𝑇[] = {𝑥1, 𝑥1𝑥2, 𝑥1𝑥2𝑥3, 𝑥1𝑥2𝑥3𝑥4}, 𝑟 ← 𝑥1𝑥2𝑥3𝑥4 −1 • Τ 1 𝑥4 = 𝑥1𝑥2𝑥3 𝑟, 𝑟 ← 𝑟𝑥4 = 𝑥1𝑥2𝑥3 −1 Τ 1 𝑥3 = 𝑥1𝑥2 𝑟, 𝑟 ← 𝑟𝑥3 = 𝑥1𝑥2 −1 Τ 1 𝑥2 = 𝑥1 𝑟, 𝑟 ← 𝑟𝑥1 = 𝑥1 −1 • 𝑛回逆数が「 2(𝑛 − 1)回の乗算+1回除算」になる 複数の除算とAffine化の高速化 34 /35
- 35. • 暗号の実装では • 代数的な構造を利用したアルゴリズムの改良 • 特定の環境の演算コストに応じた組合せ論的最適化 • 乱数を用いた確率的アルゴリズムの導入（やや飛び道具） • などを組み合わせる まとめ 35 /35