The theory of Markowitz portfolio has had enormous value and extensive applications in finance since it came into being. With the advent of the Big-Data era and the increasingly complicated financial market, the resource consumption of computing portfolio investments is significantly increasing. Cloud computing offers a good platform to efficiently compute large-scale portfolio investments, in particular, for resource-limited investors. In this paper, a Markowitz model (MM) is taken into consideration for outsourcing to a public cloud in a privacy-conscious way. As in general computation outsourcing, outsourcing MM inevitably faces four issues, namely, input/output privacy, correctness, verification, and substantial computation gain for investors; it has consistent complexity with the original methods when the cloud solves the encrypted version. However, the proposed cloud-assisted privacy-conscious MM employs location-scrambling and value-alteration encryption operations, which can protect the MM’s input/output privacy well. Moreover, the correctness of solving MM over an encrypted domain in the cloud side can be demonstrated and the results returned by the cloud can be verified. Furthermore, both theoretical and experimental analyses validate that the investor can obtain a huge amount of computational gain, and the cloud complexity consistent with that of the original case when solving the encrypted version.