A Novel Threshold Secret Sharing Scheme Using FFT Algorithm

Abstract

Secret sharing schemes (SSS) are very important, because they are used in critical applications, such as e-voting, cryptographic key distribution and sharing, secure online auctions, information hiding, and secure multiparty computation. We explained some popular algorithms of SSS and their access structures, threshold, graph, and visual schemes. Besides, we discussed the limitations of these available schemes. Additionally, we proposed a novel threshold secret sharing scheme based on Fast Fourier Transform (FFT) algorithm, which is introduced for the first time in this paper in the field of secret sharing. That is, we exploited the robust characteristics of FFT such as linearity, reversibility, efficiency, that has time complexity of O(nlogn) , and it provided us with wider field, complex numbers. The scheme introduced ideal; the shares’ size smaller than the secret, and very secure because it depends on solving linear system of equations generated by FFT that has become impossible with hiding some variables.  Thus, Our SSS combines the merits of Shamir and Blakley schemes.

Keywords

• Secret sharing, secret hiding, FFT algorithm, linear algebra

F AF: AA for all AF{ }}. A

Abstract