Discussion:
RSA related question (zero knowledge proof) - Is this trick possible?
Amitabh
2004-10-09 19:06:27 UTC
Raw Message
I have a small question regarding RSA (most probably it is a known

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
David Wagner
2004-10-11 07:51:03 UTC
Raw Message
Post by Amitabh
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.
Sure. You can use a zero knowledge proof of knowledge of a square root
of k mod Na. Carol will be convinced that Bob knows a square root of k,
but that won't help her later convince anyone else of this fact, because
she has learned nothing from the interaction other than the truth of Bob's
assertion (that's where the term "zero knowledge" comes from). There are
standard protocols in the literature for this problem. See, e.g.,
http://www.cs.ucsd.edu/users/bsy/ZKP.html
http://www.tml.hut.fi/Studies/T-110.498/2003summer/Slides/lecture03.pdf
This will likely be covered in any good textbook on the theory of
cryptography, so you should be able to find many good explanations of
the subject.

Note: Bob and Carol will probably want to communicate over a secure
channel between the two of them when they perform this protocol.
Nick Maclaren
2004-10-11 08:24:22 UTC
Raw Message
Post by David Wagner
Post by Amitabh
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.
Sure. You can use a zero knowledge proof of knowledge of a square root
of k mod Na. ...
Note: Bob and Carol will probably want to communicate over a secure
channel between the two of them when they perform this protocol.
If it is a GENUINELY zero-knowledge proof, why? A requirement
for a secure channel implies that there is SOME information that
can be extracted from the data transferred for the proof, or that
the public key system can't be trusted to ensure authenticity.

Of course, I am talking theoretically. In practice, you are quite
right, as no security system is perfect, and using a belt as well
as braces to hold your trousers up is normal. A really paranoid
person will also safety pin his trousers to his shirt.

Regards,
Nick Maclaren.
Amitabh
2004-10-12 10:45:59 UTC
Raw Message
Post by Nick Maclaren
If it is a GENUINELY zero-knowledge proof, why? A requirement
for a secure channel implies that there is SOME information that
can be extracted from the data transferred for the proof, or that
the public key system can't be trusted to ensure authenticity.
mod Na)
Suppose k is a QR mod Nb as well.

(1) Since Bob knows factors of Nb, he computes z = sqrt(k) mod Nb.

(2) Also since k is a QR mod Nb, k is a QR mod (Na*Nb) too

(3) Using z, h and k, Bob can compute a solution of x^2 = k mod
(Na*Nb)

(I think Bob can do this because he knows one sqrt of k mod Na and
also mod Nb. I am not sure how correct my assumption is)

(4) Bob makes the following information public: (x, k).

(5) Carol checks that x^2 = k mod Na*Nb. However, this does not enable
her to compute solutions to the congruence y^2 = k mod (Na*Nc)

If this is correct, this is a true non-interactive "zero knowledge
proof" also it is "non-transferrable".

I have two questions:
(1) Is this proof right? if so then:
(2) What if k is not a QR mod Nb? (can this procedure be modified to
include that?)

Rgds
Amitabh
Amitabh
2004-10-12 10:46:28 UTC
Raw Message
Post by Nick Maclaren
If it is a GENUINELY zero-knowledge proof, why? A requirement
for a secure channel implies that there is SOME information that
can be extracted from the data transferred for the proof, or that
the public key system can't be trusted to ensure authenticity.
Hi Nick,

Can you please elaborate on this? (eg. Is there a theorem ?)

(By a "secure channel", do we mean that some mechanism for
confidentiality and authentication is used?)

If Bob and Alice have certified public keys and Bob uses his private
key to compute the proof, what additional information can be extracted
if it is sent over a secure channel?

Rgds
Amitabh
Nick Maclaren
2004-10-12 15:22:30 UTC
Raw Message
In article <***@uni-berlin.de>,
***@gmail.com (Amitabh) writes:
|>
|> > If it is a GENUINELY zero-knowledge proof, why? A requirement
|> > for a secure channel implies that there is SOME information that
|> > can be extracted from the data transferred for the proof, or that
|> > the public key system can't be trusted to ensure authenticity.
|>
|> Can you please elaborate on this? (eg. Is there a theorem ?)

Well, I should have thought it is pretty obvious!

|> (By a "secure channel", do we mean that some mechanism for
|> confidentiality and authentication is used?)

I believe so.

|> If Bob and Alice have certified public keys and Bob uses his private
|> key to compute the proof, what additional information can be extracted
|> if it is sent over a secure channel?

No, that's the wrong way round.

The question is what information can be extracted by a third party
if a secure channel is NOT used. I.e. Bob is leaking nothing to
Carol except the fact that he knows the square root. Why should

Regards,
Nick Maclaren.

Amitabh
2004-10-12 15:22:06 UTC
Raw Message
Hi,

All the zero knowledge proofs I have seen require many rounds of
interaction between Bob and Carol..

Bob needs to generate the proof completely independently, without any
interaction with Alice or Carol.

I was wondering if it is possible for Bob to produce a proof that is
valid only in the ring of integers mod (Na*Nb) using the secret value
h, Alice's public key and his own private key..

For example, he can present solutions to the congruences
x^2 = k mod (Na * Nb) and y^2 = k mod Nb..

This perhaps is enough to prove that only someone knowing h and
factors of either Na or Nb could have found the solutions (Am I
right?). In fact, Bob only need provide a solution for x. (since y is