Point-of-interest (POI) recommendation has attracted many interests recently because of its significant potential for helping users to explore new places and helping location-based service (LBS) providers to carry out precision marketing. Compared with the user-item rating matrix in conventional recommender systems, the user-location check-in matrix in POI recommendation is usually much more sparse, which makes the notorious cold start problem more prominent in POI recommendation. Trust-oriented recommendation is an effective way to deal with this problem but it requires that the recommender has access to user check-in and trust data. In practice, however, these data are usually owned by different businesses who are not willing to share their data with the recommender mainly due to privacy and legal concerns. In this paper, we propose a privacy-preserving framework to boost data owners willingness to share their data with untrustworthy businesses. More specifically, we utilize partially homomorphic encryption to design two protocols for privacy-preserving trust-oriented POI recommendation. By offline encryption and parallel computing, these protocols can efficiently protect the private data of every party involved in the recommendation. We prove that the proposed protocols are secure against semi-honest adversaries. Experiments on both synthetic data and real data show that our protocols can achieve privacy-preserving with acceptable computation and communication cost.