Cryptology ePrint Archive: Report 2016/144

Highly-Efficient and Composable Password-Protected Secret Sharing (Or: How to Protect Your Bitcoin Wallet Online)

Stanislaw Jarecki and Aggelos Kiayias and Hugo Krawczyk and Jiayu Xu

Abstract: PPSS is a central primitive introduced by Bagherzandi et al [BJSL10] which allows a user to store a secret among n servers such that the user can later reconstruct the secret with the sole possession of a single password by contacting t+1 servers for t<n. At the same time, an attacker breaking into t of these servers - and controlling all communication channels - learns nothing about the secret (or the password). Thus, PPSS schemes are ideal for on-line storing of valuable secrets when retrieval solely relies on a memorizable password.

We show the most efficient Password-Protected Secret Sharing (PPSS) to date (and its implied Threshold-PAKE scheme), which is optimal in round communication as in Jarecki et al [JKK14] but which improves computation and communication complexity over that scheme requiring a single per-server exponentiation for the client and a single exponentiation for the server. As with the schemes from [JKK14] and Camenisch et al [CLLN14], we do not require secure channels or PKI other than in the initialization stage.

We prove the security of our PPSS scheme in the Universally Composable (UC) model. For this we present a UC definition of PPSS that relaxes the UC formalism of [CLLN14] in a way that enables more efficient PPSS schemes (by dispensing with the need to extract the user's password in the simulation) and present a UC-based definition of Oblivious PRF (OPRF) that is more general than the (Verifiable) OPRF definition from [JKK14] and is also crucial for enabling our performance optimization.

Category / Keywords: cryptographic protocols / password authentication, secret-sharing, threshold cryptosystems

Original Publication (in the same form): 1st IEEE European Symposium on Security and Privacy, EuroS&P, 2016

Date: received 16 Feb 2016, last revised 16 Feb 2016

Contact author: stanislawjarecki at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160216:211308 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]