格密碼與同態(tài)加密學習總結(jié)

一、格密碼學

1.與傳統(tǒng)密碼學相比的優(yōu)點

安全性：基于最糟糕情況困難安全性(Worst-case security)的可證明安全。

傳統(tǒng)密碼算法：基于平均情況困難安全性（Average-case security)的可證明安全。
- 例如蝴光，如果通過某整數(shù)的分解破解了某RSA實例叛氨，不意味著可以破解所有整數(shù)的分解問題，只意味著可以分解該RSA實例涉及的那些整數(shù)擂橘。換言之晌区，并非任何基于整數(shù)分解的密碼學實例都是安全的，因為只是在平均情況（Average-case)下整數(shù)分解是困難的通贞，而非所有整數(shù)的分解都是困難的朗若。
- 基于最糟糕困難安全性(Worst-case security)的可證明安全確保了：如果可以破解基于某個格上的困難問題所構(gòu)建的密碼學實例，就可以解決最糟糕情況下的該困難問題昌罩，換言之哭懈，如果在最糟糕情況下即使以小概率破解了該問題的一個實例，就能破解基于該問題的所有實例茎用。
困難問題：基于格的困難問題遣总。格的困難問題是一個新提出的困難問題，在計算機領(lǐng)域绘搞，它只有三四十年的歷史彤避，且目前尚不能被量子算法破解，格密碼算法是目前后量子領(lǐng)域最受矚目的算法夯辖。
計算：簡單計算琉预，效率高。計算開銷很小蒿褂，只需要加法就能實現(xiàn)密碼學方案（乘法可以看作加法的累積）圆米。
應用：可以構(gòu)造傳統(tǒng)密碼學無法實現(xiàn)的復雜而強力的密碼學應用卒暂，最具代表性的是全同態(tài)加密(fully homomorphic encryption, FHE)，傳統(tǒng)密碼學無法實現(xiàn)娄帖。

2.近年來格密碼學的研究主線

SIS（小整數(shù)解問題）與LWE（容錯學習問題）是近年來格密碼學的兩個核心問題也祠，利用這兩個問題可以構(gòu)造高效的密碼學方案。它們將格的內(nèi)容抽象化近速，使得研究者不需要去考慮最糟糕情況困難性的安全性證明诈嘿，只需要基于SIS與LWE這兩個中間問題即可構(gòu)造出安全的密碼學方案。
另一主線是基于特定格代數(shù)結(jié)構(gòu)（理想格削葱，ideal lattices）構(gòu)造高效的密碼學方案奖亚，產(chǎn)生了Ring-LWE與Ring-SIS問題∥鲈遥基于這種滿足特定性質(zhì)的格代數(shù)結(jié)構(gòu)可以在滿足安全性的同時昔字，大幅提升所構(gòu)造方案的效率（密鑰長度縮小到KB極，計算效率甚至可以接近哈希函數(shù)）首繁。

3.格中困難問題

各問題歸約關(guān)系如下：（圖來自Daniele Micciancio教授）

各困難問題問題概述：

符號說明：

格基底為B作郭，由此生成的格為 $\cal{L}$ 。
n維格 $\cal{L}$ 弦疮，定義 $\lambda_i(L),\, 1 \le i \le n$ 是第i最短向量的長度夹攒。 $\gamma$ 為長度前的近似因子。
給定格 $\cal{L}$ 挂捅，定義任一點t 到最近格點的距離函數(shù)為： $\mu(t,L)=\min\limits_{x \in L}\Vert t-x \Vert$ 芹助，格的覆蓋半徑： $\mu(L) = \max\limits_{t \in span(L)} \mu(t,L)$

各困難問題內(nèi)容如下：

$SVP$ 問題（Shortest Vector Problem）

搜索問題

給定一組基B，找到非零向量 $\boldsymbol{v}\in\cal{L}$ 闲先，使得 $||\boldsymbol{v}||=\lambda_1(\cal{L})$ 状土。
判定問題

給定一組基B， $d>0$ 伺糠，區(qū)分出 $\lambda_1(\cal{L})\leq d$ 蒙谓，還是 $\lambda_1(\cal{L}) > d$ 。
計算問題

給定一組基B训桶，計算出 $\lambda_1(\cal{L})$ 累驮。

