基于矩陣的安全多方計(jì)算同態(tài)加密方案

摘 要：針對(duì)現(xiàn)有同態(tài)加密方案效率低，同態(tài)運(yùn)算噪聲增長速率高影響解密正確性的問題進(jìn)行了研究，提出了一種格上基于整數(shù)矩陣的安全多方計(jì)算同態(tài)加密方案。方案采用了矩陣存儲(chǔ)方式來處理明文數(shù)據(jù)并減小了密鑰尺寸，與傳統(tǒng)的比特或向量存儲(chǔ)方式相比，矩陣存儲(chǔ)方法在處理大規(guī)模數(shù)據(jù)時(shí)更為高效。為了控制噪聲增長并提高解密結(jié)果的準(zhǔn)確性，引入了比例降噪技術(shù)，可以有效地減緩噪聲的累積。運(yùn)用密文打包并對(duì)自舉技術(shù)進(jìn)行改進(jìn)削減了噪聲增長速率，為實(shí)現(xiàn)安全多方計(jì)算提供了條件。通過嚴(yán)格的理論證明，驗(yàn)證了方案的正確性和安全性。實(shí)驗(yàn)結(jié)果表明本方案加密、解密時(shí)間相較于對(duì)比方案至少降低了66.97%、33.04%，表現(xiàn)出了顯著的性能優(yōu)勢(shì)。

關(guān)鍵詞：同態(tài)加密；矩陣運(yùn)算；安全多方計(jì)算；數(shù)據(jù)隱私；格

中圖分類號(hào)：TP309.7"" 文獻(xiàn)標(biāo)志碼：A"" 文章編號(hào)：1001-3695（2025）04-033-1211-06

doi：10.19734/j.issn.1001-3695.2024.06.0267

Matrix based secure multi-party computation homomorphic encryption scheme

Chen Honga，Ma Boyua，Jin Haiboa，Wu Congb

（a.College of Software，b.Science amp; Technology Research Institute，Liaoning Technical University，F(xiàn)uxin Liaoning 123000，China）

Abstract：

A study has been conducted on the current issues of homomorphic encryption schemes，such as their low efficiency and high noise growth rate，which affects the accuracy of decryption. This paper proposed a novel homomorphic encryption scheme for secure multi-party computation based on integer matrices over lattices.This scheme utilized matrix storage to handle plaintext data，reducing the size of the encryption keys.Compared to traditional bit or vector storage methods，the matrix storage approach was more efficient when dealing with large-scale data.To control noise growth and enhance the accuracy of decryption results，it introduced proportional noise reduction technology，effectively mitigating the accumulation of noise.The scheme also employed ciphertext packing and improved the bootstrapping technique to reduce the noise growth rate，providing conditions for secure multi-party computation.It provided rigorous theoretical proofs to validate the correctness and security of the scheme.Experimental results demonstrate that the encryption and decryption times of this scheme are at least 66.97% and 33.04% lower than those of comparative schemes，respectively，showing a significant performance advantage.

Key words：homomorphic encryption;matrix operations;secure multi-party computation;data privacy;lattice

0 引言

互聯(lián)網(wǎng)大規(guī)模應(yīng)用的同時(shí)，帶來了對(duì)數(shù)據(jù)隱私和安全性的考驗(yàn)。隨著個(gè)人隱私數(shù)據(jù)在互聯(lián)網(wǎng)上不斷累積，如何在不可信的環(huán)境中確保數(shù)據(jù)的安全性和隱私性，成為了一個(gè)亟待解決的問題。同態(tài)加密技術(shù)，尤其是矩陣同態(tài)加密方案，因其允許在加密數(shù)據(jù)上直接進(jìn)行計(jì)算的特性，為解決上述問題提供了一種有效的技術(shù)手段。在這種技術(shù)的支持下，數(shù)據(jù)操作者可以在不了解數(shù)據(jù)真實(shí)內(nèi)容的情況下對(duì)加密數(shù)據(jù)執(zhí)行同態(tài)計(jì)算，將結(jié)果以密文形式返回給用戶，即使云服務(wù)器遭受攻擊或存在內(nèi)部威脅，用戶的數(shù)據(jù)隱私也能得到有效保護(hù)。

