An index-based proof-of-responsibility method and system for preventing side-channel attacks in data deduplication systems is described. A storage server computer creates a secret index referencing a specific random block in a file stored in a central data store. The server stores the hash value of the file along with the block referenced by the index. When a client computer submits a deduplication request regarding the file, server challenges the client to produce the block referenced by the index. If the proper file block is returned, the client has proven ownership of the file, and the request is granted. The server refreshes the index and associated challenge block after processing each request by a client computer.