基于格密碼全同態(tài)加密的數(shù)學(xué)基礎(chǔ)

--基于格密碼全同態(tài)加密的數(shù)學(xué)基礎(chǔ)

此情此景，我想先吟詩二首：

從文學(xué)的角度看，以上兩首詩比李白寫的稍微遜色一點(diǎn)，不過，從數(shù)學(xué)角度來看，簡(jiǎn)直可以獲得諾貝爾數(shù)學(xué)領(lǐng)域的文學(xué)獎(jiǎng)（可惜了，目前還沒有這個(gè)獎(jiǎng)項(xiàng)）。

以上是定場(chǎng)詩，本文旨在盡量少用數(shù)學(xué)公式的情況下，解釋清楚FHE（Fully Homomorphic Encryption,全同態(tài)加密）相關(guān)的數(shù)學(xué)基礎(chǔ)。話不多說，我們繼續(xù)。

一點(diǎn)定乾坤

當(dāng)時(shí)的故事是這樣的：

一個(gè)陽光明媚的下午，初三(一)班剛剛上完第二節(jié)數(shù)學(xué)課，老師講的是函數(shù)相關(guān)的內(nèi)容。陽光灑在我課桌上，溫暖的光線散射到眼睛里，而我卻盯著老師講的拋物線函數(shù)圖像，一動(dòng)也不動(dòng)。

當(dāng)時(shí)我本子上的圖像是下面這樣的：

發(fā)呆的時(shí)候，我們班里的泰勒同學(xué)去完廁所從教室前門走了進(jìn)來，我的座位正沖門口，可能是他發(fā)現(xiàn)了我在發(fā)呆，就徑直走了過來，跟我說：

“干嘛呢？大白天的，發(fā)什么呆?。俊?/p>

“發(fā)呆跟白天晚上有關(guān)系嗎？”我應(yīng)道，“別打擾我，我在思考一個(gè)深?yuàn)W的問題！”

“什么問題?。縿e思考了，我跟你說個(gè)事兒，我會(huì)魔法你知道嗎？”泰勒不僅沒走開，反而挨著我坐了下來。

“別扯了，我們又不是幼兒園的小朋友，都初三了，誰還相信魔法？！”我有點(diǎn)不耐煩，打算繼續(xù)思考我的深?yuàn)W的問題。

“你別不信啊，我眼睛有透視的能力”泰勒有點(diǎn)不依不饒，繼續(xù)說道：

“不信的話，你把你的草稿本合起來，別讓我看到，我可以在不看你本子的前提下，知道你畫的是什么函數(shù)”

“滾一邊兒去，我沒那閑工夫跟你玩兒”因?yàn)樘├沾驍辔业乃悸?，想趕緊轟他走。

“實(shí)在不信的話，我們?cè)囋嚥痪椭懒藛?？！”泰勒不僅沒走，還挪了一下凳子，離我更近了。

“好吧，好吧，如果不靈的話，有多遠(yuǎn)滾多遠(yuǎn)，行不行？”我說。

“沒問題，這樣，你把你的函數(shù)圖像用兩本書遮起來，兩書之間只留一個(gè)點(diǎn)，我可以根據(jù)這一個(gè)點(diǎn)的信息得到整幅函數(shù)圖像！”泰勒顯得有點(diǎn)興奮。我自已也有點(diǎn)躍躍欲試。

“行啊，沒問題，就給你留一個(gè)點(diǎn)，看你怎么猜！”我心想，別說一個(gè)點(diǎn)，就是給你十個(gè)點(diǎn)，你能猜出來的話，我也算你贏。

我邊說邊把草稿本打開，用語文書和英語書遮住，中間只留了一個(gè)小縫兒，我自己剛剛能看到橫軸上‘1’對(duì)應(yīng)的那一點(diǎn)點(diǎn)圖像。

“行了，我準(zhǔn)備好了，猜吧！”我說。

“好，現(xiàn)在正式開始，不過我要先問你幾個(gè)問題”泰勒說。

“問吧，問吧！”我說。

“請(qǐng)問，在這個(gè)點(diǎn)，這個(gè)函數(shù)的一階導(dǎo)數(shù)是多少？”泰勒正式開始了他莫名其妙的發(fā)問。

“一階導(dǎo)數(shù)？是2”我略作思考，回答道。

“二階導(dǎo)數(shù)呢？”泰勒繼續(xù)問。

“還是2”我腦筋微轉(zhuǎn)，答道。

“三階導(dǎo)數(shù)呢？”泰勒繼續(xù)問。

“三階導(dǎo)數(shù)??？是0”我快速說道。

“四階導(dǎo)數(shù)呢？”泰勒還要問，沒有停下來的意思。

“哎呀，你煩不煩，三階導(dǎo)數(shù)后面所有的導(dǎo)數(shù)都是0”我說。

這時(shí)，只見泰勒嘴角上揚(yáng)，微微一笑，說：“你畫的函數(shù)是,對(duì)不對(duì)?。?！”

“這怎么可能？！”我很是驚訝，僅僅通過一個(gè)點(diǎn)的信息，泰勒怎么會(huì)知道整幅函數(shù)圖像的呢？

只見泰勒那時(shí)的表情，得意洋洋，心滿意足，開始手舞足蹈。。。

我還是不信，懷疑剛才泰勒偷看到了我的草稿本兒。所以我又緊接著測(cè)試了，甚至還測(cè)試了，還有很多其它很復(fù)雜的函數(shù)，令人震驚的是，這些函數(shù)，無一例外，泰勒都只通過一個(gè)點(diǎn)就猜出來了。

