Cloud computing is an important trend that in many ways is beginning to fulfill the early promise of the Internet and creating unanticipated change in computing paradigm. As promising as cloud computing is, this paradigm brings forth new security and privacy challenges when operating in the untrusted cloud scenarios. Motivated by the challenging problem “Private Searching over Encrypted Data”, we propose a new cryptographic primitive, Proxy Re-encryption with Private Searching (PRPS for short). The PRPS scheme enables the data users and owners efficiently query and access files stored in untrusted cloud, while keeping query privacy and data privacy from the cloud providers. The concrete construction is based on proxy re-encryption, public key encryption with keyword search and the dual receiver cryptosystem. Extensive analysis shows that our scheme is efficient and semantically secure under the BDH assumption.