Attribute-Based Identiﬁcation:
Deﬁnitions and Eﬃcient ConstructionsHiroaki Anada, Seiko Arita, Sari Handa, and Yosuke Iwabuchi
Graduate School of Information Security, Institute of Information Security, Japan
2-14-1 Tsuruya-Cho, Kanagawa-Ku, Yokohama-Shi, 221-0835, Japanhiroaki.anada@gmail.com, {arita,mgs125502,mgs123101}@iisec.ac.jp

Abstract. We propose a notion of attribute-based identiﬁcation(ABID) in two ﬂavors: prover-policy ABID (PP-ABID) and veriﬁerpolicy ABID (VP-ABID). In a PP-ABID scheme, a prover has an authorized access policy written as a boolean formula over attributes,
while each veriﬁer maintains a set of attributes. The prover is accepted
when his access policy ﬁts the veriﬁer’s set of attributes. In a VPABID scheme, a veriﬁer maintains an access policy written as a boolean
formula over attributes, while each prover has a set of authorized attributes. The prover is accepted when his set of attributes satisﬁes theveriﬁer’s access policy. Our design principle is ﬁrst to construct keypolicy and ciphertext-policy attribute-based key encapsulation mechanisms (KP-ABKEM and CP-ABKEM). Second, we convert KP-ABKEM
and CP-ABKEM into challenge-and-response PP-ABID and VP-ABID,
respectively, by encapsulation-and-decapsulation. There, we show that
KP-ABKEM and CP-ABKEM only have to be secure against chosenciphertext attacks on one-wayness (OW-CCA secure) for the obtained
PP-ABID and VP-ABID to be secure against concurrent man-in-themiddle attacks (cMiM secure). According to the design principle, weconstruct concrete KP-ABKEM and CP-ABKEM with the OW-CCA
security by enhancing the KP-ABKEM of Ostrovsky, Sahai and Waters
and CP-ABKEM of Waters, respectively. Finally, we obtain concrete PPABID and VP-ABID schemes that are proved to be selectively secure in
the standard model against cMiM attacks.
Keywords: access policy, attribute, identiﬁcation, key encapsulation
mechanism.

1

Introduction

An identiﬁcation (ID) scheme enables a prover to convince a veriﬁer that theprover certainly knows a secret key that corresponds to the matching public
key. For example, Σ-protocols [7] such as the Schnorr protocol [14,5] are widely
recognized. In these ID schemes, the public key to which the veriﬁer refers limits
the corresponding secret key uniquely, and also, the corresponding prover.
Supported by MEXT-Supported Program for the Strategic Research Foundation atPrivate Universities, 2011-2013.

C. Boyd and L. Simpson (Eds.): ACISP 2013, LNCS 7959, pp. 168–186, 2013.
c Springer-Verlag Berlin Heidelberg 2013

Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

169

In this paper, we will describe an attribute-based identiﬁcation (ABID). In an
ABID scheme, each entity has credentials called attributes. On the other hand,an access policy is written as a boolean formula over those attributes. Then,a veriﬁer can identify that a prover certainly belongs to a set of entities thathave authorized access policies that ﬁt the veriﬁer’s attributes, or, in the dual
ﬂavor, a veriﬁer can identify that a prover certainly belongs to a set of entities
that possess authorized attributes that satisfy the veriﬁer’s access policy. Hence,
ABID schemes can be considered as an expansion of the usual ID schemes.
However, ABID schemes are not a mere expansion, but have useful applications beyond those of the usual ID schemes. For example, the following scenariosof smart card systems motivate us to apply ABID.
Functional Tickets. Suppose that we are going to stay at a resort complex, aski resort, for instance. We search Web sites or brochures for information about
services: available dates, accommodation, ski lifts, restaurants in ski areas andhot springs around the areas. For each service, we usually buy a ticket, paying
with money or using a credit card. However, acquiring many tickets and carrying
a wallet is inconvenient, and therefore, it would be more convenient if we could
gain access to these services by using only one smart card. In the smart card,a service authority writes an access policy in terms of the service names that
we choose, for instance, [January 1 to 4, 2014] AND [[Hotel A] OR [Ski LiftAND [Day OR Night]] OR [Lunch OR Beer] OR [Hot Spring X]]. A functional
ticket is a ticket embedded in a smart card that realizes an access policy as
a boolean formula over services, as in this scenario. Here, the access policy is
chosen according to our requirements.
Functional Gates. Suppose that we have to design a security gate system foran oﬃce building in which diﬀerent kinds of people work: employees of several
companies holding many diﬀerent positions, security guards, food service staﬀs,
cleaning staﬀs and janitors. There are also many types of security gates to be
designed: building entrances, intelligent elevators to limit available ﬂoors, company gates, common refreshment areas and room doors for the above staﬀs. In
this case, one solution is to use smart cards and gates with sensors. That is,
an authority issues each person a smart card in which a set of attribute data is
written. Each gate decides whether to “pass” each person carrying a smart card
according to the gate’s access policy, for instance, [Year 2014] AND [[[Company
A] AND [Manager]] OR [Security Guard]]. A functional gate is a gate that maintains an access policy as a boolean formula over attributes of people, as in this
scenario. Here, the access policy is chosen according to the kind of people thatthe gate should allow to pass.
1.1

Our Contributions

Bearing the above scenarios in mind, we propose a notion of attribute-based
identiﬁcation (ABID) that has two ﬂavors corresponding to the scenarios: proverpolicy ABID and veriﬁer-policy ABID.

170

H. Anada et al.

Prover-Policy ABID. In a prover-policy ABID scheme (PP-ABID, for short),a prover has his own authorized access policy, while each veriﬁer maintains its
attributes. Here, the access policy is described over the veriﬁer’s attributes. Sending his access policy, each prover queries an authority for his secret key. Then,
using this secret key, each prover can convince the veriﬁer that his access policy ﬁts the veriﬁer’s attributes. Our PP-ABID deﬁned in this way realizes afunctional ticket system.
Veriﬁer-Policy ABID. In a veriﬁer-policy ABID scheme (VP-ABID, for short),a veriﬁer maintains its access policy, while each prover has his own authorized attributes. Here, the access policy is described over the prover’s attributes. Sending
his attributes, each prover queries an authority for his secret key. Then, using thissecret key, each prover convinces the veriﬁer that his attributes satisfy the veriﬁer’s
access policy. Our VP-ABID deﬁned in this way realizes a functional gate system.
Attack and Security Analysis. An adversary’s objective is impersonation:
giving a target set of attributes (or, a target access policy) to a veriﬁer, theadversary tries to make the veriﬁer accept him.
First, to reﬂect a collusion attack (that is, an attack launched by collecting
secret keys that satisfy a condition), we consider an attack model in which an
adversary issues key-extraction queries, as is the case for attribute-based encryptions [13,15]. The condition is that the adversary cannot collect any secret key
whose intrinsic access policy ﬁts the target set of attributes (or, whose intrinsic
set of attributes satisﬁes the target access policy).
Our main objective is to deﬁne a model of concurrent man-in-the-middle attack (cMiM attack) in the setting of ABID. “Concurrent” means that an adversary can invoke provers that have diﬀerent secret keys corresponding to diﬀerent
access policies (or, diﬀerent sets of attributes). The adversary interacts with theseprovers in an arbitrarily interleaved order of messages. Then, interacting with averiﬁer on a target set of attributes (or, on a target access policy, respectively)
the adversary tries to impersonate a prover. The concurrent attack modeled inthis way is a real threat, especially to smart card systems. On the other hand,“man-in-the-middle (MiM)” means that an adversary stands between a proverand a veriﬁer simultaneously. Typically, the adversary ﬁrst receives a message
from the veriﬁer, and then, the adversary begins to interact with the prover adaptively to the veriﬁer’s message. The MiM attack and the cMiM attack modeledin this way are real threats, especially to network applications.
As is the case for usual ID schemes, reset attacks should be considered. In a
reset attack, an adversary aborts an interaction at any point, and then rewinds
the interaction back to any other point to start the interaction again. At thatre-starting point, the adversary is allowed to change messages as long as theinteraction remains valid (as captured by the word “reset”). Such a reset attack
is a strong threat, not only to smart card systems [4] (including the functional
tickets and functional gates described above) but also to virtual machine services
in cloud computing [17]. As our contribution, an ABID constructed using ourAttribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

