Cryptology ePrint Archive: Report 2017/363

TOPPSS: Cost-minimal Password-Protected Secret Sharing based on Threshold OPRF

Stanislaw Jarecki and Aggelos Kiayias and Hugo Krawczyk and Jiayu Xu

Abstract: We present TOPPSS, the most efficient Password-Protected Secret Sharing (PPSS) scheme to date. A (t; n)-threshold PPSS, introduced by Bagherzandi et al, allows a user to share a secret among n servers so that the secret can later be reconstructed by the user from any subset of t+1 servers with the sole knowledge of a password. It is guaranteed that any coalition of up to t corrupt servers learns nothing about the secret (or the password). In addition to providing strong protection to secrets stored online, PPSS schemes give rise to efficient Threshold PAKE (T-PAKE) protocols that armor single-server password authentication against the inherent vulnerability to offline dictionary attacks in case of server compromise.

TOPPSS is password-only, i.e. it does not rely on public keys in reconstruction, and enjoys remarkable efficiency: A single communication round, a single exponentiation per server and just two exponentiations per client regardless of the number of servers. TOPPSS satis es threshold security under the (Gap) One-More Diffie-Hellman (OMDH) assumption in the random-oracle model as in several prior efficient realizations of PPSS/TPAKE. Moreover, we show that TOPPSS realizes the Universally Composable PPSS notion of Jarecki et al under a generalization of OMDH, the Threshold One-More Diffie-Hellman (T-OMDH) assumption. We show that the T-OMDH and OMDH assumptions are both hard in the generic group model.

The key technical tool we introduce is a universally composable Threshold Oblivious PRF which is of independent interest and applicability.

Category / Keywords:

Original Publication (with major differences): Applied Cryptography and Network Security (ACNS) 2017

Date: received 21 Apr 2017, last revised 24 Apr 2017

Contact author: stanislawjarecki at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170426:175121 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]