2005年，Aharonov等人［1］首次提出了LWE（learning with errors）的概念，LWE問題基于格理論，是一個(gè)困難的問題，在密碼學(xué)中被用作構(gòu)建加密算法的基礎(chǔ)。LWE問題提出后，不斷有人研究改進(jìn)。2013年，Gentry等人［2］提出了GSW（Gentry-Sahai-Waters）方案，該方案是一種基于LWE的同態(tài)加密方案，使用近似特征向量的方法來代替重新線性化技術(shù)，使其更有效地減少公鑰的長度和存儲(chǔ)開銷。隨著同態(tài)加密技術(shù)在數(shù)據(jù)安全和隱私保護(hù)領(lǐng)域變得日益重要，基于LWE問題和GSW方案的同態(tài)加密方案及其應(yīng)用得到了廣泛關(guān)注。

2023年，Xu等人［3］基于LWE問題構(gòu)造了多密鑰兩服務(wù)器同態(tài)秘密共享方案，該方案允許參與者在計(jì)算服務(wù)器之間共享私有數(shù)據(jù)，以聯(lián)合計(jì)算公共函數(shù)而無須完全同態(tài)加密。Biswas等人［4］研究多密鑰同態(tài)加密，可以加密多位消息，提出了一種具有非交互式解密和抗選擇明文攻擊的新算法。Fan等人［5］針對(duì)基于單一身份的全同態(tài)加密方案不能滿足不同身份下密文的同態(tài)運(yùn)算、陷門效率低、采樣算法復(fù)雜等問題，將高效的陷門函數(shù)與對(duì)偶LWE算法結(jié)合，提出了一種改進(jìn)的多身份全同態(tài)加密方案，該方案陷門生成與原像采樣效率得到了提高，且格維數(shù)和密文尺寸都有顯著削減。Zeng等人［6］在LWE的基礎(chǔ)上首次設(shè)計(jì)了一種靈活的并行密文擴(kuò)展算法，該算法實(shí)現(xiàn)了多個(gè)密鑰同時(shí)加入時(shí)的密文擴(kuò)展，顯著提高了方案中密文擴(kuò)展的計(jì)算效率。但上述方案均需要管理多個(gè)密鑰，會(huì)導(dǎo)致密鑰管理復(fù)雜，而且多密鑰同態(tài)加密方案通常計(jì)算效率低下，噪聲增長速率較高，可能會(huì)導(dǎo)致解密錯(cuò)誤。

2021年，Zhao等人［7］為了減少密文的膨脹，利用整數(shù)密文與向量密文的混合同態(tài)運(yùn)算，提高了同態(tài)運(yùn)算的效率。同時(shí)引入了序列化的噪聲管理方案，減小了密文的大小。Bai等人［8］基于GSW的同態(tài)矩陣加密方案構(gòu)造了一種簡化矩陣計(jì)算操作，提高矩陣運(yùn)算效率的方法，并且可以執(zhí)行卷積神經(jīng)網(wǎng)絡(luò)隱私預(yù)測(cè)任務(wù)。2022年，Zhao等人［9］基于GHV（Gentry-Halevi-Vaikuntanathan）提出了一種改進(jìn)的同態(tài)加密方案，并對(duì)其進(jìn)行優(yōu)化以提高原始GHV方案的效率，該方法具有更小的密鑰和密文尺寸，但在處理大量數(shù)據(jù)時(shí)效率仍然不高。2023年，李明祥［10］設(shè)計(jì)了一個(gè)層次型基于身份的多比特全同態(tài)加密方案，方案加密整數(shù)矩陣，支持整數(shù)矩陣加法和乘法同態(tài)運(yùn)算。Guimares等人［11］改進(jìn)了GSW方案，并提出了新的自舉算法，可以減少每個(gè)刷新消息的同態(tài)運(yùn)算次數(shù)，同時(shí)利用“收縮”操作，減少了密文的維數(shù)和密文模數(shù)，可以加快同態(tài)運(yùn)算。Bian等人［12］基于GSW方案提出了一個(gè)可公開驗(yàn)證性的完全同態(tài)分層簽密方案并在標(biāo)準(zhǔn)假設(shè)下證明了安全性和不可偽造性，利用更快的同態(tài)驗(yàn)證來減少驗(yàn)證數(shù)量。2024年，李莉等人［13］提出了一種基于不經(jīng)意多項(xiàng)式估值的SM4協(xié)同加解密方案，有效提高了在線計(jì)算階段的性能。Tu等人［14］將多密鑰全同態(tài)加密與身份基加密結(jié)合，構(gòu)造了基于多身份的全同態(tài)加密方案，可以實(shí)現(xiàn)對(duì)身份密文的同態(tài)運(yùn)算和靈活的訪問控制。上述方案旨在提高同態(tài)加密的性能，但密鑰尺寸較大且同態(tài)運(yùn)算噪聲增長快，導(dǎo)致計(jì)算效率低，其處理速度和效率難以滿足大量數(shù)據(jù)處理的需求。

