Cloud storage is used to store huge amounts of data, both for companies and private users. Multi-cloud emerged to prevent data from system failure by storing simultaneously several copies of the data among multiple clouds. Yet, this solution is costly in memory, and often does not guarantee confidentiality nor integrity of the data. Moreover, handling communication with each server can be a daunting task for private users. Using secret sharing, we propose an approach involving multiple cloud servers, each holding a data share of constant size (independent of the initial data size but also of the threshold). We delegate share computations, and communications with the providers, to an untrusted proxy (intermediate server), thus minimizing the client-side workload. We consider keyless clients meaning that data recovery does not rely on client’s long-term keys.

We propose two variants of a keyless space-efficient multicloud storage scheme. One is efficient with stronger security assumptions while the other allows more adversarial capabilities but incurs higher complexity. We formalize a security model, and prove the security of our protocols. Finally, we complement this formal analysis by a proof-of-concept to demonstrate our approach feasibility.