Patent Publication Number: US-9906512-B2

Title: Flexible revocation of credentials

Description:
TECHNICAL FIELD 
     The present invention relates generally to access credentials and more specifically to handling revocation statuses of a plurality of credentials. 
     BACKGROUND 
     Credentials, and more precisely cryptographic credentials, are commonly known and used in cryptography-based applications, e.g. cryptographically secured exchange of data between computer systems or devices, to certify information. A credential holder, who is requested to provide information, may provide the requested information and use a credential to prove that the provided information is correct and trustable. A cryptographic credential is essentially a certificate generated via a cryptographic process. Such a credential is issued by a credential issuing entity to a credential holder after the information to be certified by the credential has been appropriately verified. The information in question is cryptographically encoded in the credential to certify the correctness of said information. In particular, the information to be certified may be represented by some value or function which is then encoded in the credential via a cryptographic algorithm. When requested by a verifying entity to provide certain information and to prove the same, the credential holder may provide the requested information and use a credential, in which this information is encoded, to make a suitable proof to the verifying entity, via various cryptographic proof protocols. 
     Sometimes such credentials need to be revoked, e.g. when the secret cryptographic keys to which the credential is bound have been exposed or the credential holder lost the right to possess the credential. 
     Revocation tasks are carried out by revocation authorities. The revocation authority creates and maintains a revocation list with revocation statuses of credentials. This list may be a whitelists or a blacklist, listing all the credentials which are valid or invalid, respectively. A credential becomes invalid by revoking the same. The revocation is performed through a revocation handle, i.e. a dedicated unique identifier that the issuing entity embeds in each issued credential. When a credential is to be revoked, a request for revocation must be provided to the revocation authority. Upon receiving a valid request for revocation of a credential, the revocation authority deletes or adds the respective credential from or to the revocation list, depending on whether it is a whitelists or a blacklist. 
     In order to prove that a credential used for certifying information is valid, i.e. not revoked, membership or non-membership of the credential&#39;s revocation handle in the revocation authority&#39;s whitelists or blacklist has to be proven. 
     SUMMARY 
     It is an objective of the present invention to provide for an improved computer-implemented method, a computer program product and a computer system for handling revocation statuses of credentials as specified in the independent claims. Embodiments of the invention are given in the dependent claims. Embodiments of the present invention can be freely combined with each other if they are not mutually exclusive. 
     In one aspect, the invention relates to a method for handling revocation statuses of credentials, the method including the issuing and storing a plurality of credentials by a credential issuing computer system where each credential is provided to a user computer device that is configured for requesting one or more hardware and/or software functions offered and provided by one or more credential verifying computer systems. The method additionally includes a revocation computer system initializing and storing a revocation status vector comprising vector elements, wherein for a set of the vector elements each vector element is assigned to a different one of the credentials, each vector element comprises a sequence of bits, and each bit of the set of bits is assigned to a different one of the functions. The bit value at a given bit position of the sequence is indicative of the credential assigned to the element comprising said sequence of bits as well as a revocation status indicating whether said credential is valid or invalid for the function assigned to said bit position. For each sequence of bits the same bit positions are assigned to the same functions, transforming the revocation status vector by the revocation system into a commitment value and providing the commitment value to the one or more verifying computer systems. The method additionally includes computing a witness value by the revocation system for each vector element of the set of vector elements and providing both the vector element which is assigned to the credential of said user computer device and the respective witness value to the user computer device. The witness value proves that the vector element provided is identical to the vector element for which the witness value was computed. The method further includes generating a presentation token by the user computer device for its credential comprising the vector element provided by the revocation system and a proof of possession of the respective credential assigned to said vector element and of possession of the witness value computed for said vector element. The method additionally includes transmitting the presentation token and a request for one of the hardware and/or software functions to the respective verifying computer system by the user computer device, then receiving the presentation token and request by said verifying computer system. The verifying computer system then evaluates the requested function and the validity of the revocation status of the credential for which the presentation token was generated using the commitment value for verifying the proof of possession of the witness value comprised by the presentation token. Then, if valid, providing the requested function to the requesting user computer device. 
     In another aspect, the invention relates to a computer-implemented method for handling revocation statuses of credentials which includes initializing and storing a revocation status vector for a plurality of credentials to be assigned to respective user computer devices. Each credential regulates the permissions of the respective user computer device to request one or more hardware and/or software functions. The revocation status vector comprises vector elements and for a set of the vector elements, each vector element is assigned to a different one of the credentials, each vector element comprises a sequence of bits, and each set of the vector bits is assigned to a different one of the plurality of hardware and/or software functions. The bit value at a given bit position of the sequence is indicative of for the credential assigned to the element comprising said sequence of bits and a revocation status indicating whether said credential is valid or invalid for the function assigned to said bit position. For each sequence of bits, the same bit positions are assigned to the same functions. The method further includes transforming the revocation status vector into a commitment value, computing a witness value for each vector element of the set of vector elements, and providing to a respective computer user device the vector element which is assigned to the credential of said user computer device and the respective witness value. The witness value proves that the vector element provided is identical to the vector element for which the witness value was computed. 
     In a further aspect, the invention relates to a computer program product for handling revocation statuses of credentials, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions being executable by a processor to cause the processor to execute the method according to any one of the previous claims. 
     In a further aspect, the invention relates to a computer system for handling revocation statuses of credentials. The computer system comprises a processor, a storage medium, and an interface for providing and receiving data. The processor comprises program instructions executable by the processor and causing the system to initialize and store in the storage medium a revocation status vector for a plurality of credentials to be assigned to respective user computer devices. Each credential regulates the permission of the respective user computer device to request one or more hardware and/or software functions. The revocation status vector comprises vector elements and each vector element is assigned to a different one of the credentials. Each vector element comprises a sequence of bits and for a set of the bits each bit of the set of bits is assigned to a different one of the plurality of hardware and/or software functions. The bit value at a given bit position of the sequence is indicative of the credential assigned to the element comprising said sequence of bits. The revocation status indicates whether said credential is valid or invalid for the function assigned to said bit position and for each sequence of bits the same bit positions are assigned to the same functions. The program instructions further cause the system to transform the revocation status vector into a commitment value, to compute a witness value for each vector element of the set of vector elements, and to provide to a respective computer user computer device the vector element which is assigned to the credential of said user computer device and the respective witness value. The witness value proves that the vector element provided is identical to the vector element for which the witness value was computed. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
       Embodiments of the present invention are explained in greater detail, by way of example only, making reference to the drawings in which: 
         FIG. 1  depicts a schematic block diagram of a system according to embodiments of the invention. 
         FIG. 2  depicts a schematic block diagram of a system according to embodiments of the invention. 
         FIG. 3  depicts a schematic block diagram of a system according to embodiments of the invention. 
         FIG. 4  depicts a schematic block diagram of a revocation status vector according to embodiments of the invention. 
         FIG. 5  depicts a tabular diagram of assignments of the revocation status vector depicted in  FIG. 4 . 
         FIG. 6  depicts a flow diagram of a method according to embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments may be beneficial in that a credential may be assigned to be invalid only for specific functions, e.g. a user is not allowed to use a credential with a specific function of a specific verifying computer system, but may still use it elsewhere. The effect of such invalidity may be restricted to specific functions offered by specific verifying computer systems only, while it does not affect the validity of the credential for use with other verifying computer systems or for other functions. 
     In order to implement function specific revocation statuses for a plurality of credentials, for each credential a plurality of revocation statuses, each assigned to such a specific function, has to be handled efficiently. Considering n credentials and m hardware and/or software functions, each credential is assigned with a revocation status for each of m functions. Each credential may be assigned to a user who uses the credential via a suitable user computer device or directly to a respective user computer device. The revocation statuses indicate whether the respective credential is valid or invalid for the respective function for which the revocation status is assigned. Said revocation statuses may be summarized in m revocation lists, each list listing the revocation statuses of all n credentials for one of the m functions. The amount of data may be reduced by only listing revocation statuses for valid or invalid credentials, i.e. using whitelists or blacklists. 
     The method according embodiments of the present invention may allow combining information corresponding to m such revocation lists into a single commitment value. Each user or user computer device needs only one witness value to prove that a credential assigned to and possessed by said user computer device is e.g. whitelisted. A user computer device requesting a function may in general try to prove that the credential assigned to said device is valid for the requested function, i.e. is whitelisted in case of a whitelist or not blacklisted in case of a blacklist. However, a revocation status vector according to embodiments of the present invention, comprises all revocation statuses, i.e. valid as well as invalid, and thus corresponds to mixed lists which are black and white. 
     This may have the further advantage that the corresponding scheme is particularly efficient in terms of storage. Considering n credentials and m revocation lists for m verifying computer systems and/or functions, each list comprising the revocation statuses of each credential for the respective verifying computer system and/or function to which the list is assigned, a scheme combining each list into a commitment would require the computation of m commitment values and each user computer device would need to store and update m witness values. With a scheme according to the present invention, only one commitment value based on a respective revocation vector comprising the revocation statuses of all credentials for all computer systems and/or functions and one witness value per credential is required. Consequently, for a scheme combining each of the m lists into a commitment value of its own, the required storage capacity grows with m, while this may not be the case for embodiments of the invention. 
     The same may hold in terms of computation cost: To combine n credentials with respect to m revocation lists, in case of a scheme combining each list into a commitment value of its own, the number of computational operations growths with n and with m, depending on the details of the scheme e.g. n·m multiplications may be required. Computing witness values for one credential involves a similar cost. 
     In the present schemes, the cost of transforming n credentials with respect to m verifying computer systems and/or functions into one commitment value may involve n computational operations, one per vector element. The computation of the user witness value has a similar cost. Thus, the cost may only grow with n, not with m, e.g. the costs of computing the commitment value and witness values may only be n multiplications each. This cost may be further reduced using precomputation, because, in the present case, it is likely that, when a credential is issued for each vector element all bit values may be set to indicating validity for all verifying computer systems and/or functions. 
     Embodiments may have the further advantage that they allow adding or/and removing revocation statuses indicating whether a credential is valid or invalid for a function with little effort. The set of vector elements assigned to credentials may be smaller or equal to the total number of vector elements of the revocation vector. Initiating a revocation status vector with a sufficient large number of vector elements, i.e. the total number of vector elements of the revocation vector being larger than the number of vector elements of the set, new revocation statuses for a new credential may be easily added by assigning a vector element, which is not yet part of the set of vector elements, to the new credential. Thus, the set of vector elements assigned to credentials may be easily extended. When extending the set of assigned vector elements, an additional witness value for each newly assigned vector element may be computed. Furthermore, the commitment value as well as the witness values already computed may have to be updated. 
     Embodiments may also have the advantage that it is particularly simple to add revocation statuses for new functions. The number of bits of each set of bits assigned to functions may be smaller or equal to the total number of bits of the sequence of bits the respective set is part of. Initiating a revocation status vector, wherein each sequence of bits is sufficiently large, i.e. the total number of bits of each sequence of bits being larger than the number of bits of the set of assigned bits comprised by the respective sequence, a new function may be easily added by assigning a bit of each sequence of bits, which has not yet been assigned to a function, to the new function. Thus, each set of bits assigned to functions may be easily extended. When extending the sets of bits assigned to functions, no additional commitment or witness values may have to be computed. It may be sufficient to update the commitment value as well as the witness values already computed. In case the revocation statuses for a certain function should not be taken into account anymore, e.g. because the respective function is not offered anymore, the function may be easily removed by checking for each sequence of bits, whether the bit value at the position of the sequence of bits assigned to the respective function indicates invalidity for the respective function, and, if not, altering the respective bit value such that it indicates invalidity. Again, no additional commitment or witness values may have to be computed. It may rather be sufficient to update the commitment value as well as the witness values already computed. 
     According to an example, the bit values of bits which are comprised by the revocation status vector, but not assigned to any function may be chosen such that they indicate invalidity. Furthermore, when computing the commitment value, according to an example only those vector elements of the revocation status vector assigned to a credential may be taken into account. 
     According to embodiments, the method further comprises revoking by the revocation computer system the credential in response to receiving a revocation request to revoke the credential for a function offered by the verifying computer system, the revocation comprising generating an updated vector element for the vector element of the revocation status vector assigned to the credential to be revoked by altering the revocation status associated with the credential to be revoked, providing said updated vector element to the user computer device to which the updated vector element is assigned via the credential to be revoked, updating the commitment value with said updated vector element and providing said updated commitment value to the one or more verifying computer systems and to the user computer device to which the updated vector element is assigned via the credential to be revoked, updating each witness value which computation included the vector element for which the updated vector element is generated with said updated vector element and providing each updated witness value to the user computer device to which the updated witness value is assigned via the vector element for which the updated witness value is computed. 
     This may have the advantage that a credential may be easily revoked for one specific function, while it remains valid for other functions. 
     A credential may be revoked for different reasons: Issuer-driven revocation is global in scope, meaning that any presentation token is checked against the most recent revocation information provided by the specified revocation authority and that the issuing entity denies any responsibility for revoked credentials. 
     Issuer-driven revocation may be used when credentials have been compromised or lost, or when the user is denied all further use of the credential. Issuer-driven revocation for a credential may be performed by the revocation computer system upon receiving a corresponding revocation request from the issuing computer system by altering all bit values of the vector element assigned to said credential to values indicating invalidity. 
     Verifier-driven revocation may aim to revoke a credential such that it cannot be used anymore for gaining access to hardware and/or software functions provided by anyone of the verifying computer systems. Such a revocation may be initiated by anyone of the verifying computer systems or a third party. A verifier-driven revocation may e.g. be based on a no-fly list, preventing persons, whose names are on said list from purchasing a flight ticket or passing security controls, when trying to gain access to a plane. A verifier-driven revocation may also be used to excluding a user from a website by denying access to the same. The effect of the revocation may be restricted to the functions offered by such verifying computer systems that explicitly specify the revocation computer system in their presentation policies, and does not affect presentations with other verifying computer systems. 
     Revocation may be performed through a revocation handle, a dedicated unique identifier that the issuing computer system embeds in each issued credential. When the issuing computer system, a verifying computer system, or any third party wants to revoke a credential, it may provide the respective revocation handle to the revocation computer system. The revocation handle could be revealed, for example, by enforcing in a presentation policy for presentation token that the revocation handle be encrypted with the public key of a trusted entity, which decrypts it when receiving a proof of user misbehavior. 
     Furthermore, this may have the advantage of allowing an efficient update of the commitment value and witness values due to a revocation of a credential for a verifying computer system and/or function. For a scheme with m independent revocation lists, updating the revocation status of a credential with respect to each of the m revocation lists may involve m computational operations, e.g. m multiplications, i.e., one computational operation for each of the commitments in which the status should be updated. Updating the witnesses involves a similar cost. In a construction according to embodiments of the invention, an update may require only one computational operation for the commitment value and one per witness value. Thus, the cost may only grow with n, not with m. 
     Updating a witness assigned to a user computer device imposes an important overhead on the revocation computer system, when the number of user computer devices is large. However, according to an embodiment of the invention with a non-hiding revocation scheme, the witness values may be updated by user computer devices because the update algorithm only needs public information. 
     According to embodiments, altering the revocation status of the credential comprises altering in the bit sequence of the vector element assigned to said credential to be revoked the bit value at the bit position assigned to said function to be revoked from a value indicating validity to a value indicating invalidity. 
     This may have the advantage that the revocation status of a credential for a particular function may be easily altered by altering the corresponding bit value. From the bit position it can be easily derived for which function the credential is revoked. 
     According to embodiments, the revocation request is a request of a set of revocation requests, the revocation comprising collecting the received revocation requests until a collection criterion is fulfilled, in case the collection criterion is fulfilled, updating the vector elements of the revocation vector, the commitment value and the witness values according to the collected revocation requests. 
     This may have the advantage that by bundling the revocation requests computational resources are saved. The whole update procedure is not executed for every single revocation request independently, but only after a collection criterion has been fulfilled. Before executing the update procedure, i.e. as long as the criterion is not fulfilled, revocation requests are collected. A collection criterion may for example be a laps of time, in particular laps of a predetermined time, an absolute time, a number of requests, a processor load available as well as combinations thereof. 
     According to embodiments, the method further comprises initializing by the revocation computer system a provisional revocation status vector identical to the initialized revocation status vector, the collecting of the received revocation requests comprising altering the revocation statuses identified by the provisional revocation status vector according to the received revocation requests, the updating of the vector elements of the revocation vector, the commitment value and the witness values being performed with the vector elements of the provisional vector elements differing from the corresponding vector elements of the revocation vector. 
     This may have the advantage that it can be efficiently kept track on the revocation requests collected over a predetermined time before executing the update procedure. 
     According to embodiments, the transformation for transforming the revocation status vector being described by x into the commitment value being described by com is: 
             com   =       ∏     j   =   1     n     ⁢           ⁢     g     ℓ   +   1   -   j       x   ⁡     [   j   ]                 
