Amitabh

2004-10-09 19:06:27 UTC

Permalink

I have a small question regarding RSA (most probably it is a knownRaw Message

problem already solved)

1) Let Alice and Bob have public key <Ea, Na> and <Eb, Nb>

2) Bob generates some secret number h and computes k = h^2 mod Na.

Bob now sends k to Carol.

3) Bob wants to prove to Carol that he has the square root of

k mod Na and make sure that Carol cannot reuse his proof to

falsly claim that she knows a square root of k mod Na.

Is it possible for Bob to produce such a proof? (i.e one that can

be made public but is attached to Bob's public key and cannot be

reused by Carol?). The following proof will work but can then be

reused by Carol.

{'anonymous' proof version}

1) Bob sends j = h^Ea mod Na along with k to Carol

2) Carol checks that j^2 = k^Ea mod Na.

The sender of j MUST know sqrt(k) (mod Na)

To define the problem for 'identity based' zero knowledge proof;

Suggest a way for Bob to produce a zero-knowledge proof using:

1) His private key

2) The secret value h and

3) Alice's public key

such that:

1) It can be verified using public keys of (Alice, Bob) together.

2) It is not possible to compute another proof without knowledge

of h or of one of the corresponding private keys.

Essentially Bob needs a way to 'connect' his RSA modulus with someone

(Alice) randomly chosen from a group of people using RSA keys.

NOTE: I am not looking for 'bit commitment' schemes where Bob laters

reveals h. The value of h is kept secret forever. Also the proof has

to be 'short' (i.e. non-interactive)

I need to use this as part of an authentication scheme I am trying to

develop for group environements. I would appreciate if someone could

suggest a method or provide references.

Rgds