We put forward the first simulation-based security definition for entangled cloud storage, in the framework of *universal composability* (Canetti, FOCS 2001). We then construct a protocol satisfying our security definition, relying on an *entangled encoding scheme* based on privacy-preserving polynomial interpolation; entangled encodings were originally proposed by Aspnes et al. as useful tools for the purpose of data entanglement. As a contribution of independent interest we revisit the security notions for entangled encodings, putting forward stronger definitions than previous work (that for instance did not consider collusion between clients and the cloud provider).
Protocols for entangled cloud storage find application in the cloud setting, where clients store their files on a remote server and need to be ensured that the cloud provider will not modify or delete their data illegitimately. Current solutions, e.g., based on Provable Data Possession and Proof of Retrievability, require the server to be challenged regularly to provide evidence that the clients' files are stored *at a given time*. Entangled cloud storage provides an alternative approach where any single client operates implicitly on behalf of all others, i.e., as long as one client's files are intact, the entire remote database continues to be safe and unblemished.
Category / Keywords: cloud storage, multi-party computation Original Publication (with major differences): AsiaCCS 2015 (Workshop on Security in Cloud Computing) Date: received 3 Sep 2012, last revised 10 Mar 2016 Contact author: oezguer dagdelen at cased de Available format(s): PDF | BibTeX Citation Note: Full version published in Future Generation Computer Systems - Special Issue on Cloud Cryptography Version: 20160310:123624 (All versions of this report) Short URL: ia.cr/2012/511