# F2P-ABS: A Fast and Secure Attribute-Based Signature for Mobile Platforms

Authors: Guofeng Lin; Yunhao Xia; Chun Ying; Zhixin Sun
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Attribute-based signature (ABS) is a promising cryptographic primitive. It allows the signer to generate a signature with attributes satisfying the predicate without leaking more information, so as to provide message authenticity in an anonymous manner. However, drawbacks concerning security and efficiency hinder its applications for authentication in mobile platforms. Here, we present F2P-ABS, an escrow-free and pairing-free attribute-based signature supporting perfect signer privacy for mobile anonymous authentication. To enhance its adaptiveness to mobile platforms, a novel key extraction is proposed so that the key escrow problem is mitigated over the single authority setting. It also helps to remarkably reduce the size of the signing key. Different from existing schemes, F2P-ABS is free from pairing operations. It performs no pairing operation for verification. Without the loss of security, we prove that F2P-ABS achieves signer privacy in perfect sense. It is also proven to guarantee existential unforgeability under corrupted and adaptive chosen predicate and message attack, which is securer than existing schemes.


---

## Body

## 1. Introduction

Nowadays, with rapid development of computer network, electrical messaging services have been widely used in industry, e-commerce, medical treatment, and so on. In order to reduce management cost, cloud-based messaging is gradually getting prevailing [1]. As a result, more and more messages are transferred by off-premise infrastructure that some organizations jointly held. Such an open environment makes it highly possible to be under persistent threat of tamper attack [2, 3].Attribute-based signature (ABS) [4] is a variation of digital signature, which is one of the most promising cryptographic primitives. ABS stems from the identity-based signature [5, 6] but describes the signer by a set of attributes instead of a single unique identity. To endorse a message, the signer is allowed to generate a signature with his/her attributes satisfying the predicate without leaking other information. Providing data authenticity in this anonymous manner [7], ABS has been brought into much focus. It is widely accepted to build cloud-based messaging services [8–10], which make management of dynamic environment easier.In terms of security, ABS inherently suffers from key escrow problem [11–14]. Having the absolute power to generate and issue signing keys, the attribute authority is required to be fully trusted. If got compromised, the attribute authority can forge signatures associated with any tampered messages. As a result, the whole system would be broken. Furthermore, electrical messaging services are now being mobilized with the popularity of wireless networks and smart devices. But, the resource limitation of power and computation is still a bottleneck. Existing ABS schemes have to consume much resource. For one thing, large numbers of pairing computation are involved for verification. For example, performing one pairing operation based on 512-bit Tate pairing costs about 2 times of time than performing one exponentiation on a 1024-bit module [15]. For another thing, the size of the signing key is challenging the storage capacity of signing devices such as edge nodes in the Internet of Things. If existing ABS schemes are deployed in such a mobile platform, the cost of time and other resources would be unacceptable when a large universe of attributes was involved in.


### 1.1. Related Work

Sahai and Waters [16] first introduced a fuzzy identity-based encryption as an extension of identity-based cryptography [5]. The user is identified by a set of attributes and capable of decrypting a ciphertext if the distance between this attribute set and the one embedded into the ciphertext is close enough. Their construction indicated a novel cryptographic primitive called attribute-based encryption. Goyal et al. [17] proposed a key-policy attribute-based encryption (KP-ABE) using a tree-based access policy. For KP-ABE, the ciphertext is associated with an attribute set while the private key is associated with an access policy. Bethencourt et al. [18] proposed a ciphertext-policy attribute-based encryption (CP-ABE), in which the ciphertext is associated with an access policy while the private key is associated with an attribute set. To allow the data owner to flexibly define access policy before encryption, their construction is more complicated than [17]. Chow [11] indicated a major drawback comes when deploying public key cryptosystem is the key escrow problem that the single key generation center could decrypt any message addressed to a user by generating that user’s private key. To address this problem in ABE, Chase and Chow [12] proposed a multiauthority scheme in which each authority secretly holds a unique secret. For key generation, each authority must communicate with the rest of authorities. Even if n−1 authorities corrupted, where n is the number of authorities, it poses no threat to confidentiality of ciphertext at all. However, it results in On2 communication overhead for each time of key generation. Zhang et al. [19] provided an improvement of [12] to reduce the size of keys, and more importantly, it deployed only one subauthority to generate keys by its interactions with the key authority. Hur [13] introduced a two-party computational protocol (2PC) between the key authority and the data-storing center for key issuing. His construction was a novel solution but failed to show more details about how 2PC works. Lin et al. [9] presented a collaborative key management protocol that prevents ABE-based data sharing system from key escrow and key exposure, which relies on much bilinear computation.ABS is a new attribute-based cryptographic primitive that stems from ABE. In ABS, a signer who possesses a set of attributes from the attribute authority can sign a message with a predicate that is satisfied by his attributes. It can be noted that predicate in ABS generally indicates the access policy or access structure. Waters [20] transformed IBE to an identity-based signature (IBS) through a method proposed in [5]. After that, Yang et al. [21] first proposed a fuzzy identity-based signature (FIBE), in which the signer can endorse a message on behalf of an organization if his or her identity is similar enough to the claimed predicate. Yang et al.’s scheme is of some basic functions of ABS but does not guarantee signer privacy. Maji et al. [4] first formulated ABS with formal security definitions of existential unforgeability and signer privacy. Moreover, they built the predicate by monotone span program to provide flexible access control and the multiauthority construction to avoid leaking secrets when the attribute authority gets corrupted. However, they just proved security in the generic group model. It can be noted that those schemes stated above are generally considered as laying a theoretical foundation of ABS. Li et al. [22] proposed an ABS scheme with one central attribute authority and a group of distributed attribute authority, which, respectively, generate different components of a signing key. Although they provided provable security in the standard model, the construction is lack of expressiveness due to threshold predicate. To improve efficiency, a novel threshold ABS with a constant size signature was proposed [23]. For the t,t-ABS scheme, each signature contains just two elements from group G. And, for the t,n-ABS scheme, the signature size is linear in the number of signing attributes. Su et al. [24] proposed an efficient ABS scheme for Internet of Things that provides flexible access control. It supports any predicate consists of AND and OR threshold gates. Li et al. [25] indicated that, to guarantee integrity of outsourced data, the server needs to respond to mass authentication requests when receiving data from large numbers of users. It sets a huge challenge for performance of the server due to large numbers of bilinear pairing operations in authentication. They proposed a novel ABS that supports verifying different signatures in a batch manner so as to improve verification efficiency. Cui et al. [14] separated the attribute authority into two independent parties, namely, the attribute certifying authority and the key generation center. The attribute certifying authority is responsible for authenticating users’ attributes while the key generation center is known as taking over key generation. They designed an interactive protocol between the key generation center and the user based on zero-knowledge proof, by which only the user himself or herself knows the signing key after the interaction. As a result, the key generation center can by no means forge a valid signature even it gets corrupted. Rao and Dutta [26] proposed a novel key-policy ABS in which the predicate is built by linear secret sharing scheme (LSSS) to provide rich expressiveness. In addition, only 3 times of bilinear pairing operations are executed in verification. Rao [27] introduced a key-insulated mechanism for ABS to reduce the possibility of occurrence of key exposure when deploying ABS in performance-restrained platforms such as mobile devices. Due to periodical key updating, even if the unauthorized user obtains the signing key, the valid signature cannot still be forged unless within the current time slot.


### 1.2. Our Contributions

In this paper, we focus on constructing a secure and efficient ABS scheme and try to mitigate problems that existing schemes [24–27] suffer. We try to realize the vital properties which include escrow-free, pairing-free, and perfect signer privacy. As is shown in Table 1, the ABS schemes [24, 26, 27] are not able to guarantee security if the attribute authority got compromised when it holds signing keys in escrow. The scheme in [25] mitigates the key escrow problem with dependency on multiauthority setting, which makes it cumbersome in computation and communications (see Tables 2 and 3).Table 1
Comparison in terms of functionality of ABS schemes.
Scheme
[24]
[25]
[26]
[27]
F2P-ABS
Authority
Single
Multiple
Single
Single
Single
Escrow-free
×
√
×
×
√
Pairing-free
×
×
×
×
√
Predicate
Tree
Threshold
LSSS
LSSS
Tree
Perfect signer privacy
×
×
√
×
√
Complexity assumption
CDH
CDH
n-CDHE
n-CDHE
DL
EUF-ca-CPMA
×
×
×
×
√Table 2
Comparison in terms of public parameter size, secret key size, signing key size, and signature size.
Scheme
Param.
Sec.
Sk.
Sig.
[24]
3
G
+
G
T
Z
p
∗
2
a
s
k
+
1
G
2
a
u
+
2
G
[25]
k
k
−
1
Z
p
∗
+
k
G
+
k
G
T
k
Z
p
∗
2
a
s
k
+
1
G
a
s
p
+
2
G
[26]
a
u
+
l
+
2
G
+
G
T
Z
p
∗
a
u
+
a
s
k
G
3
G
[27]
a
u
+
1
G
+
G
T
G
2
a
s
k
+
3
G
a
s
p
+
a
e
p
+
4
G
F2P-ABS
2
a
u
+
4
G
2
a
u
+
4
Z
p
∗
a
s
k
+
1
G
a
s
p
+
2
Z
p
∗
+
a
s
p
GTable 3
Comparison in terms of computation cost during signing and verifying.
Scheme
Signing
Verifying
Exp. overG
Exp. overGT
Pair.
Exp. overG
Exp. overGT
Pair.
[24]
4
a
s
p
+
2
0
0
n
s
p
+
ϕ
s
p
−
1
0
2
ϕ
s
p
+
2
[25]
k
+
1
ϕ
s
p
+
k
a
s
p
+
2
0
0
0
0
a
s
p
+
2
[26]
ϕ
s
p
+
a
s
p
+
l
+
1
0
0
ϕ
s
p
+
l
0
3
[27]
4
a
s
p
+
2
a
e
p
+
8
1
0
a
s
k
+
2
ϕ
e
p
+
1
0
a
s
p
+
5
F2P-ABS
a
s
p
0
0
a
s
p
+
n
s
p
+
ϕ
s
p
−
1
0
0The key extraction of our F2P-ABS is elegant and effective. It mitigates the key escrow problem on the condition of the single authority setting. With the participation of both attribute authority and data-storing center, anyone of them getting compromised will have no impact on security. By the key extraction of F2P-ABS, the size of the signing key is reduced by nearly half of that in [24–27] (see Table 2).Since pairing computation is considered the most expensive operation, the number of pairing operations is a critical factor of feasibility in practical scenes. Most ABS schemes are dependent on pairing, so the signer has to execute pairing operations to validate the message. The required number of pairing operations in [24] proliferates linearly with the number of attributes in a minimum attribute set of a signing predicate. The required number of pairing operations in [25, 27] proliferates linearly with the number of attributes in a signing predicate. It demonstrates that a feasible ABS scheme which provides both strong reliability and high-efficiency scheme is far-fetched, especially for authentication in mobile platform. For our F2P-ABS, in contrast, it does not need any pairing operations for verifying (see Table 3). This is even less than that in [26], which is 3 pairing operations.To enhance security, we provide a novel security model called existential unforgeability under corrupted and adaptive chosen predicate and message attack (EUF-ca-CPMA). And, our F2P-ABS is proven to be EUF-ca-CPMA secure assuming the hardness of discrete logarithm (DL) problem. It is stronger than existential unforgeability under a selective predicate/attribute set and adaptive chosen-message attack (EUF-sP-CMA/EUF-sA-CMA), which is met by [24–27]. Furthermore, it guarantees signer privacy in a perfect sense as in [26].To conclude, the proposed F2P-ABS outperforms the existing schemes in terms of security and efficiency.