${SVP}_{\gamma}$ 問題

搜索問題，即 ${SVP}_{\gamma}$

給定一組基B舵揭，找到非零向量 $\boldsymbol{v}\in\cal{L}$ 谤专，使得 $||\boldsymbol{v}||\leq\gamma\cdot\lambda_1(\cal{L})$ 。
判定問題午绳，即 $GapSVP_{\gamma}$

給定一組基B置侍，和 $d>0$ ，區(qū)分出 $\lambda_1(\cal{L})\leq d$ ，還是 $\lambda_1(\cal{L}) >\gamma\cdot d$ 蜡坊。
估算問題杠输，即 ${EstSVP}_{\gamma}$

給定一組基B ，輸出在 $[{\lambda}_1(\cal{L}),\gamma \cdot \lambda_1(\cal{L})]$ 中的 $d$ 秕衙。

解決 $SVPγ$ 問題蠢甲，其中 $\gamma=2^{(n-1)/2}$ ，可以使用LLL算法（一般在低維應用）据忘。

${SIVP}_{\gamma}$ 問題（Shortest Independent Vectors Problem）

給定一組基B, 找到一組線性獨立的向量 $\boldsymbol{v_{1},...,v_{n}}\in\cal{L}$ 鹦牛，使得 $||\boldsymbol{v_{i}}||\leq\gamma\cdot{\lambda}_{i}(\cal{L})。$
困難性： $GapSVP_{\gamma}\leq {SIVP}_{\gamma}$ 若河。

$CVP$ 問題（Closest Vector Problem）

給定一組基B能岩，點 $t$ 寞宫，找到一些格點 $\boldsymbol{v}\in\cal{L}$ 萧福，使得 $||t-\boldsymbol{v}||=\mu(t,\cal{L})$ 。

${CVP}_{\gamma}$ 問題

給定一組基B辈赋，點 $t$ 鲫忍，找到一些格點 $\boldsymbol{v}\in\cal{L}$ ，使得 $||t-\boldsymbol{v}||\leq\gamma\cdot \mu(t,\cal{L})$ 钥屈。

$BDD$ 問題（Bounded Distance Decoding）

搜索問題

給定一組基B悟民，點 $t$ ， $d<{\lambda}_{1}/2$ 篷就，使得 $\mu(t,\cal{L})\leq d$ 射亏，找到唯一接近t的 $\boldsymbol{v}\in\cal{L}$ 。換句話來說竭业，給定陪集 $t+\cal{L}\ni e$ 智润，使得 $||e||\leq d$ ，找到這個 $e$ 未辆。

一種理解方式是對 $\cal{L}$ 中的每個格點窟绷，以 $d$ 為半徑作球體，使得點 $t$ 和某一格點在一個球體內(nèi)的格點即要找的 $\boldsymbol{v}\in\cal{L}$ 咐柜〖骝冢或者理解為對 $t+\cal{L}$ 中的每個點，以原點 0 為球心拙友， $d$ 為半徑作球體为狸，球體內(nèi)包含的點即要找的 $e \in t+\cal{L}$ 。
判定問題：

給定一組基B遗契，陪集 $t+\cal{L}$ 辐棒，和d，區(qū)分出 $\mu(0,t+\cal{L})\leq d$ ，還是 $\mu(0,t+\cal{L}) >\gamma \cdot d$ 涉瘾。

一種理解方式是以原點 0 為球心知态，分別以 $d$ 為半徑作球體和以 $\gamma \cdot d$ 為半徑做球體，判斷 $t+\cal{L}$ 的點是否能落在以 $d$ 為半徑的球體之內(nèi)立叛，或判斷 $t+\cal{L}$ 的點是否都在以 $\gamma \cdot d$ 為半徑的球體之外负敏。

$ADD$ 問題（Absolute Distance Decoding）

令 $d \ge \mu(\mathbf{L})$ ，即 $d$ 已經(jīng)大于整個格的覆蓋半徑秘蛇，此時CVP問題至少會有一個解其做，但所找到的解并不一定是距離t最近的格點。

注：密碼學系統(tǒng)的安全性基于困難問題赁还，但不能基于NP困難問題來構(gòu)造格密碼方案妖泄，因為格上的NP困難問題有很多限制條件，因此艘策，格密碼學系統(tǒng)基于的困難問題其近似因子 $\gamma$ 量級常在 $n$ 與 $n^2$ 之間

