Delegated private set intersection on outsourced private datasets

The significance of cloud computing is increasing and the cloud is receiving growing attention from individuals and companies. The cloud enables ubiquitous and on-demand access to a pool of configurable computing resources that can be scaled up easily. However, the cloud is vulnerable to data security breaches such as exposing confidential data, data tampering,and denial of service. Thus, it cannot be fully trusted and it is crucial for the clients who use the cloud to protect the security of their own data.In this thesis, we design cryptographic protocols to allow clients to outsource their private data to the cloud and delegate certain computation tothe cloud securely. We focus on the computation of set intersection which has a broad range of applications such as privacy-preserving data mining,and homeland security. Traditionally, the goal of Private Set Intersection(PSI) protocols has been to enable two parties to jointly compute the intersection without revealing their own set to the other party. Many such protocols have been designed. But, in the cases where data and computation are outsourced to the cloud, the setting and trust assumptions are considerably changed. The traditional PSI protocols cannot be used directly to solve security problems, without sacrificing the advantages the cloud offers.The contribution of this thesis is a set of delegated PSI protocols that meet a variety of security and functional requirements in the cloud environment.For most clients, the most critical security concern when outsourcing data and computation to the cloud is data privacy. We start from here and design O-PSI, a novel protocol in which clients encrypt their data before outsourcing it to the cloud. The cloud uses the encrypted data to compute the intersection when requested. The outsourced data remain private against the cloud all the time since the data stored in the cloud is encrypted and the computation process leaks no information. O-PSI ensures that the computation can be performed only with the clients' consent. The protocol also takes into account several functional requirements in order to take full advantage of the cloud. For example, clients can independently prepare and upload their data to the cloud, and the clients are able to delegate to the cloud the computation an unlimited number of times, without the need to locally re-prepare the data. We then extend O-PSI in several ways to provide additional properties:* EO-PSI is a more efficient version of O-PSI that does not require public key operations.* UEO-PSI extends EO-PSI with efficient update operations, making it possible to efficiently handle dynamic data.* VD-PSI extends O-PSI with verifiability, i.e. the clients can efficiently verify the integrity of the computation result. For each protocol, we provide a formal simulation-based security analysis.We also compare the protocols against the state of the art. In addition to that, we have implemented the O-PSI and EO-PSI protocols and provide an evaluation of their performance based on our implementation.The significance of cloud computing is increasing and the cloud is receiving growing attention from individuals and companies. The cloud enables ubiquitous and on-demand access to a pool of configurable computing resources that can be scaled up easily. However, the cloud is vulnerable to data security breaches such as exposing confidential data, data tampering,and denial of service. Thus, it cannot be fully trusted and it is crucial for the clients who use the cloud to protect the security of their own data.In this thesis, we design cryptographic protocols to allow clients to outsource their private data to the cloud and delegate certain computation tothe cloud securely. We focus on the computation of set intersection which has a broad range of applications such as privacy-preserving data mining,and homeland security. Traditionally, the goal of Private Set Intersection(PSI) protocols has been to enable two parties to jointly compute the intersection without revealing their own set to the other party. Many such protocols have been designed. But, in the cases where data and computation are outsourced to the cloud, the setting and trust assumptions are considerably changed. The traditional PSI protocols cannot be used directly to solve security problems, without sacrificing the advantages the cloud offers.The contribution of this thesis is a set of delegated PSI protocols that meet a variety of security and functional requirements in the cloud environment.For most clients, the most critical security concern when outsourcing data and computation to the cloud is data privacy. We start from here and design O-PSI, a novel protocol in which clients encrypt their data before outsourcing it to the cloud. The cloud uses the encrypted data to compute the intersection when requested. The outsourced data remain private against the cloud all the time since the data stored in the cloud is encrypted and the computation process leaks no information. O-PSI ensures that the computation can be performed only with the clients' consent. The protocol also takes into account several functional requirements in order to take full advantage of the cloud. For example, clients can independently prepare and upload their data to the cloud, and the clients are able to delegate to the cloud the computation an unlimited number of times, without the need to locally re-prepare the data. We then extend O-PSI in several ways to provide additional properties:* EO-PSI is a more efficient version of O-PSI that does not require public key operations.* UEO-PSI extends EO-PSI with efficient update operations, making it possible to efficiently handle dynamic data.* VD-PSI extends O-PSI with verifiability, i.e. the clients can efficiently verify the integrity of the computation result. For each protocol, we provide a formal simulation-based security analysis.We also compare the protocols against the state of the art. In addition to that, we have implemented the O-PSI and EO-PSI protocols and provide an evaluation of their performance based on our implementation