Difference between Zero Knowledge Proof and Challenge Response Protocol

Question

What exactly is the difference between Zero Knowledge Proof & Challenge Response Authentication?

I searched online and the best I could find are these:

1. techtarget.com

Zero-knowledge password proof systems depend on cryptographic methods that enable both parties -- client and server -- to authenticate to each other. These systems allow each party to confirm to each other that they have a correct password, but without the need to share that password with each other

2. cse.scu.edu : Implying that both of them are different and one improves on the other.

An instructor in my university had asked this question in one of the assignments and when I received the answer key for the same, I found this:

Distinguish between challenge response and Zero knowledge entity authentication.

Challenge-response identification – Strong authentication. Cryptographic challenge-response protocols is that one entity (the claimant) “proves” its identity to another entity (the verifier) by demonstrating knowledge of a secret known to be associated with that entity, without revealing the secret itself to the verifier during the protocol. This is done by providing a response to a time-variant challenge, where the response depends on both the entity’s secret and the challenge. The challenge is typically a number chosen by one entity (randomly and secretly) at the outset of the protocol. If the communications line is monitored, the response from one execution of the identification protocol should not provide an adversary with useful information for a subsequent identification, as subsequent challenges will differ. Challenge-response protocols can be realized by symmetric-key or asymmetric-key cryptography

Zero-Knowledge Proof – ZKP concept. A disadvantage of simple password protocols is that when a claimant A (called a prover in the context of zero-knowledge protocols) gives the verifier B her password, B can thereafter impersonate A. Challenge-response protocols improve on this: A responds to B’s challenge to demonstrate knowledge of A’s secret in a time-variant manner, providing information not directly reusable by B. Examples of ZKP. Fiat-Shamir identification protocol. Feige-Fiat-Shamir identification protocol. Guilou-Quisquate identification protocol.

which I feel is either wrongly worded or entirely wrong (leaning on the latter).

So, what exactly is the difference between them or are they not different at all? If possible, please explain with an example along with real-life algorithms where each of these is used.

Answer 1

They're just different things. A protocol may be challenge-response or not, and zero-knowledge or not; all four combinations are possible.

1. Plain password authentication is not challenge-response and not zero-knowledge.

2. The manual-lookup copy protection in old games is challenge-response and not zero-knowledge. Another example would be CAPTCHA.

3. Non-interactive zero-knowledge proofs are zero-knowledge and not challenge-response. Ex: Where's wally?

4. Colour Blind friend problem is an example for Zero-Knowledge Proof & Challenge-Response, both.

(Wikipedia says that plain password authentication is challenge-response because "tell me the password" is a challenge, and Modal Nest's answer says the same thing. By that definition I suppose any proof is necessarily challenge-response, because "prove it" is a challenge. But I think that definition is too broad and makes the term "challenge-response" largely useless. I'd limit it to protocols in which the prover has to do a nontrivial amount of work after getting the challenge, and can't just return a canned response.)

Answer 2

ZKPP is a zero-knowledge form of challenge-response authentication.

I agree the 2nd quoted text in the question is unclear. Especially the sentence "challenge-response protocols improve on this". And "simple password protocols" should read "simple challenge-response protocols".

In simple terms, the difference is that in a ZKPP the verifier doesn't know the secret, and doesn't gain any insight into the secret through verification.

A challenge-response authentication is simply providing a response to a challenge. This may be as simple as providing a password when prompted.

The Wikipedia page has a good simple example of zero-knowledge proof:

Imagine your friend is red-green colour-blind (while you are not) and you have two balls: one red and one green, but otherwise identical. To your friend they seem completely identical and he is skeptical that they are actually distinguishable. You want to prove to him they are in fact differently-coloured, but nothing else; in particular, you do not want to reveal which one is the red and which is the green ball.

Here is the proof system. You give the two balls to your friend and he puts them behind his back. Next, he takes one of the balls and brings it out from behind his back and displays it. He then places it behind his back again and then chooses to reveal just one of the two balls, picking one of the two at random with equal probability. He will ask you, "Did I switch the ball?" This whole procedure is then repeated as often as necessary.

By looking at their colours, you can, of course, say with certainty whether or not he switched them. On the other hand, if they were the same colour and hence indistinguishable, there is no way you could guess correctly with probability higher than 50%.

Since the probability that you would have randomly succeeded at identifying each switch/non-switch is 50%, the probability of having randomly succeeded at all switch/non-switches approaches zero ("soundness"). If you and your friend repeat this "proof" multiple times (e.g. 100 times), your friend should become convinced ("completeness") that the balls are indeed differently coloured.

The above proof is zero-knowledge because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.

Answer 3

In the quoted texts, I think the main issue is the following misunderstanding:

Challenge-response does not give any guarantee about the verifier not learning the secret. And that is wrongfully stated there. But that is one of the core properties of ZKP (it is actually the ZK property). To emphasize this: You can build challenge response from symmetric cryptography, e.g. see the Kerberos protocol. But you can not build ZK from symmetric crypto (where all secret information must be known to both parties, or it doesn't work. E.g. encryption keys and MAC keys).

And in the second quote, this is just a follow-up from wrongfully assigning the ZK property to CR instead of ZKP.