(完全)準同型暗号の最前線２（原理編）: TFHEの原理 #6 HomNAND

目次

1. (完全)準同型暗号の最前線1（入門編)
2. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #1 TLWE
3. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #2 TRLWE & SampleExtarctIndex
4. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX
5. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #4 Blind Rotate
6. [(完全)準同型暗号の最前線２（原理編）: TFHEの原理 #5 Identity Key Switching](# 目次
7. (完全)準同型暗号の最前線1（入門編)
8. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #1 TLWE
9. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #2 TRLWE & SampleExtarctIndex
10. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX
11. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #4 Blind Rotate
12. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #5 Identity Key Switching
13. (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #6 HomNAND←イマココ

全体の中での位置づけ

今までのものをくっつけてHomNAND、つまり暗号上でNANDを行う方法について述べます。

復号を使ったアイデア

実はアイデア自体はTLWEの暗号化・復号と加法準同型性だけでも説明できたりします。(そのうち#1の方に書き足すかも)

二つのTLWE暗号文を$(\mathbf{a}_0,b_0),(\mathbf{a}_1,b_1)$とし, その平文が$-1/8,1/8$のいずれかであるとします.
TLWEの加法準同型性から以下の計算を行うことができます.
$$-(\mathbf{a}_0,b_0)-(\mathbf{a}_1,b_1)+(\mathbf{0},1/8)$$
この結果として出てくる出力TLWE暗号文の平文は明らかに$-1/8,1/8,3/8$のいずれかです.
また, 実際に計算してみればわかるとおり, $-1/8$となるのは両方の入力暗号文の平文が$1/8$である場合だけです.
この出力暗号文に対して復号関数を適用すると符号が正の場合は$1$を, 負の場合は$0$を返すため, これは両方の入力が$1$の場合だけ$0$を返す, つまりNANDを計算している関数であると見なすことができます.

Bootstrappingを使ったアイデア

ここまで読まれている方はおそらくお気づきだと思いますが, Bootstrappingは復号を暗号上で実行する関数ですから, 上で述べていたアイデアを暗号上で実行できます.
あたりまえですが, 上で述べたアイデアは復号関数の適用を前提としているので, 復号をしなかった場合$3/8$が出てしまう場合があり平文空間の外に出てしまうので複数の演算を行うことができません.

終わりに

とりあえずなんか下書きに残ってたので出したんですが, 何なら最初から書き直しても色々足せる気はしますね......また更新したいところですが