“怎么樣？這回相信我會(huì)魔法了吧？！”泰勒見我不解，輕飄飄撂下這句話就走開了，只留下凌亂的我，張著嘴巴，一臉懵。。。

“還真是啊，‘一點(diǎn)定乾坤’，難道說的就是這個(gè)？”我不禁自言自語。

讀到這里，聰明的同學(xué)可能早就可以拆穿泰勒所謂的魔法了，不過我實(shí)在是愚鈍，我們繼續(xù)往下看。。。

一時(shí)含永遠(yuǎn)

泰勒同學(xué)前腳剛走，我的另外一個(gè)叫傅里葉的同學(xué)就跑了過來，他好像是看到了我和泰勒玩的游戲，跟我說：

“泰勒那哪叫魔法啊，我會(huì)的才是真正的魔法，我可以讓時(shí)間停止，讓瞬間變永恒”

“你跟泰勒一個(gè)德性，凈扯玄乎兒的，把我當(dāng)幼兒園小朋友?！蔽疫€在琢磨剛剛泰勒是怎么做到的。

“你不相信的話，我們也做個(gè)游戲試試”傅里葉不想放棄展示他的魔法。

“沒問題，直接開始吧，你說怎么玩？”我說。

“好，我的第一個(gè)問題是，當(dāng)的時(shí)候，函數(shù)的值是多少？”見我同意玩，傅里葉也是開門見山，一下子問出了第一個(gè)問題，其實(shí)，也是唯一的一個(gè)問題。

我奮筆疾書，畢竟x是個(gè)e指數(shù)，還包含三角函數(shù)的角度，但是，我真正計(jì)算才發(fā)現(xiàn)，根本用不到筆算，口算就可以。我都一一回答了。當(dāng)然，在這過程中，我把本子捂得很緊，沒敢讓他偷看一眼。

“我知道了，你的函數(shù)是，對(duì)不對(duì)??！”傅里葉得意的問。

“我K，你是怎么知道的？！，難道傳說中的‘一時(shí)含永遠(yuǎn)’，說的就是你？！”我被徹底震驚了。

。。。

。。。

。。。

好吧，我承認(rèn)，泰勒和傅里葉不是我的同學(xué)，上面的故事都是編的。我也是實(shí)在編不下去了，很多聰明的同學(xué)也早就發(fā)現(xiàn)了泰勒和傅里葉的秘密。

泰勒的秘密就是：

對(duì)于任何一個(gè)光滑函數(shù)，都可以表示為多項(xiàng)式的形式，而多項(xiàng)式的系數(shù)可以通過某一點(diǎn)的導(dǎo)數(shù)獲得。

是的，你沒看錯(cuò)，一個(gè)點(diǎn)竟然蘊(yùn)含了一個(gè)函數(shù)的所有信息。

傅里葉的秘密是：

對(duì)于任何一個(gè)光滑函數(shù)，都可以表示為三角函數(shù)累加（積分）的形式，而每一項(xiàng)的系數(shù)可以通過多個(gè)點(diǎn)的自變量和因變量對(duì)兒（x, f(x)）獲得。

是的，你沒看錯(cuò)，我們手機(jī)里的歌曲，不管你播不播放，他總是呆在那里，不曾改變。一個(gè)隨時(shí)間變化的信號(hào)，經(jīng)過傅里葉變換之后，時(shí)間將消失，音樂會(huì)上一段美妙的音樂，不過是樂譜的再一次重復(fù)，而無論重復(fù)多少次，樂譜從未發(fā)生絲毫改變。

以上被稱為“感覺第一定理”。

對(duì)于喜歡看公式的同學(xué)（對(duì)于不喜歡看數(shù)學(xué)公式的同學(xué)，直接跳過公式部分，絲毫不用擔(dān)心會(huì)影響你對(duì)本文的理解），就是：

泰勒公式一句話描述：就是用多項(xiàng)式函數(shù)去逼近光滑函數(shù)。

傅里葉變換一句話描述：將用一般多項(xiàng)式表示的時(shí)域的信號(hào)，變成頻域的信號(hào)（這句不懂沒關(guān)系，看完后面就懂了）。

你在其它地方看到的傅里葉變換可能是下面的樣子：

那是因?yàn)闅W拉這位同學(xué)的存在，可以把e指數(shù)變成三角函數(shù)的形式。

歐拉公式：

所以，我總結(jié)下來，就是，對(duì)于任何一個(gè)函數(shù)，都可以用一些簡(jiǎn)單的東西的線性組合得到。這里面提到的簡(jiǎn)單的東西，就可以認(rèn)為是搭積木的一個(gè)個(gè)小積木塊，用數(shù)學(xué)的語言，小積木塊就是函數(shù)的基。用線性代數(shù)的語言，小積木塊就是單位向量。而具體的函數(shù)，就是用小積木塊搭出來的各種形狀的積木，以及用單位向量組成的一般向量。

以上被稱為“感覺定理-2”

彎路走的快

稍作休息，我又可以繼續(xù)編故事了，還是續(xù)集。

傅里葉同學(xué)說完答案，同樣留下一頭霧水的我，瀟灑的走開了。當(dāng)時(shí)，我腦袋里真是一團(tuán)漿糊，泰勒同學(xué)的秘密還沒搞懂，又來一個(gè)傅里葉的秘密。秘密加秘密，我就更摸不著頭腦了。

