ZKNiS-PoW: A privacy-preserving proof of ownership scheme for secure cloud storage
Tang Zhou, Le Wang, Minxian Liang · Array · 2025
There is a large amount of redundant data among users of cloud storage services. Client-side deduplication helps reduce the cost for service providers by avoiding repeated uploads and storage. However, this technique brings new security risks. Malicious users may use illegally obtained deduplication tags, such as file fingerprints, to fake ownership of other users’ files. Proof of Ownership (PoW) can require users to prove they have the full file, but existing methods are inefficient. They often need multiple rounds of interaction or complex computation over the whole file. As a result, the verification time increases with file size. To solve this problem, we propose a non-interactive PoW scheme based on zk-STARK. The system selects a number of challenge blocks that meet cryptographic security. It uses arithmetic circuits to encode block selection, hash computation, and the correctness of accumulators. Users only need to generate a zero-knowledge proof on these blocks. This allows them to prove they own the full file without revealing its content. The verification time does not depend on file size and appears near-constant in practice. In tests on files from 64 MB to 1 GB, our scheme is 1.2 to 46 times faster than existing methods. Security analysis shows that only a small number of blocks need to be verified. Even if an attacker knows 90% of the file, the chance of forgery is still lower than 2 − 80 . This scheme provides an efficient and practical solution for deduplication in cloud storage with strong privacy protection.