Secure data storing in a pool of vulnerable servers Marcin Gogolewski and Miroslaw Kutylowski Secure storing of data is a much more challenging task than encryption with a secret key. These data can be destroyed (for instance through overwriting) either by an external adversary or by the administrator of the data server. %DOC storing the data If such an attack is deployed only occasionally, for a well chosen data, then a hardware fault can be blamed for the loss of data. %DOC this situation. Therefore effective countermeasures are to be deployed. In order to elude the threat described one may store multiple copies of data in a pool of data servers. However, in order to limit the costs, the number of copies must be limited. Again, this provides a chance for an adversary to attack only the few servers actually storing the copies of data relevant for him. In this paper we design a simple and elegant method for secure storing of encrypted data based on Rackoff-Simon onion protocol used previously against traffic analysis. Our protocol works in an environment where the servers and the clients communicate through a shared communication channel which provides anonymity of the sender (such as an Ethernet bus). The protocol uses only standard symmetric and asymmetric encryption schemes. The protocol presented in this paper guarantees that (a) the user alone chooses where the data is stored, the number of copies can be determined immediately before storing the data, (b) the server storing the data has no knowledge about other servers storing the same data, (c) consistency: either all or no copy of the data is stored by the honest servers (i.e. the servers not overrun by an adversary), (d) the client and each server involved in storing the data sends exactly one message, (e) with high probability the system is immune against adversaries that may gain control over a limited number of servers.