Proactive Secret Sharing Schemes with Different Security Levels

• Main Authors: BAO, Feng, DENG, Robert H.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2000
• Subjects: cryptography; distributed computing; secret sharing; Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/1112
• Institution: Singapore Management University

Secret sharing schemes protect a secret by distributing the shares of the secret over different locations (share-holders). Recently, Proactive Secret Sharing (PSS) was introduced [11] to protect long-lived secrets in the presence of corrupted share-holders. In a PSS scheme, the life-time of a secret is divided into multiple periods, and the shares are periodically renewed so that the secret is protected even if every share-holder may be corrupted in some periods but no more than t share-holders are corrupted in each single period. In this paper, we consider PSS schemes in a different model from the one used in [11]. This model makes it possible to study the different levels of the security of PSS. We first show that there is an information-theoretically secure (i.e., both unconditional secrecy and unconditional resilience) PSS scheme with exponential complexity. We then present two PSS schemes with polynomial complexity - the first one has unconditional resilience but conditional secrecy; while the second one has unconditional secrecy but conditional resilience. We conjecture that there does not exist any information-theoretically secure PSS schemes with polynomial complexity.