Access privacy


Shuffle index

ESCUDO-CLOUD proposes to adopt the shuffle index as a solution for protecting content, access, and pattern confidentiality in cloud scenarios, where data are stored and managed by an external cloud provider. Data in the shuffle index are organized in a B+-tree with no link between the leaves and with every node encrypted to protect content confidentiality. Protection is realized by applying three complementary techniques:

  • cover: at every access, additional fake searches are executed together with the target search;
  • caching: the most recent target paths visited are kept in a client-side cache;
  • shuffling: at every access the content of accessed nodes is shuffled and re-written, destroying the otherwise static relationship between nodes content and physical blocks.

 

shuffle full2

 

The above figure illustrates an access to the shuffle index. The client visits in parallel one target path (green), a set of cover paths (blue), and a set of cached nodes (red). It randomly shuffles the content of accessed blocks. It re-encrypts and rewrites accessed nodes back at the server.

The innovation brought by ESCUDO-CLOUD in this context is represented by the support of range queries (i.e., queries that access a set of contiguous index values), of update operations that possibly modify the structure of the shuffle index (i.e., insertion and removal of index values), and of access control restrictions (i.e., different users can access different portions of the data in the shuffle index). ESCUDO-CLOUD techniques make read (punctual and range) and write accesses indistinguishable for any observer.

 

Distributed shuffle index

ESCUDO-CLOUD distributes the shuffle index structure to provide access and pattern confidentiality in a multi-cloud scenario, leveraging the presence of many providers. A distributed shuffle index randomly partitions data among three independent cloud providers (yellow, green, blu in the figure below).

 

distributed shuffle index 

 

Protection is realized by guaranteeing two properties:

  • uniform visibility: each provider should operate as if it was the only one serving the client, it is guaranteed by distributed covers (i.e., every time a node is accessed at a given level at a provider, access one additional block at the same level at each of the other providers);
  • continuous moving: data retrieved from a provider are not at the same provider after the access, it is guaranteed by swapping (i.e., data retrieved from a provider are randomly moved to any of the other two providers).

distributed swapping

 

The figure above illustrates an access to the distributed shuffle index, the swapping operated by the client, and the view of each provider before and after the access.

The innovation brought by ESCUDO-CLOUD in this context is represented by the analysis of the distributed shuffle index, proving its ability to provide access and pattern confidentiality also in case of collusion among the cloud providers.

Related Publications

  • Sabrina De Capitani di Vimercati, Sara Foresti, Stefano Paraboschi, Gerardo Pelosi, Pierangela Samarati "Access Control for the Shuffle Index" in Proc. of the 30th Annual IFIP WG11.3  Conference on Data and Applications Security and Privacy (DBSec 2016),  Trento, Italy, July 18-21, 2016
  • Sabrina De Capitani di Vimercati, Sara Foresti, Stefano Paraboschi, Gerardo Pelosi, Pierangela Samarati "Shuffle Index: Efficient and Private Access to Outsourced Data" in ACM Transactions on Storage (TOS), vol. 11, n. 4, October 2015, pp. 1-55 (article 19)
  • Sabrina De Capitani di Vimercati, Sara Foresti, Stefano Paraboschi, Gerardo Pelosi, Pierangela Samarati "Three-Server Swapping for Access Confidentiality" in IEEE Transactions on Cloud Computing (TCC), 2015