Cryptology ePrint Archive: Report 2019/640

On Round Optimal Statistical Zero Knowledge Arguments

Nir Bitansky and Omer Paneth

Abstract: We construct the first three message statistical zero knowledge arguments for all of NP, matching the known lower bound. We do so based on keyless multi-collision resistant hash functions and other standard primitives (based on the Learning with Errors assumption) --- the same assumptions used to obtain round optimal computational zero knowledge. The main component in our constructions is a statistically witness indistinguishable argument of knowledge based on a new notion of statistically hiding commitments with subset opening.

Category / Keywords: zero knowledge, collision resistance, statistically hiding commitments

Original Publication (in the same form): IACR-CRYPTO-2019

Date: received 2 Jun 2019

Contact author: nbitansky at gmail com, omerpa@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190603:085730 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]