Query integrity


ESCUDO-CLOUD offers novel probabilistic techniques enabling clients to efficiently verify the integrity (in terms of correctness and completeness) of computation results returned by external cloud providers. They are based on the combined adoption of three protection techniques:

  • Encryption on-the-fly: make data unintelligible to the computational cloud
  • Markers: fake tuples not recognizable as such by the computational cloud
  • Twins: replication of a subset of the original tuples

A missing marker or a twin appearing solo in the join result signals an integrity violation. Encryption guarantees data confidentiality.

query integrity

 

The above figure illustrates how the join evaluation works when there are two tables (L and R) stored at two different storage servers that need to be joined by a computational cloud.

The innovation brought by ESCUDO-CLOUD in this context is represented by the support of approximate joins (i.e., joins that combine tuples with similar values for the join attribute), many-to-many joins, and joins among more than two tables. ESCUDO-CLOUD techniques permit to limit the computation and communication overhead caused by integrity verification, with limited impact on integrity guarantees.

 

Related Publications