the witness value being described by w i  for the ith vector element being described by x[i] being computed by:
 
               w   i     =       ∏       j   =   1     ,     j   ≠   i       n     ⁢           ⁢     g     ℓ   +   1   -   j   +   1       x   ⁡     [   j   ]                 
said commitment value com and witness values w i  being updated with the updated vector element denoted by x′[j] by
 
               com   ′     =     com   ·       g     ℓ   +   1   -   j         x   ′     ⁡     [   j   ]           g     ℓ   +   1   -   j       x   ⁡     [   j   ]                       and               w   i   ′     =       w   i     ·       g     ℓ   +   1   -   j   +   i         x   ′     ⁡     [   j   ]           g     ℓ   +   1   -   j   +   i       x   ⁡     [   j   ]                   
iε[1,n], jε[1,n], x[j] with jε[1,n] and |x|=n≦  denoting the jth vector element of the n vector elements of the revocation status vector x, each vector element being a sequence of m bits, a bit value of 1 indicating validity and a value of 0 indicating invalidity of the credential for the function the bit is assigned to, the bit sequence further being handled as a binary number for the above transformations and computations, g i =g (α     i     )  and {tilde over (g)} i ={tilde over (g)} (α     i     )  with α←   p , gε  and {tilde over (g)}ε ,    p  being the additive group modulo p,   and   being groups of prime order p, com′ denoting the updated commitment value and w′ i  denoting the updated witness value for the ith vector element x[i].
 
     This may have the advantage of allowing an efficient update of the commitment value and witness values, when the credential is revoked for a function. For a scheme with m independent revocation lists, updating the revocation status of a credential with respect to each of the m revocation lists may involve m computational operations, e.g. m multiplications, i.e., one computational operation for each of the commitments in which the status should be updated. Updating witnesses involves a similar cost. According to embodiments of the invention, an update may only require one computational operation for the commitment value and one per witness value. Thus, the cost may only grow with n, not with m. 
     According to embodiments, the transformation for transforming the revocation status vector being described by x into the commitment value being described by com incorporating a random number r← : 
             com   =       g   r     ·       ∏     j   =   1     n     ⁢           ⁢     g     ℓ   +   1   -   j       x   ⁡     [   j   ]                   
the witness value being described by w i  for the ith vector element being described by x[i] incorporating the same random number r← :
 
               w   i     =       g   r     ·       ∏       j   =   1     ,     j   ≠   i       n     ⁢           ⁢     g     ℓ   +   1   -   j   +   i       x   ⁡     [   j   ]                   
said commitment value com and witness values w i  being updated with the updated vector element denoted by x′[j] and a random number r′←  assigned to said updated vector element
 
               com   ′     =     com   ·         g     r   ′       ·     g     ℓ   +   1   -   j         x   ′     ⁡     [   j   ]               g   r     ·     g     ℓ   +   1   -   j       x   ⁡     [   j   ]                         and               w   i   ′     =       w   i     ·         g     r   ′       ·     g     ℓ   +   1   -   j   +   i         x   ′     ⁡     [   j   ]               g   r     ·     g     ℓ   +   1   -   j   +   i       x   ⁡     [   j   ]                     