二蹈胡、SIS問題與LWE問題

問題之間的關(guān)系:

各難題關(guān)系

1.SIS 問題

SIS: 小整數(shù)解問題 , Small Integer Solutions Problem

定義：

給定整數(shù) $m,n,q$ ，隨機選取矩陣 $A \in Z^{n \times m}_q$ 和界定參數(shù) $β$ 朋蔫，求解非零整數(shù)向量 $\boldsymbol{z}\in Z^m$ 罚渐，使得 $A z=0$ ，且 $||z|| \le \beta$ 驯妄。

不限定 $\boldsymbol{z}$ 范圍荷并，即為平凡問題（高斯消元即可解決）。
可以構(gòu)造抗碰撞哈希函數(shù)青扔。
與格的關(guān)系:
- 非平凡解構(gòu)成的集合形成了一個格源织；
- SIS問題等價為“找到該格中的一個短向量”；
- 如果可以解決SIS問題微猖，就可以解決格的最糟糕困難問題谈息，可以從任意格中找到短向量。

2.LWE問題

LWE: 容錯學習問題, Learning with Errors Problem

定義：

給定均勻隨機生成的矩陣 $A\in Z^{n\times m}_q$ 励两，向量 $s \in Z^m_q$ 和噪聲值 $e\in Z^n_q$ 都服從錯誤分布 $\mathcal X$ 黎茎， $b_i={ A}_i s+e$ 。

搜索版本的 LWE 問題（Search LWE, SLWE）：給定多組 $(A_i,b_i)$ 当悔，找到 $\boldsymbol s$ 傅瞻。
判定版本的 LWE問題（Decision LWE, DLWE）：將 $b_i$ 和均勻隨機生成的向量區(qū)分開。

困難性關(guān)系：

SLWE在最糟糕情況下的困難度不比解決GapSVP問題簡單（該困難性的證明需要量子歸約算法盲憎，用量子性質(zhì)將高斯選取的值組合在一起）嗅骄。
- SLWE困難性并未歸約到SIVP，只是歸約到GapSVP饼疙，但GapSVP也是困難問題溺森，結(jié)論仍很有意義。
- 歸約算法要求模數(shù)q非常大，需要與n成指數(shù)關(guān)系屏积，而不是多項式關(guān)系医窿。
SLWE困難度不比DLWE難，若前者是困難問題炊林，則后者也為困難問題姥卢。
基于LWE密碼學方案的構(gòu)造需要DLWE困難。

與SIS問題對比：

密碼學角度：
- SIS問題有計算假設渣聚，屬于搜索性問題（類似整數(shù)分解問題）独榴，需要找到 $\boldsymbol{z}$ 滿足已知等式。難以把SIS轉(zhuǎn)為判定問題奕枝，因為必存在 $\boldsymbol{z}=0$ 滿足條件棺榔，如果通過縮小維度轉(zhuǎn)為判定問題，則SIS和LWE問題等價隘道。
- LWE（一般指DLWE)屬于判定性問題（類似二次剩余和DDH（判定Diffie-Hellman)問題）, 需要區(qū)分給定值滿足一定條件還是完全均勻隨機的症歇。
解的角度：
- SIS可以有多個解；
- LWE只存在唯一解薄声，這種唯一性是用來構(gòu)造公鑰密碼和加密方案的基礎(chǔ)当船。
歸約角度
- LWE可以歸約到SIS, 如果可以解決SIS，也可以平凡地解決LWE：
  
  假如擁有 $(A默辨，b)$ 和SIS預言機，首先通過預言機得到滿足 $A\boldsymbol{z}=0$ 的 $\boldsymbol{z}$ 苍息，再將 $b$ 與 $\boldsymbol{z}$ 點乘缩幸，得到 $b\boldsymbol{z}=(As+e)\boldsymbol{z}=e\boldsymbol{z}$ 。
  - 如果 $b$ 是服從LWE分布的竞思，則 $e$ 為短的錯誤向量表谊，坐標很小且服從高斯分布，又因為 $\boldsymbol{z}$ 也很小盖喷，故 $b\boldsymbol{z}$ 點乘結(jié)果非常小爆办。
  - 如果 $b$ 是均勻隨機分布的，則 $b\boldsymbol{z}$ 很大课梳，在空間均勻分布距辆。因此我們可以根據(jù) $b\boldsymbol{z}$ 的大小對 $b$ 的分布做出判別，從而解決LWE問題暮刃。
