Tensor decompositions are very powerful tools for analyzing multi-dimensional multi-modal data. Particularly, CP tensor decomposition is one of the most fundamental tensor decomposition models. However, it is usually computationally expensive to conduct CP tensor decompositions on a large-scale tensor by common algorithms like alternative least squares (ALS). To address this issue, one widely recognized solution is to adopt cloud computing. However, this raises privacy concerns due to the private information carried by a tensor. Previous algorithms for privacy-preserving outsourcing of tensor decompositions and other related computations require heavy communication cost. In this paper, we first develop an efficient tensor transformation scheme to protect the private information carried by elements' values of a tensor. Then we design a privacy-preserving outsourcing algorithm for ALS based CP tensor decompositions. We implement our proposed algorithm on a laptop and Amazon EC2 cloud and offer experiment results to show the sianificant computing time-savings.