Publicly Verifiable Delegation Of Set Operations

Delegation of set operations has great significance on theoretical research and applications. With computer technology towards the development of a multipolar direction, computing resources distribute increasingly uneven, but delegation of computation technology can make computing resources distribution more reasonable and more flexible. A lot of problems in the real life can be summed up in set operations, so it is particularly important to study the delegation of set operations.Current studies about delegation of set operations generally consider to represent calculation as Boolean or arithmetic circuits. This conversion not only brought huge extra overhead, but also lead to low calculation and verification efficiency. In addition, the existing schemes did not meet the requirements of dynamic updating and publicly verifiable which are very important in the data query. In this paper, we have the following research results for solving these problems.i. In this paper, we take characteristic polynomial as the representation of set collection. Because there exists homomorphic properities between polynomial and set. In addition, the cost for a characteristic polynomial of set representation is relatively low.ii. This paper introduces the concept of closed form efficient pseudorandom function. Based on the linear assumption, we design a pseudorandom function. This pseudorandom function can effectively deal with the polynomial evaluation function. The closed form efficiency makes the authentication complexity at client side independent of the calculation at server and the size of outsourcing set collection.iii. Before outsourcing data set to the server, we allow the client to perform precomputation in polynomial time and save some validation status for the authentication. When the server proposes a updating query, the client will also update its own authentication status. Because the validation status can be public, the proof for the correctness and completeness of computation at server is publicly verifiable.iv. To solve the problem of set operations including set intersection, set union, set difference over outsourced data, we respectively design publicly verifiable delegation schemes. Then we show the correctness and security of these schemes through theoretical proof. By comparing the compution complexity at server, and the authentication complexity at client, as well as the transmission complexity between them with previous solutions, we fully proved that the efficiency of each scheme is optimal. At the same time, we illustrate the specific application of these schemes in real life. Specially, we introduce homomorphic encryption mechanism for protecting the privacy of client’s set collection, and apply this technology in the delegation of set difference. The experimental data shows the practical feasibility of the design.