Change search
ReferencesLink to record
Permanent link

Direct link
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.
URN: urn:nbn:no:ntnu:diva-25874Local ID: ntnudaim:12010OAI: diva2:742045
Available from: 2014-08-29 Created: 2014-08-29 Last updated: 2014-08-29Bibliographically approved

Open Access in DiVA

fulltext(3560 kB)712 downloads
File information
File name FULLTEXT01.pdfFile size 3560 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(184 kB)8 downloads
File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Telematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 712 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link