A Fast Publicly Verifiable Secret Sharing Scheme using Non-homogeneous Linear Recursions

A non-interactive (t,n)-publicly veriable secret sharing scheme (non-interactive (t,n)-PVSS scheme) is a (t,n)-secret sharing scheme in which anyone, not only the participants of the scheme, can verify the correctness of the produced shares without interacting with the dealer and participants. The (t,n)-PVSS schemes have found a lot of applications in cryptography because they are suitable for real-life scenarios in which an external verifier is required to check the correctness of the produced shares without interacting with the dealer and participants. In this paper, we propose a non-interactive (t,n)-PVSS scheme using the non-homogeneous linear recursions (NHLRs), and prove its security with a formal method. We compare the computational complexity of our scheme with that of Schoenmakers's scheme and show that our non-interactive (t,n)-PVSS scheme runs faster than Schoenmakers's scheme when n > 5 and n> t >(2n+9)/n. The communicational complexity of our scheme is almost equal to that of Schoenmakers's scheme.