Attribute-Based Signatures without Pairings via theFiat-Shamir Paradigm
Hiroaki Anada∗†

Seiko Arita

Kouichi Sakurai

Institute of Systems,
Information Technologies andNanotechnologies (ISIT)
Fukuoka SRP Center Bldg. 7F
Momochihama 2-1-22,
Sawara-ku, Fukuoka,
814-0001, Japan

Graduate School ofInformation Security,
Institute of Information
Security (IISEC)
2-14-1 Tsuruyacho,
Kanagawa-ku
Yokohama, 221-0835, Japan

Department of Informatics,
Graduate School of ISEE
Faculty, Kyushu University
West Bldg. No.2
Moto-oka 744, Nishi-ku,
Fukuoka, 819-0395, Japananada@isit.or.jp

arita@iisec.ac.jp

sakurai@csce.kyushuu.ac.jp

ABSTRACT1.

We propose the first practical attribute-based signature (ABS)
scheme with attribute privacy without pairings in the random oracle model. Our strategy is in the Fiat-Shamir paradigm;
we first provide a generic construction of a boolean proof
system of Σ-protocol type. Our boolean proof system is a
generalization of the well-known OR-proof system; that is,
it can treat any boolean formula instead of a single ORgate. Then, by combining our boolean proof system witha credential bundle scheme of the Fiat-Shamir signature,
we obtain a generic attribute-based identification (ABID)
scheme of proof of knowledge. Finally, we apply the FiatShamir transform to our ABID scheme to obtain a generic
ABS scheme which possesses attribute privacy and can beproved to be secure in the random oracle model. Our ABS
scheme can be constructed without pairings.

Since the invention of digital signature scheme by Diﬃeand Hellman in 1976, there has been significant evolutionsin the area and many functional variants have been proposed. A distinguished variant is attribute-based signature(ABS), which has been developed since 2008 [11, 13]. In
ABS scheme, a message is associated with an access policy that limits signers by their attributes which the signers
possess. The access policy is described with a boolean formula over those attributes. A signer with a set of authorized
attributes can make a legitimate signature on the message
only when his attributes satisfy the access policy. Then, averifier can check whether the pair of the message and thesignature is valid or not concerning the access policy. If theaccess policy limits accepting attributes to a single identity,
ABS coincides with identity-based signature (IBS). In thatsense, ABS is a natural extension of IBS.
One remarkable property of ABS is attribute privacy for
signers. In the case that a verifier knows nothing aboutprover’s attributes except that the prover’s attributes satisfy the associated access policy of the signed message, theABS scheme is called to have attribute privacy. Some ABS
scheme ([11]) did not care attribute privacy but it is now
desirable for ABS to possess.
On the other hand, The Fiat-Shamir transform [9] is now
an established technique in interactive proof theory and cryptography. It transforms a public-coin interactive proof ofknowledge system into a non-interactive proof of knowledge one. If the interactive proof system is an identification
scheme, then the non-interactive one can be used as a digital
signature scheme.
One of the most basic interactive proof systems is a proofof knowledge system by the Σ-protocol [7, 8]; it allows aprover, in a 3-move, to convince a verifier that the prover
knows an answer (that is, a witness) of a hard problem instance. An extended notion, the OR-proof system [8], is awell-known Σ-protocol that allows a prover to convince a
verifier that the prover knows one (or both) of witnesses of
two hard problem instances, not revealing which witness heknows. The OR-proof system has been developed to achieve,for example, man-in-the-middle security.
In this paper, we will provide an attribute-based signaturescheme via the Fiat-Shamir paradigm. First, we develop a

Categories and Subject Descriptors
F.1 [Computation by Abstract Devices]: Modes of Computation—Interactive and Reactive Computation

General Terms
Theory; Security

Keywords
access control; attribute; signature; proof system; boolean
formula; identification; Fiat-Shamir transform∗He is also with IISEC†He is also with ISIT.
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
AsiaPKC’14, June 3, 2014, Kyoto, Japan.
Copyright 2014 ACM 978-1-4503-2801-2/14/06 ...$15.00.
http://dx.doi.org/10.1145/2600694.2600696.

49

INTRODUCTION

boolean proof system of Σ-protocol type, which is a generalization of the OR-proof system [8]. In our boolean proof
system, a boolean formula f , in which boolean variables
corresponds to attributes, is used. A prover has a set of
witnesses each of which corresponds to an attribute. Thena prover can convince a verifier that the prover knows a setof witnesses that satisfy f .
Then we will proceed further into the Fiat-Shamir paradigm.
By combining our boolean proof system with a credential
bundle scheme of the Fiat-Shamir signature, we obtain ageneric attribute-based identification (ABID) scheme of proofof knowledge. And finally, we apply the Fiat-Shamir transform to our ABID scheme to obtain a generic ABS schemewith attribute privacy, which can be proved to be secure in
the random oracle model. According to the above strategy,
we find a remarkable property that our ABS scheme can beconstructed without pairing maps ([6]) (pairings, for short)with the expense that its security proof is in the random
oracle model. As a result, our ABS scheme can be implemented with more eﬃciency than previous ABS schemes. To
the best of authors’ knowledge, previous ABS schemes withattribute privacy have been constructed with pairings.

struction of ABID and ABS, their security can be provedin the random oracle model. We also note that our ABS
attains attribute privacy.

1.3

Related WorkThe OR-proof system had been developed with the formalization of Σ-protocol in the present form [7, 8]. Ourboolean proof system of Σ-protocol type can be seen as anatural extension of the OR-proof system.
At a high level, our ABS scheme is constructed by combining a credential bundle scheme [13] with our boolean proof
system. This construction is compared to the generic construction of the ABS scheme by Maji et al. [13]. They
started with a credential bundle scheme. Then they employed a non-interactive witness indistinguishable proof ofknowledge (NIWIPoK) system to prove the knowledge of acredential bundle which satisfies a given access formula. The
diﬀerence between our construction and their construction
becomes apparent when we look into for what system theknowledge extractors (KEs) are needed. In our construction,
KE is needed for our interactive proof system. In contrast,in their construction, KE is needed for a non-interactive
WIPoK system.
From a practical point of view, it is notable that almost all
attribute-based cryptographic primitives so far, originatedin [10], and including ABS, employ linear secret sharing
schemes (LSSS) ([3]) and pairings ([6]). Our approach for
ABS is diﬀerent from that construction.

