Anonymous identification for ad hoc group

An anonymous identification scheme for ad hoc group allows a participant to identify himself as a member of a group of users in a way that his actual identity is not revealed. We propose a highly efficient construction of this cryptographic primitive in the symmetric key setting based on the idea of program obfuscation. The salient feature of our scheme is that only hash evaluations are needed. Consequently, our scheme outperforms all existing constructions for a reasonably large ad hoc group size (of around 50000 users) since no exponentiation nor pairing operation is involved. Technically, the participant only needs to evaluate one hash operation to identify himself. While the time complexity of the verifier is linearly in the size of the ad hoc group, the actual running time is rather insignificant since the constant factor of this linear dependence is the time of a single hash evaluation. To analyse the security of our proposal, we develop a security model to capture the security requirements of this primitive and prove that our construction satisfies these requirements in the random oracle model against unbounded attackers. Similar to other identification schemes secure in the random oracle model, our proposed protocol requires only two message flow.