IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 2014

1086

PAPER

Attribute-Based Identification: Definitions and Eﬃcient
Constructions∗,∗∗Hiroaki ANADA†,††a) , Seiko ARITA†b) , Members, Sari HANDA†c) , and Yosuke IWABUCHI†d) , Nonmembers

SUMMARY
We propose a notion of attribute-based identification(ABID) in two flavors: prover-policy ABID (PP-ABID) and verifier-policy
ABID (VP-ABID). In a PP-ABID scheme, a prover has an authorized access policy written as a boolean formula over attributes, while each verifier
maintains a set of attributes. The prover is accepted when his access policy
fits the verifier’s set of attributes. In a VP-ABID scheme, a verifier 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 satisfies the verifier’s access policy. Our design principle is first to construct key-policy 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 PPABID and VP-ABID, respectively, by encapsulation-and-decapsulation.
There, we show that KP-ABKEM and CP-ABKEM only have to be secureagainst chosen-ciphertext attacks on one-wayness (OW-CCA secure) for
the obtained PP-ABID and VP-ABID to be secure against concurrent manin-the-middle attacks (cMiM secure). According to the design principle,
we construct 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.
key words: access policy, attribute, identification, KEM

1.

Introduction

An identification (ID) scheme allows a prover to convincea verifier that the prover certainly knows a secret key that
corresponds to the matching public key. For example, theSchnorr protocol [11], [22] is widely recognized. In ID
schemes, the public key limits the corresponding secret key,
and also, the corresponding prover, uniquely.
In this paper, we will describe an attribute-based identification (ABID). In an ABID scheme, each entity has credentials called attributes. On the other hand, an access polManuscript received September 17, 2013.
Manuscript revised January 7, 2014.
†
The authors are with Institute of Information Security,
Yokohama-shi, 221-0835 Japan.
††
The author is with Institute of Systems, Information Technologies and Nanotechnologies (ISIT), Fukuoka-shi, 814-0001
Japan.
∗A preliminary version of this paper appeared in Proceedings of the 18th Australasian Conference on Information Security
and Privacy - ACISP 2013, Lect. Notes Comput. Sci., vol.7959,
pp.168–186, Springer-Verlag [2], under the same title.
∗∗
Supported by MEXT-Supported Program for the Strategic Research Foundation at Private Universities, 2011–2013.
a) E-mail: anada@isit.or.jpb) E-mail: arita@iisec.ac.jpc) E-mail: mgs125502@iisec.ac.jpd) E-mail: mgs123101@iisec.ac.jp
DOI: 10.1587/transfun.E97.A.1086

icy is written as a boolean formula over those attributes.
Then, a verifier can identify that a prover has a certain accesspolicy that fits the verifier’s set of attributes, or, in the dual
flavor, a verifier can identify that a prover possesses a certain set of attributes that satisfies the verifier’s access policy.
Hence, ABID schemes can be considered as an expansionof 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 scenarios of smart card
systems motivate us to apply ABID.
Functional Tickets. Suppose that we are going to stay at aresort complex, a ski 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 Lift AND [Day OR Night]] OR [Lunch OR Beer] OR[Hot Spring X]]. A functional ticket is a ticket embedded
in a smart card, which functions as an access policy overservices, as in this scenario. That is, the access policy is
chosen according to our requirements. Then the access policy is written in the smart card by the service authority ina randomized way. On the other hand, a set of attributes iswritten in each ticket-checker in a straightforward way.
Functional Gates. Suppose that we have to design a security gate system for an 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 floors, company gates,
common refreshment areas and room doors for the above
staﬀs. In this case, one solution is to use smart cards andgates with sensors. That is, an authority issues each person
a smart card in which a set of attribute data is written. Eachgate decides whether to “pass” each person carrying a smart
card according to the gate’s access policy, for instance, [Year2014] AND [[[Company A] AND [Manager]] OR [Security
Guard]]. A functional gate is a gate that functions as anaccess policy over attributes of people, as in this scenario.

c 2014 The Institute of Electronics, Information and Communication Engineers
Copyright ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1087

