Paper 2012/717

Practical Yet Universally Composable Two-Server Password-Authenticated Secret Sharing

Jan Camenisch, Anna Lysyanskaya, and Gregory Neven


Password-authenticated secret sharing (PASS) schemes, first introduced by Bagherzandi et al. at CCS 2011, allow users to distribute data among several servers so that the data can be recovered using a single humanmemorizable password, but no single server (or collusion of servers up to a certain size) can mount an off-line dictionary attack on the password or learn anything about the data. We propose a new, universally composable (UC) security definition for the two-server case (2PASS) in the public-key setting that addresses a number of relevant limitations of the previous, non-UC definition. For example, our definition makes no prior assumptions on the distribution of passwords, preserves security when honest users mistype their passwords, and guarantees secure composition with other protocols in spite of the unavoidable non-negligible success rate of online dictionary attacks. We further present a concrete 2PASS protocol and prove that it meets our definition. Given the strong security guarantees, our protocol is surprisingly efficient: in its most efficient instantiation under the DDH assumption in the random-oracle model, it requires fewer than twenty elliptic-curve exponentiations on the user's device. We achieve our results by careful protocol design and by exclusively focusing on the two-server public-key setting.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Extended abstract appeared at ACM Conference on Computer and Communications Security 2012, pages 525-536.
password authenticationthreshold cryptographysecret sharing
Contact author(s)
nev @ zurich ibm com
2012-12-27: received
Short URL
Creative Commons Attribution


      author = {Jan Camenisch and Anna Lysyanskaya and Gregory Neven},
      title = {Practical Yet Universally Composable Two-Server Password-Authenticated Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2012/717},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.