WO2007095691A1

WO2007095691A1 - Anonymous authentication

Info

Publication number: WO2007095691A1
Application number: PCT/AU2007/000212
Authority: WO
Inventors: Lan Duy Nguyen
Original assignee: Commonwealth Scientific and Industrial Research Organization CSIRO
Current assignee: Commonwealth Scientific and Industrial Research Organization CSIRO
Priority date: 2006-02-24
Filing date: 2007-02-26
Publication date: 2007-08-30
Anticipated expiration: 2008-08-24

Abstract

An authentication process, including: a) generating, and providing communications access for a user device to, k tag bases, k representing the number of times a user device is able use a credential, each tag base including random data and a signature on the random data, and said credential being associated with said user device, b) providing communications access to a tag database and public data for verifying the credential and tag bases. c) receiving from said user device a service request and credential-show data including a tag and a proof, said tag being generated from the credential and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of said tag bases, and being based on the signature of the tag base, and; d) processing the service request in response to verifying the proof is valid and the tag is not stored in the tag database, and adding the credential-show data to the tag database.

Description

ANONYMOUS AUTHENTICATION

FIELD

The present invention relates to an authentication system and process. In particular, the present invention relates to an authentication process that allows parties to be anonymously authenticated a limited number of times as determined by an application provider.

BACKGROUND

Services are delivered on public communications networks, such as the Internet, by application providers (APs). The services may include the delivery of digital content, such as music and videos. The APs use authentication systems, which may form part of digital rights management (DRM) systems to regulate access to their services. Anonymous authentication systems, such as those described in US Patent Publications 2002/0103999 and 2003/0177352, have the advantage that an anonymous credential, such as a digital certificate or public/private key pair, can be provided to a user that allows them to be verified without having to disclose any private information, such as identity. Difficulties, however, are encountered in limiting the number of times an anonymous authentication process can be used, without increasing the computational and communication costs associated with the system by a factor that is proportional to the limit.

For example, in a A:-times anonymous authentication (Ar-TAA) system, as discussed in I. Teranisi, J. Furukawa, and K. Sako, λ:-Times Anonymous Authentication, ASIACRYPT 2004, Springer- Verlag, LNCS 3329, pp 308-322, 2004 ("Teranisi"), participants include the computer systems or devices of a group manager (GM), some application providers (AP) and many users. The GM registers users into the group and each AP independently announces the number of times a group member can access the AP's application. A group member can be anonymously authenticated by APs within their allowed numbers of times and without contacting the GM. No one, even the GM or APs, is able to identify honest users or link two authentication executions of the same user, while anyone can trace dishonest users. No party, even the GM, can successfully impersonate an honest user in an authentication execution.

However, &-TAA systems are inflexible in the sense that the GM decides on the group membership and APs do not have any control over giving users access permission to their services. APs are passive and their role is limited to announcing the number of times a user can access their applications. In practice, APs want to select their user groups and grant or revoke access to users independently. For example, the AP may prefer to give access to users with a good profile, or the AP may need to put an expiry date on users' access. Dynamic £-times anonymous authentication, as discussed in L. Nguyen and R. Safavi-Naini, Dynamic A:-Times Anonymous Authentication Applied Cryptography and Network Security (ACNS) 2005, Springer-Verlag, LNCS 3531, 2005, ("Nguyen"), was introduced to provide these properties. In dynamic &-TAA, APs have more control over granting and revoking access to their services, and less trust and computation from the GM is required. Dynamic Ar-TAA allows APs to restrict access to their services based on not only the number of times but also other factors such as expiry date and so can be used in much wider range of realistic scenarios.

An anonymous authentication or credential system, as discussed in D. Chaum, "Security without identification: Transaction systems to make Big Brother Obsolete",

Communications of the ACM 28(10), pp 1030-1044, 1985, ("Chaum"), consists of the machines of users and organisations. Organisations know users only by their pseudonyms.

A user can obtain credentials from organisations and prove possession of these credentials without revealing their private information such as identity and without allowing their transactions to be linkable to one another. The sets of users and organisations may change over time. Optionally, in case of dispute, a Central Authority (CA) can open a credential to find the user. An example of using anonymous credentials is as follows. The organisations are a traffic authority, an insurance company, and a car rental service. A user, who wants to hire a car, needs to show the car rental service a driver license and an insurance policy. If the user just sends these documents to the rental service, a lot of the user's private information, such as name, address, license number or insurance number, is unnecessarily revealed to the rental service. Anonymous credential systems allow the user to prove his possession of a driver's license and an insurance policy without revealing any other information. In case the user violates the hiring conditions, the car rental service can request a Central Authority (CA) to open credentials to find the user's identity.

