Paper 2017/363

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

Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, and Jiayu Xu


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 satises 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.

Note: fixed some presentation issues in a proof

Available format(s)
Publication info
Published elsewhere. MAJOR revision.ACNS 2017
Contact author(s)
jiayux @ uci edu
2019-06-02: last of 4 revisions
2017-04-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Stanislaw Jarecki and Aggelos Kiayias and Hugo Krawczyk and Jiayu Xu},
      title = {TOPPSS: Cost-minimal Password-Protected Secret Sharing based on Threshold OPRF},
      howpublished = {Cryptology ePrint Archive, Paper 2017/363},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.