- 這意味著LWE問題不比SIS困難跨算。
- 困難性關(guān)系SIS<=LWE還有待證明（但從某角度看應該是對的，如果可以使用量子計算機椭懊，則可方便地證明SIS和LWE等價）诸蚕。
應用角度：
- SIS應用于Minicrypt : 單向函數(shù)、抗碰撞Hash函數(shù)、簽名方案背犯、ID方案等坏瘩，但難以用于公鑰加密。
- LWE開創(chuàng)Cryptomania世界：公鑰加密（PKE)漠魏、不經(jīng)意傳輸(OT)桑腮、全同態(tài)加密（FHE)等。
格的角度：
- 可以將SIS看作格問題蛉幸，A定義了一個隨機格（所有滿足Az=0的z組成格點）破讨，SIS等價于要在該格中找短非零向量。
- LWE中奕纫，A類似格的基提陶，指定了格點，b和某一個隨機格點跟接近匹层，e是兩者的差隙笆。

LWE特性：

易檢驗性：檢驗s’是否為解只需計算所有LWE實例的 $b - <s’ , a >$ 是否都很小，如果是則s’=s, 即s’為解升筏。
平移性：可用原向量s平移t后所得的s+t構(gòu)造LWE有效實例撑柔，新實例為： $(a, b’)=(a, b+<t,a>)=(a,<s+t,a>+e)$ 。
隨機自歸約性：以上兩點特性組成LWE的隨機自歸約性您访，敵手可以借此放大解決LWE的成功概率铅忿，例如利用平移特性重隨機化秘密，每次就可以生成一個新的LWE問題實例灵汪。
多獨立秘密值：可以將k個LWE實例中獨立的秘密值 $b_i,...,b_t$ 重新組合為一個新LWE問題檀训，判斷它們都是LWE實例還是都是隨機值。

三享言、RLWE問題

定義：

給定均勻隨機生成的多項式 $a∈R_q$ 峻凫，與服從錯誤分布 χ的 $s∈R_q$ 和 $e∈R_q$ ，生成 $b_i=a_is+e_i$ 览露。

搜索版本的 RLWE 問題 (Search RLWE) 為：給定多組 ( $a_i,b_i$ )荧琼，找到 s；
判定版本的 RLWE 問題 (Decision RLWE) 為：將 $b_i$ 和均勻隨機生成的向量區(qū)分開差牛。

Vadim Lyubashevsky等給出了 R 中理想格上的近似 SVP (最壞情況下) 到 R-LWE 的搜索版本的量子歸約 (quantum reduction)命锄，其目標是從 (a,b=a?s+e) 中恢復秘密 $s∈R_q$ 。

RLWE 與 LWE 問題很類似多糠，只不過在 RLWE 問題中累舷，和 LWE 相比，直觀地看所有元素要"小了很多"夹孔。因為 RLWE 中被盈，每個部分都是一個多項式析孽，而不是 LWE 問題中的矩陣。這極大地提高了方案的實際效率只怎，也減小了通信開銷袜瞬。

類似的更靈活的問題還有 MLWE (Module Learning with Errors)。

四身堡、全同態(tài)加密

1.第一代FHE

2009 年邓尤，Gentry基于理想格構(gòu)造出了第一個全同態(tài)加密方案，摘取了“ 密碼學圣杯”贴谎。Gentry 設計了一個構(gòu)造全同態(tài)加密方案的 “藍圖”：

首先構(gòu)造一個類同態(tài)加密( Somewhat Homomorphic Encryption, SHE)方案(這類方案能夠同態(tài)計算一定深度的電路);
然后壓縮解密電路(需要稀疏子集和假設)汞扎，使得它能夠同態(tài)計算它本身的增強的解密電路，得到一個可以“自舉”(Bootstrapping)的同態(tài)加密方案;
最后有序執(zhí)行自舉操作(需要循環(huán)安全假設)擅这，得到一個可以同態(tài)計算任意電路的方案澈魄，即全同態(tài)加密。
同時仲翎，基于理想格上的 ICP 假設痹扇，并結(jié)合稀疏子集和與循環(huán)安全假設，他也開創(chuàng)性地構(gòu)造了一個具體的方案溯香。