The non-interactive counterpart of k-TAA is &-times anonymous signatures (ie tracing-by- linking signatures, as discussed in V. Wei, "Tracing-by-Linking Group Signatures", Information Security Conference (ISC) 2005, Springer-Verlag, LNCS 3650, pp 149-163, 2005, ("Wei"), where a group member can anonymously sign messages on behalf of the group for k times. Tracing-by-linking signatures can be used to construct /t-show anonymous credential systems, as discussed in Wei, where credential issuing organisations can limit the number of times a user can show her credentials. For example, in the car rental scenario above, the traffic authority can issue driver licenses with demerit points and an insurance policy may restrict the number of claimable hired cars associated with the . policy.

Applications of k-TAA can be found in digital rights management (DRM) systems, which use a variety of technologies for securely handling the rights held over digital content. A k-TAA system can be used to provide pay-per-use anonymous access to online digital content, such as music, movies, interactive games, betting and gambling, that are supplied by different application providers. A user can buy credits to download hundreds of songs or movies over a year at a discount price. Another example is trial browsing, as discussed in Teranisi, where each provider allows members of a group, such as an Adult content community, to anonymously and freely browse content such as movies or music on trial. The provider also wants to limit the number of times that a user can access the service on trial and users, who try to go over the prescribed quota, identified.

A Ar-times anonymous signature system can be applied to e-voting with limitation on the number of votes per user. It can be used to transfer e-cash: the cash owner sends an one- time anonymous signature on the electronic cash to the receiver. It can be directly used to construct an e-coupon system, as discussed in Teranisi. In the existing ordinary and dynamic Ar-TAA systems, the authentication procedure has computation and communication costs linearly depending on the bound k. If an application provider sets A; to be a large number, the authentication procedure becomes expensive. For example, a music web site may sell multi-coupons each of which can be used to anonymously download 10000 songs within a year. Then each user device has to run the same expensive authentication protocol for each downloaded song. If there are many users in the group, the authentication cost multiplies by the number of users. So, it is desired to provide a useful alternative, and preferably an anonymous authentication system, such as a Ar-TAA system, where the computation and communication costs in the authentication procedure do not depend on k.

SUMMARY

In accordance with the present invention there is provided an authentication process, including: a) generating, and providing communications access for a user device to, k tag bases, k representing the number of times a user device is able use a credential, each tag base including random data and a signature on the random data, and said credential being associated with said user device, b) providing communications access to a tag database and public data for verifying the credential and tag bases, c) receiving from said user device a service request and credential-show data including a tag and a proof, said tag being generated from the credential and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of said tag bases, and being based on the signature of the tag base, and; d) processing the service request in response to verifying the proof is valid and the tag is not stored in the tag database, and adding the credential-show data to the tag database. The present invention also provides an authentication process performed by a user device, including sending a request for a service and credential-show data including a tag and a proof, said tag being generated from a credential for the device and a tag base, said proof being for indicating the tag is correctly generated from the credential and one of k tag bases, and being based on a signature of the tag base.

The present invention also provides an authentication process performed by a verifying system, including: receiving from a user device a service request and credential-show data including a tag and a proof, said tag being generated from a credential of the user device and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of A: tag bases, and being based on a signature of the tag base, and; processing the service request in response to verifying the proof is valid and the tag is not stored in a tag database, and adding the credential-show data to the tag database.

The present invention also provides an authentication system for performing one of the above processes.

The present invention also provides computer readable storage media including computer program code for performing one of the above processes.

The present invention also provides an authentication system including: a bounding system including a tag database and for generating, and providing communications access for a user device to, k tag bases, k representing the number of times a user device is able use a credential associated with the user device, each tag base including random data and a signature on the random data; and a verifying system for receiving from the user device a service request and credential-show data including a tag and a proof, said tag being generated from the credential and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of said tag bases, and is based on the signature of the tag base, and for processing the service request in response to verifying the proof is valid and the tag is not stored in the tag database, and adding the credential-show data to the tag database.

BRIEF DESCRIPTION OF THE DRAWINGS

Preferred embodiments of the present invention are hereinafter described, by way of example only, wherein:

FIGURE 1 is a block diagram of a preferred embodiment of an authentication system;

FIGURE 2 is a message flow diagram of processes performed by the system; FIGURE 3 is a flow diagram of processes performed by a general manager system of the authentication system;

FIGURE 4 is a flow diagram of a process performed by an application provider system of the authentication system; and

FIGURE 5 is a flow diagram of processes performed by a user device of the authentication system.

DETAILED DESCRIPTION

An anonymous authentication system 10, as shown in Figure 1, includes a number of application provider (AP) systems 14, and at least one general manager (GM) system 16 that are able to communicate with one another, and client devices 12 of users, using a communications network 18. For the purposes of this description, the communications network 18 is described as one that supports TCP/IP protocols, such as the Internet, and the

AP and GM systems 14 and 16 are described as servers that support the protocols. The servers 14 and 16 could be adapted for different communications networks to communicate with the user devices 12. The client devices 12 are computer systems able to communicate with the communications network 18.

The devices 12 may include mobile telephones or personal digital assistants (PDAs). The devices 12 are hereinafter described as being a standard personal computer 20, such as that provided by IBM Corporation, running an operating system 22, such as Microsoft Windows or Linux. The devices 12 also include application layer computer programs, such as a web browser 30 and a cryptography module 32, which may only be installed temporarily for a session.

