Supporting concurrency and multiple indexes in private access to outsourced data¹

Issue title: Research in Computer Security and Privacy: Emerging Trends

Guest editors: Vijay AtluriGuest Editor and Claudia DiazGuest Editor

Article type: Research Article

Authors: De Capitani di Vimercati, Sabrina^a | Foresti, Sara^a | Paraboschi, Stefano^b | Pelosi, Gerardo^c | Samarati, Pierangela^{a; *}

Affiliations: [a] DI, Università degli Studi di Milano, Crema, Italy. E-mails: [email protected], [email protected], [email protected] | [b] Università degli Studi di Bergamo, Dalmine, Italy. E-mail: [email protected] | [c] DEIB, Politecnico di Milano, Milano, Italy. E-mail: [email protected]

Correspondence: [*] Corresponding author: Pierangela Samarati, DI, Università degli Studi di Milano, Via Bramante 65, 26013 Crema, Italy. Tel.: +39 0373 898061; Fax: +39 0373 898074; E-mail: [email protected]

Note: [1] A preliminary version of this paper appeared under the title “Supporting concurrency in private data outsourcing”, in Proc. of the 16th European Symposium on Research in Computer Security (ESORICS 2011), Leuven, Belgium, September 2011 [10].

Abstract: Data outsourcing has recently emerged as a successful solution allowing individuals and organizations to delegate data and service management to external third parties. A major challenge in the data outsourcing scenario is how to guarantee proper privacy protection against the external server. Recent promising approaches rely on the organization of data in indexing structures that use encryption and the dynamic allocation of encrypted data to physical blocks for destroying the otherwise static relationship between data and the blocks in which they are stored. However, dynamic data allocation implies the need to re-write blocks at every read access, thus requesting exclusive locks that can affect concurrency. Also, these solutions only support search conditions on the values of the attribute used for building the indexing structure. In this paper, we present an approach that overcomes such limitations by extending the recently proposed shuffle index structure with support for concurrency and multiple indexes. Support for concurrency relies on the use of several differential versions of the data index that are periodically reconciled and applied to the main data structure. Support for multiple indexes relies on the definition of secondary shuffle indexes that are then combined with the primary index in a single data structure whose content and allocation is unintelligible to the server. We show how using such differential versions and combined index structure guarantees privacy, provides support for concurrent accesses and multiple search conditions, and considerably increases the performance of the system and the applicability of the proposed solution.

Keywords: Data outsourcing, access privacy, concurrency, shuffle index

DOI: 10.3233/JCS-130468

Journal: Journal of Computer Security, vol. 21, no. 3, pp. 425-461, 2013