A Feasibility Analysis of Secure Multiparty Computation Deployments
Name
Reimo Rebane
Abstract
Imagine a scenario where multiple companies hold valuable information and they want to combine their data for analysis that would benefit them all. In an honest world, the companies could do just that - combine their data. However, in the real world, none of them can afford to make their data public because it could compromise their competitive advantage. One can easily find many similar real-world scenarios where there are privacy issues concerned with the data. Data privacy is also a very prominent issue when outsourcing the computing resources, for example, to cloud services. A cryptographic solution to this problem would be to use secure multiparty computation (SMC). SMC is a useful tool for computing the result of an operation with the inputs of multiple parties, without revealing what the inputs were. As a result, we can perform computations on the data without disclosing it.
There exist two main approaches how to perform SMC. First, circuit evaluation, which is based on computations on arithmetic or logic circuits and is CPU intensive (CPU-bound). Second, general multiparty computation, which relies more on the communication between the parties (network-bound). Currently, the more efficient systems in this field use the latter approach. The theoretical complexity of these systems is well known. However, for real-life deployments the theoretical results alone are not enough. In this work, we would like to study the practical performance of the network-bound general multiparty computation. Based on the published results, the Sharemind SMC framework has shown the best performance and widest functionality among similar systems.
One goal of this work was to create a mathematical model for predicting computational performance of SMC depending on the network parameters. The model was constructed based on a set of experiments conducted on th Sharemind framework. To validate our model, we set up a set of servers in the cloud environment. In this setting we measured the parameters of the network connections between the machines. The predictions were compared to the actual computation results. We were unable to accurately predict the running time of the protocols in the cloud. However, we concluded that this result was probably due to the inability to accurately estimate the effective network parameters to compute the model coefficients.
The model validation in the experiment cluster environment showed that the models can be used to accurately predict the running time of the secure operations inside more complex algorithms.
In the last part of the work, we utilized the general model to assess the feasibility of SMC in the cloud environment. With the model, we computed time estimations for executing certain operations in a sample scenario. The cost estimation showed that for a secure survey scenario, the cost of the secure computations is low compared to the cost of keeping the server running during the data gathering phase for the survey. The cost of the performed operations only starts to play a role with large data sets and computation heavy algorithms.
The results of this work indicate that it is indeed feasible to do secure multiparty computation in the cloud environment for a whole range of real-world scenarios. This mainly benefits the potential cloud service scenarios where privacy of the stored data is one of the primary concerns.
In this work we also found some indications of possible improvements to the Sharemind framework. We noticed that even though the protocols have a lot of avai\-lable bandwidth, they are not using it. For high throughput connections, the performance of the protocols may be significantly increased if the bandwidth utilization rate can be improved. As a future work, we could try other approaches to construct the models or, alternatively, build a specialized tool to measure the bandwidth parameter for the models.
Graduation Thesis language
English
Graduation Thesis type
Master - Computer Science
Supervisor(s)
Dan Bogdanov, Sven Laur, Tuomas Aura
Defence year
2012