iε[1,n], jε[1,n], x[j] with jε[1, n] and |x|=n≦  denoting the jth vector element of the n vector elements of the revocation status vector x, each vector element being a sequence of m bits, a bit value of 1 indicating validity and a value of 0 indicating invalidity of the credential for the function the bit is assigned to, the bit sequence further being handled as a binary number for the above transformations and computations, g i =g (α     i     )  and {tilde over (g)} i ={tilde over (g)} (α     i     )  with α←   p , gε  and {tilde over (g)}ε ,    p  being the additive group modulo p,   and   being groups of prime order p, com′ denoting the updated commitment value and w i  denoting the updated witness value for the ith vector element x[i].
 
     This may have the advantage of allowing constructing a so-called hiding commitment value, such that based on a commitment value and an updated commitment value it is impossible to learn which credentials have been added to or revoked from the revocation vector. This is due to the additional random numbers r, r′ incorporated into the commitment value, which are only known to the revocation computer system. 
     According to embodiments, the generation of the presentation token further comprises computing an additional commitment to the vector element comprised by the presentation token and an additional witness proving that the additional commitment is a commitment to said vector element, the presentation token comprising a proof of possession of the additional witness proving that the provided vector element is identical to the vector element assigned to the credential for which the presentation token was generated and proving that the bit value at the bit position of the sequence of bits of said vector element assigned to the requested function identifies a revocation status indicating that said credential is valid for the function assigned to said bit position. 
     This may have the advantage that by using the presentation token, the user computer device is enabled to prove to the verifying computer system that the credential possessed by the user computer device is valid for the requested function, while hiding further bit values assigned to said credential. 
     According to embodiments, the credential provided to the user computer device is an attribute-based credential comprising attributes incorporated into the credentials by the issuing computer system, the attributes being assigned to the user of the user computer device to which the credential is provided, the presentation token generated by the user computer device further revealing at least one of the attributes of the credential, the generation of the presentation token determining which one of the attributes is revealed in the generated presentation token. 
     This may have the advantage that the user is enabled to select which attributes are revealed, thus enhancing the user&#39;s privacy and even allowing the user to remain anonym. 
     The attributes may be encoded in the credential to be certified by using the credential. Such an attribute may represent any information associated with a credential holder, i.e. a user or user computer device, for which the credential holder may be required to provide proofs of correctness and trustworthiness. A method according to embodiments of the invention may be particularly suitable for privacy-enhancing attribute-based credentials (PABC), also known as anonymous credentials or minimal-disclosure tokens, which are credentials allowing for data-minimizing authentication. Cryptographic mechanisms based on PABCs enable a user or user computer device to obtain a credential from an issuing entity or issuing computer system, by which the issuing computer system assigns a list of certified attribute values to the user or user computer device. Particular examples of attribute-based credentials include government or electronic ID cards certifying personal or other security-sensitive information, like a user&#39;s name, nationality, municipality, date of birth, about which proofs may need to be made by a credential holder, i.e. user of a credential, in order to gain access to a software and/or hardware function provided by a verifying computer system. The user computer device may use this credential to authenticate to a verifying computer system offering hardware and/or software functions for which certain authentication is required by computing a presentation token. Such functions comprise e.g. access to a service, facility or other resource. 
     Moreover, different presentation tokens generated using PABCs may have the advantage to be untraceable, in the sense that a verifier cannot tell whether they were computed by the same or by different users. PABCs offer important privacy advantages over other attribute credential schemes, which usually either employ a central authority that is involved in every authentication and therefore forms a privacy bottleneck (e.g., SAML, OpenID, or Facebook Connect), or force users to disclose all of their attributes (e.g., X.509 certificates). 
     This may have the further advantage that a revocation may be performed based on any attribute, not just based on the revocation handle. It is up to the verifying computer systems and/or the revocation computer system to choose an attribute that on the one hand is sufficiently identifying to avoid false positives and on the other hand will be known to the party likely to request the revocation of a credential. 
     The present invention may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention. 
     The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire. 
     Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device. 
     Computer readable program instructions for carrying out operations of the present invention may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The computer readable program instructions may execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention. 
     Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions. 
     These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions. 
     The computer readable program instructions may execute on a computer system configured for ensuring privacy. Therefore, the computer readable program instructions may execute on a trusted computer using secure communication channels. In case of outsourcing of computations secure schemes for ensuring privacy may be applied. 
     According to the present invention a method for handling revocation statuses of credentials and in particular a method for revoking such credentials is proposed which refers to a revocation status vector. The revocation status vector is transformed into to a single commitment value. 
     As examples, two embodiments of the method may be proposed, one based on a non-hiding commitment and the other one on a hiding commitment. These embodiments may for example be implemented based on the Diffie-Hellman Exponent (DHE) assumption. 
     In the first non-hiding embodiment, when computing a presentation token, the user computer device may reveal x[i] to the verifying computer system. The verifying computer system therefore learns the revocation status of the user computer device in all m revocation lists, i.e. all values x[i,j] for credential i and jε[0; m]. 
     In the second hiding embodiment, a construction that employs hiding all the revocation statutes of a credential i except for one may be implemented. The presentation tokens only reveal the bit x[i, j] to the verifying computer system. This second construction hides the revocation status of a credential from the user computer devices of other credentials of the same type as well as from the verifying computer systems. 
       FIG. 1  is a schematic diagram of an exemplary system executing a method according to embodiments of the invention. The system comprises a credential issuing computer system  100  for issuing a credential provided to the user computer device  200 . The system furthermore comprises a verifying computer system  300  which may for example be configured as a video streaming service system offering video streaming on demand. In order to provide a function requested by the user computer device  200 , the verifying computer system  300  may require certain information from the user computer device  200 . For example for some or all videos provided by the video streaming service system, said system may require information about the date of birth and municipality of a user requesting via a user computer device contents provided by the video streaming service system. The video streaming service system may e.g. require that the user lives in a municipality of a certain country and is of legal age, e.g. 18 years or older, in order to be granted access to the contents. For that purpose the user computer device  200  may be provided with a PABC credential s i  containing a plurality of attributes a i,1 , a i,2 , a i,3 , a i,4 , . . . assigned to the user of user computer device  200 . As an example, these attributes may be inter alia the users name→a i,1 , nationality→a i,2 , municipality→a i,3  and date of birth→a i,4 . This credential s i  may be an electronic document like an electronic ID card, driver&#39;s license or passport issued by a government agency via the issuing computer system  100 . 
     However, the user may not want to disclose all attributes contained in credential s i . Furthermore, not all the assigned attributes may be necessary for a sufficient authentication. In order to satisfy geographical restrictions or age-restrictions, it may only be necessary to provide attributes like municipality and date of birth. It may even be sufficient to prove that the user is of a certain minimum age, e.g. of legal age. Therefore, the user computer device may not provide the credential s i  to verifying computer system  300 , but a presentation token tk i  generated by the user computer device  200 , disclosing only a subset of the attributes, e.g. a i,3  and a i,4 , whereas all non-disclosed attributes remain hidden from the verifying computer system  300 . In case of a verifying computer system  300  configured as a video streaming service, the subset of attributes disclosed by a presentation token may be for example a i,3 →municipality and a i,3 →date of birth. 
     Attribute-based credentials need to be revoked for different reasons. In some cases, credentials need to be revoked globally, e.g., when the related secret keys are exposed, the user lost the right to possess a credential, or the attribute values have changed. Sometimes credentials may have to be revoked only for specific functions, i.e., a user is not allowed to use a credential with a specific verifier but can still use it elsewhere. Revocation tasks may be carried out by a revocation computer system  400  of a revocation authority. Such a revocation authority is a separate entity in general, but may be under the control of the issuing entity or a verifying entity in particular settings. Nevertheless, the revocation computer system  400  may in general be separate from the issuing computer system  100  and the verifying computer system  300 . 
     The user computer device  200  is provided with a commitment value com of the revocation status of credential s i  and a witness value w i . Furthermore, the video streaming service system  300  is also provided with the commitment value com. 
     The concept of commitment is a fundamental concept in cryptography applications and essentially involves use of a cryptographic function to generate cryptographic information, the commitment, which encodes information to which the provider of the commitment wants to commit. Cryptographic proofs can then be made about the value in the commitment without revealing the value itself. Furthermore, the provider of the commitment may also provide a witness, the witness being cryptographic information, which can prove that certain information is identical to or part of the information encoded in the commitment. 
     A commitment value com is provided, in which the revocation statuses of the credentials issued by the issuing computer system  100  are encoded. Each user computer device in addition to be provided with a credential s i  is also provided with a witness value w i  assigned to said credential proving that a certain combination of revocation statuses, i.e. a list of revocation statuses, is indeed the correct list of revocation statuses of this credential cryptographically encoded into said commitment value com. 
     To provide certified information, e.g. information certified by the credential, to the verifying computer system, the user computer device may generate a presentation token tk i , which instead of disclosing all information comprised by the credential, e.g. all attributes, only selective information. Such a presentation token tk i  provides cryptographic evidence of the disclosed attribute values. 
     Instead of disclosing name, nationality, municipality and date of birth of the a user, like the credential assigned to the user, a presentation token may be generated, only revealing the two attributes municipality and date of birth to the verifying computer system  300 . The presentation token may also prove that a given predicate holds, without revealing the full attributes&#39; values. The presentation token may e.g. prove that the date of birth is before a certain given date or that the name on the user&#39;s credit card matches that on her driver&#39;s license. 
     Regarding the revocation status of the credential s i  for the video streaming function provided by the video streaming service system  300 , the presentation token tk i  may further comprise the revocation status x i  and the witness value w i . The witness value w i  proving that the revealed revocation status x i  is part of the revocation information encoded within the commitment value com. The respective commitment value com may be provided to verifying computer system  300  by the revocation computer system  400 . Consequently, the verifying computer system  300  knows that the provided commitment value com is trustable and is enabled to verify with the commitment value com and the witness value w i  that the revealed revocation status x i  is the correct revocation status committed to and thus certified by the revocation computer system  400 . 
     A setting for executing the method according to the present invention comprises an issuing computer system I  100 , a revocation computer system    400 , n user computer devices    1 , . . . ,    n    200 ,  200 ′ and m verifying computer systems    1 , . . . ,    m    300 ,  300 ′,  300 ″. The issuing computer system I  100  issues n credentials s 1 , . . . , s n  to each of the user computer devices    1 , . . . ,    n . Each credential s i  signs a set of l attributes (a i,1 , . . . , a i,l ) and a revocation handle rh i . The revocation handle rh i  is data element identifying the ith credential s i , e.g. a serial number. When handling the revocation statuses of a credential s i , the revocation handle rh i  is used to unambiguously identify the credential s i . For simplicity, a integer rh i =i may be assigned for identifying the ith credential. 
       FIG. 2  is a schematic diagram of an exemplary computer system executing the method according to embodiments of the invention, with a plurality of user computer devices  200 ,  200 ′ and verifying computer systems  300 ,  300 ′,  300 ″. The revocation computer system initializes a revocation status vector comprising the revocation statuses of all credentials s i , s j  for all m verifying computer systems  300 ,  300 ′,  300 ″. All user computer devices  200 ,  200 ′ and verifying computer systems  300 ,  300 ′,  300 ″ are provided with the commitment value com committing to said revocation statuses. Furthermore, each user computer devices  200 ,  200 ′ is provided with a witness value w i , . . . , w j  for the revocation statuses of the credentials s i , . . . , s j  assigned to the said user computer devices i . . . , j, respectively. Thus, each one of the user computer devices, e.g. user computer device i  200  may generate presentation token tk i,1 , tk i,2 , . . . , tk i,m  for each of the all m verifying computer systems  300 ,  300 ′,  300 ″. Each presentation token tk i,1 , tk i,2 , . . . , tk i,m  providing the revocation statuses of the credential s i  and the witness value w i , proving that the revocation statuses are identical with the revocation statuses of credential s i , which have been encoded within the commitment value com, and thus authentic. 
       FIG. 3  shows a schematic diagram of devices and computer systems which may be used for executing the method according to embodiments of the invention. In  FIG. 3  exemplary issuing computer system  100 , user computer device  200 , verifying computer system  300  and revocation computer system  400  are depicted. These computer devices and system are each connected to the network  500  via which data is transmitted between these computer devices and system like a commitment value com, the witness values w i , a presentation token tk etc. For connecting to the network  500 , each computer device and system comprises a network interface  110 ,  210 ,  310 ,  410 . The computer devices and systems each comprises a processor  120 ,  220 ,  320 ,  420  with program instructions  121 ,  221 ,  321 ,  421  for executing the steps of the method according to the present invention. Furthermore, the computer devices and systems each comprises a memory device  130 ,  230 ,  330 ,  430 , i.e. a computer data storage, for storing the data generated by and transmitted between the computer devices and systems. Thus, the memory  130  of the issuing computer system  100  may comprise the credentials  131  issued by said system. The memory  430  of the revocation computer system  400  may comprise the revocation status vector  431  as well as a commitment value  432  resulting from a transformation of the vector  431  and witness values  433  computed from vector  431 . In the memory  230  of the user computer device  200  a credential  231  assigned to the user computer device  200  along with the vector element  232  of revocation status vector  432  comprising all revocation statuses of credential  231  may be stored. Furthermore, the commitment value  233  received from the revocation computer system  400  together with a witness value  234  for vector element  232  may be comprised by memory  230 . Also a presentation token  235 , generated by the user computer device  200  may be stored in the memory  230 . The verifying computer system  300  may store in its memory  330  the commitment value  331  received from the revocation computer system  400  via the network  500 . The verifying computer system  300  further comprises a hardware and/or software function  340 , which it offers to the user computer device  200 . 
     It is understood that the computer devices and system shown in  FIG. 3  may comprise more computer elements than the ones depicted, in particular the verifying computer system may provide more than one hardware and/or software function. Further, more data may be stored in the memories  130 ,  230 ,  330 , and  430 . Finally, although only one user computer device  200  and one verifying computer system  300  are shown as examples the method according to embodiments of the invention may be intended for handling a plurality of credentials assigned to a plurality of user computer devices, wherein each credential is assigned with a plurality of revocation statuses for a plurality of functions offered by a plurality of verifying computer systems. 
     In order to efficiently manage revocation of function-specific revocations for a plurality of n credential and m functions, according to embodiments of the invention a method is suggested, based on a vector structure from which a single commitment value is derived by transforming the vector. That method may allow combining information resembling m revocation lists into a single commitment value. More specifically, the revocation computer system may commit to a vector x of size n, where n is the number of credentials of a certain type and thus probably also the number of user computer devices that possess a credential of said type. The component x[i] is associated to user or user computer device i. The jth bit of x[i] may be denoted by x[i,j]. Furthermore, x[i,j]=1 may denote that the credential of user computer device i is valid according to revocation list j, while x[i,j]=0 may indicate that the corresponding credential is revoked for the specific function i. In this scheme each user computer device needs only one witness value w i . 
       FIG. 4  shows a schematic diagram of a revocation status vector x according to embodiments of the invention. The revocation status vector is of size n, i.e. it comprises n vector elements x[1], . . . , x[n]. Each vector element x[i] is assigned to a different one of the credentials s i , each vector x[i] element comprises a sequence of m bits x[i, 1], . . . , x[i, m]. Thus, each sequence of bits comprises m bit positions b 1 , . . . , b m  form bits x[i, 1], . . . , x[i, m]. Each bit x[i, j] of a sequence of bits is assigned to a different one of a plurality of hardware and/or software functions and for each sequence of bits the same bit positions b j  are assigned to the same functions. 
       FIG. 5  shows a tabular diagram of the assignments of vector elements x[1], . . . , x[n] of the revocation status vector x shown in  FIG. 4  as well as the assignments of the bit positions b 1 , . . . , b m . Vector elements x[1], . . . , x[n] are assigned to credential s 1 , . . . , s n . The positions b 1 , . . . , b m  of each sequence of bits are assigned to function  1 , . . . , function m. The bit value x[i, j] at a given bit position b j  of the sequence of bits of vector element x[i] identifies, for the credential s i  assigned to the vector element x[i], a revocation status indicating whether said credential s i  is valid or invalid for the function j assigned to said bit position b j . 
     The revocation status vector x shown in  FIG. 4  is transformed into a single commitment value. The transformation of the revocation status vector into a single commitment value may for example be based on bilinear maps satisfying the t-DHE assumption: For finite groups  ,  ,    t  of prime order p a with a map e:  × →   t  satisfying bilinearity, e(g x , {tilde over (g)} y )=e(g, {tilde over (g)}) xy  holds true. The groups may further be non-degenerated, i.e. for all generators gε  and {tilde over (g)}ε  of the groups   and  , respectively, e(g, {tilde over (g)}) is a generator of    t . The map e:  × =   t  may further satisfy efficiency, i.e., there exists an efficient algorithm  (1 k ) that outputs the pairing group setup (p,  ,  ,    t , e, g, {tilde over (g)}) and an efficient algorithms to compute e(a, b) for any aε  and bε . If  =  the map is called symmetric and otherwise asymmetric. 
     The t-DHE assumption is defined as follows: Let (p,  ,  ,    t , e, g, {tilde over (g)})← (1 k ) and α←   p , given (p,  ,  ,    t , e, g, {tilde over (g)}) and a tuple (g 1 , {tilde over (g)} 1 , . . . , g t , {tilde over (g)} t , g t+2 , . . . , g 2t ) such that g i =g (α     1     )  and {tilde over (g)} i ={tilde over (g)} (α     i     ) , for any probabilistic polynomial-time (PPT) adversary   Pr[g (α     t+1     ) ← (p,  ,  ,    t , e, g, {tilde over (g)}, g 1 , {tilde over (g)} 1 , . . . , g t , {tilde over (g)} t , g t+2 , . . . , g 2t )]≦ε(k) is satisfied. 
     A commitment may be based on the following schemes: A non-interactive commitment scheme may consist of algorithms CSetup, Com and VfCom. CSetup(1 k ) generates the parameters of the commitment scheme par c , which include a description of the message space  . Com (par c , x) outputs a commitment com to x and auxiliary information open. A commitment is opened by revealing (x, open) and checking whether VfCom (par c , com, x, open) outputs 1 or 0. A commitment scheme is required to fulfill the correctness, hiding and binding properties. 
     Correctness requires that VfCom accepts all commitments created by algorithm Com, i.e., for all xε   
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           
                             par 
                             c 
                           
                           ← 
                           
                             CSetup 
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 k 
                               
                               ) 
                             
                           
                         
                         ; 
                         
                           
                             ( 
                             
                               com 
                               , 
                               open 
                             
                             ) 
                           
                           ← 
                           
                             
                               Com 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     par 
                                     c 
                                   
                                   , 
                                   x 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               : 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           wit 
                           ← 
                           
                             Prove 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   par 
                                   c 
                                 
                                 , 
                                 com 
                                 , 
                                 x 
                                 , 
                                 open 
                               
                               ) 
                             
                           
                         
                         : 
                       
                     
                   
                   
                     
                       
                         1 
                         = 
                         
                           VfCom 
                           ⁡ 
                           
                             ( 
                             
                               
                                 par 
                                 c 
                               
                               , 
                               com 
                               , 
                               x 
                               , 
                               wit 
                             
                             ) 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             = 
             1. 
           
         
       
     
     The hiding property ensures that a commitment com to x does not reveal any information about x, whereas the binding property ensures that com cannot be opened to another value x′. Thus, for any PPT adversary  , the hiding property may be defined as follows: 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           
                             par 
                             c 
                           
                           ← 
                           
                             CSetup 
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 k 
                               
                               ) 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           ( 
                           
                             
                               x 
                               0 
                             
                             , 
                             
                               x 
                               1 
                             
                             , 
                             st 
                           
                           ) 
                         
                         ← 
                         
                           ?? 
                           ⁡ 
                           
                             ( 
                             
                               par 
                               c 
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           b 
                           ← 
                           
                             { 
                             
                               0 
                               , 
                               1 
                             
                             } 
                           
                         
                         ; 
                         
                           
                             ( 
                             
                               com 
                               , 
                               open 
                             
                             ) 
                           
                           ← 
                           
                             Com 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   par 
                                   c 
                                 
                                 , 
                                 
                                   x 
                                   b 
                                 
                               
                               ) 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           b 
                           ′ 
                         
                         ← 
                         
                           
                             ?? 
                             ⁡ 
                             
                               ( 
                               
                                 st 
                                 , 
                                 com 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             : 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             
                               x 
                               0 
                             
                             ∈ 
                             ℳ 
                           
                           ⩓ 
                           
                             
                               x 
                               1 
                             
                             ∈ 
                             ℳ 
                           
                           ⩓ 
                           b 
                         
                         = 
                         
                           b 
                           ′ 
                         
                       
                     
                   
                 
                 ] 
               
             
             ≤ 
             
               
                 1 
                 2 
               
               + 
               
                 
                   ε 
                   ⁡ 
                   
                     ( 
                     k 
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
     The binding property is satisfied, if for any PPT adversary   the following holds true: 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           
                             par 
                             c 
                           
                           ← 
                           
                             CSetup 
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 k 
                               
                               ) 
                             
                           
                         
                         ; 
                         
                           
                             ( 
                             
                               com 
                               , 
                               x 
                               , 
                               wit 
                               , 
                               
                                 x 
                                 ′ 
                               
                               , 
                               
                                 wit 
                                 ′ 
                               
                             
                             ) 
                           
                           ← 
                           
                             
                               ?? 
                               ⁡ 
                               
                                 ( 
                                 
                                   par 
                                   c 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               : 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             x 
                             ∈ 
                             ℳ 
                           
                           ⩓ 
                           
                             
                               x 
                               ′ 
                             
                             ∈ 
                             ℳ 
                           
                           ⩓ 
                           
                             x 
                             ≠ 
                             
                               x 
                               ′ 
                             
                           
                           ⩓ 
                           1 
                         
                         = 
                         
                           VfCom 
                           ⁡ 
                           
                             ( 
                             
                               
                                 par 
                                 c 
                               
                               , 
                               com 
                               , 
                               x 
                               , 
                               wit 
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           ⩓ 
                           1 
                         
                         = 
                         
                           VfCom 
                           ⁡ 
                           
                             ( 
                             
                               
                                 par 
                                 c 
                               
                               , 
                               com 
                               , 
                               
                                 x 
                                 ′ 
                               
                               , 
                               
                                 wit 
                                 ′ 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             ≤ 
             
               
                 ε 
                 ⁡ 
                 
                   ( 
                   k 
                   ) 
                 
               
               . 
             
           
         
       
     
     A general cryptographic signature scheme consists of the algorithms KeyGen, Sign, and VfSig. Algorithm KeyGen(1 k ) outputs a secret key sk and a public key pk, which include a description of the message space  . Sign (sk, m) outputs a signature s on message mε . VfSig(pk, s, m) outputs 1 if s is a valid signature on m and 0 otherwise. This definition may be extended to blocks of messages  m =(m 1 , . . . , m n ). Such a signature is required to fulfill the correctness and existential unforgeability properties. 
     Correctness ensures that algorithm VfSig accepts the signatures created by algorithm Sign on input of a secret key computed by algorithm KeyGen. More formally, correctness may be defined as follows: 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           
                             ( 
                             
                               sk 
                               , 
                               pk 
                             
                             ) 
                           
                           ← 
                           
                             KeyGen 
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 k 
                               
                               ) 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           m 
                           ← 
                           ℳ 
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         s 
                         → 
                         
                           
                             Sign 
                             ⁡ 
                             
                               ( 
                               
                                 sk 
                                 , 
                                 m 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             : 
                           
                         
                       
                     
                   
                   
                     
                       
                         1 
                         = 
                         
                           VfSig 
                           ⁡ 
                           
                             ( 
                             
                               pk 
                               , 
                               s 
                               , 
                               m 
                             
                             ) 
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             = 
             1. 
           
         
       
     
     The property of existential unforgeability ensures that it is not feasible to output a signature on a message without the secret key or another signature on that message. With    s  being an oracle that, on input sk and a message mε , outputs Sign (sk, m), and let S s  be a set that contains the messages sent to    s , for any PPT adversary   and for a positive integer L, L-existential unforgeability is defined as follows: 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           
                             ( 
                             
                               sk 
                               , 
                               pk 
                             
                             ) 
                           
                           ← 
                           
                             KeyGen 
                             ⁡ 
                             
                               ( 
                               
                                 1 
                                 k 
                               
                               ) 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           ( 
                           
                             m 
                             , 
                             s 
                           
                           ) 
                         
                         ← 
                         
                           
                             
                               ?? 
                               ⁡ 
                               
                                 ( 
                                 pk 
                                 ) 
                               
                             
                             
                               ↔ 
                               
                                 
                                   ?? 
                                   s 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     sk 
                                     , 
                                     · 
                                   
                                   ) 
                                 
                               
                             
                           
                           ⁢ 
                           
                             : 
                           
                         
                       
                     
                   
                   
                     
                       
                         1 
                         = 
                         
                           
                             VfSig 
                             ⁡ 
                             
                               ( 
                               
                                 pk 
                                 , 
                                 s 
                                 , 
                                 m 
                               
                               ) 
                             
                           
                           ⩓ 
                           
                             m 
                             ∈ 
                             ℳ 
                           
                           ⩓ 
                           
                             m 
                             ∉ 
                             
                               
                                 
                                   ?? 
                                   s 
                                 
                                 ⋀ 
                                 
                                    
                                   
                                     ?? 
                                     s 
                                   
                                    
                                 
                               
                               ≤ 
                               L 
                             
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             ≤ 
             
               
                 ε 
                 ⁡ 
                 
                   ( 
                   k 
                   ) 
                 
               
               . 
             
           
         
       
     
     For embodiments of the invention for example a structure preserving signature (SPS) scheme may be applied. In a SPS scheme the public key, the messages, and the signatures are group elements in groups   and  . Further, verification is required to consist purely in the checking of pairing product equations. SPS may be employed to sign group elements, while still supporting efficient zero-knowledge proof of knowledge (ZKPK) of signature possession. 
     For example a scheme may be applied in which a elements in group G and b elements in group   are signed. For this scheme the following functions may be used: 
     KeyGen (grp, a, b): With grp=(p,  ,  ,    t , e, g, {tilde over (g)}) being the bilinear map parameters, u 1 , . . . , u b , v, w 1 , . . . , w a , z← * p  are picked at random and U i =g u     i   , iε[1, b], V={tilde over (g)} v , W i ={tilde over (g)} w     i   , iε[1, a] and Z={tilde over (g)} z  are computed. Based on these parameters the verification key pk=(grp, U 1 , . . . , U b , V, W 1 , . . . , W a , Z) and the signing key sk=(pk, u 1 , . . . , u b , v, w 1 , . . . , w a , z) are returned. The verification key is in general public, while the signing key is secret. 
     Sign (sk,  m 1 , . . . , m a+b   ): At random r← * p  is picked, R=g r , S=g z-rv Π i=1   a m i   −w     i    and T=({tilde over (g)}Π i=1   b m a+i   −u     i   ) 1/r  are computed and the signature (R, S, T) is outputted. 
     VfSig(sk,  m 1 , . . . , m a+b   ): The signature s is parsed as (R, S, T) and 1 is outputted if the equalities e(R,V)e(S, {tilde over (g)})Π i=1   a e(m i , W i )=e(g,Z) and e(R,T)Π i=1   b e(U i , m a+1 )=e(g, {tilde over (g)}) hold. 
     A commitment may be used for a zero-knowledge proof of knowledge. A protocol proving knowledge of exponents w 1 , . . . , w n  satisfying the formula φ(w 1 , . . . , w n ) may be described as  K w 1 , . . . , w n :φ(w 1 , . . . , w n ). The symbol “ K ” used instead of “∃” indicates that “knowledge” of the exponents rather than just their existence is proven. The formula φ(w 1 , . . . , w n ) consists of conjunctions and disjunctions of “atoms”. An atom expresses group relations, such as   where the g j  are elements of prime order groups and the    j &#39;s are polynomials in the variables w 1 , . . . , w n . 
     A witness for a statement of the form  K w 1 , . . . , w n :φ(w 1 , . . . , w n ) is a tuple (w 1 , . . . , w n ) of integers such that φ(w 1 , . . . , w n , bases) holds. In cases where only the residue class of w i  modulo m is important, we may treat the domain of w i  as    m . 
     The formula φ(w 1 , . . . , w n , bases) is given by a formula that is built up from “atoms” using arbitrary combinations of ANDs and ORs. An atom may express several types of relations among the w i &#39;s: (i) integer relations, such as  =0,  ≧0,  ≡0(mod m), or gcd( , m)=1, where   is an integer polynomial in the variables w 1 , . . . , w n , and m is a positive integer; (ii) group relations, such as Π j=1   k   =1, where g j  ε bases are elements of an abelian group, and the    j &#39;s are integer polynomials in the variables w 1 , . . . , w n . 
     Extended zero-knowledge formulas: A proof system for  k w 1 , . . . , w n :φ(w 1 , . . . , w n ) may be transformed into a proof system for more expressive statements about secret exponents (w i ) i =sexps and secret bases (g i ) i =sbases: K sexps,sbases:φ(sexps, bases ∪sbases). The transformation uses a blinded base g′ i =g i h ρ     i    for every g i . It adds h and all g′ i  to the public bases, ρ i  to the secret sexps, and rewrites   into   for all i, j.
         This proof system supports pairing product equations Π i=1   k e =1 in groups of prime order | | with a bilinear map e: × →   t , by treating the target group as the group of the proof system. For simplicity, it may be focused on the special case of i=j. The embedding for secret bases is unchanged, except for the case in which both bases in a pairing are secret. In the latter case,   needs to be transformed into          

     A proof instance ins may be defined to consist of the set of bases and descriptions of the groups. The proof relation ((sexps, sbases), ins) ε R holds if and only if the formula φ(sexps, bases ∪ sbases) holds. A relation R is called tractable, if such a formula φ and consequently an efficient proof protocol for it exists. 
     According to an example, the revocation computer system receives revocation information and initializes a vector x. To each revocation handle rh i , i.e. to each credential s i , a bit-vector element x[i] of bit length m is assigned by the revocation computer system. Each bit x[i,j] indicates whether the corresponding credential s i  is valid for verifying computer system    j  (x[i,j]=1), i.e. the hardware and/or software functions offered by    j , or revoked (x[i,j]=0). 
     The time is divided into epochs ep, i.e. discrete time intervals, so that the revocation computer system provides user computer devices and verifying computer systems with updated revocation information at the beginning of each epoch, i.e. time interval. The time intervals may be isochronous. The revocation computer system provides each user computer device   with revocation information ri[ep, i] regarding the corresponding credential s i  and verifying computer systems    1 , . . . ,    m  with revocation verification information rvi[ep] regarding all credentials s 1 , . . . , s n . This information allows user computer devices to prove the revocation status of their credentials s i  and verifying computer systems to verify this status. 
     A user computer device    i  employs a credential s i  to compute a presentation token tk for verifying computer system    j  that shows that issuing computer system I certified the value of the attributes (a i,1 , . . . , a i,1 ) signed by s i . 
     To compute a presentation token tk, user computer device    i  also employs the revocation information ri[ep, i] to prove the validity of the corresponding credential s i , by which revocation handle rh i  has been signed, with respect to verifying computer system    j . Verifying computer system    j  employs the revocation verification information rvi[ep] to verify tk. 
     The algorithms for handling revocation statuses of credential run by issuing computer system I, revocation computer system  , user computer devices    1 , . . . ,    n  and verifying computer systems    1 , . . . ,    m  may for example be defined as follows: 
     ISetup(1 k ): On input the security parameter 1 k  a secret key Isk and a public key Ipk are generated and outputted. 
     RSetup(1 k ): On input the security parameter 1 k  revocation parameters par r  are generated and outputted. Furthermore, revocation information ri[ep 0 , i] (iε[1, n]) is generated and outputted. Revocation information ri[ep 0 , i] contains a bit-vector element comprising the revocation status of credential with revocation handle i at starting epoch ep 0  for each function. Revocation status information rvst[ep 0 ] is initialized and outputted, i.e. a vector of with n vector element, each of said elements with a sequence of bits of bit length m. Provisional revocation status information rvst=rvst[ep 0 ] is initialized and outputted as well as revocation verification information rvi[ep 0 ] containing a single value derived from the revocation status information rvst[ep 0 ]. 
     IssueCred(Isk, a i,1 , . . . , a i,n , i): On input of the secret key Isk, the attributes (a i,1 , . . . , a i,l ) and the revocation handle i, a credential s i  is generated and outputted. 
     VfCred (Ipk, a i,1 , . . . , a i,n , i, s i ): On input of the public key Ipk, the attributes (a i,1 , . . . , a i,l ), the revocation handle i, and the credential s i , 1 is outputted, if the credential is valid, and 0 otherwise. 
     UpdateUser (rvst i , rvst): On input of revocation status information rvst i  for revocation handle i, the provisional revocation status information is updated and the updated provisional revocation status information rvst′ outputted. 
     UpdateEpoch (par r , ri[ep t , i], rvi[ep t ], rvst[ep t ], rvst): On inputting the revocation parameters par r , revocation information ri[ep t , i] (iε[1, n]), revocation verification information rvi[ep t ], revocation status information rvst[ep t ], and provisional revocation status information rvst of epoch ep t , updated information for the next epoch ep t+1  is outputted, i.e. ri[ep t+1 , i] (iε[1, n]), rvi[ep t+1 ], rvst[ep t+1 ], and rvst=rvst[ep t+1 ] are outputted. 
     CreatToken(Ipk, par r , a i,1 , . . . a i,n , i, s i , ri[ep t , i],    j ): On input of the public key Ipk, the revocation parameters par r , the attributes (a i,1 , . . . , a i,l ), revocation handle i, credential s i , revocation information ri[ep t , i], and identifier of verifying computer system    j , a presentation token tk for verifying computer system    j  is generated and outputted. 
     VfToken (Ipk, par r , tk, rvi[ep t ],    j ): On inputting the public key Ipk, the revocation parameters par r , the presentation token tk, and the revocation verification information rvi[ep t ], and the identifier of verifying computer system    j , 1 is outputted, if the presentation token tk is valid, and 0 otherwise. 
       FIG. 6  shows a general flow diagram according to embodiments of the present invention. The issuing computer system I, the revocation computer system  , the user computer devices    1 , . . . ,    n  and the verifying computer systems    1 , . . . ,    m  may run the algorithms as follows: 
     The first phase is the setup phase (steps  600 - 603 ): In step  600 , the issuing computer system I executes the setup algorithm (Isk, Ipk)←ISetup(1 k ) and in step  601  sends Ipk to user computer devices    1 , . . . ,    n  and verifying computer systems    1 , . . . ,    m . In step  602  the revocation computer system   executes the algorithm (par r ,  ri[ep 0 , i]   i=1   n , rvi[ep 0 ], rvst[ep 0 ], rvst)←RSetup(1 k ) and in step  603  sends par r  to user computer devices    1 , . . . ,    n  and verifying computer systems    1 , . . . ,    m . 
     The second phase is the issuing phase (steps  604 - 605 ): In step  604 , the issuing computer system I runs s i ←IssueCred(Isk, a i,1 , . . . , a i,n , i) and sends the specific information (a i,1 , . . . , a i,n , i, s i ) assigned to revocation handle i to user computer device    i , to possessing the credential to which i is assigned. In step  605 , user computer device    i  runs b←VfCred (Ipk, a i,1 , . . . , a i,n , i, s i ) and accepts the credential s i , if b=1. 
     The third phase is the revocation phase (steps  606 - 611 ): In step  606 , issuing computer system I (or one of the verifying computer systems    1 , . . .    m .) sends updated revocation information rvst i  about a credential s i  with revocation handle i to the revocation computer system  . In step  607 , the revocation computer system   runs rvst′←UpdateUser(rvst i ,rvst) to obtain updated provisional revocation status information rvst′ based on the updated revocation information rvst i  provided. At the beginning of a new epoch ep t+1 ,   performs step  608  and runs ( ri[ep t+1 , i]   i=1   n , rvi[ep t+1 ], rvst[ep t+1 ],rvst)←UpdateEpoch(par r , ri[ep t , i], rvi[ep t ], rvst[ep t ], rvst). In step  609 , the revocation computer system   sends to each user computer device    i  the corresponding revocation information ri[ep t+1 , i] assigned to revocation handle i and in step  610  the general revocation verification information rvi[ep t+1 ] to all the verifying computer systems    1 , . . . ,    m . 
     The fourth phase is the presentation phase (steps  611 - 613 ): In step  611 , the user computer device    i  runs tk←CreatToken (Ipk, par r , a i,1 , . . . , a i, n , i, s i , ri[ep t , i],    j ) and in step  612  sends the presentation token tk to a verifying computer system V j . Upon receiving the presentation token tk, the verifying computer system V j  in step  613  runs b←VfToken (Ipk, par r , tk, rvi[ep t ],    j ) and accepts the presentation token tk, if b=1. 
     Non-Hiding Commitment 
     In an embodiment of the invention a non-hiding commitment value, i.e. single value commitment, to a vector is applied. A non-hiding single value commitment with update scheme allows to succinctly commit to a vector x=(x[1], . . . , x[n]) ε    n  such that it is possible to compute an opening w to x[i] with the size of w independent of i and n. It is also possible to update the commitment value by replacing the value x[i] by a new value x[i]′. The scheme consists of the following algorithms: 
     Setup (1 k ,  ): On input the security parameter 1 k  and an upper bound   on the size of the vector x, the parameters of the commitment scheme par are generated, which include a description of the message space  . 
     Commit(par, x): On input a vector xε   n , a commitment value com to x is outputted. 
     Prove(par, i, x): Computes a witness value w for x[i]. 
     Verify(par, com, x, i, w): Outputs 1, if w is a valid witness value for x being at position i and 0 otherwise. 
     ComUpd (par, com, j, x, x′): On inputting a commitment value com with value x at position j, outputs a commitment value com′ with value x′ at position j, while the other positions remain unchanged. 
     WitUpd(par, w, i, j, x, x′): On input of a witness value w for position i valid for a commitment value com with value x at position j, a witness value w′ for position i valid for a commitment value com′ with value x′ at position j is outputted. 
     A non-hiding vector commitment scheme should be correct and binding. Correctness requires that for par←Setup(1 k ,  ), x=(x[1], . . . , x[n]) ε   n , com←Commit(par, x), iε[1, n] and w←Prove(par, i, x), the algorithm Verify(par, com, x[i], i, w) outputs 1 with probability 1. 
     The binding property requires that no adversary can output a vector based commitment value com, a position iε[1,  ], two values x and x′ and two respective witness values w and w′ such that Verify accepts both, i.e. for l polynomial in k: 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           par 
                           ← 
                           
                             Setup 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   1 
                                   k 
                                 
                                 , 
                                 ℓ 
                               
                               ) 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           ( 
                           
                             com 
                             , 
                             i 
                             , 
                             x 
                             , 
                             
                               x 
                               ′ 
                             
                             , 
                             w 
                             , 
                             
                               w 
                               ′ 
                             
                           
                           ) 
                         
                         ← 
                         
                           
                             ?? 
                             ⁡ 
                             
                               ( 
                               par 
                               ) 
                             
                           
                           ⁢ 
                           
                             : 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           Verify 
                           ⁡ 
                           
                             ( 
                             
                               par 
                               , 
                               com 
                               , 
                               x 
                               , 
                               i 
                               , 
                               w 
                             
                             ) 
                           
                         
                         = 
                         
                           1 
                           ⩓ 
                         
                       
                     
                   
                   
                     
                       
                         
                           Verify 
                           ⁡ 
                           
                             ( 
                             
                               par 
                               , 
                               com 
                               , 
                               
                                 x 
                                 ′ 
                               
                               , 
                               i 
                               , 
                               
                                 w 
                                 ′ 
                               
                             
                             ) 
                           
                         
                         = 
                         
                           1 
                           ⩓ 
                           
                             x 
                             ≠ 
                             
                               x 
                               ′ 
                             
                           
                           ⩓ 
                           
                             i 
                             ∈ 
                             
                               [ 
                               
                                 1 
                                 , 
                                 ℓ 
                               
                               ] 
                             
                           
                         
                       
                     
                   
                 
                 ] 
               
             
             ≤ 
             
               
                 ε 
                 ⁡ 
                 
                   ( 
                   k 
                   ) 
                 
               
               . 
             
           
         
       
     
     A non-hiding vector commitment scheme may for example be constructed as follows: 
     Setup (1 k ,  ): Groups (p,  ,  ,    t , e, g, {tilde over (g)})← (1 k ) are generated, α←   p  picked and (g 1 , {tilde over (g)} 1 , . . . , g l , {tilde over (g)} l , g l+2 , . . . , g 2l ) computed, where g i =g (α     i     )  and {tilde over (g)} i ={tilde over (g)} (α     i     ) . Parameters par=(p,  ,  ,    t , e, g, {tilde over (g)}, g 1 , {tilde over (g)} 1 , . . . , g l , {tilde over (g)} l , g l+2 , . . . , g 2l ,  =   p ) are outputted. 
     Commit(par, x): Outputs com=Π j=1   n g l+1−j   x[j] =g l   x[1]  . . . g l+1−n   x[n]  with |x|=n≦   
     Prove (par, i, x): Outputs w=Π j=1, j≠i   n g l+1−j+i   x[j]  with |x|=n≦ . 
     Verify (par, com, x, i, w): Outputs 1, if e(com, {tilde over (g)} i )=e(w, {tilde over (g)} i )·e(g 1 , {tilde over (g)} l ) x . 
     ComUpd (par, com, j, x, x′): Outputs the updated commitment value 
     
       
         
           
             
               com 
               ′ 
             
             = 
             
               
                 com 
                 · 
                 
                   
                     g 
                     
                       ℓ 
                       + 
                       1 
                       - 
                       j 
                     
                     
                       x 
                       ′ 
                     
                   
                   
                     g 
                     
                       ℓ 
                       + 
                       1 
                       - 
                       j 
                     
                     
                       
                         x 
                         ′ 
                       
                       - 
                       x 
                     
                   
                 
               
               = 
               
                 com 
                 · 
                 
                   
                     g 
                     
                       ℓ 
                       + 
                       1 
                       - 
                       j 
                     
                     
                       
                         x 
                         ′ 
                       
                       - 
                       x 
                     
                   
                   . 
                 
               
             
           
         
       
     
     WitUpd(par, w, i, j, x, x′): Outputs w, if i=j. Otherwise the updated witness value 
               w   ′     =       w   ·       g     ℓ   +   1   -   j   +   i       x   ′         g     ℓ   +   1   -   j   +   1     x         =     w   ·     g     ℓ   +   1   -   j   +   i         x   ′     -   x                 