### 1.3. Organization

The rest of the paper is organized as follows. We review essential preliminaries in Section2, show the architecture in Section 3, show the security requirements in Section 4, propose main construction of F2P-ABS in Section 5, provide security analysis in Section 6, present performance comparison against similar schemes in Section 7, and draw conclusion and highlight our future work in Section 8.


## 1.1. Related Work

Sahai and Waters [16] first introduced a fuzzy identity-based encryption as an extension of identity-based cryptography [5]. The user is identified by a set of attributes and capable of decrypting a ciphertext if the distance between this attribute set and the one embedded into the ciphertext is close enough. Their construction indicated a novel cryptographic primitive called attribute-based encryption. Goyal et al. [17] proposed a key-policy attribute-based encryption (KP-ABE) using a tree-based access policy. For KP-ABE, the ciphertext is associated with an attribute set while the private key is associated with an access policy. Bethencourt et al. [18] proposed a ciphertext-policy attribute-based encryption (CP-ABE), in which the ciphertext is associated with an access policy while the private key is associated with an attribute set. To allow the data owner to flexibly define access policy before encryption, their construction is more complicated than [17]. Chow [11] indicated a major drawback comes when deploying public key cryptosystem is the key escrow problem that the single key generation center could decrypt any message addressed to a user by generating that user’s private key. To address this problem in ABE, Chase and Chow [12] proposed a multiauthority scheme in which each authority secretly holds a unique secret. For key generation, each authority must communicate with the rest of authorities. Even if n−1 authorities corrupted, where n is the number of authorities, it poses no threat to confidentiality of ciphertext at all. However, it results in On2 communication overhead for each time of key generation. Zhang et al. [19] provided an improvement of [12] to reduce the size of keys, and more importantly, it deployed only one subauthority to generate keys by its interactions with the key authority. Hur [13] introduced a two-party computational protocol (2PC) between the key authority and the data-storing center for key issuing. His construction was a novel solution but failed to show more details about how 2PC works. Lin et al. [9] presented a collaborative key management protocol that prevents ABE-based data sharing system from key escrow and key exposure, which relies on much bilinear computation.ABS is a new attribute-based cryptographic primitive that stems from ABE. In ABS, a signer who possesses a set of attributes from the attribute authority can sign a message with a predicate that is satisfied by his attributes. It can be noted that predicate in ABS generally indicates the access policy or access structure. Waters [20] transformed IBE to an identity-based signature (IBS) through a method proposed in [5]. After that, Yang et al. [21] first proposed a fuzzy identity-based signature (FIBE), in which the signer can endorse a message on behalf of an organization if his or her identity is similar enough to the claimed predicate. Yang et al.’s scheme is of some basic functions of ABS but does not guarantee signer privacy. Maji et al. [4] first formulated ABS with formal security definitions of existential unforgeability and signer privacy. Moreover, they built the predicate by monotone span program to provide flexible access control and the multiauthority construction to avoid leaking secrets when the attribute authority gets corrupted. However, they just proved security in the generic group model. It can be noted that those schemes stated above are generally considered as laying a theoretical foundation of ABS. Li et al. [22] proposed an ABS scheme with one central attribute authority and a group of distributed attribute authority, which, respectively, generate different components of a signing key. Although they provided provable security in the standard model, the construction is lack of expressiveness due to threshold predicate. To improve efficiency, a novel threshold ABS with a constant size signature was proposed [23]. For the t,t-ABS scheme, each signature contains just two elements from group G. And, for the t,n-ABS scheme, the signature size is linear in the number of signing attributes. Su et al. [24] proposed an efficient ABS scheme for Internet of Things that provides flexible access control. It supports any predicate consists of AND and OR threshold gates. Li et al. [25] indicated that, to guarantee integrity of outsourced data, the server needs to respond to mass authentication requests when receiving data from large numbers of users. It sets a huge challenge for performance of the server due to large numbers of bilinear pairing operations in authentication. They proposed a novel ABS that supports verifying different signatures in a batch manner so as to improve verification efficiency. Cui et al. [14] separated the attribute authority into two independent parties, namely, the attribute certifying authority and the key generation center. The attribute certifying authority is responsible for authenticating users’ attributes while the key generation center is known as taking over key generation. They designed an interactive protocol between the key generation center and the user based on zero-knowledge proof, by which only the user himself or herself knows the signing key after the interaction. As a result, the key generation center can by no means forge a valid signature even it gets corrupted. Rao and Dutta [26] proposed a novel key-policy ABS in which the predicate is built by linear secret sharing scheme (LSSS) to provide rich expressiveness. In addition, only 3 times of bilinear pairing operations are executed in verification. Rao [27] introduced a key-insulated mechanism for ABS to reduce the possibility of occurrence of key exposure when deploying ABS in performance-restrained platforms such as mobile devices. Due to periodical key updating, even if the unauthorized user obtains the signing key, the valid signature cannot still be forged unless within the current time slot.


## 1.2. Our Contributions

In this paper, we focus on constructing a secure and efficient ABS scheme and try to mitigate problems that existing schemes [24–27] suffer. We try to realize the vital properties which include escrow-free, pairing-free, and perfect signer privacy. As is shown in Table 1, the ABS schemes [24, 26, 27] are not able to guarantee security if the attribute authority got compromised when it holds signing keys in escrow. The scheme in [25] mitigates the key escrow problem with dependency on multiauthority setting, which makes it cumbersome in computation and communications (see Tables 2 and 3).Table 1
Comparison in terms of functionality of ABS schemes.
Scheme
[24]
[25]
[26]
[27]
F2P-ABS
Authority
Single
Multiple
Single
Single
Single
Escrow-free
×
√
×
×
√
Pairing-free
×
×
×
×
√
Predicate
Tree
Threshold
LSSS
LSSS
Tree
Perfect signer privacy
×
×
√
×
√
Complexity assumption
CDH
CDH
n-CDHE
n-CDHE
DL
EUF-ca-CPMA
×
×
×
×
√Table 2
Comparison in terms of public parameter size, secret key size, signing key size, and signature size.
Scheme
Param.
Sec.
Sk.
Sig.
[24]
3
G
+
G
T
Z
p
∗
2
a
s
k
+
1
G
2
a
u
+
2
G
[25]
k
k
−
1
Z
p
∗
+
k
G
+
k
G
T
k
Z
p
∗
2
a
s
k
+
1
G
a
s
p
+
2
G
[26]
a
u
+
l
+
2
G
+
G
T
Z
p
∗
a
u
+
a
s
k
G
3
G
[27]
a
u
+
1
G
+
G
T
G
2
a
s
k
+
3
G
a
s
p
+
a
e
p
+
4
G
F2P-ABS
2
a
u
+
4
G
2
a
u
+
4
Z
p
∗
a
s
k
+
1
G
a
s
p
+
2
Z
p
∗
+
a
s
p
GTable 3
Comparison in terms of computation cost during signing and verifying.
Scheme
Signing
Verifying
Exp. overG
Exp. overGT
Pair.
Exp. overG
Exp. overGT
Pair.
[24]
4
a
s
p
+
2
0
0
n
s
p
+
ϕ
s
p
−
1
0
2
ϕ
s
p
+
2
[25]
k
+
1
ϕ
s
p
+
k
a
s
p
+
2
0
0
0
0
a
s
p
+
2
[26]
ϕ
s
p
+
a
s
p
+
l
+
1
0
0
ϕ
s
p
+
l
0
3
[27]
4
a
s
p
+
2
a
e
p
+
8
1
0
a
s
k
+
2
ϕ
e
p
+
1
0
a
s
p
+
5
F2P-ABS
a
s
p
0
0
a
s
p
+
n
s
p
+
ϕ
s
p
−
1
0
0The key extraction of our F2P-ABS is elegant and effective. It mitigates the key escrow problem on the condition of the single authority setting. With the participation of both attribute authority and data-storing center, anyone of them getting compromised will have no impact on security. By the key extraction of F2P-ABS, the size of the signing key is reduced by nearly half of that in [24–27] (see Table 2).Since pairing computation is considered the most expensive operation, the number of pairing operations is a critical factor of feasibility in practical scenes. Most ABS schemes are dependent on pairing, so the signer has to execute pairing operations to validate the message. The required number of pairing operations in [24] proliferates linearly with the number of attributes in a minimum attribute set of a signing predicate. The required number of pairing operations in [25, 27] proliferates linearly with the number of attributes in a signing predicate. It demonstrates that a feasible ABS scheme which provides both strong reliability and high-efficiency scheme is far-fetched, especially for authentication in mobile platform. For our F2P-ABS, in contrast, it does not need any pairing operations for verifying (see Table 3). This is even less than that in [26], which is 3 pairing operations.To enhance security, we provide a novel security model called existential unforgeability under corrupted and adaptive chosen predicate and message attack (EUF-ca-CPMA). And, our F2P-ABS is proven to be EUF-ca-CPMA secure assuming the hardness of discrete logarithm (DL) problem. It is stronger than existential unforgeability under a selective predicate/attribute set and adaptive chosen-message attack (EUF-sP-CMA/EUF-sA-CMA), which is met by [24–27]. Furthermore, it guarantees signer privacy in a perfect sense as in [26].To conclude, the proposed F2P-ABS outperforms the existing schemes in terms of security and efficiency.