171

generic conversion becomes secure against the reset attacks in both senses ofprover-resettable and veriﬁer-resettable [4].
It is desirable that a veriﬁer learns nothing about a prover more than that
he belongs to the set of entities that have access policies ﬁtting the veriﬁer’s
attributes (or, belongs to the set of entities that possess attributes satisfying
the veriﬁer’s access policy). In fact, by this property (anonymity), the prover’s
privacy is protected when using a functional ticket, as opposed to using a credit
card the track of which is recorded. As our contribution, our concrete ABID in
Section 5 possesses this anonymity.
Design Principle. First, we construct key-policy and ciphertext-policy
attribute-based key encapsulation mechanisms (KP-ABKEM and CP-ABKEM[13,15]). Second, we convert the KP-ABKEM and CP-ABKEM into challengeand-response PP-ABID and VP-ABID, respectively, by encapsulation-anddecapsulation. There, we show that KP-ABKEM and CP-ABKEM only haveto be secure against chosen-ciphertext attacks on one-wayness (OW-CCA secure) for the obtained PP-ABID and VP-ABID to be secure against cMiM attacks (cMiM secure). We stress that the security of indistinguishability against
chosen-ciphertext attacks (the IND-CCA security) is excessive, and the OWCCA security is enough for constructing a cMiM secure ABID.
Concrete Constructions. We construct KP-ABKEM and CP-ABKEM with
the OW-CCA security from the KP-ABKEM of Ostrovsky, Sahai and Waters[13] and CP-ABKEM of Waters [15]. Their KEMs are secure in the indistinguishability game of chosen-plaintext attack (IND-CPA secure). Our strategy is
to apply the algebraic trick of Boneh and Boyen [3] and Kiltz [11] to attain CCA
security. Then our generic conversions yield concrete PP-ABID and VP-ABID.
New Number Theoretic Assumptions. We will introduce the Computational Bilinear Diﬃe-Hellman Assumption with Gap on Target Group and theComputational q-Parallel Bilinear Diﬃe-Hellman Exponent Assumption with
Gap on Target Group. These assumptions are reasonable, for example, for thebilinear map of a pairing on a elliptic curve. We need these assumptions forsecurity proofs of concrete constructions.
1.2

Related Works

Anonymous Deniable Predicate Authentication. First, we should referto the work of Yamada et al. [16]. Our generic construction of ABID can beconsidered as a special case of their predicate authentication; however, it diﬀers
in at least two points. The ﬁrst point is that our objective is to provide a simple,
fast ABID. In contrast, Yamada et al.’s objective is to apply their veriﬁable
predicate encryption to yield an anonymous deniable message authentication.
In fact, we simply consider a 2-round challenge-and-response ABID, whereas
they proposed a 6-round protocol for deniability. The second point is that we
provide more eﬃcient concrete ABID by using the algebraic trick ([3,11]). In
contrast, they used their generic transformation which causes a longer secret key,

172

H. Anada et al.

a longer ciphertext and more computational costs for encryption and decryption
than ours, because a veriﬁcation key of a one-time signature is involved in theirgeneric transformation.
Identiﬁcation Scheme from KEM. Anada and Arita [1] proposed a designprinciple of obtaining a cMiM secure ID scheme by constructing KEM. Theirconcrete ID scheme is more eﬃcient than known Σ-protocol-based cMiM secure
ID schemes ([9]). Our scheme can be seen as an attribute-based version of theirs.
1.3

Organization of the Paper

In Section 2, we survey the required terms. In Section 3, we deﬁne the notionsof PP-ABID and VP-ABID, cMiM attacks and security against it. In Section 4,
we provide generic conversions from KP-ABKEM to PP-ABID and from CPABKEM to VP-ABID. In Section 5, we construct concrete KP-ABKEM and
CP-ABKEM. Finally, we obtain concrete PP-ABID and VP-ABID. In Section
6, we present the conclusions of our study. Because of space limitation, the caseof PP-ABID is described in the main text and the case of VP-ABID is only
shortly described in the Appendix.

2

Preliminaries

The security parameter is denoted by λ. A prime of bit length λ is denoted by
p. A multiplicative cyclic group of order p is denoted by G. The ring of the
exponent domain of G, which consists of integers from 0 to p − 1 with modulo
p operation, is denoted by Zp . When an algorithm A with input a outputs z,
we denote it as z ← A(a). When A with input a and B with input b interact
with each other and B outputs z, we denote it as z ← A(a), B(b). When A has
oracle-access to O, we denote it as AO . When A has concurrent oracle-access tonn oracles O1 , . . . , On , we denote it as AOi |i=1 . Here “concurrent” means that A
accesses to oracles in arbitrarily interleaved order of messages. A probability ofan event E is denoted by Pr[E]. A probability of an event E on condition thatevents E1 , . . . , Em occur in this order is denoted as Pr[E1 ; · · · ; Em : E].
2.1

Access Structure

Let U = {χ1 , . . . , χu } be an attribute universe, or simply set U = {1, . . . , u}.
We must distinguish two cases: the case that U is small (i.e. |U| = u is boundedby some polynomial in λ) and the case that U is large (i.e. u is not necessarily
bounded). We assume the small case unless we state the large case explicitly. An
access structure, which reﬂects a given access policy, is deﬁned as a collection A
of non-empty subsets of U. That is, A ⊂ 2U \{φ}. An access structure A is called
monotone if for any B ∈ A and B ⊂ C, C ∈ A holds. We will consider in thispaper only monotone access structures.

Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

2.2

173

Linear Secret-Sharing Scheme

