Attribute-Based Two-Tier Signatures:
Definition and Construction
Hiroaki Anada1,2 , Seiko Arita2 , and Kouichi Sakurai3,11

Institute of Systems, Information Technologies and Nanotechnologies
7F, 2–1–22, Momochihama, Sawara–ku, Fukuoka, 814–0001 JAPANanada@isit.or.jp
2
Institute of Information Security
2–14–1 Tsuruya–cho, Kanagawa–ku, Yokohama, 221–0835 JAPANarita@iisec.ac.jp
3
Department of Informatics, Graduate School and Faculty of Information Scienceand Electrical Engineering, Kyushu University
W2–712, 744 Motooka, Nishi–ku, Fukuoka, 819–0395 JAPANsakurai@inf.kyushu-u.ac.jp

Abstract. Attribute-based signature scheme (ABS) is a functional variant of digital signature scheme proposed in 2008 by Maji et al. The twobasic requirements of ABS (and a hard task to achieve) is collusion resistance and attribute privacy. In this paper, we employ the two-tiersignature (TTS) technique to achieve the collusion resistance. Here TTS
was proposed in 2007 by Bellare et al., where a signer receives two tiersecret keys sequentially. The secondary secret key is served as a onetime key at the timing of signing. First, we propose a definition of an
attribute-based two-tier signature scheme (ABTTS). Then we provide
ABTTS concretely that enjoys existential unforgeability against chosenmessage attacks, collusion resistance and attribute privacy, in the standard model. For the construction, enhancing the Camenisch-Lysyanskayasignature, we construct signature bundle schemes that are secure under
the Strong RSA assumption and the Strong Diffie-Hellman assumption,
respectively. These signature bundle schemes enable ABTTS to achieve
attribute privacy. Then, using the signature bundle as a witness in the
Σ-protocol of the boolean proof, we obtain attribute-based identification
schemes (ABIDs). Finally, by applying the TTS technique to ABIDs, weachieve ABTTSs. A feature of our construction is that ABTTS in the
RSA setting is pairing-free.

Keywords: digital signature, attribute-based, two-tier keys.

1

Introduction

Digital signature scheme is one of the most widely recognized cryptographic primitives. Since its invention, functional variants have been proposed, which include attribute-based signature schemes (ABS) developed

by Guo and Zeng [12] and Maji, Prabhakaran and Rosulek [14] in 2008.
In ABS, a message m is associated with a signing policy f that is described as a boolean formula over signers’ attributes. Then only signers
with attributes that satisfy f can make a legitimate signature σ on m.
A verifier can check whether the signature σ is valid in accordance withthe signing policy f . The two basic requirements of ABS (and a hardtask to achieve) is collusion resistance against collecting secret keys andattribute privacy. Intuitively, ABS is called to have attribute privacy if
any cheating verifier cannot distinguish two distributions of signatures
each of which is generated by different satisfying attribute set.
A two-tier signature scheme (TTS) is a digital signature scheme proposed in 2007 by Bellare et al. [3], in which a signer receives two tier secretkeys sequentially, the latter of which is served as a one-time signing key
at the timing of signing. Accordingly, two tier public keys are issued sequentially. These two-tier keys fit the Fiat-Shamir signature scheme andenable it to achieve existential unforgeability against chosen-message attacks (EUF-CMA) in the standard model.
Our Contribution Our first contribution is to define the syntax of an
attribute-based two-tier signature scheme (ABTTS) for the first time.
The reason why we introduce ABTTS (in a construction of ABS) is toachieve the collusion resistance by employing the TTS technique. The
issuer of a secondary secret key can check integrity of components in a
primary secret keys so that the issuer can avoid collusion attacks.
Our second contribution is to provide ABTTS concretely that enjoys
existential unforgeability against chosen-message attacks, collusion resistance and attribute privacy, in the standard model. It is interesting fromthe view point of theory (and also efficiency) that our ABTTS in the RSA
setting is pairing-free.
Our Approach to Concrete Construction First, enhancing the CamenischLysyanskaya signature, we construct signature bundle schemes that are
secure under the Strong RSA assumption and the Strong Diffie-Hellman
assumption, respectively. These signature bundle schemes later enable
ABTTS to achieve attribute privacy. Then, using the signature bundle
as a witness in the Σ-protocol of the boolean proof, we obtain attributebased identification schemes (ABIDs). Finally, by applying the TTS technique to ABIDs, we achieve ABTTSs.

2

Table 1. Comparison of security, functionality and signature length.
SchemeMaji
et al. [14]OT
[16]Herranz[13]
Ghadafiet al. [8]Anadaet al. [2]Our ABTTS

Security
Model
Std.
Std.
R.O.
R.O.
R.O.
Std.

Assumption

Access Pairing Attribute
Formula -Free Privacy

q-SDH
∧DLIN
Mono.
DLIN
∧CR
Non-m.
q-SRSA∧[DDH in
QR(N )]∧CR
Mono.
q-SDH∧DDH∧
DLog∧CR
Mono.
[DLog∨RSAInv]
∧CR
Mono.
[q-SRSA∨q-SDH]
∧CR
Mono.

X
X
X

