数論変換周りの話

京都大学大学院情報学研究科情報学専攻通信情報システムコース
佐藤研究室(集積回路) D2 (DC1)
2019年度未踏 準同型暗号によるバーチャルセキュアプラットフォーム
松岡　航太郎

自己紹介的なもの

• 準同型暗号(暗号のまま計算ができる暗号)が専門
  • 今日の話も準同型暗号と密接に関わりのある話
• 研究室は集積回路
  • 今準同型暗号を高速化できるハードウェアを作ったりしてる
• 京都大学工学部電気電子工学科卒　特色入試
• 東京都立戸山高等学校卒
• 京都大学機械研究会 (2019年 NHKロボコン優勝)

多項式乗算はおそすぎる!

• 多項式乗算はnaïveにやるとO(N²)のオーダ
  • 準同型暗号では多項式の演算はたくさん出てくる
    • これを速くすると全体が早くなる
  • 今日の話は多項式乗算を高速化した人々の成果の話
• Background: RLWEと呼ばれる暗号形式において最も遅い演算
  • 準同型暗号で広く用いられる
  • 鍵交換プロトコルであるCrystal Kyber (NIST FIPS 203)などでも利用
  • もちろん円周率の計算などの多倍長計算でも使う

オーダの限界はどこ?

• David Harvey(あとでもっかい出てくる)らが2019年に証明
  • Integer multiplication in time O(n log n)
  • ※多項式に基数を代入したら整数になるので多項式乗算と整数乗算はほぼ同じもの
• 現実的にはもうちょっと大きいオーダのものを使う
  • 基本的には離散フーリエ変換の仲間を使って計算をする
    • 上の論文もそう

離散フーリエ変換とは

• フーリエ変換(DFT: Discrete Fourier Transform)を離散化したもの
  • フーリエ変換は時間信号を複数の周波数成分に分解する処理
  • ここでは多項式乗算に転用するだけなのでフーリエ変換については割愛
• 入力となる多項式を、出力をとしよう
• このとき離散フーリエ変換は以下のように与えられる
• 指数の符号は逆でもいい
• は回転因子とよぶ

逆離散フーリエ変換

• フーリエ変換の重要な性質として、逆変換が存在することがある
  • 離散フーリエ変換でも逆変換がありInverse DFT (IDFT)という
    • 定数倍と指数の符号くらいしか変わらない

畳み込み定理

• フーリエ変換の重要な性質として畳み込み定理がある
  • 畳み込みはConvolutionなのでCNNのCと一緒
• これはフーリエ変換をした結果(周波数成分)の要素ごとの積をとったものの逆変換が入力の畳み込みになっているという定理
• 離散フーリエ変換での畳み込み定理がを法とする多項式乗算になる
• つまり、が以下と同値になる
  • DFTは高速フーリエ変換(FFT: Fast Fourier Transform)でO(NlogN)で計算できる

DFT(というかFFT)の欠点

1. 精度に限界がある

• 倍精度浮動小数点数は53bitしか精度がない
• 入力となる多項式の係数が大きくなるとOverflow
  • 余談: 準同型暗号の文脈だとこれを避ける方法はなくはない
    　- Accelerating HE Operations from Key Decomposition Technique

2. 倍精度浮動小数点はHardware実装が難しい

• 倍精度浮動小数点演算器は実装コストが大きい
  • GPUでも基本的に倍精度は性能が低い

3. 固定小数点化しても演算誤差がある

• 最悪の場合Overflowを起こすと大きな誤差に
• bitのすべてを値の表現に使えるとは限らなず精度も下がる

複素数でないフーリエ変換

• 余談:一般にはポントリャーギン双対があるとフーリエ変換が定義される
• DFT以外でよく使われるのは下の2つ

1. Nussbaumer Transform

• Fast polynomial transform algorithms for digital convolution
• 多項式のの冪を回転因子(乗したら1)として使う方法
  • 実は計算量が最小になるアルゴリズムもこれベース
• 回転因子の計算が要素のcyclic shiftになるので扱いづらい

2. 今日の主役: 数論変換(NTT: Number Theoretic Transform)

• 複素数の代わりに剰余環()上の値を使う
• 複素正弦波の代わり原始乗根を使う
  • 乗した時に初めてになる数字のこと(フェルマーの小定理)

NTTってFFTより重いんじゃない?

1. 剰余演算が重い

• 普通に考えるとは割り算になるはず

2. 一般には2基底(1度に2分割)までしか高速な再帰分割がない

• FFTなら8基底までできる
  • (45度)の整数倍複素正弦波が計算しやすい形
• 原始根は一般にはそういうのがない

NTTの高速化手法

1. 剰余演算が重い

• 除算を使わない剰余アルゴリズムがある
  • 代表的なのはMotgomeryとBarret
  • 最近Plantardが増えた

