**Password-Protected Secret Sharing**

*Stanislaw Jarecki and Ali Bagherzandi and Nitesh Saxena and Yanbin Lu*

**Abstract: **We revisit the problem of protecting user's private data against
adversarial compromise of user's device(s) which would normally store
this data. We formalize an attractive solution to this problem as
Password-Protected Secret-Sharing (PPSS), which is a protocol
that allows a user to secret-share her data among n trustees in such
a way that (1) the user can retrieve the shared secret upon entering a
correct password into a reconstruction protocol which succeeds as long
as at least t+1 honest trustees participate, and (2) the shared data
remains secret even against the adversary which corrupts at most t
servers, with the level of protection expected of
password-authentication, i.e. the probability that the adversary
learns anything useful about the secret is at most negligibly greater
than q/|D| where q is the number of reconstruction protocol
instances in which adversary engages and |D| is the size of the
dictionary from which the password was randomly chosen.

We propose an efficient PPSS protocol in the public key model, i.e. where the device can remember a trusted public key, provably secure under the DDH assumption, using non-interactive zero-knowledge proofs which are efficiently instantiatable in the Random Oracle Model (ROM). The resulting protocol is robust and practical, with fewer than $4t+12$ exponentiations per party, and with only three messages exchanged between the user and each server, implying a single round of interaction in the on-line phase. As a side benefit our PPSS protocol yields a new Threshold Password Authenticated Key Exchange (T-PAKE) protocol in the public key model which is significantly faster than existing T-PAKE's provably secure in the public key model in ROM.

**Category / Keywords: **cryptographic protocols / Secret Sharing; Intrusion Tolerance; Password Authentication

**Publication Info: **not published before, under conference submission

**Date: **received 3 Nov 2010, last revised 5 Nov 2010

**Contact author: **stasio at ics uci edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20101105:211652 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]