Publicly Verifiable Computation of Polynomials Over Outsourced Data With Multiple Sources

Among all types of computations, the polynomial function evaluation is a fundamental, yet an important one due to its wide usage in the engineering and scientific problems. In this paper, we investigate publicly verifiable outsourced computation for polynomial evaluation with the support of multiple data sources. Our proposed verification scheme is universally applicable to all types of polynomial computations and allows the clients to outsource new data at any time. While the existing solutions only support the verification for polynomial evaluation over a single data source, i.e., all the inputs of the polynomial function are outsourced and signed by a single entity, our solution supports polynomial evaluations over multiple different data sources, which are more common and have wider applications, e.g., to assess the city air pollution, one needs to evaluate the environmental data uploaded from the multiple environmental monitor sites. In our proposed scheme, the verification cost for the client is independent with either the input size or the polynomial size so that it scales well in practice. We formally prove the correctness and soundness of our scheme and conduct numerical analysis and evaluation study to validate its high efficiency and scalability. The experimental results show that the data contributor signing 1000 new data only takes 2.1 s, and the verification of the delegated polynomial function takes only 22 ms, which is practically efficient for the real-world applications.