Minimal disclosure credential verification and revocation

The subject disclosure is directed towards credential verification for accessing a service provider. A user may prove to the service provider the validity of the credential by communicating a non-revocation component that is based upon a prime-order cryptographic group without a bilinear pairing. In order to authenticate the user, a verification mechanism within an identity management system applies private cryptographic data, including a verifier-designated private key to the non-revocation component, which proves that the user's identity and therefore, the credential is not revoked. The presentation proof includes a hash value that is computed using the credential's commitment and the prime-order cryptographic group. By verifying that the hash value was computed using that commitment, the verification mechanism validates the credential and permits access to the service provider.

BACKGROUND

Organizations are increasingly looking to securely identify users who access and utilize their services and resources, both on the Internet and offline, while keeping these users' information private from everyone else. These user authentication and data sharing needs are driven by cost and efficiency considerations, by new business models that leverage personal information, and by the explosive rise of phishing, identity theft, and other security threats. Conventional mechanisms for user authentication and data sharing, such as plastic cards and paper certificates, are costly, vulnerable to counterfeiting, and problematic for online use.

As a result, there is a rapidly growing interest in mechanisms (e.g., X.509 certificates) that can be implemented in software and/or hardware and employed to secure monetary or financial transactions over the Internet. However, these mechanisms are limited because, for example, they cannot be used without disclosing at least some information associated with the user. During a verification procedure, in order to determine whether a credential is valid, the user provides at least some identity data in order to be authenticated. In some cases, an issuer may want to stop a particular user from using the credential that has already been issued, such as when the user may be no longer qualified to use previously issued credentials, the attributes contained therein have become temporarily or permanently invalid, or the user violated policies associated with a service provider. For users whose credentials were not revoked, therefore, proving validity cannot be accomplished without disclosing private and/or confidential information in the form of one or more attributes. This is because the attributes themselves are used to keep track of revoked credentials.

SUMMARY

Briefly, various aspects of the subject matter described herein are directed towards proving a minimal disclosure credential's validity/non-revocation without disclosing identifying information about the credential and/or the credential's user(s). In one aspect, a non-revocation component, which may be herein referred to as a verifiable signature or presentation proof, validates the credential by verifying that some entity/authority has not revoked that credential. These credentials may be herein referred to by many terms, such as minimal disclosure credentials, security tokens, privacy protecting tokens, anonymous credentials and/or the like. As described herein, minimal disclosure credential-based identity management systems allow the user to prove the credential is not revoked without revealing any private information, such as the user's identity.

In one aspect, the credential includes an undisclosed attribute embedded therein that corresponds to the user's identity. By applying a verifier-designated private key to a non-revocation proof corresponding to this undisclosed attribute, a verifier component within an identity management system determines whether or not the non-revocation proof was generated from an accurate and an up to date accumulator representing revoked credentials of a blacklist or valid credentials of a whitelist. In another aspect, a verifier-generated challenge is signed by the user with the credential's private key and returned to the verifier for verification. In yet another aspect, a revocation authority updates the accumulator for such systems since disputes, mistakes, identity changes, intrusions and/or the like may render any credential invalid before its expiration.

In one aspect, an identity management system implements credential verification/revocation as part of a cloud-based service, infrastructure, and/or platform. In one aspect, the identity management system provides issuance, verification and/or revocation related services involving accumulators. In one aspect, if the accumulator is generated using the credential's undisclosed attribute information (e.g., a unique user identifier) and private cryptographic data, non-membership or membership in the blacklist or the whitelist may be determined using that private cryptographic data instead of the attribute's value. In one aspect, the private cryptographic data enables credential authentication while allowing the user to remain anonymous as described herein.

DETAILED DESCRIPTION

Various aspects of the technology described herein are generally directed towards minimal disclosure credential verification/revocation as facilitated by components of an identity management system and/or other hardware/software mechanisms. As described herein, one example component herein referred to as an issuer issues credentials that encode attribute data and provides other data for the purpose of authenticating the user when executing online transactions. Another example component includes a credential verification mechanism, or a verifier, configured to apply various cryptographic data to a non-revocation component (e.g., a verifiable signature or presentation proof) that is configured to validate a given minimal disclosure credential. In one aspect, the minimal disclosure credential is based upon a cryptographic scheme configured to allow a user to access service providers and/or initiate online transactions while remaining anonymous and untraceable by issuers and verifiers.

The cryptographic scheme may employ various cryptographic data, including a verifier-designated cryptographic key, such as a private key, which may be generated at random from a prime-order cryptographic group construction, such as a prime-order multiplicative cyclic subgroup of integers, or another construction, such as an elliptical curve group. Such a construction may include a standardized cryptographic group construction in accordance with the Diffie-Hellman assumption. Standardized cryptographic groups generally refer to group parameters generated and set by standardized mechanisms (e.g., Federal Information Processing Standard (FIPS) 186-3 and the American National Standards Institute (ANSI) X9.62), which may be used to issue credentials. To illustrate by way of example, the National Institute of Standards and Technology (NIST) provides example embodiments for a number of standardized cryptographic groups. Alternatively, the cryptographic data may include a verifier-generated challenge value that also is an element of a prime-order cryptographic group construction, including a prime-order additive subgroup of integers. This construction may be built without anything that could be considered a bilinear pairing between subgroups of integers and instead, may be based upon a discrete logarithmic group.

In addition to issuance and verification, the identity management system includes a revocation authority that computes and makes available an accumulator representing at least one revoked user identifier (e.g., a blacklist) or at least one valid user identifier (e.g., a whitelist) according to one or more example implementations. The accumulator generally refers to a value based upon a prime-order subgroup construction that may be computed for a designated verifier who, on behalf of the service provider, uses private cryptographic data, such as the verifier-designated private cryptographic key described herein, to validate the credential's non-revocation status. After selecting an undisclosed attribute for accumulation, the revocation authority may use the verifier-designated cryptographic key to compute the accumulator and a witness for that attribute, which may be herein referred to as a revocation attribute, whose membership or non-membership in the accumulator refers to that credential's revoked or non-revoked status, respectively.