is outputted.
 
     This commitment scheme is correct and binding under the l-DHE assumption. Correctness requires: 
     
       
         
           
             
               
                 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           com 
                           , 
                           
                             
                               g 
                               ~ 
                             
                             i 
                           
                         
                         ) 
                       
                     
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           w 
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   1 
                                 
                                 n 
                               
                               ⁢ 
                               
                                 
                                   x 
                                   ⁡ 
                                   
                                     [ 
                                     j 
                                     ] 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     α 
                                     
                                       ℓ 
                                       + 
                                       1 
                                       - 
                                       j 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           , 
                           
                             
                               g 
                               ~ 
                             
                             
                               ( 
                               
                                 α 
                                 i 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 ∑ 
                                 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                   , 
                                   
                                     j 
                                     ≠ 
                                     i 
                                   
                                 
                                 n 
                               
                               ⁢ 
                               
                                 
                                   x 
                                   ⁡ 
                                   
                                     [ 
                                     j 
                                     ] 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     α 
                                     
                                       ℓ 
                                       + 
                                       1 
                                       - 
                                       j 
                                       + 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   1 
                                 
                                 n 
                               
                               ⁢ 
                               
                                 
                                   x 
                                   ⁡ 
                                   
                                     [ 
                                     j 
                                     ] 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     α 
                                     
                                       ℓ 
                                       + 
                                       1 
                                       - 
                                       j 
                                       + 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 ∑ 
                                 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                   , 
                                   
                                     j 
                                     ≠ 
                                     i 
                                   
                                 
                                 n 
                               
                               ⁢ 
                               
                                 
                                   x 
                                   ⁡ 
                                   
                                     [ 
                                     j 
                                     ] 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     α 
                                     
                                       ℓ 
                                       + 
                                       1 
                                       - 
                                       j 
                                       + 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           g 
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                     
                       
                         x 
                         ⁡ 
                         
                           [ 
                           i 
                           ] 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           α 
                           
                             ℓ 
                             + 
                             1 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             1 
                           
                           , 
                           
                             
                               g 
                               ~ 
                             
                             ℓ 
                           
                         
                         ) 
                       
                     
                     
                       x 
                       ⁡ 
                       
                         [ 
                         i 
                         ] 
                       
                     
                   
                 
               
             
           
         
       
     
     This vector based commitment scheme also fulfills the binding property under the  -DHE assumption. Given an adversary   that breaks the binding property with non-negligible probability v, an algorithm   may be constructed that breaks the  -DHE assumption with non-negligible probability v. First,   receives an instance (e,  ,  ,    t , e, g, {tilde over (g)}, g 1 , {tilde over (g)} 1 , . . . , g l , {tilde over (g)} l , g l+2 , . . . , g 2l ) of the  -DHE assumption. Algorithm   sets par=(e,  ,  ,    t , e, g, {tilde over (g)}, g 1 , {tilde over (g)} 1 , . . . , g l , {tilde over (g)} l , g l+2 , . . . , g 2l ) and sends par to adversary  . Adversary   returns (com, i, x, x′, w, w′) such that Verify(par, com, x, i, w)=1, Verify(par, com, x′, i, w′)=1, and x≠x′. Algorithm   computes g l+1  as follows:
 
 e ( w,{tilde over (g)} ) e ( g   1   ,{tilde over (g)}   l ) x   =e ( w′,{tilde over (g)} ) e ( g   1   ,{tilde over (g)}   l ) x′ 
 
 e ( w/w′,{tilde over (g)} )= e ( g   1   ,{tilde over (g)}   l ) x′−x  
 
 e (( w/w ′) 1/(x′−x)   ,{tilde over (g)} )= e ( g   1   ,{tilde over (g)}   l )
 
 e (( w/w ′) 1/(x′−x)   ,{tilde over (g)} )= e ( g   l+1   ,{tilde over (g)}   l )
 
     The last equation implies that g l+1 =(w/w′) 1/(x′−x) . Therefore, algorithm  returns (w/w′) 1/(x′−x)  as a solution for the l-DHE problem. 
     For a commitment value com to a vector of length n, a ZKPK of a commitment opening  K i, w: Verify(par, com, x, i, w)=1  iε[i, n] may be computed. This involves proving knowledge of a position i and a witness value w such that the verification equation (com, {tilde over (g)} i )=e(w, {tilde over (g)})·e(g 1 , {tilde over (g)} l ) x  holds. Additionally, it involves proving that com is opened to a correct position iε[i, n]. 
     As a is secret, the relation between {tilde over (g)} i ={tilde over (g)} (α     i     )  and i are not efficiently provable. For this reason a structure preserving signature σ i  to sign the triple (g id , g i , {tilde over (g)} i ) may be employed. The integer id is an identifier of the vector based commitment value, which is needed in case the revocation mechanism employs more than one commitment values. 
     A prover proves possession of a signature on (g id , g i , {tilde over (g)} i ) and of a witness value w such that (com, {tilde over (g)} i )=e(w, {tilde over (g)})·e(g 1 , {tilde over (g)} l ) x  holds. The prover proves equality between {tilde over (g)} i  in the signature σ i  and in the verification equation.
 
 K   g   i   ,{tilde over (g)}   i   ,w,R,S,T:  
 
 e ( R,V ) e ( S,{tilde over (g)} ) e ( g   id   ,W   1 ) e ( g   i   ,W   2 ) e ( g,Z ) −1 =1  
 
 e ( R,T ) e ( U   1   ,{tilde over (g)}   i ) e ( g,{tilde over (g)} ) −1 =1  
 
 e (com, {tilde over (g)}   i ) e ( w,{tilde over (g)}   −1 )= e ( g   1   ,{tilde over (g)}   l ) x  
 
     The first two of the above equations for (R, S, T) prove possession of a signature (R, S, T) on (g id , g i , {tilde over (g)} i ), while the last equation proves knowledge of the witness value w. Note that, in this proof, the message g id  and the committed value x are revealed. 
     With n being the number of user computer devices that possessing a credential of a certain type and m being the number of revocation lists related to that credential type, the revocation computer system   sets a vector x=(x[1], . . . , x[n]). The component x[i] consists of m bits and is associated to revocation handle iε[1, n] and thus to user computer device    i  possessing credential s i . By x[i, j] the jth bit (j ε [1, m]) of the component x[i]. x[i, j]=1 denotes that the credential with revocation handle i is valid according to revocation list j, while x[i, j]=0 indicates that the credential is revoked. Therefore, x[i]=0 denotes that the credential is revoked in all the revocation lists. 
     The issuing computer system I employs a signature scheme (IKeyGen, Sign, VfSig) and the revocation computer system   employs a signature scheme (RKeyGen, RSign, RVfSig). 
     In case of this exemplary non-hiding commitment scheme, algorithms for handling revocation statuses of credential may be instantiated as follows: 
     ISetup(1 k ): On input of the security parameter 1 k , (Isk, Ipk)←KeyGen(1 k ) is run and a secret key Isk and a public key Ipk outputted. 
     RSetup(1 k ): On input of the security parameter 1 k , par←RSetup(1 k , l) and (Rsk, Rpk)←RKeyGen(1 k ) are run. A vector x=(0, . . . , 0) of size n is initialized. com←Commit(par,x) is run and, for i=1 to n, w i ←Prove(par, i, x) and σ i ←RSign(Rsk,  g id , g i , {tilde over (g)} i   ) are run. Parameters par r =(par, Rpk), revocation information ri[ep 0 , i]=(x[i], com, w i , σ i ) (iε[1, n]), revocation verification information rvi[ep 0 ]=com, revocation status information rvst[ep 0 ]=x and provisional revocation status information rvst=rvst[ep 0 ]=x are outputted. 
     IssueCred(Isk, a i,1 , . . . , a i,n , i): On inputting the secret key Isk, the attributes (a i,1 , . . . , a i,n ), and the revocation handle i, s i ←Sign(Isk,  a i,1 , . . . , a i,n , i ) is run and a credential s i  outputted. 
     VfCred(Ipk, a i,1 , . . . , a i,n , i, s i ): On input of the public key Ipk, the attributes (a i,1 , . . . , a i,n ), the revocation handle i, and the credential s i , it outputs b←VfSig(Ipk, s i , m). 
     UpdateUser(rvst i , rvst): On input revocation status information rvst i  for revocation handle i and the provisional revocation information rvst=(x[1], . . . , x[n]), rvst i  is parsed as the component x′[i] and updated provisional revocation status information rvst′=(x[1], . . . , x[i−1], x′[i], x[i+1], . . . , x[n]) is outputted. 
     UpdateEpoch(par r , ri[ep t , i], rvi[ep t ], rvst[ep t ], rvst): On input of the revocation parameters par r =(par, Rpk), revocation information ri[ep t , i]=(x[i], com, w, σ i ) (iε[1, n]), revocation verification information rvi[ep t ]=com, revocation status information rvst[ep t ]=x, and provisional revocation status information rvst=x′, for all j such that x[j]≠x′[j], com′←ComUpd(par, com, j, x[j], x′[j]) is run and for all iε[1,n], if i≠ j, w′ i ←WitUpd(par, w i , i, j, x[j], x′[j]) is run. Revocation information ri[ep t+1 , i]=(x′[i], com′, w′ i , σ i ) (iε[1, n]), revocation verification information rvi[ep t+1 ]=com′, revocation status information rvst[ep t+1 ]=x′ and provisional revocation status information rvst=x′ are outputted. 
     CreatToken(Ipk, par r , a i,1 , . . . , a i,n , i, s i , ri[ep t , i],    j ): On input of the public key Ipk, the revocation parameters par r , the attributes (a i,1 , . . . , a i,n ), the revocation handle i, the credential s i , the revocation information ri[ep t , i]=(x[i], com, w i , σ i ) (iε[1, n]), and the identifier of verifying computer system    j , it computes the following zero-knowledge proof of knowledge:
 
 K   s   i   ,a   1   , . . . , a   l   ,i,w:  
 
 Vf Sig( Ipk,s   i   ,     a   i   , . . . , a   i   ,i   )=1 
 