A secret-sharing scheme Π over a set of parties P is called a linear secret-sharing
scheme (LSSS) over Zp ([2]), if Π satisﬁes the following conditions.
1. The shares for each party form a vector over Zp
2. There exists a matrix M called the share-generating matrix for Π, of sizel × n, and a function ρ which maps each row index i of M to a party P,
ρ : {1, ..., l} → P.
To make shares for a secret s ∈ Zp , we ﬁrst choose n − 1 random values
v2 , . . . , vn ∈ Zp and form a vector v = (s, v2 , . . . , vn ). For i = 1 to l, we calculate each share λi = v · Mi , where Mi denotes the i-th row vector of M and ·denotes the formal inner product. The share λi belongs to the party ρ(i).
Looking at P as an attribute universe U, Π determines an access structure A
as (M, ρ) ([13,15]). Suppose that an attribute set S ⊂ U satisﬁes A (S ∈ A) andput IS = ρ−1 (S) ⊂ {1, . . . , l}. Then, there exists a set of constants
 {ωi ∈ Zp ; i ∈IS } called linear reconstruction constants ([2]) that satisﬁes i∈IS ωi λi = s.
These constants {ωi }i∈IS can be computed in time polynomial in the size of
M . We denote the algorithm by Recon(IS , M ). If S does not satisfy A (S ∈A), then no such constants {ωi }i∈IS exist, but instead, there is a vector w =(w1 , . . . , wn ) ∈ Znp such that w1 = 1 and w · Mi = 0 for all i ∈ IS . w also can becomputed in time polynomial in the size of M ([15]).
2.3

Key-Policy Attribute-Based KEM

Scheme. A key-policy ABKEM, KP-ABKEM, consists of four probabilistic polynomial time (PPT, for short) algorithms (Setup, KeyGen, Encap, Decap).
Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λand the attribute universe U. It returns a public key PK and a master secret key
MSK.
KeyGen(PK, MSK, A) → SKA . A key generation algorithm KeyGen takes as
input the public key PK, the master secret key MSK and an access structure A.
It returns a secret key SKA that corresponds to A.
Encap(PK, S) → (κ, ψ). Encap takes as input the public key PK and an attribute set S. It returns a random KEM key κ and its encapsulation ψ (wealso call it a ciphertext). We denote the set of all possible output (κ, ψ) of
Encap(PK, S) by [Encap(PK, S)]. If (κ̃, ψ̃) ∈ [Encap(PK, S)], then (κ̃, ψ̃) is
called consistent and otherwise, inconsistent.
Decap(PK, SKA , ψ) → κ̂. Decap takes as input the public key PK, an encapsulation ψ and a secret key SKA . It returns a decapsulation result κ̂ of ψ under
SKA . We demand correctness of KP-ABKEM that for any λ and U, and if S ∈ A,
then Pr[(PK, MSK) ← Setup(λ, U); SKA ← KeyGen(PK, MSK, A); (κ, ψ) ←Encap(PK, S); κ̂ ← Decap(PK, SKA , ψ) : κ = κ̂] = 1.

174

H. Anada et al.

∗∗
Exprmtow-sel-cca
Exprmtow-cca
A,KP-ABKEM (λ, U): //Adaptive S
A,KP-ABKEM (λ, U): //Selective S(PK, MSK) ← Setup(λ, U)(PK, MSK) ← Setup(λ, U)S ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (PK, U) S ∗ ← A(λ, U)(κ∗ , ψ ∗ ) ← Encap(PK, S ∗ )(κ∗ , ψ ∗ ) ← Encap(PK, S ∗ )K
G(PK,MSK,·),D
EC(PK,SK
,·)
∗
·
∗
(ψ )
κˆ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (PK, ψ ∗ )κˆ ← A∗∗ˆ
If κ = κ Return Win else Return Lose If κˆ∗ = κ∗ Return Win else Return Lose

Fig. 1. The experiment of an adversary A that executes a chosen-ciphertext attack on
one-wayness of KP-ABKEM. The left side: the case of adaptive S ∗ ; the right side: the caseof selective S ∗ .

Chosen-Ciphertext Attack on One-Wayness of KP-ABKEM and Security. The following experiment Exprmtow-cca
A,KP-ABKEM (λ, U) of an adversary A
deﬁnes the game of chosen-ciphertext attack on one-wayness of KP-ABKEM (theOW-CCA game).
In the experiment, A issues two types of queries. One is key-extraction queries
to the key-generation oracle KG. Giving an attribute set Ai , A queries KG(PK,MSK, ·) for the secret key SKAi . Another is decapsulation queries to the decapsulation oracle DEC. Giving a pair (Aj , ψj ) of an attribute set and an encapsulation,
A queries DEC(PK, SK· , ·) for the decapsulation result κ̂j . Here an attribute set
Sj , which is used to generate a ciphertext, is included in ψj . When Sj ∈ Aj ,
κ̂j =⊥ is replied to A.
The attribute set S ∗ declared by A is called a target attribute set. The encapsulation ψ ∗ is called a challenge ciphertext. Two restrictions are imposedon A concerning S ∗ and ψ ∗ . In key-extraction queries, each attribute set Ai
must satisfy S ∗ ∈/ Ai . In decapsulation queries, each pair (Aj , ψj ) must satisfy
S ∗ ∈ Aj ∨ ψj = ψ ∗ . Both types of queries are at most qk and qd times in total,
respectively, which are bounded by a polynomial in λ.
The advantage of A over KP-ABKEM in the OW-CCA game is deﬁned as 1
def

ow-ccaAdvow-cca
A,KP-ABKEM (λ) = Pr[ExprmtA,KP-ABKEM (λ, U) returns Win].

KP-ABKEM is called secure against chosen-ciphertext attacks on one-wayness if,
for any PPT A and for any U, Advow-cca
A,KP-ABKEM (λ) is negligible in λ.
Selective Security. In the selective game on a target attribute set (OW-selCCA game), A declares S ∗ before A receives PK. Exprmtow-sel-cca
A,KP-ABKEM (λ, U) deﬁnes
the selective game. The advantage in the OW-sel-CCA game is deﬁned as
def

ow-sel-cca
Advow-sel-cca
A,KP-ABKEM (λ) = Pr[ExprmtA,KP-ABKEM (λ, U) returns Win].

KP-ABKEM is called selectively secure against chosen-ciphertext attacks on onewayness if, for any PPT A and for any U, Advow-sel-cca
A,KP-ABKEM (λ) is negligible in λ.
1

Although we follow the convention, we should write the advantage as a function of
λ and u: Advow-cca
A,KP-ABKEM (λ, u), where u is the size of the attribute universe U.

Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

2.4

175

Bilinear Map

