Abstract: Abstract As the rapid adoption of cloud storage services, a new technology of client-side deduplication is proposed to save the bandwidth of uploading copies of existing files to the server. This promising technology, however, has been recently found being vulnerable to a new kind of attack, in which by learning just a small piece of information about the file, namely its Hash value, an attacker is able to get the entire file from the server. To solve the problems mentioned above, we propose a cryptographically secure and efficient scheme to support cross-user client side deduplication over encrypted file. The new scheme utilizes the technique of spot checking in which the client only need to access small portions of the original file, dynamic coefficients, randomly chosen indices of the original files and a subtle approach to distribute the file encrypting key among clients to satisfy security requirements. Extensive security analysis shows that the proposed scheme can generate provable ownership of the encrypted file (POEF) with the presence of the curious server, and maintain a high detection probability of the client misbehavior. Both performance analysis and simulation results demonstrate that our proposed scheme is much more efficient than the existing schemes, especially in reducing the burden of the client.