In one example implementation, on behalf of a user, a third party identity provider generates a unique user identifier for the identity management system to use when issuing and verifying that user's credential's non-revocation status. Note, the identity management system may know the unique user identifier, but may not know any other data identifying the user, such as the user's name. Accordingly, a user computing device may initiate transactions with service providers while remaining anonymous or only disclosing a negligible amount of information, by using a credential that encodes the unique user identifier as a signed undisclosed attribute. A component known as a prover running within the user computing device generates a non-revocation component, which comprises at least a presentation proof, for verifying that the unique user identifier is legitimate and therefore, the credential is valid and not revoked. By applying the verifier-designated cryptographic key or the verifier-generated challenge to the presentation proof, the verifier determines whether the credential has been revoked.

In addition to proving non-revocation via the verifier-designated cryptographic key or the verifier-generated challenge, the presentation proof serves a number of security purposes, such as proving integrity and source authenticity of user-disclosed attributes associated with the presented credential, and establishes that the user owns a private key for presenting/signing the attributes and the transaction related data. One example implementation may utilize, in part, the credential's commitment to generate a hash value for comparison with the presentation proof.

Hence, the presentation proof may also be referred to as a designated-verifiable signature, which generally defines a digital signature that is specifically generated for a user and can only be verified with a secret. The verifiable signature allows digital signature generation for a specific target verifier rather than anyone.

It should be understood that any of the examples herein are non-limiting. As such, the present invention is not limited to any particular embodiments, aspects, concepts, structures, functionalities or examples described herein. Rather, any of the embodiments, aspects, concepts, structures, functionalities or examples described herein are non-limiting, and the present invention may be used various ways that provide benefits and advantages in computing and computer security in general.

FIG. 1is a block diagram illustrating an example identity management system according to one or more example implementations. One example component of the identity management system includes a prover102configured to obtain secure minimal disclosure credentials with an issuer104on behalf of a user and then, initiate verification requests directed to a verifier106for some service provider associated with that user. The issuer104generally refers to an authoritative source of cryptographic information, including public/private cryptographic keys and secure credentials, for user computers being managed by the identity management system. The prover102running on an example user computer provides the issuer104with various data that, once authenticated, is encoded and returned as secure attribute data embedded within a secure minimal disclosure credential108. For the sake of clarity, the minimal disclosure credential108may be herein referred to as the credential108. The minimal disclosure credential108may be stored within a device (e.g., a smartcard, a mobile phone, or an online server).

The verifier106generally refers to a trusted hardware/software mechanism running within a computing device that provides various services. The verifier106may use a variety of mechanisms to perform the credential verification and revocation. As one example, the verifier106processes a non-revocation component110from the prover102that is configured to validate the credential108and/or any associated transaction.

The credential108may include encoded attribute data, such as identity data (e.g., a full name, a social security number (SSN), and/or the like), in addition to various other data. The prover102may maintain other credentials in which each credential encodes a different portion of the attribute such that the user can selectively disclose private and/or confidential information. As described herein, the credential108includes an undisclosed encoded attribute, which is not decipherable or identifiable except to those parties with a secret key or function. The issuer104, according to one example implementation, configures for the credential108one or more public/private keys using various data, such as another cryptographic key, which may be referred to as a secret key or a private key, the encoded attribute data and/or elements of a prime-order cyclic group.

As described herein, if the user requests access to some service provider, the verifier106applies the non-revocation component110to the credential108and/or other data to determine whether to grant or deny the user's request while maintaining that user's anonymity. The user may disclose the credential108, which may include a considerable large mathematical number or construct, without revealing the identity of the user or the user's organization or device. The credential108includes at least one unique identifier corresponding to the user.

The issuer104and the prover102establish various parameters in accordance with a prime-order group construction without bilinear pairings; and based upon these parameters, the issuer104, or a separate authority, generates the credential108having a compatible format of cryptographic and user data according one example embodiment.

One example parameter established between the issuer104and the prover102includes a groupconstruction selection. If the example parameter specifies a subgroup construction, group's description (p, q, g) specifies a subgroup of prime order q of a finite field of order p. Both p and q are prime numbers, q divides p−1, and g is a generator of. Another example parameter specifies a group construction based upon elliptic curve cryptography over a prime fieldp, group's description (p, a, b, g, q, h) specifies an elliptic curve over a finite fieldp, where p is a prime number, a and b are two field elements defining the elliptic curve, g is a base point (gx, gy) of prime-order q on the curve (and the generator ofq), a is the order of the group, and h is the co-factor of the curve. These group constructions may form a basis for generating standardized cryptographic groups and primitives.

To illustrate one example groupconstruction, letbe a cyclic group, whose order is a prime q and whose elements can be represented as giεfor i=0 . . . q−1. Some of these elements may be herein referred to as generators that are configured to generate each group element such that=g={gi|i is an integer in 0, . . . , q−1} for any i. For a groupof prime order, hereafter denote the set*=\{} whereis the identity element of the group. Unless stated otherwise, the computations of elements inqare assumed to be in mod q.

One example implementation of the cyclic groupconforms to the Discrete Logarithm (DL) assumption in which for every probabilistic polynomial time (PPT) algorithm A where x′q*, the following function is negligible with respect to the security parameter I.
AdvADL(l)=Pr[A(q,,g,gx)=x]

Another example implementation of the cyclic groupconforms to the Strong Diffie-Hellman (SDH) assumption, which states that there generally is no probabilistic polynomial time (PPT) algorithm A that can compute a pair

(c,g1x+c),
where cεq, from a tuple (g, gx, . . . , gxn). Furthermore, cyclic groupconforms to the Strong Diffie-Hellman assumption in which for every probabilistic polynomial time (PPT) algorithm A where x→q*, the following function is negligible:

Based upon either one or both of these assumptions, the example system implements at least two accumulator-based revocation schemes. These schemes may include any prime-order cryptographic group-based scheme. It is appreciated that the present disclosure envisions the use of alternative accumulator-based revocation schemes based on other assumptions. Each revocation scheme provides a universal dynamic accumulator and corresponding polynomial-time functionality. One example function (e.g., a “Setup” function) processes a substantially large binary string as input and outputs setup parameters, including a domain of elements to be accumulated, and/or auxiliary information. Another example function processes the setup parameters and a set of elements as input and returns an accumulator. Optionally, the auxiliary information may be used to compute the accumulator more efficiently. Another set of example functions represent a membership proof system configured to prove that an element is, in fact, accumulated in the accumulator. One example function computes a membership witness for this proof using cryptographic data114, the set of elements, and the undisclosed attribute being used as the credential108. Yet another set of example functions represent a non-membership proving system that proves that an element is not accumulated in the accumulator.

