基于矩陣的安全多方計算同態加密方案

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

關鍵詞：同態加密；矩陣運算；安全多方計算；數據隱私；格

中圖分類號：TP309.7"" 文獻標志碼：A"" 文章編號：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，Fuxin 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 引言

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

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

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

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

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

a）明文存儲方面，本文方案采用了矩陣來存儲明文數據，相較于傳統的比特或向量存儲方式，矩陣存儲方法大幅擴展了數據的存儲容量。這使得方案能夠更有效地處理大規模數據，滿足了現代互聯網環境中對高效數據處理的需求。

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

c）采用密文打包技術將多個明文信息打包至單一的密文之中，從而允許在加密數據上執行復雜的同態操作。此外，還對自舉操作進行改進，以減少在執行深層次同態運算時的噪聲增長。

1 相關知識

1.1 符號

文中使用的符號如表1所示。

4 性能效率分析

4.1 理論分析

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

表2中展示了公鑰尺寸、私鑰尺寸、密文尺寸以及同態乘法運算的噪聲擴展率。

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

4.2 實驗分析

實驗的硬件環境是主頻2.2 GHz，運行內存32 GB，13th Gen IntelCoreTM i9-13900HX處理器。操作系統為Windows 11_64位，編程語言為Python 3.8.10，主要使用Python中的基礎包Numpy庫進行矩陣運算。

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

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

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

5 結束語

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

參考文獻：

［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］李明祥.基于身份的整數矩陣全同態加密方案［J］.計算機科學與應用，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］李莉，宣佳錚，高尚，等.基于不經意多項式估值的SM4協同加解密方案［J］.計算機應用研究，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，Furukawa 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.