Re: Is this simple scheme secure?

From: NYC (name_at_company.com)
Date: 01/31/04 

Date: Sat, 31 Jan 2004 10:25:00 +0100

Tim Smith wrote:
> In article <1075494019.905062@kalvebod.groenjord.dk>, NYC wrote:
>
>>Suppose we have 2 individuals A & B and a message M.
>>
>>Both A & B claims to know M however none of them trusts that the other
>>party knows M and they don't want to give M to the other party in case
>>the other party doesn't already know it.
>
> ...
>
>>My simple suggestion is:
>>
>>1) A generates, say, a 20-byte random message C and sends it to B
>>2) B calculates P = SHA(C | M) and sends it to A.
>>3) A verifies that P = SHA(C | M).
>
>
> Looks good. If A is a server, B is a client, and M is the client's
> password, you've in fact just rediscovered a fairly normal
> challenge/response system for password verification.
>
> ...
>
>>However, if it this simple, why all this talk about zero-knowledge
>>proofs etc.? I read a brief note about it, and seemed very complex
>>involving Hamiltonian circuits and whatnot.
>
>
> Different situation. In your hypothetical, A and B both know M, and your
> protocol verifies to A that B knows it, and running it once the other way
> would verify to B that A knows it.
>
> The kind of problem usually under discussion with zero-knowledge systems
> would be like this:
>
> A and B both know a graph, G. B knows a Hamiltonian circuit, M, on G.
> How can B prove this to A, without giving A any information about M?
>
> Note they key difference. Here, A does *not* know M.
>

Interesting :) Does it have any practical applications (I mean, besides
from the possibility of one mathematician being able to tease another by
proving he knows the proof of some famous problem, but without telling
this)? :-)