Privacy-preserving verifiable delegation of polynomial and matrix functions

Journal of mathematical cryptology

article

Liang Feng Zhang¹  Reihaneh Safavi-Naini² 

[1] School of Information Science and Technology, ShanghaiTech University;Department of Computer Science, University of Calgary

关键词: Cloud computing;    outsourcing computation;    verifiable computation;    privacy preserving;    polynomials;    matrices;   

DOI  :  10.1515/jmc-2018-0039

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

Outsourcing computation has gained significant popularity in recent years due to the development of cloud computing and mobile services. In a basic outsourcing model, a client delegates computation of a function f on an input x to a server. There are two main security requirements in this setting: guaranteeing the server performs the computation correctly, and protecting the client’s input (and hence the function value) from the server. The verifiable computation model of Gennaro, Gentry and Parno achieves the above requirements, but the resulting schemes lack efficiency. This is due to the use of computationally expensive primitives such as fully homomorphic encryption (FHE) and garbled circuits, and the need to represent f as a Boolean circuit. Also, the security model does not allow verification queries, which implies the server cannot learn if the client accepts the computation result. This is a weak security model that does not match many real life scenarios. In this paper, we construct efficient (i.e., without using FHE, garbled circuits and Boolean circuit representations) verifiable computation schemes that provide privacy for the client’s input, and prove their security in a strong model that allows verification queries. We first propose a transformation that provides input privacy for a number of existing schemes for verifiable delegation of multivariate polynomial f over a finite field. Our transformation is based on noisy encoding of x and keeps x semantically secure under the noisy curve reconstruction (CR) assumption. We then propose a construction for verifiable delegation of matrix-vector multiplication, where the delegated function f is a matrix and the input to the function is a vector. The scheme uses PRFs with amortized closed-form efficiency and achieves high efficiency. We outline applications of our results to outsourced two-party protocols.

【 授权许可】

CC BY|CC BY-NC-ND