Secret Sharing

Summary

Secret sharing is a method for distributing a secret among \(n\) parties so that only authorized subsets can reconstruct it. First introduced independently by Shamir [1] (polynomial-based) and Blakley [2] (geometric, based on hyperplane intersections) in 1979. (Source: [3])

Types

By construction

  • Shamir Secret Sharing \((n,t)\) threshold scheme based on polynomial interpolation over a finite field.
  • Additive Secret Sharing $n$-out-of-\(n\) scheme requiring only an abelian group. Special case of Shamir with \(t = n\).
  • CRT-Secret Sharing Based on the Chinese Remainder Theorem. First introduced by [4].
  • Blakley's scheme : Geometric construction using hyperplane intersections [2].

By access structure

  • Ramp Secret Sharing \((k,d,n)\) scheme where fewer than \(k\) shares reveal nothing, more than \(d\) reveal the secret, and between \(k\) and \(d\) may leak partial information [5].
  • Packed Secret Sharing Shares multiple secrets simultaneously in a single polynomial. Introduced by [6].

By additional properties

  • Homomorphic Secret Sharing Shares support computation (e.g., addition, multiplication) without reconstruction.
  • Verifiable Secret Sharing (VSS) - Shareholders can verify consistency of their shares. (Chor, Gennaro IKR - Round complexity of VSS)
  • Publicly Verifiable Secret Sharing (PVSS) - Anyone, not just shareholders, can verify correct distribution. (Heidervand et al.)
  • Proactive Secret Sharing - Shares are periodically refreshed so an adversary must corrupt \(t\) parties within a single epoch.
  • Asynchronous Proactive Secret Sharing (APSS) - Proactive secret sharing in an asynchronous network. (Zhou et al.)
  • Asynchronous Verifiable Secret Sharing (AVSS) - VSS in an asynchronous network. (Cachin - Async VSS and proactive cryptosystems)

Bounds and Results

  • For any sharp threshold secret sharing scheme, irrespective of whether it is linear or non-linear, each share size must be at least as long as the secret. ([7], learnt from [8])

References

[1] Adi Shamir. 1979. “How to share a secret.” https://dl.acm.org/doi/10.1145/359168.359176.
[2] G. R. Blakley. 1979. “Safeguarding cryptographic keys.” https://www.computer.org/csdl/proceedings-article/afips/1979/50870313/12OmNCeK2a1.
[3] Michael Backes, Aniket Kate, and Arpita Patra. 2011. “Computational Verifiable Secret Sharing Revisited.” http://link.springer.com/10.1007/978-3-642-25385-0_32.
[4] Oded Goldreich, Dana Ron, and Madhu Sudan. 1999. “Chinese remaindering with errors.” https://dl.acm.org/doi/10.1145/301250.301309.
[5] G. Blakley, and Catherine Meadows. 1984. “Security of Ramp Schemes.”
[6] Matthew Franklin, and Moti Yung. 1992. “Communication complexity of secure computation (extended abstract).” http://portal.acm.org/citation.cfm?doid=129712.129780.
[7] R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro. 1993. “On the size of shares for secret sharing schemes.” https://doi.org/10.1007/BF00198463.
[8] Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, and Mingyuan Wang. 2024. “Scalable Multiparty Computation from Non-linear Secret Sharing.”