【ePrint解説】Liberating TFHE　1/4

2週間前の9/9（金）にIACRに掲載されたePrint（以下めんどいので論文とかペーパーとか）について解説します．

対象とするペーパーは次のとおりです：

M. Joye, M. Walter: "Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials", Cryptology ePrint Archive, 2022.

＊ZamaのePrintでは，なぜか花文字が多く出てくる（𝒻, 𝓅, 𝓋 など）のですが，わざわざ花文字を使う必要性を感じないので，普通のアルファベットで書きます
＊プログラマブルブートストラップの内容は仮定します（詳しくは今回の「2,3章について」）

全４回通しでの目次

第１回（イマココ）

• 本論文全体の流れ
• 2,3章について
• 4章でやりたいこと
• 4.1 Monomial Multiplication in $(Z/qZ)[X]/(p(X))(\mathbb{Z} / q \mathbb{Z})[X] / (p(X))$

第２回

第３回

第４回

本論文全体の流れ

• どういう背景や課題・モチベーションがあって，
• どのようなアイディアのもとで，
• どのような結果が得られたのか

を整理します．

背景・課題
現在のプログラマブルブートストラップで用いられているFFTは有限の精度で近似する必要があり，NTTを用いるにはいくつかのパラメタに制約がある

アイディア
円分多項式として用いられる $XN+1X^N + 1$ を「性質の良い」多項式（これ以外の円分多項式とか）に拡張する

結果
プログラマブルブートストラップで用いられるFFTをNTTへと一般化し，test vector をプログラムするためのいくつかの公式が与えられた

それらを元に各章を整理すると，次のようになります:

１章：イントロ
２章：FFTやNTTの導入
３章：プログラマブルブートストラップ
４章：一般化プログラマブルブートストラップ
５章：プログラマブルブートストラップの関数
６章：ノイズ
７章：パラメタの例

一番言いたいことは４章, 5章です．6, 7章も触れます．

2,3章について

そんなこんなで，今回はこの2つに関しては省略します．２章は別で記事を書いているので，そちらを参照してください．
３章は，プログラマブルブートストラップの原著論文を理解する回　4/4に大体書かれています．3.2については触れられていませんが，「背景・課題」と「アイディア」で書いた部分が詳しく書かれているので，興味のある方はお読みください．

4章でやりたいこと

現在のプログラマブルブートストラップでは，平文空間などは $(Z/qZ)[X]/(XN+1)(\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1)$ なる剰余環で考えています（$q,Nq, N$ 共に2べき）．
この $XN+1X^N + 1$ の部分を一般化しようと思うと，例えば，$NN$ を変えて他の円分多項式を使うなどが考えられます．その変更を行なった際に，そもそもどのような演算なのか，や，プログラマブルブートストラップで必要な Blind Rotation などの処理がどのように変更されるのか，を考察していきます．

その際に，$NN$ を2べきにする必要ないのであれば，$(Z/qZ)(\mathbb{Z} / q \mathbb{Z})$ の部分も一般化してOKなので，以降では，一般の（単位元を持つ）環 $RR$ とします．
＊論文には書かれていませんが，記事内では可換環とします（そうでないと結論としておかしい部分があるため）

4.1

＊タイトルだと，「Monomial Multiplication in $(Z/qZ)[X]/(p(X))(\mathbb{Z} / q \mathbb{Z})[X] / (p(X))$」になっていますが，正しくは，「Monomial Multiplication in $R[X]/(p(X))R[X] / (p(X))$」です

$RR$ 上のモニック（最高次係数が1）な $NN$ 次多項式 $p(X)=XN+pN−1XN−1+⋯+p1X+p0p(X) = X^N + p_{N - 1} X^{N - 1} + \cdots + p_1 X + p_0$ を取ります．そして，$p(X)p(X)$ は次の条件を満たすものとします:

• ある正整数 $MM$ が存在して，$p(X)p(X)$ は $XM−1X^M - 1$ を割り切る

＊$p(X)p(X)$ は既約でなくてもOK

便宜上 $pN=1p_N = 1$ として，$p(X)=∑j=0NpjXj\displaystyle p(X) = \sum_{j = 0}^N p_j X^j$ と書きます．ここで，次の命題が成り立ちます:

＊次のProp1, 2は論文と記載の順が逆ですが，こちらの方が議論として綺麗かなと

---

$Prop1‾\underline{\mathrm{Prop1}}$
$p0p_0$ は $RR$ で可逆

---

証明
「ある正整数 $MM$ が存在して，$p(X)p(X)$ は $XM−1X^M - 1$ を割り切る」から，ある $RR$ 上の多項式 $q(X)q(X)$ が存在して，$XM−1=p(X)q(X)X^M - 1 = p(X) q(X)$ と表せます．また，$p(X)p(X)$ が $NN$ 次多項式であることから，$q(X)q(X)$ は $M−NM - N$ 次多項式であり，特に $q(X)=∑i=0M−NqiXi\displaystyle q(X) = \sum_{i = 0}^{M - N} q_i X^i$ となります（$qM−N=1q_{M - N} = 1$ に注意）．
$XM−1=p(X)q(X)X^M - 1 = p(X) q(X)$ の定数項に注目すると，$−1=p0q0-1 = p_0 q_0$ が成り立ちます．よって，$p0(−q0)=1p_0 (- q_0) = 1$ ゆえ，示されました．

