Multi-key homomorphic MACs (MKHomMACs) allow multiple clients to authenticate data with their own secret keys and outsource their data together with the tags to an untrusted server. Upon receiving any user 's request of computing a function on the data, the server is able to generate both the computation result and a short tag that vouches for the correctness of the result. MKHomMACs provide a solution with minimal communication and interaction to the problem of delegating computations over outsourced data. Fiore, Mitrokotsa, Nizzardo, and Pagnin (Asiacrypt 2016) constructed a PRF-based MKHomMAC where the result verification could be as costly as the delegated computation. In this paper, we show a PRF-based MKHomMAC for quadratic arithmetic circuits such that the verification can be substantially faster than the delegated computation in an amortized setting. The efficiency improvement is achieved by using PRFs with multi-key amortized closed-form efficiency.

Choi, Katz, Kumaresan, and Cid put forward the conception of multiclient noninteractive verifiable computation (MVC), enabling a group of clients to outsource computation of a function of f . CKKC’s MVC is impractical due to their dependence on fully homomorphic encryption (FHE) and garbled circuits (GCs). In this paper, with the goal of satisfying practical requirements, a general transform is presented from the homomorphic proxy re-authenticator (HPRA) of Deler, Ramacher, and Slamanig to MVC schemes. MVC constructions in this particular study tend to be more efficient once the underlying HPRA avoids introducing FHE and GCs. By deploying the transform to DRS’s HPRA scheme, a specific MVC scheme for calculating the linear combinations of vectors has been proposed. It can be understood that it is the first feasible and implementable MVC scheme so far, and the instantiation solution has a great advantage in efficiency compared with related works.

Verifiable computation (VC) allows a client to outsource (delegate) the computation of a function f on an input x to a server and then verify the server's results with substantially less time than computing f ( x ) from scratch. The security of VC requires no efficient adversary can persuade the client to accept any wrong results. Morillo and Obrador (PST 2013) proposed three VC schemes for outsourcing the computation of polynomial functions and claimed that all schemes are secure under the decisional subgroup membership assumption. The authors show a simple attack against the security of their first scheme and then extend the attack to the other two schemes. Morillo and Obrador (PST 2013) also claimed that their third scheme keeps the client's input private under the square root assumption. The authors show that this is not true under the standard definition of input privacy. In particular, a curious server can extract the client's input x , if the x is not too large. The authors’ results show that Morillo–Obrador schemes cannot be used in the polynomial delegation.