Paper 2008/136

Constant-Size Dynamic $k$-TAA

Man Ho Au, Willy Susilo, and Yi Mu


$k$-times anonymous authentication ($k$-TAA) schemes allow members of a group to be authenticated anonymously by application providers for a bounded number of times. Dynamic $k$-TAA allows application providers to independently grant or revoke users from their own access group so as to provide better control over their clients. In terms of time and space complexity, existing dynamic $k$-TAA schemes are of complexities O($k$), where $k$ is the allowed number of authentication. In this paper, we construct a dynamic $k$-TAA scheme with space and time complexities of $O(log(k))$. We also outline how to construct dynamic $k$-TAA scheme with a constant proving effort. Public key size of this variant, however, is $O(k)$. We then describe a trade-off between efficiency and setup freeness of AP, in which AP does not need to hold any secret while maintaining control over their clients. To build our system, we modify the short group signature scheme into a signature scheme and provide efficient protocols that allow one to prove in zero-knowledge the knowledge of a signature and to obtain a signature on a committed block of messages. We prove that the signature scheme is secure in the standard model under the $q$-SDH assumption. Finally, we show that our dynamic $k$-TAA scheme, constructed from bilinear pairing, is secure in the random oracle model.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. This paper is the extended version of the paper that appear in SCN '06 under the same title
Contact author(s)
mhaa456 @ uow edu au
2008-03-31: received
Short URL
Creative Commons Attribution


      author = {Man Ho Au and Willy Susilo and Yi Mu},
      title = {Constant-Size Dynamic $k$-TAA},
      howpublished = {Cryptology ePrint Archive, Paper 2008/136},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.