Constant-Size Dynamic k-TAA

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 construct an ordinary

k

-TAA scheme from the dynamic scheme. We also 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.