Cryptographic techniques for securing data in the cloud

• Autores: Jordi Ribes Gonzalez
• Directores de la Tesis: Oriol Farràs Ventura (dir. tes.)
• Lectura: En la Universitat Rovira i Virgili ( España ) en 2018
• Idioma: español
• Tribunal Calificador de la Tesis: Jorge Luis Villar Santos (presid.) , Josep Domingo i Ferrer (secret.) , Melek Önen (voc.)
• Enlaces
  • Tesis en acceso abierto en: TDX
• Resumen

  • The cloud computing paradigm provides users with remote access to scalable and powerful infrastructures at a very low cost. While the adoption of cloud computing yields a wide array of benefits, the act of migrating to the cloud usually requires a high level of trust in the cloud service provider and introduces several security and privacy concerns. This thesis aims at designing user-centered techniques to secure an outsourced data set, and to enable the delegation of some of the most demanded functionalities in the cloud computing context.

    The studied problems and their treatment stem from use cases and requirements proposed during the course of the European Commission H2020 project "CLARUS: User-Centered Privacy and Security in the Cloud". The functionalities and techniques explored in this setting are searching over outsourced data, outsourcing Kriging interpolation computations, secret sharing schemes and privacy-preserving data splitting.

    The first work on the subject of searching over outsourced data concerns Symmetric Searchable Encryption (SSE), which aims at enabling efficient search over outsourced encrypted data in a single-user architecture. This work develops techniques that enable secure and efficient two-dimensional range queries in SSE, and the proposed solutions are oriented towards outsourcing data sets containing spatial geo-referenced data. Here, SSE is used as a cryptographic primitive and, as in previous works, binary trees and over-covers are employed to efficiently enable range queries. Moreover, a method is developed to reduce the false-positive rate induced by the over-cover technique, and a security improvement is achieved by using quadtrees instead of binary trees. Finally, the leakage induced by the proposed schemes is described according to the security definition of Cash et al., and a comparison of the worst-case efficiency of the schemes with that of previous works is shown.

    The second work on the subject of searching over outsourced data aims at designing efficient Public Key Encryption with Keyword Search (PEKS) schemes. PEKS schemes are searchable encryption schemes that enable public key holders to encrypt documents, while the secret key holder is able to generate queries for the encrypted data. This work develops two schemes achieving conjunctive and subset queries. The presented schemes follow the basic scheme of Boneh et al., working with different complexity assumptions. By using the DBDH assumption, the first scheme achieves conjunctive queries with single-element trapdoors and only one pairing operation in the search process, and the second scheme uses the p-BDHI assumption to enable subset queries with arbitrary keyword space. Proofs of consistency and security of the schemes are also provided, using the frameworks by Abdallah et al. and by Boneh et al.. Finally, a performance analysis is given through an implementation carried out using the PBC library in Python, and the worst-case efficiency analysis shows that the presented schemes outperform existing ones.

    The contribution concerning the outsourcing of computations to the cloud, guided by the CLARUS project, aims at developing a solution to securely outsource Kriging interpolation. Kriging is a spatial interpolation algorithm widely applied in areas such as geo-statistics where, for example, it may be used to predict the quality of mineral deposits in a location based on previous sample measurements. This work describes a method for the private outsourcing of Kriging interpolation that protects crucial information relating to measurement values. This is achieved by combining homomorphic encryption with a tailored modification of the Kriging interpolation algorithm. It is shown that, in the most widely used variant of Kriging (namely Ordinary Kriging), all the information regarding measurement values can be either ‘factored out’ or encrypted so that an untrusted server is able to compute Kriging predictions while being oblivious to the measurement values. The practicality of this scheme is shown through a performance analysis of an implementation in Python, using the PHE library. No previous works studied the problem of outsourcing general Ordinary Kriging computations, and this problem is interesting since Kriging interpolation is employed in many real-case applications.

    This thesis also tackles secret sharing, which is a fundamental primitive in cryptography. Secret sharing is an essential building block for many cloud-oriented cryptographic schemes, such as attribute-based encryption and secure multi-party computation. One of the most important efficiency measures in the secret sharing literature is the optimal information ratio. This efficiency measure has a great impact on the efficiency of many of the cryptographic schemes based in secret sharing (for instance, in the KP-ABE scheme by Goyal et al.). However, computing the optimal information ratio of an access structure is generally a difficult task. Hence, this motivates approaching the problem of finding properties that facilitate the description of the optimal information ratio. More concretely, this work shows that any two access structures that are close (i.e., whose symmetric difference is small) admit secret sharing schemes with similar information ratios. This result is proved constructively, by devising a method that, given a secret sharing scheme, produces another scheme whose access structure is close to that of the original scheme. The obtained result is also extended to other computational models, such as the Razborov rank measure, critical subfamilies, the leafsize of Boolean formulas and submodular formal complexity measures.

    Finally, this thesis approaches the privacy-preserving data splitting technique, which aims at protecting data privacy by storing different fragments of data at different locations. A new combinatorial formulation to the data splitting problem is presented, where data splitting is seen as a purely combinatorial problem. This problem consists in splitting data into different fragments, in a way that satisfies certain combinatorial properties derived from processing and privacy constraints. Using this formulation, new combinatorial and algebraic techniques are developed in order to obtain solutions to the data splitting problem. As an initial solution, this work presents an algebraic method which translates the processing and privacy constraints into a set of simultaneous equations. Since these equations can be solved using Gröbner bases, it is possible to build an optimal data splitting solution. However, this method is not efficient in general. Therefore, greedy algorithms are designed to find solutions that are not necessarily minimal sized, and the number of obtained fragments is bounded in the process. In the experimental evaluation of the proposed schemes, the running times of the algebraic method are analyzed in a medical data setting. The greedy algorithms are also analyzed by testing a large amount of privacy and processing constraints coming from random graphs, and by tabulating the mean time efficiency and the mean increase of the result size with respect to the optimal number of fragments.