Length of
Signature(2λ)×
X(info.) (51l + 2r + 18λl)(2λ)×
X(info.)(9l + 11)κ
λrsa (5 + λrsa)lX(comp.) +λrsa 3 − κ(θ − 1)(2λ)(3l + r + 3)
+λ(8l + 4)(2λ̂)l+λ̂(4l − 1)(2λ̂)2lX(info.)+λ̂2lComparison: Security, Functionality and Signature Length We
compare our ABTTS with previously proposed schemes from the view
point of security, functionality and signature length. The comparison issummarized in Table 1 with notations as follows. A prime of bit length
λ (the security parameter in the discrete logarithm setting) is denotedby p. Though a pairing map e should be analysed for the asymmetric bilinear groups [11], we simply evaluate the symmetric case in which both
source groups are Gp of order p. We assume that an element of Gp isrepresented by 2λ bits. l and r mean the number of rows and columnsof the share-generating matrix for monotone access formula f (that is,an access structure), respectively. CR means the collision resistance of an
employed hash function. q-SDH means the Strong Diffie-Hellman assumption with q-type input for bilinear groups [4]. DLIN means the Decisional
Linear assumption for bilinear groups [16]. DDH means the Decisional
Diffie-Hellman assumption for a cyclic group [8]. DLog means the Discrete Logarithm assumption for a cyclic group [8]. q-SRSA means theStrong RSA assumption with q-type input [13]. DDH in QR(N ) means
the Decisional Diffie-Hellman assumption for quadratic residues modulo
N (the RSA modulus) [13]. “info.” means information-theoretic securityand “comp.” means computational security. λrsa means the security parameter in the RSA setting, and λ̂ means the security parameter in either
the RSA setting or the discrete logarithm setting.
First, note that our scheme assumes the secondary secret key andthe secondary public key are issued as one-time keys at the timing of3

signing. This means the signer and the verifier should be on-line and theyneed to verify a certificate of the secondary public key. One possibilityof executing such a process is to use Online Certificate Status Protocol(OCSP) by RFC 6990 [9].
The scheme of [16] has advantages in the security model, access formula and information-theoretically secure attribute privacy, whereas our
ABS realizes shorter length of signature (less than a half). The schemeof [13] is in the RSA setting and its security parameter λrsa is almost
10 times longer than λ in the DLog setting. For example, λrsa = 2048 isalmost equivalent to λ = 224-bit security [17]. (θ is the threshold valueof the threshold-type access structure. κ is explained in the work [13].)
Therefore, our ABS in the DLog setting realizes shorter length of a signature.

2

Preliminaries

The security parameter is denoted as λ. Bit length of a string x is denoted?
as |x|. The expression “a = b” returns a value 1 if a = b and 0 otherwise.
?

The expression “a ∈ S” returns a value 1 if a ∈ S and 0 otherwise.

Σ-protocol [6, 7] A Σ-protocol on a binary NP relation R is a publiccoin 3-move protocol between interactive PPT algorithms P and V on
initial input (x, w) ∈ R for P and x for V. x and w are called a statement
and a witness, respectively. P sends the first message called a commitment
Cmt, then V sends a random bit string called a challenge Cha, and P
answers with a third message called a response Res. Then V applies adecision test on (x, Cmt, Cha, Res) to return accept (1) or reject (0).
If V accepts, then the triple (Cmt, Cha, Res) is said to be an accepting
conversation. Cha is chosen uniformly at random from the challenge space
ChaSp(1λ ) := {1, 0}l(λ) with l(·) being a super-log function.
The Σ-protocol is written by a PPT algorithm Σ as follows. Cmt ←Σ1 (x, w): the process of selecting the first message Cmt according to theprotocol Σ on input (x, w) ∈ R. Similarly we denote Cha ← Σ2 (1λ ),Res ← Σ3 (x, w, Cmt, Cha) and b ← Σvrfy (x, Cmt, Cha, Res). The Σprotocol must possess the three properties: completeness, special soundness and honest-verifier zero-knowledge [6, 7]. As a zero-knowledge proofof-knowledge system, we denote Σ as ZKPK[γ : Γ ], where γ is a knowledge to be proved and Γ is the condition that γ should satisfy.
4

Signature Bundle Scheme [14] A signature bundle (a credential bundle in [14]) scheme SB is an extended notion of a signature scheme. It
consists of three PPTs: SB = (SB.KG, SB.Sign, SB.Vrfy).
SB.KG(1λ ) → (PK, SK). Given 1λ as input, it returns a public key PK
and a secret key SK.
SB.Sign(PK, SK, (mi )ni=1 ) → (τ, (σi )ni=1 ). Given PK, SK and messages(mi )ni=1 , it returns a tag τ and signatures (σi )ni=1 . n is bounded by apolynomial in λ.
SB.Vrfy(PK, (mi )ni=1 , (τ, (σi )ni=1 )) → 1/0. Given PK, messages (mi )ni=1 ,a tag τ and signatures (σi )ni=1 , it returns 1 or 0.
∗∗
A PPT adversary F tries to make a forgery ((m∗i )ni=1 , (τ ∗ , (σi∗ )ni=1 )).
Here τ ∗ is called a target tag. An existential forgery by a chosen-message
attack is defined by:
Expreuf-cma(1λ , U)
SB,F∗∗