Let G and GT be two multiplicative cyclic groups of prime order p. We call Ga source group and GT a target group. Let g be a generator of G and e be abilinear map, e : G × G → GT . The map e satisﬁes
1. Bilinearity: for all u, v ∈ G and a, b ∈ Zp , we have e(ua , v b ) = e(u, v)ab .
2. Non-degeneracy: e(g, g) = idGT (: the identity element of the group GT ).
Groups and a bilinear map are generated by a PPT algorithm Grp on input λ:(p, G, GT , g, e) ← Grp(λ). We assume that the group operation in G and GT
and the bilinear map e : G × G → GT are computable in time polynomial in λ.
2.5Computational Bilinear Diﬃe-Hellman Assumption with Gap
on Target GroupWe introduce in this paper a new number theoretic assumption, which we call theComputational Bilinear Diﬃe-Hellman Assumption with Gap on Target Group.
Let e : G × G → GT be a bilinear map. Let a, b, c ∈ Zp , a, b, c = 0, be chosen
at random. Put A := g a , B := g b , C := g c . Then our new assumption says
it is at most with a negligible probability in λ that, for any PPT algorithm
B given input (g, A, B, C), to output Z = e(g, g)abc ∈ GT , even with the aidof the decisional Diﬃe-Hellman oracle for GT : DDHGT (·, ·, ·, ·). Here a tuple(g, gz1 , g z2 , g z3 ) ∈ G4T (g := e(g, g)) is called a Diﬃe-Hellman tuple (in GT )if z1 z2 = z3 . The oracle DDHGT returns True or False according to whether
an input tuple is a Diﬃe-Hellman tuple or not, respectively. The probability for
B to output e(g, g)abc is denoted as Advc-bdh-gap
B,(e,G,GT ) (λ) (the advantage of B in thecomputational BDH game with gap on GT ). Note that the above assumption is
diﬀerent from the Gap Bilinear Diﬃe-Hellman Assumption [6].
2.6Target Collision Resistant Hash Functions

Target collision resistant (TCR) hash functions [12] are treated as a family
Hfamλ = {Hμ }μ∈HKeyλ . The advantage Advtcr
CF ,Hfamλ (λ) of a PPT algorithm
CF over Hfamλ is deﬁned as the success probability to ﬁnd a target collision.

3

Attribute-Based Identiﬁcation

In this section, we deﬁne a notion of prover-policy attribute-based identiﬁcation(PP-ABID), a concurrent man-in-the-middle attack on PP-ABID and security
against it. The case of veriﬁer-policy ABID is described in Appendix A in a dual
manner to PP-ABID on an access structure A and an attribute set S.
3.1

Prover-Policy ABID

Scheme. PP-ABID consists of four PPT algorithms (Setup, KeyGen, P, V).

176

H. Anada et al.

Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λ andthe attribute universe U. It outputs a public key PK and a master secret key
MSK.
KeyGen(PK, MSK, A) → SKA . A key-generation algorithm KeyGen takes as
input the public key PK, the master secret key MSK and an access structure A.
It outputs a secret key SKA corresponding to A.
P(PK, SKA ) and V(PK, S). P and V are interactive algorithms called a proverand a veriﬁer, respectively. P takes as input the public key PK and the secretkey SKA . Here the secret key SKA is given to P by an authority that runs
KeyGen(PK,MSK,A). V takes as input the public key PK and an attribute set
S. P is provided V’s attribute set S by the ﬁrst round. P and V interact witheach other for some, at most constant rounds. Then, V ﬁnally returns its decision
bit b. b = 1 means that V accepts P in the sense P has a secret key SKA such that
S satisﬁes A. b = 0 means that V rejects P. We demand correctness of PP-ABID
that for any λ and U, and if S ∈ A, then Pr[(PK, MSK) ← Setup(λ, U); SKA ←KeyGen(PK, MSK, A); b ← P(PK, SKA ), V(PK, S) : b = 1] = 1.
3.2

Concurrent Man-in-the-Middle Attack on PP-ABID and
Security

An adversary A’s objective is impersonation. A tries to make a veriﬁer V accept
with a target attribute set S ∗ . The following experiment Exprmtcmim
A,PP-ABID (λ, U)of an adversary A deﬁnes the game of concurrent man-in-the-middle attack(cMiM attack, for short) on PP-ABID.
∗
Exprmtcmim
A,PP-ABID (λ, U): //Adaptive S(PK, MSK) ← Setup(λ, U)qp∗
Exprmtsel-cmim
A,PP-ABID (λ, U): //Seletive S(PK, MSK) ← Setup(λ, U)S ∗ ← AKG(PK,MSK,·),Pi (PK,SKAi )|i=1 (PK, U) S ∗ ← A(λ, U)qpqp
b ← AKG(PK,MSK,·),Pi (PK,SKAi )|i=1 ,b ← AKG(PK,MSK,·),Pi (PK,SKAi )|i=1 (PK),V(PK, S ∗ )V(PK, S ∗ )If b = 1 Return Win else Return Lose
If b = 1 Return Win else Return Lose
Fig. 2. The experiment of an adversary A that executes a cMiM attack on PP-ABID.
The left side: the case of adaptive S ∗ ; the right side: the case of selective S ∗ .

In the experiment, A issues key-extraction queries to the key-generation oracle KG. Giving an access structure Ai , A queries KG(PK, MSK, ·) for the secret key SKAi . In addition, the adversary A invokes provers Pj (PK, SKAj ) (j =1, . . . , qp , . . . , qp ) by giving an access structure Aj of A’s choice. Acting as a
veriﬁer with an attribute set Sj , A interacts with each Pj .
The attribute set S ∗ declared by A is called a target attribute set. Two restrictions are imposed on A concerning S ∗ . In key-extraction queries, each accessstructure Ai must satisfy S ∗ ∈/ Ai . In interactions with each prover, every transcript of messages of a whole interaction with a prover Pj (PK, SKAj ) must not beAttribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

177

equal to a transcript of messages of a whole interaction with a veriﬁer V(PK, S ∗ )(that is, a mere relay of messages is prohibited in the game of man-in-the-middle
attack), or, S ∗ ∈/ Aj . The number of key-extraction queries and the number of
invoked provers are at most qk and qp in total, respectively, which are bounded
by a polynomial in λ.
The advantage of A over PP-ABID in the game of cMiM attack is deﬁned as
def

cmim
Advcmim
A,PP-ABID (λ) = Pr[ExprmtA,PP-ABID (λ, U) returns Win].

PP-ABID is called secure against cMiM attacks if, for any PPT A and for any
attribute universe U, Advcmim
A,PP-ABID (λ) is negligible in λ.
Selective Security. In the selective game on a target attribute set (the game ofsel-cMiM attack), A declares S ∗ before A receives PK. Exprmtsel-cmim
A,PP-ABID (λ, U)deﬁnes the selective game. The advantage in the game of sel-cMiM attack is
deﬁned as
def

sel-cmimAdvsel-cmim
A,PP-ABID (λ) = Pr[ExprmtA,PP-ABID (λ, U) returns Win].

PP-ABID is called selectively secure against cMiM attacks if, for any PPT A andfor any U, Advsel-cmim
A,PP-ABID (λ) is negligible in λ.

4Generic Conversions from ABKEM to ABIDIn this section, we provide a generic conversion from a key-policy ABKEM toa prover-policy ABID. The conversion yields a challenge-and-response protocolof encapsulation-and-decapsulation. We show that KP-ABKEM only has to be
OW-CCA secure for the obtained PP-ABID to be cMiM secure. A generic conversion from a ciphertext-policy ABKEM to a veriﬁer-policy ABID is provided
in a similar way (in the full version).
4.1

