優化的基于錯誤學習問題的CKKS方案

鄭尚文，劉 堯，周潭平，2*，楊曉元，3

（1.武警工程大學密碼工程學院，西安 710086；2.中國科學院軟件研究所，北京 100090；3.網絡和信息安全武警部隊重點實驗室（武警工程大學），西安 710086）

（?通信作者電子郵箱850301775@qq.com）

0 引言

全同態加密（Fully Homomorphic Encryption，FHE）允許在不解密的狀態下對密文進行任意運算，且解密后結果與其對應明文進行同樣運算的結果相等。這一優良特性與云計算條件下對數據隱私保護的需求十分契合，具有廣闊的應用前景。2009 年Gentry［1］首先構造了第一個基于理想格的全同態加密方案Gen09，并且描繪了實現純全同態加密的“藍圖”——同態運行解密電路。之后，一系列（全）同態加密方案［2-7］相繼被提出，同態加密成為信息安全研究領域的熱點，得到迅速發展。目前，同態加密在基因組分析［8］、醫療［9］、金融［10］和安全多方計算（Secure Multi-Party Computation，MPC）等領域［11-12］發揮了重要作用。

CKKS17（Cheon-Kim-Kim-Song 2017）同態加密方案由Cheon 等［7］在ASIACRYPT17（2017 International Conference on the Theory and Application of Cryptology and Information Security）會議上提出，支持對浮點數進行近似計算，效率較高，是目前最重要、最具前景的同態加密算法之一。與以往同態加密方案明文空間和噪聲空間分隔開的設計不同，CKKS17的明文空間沒有取模過程，因此也不能在解密后通過相應的模運算來得到準確的解密結果:它將噪聲視為明文的一部分，而噪聲一方面來源于加密方案中為保證安全性而引入的錯誤，另一方面也來源于近似計算中的舍入誤差，密文解密后不能將明文中的噪聲去除，只能以預定的精度輸出明文的近似值。在同態運算過程中，計算結果的高有效位（Most Significant Bits，MSBs）能夠保留，而不精確的低位比特（Least Significant Bits，LSBs）則在RS（ReScaling）過程中被舍去，以此管理結果密文對應的明文尺寸，這也使得方案所需最大密文模數隨乘法深度由指數增長降為線性增長。CKKS17 方案提出之后，研究人員在此基礎上做了進一步的研究。2018年，Cheon等［13］提出了CKKS17的Bootstrapping技術，將其由層級同態加密推廣至完全同態加密，并提出了支持余數系統（Residue Number System，RNS）分解的CKKS17 方案的變體［14］；后續，Chen 等［15］對Bootstrapping 過程進行了優化，使自舉的時間降低兩個數量級；2019年，Chen等［16］提出了CKKS17的多密鑰版本CDKS19（Chen-Dai-Kim-Song 2019），并對該方案應用于神經網絡模型的效率進行了測試。

雖然同態加密為云計算中的數據隱私保護提供了一個良好的解決方案，但由于同態加密方案需要對龐大的密態數據進行同態運算，因此在存儲和傳輸加密數據時，無疑會給用戶造成較大的通信開銷負擔。同時，錯誤學習（Learning With Errors，LWE）型CKKS 方案的重線性化過程［17］所需的計算密鑰規模龐大，計算復雜，也影響了方案的實際運用。低位比特丟棄（low-order Bits Discarding algorithm，BD）的思想最早出現于格密碼中，Zhou 等［18］將其應用于同態加密以提高效率。在此基礎上，本文結合LWE型CKKS方案的密文結構，通過舍去密文中的部分低位比特來減少存儲的比特數，從而降低了重線性化過程中計算密鑰的大小和計算開銷，提高了方案的存儲和計算效率。

1 相關知識和關鍵技術

1.1 相關定義

定義1誤差學習問題［19］。

設λ為安全參數，令n=n(λ)是一個整數維數，q=q(λ) ≥2 為一個整數，χ=χ(λ)是整數上的一個分布。判定型LWEn，q，χ定義為區分下面兩個分布:1）第一個分布，均勻地從中選取產生(ai，bi)；第二個分布，均勻選取s←和計算bi=〈ai，s〉+ei，組成

定義2B?bound分布［17］。

對于一個整數分布集合{χn}n∈N，如果下列等式成立

則稱整數分布集合{χn}n∈N是B?bound分布。

1.2 關鍵技術

方案運用了BitDecomp(?)、Powersof2(?)［4］及張量積等方法，具體操作為:

1）BitDecomp(x∈，q):對于輸入向量x∈，BitDecomp將其表示為x=其 輸出為，其中uj∈R。顯然，x=

