Paper 2021/871

Traceable Secret Sharing and Applications

Vipul Goyal, Yifan Song, and Akshayaram Srinivasan


Consider a scenario where Alice stores some secret data $s$ on $n$ servers using a $t$-out-of-$n$ secret sharing scheme. Trudy (the collector) is interested in the secret data of Alice and is willing to pay for it. Trudy publishes an advertisement on the internet which describes an elaborate cryptographic scheme to collect the shares from the $n$ servers. Each server who decides to submit its share is paid a hefty monetary reward and is guaranteed ``immunity" from being caught or prosecuted in a court for violating its service agreement with Alice. Bob is one of the servers and sees this advertisement. On examining the collection scheme closely, Bob concludes that there is no way for Alice to prove anything in a court that he submitted his share. Indeed, if Bob is rational, he might use the cryptographic scheme in the advertisement and submit his share since there are no penalties and no fear of being caught and prosecuted. Can we design a secret sharing scheme which Alice can use to avoid such a scenario? We introduce a new primitive called as Traceable Secret Sharing to tackle this problem. In particular, a traceable secret sharing scheme guarantees that a cheating server always runs the risk of getting traced and prosecuted by providing a valid evidence (which can be examined in a court of law) implicating its dishonest behavior. We explore various definitional aspects and show how they are highly non-trivial to construct (even ignoring efficiency aspects). We then give an efficient construction of traceable secret sharing assuming the existence of a secure two-party computation protocol. We also show an application of this primitive in constructing traceable protocols for multi-server delegation of computation.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
Secret SharingTraitor TracingTraceable Secret SharingDelegation
Contact author(s)
goyal @ cs cmu edu
yifans2 @ andrew cmu edu
akshayaram srinivasan @ tifr res in
2021-06-29: received
Short URL
Creative Commons Attribution


      author = {Vipul Goyal and Yifan Song and Akshayaram Srinivasan},
      title = {Traceable Secret Sharing and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/871},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.