正當(dāng)我一籌莫展之際，我的第三位同學(xué)-凱萊出現(xiàn)在了我的面前。還沒等我張口請(qǐng)教，凱萊就發(fā)話了：

“泰勒和傅里葉的三腳貓功夫，有啥了不起的，在我看來，不就是多項(xiàng)式的兩種表示形式而已。”

“多項(xiàng)式，我知道，不過，我只知道一種形式，另外一種是啥？”我問。

凱萊，不像泰勒和傅里葉，他舉止優(yōu)雅，陣腳不亂，簡(jiǎn)稱“矩陣”（sorry，這是個(gè)諧音梗）。

“不用著急，聽我給你慢慢說”凱萊搬了自己的凳子來，輕坐在我旁邊。

你看啊，我們一般見到的多項(xiàng)式是下面這樣的，叫多項(xiàng)式的系數(shù)表示法。

這其中的就是多項(xiàng)式的系數(shù)，所以叫“系數(shù)（coefficient）表示法”，沒錯(cuò)，數(shù)學(xué)就是這么直白。

除了系數(shù)表示法之外，還有一種，叫“點(diǎn)值表示法（point-value representation）”，顧名思義，就是用這個(gè)多項(xiàng)式上的點(diǎn)，以及這點(diǎn)對(duì)應(yīng)的值來表示。

比如，上面的多項(xiàng)式，用點(diǎn)值表示法，就是：

看到這里，我就有點(diǎn)不太理解了，為啥點(diǎn)值表示法也能代表這個(gè)多項(xiàng)式呢？凱萊，不緊不慢，耐心解釋道：

你看啊，點(diǎn)值表示法里面的每一對(duì)點(diǎn)值，是不是表示下面一個(gè)等式,比如，第一對(duì)兒點(diǎn)值，表示的就是下面的一個(gè)等式。

第二對(duì)兒點(diǎn)值對(duì)應(yīng)的是下面的等式：

從點(diǎn)值表示法來看，本來在一個(gè)平面上有無數(shù)條曲線，每次確定一個(gè)點(diǎn)，就要求我們想要的曲線必須經(jīng)過這個(gè)點(diǎn)，當(dāng)我們確定的點(diǎn)的數(shù)量和這條曲線的次數(shù)（就是上面式子中的n）相同時(shí)，我們就找到了經(jīng)過我們指定所有點(diǎn)的唯一一條曲線。這是“感覺定理-3”

這時(shí)，凱萊好像看出了我的心思，說：

“瞎想什么啊，太難理解了，我們初中生，剛學(xué)過矩陣，用矩陣表示比你那個(gè)‘真感情’容易多了！”

“什么意思?。俊蔽疫€是不太理解。

“你看啊。。。”凱萊又開始娓娓道來：

上面用點(diǎn)值表示法表示的多項(xiàng)式，每個(gè)點(diǎn)值對(duì)兒都對(duì)應(yīng)一個(gè)方程，如果我們把他們組合到一起，寫成矩陣的形式，不就是下面這個(gè)樣子嗎：

點(diǎn)值表示法，就是上面三個(gè)矩陣，第1個(gè)和第3個(gè)，分別表示“點(diǎn)”和“值”，第2個(gè)矩陣是多項(xiàng)式的系數(shù)。當(dāng)其中第1個(gè)和第3個(gè)矩陣都確定的情況下，第2個(gè)系數(shù)矩陣其實(shí)也就確定了。所以，從這個(gè)角度看，點(diǎn)值表示法和系數(shù)表示法，只是同一個(gè)函數(shù)的兩種表示方式，就好像同一個(gè)函數(shù)既可以按泰勒同學(xué)的方式展開，也可以按傅里葉同學(xué)的方式展開，兩種方式描述的其實(shí)是一個(gè)東西。

就好像光的波粒二象性似的，泰勒同學(xué)強(qiáng)調(diào)的是粒子性，而傅里葉同學(xué)強(qiáng)調(diào)的是波動(dòng)性。或者說，系數(shù)表示法強(qiáng)調(diào)的是函數(shù)的波動(dòng)性，點(diǎn)值表示法更多體現(xiàn)函數(shù)的粒子性。此為“感覺定理-4”.

凱萊同學(xué)啰啰嗦嗦的說了半天，我也不知道說了些什么東西，就問：

“凱萊，你說的點(diǎn)值法，我是聽懂了，可我沒看出點(diǎn)值法有啥用處啊”

“這個(gè)用處可就太大了，可以加速多項(xiàng)式乘法！”凱萊說。

你看啊，比如，我們有兩個(gè)用系數(shù)表示法表示的多項(xiàng)式：

那么這兩個(gè)多項(xiàng)式的乘法結(jié)果的計(jì)算過程如下所示：

這個(gè)多項(xiàng)式乘法的復(fù)雜度是，另外還要注意的是，“多項(xiàng)式乘法”中的“乘法”兩個(gè)字非常容易產(chǎn)生誤導(dǎo)作用，給人一種真的是普通乘法的錯(cuò)覺，其實(shí)，多項(xiàng)式的乘法操作，實(shí)際上就是卷積運(yùn)算，這一點(diǎn)一定要謹(jǐn)記。

“卷積？有什么特殊的呢？這和點(diǎn)值表示法有啥關(guān)系??？”我還是似懂非懂的問。

