At present, almost all the provable data possession schemes require a large number of exponent calculations. In this paper a new scheme based on the homomorphy of NTRU algorithm is proposed. The scheme includes modules of Key Generation, Tag Generation, Challenge, Proof Generation, and Verification. This scheme requires only plus, minus, multiplication and modular computation. The correctness and security of the scheme are analyzed and the result shows that this scheme is reliable. Compared with other existing schemes, this scheme is with higher security, less computation, storage and communication cost.