By leveraging on Ciphertext-Policy Attribute-Based Encryption, we build a credential management protocol with anonymous proof of predicates. The protocol supports eficient revocation through accumulators. Anonymous credentials have experimented a renewed interest during the very last few years due to the going to mainstream of various user "wallet" models. For example, an ongoing efort at IEFT is intended to promote a very recent eficient construction of the BBS signature [ 1] as a standard cryptographic primitive for the problem space of privacy preserving identity credentials. Historically, anonymous credentials were mostly built on special signature schemas. The prover, after obtaining a signature over a set of attributes from an issuer, is able to randomize it and proves in zero-knowledge its possession to a verifier, optionally revealing a subset of those attributes (so called selective disclosure). The verifier is unable to determine which signature was used to generate the proof, removing any source of correlation (unlinkability). However, in practical contexts, selective disclosure is not the only desired feature. For example, a service may require that their users are over 18 years old and that they are based in one of the European Countries. In such a case, an anonymous proof of predicates proving user's attribute age and country satisfying the following policy:
age GT 18 AND country ONEOF {Austria, Belgium,. . . , Sweden}
would be needed. Recent advances [
In this paper, we provide the following contributions:
1. We directly build a functional credentials schema from the Ciphertext Policy
AttributeBased Encryption (CP-ABE) construct proposed in [
The original construction reported in Section 5 of [
Let and be two multiplicative cyclic groups of prime order . Let be a generator of and be a bilinear map: : × → . The bilinear map has the following properties: 1. Bilinearity: for all , ∈ and , ∈ , we have (, ) = (, ) = (, ). 2. Non-degeneracy: (, ) ̸= 1.
If the group operation in and the bilinear map are both eficiently computable, is said a bilinear group.
Here, we consider CP-WATERS-KEM in its small universe construction, however, an extension
to the large universe construction (reported in Appendix A of [
We implement a revocation scheme preventing decryption of ciphertext created after the
key has been revoked. Note that this is not a general revocation scheme for ABE. Rather, it is
a “forward revocation”, where only ciphertext generated after the actual revocation happens
becomes hard to decrypt if the key has been revoked. To implement this kind of revocation,
the original CP-WATERS-KEM scheme is slightly altered and combined with the cryptographic
accumulator based on bilinear mappings described by Camenisch in [
The accumulator makes use of a set of indexes {} kept by the Authority and assigned to
each released secret key. In the setup phase, the Authority initially creates an accumulator
0 = 1 and two public initially empty sets: = {} and = {}, where is the set of all
indexes that will be ever added to the accumulator (but may have been subsequently removed).
The sequence , . . . , , +2, . . . , 2 (but not +1) is made public by the Authority (e.g.,
as part of ). Appendix D of [
Where ∈ is a generator of the group of prime order , and is picked at random from
The schema is adapted from [
By definition, for all ∈ N, for all (MSK, MPK) ∈ CKGen(1 ) for all S ⊂ Ω, for all cred ∈ GrantCred, for all f ∈ Φ such that f(S) = 1, a functional credentials scheme • is said correct if, assumed cred is valid (i.e., cred ̸∈ Revoke) it holds that
Pr[1 ← < ShowCred(MPK, cred, f), VrfyCred(MPK, f) >] = 1 • is said unforgeable if, chosen an arbitrary policy f, any adversary having access to all system issued credentials credi ∈ GrantCred but the ones satisfying the policy (i.e, f(credi) ̸= 1) and to all revoked credentials credj ∈ Revoke, has a negligible probability to succeed in the credential verification process. • is said anonymous if, arbitrarily chosen a policy f and two provers P0 and P1 owing non-revoked credentials credi, credj ̸∈ Revoke, both satisfying or not the policy (i.e., f(credi) = f(credj)), any adversary cannot distinguish between them.
Note that we leave out one optional feature described in the original paper (policy hiding).
To support revocable functional credentials as above defined, CP-WATERS-KEM is modified as follows: 1. (MPK, MSK) ← Setup(1 ): The algorithm outputs the master secret key and the master public key , and publishes the .
• The algorithm chooses a group of prime order and generator , random group elements ℎ1, ℎ2, . . . , ℎ (where is the maximum number of system attributes) and a bilinear pairing such that : × → . In addition, it chooses random exponents , , , ∈ . • The algorithm initially creates an accumulator 0 = 1, and two initially empty public sets: = {} and = {}, where is the set of all indexes that will be ever added to the accumulator (but may have been subsequently removed). • The public key is , , ℎ1, ℎ2, . . . , ℎ, , and
( , ) (, +1)
The master secret key is , , , , . • The sequence , . . . , , +2, . . . , 2 (but not +1) is made public by the
Authority. 2. (MPK′, SKi = (Ki, Li, ∀x∈S Ki,x, witi)) ← KeyGen(MPK, MSK, S): Key generation happens by taking as input the master keys ( , ) and a set of attributes that describe the key. The output is a randomized secret key. The Authority associates an index to each new generated secret decryption key .
• The algorithm includes in the set and : = ∪ {}, = ∪ {} and updates the accumulator : • The algorithm updates the terms in the master public key using the accumulator: and ( , ) (, +1), while the master secret key remains the same. • Chosen a random ∈ , the algorithm computes the secret decryption key component as as follows: = ++ , = and, for each ∈ , , = ℎ. • Also, the algorithm releases a new key component (the witness): = ∏︁ +1+− = ∑︀̸= +1+− . 3. MPK′ ← KeyRemove(PK, MSK, i): A similar step is also executed when the Authority needs to revoke a key . In this case, the algorithm simply removes from the set , recomputes the accumulator value and, consequently, the terms in the master public key using it: and ( , ) (, +1 ) as above (the master secret key remains the same).
With the addition or removal of elements to the accumulator, previously released witnesses become stale and any Client who has previously received a witness shall update it.
Therefore, the following step is introduced into the schema: 4. wit′i ← UpdateWitness(MPK, Vold, V, witi): The algorithm takes as input the old witness and updates it to match the new master public key and the current set of authorized indices . The new witness is locally computed using the following equation: ′ ←
∏︀ ∏︀ ∈/ +1+− ∈/ +1+− Note that the Client does not know +1 , hence, this algorithm fails when the condition ∈ ∩ is not verified, i.e. a Client cannot update its if is not (no more) in as a result of a revocation. In this case the update operation returns ′ = ⊥. 5. (C = (C′, C′′, ∀k∈[1,... l] Ck), ) ← Encrypt(MPK, Ml× m, ): The algorithm takes as input an access structure (, ) and the public key . is an × matrix, while is an injective function associating each row of to an attribute (i.e., = () ∈ ); note that in this construct one attribute is associated with at most one row. The output is a random secret and the ciphertext.
• Chosen a random vector ⃗ = (, 2, . . . , ) in and being the -th row of , the algorithm computes = · . • Together with a with description of (, ), the algorithm makes public the ciphertext:
ℎ− , ′′ = = ( ∏︁ +1− ) ′ = , = ∈ • Finally, the algorithm computes the random secret
= [( , ) (, +1 )] and keeps it private. 6. ← Decrypt(SKi, C): Dually, the decryption takes as input the ciphertext and the secret key . The output is the shared secret if and only if the set of attributes satisfies the access structure, or ⊥ otherwise.
• For each such that ∈ (i.e., consider only attributes in ), compute such that ∑︀ = (there could diferent sets of {} satisfying this equation) • Compute the random secret:
(′′, ) = ∏︀ [(, )(′, , )] (′, ) = [( , ) (, +1 )]
To understand why decryption works, consider the solution equation, and note the numerator is (′′, ) = (, ) ∑︀∈ +1+− ( ++ ) = (, ) ( , ) ( , )(, )∑︀∈ +1+−
As in the original CP-ABKEM decryption algorithm, the second factor ( , ) cancels out with the first part of the denominator: ∏︁[(, )(′, )] = ∏︁ ([ ℎ− , )(, ℎ )] = ∏︁ ( , ) = ( , )
Regarding the third factor (, )∑︀∈ +1+− we note that, if and only if the index is contained in the current accumulator (i.e., ∈ ), we have: (, )∑︀∈ +1+− = (, +1+∑︀̸= +1+− ) = (, +1 )(, ) [( , ) (, +1 )]
Partially cancelling out with the factor (, ) in the denominator. Therefore, the result of the computation is
To prove security, we use a security game based on the one presented in Section 5 of [
S1, . . . , Sq′ (with 1 < ′ < ). • Revocation Using the keyremove algorithm in the schema, any key may (or not) be revoked. Phase 1 and Revocation may be arbitrarily interleaved. • Challenge. The adversary submits two equal length messages M0 and M1. In addition the adversary gives a challenge access structure A* such that none of the sets S1, . . . , Sq′ from Phase 1 satisfies the access structure, or such that any of those keys corresponding to sets satisfying the access structure has been revoked. The challenger flips a random coin , and encrypts M under A* . The ciphertext CT* is given to the adversary. • Phase 2. Phase 1 is repeated with the restriction that none of sets of attributes Sq′+1, . . . , Sq satisfies the access structure corresponding to the challenge. Revocation may also occur in this phase.
• Guess. The adversary outputs a guess ′ of .
The advantage of the adversary in the above game is = Pr[ ′ = ] − 21 and, by definition, the scheme is secure if all polynomial time adversaries have at most a negligible advantage. We use a selective proof, therefore the above game is augmented by an initial step Init in which the adversary commits to the challenge access structure * and to the final set of credentials that will eventually appear in the accumulator * .
Our security proof works under the General Difie-Hellman Exponent Problem introduced by
Boneh, Boyen and Goh in [
Note that the presented security model supports only chosen-plaintext attacks. The model is
extended to handle chosen-ciphertext attacks by allowing for decryption queries in Phase 1 and
Phase 2. To achieve chosen-ciphertext security we use the Fujisaki-Okamoto transformation
reported in subsection 3.1 and 3.2. As this transformation exactly applies as in the original
paper, we let the reader refer to [
We use the above CP-ABE schema to implement the revocable functional credential schema in
section 2.2(the protocol is also adapted from [
Note that since each challenge encapsulates a randomly generated secret token, the protocol is natively immune to replay attacks.
To ensure anonymity, the Fujisaki Okamoto transformation may be applied to
CP-WATERSKEM. This transformation was already described in [
The CCA-secure encryption algorithm is specified by the following steps: • The decrypting party (prover) shall choose a random number and send it to the encrypting party. • Received , the encrypting party (verifier) chooses an access structure and a secret and concatenates them to form the string |||| • The encrypting party runs the encryption algorithm of the original CP-WATERS-KEM or of the modified schema with revocation to get a random secret and the ciphertext. The seed |||| is used as a source of randomness for the encryption algorithm with u ← PRG(H′(rc||Kc||AP), ), where PRG is a pseudo random generator, is the length of the returned random bit string ( ∈ {0, 1}) and ′ is a collision-resistant hash function. – The random secret is (, ) for CP-WATERS-KEM or (( , ) (, +1 )) for the modified CP-WATERS-KEM. The encrypting party keeps it private and uses in the next step.
– The encrypting party releases the ABKEM ciphertext . • The encrypting party uses random secret above for XORing the concatenation || – Transform || into bytes (octects). – Using the pseudo random generator , get for CP-WATERS-KEM or r ←
PRG(H(e(g, g) s), ) r ←
PRG(H([e(accV, g) e(gb, g n+1 )]s), ) for the modified CP-WATERS-KEM, with being a collision-resistant hash function. – Finally, compute = ⊕ (||)
The CCA-secure decryption algorithm is specified by the following steps: • Run decryption of the original CP-WATERS-KEM or of the modified schema to decrypt the ciphertext and obtain the shared secret:
(, ) or for the modified schema. • Use that shared secret to generate randomness (( , ) (, +1 )) r ← r ← • Use generated randomness for XORing the ciphertext and retrieve and : ⊕ = (||) • Verify matches the random number chosen at beginning. • Run again the CCA-secure Encryption using |||| as a source of randomness and verify the result is equal to the received ciphertext .
Due to space limitations, we let the reader refer to [
Combining Ciphertext Policy Attribute-Based Encryption (CP-ABE) and accumulators we build a revocable credential management framework supporting anonymous proof of predicates over attributes; we further achieve anonymity by applying a simple transformation to the resulting schema. To the best of our knowledge, our work is the first one eficiently combining rich policy expressiveness (from ABE), revocation (from accumulator) and anonymous proof of predicates over attributes into a single framework.
Theorem. A polynomial time adversary, acting as a Verifier, cannot distinguish between any two provers with diferent CP-WATERS-KEM (plus Accumulator) keys, if their (non revoked) keys both satisfy (or not satisfy) the same access structure they are tested against.
Proof. We start considering the following security game (adapted from [
Modify the game as follows: at step 7, when given a ciphertext , oracle O1 checks if appears in the random oracle table. If so, it outputs the corresponding = (||) value in the table; otherwise, it outputs ⊥ and rejects.
The diference between the original game and the modified one is negligible, as in the original game the oracle may decrypt even in case of a forged ciphertext (i.e., a ciphertext not computed using the CCA-secure encryption algorithm). However, since O1 was not queries on (|||| ), the probability that this event happens is bounded by the probability of apriori guessing a ciphertext output by an encryption for a given message without knowing the randomness used to encrypt.
Now, the following observations apply to this modified game: • If the Verifier produces a genuine ciphertext C following the CCA-secure Encryption algorithm, she gets a correct decryption if the attributes embedded in the secret key satisfy the chosen access structure * , i.e. * () = 1. Thus, the presented schema satisfies by definition the correctness property. • Viceversa, if the attributes embedded in the secret key do not satisfy the chosen access structure * , i.e. * () = 0, the ciphertext wouldn’t decrypt at all except for a negligible probability . Thus, the presented schema satisfies by definition the unforgeability property.
Furthermore, we observe that: • The access structure * associated to the ciphertext is always known to the challenger (given as input after being chosen by the adversary) • Because a pseudo random generator is used, the ciphertext is deterministically computed from the public key and the access structure * • The ciphertext is uniformly distributed on the ciphertext space, because computed using the uniformly distributed randomness in step 3.
Under the conditions above, suppose to modify the previous game replacing prover ’s behaviour as follows: • if key embeds attributes satisfying the access structure * , then message is returned; • otherwise ⊥ is returned.
That is, no longer evaluates the decryption using the key rather it (deterministically) returns or ⊥ depending on the internal bit * (). Since * (0) = * (1) (both keys satisfy or not satisfy the access structure), in the latter schema the random coin of the oracle remains hidden in the information-theoretic sense. This implies that the advantage of any adversary is 1/2 in distinguish between 0 and 1. As the introduced modifications do not alter the advantage except for at most a negligible probability, the advantage of any adversary in the original game is negligibly close to 1/2. □