“別著急啊，還記得剛剛走的傅里葉同學(xué)嗎？他剛剛使用的秘密武器就是傅里葉變換，還記得嗎？”凱萊問我。

“當(dāng)然記得，傅里葉變換可以讓時(shí)間消失的，太厲害了，可以將時(shí)域的信號(hào)，變成頻域的信號(hào)！”我說。

“完全正確！”凱萊對(duì)我的回答非常滿意，他接著說：

“多項(xiàng)式的乘法（也就是卷積運(yùn)算），可以先將兩個(gè)多項(xiàng)式分別做傅里葉變換，變完之后的兩個(gè)式子，直接對(duì)應(yīng)項(xiàng)相乘，對(duì)應(yīng)項(xiàng)相乘完之后的結(jié)果再做傅里葉逆變換，得到的結(jié)果就是兩個(gè)原始多項(xiàng)式的乘法結(jié)果！??！”凱萊興奮的嚷道。

“這個(gè)我知道，這不就是卷積定理嘛！卷積定理說的是，在一個(gè)域的相乘等于另一個(gè)域的卷積，用式子表示，就是下面這樣子的”我補(bǔ)充道。

“可是，這個(gè)和你前面提到的矩陣有什么關(guān)系?。?！又和多項(xiàng)式的點(diǎn)值表示法有什么關(guān)系?。?！”我還是沒完全理解凱萊的意思。

“不用著急，這兩個(gè)問題很快你就明白了，只需最后一步！”凱萊還是慢條斯理的樣子。

“最后一步？什么最后一步啊？”我問。

你看啊，其實(shí)啊，點(diǎn)值表示法有個(gè)非常大的好處，我之前沒提到，就是：

對(duì)于用點(diǎn)值表示法表示的兩個(gè)多項(xiàng)式的乘法（實(shí)際是卷積），可以直接對(duì)應(yīng)項(xiàng)相乘即可，即，

“我知道了，凱萊，原來復(fù)雜度為的多項(xiàng)式乘法運(yùn)算，復(fù)雜度降低成了”我好像發(fā)現(xiàn)了什么新大陸，也吼了起來。

“不對(duì)啊，好像哪里不對(duì)啊，這個(gè)復(fù)雜度的降低要想實(shí)現(xiàn)，需要先把系數(shù)表示法變成點(diǎn)值表示法才行啊！，這個(gè)從系數(shù)轉(zhuǎn)點(diǎn)值的復(fù)雜度也是啊，你這搞半天不是瞎搞了嗎！本來可以有直行的路可以到達(dá)，你這越走越遠(yuǎn)??！”我剛剛發(fā)現(xiàn)的新大陸瞬間又不香了，滿臉狐疑的看著凱萊。

“不對(duì)啊，好像哪里不對(duì)啊，這個(gè)復(fù)雜度的降低要想實(shí)現(xiàn)，需要先把系數(shù)表示法變成點(diǎn)值表示法才行啊！，這個(gè)從系數(shù)轉(zhuǎn)點(diǎn)值的復(fù)雜度也是啊，你這搞半天不是瞎搞了嗎！本來可以有直行的路可以到達(dá)，你這越走越遠(yuǎn)啊！”我剛剛發(fā)現(xiàn)的新大陸瞬間又不香了，滿臉狐疑的看著凱萊。

“你別著急啊，你再仔細(xì)看看，你說的沒錯(cuò)，如果是一般的系數(shù)變點(diǎn)值，復(fù)雜度確實(shí)降不下來，可是，如果我取得點(diǎn)是一些特殊的點(diǎn)的話，情況就完全不一樣啦”凱萊繼續(xù)給我解釋，不緊不慢。
“取什么樣的點(diǎn)，才能降低復(fù)雜度呢？哦！我知道了，復(fù)數(shù)域的單位根，復(fù)數(shù)域的單位根，復(fù)數(shù)域的單位根！”我連續(xù)說了三遍，生怕凱萊聽不清楚。
在復(fù)數(shù)域內(nèi)，方程有個(gè)根，就叫單位根，這些根分別是：

就是前面傅里葉同學(xué)表演“一時(shí)含永遠(yuǎn)”魔法的時(shí)候用的那幾個(gè)點(diǎn)?。∵@幾個(gè)點(diǎn)太好了，口算就能知道對(duì)應(yīng)的函數(shù)值，這樣的話，系數(shù)到點(diǎn)值的轉(zhuǎn)換就簡(jiǎn)單多了。
“是的，你終于發(fā)現(xiàn)了傅里葉變換的另外一個(gè)秘密，就是傅里葉變換，其實(shí)就是多項(xiàng)式的系數(shù)轉(zhuǎn)點(diǎn)值，當(dāng)然，我們考慮的是離散的傅里葉變換（DFT）”凱萊繼續(xù)說道。
“嗯，后面我就知道了，DFT有個(gè)快速算法，叫FFT，F(xiàn)FT的計(jì)算復(fù)雜度是看到了希望，我又開心了起來。

為了防止忘記，我在心里又重新梳理了一下多項(xiàng)式乘法的過程：

多項(xiàng)式乘法本質(zhì)是卷積運(yùn)算

卷積運(yùn)算可以分三步：

a. 先把兩個(gè)多項(xiàng)式從系數(shù)表示變成點(diǎn)值表示，這一步就是DFT，可以用FFT加速，F(xiàn)FT采用分治法，可以將一根很長(zhǎng)的木棍兒每次都折半，這樣遞歸下去，就可以降低計(jì)算復(fù)雜度。FFT選用的是單位根，NTT選用的是原根，目的一樣，為了加速DFT, 相比于FFT，NTT還便于取模運(yùn)算。