Verify(par,com, x [ i ] ,i,w   i )=1
 
     Instantiated with the above identified building-blocks, the proof may be as follows:
 
 K   s   i   ,a   1   , . . . , a   l   ,i,{tilde over (g)}   i   ,w   i   ,R,S,T:  
 
 Vf Sig( Ipk,s   i   ,     a   i   , . . . , a   l   ,i   )=1 
 
 e ( R,V ) e ( S,{tilde over (g)} ) e ( g,W   1 ) id   e ( g,W   2 ) i   e ( g,Z ) −1 =1 
 
 e ( R,T ) e ( U   1   ,{tilde over (g)}   i ) e ( g,{tilde over (g)} ) −1 =1 
 
 e (com, {tilde over (g)}   i ) −1   e ( w   i   ,{tilde over (g)} ) e ( g   1   ,{tilde over (g)}   l ) x[i] =1
 
     A presentation token tk is outputted, which consists of the proof and the revocation information x[i]. 
     VfToken (Ipk, par r , tk, rvi[ep t ],    j ): On input the public key Ipk, the revocation parameters par r , the presentation token tk, and the revocation verification information rvi[ep t ], and the identifier of verifying computer system    j , verify the proof in the presentation token tk and output 1, if it is valid, and 0 otherwise. 
     Hiding Commitment 
     A hiding vector based commitment scheme according to a further embodiment may consist of the following algorithms: 
     Setup(1 k ,  ): On input of the security parameter 1 k  and an upper bound   on the size of the vector, parameters of the commitment scheme par are generated, which include a description of the message space   and a description of the randomness space  . 
     Commit(par, x, r): On input of a vector xε   n  (n≦ ) and rε  a commitment value com to x is outputted. 
     Prove (par, i, x, r): Computes a witness value w for x[i]. 
     Verify(par, com, x, i, w): Outputs 1, if w is a valid witness value for x being at position i, and 0 otherwise. 
     ComUpd(par, com, j, x, r, x′, r′): On input of a commitment value com with value x at position j and randomness r, a commitment value com′ with value x′ at position j and randomness r′ is outputted, while the other positions remain unchanged. 
     WitUpd(par, w, j, x, r, x′, r′): On input of a witness value w for position i valid for a commitment value com with value x at position j and randomness r, a witness value w′ for position i valid for a commitment value com′ with value x′ at position j and randomness r′ is outputted. 
     A vector based commitment scheme is required to be correct, hiding, and binding. 
     Correctness requires that for par←Setup(1 k ,  ), x=(x[1], . . . , x[n])ε   n , r← , com←Commit(par, x, r), iε[1,n] and w i ←Prove(par, i, x, r), the algorithm Verify (par, com, x[i], i, w) outputs 1 with probability 1. 
     The hiding property requires that any PPT adversary   has negligible advantage in the following game. Adversary   chooses a vector and a position i′ and sends them to a challenger. The challenger either commits to the vector sent by adversary   or to a vector where the i′th component being replaced by a random message. The challenger sends the commitment value to adversary   along with witness values for all the vector components except of i′. Adversary   guesses which vector has been used to compute the commitment value. More formally, for   polynomial in k: 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           par 
                           ← 
                           
                             Setup 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   1 
                                   k 
                                 
                                 , 
                                 ℓ 
                               
                               ) 
                             
                           
                         
                         ; 
                         
                           
                             ( 
                             
                               
                                 i 
                                 ′ 
                               
                               , 
                               
                                 x 
                                 0 
                               
                               , 
                               st 
                             
                             ) 
                           
                           ← 
                           
                             ?? 
                             ⁡ 
                             
                               ( 
                               par 
                               ) 
                             
                           
                         
                         ; 
                         
                           
                             x 
                             ′ 
                           
                           ← 
                           ℳ 
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           
                             x 
                             1 
                           
                           = 
                           
                             ( 
                             
                               
                                 
                                   x 
                                   0 
                                 
                                 ⁡ 
                                 
                                   [ 
                                   1 
                                   ] 
                                 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 
                                   x 
                                   0 
                                 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     i 
                                     - 
                                     1 
                                   
                                   ] 
                                 
                               
                               , 
                               
                                 x 
                                 ′ 
                               
                               , 
                               
                                 
                                   x 
                                   0 
                                 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                   ] 
                                 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 
                                   x 
                                   0 
                                 
                                 ⁡ 
                                 
                                   [ 
                                   n 
                                   ] 
                                 
                               
                             
                             ) 
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           b 
                           ← 
                           
                             { 
                             
                               0 
                               , 
                               1 
                             
                             } 
                           
                         
                         ; 
                         
                           r 
                           ← 
                           ℛ 
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           com 
                           ← 
                           
                             Commit 
                             ⁡ 
                             
                               ( 
                               
                                 par 
                                 , 
                                 
                                   x 
                                   b 
                                 
                                 , 
                                 r 
                               
                               ) 
                             
                           
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           
                             { 
                             
                               
                                 w 
                                 i 
                               
                               ← 
                               
                                 Prove 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     par 
                                     , 
                                     i 
                                     , 
                                     
                                       x 
                                       b 
                                     
                                     , 
                                     r 
                                   
                                   ) 
                                 
                               
                             
                             } 
                           
                           
                             
                               i 
                               = 
                               1 
                             
                             , 
                             
                               i 
                               ≠ 
                               
                                 i 
                                 ′ 
                               
                             
                           
                           n 
                         
                         ; 
                       
                     
                   
                   
                     
                       
                         
                           b 
                           ′ 
                         
                         ← 
                         
                           
                             ?? 
                             ⁡ 
                             
                               ( 
                               
                                 st 
                                 , 
                                 com 
                                 , 
                                 
                                   
                                     { 
                                     
                                       w 
                                       i 
                                     
                                     } 
                                   
                                   
                                     
                                       i 
                                       = 
                                       1 
                                     
                                     , 
                                     
                                       1 
                                       ≠ 
                                       
                                         i 
                                         ′ 
                                       
                                     
                                   
                                   n 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             : 
                           
                         
                       
                     
                   
                   
                     
                       
                         b 
                         = 
                         
                           b 
                           ′ 
                         
                       
                     
                   
                 
                 ] 
               
             
             = 
             
               
                 1 
                 2 
               
               + 
               
                 ε 
                 ⁡ 
                 
                   ( 
                   k 
                   ) 
                 
               
             
           
         
       
     
     The binding property may be defined according to the definition given above. 
     A hiding vector commitment scheme may for example be constructed as follows: 
     Setup (1 k ,  ): Groups (p,  ,  ,    t , e, g, {tilde over (g)})← (1 k ) are generated, α←   p  is picked and (g 1 , {tilde over (g)} 1 , . . . , g l , {tilde over (g)} l , g l+2 , . . . , g 2l ) computed, where g i =g (α     i     )  and {tilde over (g)} i ={tilde over (g)} (α     i     ) . Parameters par=(p,  ,  ,    t , e, g, {tilde over (g)}, g 1 , {tilde over (g)} 1 , . . . , g l , {tilde over (g)} l , g l+2 , . . . , g 2l ,  , =   p ,  , =   p ) are outputted. 
     Commit(par, x, r): Outputs com=g r ·Π j=1   n g l+1−j   x[j] =g r ·g l   x[1]  . . . g l+1−n   x[n]  with |x|=n≦ . 
     Prove(par, i, x, r): Outputs w=g r ·Π j=1, j≠i   n g l+1−j+i   x[j]  with |x|=n≦ . 
     Verify(par, com, x, i, w): Outputs 1, if e(com, {tilde over (g)} i )=e(w, {tilde over (g)})·e(g 1 , {tilde over (g)} l ) x , and else 0. 
     ComUpd(par, com, j, x, r, x′, r′): Outputs the updated commitment value 
     
       
         
           
             
               com 
               ′ 
             
             = 
             
               
                 com 
                 · 
                 
                   
                     
                       g 
                       
                         r 
                         ′ 
                       
                     
                     · 
                     
                       g 
                       
                         ℓ 
                         + 
                         1 
                         - 
                         j 
                       
                       
                         x 
                         ′ 
                       
                     
                   
                   
                     
                       g 
                       r 
                     
                     · 
                     
                       g 
                       
                         ℓ 
                         + 
                         1 
                         - 
                         j 
                       
                       x 
                     
                   
                 
               
               = 
               
                 com 
                 · 
                 
                   g 
                   
                     
                       r 
                       ′ 
                     
                     - 
                     r 
                   
                 
                 · 
                 
                   
                     g 
                     
                       ℓ 
                       + 
                       1 
                       - 
                       j 
                     
                     
                       
                         x 
                         ′ 
                       
                       - 
                       x 
                     
                   
                   . 
                 
               
             
           
         
       
     
     WitUpd (par, w, i, j, x, r, x′, r′): Outputs w, if i=j, otherwise the updated witness value 
               w   ′     =       w   ·         g     r   ′       ·     g     ℓ   +   1   -   j   +   i       x   ′             g   r     ·     g     ℓ   +   1   -   j   +   i     x           =     w   ·     g       r   ′     -   r       ·     g     ℓ   +   1   -   j   +   i         x   ′     -   x                 
