Anonymous identification for ad hoc group

Xingye Lu, Man Ho Allen Au

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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.
Original languageEnglish
Title of host publicationASIA CCS 2016 - Proceedings of the 11th ACM Asia Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery, Inc
Number of pages9
ISBN (Electronic)9781450342339
Publication statusPublished - 30 May 2016
Event11th ACM Asia Conference on Computer and Communications Security, ASIA CCS 2016 - Xi'an, China
Duration: 30 May 20163 Jun 2016


Conference11th ACM Asia Conference on Computer and Communications Security, ASIA CCS 2016


  • Ad Hoc Group
  • Anonymous Identification
  • Cryptography
  • Obfuscations

ASJC Scopus subject areas

  • Computer Science Applications
  • Software
  • Computer Networks and Communications

Cite this