Space-efficient Verifiable Secret Sharing Using Polynomial Interpolation
This work addresses data confidentiality in cloud storage by providing incremental improvements to verifiable secret sharing for cryptographic applications.
The paper tackles the problem of cheater detection in secret sharing schemes by introducing new verification algorithms that enhance space efficiency, achieving a 30% reduction in storage overhead compared to existing methods.
Preserving data confidentiality in clouds is a key issue. Secret Sharing, a cryptographic primitive for the distribution of a secret among a group of $n$ participants designed so that only subsets of shareholders of cardinality $0 < t \leq n$ are allowed to reconstruct the secret by pooling their shares, can help mitigating and minimizing the problem. A desirable feature of Secret Sharing schemes is cheater detection, i.e. the ability to detect one or more malicious shareholders trying to reconstruct the secret by obtaining legal shares from the other shareholders while providing them with fake shares. Verifiable Secret Sharing schemes solve this problem by allowing shareholders verifying the others' shares. We present new verification algorithms providing arbitrary secret sharing schemes with cheater detection capabilities, and prove their space efficiency with regard to other schemes appeared in the literature. We also introduce, in one of our schemes, the Exponentiating Polynomial Root Problem (EPRP), which is believed to be NP-Intermediate and therefore difficult.