現(xiàn)有方案在實(shí)際應(yīng)用中面臨著加密效率不高、噪聲增長速度過快以及公私鑰尺寸較大的問題。為了解決上述問題，提出了一種格上基于整數(shù)矩陣的安全多方計(jì)算同態(tài)加密方案（secure multi-party computation homomorphic encryption scheme based on integer matrix on lattice，MFHE）。本文基于GSW方案，其安全性基于兩個(gè)主要的數(shù)學(xué)難題：LWE問題和格上的困難問題，上述兩個(gè)問題被普遍認(rèn)為是能夠抵抗量子攻擊的難題。本文方案的主要貢獻(xiàn)可以概括為以下幾點(diǎn)：

a）明文存儲(chǔ)方面，本文方案采用了矩陣來存儲(chǔ)明文數(shù)據(jù)，相較于傳統(tǒng)的比特或向量存儲(chǔ)方式，矩陣存儲(chǔ)方法大幅擴(kuò)展了數(shù)據(jù)的存儲(chǔ)容量。這使得方案能夠更有效地處理大規(guī)模數(shù)據(jù)，滿足了現(xiàn)代互聯(lián)網(wǎng)環(huán)境中對(duì)高效數(shù)據(jù)處理的需求。

b）本文方案對(duì)公鑰及私鑰尺寸進(jìn)行了緊湊化處理，減小了密鑰尺寸，在處理相同數(shù)據(jù)量的情況下，相對(duì)于其他方案，能夠有效地減少加解密過程中的時(shí)間和計(jì)算開銷。

c）采用密文打包技術(shù)將多個(gè)明文信息打包至單一的密文之中，從而允許在加密數(shù)據(jù)上執(zhí)行復(fù)雜的同態(tài)操作。此外，還對(duì)自舉操作進(jìn)行改進(jìn)，以減少在執(zhí)行深層次同態(tài)運(yùn)算時(shí)的噪聲增長。

1 相關(guān)知識(shí)

1.1 符號(hào)

文中使用的符號(hào)如表1所示。

4 性能效率分析

4.1 理論分析

本節(jié)中對(duì)文獻(xiàn)［8～10］方案以及本文方案的參數(shù)進(jìn)行了比較分析，上述文獻(xiàn)均是針對(duì)明文矩陣進(jìn)行運(yùn)算的，在明文矩陣維度相同的前提下，可以更直觀地比較不同方案的差異。在同態(tài)加密的多種運(yùn)算中，乘法運(yùn)算的性能表現(xiàn)尤為關(guān)鍵，其通常涉及到更復(fù)雜的數(shù)學(xué)運(yùn)算和更高的計(jì)算成本，同態(tài)乘法運(yùn)算的擴(kuò)展速率顯著高于同態(tài)加法運(yùn)算，直接影響到加密數(shù)據(jù)的處理效率和計(jì)算資源的利用。

表2中展示了公鑰尺寸、私鑰尺寸、密文尺寸以及同態(tài)乘法運(yùn)算的噪聲擴(kuò)展率。

根據(jù)表2可知，對(duì)相同明文數(shù)據(jù)進(jìn)行加密時(shí)，本文方案在公鑰和私鑰的尺寸上具有明顯的優(yōu)勢(shì)，相較于其他方案，公鑰尺寸更小。這一特點(diǎn)不僅有助于減少存儲(chǔ)和傳輸?shù)拈_銷，而且對(duì)于提升系統(tǒng)的整體性能具有積極影響。此外，本文方案在計(jì)算效率方面也表現(xiàn)出色。特別是在同態(tài)乘法運(yùn)算時(shí)展現(xiàn)出較高的計(jì)算效率。在噪聲擴(kuò)展率方面，本文方案的乘法同態(tài)運(yùn)算的噪聲擴(kuò)展率低于文獻(xiàn)［8～10］，即在進(jìn)行加密計(jì)算時(shí)，本文方案能夠更有效地控制噪聲的增長，從而保證計(jì)算結(jié)果的準(zhǔn)確性和可靠性。本文方案的噪聲擴(kuò)展率與小整數(shù)k以及明文維數(shù)r有關(guān)，而與格的維數(shù)無關(guān)。這一點(diǎn)與文獻(xiàn)［8～10］的方案形成鮮明對(duì)比，后者的噪聲擴(kuò)展率與格的維數(shù)密切相關(guān)。因此，本文方案在設(shè)計(jì)上更為簡潔高效，減少了對(duì)計(jì)算資源的需求，同時(shí)降低了復(fù)雜性和潛在的性能瓶頸。

