How is the zero-knowledge proof definition violated, here?

Question

I'm confused about the definition of an interactive zero-knowledge proof (the simulator-transcript-thingy).

Assume the following setup:

• $P$ and $V$ do a Diffie-Hellman key exchange to generate the shared secret S. They then both compute the hash $H(S)$.
• $P$ computes $\sigma = sig(sk, H(S))$ and sends $\sigma$ to $V$.
• $V$ checks whether $ver(pk, H(S), \sigma) = 1$ and iff it is, assumes $P$ to have proven its identity.

For simplicity, let's assume the base to be $2$.

$sig$ is defined in such a way that its output has $k$ bit and

$∀σ∈\{0,1\}^k, sk∈\{0,1\}^n : (∃S∈\{0,1\}^ℓ : sig(sk, H(S)) = σ)$

where $n$ is the length of the private key and $ℓ$ is the length of the secret created via Diffie-Hellman.

We actually need to require that

$∀σ∈\{0,1\}^k, sk∈\{0,1\}^n, a∈ℤ_q, S∈ℤ_q : (∃b∈ℤ_q : sig(sk, S \mod p) = σ, S = g^{a\cdot b}))$

where $g$ is the primitive root of Diffie-Hellman, $p$ is prime, and $q$ is the order of the group $<g>$;. I merely wrote the formula above so it's easy enough for everyone to understand. The jump from the weaker definition above to the one described by the second formula doesn't seem too big.

As with all signatures, an attacker who knows many $sig(sk, M)$ for different $M$ but the same $s$k can learn about $sk$.

This protocol therefore is obviously not zero-knowledge. However, it seems to fit the definition as I can't think of any argument as to why for any PPT attacker $A$ knowing only about $pk$ communicating with $P$, it's not possible to find a PPT $S$ only knowing about $pk$ which simulates the transcript between $A$ and $P$.

Furthermore, I don't see how the transcript contains information about $sk$ (which after all is what the zero-knowledge definition is about). What I think I have done (and am btw pretty sure I didn't do as the definition of zero-knowledge was created by smart people, so I'm quite aware that I made a mistake somewhere (and I want to know where)) is to give $V$ information about $sk$ without there being information about $sk$ in the transcript.

One could even just let $P$ send $pk \oplus H(S)$ to $V$, giving the secret to $V$ without anyone who can only look at the transcript being able to tell whether the entity {creating; participating in the creating of} the transcript knows the secret ($pk$ which can be regarded as a password, no signature function required).

Answer 1

As with all signatures, an attacker who knows many $sig(sk,M)$ for different $M$ but the same $sk$ can learn about $sk$.

I guess you mean "can't learn anything about $sk$". Yes, that's right, but that's not the security definition of EUF-CMA (existential unforgability under chosen message attack). Informally speaking, it means that the attacker can not generate any valid signature on any message (excluding those he queried in the security game).

As you stated correctly, you can't simulate $P$: The existence of a simulator would be a direct contradction to the assumption that the signature is EUF-CMA: The simulator needs to be able to generate valid signatures with non-negligible probability without knowing the signing key, and in order for the signature to be EUF-CMA such a forgery must only be possible with negligible probability.

However, it seems to fit the definition as I can't think of any argument as to why for any PPT attacker $A$ knowing only about $pk$ communicating with $P$, it's not possible to find a PPT $S$ only knowing about $pk$ which simulates the transcript between $A$ and $P$.

Yes, you can replace the verifier $V$ with a simulator, and this is actually zero-knowledge. However, this is quite trivial, if you look at your protocol: $V$ does not send any message in dependency of the secret value. It only does a DDH key exchange and then finishes the protocol by accepting the identity. In an exchange with an honest $P$ this will work out - it's more complicated if $P$ isn't considered to be honest (but that would also require the protocol to be different).

But what does it actually mean? Well, $V$ doesn't have a secret value. So there is no information kept secret. Zero knowledge does not mean, the other side doesn't learn anything - it means that the simulator can act like the party he replaced. And that's pretty much trivial if that party has no secret value.

But more importantly: This only states that $V$ doesn't send any information, which isn't in the protocol. It does not state anything about $P$ sending $sk$ in the protocol. For that you would have to replace $P$ with a simulator - which is impossible without breaking the security of the signature scheme, see above.

Furthermore, I don't see how the transcript contains information about $sk$ (which after all is what the zero-knowledge definition is about).

$sk$ is a secret value, so yes, a zero knowledge proof replacing $P$ with a simulator would prove that - if it existed. I think there is a misconception here: The main argument of the zero-knowledge proof is that you can create a valid transcript - but the corresponding party doesn't have the secret value. That means the transcript itself doesn't depend on the actual secret - the simulator doesn't know it. If you leave $P$ in and replace $V$ with the simulator, that doesn't change anything and you don't know if the transcript leaks $sk$ or not.

.. is to give V information about pk without there being information about pk in the transcript.

The verification key $pk$ is public - you don't need to give that to $V$, he already has it.