(PK, SK) ← SB.KG(1λ ), ((m∗i )ni=1 , (τ ∗ , (σi∗ )ni=1 )) ← F SBSIGN (PK)∗∗n
If SB.Vrfy(PK, (m∗i )i=1
, (τ ∗ , (σi∗ )ni=1 )) = 1

then Return Win else Return Lose
Giving a vector of messages (mi )ni=1 , F queries SBSIGN (PK, SK, ·) for avalid signature bundle (τ, (σi )ni=1 ). τ ∗ should be different from any queriedtag τ , or, whenever τ ∗ is equal to a queried tag τ , it should hold that∗{m∗i }ni=1 6⊆ {mi }ni=1 for any queried (mi )ni=1 . The advantage of F over
SB in the experiment of existential forgery by chosen-message attack isdefdefined as Adveuf-cma(λ, U) = Pr[Expreuf-cma(1λ , U) returns Win].
SB,F
SB,F
Definition 1 SB is called existentially unforgeable against chosen-message(λ, U) is negligible in λ.
attack if, for any PPT F, Adveuf-cma
SB,F
Access Structure [10] Let U = {ati }ui=1 be an attribute universe.
|U| = u is bounded by a polynomial in λ (U is called a small universe).
Let f = f (Xat1 , . . . , Xata ) be a monotone boolean formula over U ={Xat }at , where boolean connectives are AND-gate (∧) and OR-gate (∨).
In this paper, we assume that no NOT-gate (¬) appears in f . In otherwords, we consider only a monotone access formula f .4 We denote the setof subscripts (that is, attributes) {at1 , . . . , ata } as At(f ) and the arity a
as arity(f ), respectively. For S ∈ 2U , we evaluate the boolean value of f at
4

This limitation can be removed by adding negation attributes to U for each attributein the original U though the size of the attribute universe |U| doubles.

5


?
def
S as: f (S) = f Xat ← [at ∈ S]; at ∈ At(f ) ∈ {1, 0}. We call a boolean
formula f with this map an access formula over U. An access formula
corresponds to a signing policy in the case of attribute-based signatures.
An access formula f can be represented by a finite binary tree Tf .
Each inner node corresponds to an AND-gate (∧) or OR-gate (∨) inf . Each leaf node l corresponds to a term Xat (not a variable Xat )in f in one-to-one way. For a finite binary tree T , we denote the root
node, the set of all nodes, the set of all leaf nodes, the set of all inner
nodes (all nodes excluding leaf nodes) and the set of all tree-nodes (allnodes excluding the root node) as r(T ), Node(T ), Leaf(T ), iNode(T )and tNode(T ), respectively. Then an attribute map ρ(·) is defined as:defρ : Leaf(T ) → U, ρ(l) = (at that corresponds to l). If ρ is not injective,then we call the case multi-use of attributes.
Attribute-Based Identification Scheme [1] An attribute-based identification scheme, ABID, consists of four PPT algorithms: (ABID.Setup, ABID.KG, P, V).
ABID.Setup(1λ , U) → (PK, MSK). Given the security parameter 1λand an attribute universe U, it returns a public key PK and a mastersecret key MSK.
ABID.KG(PK, MSK, S) → SKS . Given the public key PK, the mastersecret key MSK and an attribute set S ⊂ U, it returns a secret key SKS
that corresponds to S.
P(PK, SKS ) and V(PK, f ). P and V are interactive algorithms calleda 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 anauthority. V takes as input the public key PK and an access formula f . P
is provided V’s access formula f by the first move. P and V interact witheach other for at most constant rounds. Then, V returns its decision 1 or
0. When it is 1, we say that V accepts P for f . When it is 0, we say that V
rejects P for f . We demand correctness of ABID that for any λ, for any S
and for any f such that f (S) = 1, Pr[(PK, MSK) ← Setup(1λ , U); SKS ←KG(PK, MSK, S); b ← hP(PK, SKS ), V(PK, f )i : b = 1] = 1.
An adversary A tries to make a verifier V accept with an access formula f ∗ of his choice. Here f ∗ is called a target access formula. A concurrent attack is defined by:λExprmtca
ABID,A (1 , U)
qprv

(PK, MSK) ← ABID.Setup(λ, U), (f ∗ , st) ← AKG,Pj |j=1 (PK, U)b ← hA(st), V(PK, f ∗ )i, If b = 1 then Return Win else Return Lose6

