International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Cody Freitag
Ilan Komargodski
Rafael Pass
Download:
DOI: 10.1007/978-3-030-26954-8_4 (login may be required)
Search ePrint
Search Google
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 $$\mathbf{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 $$\mathbf{P }$$ (and collision resistant hash functions) yields a public-coin constant-round fully concurrent zero-knowledge argument for $$\mathbf{NP } $$.
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29911,
  title={Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11694},
  pages={98-127},
  doi={10.1007/978-3-030-26954-8_4},
  author={Cody Freitag and Ilan Komargodski and Rafael Pass},
  year=2019
}