Project topics and materials
Get Complete Project Material File(s) Now! »
Outsourced data Confidentiality by Encryption
Despite that traditional encryption mechanisms (e.g., Data Encryption Standard (DES) [NIST 1999] and Advanced Encryption Standard (AES) [FIPS. 2001]) ensures strong confidentiality guarantees. They are suffering from two main limitations that reduce the effectiveness of these traditional schemes, especially because of the large amount of outsourced data.
First, when outsourcing the data to an untrusted (honest by curious) service provider, data owners generally encrypt the data before its outsourcing to the remote storage server. However, the employment of traditional encryption schemes is inconvenient for huge amount of data as it reduces significantly the computation capacity both at the client and the server sides.
Second, these traditional encryption approaches are deterministic, they are not adaptable and do not allow performing operations over encrypted data (e.g., search, computation, etc.).
Search over encrypted data is very useful to overcome the traditional all-or-nothing retrieval policy of encrypted data. When designing an approach for searching over encrypted data, the computation on the client-side, as well as the communication overhead, plays critical roles for deciding its efficiency. More the computation on the client-side is minimized and the communication overhead is reduced, more the searching over encrypted data approach is efficient. Several approaches have emerged to allow efficient search over encrypted outsourced data. They can be classified into several classes: Bucketing-based approaches [Hacigümüs et al. 2002, Hore et al. 2004], techniques that are based on some specialized data structures [Damiani et al. 2003b, Damiani et al. 2003a, Shi et al. 2007, Park 2011, Wang et al. 2014], order preserving encryption based approaches [Agrawal et al. 2004, Boldyreva et al. 2009, Boldyreva et al. 2011, Boldyreva et al. 2012], Searchable Encryption based approaches [Song et al. 2000, Goh 2003a, Golle et al. 2004, Curtmola et al. 2006, Amanatidis et al. 2007, Chase and Kamara 2011, Kamara et al. 2012, Kamara and Papamanthou 2013], and Homomorphic Encryption based approaches [Boneh et al. 2005, Paillier 1999, Gentry 2009].
Bucketing Based Approaches
Hakan Hacigümüs et al. [Hacigümüs et al. 2002] have introduced a model for ensuring the confidentiality of outsourced databases based on a bucketization-based technique. This technique consists of segmenting the domain of attributes, which their assumed values are considered sensitive, into a number of non-intersecting subsets of values called buckets and having the same size. Then, a unique random identifier ID is associated to the set of unencrypted values in each Bucket. Finally, the encrypted tuples together with buckets IDs are outsourced to a cloud storage server. Let us suppose that a database D composed of a finite set of relational tables {T1, · · · , Tn}
has to be outsourced. For each tuple ti = {vi1 , · · · , vimi } in the relational table Ti of D, tsi = {etuple, IDvi1 , · · · , IDvim i } will be outsourced to the cloud server, where etuple represents the encryption of the tuple (vi1 , · · · , vimi) and IDij represents the identifier of the bucket containing each vij , 1 j mi. The bucketization method (segmentation function) used to generate the corresponding bucket IDs for the values of each attribute are stored privately by the data owner.
Specialized Data Structures Based Techniques
Damiani et al. [Damiani et al. 2003a, Damiani et al. 2003b] introduced an approach allowing to perform exact and order searches over encrypted data using a B+– tree based indexing method. The proposed technique is used for each attribute to efficiently allows order and exact searches over it. That is, a B+– tree is created over the unencrypted values of the attributes to be used to search the data. Then, for each node in the created trees, a couple (id, enode) is created and outsourced to the cloud server, where id is a node identifier and enode = hlid,E(value), ridi represents the encrypted form of the cleartext node using a deterministic encryption E, lid and rid represent respectively the left and the right nodes identifiers. To perform an order search (i,e,. range query) over an attribute attr, as a first step, the client (or data owner) selects the root node of the outsourced B+– tree created over the values of attr. In the second step, the client decrypts E(value) and compares value with the search condition to figure out with branch (left or right) is to be taken. This procedure repeats until the leaf level of the B+– tree is reached. Finally, the client navigates through the leaves to select the corresponding values. Although the final querying results produced using this method are accurate (no false positive), to perform a single search operation, we still need to perform many interactions (the height of B+– tree) between the client and the cloud server. Shi et al. [Shi et al. 2007] proposed MRQED – a confidentiality-preserving searchable scheme supporting multi-dimensional order search over encrypted data. In this approach, a discrete integer values 1 throught D is used to encode each attribute, where D represents the number of possible values that might be assumed by each attribute. Therefore, a binary interval tree BIT(D) is created over integers 1 from D. Despite this approach ensures provably strong security, it is useless in practice since a server needs to fully scan the whole encrypted relation to perform single order search request.
Table of contents :
1 Introduction
1.1 Data Outsourcing Basics
1.2 Data Outsourcing Security Challenges
1.3 Objectives and Contributions
1.4 Organization of the dissertation
I Preserving Outsourced Data Confidentiality
2 Outsourced Data Confidentiality: State of the Art
2.1 Introduction
2.2 Outsourced data Confidentiality by Encryption
2.2.1 Bucketing Based Approaches
2.2.2 Specialized Data Structures Based Techniques
2.2.3 Order-Preserving Encryption Based Approaches
2.2.4 Searchable Symmetric Encryption Based Approaches
2.2.5 Homomorphic Encryption Based Approaches
2.3 Outsourced Data Confidentiality by Dissociation
2.3.1 Confidentiality by Fragmentation
2.3.2 Confidentiality by Combining Fragmentation and Encryption .
2.4 Conclusion
3 Preserving Multi-relational Outsourced Databases Confidentiality using Fragmentation and Encryption
3.1 Introduction
3.1.1 Motivating Scenario
3.1.2 Contributions
3.1.3 Chapter Outline
3.2 Technical Preliminaries
3.2.1 Architecture
3.2.2 Trust and Attack Model
3.3 Confidentiality Using Fragmentation and Encryption
3.4 Query Transformation and Optimization
3.5 Preserving Data Unlinkability
3.5.1 PIR System design
3.6 Implementation and Evaluation
3.6.1 Experimental Design
3.6.2 Evaluation
3.7 Conclusion and Contributions
4 Combining Encryption-based Mechanisms to ensure Outsourced Data Confidentiality
4.1 Introduction
4.2 Problem Description
4.2.1 Adjustable Database Encryption
4.2.2 Functional Requirements
4.2.3 Security Levels
4.2.4 Security Requirements and The Need for Policy Configuration
4.2.5 Policy Enforcement
4.3 Policy Configuration
4.3.1 System Modeling
4.3.2 Policy Modeling
4.3.3 Policy Conflict Detection
4.3.4 Policy Satisfaction
4.3.5 Heuristic Search
4.4 Use Case
4.5 Implementation and Evaluation
4.5.1 Experimental Design
4.5.2 Evaluation
4.6 Conclusion and Contributions
II Heterogeneous Security and Utility Requirements Specification and Enforcement over Outsourced Data
5 An Epistemic Temporal Logic based language for Specifying Security Policy and Security Mechanisms
5.1 Introduction
5.2 An Epistemic Temporal Logic based language
5.2.1 Syntax
5.2.2 Semantics
5.2.3 Axiomatizations
5.3 Data Model Specification
5.4 Goal Specification
5.5 Policy Specification
5.5.1 Security Constraints
5.5.2 Utility Constraint
5.6 Mechanisms Specification
5.6.1 Encryption Based Security Mechanisms
5.6.2 Anonymization Based Security Mechanisms
5.6.3 Watermarking Based Security Mechanisms
5.6.4 Fragmentation Based Security Mechanisms
5.7 Conclusion and Contributions
6 Formal Reasoning Method to enforce Security Policies over Outsourced Data
6.1 Related Work
6.2 Choosing the Right Security Mechanisms
6.2.1 Fourth step: Choosing the Right Security Mechanisms.
6.3 Security Mechanisms Planning to Enforce Security Policies
6.3.1 Graphplan Description
6.3.2 Graphplan Modelling of the Planning Problem
6.3.3 Extending Planning Graph: Planning Under Security Constraints
6.3.4 Searching the Best Security Mechanisms Plan
6.4 Implementation and Evaluations
6.4.1 Implementation
6.4.2 Experimental Setup
6.4.3 Experimental Results
6.5 Conclusion and Contribution
7 Best effort based Approach for Security Mechanisms Planning to Enforce Security Policies Over Outsourced Data
7.1 Related Work
7.2 Preliminaries
7.3 Planning Graph Tainting
7.3.1 Taint Propagation Rules
7.4 Finding the Best Compromise
7.4.1 Heuristic Search
7.5 Conclusion
8 Conclusions and Perspectives
A Expression et déploiement de politiques de sécurité intégrées pour données externalisées
A.1 Introduction
A.2 middling version
A.3 middling version
A.3.1 Spécification de la politique à déployer
A.3.2 Déploiement de la politique
A.4 middling version
A.5 Conclusion
B The Specification of the System Used to Evaluate our Approach Proposed in Chapter 6
C Proofs of Theorems and Lemmas of Chapter 7
C.1 Proof of Lemma 1
C.2 Proof of Lemma 2
C.3 Proof of Theorem 11
C.4 Proof of Theorem 12
C.5 Proof of Theorem 13
List of Publications
Bibliography
