Pipeline-integrity: Scaling the use of authenticated data structures up to the cloud

Public cloud storage services are widely adopted for their scalability and low cost. However, delegating the management of the storage has serious implications from the security point of view. We focus on integrity verification of query results based on the use of Authenticated Data Structures (ADS). An ADS enables efficient updates of a cryptographic digest, when data changes, and efficient query verification against this digest. Since, the digest can be updated (and usually signed)exclusively with the intervention of a trusted party, the adoption of this approach is source of a serious performance degradation, in particular when the trusted party is far from the server that stores the ADS. In this paper, we show a protocol for a key–value storage service that provides ADS-enabled integrity-protected queries and updates without impairing scalability, even in the presence of large network latencies between trusted clients and an untrusted server. Our solution complies with the principle of the cloud paradigm in which services should be able to arbitrarily scale with respect to number of clients, requests rates, and data size keeping response time limited. We formally prove that our approach is able to detect server misbehaviour in a setting whose consistency rules are only slightly weaker than those guaranteed by previous results. We provide experimental evidence for the feasibility and scalability of our approach.