How to Utilize the Randomness of Zero-Knowledge Proofs

In zero-knowledge interactive proofs, a lot of randomized information is exchanged between the prover and the verifier, and the randomness of the prover is used in satisfying the zero-knowledge condition. In this paper, we show a new methodology that utilizes the randomness of the prover in a zero-knowledge proof for some positive objectives as well as for zero-knowledge condition. Based on this idea, we propose two types of applications; key distribution, and digital signature. We propose identity-based key distribution schemes that are provably secure against strong active attacks (chosen-message-known-key active attacks) assuming the difficulty of factoring a composite number. In addition, we show that non-transitive digital signature schemes can be constructed if and only if a one-way function exists. We also show some practical non-transitive digital signature schemes. A new general method of constructing identity-based cryptographic schemes is presented as an application of the identity-based non-transitive digital signature schemes. We also propose a new digital signature scheme based on the (extended) Fiat-Shamir identification scheme.