## 2 Background and Related Work
### Verifiable Secret Sharing (VSS)  
Earlier secret sharing schemes, including the above-mentioned Shamir's Secret Sharing and Blakley's Secret Sharing, share one common hypothesis, which is that the dealer and the players of the secret are honest. However, it is not always realistic for the employment of secret sharing in the real world. Therefore, one secure secret sharing scheme for the purpose of cryptography should put the participants in an adversarial position and try to imagine what would happen if they jump out of the rules and stray away from the instructions. The security concerns of earlier secret sharing schemes mainly come from two directions: adversary dealer and malicious player. First, the dealer is possible to distribute maliciously tampered shares or even random information as pieces of shares instead of truly split shares. The players cannot figure out the impossibility of reconstruction until they try to perform the task of reconstruction. The other main problem is that when one or more players contribute the incorrect share \(\hat{D}_{i}\
eq D_{i}\), the reconstruction of the polynomial will be a failure (taking Shamir's Secret Sharing as the example). Even worse, if \(n-k\) or more players refuse to contribute their shares, the reconstruction cannot be continued.  
[PERSON] et al. proposed the conception of Verifiable Secret Sharing [13]. Same as earlier secret sharing schemes, there are two stages in the protocol of VSS: distribution stage and reconstruction. However, to make the shares verifiable, extra commitments for verification must be provided. Informally, the VSS has two requirements as follows [14]:  
1. Verifiability constraint: upon receiving a piece of secret share, a player must be able to validate the piece. If \(k\) or more (\(k\) for threshold) pieces of a secret share are valid, there exists one unique result for the reconstruction of the original secret.
2. Unpredictability: there is no polynomial-time strategy for picking less than \(k\) pieces of shares such that they can be used to predict the original secret.  
From the perspective of interactions between players and the interactions between dealers and players, the VSS can be divided into interactive ones and non-interactive ones. The first work on VSS proposed by [PERSON] et al. belongs to the type of interactive verifiable secret sharing, which is based on the difficulty of factorization of large numbers and oblivious transfer. [PERSON] et al. proposed their work based on a zero-knowledge proofs system and one-way function, and the system can be used to build an interactive verifiable secret sharing scheme [14].  
[PERSON] presented an efficient noninteractive protocol for VSS [14] based on Shamir's Secret Sharing and the discrete logarithm problem in finite fields, which can tolerate up to \((n-1)/2\) dishonest players. According to the paper's definition, a VSS is non-interactive if there exists a polynomial-time algorithm that verifies the validity of the pieces. In [15], [PERSON] presented a commitment solution with the property of homomorphism and then one non-interactive VSS based on Lagrange interpolation. His solution has demonstrated and established three important features for the later VSS research: (1) if the dealer is honest, then all honest players can determine one unique polynomial of degree \(k-1\) (\(k\) for threshold); (2) any subset of \(k\) valid pieces of the secret share can be used for the reconstruction, even if there exist some malicious players; (3) no set of, at most, \(k-1\) players obtain any information about the secret. [PERSON] et al. [16] proposed one solution of VSS with a simple structure based on fast cryptographic primitives so as to avoid the high cost on the zero-knowledge proofs, and then the efficiency of secret sharing has a huge improvement.