Conference rusure::math

1426.0. "Zero-Information Proofs" by EDPEDP::EDP (Always mount a scratch monkey.) Fri Apr 19 1991 09:06

    Zero-information proofs came up at last night's dinner.  Here's a recap
    of what I have floating around in memory.  Hopefully, somebody can
    provide a pointer to an article.
    
    These statements are givens for the duration of the note:
    
    	Given a large u and a large m, it is difficult to find a v
    	such that v^2 is congruent to u, modulo m, for suitable values
    	of u and m.  (I don't know the constraints -- whether m
    	needs to be the product of large primes, et cetera.)
    
    	Given a large u and a large m, it is easy to find a v such
    	that uv is congruent to 1, modulo m (assuming one exists).
    
    A person, named A, who later wishes to prove their identity creates a
    large number x and a larger modulus, m, subject to appropriate
    constraints. They may then publish x^2 publicly or just give it to
    anybody to whom they will wish to prove their identity.  The
    publication must be authenticated.  That is, it must be such that
    readers are assured that A is indeed the person who published x^2.
    
    There now exists a method with the following features:
    
    	Using this method, a person who knows x can prove they know x
    	to a person who knows x^2, whom we will call B.
    
    	This proof can be accomplished with a probability as close to
    	1 as desired, although it cannot exactly equal 1.
    
    	A third person, named C, can listen to the conversation between
    	A and B and not receive any information that would enable C to
    	determine x, except that C can learn the value of x^2 if they
    	do not already know it.
    
    	In fact, C can even record the entire conversation and still not
    	be able to later fake proof to B that C knows x.
    
    	The value of x is not revealed to B.  Person A does not need to
    	verify B's identity.
    
    	This method can be repeated many times each for many different
    	people acting as B.
    
    This is the method:
    
    	The following is repeated until B is satisfied:
    
    		A selects a large number y and transmits x^2*y^2 to B.
    		(All arithmetic is modulo m.)
    
    		B randomly and uniformly selects from one of two
    		possibilities:
    
    			B sends to A:  "Tell me y.", or
    			B sends to A:  "Tell me xy.".
    
    		A complies.  If B asked for xy, then B squares it and
    		compares it to x^2*y^2.  If B asked for y, then B
    		squares it, multiplies it by x^2, and compares it to
    		x^2*y^2.
    
    Let's first demonstrate that a person C cannot successfully pretend to
    be A.  First, observe that there are ways in which C could spoof one or
    the other of the questions B asks.  For example, C might make up a
    number z and send z^2.  Then if B asks for xy, C can send z.  B will
    square it and be satisfied.  But if B by chance asks for y, C will be
    unable to give an answer that satisfies x^2*y^2 = z^2.
    
    Alternatively, C could make up a z and send x^2*z^2.  Then if B asks
    for y, C just sends z.  But if B asks for xy, C will be unable to send
    xz, since C does not know x.
    
    Another way to demonstrate that C cannot answer both questions is to
    suppose that C has transmitted some number z to B.  Suppose C could
    then provide both y and xy.  But if C could do that, then C could
    figure out x by figuring out the inverse of y modulo m (it is given
    that this is easy) and then multiplying that inverse by xy.  That will
    give x.  But that was easy, and it is a given that figuring out x from
    x^2 (modulo m) is hard.
    
    So if C is trying to fake proof to B, then on each iteration, there is
    a .5 probability that B will catch C by asking for a number C cannot
    provide.  By repeating the iterations many times, the probability that
    a fraud is detected can be made as close to one as desired.
    
    Somebody listening to the conversation will receive many numbers
    x^2*y^2 and either y or xy for each such number, but they receive only
    one of the two possible answers.  When they see an x^2*y^2 and a y,
    they will be able to deduce x^2.  But from y they cannot figure out xy,
    and from xy they cannot figure out y, so they still only have one of
    the two numbers that might be asked for when x^2*y^2 is sent.  So they
    still have a .5 probability of being caught when they try to use that
    number.
    
    One restriction is that A must be careful never to use the same y
    twice, since B might ask for y one time and xy another, and a listener
    collecting these answers would then be able to calculate x.  B does not
    need to maintain any records; the random decision is sufficient to
    guarantee a .5 probability of catching a fraud even if old numbers are
    being used over again.
    
    One application for this is to put x and the arithmetic routines in a
    smart card.  The smart card then acts as proof of identity for its
    bearer; it can be used as a "password" for computer access.
    
    Suppose ATM cards contained this logic.  Your card could not only prove
    to the bank that it is your card, but the card could verify that the
    ATM does indeed belong to the bank.  (There have been several incidents
    in which people set up fake ATMs, to collect deposits made in them.)
    
    
    				-- edp

