Scientific knowledge map · Paper #31
Brief Announcement: Proactive Secret Sharing with a Dishonest Majority
2016 · ACM Symposium on Principles of Distributed Computing (PODC)
- Theory
- protocol
- scheme
Research question
What does the paper try to establish?
Can proactive secret sharing preserve a long-lived secret when passively corrupted parties may form a dishonest majority in one refresh period, while still supporting refresh and recovery in the presence of bounded active faults?
Central answer
What is the proposed answer?
The announcement encodes the secret as many random additive summands and verifiably shares those summands with polynomials of increasing degree. It then gives DM-Share, DM-Reconstruct, DM-Refresh, and DM-Recover protocols whose stated thresholds extend passive security beyond an honest majority, at the cost of synchrony, authenticated private channels, secure deletion, non-robust active security, and polynomial communication.
Evidence profile
Six dimensions, kept separate
The chart summarizes documented evidence and process. It is not a correctness probability, confidence score, or ranking, and no composite score is calculated.
LowMediumHighN/A = not assessed
A smaller value means less documented support for that dimension, not that the paper is false or unimportant.
- Epistemic evidence Medium
-
The complete brief specifies the model, construction blueprint, protocols, thresholds, and security intuition, but its three pages omit the full formal definitions and proofs. The evidence supports a medium source-grounded rating rather than a claim of complete proof verification.
Problem, claimed novelty, thresholds, and communication Additive-summand and increasing-degree polynomial blueprint DM-Recover, privacy intuition, and recovery-dependent thresholds - Auditability High
-
A checked-in author-hosted copy with recorded page count and SHA-256, together with the official DOI, makes the represented brief directly auditable. The separate full-paper proof and any immutable artifact history are outside this record.
Problem, claimed novelty, thresholds, and communication Official PODC publication record - Production provenance Medium
-
Named authorship, date, venue, official DOI, and author-hosted manuscript are documented. Contributor roles, revision history, tool use, and the exact lineage between brief and full versions have not been audited.
Official PODC publication record Problem, claimed novelty, thresholds, and communication - External scrutiny Medium
-
PODC publication establishes external venue scrutiny, but the review reports, acceptance criteria, rebuttal, independent proof checking, and reproduction history are not public in the represented sources.
Official PODC publication record - Reception Low
-
The dated index snapshot located 1 citation. Under the author-defined corpus rule, 0 through 8 located citations is Low. Counts vary by index and date and do not measure correctness.
Dated citation-count snapshot - Contribution significance Medium
-
The source claims the first dishonest-majority PSS feasibility result and clearly identifies the prior honest-majority barrier. Priority and downstream influence require a separate literature and reception audit, so significance remains medium pending author verification.
Problem, claimed novelty, thresholds, and communication Conclusion, non-robust active security, communication, and open questions
Assessment: Ai draft author review pending · 2026-07-11 · rubric 0.2. These dimensions describe documented support and process, not truth, correctness, or a universal ranking. No composite score is calculated.
Top-down and bottom-up view
Hierarchical knowledge map
Collapse a branch for a top-level reading, or follow its source links and child nodes to audit the evidence and boundaries underneath it.
Brief Announcement: Proactive Secret Sharing with a Dishonest Majority
A three-page announcement of a proactive secret-sharing construction that uses additive encoding and verifiable polynomial sharing to exceed the passive honest-majority barrier while retaining bounded recovery and active-fault guarantees.
Problem, claimed novelty, thresholds, and communication-
question Research question
research questionCan a mobile-adversary PSS scheme remain confidential when passive corruptions within one refresh period may include a dishonest majority, rather than fewer than half of the parties?
Problem, claimed novelty, thresholds, and communication -
contribution Central construction
source assertedSplit the secret into random additive summands, verifiably share each summand with a polynomial from an increasing-degree family, and refresh or recover those polynomial shares without reconstructing the secret.
Additive-summand and increasing-degree polynomial blueprint DM-Share and DM-Reconstruct -
scope Model and required environment explicitly scoped
The protocol runs among n parties in synchronized epochs over a synchronous network with authenticated broadcast and pairwise private authenticated channels; honest parties erase old shares after refresh.
Synchronous network, channels, epochs, refresh, and deletion assumptions-
threat model Mobile mixed adversary
definedThe adversary may eventually compromise all parties across the system lifetime, but the stated passive, active, and recovery-dependent thresholds must hold within each refresh period.
Problem, claimed novelty, thresholds, and communication Synchronous network, channels, epochs, refresh, and deletion assumptions -
assumption Communication and reset assumptions
assumedSynchrony, a global clock, authenticated broadcast, private authenticated channels, restoration to a pristine state, and deletion of obsolete shares are environmental assumptions rather than guarantees constructed by this scheme.
Synchronous network, channels, epochs, refresh, and deletion assumptions -
assumption Verifiability assumption
computational assumptionActive-fault checking uses homomorphic commitments instantiated in the announcement by Feldman VSS, whose hiding/security properties rely on discrete-log hardness over the selected field group.
Secret sharing, verifiable sharing, proactive refresh, recovery, and discrete-log commitment assumption
-
-
method Four-protocol PSS construction specified
DM-Share, DM-Reconstruct, DM-Refresh, and DM-Recover jointly implement sharing, reconstruction, proactive rerandomization, and replacement of shares lost by rebooted or faulty parties.
DM-Share and DM-Reconstruct DM-Refresh and preservation of the shared secret DM-Recover, privacy intuition, and recovery-dependent thresholds-
method Additive encoding with increasing degrees
specifiedDM-Share writes s as the sum of n random summands and verifiably shares the summands with polynomials whose degrees increase across the family; reducing the maximum degree reserves interpolation capacity for share recovery.
Additive-summand and increasing-degree polynomial blueprint DM-Share and DM-Reconstruct -
protocol DM-Refresh
specifiedEach party verifiably distributes a family of random refreshing polynomials whose constant terms sum to zero; adding their evaluations rerandomizes every local share while preserving the encoded secret, after which old shares are deleted.
DM-Refresh and preservation of the shared secret -
protocol DM-Recover
specifiedNon-recovering parties mask their current polynomial shares with random polynomials that vanish at the recovering party's point, allowing that party to interpolate only its replacement shares rather than the secret or current sharing polynomials.
DM-Recover, privacy intuition, and recovery-dependent thresholds
-
-
claim group Stated guarantees source asserted
The announcement states separate thresholds for passive corruption, active corruption, mixed corruption, lost-share recovery, and batched communication; these guarantees are not interchangeable.
Problem, claimed novelty, thresholds, and communication Conclusion, non-robust active security, communication, and open questions-
claim Passive dishonest-majority confidentiality
claimed with protocol intuitionWithout lost-share recovery, the paper states confidentiality for t < n passive corruptions in a refresh period; with e simultaneous lost shares or faults, the stated passive threshold becomes t < n - e.
Problem, claimed novelty, thresholds, and communication DM-Recover, privacy intuition, and recovery-dependent thresholds Conclusion, non-robust active security, communication, and open questions -
claim Active and mixed corruption bounds
claimed non robustThe non-robust construction states security for t < n/2 - e active corruptions and for mixed adversaries whose total may be a majority provided fewer than n/2 - e corruptions are active; detected cheating may cause abort.
Problem, claimed novelty, thresholds, and communication Conclusion, non-robust active security, communication, and open questions -
claim Communication cost
asymptotic claimThe announcement reports O(n^4) communication for one secret and O(n^3) communication when multiple secrets are batched; it leaves lower communication for dishonest-majority PSS open.
Problem, claimed novelty, thresholds, and communication Conclusion, non-robust active security, communication, and open questions
-
-
evidence group Evidence and proof boundary bounded by brief announcement
The three-page source specifies the model, encoding blueprint, and protocol mechanisms and gives security intuition, but it does not contain the full definitions, games, lemmas, or complete proofs of the corresponding SCN paper.
Secret sharing, verifiable sharing, proactive refresh, recovery, and discrete-log commitment assumption Additive-summand and increasing-degree polynomial blueprint DM-Recover, privacy intuition, and recovery-dependent thresholds-
evidence Mechanism-level support
construction inspectedThe source explains why additive summands resist passive reconstruction, why zero-sum refresh polynomials preserve the secret, and why vanishing recovery masks reveal only the recovering party's replacement evaluations.
Additive-summand and increasing-degree polynomial blueprint DM-Refresh and preservation of the shared secret DM-Recover, privacy intuition, and recovery-dependent thresholds
-
-
limitation group Limitations and open obligations material
The active guarantee is non-robust, thresholds decrease with parallel recovery, the scheme assumes synchrony and secure erasure, and the brief leaves complete proofs and optimal communication outside its three pages.
Synchronous network, channels, epochs, refresh, and deletion assumptions DM-Recover, privacy intuition, and recovery-dependent thresholds Conclusion, non-robust active security, communication, and open questions-
limitation Open communication and asynchrony questions
open problemThe authors ask whether batched communication can fall below O(n^3) and note that no construction in the represented work attains dishonest-majority security up to n - 1 over asynchronous networks.
Conclusion, non-robust active security, communication, and open questions
-
-
artifact group Publication resources
publicly availableThe complete brief announcement is checked into this site with recorded fixity, and the ACM DOI provides the official publication identity; no code or executable artifact is claimed by the paper.
Problem, claimed novelty, thresholds, and communication Official PODC publication record -
scrutiny External scrutiny
venue reviewedThe construction appeared as a PODC brief announcement. That establishes venue exposure but is not equivalent to a full-paper proof audit, independent reproduction, or public review report.
Official PODC publication record -
lineage Relation to the full construction
documentedThis announcement is the compressed PODC presentation of the dishonest-majority PSS direction; the separate SCN paper contains the extended construction and proof treatment and must be mapped independently as paper #32.
Problem, claimed novelty, thresholds, and communication Conclusion, non-robust active security, communication, and open questions
Audit trail
Source index
Locators state the depth of the current audit. PDF page numbers, where present, are one-based file pages; metadata-, summary-, and abstract-bounded records explicitly identify their limitations.
- Problem, claimed novelty, thresholds, and communication Abstract and Section 1, PDF page 1
- Synchronous network, channels, epochs, refresh, and deletion assumptions Sections 2.1 and Time Periods and Refresh Phases, PDF pages 1-2
- Secret sharing, verifiable sharing, proactive refresh, recovery, and discrete-log commitment assumption Section 2.2, PDF page 2
- Additive-summand and increasing-degree polynomial blueprint Section 3.1, PDF page 2
- DM-Refresh and preservation of the shared secret Section 3.3, PDF page 3
- DM-Recover, privacy intuition, and recovery-dependent thresholds Section 3.4, PDF page 3
- Conclusion, non-robust active security, communication, and open questions Section 4, PDF page 3
- Official PODC publication record ACM PODC 2016, DOI 10.1145/2933057.2933059
- Dated citation-count snapshot SciSpace listing reported 1 citation when accessed 2026-07-11