In some papers, they just wrote that proactive secret sharing scheme is a secret sharing scheme which its shares are periodically updated. Does it have formal definition ?

  • Can you link some of these papers? – nope Aug 19 '17 at 3:21

Proactive secret sharing schemes are typically used for multi-party computation variously referred to as "Secure computation" or simply MPC that arose from the work of Yao and Goldreich, Micali and Wigderson (GMW) in the 80s. MPC's require secrets to be shared among multiple parties, and some of these parties may be controlled by an adversary that is in the most general setting able to deviate from the specified protocol in a "byzantine" manner. As a concrete case, in the GMW protocol with $n$ parties, in order for the $i$th party to share its bit $b_{i} \in \{0,1\}$ with the other $n - 1$ parties, she generates $n - 1$ i.i.d uniformly random bits and sends one of the generated bits to each of the parties. She then sets her share of $b_{i}$ such that the sum of her share and the other $n - 1$ bits mod 2 gives back the original bit $b_{i}$. This sharing scheme is "perfectly" secure since there is no complexity assumption. In the classic MPC model, it is assumed that the parties controlled by the adversary are determined beforehand and remain fixed during the course. This is sometimes called static corruption.

In the early 90s, Ostrovsky and Yung ("How to Withstand Mobile Virus Attacks", In PODC, pages 51–59) described settings where the adversary is allowed to control a varying number of parties throughout the computation and corrupt additional parties that may have been intact at the onset of the protocol. This is typically called dynamic corruption, and protos that are able to remain secure in this setting are sometimes called proactively secure. In this model, "proactive" security property stems primarily from the fact that secrets shared among the parties are periodically re-randomized through a sharing scheme, called a proactively secure secret sharing scheme (PSS).

I should note that the original Ostrovsky and Yung paper from 1991 does not explicitly use the term proactive secret sharing, but this term is used in a 2014 rework of the '91 paper ("How to withstand mobile virus attacks, revisited" by Baron, El-Defrawey, Lampkins and Ostrovsky [BELO14]). The "Block-Redistribute" aspect of the protocol forms the core part of the PSS scheme in the [BELO14] MPC, but it's presented as a specification rather than a formal definition. As such, I have not found a succinct formal definition for "proactive secret sharing". What you may ask for, on the other hand, is a definition of what it means for a MPC to be proactively secure rather than strictly a definition of the term "proactive secret sharing". If that's the case, the definitions in [BELO14] sec. 2.1 " The Proactive Model under the UC Framework" are helpful.

One formal definition I came across is the Definition 3 of

  • 2
    We aim to have comprehensive answers that are self-contained on this site. This a link-only answer, what happens if/when the link dies or changes? Can you please incorporate a summary and/or explanation of the relevant contents of the link? – Ella Rose Nov 8 at 17:24

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.