The combination of software-as-a-service and the increasing use of mobile devices gives rise to a considerable difference in computational power between servers and clients. Thus, there is a desire for clients to outsource the evaluation of complex functions to a server and to be able to verify that the resulting value is correct. Previous work in this area of Publicly Verifiable Outsourced Computation (PVC) requires a costly pre-processing stage. However, in many practical situations multiple clients will be interested in the same set of core functions and will make use of the same servers. Thus, the pre-processing phase may be performed many more times than is necessary. In this paper we introduce a Key Distribution Center (KDC) that handles the generation and distribution of the keys that are required to support PVC, thereby eliminating this redundancy. We define a number of new security models and functionalities that arise with the introduction of the KDC, and present a construction of such a scheme built upon Key-Policy Attribute-based Encryption.