Abstract or Summary:
We revisit the problem of protecting user's private data against adversarial compromise of user's device(s) which store this data. We formalize the solution we propose as Password-Protected Secret-Sharing (PPSS), which 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 uncorrupted trustees are accessible, and (2) the shared data remains secret even if the adversary which corrupts t trustees, 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 q/|D| where q is the number of reconstruction protocol the adversary manages to trigger and |D| is the size of the password dictionary. We propose an efficient PPSS protocol in the PKI model, secure under the DDH assumption, using non-interactive zero-knowledge proofs with efficient instantiations in the Random Oracle Model. Our protocol is practical, with fewer than 16 exponentiations per trustee and 8t+17 exponentiations per user, with O(1) bandwidth between the user and each trustee, and only three message flows, 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 PKI model with significantly lower message, communication, and server computation complexities then existing T-PAKE's.

PasswordResearch.com Note: Second link may be to an earlier version of the paper before it was published.