2.第二代FHE：BGV鲫构、BFV

隨著 Gentry 全同態(tài)加密方案的提出，人們開始嘗試基于RLWE和NTRU相關(guān)問題構(gòu)造全同態(tài)加密方案玫坛，并結(jié)合理想格的代數(shù)結(jié)構(gòu)结笨、快速運算等優(yōu)良性質(zhì)來進行方案的優(yōu)化和實現(xiàn)，最終取得了成功昂秃，BGV禀梳、BFV等方案隨之產(chǎn)生。

第二代FHE特性：

在整數(shù)向量上進行高效的SIMD計算（使用批處理）肠骆；
快速高精度整數(shù)算術(shù)；
快速向量的標量乘法塞耕；
Leveled design（通常不需使用bootstrapping）蚀腿。

BFV 將基于LWE問題的 Brakerski 全同態(tài)方案移植到 RLWE 中。

BGV是在BV11b方案基礎(chǔ)上改進的新的全同態(tài)加密方法扫外，它極大地提高了性能莉钙，并基于較弱的假設建立了安全性。核心貢獻是在不需要使用 Gentry 的 bootstrapping 情況下筛谚，建立一種新的方法來構(gòu)造 Leveled 的全同態(tài)加密方案（能夠評估任意多項式大小的電路）磁玉。該方案采用模數(shù)切換來控制噪聲, 使得噪聲始終維持在較小的水平, 從而可以進行較多次的乘法同態(tài)運算。

3.第三代FHE：GSW驾讲、FHEW蚊伞、TFHE

2013 年席赂，Gentry 等人基于LWE和“ 近似特征向量”技術(shù)，設計了一個無需計算密鑰的全同態(tài)加密方案:GSW时迫，標志著第三代全同態(tài)加密方案的誕生颅停。他們進而還設計了基于身份和基于屬性的全同態(tài)加密方案，掀起了全同態(tài)加密研究的新高潮掠拳。

第三代FHE特性：

能夠快速比較癞揉；
支持任意布爾電路；
快速Bootstrapping（噪聲刷新過程溺欧，減少因密文計算而產(chǎn)生的噪音喊熟，降低失敗可能性）。

與非門是完備的, 可以通過不斷地疊加與非門來實現(xiàn)相當復雜的函數(shù)運算, 并且僅用與非門可以實現(xiàn)任何一個布爾函數(shù)姐刁。但是每一次進行與非門運算, 都會導致新密文得噪聲變得更大, 因此較多層的運算后, 噪聲可能大得導致解密錯誤芥牌。因此必須評估究竟能進行多少次的運算, 以及在快要達到極限的時候使用Bootstrapping技術(shù)。

這里以GSW為代表分析龙填，GSW方案根據(jù)解密算法的選區(qū)不同, 實際上有構(gòu)造兩套方案胳泉。

第一種是選擇 $\mathsf{Dec}$ 作為解密算法, 該算法僅能解出 $\mu_i\in\{0,1\}$ , 因此整個同態(tài)運算中主要用與非門構(gòu)建邏輯電路進行計算。
另一個解密算法 $\mathsf{MPDec}$ 可以解出 $\mu_i\in\mathbb Z_q$ , 這樣就可以自然地使用加法與乘法進行運算岩遗。

GSW并不是一個標準假設下的全同態(tài)加密方案扇商。 GSW如果要做到全同態(tài)加密, 需要用到Bootstrapping, 進而需要用到LWE加密方案的Circular Security假設(即用一對公私鑰中的公鑰來加密私鑰相關(guān)信息的加密結(jié)果是安全的)。FHEW宿礁、TFHE是GSW密碼系統(tǒng)的環(huán)變體案铺。

4.浮點數(shù)FHE：CKKS

CKKS是2017年提出基于RLWE的同態(tài)加密方案。它支持浮點向量在密文空間的加減乘運算并保持同態(tài)梆靖，但是只支持有限次乘法的運算控汉。這里對CKKS方案展開細致說明，具體操作如下：

