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

（1.武警工程大學(xué)密碼工程學(xué)院，西安 710086；2.中國(guó)科學(xué)院軟件研究所，北京 100090；3.網(wǎng)絡(luò)和信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室（武警工程大學(xué)），西安 710086）

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

0 引言

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

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

雖然同態(tài)加密為云計(jì)算中的數(shù)據(jù)隱私保護(hù)提供了一個(gè)良好的解決方案，但由于同態(tài)加密方案需要對(duì)龐大的密態(tài)數(shù)據(jù)進(jìn)行同態(tài)運(yùn)算，因此在存儲(chǔ)和傳輸加密數(shù)據(jù)時(shí)，無(wú)疑會(huì)給用戶造成較大的通信開(kāi)銷負(fù)擔(dān)。同時(shí)，錯(cuò)誤學(xué)習(xí)（Learning With Errors，LWE）型CKKS 方案的重線性化過(guò)程［17］所需的計(jì)算密鑰規(guī)模龐大，計(jì)算復(fù)雜，也影響了方案的實(shí)際運(yùn)用。低位比特丟棄（low-order Bits Discarding algorithm，BD）的思想最早出現(xiàn)于格密碼中，Zhou 等［18］將其應(yīng)用于同態(tài)加密以提高效率。在此基礎(chǔ)上，本文結(jié)合LWE型CKKS方案的密文結(jié)構(gòu)，通過(guò)舍去密文中的部分低位比特來(lái)減少存儲(chǔ)的比特?cái)?shù)，從而降低了重線性化過(guò)程中計(jì)算密鑰的大小和計(jì)算開(kāi)銷，提高了方案的存儲(chǔ)和計(jì)算效率。

1 相關(guān)知識(shí)和關(guān)鍵技術(shù)

1.1 相關(guān)定義

定義1誤差學(xué)習(xí)問(wèn)題［19］。

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

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

對(duì)于一個(gè)整數(shù)分布集合{χn}n∈N，如果下列等式成立

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

1.2 關(guān)鍵技術(shù)

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

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

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

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

2 低位方法的應(yīng)用

2.1 CKKS17方案

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

其中:映射π-1表示將復(fù)數(shù)映射到本身與其共軛復(fù)數(shù)的集合；σ-1則利用離散傅里葉變換來(lái)實(shí)現(xiàn)復(fù)數(shù)向量向分圓多項(xiàng)式環(huán)上元素的變換。

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

2.2 低位比特丟棄方法的構(gòu)造

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

計(jì)算機(jī)中數(shù)的存儲(chǔ)通常采用二進(jìn)制存儲(chǔ)，不同比特所處的位置不同所代表的權(quán)重也不相同，因此，可以通過(guò)舍棄存儲(chǔ)密文每一個(gè)分量的部分低位比特來(lái)減少存儲(chǔ)空間，密文整體比特?cái)?shù)的降低也能夠提升密文通信的效率。由于密鑰采樣的分布通常是一些“小分布”（采樣值的絕對(duì)值相對(duì)較?。?，因此丟棄低位比特對(duì)噪聲的貢獻(xiàn)并不會(huì)很大。同時(shí)在方案的重線性化過(guò)程中，丟棄低位比特能夠減小計(jì)算密鑰的大小，從而降低由于重線性化加密私鑰所產(chǎn)生的噪聲，其具體構(gòu)造如下。

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

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

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

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

2.2.1 低位比特丟棄在同態(tài)加法中的應(yīng)用

同態(tài)加法操作由于不涉及進(jìn)行復(fù)雜昂貴的重線性化操作，只需要對(duì)輸入的兩個(gè)密文丟棄相應(yīng)的低位比特即可，如下所述:

設(shè)c1，c2∈是兩個(gè)加法密文輸入，首先對(duì)兩個(gè)密文進(jìn)行低位比特丟棄，得到=BD(c2，δ)。輸出同態(tài)加法的結(jié)果密文cadd=

2.2.2 低位比特丟棄在同態(tài)乘法中的應(yīng)用

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

3.1 方案構(gòu)造

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

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

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

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

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

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

對(duì)于一個(gè)密文向量c與私鑰sk，解密算法為m'=

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

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

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

3.2 正確性

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

3.2.1 加法正確性

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

令c1δ和c2δ分別代表相應(yīng)密文向量丟棄低位δ比特后的差值，當(dāng)

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

3.2.2 乘法正確性

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

故:

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

4 方案分析

4.1 噪聲分析

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

4.1.1 同態(tài)加法噪聲

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

4.1.2 同態(tài)乘法噪聲

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

與原來(lái)的同態(tài)乘法噪聲相比，在δ與δ′取合適值時(shí)，本文方案既能降低同態(tài)乘法運(yùn)算時(shí)計(jì)算密鑰的復(fù)雜性，也能降低噪聲和密文的存儲(chǔ)開(kāi)銷。

4.2 效率

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

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

4.3 安全性

本文提出的低位比特丟棄方法在CKKS17 方案上進(jìn)行了優(yōu)化，其密鑰生成算法、重線性化技術(shù)及加解密過(guò)程仍與CKKS17保持一致，安全性依賴于LWE 問(wèn)題的困難性。同時(shí)，低位比特丟棄技術(shù)可視為密文向量的低位比特與另一向量的“與”過(guò)程，對(duì)安全性沒(méi)有影響。因此，本文提出的低位比特丟棄方法設(shè)計(jì)的優(yōu)化加密方案的安全性與CKKS17 方案的安全性相同，可以達(dá)到語(yǔ)義安全。

5 結(jié)語(yǔ)

CKKS17方案作為目前實(shí)際應(yīng)用中重要的一個(gè)方案，具有支持浮點(diǎn)數(shù)運(yùn)算的優(yōu)點(diǎn)。本文在原有方案的基礎(chǔ)上通過(guò)舍棄密文低位比特的方法，對(duì)其進(jìn)行了優(yōu)化，提出了優(yōu)化的LWE型CKKS 方案。相較于現(xiàn)在的方案，本文所優(yōu)化的方案縮減了重線性化密鑰的尺寸，使得同態(tài)計(jì)算的效率得到了提升，且密文向量比特的減少也使得該方案在實(shí)際運(yùn)用過(guò)程中的存儲(chǔ)和通信效率得以提高?；赗LWE 的CKKS 方案能夠?qū)⒍鄠€(gè)密文打包進(jìn)行計(jì)算，效率更高，下一步將針對(duì)RLWE 型CKKS方案的優(yōu)化進(jìn)行研究。