The present disclosure relates to an advantageous system and related methods for distributed deduplication of encrypted chunks. One embodiment relates to a method for storing encrypted chunks in which an encryption key is generated independently from a chunk payload. With this method, two encrypted chunks are identifiable as having identical chunk payloads even when the chunk payloads are encrypted with different encryption keys. Other embodiments, aspects and features are also disclosed.