まず，前回と同じ $N - 1$ 次多項式 $\displaystyle v(X) = \sum_{i = 0}^{N - 1} v_i X^i \in R[X] / (p(X))$ を取り， $X^{-t} v(X)$ の定数項（つまり， $(X^{-t} v(X))_0 = (X^{-t} v(X))[0]$ ）を $K_t$ とします．
そして，Blind Rotation といえば，Lookup Table ということで，要素数が $N$ の配列 $T$ を考えます．そして， $T[t] = K_t$ とすることで，Lookup Table を構成することができます．
逆に，Lookup Table の各要素を $X^{-t} v(X)$ の定数項とみなすことで， $v(X)$ を構成でき，そのことを次の命題で示します:

$\underline{\mathrm{Prop1}}$
$\{ K_i \in R \}_{i = 0}^{N - 1}$ を取り，任意の $0 \leq i \leq N - 1$ に対して， $\displaystyle v_i = \sum_{j = 0}^i \frac{p_{i - j}}{p_0} K_j$ として， $\displaystyle v(X) = \sum_{i = 0}^{N - 1} v_i X^i\in v_i X^i \in R[X] / (p(X))$ とする．このとき，任意の $0 \leq t \leq N - 1$ に対して， $(X^{-t} v(X))_0 = K_t$ である．

証明
$t$ に関する帰納法で示します．

step 1
$t = 0$ のとき， $\displaystyle (X^{- 0} v(X))_0 = (v(X))_0 = v_0 = \frac{p_0}{p_0} K_0 = K_0$ ゆえOKです．

step 2
次に $j < t$ なる任意の $j$ で成り立つと仮定します．前回の【ePrint解説】Liberating TFHE　1/4「4.1」から， $X^{-1} v(X) = \sum_{i = 0}^{N - 1} (v_{i + 1} + (- p_0)^{-1} p_{i + 1} v_0) X^i$ が成り立ちます．すると，両辺の $i$ 番目の要素に注目して， $(X^{-1} v(X))_i = v_{i + 1} + (- p_0)^{-1} p_{i + 1} v_0$ が成り立ちます． $(v(X))_0 = v_0, (v(X))_{i + 1} = v_{i + 1}$ を使うと， $(X^{-1} v(X))_i = (v(X))_{i + 1} - \frac{p_{i + 1}}{p_0} (v(X))_0$ となります．
よって，

\begin{align*} (X^{-t} v(X))_0 & = (X^{-1} (X^{-t + 1} v(X)))_0 \\ & = (X^{-t + 1} v(X))_1 - \frac{p_1}{p_0} (X^{-t + 1} v(X))_0 \\ & = (X^{-1} (X^{-t + 2} v(X)))_1 - \frac{p_1}{p_0} (X^{-t + 1} v(X))_0 \\ & = (X^{-t + 2} v(X))_2 - \frac{p_2}{p_0} (X^{-t + 2} v(X))_0 - \frac{p_1}{p_0} (X^{-t + 1} v(X))_0 \\ & = \cdots \\ & = (X^{-t + t} v(X))_t - \frac{p_t}{p_0} (X^{-t + t} v(X))_0 - \frac{p_{t - 1}}{p_0} (X^{-t + (t - 1)} v(X))_0 - \cdots - \frac{p_1}{p_0} (X^{-t + 1} v(X))_0 \\ & = v_t - \sum_{j = 0}^{t - 1} \frac{p_{t - j}}{p_0} (X^{- j} v(X))_0 \end{align*}

各等号について

２行目： $(X^{-1} v(X))_i = (v(X))_{i + 1} - \frac{p_{i + 1}}{p_0} (v(X))_0$ 　に対して， $v(X) = X^{-t + 1} v(X), i = 0$
４行目：２行目と同じ
６行目：２・４行目を繰り返し
７行目：６行目の「 $\frac{p_t}{p_0} (X^{-t + t} v(X))_0$ 」以降を $\sum$ で整理

になりますので， $0 \leq j \leq t - 1$ に対して，帰納法の仮定から $(X^{- j} v(X))_0 = K_j$ なので，

\begin{align*} (X^{-t} v(X))_0 & = v_t - \sum_{j = 0}^{t - 1} \frac{p_{t - j}}{p_0} (X^{- j} v(X))_0 \\ & = v_t - \sum_{j = 0}^{t - 1} \frac{p_{t - j}}{p_0} K_j \\ & = \sum_{j = 0}^t \frac{p_{t - j}}{p_0} K_j - \sum_{j = 0}^{t - 1} \frac{p_{t - j}}{p_0} K_j \\ & = K_t \end{align*}

各等号について

