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

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

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

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

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

一點(diǎn)定乾坤

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

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

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

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

“干嘛呢？大白天的，發(fā)什么呆??？”

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

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

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

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

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

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

“實(shí)在不信的話，我們試試不就知道了嗎？！”泰勒不僅沒走，還挪了一下凳子，離我更近了。

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

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

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

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

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

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

“問吧，問吧！”我說。

“請問，在這個點(diǎn)，這個函數(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”我說。

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

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

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

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

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

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

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

一時含永遠(yuǎn)

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

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

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

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

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

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

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

“我知道了，你的函數(shù)是，對不對?。　备道锶~得意的問。

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

。。。

。。。

。。。

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

泰勒的秘密就是：

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

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

傅里葉的秘密是：

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

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

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

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

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

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

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

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

歐拉公式：

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

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

彎路走的快

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

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

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

“泰勒和傅里葉的三腳貓功夫，有啥了不起的，在我看來，不就是多項式的兩種表示形式而已?！?/p>

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

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

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

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

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

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

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

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

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

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

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

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

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

“什么意思??？”我還是不太理解。

“你看啊。。?！眲P萊又開始娓娓道來：

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

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

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

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

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

“這個用處可就太大了，可以加速多項式乘法！”凱萊說。

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

那么這兩個多項式的乘法結(jié)果的計算過程如下所示：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

“哎呀，這還不簡單嗎？提示你一下，看看多項式的矩陣表示形式，對了，不用往上翻了，我們再寫一遍，就是下面的樣子”凱萊嘿嘿一笑：

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

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

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

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

這個矩陣的逆，就是：

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

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

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

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

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

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

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

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

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

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

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

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

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

“ “格”是一種特殊的偏序集?！?br />
也很簡短，不過不出意外，還是每個字都認(rèn)識，但仍然不明白整句話說的是啥意思。按道理，既然名字叫“格”，應(yīng)該跟“格子”有關(guān)系?。?！

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

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

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

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

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

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

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

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

繼續(xù)爬。。。

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

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

“很多格子擺在一起，看起來很像矩陣啊！”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這個就是著名的CVP（Closest Vector Problem）難題??！

你可能會說，這算哪門子難題啊？我一秒鐘就破解了。

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

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

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

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

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

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

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

是的，通過上篇的學(xué)習(xí)，我們早就知道了，一個矩陣乘的式子，對應(yīng)一個線性方程組：

其中A是一個矩陣，x是一個向量，b也是一個向量。

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

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

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

“只能暴力破解”

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

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

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

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

“是的，有時候勝利來得就是這么突然?！?br />
“LWE，我們是知道了，可前面為啥提到CVP問題??？”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

是一個單位矩陣。

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

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

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

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

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

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

。。。

。。。

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

審核編輯：劉清