## 1.3. Organization

The rest of the paper is organized as follows. We review essential preliminaries in Section2, show the architecture in Section 3, show the security requirements in Section 4, propose main construction of F2P-ABS in Section 5, provide security analysis in Section 6, present performance comparison against similar schemes in Section 7, and draw conclusion and highlight our future work in Section 8.


## 2. Preliminaries

In this section, we will introduce some essential cryptographic preliminaries. Before it, we first describe some important notations, which is shown in Table4. These are required for an unambiguous presentation of the paper, some of which will be interpreted in the following sections.Table 4
Notations.
Notation
Definition
att
i
Attribute
Ω
Attribute universe
S
Signer attribute set
T
Tree-based predicate
S
min
Minimum attribute set ofS according to T
Nodex
A node ofT whose index is x
att
x
Attribute associated with the leaf nodex
T
x
Tree-based subpredicate ofT rooted at node x
parent
x
Parent node of nodex
Λ
x
Set of child nodes of nodex
Λ
′
x
Set of child nodes at which subpredicates are rooted thatSmin cannot satisfy
z
⟵
R
X
z is randomly chosen from X according to uniform distribution
GC
f
Garbled circuit of functionf


### 2.1. Predicate

Definition 1 (access structure).
LetP1,P2,…,Pn be a party of several participants. An access structure A is defined as an arbitrary collection of nonempty subsets of P1,P2,…,Pn, namely, A⊆2P1,P2,…,Pn\∅. We consider a set S authorized if S∈A.
For two arbitrary setsB and C such that B⊆C, we say A is monotonic if C∈A. It can be noted that the term access structure mentioned in the following means monotonic access structure if there is no particular revelatory. For ABS, we note that a predicate generally indicates an access structure. From now on, to avoid confusion, we only use the term predicate.Definition 2 (tree-based predicate).
LetT be a tree-based predicate, which is associated with a tree consisting of some leaf nodes and nonleaf nodes. Each nonleaf node represents a threshold gate, described by the number of its children and a threshold value. Each tree also defines an ordering among all nodes, and accordingly each index value is uniquely assigned to a node in an arbitrary manner. Without loss of generality, let x be an index of node. If numx is the number of children of a node x and kx is its threshold value, then 0<kx≤numx. When kx=1, the threshold gate is an “OR” gate, and when kx=numx, it is an “AND” gate. Each leaf node x represents an attribute. For arbitrary attribute set S, we have TS=1 if it satisfies the predicate that we described; otherwise, we have TS=0.Definition 3 (minimum attribute set).
For all attribute setS such that TS=1, there exists a minimum attribute set Smin⊆S such that TSmin=1 and TS′=0 for all S′⊈Smin. For instance, there is a tree-based predicate T whose postfix expression is {“D,” “E,” “F,” “2 of 3,” “A,” “B,” “C,” “1 of 3,” “2 of 2”}. Each character represents a leaf node associated with an attribute. Each string like “x of y” represents a nonleaf node where x is its threshold and y is the number of its child nodes. A signer, whose attribute set S is {“A,” “B,” “D,” “E,” “F”}, sends a message signed through ABS with this predicate. Obviously, one of his minimum attribute sets Smin is {“A,” “D,” “E”}.


### 2.2. Garbled Circuit

Definition 4 (garbled circuit).
Garbled circuit allows two parties holding inputsx and y, respectively, to evaluate an arbitrary function fx,y without leaking any information about their inputs beyond what is implied by the function output. The basic idea is that one party (the garbler) prepares an encrypted version of the function f; the data transmitter and receiver then obliviously compute the output of the circuit without learning any intermediate values.
Starting with a Boolean circuitfbi,bj where bi and bj are one-bit inputs, respectively, from input wires i and j. The circuit generator associates two random cryptographic keys wi0 and wi1 (wj0 and wj1) with each input wire i (j). Then, for each output bk=fbi,bj, the generator computes ciphertext Encwibi,wjbjwkbk. The resulting four ciphertexts, in a random order, constitute a garbled table. Then, the garbled table is sent to the evaluator.
The evaluator also obtains the keys corresponding to each input. The circuit generator can first simply sendwibi, which corresponds to the actual input from the circuit generator. Then, it uses 1-out-of-2 oblivious transfer (see Definition 5) to enable the circuit evaluator to obliviously obtain the key wjbj corresponding to its own input.
Given keys associated with both inputs from wiresi and j, the evaluator can extract an output key wkbk by decrypting the appropriate ciphertext. Only one single decryption suffices the extraction [28]. Mapping from output keys to output bits, the evaluator can finally learn the actual output of f. If desired, the evaluator can share the output with the circuit generator. By using the framework proposed by Huang et al. [29], it is efficient to modularly build a secure protocol computing the function f.Definition 5 (1-out-of-m oblivious transfer).
A 1-out-of-m oblivious transfer protocolOT1m [30] refers to a protocol where at the beginning of the protocol, one party, Bob, has m inputs X1,…,Xm and at the end of the protocol, the other party, Alice, learns one of the inputs Xi for an i (1≤i≤m) of own choice, without learning anything about the other inputs and without allowing Bob to learn anything about i. An efficient OT1m was proposed by Tzeng [31].


### 2.3. Complexity Assumption

Definition 6 (discrete logarithm assumption).
Given a multiplicative cyclic groupG with a prime order p. The discrete logarithm (DL) problem is given g1⟵RG and a generator g of G, to find a unique x∈Zp∗ which makes g1=gx. For clarity, we denote DLP by x⟵G,g,g1. If there is a polynomial-time algorithm A extracting x with a probability that satisfies Prx⟵G,g,g1≥ε, we denote the advantage to solve DLP by AdvADLP=ε. The DL assumption says that there is no such an algorithm which can solve DL problem with a nonnegligible advantage.
It is well known that this problem is considered to be intractable. The DL assumption has been used to create many cryptosystems, including the ElGamal cryptosystem. This intractable assumption has also been used to create signature schemes [32].


## 2.1. Predicate

Definition 1 (access structure).
LetP1,P2,…,Pn be a party of several participants. An access structure A is defined as an arbitrary collection of nonempty subsets of P1,P2,…,Pn, namely, A⊆2P1,P2,…,Pn\∅. We consider a set S authorized if S∈A.
For two arbitrary setsB and C such that B⊆C, we say A is monotonic if C∈A. It can be noted that the term access structure mentioned in the following means monotonic access structure if there is no particular revelatory. For ABS, we note that a predicate generally indicates an access structure. From now on, to avoid confusion, we only use the term predicate.Definition 2 (tree-based predicate).
LetT be a tree-based predicate, which is associated with a tree consisting of some leaf nodes and nonleaf nodes. Each nonleaf node represents a threshold gate, described by the number of its children and a threshold value. Each tree also defines an ordering among all nodes, and accordingly each index value is uniquely assigned to a node in an arbitrary manner. Without loss of generality, let x be an index of node. If numx is the number of children of a node x and kx is its threshold value, then 0<kx≤numx. When kx=1, the threshold gate is an “OR” gate, and when kx=numx, it is an “AND” gate. Each leaf node x represents an attribute. For arbitrary attribute set S, we have TS=1 if it satisfies the predicate that we described; otherwise, we have TS=0.Definition 3 (minimum attribute set).
For all attribute setS such that TS=1, there exists a minimum attribute set Smin⊆S such that TSmin=1 and TS′=0 for all S′⊈Smin. For instance, there is a tree-based predicate T whose postfix expression is {“D,” “E,” “F,” “2 of 3,” “A,” “B,” “C,” “1 of 3,” “2 of 2”}. Each character represents a leaf node associated with an attribute. Each string like “x of y” represents a nonleaf node where x is its threshold and y is the number of its child nodes. A signer, whose attribute set S is {“A,” “B,” “D,” “E,” “F”}, sends a message signed through ABS with this predicate. Obviously, one of his minimum attribute sets Smin is {“A,” “D,” “E”}.


## 2.2. Garbled Circuit

Definition 4 (garbled circuit).
Garbled circuit allows two parties holding inputsx and y, respectively, to evaluate an arbitrary function fx,y without leaking any information about their inputs beyond what is implied by the function output. The basic idea is that one party (the garbler) prepares an encrypted version of the function f; the data transmitter and receiver then obliviously compute the output of the circuit without learning any intermediate values.
Starting with a Boolean circuitfbi,bj where bi and bj are one-bit inputs, respectively, from input wires i and j. The circuit generator associates two random cryptographic keys wi0 and wi1 (wj0 and wj1) with each input wire i (j). Then, for each output bk=fbi,bj, the generator computes ciphertext Encwibi,wjbjwkbk. The resulting four ciphertexts, in a random order, constitute a garbled table. Then, the garbled table is sent to the evaluator.
The evaluator also obtains the keys corresponding to each input. The circuit generator can first simply sendwibi, which corresponds to the actual input from the circuit generator. Then, it uses 1-out-of-2 oblivious transfer (see Definition 5) to enable the circuit evaluator to obliviously obtain the key wjbj corresponding to its own input.
Given keys associated with both inputs from wiresi and j, the evaluator can extract an output key wkbk by decrypting the appropriate ciphertext. Only one single decryption suffices the extraction [28]. Mapping from output keys to output bits, the evaluator can finally learn the actual output of f. If desired, the evaluator can share the output with the circuit generator. By using the framework proposed by Huang et al. [29], it is efficient to modularly build a secure protocol computing the function f.Definition 5 (1-out-of-m oblivious transfer).
A 1-out-of-m oblivious transfer protocolOT1m [30] refers to a protocol where at the beginning of the protocol, one party, Bob, has m inputs X1,…,Xm and at the end of the protocol, the other party, Alice, learns one of the inputs Xi for an i (1≤i≤m) of own choice, without learning anything about the other inputs and without allowing Bob to learn anything about i. An efficient OT1m was proposed by Tzeng [31].


## 2.3. Complexity Assumption