2）Powersof2(x∈，q):對于某 個輸入向量，Powersof2 是BitDecomp的逆過程，其輸出為(x，2·x，…，∈。由上述定義，對于給定兩個維數相同的向量a、b，不難驗證下面等式:

3）設u、v分別為n、m維向量，則向量u、v的張量積定義為u?v=(u1v1，u1v2，…，u1vm，…，unv1，…，unvm)。根據張量積和內積的定義，可以證明如下等式:

2 低位方法的應用

2.1 CKKS17方案

CKKS17 方案［7］主要包括六個基本算法（KeyGen，Enc，Dec，Add，Mult，RS），本文主要對基于LWE 的CKKS 加密方案進行優化，下面對該方案作以簡要介紹。首先，該方案利用Ecd、Dcd及縮放因子Δ來實現消息與明文的相互映射。以消息為復數，明文以分圓多項式環上的元素為例，Dcd首先將明文多項式m(X)除上因子Δ，然后計算該明文多項式在分圓多項式ΦM(X)根處的函數值，并取整，得到最終的復數消息向量。而Ecd即為Dcd的逆變換，具體過程為:

其中:映射π-1表示將復數映射到本身與其共軛復數的集合；σ-1則利用離散傅里葉變換來實現復數向量向分圓多項式環上元素的變換。

在密鑰初始化階段，基于LWE 問題生成公私鑰對(pk，sk)以及計算密鑰evk，用于對明文加解密以及乘法中的重線性化。與其他基于LWE 加密方案不同的是，CKKS17 方案中引入了一個新的概念:rescaling，它應用在乘法密文重線性化步驟后，通過將被加密的明文除上一個整數，并利用浮點數和科學計數法在近似計算中的“四舍五入”來去除明文中一些不精確的低位比特，從而使得在同態計算期間，編碼前后的消息的大小保持基本不變，同時也保證了方案所需的最大密文模數隨運算電路深度呈線性增長，極大提高了方案的效率，促進了方案的實用化發展。根據基于RLWE（Ring LWE）的CKKS 方案編寫了開源的同態加密庫HEEAN。

2.2 低位比特丟棄方法的構造

在同態加密方案［20］的實際使用中，為了提高方案效率，一般使用中國剩余定理（Chinese Remainder Theorem，CRT）將大密文分割成小塊密文（模數較小的密文）進行操作，但進行重線性化步驟時仍需要將其轉化為一般的表示形式。重線性化過程所使用的計算密鑰的尺寸很大，這是影響方案效率的重要因素。針對這一過程，本文提出了一種低位比特丟棄方法，通過有選擇地舍棄密文中的部分低位比特從而相應地減小重線性化密鑰的尺寸來提高方案效率。下面對本文方法的主要思想進行介紹。

計算機中數的存儲通常采用二進制存儲，不同比特所處的位置不同所代表的權重也不相同，因此，可以通過舍棄存儲密文每一個分量的部分低位比特來減少存儲空間，密文整體比特數的降低也能夠提升密文通信的效率。由于密鑰采樣的分布通常是一些“小分布”（采樣值的絕對值相對較小），因此丟棄低位比特對噪聲的貢獻并不會很大。同時在方案的重線性化過程中，丟棄低位比特能夠減小計算密鑰的大小，從而降低由于重線性化加密私鑰所產生的噪聲，其具體構造如下。

定義3低位比特丟棄（BD）方法。

設密文c∈，δ為丟棄的低位比特位數，比特丟棄方法的主要做法是丟棄輸入密文c中n個分量各自的低位δ比特，得到cBD=BD(c，δ)∈，其中cBD中每一個分量根據丟棄比特向量cδ最高位0、1取值的不同，有選擇地加上進位。即當cδ的首位比特為1 時，向前進位；當cδ的首位比特為0 時，不進位，具體如圖1所示。

圖1 低位比特丟棄方法Fig.1 Low-order bits discarding method

選擇性地加上進位能夠使得丟棄低位比特后的密文向量與原始密文向量的差值更小，更好地控制噪聲的增長。單純的比特丟棄技術并不會降低密文的噪聲，但是在密文進行同態運算時丟棄低位比特能夠減少相應噪聲并提高計算效率，具體到方案同態運算中的應用如下。

2.2.1 低位比特丟棄在同態加法中的應用

同態加法操作由于不涉及進行復雜昂貴的重線性化操作，只需要對輸入的兩個密文丟棄相應的低位比特即可，如下所述:

設c1，c2∈是兩個加法密文輸入，首先對兩個密文進行低位比特丟棄，得到=BD(c2，δ)。輸出同態加法的結果密文cadd=

2.2.2 低位比特丟棄在同態乘法中的應用

3 基于低位比特丟棄的LWE型CKKS方案

3.1 方案構造

選取合適的基p＞0，模數q0，令ql=pl·q0，0 ＜l≤L。HWT(h)［21］為有符號的、漢明重量為h的N維{-1，0，1}N向量集合，λ為安全參數。在計算密鑰的生成和同態運算中運用了低位比特丟棄方法進行優化，基于低位比特丟棄的LWE 型CKKS方案主要包括以下六個算法:

1）密鑰生成算法KeyGen(1λ)。

①選取質數p和整數q0、τ，設ql=plq0，l=1，2，…，L，合理選取參數N=N(λ，qL)和B?bound 錯誤分布χ=χ(λ，qL)作為LWEN，qL，χ問題的參數。輸出params=(n，qL，χ，τ)。②隨機選取s=HWT(h)，私鑰sk←(1，s)∈。隨機均勻選取A←，e←χτ。令b=-As+e(modqL)，輸出方案的公鑰pk=(b，A)∈

2）加密算法Enc(m，pk)。

對于一個整數m∈Z 的明文，隨機均勻選取一個向量r←{0，1}τ。輸出其密文c←(m，0)+pkT·r∈

3）解密算法:Dec(c，sk)。

對于一個密文向量c與私鑰sk，解密算法為m'=

4）同態加法ADD(c1，c2)。

5）同態乘法Mult(c1，c2)。

6）重縮放RSl→l'(c)。

3.2 正確性

本文方案的加解密正確性與原始的CKKS17 方案大致相同，在此不作闡述，主要論述在運用低位比特丟棄方法之后同態加法和同態乘法的正確性。設c1，c2分別是對m1，m2∈Z加密的密文，噪聲分別為e1，e2。

3.2.1 加法正確性

其同態加法輸出cadd=c1+c2，滿足如下等式:

令c1δ和c2δ分別代表相應密文向量丟棄低位δ比特后的差值，當

Δ為消息與明文之間轉化的縮放量，方案正確性成立。

3.2.2 乘法正確性

其同態乘法輸出cmult=c1×c2，滿足如下等式:

故:

其中，[BitDecomp、ciδ(i=1，2）分別代表cBD、ci丟棄δ′位比特向量后與原來向量的差值，即:

4 方案分析

4.1 噪聲分析

假設方案加密的明文上限為ν，密文維數為N+1，δ、δ′為相應向量丟棄的比特位數。根據ei=rTei(i=1，2)，ei←χ，s=HWT(h)，sk←(1，s)∈，下面對同態加法和同態乘法的噪聲上界進行分析。

4.1.1 同態加法噪聲

由式（1）可得加法噪聲:

4.1.2 同態乘法噪聲

綜合式（2）、（3），有:

與原來的同態乘法噪聲相比，在δ與δ′取合適值時，本文方案既能降低同態乘法運算時計算密鑰的復雜性，也能降低噪聲和密文的存儲開銷。

4.2 效率

本文所提出的低位比特丟棄方法能夠減小重線性化密鑰的尺寸，使原來的計算密鑰維度從降低 至；定義計算復雜性等于向量中各數值元素參與運算的次數，本文方案通過丟棄低位比特，同態乘法的計算復雜性得到明顯減小，降低了計算開銷；同時，該方案進行通信的每一個密文向量均減少了δ比特，提高了通信效率，也減小了密文向量的存儲開銷，使該方案在實際使用過程中更加快速高效。本文方案與LWE 型CKKS 方案的性能對比如表1 所示。由表1 可以看出，相較LWE 型CKKS 方案，本文所提優化方案使得計算密鑰的維度減少，使得同態乘法的計算復雜性降低。

表1 本文方案與LWE型CKKS方案的性能對比Tab.1 Performance comparison between proposed scheme and LWE type CKKS scheme

4.3 安全性

本文提出的低位比特丟棄方法在CKKS17 方案上進行了優化，其密鑰生成算法、重線性化技術及加解密過程仍與CKKS17保持一致，安全性依賴于LWE 問題的困難性。同時，低位比特丟棄技術可視為密文向量的低位比特與另一向量的“與”過程，對安全性沒有影響。因此，本文提出的低位比特丟棄方法設計的優化加密方案的安全性與CKKS17 方案的安全性相同，可以達到語義安全。

5 結語

CKKS17方案作為目前實際應用中重要的一個方案，具有支持浮點數運算的優點。本文在原有方案的基礎上通過舍棄密文低位比特的方法，對其進行了優化，提出了優化的LWE型CKKS 方案。相較于現在的方案，本文所優化的方案縮減了重線性化密鑰的尺寸，使得同態計算的效率得到了提升，且密文向量比特的減少也使得該方案在實際運用過程中的存儲和通信效率得以提高。基于RLWE 的CKKS 方案能夠將多個密文打包進行計算，效率更高，下一步將針對RLWE 型CKKS方案的優化進行研究。