1.1 Our Construction Idea
To construct the above boolean proof system, we will look
into the technique employed in the OR-proof system [8] andexpand it so as to treat any boolean formula (without negations), as follows.
First express a boolean formula (an access formula) as abinary tree (an access tree); that is, with its inner nodes
being AND gates and OR gates and its leaf nodes being
terms that map to attributes. A verification equation ofΣ is assigned to each leaf node. Suppose that a challenge
string Cha of Σ is given. Assign Cha to the root node.
If the root node is an AND gate, assign the same string
Cha to two children. Else if the root node is an OR gate,
divide Cha into two random strings ChaL and ChaR which
satisfy Cha = ChaL ⊕ ChaR , and assign ChaL and ChaR
to the left and right children, respectively. Here ⊕ meansa bitwise exclusive-OR operation. Then continue to apply
this rule at each height, step by step, until we reach to eachleaf node. Then, basically, the OR-proof technique assures
we can either honestly execute Σ-protocol Σ or execute Σin a simulated way. Only when a set of attributes satisfies
the access tree the above procedure succeeds in satisfying
verification equations for all leaf nodes. We call the above
procedure a boolean proof. The boolean proof is a natural,
but non-trivial extension of the OR-proof.

2.

PRELIMINARIESThe security parameter is denoted by λ. When an algorithm A with input a outputs z, we denote it as z ← A(a),or, because of space limitation, A(a) → z. When A with
input a and B with input b interact with each other andB 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
concurrentn oracle-access to n oracles O1 , . . . , On , we denote
it as AOi |i=1 . Here “concurrent” means that A accesses tooracles in arbitrarily interleaved order of messages. We denote a concatenation of a string a with a string b as a ∥ b.
?

The expression a = b returns a value 1 (True) when a = b?

and 0 (False) otherwise. The expression a ∈ S returns avalue 1 (True) when a ∈ S and 0 (False) otherwise.

2.1

Access Formula [10]Let U = {att1 , . . . , attU } be an attribute universe. We
must distinguish two cases: the case that U is small (thatis, |U| = U is bounded by some polynomial in λ) and thecase that U is large (that is, U is not necessarily bounded).
We assume the small case unless we state the large case
explicitly.
Suppose that we are given an access policy as a boolean
formula f over variables {Xatt }att∈U (for example, f = Xatt1 ∧((Xatt2 ∧Xatt3 )∨Xatt4 )). That is, each term Xatt is a predicate which, on input S ∈ 2U , takes a boolean value according
to whether att ∈ S or not. Then the boolean output of f
at S is evaluated according to boolean connectives, that is,
AND gates (∧-gates) or OR gates (∨-gates). Hence f is afunction: f : 2U → {1, 0}. We call the boolean formula f anaccess formula over U.

1.2 Our Contributions
As our first contribution, we provide a boolean proof system of a Σ-protocol, Σf . Given a boolean formula f without
negation and a Σ-protocol Σ, we generically construct Σf sothat Σf is a Σ-protocol to prove knowledge of a witness set
that satisfies f . A remark is that to construct such a proof
system in a 3-move with attribute privacy was diﬃcult.
As our second contribution, we provide ABID schemes
and ABS schemes without pairings. More precisely, As a Σprotocol Σ can be constructed without pairings (for example, the case of Schnorr scheme [15, 5]), our generic, theoretical construction can produce a concrete, practical boolean
proof system Σf and hence, an ABID scheme and an ABS
scheme, without pairings. We must note that, in our con-50

Special Soundness. Any PPT algorithm P∗ without any
witness, a cheating prover, can only respond for one possible challenge Cha. In other words, there is a PPT algorithm called a knowledge extractor, ΣKE , which, given astatement x and using P∗ as a subroutine, can compute a
witness w satisfying (x, w) ∈ R with at most a negligible error probability, from two accepting conversations of the form
(Cmt, Cha, Res) and (Cmt, Cha′ , Res′ ) with Cha ̸= Cha′ .
Honest-Verifier Zero-Knowledge. Given a statement x and arandom challenge Cha ← Σ2 (λ), we can produce in polynomialtime, without knowing the witness w, an accepting conversation (Cmt, Cha, Res) whose distribution is the same as thereal accepting conversation. In other words, there is a PPT
algorithm called a simulator, Σsim , such that (Cmt, Res) ←Σsim (x, Cha).
Σ-protocols are known to be proofs of knowledge system([8]).
We will use in this paper a property that both a prover anda verifier can compute, in polynomial-time, a new statement
x′ which has the response message Res as its corresponding
witness, on input (x, Cmt, Cha). We denote the algorithm
as ΣstmtforRes :In this paper, we do not consider NOT gates (¬), that is,
we only consider monotone boolean formulas1 .

2.1.1 Access Tree
We consider in this paper a finite binary tree T , that is, atree that has finite number of nodes and each non-leaf node
has two branches. For a tree T , let Nd(T ), rt(T ), Lf(T ),iNd(T ) and tNd(T ) denote the set of all nodes, the root
node, the set of all leaf nodes, the set of all inner nodes(that is, all nodes excluding leaf nodes) and the set of alltree-nodes (that is, all nodes excluding the root node) in
T , respectively. An access formula f can be represented
by a finite binary tree Tf . Each leaf node corresponds toa term Xatt in f in one-to-one way. Each inner node represents an operator, ∧-gate or ∨-gate, in f . An attribute
map att(·) : Lf(T ) → U is defined, for lf ∈ Lf(T ), asatt(lf) := (the attribute att of the term Xatt ).
If T is of height greater than 0, T has two subtrees whoseroot nodes are two children of rt(T ). We denote the two subtrees by Lsub(T ) and Rsub(T ), which mean the left subtree
and the right subtree, respectively.

2.2 Proof of Knowledge System [4, 8]

x′ ←ΣstmtforRes (x, Cmt, Cha)

Let R be a binary polynomial-time relation R = {(x, w)} ⊂{1, 0}∗ ×{1, 0}∗ . x is called a statement and w is called a witness for the statement x. We assume that, given a statementx as input, any PPT algorithm can only output a witness
w satisfying (x, w) ∈ R with a negligible probability. If thisassumption holds, we say that R is a hard relation ([8]).
A proof of knowledge system (PoK for short) is a protocol
between interactive PPT algorithms P and V on initial input(x, w) ∈ R for P and x for V.
Completeness. An honest prover P with a legitimate witness
w can make V accept with probability 1.
Knowledge Soundness. There is a PPT algorithm called aknowledge extractor, which, given a statement x and employing P as a subroutine, can compute a witness w satisfying(x, w) ∈ R with at most a negligible error probability.

s.t. (Cmt, Cha, Res) : an accepting conversation∧ (x′ , Res) ∈ R.
Known Σ-protocols such as the Schnorr protocol and theGuillou-Quisquater protocol [15, 5] possess this property.

2.3.1