Definition 6 (discrete logarithm assumption).
Given a multiplicative cyclic groupG with a prime order p. The discrete logarithm (DL) problem is given g1⟵RG and a generator g of G, to find a unique x∈Zp∗ which makes g1=gx. For clarity, we denote DLP by x⟵G,g,g1. If there is a polynomial-time algorithm A extracting x with a probability that satisfies Prx⟵G,g,g1≥ε, we denote the advantage to solve DLP by AdvADLP=ε. The DL assumption says that there is no such an algorithm which can solve DL problem with a nonnegligible advantage.
It is well known that this problem is considered to be intractable. The DL assumption has been used to create many cryptosystems, including the ElGamal cryptosystem. This intractable assumption has also been used to create signature schemes [32].


## 3. F2P-ABS Architecture Overview

### 3.1. Definition of F2P-ABS

Following the definition in [26], our F2P-ABS consists of six algorithms:(1)
gparam⟵GSetup1λ: the GSetup algorithm is run with a security parameter λ, which outputs a global parameter param.(2)
dparam,dsk⟵DSetupgparam: the DSetup algorithm takes param as input and generates the data-storing center parameter dparam and the data-storing center secret key dsk. Finally, it publishes dparam and stores dsk.(3)
aparam,ask⟵ASetupgparam: the ASetup algorithm takes gparam as input and generates the attribute authority parameter aparam and the authority secret key ask. Finally, it publishes aparam and stores ask.(4)
sk⟵KeyExtractgparam,dparam,aparam,ask,dsk,S: the KeyExtract algorithm takes gparam, dparam, aparam, ask, and dsk as input, as well as an attribute set S. Finally, it outputs a signing key sk.(5)
σ⟵Signgparam,dparam,aparam,sk,T,m: the Sign algorithm takes gparam, dparam, aparam, and sk as input to endorse a message m with respect to the predicate T. Then, a valid signature σ is generated.(6)
1/0⟵Verifygparam,dparam,aparam,m,T,σ: the Verify algorithm takes gparam, dparam, aparam, m, T, and σ as input. It outputs 1 if σ is a valid signature of m corresponding to T; otherwise, it outputs 0.


### 3.2. System Description

As is shown in Figure1, the framework of an anonymous message authentication system based on F2P-ABS consists of the following four entities:(1)
Attribute Authority (AA). This is a semitrusted entity that generates aparam and ask. By collaborating with the data-storing center (DSC), it issues sk to the signer. All communications between the AA, the signer, and the DSC are secured by secure shell (SSH) protocol.(2)
Data-Storing Center (DSC). This is a semitrusted entity that stores messages and their corresponding signature. It takes part in issuing sk for the signer to avoid put sk in escrow in the AA. But, it also does not obtain any part of sk. Besides, it is responsible for transferring messages and signatures to corresponding verifiers by SSH protocol.(3)
Signer. This is who wants to share authentic messages in public environments, such as in social network. The signer defines a predicate that exhibits the authenticity of the signer to the public. Then, the message m will be signed by sk, and a signature σ is generated. As is shown in Figure 1, the predicate can be described by a postfix expression {“Professor,” “Associate Professor,” “Lecturer,” “1 of 3,” “Department of Informatics,” “University A,” “3 of 3”}. Alice whose attribute set is {“University A,” “Department of Informatics,” “Professor”} can sign the message with this predicate. Finally, m and σ will be outsourced to the DSC.(4)
Verifier. This is who receives m and wants to verify it. By computation with m and σ, the verifier will know whether the message is valid. As shown in Figure 1, Bob and Carol can verify that message comes from the signer satisfies that predicate but do not know who he/she is.Figure 1
The mobile anonymous authentication system based on F2P-ABS.


## 3.1. Definition of F2P-ABS

Following the definition in [26], our F2P-ABS consists of six algorithms:(1)
gparam⟵GSetup1λ: the GSetup algorithm is run with a security parameter λ, which outputs a global parameter param.(2)
dparam,dsk⟵DSetupgparam: the DSetup algorithm takes param as input and generates the data-storing center parameter dparam and the data-storing center secret key dsk. Finally, it publishes dparam and stores dsk.(3)
aparam,ask⟵ASetupgparam: the ASetup algorithm takes gparam as input and generates the attribute authority parameter aparam and the authority secret key ask. Finally, it publishes aparam and stores ask.(4)
sk⟵KeyExtractgparam,dparam,aparam,ask,dsk,S: the KeyExtract algorithm takes gparam, dparam, aparam, ask, and dsk as input, as well as an attribute set S. Finally, it outputs a signing key sk.(5)
σ⟵Signgparam,dparam,aparam,sk,T,m: the Sign algorithm takes gparam, dparam, aparam, and sk as input to endorse a message m with respect to the predicate T. Then, a valid signature σ is generated.(6)
1/0⟵Verifygparam,dparam,aparam,m,T,σ: the Verify algorithm takes gparam, dparam, aparam, m, T, and σ as input. It outputs 1 if σ is a valid signature of m corresponding to T; otherwise, it outputs 0.


## 3.2. System Description

As is shown in Figure1, the framework of an anonymous message authentication system based on F2P-ABS consists of the following four entities:(1)
Attribute Authority (AA). This is a semitrusted entity that generates aparam and ask. By collaborating with the data-storing center (DSC), it issues sk to the signer. All communications between the AA, the signer, and the DSC are secured by secure shell (SSH) protocol.(2)
Data-Storing Center (DSC). This is a semitrusted entity that stores messages and their corresponding signature. It takes part in issuing sk for the signer to avoid put sk in escrow in the AA. But, it also does not obtain any part of sk. Besides, it is responsible for transferring messages and signatures to corresponding verifiers by SSH protocol.(3)
Signer. This is who wants to share authentic messages in public environments, such as in social network. The signer defines a predicate that exhibits the authenticity of the signer to the public. Then, the message m will be signed by sk, and a signature σ is generated. As is shown in Figure 1, the predicate can be described by a postfix expression {“Professor,” “Associate Professor,” “Lecturer,” “1 of 3,” “Department of Informatics,” “University A,” “3 of 3”}. Alice whose attribute set is {“University A,” “Department of Informatics,” “Professor”} can sign the message with this predicate. Finally, m and σ will be outsourced to the DSC.(4)
Verifier. This is who receives m and wants to verify it. By computation with m and σ, the verifier will know whether the message is valid. As shown in Figure 1, Bob and Carol can verify that message comes from the signer satisfies that predicate but do not know who he/she is.Figure 1
The mobile anonymous authentication system based on F2P-ABS.


## 4. Security Requirements

For F2P-ABS, we adopt a semitrusted (also known as honest-but-curious) threat model, where attribute authorities and data-storing center are assumed to follow the protocol but may attempt to learn additional information from the protocol transcript. Although this is a bit weak, it is a standard security model for escrow-free computation. Studying F2P-ABS in the semitrusted setting is relevant for two reasons:(1)
There may be instances where a semitrusted model is appropriate: (1) when parties are legitimately trusted but are prevented from divulging information for legal reasons, or want to protect against future break-in; (2) where it would difficult for parties to change the software attestation is used or due to internal controls in place (for example, when parties represent corporations or government agencies).(2)
Protocols for the semitrusted setting are an important first step toward constructing protocols with stronger security guarantees. There exist generic ways to give full security against malicious authorities.


### 4.1. Correctness

Definition 7 (correctness of F2P-ABS).
We define a valid signature to be the one that can be verified with success probability 1. We say F2P-ABS scheme guarantees correctness if, for all pairs of attribute setS and predicate T satisfying TS=1, all signing keys associated with S can always be used to generate a valid signature of message m with predicate T.


### 4.2. Perfect Signer Privacy

Definition 8 (perfect signer privacy of F2P-ABS).
Our F2P-ABS is perfectly private if, for allgparam⟵GSetup1λ, all dparam,dsk⟵DSetupgparam, all aparam,ask⟵ASetupgparam, all messages m, all attribute sets S1 and S2, all sk1⟵KeyExtractgparam,dparam,aparam,ask,dsk,S1 and sk2⟵KeyExtractgparam,dparam,aparam,ask,dsk,S2, all predicates T such that TS1=1 and TS2=1, and the distributions of σ1⟵Signgparam,dparam,aparam,sk1,T,m and σ2⟵Signgparam,dparam,aparam,sk2,T,m are equal.


### 4.3. Existential Unforgeability

Based on the definition of existential unforgeability provided in [33], we build the definition of existential unforgeability under corrupted and adaptive chosen predicate and message attack (EUF-ca-CPMA).Definition 9 (EUF-ca-CPMA of F2P-ABS).
We defineε to be the success probability of an adversary A in the following game with a challenger C:(1)
Initial Phase. A submits a bit c0∈0,1, which will be used to forge a signature over either the corrupted AA or the corrupted DSC.(2)
Setup Phase. C publishes all parameters independent with attributes to A with the following steps:(1)
C runs gparam⟵GSetup1λ and gives gparam to A.(2)
C runs dparam,dsk⟵DSetupgparam and gives A part of dparam that is independent of attributes.(3)
C runs aparam,ask⟵ASetupgparam and gives A part of aparam that is independent to attributes(4)
Ifc0=0, C gives A part of ask that is independent to attributes. Otherwise, C gives A part of dsk that is independent to attributes.(3)
Query Phase. A adaptively issues a polynomially bounded number of queries to the following oracles:(1)
Attribute Oracle. A submits an attribute atti. If c0=0, C returns to A part of ask and dparam that correspond to attributes. Otherwise, C returns to A part of aparam and dsk that correspond to attributes.(2)
Key Extracting Oracle. A submits an attribute set S and obtains the corresponding signing key sk⟵KeyExtractgparam,dparam,aparam,ask,dsk,S.(3)
Signing Oracle. A submits a message m and a predicate T. C selects an attribute set S such that TS=1 computes a signing key sk⟵KeyExtractgparam,dparam,aparam,ask,dsk,S and returns the corresponding signature σ⟵Signgparam,dparam,aparam,sk,T,m.(4)
Forge Phase. A forges a signature σ∗ of a message m∗ with a predicate T∗ and succeeds in this game if m∗ and T∗ are never queried to the signing oracle; T∗ does not accept any attribute set queried to key extracting oracle; C eventually obtains 1⟵Verifygparam,dparam,aparam,m∗,T∗,σ∗.
We say F2P-ABS ist,qatt,qsk,qsig,ε-EUF-CPMA secure if, for any probabilistic polynomial-time adversary A running in time at most t that makes at most qatt attribute queries, qsk key extracting queries, and qsig signing queries, the A’s advantage AdvAEUF−CPMA is at most ε.


## 4.1. Correctness

