Relaxed Security Notions for Signatures of Knowledge

We revisit the definition of signatures of knowledge by Chase and Lysanskaya (Crypto 2006) which correspond to regular signatures but where the signer also proves knowledge of the secret key to the public key through any signature. From a more abstract point of view, the signer holds a secret witness w to a public NP statement x and any signature to a message allows to extract w given some auxiliary trapdoor information. Besides extractability, Chase and Lysanskaya also demand a strong witness-hiding property, called simulatability, akin to the zero-knowledge property of non-interactive proofs. They also show that this property ensures anonymity for delegatable credentials or for ring signatures, for example. In this work here we discuss relaxed notions for simulatability and when they are sufficient for applications. Namely, in one notion we forgo any explicit witness-hiding notion, beyond some weak requirement that signatures should not help to produce further signatures, analogously to unforgeability of regular signature schemes. This notion suffices for example for devising regular signature schemes with some additional proof-of-possession (POP) or knowledge-of-secret-key (KOSK) property. Our stronger notion resembles the witness-indistinguishability notion of proofs of knowledge and can be used to build anonymous ring signatures. Besides formal definitions we relate all notions and discuss constructions and the aforementioned applications.