k-core decomposition is an important task in graph data processing in various fields, such as social network analysis, computational biology, medicine research, etc. In some applications involving massive graph processing, users usually outsource the graph data and k-core decomposition task on the graph, to cloud service providers, so as to alleviate the problem of limited computational resources. This solution, however, may pose threats to the privacy of the data and of the users, for example, leakage of node and edge information, and even the k value. In this paper, we propose a homomorphic encryption-based scheme called HEkc for k-core decomposition in the scenario of graph data outsourcing. We prove that the proposed scheme is secure under the semi-honest model, i.e., it can perform k-core decomposition correctly while preserving the privacy of the graph, the k value, and the computation result. In addition, we design two variants named HEkc-fast and HEkc-safe, to improve the efficiency of HEkc and to prevent it from the known-plaintext attack, respectively. Finally, we empirically evaluate the effectiveness of our proposed schemes through extensive experiments conducted on eight real datasets and the results show that our schemes for privacy-preserving k-core decomposition are promising.