Cryptology ePrint Archive: Report 2016/233

Smooth NIZK Arguments with Applications to Asymmetric UC-PAKE

Charanjit Jutla and Arnab Roy

Abstract: We introduce a novel notion of smooth (-verifier) non- interactive zero-knowledge proofs (NIZK) which parallels the familiar notion of smooth projective hash functions (SPHF). We also show that the recent single group element quasi-adaptive NIZK (QA-NIZK) of Jutla and Roy (CRYPTO 2014) for linear subspaces can be easily extended to be computationally smooth. One important distinction of the new notion from SPHFs is that in a smooth NIZK the public evaluation of the hash on a language member using the projection key does not require the witness of the language member, but instead just requires its NIZK proof.

This has the remarkable consequence that in the Gennaro-Lindell paradigm of designing universally-composable password-authenticated key-exchange (UC-PAKE) protocols, if one replaces the traditionally employed SPHFs with the novel smooth QA-NIZK, one gets highly efficient UC-PAKE protocols that are secure even under dynamic corruption. The new notion can be seen as capturing the essence of the recent UC-PAKE protocol of Jutla and Roy (AsiaCrypt 2015) which is secure under dynamic corruption but uses intricate dual-system arguments.

This simpler and modular design methodology allows us to give the first single-round asymmetric UC-PAKE protocol, which is also secure under dynamic corruption in the erasure model. Previously, all asymmetric UC-PAKE protocols required at least two rounds. In fact, our protocol just requires each party to send a single message asynchronously. In addition, the protocol has short messages, with each party sending only four group elements. Moreover, the server password file needs to store only one group element per client. The protocol employs asymmetric bilinear pairing groups and is proven secure in the (limited programmability) random oracle model and under the standard bilinear pairing assumption SXDH.

Category / Keywords: QA-NIZK, PAKE, bilinear pairings, SXDH, MDDH, SPHF, hash proof, password, online attack, server compromise, dual system.

Date: received 2 Mar 2016, last revised 31 May 2016

Contact author: arnabr at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160531:204428 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]