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

• Main Author: Tieng, Deneisha Gayle
• Format: text
• Language: English
• Published: Animo Repository 2015
• Subjects: Cryptography; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/5075
• Institution: De La Salle University

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.