The OR-proof System[8]Suppose that a Σ-protocol Σ on a relation R is given.
Consider the following relation.
ROR ={({x0 , x1 }, {wi }i∈S ) ∈ {1, 0}∗ × {1, 0}∗ ;(0 ∈ S ∨ 1 ∈ S) ∧ ∀ i ∈ {0, 1} ∩ S, (xi , wi ) ∈ R}.
Then we construct a new protocol, ΣOR , on a relation ROR
as follows. For an explanation, suppose (x0 , w0 ) ∈ R holds.
P computes Cmt0 ← Σ1 (x0 , w), Cha1 ← Σ2 (λ), (Cmt1 , Res1 )← Σsim (x1 , Cha1 ) and sends (Cmt0 , Cmt1 ) to V. Then V
sends Cha ← Σ2 (λ) to P. Then, P computes Cha0 := Cha⊕
Cha1 , Res0 ← Σ3 (x0 , w0 , Cmt0 , Cha0 ) answers to V with
(Cha0 , Cha1 ) and (Res0 , Res1 ). Here ⊕ denotes a bitwise
Exclusive-OR operation. Then both (Cmt0 , Cha0 , Res0 )and (Cmt1 , Cha1 , Res1 ) are accepting conversations andhave the same distribution as real accepting conversations.
This protocol ΣOR also can be proved to be a Σ-protocol,
and is called the OR-proof system.

2.3

Σ-protocol [7, 8]
Let R be a binary polynomial-time relation R = {(x, w)} ⊂{1, 0}∗ × {1, 0}∗ .
A Σ-protocol on a relation R is a 3-move protocol between
interactive PPT algorithms P and V on initial input (x, w) ∈R for P and x for V. P sends the first message called acommitment Cmt, then V sends a random bit string calleda challenge Cha, and P answers with a third message calleda response Res. Then V applies a local decision test on(x, Cmt, Cha, Res) to return accept (1) or reject (0). Cha
is chosen at random from ChaSp(λ) := {1, 0}l(λ) with l(·)
being a super-log function.
This protocol is written by a PPT algorithm Σ as follows.
Cmt ← Σ1 (x, w): the process of selecting the first message
Cmt according to the protocol Σ on input (x, w) ∈ R. Similarly we denote Cha ← Σ2 (λ), Res ← Σ3 (x, w, Cmt, Cha)
and b ← Σvrfy (x, Cmt, Cha, Res).
Σ-protocol satisfies three constraints:
Completeness. An honest prover P with a legitimate witness
w can make V accept with probability 1.

2.3.2

The Fiat-Shamir Transform [1]Employing a cryptographic hash function with collisionresistance, Hλ (·) : {1, 0}∗ → {1, 0}l(λ) , a Σ-protocol Σ canbe transformed into a digital signature scheme as follows.
Given a message m ∈ {1, 0}∗ , execute: a ← Σ1 (x, w),c ← Hλ (m ∥ a), z ← Σ3 (x, w, a, c). Then σ := (a, z) isa signature on m. We denote the above signing algorithm
as FSsignΣ (x, w, m) → (a, z) =: σ. The verification algorithm
is given as follows: FSvrfy
Σ (x, m, σ) : c ← Hλ (m ∥ a), Returnb ← Σvrfy (x, a, c, z).
vrfy
The signature scheme FSΣ = (R, FSsign
Σ , FSΣ ) can beproved, in the random oracle model, to be secure in the existential unforgeability game against chosen-message attacks

1

This limitation can be removed by adding negation attributes to U for each attribute in the original U (but asa result, the size |U | doubles).

51

if and only if underlying Σ-protocol Σ is secure against passive attacks [1]. More precisely, let qH denote the maximum number of hash queries issued by the adversary on
FSΣ . Then, for any PPT algorithm F , there exists a PPT
algorithm B which satisfies the following inequality (neg(·)
means a negligible function).

a pair (Sj , fj ) of an attribute set and an access formula.
Acting as a verifier with an access formula fj , A interacts
with each Pj (PK, SKSj ) concurrently.
The access formula f ∗ declared by A is called a target access formula. Here we consider the adaptive target in thesense that A is allowed to choose f ∗ after seeing PK, issuing key-extraction queries and interacting with of provers.
Two restrictions are imposed on A concerning f ∗ . In keyextraction queries, each attribute set Si must satisfy f ∗ (Si ) =0. In interactions with each prover, f ∗ (Sj ) = 0. 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 ABID in the game of concurrent
attack is defined aspa
Adveufcma
F ,FSΣ (λ) ≤ qH AdvB,Σ (λ) + neg(λ).

2.4 Credential Bundle Scheme [13]Credential bundle is an extended notion of digital signature. Suppose that we are given a digital signature scheme(KG, Sign, Vrfy). To construct a credential bundle scheme,
first choose a string τ , a tag. τ can be chosen as a random
string or a publicly known string such as an e-mail address.
Then, for a set of messages m1 , . . . , mn ∈ {1, 0}∗ , execute
Sign on each tagged message (τ ∥ mi ), i = 1, . . . , n. Verify
is applied in a obvious way.

def

ca
Advca
A,ABID (λ) = Pr[ExprmtA,ABID (λ, U) returns Win].

ABID is called secure against concurrent attacks if, for any
PPT A, Advca
A,ABID (λ) is negligible in λ.
The game of passive attack on ABID is defined by reqp
placing concurrent provers Pj (PK, SK· )|j=1
with transcriptcaoracle Transc in ExprmtA,ABID (λ, U ). In a transcript query,giving a pair (Sj , f ) of an attribute set and an access formula, A queries Transc(P(PK, SK· ), V(PK, ·)) for a wholetranscript of messages interacted between P(PK, SKSj ) andV(PK, fj ). The advantage Advpa
A,ABID (λ) and security aredefined in the same way as the concurrent case. Note that
concurrent security means passive security; for any PPT A,
there exists a PPT B that satisfies the following inequality.

2.5 Attribute-Based Identification Scheme [2]In this paper, we will describe verifier-policy attributebased identification schemes [2]. An attribute-based identification scheme, ABID, consists of four PPT algorithms:(Setup, KG, P, V).
Setup(λ, U) → (PK, MSK). Setup takes as input the security parameter λ and an attribute universe U. It outputs
a public key PK and a master secret key MSK.
KG(PK, MSK, S) → SKS . A key-generation algorithm
KG takes as input the public key PK, the master secretkey MSK and an attribute set S ⊂ U . It outputs a secretkey SKS corresponding to S.
P(PK, SKS ) and V(PK, f ). 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 . Herethe secret key SKS is given to P by an authority that runs
KG(PK,MSK,S). V takes as input the public key PK andan access formula f . P is provided V’s access formula fby the first move. P and V interact with each 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 λ, and if f (S) = 1, then Pr[(PK, MSK) ←Setup(λ, U); SKS ← KG(PK, MSK, S); b ← ⟨P(PK, SKS ),V(PK, f )⟩ : b = 1] = 1.

ca
Advpa
A,ABID (λ) ≤ AdvB,ABID (λ).

