Proactive Secret Sharing with a Dishonest Majority
Shlomi Dolev, Karim EIDefrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung
Abstract:
In standard Secret Sharing (SS ) a dealer shares a secret s amon n parties such that an adversary corrupting no more than t parties does not learn s , while any t +1 parties can efficiently recover s. Over a long period of time all parties may be corrupted and the threshold t may be violated&3919; which is accounted for in Proactive Secret Sharing (PSS). PSS retains confidentiality even when a mobile adversary corrupts all parties over the lifetime of the secret, but no more than a threshold t during a certain window of time , called the refresh period. Existing PSS schemes only guarantee secrecy in the presence of an honest majority with at most n/2 –1 total corruptions during such a refresh period; an adversary that corrupts a single additional party beyond the n/2–1 threshold, even if only passively and only temporarily, obtains the secret. We develop the first PSS scheme secure in the presence of a dishonest majority . Our PSS scheme is robust and secure against t<n–2 passive adversaries when there are no active corruptions , and secure but non-robust (but with identifiable aborts) against t< n/2–1 active adversaries when there are no additional passive corruptions. The scheme is also secure ( with identifiable aborts) against mixed adversaries controlling a combination of passively and actively corrupted parties such that if there are k active corruptions there are less than n–k–2 total corruptions. Our scheme achieves these high thresholds with ο(n4) communication when sharing a single secret. We also observe that communication may be reduced to ο(n3) when sharing ο(n) secrets in batches. Our work is the first result demonstrating that PSS tolerating such high threshold and mixed adversaries is possible.
comment: SCN 2016 PP: 529–548
Fetch PDF file of the paper
| Back to Publications List |