b. 然后，將用點(diǎn)值形式的兩個(gè)多項(xiàng)式，對(duì)應(yīng)項(xiàng)相乘，就得到了最終結(jié)果的點(diǎn)值表示形式。

c. 最后，還需要把最終結(jié)果的點(diǎn)值表示變回系數(shù)表示

“前幾步上面都提到了，我也理解了，可這最后一步是怎么做到了？”雖然大部分的內(nèi)容我理解了，可再三回憶，最后一步確實(shí)沒聽凱萊說過。

“哎呀，這還不簡(jiǎn)單嗎？提示你一下，看看多項(xiàng)式的矩陣表示形式，對(duì)了，不用往上翻了，我們?cè)賹懸槐?，就是下面的樣子”凱萊嘿嘿一笑：

還是原來的配方，還是熟悉的味道。點(diǎn)值表示變回系數(shù)表示的過程，不就是已知上面的第1個(gè)矩陣和第3個(gè)矩陣，求中間的系數(shù)矩陣嘛？！

“原理我貌似有點(diǎn)懂了，可是，具體怎么求啊，我線性代數(shù)也學(xué)的不好”我繼續(xù)追問凱萊，凱萊畢竟是矩陣?yán)碚摰拇髱熂?jí)人物，這點(diǎn)小問題應(yīng)該難不倒他。果然，還不到1秒鐘的時(shí)間，凱萊就發(fā)話了：

“這個(gè)問題嘛，等式兩邊都乘上第1個(gè)矩陣的逆矩陣就可以了，注意啊，是“矩陣的逆：”，不是”矩陣的轉(zhuǎn)置：”，這個(gè)千萬別混淆了”凱萊細(xì)心的提醒我。
“知道啦，不過，矩陣的逆，復(fù)雜度可很大啊，是，你這又是南轅北轍?。?！”我又有被凱萊耍了的感覺。

“你說的沒錯(cuò)，上面的第一個(gè)矩陣，是一個(gè)特殊的矩陣，叫范德蒙矩陣，一般的范德蒙矩陣的逆，運(yùn)算復(fù)雜度也是，不過，但是，如果我們按照傅里葉同學(xué)的思路，搞出來的這個(gè)范德蒙矩陣是特殊中的特殊，它的逆矩陣，就是矩陣中的每個(gè)元素的共軛，再除以n，就是這么簡(jiǎn)單，哎喲，就是這么巧合，你說神奇不神奇”凱萊難得的大笑起來。用式子表示，就是下面這個(gè)樣子的：

這個(gè)矩陣的逆，就是：

“原來如此，原來如此啊，如果我記得沒錯(cuò)的話，點(diǎn)值到系數(shù)的變換過程就是傳說中的傅里葉逆變換，也叫IDFT，這個(gè)也有加速版本的IFFT?！蔽医K于恍然大悟，“彎路走的快”，誠(chéng)不欺我，有圖為證。

故事講到這里，我不禁又想起了最開始的兩首詩，史上最富含數(shù)學(xué)知識(shí)的文學(xué)作品，名副其實(shí)。不過，看標(biāo)題，內(nèi)容是同態(tài)加密啊，故事都講到這兒了，嘚啵嘚啵嘮半天嗑，咋同態(tài)加密的影兒都沒看著?。?！
別著急，這是同態(tài)加密的上篇，我們稍作休息，請(qǐng)等待后面的精彩故事。

此情此景，我想再吟詩二首：

話說上篇我們了解到了很多非常重要的內(nèi)容：

多項(xiàng)式從系數(shù)表示變成點(diǎn)值表示的過程，就是離散傅里葉變換（DFT/FFT）。

多項(xiàng)式從點(diǎn)值表示變成系數(shù)表示的過程，就是離散傅里葉逆變換(IDFT/IFFT)。

多項(xiàng)式的乘法，本質(zhì)是卷積運(yùn)算，一次卷積運(yùn)算可以分為三步：Convolution=FFT->multiply->IFFT,即卷積定理表達(dá)的內(nèi)容。

以上三種場(chǎng)景，都有相應(yīng)的矩陣操作與之對(duì)應(yīng)。原因是：一個(gè)多項(xiàng)式的點(diǎn)值表示和一個(gè)線性方程組對(duì)應(yīng)，線性方程組又和一個(gè)矩陣乘法運(yùn)算對(duì)應(yīng)，這樣多項(xiàng)式的乘法就可以轉(zhuǎn)換成FFT相關(guān)的計(jì)算。這一點(diǎn)非常重要，是理解FHE的關(guān)鍵所在。
仔細(xì)思考上篇中討論的內(nèi)容，加上上面幾點(diǎn)提示，這樣我們就把FHE相關(guān)的幾個(gè)非常重要的概念，以及這些概念之間的關(guān)系就搞清楚了，此時(shí)，我們的腦海里應(yīng)該出現(xiàn)以下幾個(gè)概念，并且這些概念不再是獨(dú)立的孤島，而是腦海里一片廣闊的大陸：泰勒公式，多項(xiàng)式，系數(shù)表示法，點(diǎn)值表示法，DFT，F(xiàn)FT，卷積，卷積定理，線性方程組，矩陣，矩陣的逆。

