Paper 2019/631

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

Cody Freitag, 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2019
Keywords
non-uniform certificatesconcurrent zero-knowledge
Contact author(s)
crf87 @ cornell edu
komargodski @ cornell edu
rnp3 @ cornell edu
History
2019-06-03: received
Short URL
https://ia.cr/2019/631
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/631,
      author = {Cody Freitag and Ilan Komargodski and Rafael Pass},
      title = {Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2019/631},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/631}},
      url = {https://eprint.iacr.org/2019/631}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.