In this paper, we propose a new efficient privacy preserving outsourced computation framework over public data, called EPOC. EPOC allows a user to outsource the computation of a function over multi-dimensional public data to the cloud while protecting the privacy of the function and its output. Specifically, we introduce three types of EPOC in order to tradeoff different levels of privacy protection and performance. We present a new cryptosystem called Switchable Homomorphic Encryption with Partial Decryption (SHED) as the core cryptographic primitive for EPOC.We introduce two coding techniques, called message pre-coding and message extending and coding respectively, for messages encrypted under a composite order group. Furthermore, we propose a Secure Exponent Calculation Protocol with Public Base (SEPB), which serves as the core subprotocol in EPOC. Detailed security analysis shows that the proposed EPOC achieves the goal of outsourcing computation of a private function over public data without privacy leakage to unauthorized parties. In addition, performance evaluations via extensive simulations demonstrate that EPOC is efficient in both computation and communications.