好，收拾行囊，我們繼續(xù)趕路，在正式向FHE山頂發(fā)起沖鋒前，我們有必要加深一下對(duì)傅里葉變換的理解，如下圖所示：

仔細(xì)查看上圖。。。在觀察這段時(shí)間里的某個(gè)時(shí)刻，一道金光從腦海劃過：為什么時(shí)間消失了？！我們感知到的隨著時(shí)間流淌的宇宙，進(jìn)行傅里葉變換后會(huì)怎樣？我們又該怎么選擇傅里葉變換的旋轉(zhuǎn)因子（twiddle factor）？如果你的腦海沒有金光劃過，可以先閱讀一下。

如果腦海里實(shí)在是沒有金光劃過，也沒關(guān)系，不會(huì)影響我們最終站上FHE的山頂。我們繼續(xù)。。。

在FHE領(lǐng)域，我們可能會(huì)反復(fù)看到一句話：“FHE是基于格密碼學(xué)的”。這句話很簡(jiǎn)短，既然反復(fù)看到，說明應(yīng)該很重要，可是，我從這句話里面又看不出什么東西，每個(gè)字我都認(rèn)識(shí)，但就是不知道整句話什么意思。什么道理都懂，仍然過不好一生。不用著急，我們慢慢拆解：

首先，這里面最難懂的可能是“格”這個(gè)字，于是，我們就百度里一下，“格”是這么定義的：

“ “格”是一種特殊的偏序集。”

也很簡(jiǎn)短，不過不出意外，還是每個(gè)字都認(rèn)識(shí)，但仍然不明白整句話說的是啥意思。按道理，既然名字叫“格”，應(yīng)該跟“格子”有關(guān)系??？！

于是，我們繼續(xù)查找FHE相關(guān)的資料，除了“格”這個(gè)東西，經(jīng)常出現(xiàn)的還有“環(huán)”這個(gè)概念，于是百度之，“環(huán)”定義的第一個(gè)條件是：

“ 集合R在+運(yùn)算下構(gòu)成阿貝爾群” 此外還有“理想（Ideal）”兩個(gè)字也出現(xiàn)在了附近。

也很簡(jiǎn)短，不過不出意外，還是每個(gè)字都認(rèn)識(shí)，但仍然不明白整句話說的是啥意思。按道理，既然名字叫“環(huán)”，應(yīng)該跟“鐵環(huán)、手環(huán)”之類的東西有關(guān)??？！

按圖索驥，從“環(huán)”的定義里，我們發(fā)現(xiàn)了“阿貝爾群”這幾個(gè)字，“阿貝爾”應(yīng)該是個(gè)人名，那“群”又是啥意思？！，于是，繼續(xù)百度之，

“在數(shù)學(xué)中，群表示一個(gè)擁有滿足封閉性、滿足結(jié)合律、有單位元、有逆元的二元運(yùn)算的代數(shù)結(jié)構(gòu)，包括阿貝爾群、同態(tài)和共軛類?！?br />
這句話相比之前“格”“環(huán)”的定義稍稍多了幾個(gè)字。欣喜的是，這句話中提到的幾個(gè)概念好像都知道什么意思，比如“結(jié)合律”，“單位元”，“共軛”等，此外，還見到了我們苦苦追尋的“同態(tài)”兩個(gè)字，相比最開始的漆黑一片，終于見到了幾個(gè)火星兒，希望有了，勝利可能就在眼前。。。

于是，我們沖向FHE這個(gè)山頂?shù)牡谝粭l路徑就出現(xiàn)在了我們眼前，那便是：群->環(huán)->域->格。雖然只有四個(gè)字，可每個(gè)字看起來都不是那么好搞定的，畢竟，我們好像依稀聽說過，“群論”，“環(huán)論”，“抽象代數(shù)”這幾個(gè)可怕的怪物，這么陡峭的山體，一不小心就可能摔得粉身碎骨，永遠(yuǎn)達(dá)不到矗立在山頂?shù)腇HE。

我駐足沉思，難道到山頂只有一條路可走？難道必須從山腳下的“群”開始？現(xiàn)在都是新時(shí)代，出門爬個(gè)山，累了都有纜車啊， FHE這座山真有沒有纜車可坐？如果FHE這座山?jīng)]有纜車，那么FHE這座山附近有沒有其它的山，如果有其它的山的話，有沒有可能在兩山的山頂建有“山頂纜車”？

一堆問題在我附近的空間里縈繞盤旋，我得不到回答，于是，在沒看到“山頂纜車”之前，我開始從山腳下的“群”開始一步一步地爬。。。群是有點(diǎn)抽象，剛開始確實(shí)不太容易理解，不過我走得很快，不一會(huì)就建立了“群，環(huán)，域”的簡(jiǎn)單概念。

繼續(xù)爬。。。

爬呀爬。。。
。。。
。。。
。。。
幾天以后。。。

又有一道金光劃過我腦海的上空，原本漆黑的海面上變得亮了起來。這道金光就是：

“很多格子擺在一起，看起來很像矩陣?。　?br />
是的啊，確實(shí)很多格子排列在一起，從遠(yuǎn)處看，就是一個(gè)矩陣啊，所以，“格”和“矩陣”之間一定存在某種關(guān)系！這個(gè)關(guān)系，不就是兩座山頂之間的“山頂纜車”嗎？！

“矩陣”，我們是比較了解的，如果矩陣和格之間建有山頂纜車的話，豈不美哉。