2.5.2Exprmtatt-prv
A,ABID (λ, U) :(PK, MSK) ← Setup(λ, U), (S0 , S1 , f ∗ ) ← A(PK)s.t. (f ∗ (S0 ) = f ∗ (S1 ) = 1) ∨ (f ∗ (S0 ) = f ∗ (S1 ) = 0)
SKS0 ← KG(PK, MSK, S0 ), SKS1 ← KG(PK, MSK, S1 )b ← {1, 0}, b̂ ← AP(PK,SKSb ) (PK, SKS0 , SKS1 )If b = b̂ Return Win else Return Lose
We say that ABID has attribute privacy if, for any PPT A,
the following advantage is negligible in λ.

An adversary A’s objective is impersonation. A tries tomake a verifier V accept with an access formula f ∗ . The
following experiment Exprmtca
A,ABID (λ, U) of an adversary
A defines the game of concurrent attack on ABID.

def

Advatt-prv
A,ABID (λ) =|Pr[Exprmtatt-prv
A,ABID (λ, U) returns Win] − 1/2|.

Exprmtca
A,ABID (λ, U) :2.6

(PK, MSK) ← Setup(λ, U)(f , st) ← A

qp

KG(PK,MSK,·),Pj (PK,SK· )|j=1

Attribute Privacy of ABID

Consider the following experiment Exprmtatt-prv
A,ABID (λ, U ).
(In the experiment, an adversary A interacts with P(PK, SKSb )as a verifier with f ∗ .)2.5.1 Attacks on ABID and Security∗(1)

Attribute-Based Signature Scheme [14]An attribute-based signature scheme, ABS, consists of four
PPT algorithms: (Setup, KG, Sign, Vrfy).
Setup(λ, U ) → (PK, MSK). Setup takes as input the security parameter λ and an attribute universe U. It outputs
a public key PK and a master secret key MSK.
KG(PK, MSK, S) → SKS . A key-generation algorithm
KG takes as input the public key PK, the master secretkey MSK and an attribute set S ⊂ U . It outputs a signing
key SKS corresponding to S.
Sign(PK, SKS , (m, f )) → σ. A signing algorithm Sign takes
as input a public key PK, a private secret key SKS corre-(PK, U)b ← ⟨A(st), V(PK, f ∗ )⟩If b = 1 then Return Win else Return LoseIn the experiment, A issues key-extraction queries to its keygeneration oracle KG. Giving an attribute set Si , A queries
KG(PK, MSK, ·) for the secret key SKSi . In addition, A
invokes provers Pj (PK, SK· ), j = 1, . . . , qp′ , . . . , qp , by giving

52

We say that ABS has attribute privacy if, for any PPT A,
the following advantage of A is negligible in λ.

sponding to an attribute set S, a pair (m, f ) of a message∈ {1, 0}∗ and an access formula. It outputs a signature σ.
Vrfy(PK, (m, f ), σ). A verification algorithm Vrfy takes as
input a public key PK, a pair (m, f ) of a message and anaccess formula, and a signature σ. It outputs a decision 1 or
0. When it is 1, we say that ((m, f ), σ) is valid. When it is 0,
we say that ((m, f ), σ) is invalid. We demand correctness of
ABS that for any λ, and if f (S) = 1, then Pr[(PK, MSK) ←Setup(λ, U); SKS ← KG(PK, MSK, S); σ ← Sign(PK, SKS ,(m, f )); b ← Vrfy(PK, (m, f ), σ) : b = 1] = 1.

def

Advatt-prv
A,ABS (λ) =|Pr[Exprmtatt-prv
A,ABS (λ, U) returns Win] − 1/2|.

2.7

Pseudorandom Function Family [12]A pseudorandom function family, {PRFκ }κ∈PRFkeysp(λ) , isa function family in which each function PRFκ : {1, 0}∗ →{1, 0}∗ is an eﬃciently-computable function that looks random to any polynomial-time distinguisher, where κ is calleda key and PRFkeysp(λ) is called a key space. (See moredetail in [12].)2.6.1 Chosen-Message Attack on ABS and Security
An adversary F ’s objective is to make an existential forgery.
F tries to make a forgery ((m∗ , f ∗ ), σ ∗ ) of a message, a target access policy and a signature. The following experiment
Exprmteufcma
F ,ABS (λ, U) of a forger F defines the existential unforgeability game by chosen-message attack on ABS.

3.

DEFINITION OF OUR BOOLEAN PROOF
SYSTEM OF Σ-PROTOCOL TYPE

In this section, we propose a notion of boolean proof systemin the form of a Σ-protocol, Σf , where f is a given accessformula. Our Σf is a generalization of the OR-proof system ΣOR [8]; that is, it treats any boolean formula insteadof a single OR-gate. In addition, as is the case for usual
Σ-protocol Σ, our boolean proof system Σf is a proof ofknowledge system; that is, it possesses a knowledge extractor that extracts a witness set which satisfies the boolean
formula f .
Let R be a binary polynomial-time relation R = {(x, w)} ⊂{1, 0}∗ × {1, 0}∗ . Let f be an access formula over U. Thenwe create a new relation Rf :Exprmteufcma
F ,ABS (λ, U) :(PK, MSK) ← Setup(λ, U )((m∗ , f ∗ ), σ ∗ ) ← F KG(PK,MSK,·),SIGN (PK,SK· ,(·,·))
If Vrfy(PK, (m∗ , f ∗ ), σ ∗ ) = 1 then Return Win
else Return LoseIn the experiment, F issues key-extraction queries to its
key-generation oracle KG and signing queries to its signing oracle SIGN . Giving an attribute set Si , A queries
KG(PK, MSK, ·) for the secret key SKSi . In addition, giving
an attribute set Sj and a pair (m, f ) of a message and an access formula, F queries SIGN (PK, SK· , (·, ·)) for a signature
σ that satisfies Vrfy(PK, (m, f ), σ) = 1 when f (Sj ) = 1.
The access formula f ∗ declared by F is called a target access formula. Here we consider the adaptive target in thesense that F is allowed to choose f ∗ after seeing PK, issuingof key-extraction queries and signing queries. Two restrictions are imposed on F concerning f ∗ . In key-extraction
queries, each attribute set Si must satisfy f ∗ (Si ) = 0. In
signing queries, (m∗ , f ∗ ) was never queried. The number of
key-extraction queries and the number of signing queries areat most qk and qs in total, respectively, which are bounded
by a polynomial in λ.
The advantage of F over ABS in the existential unforgeability game by chosen-message attack is defined as

Rf = {(X := {xatt }att∈Att(f ) , W := {watt }att∈S ) ∈ ({1, 0}∗ )2 ;def

f (S) = 1 ∧ ∀ att ∈ Att(f ) ∩ S, (xatt , watt ) ∈ R}.