---

また，次の命題が成り立ちます:

---

$Prop2‾\underline{\mathrm{Prop2}}$
$R[X]/(p(X))R[X] / (p(X))$ において，$X−1=(−p0)−1∑j=0N−1pj+1Xj\displaystyle X^{-1} = (- p_0)^{-1} \sum_{j = 0}^{N - 1} p_{j + 1} X^j$ が成り立つ

---

証明
$R[X]/(p(X))R[X] / (p(X))$ では（mod $p(X)p(X)$ なので），$p(X)=0p(X) = 0$ i.e. $∑j=0NpjXj=0\displaystyle \sum_{j = 0}^N p_j X^j = 0$ です．すると，$R[X]/(p(X))R[X] / (p(X))$ において，$∑j=1NpjXj=−p0\displaystyle \sum_{j = 1}^N p_j X^j = - p_0$ が成り立ちます．
よって，$R[X]/(p(X))R[X] / (p(X))$ において，$(−p0)−1∑j=1NpjXj=1\displaystyle (- p_0)^{-1} \sum_{j = 1}^N p_j X^j = 1$ なので（Prop 1 より $p0−1p_0^{-1}$ が存在），両辺に $X−1X^{-1}$ を掛けて，

$$X−1=(−p0)−1∑j=1NpjXjX−1=(−p0)−1∑j=1NpjXj−1=(−p0)−1∑j=0N−1pj+1Xj\begin{align*} X^{-1} & = (- p_0)^{-1} \sum_{j = 1}^N p_j X^j X^{-1} \\ & = (- p_0)^{-1} \sum_{j = 1}^N p_j X^{j - 1} \\ & = (- p_0)^{-1} \sum_{j = 0}^{N - 1} p_{j + 1} X^{j} \end{align*}$$

ゆえ，示されました．

＊ちなみに，$∑j=1NpjXj=−p0\displaystyle \sum_{j = 1}^N p_j X^j = - p_0$ から $(−p0)−1∑j=1NpjXj=1\displaystyle (- p_0)^{-1} \sum_{j = 1}^N p_j X^j = 1$ を導出する部分は，左から $(−p0)(- p_0)$ 掛けています，$(−p0)−1∑j=1NpjXj=1\displaystyle (- p_0)^{-1} \sum_{j = 1}^N p_j X^j = 1$ から $X−1=(−p0)−1∑j=1NpjXjX−1\displaystyle X^{-1} = (- p_0)^{-1} \sum_{j = 1}^N p_j X^j X^{-1}$ を導出する部分は，右から $X^{-1}$ を掛けています

---

さて，$N - 1$ 次多項式 $\displaystyle v(X) = \sum_{i = 0}^{N - 1} v_i X^i \in R[X] / (p(X))$ を取ります．便宜上 $(v(X))_i := v_i$ と書くことにします．
すると，$v_N = 0$ として，

$$\begin{align*} X^{-1} v(X) & = X^{-1} \sum_{i = 0}^{N - 1} v_i X^i \\ & = \sum_{i = 0}^{N - 1} v_i X^{i - 1} \hspace{10pt} \cdots (\star) \\ & = \left( \sum_{i = 1}^{N - 1} v_i X^{i - 1} \right) + v_0 X^{-1} \\ & = \left( \sum_{i = 0}^{N - 2} v_{i + 1} X^i \right) + v_0 (- p_0)^{-1} \left( \sum_{j = 0}^{N - 1} p_{j + 1} X^j \right) \hspace{10pt} \because) \mathrm{Prop 2} \\ & = \left( \sum_{i = 0}^{N - 2} v_{i + 1} X^i \right) + (- p_0)^{-1} v_0 \left( \sum_{j = 0}^{N - 1} p_{j + 1} X^j \right) \hspace{10pt} \cdots (\star) \\ & = \left( \sum_{i = 0}^{N - 2} (v_{i + 1} + (- p_0)^{-1} v_0 p_{i + 1}) X^i \right) + (- p_0)^{-1} v_0 p_N X^{N - 1} \hspace{10pt} \because) 同類項を整理 \\ & = \sum_{i = 0}^{N - 1} (v_{i + 1} + (- p_0)^{-1} v_0 p_{i + 1}) X^i \hspace{10pt} \because) v_N = 0 \\ & = \sum_{i = 0}^{N - 1} (v_{i + 1} + (- p_0)^{-1} p_{i + 1} v_0) X^i \hspace{10pt} \cdots (\star) \\ \end{align*}$$

となりますので，$X^{-1} v(X) = \sum_{i = 0}^{N - 1} (v_{i + 1} + (- p_0)^{-1} p_{i + 1} v_0) X^i$ を得ます．これは，Blind Rotation で見る形（test vector を回す部分）に対応しています．

＊上の式変形で $(\star)$ とした部分で $R$ の可換性を使っています

---

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！