The problem of storing secure information on a network is studied. A formal framework for distributed secret storage is introduced, and possible applications in technological and social systems are discussed. The problem is formulated as the optimization of a robustness functional in which two competing requirements are balanced: survivability under network-degrading processes and resistance to adversarial compromise. An exact representation of survivability is derived in terms of minimal information-carrying subgraphs (MICS), which provide a reduced description of the reconstruction events relevant to the stored information. This representation is then used to construct semi-local optimization methods whose dynamics do not require global knowledge of the network structure. Finally, it is shown that, in a limiting case, the robustness functional can be mapped naturally to an effective spin Hamiltonian.