Note that Rf is a generalization of the relation ROR .
Then a boolean proof system Σf on the relation Rf is
defined as a 3-move protocol between interactive PPT algorithms P and V on initial input (X := {xatt }, W :={watt }) ∈ Rf for P, and X for V. 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 a local decision teston (X, Cmt, Cha, Res) to return accept (1) or reject (0).
Here Cha is chosen at random from ChaSp(λ) := {1, 0}l(λ)
with l(·) being a super-log function.
This protocol is written by a PPT algorithm Σf as follows.
Cmt ← Σ1f (X, W ): the process of selecting the first message
def
eufcmaCmt according to the protocol Σf on input (X, W ) ∈ Rf .
Adveufcma
F ,ABS (λ) = Pr[ExprmtF ,ABS (λ, U ) returns Win].
Similarly we denote Cha ← Σ2f (λ), Res ← Σ3f (X, W, Cmt, Cha)
ABS is called secure in the existential unforgeability gameand b ← Σvrfy(X, Cmt, Cha, Res).
fagainst chosen-message attacks if, for any PPT F, Adveufcma
F ,ABS (λ)
To be a Σ-protocol, Σf must satisfy three constraints:
is negligible in λ.
Completeness An honest prover P with a legitimate witness
set W can make V accept with probability 1.
2.6.2 Attribute Privacy of ABS
Special Soundness. Any PPT algorithm P∗ without any witConsider the following experiment Exprmtatt-prv
A,ABS (λ, U).
ness set (called a cheating prover) can only respond for one
possible challenge Cha. In other words, there is a PPT alExprmtatt-prv
A,ABS (λ, U ) :gorithm called a knowledge extractor, ΣKE
f , which, given astatement X and using P ∗ as a subroutine, can compute a(PK, MSK) ← Setup(λ, U), (S0 , S1 , f ∗ ) ← A(PK)witness set W satisfying (X, W ) ∈ Rf with at most a negs.t. (f ∗ (S0 ) = f ∗ (S1 ) = 1) ∨ ((f ∗ (S0 ) = f ∗ (S1 ) = 0)
ligible error probability, from two accepting conversations
SKS0 ← KG(PK, MSK, S0 ), SKS1 ← KG(PK, MSK, S1 )of the form (Cmt, Cha, Res) and (Cmt, Cha′ , Res′ ) with
SIGN (PK,SKS ,·,·)
Cha ̸= Cha′ .
bb ← {1, 0}, b̂ ← A(PK, SKS0 , SKS1 )Honest-Verifier Zero-Knowledge. Given a statement set X
If b = b̂ Return Win else Return Lose
and a random challenge Cha ← Σ2f (λ), we can produce in53

polynomial-time, without knowing the witness set W , anaccepting conversation (Cmt, Cha, Res) whose distribution
is the same as the real accepting conversation. In otherwords, there is a PPT algorithm called a simulator, Σsim ,such that (Cmt, Res) ← Σsim (X, Cha).
The boolean proof system Σf constructed in the above
way can be proved to be a proof of knowledge system. The
reason is the same as the reason of usual Σ-protocol ([8]).

Verification. Verifier’s computation is executed for eachleaf node as follows.
Σvrfy(X, T , Cha,f
(Cmtlf )lf∈Lf(T ) , (Chand )nd∈tNd(T ) , (Reslf )lf∈Lf(T ) ) :Return(VrfyCha(T , Cha, (Chand )nd∈tNd(T ) )∧ VrfyRes(X, T , (Cmt, Cha, Res)lf∈Lf(T ) ))VrfyCha(T , Cha, (Chand )nd∈tNd(T ) ) :4. CONSTRUCTION OF OUR BOOLEAN
PROOF SYSTEM

TL := Lsub(T ), TR := Rsub(T )If rt(T ) is an ∧ -node,In this section, we construct our boolean proof system Σffrom a given Σ-protocol Σ and an access formula f . Becauseof space limitation, all proofs for Proposition, Lemma andTheorem are hereafter omitted.
Fig. 1 shows our protocol Σf . Basically Σf is a 3-moveprotocol between interactive PPT algorithms P and V on
initial input (X := {xatt }att∈Att(f ) , W := {watt }att∈S ) ∈ Rf
for P and X for V.
Evaluation of Satisfiability. The prover P begins withevaluation concerning whether and how S satisfies f . We
label each node of T with a value v = 1 (True) or 0 (False);
For each leaf node lf, we label lf with vlf = 1 if att(lf) ∈ S
and vlf = 0 otherwise. For each inner node nd, we labelnd according to AND/OR evaluation result of two labelsof its two children. The computation is executed for every
node from the root node to each leaf node, recursively, inthe following way.

?

?

then Return (Cha = Chart(TL ) ∧ Cha = Chart(TR )∧ VrfyCha(TL , Chart(TL ) , (Chand )nd∈tNd(TL ) )∧ VrfyCha(TR , Chart(TR ) , (Chand )nd∈tNd(TR ) ))else if rt(T ) is an ∨ -node,?

then Return (Cha = Chart(TL ) ⊕ Chart(TR )∧ VrfyCha(TL , Chart(TL ) , (Chand )nd∈tNd(TL ) )∧ VrfyCha(TR , Chart(TR ) , (Chand )nd∈tNd(TR ) ))else if rt(T ) is a leaf node,?

then Return (Cha ∈ ChaSp(λ))
VrfyRes(X, T , (Cmt, Cha, Res)lf∈Lf(T ) ) :For lf ∈ Lf(T )If Σvrfy (xatt(lf) , Cmtlf , Chalf , Reslf ) = 0, then Return (0)Σeval(T , S) :f
TL := Lsub(T ), TR := Rsub(T )Return (1)If rt(T ) is an ∧ -node,

Now we have to check that Σf is certainly a boolean proof
system of Σ-protocol type.

then Return vrt(T ) := (Σeval(TL , S) ∧ Σeval(TR , S))ffelse if rt(T ) is an ∨ -node,

Proposition 1 (Completeness). Completeness holds
for our Σf . More precisely, Suppose that vrt(Tf ) = 1. Then,for every node in Nd(Tf ), either vnd = 1 or Chand ̸= ∗ holds
after executing Σ1f .

then Return vrt(T ) := ((Σeval(TL , S) ∨ Σeval(TR , S))ffelse if rt(T ) is a leaf node,?

then Return vrt(T ) := (att(rt(T )) ∈ S)

Proposition 2 (Special Soundness). Special soundness holds for our Σf .

Commitment. Prover’s computation of a commitment value
for each leaf node is described in Fig. 2. Basically, the algorithm Σ1f runs for every node from the root node to eachleaf node, recursively. As a result, Σ1f generates for each leaf
node lf a value Cmtlf ; If vlf = 1, then Cmtlf is computed
honestly according to Σ1 . Else if vlf = 1, then Cmtlf is computed in the simulated way according to Σsim . Other values,(Chand )nd∈tNd(Tf ) and (Reslf )lf∈Lf(Tf ) ), are needed for thesimulation. Note that a distinguished symbol ‘∗′ is used for
those other values to indicate the honest computation.
Challenge. Verifier picks up a challenge value by using Σ2 .

Lemma 1 (Witness-Set Extraction). The set W ∗ output by ΣKE
satisfies (X, W ∗ ) ∈ Rf .
f
Proposition 3 (Honest Verifier Zero-Knowledge).
Honest verifier zero-knowledge property holds for our Σf .
Theorem 1. Σf is certainly a boolean proof system of
Σ-protocol type on the relation Rf .

5.

Σ2f (λ) : Cha ← Σ2 (λ), Return(Cha)
Response. Prover’s computation of a response value foreach leaf node is described in Fig. 3. Basically, the algorithm Σ3f runs for every node from the root node to eachleaf node, recursively. As a result, Σ3f generates values,(Chand )nd∈tNd(Tf ) and (Reslf )lf∈Lf(Tf ) ). Note that all challenge values (Chand )nd∈tNd(Tf ) are completed according to
the “division rule” described in Section 1.1.

