Abstract:
A zero-knowledge proving system includes a proving mechanism for proving equality or inequality of two discrete logarithms and a verifying mechanism for verifying said equality or inequality. The proving mechanism stores public information including a designated operation scheme, two input numbers α and β, and two predetermined bases g and h, private information x which is a discrete logarithm of α to the base g. After converting α, β and h to produce α′, β′ and γ′ as follows: α′=α r ; β′=β r ; and γ′=h xr , the equality of a log α α′ and log β β′ and the equality of log g α′ and log h γ′ are proved. The verifying mechanism verifies the equality of a log  α α′ and log β β′ and the equality of log g α′ and log h γ′. Then, the received β′ and γ′ are checked to determine the equality or inequality thereof, and it is determined whether the proof is acceptable, depending on the verification and the check results.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to zero-knowledge proving techniques for proving the equality or inequality of (discrete logarithms, which is suitable for use in undeniable signatures.  
           [0003]    2. Description of the Related Art  
           [0004]    Undeniable signatures proposed by Chaum have an important property such that a signer cannot deny the validity of a self-generated signature but a forged signature. The undeniable signature schemes like this make use of the group operation of an order-q group G on modulo p, where p and q are prime and have a relationship of q| (p−1) . When y=g x  is an element of the group G, the signer uses the generator g as a public key and x as a private key. A signature on a message m is obtained by calculating SIG−m x , where x is the private key. For (m, SIG), the validity of the signature can be decided by proving the equality of the discrete logarithm x of the public key. y=g x  and the discrete logarithm x′ of SIG=m x . In contrast, the forgery of the signature can be decided by proving the inequality of SIG′ and m x  for (m, SIG′). Accordingly, such signature system needs a proving mechanism for proving the equality or inequality the above discrete logarithms and a verifying mechanism for verifying the results in a designated group operation.  
           [0005]    There has been known the Chaum&#39;s scheme that allows a prover to convince the verifier about the equality or inequality of SIC′ and m x , which is disclosed in “Zero-knowledge undeniable signatures”, Advances in Cryptology, Proceedings of Eurocrypt&#39; 1990, LNCS473, Springer-Verlag, pp. 458-464, 1991. This Chaum&#39;s scheme, however, employs different proving systems to prove respective ones of the equality and inequality. Especially, the system of proving the inequality cannot be performed without the verifier and therefore it is impossible for the prover solely to prove the inequality.  
           [0006]    There has been proposed another proving scheme that employs the same proving systems to prove both the equality and inequality. See “Efficient convertible undeniable signature schemes”, Proceedings of 4th Annual Workshop on Selected Areas in Cryptography, SAC&#39;97, August 1997. Although this scheme allows the prover solely to prove both the equality and inequality and the efficiency thereof has been qualitatively analyzed, it has a disadvantage of leaking important information. More specifically, the information m x  is known by the verifier, loading to a contradiction such that, when indicating that a message m is not signed, the signature on m is involuntarily passed.  
         SUMMARY OF THE INVENTION  
         [0007]    An object of the present invention is to provide a zero-knowledge proving system and method allowing the same protocol to be used to prove the equality or inequality of discrete logarithms and allowing the prover solely to prove it without leaking important information.  
           [0008]    According to the present invention, a system includes a first mechanism for proving equality or inequality of two discrete logarithms and a second mechanism for verifying said equality or inequality. The first mechanism includes: a first public information memory storing a designated operation scheme, two input numbers (hereinafter, denoted by α and β), and two predetermined bases (hereinafter, denoted by g and h); a private information memory storing private information (hereafter, denoted by x) which is a discrete logarithm of α to the base g; a random number generator for generating a first random number (hereafter, denoted by r); a converter for converting the input number α, the input number β and the base h to produce α′, β′ and γ′ using the first random number r and the private information x as follows: 
           α′=α r ; 
           β′=β r ; and 
           γ′= h   xr , 
           [0009]    wherein said α′, β′ and γ′ are sent to the second mechanism; and a proving section for proving equality of a discrete logarithm of α′ to base a and a discrete logarithm of β′ to base β and equality of a discrete logarithm of α′ to the base g and a discrete logarithm of γ′ to the base h.  
           [0010]    The second mechanism includes: a second public information memory storing the designated operation scheme, the two input numbers α and β, and the two predetermined bases g and h; a verifying section corresponding to the proving section, for verifying equality of a discrete logarithm of the received α′ to base a and a discrete logarithm of the received β′ to base β, and equality of a discrete logarithm of the received α′ to the base g and a discrete logarithm of the received γ′ to the base h; a checking section for checking the received β′ and γ′ to determine equality or inequality thereof; and a decision section for deciding whether proof of the first mechanism is acceptable, depending on results of the verifying section and the checking section.  
           [0011]    According to an aspect of the present invention, the proving section may include: a first prover for proving the equality of the discrete logarithm of α′ to base α and the discrete logarithm of β′ to base β; and a second prover for proving the equality of the discrete logarithm of α′ to the base g and the discrete logarithm of γ′ to the base h, and the verifying section comprises: a first verifier corresponding to the first prover, for verifying the equality of the discrete logarithm of the received α′ to base α and the discrete logarithm of the received β′ to base β; and a second verifier corresponding to the second prover, for verifying the equality of the discrete logarithm of the received α′ to the base g and the discrete logarithm of the received γ′ to the base h.  
           [0012]    In an embodiment, the checking section may include a third verifier for verifying the equality of the received β′ and γ′. In another embodiment, the checking section ray include a third verifier for verifying the inequality of the received β′ and γ′. In still another embodiment, the checking section may include a comparator for comparing the received β′ and γ′.  
           [0013]    According to another aspect of the present invention, the proving section may include a single prover for proving the equality of the discrete logarithm of α′ to base α and the discrete logarithm of β′ to base β, and the equality of the discrete logarithm of α′ to the base g and the discrete logarithm of γ′ to the base h. The verifying section may include a single verifier for verifying the equality of a discrete logarithm of the received α′ to base α and a discrete logarithm of the received β′ to base β, and the equality of a discrete logarithm of the received α′ to the base g and a discrete logarithm of the received γ′ to the base h.  
           [0014]    In an embodiment, the checking section may include a verifier for verifying the equality of the received β′ and γ′. In another embodiment, the checking section may include a verifier for verifying the inequality of the received β′ and γ′. In still another embodiment, the checking section may include a comparator for comparing the received β′ and γ′.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    [0015]FIG. 1 is a schematic diagram showing a first basic scheme of a zero-knowledge proving system according to the present invention;  
         [0016]    [0016]FIG. 2 is a schematic diagram showing a second basic scheme of a zero-knowledge proving system according to the present invention;  
         [0017]    [0017]FIG. 3 is a schematic diagram showing a third basic scheme of a zero knowledge proving system according to the present invention;  
         [0018]    [0018]FIG. 4 is a schematic diagram showing a fourth basic scheme of a zero-knowledge proving system according to the present invention;  
         [0019]    [0019]FIG. 5 is a schematic diagram showing a fifth basic scheme of a zero-knowledge proving system according to the present invention;  
         [0020]    [0020]FIG. 6 is a schematic diagram showing a sixth basic scheme of a zero-knowledge proving system according to the present invention;  
         [0021]    [0021]FIG. 7 is a block diagram showing a zero-knowledge proving system according to a first embodiment of the present invention;  
         [0022]    [0022]FIG. 8 is a block diagram showing first prover and first verifier in a zero-knowledge proving system according to a second embodiment of the present invention;  
         [0023]    [0023]FIG. 9 is a block diagram showing first prover and first verifier in a zero-knowledge proving system according to a third embodiment of the present invention;  
         [0024]    [0024]FIG. 10 is a block diagram showing first prover and first verifier in a zero-knowledge proving system according to a fourth embodiment of the present invention;  
         [0025]    [0025]FIG. 11 is a block diagram showing second prover and second verifier in a zero-knowledge proving system according to a fifth embodiment of the present invention;  
         [0026]    [0026]FIG. 12 is a block diagram showing second prover and second verifier in a zero-knowledge proving system according to a sixth embodiment of the present invention;  
         [0027]    [0027]FIG. 13 is a block diagram showing second prover and second verifier in a zero-knowledge proving system according to a seventh embodiment of the present invention;  
         [0028]    [0028]FIG. 14 is a block diagram showing a zero-knowledge proving system according to an eighth embodiment of the present invention;  
         [0029]    [0029]FIG. 15 is a block diagram showing a prover and a first verifier in a zero-knowledge proving system according to a ninth embodiment of the present invention;  
         [0030]    [0030]FIG. 16 is a block diagram showing a prover and a first verifier in a zero-knowledge proving system according to a tenth embodiment of the present invention;  
         [0031]    [0031]FIG. 17 is a block diagram showing a prover and a first verifier in a zero-knowledge proving system according to an eleventh embodiment of the present invention;  
         [0032]    [0032]FIG. 18 is a block diagram showing a zero-knowledge proving system according to a twelfth embodiment of the present invention; and  
         [0033]    [0033]FIG. 19 is a block diagram showing a zero-knowledge proving system according to a thirteenth embodiment of the present invention.  
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0034]    In the preferred embodiments described below, p and q are primes, where q|(p−1), and g, h, α and β are all elements of a group of order q on modulo p.  
         [0035]    System Outlines  
         [0036]    1. First Basic Scheme  
         [0037]    Referring to FIG. 1, the system has a proving mechanism  100  and a verifying mechanism  150 . The proving mechanism  100  includes a random number generator  101 , a public information memory  102 , a private information memory  103 , and a variable converter  104 .  
         [0038]    The random number generator  101  generates a random number r εZ/qZ.  
         [0039]    The public information memory  102  stores p, q, g, h, α and β, where p and q indicates the group operation, g and h are first and second bases, respectively, and α and β are input numbers. The same public information are stored in a public information memory  151  of the verifying mechanism  150 .  
         [0040]    The private information memory  103  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0041]    The random number generator  101 , the public information memory  102  and the private information memory  103  output p, q, g, h, α, β, x, and r to the variable converter  104 .  
         [0042]    The variable converter  104  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r  mod  p;   
         β′=β r  mod  p ; and 
         γ′= h   xr  mod  p.   
         [0043]    The proving mechanism  100  sends these α′, β′, γ′ to the verifying mechanism  150 .  
         [0044]    The proving mechanism  100  further includes a first prover  105  and a second prover  106 . The first prover  105  proves the equality of the discrete logarithms of α′ to the base α and β′ to the base β. The second prover  106  proves the equality of the discrete logarithms of α′ to the base g and γ′ to the base h.  
         [0045]    The verifying mechanism  150  further includes a first verifier  152 , a second verifier  153 , a third verifier  154 , and a decision section  155 .  
         [0046]    The first verifier  152  verifies about the equality of the discrete logarithms of α′ to the base α and β′ to the base β and, if the equality is verified, then the verification acceptance is determined. The second verifier  153  verifies about the equality of the discrete logarithms of α′ to the base g and γ′ to the base h and, if the equality is verified, then the verification acceptance is determined. The third verifier  154  verifies about the equality of β′ and γ′ and, if it is verified that β′=γ′, then the verification acceptance is determined.  
         [0047]    The decision section  155  decides the equality of the discrete logarithms of α to the base g and β to the base h when the verification results of the first to third verifiers  152 - 154  are all verification acceptances. When the equality is decided, the decision section  155  outputs “OK” and otherwise “NG”.  
         [0048]    2. Second Basic Scheme  
         [0049]    Referring to FIG. 2, the system has a proving mechanism  200  and a verifying mechanism  250 . The proving mechanism  200  includes a random number generator  201 , a public information memory  202 , a private information memory  203 , and a variable converter  204 .  
         [0050]    The random number generator  201  generates a random number r εZ/qZ.  
         [0051]    The public information memory  202  stores p, q, g, h, α and β. The same public information are stored in a public information memory  251  of the verifying mechanism  250 .  
         [0052]    The private information memory  203  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base q, that is, x=log g α.  
         [0053]    The random number generator  201 , the public information memory  202  and the private information memory  203  output p, q, g, h, α, β, x, and r to the variable converter  204 .  
         [0054]    The variable converter  204  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r  mod  p;   
         β′=β r  mod  p ; and 
         γ′= h   xr  mod  p.   
         [0055]    The proving mechanism  200  sends these α′, β′ and γ′ to the verifying mechanism  250 .  
         [0056]    The proving mechanism  200  further includes a prover  205 , which proves the equality of the discrete logarithms of α′ to the base α and β′ to the base β and the equality of the discrete logarithms of α′ to the base g and γ′ to the base h.  
         [0057]    The verifying mechanism  250  further includes a first verifier  252 , a second verifier  254 , and a decision section  255 . The first verifier  252  verifies about the equality of the discrete logarithms of α′ to the base α and β′ to the base β and the equality of the discrete logarithms of α′ to the base g and γ′ to the base h. If these equalities are both verified, then the verification acceptance is determined. The second verifier  254  verifies about the equality of β′ and γ′ and, if it is verified that β′=γ′, then the verification acceptance is determined.  
         [0058]    The decision section  255  decides the equality of the discrete logarithms of α to the base g and β to the base h when the verification results of the first and second verifiers  252  and  254  are all verification acceptances. When the equality is decided, the decision section  255  outputs “OK” and otherwise “NG”.  
         [0059]    3. Third Basic Scheme  
         [0060]    Referring to FIG. 3, the system has a proving mechanism  300  and a verifying mechanism  350 . The proving mechanism  300  includes a random number generator  301 , a public information memory  302 , a private information memory  303 , and a variable converter  304 .  
         [0061]    The random number generator  301  generates a random number r εZ/qZ.  
         [0062]    The public information memory  302  stores p, q, g, h, α and β. The same public information are stored in a public information memory  351  of the verifying mechanism  350 .  
         [0063]    The private information memory  303  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0064]    The random number generator  301 , the public information memory  302  and the private information memory  303  output p, q, g, h, α, β, x, and r to the variable converter  304 .  
         [0065]    The variable converter  304  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r  mod  p;   
         β′=β r  mod  p ; and 
         γ′= h   xr  mod  p.   
         [0066]    The proving mechanism  300  sends these α′, β′ and γ′ to the verifying mechanism  350 .  
         [0067]    The proving mechanism  300  further includes a first prover  305  and a second prover  306 . The first prover  305  proves the equality of the discrete logarithms of α′ to the base α and β′ to the base β. The second prover  306  proves the equality of the discrete logarithms of α′ to the base g and γ′ to the base h.  
         [0068]    The verifying mechanism  350  further includes a first verifier  352 , a second verifier  353 , a third verifier  354 , and a decision section  355 .  
         [0069]    The first verifier  352  verifies about the equality of the discrete logarithms of α′ to the base α′ and β′ to the base β and, if the equality is verified, then the verification acceptance is determined. The second verifier  353  verifies about the equality of the discrete logarithms of α′ to the base g and γ′ to the base h and, if the equality is verified, then the verification acceptance is determined.  
         [0070]    The third verifier  354  verifies about the inequality of β′ and γ′ and, if it is verified that β′≠γ′, then the verification acceptance is determined.  
         [0071]    The decision section  355  decides the inequality of the discrete logarithms of ′ to the base g and β to the base h when the verification results of the first to third verifiers  352 - 354  are all verification acceptances. When the inequality is decided, the decision section  355  outputs “OK” and otherwise “NG”.  
         [0072]    4. Fourth Basic Scheme  
         [0073]    Referring to FIG. 4, the system has a proving mechanism  400  and a verifying mechanism  450 . The proving mechanism  400  includes a random number generator  401 , a public information memory  402 , a private information memory  403 , and a variable converter  404 .  
         [0074]    The random number generator  401  generates a random number r εZ/qZ.  
         [0075]    The public information memory  402  stores p, q, g, h, α and β. The same public information are stored in a public information memory  451  of the verifying mechanism  450 .  
         [0076]    The private information memory  403  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0077]    The random number generator  401 , the public information memory  402  and the private information memory  403  output p, q, g, h, α, β, x, and r to the variable converter  404 .  
         [0078]    The variable converter  404  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r  mod  p;   
         β′=β r  mod  p ; and 
         γ′= h   xr  mod  p.   
         [0079]    The proving mechanism  400  sends these α′, β′ and γ′ to the verifying mechanism  450 .  
         [0080]    The proving mechanism  400  further includes a prover  405 , which proves the equality of the discrete logarithms of α′ to the base α and β′ to the base β and the equality of the discrete logarithms of α′ to the base g and γ′ to the base h.  
         [0081]    The verifying mechanism  450  further includes a first verifier  452 , a second verifier  454 , and a decision section  455 . The first verifier  452  verifies about the equality of the discrete logarithms of α′ to the base α and β′ to the base β and the equality of the discrete logarithms of α′ to the base g and γ′ to the base h. If these equalities are both verified, then the verification acceptance is determined.  
         [0082]    The second verifier  454  verifies about the inequality of β′ and γ′ and, if it is verified that β′≠γ′, then the verification acceptance is determined.  
         [0083]    The decision section  355  decides the inequality of the discrete logarithms of α to the base g and β to the base h when the verification results of the first to third verifiers  352 - 354  are all verification acceptances. When the inequality is decided, the decision section  355  outputs “OK” and otherwise “NG”.  
         [0084]    5. Fifth Basic Scheme  
         [0085]    Referring to FIG. 5, the system has a proving mechanism  500  and a verifying mechanism  550 . The proving mechanism  500  includes a random number generator  501 , a public information memory  502 , a private information memory  503 , and a variable converter  504 .  
         [0086]    The random number generator  501  generates a random number r εZ/qZ.  
         [0087]    The public information memory  502  stores p, q, g, h, α and β, where p and q indicates the group operation, g and h are first and second bases, respectively, and α and β are input numbers. The same public information are stored in a public information memory  551  of the verifying mechanism  550 .  
         [0088]    The private information memory  503  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0089]    The random number generator  501 , the public information memory  502  and the private information memory  503  output p, q, g, h, α, β, x, and r to the variable converter  504 .  
         [0090]    The variable converter  504  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r  mod  p;   
         β′=β r  mod  p; and 
         γ′= h   xr  mod  p.   
         [0091]    The proving mechanism  500  sends these α′, β′ and γ′ to the verifying mechanism  550 .  
         [0092]    The proving mechanism  500  further includes a first prover  505  and a second prover  506 . The first prover  505  proves the equality of the discrete logarithms of α′ to the base α and β′ to the base β. The second prover  506  proves the equality of the discrete logarithms of α′ to the base g and γ′ to the base h.  
         [0093]    The verifying mechanism  550  further includes a first verifier  552 , a second verifier  553 , a comparator  554 , and a decision section  555 .  
         [0094]    The first verifier  552  verifies about the equality of the discrete logarithms of α′ to the base α and β′ to the base β and, if the equality is verified, then the verification acceptance is determined. The second verifier  553  verifies about the equality of the discrete logarithms of α′ to the base g and γ′ to the base h and, if the equality is verified, then the verification acceptance is determined. The comparator  554  compares β′ and γ′ to determine whether β′≠γ′.  
         [0095]    The decision section  555  decides the inequality of the discrete logarithms of α to the base g and β to the base h when the verification results of the first and verifiers  552  and  553  are all verification acceptances and the comparator  554  determine that β′≠γ′. When the comparator  554  determine that β′=γ′, the decision section  555  decides the equality of the discrete logarithms of α to the base g and β to the base h.  
         [0096]    6. Sixth Basic Scheme  
         [0097]    Referring to FIG. 6, the system has a proving mechanism  600  and a verifying mechanism  650 . The proving mechanism  600  includes a random number generator  601 , a public information memory  602 , a private information memory  603 , and a variable converter  604 .  
         [0098]    The random number generator  601  generates a random number r εZ/qZ.  
         [0099]    The public information memory  602  stores p, q, g, h, α and β. The same public information are stored in a public information memory  651  of the verifying mechanism  650 .  
         [0100]    The private information memory  603  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0101]    The random number generator  601 , the public information memory  602  and the private information memory  603  output p, q, g, h, α, β, x, and r to the variable converter  604 .  
         [0102]    The variable converter  604  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r  mod  p;   
         β′=β r  mod  p ; and 
         γ′= h   xr  mod  p.   
         [0103]    The proving mechanism  600  sends these α′, β′ and γ′ to the verifying mechanism  650 .  
         [0104]    The proving mechanism  600  further includes a prover  605 , which proves the equality of the discrete logarithms of α′ to the base α and β′ to the base β and the equality of the discrete logarithms of α′ to the base g and γ′ to the base h.  
         [0105]    The verifying mechanism  650  further includes a first verifier  652 , a comparator  654 , and a decision section  655 . The first verifier  652  verifies about the equality of the discrete logarithms of α′ to the base α and β′ to the base β and the equality of the discrete logarithms of α′ to the base g and γ′ to the base h. If these equalities are both verified, then the verification acceptance is determined. The comparator  654  compares β′ and γ′ to determine whether β′≠γ′.  
         [0106]    The decision section  655  decides the inequality of the discrete logarithms of α to the base g and β to the base h when the verification result of the first verifier  652  is verification acceptances and the comparator  654  determine that β′≠γ′. When the comparator  654  determine that β′=γ′, the decision section  555  decides the equality of the discrete logarithms of α to the base g and β to the base h.  
         [0107]    Embodiments  
         [0108]    1. First Embodiment  
         [0109]    1.1) System Configuration  
         [0110]    Referring to FIG. 7, the system has a proving mechanism  700  and a verifying mechanism  750 . The proving mechanism  700  includes a random number generator  701 , a public information memory  702 , a private information memory  703 , a variable converter  704 , a first prover  705  and a second prover  709 . The first prover  705  includes a second random number generator  706 , a first commitment section  707 , and a first response section  708 . The second prover  709  includes a third random number generator  710 , a second commitment section  711 , and a second response section  712 . The random number generator  701 , the variable converter  704 , the first prover  705  and the second prover  709  may be implemented by running corresponding programs on a computer.  
         [0111]    The verifying mechanism  750  includes a public information memory  751 , a first verifier  752 , a second verifier  755 , a third verifier  758 , and a decision section  759 . The first verifier  752  includes a first challenge section  753  and a second decision section  754 . The second verifier  755  includes a second challenge section  756  and a third decision section  757 . The first verifier  752 , the second verifier  755 , the third verifier  758 , and the decision section  759  may be implemented by running corresponding programs on a computer.  
         [0112]    The first prover  705  and the first verifier  752  communicate with each other such that first commitments v[1] and v[2] are sent from the first prover  705  to the first verifier  752 , a first challenge c[1] is sent from the first verifier  752  back to the first prover  705 , and a first response t[1] is sent from the first prover  705  to the first verifier  752 . The first verifier  752  determines whether the first response t[1] is consistent with the first commitments v[1] and v[2] and the first challenge c[1].  
         [0113]    The second prover  709  and the second verifier  755  communicate with each other such that second commitments v[3] and v[4] is sent from the second prover  709  to the second verifier  755 , a second challenge c[2] is sent from the second verifier  755  back to the second prover  709 , and a second response t[2] is sent from the second prover  709  to the second verifier  755 . The second verifier  755  determines whether the second response t[2] is consistent with the second commitments v[3] and v[4] and the second challenge c[2].  
         [0114]    1.2) Operation  
         [0115]    An operation of the present embodiment will be described in detail.  
         [0116]    The random number generator  701  generates a random number r εZ/qZ.  
         [0117]    The public information memory  702  stores p, q, g, h, α and β. The same public information are stored in a public information memory  751  of the verifying mechanism  750 .  
         [0118]    The private information memory  703  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0119]    The random number generator  701 , the public information memory  702  and the private information memory  703  output p, q, g, h, α, β, x, and r to the variable converter  704 . The variables p, q, g, h, α and β are also referred by the first prover  705  and the second prover  709 .  
         [0120]    The variable converter  704  uses these variables to produce α′, β′, γ′ as follows: 
         α′=α r ; 
         β′=β r ; and 
         γ′= h   xr . 
         [0121]    The proving mechanism  700  sends these α′, β′ and γ′ to the verifying mechanism  750 . These α′, β′ and γ′ are also referred by the first prover  705 , the second prover  709 , the first to third verifiers  752 ,  756  and  758 .  
         [0122]    1.3) First Prover/Verifier  
         [0123]    In the first prover  705 , the second random number generator  706  generates a random numbers s[1] εZ/qZ. The first commitment section  707  uses the second random number s[1] to compute the first commitments v[1] and v[2]: 
           v[ 1]=α s[1]  mod  p ; and 
           v[ 2]=β s[1]  mod  p.   
         [0124]    The first commitment section  707  sends the first commitments v[1] and v[2] to the first verifier  752  of the verifying mechanism  750 .  
         [0125]    In the first verifier  752 , after having received the first commitments v[1] and v[2], the first challenge section  753  randomly generates a first challenge c [1] εZ/qZ and sends it back to the first prover  705  of the proving mechanism  700 .  
         [0126]    When having received the first challenge c[1], the first response section  708  of the first prover  705  computes a first response t[1]: 
           t[ 1 ]=s[ 1]+ r c[ 1] mod  q.   
         [0127]    The first response t[1] is sent to the first verifier  752  of the verifying mechanism  750 .  
         [0128]    In the first verifier  752 , the second decision section  754  decides whether 
         [0129]    [0129] v[ 1] α′ c =α t[1]  mod  p ; and 
           v[ 2] β′ c =β t[1]  mod  p.   
         [0130]    If the equality is verified, then the verification acceptance is determined.  
         [0131]    1.4) Second Prover/Verifier  
         [0132]    In the second prover  709 , the third random number generator  710  generates a random number s[2] εZ/qZ. The second commitment section  711  uses the third random number s[2] to compute the second commitments v[3] and v[4]: 
           v[ 3 ]=g   s[2]  mod  p ; and 
           v[ 4 ]=h   s[2]  mod  p.   
         [0133]    The second commitment section  711  sends the second commitments v[3] and v[4] to the second verifier  755  of the verifying mechanism  750 .  
         [0134]    In the second verifier  755 , after having received the second commitments v[3] and v[4], the second challenge section  756  randomly generates a second challenge c[2] εZ/qZ and sends it back to the second prover  709  of the proving mechanism  700 .  
         [0135]    When having received the second challenge c[2], the second response section  712  of the second prover  709  computes a second response t[2]: 
           t[ 2 ]=s[ 2]+ x r c[ 2] mod  q,   
         [0136]    where x is private information stored in the private information memory  702  and r is a random number generated by the random number generator  701 . The second response t[2] is sent to the second verifier  755  of the verifying mechanism  750 .  
         [0137]    In the second verifier  755 , the third decision section  757  decides whether 
           v[ 3] α′ c   =g   t[2]  mod  p ; and 
           v[ 4] γ′= h   t[2]  mod  p.   
         [0138]    If the equality is verified, then the verification acceptance is determined.  
         [0139]    1.5) Decision  
         [0140]    The third verifier  758  verifies about the equality of β′ and γ′ and, if it is verified that β′=γ′, then the verification acceptance is determined.  
         [0141]    The decision section  759  outputs “OK” when the verification results of the first to third verifiers  754 ,  757  and  758  are all verification acceptances. Otherwise the decision section  759  outputs “NG”.  
         [0142]    α′, β′ and γ′ may be sent to the verifying mechanism  750  at the same time when the first commitments v[1] and v[2] are sent to the verifying mechanism  750 . The first commitments v[1] and v[2] may be sent to the verifying mechanism  750  at the same time when the second commitments v[3] and v[4] are sent. Thereafter, the first challenge c[1] and the second challenge c[2] may be simultaneously sent back to the proving mechanism  700 . After having sent the first and second challenges c[1] and c[2], the first and second responses t[1] and t[2] may be simultaneously sent to the verifying mechanism  750 .  
         [0143]    The present embodiment provides a zero-knowledge proving scheme for proving the equality of the discrete logarithms. However, the third verifier  758  may verify about the inequality of β′ and γ′ and, if it is verified that β′≠γ′, then the verification acceptance is determined. In this case, the present embodiment also provides a zero-knowledge proving scheme for proving the inequality of the discrete logarithms.  
         [0144]    2. Second Embodiment  
         [0145]    2.1) System Configuration  
         [0146]    Referring to FIG. 8, the system according to the second embodiment includes a proving mechanism  800  and a verifying mechanism  850 , in which a first prover  801  and a first verifier  851  are different from those of the first embodiment as shown in FIG. 7, Therefore, FIG. 8 shows only the first prover  801  and the first verifier  851 , and other functional blocks are the same as shown in FIG. 7.  
         [0147]    The first prover  801  includes a second random number generator  802 , a first commitment section  803 , and a first response section  804 . The first verifier  851  includes a first challenge preparation section  853 , a first challenge section  854  and a second decision section  855 . As in the case of the first embodiment, the first prover  801  and a first verifier  851  may be implemented by running corresponding programs on a computer.  
         [0148]    The first prover  801  and the first verifier  851  communicate with each other such that first challenge preparation is sent from the first verifier  851  to the first prover  801 , first commitment v[1] and v[2] and random number w[1] are sent from the first prover  801  to the first verifier  851 , first challenge a[1] and b[1] are send from the first verifier  851  back to the first prover  801 , and a first response t[1] is sent from the first prover  801  to the first verifier  851 . The first verifier  851  determines whether the first response t[1] is consistent with the first commitments v[1] and v[2], the random number w[1] and the first challenges a[1] and b[1]. More detailed operation of the present embodiment will be described below.  
         [0149]    2.2) Operation  
         [0150]    In the first verifier  851 , the third random number generator  852  generates random numbers a[1], b[1] εZ/qZ.  
         [0151]    The first challenge preparation section  853  uses the random numbers a [1], b [1] to compute first challenge preparation A[1]: 
           A[ 1 ]=g   a[1] α b[1]  mod  p.   
         [0152]    The first challenge preparation A[1] is sent to the first prover  801 .  
         [0153]    In the first prover  801 , the second random number generator  802  generates random numbers s[1]εZ/qZ and w[1]εZ/qZ. The first commitment section  803  uses the random number s[1] to compute the first commitments v[1] and v[2]: 
           v[ 1]=α s[1]  mod  p ; and 
           v[ 2]=β s[1]  mod  p.   
         [0154]    After having received the first challenge preparation A[1] from the first verifier  851 , the first commitment section  803  sends the first commitments v[1] and v[2] and the random number w[1] to the first verifier  851 .  
         [0155]    In the first verifier  851 , when having received the first commitments v[1] and v[2] and the random number w[1], the first challenge section  854  sends the random numbers a[1], b[1] as the first challenge to the first prover  801 .  
         [0156]    When having received the first challenges a[1], b[1], the first response section  804  computes g a[1] α b[1]  mod p and proves: 
           A[ 1 ]=g   a[1] α b[1] mod    p.   
         [0157]    If the equality of A[1] and g a[1] α b[1]  mod p is not proved, then the proof is terminated.  
         [0158]    When the equality of A[1] and g a[1] α b[1]  mod p is proved, the first response section  804  computes a first response t[1]: 
           t[ 1 ]=s[ 1 ]+r  ( a[ 1 ]+w[ 1]) mod  q,   
         [0159]    where r is a random number generated by the random number generator  701 . The first response t[1] is sent to the first verifier  851 .  
         [0160]    In the first verifier  851 , the second decision section  855  decides whether 
           v[ 1]α′ {a[1]+w[1]} =α t[1]  mod  p ; and 
           v[ 2]β′ {a[1]+w[1]} =β t[1]  mod  p.   
         [0161]    If the equality is verified, then the verification acceptance is determined.  
         [0162]    3. Third Embodiment  
         [0163]    3.1) System Configuration  
         [0164]    Referring to FIG. 9, the system according to the third embodiment includes a proving mechanism  900  and a verifying mechanism  950 , in which a first prover  901  and a first verifier  951  are different from those of the first embodiment as shown in FIG. 7. Therefore, FIG. 9 shows only the first prover  901  and the first verifier  951 , and other functional blocks are the same as shown in FIG. 7.  
         [0165]    The first prover  901  includes a second random number generator  902 , a first commitment section  903 , a first automatic challenge section  904 , a first response section  905 , and a first proven text sending section  906 . The first verifier  951  includes a first automatic challenge section  952  and a second decision section  953 .  
         [0166]    The first commitment section  903  uses a random number s[1] to convert α and β to produce first commitments v[1] and v[2]. The first automatic challenge section  904  produces first automatic challenge c[1] from the first commitments v[1] and v[2]. The first response section  905  computes first response t[1] from the first automatic challenge c[1] using the random number r and the random number s[1]. The first proven text sending section  906  sends the first commitments v[1] and v[2] and the first response t[1] as a first proven text to the first verifier  951 .  
         [0167]    In the first verifier  951 , the first automatic challenge section  952  produces first automatic challenge c′[1] from the first commitments v[1] and v[2]. The second decision section  953  determines whether the first response t[1] is consistent with the first commitments v[1] and v[2] and the first automatic challenge c′[1].  
         [0168]    As in the case of the first embodiment, the first prover  901  and the first verifier  951  may be implemented by running corresponding programs on a computer. More detailed operation of the present embodiment will be described below.  
         [0169]    3.2) Operation  
         [0170]    In the first prover  901 , the second random number generator  902  generates random numbers s [1]εZ/qZ. The first commitment section  903  uses the random number s[1] to compute the first commitments v[1] and v[2]: 
           v[ 1]=α a[1]  mod  p ; and 
           v[ 2]−β α[1]  mod  p.   
         [0171]    The first automatic challenge section  904  produces first automatic challenge c[1] using the first commitment v[1] and v[2]: 
           c[ 1](ε Z/qZ ) =Hash( p, q, g, h, α, β, α′, β′, γ′, v[ 1],  v[ 2]), 
         [0172]    where Hash indicates a hash function such as “SHA-1”, which is a one-directional function.  
         [0173]    The first response section  905  computes a first response t[1]: 
           t[ 1 ]=s[ 1 ]+r c[ 1] mod  q,   
         [0174]    where r is a random number generated by the random number generator  701 .  
         [0175]    The first proven text sending section  906  produces a proven text (v[1], v[2], t[1]) and send it to the first verifier  951 .  
         [0176]    In the first verifier  951 , the first automatic challenge section  952  produces first automatic challenge c′[1]: 
           c′[ 1] (ε Z/qZ ) =Hash ( p, q, g, h, α, β, α′, β′, γ′, v[ 1 ], v[ 2]). 
         [0177]    Thereafter, the second decision section  953  decides whether 
           v[ 1]α′ c′[1] =α t[1]  mod  p ; and 
           v[ 2]β′ c′[1] =β t[1]  mod  p.   
         [0178]    If the equality is verified, then the verification acceptance is determined.  
         [0179]    4. Fourth Embodiment  
         [0180]    4.1) System Configuration  
         [0181]    Referring to FIG. 10, the system according to the fourth embodiment includes a proving mechanism  1000  and a verifying mechanism  1050 , in which a first prover  1001  and a first verifier  1051  are different from those of the first embodiment as shown in FIG. 7. Therefore, FIG. 10 shows only the first prover  1001  and the first verifier  1051 , and other functional blocks are the same as shown in FIG. 7.  
         [0182]    The first prover  1001  includes a second random number generator  1002 , a first commitment section  1003 , a first automatic challenge section  1004 , a first response section  1005 , and a first proven text sending section  1006 . The first verifier  1051  includes a second decision section  1053 .  
         [0183]    The first commitment section  1003  uses a random number s[1] to convert α and β to produce first commitments v[1] and v[2]. The first automatic challenge section  1004  produces first automatic challenge c[1] from the first commitment v[1] and v[2]. The first response section  1005  computes first response t[1] from the first automatic challenge c[1] using the random number r and the random number s[1]. The first proven text sending section  1006  sends the first automatic challenge c[1] and the first response t[1] as a first proven text to the first verifier  1051 .  
         [0184]    In the first verifier  1051 , the second decision section  1053  determines whether the first automatic challenge c[1] is consistent with the first response t[1].  
         [0185]    As in the case of the first embodiment, the first prover  1001  and the first verifier  1051  may be implemented by running corresponding programs on a computer. More detailed operation of the present embodiment will he described below.  
         [0186]    4.2) Operation  
         [0187]    In the first prover  1001 , the second random number generator  1002  generates random numbers s[1]εZ/qZ. The first commitment section  1003  uses the random number s[1] to compute the first commitments v[1] and v[2]: 
           v[ 1]=α s[1]  mod  p ; and 
           v[ 2]=β s[1]  mod  p.   
         [0188]    The first automatic challenge section  1004  produces first automatic challenge c[1] using the first commitments v[1] and v[2]:  
           c        [   1   ]            (     ∈     Z   /   qZ       )       =     Hash                     (     p   ,   q   ,   g   ,   h   ,   α   ,   β   ,     α   ′     ,     β   ′     ,     γ   ′     ,     v        [   1   ]       ,     v        [   2   ]         )     .                             
 
         [0189]    The first response section  1005  computes a first response t[1]: 
           t[ 1 ]=s[ 1 ]+r c[ 1] mod  q,   
         [0190]    where r is a random number generated by the random number generator  701 .  
         [0191]    The first proven text sending section  1006  produces a proven text (c[1], t[1]) and send it to the first verifier  1051 .  
         [0192]    In the first verifier  1051 , the second decision section  1053  decides whether: 
           c[ 1]=Hash( p, q, g, h, α, β, α′, β′, γ′, α   t[1] /α′ c  mod  p, β   t[1] /β′ c  mod  p ). 
         [0193]    If the equality is verified, then the verification acceptance is determined.  
         [0194]    5. Fifth Embodiment  
         [0195]    5.1) System Configuration  
         [0196]    Referring to FIG. 11, the system according to the fifth embodiment includes a proving mechanism  1100  and a verifying mechanism  1150 , in which a second prover  1101  and a second verifier  1151  are different from those of the first embodiment as shown in FIG. 7. Therefore, FIG. 11 shows only the second prover  1101  and the second verifier  1151 , and other functional blocks are the same as shown in FIG. 7.  
         [0197]    The second prover  1101  includes a fourth random number generator  1102 , a second commitment section  1103 , and a second response section  1104 . The second verifier  1151  includes a fifth random number generator  1152 , a second challenge preparation section  1153 , a second challenge section  1154  and a third decision section  1155 . As in the case of the first embodiment, the second prover  1101  and a second verifier  151  may be implemented by running corresponding programs on a computer.  
         [0198]    The second prover  1101  and the second verifier  1151  communicate with each other such that second challenge preparation A[2] is sent from the second verifier  1151  to the second prover  1101 , second commitments v[3] and v[4] and random number w[2] are sent from the second prover  1101  to the second verifier  1151 , second challenges a[2] and b[2] are sent from the second verifier  1151  to the second prover  1101 , and a second response L[2] is sent from the second prover  1101  to the second verifier  1151 . The second verifier  1151  determines whether the second response t[2] is consistent with the second commitments v[3] and v[4], the random number w[2] and the second challenges a[2] and b[2]. More detailed operation of the present embodiment will he described below.  
         [0199]    5.2) Operation  
         [0200]    In the first verifier  1151 , the fifth random number generator  1152  generates random numbers a[2], b[2]εZ/qZ.  
         [0201]    The second challenge preparation section  1153  uses the random numbers a[2], b[2] to compute second challenge preparation A [2]: 
           A[ 2 ]=g   a[2] α b[2] mod  p.   
         [0202]    The second challenge preparation A[2] is sent to the second prover  1101 .  
         [0203]    In the second prover  1101 , the fourth random number generator  1102  generates random numbers s[2]εZ/qZ and w[2]εZ/qZ. The second commitment section  1103  uses the random number s[2] to compute the second commitments v[3] and v[4]: 
           v[ 3 ]=g   s[2] mod  p ; and 
           v[ 4 ]=h   s[2] mod  p.   
         [0204]    After having received the second challenge preparation A[2] from the second verifier  1151 , the second commitment section  1103  sends the second commitments v[3] and v[4] and the random number w[2] to the second verifier  1151 .  
         [0205]    In the second verifier  1151 , when having received the second commitments v[3] and v[4] and the random number w[2], the second challenge section  1154  sends the random numbers a [2], b[2] as the second challenge to the second prover  1101 .  
         [0206]    When having received the second challenges a[2], b[2], the second response section  1104  computes g a[2] α b[2]  mod p and proves: 
           A[ 2 ]=g   a[2] α b[2]  mod  p.   
         [0207]    If the equality of A[2] and g a[2] α b[2]  mod p is not proved, then the proof is terminated.  
         [0208]    When the equality of A[2] and g a[2] α b [2]  mod p is proved, the second response section  1104  computes a second response t[2]: 
           t[ 2 ]=s[ 2 ]+x r  ( a[ 2 ]+w[ 2]) mod  q,   
         [0209]    where x is the private information stored in the private information memory  703  and r is a random number generated by the random number generator  701 . The second response t[2] is sent to the second verifier  1151 .  
         [0210]    In the second verifier  1151 , the third decision section  1155  decides whether 
           v[ 3]α′ {a[2]+w[2]}   =g   t[2]  mod  p ; and 
           v[ 4]γ′ {a[2]+w[2]}   =h   t[2]  mod  p.   
         [0211]    If the equality is verified, then the verification acceptance is determined.  
         [0212]    6. Sixth Embodiment  
         [0213]    6.1) System Configuration  
         [0214]    Referring to FIG. 12, the system according to the sixth embodiment includes a proving mechanism  1200  and a verifying mechanism  1250 , in which a second prover  1201  and a second verifier  1251  are different from those of the first embodiment as shown in FIG. 7. Therefore, FIG. 12 shows only the second prover  1201  and the second verifier  1251 , and other functional blocks are the same as shown in FIG. 7.  
         [0215]    The second prover  1201  includes a third random number generator  1202 , a second commitment section  1203 , a second automatic challenge section  1204 , a second response section  1205 , and a second proven text sending section  1206 . The second verifier  1251  includes a second automatic challenge section  1252  and a third decision section  1253 .  
         [0216]    The second commitment section  1203  uses a random number s[2] to convert bases g and h to produce second commitments v[3] and v[4]. The second automatic challenge section  1204  produces second automatic challenge c[2] from the second commitments v[3] and v[4]. The second response section  1205  computes second response t[2] from the second automatic challenge c[2] using the private information x, the random number r and the random number s[2]. The second proven text sending section  1206  sends the second commitments v[3] and v[4] and the second response t[2] as a second proven text to the second verifier  1251 .  
         [0217]    In the second verifier  1251 , the second automatic challenge section  1252  produces second automatic challenge c′[2] from the second commitments v[3] and v[4]. The third decision section  1253  determines whether the second response t[2] is consistent with the second commitments v[3] and v[4] and the second automatic challenge c′[2].  
         [0218]    As in the case of the first embodiment, the second prover  1201  and the second verifier  1251  may be implemented by running corresponding programs on a computer. More detailed operation of the present embodiment will be described below.  
         [0219]    6.2) Operation  
         [0220]    In the second prover  1201 , the third random number generator  1202  generates random numbers s[2]εZ/qZ. The second commitment section  1203  uses the random number s[2] to compute the second commitments v[3] and v[4]: 
           v[ 4 ]=h   a[2]  mod  p.   
         [0221]    The second automatic challenge section  1204  produces second automatic challenge c[2] using the second commitments v[3] and v[4]:  
           c        [   2   ]            (     ∈     Z   /   qZ       )       =     Hash                     (     p   ,   q   ,   g   ,   h   ,   α   ,   β   ,     α   ′     ,     β   ′     ,     γ   ′     ,     v        [   3   ]       ,     v        [   4   ]         )     .                             
 
         [0222]    The second response section  1205  computes a second response t[2]: 
           t[ 2 ]=s[ 2] +x r c[ 2] mod  q,   
         [0223]    where x is the private information and r is a random number generated by the random number generator  701 .  
         [0224]    The second proven text sending section  1206  produces a proven text (v[3], v[4], t[2]) and send it to the second verifier  1251 .  
         [0225]    In the second verifier  1251 , the second automatic challenge section  1252  produces second automatic challenge c′[2]:  
             c   ′          [   2   ]            (     ∈     Z   /   qZ       )       =     Hash                     (     p   ,   q   ,   g   ,   h   ,   α   ,   β   ,     α   ′     ,     β   ′     ,     γ   ′     ,     v        [   3   ]       ,     v        [   4   ]         )     .                             
 
         [0226]    Thereafter, the third decision section  1253  decides whether 
           v[ 3]α′ c′[2]   =g   t[2]  mod  p ; and 
           v[ 4]γ′ c′[2]   =h   t[2]  mod  p.   
         [0227]    If the equality is verified, then the verification acceptance is determined.  
         [0228]    7 Seventh Embodiment  
         [0229]    7.1) System Configuration  
         [0230]    Referring to FIG. 13, the system according to the seventh embodiment includes a proving mechanism  1300  and a verifying mechanism  1350 , in which a second prover  1301  and a second verifier  1351  are different from those of the first embodiment as shown in FIG. 7. Therefore, FIG. 13 shows only the second prover  1301  and the second verifier  1351 , and other functional blocks are the same as shown an FIG. 7.  
         [0231]    The second prover  1301  includes a third random number generator  1302 , a second commitment section  1303 , a second automatic challenge section  1304 , a second response section  1305 , and a second proven text sending section  1306 . The second verifier  1351  includes a third decision section  1353 .  
         [0232]    The second commitment section  1303  uses a random number s[2] to convert bases g and h to produce second commitments v[3] and v[4]. The second automatic challenge section  1304  produces second automatic challenge c[2] from the second commitments v[3] and v[4]. The second response section  1305  computes second response t[2] from the second automatic challenge c[2] using the private information x, the random number r and the random number s[2]. The second proven text sending section  1306  sends the second automatic challenge c[2] and the second response t[2] as a second proven text to the second verifier  1351 .  
         [0233]    In the second verifier  1351 , the third decision section  1353  determines whether the second response t[2] is consistent with the second automatic challenge c[2].  
         [0234]    As in the case of the first embodiment, the second prover  1301  and the second verifier  1351  may be implemented by running corresponding programs on a computer. More detailed operation of the present embodiment will be described below.  
         [0235]    7.2) Operation  
         [0236]    In the second prover  1301 , the third random number generator  1302  generates random numbers s[2]εZ/qZ. The second commitment section  1303  uses the random number s[2] to compute the second commitments v[3] and v[4]: 
           v[ 3 ]=g   s[2]  mod  p ; and 
           v[ 4 ]=h   s[2]  mod  p.   
         [0237]    The second automatic challenge section  1304  produces second automatic challenge c[2] using the second commitment v[3] and v[4]:  
           c        [   2   ]            (     ∈     Z   /   qZ       )       =     Hash                     (     p   ,   q   ,   g   ,   h   ,   α   ,   β   ,     α   ′     ,     β   ′     ,     γ   ′     ,     v        [   3   ]       ,     v        [   4   ]         )     .                             
 
         [0238]    The second response section  1305  computes a second response t[2]: 
           t[ 2 ]=s[ 2 ]+x r c[ 2] mod  q , 
         [0239]    where x is the private information and r is a random number generated by the random number generator  701 .  
         [0240]    The second proven text sending section  1306  produces a proven text (c[2], t[2]) and send it to the second verifier  1351 .  
         [0241]    In the second verifier  1351 , the third decision section  1353  decides whether: 
           c[ 2]=Hash( p, q, α, β, α′, β′, γ′, g   t[2] /α′ c[2]  mod  p, h   t[2] /γ′ c[2]  mod  p ). 
         [0242]    If the equality is verified, then the verification acceptance is determined.  
         [0243]    8. Eighth Embodiment  
         [0244]    8.1) System Configuration  
         [0245]    Referring to FIG. 14, the system according to the eighth embodiment has a proving mechanism  1400  and a verifying mechanism  1450 . The proving mechanism  1400  includes a random number generator  1401 , a public information memory  1402 , a private information memory  1403 , a variable converter  1404 , a prover  1405 . The prover  1405  includes a second random number generator  1406 , a commitment section  1407 , and a response section  1408 . The random number generator  1401 , the variable converter  1404  and the prover  1405  may be implemented by running corresponding programs on a computer.  
         [0246]    The verifying mechanism  1450  includes a public information memory  1451 , a first verifier  1452 , a second verifier  1458 , and a decision section  1459 . The first verifier  1452  includes a challenge section  1453  and a second decision section  1454 . The first verifier  1452 , the second verifier  1458 , and the decision section  1459  may be implemented by running corresponding programs on a computer.  
         [0247]    The prover  1405  and the first verifier  1452  communicate with each other such that commitments v[1], v[2], v[3], v[4] is sent from the prover  1405  to the first verifier  1452 , a challenge c is sent from the first verifier  1452  back to the prover  1405 , and responses t[1], t[2] is sent from the prover  1405  to the first verifier  1452 . The first verifier  1452  determines whether the responses t[1], t[2] is consistent with the commitments v[1], v[2], v[3], v[4] and the challenge c.  
         [0248]    8.2) Operation  
         [0249]    An operation of the present embodiment will be described in detail.  
         [0250]    The random number generator  1401  generates a random number r εZ/qZ.  
         [0251]    The public information memory  1402  stores p, q, g, h, α and β. The same public information are stored in a public information memory  1451  of the verifying mechanism  1450 .  
         [0252]    The private information memory  1403  stores private information x satisfying α=g x  mod p, which is the discrete logarithm of α to the base g, that is, x=log g α.  
         [0253]    The random number generator  1401 , the public information memory  1402  and the private information memory  1403  output p, q, g, h, α, β, x, and r to the variable converter  1404 . The variables p, q, g, h, α and β are also referred by the prover  1405 , the first verifier  1452  and the second verifier  1458 .  
         [0254]    The variable converter  1404  uses these variables to produce α′, β′, γ as follows: 
         α′=α r ; 
         β′=β r ; and 
         γ′= h   xr . 
         [0255]    The proving mechanism  1400  sends these α′, β′ and γ′ to the verifying mechanism  1450 . These α′, β′ and γ′ are also referred by the prover  1405 , the first and second verifiers  1452  and  1458 .  
         [0256]    [0256] 8 . 3 ) Prover and First Verifier  
         [0257]    In the prover  1405 , the second random number generator  1406  generates a random numbers s[1], s[2] εZ/qZ. The commitment section  1407  uses the random numbers s[1], s[2] to compute the commitments v[1], v[2], v[3], v[4]: 
           v[ 1]=α s[1]  mod  p;   
           v[ 2]=β s[1]  mod  p;   
           v[ 3 ]=g   s[2]  mod  p ; and 
           v[ 4 ]=h   s[2]  mod  p.   
         [0258]    The commitment section  1407  sends the commitments v[1], v,[2], v[3], v[4] to the first verifier  1452  of the verifying mechanism  1450 .  
         [0259]    In the first verifier  1452 , after having received the commitment, the challenge section  1453  randomly generates a challenge c εZ/qZ and sends it back to the prover  1405  of the proving mechanism  1400 .  
         [0260]    When having received the challenge c, the response section  1408  of the prover  1405  computes responses t[1], t[2]: 
           t[ 1] =s[ 1] +r c  mod  q ; and 
           t[ 2] =s[ 2] +x r c  mod  q.   
         [0261]    The computed responses t [1], t [2] is sent to the first verifier  1452  of the verifying mechanism  1450 .  
         [0262]    In the first verifier  1452 , the second decision section  1454  decides whether 
           v[ 1]α′ c =α t[1]  mod  p;   
           v[ 2]β′ c =β t[1]  mod  p;   
           v[ 3]α′ c   =g   t[2]  mod  p ; and 
           v[ 4]γ′ c   =h   t[2]  mod  p.   
         [0263]    If the equality is verified, then the verification acceptance is determined.  
         [0264]    8.4) Decision  
         [0265]    The second verifier  1458  verifies about the equality of β′ and γ′ and, if it is verified that β′=γ′, then the verification acceptance is determined.  
         [0266]    The decision section  1459  outputs “OK” when the verification results of the first and second verifiers  1454  and  1458  are all verification acceptances. Otherwise the decision section  1459  outputs “NG”.  
         [0267]    α′, β′ and γ′ may be sent to the verifying mechanism  750  at the same time when the commitments v[1], v[2], v[3], v[4] are sent to the verifying mechanism  1450 .  
         [0268]    The present embodiment provides a zero-knowledge proving scheme for proving the equality of the discrete logarithms. However, the third verifier  758  may verify about the inequality of β′ and γ′ and, if it is verified that β′≠γ′, then the verification acceptance is determined. In this case, the present embodiment also provides a zero-knowledge proving scheme for proving the inequality of the discrete logarithms.  
         [0269]    9. Ninth Embodiment  
         [0270]    9.1) System Configuration  
         [0271]    Referring to FIG. 15, the system according to the ninth embodiment includes a proving mechanism  1500  and a verifying mechanism  1550 , in which a first prover  1501  and a first verifier  1551  are different from those of the eighth embodiment as shown in FIG. 14. Therefore, FIG. 15 shows only the first prover  1501  and the first verifier  1551 , and other functional blocks are the same as shown in FIG. 14.  
         [0272]    The first prover  1501  includes a second random number generator  1502 , a commitment section  1503 , and a response section  1504 . The first verifier  1551  includes a challenge preparation section  1553 , a challenge section  1554  and a second decision section  1555 . As in the case of the eighth embodiment, the first prover  1501  and the first verifier  1551  may be implemented by running corresponding programs on a computer.  
         [0273]    The first prover  801  and the first verifier  851  communicate with each other such that challenge preparation A is sent from the first verifier  1551  to the first prover  1501 , commitments v[1], v[2], v[3], v[4] and random number w are sent from the first prover  1501  to the first verifier  1551 , challenge a and b are sent from the first verifier  1551  back to the first prover  1501 , and responses t[1], t[2] is sent from the first prover  1501  to the first verifier  1551 . The first verifier  1551  determines whether the responses t[1], t[2] is consistent with the commitments v[1], v[2], v[3], v[4], the random number w and the challenge a and b. More detailed operation of the present embodiment will be described below.  
         [0274]    9.2) Operation  
         [0275]    In the first verifier  1551 , the third random number generator  1552  generates random numbers a, b εZ/qZ.  
         [0276]    The challenge preparation section  1553  uses the random numbers a, b to compute challenge preparation A: 
           A=g   a  α b  mod  p.   
         [0277]    The challenge preparation A is sent to the first prover  1501 .  
         [0278]    In the first prover  1501 , the second random number generator  1502  generates random numbers s[1], s[2]εZ/qZ and w εZ/qZ. The commitment section  1503  uses the random numbers s[1], s[2] to compute commitments v[1], v[2], v[3], v[4]: 
           v[ 1]=α s[1]  mod  p;   
           v[ 2]=β s[1]  mod  p;   
           v[ 3]= g   s[2]  mod  p ; and 
           v[ 4]= h   s[2]  mod  p.   
         [0279]    After having received the challenge preparation A from the first verifier  1551 , the commitment section  1503  sends the commitments v[1], v[2], v[3], v[4] and the random number w to the first verifier  1551 .  
         [0280]    In the first verifier  1551 , when having received the commitments v[1], v[2], v[3], v[4] and the random number w, the challenge section  1554  sends the random numbers a, b as the challenge to the first prover  1501 .  
         [0281]    When having received the challenges a, b, the response section  1504  computes g a  α b  mod p and proves: 
           A=g   a  α b  mod  p.   
         [0282]    If the equality of A and g a  α b  mod p is not proved, then the proof is terminated.  
         [0283]    When the equality of A and g a  α b  mod p is proved, the response section  1504  computes response t[1], t[2]: 
           t[ 1 ]=s[ 1 ]+r  ( a+w ) mod  q ; and 
           t[ 2 ]=s[ 2 ]+x r  ( a+w ) mod  q,   
         [0284]    where r is a random number generated by the random number generator  1401  and x is the private information. The responses t[1], t[2] is sent to the first verifier  1551 .  
         [0285]    In the first verifier  1551 , the second decision section  1555  decides whether 
           v[ 1]α′ {a+w} =α t[ 1] mod  p;   
           v[ 2]β′ {a+w} =β t[ 1] 0  mod  p;   
           v[ 3]α′ {a+w}   =g   t[2]  mod  p ; and 
           v[ 4]γ′ {a+w}   =h   t[2]  mod  p.   
         [0286]    If the equality is verified, then the verification acceptance is determined.  
         [0287]    10. Tenth Embodiment  
         [0288]    10.1) System Configuration  
         [0289]    Referring to FIG. 16, the system according to the tenth embodiment includes a proving mechanism  1600  and a verifying mechanism  1650 , in which a prover  1601  and a first verifier  1651  are different from those of the eighth embodiment as shown in FIG. 14. Therefore, FIG. 16 shows only the prover  1601  and the first verifier  1651 , and other functional blocks are the same as shown in FIG. 14.  
         [0290]    The prover  1601  includes a second random number generator  1602 , a commitment section  1603 , an automatic challenge section  1604 , a response section  1605 , and a proven text sending section  1606 . The first verifier  1651  includes an automatic challenge section  1652  and a second decision section  1653 .  
         [0291]    The commitment section  1603  uses random numbers s[1], s[2] to convert α, β, g and h to produce commitments v[1], v[2], v[3], v[4]. The automatic challenge section  1604  produces automatic challenge c from the commitments v[1], v[2], v[3], v[4]. The response section  1605  computes responses t[1], t[2] from the automatic challenge c using the private information x, the random number r and the random numbers s[1], s[2]. The proven text sending section  1606  sends the commitments v[1], v[2], v[3], v[4] and the responses t[1], t[2] as a proven text to the first verifier  1651 .  
         [0292]    In the first verifier  1651 , the automatic challenge section  1652  produces automatic challenge c′ from the commitments v[1], v[2], v[3], v[4]. The second decision section  1653  determines whether the response t[1], t[2] is consistent with the commitments v[1], v[2], v[3], v[4] and the automatic challenge c′.  
         [0293]    As in the case of the eighth embodiment, the prover  1601  and the first verifier  1651  may be implemented by running corresponding programs on a computer. More detailed operation of the present embodiment will be described below.  
         [0294]    10.2) Operation  
         [0295]    In the prover  1601 , the second random number generator  1602  generates random numbers s[1], s[2] εZ/qZ. The commitment section  1603  uses the random numbers s[1], s[2] to compute the commitments v[1], v[2], v[3], v[4]: 
           v[ 1]=α s[1]  mod  p;   
           v[ 2]=β s[1]  mod  p;   
           v[ 3]= g   s[2]  mod  p ; and 
           v[ 4]= h   s[2]  mod  p.   
         [0296]    The automatic challenge section  1604  produces the automatic challenge c using the commitments v[1], v[2], v[3], v[4]: 
           c  (ε Z/qZ )=Hash( p, q, g, h, α, β, α′, β′, γ′, v[ 1] , v[ 2] , v[ 3] , v[ 4]). 
         [0297]    The response section  1605  computes the response t[1], t[2]: 
           t[ 1] =s[ 1] +r c  mod  q ; and 
           t[ 2] =s[ 2] +x r c  mod  q,   
         [0298]    where x is the private information and r is a random number generated by the random number generator  1401 .  
         [0299]    The proven text sending section  1606  produces a proven text (v[1], v[2], v[3], v[4], t[1], t[2]) and send it to the first verifier  1651 .  
         [0300]    In the first verifier  1651 , the automatic challenge section  1652  produces automatic challenge c′: 
           c′ ((ε Z/qZ )=Hash ( p, q, g, h, α, β, α′, β′, γ′, v[ 1] , v[ 2 ], v[ 3 ], v[ 4]). 
         [0301]    Thereafter, the second decision section  1653  decides whether 
           v[ 1]α′ c′ =α t[1]  mod  p;   
           v[ 2]β′ c′ =β t[1]  mod  p;   
           v[ 3]α′ c′   =g   t[2]  mod  p ; and 
           v[ 4]γ′ c′   =h   t[2]  mod  p.   
         [0302]    If the equality is verified, then the verification acceptance is determined.  
         [0303]    11. Eleventh Embodiment  
         [0304]    11.1) System Configuration  
         [0305]    Referring to FIG. 17, the system according to the eleventh embodiment includes a proving mechanism  1700  and a verifying mechanism  1750 , in which a prover  1701  and a first verifier  1751  are different from those of the eighth embodiment as shown in FIG. 14. Therefore, FIG. 17 shows only the prover  1701  and the first verifier  1751 , and other functional blocks are the same as shown in FIG. 14.  
         [0306]    The prover  1701  includes a second random number generator  1702 , a commitment section  1703 , an automatic challenge section  1704 , a response section  1705 , and a proven text sending section  1706 . The first verifier  1751  includes a second decision section  1753 .  
         [0307]    The commitment section  1703  uses random numbers s[1], s[2] to convert α, β, q and h to produce commitments v[1], v[2] v[3], v[4]. The automatic challenge section  1704  produces automatic challenge c from the commitments v[1], v[2], v[3], v[4]. The response section  1705  computes responses t[1], t[2] from the automatic challenge c using the private information x, the random number r and the random numbers s[1], s[2]. The proven text sending section  1706  sends the automatic challenge c and the responses t[1], t[2] as a proven text to the first verifier  1751 .  
         [0308]    In the first verifier  1751 , the second decision section  1753  determines whether the response t[1], t[2] is consistent with the automatic challenge c.  
         [0309]    As in the case of the eighth embodiment, the prover  1701  and the first verifier  1751  may be implemented by running corresponding programs on a computer. More detailed operation of the present embodiment will be described below.  
         [0310]    11.2) Operation  
         [0311]    In the prover  1701 , the second random number generator  1702  generates random numbers s[1], s[2] εZ/qZ. The commitment section  1703  uses the random numbers s[1], s[2] to compute the commitments v[1], v[2], v[3], v[4]: 
           v[ 1]=α s[1]  mod  p;   
           v[ 2]=β s[1]  mod  p;   
           v[ 3] =g   s[2]  mod  p ; and 
           v[ 4] =h   s[2]  mod  p.   
         [0312]    The automatic challenge section  1704  produces the automatic challenge c using the commitments v[1], v[2], v[3], v[4]: 
           c  (ε Z/qZ )=Hash( p, q, g, h, α, β, α′, β′, γ′, v[ 1] , v[ 2 ], v[ 3 ], v[ 4]). 
         [0313]    The response section  1705  computes the response t[1], t[2]: 
           t[ 1 ]=s[ 1] +r c  mod  q ; and 
           t[ 2 ]=s[ 2] +x r c  mod  q,   
         [0314]    where x is the private information and r is a random number generated by the random number generator  1401 .  
         [0315]    The proven text sending section  1706  produces a proven text (c, t[1], t[2]) and send it to the first verifier  1751 .  
         [0316]    In the first verifier  1751 , the second decision section  1753  decides whether: 
           c= Hash( p, q, g, h, α, β, α′, β′, γ′, α   t[1] /α′ c  mod  p, β   t[1] /β′ c  mod  p, g   t[2] /α′ c  mod  p, h   t[2] /γ′ c  mod  p ). 
         [0317]    If the equality is verified, then the verification acceptance is determined.  
         [0318]    12. Twelfth Embodiment  
         [0319]    As shown in FIG. 18, a modification of the first embodiment as shown in FIG. 7 may be constructed as a twelfth embodiment. In the twelfth embodiment, the verifying mechanism  750  is provided with a comparator  1858  in place of the third verifier  758  and a decision section  1859  in place of the decision section  759 , of the first embodiment as shown in FIG. 7.  
         [0320]    The comparator  1858  compares β′ and γ′ to determine whether β′=γ′. The decision section  1859  decides the equality of the discrete logarithms when the verification results of the first and second verifiers  754  and  757  are verification acceptances and the comparator  1858  determine that β′=γ′. When the comparator  654  determine that β′≠γ′, the decision section  1859  decides the inequality of the discrete logarithms.  
         [0321]    13. Thirteenth Embodiment  
         [0322]    As shown in FIG. 19, a modification of the eighth embodiment as shown in FIG. 14 may be constructed as a thirteenth embodiment. In the thirteenth embodiment, the verifying mechanism  1450  is provided with a comparator  1958  in place of the second verifier  1458  and a decision section  1959  in place of the decision section  1459 , of the eighth embodiment as shown in FIG. 14. In other words, the thirteenth embodiment provides the zero-knowledge proving scheme for proving the equality or inequality of discrete logarithms.  
         [0323]    The comparator  1958  compares β′ and γ′ to determine whether β′=γ′. The decision section  1959  decides the equality of the discrete logarithms when the verification result of the second verifier  1454  is verification acceptance and the comparator  1958  determine that β′=γ′. When the comparator  1958  determine that β′≠γ′, the decision section  1959  decides the inequality of the discrete logarithms.  
         [0324]    As described above, provided with g, h, α (=g x  )mod p εG, and βεG, where G is a group of order q on mod p, β≠h x  mod p or β−h x  mod p can be efficiently proved without indicating x and h x  mod p. In addition, a prover can prove it solely.  
         [0325]    It should be noted that a combination of first prover and first verifier as described in the above second through fourth embodiments and a combination of second prover and second verifier as described in the above fifth through seventh embodiment, can be arbitrarily combined to form another embodiment of the present invention.  
         [0326]    In the above embodiments, a proving mechanism and a verifying mechanism can be communicated through wired or wireless connection. In other words, the proving mechanism and verifying mechanism can be implemented in any devices having wired or wireless signal transmitting and receiving functions.  
         [0327]    Although the invention has been described in its preferred embodiments, it is understood that modifications or variations will be apparent to those skilled in the art without departing from the spirit or scope of the invention.