数論変換における最新の研究動向

京都大学 佐藤研究室 D1 松岡　航太郎

普段の研究

• 準同型暗号が専門
  • 暗号のまま計算ができる暗号
  • 今日の話も準同型暗号と密接に関わりのある話
• 研究室は集積回路
  • 今準同型暗号を高速化できるハードウェアを作ったりしてる
  • 1月にASP-DAC(韓国)でしゃべる
• 京都大学工学部電気電子工学科卒　特色入試
• 東京都立戸山高等学校卒
• 2019年度未踏スーパークリエータ
• 京都大学機械研究会

• Kotaro Matsuoka, Ryotaro Banno, Naoki Matsumoto, Takashi Sato, & Song Bian. (2020). Virtual Secure Platform: A Five-Stage Pipeline Processor over TFHE.
• Kotaro Matsuoka, Yusuke Hoshizuki, Takashi Sato, & Song Bian. (2021) Towards Better Standard Cell Library: Optimizing Compound Logic Gates for TFHE.
• Ryotaro Banno, Kotaro Matsuoka, Naoki Matsumoto, Song Bian, Masaki Waga, & Kohei Suenaga. (2022). Oblivious Online Monitoring for Safety LTL Specification via Fully Homomorphic Encryption.
• Kotaro Matsuoka, Yasutomo Yushima, Ryo Hayakawa, Riho Kawasaki, Kazunori Hayashi, Megumi Kaneko, An RFID tag identification protocol via Boolean compressed sensing

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

• 多項式乗算はnaïveにやるとO(N²)のオーダ
  • 準同型暗号では多項式の演算はたくさん出てくる
    • これを速くすると全体が早くなる
  • 今日の話は多項式乗算を高速化した人々の成果の話

オーダの限界はどこ?

• 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
• 多項式のの冪を回転因子として使う方法
  • 実は計算量が最小になるアルゴリズムもこれベース
• 回転因子の計算が要素のcyclic shiftになるので扱いづらい

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

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

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

1. 剰余演算が重い

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

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

• FFTなら8基底までできる

NTTの高速化手法

1. 剰余演算が重い

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

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

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

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

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

• NTLで使われているShoup's algorithmの改良
  • 現在最も広く使われている(Intel HEXLなど)
• 回転因子は定数なのでそこに割り算を埋め込んでおく
• 大きな桁のかけ算がない(が3回で1回分は入力のかけ算)

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

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のがにとれるので簡単

他にいい感じの法あるの?

• Reductionが効率的な法は知られている
  • 競技プログラミングとかで使われがち
  • 基底も大きくできるやつみつけたら教えてください