Cryptanalysis of Shamir's secret sharing scheme under two cases of implementation

Date of Publication

2015

Document Type

Master's Thesis

Degree Name

Master of Science in Mathematics

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Ederlinda G. Nocon

Abstract/Summary

Shamir's Secret Sharing Scheme (SSSS) is one of the rst secret sharing schemes. It was invented by Shamir in 1979 and uses the idea of polynomial interpolation. There are two ways in which the shares can be revealed- synchronously or asynchronously. In synchronous sharing, shares are revealed by the participants at the same time, while in asynchronous sharing, shares are revealed one at a time. Tompa and Woll (1989) however showed that a single cheater can successfully cheat if shares are revealed asynchronously by revealing his or her share after all other participants have revealed their shares. Harn, Lin and Li (2015) also mentioned that in general, a secret sharing scheme and not just SSSS can be cheated by a single cheater using the same strategy when shares are revealed asynchronously. No analysis on synchronous sharing however was made. As for asyn- chronous sharing, the instance where a single cheater does not reveal his/her share last was not considered. In all existing analysis on SSSS, only single cheaters were considered, and collaborations and multiple cheaters were not considered. This paper aims to bridge this gap in the literature by performing cryptanalysis on SSSS by testing it against four types of attack under two cases of implementation. The attacks are mostly taken from Harn and Lin's paper in 2009, but certain adjustments were made in our study. We discuss two cases. In the rst case, both the shares and the secret are revealed. In this case, we were able to show that when there are two or more cheaters, or two or more groups who will cheat, certain conditions must be met so that no one can know what the true secret is. In the second case, only the secret is revealed to the participants. In this case, we were able to show that no one can verify whether the secret is true or not, but when there is one cheater, or when there is one group of cheaters, then the key they will compute for is 1 the true key. In our proofs, we have shown that what is critical in cheating SSSS is the knowledge of the shares, and not the order in which shares were revealed.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG006613

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

1 computer optical disc ; 4 3/4 in.

Keywords

Cryptography

This document is currently not available here.

Share

COinS