今回の記事は下記の記事からの続きとなります．
原著論文：プログラマブルブートストラップの原著論文
第１回：第１回
プログラマブルブートストラップの原著論文の第２〜４章を厳密に考察します．
全体を通して使う記号や前提知識などは第１回目の記事にまとめています．
本論文全体の流れ
全体の前提知識と参考文献
この連載を読みやすくリメイクしたQiitaの記事
第１回：第１回
第２回：第２回
第３回：第３回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
全４回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
- 2.2 Probability Distributions
第２回（イマココ）
- 今回出てくる予備知識のまとめ
- Appendix A : Complexity Assumptions Over the Real Torus
- 3章前説
- 3章の流れ
- ギリシャ文字と花文字
-
\hat{\mathbb{Z}} と \hat{\mathbb{T}}
- 3章前説の議論
- 3章前説の議論の考察
- 3.1 Encoding/Decoding Messages
- lift
- Upper
- 3.1の議論
- 3.1の議論の考察
第2.5回（番外編）
- なぜ番外編が必要なのか
- 今回出てくる予備知識のまとめ
- GGSW方式とは
- 無限ノルム
- Tensor積
- gadget行列
- gadget decomposition
- GGSW方式のアルゴリズム
- GGSW方式のアルゴリズムの具体例
- これまでの議論の考察１
- GGSW方式の暗号文の足し算
- GGSW方式の暗号文同士の内積
- これまでの議論の考察２
第３回
- 今回出てくる予備知識のまとめ
- 3.2 Description
- TFHE方式のアルゴリズム
- TFHE方式のアルゴリズムの具体例
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- 3.2の議論の考察
- 3.3 Leveled Operation
- Tensor積
- gadget行列
- gadget decompostion
- GGSW方式の概要
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- 結局 Leveled Operaion とは何か
- TFHE方式の暗号文とGGSW方式の暗号文の外積
- Cmuxゲート
- 3.3の議論の考察
第４回
今回は第２回目で，
Appendix A : Complexity Assumptions Over the Real Torus
3 Discretized TFHE
3.1 Encoding/Decoding Messages
を扱います．
具体的な内容としては，次のようになります:
- Appendix A : Complexity Assumptions Over the Real Torus
- 3章前説
- ギリシャ文字と花文字
-
\hat{\mathbb{Z}} と \hat{\mathbb{T}}
- 3章前説の議論
- 3.1 Encoding/Decoding Messages
ちなみに次回からが本番って感じです．前回と今回は論文の理解としては楽なので，数学的な補足を多めにしています．
論文中の議論をどのように解説するかは，今回の「3章前説の議論」に記載しています．
それでは早速見ていきましょう．
今回出てくる予備知識のまとめ
前提知識以外の数学的な予備知識は適宜まとめてはいますが，一覧がほしい方もいらっしゃるかもなので，先にまとめます．折りたたみで出てくる概念のみを対象で，本文中に出てくるものは目次を参考にしてください．今回はそんなに重要なものではないです．
順番は今回の記事で出てくる順で，内容は定義だけざっと並べています．
- Z / p Z について
- 拡張 Euclid の互除法
- p進整数環
- 素体
Z / p Z について
\underline{\mathrm{Thm}}
p を整数とするとき，次は同値:
(1) p は素数
(2) \mathbb{Z} / p \mathbb{Z} は体
拡張 Euclid の互除法
\underline{\mathrm{Thm(拡張 Euclid の互除法, Euclidean \ Algorithm)}}
a, b を互いに素な整数とするとき，ある整数 m, n が存在して，am + bn = 1 を満たす．
p進整数環
\underline{\mathrm{Def(p進整数環, p-adic \ number \ ring)}}
p を素数として，p 進整数環 \mathbb{Z}_p \subset \mathbb{Q} とは，元 \alpha が
\displaystyle
\begin{align*}
\alpha = \sum_{n = - n_0}^{\infty} a_n p^n \hspace{10pt} a_n \in [0, p - 1] \subset \mathbb{N}
\end{align*}
と表せて，通常の加法と乗法で環になっているものである．
素体
\underline{\mathrm{Def(素体,prime \ field)}}
自分自身以外に部分体を含まない体を素体という．
TLWEとTRLWE
＊はじめはここのタイトルを論文に合わせて「LWEとGLWE」にしていたのですが，あまりにもセンスがないので変更することにしました．
Torus上のLWE問題なのでTLWE，Torus上の多項式環ベースのLWE問題なのでTRLWEとします．影響がある部分は全て変更しています．
格子暗号が基づくNP困難な問題として，TLWEとそれを多項式環上に拡張したTRLWEを紹介します．
\underline{\mathrm{TLWE問題, TLWE(Torus \ Learning \ with \ Errors) \ problem}}
n \in \mathbb{N}, \ s = (s_1, s_2, \cdots, s_n) \overset{\#}{\leftarrow} \mathbb{B}^n とする．また，\mathcal{X} を \mathbb{R} 上の正規分布とする．
このとき，Torus上のLWE問題（TLWE問題）とは次の2つの分布を識別することである:
\begin{align*}
\displaystyle
\tilde{D}_0 & = \{ (a, r) \ | \ a = (a_1, a_2, \cdots, a_n) \overset{\#}{\leftarrow} \mathbb{T}^n, \ r \overset{\#}{\leftarrow} \mathbb{T} \} \\
\tilde{D}_1 & = \{ (a, r) \ | \ a = (a_1, a_2, \cdots, a_n) \overset{\#}{\leftarrow} \mathbb{T}^n, e \overset{\#}{\leftarrow} \mathcal{X}, \ r = \sum_{j = 1}^n s_j \cdot a_j + e \}
\end{align*}
\underline{\mathrm{TRLWE問題, TRLWE(Torus \ Ring \ Learning \ with \ Errors) \ problem}}
N, k \in \mathbb{N} で N を2べきとする． \tilde{s} = (\tilde{s}_1, \cdots,\tilde{s}_k) \overset{\#}{\leftarrow} \mathbb{B}_N[X]^K とする． また，\mathcal{X} を \mathbb{R} 上の正規分布とする．
このとき，Torus上のRLWE問題（TRLWE問題）とは次の2つの分布を識別することである:
\begin{align*}
\displaystyle
\tilde{D}_0 & = \{ (\tilde{a}, \tilde{r}) \ | \ \tilde{a} = (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n) \overset{\#}{\leftarrow} \mathbb{T}[X]^n, \ \tilde{r} \overset{\#}{\leftarrow} \mathbb{T}[X] \} \\
\tilde{D}_1 & = \{ (\tilde{a}, \tilde{r}) \ | \ \tilde{a} = (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n) \overset{\#}{\leftarrow} \mathbb{T}[X]^n, \tilde{e} \overset{\#}{\leftarrow} \mathcal{X}, \ \tilde{r} = \sum_{j = 1}^n \tilde{s}_j \cdot \tilde{a}_j + \tilde{e} \}
\end{align*}
＊論文と記号が対応していない箇所がありますが，今回の「ギリシャ文字と花文字」で補足します
一見すると，仰々しいかもしれませんが，TLWEさえ理解できれば，TRLWEは範囲を多項式環に拡張しただけ，と分かります．
TLWEは大雑把にいうと，a, r が与えられたときに，誤差 e が生じる状況で \displaystyle r = \sum_{j = 1}^n s_j \cdot a_j + e から s を求める，という問題です．
設定から分かるように，機械学習由来の問題です．この s を求める部分が（s のビット長をオーダーとした）NP困難な問題です．
識別について
「s が簡単に分かってしまうと識別できる」が結論です．ので，s は秘密鍵のようなものと思えます．
ある目的を持った分布とランダムに作られた分布がどちらかを判定するには，目的を持った分布の「構造」が分かっている必要があります．ここではそれが s に相当し，「識別できる」ということになります．
逆に分かっていないと，当てずっぽうでしか判定できないので，「識別できない」です．
目的を持った分布の「構造」が簡単には分からない，それを暗号の分野ではNP困難というわけです．NP困難な問題をそのまま扱うこともあれば，今回のように識別性で定義することもあります．
＊LWE問題がNP困難な仮定のもとで，TLWE問題もNP困難であることが知られています
以下では e = 0 とします．
\tilde{D}_0 は「ランダムに選ばれた a と，ランダムに選ばれた r」の分布を表しており，\tilde{D}_1 は「ランダムに選ばれた a と，a と s との内積の値」の分布を表しています．
すると，s は固定なので，
\displaystyle
\begin{align*}
\left\{
\begin{array}{l}
a_1 s_1 + a_2 s_2 + \cdots + a_n s_n & = r \\
a_1^{\prime} s_1 + a_2^{\prime} s_2 + \cdots + a_n^{\prime} s_n & = r^{\prime} \\
a_1^{\prime \prime} s_1 + a_2^{\prime \prime} s_2 + \cdots + a_n^{\prime \prime} s_n & = r^{\prime \prime} \\
\cdots
\end{array}
\right.
\end{align*}
という連立方程式を解けばいいことになります．a を係数で，r を右辺の値とする連立方程式の解が s です．
\tilde{D}_1 の元を１つ観測すると，方程式が１つ得られるイメージです．
すると，十分な回数の観測を行うことで，左辺の (a_1, a_2, \cdots, a_n), (a_1^{\prime}, a_2^{\prime}, \cdots, a_n^{\prime}), (a_1^{\prime \prime}, a_2^{\prime \prime}, \cdots, a_n^{\prime \prime}), \cdots などのベクトルからなる n \times n 正方行列のうち，正則（行列式が0以外）なものを取ることができます．
正則な行列は連立方程式の解を一意に定めるので，s がここからわかってしまいます．
s が完全にわかると，ランダムに選ばれた a を係数で，ランダムに選ばれた r を右辺の値とする連立方程式の解が s になる，というのは考えづらい状況なので，簡単に識別できてしまいます．
要するに s が求められると \tilde{D}_0 と \tilde{D}_1 は識別できる，ということです．
ただ，実際は右辺にノイズが加わってきます．そのため真の値 r にノイズが加算されるので，観測者から見た真の値は不明なため，上記の連立方程式を解くのがぐっと難しくなります．
それはつまり，s を求めるのがぐっと難しくなった，ということです．ちなみにこれはNP困難です．
上記の説明は下記の書籍を参考にしました．聖書なので素晴らしいですね．
耐量子計算機暗号
3章の流れ
ここから３章です．
３章ではTFHE方式の一般論と Leveled operation について触れます．具体的には次のようになります．
前説：TLWEを使った暗号化
3.1：メッセージの暗号化
3.2：THFE方式の暗号化アルゴリズム
3.3：leveled operation
前説と3.1は3.2のためにあって，3.3では3.2で定義した暗号文に対しての演算を考えています．
ギリシャ文字と花文字
よくある問題として
議論の際に文字足りないがち
という問題がどの分野でも往々にしてあります（たぶん）．
例えばすでに m という記号を使っていたり似たような意味で使いたい場合，m' とか \tilde{m} とか M とか \hat{m} とか色々な方法があります．
ただし，これでは限界があり，アルファベット以外の表音文字に頼ることがあります．よく使うのがギリシャ文字と花文字です．
見慣れない文字のせいで変に議論が難しく見えてしまうこともあります．そこで，ここでは今回の論文に出てくるギリシャ文字・花文字とアルファベットの対応をまとめました．
なんかよく分からん文字が出てきたなと思ったら，ここに立ち返ってみてください．
そして，今回の「TLWEとTRLWE」で触れた補足をします．
この論文中では，「花文字の小文字」を使用しています．が，それをTeXで出力する方法が分からんのです・・・（大文字なら分かるんですけどねぇ・・・）．
よって，花文字の一覧は下記に提示しますが，この記事では（大文字も）「アルファベットにチルダを付けたもので代用」とします．上の出力方法が分かれば，良い感じにリメイクします．
| アルファベット |
ギリシャ文字 |
花文字 |
花文字の代わり |
| a |
\alpha |
𝒶 |
\tilde{a} |
| e |
\epsilon |
ℯ |
\tilde{e} |
| r |
\rho |
𝓇 |
\tilde{r} |
| s |
\sigma |
𝓈 |
\tilde{s} |
| D |
\Delta |
\mathscr{D} |
\tilde{D} |
| M |
\Mu |
\mathscr{M} |
\tilde{M} |
| N |
\Nu |
\mathscr{N} |
\tilde{N} |
| O |
\Omega |
\mathscr{O} |
\tilde{O} |
| U |
\Sigma |
\mathscr{U} |
\tilde{U} |
花文字の小文字は こちらのサイトからコピペしました
hatについて
上ででてきた「似たような意味で使いたい」場合の例になっています．
\hat{\mathbb{T}} と \hat{\mathbb{Z}} を定義します．
以下では q を2べきの自然数とします．
\underline{\mathrm{Def(\hat{\mathbb{T}}, \hat{\mathbb{Z}})}}
q を2べきの自然数として，\hat{\mathbb{T}} = q^{-1} \mathbb{Z} / \mathbb{Z}, \ \hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z} と定める．
具体的な元を書いておくと，
\displaystyle
\begin{align*}
\hat{\mathbb{T}} &= q^{-1} \mathbb{Z} / \mathbb{Z} = \left \{ 0 + n, \frac{1}{q} + n, \frac{2}{q} + n, \cdots, \frac{q - 1}{q} + n \right \} \\
\hat{\mathbb{Z}} &= \mathbb{Z} / q \mathbb{Z} = \left \{ 0 + nq, 1 + nq, 2 + nq, \cdots, q - 1 + nq \right \}
\end{align*}
です．
なぜ q が2べきなのか，なぜ \hat{\mathbb{T}} や \hat{\mathbb{Z}} を導入する必要があるのか，については 今回の「3章前説の議論」 の最後の太字で解説しています．
これらは体ではありません（q が素数ではないため）．
また，\hat{\mathbb{T}} 内では掛け算は定義されません．分母の q の指数は1のみ許されていますが，掛け算をすると，指数が2以上になるためです．
Z / p Z について
前回の記事の「既約多項式と円分多項式」の折りたたみ「整域」で言及したことです．
次の定理を示すことが目標です．
\underline{\mathrm{Thm}}
p を整数とするとき，次は同値:
(1) p は素数
(2) \mathbb{Z} / p \mathbb{Z} は体
この定理を使うと，前回の記事の「\mathbb{Z} / 5 \mathbb{Z} は体だけど，\mathbb{Z} / 4 \mathbb{Z} は体じゃない」なども分かりますね．
上の定理の証明
\mathbb{Z} / p \mathbb{Z} は環であるため，以下では一々，代表元などを気にせずに0以上 p-1 以下の整数に絞って議論を進めます．つまり，\mathbb{Z} / p \mathbb{Z} の代表元を0以上 p-1 以下に制限します．
(1) \Rightarrow (2)
拡張 Euclid の互除法を使います．次のような内容でした．
\underline{\mathrm{Thm(拡張 Euclid の互除法, Euclidian \ Algorithm)}}
a, b を互いに素な整数とするとき，ある整数 m, n が存在して，am + bn = 1 を満たす．
よって，1以上 p - 1 以下の任意の整数 a に対して，a と p は互いに素ですから，上記のThmから a m + b p = 1 なる整数 m , n が存在します．
すると，\mathbb{Z} / p \mathbb{Z} 内では a m = 1 となるので，m が a の逆元なので，逆元の存在性が言えて，これで \mathbb{Z} / p \mathbb{Z} が体であることが示されました．
(2) \Rightarrow (1)
1以上 p - 1 以下の任意の整数 a に対して，a の逆元 m が存在します．つまり am = 1 です．
p が素数でないとすると，p = qr という2以上の整数 q, r の積とに分解できます．
このとき，a(m - q) = 1 です．なぜなら p は q の倍数なので aq \equiv 0 \ \mathrm{mod} \ q \Rightarrow aq \equiv 0 \ \mathrm{mod} \ p が成り立つからです．
ここで，r は2以上ですので， m \neq m - q から，体の乗法の逆元の一意性に矛盾します．
よって，p は素数です．
以上より示されました．
Z_P と F_p
こんな記述を見たことありませんか？
「\mathbb{Z} / p \mathbb{Z} を \mathbb{Z}_p と書くことにする」
結論から書くと，この記事っていうか僕が書く記事は絶対に上記の表記をせずに \mathbb{Z} / p \mathbb{Z} できっちり書くか，\mathbb{F}_p と書きます．
それは次のような概念があるからです．
\underline{\mathrm{Def(p進整数環, p-adic \ number \ ring)}}
p を素数として，p 進整数環 \mathbb{Z}_p \subset \mathbb{Q} とは，元 \alpha が
\displaystyle
\begin{align*}
\alpha = \sum_{n = - n_0}^{\infty} a_n p^n \hspace{10pt} a_n \in [0, p - 1] \subset \mathbb{N}
\end{align*}
と表せて，通常の加法と乗法で環になっているものである．
＊実は上の定義はめちゃくちゃざっくりしていて，本来は「p 進絶対値による \mathbb{Q} の完備化である p 進数体 \mathbb{Q}_p の付値環」と定義されるのですが，
それだけで３回分ぐらいの記事が書けるので，今回はこちらでご勘弁を
「\mathbb{Z} / p \mathbb{Z} を \mathbb{Z}_p と」書いてしまうと，上の p 進整数環と記号がバッティングしてしまいます．
多くの方は気にせずに使っていますが，ちゃんと \mathbb{Z} / p \mathbb{Z} を表す記号として， \mathbb{F}_p という代わりの記号が用意されているので，もし使うならこちらにします．
上記の参考文献をここで紹介します
表記について
（前回も紹介した）マジもんの聖書（著者が数学にお強いので・・・）
耐量子計算機暗号
代数的整数論
代数学シリーズの続き（具体例で困ったらこれを見ています）
整数論2: 代数的整数論の基礎
聖書（代数的整数論といえばこれ，みたいな風潮がずっとあります）
代数的整数論
個人的には一番好き（具体例は少なめですが）
整数論 (基礎数学)
素体
こちらもたまに見かける記述関連の話です
「\mathbb{Z} / p \mathbb{Z} を素体という」
p が素数のとき，\mathbb{Z} / p \mathbb{Z} は体なので，いかにもそれっぽい名前ですが，実は素体の定義は次のようになっています．
\underline{\mathrm{Def(素体,prime \ field)}}
自分自身以外に部分体を含まない体を素体という．
詳細は省きますが，\mathbb{Q} も素体です．\mathbb{Q} と \mathbb{Z} / p \mathbb{Z} しか素体は存在しないことが知られています．
だから，素体の「素」は素数を表しているわけではないことに注意してください．ただ，任意の体は \mathbb{Q} か \mathbb{Z} / p \mathbb{Z} を含み，\mathbb{Q} と \mathbb{Z} / p \mathbb{Z} はその中に体を含まないので，そのイメージが素数っぽい，でも今は体だから素体ということです（この辺の解釈は間違っているかもなので，有識者教えてください）．
これらの多項式環は次のようにかけます．
\underline{\mathrm{Def(\hat{\mathbb{T}}_N[X], \hat{\mathbb{Z}}_N[X])}}
q を2べきの自然数で N を自然数として，
\begin{align*}
\hat{\mathbb{T}}_N[X] &= \hat{\mathbb{T}}[X] / (X^N + 1) = (q^{-1} \mathbb{Z} / \mathbb{Z})[X] / (X^N + 1) \\
\hat{\mathbb{Z}}_N[X] &= \hat{\mathbb{Z}}[X] / (X^N + 1) = (\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1)
\end{align*}
と定める．
\mathbb{T} は
と同様に，\mathbb{T}_N[X] は
と同様に，\hat{\mathbb{T}}_N[X] は
ことに注意しましょう．
証明はさすがに省略します（気が向いたら書くかもです，第１回「Torus上の多項式」 と方針は同じです）
さてここから議論の流れが少し変わります．
これからは \hat{\mathbb{T}} を扱っていく・・・んですが，\hat{\mathbb{T}} と \hat{\mathbb{Z}} の元を見比べてください．各元を q 倍しただけしか違いがありません．
よって，\hat{\mathbb{T}} を扱っていく代わりに今後はより扱いやすい，\hat{\mathbb{Z}} で考えていくことになります．
流れをまとめると，
始めは Torus \mathbb{T} を考えていた
\rightarrow Torus の元１つだけでなく，多項式（ベクトル）として \mathbb{T}[X] で考える
\rightarrow 計算機上で扱えるように多項式の長さを制限すべく \mathbb{T}_N[X] で考える
\rightarrow 計算機上で扱えるように多項式の長さを制限すべく \hat{\mathbb{T}}_N[X] で考える
\rightarrow 更に扱いやすくするために，\hat{\mathbb{Z}}_N[X] で考える
という感じです．
そして，\hat{\mathbb{T}}_N[X] では定義できなかった掛け算が，\hat{\mathbb{Z}}_N[X] では定義できるようになる，というのが後々で効いてきます．が，この辺は第３回の話です．
掛け算について
簡単には，\hat{\mathbb{T}} だと，掛け算は「定義できない」が，\hat{\mathbb{Z}} だと，掛け算は「定義できるし，well-definedである」ということです．
＊well-defined については，下記を参照してください
参照：第１回「Torus」 の折りたたみ「トーラス内の掛け算」
\hat{\mathbb{T}} については，
分母の q の指数は1のみ許されていますが，掛け算をすると，指数が2以上になるためです．
と解説したとおりです．
\hat{\mathbb{Z}} については，任意の a, b \in [0, q - 1] を取って，a + m q と b + n q の積を考えます．
すると，(a + m q)(b + n q) = ab \ \mathrm{mod} \ q となり，well-defined 性もOKです．
3章前説の議論
さて，ここからが本番なのですが，議論をただ追うのは理解したことにならない（数学科っぽいこと言ってる）ので，
- 論文中に出てくる定義や定理の仮定が誤っていると判断したら，修正版を記載する（なぜ誤りかの理由も記載する）
- 定義や定理の仮定の一部を落とすと，どのような反例があるかを提示する
- 式を追うだけではなく，どういうモチベーションがあるのかを説明する（これを目指して，こう式変形する的な）
- （広く見て）論文中の定理の証明はskecthを用意する（証明の方針のこと）
- 式の厳密性とイメージ（お気持ち）の両方を解説する
以上の点に注意していきます．ゼミっぽい．
個人的には「イメージ」を「式」で厳密にする感覚で進めます（もちろん全部が全部できるわけではないですが）．
定義や定理の仮定の一部を落とす，っていうのは今回の「TLWEとTRLWE」でもやっています．
TLWE問題とはNP困難な問題でした．暗号理論では，NP困難な問題を背景に暗号方式が作られます．
重要なことは，a と r が分かっても，s は簡単には分からないことです．
TLWEを振り返ってみると
自然数 n が与えられて，s = (s_1, s_2, \cdots, s_n) \in \mathbb{B}^n を秘密鍵として，r \in \mathbb{T}, \ a = (a_1, a_2, \cdots, a_n) \in \mathbb{T}^n とノイズ e が与えられたときに，\displaystyle r = \sum_{j = 1}^n s_j \cdot a_j + e なる s を求めるのが難しい
ということでした．
実際の暗号化では，\mu \in \mathbb{T} なる平文に対して，a と r + \mu を送信します．論文では，a = (a_1, a_2, \cdots, a_n) \in \mathbb{T}^n と \mathbb{T} が和で閉じていることから \mu + r \in \mathbb{T} なので，これらの組として，c = (a_1, a_2, \cdots, a_n, \mu + r)\in \mathbb{T}^{n + 1} を暗号文を送信します．
以上がTLWEについてです．
そして，TRLWEに拡張しましょう．TRLWEはTLWEの実数部分を実数多項式へ拡張すればいいのでした．上との対比を見てみましょう．
TRLWEを振り返ってみると
自然数 n, N が与えられて，\tilde{s} = (\tilde{s}_1, \tilde{s}_2, \cdots, \tilde{s}_n) \in \mathbb{B}_N[X]^n を秘密鍵として，\tilde{r} \in \mathbb{T}_N[X], \ \tilde{a} = (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n) \in \mathbb{T}_N[X]^n とノイズ \tilde{e} が与えられたときに，\displaystyle \tilde{r} = \sum_{j = 1}^n \tilde{s}_j \cdot \tilde{a}_j + \tilde{e} なる \tilde{s} を求めるのが難しい
ということでした．
実際の暗号化では，\tilde{\mu} \in \mathbb{T}_N[X] なる平文に対して，\tilde{a} と \tilde{r} + \tilde{\mu} を送信します．論文では，\tilde{a} = (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n) \in \mathbb{T}_N[X]^n と \mathbb{T}_N[X] が和で閉じていることから \tilde{\mu} + \tilde{r} \in \mathbb{T}_N[X] なので，これらの組として，\tilde{c} = (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n, \tilde{\mu} + \tilde{r})\in \mathbb{T}_N[X]^{n + 1} を暗号文を送信します．
Torus上かどうかに限らずLWEからRLWEへの拡張は毎回こんなテンションです．
しかしここでよく考えたいこととして，
-
\mathbb{T} の任意の元って計算機上で表せるの？
ということです．\mathbb{T} は0以上1未満の実数全体の集合ですので，無限集合になります．
先にこちらの問いを考えてみましょう．
-
\mathbb{Z} の任意の元って計算機上で表せるの？
これは無理です．そもそも計算機上で表せる数には限界があるからです．よって， 32bit なり 64bit 精度で以下は考えることにしましょう．
３２bit であれば，0以上 2^{32} - 1 までの全ての整数を実現できます．64 bit であれば，0以上 2^{64} - 1 までの全ての整数です．
すると，\Omega bit 精度では，0以上 q = 2^{\Omega} として q - 1 までの全ての整数を表せます．そして，この範囲の整数は \mathrm{mod} \ q での足し算と掛け算を考えることで，\mathbb{Z} / q \mathbb{Z} 内で考えれば良いことになります．\mathbb{Z} / q \mathbb{Z} を \hat{\mathbb{Z}} と書くわけです．
つまり，「\mathbb{Z} の任意の元は計算機上で表せない」ですが，「\mathbb{Z} / q \mathbb{Z} の任意の元は計算機上で表せる」ということになります．
0以上 q - 1 までの全ての整数を実現できるのなら，\cfrac{1}{q} 刻みで0以上 \cfrac{q - 1}{q} までの全ての有理数を実現できる，と考えるのは自然ではないでしょうか．
そこで出てくるのが \hat{\mathbb{T}} になります．
以上をまとめると，理論的には \mathbb{Z} や \mathbb{T} で考えればよかったものを，計算機上で扱うために離散化した \hat{\mathbb{Z}} や \hat{\mathbb{T}} で置き換えていきます． よって，本質的な議論が何か変わったわけではありません．
ただし，\hat{\mathbb{T}} 内では厳密に掛け算が定義されないことに注意してください（元々 \mathbb{T} 内の掛け算も考えてなかったので，あまり影響はないですが，気になる方は 第１回「Torus」 の折りたたみ「トーラス内の掛け算」を参照してください）．
そして，これらの多項式環として，\hat{\mathbb{T}}_N[X] や \hat{\mathbb{Z}}_N[X] も考えていきます．
以上で３章前説の議論は終わりです．
3章前説の議論の考察
ここでは本文の議論をもう１歩踏み込んだ考察をします．踏み込み方は人それぞれだと思うので，興味のない方は飛ばしてくださって構いません．
まず始めにこれは前説なのか・・・？立項した方がよかったんじゃない？という個人的な感想があります．
それはどうでもいいとして，気になったのは，\hat{\mathbb{T}} の離散化の仕方でした．結局 \hat{\mathbb{T}} = q^{-1} \mathbb{Z} / \mathbb{Z} で離散化するなら元々Torusなんてものを考える必要はなかったんじゃないかということです．
言い換えると，Torusは「0以上1以下の実数全体の集合」でしたが，「0以上1以下の有理数全体の集合」で \mathbb{Q} / \mathbb{Z} を全体とみなしてもよかったんじゃない？わざわざ実数で考えた意味は？って思っています．
おそらく TFHEに関する原論文 に何かしらの理由が書いてあるのかなと思うので，読んでみようかな or 有識者教えてください．
理論的に実数を含めたTorusの方が扱いやすいんだろうなって気はしていますが，\mathbb{Q} / \mathbb{Z} だとどこで理論が破綻するのか気になるところです．
現時点だと円分多項式とかが関係しているのかなぁと思ったり思わなかったり．
↑の疑問に答えてくれそうな論文を見つけました Ring-LWE in Polynomial Rings
lift
ここから3.1です．
「持ち上げ」関数についてです．定義域を拡張する関数と解釈できます．
\underline{\mathrm{Def(lift \ function)}}
\overline{x} \in \mathbb{Z} / q \mathbb{Z} に対して，\overline{x} に対応する代表元 x \in [0, q) を取る．このとき，lift関数を次のように定める:
\mathrm{lift} : \mathbb{Z} / q \mathbb{Z} \ni \overline{x} \mapsto x \in \mathbb{Z}
元の取り方について
ここで言いたいことは \mathbb{Z} /q \mathbb{Z} から元を取る，と言ったときは，[0, q - 1] から元を取る，と読み替えてください．今後も同様です．当たり前じゃんって思うかもしれませんが．
論文では
\mathrm{lift} : \mathbb{Z} / q \mathbb{Z} \ni \overline{x} \mapsto \overline{x} \in \mathbb{Z}
と定義しています．
しかし，前回の記事で書きましたが，\mathbb{Z} / q \mathbb{Z} は 整数ではなく集合 です．つまり，\overline{x} は集合を表しますが，これは \mathbb{Z} の 元ではなく部分集合 です．すると，\overline{x} \in \mathbb{Z} は間違っていて，\overline{x} \subset \mathbb{Z} が正しいです．
\mathbb{Z} / q \mathbb{Z} の代表元を対応させる関数と思えばいいんじゃないの？と思う方もいらっしゃるかもしれません．
すると，今度は well-defined 性の問題が生じます．代表元の取り方に依存するってやつですね．
＊この辺は前回の記事の「Torus」の折りたたみ「Torus内の掛け算」を参照してください
この問題を解決するには，事前に \mathbb{Z} / q \mathbb{Z} の代表元の取り方を指定する必要があります．そこで，上記の定義では [0, q) に制限したわけです．
この辺の集合としてみていいのか否か，という感覚は少し難しいですが，一旦厳密に考えてみて，良さそうなら集合を数とみなしてみてください．
一見すると何もやっていない関数のように思えますが，後で q で割ることを考えます．
すると \mathbb{Z} / q \mathbb{Z} では0で割ることに対応してしまいますので，それを避けるために一旦定義域を広げる必要があります．
これはプログラム的には，例えば，
int a = 1;
long long b = pow(2, 11);
b += (long long)a;
みたいな感じです．long long 内での足し算を行うには，aの定義域を int から long long に一旦広げる必要があります．
定義から分かりますが lift は単射です．数学に詳しい方は，次のように書いた方が馴染みがあるかもしれません．
\mathrm{lift} : \mathbb{Z} / q \mathbb{Z} \hookrightarrow \mathbb{Z}
Upper
続いてUpper関数についてです．
以下では p, q を2べきで 2p \leq q とします．つまり，p = 2^m, q = 2^n としたとき，m + 1 \leq n です．
このとき，x_H \in \mathbb{Z} / q \mathbb{Z} と \displaystyle x_L \in \left [0, \frac{q}{2p} - 1 \right] を任意に取って，x \in \mathbb{Z} / q \mathbb{Z} を \displaystyle x = x_H \frac{q}{p} \pm x_L と表します．\pm はどちらを選択してもいいとします．
Upper関数とは，上記の x_H \frac{q}{p} を返す関数です．
\underline{\mathrm{Def(Upper \ function)}}
x_H \in \mathbb{Z} / q \mathbb{Z} と \displaystyle x_L \in \left[ 0, \frac{q}{2p} - 1 \right] を任意に取って，x \in \mathbb{Z} / q \mathbb{Z} を \displaystyle x = x_H \frac{q}{p} \pm x_L とする．
このとき，Upper 関数を次のように定める:
\begin{align*}
\displaystyle
\mathrm{Upper}_{q, p} : \mathbb{Z} / q \mathbb{Z} \ni x \mapsto \frac{q}{p} \left \lfloor \frac{p \ \mathrm{lift}(x)}{q} \right \rceil \in \mathbb{Z} / q \mathbb{Z}
\end{align*}
返り値のチェック
仮定から
\begin{align*}
\displaystyle
\mathrm{Upper}_{q, p}(x)
& = \frac{q}{p} \left \lfloor \frac{p \ \mathrm{lift}(x)}{q} \right \rceil \\
& = \frac{q}{p} \left \lfloor \frac{p}{q} x \right \rceil \\
& = \frac{q}{p} \left \lfloor \frac{p}{q} \left( x_H \frac{q}{p} \pm x_L \right) \right \rceil \\
& = \frac{q}{p} \left \lfloor x_H \pm \frac{x_L}{2^{n - m}} \right \rceil \\
\end{align*}
が成り立ちます．このとき，0 \leq x_L \leq 2^{n - m - 1} - 1 ですから，\displaystyle \frac{x_L}{2^{n - m}} < \frac{2^{n - m - 1}}{2^{n - m}} = \frac{1}{2} ですので，
\begin{align}
\displaystyle
\left \lfloor x_H \pm \frac{x_L}{2^{n - m}} \right \rceil = x_H
\end{align}
となり，無事に \displaystyle \mathrm{Upper}_{q, p}(x) = \frac{q}{p} x_H が得られました．
x_L の範囲について
論文中では \displaystyle 0 \leq x_L \leq \frac{q}{2p} と定義されていますが，これは間違っています．\displaystyle 0 \leq x_L < \frac{q}{2p} が正しいです．
これは，\displaystyle x_L = \frac{q}{2p} の場合だと，\displaystyle \frac{x_L}{2^{n - m}} = \frac{1}{2} ですので，上の(1)の \pm が + か - によって，値が異なります．特に + のときは，x_H と一致しません．
具体的に書くと，
\begin{align*}
\displaystyle
\left \lfloor x_H + \frac{x_L}{2^{n - m}} \right \rceil = \left \lfloor x_H + \frac{1}{2} \right \rceil = x_H + 1 \\
\left \lfloor x_H - \frac{x_L}{2^{n - m}} \right \rceil = \left \lfloor x_H - \frac{1}{2} \right \rceil = x_H \\
\end{align*}
ですね．
そもそも \pm はどう取るか定義されていないのも問題ですが，どちらを取っても良いと解釈できるので，そうすると，上記の場合で破綻します．
定義から，0以上 q - 1 以下の整数を \cfrac{q}{p} の倍数に返す関数と思えます．
何が「Upper」ぽいのかとx_L の定義域が [0, \frac{q}{2p} - 1] であるもう少しダイレクトな理由は，同じく今回の「3.1の議論」 のデコード太字部で解説しています．
3.1の議論
最後に cleartext から plaintext への変換の話を紹介して今回は終了します．
ここでは一旦 TLWE や TRLWE のことは忘れてください．
- cleartext と plaintext について
- エンコードとデコードの関係
- エンコード
- デコード
- エンコードとデコードの具体例
の順で説明します．
以下，自然数 N, w, \Omega, \bar{w} を固定します．
cleartext と plaintext について
まず，cleartext と plaintext の2つについて説明します．
cleartext とは，俗にいうメッセージのことです．plaintext は「暗号化アルゴリズム」の input のことです．イメージとしては，cleartext が実際の文章で，plaintext が bit 変換とか思うといいかと（実際には下記のようにもっと色々やりますが）．
ここでは cleartext から plaintext へのエンコードとデコードを説明します．
＊エンコードは変に和訳しないで，エンコードと表現することにします．「暗号化」と言ったら，3.2 での plaintext から ciphertext への変換のことを指すことにします．
エンコードとデコードの関係
上記のエンコードとデコードではどのような関係があるかというと，任意の cleartext m に対して（定義域は後で正当化），エンコードアルゴリズム Encode とデコードアルゴリズム Decode があって，\mathrm{Decode(Encode(} m \mathrm{))} = m が成り立ちます．暗号化のアルゴリズムと同じですね．
エンコード
エンコードの結論を図解すると次のとおりです．
＊上記は，元の論文の4ページ記載のFig1 をスクショしたものです
それぞれのパラメタ w, \ \bar{w}, \ \Omega - (\bar{w} + w) について説明します．
まず \bar{w} です．
これは，準同型暗号では，plaintext の各係数 \mu_i の先頭数ビットに0をパディングする必要があります．ここで必要な bit 長を \bar{w} としています．
次に w です．
これは cleartext を m = (m_0, m_1, \cdots, m_{N - 1}) の文字列で各係数 m_i は w bit 長としています．
最後に \Omega - (\bar{w} + w) です．
まず，\Omega について．
これは，\hat{\mathbb{Z}}_N[X] を定義域とする plaintext \mu = \mu_0 + \mu_1 X + \cdots + \mu_{N - 1} X^{N - 1} を考えます．各係数 \mu_i は定義域が \hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z} = \mathbb{Z} / 2^{\Omega} \mathbb{Z} なので \Omega bit 長としています．
このときパラメタの間には \bar{w} + w \leq \Omega が成り立っているものと仮定します．後ろの \Omega - (\bar{w} + w) bit が余っていることに注意してください．
そして，後ろの余った \Omega - (\bar{w} + w) bit についてです．
今回の「3章前説の議論」では，この plaintext に \tilde{r} を加えるのでした．r にはノイズ \tilde{e} が含まれています．つまり，\mu の各係数 \mu_i \in \hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}, \ q = 2^{\Omega} に対して，ノイズ e_i が加わっている状況です．
ここでノイズを加える場所を後ろの余った \Omega - (\bar{w} + w) bit としているわけです．
厳密には，後ろ \Omega - (\bar{w} + w) - 1 bit にノイズを挿入します
以上で cleartext から plaintext へのエンコードが終わりです．上記の図をもとに振り返ると，左から順に
先頭 \bar{w} bit \cdots パディング用
中央 w bit \cdots cleartext の情報格納用
調整用 1 bit \cdots 0 が入る
後ろ \Omega - (\bar{w} + w) - 1 bit \cdots ノイズ格納用
ということになります．
デコード
plaintext x \in \mathbb{Z} / q \mathbb{Z} が与えられたとします．つまり x は \Omega bit 長です．
結論としては，x に Upper 関数を作用させれば復号できます．
また，Upper 関数は \Omega bit の文字列から先頭 \bar{w} + w bit の情報を取り出すように定義されていて，先頭の情報を取り出す様子が「Upper っぽい」 ことも解説します．
このとき，ノイズ部分を除いた先頭の \bar{w} + w bit 長の情報を取得できれば，\bar{w} は分かっているので，先頭の \bar{w} bit の0を取り除くことで，cleartext を復元できることになります．
では，どうやって x から先頭 \bar{w} + w bit 長を取得するかというと，そこで登場するのが Upper 関数です．
Upper 関数とは x \in \mathbb{Z} / q \mathbb{Z} に対して \displaystyle x = x_H \frac{q}{p} \pm x_L から \displaystyle x_H \frac{q}{p} を返す関数のことでした．q = 2^{\Omega}, \ p = 2^{\bar{w} + w} とすると，plaintext x = x_H \frac{q}{p} \pm x_L から \displaystyle x_H 2^{\Omega - (\bar{w} + w)} が返ってきます．
実は，この操作でノイズ部分を無視した先頭 \bar{w} + w bit が返ってきます．
実際に計算する
\begin{align*}
\displaystyle
\mathrm{Upper}_{q, p}(x)
&= \frac{q}{p} \left \lfloor \frac{p \ \mathrm{lift}(x)}{q} \right \rceil \\
&= 2^{\Omega - (\bar{w} + w)} \left \lfloor \frac{p}{q} \mathrm{lift}(x) \right \rceil \\
&= 2^{\Omega - (\bar{w} + w)} \left \lfloor \frac{1}{2^{\Omega - (\bar{w} + w)}} (x_H \frac{q}{p} \pm x_L) \right \rceil \\
&= 2^{\Omega - (\bar{w} + w)} \left \lfloor \frac{1}{2^{\Omega - (\bar{w} + w)}} (2^{\Omega - (\bar{w} + w)} x_H \pm x_L) \right \rceil \\
&= 2^{\Omega - (\bar{w} + w)} \left \lfloor 1 \pm \frac{1}{2^{\Omega - (\bar{w} + w)}} x_L \right \rceil \\
\end{align*}
であり，x_L の定義域は，x_L の範囲は [0, 2^{\Omega - (\bar{w} + w) - 1} - 1] なので，
\begin{align*}
\displaystyle & \left \lfloor 1 \pm \frac{1}{2^{\Omega - (\bar{w} + w)}} x_L \right \rceil \\
& <= \left \lfloor 1 \pm \frac{2^{\Omega - (\bar{w} + w) - 1} - 1}{2^{\Omega - (\bar{w} + w)}} \right \rceil \\
& = 1
\end{align*}
となり，\lfloor \cdot \rceil の中身はちょうど x_H です．よって，このときの返り値が 2^{\Omega - (\bar{w} + w)} x_H で，x_H を 2^{\Omega - (\bar{w} + w)} bit だけ左シフトさせたものであることが分かります．
上記の計算からも分かりますが，ノイズを格納する x_L の範囲が [0, 2^{\Omega - (\bar{w} + w) - 1} - 1] であって，[0, 2^{\Omega - (\bar{w} + w)} - 1] や [0, 2^{\Omega - (\bar{w} + w) - 1}] でない理由は，\lfloor \cdot \rceil の中身がノイズの部分がちょうどうまく消えて，x_H になるように調整されているため，ということです．
先ほども書きましたが，そこから先頭 \bar{w} bit と後ろの \Omega - (\bar{w} + w) bit（共に全て0）を取り除くと，無事に cleartext へ復号できました．
エンコードとデコードの具体例
では，エンコードとデコードの具体例を紹介して終わりにします．
以下では，N = 4, \ w = 4, \ \Omega = 8, \bar{w} = 2 とします．つまり，p = 2^{\bar{w} + w} = 2^6 = 64, \ q = 2^{\Omega} = 256 です．
このとき，cleartext m = (m_0, m_1, m_2, m_3) \in (\mathbb{Z} / 2^w \mathbb{Z})^N = (\mathbb{Z} / 16 \mathbb{Z})^4 として，m_0 = 13, \ m_1 = 4, m_2 = 9, m_3 = 6 とします．つまり，それぞれの bit 表現を順に 1101, \ 0100, \ 1001, \ 0110 とします．
すると，plaintext \mu \in (\mathbb{Z} / 2^{\Omega} \mathbb{Z})^N = (\mathbb{Z} / 256 \mathbb{Z})^4 の各係数の bit 表現は 00110100, \ 00010000, \ 00100100, \ 00011000 となって，これを10進数に直すと \mu_0 = 52, \ \mu_1 = 16, \ \mu_2 = 36, \ \mu_3 = 24 です．確かに 2 bit だけ左シフトしているときに \mu_0 = 4 m_0, \ \mu_1 = 4 m_1, \ \mu_2 = 4 m_2, \ \mu_3 = 4 m_3 が成り立っています．
このとき，ノイズを考慮して，plaintext の各係数の後ろ1 bit に bit 反転が起こったり起こらなかったりを仮定します．つまり， \mu_0^{\prime}, \ \mu_1^{\prime}, \ \mu_2^{\prime}, \ \mu_3^{\prime} であって，bit 表現が 00110101, \ 00010000, \ 00100101, \ 00011001 のように変換したとします．すると，10進数に直したとき \mu_0^{\prime} = 53, \ \mu_1^{\prime} = 16, \ \mu_2^{\prime} = 37, \ \mu_3^{\prime} = 25 になります．
\mu_0^{\prime}, \ \mu_1^{\prime}, \ \mu_2^{\prime}, \ \mu_3^{\prime} のそれぞれに対して，Upper関数を作用させることを考えると，
\begin{align*}
\displaystyle
\mathrm{Upper}_{p, q}(\mu_0^{\prime}) & = \frac{q}{p} \left \lfloor \frac{p \mu_0^{\prime}}{q} \right \rceil = 2^2 \left \lfloor \frac{1}{2^2} 53 \right \rceil = 2^2 \cdot 13 \\
\mathrm{Upper}_{p, q}(\mu_1^{\prime}) & = \frac{q}{p} \left \lfloor \frac{p \mu_1^{\prime}}{q} \right \rceil = 2^2 \left \lfloor \frac{1}{2^2} 16 \right \rceil = 2^2 \cdot 4 \\
\mathrm{Upper}_{p, q}(\mu_2^{\prime}) & = \frac{q}{p} \left \lfloor \frac{p \mu_2^{\prime}}{q} \right \rceil = 2^2 \left \lfloor \frac{1}{2} 37 \right \rceil = 2^2 \cdot 9 \\
\mathrm{Upper}_{p, q}(\mu_3^{\prime}) & = \frac{q}{p} \left \lfloor \frac{p \mu_3^{\prime}}{q} \right \rceil = 2^2 \left \lfloor \frac{1}{2} 25 \right \rceil = 2^2 \cdot 6
\end{align*}
となります．
これでちゃんと plaintext の各係数に対して \mathrm{Decode(Encode(} m \mathrm{))} = m が成り立っていることが確認できました．
以上で3.1の議論は終わりです．
3.1の議論の考察
ここでは本文の議論をもう１歩踏み込んだ考察をします．踏み込み方は人それぞれだと思うので，興味のない方は飛ばしてくださって構いません．
上記では議論の流れを綺麗にするために「Upper関数の定義」→「3.1の議論」という構成を取ってしまったため，
Upper関数というものがあって，それを使うために plaintext をあのような定義にしたのか・・・？
と思う方もいらっしゃるかもしれませんが，個人的には逆かなって思っています．
つまり，plaintext にエンコードの写真に載せた順番で「padding」・「cleartext」・「ノイズ」の情報を組み込もうと思ったら，自然とUpper関数が必要になることが分かります．
上記の大雑把なイメージ
大雑把に考えると，あの順番では
(plaintext の情報) = 2^{\Omega - (\bar{w} + w)} \cdot (padding と cleartext の情報) + (ノイズの情報)
という式を表すからです（もちろん上記は「数式」としては意味のないものです）．
つまり，そこから(padding と cleartext の情報)を引き出そうと思うと，
(padding と cleartext の情報) = \frac{1}{2^{\Omega - (\bar{w} + w)}} ((plaintext の情報) - (ノイズの情報))
と考えることができて，
(ノイズの情報) = (plaintext の情報) \mathrm{mod} \ 2^{\Omega - (\bar{w} + w) - 1}
でしたから，
(padding と cleartext の情報) = \frac{1}{2^{\Omega - (\bar{w} + w)}} ((plaintext の情報) - (plaintext の情報) \mathrm{mod} \ 2^{\Omega - (\bar{w} + w) - 1})
と考えることができます．そして，演算に依存しない形で書こうと思うと，
(padding と cleartext の情報) = \frac{1}{2^{\Omega - (\bar{w} + w)}} ((plaintext の情報) \pm (\frac{1}{2^{\Omega - (\bar{w} + w)}} (plaintext の情報) を四捨五入したもの) )
と考えられます．
最後の形を一般化すると，(plaintext の情報) を引数としたUpper関数になっていることが分かります．
そうは言われてもやっぱり
- Upper 関数の定義が作為的すぎる
- cleartext とノイズの情報の間に1 bit 挟むのが嫌
と思う方もいらっしゃるかもしれません．っていうか僕もそう思っています．
ここでは，plaintext に「ノイズ」・「cleartext」・「padding」の順で情報を組み込んだと仮定します．すると，実は上記の問題1はもう少しスッキリしますし，2は解決します．
上記を定式化して考察する
cleartext を w bit で，padding を \bar{w} bit とし，plaintext 全体を \Omega bit とします．
そして，先頭から \Omega - (w + \bar{w}) bit に「ノイズ」・続く w bit に cleartext で，後ろ \bar{w} bit に padding の情報を付与したとします．
＊「先頭から \Omega - (w + \bar{w} - 1) bit」ではないことに注意してください，つまりこの構成でうまく「cleartext」と「padding」の情報を抜き出せれば解決することになります
すると，plaintextの係数 \mu_i が \Omega bit で上記の構成のとき，x_H で「ノイズ」，x_L で「cleartextとpaddingの連結」を表すことにします．
＊今回の記事の「3.1の議論」 では逆でした
すると \mu_i = 2^{\bar{w} + w} x_H \pm x_L と考えることができて，x_L = \mu_i \ \mathrm{mod} \ 2^{\bar{w} + w + 1} とすれば一発ですし，
もしくは round 関数を使いたいなら，p = 2^{w + \bar{w}} として x_L = \left \lfloor \frac{p}{2q} \mu_i \right \rceil とすれば上記と同じ結果を表します．この辺の計算は 今回の記事の「Upper」 と同じです．
ですから，個人的には，「ノイズ」・「cleartext」・「padding」の順の方が見通しがいいんじゃないかなぁって思ったりしています．何か理由があるのかもしれませんが．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion