From: mpd@netcom.com (Mike Duvos)
Date: Sun, 10 Apr 94 22:40:43 PDT
To: Cypherpunks@toad.com
Subject: Re: TCMay's posting on zero knowledge, last year
In-Reply-To: <Pine.3.89.9404101833.A1164-0100000@stein3.u.washington.edu>
Message-ID: <199404110541.WAA27965@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Tim writes:

> 5. How general is the "zero knowledge interactive proof" approach?

> Anything provable in formal logic is provable in zero knowledge, saith the
> mathematicians and crypto gurus. Check out the various "Crypto Conference"
> Proceedings.

Perhaps one could adapt this approach to demonstrate to someone that you
know the factors of a certain PGP public key.  You blind the factors,
commit to the blinded values, and present the product to your opponent. 
He chooses to have you either factor the product or unblind the
modulus.  Do this a sufficient number of times and one can be pretty 
certain the key has been compromised.

Of course it would probably be simpler to simply decode a message 
encrypted with the public key as proof that you are in possession of the 
factors, but this idea struck me as kind of cute.

-- 
     Mike Duvos         $    PGP 2.3a Public Key available    $
     mpd@netcom.com     $    via Finger.                      $