Two-Server Verifiable Homomorphic Secret Sharing for High-Degree Polynomials

Xin Chen, Liang Feng ZhangLecture Notes in Computer Science 2020 · DOI · arXiv · OpenAlex

Abstract

This paper introduces a novel cryptographic framework for Two-Server Verifiable Homomorphic Secret Sharing (2SVHSS). The scheme enables users to outsource the computation of high-degree polynomials to two non-colluding servers while ensuring both data privacy and result integrity. By utilizing Public-Key Encryption with Nearly Linear Decryption (PKE-NLD) and a lightweight verification mechanism, the proposed method achieves significant performance improvements over existing state-of-the-art solutions, offering speeds 3–10 times faster for server-side evaluation and up to 54 times faster for client-side reconstruction.

Introduction

As data processing increasingly moves to the cloud, clients face two primary challenges: privacy and integrity. While Fully Homomorphic Encryption (FHE) addresses privacy by allowing computation on encrypted data, its high computational overhead often makes it impractical. Homomorphic Secret Sharing (HSS) offers a more efficient alternative by splitting data across multiple servers. However, existing HSS schemes for complex, high-degree polynomials—essential for deep learning and advanced analytics—typically struggle to provide verifiability without requiring a large number of servers or sacrificing performance. This paper addresses this gap by providing a verifiable, two-server solution for polynomials of nearly any degree.

Comparison with Prior Work

Previous research in homomorphic secret sharing has often faced trade-offs between the number of servers required, the degree of polynomials supported, and the ability to verify results. As shown in the comparison below, the proposed 2SVHSS scheme is unique in its ability to support high-degree polynomials ($poly(\lambda)$) with only two servers while maintaining semantic security, verifiability, context hiding, and compactness.

Comparison of the proposed 2SVHSS scheme with existing homomorphic secret sharing and verifiable schemes.

Methodology

The construction is built upon Public-Key Encryption with Nearly Linear Decryption (PKE-NLD). The authors introduce several technical innovations to achieve efficient verifiability:

  • Additive Key Splitting: The secret key is divided into evaluation keys for two non-colluding servers, each performing local computations on their respective data shares.
  • Efficient Verifiability: A verification key ($vk$), derived from a random value ($\hat{s}$) and the secret key ($s$), is split between servers.
  • Lightweight Check: Instead of heavy decryption, the client verifies the result using a simple algebraic equation: $\tau = \hat{s} \cdot y$. This check involves only basic ring operations, making it ideal for resource-constrained devices like IoT sensors.
  • Subroutine Architecture: The process is modularized into six subroutines (Load, Add1, Add2, cMult, Mult, Output) that handle the homomorphic evaluation of polynomials.

Experimental Evaluation

The scheme was evaluated using synthetic polynomial benchmarks for degrees $d \in \{5, 7, 9, 11\}$. The implementation utilized the GMP and FLINT libraries for large integer arithmetic and OpenSSL for pseudorandom functions.

Key Results

When compared against the LMS scheme (the previous state-of-the-art for high-degree polynomials), the 2SVHSS scheme demonstrated superior performance:

  • Server-Side Speedup: For degree-7 polynomials, the new scheme is significantly faster. The advantage grows exponentially with the degree, as LMS complexity scales at $2^{d-1}$ while 2SVHSS remains stable.
  • Client-Side Efficiency: For degree-5 polynomials, 2SVHSS is approximately 54 times faster than LMS during reconstruction and verification. At degree-11, 2SVHSS requires only 0.0024 seconds, compared to 2.134 seconds for LMS.
  • Compactness: The client's workload remains low and independent of the polynomial's complexity, ensuring practical utility for outsourcing tasks.

Conclusion and Future Work

The 2SVHSS scheme provides a robust and efficient solution for verifiable outsourced computation. While it relies on a non-collusion assumption between the two servers, it offers unprecedented performance for high-degree polynomial evaluation. Future research may focus on extending this verifiability to more general branching programs or arbitrary circuits and further optimizing communication overhead for bandwidth-constrained environments.

Summary updated

BibTeX
@inproceedings{chen2020two,
  author = {Xin Chen and Liang Feng Zhang},
  title = {{Two-Server Verifiable Homomorphic Secret Sharing for High-Degree Polynomials}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2020},
  doi = {10.1007/978-3-030-62974-8\_5},
}
Figure