Verifiable Homomorphic Secret Sharing for Low Degree Polynomials

doi:10.1109/TDSC.2022.3194321

	Verifiable Homomorphic Secret Sharing for Low Degree Polynomials
	Xin Chen; Liang Feng Zhang; Jing Liu
	2022
发表期刊	IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING (IF:7.0[JCR-2023],6.8[5-Year])
ISSN	1545-5971
EISSN	1941-0018
卷号	20 期号:4 页码:2882-2895
发表状态	已发表
DOI	10.1109/TDSC.2022.3194321
摘要	An (n, m, t)-homomorphic secret sharing (HSS) scheme for a function family F allows n clients to share their data x1, ... , xn among m servers and then distribute the computation of any function f E F to the servers such that: (i) any t colluding servers learn no information about the data; (ii) each server is able to compute a partial result and f(x1, ... , xn) can be reconstructed from the servers' partial results. HSS schemes cannot guarantee correct reconstruction, if some servers are malicious and provide wrong partial results. Recently, verifiable HSS (VHSS) has been introduced to achieve an additional property: (iii) any t colluding servers cannot persuade the client(s) to accept their partial results and reconstruct a wrong value. The property (iii) is usually achieved by the client verifying the servers' partial results. A VHSS scheme is compact if the verification is substantially faster than locally computing f(x1, ... , xn). Of the existing VHSS schemes for polynomials, some are not compact; the others are compact but impose very heavy workload on the servers, even for low degree polynomials (e.g., they are at least 4000x slower than the existing HSS schemes in order to evaluate polynomials of degree < 5, which have many applications such as privacy-preserving machine learning). In this paper, we propose both a single-client VHSS (SVHSS) model and a multi-client VHSS (MVHSS) model. Our SVHSS allows a client to use a secret key to share its data among servers; our MVHSS allows multiple clients to share their data with a public key. For any integers m, t > 0, we constructed both an (m, t)-SVHSS scheme and an (m, t)-MVHSS scheme that satisfy the properties of (i)-(iii). Our constructions are based on level -k homomorphic encryptions. The (m, t)-SVHSS and (m, t)-MVHSS are compact and allow the computations of degree d polynomials ford < ((k + 1)m 1)/t and d < ((k + 1)(m t) 1)/t, respectively. Experiments show that our schemes are much more efficient than the existing compact VHSS for low degree polynomials. For example, to compute polynomials of degree = 5, our MVHSS scheme is at least 420x faster. By applying SVHSS and MVHSS, we may add verifiability to privacy-preserving machine learning (PPML) algorithms. Experiments show that the resulting schemes are at least 52x and 20x faster than the existing verifiable PPML schemes.
关键词	Servers Cryptography Genomics Bioinformatics Computational modeling Data models Data privacy Homomorphic secret sharing verifiability homomorphic encryption privacy
URL	查看原文
收录类别	EI ; SCI
语种	英语
资助项目	Natural Science Foundation of Shanghai[21ZR1443000] ; Singapore Ministry of Education[RG12/19]
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Information Systems ; Computer Science, Software Engineering
WOS记录号	WOS:001029054600015
出版者	IEEE COMPUTER SOC
EI入藏号	20223312569220
EI主题词	Genome
EI分类号	461.8.2 Bioinformatics ; 721.1 Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory ; 723.2 Data Processing and Image Processing ; 801.3 Colloid Chemistry ; 921 Mathematics
原始文献类型	Journal article (JA)
来源库	IEEE
引用统计	正在获取...
文献类型	期刊论文
条目标识符	https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/242774
专题	信息科学与技术学院信息科学与技术学院_PI研究组_张良峰组信息科学与技术学院_硕士生信息科学与技术学院_博士生
作者单位	School of Information Science and Technology, ShanghaiTech University, Shanghai, China
第一作者单位	信息科学与技术学院
第一作者的第一单位	信息科学与技术学院
推荐引用方式 GB/T 7714	Xin Chen,Liang Feng Zhang,Jing Liu. Verifiable Homomorphic Secret Sharing for Low Degree Polynomials[J]. IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,2022,20(4):2882-2895.
APA	Xin Chen,Liang Feng Zhang,&Jing Liu.(2022).Verifiable Homomorphic Secret Sharing for Low Degree Polynomials.IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING,20(4),2882-2895.
MLA	Xin Chen,et al."Verifiable Homomorphic Secret Sharing for Low Degree Polynomials".IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING 20.4(2022):2882-2895.