Zero-knowledge proving system and method

A proving device for proving equality or inequality of two discrete logarithms, comprising:

• a 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 and the private information x as follows:
• α′=αr;
• β′=βr;
• and
• γ′=hxr,
• wherein said α′, β′ and γ′ are sent to the second mechanism;
• and
• a proving section for proving equality of a discrete logarithm of α′ to base α 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.

A verifying device for verifying proof provided by a proving device for proving equality or inequality of two discrete logarithms, comprising:

• a public information memory storing a designated operation scheme, two input numbers α and β, and two predetermined bases g and h;
• a verifying section corresponding to the proving device, for verifying equality of a discrete logarithm of α′ to base α 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, wherein said α′, β′ and γ′ are received from the proving device;
• a checking section for checking β′ 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.

A zero-knowledge proving method in a system comprising a first mechanism for proofing equality or inequality of two discrete logarithms and a second mechanism for verifying said equality or inequality, the method comprising the steps of:

• at the first mechanism,
• a) storing a designated operation scheme, two input numbers (hereinafter, denoted by α and β), and two predetermined bases (hereinafter, denoted by g and h) in a first public information memory;
• b) storing private information (hereafter, denoted by x) which is a discrete logarithm of α to the base g in a private information memory;
• c) generating a first random number (hereafter, denoted by r);
• d) 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
• γ′=hxr,
• wherein said α′, β′ and γ′ are sent to the second mechanism;
• and
• e) proving equality of a discrete logarithm of α′ to base α 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, and
• at the second mechanism,
• f) storing the designated operation scheme, the two input numbers α and β, and the two predetermined bases g and h in a second public information memory;
• g) verifying equality of a discrete logarithm of the received α′ to base α 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;
• h) checking the received β′ and γ′ to determine equality or inequality thereof;
• and
• i) deciding whether proof of the first mechanism is acceptable, depending on results of the verifying section and the checking section.

A computer program instructing a computer to implement a first mechanism for proving equality or inequality of two discrete logarithms and a second mechanism for verifying said equality or inequality, the program comprising the steps of:

• to implement the first mechanism,
• a) storing a designated operation scheme, two input numbers (hereinafter, denoted by α and β), and two predetermined bases (hereinafter, denoted by g and h) in a first public information memory;
• b) storing private information (hereafter, denoted by x) which is a discrete logarithm of α to the base g in a private information memory;
• c) generating a first random number (hereafter, denoted by r);
• d) 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
• γ′=hxr,
• wherein said α′, β′ and γ′ are sent to the second mechanism;
• and
• e) proving equality of a discrete logarithm of α′ to base α 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, and
• to implement the second mechanism,
• f) storing the designated operation scheme, the two input numbers α and β, and the two predetermined bases g and h in a second public information memory;
• g) verifying equality of a discrete logarithm of the received α′ to base α 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;
• h) checking the received β′ and γ′ to determine equality or inequality thereof;
• and
• i) deciding whether proof of the first mechanism is acceptable, depending on results of the verifying section and the checking section.