A Verifiable Multi-Secret Sharing Scheme Based on Short Integer Solution

With the possible birth of the quantum computer, traditional secret sharing schemes have been unable to meet security requirements. We proposed a new verifiable multi-secret sharing scheme based on the short integer solution problem. By utilizing a symmetric binary polynomial, ${\boldsymbol{k}}$ secrets and secret shares can be generated, and then we convert the secret shares into binary string on $\mathbb{Z}_{\boldsymbol{q}}$ , which can be identified by one-way anti-collision hash function on the lattice, so that multiple secrets can be reconstructed safely. The advantages mainly focus on verifiability without interaction in the distribution phase and less memory requirement. In a secret sharing scheme, verifiability prevents the dealer to share the wrong shares and forces the participants to submit their shares correctly. Meanwhile, the interaction can be reduced, which means the security is improved. In a multi-secret sharing scheme, releasing the public values is inevitable, this paper has less public values and less size of shares per secret size to reduce the pressure of memory consumption in the proper parameters. In the end, it can also effectively resist the quantum attack.