Provably Secure Anonymous Identification Protocols for Ad-hoc Access Structures

Abstract:
Anonymous routing protocols must be equipped with secure anonymous identification protocols for ad-hoc access, otherwise, successive nodes cannot be convinced that the request messages are from a specified set in which each node will provide service for path discovery requests. In this paper, we study anonymous identification schemes in the setting where each participant generates its public key and maintains the correspondent secret key independently. The presented scheme is efficient as we separate soundness and honest verifier zero-knowledge from the hardness of any problem. The security of our construction can be rigorously proved by simply assuming that each challenge string is chosen uniformly at random by the honest verifier. Finally, we provide alternative construction by reducing the 3-move protocol to 2-move protocol assuming that the RSA problem is hard.