Sparse Matrix Masking-Based Non-Interactive Verifiable (Outsourced) Computation, Revisited

Abstract

A Privacy-preserving Verifiable (outsourced) Computation (PVC) protocol enables a resource-constrained client to outsource expensive and sensitive workloads to computationally powerful but possibly untrusted service providers (called workers) and to verify the correctness of the results. In a PVC protocol, the inputs and outputs of the computation are hidden, so that the worker is unable to determine them. This is referred to as the privacy property. A Non-interactive PVC (NPVC) protocol is a PVC protocol without communications between a client and worker, apart from distributing the workloads and results. In the literature, Sparse Matrices (SMs) have been used in NPVC protocols to efficiently hide the inputs and outputs from the worker. However, to the best of our knowledge, how the low density of an SM affects privacy in such NPVC protocols has not been formally analyzed. In this work, we first propose a formal definition of the privacy property of an NPVC protocol with respect to matrix density. We use this definition to demonstrate that all of the SM masking-based NPVC protocols that we know of do not hold this privacy property under the ciphertext-only attack model. We then propose an SM masking construction to modify two of those protocols, chosen because they are state-of-the-art, and prove that the modified protocols hold the privacy property under the chosen-plaintext attack model. Our modifications do not require the client operating matrix inversion, and they are able to keep the same level of high performance and all other properties as the originals.