Change search

A Secure Multi-Party Computation Protocol Suite Inspired by Shamir's Secret Sharing Scheme
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Telematics.
2014 (English)MasteroppgaveStudent thesis
##### Abstract [en]

Secure multi-party computation allows us to perform analysis on private data without compromising it. Therefore, practical solutions for SMC are very welcome and Sharemind is one of the examples of such frameworks. There are already various protocol suites implemented on Sharemind, such as an additive three-party protocol suite. In this thesis, we designed and implemented a protocol suite, that was inspired by Shamir's secret sharing scheme. The latter is a popular way to divide a secret into pieces, called shares. The main result of this thesis are the implemented protocols with correctness and security proofs. We created a new protection domain kind \pdname{shamirnpp}, that allows one to create protection domains for various $n$-out-of-$k$ Sharmir's secret-sharing schemes. This PDK can now be used to write secure applications in the SecreC language. More specifically, we implemented protocols for addition, multiplication, boolean arithmetic and comparison operations. These protocols are the building blocks for various other functions one would want to possess, when analysing private data. As Sharemind has a standard library and a possibility to write domain-polymorphic code, many additional features, such as the absolute value function, can already be used with our newly implemented PDK. The goal of this work was to explore another SMC implementation option and compare it to the existing one on Sharemind. Our new protection domain kind based on Shamir's scheme was compared to \pdname{additive3pp}. Looking at simpler protocols, such as declassification or multiplication, we saw that our SMC algorithms offer better theoretical complexity. That was also evident from the benchmarking results for smaller input sizes. For larger inputs and more complicated operations, such as equality testing and less-than comparison, we had to admit \pdname{additive3pp} being better. One of the reasons, for the performance difference, is our naive implementations for \cmd{Conjunct} and \cmd{PrefixAND} algorithms. Many other algorithms depend on their performance, see Figure~\ref{fig:relations}, and improving it would improve the speed of equality testing and less-than comparison. This brings us to future work. As mentioned before, some of the protocols from this thesis could be improved. There are also other algorithms that could be added to our protocol suite. For example, it may be useful, if we could convert shares into a different PD's shares. In this thesis, we in theory separated the offline and online phase, in practice, we did not. Shamir's $k$-out-of-$n$ threshold scheme would allow to handle some \CPs disappearing or dealing with more corrupted parties. Exploring the implementation specifics of protocol interruption is an interesting topic for further research.

##### Place, publisher, year, edition, pages
Institutt for telematikk , 2014. , 84 p.
##### Identifiers
Local ID: ntnudaim:12010OAI: oai:DiVA.org:ntnu-25874DiVA: diva2:742045
##### Supervisors
Available from: 2014-08-29 Created: 2014-08-29 Last updated: 2014-08-29Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 3560 kBChecksum SHA-512
Type fulltextMimetype application/pdf
##### File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
c37935f044c9c7a7ca910ef067786ba7b80105da4b948df1e16962352a00ed530186c74729a82378d66e47bd327f37b20ec756f749e5190d7355fda818b6de81
Type coverMimetype application/pdf
##### By organisation
Department of Telematics