Paper 2010/561

Password-Protected Secret Sharing

Stanislaw Jarecki, Ali Bagherzandi, 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.