Generic Conversion from KP-ABKEM to PP-ABID

Let KP-ABKEM= (KEM.Setup, KEM.KeyGen, KEM.Encap, KEM.Decap) be a
KP-ABKEM. Then PP-ABID= (Setup, KeyGen, Encap, Decap) is obtained asa challenge-and-response protocol of encapsulation-and-decapsulation. Figure 3
shows this conversion. Setup of PP-ABID uses KEM.Setup. KeyGen of PP-ABID
uses KEM.KeyGen. The veriﬁer V, given a public key PK and an attribute set S
as input, invokes the encapsulation algorithm KEM.Encap on (PK, S). V gets a
return (κ, ψ). V sends the encapsulation ψ to the prover P as a challenge message.
P , given a public key PK and the secret key SKA as input, and receiving ψ as amessage, invokes the decapsulation algorithm KEM.Decap on (PK, SKA , ψ). P
gets a return κ̂. P sends the decapsulation κ̂ to V as a response message. Finally,V, receiving κ̂ as a message, veriﬁes whether κ̂ is equal to κ. If so, then V returns
1 and otherwise, 0.

178

H. Anada et al.

Setup(λ, U):(PK, MSK) ← KEM.Setup(λ, U)
Return (PK, MSK)

KeyGen(PK, MSK, A):
SKA ← KEM.KeyGen(PK, MSK, A)
Return (SKA )P(PK, SKA ):V(PK, S):(κ, ψ) ← KEM.Encap(PK, S)ψ

Receiving ψ as input:κ̂ ← KEM.Decap(PK, SKA , ψ)←− Send ψ to P

Send κ̂ to V−→ Receiving κ̂ as input:
If κ̂ = κ then b := 1 else b := 0, Return bκ̂Fig. 3. A generic conversion from KP-ABKEM to PP-ABID

Theorem 1. If KP-ABKEM is OW-CCA secure, then the derived PP-ABID is cMiM
secure. More precisely, for any given PPT adversary A on PP-ABID in the gameof cMiM attack, and for any given attribute universe U, there exists a PPT adversary B on KP-ABKEM in the OW-CCA game that satisﬁes the following tight
reduction.
ow-ccaAdvcmim
A,PP-ABID(λ)  AdvB,KP-ABKEM(λ).

Proof. Employing any given PPT cMiM adversary A on PP-ABID in Theorem 1,
we construct a PPT OW-CCA adversary B on KP-ABKEM. The left side of Figure
4 shows the construction.
On input (PK, U), B initializes its inner state and invokes A on (PK, U).
When A issues a key-extraction query for A, B queries its key-generation oracle
KG(PK, MSK, ·) for the answer for A and gets a reply SKA . B reply SKA to A.
When A sends a challenge message (A, ψ) to a prover P, B queries its decapsulation oracle DEC(PK, SK· , ·) for the answer for (A, ψ) and gets a reply κ̂. B replyκ̂ to A. When A outputs a target attribute set S ∗ , B output S ∗ as its target attribute set. Then B receives a challenge ciphertext ψ ∗ from its challenger. WhenA queries V for a challenge message, B sends ψ ∗ to A as a challenge message.
When A sends the response message κˆ∗ to V, B returns κˆ∗ as its guess.
The view of A in B is the same as the real view of A. If A wins, then B wins.
Hence the inequality in Theorem 1 holds.

4.2

Discussion

Selective Security. The right side of Figure 4 shows the construction of B in
the game of selective S ∗ . The inequality of advantages becomesow-sel-cca
Advsel-cmim
A,PP-ABID (λ)  AdvB,KP-ABKEM (λ).

Resettable Security. We note that the derived PP-ABID is prover-resettable inthe sense in [4] because underlying KP-ABKEM has the OW-CCA security. PP-ABID
is also veriﬁer-resettable because PP-ABID consists of two rounds interaction.

Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

179

B(PK, U): //Selective S ∗B(PK, U): //Adaptive S ∗//Set up//Set up
Initialize inner state, Invoke A on (PK, U) Initialize inner state, Invoke A on (λ, U)//Answering A’s Queries//Answering A’s QueriesS ∗ ← A(λ, U)
When A issues a key-ext. query for A
Output S ∗ as its target attribute set
SKA ← KG(PK, MSK, A)
Receive ψ ∗ as a chal. ciphertext
Reply SKA to A
Give PK to A
When A sends a chal. msg. (A, ψ) to P
When A issues a key-ext query for Aκ̂ ← DEC(PK, SKA , ψ)
SKA ← KG(PK, MSK, A)
Send κ̂ to A as the res. msg.
When A outputs a target attribute set S ∗ When A sends a chal. msg. (A, ψ) to Pκ̂ ← DEC(PK, SKA , ψ)
Output S ∗ as its target attribute set
Send κ̂ to A as the res. msg.
Receive ψ ∗ as a chal. ciphertext
When A queries V for a chal. msg.
When A queries V for a chal. msg.
Send ψ ∗ to A as a chal. msg.
Send ψ ∗ to A as a chal. msg.
∗
When A sends the res. msg. κˆ∗ to V
When A sends the res. msg. κˆ to V∗ˆReturn κˆ∗Return κ
Fig. 4. A one-way CCA adversary B on KP-ABKEM that employs a given cMiM adversary
A on the PP-ABID. The left side: the case of adaptive S ∗ ; the right side: the case of
selective S ∗ .

5Concrete Constructions of ABKEM

In this section, we construct a concrete KP-ABKEM that is OW-sel-CCA secure.
Using the algebraic trick of Boneh and Boyen [3] and Kiltz [11], we build an enhanced version, KP-ABKEM, of the KP-ABKEM of Ostrovsky, Sahai and Waters [13](OSW, for short). Then we obtain our concrete PP-ABID by applying the genericconversion. (Our concrete CP-ABKEM and VP-ABID is described in Appendix C).
5.1

Our Enhanced OSW KP-ABKEM and PP-ABID

The construction of our concrete KP-ABKEM is described in Figure 5. We only explain the enhanced part from the original [13]. We indicate the part of the originalscheme by the index: cpa . In Setup, a second component α2 ∈ Zp is added to themaster secret key MSKcpa . Also, the corresponding Y2 := e(g, g)α2 b and a hashkey η is added to the public key PKcpa . In KeyGen, components in SKcpa,A are
doubled reﬂecting the index 2 (but randomness is chosen independently of index
1). So computational cost for KeyGen is doubled. In Encap, a temporal KEM
key κ2 is generated in the same way as κ1 . Next, a hash value τ ← Hη (ψcpa )and a check sum d := κτ1 κ2 are computed. Then (κ, ψ) := (κ1 , (ψcpa , d)) is a
new KEM key and encapsulation. In Decap, ﬁrst, Decapcpa is executed twice
for index 1 and 2 to yield κˆ1 and κˆ2 . Then, whether ψcpa is a consistent ciphertext and (e(g, g), Y1τ Y2 , e(C  , g), d) is a Diﬃe-Hellman tuple is veriﬁed. These
two conditions are veriﬁed by one equation κˆ1 τ κˆ2 = d, though the veriﬁcation
equation overlooks inconsistent ψcpa only with a negligible probability. Finally,κ̂ := κˆ1 is returned only when the veriﬁcation equation holds.