An accumulator is dynamic if polynomial-time functions exist whose costs do not depend upon the number of accumulated elements with respect to adding/removing user identifiers to or from the accumulator and updating a non-membership or membership witness. These user identifiers represent a set of revoked credentials or a set of valid credentials. One or more example implementations of the cryptographic data114include verifier-specific cryptographic data for computing the accumulator, updating the accumulator in response to credential revocations and/or subsequently, determining credential validity using the non-revocation component110.

By way of example, the following describes an implementation without a central revocation authority, whereis a cyclic group of prime order and xεq, represents a challenge from the verifier106to the prover102. Suppose n elements are accumulated into an accumulator representing revoked identifiers of which identifier u is not a member and whose witness is defined as a function ƒ(x)=c(x)(x−u)+d in accordance with the revocation scheme. The value u represents the user's identifier for which the prover102generates the non-revocation component110proving u's non-membership in the accumulator. The value d represents a remainder value. The prover102computes the remainder d and coefficients aiof function c(x)=Σi=0n-1aixiand B=Πi=0n-1giaignd. The prover102communicates a commitment C1to the remainder d and coefficients of function c(x) where C1=Bgr1and receives the challenge x←qin return. The prover102may compute a cryptographic element A=gƒ(x)and designate that element for the verifier104to use for validating non-revocation of the credential108. Alternatively, the prover102may receive that element from the verifier. Using this element, the prover102generates a zero-knowledge proof of u, d, ai(i=0 . . . n−1), ru, r1, r2, r2′ such that

Cu=⁢g1u⁢g2ru⋀C1=∏i=0n-1⁢⁢giai⁢gnd⁢gr1⋀C2=g∑i=0n-1⁢ai⁢xi⁢g0r2⋀A⁢⁢C2-x=C2-u⁢gd⁢g0r2′⋀d≠0
where Curepresents a commitment to the user identifier and C2represents a commitment to the function c(x), proving that the user is not accumulated in the set of revoked identities. In the above proof, the values labeled ru, r1, r2, r2′ denote randomly generated numbers.

One example implementation includes one or more verifier-designated cryptographic keys, such as a public key of pka=(q,, P, H, K, G) and a private key of δ of which both are maintained by the verifier106and/or the revocation authority112. Generally, the private key δεq*, which is a multiplicative group of integers, and random group generators P, H, Gεsuch that K=Hδ. Alternatively, H and G may be related to other issuer parameters, for example H=g and/or G=g1. The private key δ may be generated at random fromq*.

According to one example embodiment involving a U-prove cryptographic scheme, during issuance, the prover102generates cryptographic keys, such as a private key α−1εq* of the credential108. A corresponding public key for the credential108, which is evaluated as h=(g0g1x1. . . gnxngtxt)αwhere each attribute value xiεq\{−δ} for i . . . n are generated, includes a unique user identifier xidencoded as one of the attributes xi(1≦i≦n). To blacklist an identity, the revocation authority accumulates xid. In one exemplary implementation, xiduniquely identifies the user or an organization.

According to one example implementation, the verifier106, or alternatively, an independent revocation authority, provides a repository116for storing various cryptographic scheme related information and implements protocols for verifying an identity of the user to third parties, such as the service provider, without disclosing that identity. As will be understood, this is done without disclosing private or confidential information (e.g., social security numbers, credit card numbers, intellectual property, passwords and/or the like). In one exemplary implementation, the repository116includes various mathematical numbers (e.g., numbers exceeding over 100 digits) that follow certain, well-known cryptographic principles.

For example, the repository116includes encoded attributes associated with at least one revoked user in the form of a blacklist. These attributes may refer to accumulated credentials of revoked users. Alternatively, the repository116includes accumulated credentials for valid users in the form of a whitelist. The repository116also includes packages of mathematical numbers that, when applied to corresponding portions of the credential108, effectuate secure user verification for the service provider.

The verifier106, operating as a revocation authority, accumulates identifiers associated with the at least one revoked user to create a value representing each member, which may be referred to as an accumulator. Such a value may exceed several hundred digits and constitute a portion of a blacklist according to some embodiments of the present disclosure. Similarly, user identifiers for the at least one valid user may be accumulated to form a whitelist.

As described herein, if the user is not a member of the blacklist, or alternatively, if the user is a member of the whitelist, the non-revocation component110includes one or more mathematical values that complement the accumulator. These mathematical values may include one or more membership/non-membership proof components, one or more witness values, one or more commitment values and/or the like. Using the one or more witness values, the prover102generates the non-revocation component110for proving membership or non-membership while selectively disclosing certain attributes. The user retains any information that is to remain private. In one example embodiment, the user only communicates a credential identifier and no other attribute.

The non-revocation component110constitutes a proof-of-possession of the private key of the prover112as well as a digital signature of the user on transaction-related data in which the digital signature is verifiable via verifier-specific cryptographic data. Hence, the non-revocation component110operates as a verifiable digital signature on the transaction-related data (e.g., messages). To create a digital signature with the credential, the prover102generates non-revocation component110using a verifier-designated public key. The non-revocation component110also includes various cryptographic data that enable the verifier106to authenticate the digital signature by verifying that the credential's commitment was generated using the verifier-designated public key and/or verifying that the credential's accumulator-based witness was generated using the verifier-designated private key or the verifier-designated challenge.

Optionally, the issuer104issues the credential108to the prover102in such a manner that the prover102cannot use the credential without the assistance of a trusted device (e.g., a smartcard, a mobile phone, or an online server). Generally, such a device may be configured to efficiently protect multiple credentials issued by any number of issuers, and dynamically (e.g., at presentation time) enforce policies on behalf of the issuers, verifiers, or third parties—without compromising the privacy of the prover102and without needing to interact with the issuer104.

FIG. 2is a block diagram illustrating an example protocol for credential verification according to one or more example implementations. The example system is an alternate implementation of the exemplary system described with respect toFIG. 1. Parties involved in the example protocol include an identity management system202, a service provider204, a user computing device206and an identity provider208. It is appreciated that other parties may be recruited at any operation prescribed by the example protocol.

