TFHE実装入門

2.TRLWE & SampleExtarctIndex

松岡　航太郎

説明内容のHomNANDでの位置づけ

TRLWEとは

• Torus Ring-LWEの略
• TLWEは平文がスカラーだったが、TRLWEでは多項式になる
• Ringは多項式『環』の上で定義することから来ている
  • 課題でやってもらった多項式の剰余演算が出てくる
  • 厳密にはTorus係数多項式だと環じゃない気もしないでもない

多項式環

• とする
• TRLWEで使う多項式環はTorusを係数とする多項式をで割った余りが成す剰余環である
• この多項式環をと表記する
• Torus同士の乗算は定義できないので当然の元同士の積は定義できない
• 整数とTorusの乗算は定義できるので、の元との積は定義できる

多項式環上の乗算

• この処理がTFHEで一番重い処理なので高速化したいならここを高速化すべき
  • FFT(高速フーリエ変換)かNTT(数論変換)を使って実装するのが知る限り最速
• ここではナイーブな実装を扱う(知る限り最適な実装は7章で扱う)
• 普通に２つの元を掛け算したあと、剰余を取って、係数の小数部に相当する部分を抜き出せば良い
• 入力をとする
• である

for i from 0 to N-1
  cᵢ = 0
for i from 0 to N-1
  for j from 0 to N-1
    if i+j<N
      cᵢ₊ⱼ += aᵢ⋅bⱼ
    else
      cᵢ₊ⱼ₋ₙ -= aᵢ⋅bⱼ (Nの下付きが打てないのでₙになっている)

TRLWEの具体的構成(平文がの場合)

• 暗号の安全性を決めるパラメータは3つで
  • 厳密にはの場合のみがTRLWEでの場合はTMLWEと呼ぶべきか
    • 本講義ではTRLWEと一緒くたに呼ぶ
• とする
• が平文、,,とする
• TRLWEの暗号文はとして、という次の多項式要素のベクトルである
• になるので、このをどうにかして削除する方法を加えるとがとれて復号できる
• を大きくすればするほど安全(は大きくしすぎると暗号文が壊れる)
• 同じ安全性、同じデータならTLWEよりTRLWEの方がサイズが小さい(と信じられている)

TRLWEの加法準同型性

• TLWEとTRLWEはよく似ているので加法準同型性も同じように成り立つ
• ２つの暗号文を考える
• その和をとする
• になり、が出てくるので加法準同型になっている
• TLWEよりサイズが小さいのでより高速に加算ができることになる(SIMDライク)

TRLWEの具体的構成(平文がの場合)

• これもTLWEと似た形
• とする
• である
• TRLWEの暗号文は
• 復号は(は符号関数で各係数に作用)

SampleExtractIndex

• TRLWEを個のTLWEに分解する操作
• 平文に対しての操作で言うと、多項式の係数を取り出す操作に相当する
• 1.で話したTLWEはの要素は個だがここでは個
  • 区別が必要なときは前のをTLWElvl0、今のをTLWElvl1と以降呼ぶ
• 鍵も2本あることに注意
  • 2本の鍵に依存関係を持たすとちょっと計算楽になったりはする
    • https://eprint.iacr.org/2023/979
    • https://eprint.iacr.org/2023/958
  • が、とりあえず一般の場合として独立なものとして扱う
• TLWEが破れるならTRLWEが破れることを意味するので安全性の意味でも大事

SampleExtractIndexの具体的構成(数式表現)

• 基本的には復号の一部をぐっと睨むと出てくるので表現を変えてみてみる

• 3つ目ので中の掛け算にマイナスがついてるのは剰余環の上の演算だから
• 基本的な発想はを一つの値に固定すること
• そうすると平文の多項式の項を表現するTLWEが以下のようになることが分かる

SampleExtractIndexの具体的構成(疑似コード表現)

SampleExtractIndex((𝐚[X],b[X]),x)
  b̄ = bₓ
  𝐚̄ = 0
  for j from 0 to k-1
    for i from 0 to x
      āⱼᵢ = aⱼ₍ₓ₋ᵢ₎
    for i from x+1 to N-1
      āⱼᵢ = -aⱼ₍ₙ₊ₓ₋ᵢ₎ //下付きにできないのでNが小文字になっている
  return (𝐚̄,b̄)

TRLWEのパラメータについて

• 実はTRLWEの安全性を直接推定する方法は知られていない
  • TRLWEに入っている環の構造を利用した攻撃が知られていないため
  • 安全性の推定はTLWEに変換して行われている(十分条件による弱い推定)

なぜなのか

• 実のところでなければならないわけではない
• 因数分解できてしまうとが小さなTRLWEに分解できてしまって明らかに脆弱
• はが2のべきなら因数分解できない
  • 円分多項式の一種
  • 円分多項式であれば安全性の証明も破綻しない
    • https://eprint.iacr.org/2012/230
• 非ゼロの項も2つしかないので剰余がとりやすい
  • 3つしか無い2と3だけが因数のケースも使われたりはする
• 7.で見るようにFFT/NTTによる高速化ができるのも利点

TRLWEで最低限実装すべきもの

• 暗号化と復号は平文をバイナリ係数多項式に限定した場合だけできればよい
• SampleExtractIndexはの場合しか使わない
• 暗号文同士の加算は後で使うので、ベクトルっぽい加算がしやすいようにデータを保持しておくと良い
• パラメータは後で簡単に変更できるように書いておいた方が汎用性は高い

参考文献

• である理由
• Ring LWE等の安全性reduction