This exact same problem is one of the questions on my final exam of
Randomness in Computation. 

The problem statement is:

It is a known fact that calculating square roots mod n (i.e. given any y <
n, which is a square mod n, to find an integer x such that x^2 mod n = y)
is as difficult as factoring the integer n.  Based on this fact and the
(unproven) assumption that factoring is hard, we can construct the
following user-authentication scheme:

1. A trusted agent chooses large primes p, q.  The agent calculates n=pq,
   destroys p and q and publishes n.

2. Every user i secretly and randomly chooses 1 < x[i] < n, computes 
   y[i] = x[i]^2 mod n, and publishes y[i].  The system records y[i].

3. The system authenticates user i by checking that i knows a square root
   of y[i] mod n.

Devise a Zero-knowledge proof by which user i can convince the system that
he knows a square root mod n of y[i].  The probability of impersonation
should be smaller than 1/2^20.  In this situation the user is the Prover
and the system is the Verifier.

Hint: Develop a protocol which is like the ZKP for graph isomorphism or for
Hamiltonian ciccuits in a graph, in that the Verifier randomly chooses
between two types of questions.  Use the fact that the product of two
squares mod n is a square mod n.  In one version, the protocol starts with
the users randomly choosing an integer 0 < r < n and sending z = r^2 mod n
to the system.  Include a proof by simulation that your proof is indeed a
ZKP.  Write the algorithm for the simulator.

------ Problem statement ends ----

Easy question for the conference.  Why must n be composite?  

----------

I quickly thought of the solution in .0.  

                             2 2
Prover choses r .  Supplies r x  to Verifier.
               1             1

Verifier asks with equal probability, 

    1. What is r
                1

    2. What is r x
                1

But I ran into problems when I noticed that at some point, the Verifier
has both r x and r x.  That this point, can't the verifier compute:
          1       2

GCD(r x, r x) and discover x?  Perhaps GCD mod n is not doable.  
     1    2

(Something for me to investigate more fully now that I've completed the
other 4 problems.)

                                    August G. Reinig

        If you had both r1 x and r2 x then you could compute
        gcd(r1 x, r2 x).  But you only have r1 x (mod n) and
        r2 x (mod n).
        
        For example, if n = 17 * 29 = 493, and x = 103, r1 = 345,
        r2 = 296, then r1 x = 35535 and r2 x = 30488, with gcd 103.
        But you have r1 x (mod n) = 39 and r2 x (mod n) = 415
        with gcd 1.  [It is good to choose r1 and r2 large enough
        so that the product "wraps" mod n.]
        
        Dan
        

    In my answer I noted that GCD(a, b) <= min(a, b).  So, the Prover
    chooses r such that rx mod n < x.
    
                                    August

>Easy question for the conference.  Why must n be composite?
        
        Finding square roots modulo a prime p isn't a hard enough
        problem.  (One of the 4k+3 vs. 4k+1 cases was just discussed
        recently on sci.math.)
        
        Dan

re .0
        
>(There have been several incidents in which people set up fake ATMs, to
>collect deposits made in them.)
    
    There have also been incidents of fake ATMs collecting card numbers and
    PINs for later use in real ATMs (just as in a password grabber).