稍作驗(yàn)證，果不其然，我的想法是對(duì)的，“山頂纜車”早已建成，因?yàn)槲铱吹搅恕罢麛?shù)格”的定義：

“離散的基向量生成空間集合，稱之為整數(shù)格（Integer Lattice）”

這里面可能稍有難度的是“生成空間”，我們先來搞定它。

在線性代數(shù)中，如果我們要描述一個(gè)線性空間的話，我們需要先找到這個(gè)空間的一組基(Basis)。（PS：看到“基”這個(gè)字，你是不是又想起了傅里葉，想起了泰勒，想起了點(diǎn)值法，想起了消失的時(shí)間。。。）

比如常見的二維平面空間（笛卡爾坐標(biāo)系），我們可以選用x軸和y軸的單位向量，作為我們的基向量（或者叫單位向量），分別是：

這樣的話，任何XY坐標(biāo)系的向量都可以用上面的一組基來表示。即，

其中c_0和c_1可以是任意實(shí)數(shù)，如果是任意實(shí)數(shù)，那么v的所有可能的組合，就可以鋪滿整個(gè)二維平面空間，我們管所有的v組成的這個(gè)線性空間，就叫做，b_1兩個(gè)基向量的線性生成空間（Span）。

我們不難想象，如果c_0和c_1是實(shí)數(shù)，那么b_0，b_1的生成空間是“連成一片”的，可以叫“片”，但是，如果c_0和c_1是只能是整數(shù)的話，那么b_0，b_1的生成空間就由“片”變成了無數(shù)個(gè)離散的“點(diǎn)”，這些點(diǎn)整齊的排列在一起，非常像無數(shù)個(gè)小格子，我們把這樣的一個(gè)離散的生成空間，叫做“整數(shù)格（Integer Lattice）”。

果不其然，從“矩陣”到“格”，只有簡(jiǎn)單的一步，這個(gè)“山頂纜車”建得實(shí)在是太好了。

乘坐這條意外發(fā)現(xiàn)的纜車，我們快速抵達(dá)了“格”，這時(shí)，我們離FHE的核心腹地--LWE只有一步之遙了，加油，勝利就在眼前。

稍微瞄一眼上圖，我們就會(huì)發(fā)現(xiàn)，這確實(shí)是很多格子啊，“格”這個(gè)字用的還是挺好的。

有了Lattice（格），就有很多跟Lattice 有關(guān)的有意思的問題就出現(xiàn)了。比如，想要表達(dá)一個(gè)向量v：

我們會(huì)發(fā)現(xiàn)，這個(gè)向量沒辦法在整數(shù)格中表達(dá)它，因?yàn)檎麛?shù)格中的系數(shù)必須是整數(shù)才行啊。

好了，問題來了，既然不能用整數(shù)格完美表達(dá)v，那么，是否可以找到一個(gè)最接近v的v_0，而v_0可以用整數(shù)格完美表達(dá)。對(duì)于上面的例子：

這個(gè)就是著名的CVP（Closest Vector Problem）難題?。?br />
你可能會(huì)說，這算哪門子難題?。课乙幻腌娋推平饬?。

沒錯(cuò)，如果只是二維正交基向量的格，那么CVP問題不是特別難，但是，如果基向量不正交呢？如果v的維度變大到, 的成員的值變大到需要1000bit呢？

這個(gè)難度是被嚴(yán)格證明的，CVP問題是非常難解決的（Nondeterministic Polynomial hard, NP-hard）。

是的，這個(gè)乍看起來很簡(jiǎn)單，實(shí)際上很難的問題，就是格密碼學(xué)的開端。

“什么？！搞了這么久，我以為已經(jīng)達(dá)到了頂峰，竟然被你說成是‘開端‘？??！”

“是的，的確是格密碼學(xué)的開端，現(xiàn)實(shí)就是這么的殘酷，你以為的天花板，很可能只是別人的起點(diǎn)。比如，你家的天花板，可能只是樓上的地板，…^_^”

不過不要?dú)怵H，前面就是我們要找的LWE了。

在正式引入LWE之前，我們先回顧一下，送我們快速到達(dá)“格”的山頂纜車—矩陣。

是的，通過上篇的學(xué)習(xí)，我們?cè)缇椭懒?，一個(gè)矩陣乘的式子，對(duì)應(yīng)一個(gè)線性方程組：

其中A是一個(gè)矩陣，x是一個(gè)向量，b也是一個(gè)向量。

已知A和b，求x的過程，就是求解線性方程組的過程。具體就是在上篇提到的方法：等式兩邊都乘以的逆矩陣,乘完之后，等式左邊就只剩下我們要求出的未知向量了。

現(xiàn)在稍稍把上面的矩陣乘法等式變化一下：

其中e是一個(gè)在固定數(shù)值范圍內(nèi)隨機(jī)采集的一個(gè)隨機(jī)噪音向量。這時(shí)，之前“等式兩邊都乘以A的逆矩陣”的方法就不行了，那我們?cè)趺辞竽?？答案很?jiǎn)單：

“只能暴力破解”

也就是一個(gè)一個(gè)的猜x這個(gè)向量里的值，然后逐漸逼近。

這就是我們苦苦尋找的LWE(Learning With Error)問題！即：

已知一個(gè)矩陣，和它與一個(gè)向量相乘得到的乘積再加上一定的誤差，也就是，如何有效的還原（learn）未知的向量。

“什么？LWE的定義這么草率嗎？”

“是的，有時(shí)候勝利來得就是這么突然。”