That is, the access policy is chosen according to kinds ofpeople which the gate should allow. Then the access policy
is implemented in the gate in a straightforward way. On theother hand, a set of attributes is written in each smart cardby the service authority in a randomized way.
1.1 Our Contributions
We propose a notion of attribute-based identification(ABID) that has two flavors corresponding to the scenarios:
prover-policy ABID and verifier-policy ABID.
Prover-Policy ABID. In a prover-policy ABID scheme (PPABID, for short), a prover has his own authorized accesspolicy, while each verifier maintains its set of attributes.
Here, the access policy is described over attributes. Sending his access policy, each prover queries an authority forhis secret key. Then, using this secret key, each prover canconvince the verifier that his access policy fits the verifier’s
set of attributes. Our PP-ABID defined in this way realizes
a functional ticket system.
Verifier-Policy ABID. In a verifier-policy ABID scheme(VP-ABID, for short), a verifier maintains its access policy,
while each prover has his own authorized set of attributes.
Here, the access policy is described over attributes. Sending his set of attributes, each prover queries an authority forhis secret key. Then, using this secret key, each prover convinces the verifier that his set of attributes satisfy the verifier’s access policy. Our VP-ABID defined in this way realizes a functional gate system.
Attack and Security Analysis. An adversary’s objective isimpersonation: giving a target set of attributes (or, a target
access policy) to a verifier, the adversary tries to make theverifier accept him.
First, to reflect 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 [21], [23]. The condition is that the adversary
cannot collect any secret key whose intrinsic access policy
fits the target set of attributes (or, whose intrinsic set of attributes satisfies the target access policy).
Our main objective is to define a model of concurrent man-in-the-middle attack (cMiM attack) in the settingof ABID. “Concurrent” means that an adversary can invoke
provers that have diﬀerent secret keys corresponding to different access policies (or, diﬀerent sets of attributes). The
adversary interacts with these provers in an arbitrarily interleaved order of messages. Then, interacting with a verifier with the target set of attributes (or, the target accesspolicy, respectively) the adversary tries to impersonate aprover. The concurrent attack modeled in this 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 prover and a verifier simultaneously. Typically,
the adversary first receives a message from the verifier, andthen, the adversary begins to interact with the prover adaptively to the verifier’s message. The MiM attack and thecMiM attack modeled in this way are real threats, especiallyto 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 that re-starting point, the adversary is allowed to change
messages as long as the interaction remains valid (as captured by the word “reset”). Such a reset attack is a strong
threat, not only to smart card systems [10] (including thefunctional tickets and functional gates described above) but
also to virtual machine services in cloud computing [25].
As our contribution, an ABID constructed using our genericconversion becomes secure against the reset attacks in bothsenses of prover-resettable and verifier-resettable [10].
It is desirable that a verifier learns nothing about aprover more than that he belongs to the set of entities thathave access policies that fit the verifier’s set of attributes (or,belongs to the set of entities that possess sets of attributes
that satisfy the verifier’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 thetrack of which is recorded. As our contribution, our concrete
ABID in Sect. 5 possesses this anonymity.
Design Principle. First, we construct key-policy andciphertext-policy attribute-based key encapsulation mechanisms (KP-ABKEM and CP-ABKEM [21], [23]). Second, we convert the KP-ABKEM and CP-ABKEM into
challenge-and-response PP-ABID and VP-ABID, respectively, by encapsulation-and-decapsulation. There, we showthat KP-ABKEM and CP-ABKEM only have to be secureagainst chosen-ciphertext attacks on one-wayness (OWCCA secure) for the obtained PP-ABID and VP-ABID to be
secure against cMiM attacks (cMiM secure). We stress thatthe security of indistinguishability against chosen-ciphertext
attacks (IND-CCA security) is excessive, and OW-CCA 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 KPABKEM of Ostrovsky, Sahai and Waters [21] (OSW, forshort) and CP-ABKEM of Waters [23]. 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 [5] and Kiltz [17] to attain
CCA security. The application is not a black-box because,
in security proofs, we have to adapt the trick to both simulations of decapsulation oracle and key-generation oracle.
Finally, our generic conversion turns obtained OW-CCA secure KP-ABKEM and CP-ABKEM into cMiM secure PPABID and VP-ABID, respectively.
New Number Theoretic Assumptions. For our eﬃcientconstructions, We introduce the Computational Bilinear
Diﬃe-Hellman Assumption with Gap on Target Group andthe Computational q-Parallel Bilinear Diﬃe-Hellman Exponent Assumption with Gap on Target Group. The validity ofthese assumptions is explained by the generic bilinear groupmodel [6] in Appendix E.

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 2014

1088

1.2 Related Works
Anonymous Credential System. Our ABID is comparable with widely studied anonymous credential system (ACfor short). AC originates from a blind signature schemeby Chaum [13], and now it has been accomplished as Microsoft’s U-Prove [4]. AC was further advanced by Camenisch et al. with group signature scheme [3], has beenaccomplished as IBM’s Idemix [12]. Those AC schemes arecharacterized by two functionalities of untraceability fromshown credentials to provers and unlinkability between credential showings. In contrast, our ABID does not have theuntraceability because, in a VP-ABID scheme, a secret-key
issuing authority knows what credentials it authorizes andgives them as a secret key to a prover. Nevertheless, our concrete ABID schemes have a kind of unlinkability because it
never leaks information to a verifier except a fact that theprover’s set of attributes satisfies the verifier’s access policy.
Furthermore, our ABID can treat any access policy written
as a boolean formula, which may includes any combinationof AND gates and OR gates. This is not the case for AC in
at least credential-showing process. And finally, a PP-ABID
scheme, in which a prover is given a secret key reflecting not
a set of attributes but an access policy, is a new notion thatis not achieved by AC.
Anonymous Deniable Predicate Authentication. We
should refer to the work of Yamada et al. [24] of verifiable predicate encryption. As an application, they provided
an anonymous deniable message authentication scheme. It
is possible to see their message authentication scheme as
an ABID scheme of challenge-and-response type like ourgeneric construction. However, it diﬀers in objectives. We
simply try to attain a 2-round, fast ABID, while they proposed a 6-round protocol for deniability. In addition, we
provide more eﬃcient concrete ABID schemes by applying
the algebraic trick ([5], [17]); a kind of (non-black box) direct chosen-ciphertext security technique [7]. In contrast,
they used their versatile generic transformation; as a result,it causes a longer secret key, a longer ciphertext and morecomputational costs for encryption and decryption than our
strategy (the diﬀerence being about O(λ2 ) in the security parameter λ). This is because the generic transformation involves a verification key of a one-time signature.
Attribute-Based Encryption. After the pioneering works
on attribute-based encryption [16] (ABE, for short), eﬃcient
KP-ABE and CP-ABE schemes are proposed [21], [23] thatare IND-CPA secure in the standard model. These ABE
schemes can naturally be considered as ABKEMs. Our concrete constructions of ABKEM in Sect. 5 are enhanced versions of these ABKEMs to attain the OW-CCA security. We
choose OSW KP-ABKEM [21] and Waters CP-ABKEM[23], which can be seen as basic schemes in the growthof attribute-based encryption, as representative examples.
Concerning a constraint of adversary’s behavior, those KPABKEM and CP-ABKEM are secure in the game of selectively declared target of attribute set and access structure,

respectively. Here “selective” means that an adversary declares the target before getting a public key. There are KPABKEM and CP-ABKEM which are secure in the game ofadaptively declared target [18] and we discuss the adaptive
case in Sect. 5.2.
Identification Scheme from KEM. Anada and Arita [1]proposed a design principle to obtain a cMiM secure ID
scheme by constructing KEM. Their concrete ID scheme ismore eﬃcient than known Σ-protocol-based cMiM secure
ID schemes, such as [15]. Our scheme can be seen as an
attribute-based version of theirs.
Attribute-Based Signature. Maji et al. [19] introduced anotion of attribute-based signature (ABS). As they noted,
it can be used as a verifier-policy ABID (sending a random
message as a challenge and getting an attribute-based signature as a response). But the VP-ABID scheme from their
Instantiation 1 needs O(λ2 ) bits for a pair of challenge andresponse messages, while the VP-ABID scheme from their
Instantiation 2 needs O(λ2 ) bits for a public key. In contrast,
our concrete VP-ABID scheme needs O(λ) bits for both apair of challenge and response messages and a public key.
1.3 Organization of the Paper
In Sect. 2, we survey the required terms. In Sect. 3, we
define the notions of PP-ABID and VP-ABID, cMiM attacks and security against it. In Sect. 4, we provide genericconversions from KP-ABKEM to PP-ABID and from CPABKEM to VP-ABID. In Sect. 5, we construct concrete KPABKEM and CP-ABKEM. Finally, we obtain concrete PPABID and VP-ABID. In Sect. 6, we present the conclusionsof our study. Because of space limitation, the case of PPABID 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 oforder p is denoted by G. The ring of the exponent domainof G, which consists of integers from 0 to p − 1 with modulo
p operation, is denoted by Z p . 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 to n oracles O1 , . . . , On , we denote it asn
AOi |i=1 . Here “concurrent” means that A accesses to oracles
in arbitrarily interleaved order of messages. A probabilityof an event E is denoted by Pr[E]. A probability of an event
E on condition that events E1 , . . . , Em occur in this order isdenoted 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ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1089

that U is small (i.e. |U| = u is bounded by 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 reflects
a given access policy, is defined as a collection A of nonempty 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 this paper only monotone accessstructures.
2.2 Linear Secret-Sharing Scheme
A secret-sharing scheme Π over a set of parties P is calleda linear secret-sharing scheme (LSSS) over Z p ([9]), if Πsatisfies the following conditions.
1. The shares for each party form a vector over Z p .
2. There exist a matrix M called the share-generating matrix
for Π, of size l × n, and a function ρ which maps each row
index i of M to a party in P, ρ : {1, ..., l} → P.
To make shares for a secret s ∈ Z p , we first choosen − 1 random values v2 , . . . , vn ∈ Z p 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, ρ) ([21], [23]). Suppose that an
attribute set S ⊂ U satisfies A (S ∈ A). Then, there exists
a set of constants {ωi ∈ Z p ; i ∈ ρ−1 (S )}called linear reconstruction constants ([9]) that satisfies i∈ρ−1 (S ) ωi λi = s.
These constants {ωi }i∈ρ−1 (S ) can be computed in time polynomial in the size of M. We denote the algorithm byRecon(ρ−1 (S ), M). If S does not satisfy A (S  A), then nosuch constants {ωi }i∈ρ−1 (S ) exist, but instead, there is a vector
 · Mi = 0 forw
 = (w1 , . . . , wn ) ∈ Znp such that w1 = 1 and w−1 also can be computed in time polynomial
all i ∈ ρ (S ). w
in the size of M ([23]).
2.3 Key-Policy Attribute-Based KEM
Scheme. A key-policy ABKEM, KP-ABKEM, consists offour probabilistic polynomial time algorithms (PPTAs, forshort): (Setup, KeyGen, Encap, Decap).
Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λ and the attribute universe U. It returns apublic 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 mastersecret key MSK and an access structure A. It returns a secretkey 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 ψ (we also 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 forany λ and U, and if S ∈ A, then Pr[(PK, MSK) ←Setup(λ, U); SKA ← KeyGen(PK, MSK, A); (κ, ψ) ←Encap(PK, S ); κ̂ ← Decap(PK, SKA , ψ) : κ = κ̂] = 1.
Chosen-Ciphertext Attack on One-Wayness of KPABKEM and Security.
The following experiment
(λ,
U)
of
an
adversary
A defines the game
Exprmtow-cca
A,KP-ABKEM
of chosen-ciphertext attack on one-wayness of KP-ABKEM(the OW-CCA game).
∗
Exprmtow-cca
A,KP-ABKEM (λ, U) : //AdaptiveS(PK, MSK) ← Setup(λ, U)S ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (PK, U)(κ∗ , ψ∗ ) ← Encap(PK, S ∗ )κˆ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (ψ∗ )Ifκˆ∗ = κ∗ then Return Win else Return LoseIn the experiment, A issues two types of queries. One
is key-extraction queries to the key-generation oracle KG.
Giving an access structure Ai , A queries KG(PK, MSK, ·)for the secret key SKAi . Another is decapsulation queries
to the decapsulation oracle DEC. Giving a pair (A j , ψ j )of an access structure and an encapsulation, A queries
DEC(PK, SK· , ·) for the decapsulation result κ̂ j . Here an attribute set S j , which is used to generate a ciphertext, is included in ψ j . When S j  A j , κ̂ 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 imposed on A concerning S ∗and ψ∗ . In key-extraction queries, each access structure Ai
must satisfy S ∗  Ai . In decapsulation queries, each pair
(A j , ψ j ) must satisfy S ∗  A j ∨ ψ j  ψ∗ . Both types ofqueries 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 defined as †Advow-cca
A,KP-ABKEM (λ)
def= Pr[Exprmtow-cca
A,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 atarget attribute set (OW-sel-CCA game), A declaresS ∗ before A receives PK. The following experiment
Exprmtow-sel-cca
A,KP-ABKEM (λ, U) defines the selective game.
∗
Exprmtow-sel-cca
A,KP-ABKEM (λ, U) : //SelectiveS(PK, MSK) ← Setup(λ, U)†

More rigorously, we have to treat the right-hand side as
sup|U|:poly(λ) {Pr[Exprmt(game)(PPTA),(scheme) (λ, U) returns Win]}.

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 20141090

S ∗ ← A(λ, U)(κ∗ , ψ∗ ) ← Encap(PK, S ∗ )algorithm CF , a collision finder, we consider the following
experiment (the game of target collision resistance).

κˆ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (PK, ψ∗ )Ifκˆ∗ = κ∗ then Return Win else Return Lose

Exprmttcr
CF ,Hfamλ (λ)
m∗ ← CF (λ), μ ← HKeyλ , m ← CF (μ)
If m∗  m ∧ Hμ (m∗ ) = Hμ (m) then Return Win
else Return Lose.

The advantage in the OW-sel-CCA game is defined as
Advow-sel-cca
A,KP-ABKEM (λ)
def= Pr[Exprmtow-sel-cca
A,KP-ABKEM (λ, U) returns Win].

KP-ABKEM is called selectively secure against chosenciphertext attacks on one-wayness if, for any PPT A andfor any U, Advow-sel-cca
A,KP-ABKEM (λ) is negligible in λ.
2.4 Bilinear Map
Let G and GT be two multiplicative cyclic groups of prime
order p. We call G a source group and GT a target group. Let
g be a generator of G and e be a bilinear map, e : G × G →GT . The map e satisfies the following conditions:
1. Bilinearity: ∀u, v ∈ G, ∀a, b ∈ Z p , e(ua , vb ) = e(u, v)ab ,2. Non-degeneracy: e(g, g)  (the identity element of 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 λ.

Then we define CF ’s advantage over Hfamλ in the game oftarget collision resistance as
def

tcr
Advtcr
CF ,Hfamλ (λ) = Pr[ExprmtCF ,Hfamλ (λ) returns Win].

We say that Hfamλ is a TCR function family if, for any PPT
algorithm CF , Advtcr
CF ,Hfamλ (λ) is negligible in λ. TCR hashfunction families can be constructed from a one-way function [20].
3.

Attribute-Based Identification

In this section, we define a notion of prover-policy attributebased identification (PP-ABID), a concurrent man-in-themiddle attack on PP-ABID and security against it. The caseof verifier-policy ABID goes in a dual manner to PP-ABID
on an access structure A and an attribute set S and is described in Appendix A.
3.1 Prover-Policy ABID

2.5 Computational Bilinear Diﬃe-Hellman Assumption
with Gap on Target Group.
We introduce in this paper a new number theoretic assumption, which we call the Computational Bilinear DiﬃeHellman Assumption with Gap on Target Group. Let e :G × G → GT be a bilinear map. Let a, b, c ∈ Z p , a, b, c  0,
be chosen at random. Put A := ga , B := gb , C := gc . We
denote e(g, g) as gT . 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 = gabc
T ∈ GT ,even with the aid of the decisional Diﬃe-Hellman oracle for
GT : DDH GT (gT , ·, ·, ·). Here a tuple (gT , gzT1 , gzT2 , gzT3 ) ∈ G4T iscalled a Diﬃe-Hellman tuple (in GT ) if z1 z2 = z3 . The oracle
DDH GT returns True or False according to whether an input tuple is a Diﬃe-Hellman tuple or not, respectively. The
c-bdh-gap
probability for B to output gabc
T is denoted as AdvB,(e,G,GT ) (λ)(the advantage of B in the computational BDH game with
gap on GT ). Note that the above assumption is in generalstronger than the Gap Bilinear Diﬃe-Hellman Assumption[8]. The validity of the assumption is explained by thegeneric bilinear group model [6] in Appendix E.
2.6 Target Collision Resistant Hash Functions
Target collision resistant (TCR) hash functions [20] aretreated as a family Hfamλ = {Hμ }μ∈HKeyλ . Here HKeyλ isa hash key space and Hμ is a function from {0, 1}∗ to {0, 1}λ .
We may assume that Hμ is from {0, 1}∗ to Z p . Given a PPT

Scheme. PP-ABID consists of four PPT algorithms: (Setup,
KeyGen, P, V).
Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λ and the attribute universe U. It outputs apublic 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 asecret key SKA corresponding to A.
P(PK, SKA ) and V(PK, S ). P and V are interactive algorithms called a prover and a verifier, respectively. P takes
as input the public key PK and the secret key SKA . Herethe 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 first round. P and V interact with each other for some, at
most constant rounds. Then, V finally returns its decision bit
b. b = 1 means that V accepts P in the sense P has a secretkey SKA such that S satisfies 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.
Concurrent Man-in-the-Middle Attack on PP-ABID and
Security. An adversary A’s objective is impersonation. A
tries to make a verifier V accept with an attribute set S ∗ . The
following experiment Exprmtcmim
A,PP-ABID (λ, U) of an adversary A defines the game of concurrent man-in-the-middle

ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1091

attack (cMiM attack, for short) on PP-ABID.
∗
Exprmtcmim
A,PP-ABID (λ, U) : //AdaptiveS(PK, MSK) ← Setup(λ, U)qp

S ∗ ← AKG(PK,MSK,·),P j (PK,SK· )| j=1 (PK, U)
qp

KG(PK,MSK,·),P j (PK,SK· )|j=qp, V(PK, S ∗ )b ← AIf b = 1 then Return Win else Return Lose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 . We do
not require any two input, Ai1 and Ai2 , to be distinct. In addition, the adversary A invokes provers P j (PK, SK· ), j =1, . . . , qp , . . . , qp , by giving an access structure A j of A’s
choice. Acting as a verifier with an attribute set S j , A interacts with each P j .
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 access structure Ai mustsatisfy S ∗  Ai . In interactions with each prover, S ∗  A j ,or, every transcript of messages of a whole interaction witha prover P j (PK, SKA j ) must not be equal to a transcript of
messages of a whole interaction with a verifier V(PK, S ∗ )(that is, a mere relay of messages is prohibited in the gameof man-in-the-middle attack). 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 ofcMiM attack is defined 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 of sel-cMiM attack), A declares S ∗ before A receives PK. The following experiment
Exprmtsel-cmim
A,PP-ABID (λ, U) defines the selective game.
∗
Exprmtsel-cmim
A,PP-ABID (λ, U) : //SeletiveS(PK, MSK) ← Setup(λ, U)S ∗ ← A(λ, U)qpb ← AKG(PK,MSK,·),P j (PK,SK· )| j=1 (PK), V(PK, S ∗ )If b = 1 then Return Win else Return Lose
The advantage in the game of sel-cMiM attack is defined asdef
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 and for any U, Advsel-cmim
A,PP-ABID (λ) is negligible in λ.

Anonymity Anonymity that is discussed briefly in Introduction is formalized as follows. Consider the following experanonym
iment ExprmtA,PP-ABID (λ, U). (In the experiment, an adversary A interacts with P(PK, SKAb ) as a verifier with S ∗ .)anonymExprmtA,PP-ABID (λ, U) :(PK, MSK) ← Setup(λ, U), (A0 , A1 , S ∗ ) ← A(PK)s.t. (S ∗ ∈ A0 ∧ S ∗ ∈ A1 ) ∨ (S ∗  A0 ∧ S ∗  A1 )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

We say that PP-ABID have anonymity if, for any PPT A andfor any U, the following advantage of A is negligible in λ.
anonymdef

AdvA,PP-ABID (λ) =|Pr[Exprmtanonym
A,PP-ABID (λ, U) returns Win] − 1/2|.
4.

Generic Conversions from ABKEM to ABIDIn this section, we provide a generic conversion from a keypolicy ABKEM to a prover-policy ABID. The conversion
yields a challenge-and-response protocol of encapsulationand-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 ciphertextpolicy ABKEM to a verifier-policy ABID is described inAppendix C.
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 as a challenge-andresponse protocol of encapsulation-and-decapsulation. Figure 1 shows this conversion. Setup of PP-ABID uses
KEM.Setup. KeyGen of PP-ABID uses KEM.KeyGen. The
verifier 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, verifies whether κ̂ is equal to κ. If so, then V
returns 1 and otherwise, 0.
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 game of cMiM
attack, and for any given attribute universe U, there exists a
PPT adversary B on KP-ABKEM in the OW-CCA game thatsatisfies the following tight reduction.

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 2014

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

KeyGen(PK, MSK, A):
SKA ← KEM.KeyGen(PK, MSK, A)
Return (SKA )Fig. 1P(PK, SKA ):←−Send κ̂ to V−→κ̂Send ψ to P
Receiving κ̂ as input:
If κ̂ = κ then b := 1 else b := 0, Return b

A generic conversion from KP-ABKEM to PP-ABID.

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-ABKEMas follows.
B(PK, U) : //Adaptive S ∗//Setup
Initialize inner state, Invoke A on (PK, U)//Answering A s Queries
When A issues a key-ext. query for A
SKA ← KG(PK, MSK, A), Reply SKA to A
When A sends a chal. msg. (A, ψ) to Pκ̂ ← DEC(PK, SKA , ψ), Send κ̂ to A as the res. msg.
When A outputs a target attribute set S ∗Output S ∗ as its target attribute set
Receive ψ∗ as a chal. ciphertext
When A queries V for a chal. msg.
Send ψ∗ to A as a chal. msg.
When A sends the res. msg. κˆ∗ to V
Return κˆ∗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 theanswer 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 ψ∗ fromits challenger. When A 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. In the game of selective S ∗ , B is constructed as follows.
B(PK, U) : //Selective S ∗ψReceiving ψ as input:κ̂ ← KEM.Decap(PK, SKA , ψ)V(PK, S ):(κ, ψ) ← KEM.Encap(PK, S )//Setup
Initialize inner state, Invoke A on (λ, U)//Answering A s QueriesS ∗ ← A(λ, U)
Output S ∗ as its target attribute set
Receive ψ∗ as a chal. ciphertext, Give PK to A
When A issues a key-ext query for A
SKA ← KG(PK, MSK, A)
When A sends a chal. msg. (A, ψ) to Pκ̂ ← DEC(PK, SKA , ψ), Send κ̂ to A as the res. msg.
When A queries V for a chal. msg.
Send ψ∗ to A as a chal. msg.
When A sends the res. msg. κˆ∗ to V
Return κˆ∗Then 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 in the sense in [10] because underlying KP-ABKEM has the OW-CCA security. PP-ABID is also
verifier-resettable because PP-ABID consists of two rounds
interaction.
5.

Concrete Constructions of ABKEM

In this section, we construct a concrete KP-ABKEM thatis OW-sel-CCA secure. Using the algebraic trick of Bonehand Boyen [5] and Kiltz [17], we build an enhanced version,
KP-ABKEM, of the KP-ABKEM of Ostrovsky, Sahai and Waters [21] (OSW, for short). Then we obtain our concrete
PP-ABID by applying the generic conversion. (Our concrete
CP-ABKEM and VP-ABID is described in Appendix F).
5.1 Our Enhanced OSW KP-ABKEM and PP-ABID
The construction of our concrete KP-ABKEM is described inFig. 2. We only explain the enhanced part from the original [21]. We indicate the part of the original scheme by
the index: cpa . In Setup, a second component α2 ∈ Z p
is added to the master secret key MSKcpa . Also, the corresponding Y2 := e(g, g)α2 b and a hash key η is added tothe public key PKcpa . In KeyGen, components in SKcpa,Aare doubled reflecting the index 2 (but randomness is chosen independently of index 1). So computational cost forANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1093
Setup(λ, U):(p, G, GT , g, e) ← Grp(λ)
For x = 1 to u: T x ← G
b ← Z p , B := gb , α1 , α2 ← Z p
Y1 := e(g, g)α1 b , Y2 := e(g, g)α2 b
η ← HKeyλPK := (g, T 1 , . . . , T u , 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 ← Z p
For k = 1, 2:
vk := (αk , vk,2 , . . . , vk,n )For i = 1 to l: λk,i := vk · Mi
For k = 1, 2: For i = 1 to l:rk,irk,i ← Z p , Kk,i := Bλk,i T ρ(i),r
Lk,i := g k,iSKA := (((Kk,i , Lk,i );
i = 1, . . . , l); k = 1, 2)
Return SKA
Fig. 2

Decap(PK, SKA , ψ):
If S  A Return κ̂ :=⊥else{ωi ; i ∈ ρ−1 (S )}← Reconst(ρ−1 (S ), M)
For k = 1, 2:κˆk := i∈ρ−1 (S )(e(Kk,i , C  )/e(Lk,i , Cρ(i) ))ωiτ ← Hη (ψcpa )If κˆ1 τ κˆ2  d then κ̂ :=⊥ else κ̂ := κˆ1
Return κ̂Encap(PK, S ):s ← Z p , C  = gs
For x ∈ S : C x = T xs
ψcpa := (S , C  , (C x ; x ∈ S ))τ ← Hη (ψcpa )For k = 1, 2: κk := Yks ; d := κ1τ κ2(κ, ψ) := (κ1 , (ψcpa , d))Return (κ, ψ)

Our concrete KP-ABKEM (an enhanced OSW KP-ABKEM).

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, first, Decapcpa is executed twice for index
1 and 2 to yield κˆ1 and κˆ2 . Then, whether ψcpa is a consistentciphertext and (e(g, g), Y1τ Y2 , e(C  , g), d) is a Diﬃe-Hellman
tuple are verified. These two conditions are verified by one
equation κˆ1 τ κˆ2 = d, though the verification equation overlooks inconsistent ψcpa only with a negligible probability.
Finally, κ̂ := κˆ1 is returned only when the verification equation holds.
Theorem 2: If the computational bilinear Diﬃe-Hellman
assumption with gap on target group holds, and an employedhash function family has target collision resistance, 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 the computational BDH
game with gap on GT and a PPT target collision finder 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λ (λ).

Proof. Using any given PPT 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 =ga , B = gb , C = gc , 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 T x of PK
as
If x ∈ S ∗ then t x ← Z p , T x := gtx
else θ x , η x ← Z p s.t. (θ x  0), T x := Bθx gηx .

Here, in else case, we have implicitly set t x := bθ x +η x . B sets Y1 := e(A, B) = e(g, g)ab and PKcpa :=(g, T 1 , . . . , T u , B, Y1). Here we have implicitly set α1 := a.
A challenge ciphertext is computed as follows (we implicitly set s∗ = c):∗ψ∗cpa := (S ∗ , C ∗ = g s := C, (C ∗x := C tx , x ∈ S ∗ )).
Then a public key PK and a whole challenge ciphertext ψ∗is computed as∗η ← HKeyλ , τ∗ ← Hη (ψ∗cpa ), μ ← Z p , Y2 := e(B, g)μ /Y1τ ,PK := (PKcpa , Y2 , η), d∗ := e(B, C ∗ )μ , ψ∗ := (ψ∗cpa , d∗ ).
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−1 ∗
 · Mi = 0. Note here that
w1 = 1 and for all i ∈ ρ (S ), w
 surely exists. B chooses random valuesS ∗  A, so such w
u1,1 , . . . , u1,n ∈ Z p and put u1 := (u1,1 , . . . , u1,n ). Then wew.
implicitly set v1 := u1 + (a − u1,1 )
Here for each i = 1, . . . , l, B can compute gλ1,i asg Mi ·v1 = g Mi ·(u1 −u1,1 w ) A Mi ·w . Then B computes the index 1
components of SKS as
For i = 1 to l :If i ∈ ρ−1 (S ∗ ) then r1,i ← Z p1,i
K1,i := B Mi ·u1 T ρ(i), L1,i := gr1,irelse r1,i
← Zp




K1,i := (gλ1,i )−ηρ(i) /θρ(i) (Bθρ(i) gηρ(i) )r1,i , L1,i := (gλ1,i )−1/θρ(i) gr1,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 valuesu2 ,1 , . . . , u2 ,n , r2 ,i (or r2  ,i ) ∈ Z p 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) toA.
(2) Decapsulation Queries. When A issues a decapsulation
query for (A, ψ = (ψcpa , d)) (where ψcpa is about S ), B has

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 20141094

to reply the decapsulation κ̂ to A. To do so, B computes asfollows. (Note that the oracle DDH GT is accessed.)
If S  A then κ̂ :=⊥else If Verify(PKcpa , ψcpa ) = False then κ̂ :=⊥else τ ← Hη (ψcpa )If DDH GT (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/(τ−τ )∗Verify(PKcpa , ψcpa ) :For x ∈ S : If e(T x , C  )  e(C x , 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 thecase Abort happens. To see why, we prove the following
claims.
Claim 1: The reply SKA to a key-extraction query is a perfect simulation.

Proof. First, the index 1 components K1,i , L1,i , i = 1, . . . , l
are correctly distributed, as is proved in the original work of
Ostrovsky, Sahai and Waters [21]. By the construction, theindex 2’ components K2 ,i , L2 ,i , i = 1, . . . , l are distributed in
the same way as the index 1 (but with independent randomness).
For the index 2 components K2,i , L2,i , i = 1, . . . , l,note that we have implicitly set v2, j := v2 , j (−τ∗ ), j =2, . . . , n, r2,i = r2 ,i (−τ∗ ), i = 1, . . . , l. Using another implicit
relation (1) together, we get∗

K2,i = B Mi,1 μ (K2 ,i )−τ∗

2 ,i −τ= B Mi,1 μ (Bλ2 ,i T ρ(i))∗

2 ,i −τ
= gbMi,1 μ (gbMi ·(α1 ,v2 ,2 ,...,v2 ,n ) T ρ(i)
)

r

∗

∗

∗

r  (−τ∗ )2 ,i= gb(Mi,1 (μ−α1 τ )+Mi,2 v2 ,2 (−τ )+···+Mi,n v2 ,n (−τ )) T ρ(i)b(Mi,1 α2 +Mi,2 v2,2 +···+Mi,n v2,n )

=g

∗

∗

= (e(g, g)α1 (τ−τ )bs )1/(τ−τ ) = Y1s .
Claim 3: The challenge ciphertext ψ∗ = (ψ∗cpa , d∗ ) is correctly distributed.

Proof. Using the implicit relations (1), a direct calculationshows;∗∗∗∗d∗ = e(B, C ∗ )μ = e(g, g)bs (α1 τ +α2 ) = (Y1τ Y2 ) s .
Hence ψ∗ = (ψ∗cpa , d∗ ) is legitimate and correctly distributed.

Now we are ready to evaluate the advantage of B in the
OW-sel-CCA game. First, the following claim holds.
Claim 4: The probability that Abort occurs is negligible in λ. More precisely, the following equality holds:
Pr[Abort] = Advtcr
CF ,Hfamλ (λ).

Proof. We construct a PPT target collision finder CF by
using A as subroutine as follows. (Remark that the caseCollision is defined. Encapcpa (PKcpa , S ) is a subalgorithmof Encap(PK, S ) that outputs (κ, ψcpa ).)CF (λ) ://Setup
Initialize its inner state
Choose an attribute universe U = {1, . . . , u} at random,
where u is bounded by a polynomial in λS ∗ ← A(λ, U), (p, G, GT , g, e) ← Grp(λ),
T 1 , . . . , T u ← G, b, α1 ← Z p , B := gb , Y1 := e(g, g)α1 b
PKcpa := (g, T 1 , . . . , T u , B, Y1 )(κ∗ , ψ∗cpa ) ← Encapcpa (PKcpa , S ∗ )r2,i
T ρ(i)

2,i= B Mi ·v2 T ρ(i)
,

r

∗

∗

κ̂ = ((Y1τ Y2 ) s /e(B, C  )μ )1/(τ−τ ) = (e(g, g)(α1 τ+α2 −μ)bs )1/(τ−τ )where Verify is the following PPT algorithm to check consistency of ψcpa :rinconsistency of ψ because it uses subroutine Verify whichchecks consistency of ψcpa perfectly and hence, in combination with the verification equation, consistency of ψ perfectly. Then the computationally bounded adversary A cannot distinguish the diﬀerence between the response of DEC
and B.
Hence it is enough to prove that if DDH GT (e(g, g),
Y1τ Y2 , e(C  , g), d) = True, then κ̂ = Y1s . This is deduced
by using the implicit relations (1), as follows.

∗

L2,i = (L2 ,i )−τ = (gr2 ,i )−τ = gr2,i , i = 1, . . . , l.

Output ψ∗cpa //a Target
Claim 2: The reply κ̂ to a decapsulation query is a simulation that is computationally indistinguishable from a real,
until the case Abort happens.

Proof. First note that the honest decapsulation algorithm
Decap overlooks an inconsistent ciphertext ψ only with negligible probability 1/p in its verification process by the verification equation (κˆ1 τ κˆ2 = d) (the reason is the same as in
Sect. 5.2). On the other hand, the solver B never overlook

Receive η ∈ HKeyλ , τ∗ ← Hη (ψ∗cpa )α2 ← Z p , PK := (PKcpa , Y2 := e(g, g)α2 b , η), MSK := (α1 , α2 )∗d∗ := e(B, C ∗ )α1 τ e(B, C ∗ )α2 , ψ∗ := (ψ∗cpa , d∗ )Give (PK, ψ∗ ) to A//Answering A s Queries
When A issues a key-extraction query by A
Reply SKA ← KeyGen(PK, MSK, A) to A
When A issues a decapsulation query by (A, ψ = (ψcpa , d))ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1095
P(PK = (g, T 1 , . . . , T u , B, Y1 , Y2 , η),rk,iSKA = (((Kk,i = Bλk,i T ρ(i), Lk,i = grk,i );
i = 1, . . . , l); k = 1, 2)):
ψ

Receiving ψ as input;
If S  A then κ̂ :=⊥else τ ← Hη (ψcpa ){ωi ; i ∈ ρ−1 (S )} ← Reconst(ρ−1 (S ), M)
For k = 1, 2 :κˆk := i∈ρ−1 (S ) (e(KK,i , C  )/e(LK,i , Cρ(i) ))ωiτ
If κˆ1 κˆ2  d then κ̂ :=⊥ else κ̂ := κˆ1←−

Send κ̂ to V−→
Fig. 3κ̂

V(PK, S ):s ← Z p , C  := g s , For x ∈ S : C x := T xs
ψcpa := (S , C  , (C x ; x ∈ S )), τ ← Hη (ψcpa )For k = 1, 2: κk := Yks ; d := κ1τ κ2 , (κ, ψ) := (κ1 , (ψcpa , d))Send ψ to P

Receiving κ̂ as input;
If κ̂ = κ then b := 1 else b := 0, Return b

An interaction of our concrete PP-ABID.

τ ← Hη (ψcpa )If e(B, C  )α1 τ+α2  d then κ̂ :=⊥else
If ψcpa  ψ∗cpa ∧ τ = τ∗then Return ψcpa //the CaseCollisionelse

SKA ← KeyGen(PK, MSK, A)
Reply κ̂ ← Decap(PK, SKA , ψ) to A//StopWhen A returns its guess κˆ∗ , Stop.
By the construction, the view of A in CF is the sameas the view of A in B. (Remark that if e(B, C  )α1 τ+α2 = dholds, then ψcpa  ψ∗cpa holds automatically, as is explained
below.)Let us evaluate the probability in Claim 4. If, in addition to τ = τ∗ , it occurred that ψcpa = ψ∗cpa (and hence
S = S ∗ , C  = C ∗ ), then it would occur that d = d∗ .
So ψ = ψ∗ holds. This is because the following twotuples are equal DH tuples: (e(g, g), Y1τ Y2 , e(C  , g), d) and∗(e(g, g), Y1τ Y2 , e(C ∗ , g), d∗ ). So both S ∗ ∈ A and ψ =(ψcpa , d) = (ψ∗cpa , d∗ ) = ψ∗ would occur. This is ruled out
by definition in decapsulation query.
Therefore, we have ψcpa  ψ∗cpa . That is, CF gets acollision:
ψcpa  ψ∗cpa ∧ Hη (ψcpa ) = τ = τ∗ = Hη (ψ∗cpa ).
Therefore, we get Pr[Abort] = Pr[Collision]. Substituting
the advantage, we obtain
Pr[Abort] = Advtcr
CF ,Hfamλ (λ).

By definition, 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 definition that B succeeds
in computing the answer for the given instance (g, A, B, C).
Therefore, the probability that B wins is equal to theprobability that A wins and Abort never occurs. So wehave:

Pr[B wins] = Pr[(A wins) ∧ (¬Abort)] Pr[A wins] − Pr[Abort].
Substituting advantages and using the equality in Claim 4,
we have:
c-bdh-gap

tcr
AdvB,(e,G,GT ) (λ)  Advow-sel-cca
A,KP-ABKEM (λ) − AdvCF ,Hfamλ (λ).

This is what we should prove in Theorem 5Applying the generic conversion in 4.1 (fromKP-ABKEM to PP-ABID) to our concrete KP-ABKEM above,
we obtain a concrete PP-ABID. Figure 3 shows the interaction of the obtained PP-ABID.
Theorem 3 (Corollary to Theorem 1 and 2): Our PP-ABID
is selectively secure against cMiM attacks under the same
assumptions. More precisely,
c-bdh-gap

tcr
Advsel-cmim
A,PP-ABID (λ)  AdvB,(e,G,GT ) (λ) + AdvCF ,Hfamλ (λ).

Figure 3 shows an interaction of our PP-ABID.
5.2 Discussion
Anonymity.
Our concrete PP-ABID possesses theanonymity in the sense in Sect. 3.1 because the response
message in the protocol of PP-ABID is a result of decapsulation; the result does not depend on prover’s access structure
A itself, but depends on whether A fits verifier’s attribute
set S or not (S ∈ A or not). That is, when a verifier or acheating adversary receives a result of decapsulation, the information of prover’s access structure A never leaks. (Ourconcrete VP-ABID in Appendix F also has anonymity.)
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 [23], we use for x ∈ U a hashed value H(x) instead ofT x (and hence T x is removed from PK). Although the resulting schemes are proved to be secure only in the random
oracle model, we do not have to rewrite the public key PK
each time when a new attribute x is added.
Exiting the Gap Assumption. Instead of using the aid oforacle DDH GT , we can use the twin Diﬃe-Hellman trapdoor

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 20141096

test of Cash, Kiltz and Shoup [14] in the security proofs. At
the price of that, the resulting schemes have a secret key of
double size and decapsulation costs twice as much.
Security against Adaptive Target. Our concrete PP-ABID(and our concrete VP-ABID in Appendix F) is secure in thegame of selectively declared target. When we consider the
security game in the random oracle model, we can apply
our CCA secure enhancing technique to the dual system encryptions of Lewko, Okamoto, Sahai, Takashima and Waters[18], which are CPA secure against adaptive target. We remark that our CCA secure enhancing technique is a kind of(non-black box) direct chosen-ciphertext security technique[7].
6.

Conclusions

We introduced the notion of attribute-based identification (ABID) and defined prover-policy ABID scheme andverifier-policy ABID scheme. We provided a design principle: construct a one-way CCA secure ABKEM and use it
as challenge-and-response ABID. The obtained ABID is secure against concurrent man-in-the-middle attacks. We actually constructed concrete KP-ABKEM and CP-ABKEM
with OW-CCA security and obtained concrete PP-ABID and
VP-ABID schemes. We proposed that functional tickets
and functional gates are useful applications of PP-ABID and
VP-ABID, respectively.
Acknowledgements
We sincerely appreciate helpful comments about anonymous credential systems from Prof. Mitchel of Universityof London at ACISP 2013, Brisbane. We also appreciateanonymous reviewers for comments about our new number
theoretic assumptions and generic bilinear group model.
References[1] H. Anada and S. Arita, “Identification schemes from key encapsulation mechanisms,” Proc. AFRICACRYPT 2011, Dakar, Senegal,
July 2011, Lect. Notes Comput. Sci., vol.6737, pp.59–76, SpringerVerlag, Heidelberg.
[2] H. Anada, S. Arita, S. Handa, and Y. Iwabuchi, “Attribute-based
identification: Definitions and eﬃcient constructions,” Proc. ACISP
2013, Brisbane, Australia, July 2013, Lect. Notes Comput. Sci.,
vol.7959, pp.168–186, Springer-Verlag, Heidelberg.
[3] G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik, “A practical andprovably secure coalition-resistant group signature scheme,” Proc.
CRYPTO 2000, Santa Barbara, California, USA, Aug. 2000, Lect.
Notes Comput. Sci., vol.1880, pp.255–270, Springer-Verlag, Heidelberg.
[4] S. Brands, Rethinking public key infrastructures and digital certificates, MIT Press, 2000.
[5] D. Boneh and X. Boyen, “Eﬃcient selective-ID secure identitybased encryption without random oracles,” Proc. EUROCRYPT
2004, Interlaken, Switzerland, May 2004, Lect. Notes Comput. Sci.,
vol.3027, pp.223–238, Springer-Verlag, Heidelberg.
[6] D. Boneh, X. Boyen, and E.J. Goh, “Hierarchical identity based encryption with constant size ciphertext,” Proc. EUROCRYPT 2005,
Aarhus, Denmark, May 2005, Lect. Notes Comput. Sci., vol.3494,
pp.440–456, Springer-Verlag, Heidelberg. Full version available at

IACR Cryptology ePrint Archive, 2005/015, http://eprint.iacr.org/[7] X. Boyen, Q. Mei, and B. Waters, “Direct chosen ciphertext security from identity-based techniques,” Proc. ACM Conference on
Computer and Communications Security, pp.320–329, 2005. Fullversion available at IACR Cryptology ePrint Archive, 2005/288,
http://eprint.iacr.org/[8] J. Baek, R. Safavi-Naini, and W. Susilo, “Eﬃcient multi-receiver
identity-based encryption and its application to broadcast encryption,” Proc. PKC 2005, Les Diablerets, Switzerland, Jan. 2005, Lect.
Notes Comput. Sci., vol.3386, pp.380–397, Springer-Verlag, Heidelberg.
[9] A. Beimel, “Secure schemes for secret sharing and key distribution,”
Ph.D. thesis, Israel Institute of Technology, Technion, Haifa, Israel,
1996.
[10] M. Bellare, M. Fischlin, S. Goldwasser, and S. Micali, “Identification protocols secure against reset attacks,” Proc. EUROCRYPT
2001, Innsbruck, Austria, May 2001, Lect. Notes Comput. Sci.,
vol.2045, pp.495–511, Springer-Verlag, Heidelberg.
[11] M. Bellare and A. Palacio, “GQ and schnorr identification schemes:
Proofs of security against impersonation under active and concurrent attacks,” Proc. CRYPTO 2002, Santa Barbara, California,
USA, Aug. 2002, Lect. Notes Comput. Sci., vol.2442, pp.162–177,
Springer-Verlag, Heidelberg.
[12] J. Camenisch and A. Lysyanskaya, “An eﬃcient system for nontransferable anonymous credentials with optional anonymity revocation,” Proc. EUROCRYPT 2001, Innsbruck, Austria, May 2001,
Lect. Notes Comput. Sci., vol.2045, pp.93–118, Springer-Verlag,
Heidelberg.
[13] D. Chaum, “Blind signatures for untraceable payments,” Proc.
CRYPTO’82, Santa Barbara, California, USA, Aug. 1982, pp.199–
203, Plenum Press, New York.
[14] D. Cash, E. Kiltz, and V. Shoup, “The twin Diﬃe-Hellman problem
and applications,” Proc. EUROCRYPT 2008, Istanbul, Turkey, April
2008, Lect. Notes Comput. Sci., vol.4965, pp.127–145, SpringerVerlag, Heidelberg. Full version available at Cryptology ePrint
Archive, 2008/067, http://eprint.iacr.org/[15] R. Gennaro, “Multi-trapdoor commitments and their applications
to non-malleable protocols,” Proc. CRYPTO 2004, Santa Barbara,
California, USA, Aug. 2004, Lect. Notes Comput. Sci., vol.3152,
pp.220–236, Springer-Verlag, Heidelberg.
[16] V. Goyal, O. Pandey, A. Sahai, and B. Waters, “Attribute-based encryption for fine-grained access control of encrypted data,” Proc.
ACM Conference on Computer and Communications Security,
pp.89–98, 2006.
[17] E. Kiltz, “Chosen-ciphertext security from tag-based encryption,”
Proc. TCC 2006, Tokyo, Japan, March 2013, Lect. Notes Comput.
Sci., vol.3876, pp.581–600, Springer-Verlag, Heidelberg.
[18] A.B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B.
Waters, “Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption,” Proc. EUROCRYPT 2010, French Riviera, May-June 2010, Lect. Notes Comput. Sci., vol.6110, pp.62–91, Springer-Verlag, Heidelberg. Fullversion available at IACR Cryptology ePrint Archive, 2010/110,
http://eprint.iacr.org/[19] H.K. Maji, M. Prabhakaran, and M. Rosulek, “Attribute-based signatures,” Proc. CT-RSA 2011, San Francisco, CA, USA, Feb. 2011,
Lect. Notes Comput. Sci., vol.6558, pp.376–392, Springer-Verlag,
Heidelberg. Full version available at Cryptology ePrint Archive,
2010/595, http://eprint.iacr.org/[20] M. Naor and M. Yung, “Universal one-way Hash functions and theircryptographic applications,” Proc. 21st Symposium on Theory ofComputing 1989, pp.33–43, Association for Computing Machinery,
New York.
[21] R. Ostrovsky, A. Sahai, and B. Waters, “Attribute-based encryption
with non-monotonic access structures,” Proc. ACM Conference on
Computer and Communications Security, pp.195–203, 2007.
[22] C.P. Schnorr, “Eﬃcient identification and signatures for smart

ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1097

cards,” Proc. CRYPTO’89, Santa Barbara, California, USA, Aug.
1989, Lect. Notes Comput. Sci., vol.435, pp.239–252, SpringerVerlag, Heidelberg.
[23] B. Waters, “Ciphertext-policy attribute-based encryption: An expressive, eﬃcient and provably secure realization,” Proc. PKC 2011,
Taormina, Italy, March 2011, Lect. Notes Comput. Sci., vol.6571,
pp.53–70, Springer-Verlag, Heidelberg. Full version available at
IACR Cryptology ePrint Archive, 2008/290, http://eprint.iacr.org/[24] S. Yamada, N. Attrapadung, B. Santoso, J.C.N. Schuldt, G.
Hanaoka, and N. Kunihiro, “Verifiable predicate encryption and applications to CCA security and anonymous predicate authentication,” Proc. PKC 2012, Darmstadt, Germany, May 2012, Lect. Notes
Comput. Sci., vol.7293, pp.243–261, Springer-Verlag, Heidelberg.
[25] S. Yilek, “Resettable public-key encryption: How to encrypt on
a virtual machine,” Proc. CT-RSA 2010, San Francisco, CA,
USA, March 2010, Lect. Notes Comput. Sci., vol.5985, pp.41–56,
Springer-Verlag, Heidelberg.

qpA∗ ← AKG(PK,MSK,·),P j (PK,SK· )| j=1 (PK, U)
qp

KG(PK,MSK,·),P j (PK,SK· )|j=qp, V(PK, A∗ )
b ← AIf b = 1 then Return Win else Return LoseThe advantage of A over VP-ABID in the game ofcMiM attack is defined as
def

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

VP-ABID is called secure against cMiM attacks if, for any
PPT A and for any attribute universe U, Advcmim
A,VP-ABID (λ) is
negligible in λ.
A.3 Selective Security

Appendix A: Verifier-Policy ABID
A.1 Scheme
VP-ABID consists of four PPT algorithms: (Setup, KeyGen,
P, V).
Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λ and the attribute universe U. It outputs apublic key PK and a master secret key MSK.
KeyGen(PK, MSK, S ) → SKS . A key-generation algorithm KeyGen takes as input the public key PK, the mastersecret key MSK and an attribute set S . It outputs a secretkey SKS corresponding to S .
P(PK, SKS ) and V(PK, A). P and V are interactive algorithms called a prover and a verifier, respectively. P
takes as input the public key PK and the secret key SKS .
Here the secret key SKS is given to P by an authoritythat runs KeyGen(PK,MSK,S ). V takes as input the public key PK and an attribute set S . P is provided V’s access structure A by the first round. P and V interact witheach other for some, at most constant rounds. Then, V
finally returns its decision bit b. b = 1 means that V
accepts P in the sense P has a secret key SKS such that
S satisfies A. b = 0 means that V rejects P. We demand correctness of VP-ABID that for any λ and U, and
if S ∈ A, then Pr[(PK, MSK) ← Setup(λ, U); SKS ←KeyGen(PK, MSK, S ); b ← P(PK, SKS ), V(PK, A) : b =1] = 1.
A.2 Concurrent Man-in-the-Middle Attack on VP-ABID
and Security
An adversary A’s objective is impersonation. A tries tomake a verifier V accept with an access structure A∗ . The
following experiment Exprmtcmim
A,VP-ABID (λ, U) of an adversary A defines the game of concurrent man-in-the-middle
attack (cMiM attack, for short) on VP-ABID in the dual way
to PP-ABID.
∗
Exprmtcmim
A,VP-ABID (λ, U) : //AdaptiveA(PK, MSK) ← Setup(λ, U)

In the selective game on a target access structure (the gameof sel-cMiM attack), A declares A∗ before A receives PK.
The following experiment Exprmtsel-cmim
A,VP-ABID (λ, U) defines
the selective game.
∗
Exprmtsel-cmim
A,VP-ABID (λ, U) : //SeletiveA(PK, MSK) ← Setup(λ, U)A∗ ← A(λ, U)qpb ← AKG(PK,MSK,·),P j (PK,SK· )| j=1 (PK), V(PK, A∗ )
If b = 1 then Return Win else Return Lose
The advantage in the game of sel-cMiM attack is defined asdef

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

VP-ABID is called selectively secure against cMiM attacks
if, for any PPT A and for any U, Advsel-cmim
A,VP-ABID (λ) is negligible in λ.
A.4 Anonymity
Anonymity that is discussed briefly in Introduction is formalized as follows. Consider the following experimentanonymExprmtA,VP-ABID (λ, U). (In the experiment, an adversary Ainteracts with P(PK, SKS b ) as a verifier with A∗ .)anonymExprmtA,VP-ABID (λ, U) :(PK, MSK) ← Setup(λ, U), (S 0 , S 1 , A∗ ) ← A(PK)s.t. (S 0 ∈ A∗ ∧ S 1 ∈ A∗ ) ∨ (S 0  A∗ ∧ S 1  A∗ )SKS 0 ← KeyGen(PK, MSK, S 0 )SKS 1 ← KeyGen(PK, MSK, S 1 )b ← {0, 1}, b̂ ← AP(PK,SKS b ) (PK, SKS 0 , SKS 1 )If b = b̂ Return Win else Return Lose

We say that VP-ABID have anonymity if, for any PPT A andfor any U, the following advantage of A is negligible in λ.
def

Advanonym
A,VP-ABID (λ) =IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 20141098
anonym|Pr[ExprmtA,VP-ABID (λ, U) returns Win] − 1/2|.

Ifκˆ∗ = κ∗ then Return Win else Return Lose

The advantage in the OW-sel-CCA game is defined as
Appendix B: Ciphertext-Policy Attribute-Based KEM
B.1 Scheme
A ciphertext-policy ABKEM, CP-ABKEM, consists of four
probabilistic polynomial time algorithms: (Setup, KeyGen,
Encap, Decap). The definition goes in a dual manner to keypolicy ABKEM on an access structure A and an attribute set
S . Setup(λ, U) → (PK, MSK). KeyGen(PK, MSK, S ) →SKS . Encap(PK, A) → (κ, ψ). Decap(PK, SKS , ψ) →
κ̂. We demand correctness of CP-ABKEM that for any
λ and U, and if S ∈ A, then Pr[(PK, MSK) ←Setup(λ, U); SKS ← KeyGen(PK, MSK, S ); (κ, ψ) ←Encap(PK, A); κ̂ ← Decap(PK, SKS , ψ) : κ = κ̂] = 1.
B.2 Chosen-Ciphertext Attack on One-Wayness of CPABKEM and Security
The following experiment Exprmtow-cca
A,CP-ABKEM (λ, U) of an adversary A defines the game of chosen-ciphertext attack on
one-wayness of CP-ABKEM (the OW-CCA game).
∗
Exprmtow-cca
A,CP-ABKEM (λ, U) : //AdaptiveA(PK, MSK) ← Setup(λ, U)A∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (PK, U)(κ∗ , ψ∗ ) ← Encap(PK, A∗ )Advow-sel-cca
A,CP-ABKEM (λ)
def= Pr[Exprmtow-sel-cca
A,CP-ABKEM (λ, U) returns Win].

CP-ABKEM is called selectively secure against chosenciphertext attacks on one-wayness if, for any PPT A andfor any U, Advow-sel-cca
A,CP-ABKEM (λ) is negligible in λ.
Appendix C: Generic Conversion from CP-ABKEM to
VP-ABID
C.1 The Conversion
Let CP-ABKEM= (KEM.Setup, KEM.KeyGen, KEM.Encap,
KEM.Decap) be a CP-ABKEM. Then VP-ABID= (Setup,
KeyGen, Encap, Decap) is obtained as a challenge-andresponse protocol of encapsulation-and-decapsulation. Figure A· 1 shows this conversion.
Theorem 4: If CP-ABKEM is OW-CCA secure, then the derived VP-ABID is cMiM secure. More precisely, for any
given PPT adversary A on VP-ABID in the game of cMiM
attack, and for any given attribute universe U, there exists a
PPT adversary B on CP-ABKEM in the OW-CCA game thatsatisfies the following tight reduction.
ow-ccaAdvcmim
A,VP-ABID (λ)  AdvB,CP-ABKEM (λ).

κˆ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (ψ∗ )Ifκˆ∗ = κ∗ then Return Win else Return Lose

The proof of Theorem 4 goes in a dual manner to the proofof Theorem 1 on an access structure A and an attribute set S
and is omitted.

The advantage of A over KP-ABKEM in the OW-CCA
game is defined as

Appendix D: Computational q-Parallel Bilinear DiﬃeHellman Exponent Assumption with Gap
on Target Group

Advow-cca
A,CP-ABKEM (λ)
def= Pr[Exprmtow-cca
A,CP-ABKEM (λ, U) returns Win].

CP-ABKEM is called secure against chosen-ciphertext attacks on one-wayness if, for any PPT A and for any U,
Advow-cca
A,CP-ABKEM (λ) is negligible in λ.
B.3 Selective Security
In the selective game on a target access structure (OW-selCCA game), A declares A∗ before A receives PK. The following experiment Exprmtow-sel-cca
A,CP-ABKEM (λ, U) defines the selective game.
∗
Exprmtow-sel-cca
A,CP-ABKEM (λ, U) : //SelectiveA(PK, MSK) ← Setup(λ, U)A∗ ← A(λ, U)(κ∗ , ψ∗ ) ← Encap(PK, A∗ )κˆ∗ ← AKG(PK,MSK,·),DEC(PK,SK· ,·) (PK, ψ∗ )Let a, s, b1 , . . . , bq ∈ Z p , all of which is not zero, be chosen
at random. Denote e(g, g) as gT . Letqq+2

y := (g, g s , ga , . . . , g(a ) , g(a)

2q, . . . , g(a ) ,∀1 jq g sb j , ga/b j , . . . , g(a /b j ) , g(aqq+2/b j ), . . . , g(a /b j ) ,2q∀1 j, kq, k j gasbk /b j , . . . , ga sbk /b j ).
q

Then our new assumption says it is at most with a negligible
probability in λ that, for any PPT algorithm B given input yq+1(parametrized by q), to output Z = gaT s ∈ GT , even with theaid of the decisional DDH oracle DDH GT (gT , ·, ·, ·). The validity of the assumption is explained by the generic bilinear
group model [6] in Appendix E.
Appendix E: Validity of Our Assumptions in the
Generic Bilinear Group Model
We explain validity of our two assumptions in Sect. 2.5 andAppendix D in the generic bilinear group model, especially

ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

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

KeyGen(PK, MSK, S ):SKS ← KEM.KeyGen(PK, MSK, S )Return (SKS )Fig. A· 1

P(PK, SKS ):←−Send κ̂ to V−→κ̂Send ψ to P
Receiving κ̂ as input:
If κ̂ = κ then b := 1 else b := 0, Return b

A generic conversion from CP-ABKEM to VP-ABID.

in the light of Boneh, Boyen and Goh [6]. In Appendix Aof [6], a template is given for the decisional BDH assumption and its variants, so we adapt the template for our computational BDH assumption and PBDHE assumption with
gap on target group. According to the template, our two
assumptions can be treated in a unified manner.
Let ξ0 , ξ1 be two random encodings of the additive
group Z+p : i.e. injective maps ξ0 , ξ1 : Z+p → {0, 1}m . We
write G = {ξ0 (x); x ∈ Z+p } and GT = {ξ1 (x); x ∈ Z+p }.
Lemma 1 (Comp.(P, Q, f )-DH Problem with Gap on GT):
(Notations are the same as in [6].) Let P, Q ∈ Z p[X1 , . . . , Xn ] s be two s-tuples of n-variate polynomials overZ p and let f ∈ Z p [X1 , . . . , Xn ]. Let d = max(2dP , dQ , d f ).
If f is independent of P, Q in the sense in [6], then for any
algorithm A that makes a total of q queries to the oracles ofgroup operation in G, GT , the oracle of bilinear pairing e:
G × G → GT and the oracle DDH GT (gT , ·, ·, ·), we have:|Pr[x1 , . . . , xn ← Z p :A(p, ξ0 (P(x1 , . . . , xn )), ξ1 (Q(x1 , . . . , xn )))= ξ1 ( f (x1 , . . . , xn ))]|  (q + 2s + 1)3 (d/p).
Especially, if q, s, d are polynomial in λ, then the successprobability for A to solve (P, Q, f )-Diﬃe-Hellman problem
is negligible in λ.

Proof (sketch). According to the template in [6], we construct an algorithm B that simulates replying to A’s queries.
For the simulation, B maintains two lists as in [6]:L0 = {(pi , ξ0,i ); i = 1, . . . , τ0 }, L1 = {(qi , ξ1,i ); i = 1, . . . , τ1 }.
Here pi ∈ Z p [X1 , . . . , Xn ], qi ∈ Z p [X1 , . . . , Xn , Y], and ξ∗,∗are strings in {0, 1}m . At step τ = 0, L0 , L1 are initialized as
τ0 = s, τ1 = s + 1, L0 := {(pi , ξ0,i ); pi ∈ P for i = 1, . . . , s},
L1 := {(qi , ξ1,i ); qi ∈ Q for i = 1, . . . , s, q s+1 = Y}, where ξ∗,∗strings are chosen at random from {0, 1}m .
The first and the second types of queries can be simulated in the same way as in [6]. The third type of queries
to DDH GT (gT , ·, ·, ·) is simulated as follows. When queried
about (ξ1,i , ξ1, j , ξ1,k ) by A, B sets τ2 ← τ2 + 1 and replies
True if qi q j = qk as polynomials, and False otherwise.
τ0 + τ1 + τ2 = τ + 2s + 1 holds at each step τ.
The simulation of B is perfect except three error-cases.
The first and the second error-cases are the same as in [6].
The third error-case is the case that the following holds:
putting y = f (x1 , . . . , xn ) ∈ Z p ;1  ∃ i, ∃ j, ∃ k  τ1 such that

ψ

Receiving ψ as input:κ̂ ← KEM.Decap(PK, SKS , ψ)V(PK, A):(κ, ψ) ← KEM.Encap(PK, A)

i, j, k : pairwise distinct,∧ qi (x1 , . . . , xn , y) q j (x1 , . . . , xn , y) = qk (x1 , . . . , xn , y),∧ qi (X1 , . . . , Xn , Y) q j (X1 , . . . , Xn , Y)  qk (X1 , . . . , Xn , Y).
Here the upper equality is an equality as elements in Z p ,and the lower equality is an equality as polynomials in
Z p [X1 , . . . , Xn , Y].
If none of the three error-cases occurs, then A
never return the correct answer ξ1 ( f (x1 , . . . , xn )) because
f (X1 , . . . , Xn ) never appear in the list L1 . This is because
f is independent of (P, Q) as polynomials, in the sense defined in [6] (see [6] for the precise argument).
Therefore, when A returns the correct answer
ξ1 ( f (x1 , . . . , xn )), it must be in one of the three error-cases.
The probability that the three error-cases occur is evaluated in a similar way as in [6], but in our case the above
third error-case is dominant and we have the upper bound(q + 2s + 1)3 (d/p), which is negligible in λ.
Corollary 1: In the generic bilinear group model, our assumptions in Sects. 2.5 and Appendix D are valid.

Proof. Just put P = (1, X1 , X2 , X3 ), Q = (1, 1, 1, 1) and f =X1 X2 X3 for the former. By degree argument, we can seethat f is independent of (P, Q) in the sense in [6], hence
the assumption in Sect. 2.5 holds. For the latter, put P as in[23] (the exponents of components of y), Q = (1, . . . , 1) andf = X1 X2 X3 . By the argument in [23], f is independent of(P, Q) in the sense in [6], hence the assumption in Appendix
D holds.
Appendix F: Concrete Construction: Our Enhanced
Waters CP-ABKEM and VP-ABID
The construction of our concrete CP-ABKEM is described inFig. A· 2.
Theorem 5: If the computational q-parallel bilinear DiﬃeHellman exponent assumption with gap on target groupholds, and an employed hash function family has target collision resistance, then our CP-ABKEM is OW-sel-CCA securewith a challenge matrix of size l∗ × n∗ , l∗ , n∗  q. More precisely, for any given PPT adversary A on CP-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 the computational q-PBDHE with gap-for-GT game and a PPT target
collision finder CF on Hfamλ that satisfy the following tight
reduction.
c-pbdhe-gap

tcr
Advow-sel-cca
A,CP-ABKEM (λ)  AdvB,(e,G,GT ) (λ) + AdvCF ,Hfamλ (λ).

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 2014

1100
Setup(λ, U):(p, G, GT , g, e) ← Grp(λ)
For x = 1 to u: T x ← G
a ← Z p , A := ga
α1 , α2 ← Z p
Y1 := e(g, g)α1 , Y2 := e(g, g)α2η ← HKeyλPK := (g, T 1 , . . . , T u , A, Y1 , Y2 , η)MSK := (gα1 , gα2 )Return (PK, MSK)

Encap(PK, A = (M, ρ)):s ← Z p , For j = 2 to n: v j ← Z p
v = (s, v2 , . . . , vn )For i = 1 to l: λi = v · Mi , ri ← Z p
C  := g s
For i = 1 to l:−r
Ci := Aλi T ρ(i)i , Di := griψcpa := (A, C , ((Ci , Di ); i = 1, . . . , l))τ ← Hη (ψcpa )For k = 1, 2: κk := Yks ; d := κ1τ κ2(κ, ψ) := (κ1 , (ψcpa , d))Return (κ, ψ)

KeyGen(PK, MSK, S ):For k = 1, 2: lk ← Z p
For k = 1, 2:
Kk := gαk Alk , Lk := glkl
For x ∈ S : Kk,x := T xk
SKS := ((Kk , Lk ,(Kk,x ; x ∈ S )); k = 1, 2)
Return SKS

Decap(PK, SKS , ψ):
If S  A then Return κ̂ :=⊥else τ ← Hη (ψcpa ){ωi ∈ Z p ; i ∈ ρ−1 (S )}← Reconst(ρ−1 (S ), M)
For k = 1, 2:
κˆk := e(Kk , C  )/ωii∈ρ−1 (S ) (e(Lk , C i )e(Kk,ρ(i) , Di ))If κˆ1 τ κˆ2  d then κ̂ :=⊥ else κ̂ := κˆ1
Return κ̂

Fig. A· 2 Our concrete CP-ABKEM (an enhanced Waters CP-ABKEM). (“←” from a set (Z p or HKeyλ )means uniform random sampling.)

Proof. Using any given OW-sel-CCA adversary A as subroutine, we construct a solver B that solves an instanceof the problem of computational q-parallel bilinear DiﬃeHellman exponent assumption with gap on target group, as
follows.
Set up. B is given a random instance of the problem, y,as input (see Appendix D). B initializes its inner state. B
chooses an attribute universe U = {1, . . . , u} at random,
where the size u is bounded by a polynomial in λ. B invokes A on input (λ, U). In return, B receives a target access structure A∗ = (M ∗ , ρ∗ ) from A, where M ∗ is of sizel∗ × n∗ . By the assumption in Theorem 5, l∗ , n∗  q.
For each x = 1, . . . , u, let X x := (ρ∗ )−1 (x). Then B puts
each component T x of PK as

∗
∗
2
∗
n∗
z x ← Z p , T x := gzx(ga/bi ) Mi,1 (ga /bi ) Mi,2 · · · (ga /bi ) Mi,n∗ .
i∈X xNote that if X x is empty, we have T x := gzx .
B chooses α ∈ Z p at random and sets Y1 :=a aqe(g , g )e(g, g)α . Here we implicitly set

Here we have set an implicit relation
α2 = μ − α1 τ∗ .

(A· 2)

B inputs (PK, ψ∗ ) to A. Note that PK determines thecorresponding MSK uniquely.
Answering A’s Queries. (1) Key-Extraction Queries.
When A issues a key-extraction query for an attribute set
S , B has to reply a corresponding secret key SKS .
First, B chooses a random value r1 ∈ Z p . B computes∗
a vector w
 = (w1 , . . . , wn∗ ) ∈ Znp such that w1 = −1 and for∗ −1∗
all i ∈ (ρ ) (S ), w
 · Mi = 0. Note here that S  A∗ , so suchw
 surely exists. Then we implicitly set l1 as∗

l1 := r1 + w1 aq + w2 aq−1 + · · · + wn∗ aq−n +1 .
Then B computes the component L1 and K1 of SKS asq+1−i(ga )wi ,L1 := gl1 = gr1
i=1,...,n∗αK1 := g (g )

a r1

q+2−i

(ga

)wi .

i=2,...,n∗α1 := aq+1 + α .

(A· 1)

B puts PKcpa := (g, T 1 , . . . , T u , A := ga , Y1 ).
B chooses random values y2 , . . . , yn∗ ∈ Z p andr1 , . . . , rl∗ ∈ Z p . For each i = 1, . . . , l∗ , let Ri :=(ρ∗ )−1 (ρ∗ (i))\{i}. Then challenge ciphertext components arecomputed as∗ψ∗cpa := (A∗ , C ∗ := g s = g s ,

∗ 
r 
(Ci∗ := T ρi∗ (i)(ga ) Mi, j y j (gbi s )−zρ∗ (i)j=2,...,n∗

×

 

∗ 
j
(ga sbi /bk ) Mk, j ,Finally, for each x ∈ S , B computes K1,x as   j
 ∗q+1+ j−k/bi wk Mi, j
K1,x := Lzx(ga).
(ga /bi )r1
i∈X x j=1,...,n∗k=1,...,n∗ ,k jNote that if X x is empty, we have K1,x := Lzx .
Now B has to compute the index 2 components
L2 , K2 , K2,x for all x ∈ S . To do so, B chooses a random
value r2 ∈ Z p and computes L2 , K2 , K2 ,x , x ∈ S just in
the same way as to the index 1. Then B converts them asfollows.
∗∗∗

K2 := gμ (K2 )−τ , L2 := (L2 )−τ , K2,x := (K2 ,x )−τ , x ∈ S .

k∈Ri j=1,...,n∗D∗i := g−ri g sbi ), i = 1, . . . , l∗ ).

η ← HKeyλ , τ∗ ← Hη (ψ∗cpa ), μ ← Z p , Y2 := e(g, g)μ /Y1τ ,Then B replies SKS = ((Kk , Lk , (Kk,x ; x ∈ S )); k = 1, 2) toA.
(2) Decapsulation Queries. When A issues a decapsulation
query for (S , ψ = (ψcpa , d)) (where ψcpa is about A), B has
to reply the decapsulation κ̂ to A. To do so, B computes asfollows. (Note that the oracle DDH GT is accessed.)

PK := (PKcpa , Y2 , η), d∗ := e(C ∗ , g)μ , ψ∗ := (ψ∗cpa , d∗ ).

If S  A then κ̂ :=⊥∗Here we have set an implicit relation s = s.
Then a public key PK and a whole challenge ciphertextψ∗ is computed as∗

ANADA et al.: ATTRIBUTE-BASED IDENTIFICATION: DEFINITIONS AND EFFICIENT CONSTRUCTIONS

1101
P(PK = (g, T 1 , . . . , T u , A, Y1 , Y2 , η),
SKS = ((Kk = gαk Alk , Lk = glk ,l(Kk,x = T xk ; x ∈ S); k = 1, 2))):

ψ

Receiving ψ as input:
If S  A then κ̂ :=⊥else τ ← Hη (ψcpa ){ωi ; i ∈ ρ−1 (S )} ← Reconst(ρ−1 (S ), M)
For k = 1, 2 :κˆk := e(Kk , C  )/ i∈ρ−1 (S ) (e(Lk , Ci )e(Kk,ρ(i) , Di ))ωiτ
If κˆ1 κˆ2  d then κ̂ :=⊥ else κ̂ := κˆ1←−

Send κ̂ to V−→
Fig. A· 3κ̂

V(PK, A) :s ← Z p , For j = 2 to n: v j ← Z p ,v := (s, v2 , . . . , vn )For i = 1 to l: λi := v · Mi , ri ← Z p
C  := g s−r
For i = 1 to l: Ci := Aλi T ρ(i)i , Di := griψ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 κ̂ = κ then b := 1 else b := 0, Return b

An interaction of our concrete VP-ABID.
∗

Claim 6: The reply κ̂ = (d/e(C  , g)μ )1/τ−τ to a decapsulation query of A is correct.

else If Verify(PKcpa , ψcpa , S ) = False then κ̂ :=⊥else τ ← Hη (ψcpa )If DDH GT (e(g, g), Y1τ Y2 , e(C  , g), d) = False then κ̂ :=⊥else If τ = τ∗ then Abort //Call this case Abort∗

else κ̂ := (d/e(C  , g)μ )1/(τ−τ )Proof. It is enough to prove that if DDH GT (e(g, g), Y1τ Y2 ,e(C  , g), d) = True, then κ̂ = Y1s . This is deduced by using
the implicit relations (A· 2) as follows.
∗

where Verify is the following PPT algorithm to check consistency of ψcpa :∗κ̂ = ((Y1τ Y2 ) s /e(C  , g)μ )1/(τ−τ ) = (e(g, g)(α1 τ+α2 −μ)s )1/(τ−τ )∗∗= (e(g, g)α1 (τ−τ )s )1/(τ−τ ) = Y1s .


Verify(PKcpa , ψcpa , S ) :∗Claim 7: The challenge ciphertext ψ
rectly distributed.

{ωi ∈ Z p ; i ∈ ρ−1 (S )} ← Reconst(ρ−1 (S ), M)
If e(A, C  ) ={e(Ci , g)e(T ρ(i) , Di )}ωi

= (ψ∗cpa , d∗ ) is cor-

Proof. Using the implicit relations (A· 2), a direct calculation showsi∈ρ−1 (S )then Return True else Return False.

∗

∗

∗

∗

d∗ = e(C ∗ , g)μ = e(g, g) s (α1 τ +α2 ) = (Y1τ Y2 ) s .

Guess. When A returns A’s guess κˆ∗ , B returns Z :=κˆ∗ /e(C ∗ , g)α as B’s guess.
By the above construction, B can perfectly simulate thereal view of A until the case Abort happens. To see why,
we prove the following claims.

Hence ψ∗ = (ψ∗cpa , d∗ ) is legitimate and correctly distributed.

Now we are ready to evaluate the advantage of B in the
OW-sel-CPA game. First, we evaluate the probability thatthe case Abort occurs.

Claim 5: The reply SKS to a key-extraction query of A isa perfect simulation.

Claim 8: The probability that Abort occurs is negligiblein λ. More precisely, the following equality holds.

Proof. First, the index 1 components (K1 , L1 , (K1,x ; x ∈ S ))are correctly distributed, as is proved in the original work of
Waters [23]. By the construction, the index 2’ components(K2 , L2 , (K2 ,x ; x ∈ S )) are distributed in the same way as
the index 1 (but with independent randomness).
For the index 2 components (K2 , L2 , (K2,x ; x ∈ S )), notethat we have implicitly set l2 = l2 (−τ∗ ). Using another implicit relation (A· 2) together, we get∗∗∗

K2 = gμ (K2 )−τ = gμ (gα1 Al2 )−τ = gμ−α1 τ Al2 = gα2 Al2 ,∗∗L2 = (L2 )−τ = (gl2 )−τ = gl2 ,∗Pr[Abort] = Advtcr
CF ,Hfamλ (λ).

Proof. To reduce to the target collision resistance of an employed hash function family Hfamλ , we construct a PPT target collision finder CF by using A as a subroutine. The
construction is done in a similar way to the construction for
Claim 4.

By definition, A wins in the OW-sel-CCA game if andonly if κ̂∗ is correctly guessed. That is, κˆ∗ = Y1s = e(g, g)α1 s .
Using (A· 1) and C ∗ = g s ,Z := κˆ∗ /e(C ∗ , g)α = e(g, g)(a∗K2,x = (K2 ,x )−τ = (T xl2 )−τ = T xl2 , x ∈ S .
+α )sq+1/e(C ∗ , g)α = e(g, g)a

q+1

s

.

This is the definition that B succeeds in computing the answer for the given instance y.

IEICE TRANS. FUNDAMENTALS, VOL.E97–A, NO.5 MAY 2014

1102

Therefore, the probability that B wins is equal to theprobability that A wins and Abort never occurs. So wehave:

Sari Handa
received her B.E. from Meiji
University, and she is with Institute of Information Security (IISEC), Japan. She is interested
in lattice and multi-linear map.

Pr[B wins] = Pr[(A wins) ∧ (¬Abort)]= Pr[A wins] − Pr[(A wins) ∧ ¬(¬Abort)] Pr[A wins] − Pr[Abort].
Substituting advantages and using the equality in Claim 8,
we have:
Advow-sel-cca
A,CP-ABKEM (λ) = Pr[A wins]  Pr[B wins] + Pr[Abort]c-pbdhe-gap= AdvB,(e,G,GT ) (λ) + Advtcr
CF ,Hfamλ (λ).
This is what we should prove in Theorem 5.
Figure A· 3 shows the interaction of the obtained
VP-ABID.
Theorem 6 (Corollary to Theorem 4 and 5): Our PP-ABID
is selectively secure against cMiM attacks under the same
assumptions. More precisely,
c-pbdhe-gap

tcr
Advsel-cmim
A,VP-ABID (λ)  AdvB,(e,G,GT ) (λ) + AdvCF ,Hfamλ (λ).

Hiroaki Anada
received his B.E. and M.E.
from Waseda University, and Ph.D. from Institute of Information Security (IISEC), Japan. He
is with Institute of Systems, Information Technologies and Nanotechnologies (ISIT), Japanand a visitor researcher at IISEC. He is interested in interactive proofs.

Seiko Arita
received his B.E. and M.E. from
Kyoto University, and Ph.D. from Chuo University. He has been interested in prime numbers, algebraic curves and cryptographic protocols. He is with Institute of Information Security(IISEC), Japan.

Yosuke Iwabuchi
received his B.E. from
Tokyo University of Science in 2012, and he iswith Institute of Information Security (IISEC),
Japan.