Rafail Ostrovsky - Publications

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

Shlomi Dolev, Karim EIDefrawy, Joshua Lampkins


In a secret sharing scheme a dealer shares secret s among n parties such that adversary corrupting up to t parties does not learn s, while any t + 1parties can efficiently recover s. Over a long period of time all parties may be corrupted thus violating the threshold, which is accounted for in Proactive Secret Sharing (PPS). PPS schemes periodically randomize (refresh) the shares of the secret and invalidate old ones. PPS retains confidently even when all parties are corrupted over the lifetime of the secret, but no more than during a certain window if time, called thee refresh period. Existing PPSschemes only guarantee secrecy in the presence of an honest majority with less than n=2 total corruption during a refresh period; and adversary corrupting a single additional party, even if only passively, obtains the secret. This work is the First Feasibility result demonstrating PPS tolerating a dishonest majority,It introduces the first PPS scheme secure against t< n passive adversaries without recovery of lost shares&$44; it can also recover from honest faculty parties losing their shares, and when tolerating e passive corruptions. A non–robust version f the scheme can tolerate t< n/2–e active adversaries, and mixed adversaries that control a combination of passively and actively corrupted parties that are majority, but where less these than n/2–e of such corruptions are active. We achieve these high thresholds with Ο(/n4) communication when sharing a single secret , and Ο(/n3) Communication when sharing multiple secrets in batches.

comment: PODC 2016 PP: 401–403

Fetch PDF file of the paper

Back to Publications List