Definition 7 (correctness of F2P-ABS).
We define a valid signature to be the one that can be verified with success probability 1. We say F2P-ABS scheme guarantees correctness if, for all pairs of attribute setS and predicate T satisfying TS=1, all signing keys associated with S can always be used to generate a valid signature of message m with predicate T.


## 4.2. Perfect Signer Privacy

Definition 8 (perfect signer privacy of F2P-ABS).
Our F2P-ABS is perfectly private if, for allgparam⟵GSetup1λ, all dparam,dsk⟵DSetupgparam, all aparam,ask⟵ASetupgparam, all messages m, all attribute sets S1 and S2, all sk1⟵KeyExtractgparam,dparam,aparam,ask,dsk,S1 and sk2⟵KeyExtractgparam,dparam,aparam,ask,dsk,S2, all predicates T such that TS1=1 and TS2=1, and the distributions of σ1⟵Signgparam,dparam,aparam,sk1,T,m and σ2⟵Signgparam,dparam,aparam,sk2,T,m are equal.


## 4.3. Existential Unforgeability

Based on the definition of existential unforgeability provided in [33], we build the definition of existential unforgeability under corrupted and adaptive chosen predicate and message attack (EUF-ca-CPMA).Definition 9 (EUF-ca-CPMA of F2P-ABS).
We defineε to be the success probability of an adversary A in the following game with a challenger C:(1)
Initial Phase. A submits a bit c0∈0,1, which will be used to forge a signature over either the corrupted AA or the corrupted DSC.(2)
Setup Phase. C publishes all parameters independent with attributes to A with the following steps:(1)
C runs gparam⟵GSetup1λ and gives gparam to A.(2)
C runs dparam,dsk⟵DSetupgparam and gives A part of dparam that is independent of attributes.(3)
C runs aparam,ask⟵ASetupgparam and gives A part of aparam that is independent to attributes(4)
Ifc0=0, C gives A part of ask that is independent to attributes. Otherwise, C gives A part of dsk that is independent to attributes.(3)
Query Phase. A adaptively issues a polynomially bounded number of queries to the following oracles:(1)
Attribute Oracle. A submits an attribute atti. If c0=0, C returns to A part of ask and dparam that correspond to attributes. Otherwise, C returns to A part of aparam and dsk that correspond to attributes.(2)
Key Extracting Oracle. A submits an attribute set S and obtains the corresponding signing key sk⟵KeyExtractgparam,dparam,aparam,ask,dsk,S.(3)
Signing Oracle. A submits a message m and a predicate T. C selects an attribute set S such that TS=1 computes a signing key sk⟵KeyExtractgparam,dparam,aparam,ask,dsk,S and returns the corresponding signature σ⟵Signgparam,dparam,aparam,sk,T,m.(4)
Forge Phase. A forges a signature σ∗ of a message m∗ with a predicate T∗ and succeeds in this game if m∗ and T∗ are never queried to the signing oracle; T∗ does not accept any attribute set queried to key extracting oracle; C eventually obtains 1⟵Verifygparam,dparam,aparam,m∗,T∗,σ∗.
We say F2P-ABS ist,qatt,qsk,qsig,ε-EUF-CPMA secure if, for any probabilistic polynomial-time adversary A running in time at most t that makes at most qatt attribute queries, qsk key extracting queries, and qsig signing queries, the A’s advantage AdvAEUF−CPMA is at most ε.


## 5. F2P-ABS Main Construction

In this section, the main construction of F2P-ABS and the details of how our F2P-ABS proceeds among the AA, the DSC, the singer, and the verifier are presented.


### 5.1. Global Setup

To initialize the system, the AA first calls theGSetup algorithm. It can be noted that the GSetup algorithm can be run by any other trusted party ahead of system initialization. It takes a security parameter λ as input and proceeds the following steps:(1)
It selects a cyclic groupG of λ-bit prime order p with generator g(2)
It generates an attribute universeΩ=att1,att2,…,attn, which is a large universe that contains attributes of all authorized users(3)
It selects a hash functionH:0,1∗⟶Zp∗(4)
Outputs the parametergparam=p,G,g,Ω,H


### 5.2. DSC Setup

It is also necessary for the DSC to participate in the system initialization. After the global setup, the DSC callsDSetup algorithm with gparam and runs the following steps:(1)
It selectsα1,α2⟵RZp∗ and computes A1=gα1 and A2=gα2(2)
For each attributeatti∈Ω, it selects ε1,i,ε2,i⟵RZp∗ and computes T1,i=gε1,i and T2,i=gε2,i(3)
It generates a garbled circuitGCf of the function fx1,x2,y1,y2=x1+y1/x2+y2(4)
It published the DSC parameterdparam=A1,A2,C,∀atti∈Ω:T1,i,T2,i and stores the DSC secret key dsk=α1,α2,∀atti∈Ω:ε1,i,ε2,i


### 5.3. AA Setup

As the final procedure of system initialization, the AA calls theASetup algorithm which takes gparam as input. Then, it runs the following steps:(1)
It selectsβ1,β2⟵RZp∗ and computes B1=gβ1 and B2=gβ2(2)
For eachatti∈Zp∗, it selects γ1,i,γ2,i⟵RZp∗ and computes U1,i=gγ1,i and U2,i=gγ2,i(3)
It publishes the AA parameteraparam=B1,B2,∀atti∈Ω:U1,i,U2,i and stores the AA secret key ask=β1,β2,∀atti∈Ω:γ1,i,γ2,i


### 5.4. Key Extraction

When the signer asks for authorization with an attribute setS, the AA and the DSC jointly calls the KeyExtract algorithm, which takes as input gparam, dparam, aparam, dsk, ask, and the attribute set S. The execution of the KeyExtract algorithm is as follows:(1)
The AA selectsr⟵RZp∗(2)
D1α1,α2,β1+r,β2 is generated by using GCf between the AA and the DSC(3)
For eachatti∈Ω, D2,i=fε1,i,ε2,i,γ1,i−r,γ2,i is generated by using GCf between the AA and the DSC(4)
The signing keysk=S,D1,∀atti∈S:D2,i returns to the signer


### 5.5. Signing

To sign a messagem with predicate T, the signer calls the Sign algorithm. It takes as input the predicate T, the message m, and the signing key sk. Then, it proceeds as follows:(1)
It randomly selects a secrets⟵RZp∗ and then assigns a random polynomial for each node x of T as follows:(1)
If nodex is the root node and its threshold is kroot, set a random droot-degree polynomial qroot such that qroot0=s, where droot=kroot−1.(2)
If nodex is neither the root node nor a leaf node and its threshold is kx, set a random dx-degree polynomial qx such that qx0=qparentxx, where dx=kx−1.(3)
If nodex is a leaf node, set a zero-degree polynomial qx=qparentxx.(2)
It selects another secrets′⟵RZp∗ and assigns another polynomial for each node x of T as follows:(1)
If nodex is the root node, set a random 2-degree polynomial qroot′ such that qroot′0=s′.(2)
If nodex is neither the root node nor a leaf node, set a random 2-degree polynomial qx′ such that qx′0=qparentx′x.(3)
If nodex is a leaf node, set a 0-degree polynomial qx′=qparentx′x.(3)
The signer chooses a minimum attribute setSmin. For each leaf node x in T such that attx=atti, the following computation will be executed:(1)
IfTxSmin=1, compute σ1,x=T1,iU1,iqx0 and σ2,x=D2,iqx0.(2)
IfTxSmin=0, compute σ1,x=T1,iU1,iqx′0 and σ2,x=D2,iqx′0.(4)
Finally, it computesσ3=D1s+s′ and σ4=HA1B1s+s′m and the signature is presented as σ=T,σ1,x,σ2,x,σ3,σ4.LetΛx denote the set of the all child nodes of node x. Let Λ′x denote the set of some child nodes of node x such that Smin cannot satisfy the predicate rooted at them, namely, Λ′x=z∣z∈Λx∩​TzSmin=0. For F2P-ABS, there is only one restriction on predicate T which is Λ′x≥2.


### 5.6. Verifying

To validate this message, the verifier calls for theVerify algorithm. It takes as input the message m and the corresponding signature σ. Then, it proceeds as follows:(1)
For each nodex of T, it recursively calls the function VerifyNodex.(1)
Ifx is a leaf node, it computes as equation (1). For generality, we define that, for each node x such that TxSmin=1, it has a qz′0=0.(1)VerifyNodex=T2,iU2,iσ2,xσ1,x=g−rqx0+qx′0,ifTxSmin=1,g−rqx′0,ifTxSmin=0.(2)
Ifx is a nonleaf node, we denote the computation result of its arbitrary child node z by Fz. Then, it computes as equation (2). It is assured that the result g−rs+s′ of the root node can be computed with finite recursion, if TS=1 holds:(2)VerifyNodex=∏z∈ΛxFzΔz,Λx0=∏z∈Λx,TzSmin=1g−rqz0+qz′0⋅∏z∈Λx,TzSmin=0g−rqz′0=g−rqx0+qz′0,ifTxSmin=1,g−rqz′0,ifTxSmin=0.(2)
It computesZ=HA2B2σ3g−rs+s′m and output 1 if Z=σ4 holds. That is, the message is indeed from a legal signer. Otherwise, it outputs 0 to indicate the signature is invalid.


## 5.1. Global Setup

To initialize the system, the AA first calls theGSetup algorithm. It can be noted that the GSetup algorithm can be run by any other trusted party ahead of system initialization. It takes a security parameter λ as input and proceeds the following steps:(1)
It selects a cyclic groupG of λ-bit prime order p with generator g(2)
It generates an attribute universeΩ=att1,att2,…,attn, which is a large universe that contains attributes of all authorized users(3)
It selects a hash functionH:0,1∗⟶Zp∗(4)
Outputs the parametergparam=p,G,g,Ω,H


## 5.2. DSC Setup

It is also necessary for the DSC to participate in the system initialization. After the global setup, the DSC callsDSetup algorithm with gparam and runs the following steps:(1)
It selectsα1,α2⟵RZp∗ and computes A1=gα1 and A2=gα2(2)
For each attributeatti∈Ω, it selects ε1,i,ε2,i⟵RZp∗ and computes T1,i=gε1,i and T2,i=gε2,i(3)
It generates a garbled circuitGCf of the function fx1,x2,y1,y2=x1+y1/x2+y2(4)
It published the DSC parameterdparam=A1,A2,C,∀atti∈Ω:T1,i,T2,i and stores the DSC secret key dsk=α1,α2,∀atti∈Ω:ε1,i,ε2,i