Giving an attribute set Si , A queries KG(PK, MSK, ·) for the secret key
0 ,...,q
SKSi . In addition, A invokes provers Pj (PK, SK· ), j = 1, . . . , qprv
prv ,by giving a pair (Sj , fj ). Acting as a verifier with an access formula fj , A
interacts with each Pj (PK, SKSj ) concurrently. In the above we consider
the adaptive target f ∗ . In key-extraction queries, each attribute set Si
must satisfy f ∗ (Si ) = 0. In interactions with each prover, f ∗ (Sj ) = 0.
The advantage of A over ABID in the game of concurrent attack is dedefca
λfined as Advca
ABID,A (λ) = Pr[ExprmtABID,A (1 , U) returns Win]. ABID iscalled secure against concurrent attacks if, for any PPT A, Advca
ABID,A (λ)
is negligible in λ.
Strong RSA Assumption [5] Let p = 2p0 + 1 denote a safe prime (p0is also a prime). Let N denote the special RSA modulus; that is, N = pq
where p = 2p0 +1 and q = 2q 0 +1 are two safe primes such that |p0 | = |q 0 | =λ − 1. We denote the probabilistic algorithm that generates such N at
random on input 1λ as RSAmod. Let QRN ⊂ Z∗N denote the set of quadratic
residues modulo N ; that is, elements a ∈ Z∗N such that a ≡ x2 mod N forsome x ∈ Z∗N . The strong RSA assumption [5] states that for any PPT A,
the following advantage is negligible in λ: Advsrsa
RSAmod,S (λ, U) := Pr[N ←$RSAmod(1λ ), g ← QRN , (V, e) ← A(N, g) : e > 1 ∧ V e ≡ g mod N ].
Strong Diffie-Hellman Assumption [4] Let p denote a prime of bit
length λ. Let e : G1 × G2 → GT denote bilinear groups of order p,
where G1 is generated by g, G2 is generated by h and GT is generated bye(g, h) 6= 1GT . We denote the probabilistic algorithm that generates suchparameters params := (p, G1 , G2 , GT , e) on input 1λ as BlGrp. Let q denote a number that is less than a fixed polynomial in λ. The strong DiffieHellman assumption [4] states that for any PPT A, the following advan$

λtage is negligible in λ: Advsdh
BlGrp,S (λ, U) := Pr[params ← BlGrp(1 ), α ←2qZp , (u, e) ← A(params, (g, g α , g α , . . . , g α , h, hα )) : uα+e = g].

3

Syntax of Attribute-Based Two-Tier Signature Scheme

In this section, we propose a definition of syntax of an attribute-based twotier signature scheme (ABTTS). Then, we define a chosen-message attack(CMA) on ABTTS where an adversary makes an existential forgery, andwe define the existential unforgeability (EUF) against CMA.
7

3.1

Definition: Syntax of ABTTS

An attribute-based two-tier signature scheme, ABTTS, consists of five PPTs:
ABTTS= (ABTTS.Setup, ABTTS.KG, ABTTS.SKG, ABTTS.Sign,
ABTTS.Vrfy).
ABTTS.Setup(1λ , U) → (MSK, PK). Given the security parameter 1λand the attribute universe U, it returns a master secret key MSK and apublic key PK.
ABTTS.KG(MSK, PK, S) → SKS . Given the master secret key MSK,
the public key PK and an attribute set S ⊂ U, it returns a secret key
SKS that corresponds to S.
ABTTS.SKG(MSK, PK, SKS , f ) → (SSKS,f , SPKf ). Given the mastersecret key MSK, the public key PK, a secret key SKS and an accessformula f , it returns a pair (SSKS,f , SPKf ) of a secondary secret key anda secondary public key.
ABTTS.Sign(PK, SKS , SSKS,f , SPKf , (m, f )) → σ. Given the public
key PK, a secret key SKS , a secondary secret key SSKS,f , a secondary
public key SPKf and a pair (m, f ) of a message m ∈ {1, 0}∗ and an accessformula f , it returns a signature σ.
ABTTS.Vrfy(PK, SPKf , (m, f ), σ) → 1/0. Given the public key PK, asecondary public key SPKf , a pair (m, f ) of a message and an access formula and a signature σ, it returns a decision 1 or 0. When it is 1, we saythat ((m, f ), σ) is valid. When it is 0, we say that ((m, f ), σ) is invalid.
We demand correctness of ABTTS that, for any λ, any U, any S ⊂ U andany (m, f ) such that f (S) = 1, Pr[(MSK, PK) ← ABTTS.Setup(1λ , U),
SKS ← ABTTS.KG(MSK, PK, S), (SSKS,f , SPKf )← ABTTS.SKG(MSK, PK, SKS , f ), σ ← ABTTS.Sign(SKS , PK, SSKS,f , SPKf , (m, f )),b ← ABS.Vrfy(PK, SPKf , (m, f ), σ) : b = 1] = 1.
3.2

Security against Chosen-Message Attacks on ABTTS

A PPT adversary F tries to make a forgery ((m∗ , f ∗ ), σ ∗ ) that consists ofa message, a target access formula and a signature. The following experiλment Expreuf-cma
ABTTS,F (1 , U) of a forger F defines the chosen-message attack
making an existential forgery.
λExpreuf-cma
ABTTS,F (1 , U) :(PK, MSK) ← ABTTS.Setup(1λ , U)((m∗ , f ∗ ), σ ∗ ) ← F ABT T SKG,ABT T SSPK,ABT T SSIGN (PK)If ABTTS.Vrfy(PK, SPKf , (m∗ , f ∗ ), σ ∗ ) = 1
then Return Win else Return Lose8

