Karim Eldefrawy

Cryptography, Cybersecurity, Privacy

Co-founder and CTO at Confidencial.io
2017-2021: SRI
2011-2016: HRL Laboratories
2006-2010: PhD@UC Irvine

Scientific curiosity

Scientific knowledge map · Paper #31

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

Shlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky, and Moti Yung

2016 · ACM Symposium on Principles of Distributed Computing (PODC)

  • Theory
  • protocol
  • scheme

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?

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.

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.

The visual spider chart requires JavaScript. The complete values and rationales follow in text.

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.

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.

paper

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
  1. question

    Research question

    research question

    Can 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
  2. 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
  3. 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
    1. protocol

      DM-Refresh

      specified

      Each 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
    2. protocol

      DM-Recover

      specified

      Non-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
  4. 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
  5. 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
  6. 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
  7. scrutiny

    External scrutiny

    venue reviewed

    The 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

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.

  1. Problem, claimed novelty, thresholds, and communication Abstract and Section 1, PDF page 1
  2. Synchronous network, channels, epochs, refresh, and deletion assumptions Sections 2.1 and Time Periods and Refresh Phases, PDF pages 1-2
  3. Secret sharing, verifiable sharing, proactive refresh, recovery, and discrete-log commitment assumption Section 2.2, PDF page 2
  4. Additive-summand and increasing-degree polynomial blueprint Section 3.1, PDF page 2
  5. DM-Share and DM-Reconstruct Section 3.2, PDF pages 2-3
  6. DM-Refresh and preservation of the shared secret Section 3.3, PDF page 3
  7. DM-Recover, privacy intuition, and recovery-dependent thresholds Section 3.4, PDF page 3
  8. Conclusion, non-robust active security, communication, and open questions Section 4, PDF page 3
  9. Official PODC publication record ACM PODC 2016, DOI 10.1145/2933057.2933059
  10. Dated citation-count snapshot SciSpace listing reported 1 citation when accessed 2026-07-11