Private Outsourcing of Polynomial Evaluation and Matrix Multiplication using Multilinear Maps
This work addresses the need for secure and efficient computation outsourcing in scenarios where client data and functions must remain confidential, representing an incremental improvement in privacy-preserving verifiable computation.
The paper tackles the problem of privately outsourcing polynomial evaluation and matrix multiplication to an untrusted server, achieving both input and function privacy using multilinear maps, with applications to private information retrieval.
{\em Verifiable computation} (VC) allows a computationally weak client to outsource the evaluation of a function on many inputs to a powerful but untrusted server. The client invests a large amount of off-line computation and gives an encoding of its function to the server. The server returns both an evaluation of the function on the client's input and a proof such that the client can verify the evaluation using substantially less effort than doing the evaluation on its own. We consider how to privately outsource computations using {\em privacy preserving} VC schemes whose executions reveal no information on the client's input or function to the server. We construct VC schemes with {\em input privacy} for univariate polynomial evaluation and matrix multiplication and then extend them such that the {\em function privacy} is also achieved. Our tool is the recently developed {mutilinear maps}. The proposed VC schemes can be used in outsourcing {private information retrieval (PIR)}.