With the increasing concern on the erosion of privacy in the
society, privacy-preserving techniques have become a very essential
issue. This paper provides a formal treatment of deniability
in identification schemes. In particular, the contributions of this
paper are three folds. Firstly, for the first time in the
literature, we address the issue of deniability in identification
scheme. Deniability ensures the prover's privacy even after the
identification protocol completes. With the deniability property, it
is assured that the verifier will not be able to convince any
other third party that the prover has engaged in the identification
protocol with the verifier. We address the need of this property in
identification schemes. Secondly, we point out that although some
existing schemes in the literature have provided this property, this
property has never been formally defined.
We shall show an example that shows an identification scheme built
from HVZK protocol will not provide deniability.
Thirdly, we provide a generic construction of identification schemes
with deniability property and show how to instantiate it.
Our generic construction is very efficient, which requires only
three moves. We note that this can be optimized to two moves if the
first move is combined with the third move.