## 5.3. AA Setup

As the final procedure of system initialization, the AA calls theASetup algorithm which takes gparam as input. Then, it runs the following steps:(1)
It selectsβ1,β2⟵RZp∗ and computes B1=gβ1 and B2=gβ2(2)
For eachatti∈Zp∗, it selects γ1,i,γ2,i⟵RZp∗ and computes U1,i=gγ1,i and U2,i=gγ2,i(3)
It publishes the AA parameteraparam=B1,B2,∀atti∈Ω:U1,i,U2,i and stores the AA secret key ask=β1,β2,∀atti∈Ω:γ1,i,γ2,i


## 5.4. Key Extraction

When the signer asks for authorization with an attribute setS, the AA and the DSC jointly calls the KeyExtract algorithm, which takes as input gparam, dparam, aparam, dsk, ask, and the attribute set S. The execution of the KeyExtract algorithm is as follows:(1)
The AA selectsr⟵RZp∗(2)
D1α1,α2,β1+r,β2 is generated by using GCf between the AA and the DSC(3)
For eachatti∈Ω, D2,i=fε1,i,ε2,i,γ1,i−r,γ2,i is generated by using GCf between the AA and the DSC(4)
The signing keysk=S,D1,∀atti∈S:D2,i returns to the signer


## 5.5. Signing

To sign a messagem with predicate T, the signer calls the Sign algorithm. It takes as input the predicate T, the message m, and the signing key sk. Then, it proceeds as follows:(1)
It randomly selects a secrets⟵RZp∗ and then assigns a random polynomial for each node x of T as follows:(1)
If nodex is the root node and its threshold is kroot, set a random droot-degree polynomial qroot such that qroot0=s, where droot=kroot−1.(2)
If nodex is neither the root node nor a leaf node and its threshold is kx, set a random dx-degree polynomial qx such that qx0=qparentxx, where dx=kx−1.(3)
If nodex is a leaf node, set a zero-degree polynomial qx=qparentxx.(2)
It selects another secrets′⟵RZp∗ and assigns another polynomial for each node x of T as follows:(1)
If nodex is the root node, set a random 2-degree polynomial qroot′ such that qroot′0=s′.(2)
If nodex is neither the root node nor a leaf node, set a random 2-degree polynomial qx′ such that qx′0=qparentx′x.(3)
If nodex is a leaf node, set a 0-degree polynomial qx′=qparentx′x.(3)
The signer chooses a minimum attribute setSmin. For each leaf node x in T such that attx=atti, the following computation will be executed:(1)
IfTxSmin=1, compute σ1,x=T1,iU1,iqx0 and σ2,x=D2,iqx0.(2)
IfTxSmin=0, compute σ1,x=T1,iU1,iqx′0 and σ2,x=D2,iqx′0.(4)
Finally, it computesσ3=D1s+s′ and σ4=HA1B1s+s′m and the signature is presented as σ=T,σ1,x,σ2,x,σ3,σ4.LetΛx denote the set of the all child nodes of node x. Let Λ′x denote the set of some child nodes of node x such that Smin cannot satisfy the predicate rooted at them, namely, Λ′x=z∣z∈Λx∩​TzSmin=0. For F2P-ABS, there is only one restriction on predicate T which is Λ′x≥2.


## 5.6. Verifying

To validate this message, the verifier calls for theVerify algorithm. It takes as input the message m and the corresponding signature σ. Then, it proceeds as follows:(1)
For each nodex of T, it recursively calls the function VerifyNodex.(1)
Ifx is a leaf node, it computes as equation (1). For generality, we define that, for each node x such that TxSmin=1, it has a qz′0=0.(1)VerifyNodex=T2,iU2,iσ2,xσ1,x=g−rqx0+qx′0,ifTxSmin=1,g−rqx′0,ifTxSmin=0.(2)
Ifx is a nonleaf node, we denote the computation result of its arbitrary child node z by Fz. Then, it computes as equation (2). It is assured that the result g−rs+s′ of the root node can be computed with finite recursion, if TS=1 holds:(2)VerifyNodex=∏z∈ΛxFzΔz,Λx0=∏z∈Λx,TzSmin=1g−rqz0+qz′0⋅∏z∈Λx,TzSmin=0g−rqz′0=g−rqx0+qz′0,ifTxSmin=1,g−rqz′0,ifTxSmin=0.(2)
It computesZ=HA2B2σ3g−rs+s′m and output 1 if Z=σ4 holds. That is, the message is indeed from a legal signer. Otherwise, it outputs 0 to indicate the signature is invalid.


## 6. Security Analysis

In this section, we will discuss how our F2P-ABS meets the security requirements mentioned in previous section.


### 6.1. Correctness

Theorem 1.
F2P-ABS guarantees correctness.Proof.
Considering theVerify algorithm, the result g−rqroot0+qroot′0=g−rs+s′ of the root node can be computed with finite recursion if TS=1 holds. If the message is integrated, accordingly, equation (3) will always hold:(3)HA2B2σ3g−rs+s′m=Hgα2gβ2α1+β1+r/α2+β2s+s′g−rs+s′m=Hgα1+β1+rg−rs+s′m=Hgα1+β1s+s′m=σ4.
In this case, theVerify algorithm outputs 1 with success probability 1.


### 6.2. Perfect Signer Privacy

Theorem 2.
F2P-ABS guarantees perfect signer privacy.Proof.
Considering theSign algorithm, the following assertion always holds:(1)
Since the secret numberss and s′ are randomly selected, both σ3=D1s+s′ and σ4=HA1B1s+s′m are uniformly distributed in Zp∗(2)
For an arbitrary leaf nodex such that TxSmin=1, we have σ1,x=T1,iU1,iqx0 and σ2,x=D2,iqx0, which are uniformly distributed in G because qx0 is from a random polynomial(3)
For an arbitrary leaf nodex such that TxSmin=0, we have σ1,x=T1,iU1,iqx′0 and σ2,x=D2,iqx′0, which are also uniformly distributed in G because qx′0 is also from a random polynomial
Therefore, for allgparam⟵GSetup1λ, all dparam,dsk⟵DSetupgparam, all aparam,ask⟵ASetupgparam, all messages m, all attribute sets S1 and S2, all signing keys sk1⟵KeyExtractgparam,dparam,aparam,ask,dsk,S1 and sk2⟵KeyExtractgparam,dparam,aparam,ask,dsk,S2, all predicates T such that TS1=1 and TS2=1, and the distributions of σ1⟵Signgparam,dparam,aparam,sk1,T,m and σ2⟵Signgparam,dparam,aparam,sk2,T,m are equal.


### 6.3. Existential Unforgeability