The identity management system202may be implemented as a network or cloud computing resource in which an issuer210generates various cryptographic data, including cryptographic keys based upon prime-order cyclic groups and other cryptographic primitives. Example architectures of the identity management system202include Microsoft® Windows® Live Id and Microsoft® Azure™ Active Directory® in which a trusted Security Token Service (STS) authenticates users and then, issues credentials to access other relying services. By operating as a designated-verifier revocation authority for accumulator-based cryptographic schemes, the designated-verifier property of the trusted STS provides another level of privacy. One embodiment of the identity management system202may be an integrated service over the network or cloud-computing resource, such as a Microsoft® Windows® Azure™ Active Directory® federation service.

The identity management system202configures a verification mechanism, herein referred to as a verifier216, to authenticate the user computing device on behalf of the service provider204. The identity management system202may also implement a revocation authority212for managing blacklists and/or whitelists comprising revoked and/or valid identifiers, respectively. One example implementation of the example protocol involves the revocation authority212assigning a set of cryptographic keys to each credential verification mechanism.

The user employs security credential technology in order to selectively disclose attribute information and still be permitted access to services associated with the service provider204. The service provider204includes various online (i.e., Internet) properties that employ accumulator-based identity revocation and verification to protect information stored within computer data. The service provider204uses the identity management system202for credential validation by applying a non-revocation component to the credential associated with the user to determine membership or non-membership in either a group of revoked identities or valid identities as described herein.

To illustrate one example, the identity provider208includes a licensing department that generates at least one credential using various user data and issues the at least one credential to the user. As described herein, each credential includes a different combination of attributes, such a Vehicle Identification Number (VIN), car make/model, credential identifier, owner name, driver's license number and/or the like. Depending upon which attribute, if any, the user desires to disclose, the licensing department configures a valid credential with an encoding of only these attributes. The identity provider208enables the revocation authority212to revoke a credential based on characteristics of the valid user identifier embedded therein as an attribute. Once revoked, the public/private key pair associated with the credential cannot be used again.

As depicted byFIG. 2, one example implementation of the example protocol executes a sequence of at least eight operations where each operation corresponds to specific chronological point in time. Each operation's label is an encircled number representing that operation's sequence position.

At operation one (1), the identity management system202initiates the example protocol when a component referred to as the issuer210generates setup parameter data, including cryptographic data for securing user data. Generating setup parameters results in any combination of identifiers (e.g., application-specific identifiers), a cryptographically secure hash algorithm, public/private cryptographic keys for issuing credentials and/or the like.

According to one example implementation, the revocation authority212generates a private key δ, at random, from a prime-order groupq* and designates the private key δ for credential verification. It is appreciated that the present disclosure may refer to the private key δ as a verifier-designated private (cryptographic) key214and vice versa. The revocation authority212provides the verifier216with the verifier-designated key214to perform credential verification. As described herein, credential verification may involve determining non-membership or membership in a blacklist or a whitelist, respectively, in which the blacklist represents a set of revoked user identities and/or the whitelist represents a set of valid user identities. If a user's identity is revoked, any credential based upon that identity also is revoked and is to be considered invalid.

At operation two (2), the identity provider208assigns a unique identifier to the user's devices and informs the identity management system202as to the unique identifier's value, which may refer to the user or the user's organization. The issuer210embeds the unique identifier as an undisclosed attribute in the credential. As an example, the issuer210employs a cryptographic hash function UIDand the unique identifier to compute a hash value, representing one example attribute that the user can recruit to prove non-revocation of the unique identifier and obtain access to the service provider204. As another example, the issuer210transforms the unique identifier's value into a binary encoding of an unsigned integer in big-endian byte-order, which must be smaller than q to be a valid element of multiplicative subgroupq*.

At operation three (3), the user, via the user computing device206, authenticates certain credentials with the identity provider208. To illustrate one example, the user may login into web server associated with the identity provider208by using a valid password. At operation four (4), the user receives a credential encoding the unique identifier as an undisclosed attribute and stores the credential in the user computing device206. Optionally, the credential may be stored in a separate trusted device coupled to the user computing device206.

A component of the user computing device206, referred to herein as a prover220, is configured to obtain access to the service provider204using a valid credential. According to one example embodiment involving U-Prove credentials, the prover220randomly generates a private key α−1εq*, and computes a public key h=(g0g1x1, . . . gnxngtxt)αmod p using the public key of the issuer210in which one of the attributes xiencodes the user identifier xid. The modular multiplicative inverse of the private key randomizes the public key.

Assuming an example revocation attribute for the user identifier xidcorresponds to the credential to be revoked, according to one example implementation, the revocation authority212selects that user identifier for revocation and accumulates xidinto an accumulator218. The user identifier xidmay represent any object; to illustrate a few examples, xidmay uniquely identify a credential, a user or an organization.

The revocation authority212produces the accumulator218with one or more components of public key pka, using the same q as the issuer210, and the verifier-designated private key214. In one example implementation, the revocation authority212includes the blacklist representing at least one revoked identifier or, alternatively, a whitelist represents at least one valid identifier. The revocation authority212may publish the blacklist and or the whitelist with a signature or, alternatively, kept the blacklist and/or the whitelist secret. If signed, anyone with a public key may validate the signed blacklist/whitelist.

Values comprising a witness222, which determine membership or non-membership of the user identifier xidin the accumulator218, may be computed using the verifier-designated private key214and sent to the user. From that moment, the user can update the witness when the accumulated list changes based on the history of the accumulator values. As described herein, the proof224is generated using the accumulator218and the witness222in order to verify that the user's identity is not revoked and therefore, the user's credential is valid. The proof224includes a non-membership proof or a membership proof that enhances security at the service provider204, such as an online vehicle auction web server. The membership proof proves that the user identifier xidis accumulated. The non-membership proof, in contrast, proves that the user identifier xidis not accumulated. Based upon the proof224and the verifier-designated private key214, the verifier216determines whether the user's identity is not revoked and therefore, the credential is valid.

At operation five (5), the revocation authority212of the identity management system202periodically updates the blacklist of revoked identifiers or the whitelist comprising valid identifiers. In one example implementation, the identity provider208and/or other identity providers communicate valid credentials to the revocation authority212and at a later point in time, inform the revocation authority212when these identities become revoked.

