Abstract—Thanks to their high availability, scalability, and
usability, cloud databases have become one of the dominant
cloud services. However, since cloud users do not physically
possess their data, data integrity may be at risk. In this
paper, we present a novel protocol that utilizes crowdsourcing
paradigm to provide practical data integrity assurance in keyvalue
cloud databases. The main advantage of our protocol
over previous work is its high applicability – as opposed to
existing approaches, our scheme does not require any system
changes on the cloud side and thus can be applied directly
to any existing system. We demonstrate the feasibility of our
scheme by a prototype implementation and its evaluation.