180

H. Anada et al.

Setup(λ, U):(p, G, GT , g, e) ← Grp(λ)
For x = 1 to u: Tx ← G
b ← Zp , B := g b , α1 , α2 ← Zp
Y1 := e(g, g)α1 b , Y2 := e(g, g)α2 b
η ← HKeyλPK := (g, T1 , . . . , Tu , B, Y1 , Y2 , η)MSK := (α1 , α2 )Return (PK, MSK)

KeyGen(PK, MSK, A = (M, ρ)):For k = 1, 2: For j = 2 to n: vk,j ← Zp
For k = 1, 2: v k := (αk , vk,2 , . . . , vk,n )For i = 1 to l: λk,i := v k · Mi
For k = 1, 2: For i = 1 to l:rk,irk,i ← Zp , Kk,i := B λk,i Tρ(i),rk,iLk,i := g
SKA := (((Kk,i , Lk,i ); i = 1, . . . , l); k = 1, 2)
Return SKA

Encap(PK, S):
Decap(PK, SKA , ψ):/ A Return κ̂ :=⊥s ← Zp , C  = g s , For x ∈ S : Cx = Txs If S ∈else IS := ρ−1 (S)ψcpa := (S, C  , (Cx ; x ∈ S)){ωi ; i ∈ IS } ← Recon(IS , M )τ ← Hη (ψcpa )For k =1, 2:
For k = 1, 2: κk := Yks ; d := κτ1 κ2
κˆk := i∈IS (e(Kk,i , C  )/e(Lk,i , Cρ(i) ))ωi
(κ, ψ) := (κ1 , (ψcpa , d))Return (κ, ψ)τ ← Hη (ψcpa )If κˆ1 τ κˆ2 = d then κ̂ :=⊥ else κ̂ := κˆ1
Return κ̂
Fig. 5. Our concrete KP-ABKEM (an enhanced OSW KP-ABKEM)

Theorem 2. If the computational bilinear Diﬃe-Hellman assumption with gap
on target group holds, and an employed hash function family has target collisionresistance, then our KP-ABKEM is OW-sel-CCA secure. More precisely, for any
given PPT adversary A on KP-ABKEM in the OW-sel-CCA game and for any
given attribute universe U, there exist a PPT adversary B on (e, G, GT ) in thecomputational BDH game with gap on GT and a PPT target collision ﬁnder CF
on Hfamλ that satisfy the following tight reduction.
c-bdh-gap
tcr
Advow-sel-cca
A,KP-ABKEM (λ)  AdvB,(e,G,GT ) (λ) + AdvCF ,Hfamλ (λ).

5.2

Proof for Theorem 2

Using any given OW-sel-CCA adversary A as a subroutine, we construct a PPT
solver B of the problem of the computational bilinear Diﬃe-Hellman assumption
with gap on target group, as follows.
Set Up. B is given a random instance of the problem, g, A = g a , B = g b , C =g c , as input. B initializes its inner state. B chooses an attribute universe U ={1, . . . , u} at random. B invokes A on input (λ, U).
In return, B receives a target attribute set S ∗ ∈ U from A, For each x =1, . . . , u, B puts each component Tx of PK as
If x ∈ S ∗ then tx ← Zp , Tx := g tx else θx , ηx ← Zp s.t. θx = 0, Tx := B θx g ηx .
Here, in else case, we have implicitly set tx := bθx + ηx . B sets Y1 := e(A, B) =e(g, g)ab and PKcpa := (g, T1 , . . . , Tu , B, Y1 ). Here we have implicitly set α1 := a.
Challenge ciphertext are computed as follows (we implicitly set s∗ = c):Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

181

∗

∗
ψcpa
:= (S ∗ , C ∗ = g s := C, (Cx∗ := C tx , x ∈ S ∗ )).