Theorem 3.
F2P-ABS is EUF-ca-CPMA secure in the random oracle assuming the hardness of DL problem.Proof.
Suppose there exists an adversaryA that can break F2P-ABS by chosen predicate and message attacks. We can build a simulator ℬ that can solve DL problem in a challenge game. The challenge game proceeds as follows:(1)
Initial Phase. A sends a challenge bit c0∈0,1 to ℬ.(2)
Setup Phase. The challenger C generates g1∈G and sends g and g1 to ℬ. Then, a group of parameters are generated by ℬ as follows:(1)
ℬ selects a random oracle H:0,1∗⟶Zp∗ and sends p, G, g, and H to A.(2)
ℬ randomly selects α1,α2∈Zp∗ and computes A1=gα1 and A2=gα2. Then, it checks c0 and sends α1 and α2 to A if c0=1. Otherwise, it sends A1 and A2.(3)
ℬ randomly selects β1,β2∈Zp∗ and computes B1=gβ1 and B2=gβ2. Then, it checks c0 and sends β1 and β2 to A if c0=0. Otherwise, it sends B1 and B2 to A.(3)
Query Phase. A adaptively issues a polynomially bounded number of queries to the following oracles:(1)
Attribute Oracle. ℬ maintains a list Latt=atti,ε1,i,ε2,i,γ1,i,γ2,i,T1,i,T2,i,U1,i,U2,i and scans it when A makes a query for parameter associated with an attribute atti. It returns the corresponding T1,i, T2,i, U1,i, and U2,i if atti is in Latt. Otherwise, it randomly chooses ε1,i,ε2,i,γ1,i,γ2,i∈Zp∗ and c1∈0,1 under the Bernoulli distribution with θ∈0,1, that is, Prc1=0=θ and Prc1=1=1−θ. If c1=0, ℬ computes T1,i=gε1,i, T2,i=gε2,i, U1,i=gγ1,i, and U2,i=gγ2,i. Otherwise, it computes T1,i=g1ε1,i, T2,i=g1ε2,i, U1,i=g1γ1,i, and U1,i=g1γ1,i. Then, ℬ checks c0 and sends ε1,i, ε2,i, U1,i, and U2,i to A. Otherwise, it sends T1,i, T2,i, γ1,i, and γ2,i to A. Finally, it adds the new tuple atti,ε1,i,ε2,i,γ1,i,γ2,i,T1,i,T2,i,U1,i,U2,i into Latt.(2)
Key Extracting Oracle. ℬ maintains a list Lsk=S,r,D1,∀atti∈S:D2,i and scans Latt when A issues a query to the key extracting oracle with an attribute set S. ℬ will abort the game if there exists an attribute atti that is not in Latt because it is unable to coherently answer the query. We denote this abortion by E1. If not, ℬ scans Lsk and returns S,r,D1,∀atti∈S:D2,i if S is in Lsk. Otherwise, ℬ randomly selects r,R∈Zp∗ and computes D=R and D2,i=ε1,i+γ1,i−r/ε2,i+γ2,i for each attribute atti in S. Then, ℬ returns S,D1,∀atti∈S:D2,i to A if c0=0, otherwise, returns S,r,D1,∀atti∈S:D2,i to A. Finally, ℬ adds the new tuple S,r,D1,∀atti∈S:D2,i into Lsk.(3)
Signing Oracle. ℬ maintains a list Lsig=m,T,s,s′,σ1,x,σ2,x,σ3,σ4 and scans Latt when A makes a signing query on a message m with predicate T. The game will be aborted if there exists an attribute atti of T that is not in Latt. We denote this abortion by E2. Otherwise, ℬ checks c1 for each attribute of T. The game will be aborted, which is denoted by E3, if there exists an attribute atti such that c1=1. If not, ℬ generates a random attribute set S and runs the key extracting oracle to obtain S,D1,∀atti∈S:D2,i. Then, it computes σ1,x=T1,iU1,iqx0 and σ2,x=D2,iqx0 for each leaf node x, where qx0 is generated as the real Sign algorithm. Then, it randomly chooses s,s′∈Zp∗ to compute σ3=Rs+s′ and Z=A1B1s+s′. Meanwhile, σ4=HA1B1s+s′m is computed by the random oracle H. Finally, ℬ adds the new tuple m,T,s,s′,σ1,x,σ2,x,σ3,σ4 into Lsig and sends T,σ1,x,σ2,x,σ3,σ4 to A.(4)
Forge Phase. A forges a signature σ∗=T∗,σ1,x∗,σ2,x∗,σ3∗,σ4∗ of message m∗. ℬ will abort the game if there exist attributes of T∗ that is not in Latt. We denote this abortion by E4. Otherwise, ℬ checks c1 for each attribute that every leaf node is associated with. If there exists a c1=0, ℬ will abort the game. We denote this abortion by E5. If not, ℬ runs the verifying oracles as follows:(1)
Ifx is a leaf node, it runs VerifyNodex as(4)VerifyNodex=T2,iU2,iσ2,x∗σ1,x∗=g1−rqx0+qx′0,ifTx∗Smin=1,g1−rqx′0,ifTx∗Smin=0..(2)
Ifx is a nonleaf node, we denote the computation result of its arbitrary child node z by Fz. It runs VerifyNodex as equation (5). By those finite recursions, ℬ can validate the forged signature as the real F2P-ABS. We say A wins the game if Z=σ4∗. In this case, ℬ chooses a tuple m,T,s,s′,σ1,x,σ2,x,σ3,σ4 from Lsig and a tuple S,r,D1,∀atti∈S:D2,i and finally returns α1+β1+r/σ3∗α2+β2 to C as the answer to DL problem:(5)VerifyNodex=∏z∈ΛxFzΔz,Λx0=∏z∈Λx,TzSmin=1g1−rqz0+qz′0⋅∏z∈Λx,TzSmin=0g1−rqz′0=g−rqx0+qx′0,ifTx∗Smin=1,g−rqx′0,ifTx∗Smin=0.Lemma 1.
IfE1, E2, and E3 do not happen, all results output by ℬ in the query phase are valid and indistinguishable.Lemma1 holds because(1)
For any query to the attribute oracle with an attributeatti, ℬ selects random ε1,i,ε2,i,γ1,i,γ2,i∈Zp∗ and a random c1∈0,1. No matter what the value of c1 is, A will be obtained. We note that ε1,i,ε2,i,U1,i,andU2,i are all randomly chosen, which are valid and indistinguishable from those generated by the real F2P-ABS. Likewise, A will obtain T1,i,T2,i,γ1,i,andγ2,i if c0=1, and those are also randomly chosen and indistinguishable.(2)
For any query to the key extracting oracle,ℬ selects two random numbers r,R∈Zp∗ if E1 does not happen. It generates a tuple S,D1,∀atti∈S:D2,i where D1=R and D2,i=ε1,i+γ1,i−r/ε2,i+γ2,i. If c0=0, there always exist β1′,β2′,r′,γ1,i′,γ2,i′∈Zp∗ such that D1=α1+β1′+r′/α2+β2′ and D2,i=ε1,i+γ1,i′−r′/ε2,i+γ2,i′. If c0=1, there always exist α1′,α2′,ε1,i′,ε2,i′∈Zp∗ such that D1=α1′+β1+r/α2′+β2 and D2,i=ε1,i′+γ1,i−r/ε2,i′+γ2,i. Therefore, the output is valid and indistinguishable from real singing keys.(3)
For any query to the signing oracle, each leaf node of predicate has a corresponding attribute inLatt if E2 does not happen. And, if E3 does not happen, ℬ will generate a tuple S,D1,∀atti∈S:D2,i. Then, it computes the tuple T,σ1,x,σ2,x,σ3,σ4 in a way of the real F2P-ABS. So, the output of the signing oracle is valid and indistinguishable from real signatures.Lemma 2.
IfE4 and E5 do not happen, ℬ can probably solve DLP when A successfully breaks the F2P-ABS.Lemma2 holds because if E4 and E5 do not happen, each atti has corresponding T1,i=g1ε1,i, T2,i=g1ε2,i, U1,i=g1γ1,i, and U2,i=g1γ2,i in Latt. In this case, ℬ can output the answer to the DL problem if it finds the proper r in Lsk and proper s and s′ in Lsig.SupposeA makes at most qatt queries to the attribute oracle, qsk queries to the key extracting oracle and qsig queries to the signing oracle. Let t be the time required for A to break F2P-ABS. Let ta and tm be the time required for one-time addition and scalar multiplication operation, respectively, in Zp∗. Let te be the time required for one-time exponentiation in G. The total time t′ required for ℬ to solve DL problem satisfies(6)t′≤t+3qsk+qsigta+qsk+n+1qsigtm+4qatt+n+1qsigte.The probability thatE1, E2, and E4 do not happen is PrE1¯∧E2¯∧E4¯=qatt/2lnqsk+nqsig+1. The probability that E3 and E5 do not happen is PrE3¯∧E5¯=θnqsk1−θn which achieves its upper bound when θ=nqsk/1+nqsk. That is, PrE3¯∧E5¯≤nqsk/1+nqsknqsk1/1+nqskn. Considering all situations mentioned above, the advantage ε′ of ℬ to solve DL problem satisfies(7)ε′≤qatt2lnqsk+nqsig+1nqsk1+nqsknqsk11+nqsknε.


## 6.1. Correctness

Theorem 1.
F2P-ABS guarantees correctness.Proof.
Considering theVerify algorithm, the result g−rqroot0+qroot′0=g−rs+s′ of the root node can be computed with finite recursion if TS=1 holds. If the message is integrated, accordingly, equation (3) will always hold:(3)HA2B2σ3g−rs+s′m=Hgα2gβ2α1+β1+r/α2+β2s+s′g−rs+s′m=Hgα1+β1+rg−rs+s′m=Hgα1+β1s+s′m=σ4.
In this case, theVerify algorithm outputs 1 with success probability 1.


## 6.2. Perfect Signer Privacy

Theorem 2.
F2P-ABS guarantees perfect signer privacy.Proof.
Considering theSign algorithm, the following assertion always holds:(1)
Since the secret numberss and s′ are randomly selected, both σ3=D1s+s′ and σ4=HA1B1s+s′m are uniformly distributed in Zp∗(2)
For an arbitrary leaf nodex such that TxSmin=1, we have σ1,x=T1,iU1,iqx0 and σ2,x=D2,iqx0, which are uniformly distributed in G because qx0 is from a random polynomial(3)
For an arbitrary leaf nodex such that TxSmin=0, we have σ1,x=T1,iU1,iqx′0 and σ2,x=D2,iqx′0, which are also uniformly distributed in G because qx′0 is also from a random polynomial
Therefore, for allgparam⟵GSetup1λ, all dparam,dsk⟵DSetupgparam, all aparam,ask⟵ASetupgparam, all messages m, all attribute sets S1 and S2, all signing keys sk1⟵KeyExtractgparam,dparam,aparam,ask,dsk,S1 and sk2⟵KeyExtractgparam,dparam,aparam,ask,dsk,S2, all predicates T such that TS1=1 and TS2=1, and the distributions of σ1⟵Signgparam,dparam,aparam,sk1,T,m and σ2⟵Signgparam,dparam,aparam,sk2,T,m are equal.


## 6.3. Existential Unforgeability

