VeHSS: Two-server Verifiable Homomorphic Secret Sharing Leveraging SIMD Operations
Authors:
Open Access
- 1 January 2025
- journal article
- Published by Information Processing Society of Japan in Journal of Information Processing
- Vol. 33, 583-593
Abstract
Outsourced computation poses challenges in data privacy and computation integrity. Fully homomorphic encryption (FHE) ensures data privacy but incurs high computational overhead. Homomorphic secret sharing (HSS), an alternative with reduced overhead, enables homomorphic evaluations to be distributed across remote servers without interaction. On the downside, neither FHE nor HSS guarantees computation integrity. To address this issue, verifiable homomorphic secret sharing (VHSS) schemes have been proposed to verify computation correctness. However, existing VHSS schemes for polynomials only verify whether the servers perform the same function rather than the intended specified function, and implicitly assume that at least one server is honest. Moreover, the costs of generating verification information are the same as or even more than re-executing the computation. We propose a two-server VHSS scheme leveraging single-instruction multiple data (SIMD) parallel computations. Our scheme verifies computation correctness for specified functions even when both non-colluding servers are malicious under our security model. Moreover, it supports amortized verification on the client side by enabling the precomputation of reusable values for verification, while introducing no additional computational costs on servers. As a byproduct, we also discuss how our method can be applied to FHE to mitigate recent attacks targeting decryption keys.Keywords
This publication has 30 references indexed in Scilit:
- Homomorphic Secret Sharing with Verifiable Evaluation2024
- On the Practical $\text {CPA}^{D}$ Security of “exact” and Threshold FHE Schemes and Libraries2024
- An Algebraic Framework for Silent Preprocessing with Trustless Setup and Active Security2022
- Large Message Homomorphic Secret Sharing from DCR and Applications2021
- The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT2021
- Constructive t-secure Homomorphic Secret Sharing for Low Degree Polynomials2020
- Two-Server Verifiable Homomorphic Secret Sharing for High-Degree Polynomials2020
- Sum It Up: Verifiable Additive Homomorphic Secret Sharing2020
- Homomorphic Secret Sharing from Lattices Without FHE2019
- Verifiable Homomorphic Secret Sharing2018