TFHE実装入門

2.TRLWE & SampleExtarctIndex

松岡　航太郎

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

TRLWEとは

  • Torus Ring-LWEの略
  • TLWEは平文がスカラーだったが、TRLWEでは多項式になる
  • Ringは多項式環の上で定義することから来ている
  • ナイーブな実装だと課題でやってもらった多項式の剰余演算が出てくる

多項式環

  • N∈N+N∈\mathbb{N}^+とする
  • TRLWEで使う多項式環はTorusを係数とする多項式をXN+1X^N+1で割った余りが成す剰余環である
  • この多項式環をTN[X]\mathbb{T}_N[X]と表記する
  • Torus同士の乗算は定義できないので当然TN[X]\mathbb{T}_N[X]の元同士の積は定義できない
  • 整数とTorusの乗算は定義できるので、ZN[X]\mathbb{Z}_N[X]の元との積は定義できる

多項式環上の乗算

  • 実はこの処理がTFHEで一番重い処理なので高速化したいならここを高速化すべき
  • FFT(高速フーリエ変換)かNTT(数論変換)を使って実装するのが知る限り最速
  • ここでは課題と関連のあるナイーブな実装を扱う
  • 普通に２つの元を掛け算したあと、剰余を取って、係数の小数部に相当する部分を抜き出せば良い
  • 入力をa[X]∈TN[X],b[X]∈ZN[X]a[X]∈\mathbb{T}_N[X],b[X]∈\mathbb{Z}_N[X]とする
  • a[X]=∑i=0N−1aiXi,ai∈Ta[X]=\sum_{i=0}^{N-1}a_iX^i,a_i∈\mathbb{T}である
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の具体的構成(平文がTN[X]\mathbb{T}_N[X]の場合)

  • 暗号の安全性を決めるパラメータは２つでN∈Z+,αbk∈R+N∈\mathbb{Z}^+,α_{bk}∈\mathbb{R}^+
  • a[X]∈TN[X],e[X],b[X]∈TN[X],s[X]∈BN[X],m[X]∈TN[X]a[X]∈ \mathbb{T}_N[X], e[X],b[X]∈ \mathbb{T}_N[X], s[X]∈ \mathbb{B}_N[X],m[X]∈ \mathbb{T}_N[X]とする
  • m[X]m[X]が平文、a[X]←UTN[X]a[X]←U_{\mathbb{T}_N[X]},e[X]←DTN[X],αbke[X]←\mathcal{D}_{\mathbb{T}_N[X],α_{bk}},s[X]←UBN[X]s[X]←U_{\mathbb{B}_N[X]}とする
  • TRLWEの暗号文はb[X]=a[X]⋅s[X]+m[X]+e[X]b[X]=a[X]⋅ s[X]+ m[X] +e[X]として、(a[X],b[X])(a[X],b[X])というN−1N-1次の多項式2要素のベクトルである
  • b[X]−a[X]⋅s[X]=m[X]+e[X]b[X]-a[X]⋅s[X]=m[X]+e[X]になるので、このe[X]e[X]をどうにかして削除する方法を加えるとm[X]m[X]がとれて復号できる
  • N,αbkN,α_{bk}を大きくすればするほど安全(αbkα_{bk}は大きくしすぎると暗号文が壊れる)
  • 同じ安全性、同じデータならTLWEよりTRLWEの方がサイズが小さい

TRLWEの加法準同型性

  • TLWEとTRLWEはよく似ているので加法準同型性も同じように成り立つ
  • ２つの暗号文(a[X]1,b[X]1),(a[X]2,b[X]2)(a[X]_1,b[X]_1),(a[X]_2,b[X]_2)を考える
  • その和を(a[X]1+a[X]2,b[X]1+b[X]2)(a[X]_1+a[X]_2,b[X]_1+b[X]_2)とする
  • b1[X]+b2[X]−(a1[X]+a2[X])⋅s[X]=m1[X]+m2[X]+e1[X]+e2[X]b_1[X]+b_2[X]-(a_1[X]+a_2[X])⋅s[X]=m_1[X]+m_2[X]+e_1[X]+e_2[X]になり、m1+m2m_1+m_2が出てくるので加法準同型になっていることが分かる
  • TLWEよりサイズが小さいのでより高速に加算ができることになる(SIMDライク)

TRLWEの具体的構成(平文がBN[X]\mathbb{B}_N[X]の場合)

  • これもTLWEと似た形
  • m[X]∈B[X],μ=1/8∈Tm[X] ∈ \mathbb{B}[X],μ=1/8\in\mathbb{T}とする
  • (μ(2⋅m[X]−1[X])∈TN[X])(μ(2⋅ m[X]-1[X])∈\mathbb{T}_N[X])である
  • TRLWEの暗号文はb[X]=a[X]⋅s[X]+μ(2⋅m[X]−1[X])+e[X]b[X]=a[X]⋅ s[X]+μ(2⋅ m[X]-1[X])+e[X]
  • 復号は(1+sgn(b[X]−a[X]⋅s[X]))/2(1+\mathit{sgn}(b[X]-a[X]⋅ s[X]))/2である。(sgn\mathit{sgn}は符号関数で各係数に作用)

SampleExtractIndex

  • TRLWEをNN個のTLWEに分解する操作
  • 平文に対しての操作で言うと、多項式の係数を取り出す操作に相当する
  • 1.で話したTLWEはa\mathbf{a}の要素はnn個だがここではNN個
  • 同じTLWEだが区別が必要なときは前のをTLWElvl0、今のをTLWElvl1と以降呼ぶ
  • 鍵も2本あることに注意
  • これはTLWEが破れるならTRLWEが破れることを意味するので安全性の意味でも大事

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

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

b[X]−a[X]⋅s[X]=∑k=0N−1[bk−(∑i+j=k,0≤i,j≤N−1ai⋅sj)−(∑i+j=N+k,0≤i,j≤N−1−ai⋅sj)]Xkb[X]-a[X]⋅ s[X]=∑^{N-1}_{k=0} [b_k-(∑_{i+j=k,0≤i,j≤N-1}a_i⋅s_j)-(∑_{i+j=N+k,0≤i,j≤N-1}-a_i⋅s_j)]X^k

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

b′=bkai′={ak−i if i≤k−aN+k−i otherwise\begin{aligned} b'&=b_k\\ a'_i&=\begin{cases} a_{k-i}\ \mathrm{if}\ i≤k\\ -a_{N+k-i}\ \mathrm{otherwise} \end{cases} \end{aligned}

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

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

TRLWEのパラメータについて

  • N=1024,αbk=2−25N=1024,α_{bk}=2^{-25}
  • 実はTRLWEの安全性を直接推定する方法は知られていない
  • TRLWEに入っている環の構造を利用した攻撃が知られていないため
  • 安全性の推定はTLWEに変換して行われている(十分条件による弱い推定)

なぜXN+1X^N+1なのか

  • 実のところXN+1X^N+1でなければならないわけではない
  • しかし因数分解できてしまうとNNが小さなTRLWEに分解できてしまって脆弱
  • XN+1X^N+1はNNが2のべきなら因数分解できない
  • 非ゼロの項も2つしかないので剰余がとりやすい
  • 7.で見るようにFFTによる高速化ができるのも利点

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

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

参考文献

page_number: true