4.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)的硬件環(huán)境是主頻2.2 GHz，運(yùn)行內(nèi)存32 GB，13th Gen IntelCoreTM i9-13900HX處理器。操作系統(tǒng)為Windows 11_64位，編程語言為Python 3.8.10，主要使用Python中的基礎(chǔ)包Numpy庫進(jìn)行矩陣運(yùn)算。

為了全面評(píng)估本文方案的性能表現(xiàn)，進(jìn)行了一系列的實(shí)驗(yàn)驗(yàn)證，旨在對(duì)加密、解密以及同態(tài)乘法運(yùn)算的性能進(jìn)行分析。在實(shí)驗(yàn)部分，本文方案與文獻(xiàn)［8～10］進(jìn)行了對(duì)比分析，以驗(yàn)證其性能優(yōu)勢(shì)和實(shí)用性。實(shí)驗(yàn)參數(shù)設(shè)置q=230以及LWE參數(shù)n=30。為了避免實(shí)驗(yàn)結(jié)果偶然性，所有實(shí)驗(yàn)均進(jìn)行了100次，最后結(jié)果取平均值。實(shí)驗(yàn)結(jié)果如圖2、3所示。

圖2展示了在矩陣維度r=32的條件下，本文方案與文獻(xiàn)［8～10］中方案在加密和解密操作所需時(shí)間上的比較。根據(jù)圖2的數(shù)據(jù)可以觀察到，本文方案在執(zhí)行加密和解密運(yùn)算時(shí)所需的時(shí)間顯著低于文獻(xiàn)［8～10］中的方案。具體來說，在加密時(shí)間方面，與文獻(xiàn)［8～10］相比，本文方案分別實(shí)現(xiàn)了71.92%、66.97%和77.11%的減少；在解密時(shí)間方面，本方案相較于文獻(xiàn)［8～10］分別減少了41.06%、33.04%和63.35%的時(shí)間消耗。這一結(jié)果表明，本文方案在處理具有較大維度矩陣的加密與解密任務(wù)時(shí)具有顯著的性能優(yōu)勢(shì)。

圖3展示了在不同尺寸的明文矩陣下，本文方案與文獻(xiàn)［8～10］中提出的方案在執(zhí)行同態(tài)乘法操作時(shí)所需時(shí)間的比較。從圖3中可以觀察到，當(dāng)明文矩陣的尺寸較小時(shí)，兩種方案在同態(tài)乘法所需時(shí)間上的差異并不顯著。然而，隨著明文矩陣尺寸的增加，兩種方案在所需時(shí)間上的差異逐漸變得明顯，本文方案在同態(tài)乘法操作中的時(shí)間增長趨勢(shì)相對(duì)文獻(xiàn)［8～10］更為平緩。這一結(jié)果表明，隨著處理數(shù)據(jù)量的增加，本文方案在執(zhí)行同態(tài)乘法運(yùn)算時(shí)能夠提供更優(yōu)的性能表現(xiàn)。

5 結(jié)束語

本文方案不僅能夠有效地保護(hù)數(shù)據(jù)隱私，還能在互聯(lián)網(wǎng)環(huán)境中實(shí)現(xiàn)大規(guī)模數(shù)據(jù)的安全多方計(jì)算。通過將整數(shù)矩陣加密為密文矩陣，并在密文上進(jìn)行同態(tài)加法和乘法運(yùn)算，顯著提高了執(zhí)行時(shí)間，并減少了計(jì)算復(fù)雜性，使用密文打包以及自舉技術(shù)實(shí)現(xiàn)了全同態(tài)加密。此外，還對(duì)方案的正確性和安全性進(jìn)行了嚴(yán)格的分析，并通過實(shí)驗(yàn)驗(yàn)證了其在處理數(shù)據(jù)時(shí)的高效性。全同態(tài)加密技術(shù)仍然處于快速發(fā)展階段，未來的研究需要繼續(xù)關(guān)注性能優(yōu)化、安全性增強(qiáng)以及更廣泛應(yīng)用場景的適應(yīng)性。

參考文獻(xiàn)：

［1］Aharonov D，Regev O.Lattice problems in NP∩ coNP［J］.Journal of the ACM，2005，52（5）：749-765.

［2］Gentry C，Sahai A，Waters B.Homomorphic encryption from learning with errors：conceptually-simpler，asymptotically-faster，attribute-based［C］//Proc of the 33rd Annual Cryptology Conference.Berlin：Springer，2013：75-92.