is outputted.
 
     This commitment scheme is correct, hiding, and binding under the l-DHE assumption. Correctness may be proven as follows: 
     
       
         
           
             
               
                 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           com 
                           , 
                           
                             
                               g 
                               ~ 
                             
                             i 
                           
                         
                         ) 
                       
                     
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           w 
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               r 
                               + 
                               
                                 
                                   ∑ 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                   n 
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     ⁡ 
                                     
                                       [ 
                                       j 
                                       ] 
                                     
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       α 
                                       
                                         ℓ 
                                         + 
                                         1 
                                         - 
                                         j 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           , 
                           
                             
                               g 
                               ~ 
                             
                             
                               ( 
                               
                                 α 
                                 i 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 r 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     α 
                                     i 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     
                                       j 
                                       = 
                                       1 
                                     
                                     , 
                                     
                                       j 
                                       ≠ 
                                       i 
                                     
                                   
                                   n 
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     ⁡ 
                                     
                                       [ 
                                       j 
                                       ] 
                                     
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       α 
                                       
                                         ℓ 
                                         + 
                                         1 
                                         - 
                                         j 
                                         + 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 r 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     α 
                                     i 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                   n 
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     ⁡ 
                                     
                                       [ 
                                       j 
                                       ] 
                                     
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       α 
                                       
                                         ℓ 
                                         + 
                                         1 
                                         - 
                                         j 
                                         + 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             
                               
                                 r 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     α 
                                     i 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     
                                       j 
                                       = 
                                       1 
                                     
                                     , 
                                     
                                       j 
                                       ≠ 
                                       i 
                                     
                                   
                                   n 
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     ⁡ 
                                     
                                       [ 
                                       j 
                                       ] 
                                     
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       α 
                                       
                                         ℓ 
                                         + 
                                         1 
                                         - 
                                         j 
                                         + 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           g 
                           , 
                           
                             g 
                             ~ 
                           
                         
                         ) 
                       
                     
                     
                       
                         x 
                         ⁡ 
                         
                           [ 
                           i 
                           ] 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           α 
                           
                             ℓ 
                             + 
                             1 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       e 
                       ⁡ 
                       
                         ( 
                         
                           
                             g 
                             1 
                           
                           , 
                           
                             
                               g 
                               ~ 
                             
                             ℓ 
                           
                         
                         ) 
                       
                     
                     
                       x 
                       ⁡ 
                       
                         [ 
                         i 
                         ] 
                       
                     
                   
                 
               
             
           
         
       
     
     This vector based commitment scheme is further a hiding scheme. The proof of the binding property follows the proof outlined above. 
     A ZKPK of a commitment opening  K x, i, w: Verify(par, com, x, i, w)=1  iε[i, n] is computed. Unlike before in case of the exemplary non-hiding scheme, in this proof the committed value x is hidden. A proof similar to the one described before may be employed. The only difference is that x is not revealed to the verifying computer system.
 
 K   x,g   i   ,{tilde over (g)}   i   ,w,R,S,T:  
 
 e ( R,V ) e ( S,{tilde over (g)} ) e ( g   id   ,W   1 ) e ( g   i   ,W   2 ) e ( g,Z ) −1 =1 
 
 e ( R,T ) e ( U   1   ,{tilde over (g)}   i ) e ( g,{tilde over (g)} ) −1 =1 
 
 e (com, {tilde over (g)}   i ) e ( w,{tilde over (g)}   −1 ) e ( g   1   −1   ,{tilde over (g)}   l ) x =1
 
     In case of this exemplary hiding commitment scheme, algorithms for handling revocation statuses of credential may be instantiated as follows: 
     ISetup(1 k ): On input of the security parameter 1 k , (Isk, Ipk)←IKeyGen(1 k ) run and outputted a secret key Isk and a public key Ipk. 
     RSetup(1 k ): On input of the security parameter 1 k , par←RSetup(1 k ,  ) and (Rsk, Rpk)←RKeyGen (1 k ) are run. A vector x=(0, . . . , 0) of size n is initialized. r←  is picked. com←Commit(par, x, r) is run and, for i=1 to n, w i ←Prove(par, i, x, r) and σ i ←RSign(Rsk,  g id , g i , {tilde over (g)} i   ) are run. Parameters par r =(par, Rpk), revocation information ri[ep 0 , i]=(x[i], com, w i , σ i ) (iε[1, n]), revocation verification information rvi[ep 0 ]=com, revocation status information rvst[ep 0 ]=(r, x) and provisional revocation status information rvst=rvst[ep 0 ]=x are outputted. 
     IssueCred(Isk, a i,1 , . . . , a i,n , i): On inputting the secret key Isk, the attributes (a i,1 , . . . , a i,n ), and the revocation handle i, s i ←Sign(Isk,  a i,1 , . . . , a i,n , i ) is run and a credential s i  outputted. 
     VfCred(Ipk, a i,1 , . . . , a i,n , i, s i ): On input of the public key Ipk, the attributes (a i,1 , . . . , a i,n ), the revocation handle i, and the credential s i , it outputs b←VfSig(Ipk, s i , m). 
     UpdateUser(rvst i , rvst): On input of revocation status information rvst i  for revocation handle i and the provisional revocation information rvst=(x[1], . . . , x[n]), rvst i  is parsed as the component x′[I] and updated provisional revocation status information rvst′=(x[1], . . . , x[i−1], x′[i], x[i+1], . . . , x[n]) is outputted. 
     UpdateEpoch(par r , ri[ep t , i], rvi[ep t ], rvst[ep t ], rvst): The revocation parameters par r =(par, Rpk), revocation information ri[ep t , i]=(x[i], com, w, σ i ) (iε[1, n]), revocation verification information rvi[ep t ]=com, revocation status information rvst[ep t ]=(r, x), provisional revocation status information rvst=x′ are inputted and r′←  is picked. For all j such that x[j]≠x′[j], com′←ComUpd(par, com, j, x[j], r, x′[j], r′) is run and for all iε[1, n], if i≠j, w′ i ←WitUpd(par, w, i, j, x[j], r, x′[j], r′) is run. Revocation information ri[ep t+1 , i]=(x′[i], com′, w′ i , σ i ) (iε[1, n]), revocation verification information rvi[ep t+1 ]=com′, revocation status information rvst[ep t+1 ]=(r′, x′) and provisional revocation status information rvst=x′ is outputted. 
     CreatToken(Ipk, par r , a i,1 , . . . , a i,n , i, s i , ri[ep t , i],    j ): On input of the public key Ipk, the revocation parameters par r , the attributes (a i,1 , . . . , a i,n ), the revocation handle i, the credential s i , the revocation information ri[ep t ,i]=(x[i], com, w i , σ i ) (iε[1, n]), and the identifier of verifying computer system    j , it computes a commitment (com, open)←Com(par c , x[i]), a witness wit←Prove(par c , com, x[i], open) and the following zero-knowledge proof of knowledge:
 
 K   x [ i ], x [i,1 . . .  j− 1], x [ i,j+ 1 . . .  m ],s i   ,a   1   , . . . , a   l   ,i,w   i :
 
 Vf Sig( pk,s   i   ,     a   i   , . . . , a   l   ,i   )=1  
 
