The need for deniability in identification schemes
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.