The AP systems 14 and GM system 16 are described as being server computer systems 40, such as that provided by IBM Corporation, running an operating system 42, such as Windows Server 2003, Linux, Unix or Solaris. The AP systems 14 include service application modules, such as a web server 44 and web server application modules 46 to deliver a web based service or application to users of the client devices 12, The AP systems 14 also include DRM modules 48 to support the anonymous authentication system and to control delivery of the application service. The GM system 16 includes GM DRM component modules 50 and other application layer software so that the GM server 16 is able to operate as a Central Authority (CA). The application layer components 46, 48 and 50 comprise computer program instruction code in languages such as Java, Perl, HTML and XML. The DRM components 48 and 50 include cryptographic libraries, such as those available at Victor Shoup's NTL (http://shoup.net/ntl) or GNU's GMP (http://swox.com/gmp). Database servers 52 and 54, such as MySQL (http://www.msql.com), also run on the systems 14 and 16 to maintain databases on the systems 14 and 16 for storing application data and authentication data associated with users of the devices 12.

The components 42 to 54 of the servers 14 and 16 could also be placed and distributed on a number of computers connected by the communications network 18, or combined on the one server. Also the processes executed by the components could also be executed at least in part by dedicated hardware circuits, e.g. ASICs and FPGAs. In particular, the DRM components 48 and 50 could have at least part of their process performed by a dedicated hardware circuits to improve the speed of performance of the authentication system. The cryptography application 32 is normally installed for use with the served application, but could also have part of its processes performed by dedicated hardware circuits in a user device 12. The authentication system 10 performs an anonymous authentication process that is controlled by the DRM components 48 and 50 and the cryptography component 32. An overview of the process performed by the GM DRM component 50, the AP DRJVl component 48, and the user device component 32 is illustrated in Figure 2. The GM, AP and user components 48, 50 and 32 provide a dynamic Ar-TAA system, in which the computation and communication costs of at least one of the authentication processes performed do not depend on k.

With reference to Figure 2, the authentication process commences with the GM 16 running a setup process 201 in which data strings representing cryptographic keys are generated for a group of user devices 12. Once the group is established, at least one user device 12 joins the group through an accreditation process 202. The accreditation process involves two processes 203 and 204, one run by the client components 30, 32 and the other run by the

GM 16, which exchange data. In the accreditation process 202, the GM securely provides the user device 12 generates unique data, known as a credential, which represents that the user 12 has been accredited to join the group. To achieve accreditation, the client communicates information to the GM, including for example personal details of the user or a payment commitment. The accreditation process 202 might, for example, be used by a user to purchase a voucher (credential) online, where the voucher is to be used to download a set number of music files from a music AP 14 for no further cost. Also in step

202, the client 30, 32 generates unique cryptographic keys and makes the public key accessible over the communications network 18 for other parties.

After the GM 16 runs setup process 201, at least one AP 14 performs a setup process 205, in which unique cryptographic keys, based on the GM's public cryptographic key generated for the group, are generated for the AP. In step 206, the AP generates k digitally-signed data blocks, known as tag bases, where k is the number selected for the maximum number of allowable access requests from a client for that AP. For example, a music AP may have a set number of downloadable music files where k = 100 files. The tag bases are provided by the AP to be accessible over the communications network 18 for other parties, including the GM 16 and the user devices 12. In step 207, the AP 14 accesses the public encryption keys of the user devices 12 which are accessible over the communications network 18, and processes the publicly available information on these public user keys to generate a list of user keys that will be granted access to the AP; the list of granted user keys is then published (i.e. made accessible over the communications network 18 for other parties). If a user device 12 has been granted access to an AP in step 207, the device 12 initiates an AP access request in step 209, for example the device 12 sends a request for a selected music data file to the AP. In the authorisation process 209, the client 30, 32 generates a deterministic data code that depends on the user's credential and one of the tag bases, and transmits this code to the AP. The AP processes this code in step 210 to determine whether access should be authorised. If the user was not granted access in step 207, or if the credential is not proven, or if the client 30, 32 has already transmitted the maximum allowable number (k) of tags, then the client request is rejected 21 1 , If the authorisation process is passed, however, the request is approved 212.

The AP is able to revoke access that has been granted to users in step 207, and a tracing process can be used to enable any party on the network to access the hidden details of a user that attempts to accesses an AP more than k times, as described below.

The following paragraphs introduce notation that is used to represent data fields, values, elements and procedures of the authentication system described herein.

For a function/; N -^ R⁺, if for every positive number a, there exists a positive integer KQ such that for every integer κ > KQ, it holds that f(κ) < κ ^'a-, then/is said to be negligible. PT denotes polynomial-time, PPT denote probabilistic PT, and DPT denote deterministic PT. For a PT process A(»), "x 4- A(»)" denotes an output from the process. For a set X, "x 4- X" denotes an element uniformly chosen from X, and #X denotes the number of elements in X. Let "¥x[Procedures\Predicate]" denote the probability that Predicate is true after executing the Procedures, Hy denote a hash function from the set of all finite binary strings {0, 1 }* onto the set X, and PK{x : R(x)} denote a proof of knowledge of x that satisfies the relation R(x). An adversary is modelled by an interactive Turing machine, which interacts with some oracles. Each oracle performs operations and produces outputs required by queries from the adversary. An entity is corrupted if the adversary has the entity's secret keys and completely controls the entity's actions. Finally, 1=0 is defined to be 0. Adversaries and oracles are further described in Appendix 1.

Gi, G2 and Gj are multiplicative cyclic groups of prime order p. Suppose Pi and P₂ are generators of Gj and G₂ respectively, and there is an isomorphism ψ : Gi -^ Gj such that ψ (P 2) - Pi- A function e : G; x G₂ -^ C7χ is said to be a bilinear pairing if it satisfies the following properties:

(i) Bilinearity: e(P^a, Q^b) = e(P, Q)^ab for all P e Gu Q e G₂ and a, b e Z_p. (ii) Non-degeneracy: e(P], P 2) ≠ 1.

