When using distributed storage systems to outsource data storage into the cloud, it is often vital that this is done in a privacy preserving way, i.e., without the storage servers learning anything about the stored data. Especially when storing critical data, one often further requires efficient means to check whether the data is actually stored correctly on these servers. In the best case, such an auditing could itself be outsourced to a third party which does not need to be trusted by the data owner. That is, also the auditing mechanism should guarantee privacy, even if the auditor collaborates with a (sub)set of the storage servers. However, so far only a small number of privacy preserving third party auditing mechanisms has been presented for single server storage solutions, and no such protocols exist at all for a distributed storage setting. In this patent, we therefore define and instantiate a privacy preserving auditable distributed storage system. Our instantiation can be based on any homomorphic secret sharing scheme, and is fully keyless, efficient, and information-theoretically private. Furthermore, it supports batch audits, and is backward compatible with existing secret sharing based storage solutions.