METHOD FOR PROVING ZERO KNOWLEDGE AS TO N-TH ROOT OF N-TH POWER RESIDUE

摘要

PURPOSE: To prevent cipher decoding and also save communication amount. ;CONSTITUTION: A communication line 3 connects electronic computers 1 and 2. In this case, a prover P transmits an n-th power residue (y) with a natural number N as modulus to a verifier V executing verification for receiving verification that the prover P knows the n-th root of the n-th power residue (u). In the meantime, the verifier V selectively transmits an optional integer (w) which is under n and is not negative to the prover P regardless of the value of the n-th power residue (y). According to this, the prover P transmits the product of the w-th power of the n-th root of the n-th power surplus (u) and the n-th root of the n-th power surplus (y) to the verifier V. Thus, the verifier V confirms that the n-th power of the product and the value obtained by multiplying the w-th power of the n-th power residue (u) by the n-th power residue (y) are congruent with N as modulus. The above-mentioned transmission and reception and confirmation of information with the n-th power residue (u) and (y) as media are plurally repeated so that the prover P proves that he knows n-th root of the n-th power surplus (u) to the verifier V.;COPYRIGHT: (C)1993,JPO&Japio