Cryptology ePrint Archive: Report 2012/717

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

Jan Camenisch and Anna Lysyanskaya and Gregory Neven

Abstract: 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.

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

Publication Info: Extended abstract appeared at ACM Conference on Computer and Communications Security 2012, pages 525-536.

Date: received 21 Dec 2012

Contact author: nev at zurich ibm com

Available format(s): PDF | BibTeX Citation

Version: 20121227:172803 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]