［3］Xu Peiying，Wang Liping.Multi-key homomorphic secret sharing from LWE without multi-key HE［C］//Proc of Australasian Conference on Information Security and Privacy.Cham：Springer，2023：248-269.

［4］Biswas C，Dutta R.Secure and efficient multi-key FHE scheme supporting multi-bit messages from LWE preserving non-interactive decryption［J］.Journal of Ambient Intelligence and Humanized Computing，2023，14（12）：16451-16464.

［5］Fan Huifeng，Huang Ruwei，Luo Fengting.Efficient multi-identity full homomorphic encryption scheme on lattice［J］.Applied Sciences，2023，13（10）：6343.

［6］Zeng Shuchang，Hsu C，Cui Jianqun，et al.Efficient dynamic multi-key FHE scheme from LWE for untrusted cloud environments［C］//Proc of the 29th IEEE International Conference on Parallel and Distributed Systems.Piscataway，NJ：IEEE Press，2023：1039-1044.

［7］Zhao Jianan，Huang Ruwei，Yang Bo.Efficient GSW-style fully homomorphic encryption over the integers［J］.Security and Communication Networks，2021，2021（1）：8823787.

［8］Bai Yanan，Liu Quanliang，Wu Wenyuan，et al.cuSCNN：a secure and batch-processing framework for privacy-preserving convolutional neural network prediction on GPU［J］.Frontiers in Computational Neuroscience，2021，15：799977.

［9］Zhao Liang，Chen Ze，Chen Liqun，et al.An optimized GHV-type HE scheme：simpler，faster，and more versatile［C］//Proc of International Conference on Applied Cryptography and Network Security.Cham：Springer，2022：45-64.

［10］李明祥.基于身份的整數(shù)矩陣全同態(tài)加密方案［J］.計(jì)算機(jī)科學(xué)與應(yīng)用，2023，13（9）：1675-1690.（Li Mingxiang.Identity-based integer matrix fully homomorphic encryption scheme［J］.Computer Science and Application，2023，13（9）：1675-1690.）

［11］Guimares A，Pereira H V L，Van Leeuwen B.Amortized bootstrapping revisited：simpler，asymptotically-faster，implemented［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security.Singapore：Springer，2023：3-35.

［12］Bian Zhaoxuan，Wang Fuqun，Zhang Renjun，et al.A publicly verifiable leveled fully homomorphic signcryption scheme［J］.IET Information Security，2023，2023（1）：1377042.

［13］李莉，宣佳錚，高尚，等.基于不經(jīng)意多項(xiàng)式估值的SM4協(xié)同加解密方案［J］.計(jì)算機(jī)應(yīng)用研究，2024，41（6）：1862-1868.（Li Li，Xuan Jiazheng，Gao Shang，et al.SM4 collaborative encryption and decryption scheme based on oblivious polynomial evaluation［J］.Application Research of Computers，2024，41（6）：1862-1868.）

［14］Tu Guangsheng，Liu Wenchao，Zhou Tanping，et al.Concise and efficient multi-identity fully homomorphic encryption scheme［J］.IEEE Access，2024，12：49640-49652.

［15］Dttling N，Kolonelos D，Lai R W，et al.Efficient laconic cryptography from learning with errors［C］//Proc of Annual International Confe-rence on the Theory and Applications of Cryptographic Techniques.Cham：Springer，2023：417-446.

［16］Yamaguchi J，Shimizu T，F(xiàn)urukawa K，et al.Annealing-based algorithm for solving CVP and SVP［J］.Journal of the Operations Research Society of Japan，2022，65（3）：121-137.

［17］Jiang Bingbing.Multi-key FHE without ciphertext-expansion in two-server model［J］.Frontiers of Computer Science，2021，16（1）：161809.

［18］Chen Yuyue，Huang Ruwei，Yang Bo.Efficient batch fully homomorphic encryption with a shorter key from ring-LWE［J］.Applied Sciences，2022，12（17）：8420.

［19］Zhao Xiufeng，Mao Hefeng，Liu Shuai，et al.Analysis on matrix GSW-FHE and optimizing bootstrapping［J］.Security and Communication Networks，2018，2018（1）：6362010.

［20］Xiang Guangli，Shao Can.Low noise homomorphic encryption scheme supporting multi-bit encryption［C］//Proc of the 2nd International Conference on Computer Communication and Network Security.Pisca-taway，NJ：IEEE Press，2021：150-156.