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 (\mathbb{Z} / q \mathbb{Z})[X] / (p(X))
第２回
第３回
第４回
本論文全体の流れ
- どういう背景や課題・モチベーションがあって，
- どのようなアイディアのもとで，
- どのような結果が得られたのか
を整理します．
背景・課題
現在のプログラマブルブートストラップで用いられているFFTは有限の精度で近似する必要があり，NTTを用いるにはいくつかのパラメタに制約がある
アイディア
円分多項式として用いられる X^N + 1 を「性質の良い」多項式（これ以外の円分多項式とか）に拡張する
結果
プログラマブルブートストラップで用いられるFFTをNTTへと一般化し，test vector をプログラムするためのいくつかの公式が与えられた
それらを元に各章を整理すると，次のようになります:
１章：イントロ
２章：FFTやNTTの導入
３章：プログラマブルブートストラップ
４章：一般化プログラマブルブートストラップ
５章：プログラマブルブートストラップの関数
６章：ノイズ
７章：パラメタの例
一番言いたいことは４章, 5章です．6, 7章も触れます．
2,3章について
そんなこんなで，今回はこの2つに関しては省略します．２章は別で記事を書いているので，そちらを参照してください．
３章は，プログラマブルブートストラップの原著論文を理解する回 4/4に大体書かれています．3.2については触れられていませんが，「背景・課題」と「アイディア」で書いた部分が詳しく書かれているので，興味のある方はお読みください．
4章でやりたいこと
現在のプログラマブルブートストラップでは，平文空間などは (\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1) なる剰余環で考えています（q, N 共に2べき）．
この X^N + 1 の部分を一般化しようと思うと，例えば，N を変えて他の円分多項式を使うなどが考えられます．その変更を行なった際に，そもそもどのような演算なのか，や，プログラマブルブートストラップで必要な Blind Rotation などの処理がどのように変更されるのか，を考察していきます．
その際に，N を2べきにする必要ないのであれば，(\mathbb{Z} / q \mathbb{Z}) の部分も一般化してOKなので，以降では，一般の（単位元を持つ）環 R とします．
＊論文には書かれていませんが，記事内では可換環とします（そうでないと結論としておかしい部分があるため）
4.1
＊タイトルだと，「Monomial Multiplication in (\mathbb{Z} / q \mathbb{Z})[X] / (p(X))」になっていますが，正しくは，「Monomial Multiplication in R[X] / (p(X))」です
R 上のモニック（最高次係数が1）な N 次多項式 p(X) = X^N + p_{N - 1} X^{N - 1} + \cdots + p_1 X + p_0 を取ります．そして，p(X) は次の条件を満たすものとします:
- ある正整数 M が存在して，p(X) は X^M - 1 を割り切る
＊p(X) は既約でなくてもOK
便宜上 p_N = 1 として，\displaystyle p(X) = \sum_{j = 0}^N p_j X^j と書きます．ここで，次の命題が成り立ちます:
＊次のProp1, 2は論文と記載の順が逆ですが，こちらの方が議論として綺麗かなと
\underline{\mathrm{Prop1}}
p_0 は R で可逆
証明
「ある正整数 M が存在して，p(X) は X^M - 1 を割り切る」から，ある R 上の多項式 q(X) が存在して，X^M - 1 = p(X) q(X) と表せます．また，p(X) が N 次多項式であることから，q(X) は M - N 次多項式であり，特に \displaystyle q(X) = \sum_{i = 0}^{M - N} q_i X^i となります（q_{M - N} = 1 に注意）．
X^M - 1 = p(X) q(X) の定数項に注目すると，-1 = p_0 q_0 が成り立ちます．よって，p_0 (- q_0) = 1 ゆえ，示されました．
また，次の命題が成り立ちます:
\underline{\mathrm{Prop2}}
R[X] / (p(X)) において，\displaystyle X^{-1} = (- p_0)^{-1} \sum_{j = 0}^{N - 1} p_{j + 1} X^j が成り立つ
証明
R[X] / (p(X)) では（mod p(X) なので），p(X) = 0 i.e. \displaystyle \sum_{j = 0}^N p_j X^j = 0 です．すると，R[X] / (p(X)) において，\displaystyle \sum_{j = 1}^N p_j X^j = - p_0 が成り立ちます．
よって，R[X] / (p(X)) において，\displaystyle (- p_0)^{-1} \sum_{j = 1}^N p_j X^j = 1 なので（Prop 1 より p_0^{-1} が存在），両辺に X^{-1} を掛けて，
\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*}
ゆえ，示されました．
＊ちなみに，\displaystyle \sum_{j = 1}^N p_j X^j = - p_0 から \displaystyle (- p_0)^{-1} \sum_{j = 1}^N p_j X^j = 1 を導出する部分は，左から (- p_0) 掛けています，\displaystyle (- p_0)^{-1} \sum_{j = 1}^N p_j X^j = 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 の可換性を使っています
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion