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

Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, 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 optimisation.

IEEE EURO S&P 2016. For the full paper visit https://eprint.iacr.org/2016/144

[BJSL10] A. Bagherzandi, S. Jarecki, N. Saxena, and Y. Lu. Password- protected secret sharing. In ACM Conference on Computer and Communications Security, pp. 433-444, 2011,
[CLLN14] J. Camenisch, A. Lehmann, A. Lysyanskaya, and G. Neven. Me- mento: How to reconstruct your secrets from a single password in a hostile environment. In Crypto’2014, pp. 256–275,
[JKK14] S. Jarecki, A. Kiayias, and H. Krawczyk. Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model. In pt’2014, pp. 233–253.