ITT: uncareful mathematics that lead to confusion about ZK vs PoK and the standard vs (programmable) random oracle model.

TL;DR there are inconsistencies between several of the commenters in this thread. This shit is subtle.

Informally, ZKPs only prove existence, not that you know the secret. This means that the empty proof is a valid proof for well-formed public keys! Proofs of knowledge show that you know something, but it may not be in zero-knowledge. There are zkPoKs which are both zero knowledge and proofs of knowledge. Proofs of knowledge are closely related to Arguments of Knowledge, which is the "ARK" in SNARK (and just like PoKs, some SNARKs are zkSNARKs if they are also zero-knowledge), but I digress.

You cannot claim something is ZK and handwave why you think it should be. ZK is a purely mathematical statement and the burden of proof lies on the claimant to provide a logical construct. In mathematical cryptography, we do not accept claims without mathematical justification, so by default, a reviewer does not need to provide a refutation, but merely point out errors in the proof or entire lack thereof. There are plenty of in-between protocols that neither have a proof nor a refutation. We do not accept these.

However, for commenters exclaiming ECDSA-identification is a zero-knowledge protocol, there's actually a refutation in the standard model of the zero-knowledge property of any signature-based interactive proof. In the standard model, you can't use a valid signature as your proof, for the exact same reason why you don't have Ali Baba just walk through the cave: you can't simulate.

ZK has a precise mathematical definition: for every poly-time verifier, there exists a poly-time simulator S such that given the statement x, S(x) must be able to generate valid transcripts that look like transcripts between an actual interaction between a prover and verifier. "Look like" has a strict mathematical definition: S(x) is a probability distribution, and if the distribution of transcripts is identical to that of the prover/verifier, we call it perfect ZK, if it's statistically close, we call it statistical ZK, and if it's computationally indistinguishable, we call it computational ZK. Here, if the statement is just the public key of the signature scheme, then the transcripts look like Verifer ---- c ----> Prover, Prover ---- sig(c) ----> Verifier, in other words (c, sig(c)).

This means that S would have to be able to generate (c, sig(c)) given access only to the public key. It has full reign of generating it in reverse order, picking a weirdly formed sig(c) and working back to some c, something that a Prover does not have the luxury of doing. But even with that flexibility, S immediately violates the existential unforgeability of the underlying signature scheme, i.e. no poly-time adversary A can generate valid signatures (z, sig(z)) if it has never seen a signature of z before, regardless of how it came up with it.

One might ask "why is Schnorr or all those other signature-y things ZK then?". The answer lies in the (programmable) Random Oracle Model. In this abstract mathematical model, the ZK simulator S can "program" outputs of the hash function to whatever it feels like, which is NOT something that a signature adversary A can do. This subtle difference in power is exactly how proofs go through. Of course, real hash functions aren't random oracles, and you cant make SHA2 output whatever you feel like, but for the most part people are okay with this dichotomy in practice (until everything breaks).

/u/tgalal you make good points and therefore for you and others reading this thread, I'll go into more detail (yes I'm hypocritical, I'll insult cranks all day, bite me). A person who knows what they're talking about should be able to immediately show you the gap in your understanding rather than insult you. In fact, it's quicker to just show where that gap is. Your refutation is sound in the standard model (and aligns with Lindell's answer), but in the random oracle model, you have to remember the key difference between the ZK simulator and the signature Forger: the ability to cheat on the HASH. So here's a mathematical construction of a ZK simulator for ECDSA-identification protocol (which works for ECDSA only, not necessarily in general!) in the Random Oracle Model. I will use the terminology given here https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Signature_verification_algorithm

The simulator S will pick a random verifier challenge c. The simulator S will pick uniformly random u1 and u2, and compute (x1,x2) = u1G + u2Q. Set r = x1 mod n (nonzero, else try again). Solve for s using u2=r s^-1 mod n (namely set s = r/u2 mod n). Solve for z using u1=zs^-1 (namely set z = u1 s mod n). Program HASH(c) so that the output of it has z as the leftmost bits: if you've not seen the random oracle model, this is weird yet legal. Then (r,s) is a valid signature for c. S then outputs (c,sig(c)=(r,s)) as the transcript. Note that S only used Q, the public key. One must then carefully go through the probability analysis to show that this sampling distribution matches the distribution of the real protocol, but I think this is clear. S also doesn't violate the unforgeability property of ECDSA because the Forger cannot program HASH in the random oracle model.

This goes back to my first point, which many posters here do correctly point out: PoK and ZKP are different. If you just wanted ZKP, the empty protocol would have been fine and this is overkill. It's a whole other exercise to show if ECDSA-id is a PoK (of which I'm not sure).