2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ @tylo Thanks for formatting the math stuff. I'm sorry for not posting it with proper formatting right away. I originally posted the question on security.stackexchange.com where LaTeX isn't supported, so I had to use unicode symbols, and then just copied the entire question over without checking whether LaTeX is supported on this site. $\endgroup$ – UTF-8 Jun 30 '17 at 12:46
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "Zero knowledge does not mean, the other side doesn't learn anything - it means that the simulator can act like the party he replaced." According to the script of a lecture I attend, the simulator doesn't simulate either entity. It simulates the transcript. In the last paragraph, I accidentally wrote "$pk$" when intending to write "$sk$". I corrected this and added a new last paragraph where $P$ just straight-up gives $pk$ (which can then be regarded as a password (no signature function required)) to $V$. Does this qualify as ZK when you can't learn anything about $pk$ from the transcript? $\endgroup$ – UTF-8 Jun 30 '17 at 13:00
  • $\begingroup$ Well, if you simulate the entire protocol - that's like replacing both parties. That also does not work (if the signature scheme is EUF-CMA) - you can not simulate valid signatures without contradicting the security definition. $\endgroup$ – tylo Jun 30 '17 at 13:36
  • $\begingroup$ You cannot create any valid pair of a message and a signature without knowing the secret without violating EUF-CMA. The message to which the signature corresponds is never sent. The simulator therefore doesn't have to create it. Simulating only $P$ would require coming up with a valid signature but simulating the entire transcript doesn't. No one just looking at the transcript can check whether the signature is valid for the message it's supposed to be the signature of. What I wrote in the last paragraph of the question even eliminates the signature all together. $\endgroup$ – UTF-8 Jun 30 '17 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.