Cryptology ePrint Archive: Report 2010/561

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 formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Discussion forum: Show discussion | Start new discussion