(iii) Computability: There is an efficient process to compute e(P, Q) for all P e Gi and Q e G₂.

For simplicity, hereafter, Gi = G₂ and P; = P₂ but the processes can be modified for the general case when Gi ≠ G₂. A Bilinear Pairing Instance Generator is defined as a PPT process G that takes as input a security parameter 1 ^κ and returns a uniformly random tuple t = (p, G, G_T1 e, P) of bilinear pairing parameters, including a prime number p of size K, two cyclic groups G and GT of the same order p, a bilinear map e : G x G -$ Gy and a generator P of G.

The q-Strong Diffie-Hellman (q-SDH) Assumption states that for every PPT process A., the following is negligible:

Adυ^^SDH(_K) = Pr[(A(t, P_: P^s, . . . , P^) = {c, P^l^^s+^)) Λ (c € Z₃₃)] where t = (p, G, G_τ, e, P) <- G(7*) and j <r Z^* _p. The assumption informally means that there is no PPT process that can compute a pair (c, p^1/(s*^c))_^ where c e Z^, from a tuple (T⁵, r, ..., P^j, where s <e zV

The Decisional Bilinear Diffie-Hellman Inversion (DBDHI) Assumption states that for every PPT process Λ., the following is negligible: Adυζ^BDHI(κ,)

= 1]| where t = (p, G, GT, e, P) <- G(I ^κ) and s <- Z%. Intuitively the DBDHI assumption states that there is no PPT process that can distinguish between a (P, P^s, ..., P^(s*q), e(P, P)^l/s), and a tuple (P, P^s, .... P^(s™, r), where r <r G^* _p and s <r

The Computational Bilinear Diffie-Hellman Inversion (CBDHI) Assumption states that for every PPT process A, the following is negligible:

Adυ$^BDHI(κ) = Prμ(t, P, P'⁹, . . . , P^(s"⁾, e(P, P)¹/^s) = s] where t - (p, G, G₇, e, P) <r G(l^κ) and s <r Z%.

Figure 3 shows the processes that are run on the GM 16 and the data pathways used during these processes. In Figure 3, the DRM component 50 of the GM 16 runs the following processes: a setup process 201 (¹GKg') in which data is made available to the communications network 18, a join process 202 ('Join^M') in which the GM 301 exchanges data with a user device 12 during accreditation; and a trace process 306 ('Trace') in which the GM access data from the network 18. This trace process 306 can be carried out by any system or entity, including the GM 16, AP 14 or user device 12, on the network 18. The trace process 306 generates data about malicious parties on the network.

The setup process 201, based on a PPT process, takes data representing a security parameter l^κ and performs a Bilinear Pairing Instance Generator process, described in the section on Notation and Definitions, which generates a tuple (p,G,Gτ,e,P). The GM sets P _pub = P⁷ and selects the following: P₀, H, H', G₁, G₂ <r G, y <r Z^* _p and Δ <rG. The GM then generates a secret cryptographic key for the group, gsk, and a public key for the group, gpk. The secret key gsk is generated from these data: γ. The public key gpk is generated from this data: (P, P_pub, Po, H, H', Gi, Gj, Δ) and is transmittable to the network 18 for access by other parties (published). Finally, the GM generates a data list representing accredited users 12 who are members in the group, LIST, which initially has no members; the data list LIST is also published to the network 18. In the join process 202, the GM 16 exchanges data with the client cryptography module 32 of a user device 12 which enables the user to achieve accreditation, i.e. enables a user to join the group. The join process 202 includes a GM join process 204 performed by the GM 16 and a user join process 203 performed by the user device 12. The process 202 is initiated by a data request to join, coming from a user device 12. The device 12 selects, possibly randomly, the data values x and v' <- Z^* _p, then generates a value β = Δ^1/x and a commitment C = P*H'^V of x and adds (U β) to the identification list LIST. The device 12 then transmits β and C to the GM with a standard non-interactive zero-knowledge proof, Proof i = PK{(x,v'): C = P^xH^lV< Λ A = β^x}, i.e. using data from the group public key, gpk, which is available on the network. The GM performs a verification process that verifies whether (i;β) is an element of list ZJST and whether the proof is valid. If the device 12 is in the list and a valid proof has been transmitted, the GM then generates a unique a ^r Z_p, u <r Z^* p and S = (CH ⁿP₀)^1/(γ+a), and transmits the data set (S, a, ύ) to the device 12. Finally, the client 32 generates a data value v = v' + u and processes the received data set (S, a, u) to data to determine whether the relationship e(S, P^aP_pub) ⁼ e(P^xH'^vPo, P) is satisfied, in which case the user's new secret key, as a group member, is generated according to the relation msk = (x; v), and the new public key is generated according to the relation mpk = (a; S; β). The SDH assumption assures that it is computationally hard to forge such a key pair without collusion from the GM. The data acquired by the user's client machine at the end of process 204 includes data providing a credential; the user can be anonymously authenticated as a group member by proving the knowledge of the stored data values (a, S, x, v) on the user device 12, such that e(S, P^aP_pub) = e(F^xH'^vP₀, P).

In the trace process 306, the GM 16 accesses data publically available on the network, which may include data published by the GM, to trace a malicious user. If the member uses the same tag base to compute another tag (F ', f ) ' , the member can be identified from the AP's authentication log LOG (since F= F *) and use it to determine β, which is part of the user's public key. However, according to the the DBDHI assumption, a member's anonymity is protected if any tag base is only used once. The inputs to process 306 include all public information and an authentication log which has been generated by an

AP and made publically available over the network. The output of the process either indicates the indentity of a malicious user, or that the GM has been malicious, or that there is no malicious user in the authentication log. The authentication log LOG contains data in the form of entries, including the values of F, F, /, and Proof. The first step in the process is to numerically compare pairs of entries in the log and generate a null output NONE if there are no entries where the same tag base has been used by the same client, i.e. F- F ' and / ≠ /'. If there is such an entry, the process generates and publishes the identification details of a user device 12 using inputs of the two matching entries; the value for β is generated from (Fl F')^1/(l'l) and the user details found by searching for the pair (i, β) in the list LIST. If a matching pair is found but no user is found in the LIST, then the process generates and publishes the output 'GM' because this can only arise when the GM has deleted data from the LIST.

Figure 4 shows the processes that are run on the AP 14 and the data pathways used during these processes. The AP runs an initialisation process 205 (¹AKg') to generate cryptographic keys, a tag base publishing process 206 ('Bound') to share the AP identity details and indicate how many times k access will be authorised, an access granting process 207 ('Grant') and an access revoking process 407 ('Revoke') to control which client machines 403 may be authorised, an authorising process 210 (Αuth^Pτ) to verify credentials of a client 201 requesting access, and a trace process 306 ('Trace') which corresponds to the Trace process 306 of the GM 16 in Figure 3.

In the initialisation process 205, the AP receives the group public key gpk over a transmission link and selects data values Q <r G, s, s' 4- Z^* _p, Q_put = Qf, and Q'_pι,_b ^~ Of . The AP then generates a pair of AP-specfic public and secret keys, apk = (Q, Q_pub, Qf) and ask - (s, s)' . The AP initialises an authentication log LOG, an accumulated value which is published and updated after granting or revoking a member, and a public archive ARC. The ARC is a list of 3-tuples. Each 3-tuple contains three data components: the first component is an element in the public key of a member who has been granted accessing to the AP or had that access revoked; the second component is a single data bit indicating whether the member was granted (1) or revoked (0); and the third component is the published copy of the accumulated value data. Initially, in process 205, the accumulated value is set to VQ <- G and log LOG and archive ARC are empty.

In the tag base publishing process 206 the AP publishes its identity details ID and indicates (i.e. 'announces') how many times, k, access will be authorised. The number k is selectable for each AP and each implementation of the process 206. The AP publishes k tag bases, where each one is intended to be used by a user device process to affect a single authentication with the AP, as described below. Each tag base is signed by the AP digitally. If (t_j, j t = Hz_*px_z*p(ID, k, j) for; = 1, ..., k, then the AP generates R_j = (Q⁰ H')^{!/(s'A'M )} for; = 1, .... fc and publishes (t_h j t , R₁), ..., (t_k, j t , RiJ. Υhejth tag base of the AP is thus (t_j, _j t, R_j). Each tag base satisfies the condition e(R\ Q}'Q'_pub) = 6(Qj-¹H', Q). As proven later, if the SDH assumption holds, it is intractable to forge a tag base without colluding with the AP.

In the access granting process 207, the AP adds a group member to its access group AG and publishes the AP's public information PI, which a user's client can access and receive a member access key mak. This is referred to as a dynamic process because the AP has dynamic control over which users are granted access, or have their access revoked. In this access granting process 207, the value a of a user's public key is added to an accumulated value V <r V^+a by the AP; the AP then adds (a, 1, V_J+I) to the AP's archive ARC: the data value a indicates which user device 12 is referred to (by using part of the client's public key) and the value '1' indicates that access is granted. From the AP's ARC, the user's client 32 is able to receive the issued data value a through use of the user's access key mak = (J + I; W), where W = Vj ; the old accumulated value is known as the witness, W. In later transactions, the device 12 that is now granted membership is able to show that the AP has granted access by proving knowledge of (a, W) such that e(W, Q^aQ_Pub) ⁼ e(V, Q). At the end of process 207, the device 12 initiates a counter d with an initial value of zero; this counter is used by the device 12 to record the number of times an AP's service has been accessed, and thus record whether the limit of A; has been reached. In the access revoking process 407, the AP removes data representing a member from the AP' s access group — by generating a new accumulated value V 4- V^1/(s+a) — and updates its public information archive ARC to include the tuple of values (a, 0, V_j+i) : the data value a indicates which client 32 is referred to (by using part of the client's public key) and the value '0' indicates that access is no longer granted.

In the authorisation process 210, the AP verifies the credentials of a user device 12 that is requesting access to data representing a service provided by the AP. The client 32 first increments the counter d; if d > k the client 32 transmits a data flag to the AP and the process ceases. If d < k, the client 32 generates a new access key mak using the UPDATE process described in Appendix 2 and sends a data request to the AP 401. The AP then transmits a random integer / 4- Z^" _p to the client. The client 32 then generates a new tag from an unused tag base and the random integer where the tag (F₁ F) is generated from (Δ^I/(x+ι°, A ^^+/-«⁺*J^/f**⁺^_ _{τhe client} 32 transmits the new tag to the AP with a PROOF2, described in Appendix 2. The AP processes the PROOF2 data; this is a zero-knowledge proof, which enables the user device 12 to prove that it possesses certain data (in this case a credential) and the tag is correctly generated from the tag base and the credential whilst revealing zero information about that data. If the proof generates a valid result and if the tag being transmitted is different to all corresponding tags in the AP 's log LOG, the AP adds tuple (F, F, I) and the Proof ^'to LOG, and outputs a data flag ACCEPT representing acceptance of the authentication. If the proof is valid and the tag is already written in LOG, the AP adds tuple (F, F, I) and the Proof to the LOG, outputs (DETECT, LOG) and stops. If the proof is invalid, the AP outputs REJECT and stops.

The trace process 306 is performed by the AP 14 in the same manner as the trace process 306 in Figure 3 is performed by the GM 16; all the data required for this process is available on the network 18.

Figure 5 shows the processes that are run on the user device 12 under the control of the client cryptography and the data pathways used during these processes. The join process

203 on the user device 12 is described above with reference to the join process 201 on the GM 16, with which it coordinates and communicates. Similarly, the authentication process

209 on the client machine is described above with reference to the authentication process

210 on the AP 14, with which it coordinates and communicates.

The trace process 306 is performed by the client 32 in the same manner as the trace process 306 in Figure 3 is performed by the GM; all the data required for this process is available on the network 18.

The dynamic k-ΥAA process described above can be converted, if desired, into a Ar-TAA process. The setup 201, joining 202, bound announcement 206 and public tracing procedures 306 remain the same. The AP setup 205, granting access 207 and revoking access 407 procedures are removed. In the authentication procedure 210, 209 for dynamic

Ar-TAA, a user needs to prove to an AP three conditions: (i) he has been registered as a group member; (ii) he is in the access group of the AP; and (iii) he has not accessed the AP more than the allowable number of times. For Ar-TAA, the user do not have to prove condition (ii) and just needs to prove two conditions (i) and (iii).

Using the above approach a Ar-TAA process can be derived from the dynamic process. In the authentication procedure 206, 209, a different Prooflb is used and there is no UPDATE or PUBLIC INSPECTION process, as described in Appendix 2. It is also possible to construct a combined Ar-TAA process, where some of the APs have the dynamic property and other APs do not. This means some APs can determine users who are allowed to access their services, whereas other AP completely depend on the GM to decide who can access their services.

Many modifications will be apparent to those skilled in the art without departing from the scope of the present invention as herein described with reference to the accompanying drawings. APPENDIX 1

Adversaries (oracles), correctness and security requirements

An adversary has access to a number of oracles and can query them according to the brief description below, to learn about the system and increase his success chance in the attacks.

Their formal definitions can be found in Nguyen and Teranisi.

OLIST : Suppose there is an identification list LIST of user identity/public-key pairs, this oracle maintains correct correspondence between user identities and user public keys. Any party can query the oracle to view a user's public key. A user or his colluder can request the oracle to record the user's identity and public key to LIST. The GM or his colluder can request the oracle to delete data from LIST.

OJOIN-GM: Given a user identity, it performs the (JoinU, JoinM) protocol as executed by the honest GM and the user.

OJOIN-U: Given an honest user's identity, it performs the (JoinU, JoinM) protocol between the GM and the user.

OAUTH-AP : Given an honest AP 's identity and a user identity, it makes the AP to execute the authentication protocol with the user. OAUTH-U: Given an honest user's identity and an AP identity, it makes the user to perform the authentication protocol with the AP.

OGRAN-AP : It takes as input an honest AP 's identity and a group member's identity and the AP executes the Grant process to grant access to the user.

OREV O-AP : It takes as input an honest AP 's identity and a member of the AP 's access group and the AP executes the Revoke process to revoke the user from accessing its application.

OCORR-AP : It corrupts an AP specified in its input.

OQUERY : It is only used once in the definition for anonymity requirement to give the adversary a challenged authentication transcript. Identities of two honest users, who are in an AP' s access group and have not been authenticated by the AP more than the limit, are given to the oracle. It then randomly chooses one of the two identities, executes the authentication protocol between the chosen identity and the AP, and outputs the transcript of the protocol.

The correctness condition and security requirements for dynamic k-TAA are summarized as follows and full description can be found in Nguyen and Teranisi.

Correctness: It requires that an honest member who is in the access group of an honest AP and has performed the authentication protocol with the AP for less than the allowed number of times, is successfully authenticated by the AP. Anonymity: Intuitively, it means that given two honest group members iO and il, who are in the access group of an AP, it is computationally hard to distinguish between authentication executions, which are performed by the AP and one of the two members. In the experiment, the adversary is allowed to collude with the GM, all APs, and all users except target users iO and il, and to query oracles OLIST , OJOIN-U, OAUTH-U and OQUERY . The adversary is allowed to make only one query to OQUERY on input iO, il and an AP whose access group contains iO and il. On receiving such a query, OQUERY makes either iO or il to execute the authentication protocol with the AP and outputs the transcript. Each of the users iO and il must be authenticated by the AP within k times. The anonymity condition holds if the probability that the adversary can correctly guess the user identity used in OQUERY 's authentication execution is negligibly better than a random guess.

Detectability: It loosely means that if a subgroup of corrupted members have performed the authentication procedure with the same honest AP for more than the total allowed number of times, then the public tracing process using the AP's authentication log outputs NONE with negligible probability. The experiment has two stages and the adversary is allowed to corrupt all users. In the first stage, the adversary can query OLIST , OJOIN- GM, OAUTH-AP, OGRAN-AP, OREV O-AP and OCORR-AP . Then all authentication logs of all APs are emptied. In the second stage, the adversary continues the experiment, but without access to the revoking oracle OREV O-AP . The adversary wins if he can be successfully authenticated by an honest AP V with access bound k for more than k x #AGV times, where #AGV is the number of members in the AP's access group. The detectability condition requires that the probability that the adversary wins is negligible. Exculpability for users: It intuitively means that the tracing process does not output the identity of an honest user even if other users, the GM and all Aps are corrupted. In the experiment, the adversary, who wants to frame an honest user i, is allowed to corrupt all entities except the user i and can access OLIST , OJOIN-U, and OAUTH-U. The adversary must authenticate user i using OAUTH-U within the allowable numbers of times set by the APs. If the adversary succeeds in computing an authentication log, with which the public tracing process outputs i, the adversary wins. The exculpability condition for users requires that the probability that the adversary wins is negligible. Exculpability for the GM: Loosely speaking, it means that the tracing process does not output the honest GM even if all users and all APs are corrupted. In the experiment, the adversary wants to frame the honest GM and he is allowed to corrupt all users and all APs and access OLIST and OJOIN-GM. If the adversary succeeds in computing an authentication log, with which the public tracing process outputs GM, the adversary wins. The exculpability condition for the GM requires that the probability that the adversary wins is negligible.

APPENDIX 2

PROOF2, UPDATE and PUBLIC INSPECTION processes

PROOF2

Most of the pairing operations in this proof can be pre-computed. The member M computes the proof as follows.

UPDATE

Suppose the AP's ARC currently has n tuples, the member M with the public key (a, ., .) and the access key (j, W_j) computes a new access key as follows. for (k = j + 1; k + +; k < n) do retrieve from ARC the k^th tuple (u, δ, 14);

end for; return (n, W_n);

PUBLIC INSPECTION Any party can run this process to assure the correctness of an AP's tag bases and public archive ARC. With such a process, it can be assumed that tag bases are always correctly issued and ARC is always correctly updated. For each tag base , any party can

verify if

■ After a change on ARC, any party can retrieve

the new tuple (u,b,Vk) . If (b = 1) then he checks if

otherwise, he checks if

Claims

CLAIMS:

1. An authentication process, including: a) generating, and providing communications access for a user device to, k tag bases, k representing the number of times a user device is able use a credential, each tag base including random data and a signature on the random data, and said credential being associated with said user device, b) providing communications access to a tag database and public data for verifying the credential and tag bases, c) receiving from said user device a service request and credential-show data including a tag and a proof, said tag being generated from the credential and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of said tag bases, and being based on the signature of the tag base, and; d) processing the service request in response to verifying the proof is valid and the tag is not stored in the tag database, and adding the credential-show data to the tag database.

2. A process as claimed in claim 1, wherein said user device is granted said credential by a credential granting system.

3. A process as claimed in claim 2, wherein the credential includes public and secret cryptographic keys generated by a join process performed by the user device and the credential granting system.

4. A process as claimed in claim 1 or 3, wherein said tag database is maintained by a bounding system, and said bounding system monitors the number of times said credential and said tag bases are used.

5. A process as claimed in claim 4, wherein said bounding system sets k.

6. A process as claimed in claim 5, wherein said bounding system includes an application provider system providing the service on processing said service request.

7. A process as claimed in claim 6, wherein said signature is a digital signature of said application provider system.

8. A process as claimed in claim 2, wherein said credential is revocable by said credential-granting system.

9. A process as claimed in claim 4, wherein said user device is granted said credential by at least one of a credential-granting system and said bounding system

10. A process as claimed in claim 9, wherein said credential is revocable by at least one of said credential-granting system and said bounding system.

11. A process as claimed in anyone of the preceding claims, including a tracing process for accessing said tag database to determine use of said credential more than & times.

12. An authentication process performed by a user device, including sending a request for a service and credential-show data including a tag and a proof, said tag being generated from a credential for the device and a tag base, said proof being for indicating the tag is correctly generated from the credential and one of k tag bases, and being based on a signature of the tag base.

13. An authentication process as claimed in claim 12, wherein k represents the number of times the user device is able use the credential, and each tag base includes random data and said signature on the random data, said signature being a digital signature of an application system providing the service.

14. An authentication process as claimed in claim 13, including receiving said service after verifying the proof is valid and the tag is not stored in a tag database, and adding the credential-show data to the tag database.

15. A process as claimed in claim 14, wherein said user device is granted said credential by a credential granting system.

16. A process as claimed in claim 15, wherein the credential includes public and secret cryptographic keys generated by a join process performed by the user device and the credential granting system.

17. A process as claimed in claim 15 or 16, wherein said tag database is maintained by a bounding system, and said bounding system monitors the number of times said credential and said tag bases are used.

18. A process as claimed in claim 17, wherein said bounding system sets k,

19. An authentication process performed by a verifying system, including: receiving from a user device a service request and credential-show data including a tag and a proof, said tag being generated from a credential of the user device and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of k tag bases, and being based on a signature of the tag base, and; processing the service request in response to verifying the proof is valid and the tag is not stored in a tag database, and adding the credential-show data to the tag database. •

20. An authentication process as claimed in claim 19, wherein k represents the number of times the user device is able use the credential, and each tag base includes random data and said signature on the random data, said signature being a digital signature of an application system providing the service.

21. A process as claimed in claim 20, wherein said user device is granted said credential by a credential granting system.

22. A process as claimed in claim 21, wherein the credential includes public and secret cryptographic keys generated by a join process performed by the user device and the credential granting system.

23. A process as claimed in claim 20 or 22, wherein said tag database is maintained by a bounding system, and said bounding system monitors the number of times said credential and said tag bases are used.

24. A process as claimed in claim 23, wherein said bounding system sets k.

25. A process as claimed in claim 24, wherein said bounding system includes said application system providing the service on processing said service request.

26. A process as claimed in claim 21, wherein said credential is revocable by said credential-granting system.

27. A process as claimed in claim 23, wherein said user device is granted said credential by at least one of a credential-granting system and said bounding system

28. A process as claimed in claim 27, wherein said credential is revocable by at least one of said credential- granting system and said bounding system.

29. A process as claimed in anyone of claims 19 to 28, including a tracing process for accessing said tag database to determine use of said credential more than k times.

30. An authentication system for performing a process as claimed in any one of the preceding claims.

31. Computer readable storage media including computer program code for performing a process as claimed in any one of the preceding claims.

32. An authentication system including: a bounding system including a tag database and for generating, and providing communications access for a user device to, k tag bases, k representing the number of times a user device is able use a credential associated with the user device, each tag base including random data and a signature on the random data; and a verifying system for receiving from the user device a service request and credential-show data including a tag and a proof, said tag being generated from the credential and a tag base, and said proof being for indicating the tag is correctly generated from the credential and one of said tag bases, and is based on the signature of the tag base, and for processing the service request in response to verifying the proof is valid and the tag is not stored in the tag database, and adding the credential-show data to the tag database.

33. An authentication system as claimed in claim 32, including a credential granting system for granting said user device said credential.

34. An authentication system as claimed in claim 33, wherein the credential includes public and secret cryptographic keys generated by a join process performed by the user device and the credential granting system.

35. An authentication system as claimed in claim 32 or 34, including a bounding system for maintaining said tag database and for monitoring the number of times said credential and said tag bases are used.

36. An authentication system as claimed in claim 35, wherein said bounding system sets k.

37. An authentication system as claimed in claim 36, wherein said verifying system includes an application provider system providing the service on processing said service request.

38. An authentication system as claimed in claim 37, wherein said signature is a digital signature of said application provider system.

39. An authentication system as claimed in claim 38, wherein said application provider system includes said bounding system.

40. An authentication system as claimed in claim 33, wherein said credential is revocable by said credential-granting system.

41. An authentication system as claimed in claim 35, wherein said user device is granted said credential by at least one of a credential-granting system and said bounding system

42. An authentication system as claimed in claim 41, wherein said credential is revocable by at least one of said credential-granting system and said bounding system.

43. An authentication system as claimed in anyone of claims 32 to 42, wherein said verifying system includes a tracing module for accessing said tag database to determine use of said credential more than k times.