Integrity guarantees over highly dynamic outsourced map data

Highly dynamic map data play nowadays a crucial role in different application contexts. Their huge volume often enforces the data owner to outsource them to the cloud, becoming this way the client of analytical queries computed by the cloud. Therefore, the classical problem of query integrity, usually considered in the scenario of location-based services (LBS) over outsourced databases, arises also in this different scenario. This means that the data owner should have guarantees that the cloud response to a submitted query is correct, complete, and fresh. On the one hand, the considered setting simplifies the problem, because public verifiability is no longer required, but poses new challenges, such as supporting very efficient insertions and deletions and, consequently, effective guarantees for freshness. This paper studies this problem by proposing a lightweight message-authentication-code-based approach fulfilling the above requirements better than the approaches available in the literature, according to an analytical cost evaluation.