Verifiable Homomorphic Secret Sharing for SIMD Operations

Outsourced computation poses security challenges in terms of data privacy and computation integrity. A general solution for data privacy in outsourced computation is fully homomorphic encryption (FHE). However, current implementations of FHE still suffer from high overhead. Homomorphic secret sharing (HSS) is an alternative approach for ensuring data privacy with reduced overhead. HSS is the secret sharing analogue of homomorphic encryption, where homomorphic evaluation can be distributed among remote servers without interaction. The partial results from each server can be used to reconstruct the computation result. On the downside, neither FHE nor HSS guarantees computation integrity in outsourced computation scenarios. To address this issue, verifiable homomorphic secret sharing (VHSS) schemes have been proposed to check the correctness of reconstructed computation results from servers. However, existing VHSS schemes for polynomials only verify if the servers perform the same function rather than the 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.In this work, we present a two-server VHSS scheme for single-instruction multiple data (SIMD) parallel computations. The proposed scheme allows users to verify the computation correctness of specified functions. In particular, both non-colluding servers can be malicious in our security model. Moreover, our scheme supports amortized verification on the client side, enabling the precomputation of reusable values for verification of the same program/function. On the server side, our scheme does not introduce additional costs during computation. Furthermore, we give the extension of our construction against what we call chosen-slot attack which is more difficult to prevent.