Theory Question: Why isn't RSA a 0-knowledge Proof

Joseph M. Reagle Jr. reagle at rpcp.mit.edu
Sat Jan 13 16:56:01 PST 1996


At 06:01 PM 1/13/96 -0500, you wrote:
>
>Zero knowledge means that the recipient obtains no information that they could 
>not have obtained without knowing the secret information corresponding to the 
>key. 
>
>If I authenticate myself to you by giving a signature on a nonce you chose you 
>have obtained information that you could not have obtained otherwise.

        Seems right enough.

        Still pondering though... 

[1]  If I (the signer) choose the series of messages to sign, this still
demonstrates that I have a secret without telling you the secret (and
without giving you the information you might have been fishing for..)  You
do get information you would not have been able to create
otherwise,(whatever it is I choose to sign) ...but it doesn't matter if you
wanted the information or not, what matters is that you got it???  You could
get random information (entropy) as part of a protocol, would this destroy
the 0-knowledge aspect as well (and make it merely a min-disclosure
proof...?))  (if you aren't directly challanging me, there could be a replay
or man in the middle attack or whatnot, but the man in the middle attack
also applies to 0KP.)

        What I was thinking of, was a hamiltonian cycle example:

[2]where the person that wants to see the proof is getting information
regarding the iso-morphism between the various graphs... (For instance, say
G is the real graph, Alice knows the path, and Bob wants proof that Alice
knows it...)  So in the first instance Alice produces H1 and shows it to Bob
and proves it is iso-morphic, in the second example she produces H2 and
shows the cycle, in the third instance, she provides H3 and it's isomorphism
to G... Bob can then conclude that H1 and H2 are isomorphic... I'm not sure
about this (this must be where I am in error) but I don't think Bob could
have derived the fact easily (if it is plausible for him to believe H1~=H2
based on this protocol) that H1 and H2 are isomorphic without Alice's help
here... So in this case, Bob picked up some info he would have not otherwise
known for free (similar to the first example) even though this information
isn't of any use to him with regard to the solution to G.

>If it wasn't for the fact that it is IAP and you apear to be a grad student I 
>might wonder about somone doing their course assignments via the net... :-)

        The effect of the eggnaugh hasn't worn off and trying to vamp up...
<smile>
_______________________
Regards,               Is this true or only clever? -Augustine Birrell
Joseph Reagle          http://farnsworth.mit.edu/~reagle/home.html
reagle at mit.edu         0C 69 D4 E8 F2 70 24 33  B4 5E 5E EC 35 E6 FB 88







More information about the cypherpunks-legacy mailing list