Paper 2006/449

Robust Computational Secret Sharing and a Unified Account of Classical Secret-Sharing Goals

Mihir Bellare and Phillip Rogaway


We give a unified account of classical secret-sharing goals from a modern cryptographic vantage. Our treatment encompasses perfect, statistical, and computational secret sharing; static and dynamic adversaries; schemes with or without robustness; schemes where a participant recovers the secret and those where an external party does so. We then show that Krawczyk's 1993 protocol for robust computational secret sharing (RCSS) need not be secure, even in the random-oracle model and for threshold schemes, if the encryption primitive it uses satisfies only one-query indistinguishability (ind1), the only notion Krawczyk defines. Nonetheless, we show that the protocol is secure (in the random-oracle model, for threshold schemes) if the encryption scheme also satisfies one-query key-unrecoverability (key1). Since practical encryption schemes are ind1+key1 secure, our result effectively shows that Krawczyk's RCSS protocol is sound (in the random-oracle model, for threshold schemes). Finally, we prove the security for a variant of Krawczyk's protocol, in the standard model and for arbitrary access structures, assuming ind1 encryption and a statistically-hiding, weakly-binding commitment scheme.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
secret sharing
Contact author(s)
rogaway @ cs ucdavis edu
2007-08-20: revised
2006-12-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Phillip Rogaway},
      title = {Robust Computational Secret Sharing and a Unified Account of Classical Secret-Sharing Goals},
      howpublished = {Cryptology ePrint Archive, Paper 2006/449},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.