密码学报（中英文）2026，Vol.13Issue(4)：689-708,20.DOI:10.13868/j.cnki.jcr.000873
高效可扩展的多密钥同态秘密分享协议
Efficient and Scalable Multi-Key Homomorphic Secret Sharing Protocol
摘要
Abstract
Homomorphic secret sharing is a data privacy protection technology that enables partic-ipants to share private data among computing servers and collaboratively compute public functions without relying on fully homomorphic encryption.However,existing homomorphic secret sharing schemes capable of handling multi-source data face significant limitations:some can only evaluate polynomials whose degrees are constrained by the number of participants,while others rely on com-plex multi-key homomorphic encryption technologies,leading to low efficiency and poor scalability.To address these issues,this paper proposes an efficient and scalable multi-key homomorphic secret sharing scheme based on the formal concept of multi-key homomorphic secret sharing introduced by Xu et al.,combined with the learning with errors problem,which can compute securely restricted multiplication straight-line programs on private data from multiple independent sources with server assistance.This scheme abandons the traditional reliance on multi-key fully homomorphic encryption and employs homomorphic linear combination techniques to securely compute restricted multiplication straight-line programs on private data from multiple independent sources with server assistance.In terms of security,this paper provides rigorous security proofs to ensure the scheme's security under standard security assumptions.This scheme does not rely on the traditional multi-key fully homomor-phic encryption.By constructing an encryption scheme ERegev,the ciphertext matrix is reduced from Zd×2lq to Zd×2q,significantly improving the encryption efficiency;pre-computation is carried out at the client side to reduce the communication volume.In terms of security,based on the LWE assumption,this paper provides a strict security proof under the semi-honest adversary model.Performance-wise,experimental results demonstrate that compared to Xu et al.'s scheme,our scheme reduces communica-tion overhead by over 90%and improves the execution efficiency of Server-side algorithm by an average of more than 4 times,and the execution of the client-side algorithm has achieved an improvement in efficiency by two orders of magnitude,significantly optimizing resource consumption and computa-tional efficiency.This work offers a more efficient and practical solution for multi-source data privacy computing scenarios.关键词
隐私保护/同态秘密分享/容错学习问题/同态线性组合/受限乘法直线程序Key words
privacy preservation/homomorphic secret sharing/learning with errors/homomorphic linear combination/restricted multiplicative linear programs分类
信息技术与安全科学引用本文复制引用
张明广,黄豪杰,刘亮,张书卿,高莹..高效可扩展的多密钥同态秘密分享协议[J].密码学报（中英文）,2026,13(4):689-708,20.基金项目
国家自然科学基金专项项目(12441101)Special Program of National Natural Science Foundation of China(12441101) （12441101）