Verify(par,com, x [ i ], i,w )=1
 
 x [ i ]= x [ i,j+ 1 . . .  m ] ∥ 1∥ x [ i, 1 . . .  j− 1] 
 
 x [ i,j+ 1 . . .  m ]ε[0,2 m−j+1 ]   x [i,1 . . .  j− 1]ε[0,2 j−1 ]
 
     Instantiated with the above identified building-blocks, the proof may be as follows:
 
 K   x [ i ], x [ i, 1 . . .  j− 1], x [ i,j+ 1 . . .  m ], s   i   ,a   1   , . . . ,a   l   ,i,{tilde over (g)}   i   ,w   i   ,R,S,T ,wit:
 
 Vf Sig( pk,s   i   ,     a   i   , . . . , a   l   ,i   )=1 
 
 e ( R,V ) e ( S,{tilde over (g)} ) g ( g,W   1 ) id   e ( g,W   2 ) i   e ( g,Z ) −1 =1 
 
 e ( R,T ) e ( U   1   ,{tilde over (g)}   i ) e ( g,{tilde over (g)} ) −1 =1 
 
 e (com, {tilde over (g)}   i ) −1   e ( w   i   ,{tilde over (g)} ) e ( g   1   ,{tilde over (g)}   l ) x[i] =1 
 