1.編碼

目的：將復數(shù)向量映射成為多項式.
初始：對于 $M > 4$ 返吻，我們有 $N = ? ( M ) = M / 2$ 并且分圓多項式 $\Phi_M(X) = X^N + 1$ 姑子。
映射：求一個整數(shù)系數(shù)的插值多項式 $m(X)$ （用牛頓插值、拉格朗日插值测僵、快速傅里葉變換等都可以）街佑，使得 $m(\xi) \approx \Delta \times Message'_i$ 。即把 $X^n + 1 = 0$ 的復數(shù)根作為自變量丟到 m 里面去捍靠，使得輸出的值是 $Message'$ 的對應分量沐旨。
系數(shù)放大：由于共軛性質(zhì)，插值出來的 m 的系數(shù)都是實數(shù)榨婆。但是磁携，CKKS最后要對整數(shù)進行操作，因此需要對多項式系數(shù)進行取整良风。但如果直接對 m 系數(shù)取整谊迄，誤差會比較大闷供。因此在這里引入放大因子 $\Delta$ ，將Message的數(shù)值放大鳞上，得到 $m = m · \Delta$ 之后再進行取整这吻。這樣可以盡可能保留小數(shù)的位數(shù)，提高加密的精度篙议。
重縮放：引入了放大操作之后唾糯，多項式系數(shù)變大了很多。如果再做多次乘法鬼贱，就不可避免地會出現(xiàn)溢出模數(shù)的情形移怯。于是需要重縮放來避免這一問題。

CKKS的重縮放可以看作一種分層乘法機制这难，它引入了一個模數(shù)鏈 $Q = q_0 · p^L$ 舟误。這里的 p是和 $\Delta$ 大小近似的素數(shù)， $L$ 稱為乘法深度姻乓，近似為乘法最多可計算次數(shù)嵌溢。剛加密的密文的模數(shù)為 $Q$ ，當密文相乘時蹋岩， $\Delta$ 就會增加為原來的平方赖草，此時對系數(shù)除以 $p$ （也相當于對模數(shù)除以 $p$ ）來抵消掉 $\Delta$ 的增加，從而確保密文數(shù)據(jù)中自始至終僅有一個 $\Delta$ 因子剪个，但由于模數(shù)被除變小秧骑，乘法深度有一定的降低。
最終得到的m 即對消息編碼的結(jié)果扣囊。

2.解碼

與編碼過程相反乎折，將m代入 $\xi$ 即可，最后除以 $\Delta$ 侵歇。

3.加密

取私鑰 $(1, s)$ 骂澄，公鑰 $(b = -a·s + e, a)$ ，其中 s和 a 為向量惕虑，e為隨機數(shù)（這里基于RLWE問題確保了破解私鑰的困難性）
則密文 $(c_0, c_1) = r(b, a) + (m + e_1, e_2) = (rb + m + e_1, ra + e_2)$ 酗洒，其中r 為隨機整數(shù)， $e_1, e_2$ 為隨機多項式（也可以理解為向量）枷遂。

4.解密

計算 $c_0 + c_1 s$ 即可，其結(jié)果約等于m 棋嘲。過程如下：
$c_0 + c_1s = rb + m + e_1 + ra·s + e_2s = m + e_1 + e_2s + er$

5.運算

加法：明文向量按元素相加酒唉，密文向量對應位相加。
明文乘密文：
- 實質(zhì)： $m \times (c_1+ c_2s) = mc_1 + mc_2s$ ;
- 操作：將明文 $m$ 和密文中的 $c_1, c_2$ 逐個做多項式乘法沸移，得到的 $(c_1m, c_2m)$ 即為新密文痪伦。
密文乘密文：實質(zhì)計算

$(c_{11}+ c_{12}s) \times (c_{21}+ c_{22}s) = c_{11}c_{21} + (c_{21}c_{12}+c_{11}c_{22})s + c_{12}c_{22}s^2$

6.重現(xiàn)性化

