The present invention enables deniable zero-knowledge interactive proof to be performed with low amounts of communications and calculations by utilizing a method of a special honest verifier zero-knowledge interactive proof when such method is given. The verification apparatus generates a commitment of a challenge value with respect to a predetermined relationship and transmits the commitment of the challenge value to the proving apparatus, which determines whether or not a required relationship using the commitment of the challenge value holds, and stops its operation if such relationship does not hold. The proving apparatus causes the proof commitment generation apparatus to generate a proof commitment and transmits the proof commitment to the verification apparatus, which transmits a challenge value and a random number to the proving apparatus. The ladder transmits a response to the verification apparatus which determines acceptance or non-acceptance of the proof through communications with the interactive proof verification apparatus.