Re: Is this simple scheme secure?

From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 01/31/04 

Date: Sat, 31 Jan 2004 08:41:01 GMT

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. 

-- 
--Tim Smith
Quantcast