原因：乘法會不可避免地導致乘積多項式的次數(shù)增加侄榴，從而需要更多空間存儲，我們希望進行在密文空間中做乘法之后密文向量對應的多項式次數(shù)保持不變网沾，即 $(c_0 +c_1s) * (c_2 + c_3s) = (d_0 + d_1s)$ 癞蚕，沒有s的平方項。
設計：
- 啟用一個重線性化秘鑰 $evk = (b', a') = (-a'·s + e' + bs^2, a')$ 辉哥。我們將示例 $c_0c_2 + (c_0c_3 + c_1c_2)s + c_1c_3s^2$ 記為： $d_0 + d_1s + d_2 s^2$ 桦山，其中 $d_0, d_1, d_2$ 都可由密文乘積計算得出。
輸出的密文結(jié)果為 $(c'_1, c'_2) = (d_0, d_1) + p^{-1}·d_2·evk$ 醋旦，其中 $p$ 為重縮放中的模數(shù)因子恒水。
理由：

$P^{-1}d_2(b', a')·(1, s) = P^{-1}·d_2·b' + P^{-1}·d_2·a' ·s = d_2s^2 + P^{-1}d_2e' \approx d_2s^2$

五、同態(tài)加密的工程實現(xiàn)

當前已經(jīng)有非常多的成熟同態(tài)加密庫饲齐，主要包括cuFHE钉凌、FHEW、FV-NFLib捂人、HEAAN御雕、HElib、PALISADE滥搭、SEAL酸纲、TFHE 和 Lattigo等。各有其優(yōu)勢论熙，一些庫及其支持的同態(tài)加密算法如下圖所示：

SEAL實現(xiàn)

這里以BFV算法為例進行SEAL庫的同態(tài)加密實現(xiàn)說明福青，CKKS算法的實現(xiàn)過程與之類似，因此只對兩者不同處做出說明脓诡，不再對CKKS的實現(xiàn)展開介紹无午。

1.參數(shù)的取值與作用

poly_modulus_degree：環(huán)的分母項（分圓多項式） $x^n + 1$ 中n的值。明文多項式或密文多項式中最高次數(shù)為n-1祝谚。BFV方案中n必須為2的冪宪迟，通常取值為 $2^{10}$ 到 $2^{15}$ 。n取值越大則RLWE加密方案越安全交惯，但對應的密文也越大次泽，各種計算操作也更慢。
coeff_modulus: 密文多項式系數(shù)的模, 決定密文噪音預算（noise budget）的重要參數(shù), 值越大席爽，噪聲預算越大意荤，加密計算能力越強，但其上限由poly_modulus_degree決定只锻。但該值越大則RLWE加密方案越不安全玖像。
plain_modulus：取值任意，這里取了2的模數(shù)齐饮。它決定了明文數(shù)據(jù)的規(guī)模以及乘法計算所消耗的噪聲預算捐寥。因此笤昨，可以盡量取小值來保證效率。

一個新加密的密文的噪聲預算為： $log_2(\frac{coeff\_modulus}{plain\_modulus})\ bits$

一次同態(tài)乘法所消耗的噪聲預算為： $log_2(plain\_moduls)\ +\ 其他次要項$

plaintext modulus為BFV獨有握恳，CKKS無法設置瞒窒。

2.編碼操作（Encode)

BFV的加密過程是將明文多項式轉(zhuǎn)化為密文多項式，而不是直接對整數(shù)或浮點數(shù)進行加密操作乡洼。因此崇裁，需要編碼操作將整數(shù)或浮點數(shù)轉(zhuǎn)化為明文多項式，以便進行隨后的加密操作就珠。BFV目前主要有三種編碼方式：IntegerEncoder寇壳、FractionalEncoder和BatchEncoder。

3.重線性化操作（Relinearization）

BFV密文的size是其所含的多項式的個數(shù)妻怎。初始時密文由2個多項式組成壳炎，其size為2。但是逼侦，每次乘法操作后匿辩，結(jié)果密文的size變?yōu)镸 + N - 1，其中M和N分別為參與乘法操作的密文的size榛丢。雖然size變大后密文還能正常解密铲球，但會帶來兩個負面影響：

乘法和加法的計算開銷變大。每次密文乘法需要進行O(M * N)次多項式乘法晰赞，而密文加法則需要O(M + N)次多項式加法稼病。
每次乘法操作所消耗的noise budget也變大响禽。

重線性化可以讓密文的size重新回到最小值2猫妙，因此對性能有較大好處揭鳞。