Then a public key PK and a whole challenge ciphertext ψ ∗ is computed as∗∗η ← HKeyλ , τ ∗ ← Hη (ψcpa), μ ← Zp , Y2 := e(B, g)μ /Y1τ ,∗, d∗ ).
PK := (PKcpa , Y2 , η), d∗ := e(B, C ∗ )μ , ψ ∗ := (ψcpa

Here we have an implicit relation α2 b = bμ − α1 bτ ∗ , b = 0. That is,α2 = μ − α1 τ ∗ .

(1)

B inputs (PK, ψ ∗ ) to A.
Answering A’s Queries. (1) Key-Extraction Queries. When A issues a
key-extraction query for an attribute set A = (M, ρ), where M is of size l × n,
B has to reply a corresponding secret key SKA .
B computes a vector w = (w1 , . . . , wn ) ∈ Znp such that w1 = 1 and for all/ A, so such w surely exists. Bi ∈ ρ−1 (S ∗ ), w · Mi = 0. Note here that S ∗ ∈chooses random values u1,1 , . . . , u1,n ∈ Zp and put u1 := (u1,1 , . . . , u1,n ). Thenwe implicitly set v 1 := u1 + (a − u1,1 )w.
Here for each i = 1, . . . , l, B can compute g λ1,i as g Mi ·v1 = g Mi ·(u1 −u1,1 w)
Mi ·w
A. Then B computes the index 1 components of SKS asr

1,i
For i = 1 to l : If i ∈ ρ−1 (S ∗ ) then r1,i ← Zp , K1,i := B Mi ·u1 Tρ(i), L1,i := g r1,ielse r1,i← Zp , K1,i := (g λ1,i )−ηρ(i) /θρ(i) (B θρ(i) g ηρ(i) )r1,i , L1,i := (g λ1,i )−1/θρ(i) g r1,i .

Here, in else case, we implicitly set r1,i := r1,i− λ1,i /θρ(i) .
Now B has to compute the index 2 components K2,i , L2,i for i = 1, . . . , l. To
do so, B chooses random values u2 ,1 , . . . , u2 ,n , r2 ,i (or r2  ,i ) ∈ Zp and computes
K2 ,i , L2 ,i , i = 1, . . . , l just in the same way as to the index 1. Then B converts
them as follows:∗∗

K2,i := B Mi,1 μ (K2 ,i )−τ , L2,i := (L2 ,i )−τ , i = 1, . . . , l.
Then B replies SKA = (((Kk,i , Lk,i ); i = 1, . . . , l); k = 1, 2) to A.
(2) Decapsulation Queries. When A issues a decapsulation query for (A, ψ =(ψcpa , d)) (where ψcpa is about S), B has to reply the decapsulation κ̂ to A. To
do so, B computes as follows. (Note that the oracle DDHGT is accessed.)
If S ∈/ A then κ̂ :=⊥else If Verify(PKcpa , ψcpa ) = False then κ̂ :=⊥else τ ← Hη (ψcpa ) If DDHGT (e(g, g), Y1τ Y2 , e(C  , g), d) = False then κ̂ :=⊥else If τ = τ ∗ then Abort //Call this case Abort∗

else κ̂ := (d/e(B, C  )μ )1/(τ −τ )

182

H. Anada et al.

where Verify is the following PPT algorithm to check consistency of ψcpa :Verify(PKcpa , ψcpa ) :For x ∈ S : If e(Tx , C  ) = e(Cx , g) then Return False
Return True.
Guess. When A returns A’s guess κˆ∗ , B returns Z := κˆ∗ as B’s guess.
B can perfectly simulate the real view of A until the case Abort happens. To
see why, we prove the following claims. (The proofs will be in the full version.)
Claim 1. The reply SKA to a key-extraction query is a perfect simulation.

Claim 2. The reply κ̂ to a decapsulation query is a simulation that is computationally indistinguishable from a real, until the case Abort happens.
∗
Claim 3. The challenge ciphertext ψ ∗ = (ψcpa, d∗ ) is correctly distributed.



Now we are ready to evaluate the advantage of B in the OW-sel-CCA game.
First, the following claim holds. (The proof will be described in the full version.)
Claim 4. The probability that Abort occurs is negligible in λ. More precisely,
the following equality holds: Pr[Abort] = Advtcr

CF ,Hfamλ (λ).
By deﬁnition, A wins in the OW-sel-CCA game if and only if κ̂∗ is correctly∗∗
guessed. That is, κˆ∗ = Y1s = e(g, g)abs = e(g, g)abc . This is the deﬁnition that
B succeeds in computing the answer for the given instance (g, A, B, C).
Therefore, the probability that B wins is equal to the probability that A wins
and Abort never occurs. So we have:
Pr[B wins] = Pr[(A wins) ∧ (¬Abort)]  Pr[A wins] − Pr[Abort].
Substituting advantages and using the equality in Claim 4, we have:ow-sel-cca
tcr
Advc-bdh-gap
B,(e,G,GT ) (λ)  AdvA,KP-ABKEM (λ) − AdvCF ,Hfamλ (λ).

This is what we should prove.



Theorem 3 (Corollary to Theorem 1 and 2). Our PP-ABID is selectively
secure against cMiM attacks. More precisely, the following inequality holds:
c-bdh-gap
tcr
Advsel-cmim
A,PP-ABID(λ)  AdvB,(e,G,GT ) (λ) + AdvCF ,Hfamλ (λ).

Figure 6 shows an interaction of our PP-ABID.

Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions
P(PK = (g, T1 , . . . , Tu , B, Y1 , Y2 , η),rk,iSKA = (((Kk,i = B λk,i Tρ(i),rk,iLk,i = g);i = 1, . . . , l); k = 1, 2)):

ψ

183

V(PK, S):s ← Zp , C  := g s , For x ∈ S : Cx := Txs
ψcpa := (S, C  , (Cx ; x ∈ S))
τ ← Hη (ψcpa )For k = 1, 2: κk := Yks ; d := κτ1 κ2(κ, ψ) := (κ1 , (ψcpa , d))←− Send ψ to P
Receiving ψ as input:
If S ∈ A then κ̂ :=⊥else τ ← Hη (ψcpa ), IS := ρ−1 (S){ωi ; i ∈ IS } ← Recon(IS , M )For k =1, 2:
κˆk := i∈IS (e(KK,i , C  )/e(LK,i , Cρ(i) ))ωi
If κˆ1 τ κˆ2 = d then κ̂ :=⊥ else κ̂ := κˆ1
Send κ̂ to Vκ̂−→ Receiving κ̂ as input:
If κ̂ = κ then b := 1 else b := 0, Return b
Fig. 6. An interaction of our concrete PP-ABID

5.3

Discussion

Anonymity. Consider the following experiment in Figure 7. (In the experiment,
an adversary A interacts with P(PK, SKAb ) as a veriﬁer with S ∗ .)We say that PP-ABID have anonymity if, for any PPT A and for any U,
defanonymAdvanonym
A,PP-ABID (λ) = |Pr[ExprmtA,PP-ABID (λ, U) returns Win] − 1/2| is negligiblein λ. Our concrete PP-ABID possesses the anonymity because, in the case that
ψ is inconsistent, the randomness in SKAb is not canceled out correctly in thecomputation of a response message κˆb .
Exprmtanonym
A,PP-ABID (λ, U):(PK, MSK) ← Setup(λ, U), (A0 , A1 , S ∗ ) ← A(PK)/ A0 ∧ S ∗ ∈/ A1 )
s.t. (S ∗ ∈ A0 ∧ S ∗ ∈ A1 ) ∨ (S ∗ ∈SKA0 ← KeyGen(PK, MSK, A0 ), SKA1 ← KeyGen(PK, MSK, A1 )b ← {0, 1}, b̂ ← AP(PK,SKAb ) (PK, SKA0 , SKA1 )If b = b̂ Return Win else Return Lose
Fig. 7. The anonymity experiment of an adversary A on PP-ABID

Large Universe Case. If the attribute universe U is large, we have to modify
our concrete schemes to make security reductions in time polynomial in λ. As
is proposed by Waters [15], we use for x ∈ U a hashed value H(x) instead of Tx(and hence Tx is removed from PK). Although the resulting schemes are proved
to be secure only in the random oracle model, we get relief from rewriting the
public key PK each time when a new attribute x is added.
Exiting the Gap Assumption. Instead of the oracle DDHGT , we can apply
the twin Diﬃe-Hellman trapdoor test of Cash, Kiltz and Shoup [8] in the security

184

H. Anada et al.

proofs. In compensation, the resulting schemes become to have a twice as longsecret key and twice as much computational cost in decapsulation.
Security against Adaptive Target. To attain the adaptive security in the
OW-CCA game, we can apply our enhancing technique to the dual system encryption of Lewko, Okamoto, Sahai, Takashima and Waters [10] in the random
oracle model.

6Conclusions

We proposed PP-ABID and VP-ABID. We established a design principle. We
constructed concrete KP-ABKEM and CP-ABKEM with the OW-CCA security.
Finally, we obtained concrete PP-ABID and VP-ABID. Functional tickets andfunctional gates are realized by those PP-ABID and VP-ABID, respectively.

References
1. Anada, H., Arita, S.: Identiﬁcation Schemes from Key Encapsulation Mechanisms.
In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp.
59–76. Springer, Heidelberg (2011)
2. Beimel, A.: Secure schemes for secret sharing and key distribution. Ph.D. thesis,
Israel Institute of Technology, Technion, Haifa, Israel (1996)
3. Boneh, D., Boyen, X.: Eﬃcient Selective-ID Secure Identity-Based Encryption
Without Random Oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT
2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
4. Bellare, M., Fischlin, M., Goldwasser, S., Micali, S.: Identiﬁcation Protocols Secure against Reset Attacks. In: Pﬁtzmann, B. (ed.) EUROCRYPT 2001. LNCS,
vol. 2045, pp. 495–511. Springer, Heidelberg (2001)
5. Bellare, M., Palacio, A.: GQ and Schnorr Identiﬁcation Schemes: Proofs of Security
against Impersonation under Active and Concurrent Attacks. In: Yung, M. (ed.)
CRYPTO 2002. LNCS, vol. 2442, pp. 162–177. Springer, Heidelberg (2002)
6. Baek, J., Safavi-Naini, R., Susilo, W.: Eﬃcient Multi-receiver Identity-Based Encryption and Its Application to Broadcast Encryption. In: Vaudenay, S. (ed.) PKC
2005. LNCS, vol. 3386, pp. 380–397. Springer, Heidelberg (2005)
7. Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty Computation from Threshold
Homomorphic Encryption. In: Pﬁtzmann, B. (ed.) EUROCRYPT 2001. LNCS,
vol. 2045, pp. 280–300. Springer, Heidelberg (2001)
8. Cash, D., Kiltz, E., Shoup, V.: The Twin Diﬃe-Hellman Problem and Applications.
In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 127–145. Springer,
Heidelberg (2008); Full version available at Cryptology ePrint Archive, 2008/067,
http://eprint.iacr.org/
9. Gennaro, R.: Multi-trapdoor Commitments and their Applications to Proofs ofKnowledge Secure Under Concurrent Man-in-the-Middle Attacks. In: Franklin, M.
(ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 220–236. Springer, Heidelberg (2004)
10. Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp.
62–91. Springer, Heidelberg (2010); Full version available at IACR Cryptology
ePrint Archive, 2010/110, http://eprint.iacr.org/

Attribute-Based Identiﬁcation: Deﬁnitions and Eﬃcient Constructions

185

11. Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: Halevi, S.,
Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581–600. Springer, Heidelberg(2006)
12. Naor, M., Yung, M.: Universal One-Way Hash Functions and their Cryptographic
Applications. In: The 21st Symposium on Theory of Computing 1989, pp. 33–43.
Association for Computing Machinery, New York (1989)
13. Ostrovsky, R., Sahai, A., Waters, B.: Attribute-based encryption with nonmonotonic access structures. In: ACM Conference on Computer and Communications Security, pp. 195–203 (2007)
14. Schnorr, C.P.: Eﬃcient Identiﬁcation and Signatures for Smart Cards. In: Brassard,
G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)
15. Waters, B.: Ciphertext-Policy Attribute-Based Encryption: An Expressive, Eﬃcient, and Provably Secure Realization. In: Catalano, D., Fazio, N., Gennaro,R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011), Full version available at IACR Cryptology ePrint Archive,2008/290,
http://eprint.iacr.org/
16. Yamada, S., Attrapadung, N., Santoso, B., Schuldt, J.C.N., Hanaoka, G., Kunihiro,
N.: Veriﬁable Predicate Encryption and Applications to CCA Security and Anonymous Predicate Authentication. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.)
PKC 2012. LNCS, vol. 7293, pp. 243–261. Springer, Heidelberg (2012)
17. Yilek, S.: Resettable Public-Key Encryption: How to Encrypt on a Virtual Machine. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 41–56. Springer,
Heidelberg (2010)