２行目： $0 \leq j leq t - 1$ に対して，帰納法の仮定から $(X^{- j} v(X))_0 = K_j$
３行目：命題の仮定の「任意の $0 \leq i \leq N - 1$ に対して， $\displaystyle v_i = \sum_{j = 0}^i \frac{p_{i - j}}{p_0} K_j$ 」
４行目： $0 \leq j \leq t - 1$ の部分が消えて， $j = t$ の部分だけ残る

となるので，一般の $t$ でも示されました．

4.2.2 Leading coefficient

今度は，Lookup Table の各要素を $X^{-t} v(X)$ の先頭項とみなすことで， $v(X)$ を構成します．

$\underline{\mathrm{Prop2}}$
$\{ K_i \in R \}_{i = 0}^{N - 1}$ を取り，任意の $0 \leq i \leq N - 2$ に対して， $\displaystyle v_{N - 1} = K_0, v_i = - \sum_{j = 0}^i p_{i - j} K_{j + 1}$ として， $\displaystyle v(X) = \sum_{i = 0}^{N - 1} v_i X^i \in R[X] / (p(X))$ とする．このとき，任意の $0 \leq t \leq N - 1$ に対して， $(X^{-t} v(X))_{N - 1} = K_t$ である．

証明
こちらも $t$ に関する帰納法で示します．
step 1
$t = 0$ のとき， $(X^{- 0} v(X))_{N - 1} = (v(X))_{N - 1} = K_0$ で，右辺も $K_0$ ゆえ一致します．

step 2
$t = 1$ のとき，前回の【ePrint解説】Liberating TFHE　1/4「4.1」から，任意の $0 \leq i \leq N - 1$ に対して， $(X^{-1} v(X))_i = v_{i + 1} + (- p_0)^{-1} p_{i + 1} v_0$ ゆえ， $i = N - 1$ で， $(X^{-1} v(X))_{N - 1} = v_N + (- p_0)^{-1} p_N v_0$ が成り立ちます． $v_N = 0, p_N = 1$ なので， $(X^{-1} v(X))_{N - 1} = (- p_0)^{-1} v_0$ です．また，仮定から任意の $0 \leq i \leq N - 2$ に対して， $\displaystyle v_i = - \sum_{j = 0}^i p_{i - j} K_{j + 1}$ ゆえ， $i = 0$ で $v_0 = - p_0 K_1$ が成り立つため， $(X^{-1} v(X))_{N - 1} = (- p_0)^{-1} v_0 = (- p_0)^{-1} (- p_0 K_1) = K_1$ となります．

step 3
次に $j < t$ なる任意の $j$ で成り立つと仮定します．特に， $t = 1$ で成り立つので， $(v(X))_0 = v_0 = - p_0 K_1 = - p_0 (X^{-1} v(X))_{N - 1}$ です．つまり， $(v(X))_0 = - p_0 (X^{-1} v(X))_{N - 1}$ となります．今， $v(X)$ は任意なので， $v(X) \mapsto X^{-j} v(X)$ として， $(X^{-j} v(X))_0 = - p_0 (X^{-1} X^{-j} v(X))_{N - 1}$ です．よって， $(X^{-j} v(X))_0 = - p_0 (X^{-j-1} v(X))_{N - 1}$ となります．
また，先ほどの命題から $\displaystyle (X^{-i} v(X))_0 = v_i - \sum_{j = 0}^{i - 1} \frac{p_{i - j}}{p_0} (X^{- j} v(X))_0$ が任意の $0 \leq i \leq N - 1$ で成り立ちます．
＊この式の導出では，前回の【ePrint解説】Liberating TFHE　1/4「4.1」しか，本質的には使っていないので，この場合でも成り立ちます
＊Prop1 では， $\displaystyle (X^{-t} v(X))_0 = v_t - \sum_{j = 0}^{t - 1} \frac{p_{t - j}}{p_0} (X^{- j} v(X))_0$ と書いていましたが，今 $t$ を書くと，帰納法の変数とバッティングするため， $t \mapsto i$ で変数名を変更しました

よって，

\begin{align*} -p_0 (X^{-t} v(X))_{N - 1} & = (X^{-t + 1} v(X))_0 \\ & = v_{t - 1} - \sum_{j = 0}^{t - 2} \frac{p_{t - j - 1}}{p_0} (X^{- j} v(X))_0 \\ & = v_{t - 1} - \sum_{j = 0}^{t - 2} \frac{p_{t - j - 1}}{p_0} (- p_0 (X^{- j - 1} v(X))_{N - 1}) \\ & = v_{t - 1} + \sum_{j = 0}^{t - 2} p_{t - j - 1} (X^{- j - 1} v(X))_{N - 1} \\ & = - \sum_{j = 0}^{t - 1} p_{t - 1 - j} K_{j + 1} + \sum_{j = 0}^{t - 2} p_{t - j - 1} (X^{- j - 1} v(X))_{N - 1} \\ & = - p_0 K_t \end{align*}

