The current document is directed to distributed-secure-storage systems, and processes carried out within the distributed-secure-storage systems, that provide for secure storage and retrieval of confidential and critical data, referred to as “secrets,” within distributed computer systems. The secret-storage systems partition an input secret into multiple secret shares and distribute the secret shares among multiple secret-share-storing node subsystems, without persistently storing the secret itself. An agent within a client device subsequently requests a secret share corresponding to a secret, or a share of data derived from the secret share, from each of the multiple secret-share-storing nodes. The multiple secret-share-storing nodes additionally cooperate to periodically alter the stored secret shares corresponding to a secret in a way that allows agents to recover the original secret, or derived data, from all or a portion of the altered secret shares or derived-data shares.