“LWE，我們是知道了，可前面為啥提到CVP問題??？”

如果我們細(xì)心的看LWE的問題描述的話，可以發(fā)現(xiàn)，LWE問題與我們之前提到的CVP問題有著驚人的相似。

不能說相似，簡(jiǎn)直一模一樣。都是需要找到一組“系數(shù)”--，使得一組基向量--的線性組合，無限逼近我們想要的目標(biāo)向量--。這里我們使用誤差噪音--的大小來定義到底我們需要距離目標(biāo)向量多近。

所以，如果CVP是一個(gè)NP-hard問題的話，那么LWE問題也是一個(gè)NP-hard問題了。

現(xiàn)在，我么是時(shí)候展示一下LWE問題的數(shù)學(xué)定義了：

是不是猛一看，一堆亂七八糟的數(shù)學(xué)符號(hào)，想直接跳過去？莫慌，其實(shí)很簡(jiǎn)單。此外，這幾個(gè)數(shù)學(xué)符號(hào)會(huì)反復(fù)出現(xiàn)在FHE有關(guān)的論文中，我們是繞不過去的。

從上面的學(xué)習(xí)中，我們知道，一個(gè)LWE問題中，包含以下幾步：

第一，我們需要定義矩陣A的維度--m×n，其中m代表了整個(gè)線性方程組包含幾個(gè)方程，而n代表每個(gè)方程中有幾個(gè)未知數(shù)，也稱為“安全系數(shù)”。n越大，LWE越難，m越大，LWE越簡(jiǎn)單。

第二，我們需要決定有限整數(shù)域中的，一般會(huì)選擇一個(gè)很大的素?cái)?shù)。越大，LWE越難。

第三，我們要決定疊加的噪音的取值上限。越大，越難。

第四，上面三條已經(jīng)足夠，不過，為了簡(jiǎn)單，我們一般只設(shè)置一個(gè)參數(shù)n,然后通過一個(gè)函數(shù)計(jì)算出一組合適的m,q,B，可以保證LWE問題實(shí)例很大概率會(huì)擁有唯一的解，一般m,q都是n的多項(xiàng)式倍數(shù)（m=poly(n)）。

我們定義了這些參數(shù)之后，LWE問題就好理解了：已知和，求未知向量s。其實(shí)，還是我們前面反復(fù)看到的這個(gè)矩陣乘法等式：

此情此景，我就不再吟詩了。。。

到此為止，其實(shí)我們已經(jīng)掌握了FHE的絕大部分內(nèi)容了，萬事俱備，東風(fēng)也不欠了，現(xiàn)在我們正式構(gòu)建一個(gè)我們自己的同態(tài)加密系統(tǒng)。

首先，一個(gè)典型的HE系統(tǒng)包含以下幾步：

第一，密鑰生成（KeyGen）
第二，加密（Enc）
第三，解密（Dec）
第四，同態(tài)運(yùn)算（Eval）

我們下面通過一個(gè)具體的例子來說明如何構(gòu)建一個(gè)HE系統(tǒng)。
首先，KeyGen()，我們先隨機(jī)生成一個(gè)私密向量s，然后在這個(gè)向量的最下面加一個(gè)“-1”，變成,對(duì)，沒錯(cuò)，就是這么草率，就是密鑰。

然后，,其中 m是我們要加密的明文-一個(gè)數(shù)。我們通過以下方式計(jì)算密文:

其中就是我們上面提到的LWE問題，A是隨機(jī)生成的矩陣，s是我們第一步KenGen()生成的，e是一個(gè)隨機(jī)噪音，所以LWE(A,A·s+e)的結(jié)果是一個(gè)看起來亂七八糟的的矩陣。

是一個(gè)單位矩陣。

一個(gè)矩陣C就是我們對(duì)加密之后的密文。
第三步，,在解密時(shí)，對(duì)于一個(gè)密文矩陣，我們只需要計(jì)算，就會(huì)得到我們是我們的密鑰，是已知的，所以，明文m就水落石出了。不知道各位在這時(shí)有沒有想到矩陣的特征值和特征向量這兩個(gè)概念。這里，密鑰是特征向量，明文是特征值，所以不加噪聲的話，明文實(shí)際上是在裸奔，畢竟求一個(gè)已知矩陣的特征值和特征向量還是很容易的！

第四步，，即，密文直接加、乘就可以了。這里需要注意的是，密文下的乘法運(yùn)算可能會(huì)將噪音放大，導(dǎo)致解密失敗，為了提高成功解密的概率，我們可以將和，進(jìn)行二進(jìn)制分解（就是用只包含0、1的二進(jìn)制表示）。

如果你看到了這里，那么恭喜你，已基本掌握了FHE的精髓，最后，我們用下圖來結(jié)束本文：

我定睛觀察上面的圖，持續(xù)十分鐘，然后閉上眼睛，這時(shí)圖中的格子忽然動(dòng)了起來：

Polynomial、Point-Value、Convolution、DFT、FFT、NTT、UnitRoot、PrimitiveRoot、Matrix、Lattice、LWE。。。

這些原來一個(gè)個(gè)相互獨(dú)立的單詞，忽然間變成了一個(gè)個(gè)精靈，他們開心的跳著歡快的舞步，旋轉(zhuǎn)、跳躍、相互握手，點(diǎn)頭致意。。。

。。。

。。。

。。。
最后的最后，送上一幅藏寶圖，祝一路順風(fēng)：

審核編輯：劉清