となり，示されました．

各等号について

１行目： $(X^{-j} v(X))_0 = - p_0 (X^{-j-1} v(X))_{N - 1}$ で $j = t - 1$
２行目： $\displaystyle (X^{-i} v(X))_0 = v_i - \sum_{j = 0}^{i - 1} \frac{p_{i - j}}{p_0} (X^{- j} v(X))_0$ で $j = t - 1$
３行目： $(X^{-j} v(X))_0 = - p_0 (X^{-j-1} v(X))_{N - 1}$
４行目： $p_0$ の消去と符号を変更
５行目： $v_i = - \sum_{j = 0}^i p_{i - j} K_{j + 1}$ （仮定）で $i = t - 1$ （論文だとこの等号が消去されて成り立たない等式となっている）
６行目： $j = t - 1$ の場合のみが残る

4.2.3 Trinomials

この節では， $N$ を偶数， $\varepsilon$ を -1, 1 のいずれかとして， $p(X) = X^N + \varepsilon X^{\frac{N}{2}} + 1$ と置きます．
ちなみにこのとき， $p(X)$ が円分多項式であれば，3の倍数の次数の円分多項式です．

上記の証明

$\varepsilon = 1$ のとき， $(X{\frac{N}{2}} - 1)(X^N + X^{\frac{N}{2}} + 1) = X^{3 \frac{N}{2}} - 1$ であり，
$\varepsilon = -1$ のとき， $(X{\frac{N}{2}} + 1)(X^N - X^{\frac{N}{2}} + 1) = X^{3 \frac{N}{2}} + 1$ から成り立ちます．
＊この命題の逆，つまり， $p(X)$ が3の倍数の次数の円分多項式であれば， $p(X) = X^N + \varepsilon X^{\frac{N}{2}} + 1$ は成り立ちません

この $p(X)$ に限定することで， $s$ 番目の要素を参照するだけで， $v(X)$ を構成できます．
このとき， $s$ 番目をどう指定するかで，test polynomial の構成が変わります

$\underline{\mathrm{Prop3}}$
$N$ を正の偶数， $\varepsilon = 1, -1$ として， $p(X) = X^N + \varepsilon X^{\frac{N}{2}} + 1$ とする． $s < \frac{N}{2}$ を非零な整数とする． $\{ K_i \in R \}_{i = 0}^{N - 1}$ を取り，

\begin{align*} v_i = \begin{cases} -\varepsilon K_{\frac{N}{2} + (i - s)} - K_{N + (i - s)} \hspace{10pt} & (0 \leq i < s) \\ K_{i - s} & (s \leq i < \frac{N}{2}) \\ -\varepsilon K_{\frac{N}{2} + (i - s)} & (\frac{N}{2} \leq i < \frac{N}{2} + s) \\ \varepsilon K_{(i - s) - \frac{N}{2}} + K_{i - s} & (\frac{N}{2} + s \leq i < N) \end{cases} \end{align*}

として， $\displaystyle v(X) = \sum_{i = 0}^{N - 1} v_i X^i \in R[X] / (p(X))$ とする．このとき，任意の $0 \leq t \leq N - 1$ に対して， $(X^{-t} v(X))_s = K_t$ である．

証明
地道に場合分けするだけなので略（めんどくさい）

上の命題では， $s < \frac{N}{2}$ でしたが， $\frac{N}{2} \leq s < N$ の場合でも構成できます

$\underline{\mathrm{Prop4}}$
$N$ を正の偶数， $\varepsilon = 1, -1$ として， $p(X) = X^N + \varepsilon X^{\frac{N}{2}} + 1$ とする． $\frac{N}{2} \leq s < N$ を整数とする． $\{ K_i \in R \}_{i = 0}^{N - 1}$ を取り，

\begin{align*} v_i = \begin{cases} -K_{N - (s - i)} & (0 \leq i < \frac{N}{2}) \\ -\varepsilon K_{\frac{N}{2} - (s - i)} - K_{N - (s - i)} & (\frac{N}{2} \leq i < s) \\ K_{-(s - i)} & (s \leq i < N) \end{cases} \end{align*}

として， $\displaystyle v(X) = \sum_{i = 0}^{N - 1} v_i X^i \in R[X] / (p(X))$ とする．このとき，任意の $0 \leq t \leq N - 1$ に対して， $(X^{-t} v(X))_s = K_t$ である．

証明
Prop3とほぼ同じ（つまり場合分けがめんどくさい）ので略

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

全４回通しでの目次

4.2 Programming the Test Polynomial

4.2.1 Constant coefficient

4.2.2 Leading coefficient

4.2.3 Trinomials

Discussion