Publicly Verifiable Multi-server Homomorphic Secret Sharing

Outsourced computation requires both data confidentiality and computation integrity. While fully homomorphic encryption (FHE) ensures strong confidentiality guarantees, it suffers from substantial computational and storage overhead. Homomorphic secret sharing (HSS) has emerged as a more efficient alternative to FHE, enabling multiple non-interacting servers to locally evaluate a function on their shares. To ensure computation integrity, verifiable homomorphic secret sharing (VHSS) has been proposed. However, most existing VHSS schemes support only private verification, where only the data owner can verify the result. This limits their applicability in scenarios where the result must be trusted by external parties. Publicly verifiable HSS (PVHSS) addresses this limitation by enabling anyone to verify the computation correctness with a public key. However, existing PVHSS schemes for polynomial functions incur high verification overhead. In this work, we propose a new PVHSS scheme for polynomial functions, building upon the HSS scheme of Dao et al. (CRYPTO’23). Our scheme enables any third party to verify whether multiple non-interacting servers have correctly evaluated the function. Moreover, our construction ensures that any set of up to t servers learn nothing about the outsourced data and cannot generate an incorrect computation result. Compared to existing PVHSS schemes for polynomials, our approach achieves smaller share sizes and lower verification costs.