Theorem 3.
F2P-ABS is EUF-ca-CPMA secure in the random oracle assuming the hardness of DL problem.Proof.
Suppose there exists an adversaryA that can break F2P-ABS by chosen predicate and message attacks. We can build a simulator ℬ that can solve DL problem in a challenge game. The challenge game proceeds as follows:(1)
Initial Phase. A sends a challenge bit c0∈0,1 to ℬ.(2)
Setup Phase. The challenger C generates g1∈G and sends g and g1 to ℬ. Then, a group of parameters are generated by ℬ as follows:(1)
ℬ selects a random oracle H:0,1∗⟶Zp∗ and sends p, G, g, and H to A.(2)
ℬ randomly selects α1,α2∈Zp∗ and computes A1=gα1 and A2=gα2. Then, it checks c0 and sends α1 and α2 to A if c0=1. Otherwise, it sends A1 and A2.(3)
ℬ randomly selects β1,β2∈Zp∗ and computes B1=gβ1 and B2=gβ2. Then, it checks c0 and sends β1 and β2 to A if c0=0. Otherwise, it sends B1 and B2 to A.(3)
Query Phase. A adaptively issues a polynomially bounded number of queries to the following oracles:(1)
Attribute Oracle. ℬ maintains a list Latt=atti,ε1,i,ε2,i,γ1,i,γ2,i,T1,i,T2,i,U1,i,U2,i and scans it when A makes a query for parameter associated with an attribute atti. It returns the corresponding T1,i, T2,i, U1,i, and U2,i if atti is in Latt. Otherwise, it randomly chooses ε1,i,ε2,i,γ1,i,γ2,i∈Zp∗ and c1∈0,1 under the Bernoulli distribution with θ∈0,1, that is, Prc1=0=θ and Prc1=1=1−θ. If c1=0, ℬ computes T1,i=gε1,i, T2,i=gε2,i, U1,i=gγ1,i, and U2,i=gγ2,i. Otherwise, it computes T1,i=g1ε1,i, T2,i=g1ε2,i, U1,i=g1γ1,i, and U1,i=g1γ1,i. Then, ℬ checks c0 and sends ε1,i, ε2,i, U1,i, and U2,i to A. Otherwise, it sends T1,i, T2,i, γ1,i, and γ2,i to A. Finally, it adds the new tuple atti,ε1,i,ε2,i,γ1,i,γ2,i,T1,i,T2,i,U1,i,U2,i into Latt.(2)
Key Extracting Oracle. ℬ maintains a list Lsk=S,r,D1,∀atti∈S:D2,i and scans Latt when A issues a query to the key extracting oracle with an attribute set S. ℬ will abort the game if there exists an attribute atti that is not in Latt because it is unable to coherently answer the query. We denote this abortion by E1. If not, ℬ scans Lsk and returns S,r,D1,∀atti∈S:D2,i if S is in Lsk. Otherwise, ℬ randomly selects r,R∈Zp∗ and computes D=R and D2,i=ε1,i+γ1,i−r/ε2,i+γ2,i for each attribute atti in S. Then, ℬ returns S,D1,∀atti∈S:D2,i to A if c0=0, otherwise, returns S,r,D1,∀atti∈S:D2,i to A. Finally, ℬ adds the new tuple S,r,D1,∀atti∈S:D2,i into Lsk.(3)
Signing Oracle. ℬ maintains a list Lsig=m,T,s,s′,σ1,x,σ2,x,σ3,σ4 and scans Latt when A makes a signing query on a message m with predicate T. The game will be aborted if there exists an attribute atti of T that is not in Latt. We denote this abortion by E2. Otherwise, ℬ checks c1 for each attribute of T. The game will be aborted, which is denoted by E3, if there exists an attribute atti such that c1=1. If not, ℬ generates a random attribute set S and runs the key extracting oracle to obtain S,D1,∀atti∈S:D2,i. Then, it computes σ1,x=T1,iU1,iqx0 and σ2,x=D2,iqx0 for each leaf node x, where qx0 is generated as the real Sign algorithm. Then, it randomly chooses s,s′∈Zp∗ to compute σ3=Rs+s′ and Z=A1B1s+s′. Meanwhile, σ4=HA1B1s+s′m is computed by the random oracle H. Finally, ℬ adds the new tuple m,T,s,s′,σ1,x,σ2,x,σ3,σ4 into Lsig and sends T,σ1,x,σ2,x,σ3,σ4 to A.(4)
Forge Phase. A forges a signature σ∗=T∗,σ1,x∗,σ2,x∗,σ3∗,σ4∗ of message m∗. ℬ will abort the game if there exist attributes of T∗ that is not in Latt. We denote this abortion by E4. Otherwise, ℬ checks c1 for each attribute that every leaf node is associated with. If there exists a c1=0, ℬ will abort the game. We denote this abortion by E5. If not, ℬ runs the verifying oracles as follows:(1)
Ifx is a leaf node, it runs VerifyNodex as(4)VerifyNodex=T2,iU2,iσ2,x∗σ1,x∗=g1−rqx0+qx′0,ifTx∗Smin=1,g1−rqx′0,ifTx∗Smin=0..(2)
Ifx is a nonleaf node, we denote the computation result of its arbitrary child node z by Fz. It runs VerifyNodex as equation (5). By those finite recursions, ℬ can validate the forged signature as the real F2P-ABS. We say A wins the game if Z=σ4∗. In this case, ℬ chooses a tuple m,T,s,s′,σ1,x,σ2,x,σ3,σ4 from Lsig and a tuple S,r,D1,∀atti∈S:D2,i and finally returns α1+β1+r/σ3∗α2+β2 to C as the answer to DL problem:(5)VerifyNodex=∏z∈ΛxFzΔz,Λx0=∏z∈Λx,TzSmin=1g1−rqz0+qz′0⋅∏z∈Λx,TzSmin=0g1−rqz′0=g−rqx0+qx′0,ifTx∗Smin=1,g−rqx′0,ifTx∗Smin=0.Lemma 1.
IfE1, E2, and E3 do not happen, all results output by ℬ in the query phase are valid and indistinguishable.Lemma1 holds because(1)
For any query to the attribute oracle with an attributeatti, ℬ selects random ε1,i,ε2,i,γ1,i,γ2,i∈Zp∗ and a random c1∈0,1. No matter what the value of c1 is, A will be obtained. We note that ε1,i,ε2,i,U1,i,andU2,i are all randomly chosen, which are valid and indistinguishable from those generated by the real F2P-ABS. Likewise, A will obtain T1,i,T2,i,γ1,i,andγ2,i if c0=1, and those are also randomly chosen and indistinguishable.(2)
For any query to the key extracting oracle,ℬ selects two random numbers r,R∈Zp∗ if E1 does not happen. It generates a tuple S,D1,∀atti∈S:D2,i where D1=R and D2,i=ε1,i+γ1,i−r/ε2,i+γ2,i. If c0=0, there always exist β1′,β2′,r′,γ1,i′,γ2,i′∈Zp∗ such that D1=α1+β1′+r′/α2+β2′ and D2,i=ε1,i+γ1,i′−r′/ε2,i+γ2,i′. If c0=1, there always exist α1′,α2′,ε1,i′,ε2,i′∈Zp∗ such that D1=α1′+β1+r/α2′+β2 and D2,i=ε1,i′+γ1,i−r/ε2,i′+γ2,i. Therefore, the output is valid and indistinguishable from real singing keys.(3)
For any query to the signing oracle, each leaf node of predicate has a corresponding attribute inLatt if E2 does not happen. And, if E3 does not happen, ℬ will generate a tuple S,D1,∀atti∈S:D2,i. Then, it computes the tuple T,σ1,x,σ2,x,σ3,σ4 in a way of the real F2P-ABS. So, the output of the signing oracle is valid and indistinguishable from real signatures.Lemma 2.
IfE4 and E5 do not happen, ℬ can probably solve DLP when A successfully breaks the F2P-ABS.Lemma2 holds because if E4 and E5 do not happen, each atti has corresponding T1,i=g1ε1,i, T2,i=g1ε2,i, U1,i=g1γ1,i, and U2,i=g1γ2,i in Latt. In this case, ℬ can output the answer to the DL problem if it finds the proper r in Lsk and proper s and s′ in Lsig.SupposeA makes at most qatt queries to the attribute oracle, qsk queries to the key extracting oracle and qsig queries to the signing oracle. Let t be the time required for A to break F2P-ABS. Let ta and tm be the time required for one-time addition and scalar multiplication operation, respectively, in Zp∗. Let te be the time required for one-time exponentiation in G. The total time t′ required for ℬ to solve DL problem satisfies(6)t′≤t+3qsk+qsigta+qsk+n+1qsigtm+4qatt+n+1qsigte.The probability thatE1, E2, and E4 do not happen is PrE1¯∧E2¯∧E4¯=qatt/2lnqsk+nqsig+1. The probability that E3 and E5 do not happen is PrE3¯∧E5¯=θnqsk1−θn which achieves its upper bound when θ=nqsk/1+nqsk. That is, PrE3¯∧E5¯≤nqsk/1+nqsknqsk1/1+nqskn. Considering all situations mentioned above, the advantage ε′ of ℬ to solve DL problem satisfies(7)ε′≤qatt2lnqsk+nqsig+1nqsk1+nqsknqsk11+nqsknε.


## 7. Performance Analysis

In this section, we analyze the performance of our F2P-ABS scheme against current ABS schemes [24–27] in Tables 2 and 3 in terms of public parameter size, secret key size and signing key size, signature size, and computation overhead (number of required exponentiation and pairing computation, which are time-consuming operations). For clarity, we list some essential notations for analysis in Table 5.Table 5
Notations.
Notation
Definition
a
u
Size of the attribute universe
a
s
k
Size of the signer attribute set
a
s
p (aep)
Size of the signing (encrypting) predicate
n
e
p
Number of nonleaf nodes of a signing predicate
ϕ
s
p (ϕep)
Size of the minimum signing (encrypting) attribute set
k
Number of attribute authorities
G (|GT|)
bit size of an element of a groupG (GT)
Z
p
∗
bit size of an element of a groupZp∗
Param.
Size of the public parameter
Sec.
Size of the secret key
Sig.
Size of the signature
Exp.
Number of exponentiation operations
Pair.
Number of pairing operationsAs is shown in Table2, the size of the public parameter in [25] increases fast with the square of the number k of authorities, which is less practical for initializing the system. The size of public parameter in [26, 27] is linear to the size of attribute universe. To mitigate key escrow problem, we assign part of public parameters to the AA and the DSC, respectively. As a result, our F2P-ABS has a group of public parameters two times the size of that in [26, 27]. The secret key in F2P-ABS has 2au+4 group elements, which is linear to the size of attribute universe. Although F2P-ABS has big-sized public parameters and secret key, it hardly causes performance dilemma considering significant storage capacity of the AA and the DSC.We achieve a short signing key size compared to existing schemes [24–27]. The signing key size in [26] is linear to the size of attribute universe, which is a huge challenge to the storage capacity of signer when large numbers of attributes are engaged. The signing key of F2P-ABS consists of ask+1 group elements, while that for [24, 25] is 2ask+1. Meanwhile, signing key in [27] consists of 2ask+3 group elements. Hence, we successfully reduce the number of group elements in signing key by half. The signature of F2P-ABS totally has 2asp+2 group elements, which is slightly less than that for [27].Since pairing computation is considered the most expensive operation, number of pairing operations is a critical factor of feasibility in practical scenes. We note that there is a signcryption in [27], which is a mixture of ABE and ABS. It requires asp+3 pairings for verification and 2 pairings to recover the message plaintext. The number of pairings in [24, 25] is also linear to the size of the minimum signing attribute set and the size of signing predicate, respectively. As clearly seen in Table 3, F2P-ABS requires no pairing for verification. This is even less than that for [26], which is 3 pairing operations. In addition, it achieves light computation at the cost of large signing key size being linear to the size attribute universe. It is worth noting that garbled circuit operations become the only performance bottleneck of F2P-ABS. Although we are unsatisfied with existing garbled circuit implementation, we believe there will be better ones in future which help to achieve better performance in practical scenes. Hence, F2P-ABS is efficient from computation point of view.To sum up, our F2P-ABS achieves a better performance, in terms of signing key size, signature size, and computation cost, than existing schemes. Furthermore, it achieves other desirable goals such as expressive predicate, authenticity, and signer privacy.


## 8. Conclusion

ABS is a promising cryptographic primitive for anonymous authentication. However, existing ABS approaches have drawbacks with respect to security and efficiency, which hinders their application for authentication in mobile platforms. We focus on constructing an ABS scheme that is elegantly free from key escrow problem and heavy pairing operations. In addition, the size of the signing key is much less than existing schemes. Without the loss of security, it achieves perfect signer privacy. It is proven to guarantee existential unforgeability under corrupted and adaptive chosen predicate and message attack, which is securer than existing schemes. Therefore, it outperforms existing schemes and shows more feasibility for anonymous authentication in mobile platforms.To further its application, we are exploiting a new method to enhance efficiency. Considering its performance bottleneck, our future work will build on the preliminary construction in this work to develop the proposed scheme by improving the performance of garbled circuit operations.



---

*Source: 5380710-2019-12-19.xml*