Co-sound Zero-Knowledge with Public Keys

In this paper we present two variations of the notion of

co-soundness

previously defined and used by [Groth et al. - EUROCRYPT 2006] in the common reference string model. The first variation holds in the Bare Public-Key (BPK, for short) model and closely follows the one of [Groth et al. - EUROCRYPT 2006]. The second variation (which we call weak co-soundness) is a weaker notion since it has a stronger requirement, and it holds in the Registered Public-Key model (RPK, for short).

We then show techniques to construct co-sound argument systems that can be proved secure under standard assumptions, more specifically:

1

in the main result of this paper we show a constant-round resettable zero-knowledge argument system in the BPK model using black-box techniques only (previously it was achieved in [Canetti et al. - STOC 2000, Di Crescenzo et al. - CRYPTO 2004] with complexity leveraging);

1

additionally, we show an efficient statistical non-interactive zero- knowledge argument system in the RPK model (previously it was achieved in [Damgård et al. - TCC 2006] with complexity leveraging).

We stress that no alternative solution preserving all properties enjoyed by ours is currently known using the classical notion of soundness.