To illustrate one example implementation, for a blacklist comprising a set of revoked identifiers {x1, . . . , xm}εq\{−δ} where m≦k, the accumulator218is computable in polynomial time with the expression V=PΠi=1m(δ+xi). If a whitelist of valid identifiers {x1, . . . , xm}εq\{−δ} is employed instead of the blacklist, the accumulator218may be computed in polynomial time with the same expression V=PΠi=1m(δ+xi)where δ is the verifier-designated private key214.

At operation six (6), the user periodically obtains non-revocation witnesses from the identity management system202. These non-revocation witnesses include values computed from the unique identifier attribute used for the credential. In one implementation, for the user identifier xidnot in the blacklist, the witness222is labeled by (W, d, Q) and computed using expression (W=P(Πi=1m(δ+xi)−d)/(δ+xid), d=Πi=1m(δ+xi)mod(δ+xid)εq, Q=VW−xidP−d), proving that xidis not accumulated in V (then Q=Wδ). If there are several members added or deleted to the blacklist or the whitelist, the identity management system updates Q after completely updating W, d.

In example implementations associated with member addition, when a new attribute x′ for a revoked identifier is accumulated into the accumulator218, a new witness (W′, d′, Q′) of the user identifier xidcan be computed as (W′=VW(x′−xid), d′=d(x′−xid), Q′=V′W′−xidP−d′) where V′ is the new accumulated value. For implementations involving member deletion, when an accumulated attribute x′ is removed, the new witness (W′, d′, Q′) of xidcan be computed as

At operation seven (7), the user presents the credential to the service provider204with the witness222of the accumulator218and the proof224. As described herein, the witness222is used to generate a non-membership or membership proof that is stored in the proof224. For some value xidin the credential that is not accumulated in the accumulator218, proving that xidis not accumulated is equivalent to the following expression:
PK{(W,d,xid):V=Wδ+xidPdd≠0}

Let X:=WHt1and Y:=QKt1, then Y=Xδand the previous expression is equivalent to:
PK{(t1,d,xid):VY−1=XxidH−t1xidK−t1PdY=Xδd≠0}

The following five steps refer to one example implementation for generating the non-membership proof of validity for xid's commitment C:=GxidHuwhere u is set by a commitment scheme:

A first step of the above steps refers to generating random numbers (e.g., integers) inq—a prime-order cyclic group of order q under addition. The set ofqis isomorphic to the elements of group. With respect to a second step, the prover220uses the commitment of xidto compute a number of different mathematical elements in groupfor the purpose of computing a hash challenge c at step three. Using the user identifier xid, the prover computes a set of real positive numbers r0, s0, . . . , s8based upon the hash challenge c, the commitment values and the user identifier xid. Along with elements X, Y, R, S, the set of r0, s0, . . . , s8and the hash challenge c form at least a portion of a digital signature allowing the user to prove authenticity of the commitment, which means the committed identifier xidwas used to compute the witness222.

In the above proof, T3, T4, s5, s6show the existence of d−1, therefore d≠0. Commitment of xidcould vary, so a presentation protocol between the service provider204and the user computing device206varies.

The following five steps refer to one alternate implementation for generating the non-membership proof for xid's commitment C:=GxidHu:

The following five steps refer to yet another alternate implementation for generating the non-membership proof for xid's commitment C:=HxidGu:

At operation eight (8), the service provider204communicates the credential and the proof224to the identity management system202for verification. According to one example implementation, using the revocation authority212, the verifier216determines that the credential is not a member of a blacklist comprising revoked identifiers. If the credential is somehow misused, the credential may be revoked and the user identifier may be accumulated into the accumulator218representing at least one revoked identifier. In either implementation, the revocation authority212computes the accumulator218using at least one attribute from each credential whose user's identity is revoked.

In order to produce the witness222, the revocation authority212uses the accumulator218, a prime-order cyclic group generator forming the basis of the credential, and a public/private key pair issued to the verifier216. The accumulator210and the witness222may be based on a Strong Diffie-Hellman assumption. In another example implementation, the prover220computes values for the witness222.

The following two steps illustrate one exemplary implementation in which the verifier216within the identity management system202validates a blacklist non-membership proof labeled c, r0, s0, . . . , s8, X, Y, R, S for x's commitment C:=GxidHu:

The following two steps illustrate one alternate exemplary implementation in which the verifier216within the identity management system202validates a blacklist non-membership proof labeled c, s1, . . . , s7, X, Y, Cx, Cdfor xid's commitment C:=GxidHu:

The following two steps illustrate a second alternate exemplary implementation in which the verifier216within the identity management system202validates a blacklist non-membership proof labeled c, s1, . . . , s6, X, Y, Cdfor xid's commitment C:=HxidGu:

A first step labeled “Compute” involves extracting values from the proof224, including a hash challenge c, and computing mathematical elements of a prime-order cyclic group based upon the extracted values. A first part of a second step labeled “Verify” computes a hash value based upon the mathematical elements computed during the first step, and compares that hash value with the hash challenge c to determine authenticity of the user computing device206without learning the identity of the user. A second part of the security step determines whether the verifier-designated key δ was used to compute the witness222for the credential. If so, the verifier216may assure the service provider204as to the validity of the credential without revealing the identity of the user.

With respect to embodiments where the proof224is a membership proof for the whitelist, a membership witness (W, Q) is computed using an expression (W=PΠi=1m(δ+xi)/(δ+xid), Q=VW−xid) for a xidin the set of valid credentials for the accumulator218. Hence, (W, Q) is the witness indicating that xidis accumulated in V in which Q=Wδ.

When members are added or deleted to the whitelist, the identity management system202only updates Q after completely updating W. In one exemplary implementation of member addition, when a new credential x′ is accumulated, a new witness (W′, Q′) of xidcan be computed as (w′=VW(x′−xid), Q′=V′W′−xid), where V′ is the new accumulating value. In one exemplary implementation of member deletion, when an accumulated credential x′ is removed, the new witness (W′, Q′) of xidcan be computed as the tuple

With respect to generating a membership proof for an accumulated xid, after computing or updating xid's witness (W, Q), proving that xidis accumulated is equivalent to the following expression: PK{(W, xid):V=Wδ+xid}. By assigning X:=WHt1and Y:=QKt1, then Y=Xδand the above expression can be reduced to: PK{(t1, xid):VY−1=XxidH−t1xidK−t1}.

