Cryptology ePrint Archive: Report 2019/631

Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge

Cody Freitag and Ilan Komargodski and Rafael Pass

Abstract: We introduce the notion of non-uniformly sound certificates: succinct single-message (unidirectional) argument systems that satisfy a ``best-possible security'' against non-uniform polynomial-time attackers. In particular, no polynomial-time attacker with s bits of non-uniform advice can find significantly more than s accepting proofs for false statements. Our first result is a construction of non-uniformly sound certificates for all NP in the random oracle model, where the attacker's advice can depend arbitrarily on the random oracle.

We next show that the existence of non-uniformly sound certificates for P (and collision resistant hash functions) yields a public-coin constant-round fully concurrent zero-knowledge argument for NP.

Category / Keywords: non-uniform certificates, concurrent zero-knowledge

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

Date: received 2 Jun 2019

Contact author: crf87 at cornell edu, komargodski at cornell edu, rnp3 at cornell edu

Available format(s): PDF | BibTeX Citation

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

Short URL:

[ Cryptology ePrint archive ]