APPLICATION TO
ATTRIBUTE-BASED IDENTIFICATIONIn this section, by combining our boolean proof system Σfwith a credential bundle scheme of the Fiat-Shamir signature FSΣ , we obtain an attribute-based identification scheme
ABID of proof of knowledge, which has collusion resistanceagainst collecting private secret keys. Our ABID scheme
ABID has a feature that it can be constructed without pairings.

54

P(X := {xatt }att∈Att(f ) , W := {watt }att∈S ) :Initialize inner stateΣeval(Tf , S) → (vnd )nd∈Nd(Tf )f
If vrt(Tf ) ̸= 1, then abort
else Chart(Tf ) := ∗
Σ1f (X, W, Tf , (vnd )nd∈Nd(Tf ) , Chart(Tf ) )→ ((Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )Chart(Tf ) := Cha
Σ3f (X, W, Tf , (vnd )nd∈Nd(Tf ) , Chart(Tf ) ,(Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )→ ((Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )V(X, f ):Initialize inner state(Cmtlf )lf∈Lf(Tf )−→Cha ← Σ2f (λ)

Cha←−(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf )
−→

Σvrfy
(X, Tf , Cha,f
(Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) ) → b
Return b

Figure 1: Our boolean proof system Σf on a relation Rf = {(X, W )}.
Σ1f (X, W, T , (vnd )nd∈Nd(T ) , Cha) :TL := Lsub(T ), TR := Rsub(T )Ifrt(T ) is ∧-node, then Chart(TL ) := Cha, Chart(TR ) := Cha
Return(Chart(TL ) , Σ1f (X, W, TL , (vnd )nd∈Nd(TL ) , Chart(TL ) ),Chart(TR ) , Σ1f (X, W, TR , (vnd )nd∈Nd(TR ) , Chart(TR ) ))else if rt(T ) is ∨-node, thenIfvrt(TL ) = 1 ∧ vrt(TR ) = 1, then Chart(TL ) := ∗,Chart(TR ) := ∗else if vrt(TL ) = 1 ∧ vrt(TR ) = 0, then Chart(TL ) := ∗,Chart(TR ) ← Σ2 (λ)
else if vrt(TL ) = 0 ∧ vrt(TR ) = 1, then Chart(TL ) ← Σ2 (λ), Chart(TR ) := ∗else if vrt(TL ) = 0 ∧ vrt(TR ) = 0, then Chart(TL ) ← Σ2 (λ), Chart(TR ) := Cha ⊕ Chart(TL )Return(Chart(TL ) , Σ1f (X, W, TL , (vnd )nd∈Nd(TL ) , Chart(TL ) ),Chart(TR ) , Σ1f (X, W, TR , (vnd )nd∈Nd(TR ) , Chart(TR ) ))else if rt(T ) is a leaf-node, thenIfvrt(T ) = 1, then Cmtrt(T ) ← Σ1 (xatt(rt(T )) , watt(rt(T )) ), Resrt(T ) := ∗else if vrt(T ) = 0, then (Cmtrt(T ) , Resrt(T ) ) ← Σsim (xatt(rt(T )) , Cha)
Return(Cmtrt(T ) , Resrt(T ) )Figure 2: The subroutine Σ1f of our Σf .
message matt := (τ ∥ att), att ∈ S. Here we employ the
Fiat-Shamir signing algorithm FSsign
that is obtained fromΣ
the same Σ-protocol Σ.

5.1 Our ABID Scheme
Our ABID = (Setup, KG, P, V) is described as follows.
Setup(λ, U) :(xM , wM ) ← InstanceR (λ), PK := (xM , U), MSK := wM

Supp(PK, SKS , f ) :Return(PK, MSK)

For att ∈ Att(f )If att ∈/ S, then catt ← PRFκ (0 ∥ att)

Setup computes a public key PK and a master secret key
MSK by running InstanceR (λ), which chooses an element(xM , wM ) that corresponds to the security parameter λ, at
random from a fixed hard relation R = {(x, w)}.

(aatt , zatt ) ← Σsim (xM , catt ; PRFκ (1 ∥ att))
Return (aatt )att∈Att(f )P uses supplementary algorithm, Supplement, to generatevalues aatt for all att ∈ Att(f ).

KG(PK, MSK, S) :κ ← PRFkeysp(λ), τ ← {1, 0}λFor att ∈ S : matt := (τ ∥ att)

StmtGen(PK, τ, (aatt )att∈Att(f ) ) :σatt := (aatt , watt ) ← FSsign
Σ (xM , wM , matt )For att ∈ Att(f ) :matt := (τ ∥ att), catt ← Hλ (matt ∥ aatt )SKS := (κ, τ, (σatt )att∈S ), Return SKS .

xatt ← ΣstmtforRes (xM , aatt , catt )KG first chooses a random string, a tag τ , at random. Then
KG applies the credential bundle technique [13] for each

Return {xatt }att∈Att(f )55Σ3f (X, W, T , (vnd )nd∈Nd(T ) , Cha, (Cmtlf )lf∈Lf(T ) , (Chand )nd∈tNd(T ) , (Reslf )lf∈Lf(T ) ) :TL := Lsub(T ), TR := Rsub(T )Ifrt(T ) is ∧-node, then Chart(TL ) := Cha, Chart(TR ) := Cha
Return(Chart(TL ) , Σ3f (X, W, TL , (vnd )nd∈Nd(TL ) , (Cmtlf )lf∈Lf(TL ) , Chart(TL ) , (Chand )nd∈tNd(TL ) , (Reslf )lf∈Lf(TL ) ),Chart(TR ) , Σ3f (X, W, TR , (vnd )nd∈Nd(TR ) , (Cmtlf )lf∈Lf(TR ) , Chart(TR ) , (Chand )nd∈tNd(TR ) , (Reslf )lf∈Lf(TR ) ))else if rt(T ) is ∨-node, thenIfvrt(TL ) = 1 ∧ vrt(TR ) = 1, then Chart(TL ) ← Σ2 (λ),
Chart(TR ) := Cha ⊕ Chart(TL )else if vrt(TL ) = 1 ∧ vrt(TR ) = 0, then Chart(TL ) := Cha ⊕ Chart(TR ) , Chart(TR ) := Chart(TR )else if vrt(TL ) = 0 ∧ vrt(TR ) = 1, then Chart(TL ) := Chart(TL ) ,Chart(TR ) := Cha ⊕ Chart(TL )else if vrt(TL ) = 0 ∧ vrt(TR ) = 0, then Chart(TL ) := Chart(TL ) ,Chart(TR ) := Chart(TR )Return(Chart(TL ) , Σ3f (X, W, TL , (vnd )nd∈Nd(TL ) , (Cmtlf )lf∈Lf(TL ) , Chart(TL ) , (Chand )nd∈tNd(TL ) , (Reslf )lf∈Lf(TL ) ),Chart(TR ) , Σ3f (X, W, TR , (vnd )nd∈Nd(TR ) , (Cmtlf )lf∈Lf(TR ) , Chart(TR ) , (Chand )nd∈tNd(TR ) , (Reslf )lf∈Lf(TR ) ))else if rt(T ) is a leaf-node, thenIfvrt(T ) = 1, then Resrt(T ) ← Σ3 (xatt(rt(T )) , watt(rt(T )) , Cmtrt(T ) , Cha)else if vrt(T ) = 0, then do nothing
Return(Resrt(T ) )Figure 3: The subroutine Σ3f of our Σf .

5.3.2

P and V utilizes a statement-generator algorithm, StmtGen.
This generates for each att ∈ Att(f ) a statement xatt thatmakes the output watt of KG be a corresponding witness.
Note that we employ here the algorithm ΣstmtforRes whichis associated with Σ, and whose existence is assured by assumption (see Section 2.3).
Finally, a whole ABID scheme is obtained by adding thefollowing procedures (1) and (2) to our Σ-protocol Σf .
(1) In P(PK, SKS ), add the following procedures to give astatement set and a witness set (X, W ) to Σ1f .

Attribute Privacy of our ABID.

For the case of an honest verifier, that is, if an adversary
A chooses a challenge Cha at random from ChaSp(λ) inthe attribute privacy game in Section 2.5.2 , attribute privacy follows from the honest verifier zero-knowledge property. However, in general, attribute privacy is not obvious.
It seems an open problem to the best of authors’ knowledge.

5.3.3

Security Reduction.

We mean a number theoretic problem here as the discretelogarithm problem or the RSA-inverse problem ([5]).
There exists the following security reduction to a number
theoretic problem.

Supp(PK, SKS , f ) → (aatt )att∈Att(f )StmtGen(PK, τ, (aatt )att∈Att(f ) )→ {xatt }att∈Att(f ) =: X, W := {watt }att∈S .

1/2

num.prob.
Advca(λ))1/4 + neg(λ).
A,ABID (λ) ≤ qH (AdvS,Grp

At the first move, P sends to the verifier V not only commitments (Cmtlf )lf∈Lf(Tf ) but also elements τ and (aatt )att∈Att(f ) .
(2) In V(PK, f ), add the following procedure to give a statement set X to Σvrfy
.
f

(2)

Here we denote qH as the maximum number of hash queries
issued by the adversary on FSΣ in the random oracle model.

6.

StmtGen(PK, τ, (aatt )att∈Att(f ) ) → {xatt }att∈Att(f ) =: X.
Theorem 2. Suppose that a given Σ-protocol Σ possessesa polynomial-time algorithm ΣstmtforRes . Then our ABID isalso a Σ-protocol on the relation Rf := {(X, W )}.

FURTHER APPLICATION TO ATTAINATTRIBUTE-BASED SIGNATURE

In this section, by applying the Fiat-Shamir transform [1]to our ABID, we obtain an attribute-based signature scheme
ABS. Our ABS is secure in the random oracle model, possesses attribute privacy, and has a feature that it can beconstructed without pairings.

5.2 Security of Our ABID

6.1

Theorem 3. If the employed signature scheme FSΣ is secure in the existential unforgeability game against chosenmessage attacks, then our ABID is secure against concurrent
attacks. More precisely, for any PPT algorithm A, there
exists a PPT algorithm F which satisfies the following inequality (neg(·) means a negligible function).

Our ABS Scheme

The Fiat-Shamir transform ([9, 1]), briefly described in
Section 2.3.2, can be directly applied to our ABID because
our ABID is a Σ-protocol. Fig. 4 shows our construction of
ABS scheme, ABS =(Setup, KG, Sign, Vrfy).

6.2

eufcma1/2
Advca+ neg(λ).
A,ABID (λ) ≤ (AdvF ,FSΣ (λ))

Security of Our ABS

We can apply the discussions in [1]. Then the security ofthe obtained attribute-based signature scheme is equivalent
to the security of our ABID against passive attacks.

5.3 Discussion
5.3.1 Attribute-Based Proof of Knowledge

Theorem 4. Our attribute-based signature scheme ABS
obtained by applying the Fiat-Shamir transform to our ABID
is secure in the existential unforgeability game against chosenmessage attacks, in the random oracle model, based on thepassive security of ABID. More precisely, let qH denote the

Our ABID is a proof of knowledge system. That is, fora fixed access policy f , a PPT knowledge extractor can beconstructed, which extracts a secret key SKS ∗ for some attribute set S ∗ with f (S ∗ ) = 1.

56Setup(λ, U):(xM , wM ) ← InstanceR (λ)
PK := (xM , U), MSK := wM
Return(PK, MSK)

KG(PK, MSK, S):κ ← PRFkeysp(λ), τ ← {1, 0}λFor att ∈ Smatt := (τ ∥ att)
σatt := (aatt , watt ) ← FSsign
Σ (xM , wM , matt )SKS := (κ, τ, (σatt )att∈S )Return SKS

Sign(PK, SKS , (m, f )):Initialize inner stateΣeval(Tf , S) → (vnd )nd∈Nd(Tf )f
If vrt(Tf ) ̸= 1, then abort

Vrfy(PK, (m, f ), σ := (τ, (aatt )att∈Att(f ) ,(Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) ))) :Initialize inner state
Cha ← H(m ∥ (Cmtlf )lf∈Lf(Tf ) )StmtGen(PK, τ, (aatt )att∈Att(f ) )→ {xatt }att∈Att(f ) =: X

else Chart(Tf ) := ∗Supp(PK, SKS , f ) → (aatt )att∈Att(f )StmtGen(PK, τ, (aatt )att∈Att(f ) )→ {xatt }att∈Att(f ) =: X
W := {watt }att∈SΣ1f (X, W, Tf , (vnd )nd∈Nd(Tf ) , Chart(Tf ) )→ ((Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )Σvrfy(X, Tf ,f(Cmtlf )lf∈Lf(Tf ) ,Cha, (Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )→ b, Return b

Cha ← H(m ∥ (Cmtlf )lf∈Lf(Tf ) )Chart(Tf ) := Cha
Σ3f (X, W, Tf , (vnd )nd∈Nd(Tf ) , Chart(Tf ) ,(Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )→ ((Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) )Return σ := (τ, (aatt )att∈Att(f ) ,(Cmtlf )lf∈Lf(Tf ) ,(Chand )nd∈tNd(Tf ) ,(Reslf )lf∈Lf(Tf ) ))Figure 4: Our ABS scheme.

57

9.

maximum number of hash queries issued by the adversary on
ABS. Then, for any PPT algorithm F, there exists a PPT
algorithm B which satisfies the following inequality (neg(·)
means a negligible function).
pa
Adveufcma
F ,ABS (λ) ≤ qH AdvB,ABID (λ) + neg(λ).

ACKNOWLEDGEMENTS

We appreciate sincere comments of anonymous reviewers,
Dr. Emura and A.Prof. Hasegawa at SCIS2014, and Prof.
Takagi and A.Prof. Morozov at Kyushu University. Concerning the third author, this work is partially supported
by Grants-in-Aid for Scientific Research; Research Project
Number:25540004.

(3)

6.3 Discussion
6.3.1 Attribute Privacy of our ABS.

10.

As opposed to the case of our ABID, our ABS has attributeprivacy defined in Section 2.5.2. Actually, more strongly,
attribute privacy holds for A with unbounded computational
ability because, for a fixed access policy f , the distributionof messages and signatures (m, σ) does not depend on secretkeys SKS where f (S) = 1.

[1] M. Abdalla, J. H. An, M. Bellare, and
C. Namprempre. From Identification to Signatures via
the Fiat-Shamir Transform: Minimizing Assumptionsfor Security and Forward-Security. In EUROCRYPT
2002, volume 2332 of LNCS, pages 418–433. Springer.
[2] H. Anada, S. Arita, S. Handa, and Y. Iwabuchi.
Attribute-Based Identification: Definitions andEﬃcient Constructions. In ACISP 2013, volume 7959
of LNCS, pages 168–186. Springer.
[3] A. Beimel. Secure Schemes for Secret Sharing and Key
Distribution. PhD thesis, Israel Institute ofTechnology, Technion, Haifa, Israel, 1996.
[4] M. Bellare and O. Goldreich. On Defining Proofs ofKnowledge. In CRYPTO ’92, volume 740 of LNCS,
pages 390–420. Springer.
[5] M. Bellare and A. Palacio. GQ and Schnorr
Identification Schemes: Proofs of Security against
Impersonation under Active and Concurrent Attacks.
In CRYPTO 2002, volume 2442 of LNCS, pages
162–177. Springer.
[6] D. Boneh and X. Boyen. Eﬃcient Selective-ID Secure
Identity-Based Encryption without Random Oracles.
In EUROCRYPT 2004, volume 3027 of LNCS, pages
223–238. Springer.
[7] R. Cramer, I. Damgård, and J. B. Nielsen. Multiparty
Computation from Threshold Homomorphic
Encryption. In EUROCRYPT 2001, volume 2045 of
LNCS, pages 280–300. Springer.
[8] I. Damgård. On σ-protocols. In Course Notes,
http://www.daimi.au.dk/ ivan/Sigma.ps, 2004.
[9] A. Fiat and A. Shamir. How to Prove Yourself:
Practical Solutions to Identification and Signature
Problems. In CRYPTO ’86, volume 263 of LNCS,
pages 186–194. Springer.
[10] V. Goyal, O. Pandey, A. Sahai, and B. Waters.
Attribute-Based Encryption for Fine-Grained AccessControl of Encrypted Data. In ACM-CCS ’06, volume263, pages 89–98. ACM.
[11] S. Guo and Y. Zeng. Attribute-Based Signature
Scheme. In ISA ’08, pages 509–511. IEEE.
[12] J. Katz and Y. Lindell. Introduction to Modern
Cryptography. Chapman and Hall/CRC, 2008.
[13] H. K. Maji, M. Prabhakaran, and M. Rosulek.
Attribute-Based Signatures. In CT-RSA 2011, volume6558 of LNCS, pages 376–392. Springer.
[14] T. Okamoto and K. Takashima. Eﬃcient
Attribute-Based Signatures for Non-monotone
Predicates in the standard model. In PKC 2011,
volume 6571 of LNCS, pages 35–52. Springer.
[15] C. P. Schnorr. Eﬃcient Identification and Signatures
for Smart cards. In CRYPTO ’89, volume 435 of
LNCS, pages 239–252. Springer.

6.3.2 Security Reduction.
Let qH denote the maximum number of hash queries issued by the adversaries on ABS and FSΣ . Combining theinequalities (3), (1) and (2), we obtain the following security reduction on advantages.
3/2

num.prob.
(λ))1/4 + neg(λ).
Adveufcma
F ,ABS (λ) ≤ qH (AdvS,Grp

7. EFFICIENCY COMPARISON
The most eﬃcient, previously known ABS scheme is theone by Okamoto and Takashima (OT11) [14]. We compare eﬃciency of our ABS scheme with their scheme in thelength of a signature as well as underlying assumption, inthe discrete-logarithm setting.
A prime of bit length λ (the security parameter) is denotedby p and we fix a cyclic group Gp of order p. We assume that
an element of Gp is represented by 2λ bits. Let l := |Lf(Tf )|denote the number of leaf nodes in an access tree. DLIN andCR hash mean the Decisional Linear assumption for pairinggroup [14] and the collision resistance of an employed hashfunction, respectively.
Then the lengths of a signature of the scheme OT11 andour ABS are as in the Table 1. OT11 scheme has advantages
in the security-proof model and access formula, whereas our
ABS realizes shorter length of signature.
Table 1: Eﬃciency Comparison.
SchemeLen. of Sig. (bit)Sec.-Proof Model
Assumption
Access Formula
Adaptive Target
Attribute Privacy

OT11[14](2λ)(9l + 11)
Standard
DLIN ∧ CR hashnon-monotone
Yes
Yes

Our ABS(2λ)l + (λ)(4l − 1)
Random Oracle
DLogmonotoneYes
Yes

8. CONCLUSIONS
Our strategy is in the Fiat-Shamir paradigm; we first constructed a boolean proof system Σf from a given Σ-protocol
Σ. Then, combining it with a credential bundle scheme fromFSΣ , we constructed ABID of proof of knowledge. Finally,
by applying the Fiat-Shamir transform to our ABID, we obtained our ABS. Our ABS can be constructed without pairings.

58

REFERENCES