Because compatible commitment schemes of xidvary, the presentation protocol also varies. The following four steps illustrate one example whitelist membership proof generation for xid's commitment C:=GxidHu:

The following four steps illustrate an alternate whitelist membership proof generation for xid's commitment C:=GxidHu:

The following four steps illustrate an alternate whitelist membership proof generation for xid's commitment C:=HxidGu:

The following two steps illustrate one exemplary implementation in which the verifier216within the identity management system202validates the credential xidby verifying values provided in the whitelist membership proof labeled c, r0, s0, . . . , s4, X, Y, R for commitment C:=GxidHu:

A first step labeled “Compute” involves extracting values from the proof224, including a hash challenge c, and computing mathematical elements of a prime-order cyclic group based upon the extracted values. A first part of a second step labeled “Verify” computes a hash value based upon the mathematical elements computed during the first step, and compares that hash value with the hash challenge c to determine authenticity of the user computing device206without learning the identity of the user. The hash value comparison determines whether xid's commitment was actually computed using the user identifier xidand not junk data. A second part of the security step determines whether the verifier-designated key δ was used to compute the witness222for the user identifier xid.

The following two steps illustrate one alternate exemplary implementation in which the verifier216within the identity management system202validates the credential by verifying values provided in the whitelist membership proof labeled c, s1, . . . , s5, X, Y, Cxfor commitment C:=GxidHu:

The following two steps illustrate a second alternate exemplary implementation in which the verifier216within the identity management system202validates the credential by verifying values provided in the whitelist membership proof labeled c, s1, . . . , s4, X, Y for commitment C:=HxidGu:

FIG. 3is a flow diagram illustrating example steps for initiating transactions while remaining anonymous using a minimal disclosure credential according to one or more example implementations. In one implementation, the example steps are performed by various hardware and/or software, such as the prover102ofFIG. 1as described herein.

Steps depicted inFIG. 3commence at step302and proceed to step304at which a credential is processed that is built using standardized cryptographic groups. To illustrate by way of example, the National Institute of Standards and Technology (NIST) provides example embodiments for a number of cryptographic groups. One or more credential parameters, such as a public cryptographic key, may be generated with/without any bilinear pairings and/or based on discrete logarithms. The public cryptographic key, for instance, is computed using group generators of a prime-order finite-field subgroup or elliptic curve and a private key generated by the additive subgroup of integers. Both subgroups may be of the same order and/or isomorphic to each other. Some example embodiments do not employ bilinear pairings in order to enable credential verification and revocation. Lacking a central authority, standardized cryptographic subgroups may be instantiated in a more ad-hoc manner, which allows a cryptographic key or challenge value to remain a secret from other computing devices, except for the designated verifier.

The following describes one or more example implementations in whichrepresents a standardized cryptographic cyclic group, whose order is a prime q, generated by elements P, H, Gε. A verifier-designed private key is generated for an accumulator and labeled δεq*. A value for K=Hδalso is computed. A corresponding domain for elements to be accumulated isq\{−δ}. The accumulator's public key is pka=(q,, P, H, K, G). The grouporder q may be any NIST standardized groups or any groups used by appropriate cryptographic schemes.

Referring to one example embodiment associated with a U-prove cryptographic scheme, the prover receives at least the following information from an identity management system during a credential issuance protocol:

Ordered indices of committed attributes: C⊂U

It is appreciated that the U-prove cryptographic scheme is one example embodiment and other cryptographic schemes may employ private cryptographic data to validate a proof of credential non-revocation. Step306examines the credential's attribute data and identifies a revocation attribute comprising a unique user identifier xidthat is a member of the set of attribute values {A1, . . . , An} either in the form of cleartext data (e.g., an integer) or encoded data (e.g., a hash value). Using the unique user identifier xid, step306generates witness values for proving non-revocation of the credential. The witness values may be computed using a published blacklist/whitelist comprising a signed accumulator. Alternatively, the prover may receive non-revocation witness values (W, d, Q) for the credential from the revocation authority of the identity management system.

Step308computes a commitment for the user identifier xidbased upon the accumulator's public key elements G, Hεq. A commitment is computed by applying these public key elements to a secret value, such as the unique identifier described herein, such that the commitment both binds to and hides the secret value. The accumulator's public key elements can be set G:=g and H:=g1where g, g1are extracted from the issuer parameters. Alternatively, H and G may be set to H=g and/or G=g1, or chosen at random.

Step310represents transaction preparation and presentation proof generation. It is appreciated that the presentation proof may be used to authenticate the integrity of transaction related messages to a service provider in addition to proving validity of the credential. One example embodiment for generating commitments to attributes in a presentation proof is as follows:For each iεCGenerate õi, {tilde over (w)}ifromq{tilde over (c)}i:=gxig1õiãi:=(gwig1{tilde over (w)}i)

For each undisclosed yet committed attribute index i, random values õi, {tilde over (w)}iare generated from the subgroupqand then, used to compute a commitment {tilde over (c)}iand a hash value ãi.

The following refers to one example implementation for generating a challenge value for verifying the user identifier's commitment:

Presenting the credential with at least a commitment and an opening allows the user to access online services anonymously by keeping the user identifier xidsecret while achieving verification. Verifying the user identifier xidinvolves the verification of a cryptographic hash challenge computed independently by both the prover and the verifier.

Example implementations may proceed to following set of operations:

For each iεC, {tilde over (r)}i:=−cõi+{tilde over (w)}imod q

According to the above description, the prover computes a response value r′ for an committed and undisclosed attribute in C that corresponds to the user identifier xid. Computing one example response value r′ may involve performing a transformation on the hash challenge c′ based upon a commitment {tilde over (c)}idcorresponding to the user identifier xid. The prover uses the hash value c′ and an opening õidcorresponding to the user identifier xidin computing the response value r′.

According to one example implementation, the prover uses a set of randomly generated numbers inq, the hash value c′, and the user identifier xidto compute various mathematical numbers based upon a prime-order cyclic group construction, including signature elements s0, . . . , s8. The prover assemblies at least some of these numbers as components of the presentation proof, which is communicated to the service provider in step312. Example embodiments of the presentation proof and commitment to the user identifier xid, of which the provider communicates to the service provider for verification, are described below:

Other embodiments may be constructed using the alternative blacklist non-membership proofs described herein.

