A method, non-transitory computer readable medium, and device that assists with managing storage in a distributed deduplication system includes receiving an object to be stored from a client computing device. The received object is divided into a plurality of fragments. A plaintext hash value and a ciphertext hash value is determined for each of the plurality of fragments, wherein each of the plurality of fragments is renamed with the corresponding determined ciphertext hash value. Each of the renamed plurality of fragments are stored in a plurality of storage repositories.