--基于格密碼全同態(tài)加密的數(shù)學基礎
此情此景,我想先吟詩二首:
從文學的角度看,以上兩首詩比李白寫的稍微遜色一點,不過,從數(shù)學角度來看,簡直可以獲得諾貝爾數(shù)學領域的文學獎(可惜了,目前還沒有這個獎項)。
以上是定場詩,本文旨在盡量少用數(shù)學公式的情況下,解釋清楚FHE(Fully Homomorphic Encryption,全同態(tài)加密)相關的數(shù)學基礎。話不多說,我們繼續(xù)。
一點定乾坤
當時的故事是這樣的:
一個陽光明媚的下午,初三(一)班剛剛上完第二節(jié)數(shù)學課,老師講的是函數(shù)相關的內容。陽光灑在我課桌上,溫暖的光線散射到眼睛里,而我卻盯著老師講的拋物線函數(shù)圖像,一動也不動。
當時我本子上的圖像是下面這樣的:
發(fā)呆的時候,我們班里的泰勒同學去完廁所從教室前門走了進來,我的座位正沖門口,可能是他發(fā)現(xiàn)了我在發(fā)呆,就徑直走了過來,跟我說:
“干嘛呢?大白天的,發(fā)什么呆啊?”
“發(fā)呆跟白天晚上有關系嗎?”我應道,“別打擾我,我在思考一個深奧的問題!”
“什么問題啊?別思考了,我跟你說個事兒,我會魔法你知道嗎?”泰勒不僅沒走開,反而挨著我坐了下來。
“別扯了,我們又不是幼兒園的小朋友,都初三了,誰還相信魔法?!”我有點不耐煩,打算繼續(xù)思考我的深奧的問題。
“你別不信啊,我眼睛有透視的能力”泰勒有點不依不饒,繼續(xù)說道:
“不信的話,你把你的草稿本合起來,別讓我看到,我可以在不看你本子的前提下,知道你畫的是什么函數(shù)”
“滾一邊兒去,我沒那閑工夫跟你玩兒”因為泰勒打斷我的思路,想趕緊轟他走。
“實在不信的話,我們試試不就知道了嗎?!”泰勒不僅沒走,還挪了一下凳子,離我更近了。
“好吧,好吧,如果不靈的話,有多遠滾多遠,行不行?”我說。
“沒問題,這樣,你把你的函數(shù)圖像用兩本書遮起來,兩書之間只留一個點,我可以根據這一個點的信息得到整幅函數(shù)圖像!”泰勒顯得有點興奮。我自已也有點躍躍欲試。
“行啊,沒問題,就給你留一個點,看你怎么猜!”我心想,別說一個點,就是給你十個點,你能猜出來的話,我也算你贏。
我邊說邊把草稿本打開,用語文書和英語書遮住,中間只留了一個小縫兒,我自己剛剛能看到橫軸上‘1’對應的那一點點圖像。
“行了,我準備好了,猜吧!”我說。
“好,現(xiàn)在正式開始,不過我要先問你幾個問題”泰勒說。
“問吧,問吧!”我說。
“請問,在這個點,這個函數(shù)的一階導數(shù)是多少?”泰勒正式開始了他莫名其妙的發(fā)問。
“一階導數(shù)?是2”我略作思考,回答道。
“二階導數(shù)呢?”泰勒繼續(xù)問。
“還是2”我腦筋微轉,答道。
“三階導數(shù)呢?”泰勒繼續(xù)問。
“三階導數(shù)啊?是0”我快速說道。
“四階導數(shù)呢?”泰勒還要問,沒有停下來的意思。
“哎呀,你煩不煩,三階導數(shù)后面所有的導數(shù)都是0”我說。
這時,只見泰勒嘴角上揚,微微一笑,說:“你畫的函數(shù)是,對不對啊?!”
“這怎么可能?!”我很是驚訝,僅僅通過一個點的信息,泰勒怎么會知道整幅函數(shù)圖像的呢?
只見泰勒那時的表情,得意洋洋,心滿意足,開始手舞足蹈。。。
我還是不信,懷疑剛才泰勒偷看到了我的草稿本兒。所以我又緊接著測試了,甚至還測試了,還有很多其它很復雜的函數(shù),令人震驚的是,這些函數(shù),無一例外,泰勒都只通過一個點就猜出來了。
“怎么樣?這回相信我會魔法了吧?!”泰勒見我不解,輕飄飄撂下這句話就走開了,只留下凌亂的我,張著嘴巴,一臉懵。。。
“還真是啊,‘一點定乾坤’,難道說的就是這個?”我不禁自言自語。
讀到這里,聰明的同學可能早就可以拆穿泰勒所謂的魔法了,不過我實在是愚鈍,我們繼續(xù)往下看。。。
一時含永遠
泰勒同學前腳剛走,我的另外一個叫傅里葉的同學就跑了過來,他好像是看到了我和泰勒玩的游戲,跟我說:
“泰勒那哪叫魔法啊,我會的才是真正的魔法,我可以讓時間停止,讓瞬間變永恒”
“你跟泰勒一個德性,凈扯玄乎兒的,把我當幼兒園小朋友耍”我還在琢磨剛剛泰勒是怎么做到的。
“你不相信的話,我們也做個游戲試試”傅里葉不想放棄展示他的魔法。
“沒問題,直接開始吧,你說怎么玩?”我說。
“好,我的第一個問題是,當的時候,函數(shù)的值是多少?”見我同意玩,傅里葉也是開門見山,一下子問出了第一個問題,其實,也是唯一的一個問題。
我奮筆疾書,畢竟x是個e指數(shù),還包含三角函數(shù)的角度,但是,我真正計算才發(fā)現(xiàn),根本用不到筆算,口算就可以。我都一一回答了。當然,在這過程中,我把本子捂得很緊,沒敢讓他偷看一眼。
“我知道了,你的函數(shù)是,對不對啊!”傅里葉得意的問。
“我K,你是怎么知道的?!,難道傳說中的‘一時含永遠’,說的就是你?!”我被徹底震驚了。
。。。
。。。
。。。
好吧,我承認,泰勒和傅里葉不是我的同學,上面的故事都是編的。我也是實在編不下去了,很多聰明的同學也早就發(fā)現(xiàn)了泰勒和傅里葉的秘密。
泰勒的秘密就是:
對于任何一個光滑函數(shù),都可以表示為多項式的形式,而多項式的系數(shù)可以通過某一點的導數(shù)獲得。
是的,你沒看錯,一個點竟然蘊含了一個函數(shù)的所有信息。
傅里葉的秘密是:
對于任何一個光滑函數(shù),都可以表示為三角函數(shù)累加(積分)的形式,而每一項的系數(shù)可以通過多個點的自變量和因變量對兒(x, f(x))獲得。
是的,你沒看錯,我們手機里的歌曲,不管你播不播放,他總是呆在那里,不曾改變。一個隨時間變化的信號,經過傅里葉變換之后,時間將消失,音樂會上一段美妙的音樂,不過是樂譜的再一次重復,而無論重復多少次,樂譜從未發(fā)生絲毫改變。
以上被稱為“感覺第一定理”。
對于喜歡看公式的同學(對于不喜歡看數(shù)學公式的同學,直接跳過公式部分,絲毫不用擔心會影響你對本文的理解),就是:
泰勒公式一句話描述:就是用多項式函數(shù)去逼近光滑函數(shù)。
傅里葉變換一句話描述:將用一般多項式表示的時域的信號,變成頻域的信號(這句不懂沒關系,看完后面就懂了)。
你在其它地方看到的傅里葉變換可能是下面的樣子:
那是因為歐拉這位同學的存在,可以把e指數(shù)變成三角函數(shù)的形式。
歐拉公式:
所以,我總結下來,就是,對于任何一個函數(shù),都可以用一些簡單的東西的線性組合得到。這里面提到的簡單的東西,就可以認為是搭積木的一個個小積木塊,用數(shù)學的語言,小積木塊就是函數(shù)的基。用線性代數(shù)的語言,小積木塊就是單位向量。而具體的函數(shù),就是用小積木塊搭出來的各種形狀的積木,以及用單位向量組成的一般向量。
以上被稱為“感覺定理-2”
彎路走的快
稍作休息,我又可以繼續(xù)編故事了,還是續(xù)集。
傅里葉同學說完答案,同樣留下一頭霧水的我,瀟灑的走開了。當時,我腦袋里真是一團漿糊,泰勒同學的秘密還沒搞懂,又來一個傅里葉的秘密。秘密加秘密,我就更摸不著頭腦了。
正當我一籌莫展之際,我的第三位同學-凱萊出現(xiàn)在了我的面前。還沒等我張口請教,凱萊就發(fā)話了:
“泰勒和傅里葉的三腳貓功夫,有啥了不起的,在我看來,不就是多項式的兩種表示形式而已。”
“多項式,我知道,不過,我只知道一種形式,另外一種是啥?”我問。
凱萊,不像泰勒和傅里葉,他舉止優(yōu)雅,陣腳不亂,簡稱“矩陣”(sorry,這是個諧音梗)。
“不用著急,聽我給你慢慢說”凱萊搬了自己的凳子來,輕坐在我旁邊。
你看啊,我們一般見到的多項式是下面這樣的,叫多項式的系數(shù)表示法。
這其中的就是多項式的系數(shù),所以叫“系數(shù)(coefficient)表示法”,沒錯,數(shù)學就是這么直白。
除了系數(shù)表示法之外,還有一種,叫“點值表示法(point-value representation)”,顧名思義,就是用這個多項式上的點,以及這點對應的值來表示。
比如,上面的多項式,用點值表示法,就是:
看到這里,我就有點不太理解了,為啥點值表示法也能代表這個多項式呢?凱萊,不緊不慢,耐心解釋道:
你看啊,點值表示法里面的每一對點值,是不是表示下面一個等式,比如,第一對兒點值,表示的就是下面的一個等式。
第二對兒點值對應的是下面的等式:
從點值表示法來看,本來在一個平面上有無數(shù)條曲線,每次確定一個點,就要求我們想要的曲線必須經過這個點,當我們確定的點的數(shù)量和這條曲線的次數(shù)(就是上面式子中的n)相同時,我們就找到了經過我們指定所有點的唯一一條曲線。這是“感覺定理-3”
這時,凱萊好像看出了我的心思,說:
“瞎想什么啊,太難理解了,我們初中生,剛學過矩陣,用矩陣表示比你那個‘真感情’容易多了!”
“什么意思啊?”我還是不太理解。
“你看啊。。。”凱萊又開始娓娓道來:
上面用點值表示法表示的多項式,每個點值對兒都對應一個方程,如果我們把他們組合到一起,寫成矩陣的形式,不就是下面這個樣子嗎:
點值表示法,就是上面三個矩陣,第1個和第3個,分別表示“點”和“值”,第2個矩陣是多項式的系數(shù)。當其中第1個和第3個矩陣都確定的情況下,第2個系數(shù)矩陣其實也就確定了。所以,從這個角度看,點值表示法和系數(shù)表示法,只是同一個函數(shù)的兩種表示方式,就好像同一個函數(shù)既可以按泰勒同學的方式展開,也可以按傅里葉同學的方式展開,兩種方式描述的其實是一個東西。
就好像光的波粒二象性似的,泰勒同學強調的是粒子性,而傅里葉同學強調的是波動性。或者說,系數(shù)表示法強調的是函數(shù)的波動性,點值表示法更多體現(xiàn)函數(shù)的粒子性。此為“感覺定理-4”.
凱萊同學啰啰嗦嗦的說了半天,我也不知道說了些什么東西,就問:
“凱萊,你說的點值法,我是聽懂了,可我沒看出點值法有啥用處啊”
“這個用處可就太大了,可以加速多項式乘法!”凱萊說。
你看啊,比如,我們有兩個用系數(shù)表示法表示的多項式:
那么這兩個多項式的乘法結果的計算過程如下所示:
這個多項式乘法的復雜度是,另外還要注意的是,“多項式乘法”中的“乘法”兩個字非常容易產生誤導作用,給人一種真的是普通乘法的錯覺,其實,多項式的乘法操作,實際上就是卷積運算,這一點一定要謹記。
“卷積?有什么特殊的呢?這和點值表示法有啥關系啊?”我還是似懂非懂的問。
“別著急啊,還記得剛剛走的傅里葉同學嗎?他剛剛使用的秘密武器就是傅里葉變換,還記得嗎?”凱萊問我。
“當然記得,傅里葉變換可以讓時間消失的,太厲害了,可以將時域的信號,變成頻域的信號!”我說。
“完全正確!”凱萊對我的回答非常滿意,他接著說:
“多項式的乘法(也就是卷積運算),可以先將兩個多項式分別做傅里葉變換,變完之后的兩個式子,直接對應項相乘,對應項相乘完之后的結果再做傅里葉逆變換,得到的結果就是兩個原始多項式的乘法結果!!!”凱萊興奮的嚷道。
“這個我知道,這不就是卷積定理嘛!卷積定理說的是,在一個域的相乘等于另一個域的卷積,用式子表示,就是下面這樣子的”我補充道。
“可是,這個和你前面提到的矩陣有什么關系啊?!又和多項式的點值表示法有什么關系啊?!”我還是沒完全理解凱萊的意思。
“不用著急,這兩個問題很快你就明白了,只需最后一步!”凱萊還是慢條斯理的樣子。
“最后一步?什么最后一步啊?”我問。
你看啊,其實啊,點值表示法有個非常大的好處,我之前沒提到,就是:
對于用點值表示法表示的兩個多項式的乘法(實際是卷積),可以直接對應項相乘即可,即,
“我知道了,凱萊,原來復雜度為的多項式乘法運算,復雜度降低成了”我好像發(fā)現(xiàn)了什么新大陸,也吼了起來。
“不對啊,好像哪里不對啊,這個復雜度的降低要想實現(xiàn),需要先把系數(shù)表示法變成點值表示法才行啊!,這個從系數(shù)轉點值的復雜度也是啊,你這搞半天不是瞎搞了嗎!本來可以有直行的路可以到達,你這越走越遠啊!”我剛剛發(fā)現(xiàn)的新大陸瞬間又不香了,滿臉狐疑的看著凱萊。
“不對啊,好像哪里不對啊,這個復雜度的降低要想實現(xiàn),需要先把系數(shù)表示法變成點值表示法才行啊!,這個從系數(shù)轉點值的復雜度也是啊,你這搞半天不是瞎搞了嗎!本來可以有直行的路可以到達,你這越走越遠啊!”我剛剛發(fā)現(xiàn)的新大陸瞬間又不香了,滿臉狐疑的看著凱萊。
“你別著急啊,你再仔細看看,你說的沒錯,如果是一般的系數(shù)變點值,復雜度確實降不下來,可是,如果我取得點是一些特殊的點的話,情況就完全不一樣啦”凱萊繼續(xù)給我解釋,不緊不慢。
“取什么樣的點,才能降低復雜度呢?哦!我知道了,復數(shù)域的單位根,復數(shù)域的單位根,復數(shù)域的單位根!”我連續(xù)說了三遍,生怕凱萊聽不清楚。
在復數(shù)域內,方程有個根,就叫單位根,這些根分別是:
就是前面傅里葉同學表演“一時含永遠”魔法的時候用的那幾個點!!這幾個點太好了,口算就能知道對應的函數(shù)值,這樣的話,系數(shù)到點值的轉換就簡單多了。
“是的,你終于發(fā)現(xiàn)了傅里葉變換的另外一個秘密,就是傅里葉變換,其實就是多項式的系數(shù)轉點值,當然,我們考慮的是離散的傅里葉變換(DFT)”凱萊繼續(xù)說道。
“嗯,后面我就知道了,DFT有個快速算法,叫FFT,F(xiàn)FT的計算復雜度是看到了希望,我又開心了起來。
為了防止忘記,我在心里又重新梳理了一下多項式乘法的過程:
多項式乘法本質是卷積運算
卷積運算可以分三步:
a. 先把兩個多項式從系數(shù)表示變成點值表示,這一步就是DFT,可以用FFT加速,F(xiàn)FT采用分治法,可以將一根很長的木棍兒每次都折半,這樣遞歸下去,就可以降低計算復雜度。FFT選用的是單位根,NTT選用的是原根,目的一樣,為了加速DFT, 相比于FFT,NTT還便于取模運算。
b. 然后,將用點值形式的兩個多項式,對應項相乘,就得到了最終結果的點值表示形式。
c. 最后,還需要把最終結果的點值表示變回系數(shù)表示
“前幾步上面都提到了,我也理解了,可這最后一步是怎么做到了?”雖然大部分的內容我理解了,可再三回憶,最后一步確實沒聽凱萊說過。
“哎呀,這還不簡單嗎?提示你一下,看看多項式的矩陣表示形式,對了,不用往上翻了,我們再寫一遍,就是下面的樣子”凱萊嘿嘿一笑:
還是原來的配方,還是熟悉的味道。點值表示變回系數(shù)表示的過程,不就是已知上面的第1個矩陣和第3個矩陣,求中間的系數(shù)矩陣嘛?!
“原理我貌似有點懂了,可是,具體怎么求啊,我線性代數(shù)也學的不好”我繼續(xù)追問凱萊,凱萊畢竟是矩陣理論的大師級人物,這點小問題應該難不倒他。果然,還不到1秒鐘的時間,凱萊就發(fā)話了:
“這個問題嘛,等式兩邊都乘上第1個矩陣的逆矩陣就可以了,注意啊,是“矩陣的逆:”,不是”矩陣的轉置:”,這個千萬別混淆了”凱萊細心的提醒我。
“知道啦,不過,矩陣的逆,復雜度可很大啊,是,你這又是南轅北轍啊?!”我又有被凱萊耍了的感覺。
“你說的沒錯,上面的第一個矩陣,是一個特殊的矩陣,叫范德蒙矩陣,一般的范德蒙矩陣的逆,運算復雜度也是,不過,但是,如果我們按照傅里葉同學的思路,搞出來的這個范德蒙矩陣是特殊中的特殊,它的逆矩陣,就是矩陣中的每個元素的共軛,再除以n,就是這么簡單,哎喲,就是這么巧合,你說神奇不神奇”凱萊難得的大笑起來。用式子表示,就是下面這個樣子的:
這個矩陣的逆,就是:
“原來如此,原來如此啊,如果我記得沒錯的話,點值到系數(shù)的變換過程就是傳說中的傅里葉逆變換,也叫IDFT,這個也有加速版本的IFFT。”我終于恍然大悟,“彎路走的快”,誠不欺我,有圖為證。
故事講到這里,我不禁又想起了最開始的兩首詩,史上最富含數(shù)學知識的文學作品,名副其實。不過,看標題,內容是同態(tài)加密啊,故事都講到這兒了,嘚啵嘚啵嘮半天嗑,咋同態(tài)加密的影兒都沒看著啊?!
別著急,這是同態(tài)加密的上篇,我們稍作休息,請等待后面的精彩故事。
此情此景,我想再吟詩二首:
話說上篇我們了解到了很多非常重要的內容:
多項式從系數(shù)表示變成點值表示的過程,就是離散傅里葉變換(DFT/FFT)。
多項式從點值表示變成系數(shù)表示的過程,就是離散傅里葉逆變換(IDFT/IFFT)。
多項式的乘法,本質是卷積運算,一次卷積運算可以分為三步:Convolution=FFT->multiply->IFFT,即卷積定理表達的內容。
以上三種場景,都有相應的矩陣操作與之對應。原因是:一個多項式的點值表示和一個線性方程組對應,線性方程組又和一個矩陣乘法運算對應,這樣多項式的乘法就可以轉換成FFT相關的計算。這一點非常重要,是理解FHE的關鍵所在。
仔細思考上篇中討論的內容,加上上面幾點提示,這樣我們就把FHE相關的幾個非常重要的概念,以及這些概念之間的關系就搞清楚了,此時,我們的腦海里應該出現(xiàn)以下幾個概念,并且這些概念不再是獨立的孤島,而是腦海里一片廣闊的大陸:泰勒公式,多項式,系數(shù)表示法,點值表示法,DFT,F(xiàn)FT,卷積,卷積定理,線性方程組,矩陣,矩陣的逆。
好,收拾行囊,我們繼續(xù)趕路,在正式向FHE山頂發(fā)起沖鋒前,我們有必要加深一下對傅里葉變換的理解,如下圖所示:
仔細查看上圖。。。在觀察這段時間里的某個時刻,一道金光從腦海劃過:為什么時間消失了?!我們感知到的隨著時間流淌的宇宙,進行傅里葉變換后會怎樣?我們又該怎么選擇傅里葉變換的旋轉因子(twiddle factor)?如果你的腦海沒有金光劃過,可以先閱讀一下。
如果腦海里實在是沒有金光劃過,也沒關系,不會影響我們最終站上FHE的山頂。我們繼續(xù)。。。
在FHE領域,我們可能會反復看到一句話:“FHE是基于格密碼學的”。這句話很簡短,既然反復看到,說明應該很重要,可是,我從這句話里面又看不出什么東西,每個字我都認識,但就是不知道整句話什么意思。什么道理都懂,仍然過不好一生。不用著急,我們慢慢拆解:
首先,這里面最難懂的可能是“格”這個字,于是,我們就百度里一下,“格”是這么定義的:
“ “格”是一種特殊的偏序集。”
也很簡短,不過不出意外,還是每個字都認識,但仍然不明白整句話說的是啥意思。按道理,既然名字叫“格”,應該跟“格子”有關系啊?!
于是,我們繼續(xù)查找FHE相關的資料,除了“格”這個東西,經常出現(xiàn)的還有“環(huán)”這個概念,于是百度之,“環(huán)”定義的第一個條件是:
“ 集合R在+運算下構成阿貝爾群” 此外還有“理想(Ideal)”兩個字也出現(xiàn)在了附近。
也很簡短,不過不出意外,還是每個字都認識,但仍然不明白整句話說的是啥意思。按道理,既然名字叫“環(huán)”,應該跟“鐵環(huán)、手環(huán)”之類的東西有關啊?!
按圖索驥,從“環(huán)”的定義里,我們發(fā)現(xiàn)了“阿貝爾群”這幾個字,“阿貝爾”應該是個人名,那“群”又是啥意思?!,于是,繼續(xù)百度之,
“在數(shù)學中,群表示一個擁有滿足封閉性、滿足結合律、有單位元、有逆元的二元運算的代數(shù)結構,包括阿貝爾群、同態(tài)和共軛類。”
這句話相比之前“格”“環(huán)”的定義稍稍多了幾個字。欣喜的是,這句話中提到的幾個概念好像都知道什么意思,比如“結合律”,“單位元”,“共軛”等,此外,還見到了我們苦苦追尋的“同態(tài)”兩個字,相比最開始的漆黑一片,終于見到了幾個火星兒,希望有了,勝利可能就在眼前。。。
于是,我們沖向FHE這個山頂?shù)牡谝粭l路徑就出現(xiàn)在了我們眼前,那便是:群->環(huán)->域->格。雖然只有四個字,可每個字看起來都不是那么好搞定的,畢竟,我們好像依稀聽說過,“群論”,“環(huán)論”,“抽象代數(shù)”這幾個可怕的怪物,這么陡峭的山體,一不小心就可能摔得粉身碎骨,永遠達不到矗立在山頂?shù)腇HE。
我駐足沉思,難道到山頂只有一條路可走?難道必須從山腳下的“群”開始?現(xiàn)在都是新時代,出門爬個山,累了都有纜車啊, FHE這座山真有沒有纜車可坐?如果FHE這座山沒有纜車,那么FHE這座山附近有沒有其它的山,如果有其它的山的話,有沒有可能在兩山的山頂建有“山頂纜車”?
一堆問題在我附近的空間里縈繞盤旋,我得不到回答,于是,在沒看到“山頂纜車”之前,我開始從山腳下的“群”開始一步一步地爬。。。群是有點抽象,剛開始確實不太容易理解,不過我走得很快,不一會就建立了“群,環(huán),域”的簡單概念。
繼續(xù)爬。。。
爬呀爬。。。
。。。
。。。
。。。
幾天以后。。。
又有一道金光劃過我腦海的上空,原本漆黑的海面上變得亮了起來。這道金光就是:
“很多格子擺在一起,看起來很像矩陣啊!”
是的啊,確實很多格子排列在一起,從遠處看,就是一個矩陣啊,所以,“格”和“矩陣”之間一定存在某種關系!這個關系,不就是兩座山頂之間的“山頂纜車”嗎?!
“矩陣”,我們是比較了解的,如果矩陣和格之間建有山頂纜車的話,豈不美哉。
稍作驗證,果不其然,我的想法是對的,“山頂纜車”早已建成,因為我看到了“整數(shù)格”的定義:
“離散的基向量生成空間集合,稱之為整數(shù)格(Integer Lattice)”
這里面可能稍有難度的是“生成空間”,我們先來搞定它。
在線性代數(shù)中,如果我們要描述一個線性空間的話,我們需要先找到這個空間的一組基(Basis)。(PS:看到“基”這個字,你是不是又想起了傅里葉,想起了泰勒,想起了點值法,想起了消失的時間。。。)
比如常見的二維平面空間(笛卡爾坐標系),我們可以選用x軸和y軸的單位向量,作為我們的基向量(或者叫單位向量),分別是:
這樣的話,任何XY坐標系的向量都可以用上面的一組基來表示。即,
其中c_0和c_1可以是任意實數(shù),如果是任意實數(shù),那么v的所有可能的組合,就可以鋪滿整個二維平面空間,我們管所有的v組成的這個線性空間,就叫做,b_1兩個基向量的線性生成空間(Span)。
我們不難想象,如果c_0和c_1是實數(shù),那么b_0,b_1的生成空間是“連成一片”的,可以叫“片”,但是,如果c_0和c_1是只能是整數(shù)的話,那么b_0,b_1的生成空間就由“片”變成了無數(shù)個離散的“點”,這些點整齊的排列在一起,非常像無數(shù)個小格子,我們把這樣的一個離散的生成空間,叫做“整數(shù)格(Integer Lattice)”。
果不其然,從“矩陣”到“格”,只有簡單的一步,這個“山頂纜車”建得實在是太好了。
乘坐這條意外發(fā)現(xiàn)的纜車,我們快速抵達了“格”,這時,我們離FHE的核心腹地--LWE只有一步之遙了,加油,勝利就在眼前。
稍微瞄一眼上圖,我們就會發(fā)現(xiàn),這確實是很多格子啊,“格”這個字用的還是挺好的。
有了Lattice(格),就有很多跟Lattice 有關的有意思的問題就出現(xiàn)了。比如,想要表達一個向量v:
我們會發(fā)現(xiàn),這個向量沒辦法在整數(shù)格中表達它,因為整數(shù)格中的系數(shù)必須是整數(shù)才行啊。
好了,問題來了,既然不能用整數(shù)格完美表達v,那么,是否可以找到一個最接近v的v_0,而v_0可以用整數(shù)格完美表達。對于上面的例子:
這個就是著名的CVP(Closest Vector Problem)難題!!
你可能會說,這算哪門子難題啊?我一秒鐘就破解了。
沒錯,如果只是二維正交基向量的格,那么CVP問題不是特別難,但是,如果基向量不正交呢?如果v的維度變大到, 的成員的值變大到需要1000bit呢?
這個難度是被嚴格證明的,CVP問題是非常難解決的(Nondeterministic Polynomial hard, NP-hard)。
是的,這個乍看起來很簡單,實際上很難的問題,就是格密碼學的開端。
“什么?!搞了這么久,我以為已經達到了頂峰,竟然被你說成是‘開端‘?!!”
“是的,的確是格密碼學的開端,現(xiàn)實就是這么的殘酷,你以為的天花板,很可能只是別人的起點。比如,你家的天花板,可能只是樓上的地板,…^_^”
不過不要氣餒,前面就是我們要找的LWE了。
在正式引入LWE之前,我們先回顧一下,送我們快速到達“格”的山頂纜車—矩陣。
是的,通過上篇的學習,我們早就知道了,一個矩陣乘的式子,對應一個線性方程組:
其中A是一個矩陣,x是一個向量,b也是一個向量。
已知A和b,求x的過程,就是求解線性方程組的過程。具體就是在上篇提到的方法:等式兩邊都乘以的逆矩陣,乘完之后,等式左邊就只剩下我們要求出的未知向量了。
現(xiàn)在稍稍把上面的矩陣乘法等式變化一下:
其中e是一個在固定數(shù)值范圍內隨機采集的一個隨機噪音向量。這時,之前“等式兩邊都乘以A的逆矩陣”的方法就不行了,那我們怎么求呢?答案很簡單:
“只能暴力破解”
也就是一個一個的猜x這個向量里的值,然后逐漸逼近。
這就是我們苦苦尋找的LWE(Learning With Error)問題!即:
已知一個矩陣,和它與一個向量相乘得到的乘積再加上一定的誤差,也就是,如何有效的還原(learn)未知的向量。
“什么?LWE的定義這么草率嗎?”
“是的,有時候勝利來得就是這么突然。”
“LWE,我們是知道了,可前面為啥提到CVP問題啊?”
如果我們細心的看LWE的問題描述的話,可以發(fā)現(xiàn),LWE問題與我們之前提到的CVP問題有著驚人的相似。
不能說相似,簡直一模一樣。都是需要找到一組“系數(shù)”--,使得一組基向量--的線性組合,無限逼近我們想要的目標向量--。這里我們使用誤差噪音--的大小來定義到底我們需要距離目標向量多近。
所以,如果CVP是一個NP-hard問題的話,那么LWE問題也是一個NP-hard問題了。
現(xiàn)在,我么是時候展示一下LWE問題的數(shù)學定義了:
是不是猛一看,一堆亂七八糟的數(shù)學符號,想直接跳過去?莫慌,其實很簡單。此外,這幾個數(shù)學符號會反復出現(xiàn)在FHE有關的論文中,我們是繞不過去的。
從上面的學習中,我們知道,一個LWE問題中,包含以下幾步:
第一,我們需要定義矩陣A的維度--m×n,其中m代表了整個線性方程組包含幾個方程,而n代表每個方程中有幾個未知數(shù),也稱為“安全系數(shù)”。n越大,LWE越難,m越大,LWE越簡單。
第二,我們需要決定有限整數(shù)域中的,一般會選擇一個很大的素數(shù)。越大,LWE越難。
第三,我們要決定疊加的噪音的取值上限。越大,越難。
第四,上面三條已經足夠,不過,為了簡單,我們一般只設置一個參數(shù)n,然后通過一個函數(shù)計算出一組合適的m,q,B,可以保證LWE問題實例很大概率會擁有唯一的解,一般m,q都是n的多項式倍數(shù)(m=poly(n))。
我們定義了這些參數(shù)之后,LWE問題就好理解了:已知和,求未知向量s。其實,還是我們前面反復看到的這個矩陣乘法等式:
此情此景,我就不再吟詩了。。。
到此為止,其實我們已經掌握了FHE的絕大部分內容了,萬事俱備,東風也不欠了,現(xiàn)在我們正式構建一個我們自己的同態(tài)加密系統(tǒng)。
首先,一個典型的HE系統(tǒng)包含以下幾步:
第一,密鑰生成(KeyGen)
第二,加密(Enc)
第三,解密(Dec)
第四,同態(tài)運算(Eval)
我們下面通過一個具體的例子來說明如何構建一個HE系統(tǒng)。
首先,KeyGen(),我們先隨機生成一個私密向量s,然后在這個向量的最下面加一個“-1”,變成,對,沒錯,就是這么草率,就是密鑰。
然后,,其中 m是我們要加密的明文-一個數(shù)。我們通過以下方式計算密文:
其中就是我們上面提到的LWE問題,A是隨機生成的矩陣,s是我們第一步KenGen()生成的,e是一個隨機噪音,所以LWE(A,A·s+e)的結果是一個看起來亂七八糟的的矩陣。
是一個單位矩陣。
一個矩陣C就是我們對加密之后的密文。
第三步,,在解密時,對于一個密文矩陣,我們只需要計算,就會得到我們是我們的密鑰,是已知的,所以,明文m就水落石出了。不知道各位在這時有沒有想到矩陣的特征值和特征向量這兩個概念。這里,密鑰是特征向量,明文是特征值,所以不加噪聲的話,明文實際上是在裸奔,畢竟求一個已知矩陣的特征值和特征向量還是很容易的!
第四步,,即,密文直接加、乘就可以了。這里需要注意的是,密文下的乘法運算可能會將噪音放大,導致解密失敗,為了提高成功解密的概率,我們可以將和,進行二進制分解(就是用只包含0、1的二進制表示)。
如果你看到了這里,那么恭喜你,已基本掌握了FHE的精髓,最后,我們用下圖來結束本文:
我定睛觀察上面的圖,持續(xù)十分鐘,然后閉上眼睛,這時圖中的格子忽然動了起來:
Polynomial、Point-Value、Convolution、DFT、FFT、NTT、UnitRoot、PrimitiveRoot、Matrix、Lattice、LWE。。。
這些原來一個個相互獨立的單詞,忽然間變成了一個個精靈,他們開心的跳著歡快的舞步,旋轉、跳躍、相互握手,點頭致意。。。
。。。
。。。
。。。
最后的最后,送上一幅藏寶圖,祝一路順風:
審核編輯:劉清
-
傅里葉變換
+關注
關注
6文章
441瀏覽量
42592 -
三角函數(shù)
+關注
關注
0文章
13瀏覽量
6725 -
同態(tài)加密
+關注
關注
1文章
5瀏覽量
1914
原文標題:看完這篇文章,還搞不懂全同態(tài)加密,你過來打我--基于格密碼全同態(tài)加密的數(shù)學基礎
文章出處:【微信號:LinuxDev,微信公眾號:Linux閱碼場】歡迎添加關注!文章轉載請注明出處。
發(fā)布評論請先 登錄
相關推薦
評論