The whitelist, as an alternative mechanism, may need a different set of operations to generate a presentation proof demonstrating membership—and therefore, validity—of the user identifier xid. The following represents one example embodiment of such a set of operations with respect to a minimal disclosure credential of which the user identifier xidis accumulated into the whitelist with a witness (W, D):

For each iεC, {tilde over (r)}i:=−cõi+{tilde over (w)}imod q

Step312is directed towards communicating the credential, the presentation proof and commitment values to the service provider in order to initiate the transaction. The presentation proof resulting from the above operations and returned to the service provider may be defined as follows:Presentation proof: {Ai}iεD, a, r0, {ri}iεU, {({tilde over (c)}i, ãi, {tilde over (r)}i)}iεCc′, r′, s0, . . . , s4, X, Y, RCommitment values: {õi}iεC

Other embodiments may be constructed using the alternative whitelist membership proofs described herein.

Once the user identifier xidis verified either to be a whitelist member or a blacklist non-member by validating the credential and the presentation proof, the service provider completes the transaction and returns any related data to the prover. Step314terminates the example steps depicted forFIG. 3.

FIG. 4is a flow diagram illustrating example steps for controlling access to a service provider according to one or more example implementations. In one implementation, the example steps are performed by various software and/or hardware, such as the verifier106ofFIG. 1as described herein.

Access control may involve verifying a credential's validity by applying verifier-specific cryptographic data to a non-revocation component, such as a mathematical proof based upon a prime-order cyclic group construction, for example, that is built using a standardized discrete logarithmic cryptographic group. The mathematical proof may be referred to herein as a presentation proof. The presentation proof, such as a membership proof or a non-membership proof, generally proves credential non-revocation by verifying that the user identifier xidis not accumulated in a blacklist representing revoked credentials or is accumulated in a whitelist representing valid credentials, without learning the user identifier xid's value.

Steps depicted inFIG. 4commence at step402and proceed to step404when a credential is received accompanied by the proof of a credential within that credential. In addition to the credential and the presentation proof, the verifier accesses verifier-specific cryptographic data from a revocation authority in order to validate the credential's non-revocation status. The following represents one set of example input parameters when the revocation scheme is used in conjunction with a U-Prove cryptographic scheme:

Ordered indices of committed attributes: C⊂U

The current accumulating value V

When requesting access to a service provider, the provider running on the user's computing device presents the credential and the proof for credential verification. In one exemplary implementation, the service provider and the user negotiate which attributes to disclose before denying or granting access. The service provider, for instance, may insist on certain information, including credentials. The user and the service provider may decide that no attribute is to be disclosed in order to verify the credential in which instance the user employs an credential to validate the user's request.

Once received, the verifier performs a series of operations to verify the presentation proof in order to determine membership or non-membership in an accumulator. The following represents one example embodiment of such operations in which the accumulator corresponds to the blacklist.

Presentation Proof Verification

Verify that a=((g0gtxtΠiεDgixi)−chr0(ΠiεUgir1))

For each iεC, verify that ãi=({tilde over (c)}icg0rig1{tilde over (r)}i)

Step406to step410refer at least some of these operations, but it is appreciated that these operations may be modified in other embodiments to achieve credential verification. Step406refers to computing discrete logarithmic cryptographic group based values using at least some proof components. Step408is directed towards comparing a hash value based upon a commitment value with an appropriate proof component. Step410illustrates application of a verifier-designated private cryptographic key and a cryptographic hash function to the presentation proof. Step412refers to determining membership or non-membership of the user identifier xidin a blacklist while step414refers to determining membership or non-membership of the user identifier xidin a whitelist. If the presentation proof includes a non-membership proof, the series of operations described above is executed.

On the other hand, if the presentation proof includes a membership proof, step414is executed instead of step412, as represented by the following series of operations.

Presentation Proof Verification

Verify that a=((g0gtxtΠiεDgixi)−chr0(ΠiεUgiri))

Step416represents a determination as to whether the credential is invalid or valid. According to one example implementation, if each and every proof component can be verified, the credential is valid because the credential user's identity has not been revoked and that user may be granted access to the service provider.

If the credential is revoked, step418illustrates denial of access to the user. If the credential is valid, step420illustrates granting of access to the user. Step422terminates execution of the example steps described forFIG. 4.

FIG. 5is a flow diagram illustrating steps for updating at least one witness value according to one or more example implementations. Steps depicted inFIG. 5commence at step502and proceed to step504when at least one witness value is accessed. In one implementation, the example steps are performed by various software and/or hardware, such as the revocation authority212ofFIG. 2as described herein.

Computation of at least one witness value utilizes the unique user identifier embedded as a revocation attribute within a credential, and an accumulator representing at least one revoked identifier or at least one valid identifier. In one implementation, the at least one credential is valid and the at least one user identifier is not accumulated in the blacklist. In another implementation, the at least one credential was pending while the user completed the transaction with a prior credential. Hence, the at least one credential is not valid. The authentication service revoked these credentials and accumulates the at least one user identifier and produce a new accumulator.

Step506represents a determination as to whether to update the at least one witness value in response to an accumulator member addition or member deletion. The accumulator may form a portion of a blacklist or a whitelist. If no such addition or deletion occurred, execution of these steps waits at step508. Once such an addition or deletion occurs, the at least one witness value is updated to reflect a new accumulator. Step510represents implementations that add members to the accumulator and compute up to date witness values. Step512represents implementations that delete members from the accumulator and compute up to date witness values.

Step514represents a comparison of the at least one up to date witness values with the new accumulator. Step514is executed in order to verify that the at least one witness value complements the new accumulator and proves that a user identifier is not accumulated in the blacklist. This ensures a service provider that a credential is indeed valid. Alternatively, the at least one witness value proves that the user identifier is accumulated in the whitelist. Step516represents returning the up to date witness values to a user. Step518represents termination of the example steps.

Example Networked and Distributed Environments

One of ordinary skill in the art can appreciate that the various embodiments and methods described herein can be implemented in connection with any computer or other client or server device, which can be deployed as part of a computer network or in a distributed computing environment, and can be connected to any kind of data store or stores. In this regard, the various embodiments described herein can be implemented in any computer system or environment having any number of memory or storage units, and any number of applications and processes occurring across any number of storage units. This includes, but is not limited to, an environment with server computers and client computers deployed in a network environment or a distributed computing environment, having remote or local storage.