Relinearization操作本身也有計算開銷和noise budget消耗钝域，并且與分解位數(shù)（decomposition bit count)參數(shù)（記為w）相關(guān)，具體關(guān)系如下：

w取值為1到60之間的整數(shù)硕淑∏瞅剑總體來說皮胡，若w取值小褐墅，計算速度較慢拆檬，但每次操作noise budget消耗很少；反之妥凳，若w取值大竟贯，計算速度較快，但每次操作noise budget消耗很大逝钥。
雖然w可能取值較大澄耍，但該w在每一組加密參數(shù)取值下都對應一個noise budget閾值。
- 當ciphertext的noise budget在該閾值之上時，每次relinearization操作會消耗較多的noise budget齐莲；
- 一旦ciphertext的noise budget減小到低過該閾值，再進行relinearizaiton時noise budget的消耗會下降到很小磷箕。

4.旋轉(zhuǎn)操作（Rotation）

在BatchEncoding(編碼方式的一種）下选酗，每個密文可看作內(nèi)含一個2*(n/2)的矩陣。而旋轉(zhuǎn)操作Rotation就是將矩陣內(nèi)的元素按行或列循環(huán)移位岳枷。

與Relinearization操作一樣芒填，Rotation的計算也基于分解位數(shù)（Decomposition Bit Count）參數(shù)w，w在1到60之間取值越大則計算越快空繁，但消耗的noise budget也越多殿衰。
同樣的，在某個w和一組加密參數(shù)下存在對應的noise budget閾值盛泡，當密文的noise budget大于閾值時闷祥，每次選擇會導致noise budget消耗很多，但一旦下降到低于該閾值傲诵，再進行Rotation操作時noise budge的消耗會下降到很小凯砍。

5.模轉(zhuǎn)換操作（Modulus switching）

BFV密文多項式系數(shù)的模coeff_modulus是一組素數(shù)的乘積。在初始化一組加密參數(shù)時拴竹，SEAL會自動生成一個參數(shù)鏈悟衩，鏈上的每個節(jié)點都是由初始參數(shù)推算出的一組新的加密參數(shù)，并且栓拜，每個節(jié)點與前一個節(jié)點的參數(shù)相比只是在coeff_modulus上減少了一個素數(shù)座泳，其它的幾乎完全一樣。鏈上最后一組參數(shù)的index為0幕与，且滿足參數(shù)的有效性：coeff_modulus大于plain_modulus的值挑势。
初始創(chuàng)建的參數(shù)組中coeff_modulus是最大的，每次Modulus switching都會減少coeff_modulus纽门，從而可能帶來noise budget降低薛耻。Modulus switching有如下益處：

密文大小與coeff_modulus線性正相關(guān)，如果確定密文不需再參與計算后赏陵，可以將其coeff_modulus降到最低值饼齿，以降低存儲和傳輸?shù)拈_銷。
密文在經(jīng)過計算后其內(nèi)部的noise budget已經(jīng)降低蝙搔，此時如果適當降低coeff_modulus缕溉，有可能不會對noise budget產(chǎn)生影響。
有些情況下即使減小coeff_modulus會降低noise budget吃型，但這種操作可以有效降低隨后的計算開銷（加快計算速度）证鸥，并減小密文的大小，仍是一種利大于弊的操作。

6.CKKS與BFV的主要區(qū)別

參數(shù)上枉层，CKKS沒有plain_modulus泉褐。其主要參數(shù)的設置（poly_modulus_degree和coeff_modulus）與BFV方案的設置類似。CKKS的明文多項式系數(shù)以coeff_modulus為模鸟蜡，與BFV不同膜赃。
操作上，CKKS設計了重縮放Rescaling操作：
- Rescaling操作是CKKS區(qū)別于BFV的重要操作揉忘。Rescaling與Modulus switching類似跳座，相同之處在于也是從coeff_modulus中除去一個素數(shù)因子。
- 不同之處在于泣矛，它同時產(chǎn)生的效果是將當前的scale因子也除以該素數(shù)因子疲眷。BFV處理浮點數(shù)時最大的問題是密文中的scale因子會累積膨脹越來越大而無法計算，而CKKS通過Rescaling降低密文的scale因子您朽，有效解決了處理浮點數(shù)時的scale問題狂丝。