1=VfCom(par c ,com, x [ i ] ,i ,wit) 
 
com=( g   2     j+1   ) x[i,j+1 . . . m]   g   2     j   g x[i,1 . . . j−1]   h   wit   
 
 x [ i,j+ 1 . . .  m ]ε[0,2 m−j+1 ]   x [ i, 1 . . .  j− 1]ε[0,2 j−1 ]
 
     A presentation token tk is outputted, which consists of the proof and the revocation information x[i]. 
     VfToken (Ipk, par r , tk, rvi[ep t ],    j ): On input of the public key Ipk, the revocation parameters par r , the presentation token tk, and the revocation verification information rvi[ep t ], and the identifier of verifying computer system    j , verify the proof in the presentation token tk and output 1 if is valid and 0 otherwise. 
     The interaction between issuing computer system, user computer device, verifying computer system and revocation computer system is the same as described before for the other preferred embodiment, except for the computation of the presentation token tk. 
     To compute a presentation token, the user computer device computes a zero-knowledge proof of knowledge of a credential cr assigned to the user computer device and of the signature s i , and proves that the revocation handle i in the credential cr equals the one in signature s i . The user computer device also proves possession of a witness value w i  such that the verification equation e(com, {tilde over (g)} i ) −1  e(w i , {tilde over (g)})e(g 1 , {tilde over (g)} l ) x[i] =1 holds. Finally, the user computer device proves that x[i,j]=1. 
     For a revocation handle i assigned to the user computer device    i  having a credential cr on attributes a 1 , . . . , a l  and revocation handle i. The proof works as follows: 
     In this case, to prove that x[i,j]=1, the user computer device computes a commitment value com to x[i] with opening open, proves that x[i]=x[i, j+1 . . . m]∥1∥x[i, 1 . . . j−1], where ∥ denotes concatenation and proves that x[i, j+1 . . . m] and x[i, 1 . . . j−1] lie in the correct intervals.