[Resource Topic] 2019/631: Non-Uniformly Sound Certificates with Applications to Concurrent Zero-Knowledge

Welcome to the resource topic for 2019/631

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

Authors: Cody Freitag, Ilan Komargodski, 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.

ePrint: https://eprint.iacr.org/2019/631

Talk: https://www.youtube.com/watch?v=PBY7ocioSAc

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .