Fair and dynamic proofs of retrievability

Cloud computing is getting increasingly popular, but has yet to be widely adopted arguably because there are many security and privacy problems that have not been adequately addressed. A specific problem encountered in the context of cloud storage, where clients outsource their data (files) to untrusted cloud storage servers, is to convince the clients that their data are kept intact at the storage servers. An important approach to achieve this goal is called Proof of Retrievability (POR), by which a storage server can convince a client --- via a concise proof --- that its data can be recovered. However, existing POR solutions can only deal with static data (i.e., data items must be fixed), and actually are not secure when used to deal with dynamic data (i.e., data items need be inserted, deleted, and modified). Motivated by the need to securely deal with dynamic data, we propose the first dynamic POR scheme for this purpose. Moreover, we introduce a new property, called fairness, which is necessary and also inherent to the setting of dynamic data because, without ensuring it, a dishonest client could legitimately accuse an honest cloud storage server of manipulating its data. Our solution is based on two new tools, one is an authenticated data structure we call range-based 2-3 trees (rb23Tree for short), and the other is an incremental signature scheme we call hash-compress-and-sign (HCS for short). These tools might be of independent value as well.