Authentication of function queries

Abstract

Consider a database where each record represents a math function. A third party is in charge of processing queries over this database and we want to provide a mechanism for users to verify the correctness of their query results. Here each query, referred to as a Function Query (FQ), retrieves the functions whose computation results with user-supplied arguments satisfy certain conditions (e.g., within a certain range). We present authentication solutions that work on a variety of functions, including univariate linear function, multivariate linear function, and multivariate high degree function. Our solutions are based on the fact that the functions can be sorted in the subdomains defined by their intersections and thus can be chained to produce a signature mesh for query result verification. We study the performance of the proposed techniques through theoretical analysis, simulation and empirical study, and include the results in this paper.