Abstract: In outsourcing cloud storage environment, users cannot completely trust storage service providers. It is a challenge problem to validate whether storage service providers are faithfully maintaining enough replicas complying its promise with users. Most of existing solutions have several disadvantages, such as low efficiency, high computation overload and the absence of supporting for dynamic data updating. A multiple replica cloud storage model with Collector is presented, and a novel multiple replica possession proving scheme, namely MRP-PKP(multiple replica possession proving scheme based on public key partition), is proposed based on public key partition. In preparing phrase, a public key is divided into several private shares and distributed to corresponding storage servers. In validating phrase, only after all storage servers show their possession evidences can the challenge be admitted as success. The scheme is designed to defeat collude adversaries, and can support dynamic data updating operations at block level easily. It is the first scheme to validate all replica’s possessions with just one challenge. Both theoretical analysis and simulating experiment show that MRP-PKP scheme has higher secure guarantee, lower communication cost and computation overload than existing schemes.