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 secrets within distributed computer systems, including private encryption keys used for client authentication during establishment of secure communications channels. 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. Each secret-share-storing node transmits the requested secret share or derived-data share to the agent, which reconstructs the secret from all or a portion of the secret shares or a data value from all or a portion of the derived-data shares transmitted to the agent.