In the experiment, F issues key-extraction queries to its oracle ABT T SKG,
secondary public key queries to its oracle ABT T SSPK and signing queries
to its oracle ABT T SSIGN . Giving an attribute set Si , F queries ABT T SKG(MSK, PK, ·)for a secret key SKSi . Giving an attribute set S and an access formulaf , F queries ABT T SSPK(MSK, PK, SK· , ·) for a secondary public key
SPKf . Giving an attribute set Sj and a pair (mj , fj ) of a message and anaccess formula, F queries ABT T SSIGN (PK, SK· , SSK·,· , SPK· , (·, ·)) for avalid signature σ when f (Sj ) = 1. As a rule of the two-tier signature, eachpublished secondary public key SPKf can be used only once to obtain asignature [3].
f ∗ is called a target access formula of F. Here we consider the adaptive
target case in the sense that F is allowed to choose f ∗ after seeing PK andissuing three queries. Two restrictions are imposed on F: 1) f ∗ (Si ) = 0 for
all Si in key-extraction queries; 2) (m∗ , f ∗ ) was never queried in signing
queries. The numbers of key-extraction queries and signing queries areat most qke and qsig , respectively, which are bounded by a polynomial
defin λ. The advantage of F over ABTTS is defined as Adveuf-cma
ABTTS,F (λ, U) =λ , U) returns Win].
Pr[Expreuf-cma(1
ABTTS,F

Definition 2 (EUF-CMA of ABTTS) ABTTS is called existentially unforgeable against chosen-message attacks if, for any PPT F and any U,
Adveuf-cma
ABTTS,F (λ, U) is negligible in λ.
Then we define attribute privacy of ABTTS.
Definition 3 (Attribute Privacy of ABTTS) ABTTS is called to haveattribute privacy if, for all (PK, MSK) ← ABS.Setup(1λ , U), for all
message m, for all attribute sets S1 and S2 , for all signing keys SKS1 ←ABS.KG(PK, MSK, S1 ) and SKS2 ← ABS.KG(PK, MSK, S2 ), for all
secondary keys (SSKS1 ,f , SPKf ) ← ABTTS.SKG(MSK, PK, SKS , f ) and(SSKS2 ,f , SPKf ) ← ABTTS.SKG(MSK, PK, SKS , f ) and for all accessformula f such that [f (S1 ) = 1 ∧ f (S2 ) = 1] ∨ [f (S1 ) 6= 1 ∧ f (S2 ) 6= 1],
two distributions
σ1 ← ABTTS.Sign(PK, SKS1 , SSKS1 ,f , SPKf , (m, f )) andσ2 ← ABTTS.Sign(PK, SKS2 , SSKS2 ,f , SPKf , (m, f )) are identical.

4

Σ-protocol for Monotone Access Formula

In this section, we enhance the identification protocol by Okamoto [15]to the boolean proof system Σf proposed by Anada et al. [2].
9

4.1

Our Language Lf

We assume R to be an NP-relation. Let R(·, ·) : ({1, 0}∗ )2 → {1, 0} denote?

the relation-function which returns (x, w) ∈ R. Let f = f ((Xij )aj=1 ) be aboolean formula over boolean variables {Xi }i .
Definition 4 (Language for f ) The relation Rf and the corresponding
language Lf for a boolean formula f are:
def
Rf = { x = (xij )aj=1 , w = (wij )aj=1 ∈ {1, 0}∗ × {1, 0}∗ ; f (R(xij , wij )aj=1 ) = 1},
def

Lf = {x ∈ {1, 0}∗ ; ∃w, (x, w) ∈ Rf }.
We consider hereafter the case that w is divided into (wij )aj=1 = (eij , sij )aj=1 .
(In/after the next section, we will consider the special case that eij , j =1, . . . , a, are all equal to a single element e. The common component e
will be a tag τ of a signature bundle. )4.2

Our Σ-protocol Σf for Lf

Our Σ-protocol Σf is a zero-knowledge proof-of-knowledge ZKPK[w :=(wρ(l) )l := (eρ(l) , sρ(l) )l , l ∈ Leaf(Tf ) : x := (equations)] for the language
Lf , where the equations are for all the leaf nodes:
e

s

ρ(l)
ρ(l)
Zρ(l) = Zρ(l),1Zρ(l),2, l ∈ Leaf(Tf ).

(1)

In the above equation, Zρ(l) is represented by (eρ(l) , sρ(l) ) to the base(Zρ(l),1 , Zρ(l),2 ). A prover P(x, w, f ) and a verifier V(x, f ) execute ourΣ-protocol in the following way.
P(x, w, f ). To prove the knowledge of those representations (eρ(l) , sρ(l) ),P computes the first message, a commitment (Cmtl )l , as follows. LetZ̄ be the exponent domain for the above expression. To do the compu$

tation honestly at a leaf l, P chooses ηe,l , ηs,n ← Z̄, and puts Cmtl :=
η

$

η

e,l
s,n
Zρ(l),1Zρ(l),2. To simulate the computation at a leaf l, P chooses ηe,l , θs,l ←Z̄, and in addition, (cn )n , cn ∈ Z̄. Here (cn )n are chosen in accordance withthe so called boolean proof system of Anada et al. [2]. Then P puts forθs,l−cl θe,leach leaf l θe,l := ηe,l + cl eρ(l) , and Cmtl := Zρ(l)Zρ(l),1 Zρ(l),2. P sends(Cmtl )l to a verifier V.
V(x, f ). Receiving (Cmtl )l , V(x, f ) chooses the second message: a chal-$lenge Cha ← Z̄, uniformly at random, and sends Cha to P.
10

P(x, w, f ). Receiving Cha, P completes to compute the third message;
that is, P completes the division (Chan := cn )n such that Char(Tf ) =Cha, and a response (Resl := (θe,l , θs,l ))l with θe,l := ηe,l + cl eρ(l) , θs,l :=ηs,l + cl vl . P sends (Chal )l and (Resl )l to V.
V(x, f ). Receiving (Chal )l and (Resl )l , V checks the integrity of thedivision (Chal )l . Then V verifies:
?

θ

θ

−cl
s,l
e,l
, l ∈ Leaf(Tf ).
Zρ(l),2Zρ(l),1
Cmtl = Zρ(l)(2)

According to the division rule of Anada et al. [2], the integrity of (Chal =cl )l can be checked as follows: From the leaves to the root, and at every
inner node n ∈ iNode(Tf ) as well as its two children ch1 , ch2 ;?

• If n is an AND node (∧), then verify cch1 = cch2 . If so, put cn := cch1 .
• Else if n is an OR node (∨), then just put cn := cch1 + cch2 .
?

• If n is the root node, then verify cn = Cha.
• Repeat until all n ∈ iNode(Tf ) are verified.
Our Σf can be shown to possess the three requirements of Σ-protocol:
completeness, special soundness and honest-verifier zero-knowledge.

5

Signature Bundle Scheme in RSA

In this section, we propose a signature bundle scheme in the RSA setting by extending the Camenisch-Lysyanskaya signature scheme [5]. We
first construct the scheme. Then we discuss its EUF-CMA security. (Thescheme in the discrete logarithm setting is proposed in Appendix A.)
5.1

Construction of Our SB in RSA

Our signature bundle scheme SB = (SB.KG, SB.Sign, SB.Vrfy) is described as follows. Let lM be a parameter. The message space M consistsof all binary strings of length lM . Let n = n(λ) denote the maximum
number of messages made into a bundle, which is a polynomial in λ.
SB.KG(1λ ) → (PK, SK). Given 1λ , it chooses a special RSA modulus
N = pq of length lN = λ, where p = 2p0 + 1 and q = 2q 0 + 1 are$safe primes. For i = 1 to n, it chooses gi,0 , gi,1 , gi,2 ← QRN . It puts
PK := (N, (gi,0 , gi,1 , gi,2 )ni=1 ) and SK = p, and returns (PK, SK).
SB.Sign(PK, SK, (mi )ni=1 ) → (τ, (σi )ni=1 ). Given PK, SK and messages(mi )ni=1 each of which is of length lM , it chooses a prime e of length11le = lM + 2 at random. For i = 1 to n, it chooses an integer si of length
ls = lN + lM + l at random, where l is a security parameter, and it
computes the value Ai :1

m i si e
Ai := (gi,0 gi,1
gi,2 ) .

(3)

It puts τ = e and σi = (si , Ai ) for each i and returns (τ, (σi )ni=1 ).
SB.Vrfy(PK, (mi )ni=1 , (τ, (σi )ni=1 )) → 1/0. Given PK, (mi )ni=1 and a signature bundle (τ, (σi )ni=1 ), it verifies whether the following holds: e := τm i siis of length le and for i = 1 to n: Aei = gi,0 gi,1
gi,2 .
5.2

Security of Our SB in RSA

Theorem 1 (EUF-CMA of Our SB in RSA) Our signature bundle scheme
SB is existentially unforgeable against chosen-message attacks under theStrong RSA assumption.

6

Attribute-Based ID Scheme in RSA

In this section, we combine two building blocks to obtain our attributebased identification scheme; that is, the Σ-protocol Σf in Section 4.2 andthe signature bundle scheme SB in Section 5.1.
6.1

Construction of Our ABID in RSA

ABID.Setup(1λ , U) → (MSK, PK). Given the security parameter 1λand an attribute universe U, it chooses a special RSA modulus N =pq, p = 2p0 + 1, q = 2q 0 + 1 of length lN = 2λ. For at ∈ U, it chooses$$

gat,0 , gat,1 , gat,2 ← QRN and a hash key µ ← Hashkeysp(1λ ) of a hashfunction Hashµ with the value in Zp . It puts PK := (N, (gat,0 , gat,1 , gat,2 )at∈U , µ, U)
and MSK := p. It returns PK and MSK.
ABID.KG(MSK, PK, S) → SKS . Given PK, MSK and an attribute
subset S, it chooses a prime e of length le . For at ∈ S, it computes$

1aat ← Hashµ (at), sat ← Z of length le , Aat := (g0 g1aat g2sat ) e . It puts
SKS := (e, (sat , Aat )at∈S ).
P(SKS , PK, f ) and V(PK, f ) execute Σf with the following precompu$

tation. For at ∈ At(f ), P chooses rat ← Z of length le . If at ∈ S then$$s0at := sat + erat , A0at := Aat g2−rat . Else s0at ← Z of length le , A0at ← Z∗N .
aat
P puts Zat := gat,0 gat,1, Zat,1 := A0at , Zat,2 := gat,2 . Then the statement for Σf is x := (xat := (Zat , Zat,1 , Zat,2 ))at and the witness is12w := (τ := e, (wat := s0at )at ), where at ∈ At(f ) for x and w. P sends
the randomized values (A0at )at to V for V to be able to compute the statement x.
After the above precomputation, P and V can execute Σf for the
language Lf . In other words, P and V execute ZKPK[(e, s0ρ(l) )l , l ∈Leaf(Tf ) : equations], for the language Lf , where equations are: Zρ(l) =
s0

ρ(l)
e
Zρ(l),1Zρ(l),2, l ∈ Leaf(Tf ). Note that V verifies whether the following verification equations hold or not for all the leaf nodes:

?

θ 0

θ

−cl
e,l
s ,l
Zρ(l),2, l ∈ Leaf(Tf ).
Zρ(l),1
Cmtl = Zρ(l)(4)

V returns 1 or 0 accordingly.
6.2

Security of Our ABID in RSA

Claim 1 (Concurrent Security of Our ABID under a Single Tag)
Our ABID is secure against concurrent attacks if our signature bundle
scheme SB is existentially unforgeable against chosen-message attacks andif the extracted values e by the extractor of the underlying Σ-protocol Σf
is a single value.
Note that Claim 1 is needed only as intermediate result. That is, theassumption that the extracted value e is a single value is assured by thetwo-tier keys issuer, ABTTS.SKG, in the next section.

7

Attribute-Based Two-Tier Signature Scheme in RSA

In this section, we construct our ABTTS concretely. By applying themethod of two-tier keys to our ABID in the last section, we attain the
ABTTS scheme. Our ABTTS enjoys EUF-CMA, collusion resistance andattribute privacy, in the standard model.
The critical point is that the secondary key generator ABTTS.SKG
can issue a legitimate statement x for the boolean proof system Σf . Hence
our ABTTS can avoid collusion attacks on secret keys.
7.1

Construction of Our ABTTS in RSA

ABTTS.Setup(1λ , U) → (MSK, PK). Given the security parameter 1λand an attribute universe U, it chooses a special RSA modulus N =pq, p = 2p0 + 1, q = 2q 0 + 1 of length lN = 2λ. For at ∈ U, it chooses
13

$

$

gat,0 , gat,1 , gat,2 ← QRN and a hash key µ ← Hashkeysp(1λ ) of a hashfunction Hashµ with the value in Zp . It puts PK := (N, (gat,0 , gat,1 , gat,2 )at∈U , µ, U)
and MSK := p. It returns PK and MSK.
ABTTS.KG(MSK, PK, S) → SKS . Given PK, MSK and an attribute
subset S, it chooses a prime e of length le . For at ∈ S, it computes$

1aat ← Hashµ (at), sat ← Z of length le , Aat := (g0 g1aat g2sat ) e . It puts
SKS := (e, (sat , Aat )at∈S ) and returns SKS .
ABTTS.SKG(MSK, PK, SKS , f ) → (SSKS,f , SPKf ). Given MSK, PK,
the secret key SKS and an access formula f , it first checks whether thecomponents eρ(l) in SKS , ρ(l) ∈ S, are equal to a single value e or not. If
it is false, then it aborts. Then it computes the statement for Σf , x :=(xat := (Zat , Zat,1 , Zat,2 ))at , and the witness w := (τ := e, (wat := s0at )at ),where at ∈ At(f ) for x and w. Then it runs the prover P according to Σfas ((Cmtl )l , st) ← P(SKS , PK, f ). Then it puts SSKS,f := (w, Cmt k st)
and SPKf := (x, Cmt). It returns SSKS,f and SPKf .
ABTTS.Sign(PK, SKS , SSKS,f , SPKf , (m, f )) → σ. Given PK, SKS ,the secondary secret key SSKS,f , the secondary public key SPKf , anda pair (m, f ) of a message in {1, 0}lM and an access formula f , it computes Cha ← Hashµ ((A0at )at k (Cmtl )l k m). Then, it runs the prover P
according to Σf as ((Chal )l , (Resl )l ← P((Cmtl )l k Cha k, st). Finally,
it returns the signature σ := ((A0at )at , (Cmtl )l , (Chal )l , (Resl )l ).
ABTTS.Vrfy(PK, SPKf , (m, f ), σ) → 1/0. Given PK, the secondary
public key SPKf , a pair (m, f ) and a signature σ, it first computes thestatement for Σf , x := (xat := (Zat , Zat,1 , Zat,2 ))at , and the witness
w := (τ := e, (wat := s0at )at ), where at ∈ At(f ) for x and w. Then it
computes Cha ← Hashµ ((A0at )at k (Cmtl )l k m). Then, it runs the verifier V according to Σf as acc or 0 ← V(PK, f, (Cmtl )l k Cha k (Resl )l ).
It returns 1 or 0 accordingly.

7.2

Security of Our ABTTS in RSA

Theorem 2 (EUF-CMA of Our ABTTS in RSA) Our attribute-based
two-tier signature scheme ABTTS is existentially unforgeable against chosenmessage attacks under the Strong RSA assumption in the standard model.
Theorem 3 (Attribute Privacy of Our ABTTS in RSA) Our attributebased two-tier signature scheme ABTTS has attribute privacy.
14

8Conclusions

We defined the attribute-based two-tier signature scheme (ABTTS). Then
we provided ABTTS concretely that enjoys EUF-CMA, collusion resistance and attribute privacy, in the standard model.
Acknowledgements Concerning the first and the second authors, thiswork is partially supported by Grants-in-Aid for Scientific Research; Research Project Number:15K00029.

References
1. H. Anada, S. Arita, S. Handa, and Y. Iwabuchi. Attribute-based identification:
Definitions and efficient constructions. In ACISP 2013, volume 7959 of LNCS,
pages 168–186. Springer, 2013.
2. H. Anada, S. Arita, and K. Sakurai. Attribute-based signatures without pairings
via the fiat-shamir paradigm. In ASIAPKC2014, volume 2 of ACM-ASIAPKC,
pages 49–58. ACM, 2014.
3. M. Bellare and S. Shoup. Two-tier signatures, strongly unforgeable signatures,and fiat-shamir without random oracles. In Public Key Cryptography - PKC 2007,
10th International Conference on Practice and Theory in Public-Key Cryptography,
Beijing, China, April 16-20, 2007, Proceedings, pages 201–216, 2007.
4. D. Boneh and X. Boyen. Efficient selective-id secure identity-based encryption
without random oracles. In EUROCRYPT 2004, volume 3027 of LNCS, pages
223–238. Springer, 2004.
5. J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In
Security in Communication Networks, Third International Conference, SCN 2002,
Amalfi, Italy, September 11-13, 2002. Revised Papers, pages 268–289, 2002.
6. R. Cramer. Modular Designs of Secure, yet Practical Cyptographic Protocols. PhD
thesis, University of Amsterdam, Amsterdam, the Netherlands, 1996.
7. I.
Damgård.
On
σ-protocols.
In
CourseNotes,
https://services.brics.dk/java/courseadmin/CPT/documents, 2011.
8. A. El Kaafarani, L. Chen, E. Ghadafi, and J. H. Davenport. Attribute-based
signatures with user-controlled linkability. In Cryptology and Network Security- 13th International Conference, CANS 2014, Heraklion, Crete, Greece, October
22-24, 2014. Proceedings, pages 256–269, 2014.
9. I. E. T. Force. Request for comments: 6960. http://tools.ietf.org/html/rfc6960.
10. V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption forfine-grained access control of encrypted data. In ACM-CCS ’06, volume 263, pages
89–98. ACM, 2006.
11. R. Granger, T. Kleinjung, and J. Zumbrägel. Breaking ’128-bit secure’ supersingular binary curves - (or how to solve discrete logarithms in f 4 1223 and f 12 367 ).
2
2
In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, pages
126–145, 2014.
12. S. Guo and Y. Zeng. Attribute-based signature scheme. In ISA ’08, pages 509–511.
IEEE, 2008.

15

13. J. Herranz. Attribute-based signatures from rsa. Theoretical Computer Science,
527:73–82, 2014.
14. H. K. Maji, M. Prabhakaran, and M. Rosulek. Attribute-based signatures. In
CT-RSA 2011, volume 6558 of LNCS, pages 376–392. Springer, 2011. Full version
available at IACR Cryptology ePrint Archive, 2010/595, http://eprint.iacr.org/.
15. T. Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In Advances in Cryptology - CRYPTO ’92, 12th Annual
International Cryptology Conference, Santa Barbara, California, USA, August 1620, 1992, Proceedings, pages 31–53, 1992.
16. T. Okamoto and K. Takashima. Efficient attribute-based signatures for nonmonotone predicates in the Standard Model. In PKC 2011, volume 6571 of LNCS,
pages 35–52. Springer, 2011.
17. M. Yasuda, T. Shimoyama, J. Kogure, and T. Izu. On the strength comparison of
the ECDLP and the IFP. In Security and Cryptography for Networks - 8th International Conference, SCN 2012, Amalfi, Italy, September 5-7, 2012. Proceedings,
pages 302–325, 2012.

A

Signature Bundle Scheme in Discrete Log

Our pairing-based Signature Bundle Scheme, SB = (SB.KG, SB.Sign, SB.Vrfy),
is described as follows.
SB.KG(1λ ) → (PK, SK). Given 1λ , it executes a group generator BlGrp(1λ )$to get (p, G1 , G2 , GT , e(·, ·)). For i = 1 to n, it chooses gi,0 , gi,1 , gi,2 ←$$G1 , h0 ← G2 , α ← Zp and it puts h1 := hα0 . It puts PK := ((gi,0 , gi,1 , gi,2 )ni=1 , h0 , h1 )and SK := α, and returns (PK, SK).
SB.Sign(PK, SK, (mi )ni=1 ) → (τ, (σi )ni=1 ). Given PK, SK and messages$(mi )ni=1 each of which is of length lM , it chooses e ← Zp . For i = 1 to n,$

it chooses si ← Zp , and it computes the value Ai :1

mi si α+eAi := (gi,0 gi,1
gi,2 ).

(5)

It puts τ = e and σi = (si , Ai ) for each i and returns (τ, (σi )ni=1 ).
SB.Vrfy(PK, (mi )ni=1 , (τ, (σi )ni=1 )) → 1/0. Given PK, (mi )ni=1 and (τ, (σi )ni=1 ),m i siit verifies whether the following holds: e(Ai , he0 h1 ) = e(gi,0 gi,1
gi,2 , h0 ), i =1, . . . , n.
Theorem 4 (EUF-CMA of Our SB in Discrete Log) Our signaturebundle scheme SB is existentially unforgeable against chosen-message attack under the Strong Diffie-Hellman assumption.
Our ABID and ABTTS in the discrete logarithm setting will be given in
the full version.

16