2. 一般には2基底(1度に2分割)までしか高速な再帰分割がない

• 特別な法であれば4基底以上が可能
  • や

Montgomery Reduction (1985年)

• RSA暗号の計算のべき乗によく使われる
• を2冪の値とする
• 入力に対しが返ってくる
• q' =
• をかけた状態にしてから適用する必要がある
  • アルゴリズム全体の修正が必要
• bit同士の乗算が2回ある

m ← ((a mod R) q') mod R
t ← (a + mq)/R //右シフト
return  t ≥ q ? t - q : t

Signed Motgomery Reduction (2018年)

• 通常のMontgomeryは入力が正整数しか取れない
  • 減算を計算したい場合面倒
• に対しが返ってくる
• と下位と上位にわける

m ← a₀q' mod R
t ← ⌊mq/R⌋ //乗算の上位だけでよい
return a₁ - t

Barret Reduction (1986)

• アイデアとしては除算を逆数との積に置き換える
• とする
• に対しが返ってくる
• bitとbitの乗算が1回とbit同士の乗算が1回
  • 一般にはMontgomeryより重い
  • NTTで使う場合には定数との掛け算をするので改良ができる

t ← a - q⋅⌊ar/R⌋
return  t ≥ q ? t - q : t

(再びの)Harvery's Algorithm (2014)

• NTTのバタフライ演算とBarret Reductionをくっつけることで演算を減らす
  • がの中にあり, $$
• NTLで使われているShoup's algorithmの改良
  • 現在最も広く使われている(Intel HEXLなど)
• 回転因子は定数なのでそこに割り算を埋め込んでおく

Plantard Reduction (2021)

• Efficient word size modular arithmetic
• の乗算が前提のReduction
• は2冪で
• 一般にはRの積2回(1回は入力の積)とR²の積1回
  • Barretより重い
• Bが定数だとを先に計算できる(が1回ととが1回)
  • のかけ算1回の方がのかけ算2回より早いとき有利(Rが16bit以下の時とか)

C ← ⌊((⌊(ABq' mod R²)/R⌋+1)q)/R⌋
return C==q ? 0 : C

Signed Plantard Reduction (2022)

• Efficient Word Size Modular Multiplication over
  Signed Integers
• Signed Montgomeryと動機は同じ

Reductionのまとめ

1. Montgomery

• が掛ってしまうのでアルゴリズム全体の修正が必要
• 大体の場合で軽め(の乗算が2回)

2. Barret(Harvey)

• 大きめのかけ算が必要, 一般にMontgomeryより遅いが表現の変更は不要
  • (との乗算が1回との乗算が1回)
• NTTだと定数乗算しかないので改善できる(の乗算が2回)
  • 実はメモリ的には定数2倍送らないと行けないのでその点は不利

3. Plantard

• 入力の乗算を除くとの乗算が1回
  • 組み込みプロセッサで小さな法を扱うとき(耐量子計算機暗号の一部など)早い

特別な法

• 一般に2基底しかできないのは原始根の乗との積が計算しにくいから
  • FFTだと乗は,乗は
• 逆に言えばそういう特別な原始根があるような法なら高速に計算できる
  • ここではとを紹介
    • どちらもSolinas Primeに分類される

• この数字はGoldilocks primeの一つでもある
  • Ed448-Goldilocks, a new elliptic curve, 2015年
• 形を見ればわかるとおりReductionが非常に簡単
• 
  　- 基底まで左シフトで実装できる
• zkEVM, Plonky2, 0xPolygonなんかでもこの法をつかっているらしい

• 最近自分の研究で使っている数字
  • Montgomery Friendry Primeに分類できる
    • Montgomery-friendly primes and applications to cryptography
    • Reductionが簡単なことは知られているが回転因子としての性質の良さは利用されていなかったらしい?
• • が乗算の計算しやすい値なら高速に計算できる
  • 基底までできる
  • 例: が使える
• • Montgomeryのがにとれるので簡単

特別な法の場合のまとめ

• • 64基底までできる広く使われている法
    • 乗算がシフトに変換できてうれしい
  • 64bitなので過剰すぎる場合がある
    • AVX512-IFMAにも収まらない
• • 基底までとれる
  • 32bitより小さい場合も使える
    • 大きな数字の場合も存在するかは不明
  • との掛け算は消えないのでハードウェア向け

数論変換の今後

• NIST PQCにRLWE(の正確には拡張)が選定された以上今後研究が進むと期待される
  • RSAなど既存の暗号に比べ用いる法が小さいなどの特徴がある
    • Plantardアルゴリズムのような最適化が今後も出てくるかも？
  • 使用する法の形も特定のものに固定可能
    • NIST PQCはもう規格化段階なので変えられない
    • 準同型暗号など他のRLWEベースのものはまだ自由度がある
    • より優れた法の探索の研究も進む?