A

Veriﬁer-Policy ABIDWe deﬁne a notion of veriﬁer-policy attribute-based identiﬁcation (VP-ABID).
Scheme. VP-ABID consists of four PPT algorithms (Setup, KeyGen, P, V).
Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λ andthe attribute universe U. It outputs public a public key PK and a master secretkey MSK.
KeyGen(PK, MSK, S) → SKS . A key-generation algorithm KeyGen takes as
input the public key PK, the master secret key MSK and an attribute set S. It
outputs a secret key SKS corresponding to S.
P(PK, SKS ) and V(PK, A). P and V are interactive algorithms called a proverand a veriﬁer, respectively, which are deﬁned in a similar way as in Section
3.1. A cMiM attack on VP-ABID is deﬁned in a similar way as in Section 3.2.
CP-ABKEM=(Setup,KeyGen,Encap,Decap) is deﬁned in a dual manner to
KP-ABKEM on an access structure A and an attribute set S. Then a generic conversion from CP-ABKEM to VP-ABID is deﬁned in a similar way as in Section 4.1.
Theorem 4. If CP-ABKEM is OW-CCA secure, then the derived VP-ABID iscMiM secure.

186

B

H. Anada et al.

Computational Parallel Bilinear Diﬃe-Hellman
Exponent Assumption with Gap on Target GroupLet a, s, b1 , . . . , bq ∈ Zp , all of which is not zero, be chosen at random. Let y :=
q
q+2
2q
q
q+2
(g, g s , g a , . . . , g (a ) , g (a ) , . . . , g (a ) , ∀1jq g sbj , g a/bj , . . . , g (a /bj ) , g (a /bj ) ,2qq. . . , g (a /bj ) , ∀1j,kq,k=j g asbk /bj , . . . , g a sbk /bj ). Then our new assumption says
it is at most with a negligible probability in λ that, for any PPT algorithm B
q+1
given input y (parametrized by q), to output Z = e(g, g)a s ∈ GT , even withthe aid of the oracle DDHGT (·, ·, ·, ·).

C

Our Enhanced Waters CP-ABKEM and VP-ABID

We can build an enhanced version, CP-ABKEM, of the CP-ABKEM of Waters [15].
Then we can obtain our concrete VP-ABID as in Figure 8.

P(PK = (g, T1 , . . . , Tu , A, Y1 , Y2 , η),
SKS = ((Kk = g αk Alk , Lk = g lk ,l(Kk,x = Txk ; x ∈ S); k = 1, 2))):

ψ

V(PK, A) :s ← Zp , For j = 2 to n: vj ← Zp ,v := (s, v2 , . . . , vn )For i = 1 to l: λi := v · Mi , ri ← Zp
C  := g s−ri
For i = 1 to l: Ci := Aλi Tρ(i), Di := g ri

ψcpa := (A, C , ((Ci , Di ); i = 1, . . . , l))τ ← Hη (ψcpa )For k = 1, 2: κk := Yks ; d := κτ1 κ2(κ, ψ) := (κ1 , (ψcpa , d))←− Send ψ to P
Receiving ψ as input:
If S ∈ A then κ̂ :=⊥else τ ← Hη (ψcpa ), IS := ρ−1 (S){ωi ; i ∈ IS } ← Recon(IS , M )For k = 1, 2 : κˆk := e(Kk , C )/ ωi
(e(L
,
C
)e(K
,
D
i
i ))
k
k,ρ(i)i∈IS
If κˆ1 τ κˆ2 = d then κ̂ :=⊥ else κ̂ := κˆ1
Send κ̂ to Vκ̂−→ Receiving κ̂ as input:
If κ̂ = κ then b := 1 else b := 0, Return b
Fig. 8. An interaction of our concrete VP-ABID

Theorem 5. If the computational q-parallel bilinear Diﬃe-Hellman exponent
assumption with gap on target group holds, and an employed hash function family
has target collision resistance, then our CP-ABKEM is OW-sel-CCA secure with achallenge matrix of size l∗ × n∗ , l∗ , n∗  q.
Theorem 6 (Corollary to Theorem 4 and 5). Our VP-ABID is selectively
secure against cMiM attacks.
The proof of Theorem 5 will be described in the full version.