Identification Protocols based on Discrete Log Representation Problem

Identification protocols are powerful tools in many areas of cryptography. A prover's identity (ID) has n distinct secrets which in total construct her identity. When a prover, Peggy, wants to prove to a verifier, Victor, that she is the holder of a certain identity ID and at the same time, she is not willing to reveal these secrets due to privacy concerns, Peggy must prove to Victor that she indeed knows n witnesses that are related to the public instances that form her identity. The simplest way to prove this knowledge of n witnesses is to run an identification protocol for n times. This naive method results in protocols that have communication and computational complexities that are linear in the number of secrets. In this paper, we propose an identification protocol based on proof of knowledge of Discrete Logarithm (DL) representation. This protocol allows the prover to prove her knowledge of some personal information (encoded in a certain identity ID) without revealing any/some of this information to the verifier, at the same time, prevent the verifier from impersonating the prover in the future. Furthermore, we tackle the issue of reducing communication and computation costs.