Distributed computing provides sharing of computer resources and services by communicative exchange among computing devices and systems. These resources and services include the exchange of information, cache storage and disk storage for objects, such as files. These resources and services also include the sharing of processing power across multiple processing units for load balancing, expansion of resources, specialization of processing, and the like. Distributed computing takes advantage of network connectivity, allowing clients to leverage their collective power to benefit the entire enterprise. In this regard, a variety of devices may have applications, objects or resources that may participate in the resource management mechanisms as described for various embodiments of the subject disclosure.

FIG. 6provides a schematic diagram of an example networked or distributed computing environment. The distributed computing environment comprises computing objects610,612, etc., and computing objects or devices620,622,624,626,628, etc., which may include programs, methods, data stores, programmable logic, etc. as represented by example applications630,632,634,636,638. It can be appreciated that computing objects610,612, etc. and computing objects or devices620,622,624,626,628, etc. may comprise different devices, such as personal digital assistants (PDAs), audio/video devices, mobile phones, MP3 players, personal computers, laptops, etc.

Each computing object610,612, etc. and computing objects or devices620,622,624,626,628, etc. can communicate with one or more other computing objects610,612, etc. and computing objects or devices620,622,624,626,628, etc. by way of the communications network640, either directly or indirectly. Even though illustrated as a single element inFIG. 6, communications network640may comprise other computing objects and computing devices that provide services to the system ofFIG. 6, and/or may represent multiple interconnected networks, which are not shown. Each computing object610,612, etc. or computing object or device620,622,624,626,628, etc. can also contain an application, such as applications630,632,634,636,638, that might make use of an API, or other object, software, firmware and/or hardware, suitable for communication with or implementation of the application provided in accordance with various embodiments of the subject disclosure.

Thus, a host of network topologies and network infrastructures, such as client/server, peer-to-peer, or hybrid architectures, can be utilized. The “client” is a member of a class or group that uses the services of another class or group to which it is not related. A client can be a process, e.g., roughly a set of instructions or tasks, that requests a service provided by another program or process. The client process utilizes the requested service without having to “know” any working details about the other program or the service itself.

In a client/server architecture, particularly a networked system, a client is usually a computer that accesses shared network resources provided by another computer, e.g., a server. In the illustration ofFIG. 6, as a non-limiting example, computing objects or devices620,622,624,626,628, etc. can be thought of as clients and computing objects610,612, etc. can be thought of as servers where computing objects610,612, etc., acting as servers provide data services, such as receiving data from client computing objects or devices620,622,624,626,628, etc., storing of data, processing of data, transmitting data to client computing objects or devices620,622,624,626,628, etc., although any computer can be considered a client, a server, or both, depending on the circumstances.

In a network environment in which the communications network640or bus is the Internet, for example, the computing objects610,612, etc. can be Web servers with which other computing objects or devices620,622,624,626,628, etc. communicate via any of a number of known protocols, such as the hypertext transfer protocol (HTTP). Computing objects610,612, etc. acting as servers may also serve as clients, e.g., computing objects or devices620,622,624,626,628, etc., as may be characteristic of a distributed computing environment.

Example Computing Device

As mentioned, advantageously, the techniques described herein can be applied to any device. It can be understood, therefore, that handheld, portable and other computing devices and computing objects of all kinds are contemplated for use in connection with the various embodiments. Accordingly, the below general purpose remote computer described below inFIG. 7is but one example of a computing device.

FIG. 7thus illustrates an example of a suitable computing system environment700in which one or aspects of the embodiments described herein can be implemented, although as made clear above, the computing system environment700is only one example of a suitable computing environment and is not intended to suggest any limitation as to scope of use or functionality. In addition, the computing system environment700is not intended to be interpreted as having any dependency relating to any one or combination of components illustrated in the example computing system environment700.

With reference toFIG. 7, an example remote device for implementing one or more embodiments includes a general purpose computing device in the form of a computer710. Components of computer710may include, but are not limited to, a processing unit720, a system memory730, and a system bus722that couples various system components including the system memory to the processing unit720.

Computer710typically includes a variety of computer readable media and can be any available media that can be accessed by computer710. The system memory730may include computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) and/or random access memory (RAM). By way of example, and not limitation, system memory730may also include an operating system, application programs, other program modules, and program data.

A user can enter commands and information into the computer710through input devices740. A monitor or other type of display device is also connected to the system bus722via an interface, such as output interface750. In addition to a monitor, computers can also include other peripheral output devices such as speakers and a printer, which may be connected through output interface750.

The computer710may operate in a networked or distributed environment using logical connections to one or more other remote computers, such as remote computer770. The remote computer770may be a personal computer, a server, a router, a network PC, a peer device or other common network node, or any other remote media consumption or transmission device, and may include any or all of the elements described above relative to the computer710. The logical connections depicted inFIG. 7include a network772, such local area network (LAN) or a wide area network (WAN), but may also include other networks/buses. Such networking environments are commonplace in homes, offices, enterprise-wide computer networks, intranets and the Internet.

As mentioned above, while example embodiments have been described in connection with various computing devices and network architectures, the underlying concepts may be applied to any network system and any computing device or system in which it is desirable to improve efficiency of resource usage.

Also, there are multiple ways to implement the same or similar functionality, e.g., an appropriate API, tool kit, driver code, operating system, control, standalone or downloadable software object, etc. which enables applications and services to take advantage of the techniques provided herein. Thus, embodiments herein are contemplated from the standpoint of an API (or other software object), as well as from a software or hardware object that implements one or more embodiments as described herein. Thus, various embodiments described herein can have aspects that are wholly in hardware, partly in hardware and partly in software, as well as in software.

In view of the example systems described herein, methodologies that may be implemented in accordance with the described subject matter can also be appreciated with reference to the flowcharts of the various figures. While for purposes of simplicity of explanation, the methodologies are shown and described as a series of blocks, it is to be understood and appreciated that the various embodiments are not limited by the order of the blocks, as some blocks may occur in different orders and/or concurrently with other blocks from what is depicted and described herein. Where non-sequential, or branched, flow is illustrated via flowchart, it can be appreciated that various other branches, flow paths, and orders of the blocks, may be implemented which achieve the same or a similar result. Moreover, some illustrated blocks are optional in implementing the methodologies described hereinafter.

CONCLUSION