Password-Protected Secret Sharing

摘要

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 than existing T-PAKE's.