Fully adaptive MA-ABE supporting multi-fan-in circuits

Abstract

As a distributed extension of ciphertext-policy attribute-based encryption (CP-ABE), multi-authority ABE (MA-ABE) does not require the participation of a trusted central authority and has a wider application prospect in the decentralized background of the cloud computing environment. We propose the first MA-ABE scheme supporting multi-fan-in circuits and collusion-resistance on prime-order bilinear groups and prove the fully adaptive security based on the matrix decision Diffie-Hellman (MDDH) assumption. Compared with the only two fully adaptively secure MA-ABE schemes, our scheme enjoys shorter parameters, which has lower ciphertext and key size, and supports many-use of attribute.

Keywords

multi-authority attribute-based encryption multi-fan-in circuit dual system encryption fully adaptive security

1. Introduction

With the development of cloud computing, an increasing number of users and enterprises choose to store data in the cloud to enjoy dynamic and scalable storage services. At present, encryption is an effective means of protecting data confidentiality, but traditional encryption mechanisms cannot implement flexible and fine-grained access control while ensuring data confidentiality.

In 2005, Sahai and Waters¹ introduced the concept of attribute-based encryption (ABE) to solve this problem. In 2006, Goyal et al.² proposed the first real ABE scheme for fine-grained access control. As an advanced public key encryption primitive, ABE can achieve fine-grained access control for encrypted data. But there is a major limitation in the standard ABE scheme, that is, each user must prove to the unique authority that he or she possesses certain attributes, such as driver’s licenses and enrollment school numbers, to obtain the keys corresponding to these attributes, which means that the authority must be trusted. However, different authorities are responsible for issuing and maintaining different attributes in reality. To solve the above problem, Chase³ introduced a multi-authority attribute-based encryption (MA-ABE) scheme. In MA-ABE, multiple authorities control different attributes, and each authority can issue the corresponding key to the user who has the attribute under control without any interaction with other authorities in the system. We can divide the MA-ABE schemes into the standard model and the random oracle (RO) model according to whether the RO model is used in the security proof. We can also divide MA-ABE schemes into the static security model, the adaptive security model, and the fully adaptive security model according to the different attack capabilities of adversaries. The differences are shown in Table 1.

Table 1.
Comparison between different security models.

Security model Authority corruption Authority setup queries Authority master key queries Whether to declare the attack target in advance

Static Static $\times$ $\times$ $\sqrt$

Adaptive Static $\times$ $\times$ $\times$

Fully adaptive Adaptive $\sqrt$ $\sqrt$ $\times$

Security model	Authority corruption	Authority setup queries	Authority master key queries	Whether to declare the attack target in advance
Static	Static	$\times$	$\times$	$\sqrt$
Adaptive	Static	$\times$	$\times$	$\times$
Fully adaptive	Adaptive	$\sqrt$	$\sqrt$	$\times$

In 2020, Okamoto and Takashima⁴ constructed an MA-ABE scheme based on the prime-order bilinear group and proved the adaptive security of the scheme under the decision linear (DLin) assumption and the RO model. In 2021, Datta et al.⁵ proposed the first lattice-based MA-ABE scheme, which has static security under the learning with errors (LWE) assumption in the RO model. In 2022, Waters et al.⁶ generalized the work of Brakerski and Vaikuntanathan,⁹ proposed a new trapdoor sampling lemma, and designed an MA-ABE scheme with static security under the evasive LWE assumption^10,11 in the standard model. However, the above schemes only consider static corruption in the security proof, that is, the attacker must complete the submission of both the honest and corrupted authorities in the global setup phase and cannot be changed later.

In 2023, Datta et al.⁷ first proposed a fully adaptive security model characterized by supporting adaptive authority corruption. Then, they constructed the first fully adaptively secure MA-ABE and proved its security by the dual system encryption technology. Chen et al.⁸ used the security model of Datta et al.⁷ and proposed an MA-ABE scheme with smaller parameter size, which satisfies many-use of attribute based on the NC $^{1}$ circuit. With the help of the Core 1-ABE component,¹² the fully adaptive security of the scheme is proved based on the MDDH assumption in the RO model. Table 2 shows the characteristics of the schemes more intuitively. Note that the model in Table 1 is divided according to the different attack capabilities of the adversary, and the model in Table 2 is divided according to whether the RO model is used in the security proof.

Table 2.

Scheme comparison.

Reference	Hardness assumption	Access structure	Security
Okamoto and Takashima⁴	DLin	NC $^{1}$	RO model $+$ adaptive security
Datta et al.⁵	LWE	DNFs	RO model $+$ static security
Waters et al.⁶	Evasive LWE	Subset strategy and DNFs	Standard model $+$ static security
Datta et al.⁷	MDDH and SD	LSSS and DNFs	RO model $+$ fully adaptive security
Chen et al.⁸	MDDH	NC $^{1}$	RO model $+$ fully adaptive security
This article	MDDH	Multi-fan-in circuits	RO model $+$ fully adaptive security

Note: NC $^{1}$ denotes circuits with fan-in two and fan-out one, and DNFs denote disjunctive normal forms.

Shorter parameter is always the goal for ABE. The public and private keys are not compact enough in the scheme of Datta et al.⁷ and the size of the cascade matrix $A = (A_{1} ‖ A_{2} ‖ A_{3})$ used in the security proof is shown in Figure 1, where $A_{1}$ participates in the generation of ciphertexts and keys. Chen et al.⁸ improved in this regard using the Core 1-ABE component in the security proof. The size of $A$ and $A_{1}$ is reduced, as shown in Figure 2, thereby reducing the parameter size of the scheme.

Figure 1.

The size of $A$ in the scheme of Datta et al.⁷

Figure 2.

The size of $A$ in the scheme of Chen et al.⁸

In the key generation algorithm and encryption algorithm of the above two schemes, two parallel sub-systems are introduced, called the ‘A’ sub-system and the ‘B’ sub-system. The purpose of introducing the ‘B’ sub-system is to cancel some exponents in the ‘A’ sub-system during decryption, so as to ensure the correctness. We consider that if the ‘B’ sub-system can be removed directly, the computational complexity of ciphertext and key will be reduced by about half. Therefore, the first problem to be solved in this article is that how to design the MA-ABE, which no longer uses ‘B’ sub-system, so as to shorten the parameter size and further improve the efficiency of the scheme.

It is pointed out in Benaloh and Leichter¹³ that the NC $^{1}$ circuit can be represented by a monotone LSSS matrix. Although the scheme⁸ is an MA-ABE scheme for NC $^{1}$ circuits, the LSSS matrix is actually embedded in its encryption algorithm. In 2023, Sun and Gao¹⁴ pointed out that for the same access structure, multi-fan-in circuits can reduce the total number of lines in the circuit compared to NC $^{1}$ circuits. Corresponding examples are shown in Section 2.3.1. If the ciphertext size of the ABE scheme is proportional to the number of lines, then the ciphertext size can be reduced, thereby improving the computational efficiency of the scheme. Therefore, it is necessary to design a fully adaptively secure MA-ABE scheme for multi-fan-in circuit.

1.1. Our contributions

In this article, we have achieved the following results:

Inspired by the secret sharing scheme for multi-fan-in circuits,¹⁴ we extend this method and embed it into the encryption algorithm, so that the LSSS matrix is no longer used. In this way, we overcome the difficulty of attribute reuse caused by the mapping in the LSSS matrix must be injective, and make the access structure of the scheme support many-use of attribute.

In the encryption algorithm, a new ciphertext component is introduced to replace the original ‘B’ sub-system. Specifically, the ciphertext and key components in the schemes of Datta et al.⁷ and Chen et al.⁸ are as follows:

\begin{aligned} c t & = (C, {C_{1, A, j}, C_{2, A, j}, C_{1, B, j}, C_{2, B, j}}_{j \in [l]}), \\ s k_{GID, u} & = {K_{GID, A, u}, K_{GID, B, u}}_{x_{u} \in S_{u}} . \end{aligned}

While in this article, they can be replaced by

s k_{GID, u} = {K_{GID, u}}_{x_{u} \in S_{u}}

. Theoretical analysis shows that our scheme can not only ensure the correctness of decryption, but also further reduce the overhead of ciphertext and key.

We introduce the user identifier universe $GID= {H (GID), H^{'} (GID)}$ to replace $H (GID)$ used in previous schemes, where ${H}^{'} (GID)$ is used for the generation of user keys and the decryption, and $H (GID)$ is only used for the decryption, which ensures that each step in the decryption contains the user’s unique identity information, thus avoiding collusion attacks between illegal users.

Combining the above techniques, we construct the first MA-ABE scheme supporting multi-fan-in circuits, and prove the fully adaptive security of the scheme using dual-system encryption technology. The experimental results show that our scheme has great advantages in the algorithm efficiency and the length of both ciphertext and key compared with the only two MA-ABE schemes,^7,8 which are also fully adaptively secure based on prime-order bilinear groups.

1.2. Organization

The remainder of this article is organized as follows. We refer the reader to Section 2 for some preliminary definitions, including the secret sharing scheme for multi-fan-in circuits and the fully adaptive security model of the MA-ABE scheme. In Section 3, an MA-ABE scheme for multi-fan-in circuits is proposed, whose security is proved using dual-system encryption technology. In Section 4, the parameters of the proposed scheme are compared with those of other schemes, and the correctness of the theoretical derivation is verified by experiments. Section 5 summarizes the whole article.

2. Preliminary

2.1. Prime-order bilinear group and the related symbol notations

Given a generator $G$ , whose input is a security parameter $λ$ and output is a group $G = (p, G_{1}, G_{2}, G_{T}, e)$ , where $p$ is a prime number. $G_{1}, G_{2}$ and $G_{T}$ are cyclic groups of order $p$ . $g \in G_{1}, h \in G_{2}, e (g, h) \in G_{T}$ are generators in their respective groups. $e : G_{1} \times G_{2} \to G_{T}$ is an efficiently bilinear map that satisfies the following properties:

Bilinearity: $\forall u \in G_{1}, v \in G_{2}, a, b \in Z_{p}$ , it is true that $e (u^{a}, v^{b}) = e {(u, v)}^{a b}$ .

Non-degeneracy: $e (g, h) \neq 1_{G_{T}}$ , where $1_{G_{T}}$ is the identity element of the group $G_{T}$ .

In particular, when $G_{1} = G_{2}$ , $g = h$ , we call $e$ a symmetric bilinear map. Otherwise, we call $e$ an asymmetric bilinear map.

The definition of related symbols is shown in Table 3.

Table 3.
Symbol notations.

Symbols Notations

$[n]$ ${1, 2, \dots, n}$

Lowercase letters bold $a \in Z_{p}^{k}$ Column vector $a$

Uppercase letters bold $A \in Z_{p}^{k \times k}$ Matrix $A$

$(A ‖ a)$ The cascade of $A$ and $a$

$span (a), span (A), span (A, a)$ Row expansion of $a$ , $A$ , and the cascade of $A$ and $a$

$basis (a),basis (A),basis (A, a)$ Basis of $span (a)$ , $span (A)$ , and $span (A, a)$

$M \leftarrow spa n^{m} (A)$ Matrix with column width $m$ and each column is taken from $span (A)$

Symbols	Notations
$[n]$	${1, 2, \dots, n}$
Lowercase letters bold $a \in Z_{p}^{k}$	Column vector $a$
Uppercase letters bold $A \in Z_{p}^{k \times k}$	Matrix $A$
$(A ‖ a)$	The cascade of $A$ and $a$
$span (a), span (A), span (A, a)$	Row expansion of $a$ , $A$ , and the cascade of $A$ and $a$
$basis (a),basis (A),basis (A, a)$	Basis of $span (a)$ , $span (A)$ , and $span (A, a)$
$M \leftarrow spa n^{m} (A)$	Matrix with column width $m$ and each column is taken from $span (A)$

For simplicity and accuracy of the description, we specify the following symbols and operations:

Let ${[A]}_{1} = g^{A}$ , ${[A]}_{2} = h^{A}$ , ${[A]}_{T} = e {(g, h)}^{A}$ , $e ({[A]}_{1}, {[B]}_{2}) = {[A B]}_{T} = e {(g, h)}^{A B}$ , ${[A]}_{i} ⊞ {[B]}_{i} = {[A + B]}_{i}$ , ${[A]}_{i} ⊟ {[B]}_{i} = {[A - B]}_{i}$ , $A ⊙ {[B]}_{i} = {[A B]}_{i}$ , ${[B]}_{i} ⊙ A = {[B A]}_{i}$ , $i = 1, 2$ .

For example, suppose

A = (\begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32} \end{array})

and

B = (\begin{array}{ccc} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \end{array}),

then,

\begin{aligned} {[A]}_{1} & = g^{A} = (\begin{array}{cc} g^{a_{11}} & g^{a_{12}} \\ g^{a_{21}} & g^{a_{22}} \\ g^{a_{31}} & g^{a_{32}} \end{array}), \\ {[B]}_{2} & = h^{B} = (\begin{array}{ccc} h^{a_{11}} & h^{a_{12}} & h^{a_{13}} \\ h^{a_{21}} & h^{a_{22}} & h^{a_{23}} \end{array}), \\ {[A]}_{T} & = e {(g, h)}^{A} = (\begin{array}{cc} e {(g, h)}^{a_{11}} & e {(g, h)}^{a_{12}} \\ e {(g, h)}^{a_{21}} & e {(g, h)}^{a_{22}} \\ e {(g, h)}^{a_{31}} & e {(g, h)}^{a_{32}} \end{array}) \end{aligned}

and

{[A B]}_{T} = e {(g, h)}^{(\begin{matrix} a_{11}, a_{12} \\ a_{21}, a_{22} \\ a_{31}, a_{32} \end{matrix}) \cdot (\begin{matrix} b_{11}, b_{12}, b_{13} \\ b_{21}, b_{22}, b_{23} \end{matrix})} .

2.2. Hardness assumption based on the bilinear group

Assumption 1 Escala et al.¹⁵

Given $k > l \geq 1, t \in [2]$ , the ${MDDH}_{l, k}^{G_{t}}$ assumption holds if and only if the following advantage is negligible for any probabilistic polynomial-time (PPT) adversary $A$ : ${Adv}_{A}^{{MDDH}_{l, k}^{G_{t}}} (λ) = | Pr [A (A, {[M]}_{t}, {[M S]}_{t}) = 1] - Pr [A (A, {[M]}_{t}, {[U]}_{t}) = 1] |$ , where $M \leftarrow Z_{p}^{k \times l}, S \leftarrow Z_{p}^{l \times m}, U \leftarrow Z_{p}^{k \times m}$ .

Assumption 2
Given $i, j \in [3], k > l \geq 1$ , $A_{i} \leftarrow A_{p}^{k \times l}$ , satisfying $(A_{1}^{} ‖ A_{2}^{} ‖ A_{3}^{}) = {({(A_{1} ‖ A_{2} ‖ A_{3})}^{- 1})}^{T}$ and $A_{i}^{T} A_{j}^{} = {\begin{matrix} I^{l \times l} i = j \\ 0 i \neq j \end{matrix}$ . The ${SD}_{A_{i} \to A_{i}, A_{j}}^{G_{1}}$ assumption holds if and only if the following advantage is negligible for any probabilistic polynomial-time (PPT) adversary $A$ : ${Adv}_{A}^{{SD}_{A_{i} \to A_{i}, A_{j}}^{G_{1}}} (λ) = | Pr [A (G, D, {[t_{0}]}_{1}) = 1] - Pr [A (G, D, {[t_{1}]}_{1}) = 1] |,$ where $D = ({[A_{1}]}_{1}, {[A_{2}]}_{1}, {[A_{3}]}_{1}, basis (A_{i}^{}), basis (A_{d}^{})$ , $basis (A_{i}^{}, A_{j}^{}))$ , $d \in [3] / {i, j}$ , $t_{0} \leftarrow span (A_{i})$ , $t_{1} \leftarrow span (A_{i}, A_{j})$ .

The definition of ${SD}_{B_{i} \to B_{i}, B_{j}}^{G_{2}}$ assumption is similar. Note that in the security proof of this article, $A_{2}$ and $B_{2}$ used are column vectors, so they are represented by $a_{2}$ and $b_{2}$ .
2.3. Access structure

Let $S$ be the attribute universe. An access structure $A$ on $S$ is a collection of non-empty attribute sets of $2^{S} ∖ \emptyset$ . The sets in $A$ are called the authorized sets and the sets not in $A$ are called the unauthorized sets. $\forall B, C \in 2^{S}$ , when $B \in A$ and $B \subseteq C$ , $C \in A$ , then $A$ is called monotone.¹⁶ $F (S, A) = 1$ is used to denote that the attribute universe $S$ satisfies the access structure $A$ , while $F (S, A) = 0$ to denote that $S$ does not satisfy $A$ .

2.3.1. $N C^{1}$ circuit and multi-fan-in circuit

The nodes of the $N C^{1}$ circuit are divided into two categories: leaf nodes and nonleaf nodes. The leaf node is at the bottom of the circuit as input, and all nonleaf nodes are fan-in 2. This circuit can be defined by a tuple $(g_{node}, a^{(1)}, a^{(2)}, b)$ , where $g_{node} : {0, 1}^{2} \to {0, 1}$ means that the node is an AND gate or an OR gate, $a^{(1)}, a^{(2)}$ are the input lines of the node, and $b_{g}$ is the output line of the node.

A monotone multi-fan-in circuit is a generalized form of the $N C^{1}$ circuit in which the nodes are also divided into leaf nodes and nonleaf nodes. The nonleaf nodes in the circuit can contain any number of input lines, and these nodes are defined by tuples

(g_{node}, a^{(1)}, \dots, a^{(m)}, b),

where

g_{node} : {0, 1}^{m} \to {0, 1}

indicates that the node is an AND gate or an OR gate,

a^{(1)}, \dots, a^{(m)}

are the input lines of the node,

b

is the output line of the node, and

m

is the number of input lines.

The difference between the $N C^{1}$ circuit and the multi-fan-in circuit is that the number of input lines of a nonleaf node of the multi-fan-in circuit can be arbitrary. For some special access structures, the depth of the $N C^{1}$ circuit is completely different from that of the multi-fan-in circuit. For example, for the access structure $f (x_{1}, x_{2}, \dots, x_{m}) = x_{1} \lor x_{2} \lor \dots \lor x_{m}$ , the corresponding $N C^{1}$ circuit is shown in Figure 3, whose depth is $m - 1$ , and the corresponding multi-fan-in circuit is shown in Figure 4, whose depth is 1.

Figure 3.

$N C^{1}$ circuit.

Figure 4.

Circuit with fan-in m.

Figure 5.

Relationship between different sets.

For the multi-fan-in circuit, let the set of leaf nodes be $S_{leaf}$ , the set of nonleaf nodes be $X$ , where $| X |$ represents the number of nonleaf nodes. In the MA-ABE scheme, different attribute categories are controlled by different authorities, since they are embedded in the leaf nodes. We assume that all attribute categories in the system constitute $I_{S} = {a t t_{1}, \dots, a t t_{n}}$ , the attribute categories controlled by honest authorities constitute $Y$ , and those controlled by corrupted authorities constitute $\bar{Y} = ∁_{I_{S}} (Y)$ , where $\bar{Y}$ is the complement of $Y$ in $I_{S}$ . Let the attribute value of the user about the attribute category $u \in I_{S}$ is $x_{u}$ , and all the legal attribute values constitute the set $S_{u}$ . In this article, we assume that each authority controls only one attribute category, so the terms ‘authority’ and ‘attribute category’ can be regarded as equivalent (‘authority’ is mainly used in the description of the security model, and ‘attribute category’ is mainly used in the description of the scheme). This assumption can be extended to the case where the authority controls any number of attributes.¹⁷ We use ‘honest attribute category’ to represent the attribute category controlled by honest authority, and ‘corrupted attribute category’ is similar. Therefore, $S_{leaf}$ can be further divided into a set $L_{1}$ embedded in honest attribute categories and a set ${\bar{L}}_{1} = ∁_{S_{leaf}} (L_{1})$ embedded in corrupted attribute categories. The relationship between the above sets is shown in Figure 5.

Given a set of user attributes $S = {x_{a t t_{1}}, \dots, x_{a t t_{n}}}$ , the multi-fan-in circuit $A$ embedded in our scheme can be transformed into the following boolean expression:

f (ϕ (x_{a t t_{1}}), \dots, ϕ (x_{a t t_{n}})) = {\begin{matrix} 1, & F (S, A) = 1 \\ 0, & F (S, A) = 0 \end{matrix},

where

ϕ (x_{i}) = {\begin{matrix} 1, & x_{i} \in S_{i} \\ 0, & x_{i} \notin S_{i} \end{matrix}, i \in S .

Next, we define two new mappings that will play a key role in the security proof.

Definition 1

The mapping $φ : {0, 1, \dots, | L_{1} | + | X |} \to {0} \cup X \cup L_{1}$ satisfies:

$φ (0) = 0$ .

$φ (1), \dots, φ (| L_{1} |)$ correspond to the elements in $L_{1}$ one by one.

$φ (| L_{1} | + 1), \dots, φ (| L_{1} | + | X |)$ correspond to the elements in $X$ one by one.

Obviously, the mapping $φ$ is surjective, and $φ (i)$ denotes the node label corresponding to each nonleaf node and the honest attribute category.

Definition 2

The mapping $ρ : X \cup S_{leaf} \to {0} \cup I_{S}$ satisfies:

For nonleaf node $i \in X$ , $ρ (i) = 0$ .

For the leaf node $i \in S_{leaf}$ , $ρ (i) \in I_{S}$ denotes the attribute category embedded in $i$ .

Since different leaf nodes may be embedded in the same attribute category, attribute reuse is allowed in multi-fan-in circuit. Therefore, mapping $ρ$ must be surjective, but not necessarily bijective.

In order to facilitate understanding, we describe the corresponding mapping $φ$ and mapping $ρ$ based on the access tree in Figure 6.

Figure 6.

Access tree instance.

In Figure 6, the node label is represented by 1-9, where $S_{leaf} = {1, 2, 3, 4, 5, 6}$ , $X = {7, 8, 9}$ . The leaf node contains the information of the attribute value $x_{u}$ , where $u \in I_{S}$ . Suppose that $a t t_{4}$ has been corrupted by the authority, so $Y = {a t t_{1}, a t t_{2}, a t t_{3}, a t t_{5}}$ , $\bar{Y} = {a t t_{4}}$ , $L_{1} = {1, 2, 3, 4, 6}$ , $L = X \cup L_{1} = {1, 2, 3, 4, 6, 7, 8, 9}$ , $| X | = 3$ , $| L_{1} | = 5$ . The specific mapping relationship is shown in Tables 4 and 5.

Table 4.

Mapping $φ$ .

Table 5.

Mapping $ρ$ .

$i$	1	2	3	4	5	6	7	8	9
$ρ (i)$	$a t t_{1}$	$a t t_{2}$	$a t t_{3}$	$a t t_{1}$	$a t t_{4}$	$a t t_{5}$	0	0	0

2.4. LSSS for multi-fan-in circuits

The extended LSSS used in this article is described in Table 6. Different from the general secret sharing scheme for multi-fan-in circuits,¹⁴ the input secret $d \in Z_{p}^{k}$ rather than $d \in Z_{p}$ , and the output sharing value $μ_{j} \in Z_{p}^{k}$ rather than $μ_{j} \in Z_{p}$ .

Table 6.
The extended LSSS $s h a r e (f, d)$ .

Input: The multi-fan-in circuit for a boolean function $f : {0, 1}^{m} \to {0, 1}$ , which has $l$ nodes, and the secret $d \in Z_{p}^{k}$ .

1. For each nonoutput line $j = 1, \dots, l - 1$ , select a ${\hat{μ}}_{j} \leftarrow Z_{p}^{k}$ randomly. For the uppermost output line, let ${\hat{μ}}_{l} = d$ .

2. Regarding the output line $j$ of the leaf nodes and the share $μ_{j} = {\hat{μ}}_{j}$ on the line.

3. For an AND gate $g_{node}$ , let the label of its output line be $j$ . $i n^{(1)}, \dots, i n^{(m)}$ are the input lines of $g$ . Then, the share of its output line is $μ_{j} = {\hat{μ}}_{j} + {\hat{μ}}_{i n^{(1)}} + \dots + {\hat{μ}}_{i n^{(m)}}$ .

4. For an OR gate $g_{node}$ , let the label of its output line be $j$ . $i n^{(1)}, \dots, i n^{(m)}$ are the input lines of $g_{node}$ . Then, the shares of its output line are $μ_{j^{(1)}} = {\hat{μ}}_{j} + {\hat{μ}}_{i n^{(1)}}, \dots, μ_{j^{(m)}} = {\hat{μ}}_{j} + {\hat{μ}}_{i n^{(m)}}$ , which means $μ_{j} =(μ_{j^{(1)}}, \dots, μ_{j^{(m)}})$ .

5. Output the shares of all nodes ${v_{j}}$ and the mapping $ρ$ , whose definition is consistent with Section 2.3.1.

Let the user’s attribute value of the attribute category $u$ be represented by $x_{u}$ . $S_{u}$ contains all the legal attribute values of $u$ , where $u \in I_{S}$ . For legitimate users in the system, there is a set of coefficients $ω_{j} \in {- 1, 0, 1}$ such that $d = \sum_{ρ (j) = 0 \lor x_{ρ (j)} \in S_{ρ (j)}} ω_{j} μ_{j}$ holds.

For the example given in Figure 6, the output results of the secret sharing scheme are shown in Table 7. It is assumed that the user has the attribute values $x_{a t t_{1}} \in S_{a t t_{1}}$ , $x_{a t t_{2}} \in S_{a t t_{2}}$ , $x_{a t t_{3}} \in S_{a t t_{3}}$ , that is, $ϕ (x_{a t t_{1}}) = ϕ (x_{a t t_{2}}) = ϕ (x_{a t t_{3}}) = 1$ , which obviously satisfy the access structure in Figure 6. Therefore, there is a set of coefficients $ω_{1} = ω_{2} = ω_{3} = ω_{9^{(1)}} = 1$ , $ω_{4} = ω_{5} = ω_{6} = ω_{8} = ω_{9^{(2)}} = 0$ , $ω_{7} = - 1$ , such that $d = {\hat{μ}}_{1} + {\hat{μ}}_{2} + {\hat{μ}}_{3} - ({\hat{μ}}_{1} + {\hat{μ}}_{2} + {\hat{μ}}_{3} + {\hat{μ}}_{7}) + ({\hat{μ}}_{7} + d)$ .

Table 7.

The output of the LSSS for the circuit in Figure 6.

$j$	$μ_{j}$	$ρ (j)$
1	${\hat{μ}}_{1}$	$a t t_{1}$
2	${\hat{μ}}_{2}$	$a t t_{2}$
3	${\hat{μ}}_{3}$	$a t t_{3}$
4	${\hat{μ}}_{4}$	$a t t_{1}$
5	${\hat{μ}}_{5}$	$a t t_{4}$
6	${\hat{μ}}_{6}$	$a t t_{5}$
7	${\hat{μ}}_{1} + {\hat{μ}}_{2} + {\hat{μ}}_{3} + {\hat{μ}}_{7}$	0
8	${\hat{μ}}_{4} + {\hat{μ}}_{5} + {\hat{μ}}_{6} + {\hat{μ}}_{8}$	0
$9^{(1)}$	${\hat{μ}}_{7} + d$	0
$9^{(2)}$	${\hat{μ}}_{8} + d$	0

2.5. Formal definition of MA-ABE and fully adaptive security model

2.5.1. Formal definition

We use $G I D$ to represent the global identity universe of the user, and it can be seen from Section 2.3.1 that $I_{S} = {a t t_{1}, \dots, a t t_{n}}$ , ‘authority’ and ‘attribute category’ are equivalent. The decentralized MA-ABE scheme consists of the following five algorithms:

$G l o b a l S e t u p (1^{λ}) \to GP$ : The input of the global setup algorithm is the security parameter $λ$ , and the output is the global parameter $GP$ of the system, including the user’s global identity universe $G I D$ .

$A u t h S e t u p (GP, u) \to (m p k_{u}, m s k_{u})$ : When the attribute category $u \in I_{S}$ is initialized, the global parameter $GP$ is used as the input, and the algorithm is called to output the master public and private key pair $(m p k_{u}, m s k_{u})$ .

$K e y G e n (GP, GID, m s k_{u}, S) \to s k_{GID, u}$ : The input of the key generation algorithm is the global parameter $GP$ , the user’s global identity $GID \in G I D$ , the master private key $m s k_{u}$ and the user attribute universe $S$ , and the output is the user’s private key $s k_{GID, u}$ .

$E n c (GP, m, A, {m p k_{u}}) \to c t$ : The encryption algorithm inputs the global parameter $GP$ , the message $m$ , the access structure $A$ and the public key ${m p k_{u}}$ , and outputs the ciphertext $c t$ .

$D e c (GP, GID, {s k_{GID, u}}, c t) \to m^{'}$ : The input of the decryption algorithm is the global parameter $GP$ , the user’s global identity $GID \in G I D$ , the private key ${s k_{GID, u}}$ and the ciphertext $c t$ . When the user attribute set $S$ satisfies the access structure $A$ , that is, $F (S, A) = 1$ , the algorithm outputs message $m^{'}$ .

If for any message $m$ , $GID \in G I D$ and $F (S, A) = 1$ , the following equation holds:

Pr [m^{'} = m | \begin{matrix} GP \leftarrow G l o b a l S e t u p (1^{λ}) \\ \forall u \in I_{S} : m p k_{u}, m s k_{u} \leftarrow A u t h S e t u p (GP, u) \\ \forall u \in I_{S} : s k_{GID, u} \leftarrow K e y G e n (GP, GID, m s k_{u}, S) \\ c t \leftarrow E n c (GP, m, A, {m p k_{u}}) \\ m^{'} = D e c (GP, GID, {s k_{GID, u}}, c t) \end{matrix}] = 1,

we say that the MA-ABE scheme is correct.

2.5.2. Fully adaptive security model

We give the definition of the fully adaptive security model between adversary $A$ and challenger $B$ . The difference between fully adaptive security and static security is that before the setup phase, the static security model requires $A$ to disclose the access structure to be challenged, while in the fully adaptive security model, $A$ does not need to disclose. At the same time, we consider the following two cases of authority corruption. (a) For the corrupted authority before the setup phase, the corresponding corrupted attribute universe is represented by $S_{C}$ . (b) When $A$ ’s multiple private key queries about $u$ are ignored by $B$ , $A$ is allowed to replace $B$ to set up $u$ and generate the corresponding master public and private key pair $(m p k_{u}, m s k_{u})$ , whose corresponding corrupted attribute universe is represented by $S_{I}$ . According to the definition in Section 2.3.1, $S_{C} \cup S_{I} = \bar{Y}$ .

The fully adaptive security model includes the following phases:

The challenger $B$ calls $G l o b a l S e t u p (1^{λ})$ to generate the global public parameter $GP$ and sends it to the adversary $A$ .

When $A$ requests to set up the authority $u$ for the first time, it needs to send $u$ to $B$ . $B$ calls $A u t h S e t u p (GP, u)$ to generate the master public and private key pair $(m p k_{u}, m s k_{u})$ , and sends $m p k_{u}$ to $A$ . If $A$ repeats the request later, $B$ will ignore. If $A$ corrupts the authority $u$ , the authority master key query can be performed, and $B$ needs to send $m s k_{u}$ to $A$ .

$A$ chooses the user attribute universe $S$ by himself, and performs private key query of any polynomial time. For some authority $u$ , if $A$ does not set up the authority $u$ before querying the private key, $B$ will ignore $A$ ’s private key query. If $A$ continues to query the private key about $u$ , it will set up $u$ instead of $B$ , and send the generated master public and private key $(m p k_{u}, m s k_{u})$ to $B$ . Finally, $B$ calls $K e y G e n (GP, GID, m s k_{u}, S)$ to generate $s k_{GID, u}$ and sends it to $A$ .

$A$ sends two equal-length messages $m_{0}, m_{1} \in G_{T}$ to $B$ . $B$ randomly throws a coin $β \in {0, 1}$ , calls $E n c (GP, m, A, {m p k_{u}})$ to generate the challenge ciphertext $c t$ and sends it to the adversary, where the access structure $A$ satisfies $F (S, A) = 0$ .

The adversary continues to query the private key of polynomial degree, the same as step 3, and the attribute universe $S$ is required to satisfy $F (S, A) = 0$ . $A$ outputs the challenge bit $β^{'}$ .

Definition 3
Assuming that the advantage of the adversary $A$ to break the above game is ${Adv}_{A}^{MA-ABE} (λ) ≜ | Pr [β^{'} = β] - 1 / 2 |$ , if for any PPT adversary $A$ , there is a negligible function $n e g l (\cdot)$ such that $\forall λ \in A$ , ${Adv}_{A}^{MA-ABE} (λ) \leq negl (λ)$ , the MA-ABE scheme is said to be fully adaptively secure.
3. MA-ABE with multi-fan-in circuits

3.1. Construction

$G l o b a l S e t u p (1^{λ}) :$ Let the security parameter be $λ$ . Run the bilinear group generator $G = (p, G_{1}, G_{2}, G_{T}, g, h, e)$ , where $G_{1}$ , $G_{2}$ and $G_{T}$ are all cyclic groups of order $p$ , $g$ and $h$ are the generators of $G_{1}$ and $G_{2}$ , respectively. The algorithm randomly selects

\begin{aligned} A_{1}, A_{3} \leftarrow Z_{p}^{(2 k + 1) \times k}, a_{2} \leftarrow Z_{p}^{2 k + 1}, \\ J \leftarrow Z_{p}^{(2 k + 1) \times (2 k + 1)}, h \leftarrow Z_{p}^{k} . \end{aligned}

Let

(A_{1}^{*} ‖ a_{2}^{*} ‖ A_{3}^{*}) = {({(A_{1} ‖ a_{2} ‖ A_{3})}^{- 1})}^{T}

, where

A_{1}^{*}, A_{3}^{*} \leftarrow Z_{p}^{(2 k + 1) \times k}

a_{2}^{*} \leftarrow Z_{p}^{2 k + 1}

, satisfying

A_{1}^{T} A_{1}^{*} = A_{3}^{T} A_{3}^{*} = I^{k \times k}

A_{1}^{T} a_{2}^{*} = A_{3}^{T} a_{2}^{*} = 0^{k \times 1}

a_{2}^{T} A_{1}^{*} = a_{2}^{T} A_{3}^{*} = 0^{1 \times k}

A_{1}^{T} A_{3}^{*} = A_{3}^{T} A_{1}^{*} = 0^{k \times k}

a_{2}^{T} a_{2}^{*} = 1

. The algorithm outputs the global parameter

GP = (G, {[A_{1}]}_{1}, H = {[A_{1}^{*} h]}_{2}, {[J]}_{1}, {[J^{T} A_{1}]}_{1})

and the user identifier universe

GID= {H (GID), H^{'} (GID)}

, where

H (GID) = {[h_{GID}]}_{2}

H^{'} (GID) = {[J h_{GID}]}_{2}

, and

h_{GID} \leftarrow Z_{p}^{2 k + 1}

$A u t h S e t u p (GP, u) :$ For each attribute category $u \in I_{S}$ , the algorithm randomly selects $W_{u} \in Z_{p}^{(2 k + 1) \times (2 k + 1)}$ and outputs the master private key $m s k_{u} = W_{u}$ , the master public key $m p k_{u} = W_{u}^{T} ⊙ {[A_{1}]}_{1} = {[W_{u}^{T} A_{1}]}_{1}$ . In particular, let $W_{0} = 0$ .

$E n c (GP, m, (f, ρ), {m p k_{ρ (j)}}) :$ The algorithm randomly selects $d, s_{j} \in Z_{p}^{k}$ , where $j$ denotes the node label in the circuit, and calls the secret sharing scheme about circuit $f$ to generate the sharing values, that is, $({μ_{j}}, ρ) \leftarrow s h a r e (f, d)$ , where $μ_{j} \in Z_{p}^{k}$ , $ρ (j) \neq 0$ denotes that $j$ is a leaf node, and $ρ (j) = 0$ denotes that $j$ is a nonleaf node. The generated ciphertext $c t = (c_{0}, {c_{1, j}, c_{2, j}}, c_{3})$ , where $c_{0} = m \cdot e (d^{T} ⊙ {[A_{1}^{T}]}_{1}, H)$ , $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{3} = {[J^{T} A_{1}]}_{1} ⊙ d = {[J^{T} A_{1} d]}_{1}$ ,

\begin{aligned} c_{2, j} & = {\begin{matrix} {{[W_{ρ (j)}^{T} A_{1}]}_{1} ⊙ s_{j} ⊞ {[A_{1}]}_{1} ⊙ μ_{j}}_{ρ (j) \neq 0} \\ {{[A_{1}]}_{1} ⊙ μ_{j}}_{ρ (j) = 0} \end{matrix} \\ = {\begin{matrix} {{[W_{ρ (j)}^{T} A_{1} s_{j} + A_{1} μ_{j}]}_{1}}_{ρ (j) \neq 0} \\ {{[A_{1} μ_{j}]}_{1}}_{ρ (j) = 0} \end{matrix} . \end{aligned}

$K ey G en (GP, H^{'} (GID), m s k_{u}, S) :$ Taken as input the global parameter $GP$ , the user identifier $H^{'} (GID)$ , the master private key $m s k_{u}$ and the user attribute universe $S$ . The user’s attribute value is $x_{u}$ for the attribute category $u$ . If $ϕ (x_{u}) = 1$ , the algorithm outputs the user’s private key $s k_{GID, u} = {K_{GID, u}}_{ϕ (x_{u}) = 1}$ , where $K_{GID, u} = W_{u} ⊙ (H^{'} (GID) \cdot H) = {[W_{u} \cdot (J h_{GID} + A_{1}^{*} h)]}_{2}$ . If $ϕ (x_{u}) = 0$ , the algorithm will not generate the user private key.

$D e c (GP, GID, {s k_{GID, u}}, c t) :$ Taken as input the global parameter $GP$ , the user identifier universe $GID$ , the user private key ${s k_{GID, u}}$ and the ciphertext $c t$ .

Firstly, when $j$ is a leaf node, compute

D_{j} = e (c_{2, j}^{T}, H^{'} (GID) ⊞ H) e {(c_{1, j}^{T}, K_{GID, ρ (j)})}^{- 1} .

When

j

is a nonleaf node, compute

D_{j} = e (c_{2, j}^{T}, H^{'} (GID) ⊞ H) .

Then compute the coefficient

ω_{j}

such that

d = \sum_{ρ (j) = 0 \lor x_{ρ (j)} \in S_{ρ (j)}} ω_{j} μ_{j}

. Therefore,

\begin{aligned} D & = \prod_{ρ (j) = 0 \lor x_{ρ (j)} \in S_{ρ (j)}} {(D_{j})}^{ω_{j}} = e ({[d^{T} A_{1}^{T}]}_{1}, {[J h_{GID} + A_{1}^{*} h]}_{2}), \\ D^{'} & = \frac{D}{e (c_{3}^{T}, H (GID))} = e ({[d^{T} A_{1}^{T}]}_{1}, {[A_{1}^{*} h]}_{2}) . \end{aligned}

At last, compute

\frac{c_{0}}{D^{'}} = \frac{m \cdot e (d^{T} ⊙ {[A_{1}^{T}]}_{1}, H)}{e ({[d^{T} A_{1}^{T}]}_{1}, {[A_{1}^{*} h]}_{2})} = m .

3.2. Security proof

Before the proof, we note that since ${[A_{1}]}_{1}$ is public, ${[A_{1}]}_{1} ⊙ μ_{j}$ in the ciphertext component $c_{2, j}$ can be directly regarded as the sharing value generated by the secret sharing scheme. ${[A_{1}]}_{1}$ can be further regarded as a part of the secret to be shared and then a new secret sharing scheme $s h a r e^{'} (f, {[A_{1}]}_{1} ⊙ d)$ is obtained because of the linear properties of the secret sharing scheme. At this time, the information of ${[A_{1}]}_{1}$ is embedded in the generated secret sharing values ${μ_{j}}$ . Therefore, the original encryption algorithm can be equivalent to the following algorithm, the difference is represented by ‘ $◻$ ’:

$E n c^{'} (GP, m, {m p k_{ρ (j)}}, f, ρ) :$ The algorithm randomly selects $d, s_{j} \in Z_{p}^{k}$ and calls the secret sharing scheme about circuit $f$ to generate the sharing values, that is, $({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[A_{1}]}_{1} ⊙ d),$ where $j$ denotes the node label in the circuit. The generated ciphertext $c t = (c_{0}, {c_{1, j}, c_{2, j}}, c_{3})$ , where $c_{0} = m \cdot e (d^{T} ⊙ {[A_{1}^{T}]}_{1}, H)$ , $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ ,

c_{2, j} = {\begin{matrix} {{[W_{ρ (j)}^{T} A_{1}]}_{1} ⊙ s_{j} ⊞ μ_{j}}_{ρ (j) \neq 0} \\ {μ_{j}}_{ρ (j) = 0} \end{matrix},

c_{3} = {[J^{T} A_{1} d]}_{1}

$s h a r e^{'} (f, {[A_{1}]}_{1} ⊙ d)$ is different from $s h a r e (f, d)$ described in Table 4 only in the range of variable, which can be seen as follows:

The secret to be shared is ${[A_{1} d]}_{1} \in G_{1}^{2 k + 1}$ rather than $d \in Z_{p}^{k}$ .

The selected random number ${\hat{μ}}_{j} \in G_{1}^{2 k + 1}$ rather than ${\hat{μ}}_{j} \in Z_{p}^{k}$ .

The operation involved is the multiplication operation on $G_{1}$ rather than the addition operation on $Z_{p}$ .

The output sharing value is $μ_{j} \in G_{1}^{2 k + 1}$ instead of $μ_{j} \in Z_{p}^{k}$ .

The reason why $s h a r e (f, d)$ scheme is adopted in the design of encryption algorithm is that the operation on $Z_{p}$ is faster than that on $G_{1}$ , which makes it have better performance in generating shared values on nonleaf nodes. Due to the need of proof, we only regard the original encryption algorithm as $E n c^{'} (GP, m, {m p k_{ρ (j)}}, f, ρ)$ in the security proof.

Next, we will use the dual system encryption technology to prove the fully adaptive security of the scheme. Assume that the adversary $A$ performs at most $q$ private key queries, which $B$ will ignore if there is no request for setting up the authority $u$ before querying the private key. If $A$ continues to query the private key about $u$ , he will set up the authority $u$ instead of $B$ , and send the generated master public and private key pair $(m p k_{u} = {[P_{u}]}_{1}, m s k_{u})$ to $B$ , so that $B$ can respond to the key query and generate the challenge ciphertext, where $P_{u} \leftarrow Z_{p}^{(2 k + 1) \times k}$ . Note that $B$ mainly responds to $A$ ’s private key query by simulating $H (GID)$ . The game sequence used in the proof is shown in Table 8, and the classification of the subscript $t^{'}$ is shown in Table 9.

Table 8.
Game sequences used in the proof.

Table 9.

Classification of $t^{'}$ .

$t^{'}$	$φ (t^{'})$	Notation
$0$	$0$	Connected with the previous game
$1, \dots, \| L_{1} \|$	$φ (t^{'}) \in L_{1}$	$φ (t^{'})$ is an uncorrupted leaf node
$\| L_{1} + 1 \|, \dots, \| X \|$	$φ (t^{'}) \in X$	$φ (t^{'})$ is a nonleaf node

$H_{0}$ : As the same as our proposed scheme, note that the encryption algorithm uses the equivalent $E n c^{'}$ algorithm.

$H_{1, t} (t \in {0, \dots, q})$ : The only difference with $H_{0}$ is that the challenger uses different $GI D_{i}$ when responding to private key queries. Specifically, for $i \leq t$ , $H (GI D_{i}) = {[A_{1}^{*} h_{GI D_{i}}]}_{2}$ , $H^{'} (GI D_{i}) = {[{J A}_{1}^{*} h_{GI D_{i}}]}_{2}$ , for $i > t$ , $H (GI D_{i}), H^{'} (GI D_{i}) \leftarrow G_{2}^{2 k + 1}$ are consistent with $H_{0}$ . Obviously, $H_{1, 0} = H_{0}$ .

$H_{2}$ : The only difference with $H_{1, q}$ is the secret shared by $s h a r e^{'}$ scheme, thus the challenge ciphertexts $c_{0}$ and $c_{3}$ are different. The challenger first randomly selects $b \in {0, 1}$ , $d, s_{j}, d^{'} \in Z_{p}^{k}$ , where $j$ is used to represent the node label in the circuit. Then he calls the secret sharing scheme about the circuit $f$ to generate the sharing value, that is, $({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[A_{1}]}_{1} ⊙ d ⊞ {[A_{3}]}_{1} ⊙ d^{'})$ . The challenge ciphertext is as follows:

$c_{0} = m_{b} \cdot e (d^{T} ⊙ {[A_{1}^{T}]}_{1} ⊞ (d^{'})^{T} ⊙ {[A_{3}^{T}]}_{1}, H)$ , $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{3} = {[J^{T} \cdot (A_{1} d + A_{3} d^{'})]}_{1}$ .

When $j$ is represented a nonleaf node, $c_{2, j} = μ_{j}$ .

When $j$ is represented a leaf node, (1)

If $ρ (j) \in \bar{Y}$ , $c_{2, j} = {[P_{ρ (j)} s_{j}]}_{1} ⊞ μ_{j}$ .

(2)

If $ρ (j) \in Y$ , $c_{2, j} = {[W_{ρ (j)}^{T} A_{1}]}_{1} ⊙ s_{j} ⊞ μ_{j}$ .

$H_{3, t^{'}} (t^{'} \in {0, \dots, | L_{1} | + | X |})$ : The only difference with $H_{2}$ is the partial challenge ciphertext $c_{1, j}$ and $c_{2, j}$ . Obviously, $H_{3, 0} = H_{2}$ . The challenger first randomly selects $b \in {0, 1}$ , $d, d^{'} \in Z_{p}^{k}$ , and calls the secret sharing scheme about the circuit $f$ to generate the sharing value, that is, $({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[A_{1}]}_{1} ⊙ d ⊞ {[A_{3}]}_{1} ⊙ d^{'})$ , where $j$ is used to represent the node label in the circuit. The challenge ciphertext is as follows:

$c_{0} = m_{b} \cdot e (d^{T} ⊙ {[A_{1}^{T}]}_{1} ⊞ (d^{'})^{T} ⊙ {[A_{3}^{T}]}_{1}, H)$ , $c_{3} = {[J^{T} \cdot (A_{1} d + A_{3} d^{'})]}_{1}$ .

For $ρ (j) \in \bar{Y}$ , $j$ represents the corrupted leaf node. Randomly select $s_{j} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{2, j} = {[P_{ρ (j)} s_{j}]}_{1} ⊞ μ_{j}$ .

For $ρ (j) \in Y$ , $j$ represents the uncorrupted leaf node. $c_{1, j}$ and $c_{2, j}$ will be gradually replaced with the accumulation of $t^{'}$ . (1)

If $φ^{- 1} (j) \leq t^{'}$ , randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j} ⊞ {[A_{3}]}_{1} ⊙ s_{j}^{'} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1}$ , $c_{2, j} = {[W_{ρ (j)}^{T} (A_{1} s_{j} + A_{3} s_{j}^{'})]}_{1} ⊞ μ_{j}$ .

(2)

If $φ^{- 1} (j) > t^{'}$ , randomly select $s_{j} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{2, j} = {[W_{ρ (j)}^{T} A_{1} s_{j}]}_{1} ⊞ μ_{j}$ .

For $ρ (j) = 0$ , $j$ represents the nonleaf node. $c_{1, j}$ will be gradually replaced with the accumulation of $t^{'}$ . (1)

(2)

If $φ^{- 1} (j) > t^{'}$ , randomly select $s_{j} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{2, j} = μ_{j}$ .

$H_{4, t} (t \in {0, \dots, q})$ : The only difference with $H_{3, | L_{1} | + | X |}$ is that the challenger uses different $GI D_{i}$ when responding to private key queries. Specifically, for $i \leq t$ , the challenger randomly selects $h_{GI D_{i}}, h_{GI D_{i}}^{'} \leftarrow Z_{p}^{k}$ , then $H (GI D_{i}) = {[A_{1}^{*} h_{GI D_{i}} + A_{3}^{*} h_{GI D_{i}}^{'}]}_{2}$ , $H^{'} (GI D_{i}) = {[J (A_{1}^{*} h_{GI D_{i}} + A_{3}^{*} h_{GI D_{i}}^{'})]}_{2}$ . For $i > t$ , $H (GI D_{i}) = {[A_{1}^{*} h_{GI D_{i}}]}_{2}$ and $H^{'} (GI D_{i}) = {[{J A}_{1}^{*} h_{GI D_{i}}]}_{2}$ are consistent with $H_{3, | L_{1} | + | X |}$ . Obviously, $H_{4, 0} = H_{3, | L_{1} | + | X |}$ .

$H_{5}$ : The only difference with $H_{4, q}$ is the secret shared by $s h a r e^{'}$ scheme, thus the challenge ciphertexts $c_{0}$ and $c_{3}$ are different. The challenger first randomly selects $b \in {0, 1}$ , $d, d^{'} \in Z_{p}^{k}$ and ${d}^{″} \in Z_{p}$ . Then he calls the secret sharing scheme about the circuit $f$ to generate the sharing value, that is,

({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[A_{1} d + A_{3} d^{'}]}_{1} ⊞ {d}^{″} ⊙ {[a_{2}]}_{1}),

where

j

is used to represent the node label in the circuit. The challenge ciphertext is as follows:

$c_{0} = m_{b} \cdot e ({[d^{T} A_{1}^{T} + (d^{'})^{T} A_{3}^{T}]}_{1} ⊞ d^{″} ⊙ {[a_{2}^{T}]}_{1}, H)$ , $c_{3} = {[J^{T} \cdot (A_{1} d + A_{3} (d^{'}) + a_{2} d^{″})]}_{1}$ .

For $ρ (j) \in Y$ , $j$ represents the uncorrupted leaf node. Randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j} ⊞ {[A_{3}]}_{1} ⊙ s_{j}^{'} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1}$ , $c_{2, j} = {[W_{ρ (j)}^{T} (A_{1} s_{j} + A_{3} s_{j}^{'})]}_{1} ⊞ μ_{j}$ .

For $ρ (j) = 0$ , $j$ represents the nonleaf node. Randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1}$ , $c_{2, j} = μ_{j}$ .

$H_{6, t^{'}} (t^{'} \in {0, \dots, | L_{1} | + | X |})$ : The only difference with $H_{5}$ is the partial challenge ciphertext $c_{1, j}$ and $c_{2, j}$ . Obviously, $H_{6, 0} = H_{5}$ . The challenger first randomly selects $b \in {0, 1}$ , $d, d^{'} \in Z_{p}^{k}$ , and calls the secret sharing scheme about the circuit $f$ to generate the sharing value, that is, $({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[A_{1} d + A_{3} d^{'} + {d}^{″} a_{2}]}_{1})$ , where $j$ is used to represent the node label in the circuit. The challenge ciphertext is as follows:

$c_{0} = m_{b} \cdot e ({[d^{T} A_{1}^{T} + (d^{'})^{T} A_{3}^{T} + {d}^{″} a_{2}^{T}]}_{1}, H)$ , $c_{3} = {[J^{T} \cdot (A_{1} d + A_{3} d^{'} + a_{2} {d}^{″})]}_{1}$ .

For $ρ (j) \in Y$ , $j$ represents the uncorrupted leaf node. $c_{1, j}$ and $c_{2, j}$ will be gradually replaced with the accumulation of $t^{'}$ . (1)

If $φ^{- 1} (j) \leq t^{'}$ , randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , $s_{j}^{″} \in Z_{p}$ , then $c_{1, j} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1} ⊞ s_{j}^{″} ⊙ {[a_{2}]}_{1} = {[A_{1} s_{j} + A_{3} s_{j}^{'} + s_{j}^{″} a_{2}]}_{1}$ , $c_{2, j} = {[W_{ρ (j)}^{T} (A_{1} s_{j} + A_{3} s_{j}^{'} + s_{j}^{″} a_{2})]}_{1} ⊞ μ_{j}$ .

(2)

If $φ^{- 1} (j) > t^{'}$ , randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1}$ , $c_{2, j} = {[W_{ρ (j)}^{T} (A_{1} s_{j} + A_{3} s_{j}^{'})]}_{1} ⊞ μ_{j}$ .

For $ρ (j) = 0$ , $j$ represents the nonleaf node. $c_{1, j}$ will be gradually replaced with the accumulation of $t^{'}$ . (1)

(2)

If $φ^{- 1} (j) > t^{'}$ , randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1}$ , $c_{2, j} = μ_{j}$ .

$H_{7, t} (t \in {0, \dots, q})$ : The only difference with $H_{6, | L_{1} | + | X |}$ is that the challenger uses different $GI D_{i}$ when responding to private key queries. Specifically, for $i \leq t$ , $H (GI D_{i}), {H}^{'} (GI D_{i}) \leftarrow G_{2}^{3 k}$ .

For $i > t$ , $H (GI D_{i}) = {[A_{1}^{*} h_{GI D_{i}} + A_{3}^{*} h_{GI D_{i}}^{'}]}_{2}$ and ${H}^{'} (GI D_{i}) = {[J (A_{1}^{*} h_{GI D_{i}} + A_{3}^{*} h_{GI D_{i}}^{'})]}_{2}$ are consistent with $H_{6, | L_{1} | + | X |}$ . Obviously, $H_{7, 0} = H_{6, | L_{1} | + | X |}$ .

$H_{8}$ : The only difference with $H_{7, q}$ is the challenge ciphertext $c_{0} \leftarrow G_{T}$ .

Lemma 1

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{1, t} (\cdot)$ such that $\forall λ \in N$ ,

| Pr [⟨ A, H_{1, (t - 1)} ⟩ = 1] - Pr [⟨ A, H_{1, t} ⟩ = 1] | \leq n e g l_{1, t} (λ)

if the

{MDDH}_{k, 2 k + 1}^{G_{2}}

assumption holds.

Proof.

Supposed that there is a PPT adversary $A$ that can distinguish $H_{1, (t - 1)}$ and $H_{1, t}$ with a non-negligible advantage successfully, then the challenger $B$ can solve the ${MDDH}_{k, 2 k + 1}^{G_{2}}$ assumption with a non-negligible advantage.

First, $B$ gets an instance of the ${MDDH}_{k, 2 k + 1}^{G_{2}}$ assumption that consists of $G = (p, G_{1}, G_{2}, G_{T}, g, h, e)$ , ${[M]}_{2}$ , where $M \leftarrow Z_{p}^{(2 k + 1) \times k}$ . $t_{β} = M u$ when $β = 0$ or $t_{β} \leftarrow Z_{p}^{2 k + 1}$ when $β = 1$ , where $u \leftarrow Z_{p}^{k}$ . $B$ proceeds as follows:

Generating the global public parameters: $B$ randomly selects $A_{1} \leftarrow Z_{p}^{(k + 2) \times k}$ , $J \leftarrow Z_{p}^{(k + 2) \times (k + 2)}$ and implicitly sets $A_{1}^{*} = M R^{- 1}$ , where $R = A_{1}^{T} M \in Z_{p}^{k \times k}$ . $B$ further samples $\tilde{h} \in Z_{p}^{k}$ and implicitly sets $h = R \tilde{h}$ , $H = {[M]}_{2} ⊙ \tilde{h} = {[A_{1}^{*} h]}_{2}$ . The global public parameter $GP = (G, {[A_{1}]}_{1}, H = {[A_{1}^{*} h]}_{2}, {[J]}_{1}, {[J^{T} A_{1}]}_{1})$ .

Generating authority master public and private keys: When $A$ queries the master public and private keys of attribute category $u$ for the first time (i.e., requests to set up an authority $u$ ), $B$ runs $A u t h S e t u p$ : Randomly select $W_{u} \in Z_{p}^{(2 k + 1) \times (2 k + 1)}$ , keep the private key $m s k_{u} = W_{u}$ , and send the master public key $m p k_{u} = W_{u}^{T} ⊙ {[A_{1}]}_{1}$ to $A$ . If the subsequent query about $u$ is repeated, $B$ aborts. If $u$ is corrupted by $A$ later, B will send $m s k_{u}$ to $A$ .

Generating the user identifier universe: In response to the $i$ th user identifier query of $A$ , $B$ generates $GI D_{i}$ as follows:

For $i \leq t - 1$ , randomly select ${\tilde{h}}_{GI D_{i}} \leftarrow Z_{p}^{k}$ , which implicitly sets $h_{GI D_{i}} = R {\tilde{h}}_{GI D_{i}}$ . Then $H (GI D_{i}) = {[M]}_{2} ⊙ {\tilde{h}}_{GI D_{i}} = {[A_{1}^{*} h_{GI D_{i}}]}_{2}$ , ${H}^{'} (GI D_{i}) = {[{J A}_{1}^{*} h_{GI D_{i}}]}_{2}$ .

For $i = t$ , let $H (GI D_{i}) = {[t_{β}]}_{2}$ . Note that if $t_{β} = M u$ , $B$ simulates $H (GI D_{t}) = {[t_{β}]}_{2} = {[M u]}_{2} = {[A_{1}^{*} R R^{- 1} h_{GI D_{t}}]}_{2} = {[A_{1}^{*} h_{GI D_{t}}]}_{2}$ , which implicitly sets $h_{GI D_{t}} = R u$ . If $t_{β} \leftarrow Z_{p}^{2 k + 1}$ , then $H (GI D_{t}) = {[t_{β}]}_{2} \leftarrow G_{2}^{2 k + 1}$ , ${H}^{'} (GI D_{i}) = {[J t_{β}]}_{2}$ .

For $i > t$ , randomly select $H (GI D_{i}) {,{H}}^{'} (GI D_{i}) \leftarrow G_{2}^{2 k + 1}$ .

Generating the user private keys: When $A$ queries for the private keys of the user’s attribute universe $S$ (assuming that the user identifier universe is $GI D_{i}$ ), $B$ runs $K ey G en$ : Let $S_{u}$ consist of all the legal attribute values of the attribute category $u$ , and $x_{u}$ denote the user’s attribute value about $u$ . If $ϕ (x_{u}) = 1$ , the algorithm outputs the user’s private key $s k_{GID, u} = {K_{GID, u}}_{ϕ (x_{u}) = 1}$ , where $K_{GID, u} = W_{u} ⊙ ({H}^{'} (GI D_{i}) \cdot H)$ .

Note: (1) $B$ will ignore the query about the private key if there is no request for setting up the authority $u$ before. If $A$ continues to query the private key about $u$ , he will set up the authority $u$ instead of $B$ , and send the generated master public key $m p k_{u} = {[P_{u}]}_{1}$ to $B$ , so that $B$ can generate the challenge ciphertext. (2) $B$ also ignores the query about the private key if $F (S \cup \bar{Y}, A) = 1.$

Guess: $A$ eventually outputs a guess bit $b^{'} \in {0, 1}$ . $B$ outputs 1 if $b^{'} = b$ and 0 otherwise.

When $t_{β} = M u$ , it implies that $B$ simulates the global identifier $H (GI D_{t}) = {[A_{1}^{*} h_{GI D_{t}}]}_{2}$ , ${H}^{'} (GI D_{i}) = {[{J A}_{1}^{*} h_{GI D_{i}}]}_{2}$ in response to the $t$ th private key query, so it coincides with that in $H_{1, t}$ . When $t_{β} \leftarrow Z_{p}^{2 k + 1}$ , it implies that $B$ simulates the global identifier $H (GI D_{i}), {H}^{'} (GI D_{i}) \leftarrow G_{2}^{2 k + 1}$ in response to the $t$ th private key query, so it coincides with that in $H_{1, (t - 1)}$ . If $A$ can successfully distinguish between $H_{1, (t - 1)}$ and $H_{1, t}$ , $B$ must be able to solve the ${MDDH}_{k, 2 k + 1}^{G_{2}}$ assumption with a non-negligible advantage, which contradicts the hardness assumption.

Lemma 2

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{2} (\cdot)$ such that $\forall λ \in N,$

| Pr [⟨ A, H_{1, q} ⟩ = 1] - Pr [⟨ A, H_{2} ⟩ = 1] | \leq n e g l_{2} (λ)

if the

{SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}

assumption holds.

Proof.

Supposed that there is a PPT adversary $A$ that can distinguish $H_{1, q}$ and $H_{2}$ with a non-negligible advantage successfully, then the challenger $B$ can solve the ${SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}$ assumption with a non-negligible advantage.

First, $B$ gets an instance of the ${SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}$ assumption that consists of $G = (p, G_{1}, G_{2}, G_{T}, g, h, e)$ , ${[A_{1}]}_{1}, {[a_{2}]}_{1}, {[A_{3}]}_{1}$ , $basis (A_{1}^{*}),$ $basis (a_{2}^{*}), basis (A_{1}^{*}, A_{3}^{*})$ . $t_{β} \leftarrow span (A_{1})$ when $β = 0$ or $t_{β} \leftarrow span (A_{1}, A_{3})$ when $β = 1$ . $B$ proceeds as follows:

Generating the global public parameters: $B$ randomly selects $J \leftarrow Z_{p}^{(2 k + 1) \times (2 k + 1)}$ and a linear combination about $basis (A_{1}^{*})$ to generate $H = {[A_{1}^{*} h]}_{2}$ , and provide the following global parameter to $A$ :

GP = (G, {[A_{1}]}_{1}, H = {[A_{1}^{*} h]}_{2}, {[J]}_{1}, {[J^{T} A_{1}]}_{1}) .

Similarly, for $i \leq q$ , $B$ randomly selects a linear combination about $basis (A_{1}^{*})$ to generate the user identifier $H (GI D_{i}) = {[A_{1}^{*} h_{GI D_{i}}]}_{2}$ and ${H}^{'} (GI D_{i}) = {[{J A}_{1}^{*} h_{GI D_{i}}]}_{2}$ required in the $i$ th query.

First, $B$ samples $s_{j} \in Z_{p}^{k}$ , where $j$ is used to represent the node label in the circuit. Then he calls the secret sharing scheme about the circuit $f$ to generate the sharing value, that is, $({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[t_{β}]}_{1})$ . The challenge ciphertext is as follows:

$c_{0} = m_{b} \cdot e ({[t_{β}^{T}]}_{1}, H)$ , $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{3} = {[J^{T} t_{β}]}_{1}$ .

When $j$ is represented a nonleaf node, $c_{2, j} = μ_{j}$ .

When $j$ is represented a leaf node, (1)

If $ρ (j) \in \bar{Y}$ , $c_{2, j} = {[P_{ρ (j)} s_{j}]}_{1} ⊞ μ_{j}$ .

(2)

If $ρ (j) \in Y$ , $c_{2, j} = {[W_{ρ (j)}^{T} A_{1}]}_{1} ⊙ s_{j} ⊞ μ_{j}$ .

$Guess:$ $A$ eventually outputs a guess bit $b^{'} \in {0, 1}$ . $B$ outputs 1 if $b^{'} = b$ and 0 otherwise.

When $t_{β} \leftarrow span (A_{1})$ , it implies that the secret shared in LSSS is ${[A_{1}]}_{1} ⊙ d$ , the ciphertext components $c_{0} = m_{b} \cdot e ({[d^{T} A_{1}^{T}]}_{1}, H)$ and $c_{3} = {[J^{T} t_{β}]}_{1} = {[J^{T} A_{1} d]}_{1}$ , so it coincides with that in $H_{1, q}$ . When $t_{β} \leftarrow span (A_{1}, A_{3})$ , it implies that the secret shared in LSSS is ${[A_{1}]}_{1} ⊙ d ⊞ {[A_{3}]}_{1} ⊙ d^{'}$ , the ciphertext components $c_{0} = m_{b} \cdot e ({[d^{T} A_{1}^{T} + (d^{'})^{T} A_{3}^{T}]}_{1}, H)$ , and $c_{3} = {[J^{T} t_{β}]}_{1} = {[J^{T} (A_{1} d + A_{3} d^{'})]}_{1}$ , so it coincides with that in $H_{2}$ . All the other components of the game are properly simulated by $B$ . If $A$ can successfully distinguish between $H_{1, q}$ and $H_{2}$ , $B$ must be able to solve the ${SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}$ assumption with a non-negligible advantage, which contradicts the hardness assumption.

Lemma 3

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{3, t^{'}} (\cdot)$ such that $\forall λ \in N,$

| Pr [⟨ A, H_{3, (t^{'} - 1)} ⟩ = 1] - Pr [⟨ A, H_{3, t^{'}} ⟩ = 1] | \leq n e g l_{3, t^{'}} (λ)

if the

{SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}

assumption holds.

Proof.

Supposed that there is a PPT adversary $A$ that can distinguish $H_{3, (t^{'} - 1)}$ and $H_{3, t^{'}}$ with a non-negligible advantage successfully, then the challenger $B$ can solve the ${SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}$ assumption with a non-negligible advantage.

$B$ is consistent with Lemma 2 in the process of generating global public parameters, user identifiers, authority master public and private keys, and user private keys.

Generating the challenge ciphertext: When $A$ queries for the challenge ciphertext about plaintext $m_{0}$ and $m_{1}$ , he needs to send to $B$ the access structure $(f, ρ)$ to be challenged and the master public key ${m p k_{u} = {[P_{u}]}_{1}}_{u \in S_{I}}$ corresponding to the corrupted attribute universe $S_{I}$ . $B$ randomly selects $r \leftarrow span (A_{1}, A_{3})$ , $b \in {0, 1}$ , and calls the secret sharing scheme about the circuit $f$ to generate the sharing value, that is, $({μ_{j}}, ρ) \leftarrow s h a r e^{'} (f, {[r]}_{1})$ , where $j$ is used to represent the node label in the circuit. It is implied that ${[r]}_{1} = {[A_{1}]}_{1} ⊙ d ⊞ {[A_{3}]}_{1} ⊙ d^{'}$ , where $d, d^{'} \in Z_{p}^{k}$ . The challenge ciphertext is as follows:

$c_{0} = m_{b} \cdot e ({[r^{T}]}_{1}, H)$ , $c_{3} = {[J^{T} r]}_{1} = {[J^{T} (A_{1} d + A_{3} d^{'})]}_{1}$ .

For $ρ (j) \in Y$ , $j$ represents the uncorrupted leaf node. (1)

If $φ^{- 1} (j) < t^{'}$ , randomly select $s_{j}, s_{j}^{'} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j} ⊞ {[A_{3}]}_{1} ⊙ s_{j}^{'} = {[A_{1} s_{j} + A_{3} s_{j}^{'}]}_{1}$ , $c_{2, j} = W_{ρ (j)}^{T} ⊙ {[(A_{1} s_{j} + A_{3} s_{j}^{'})]}_{1} ⊞ μ_{j} = {[W_{ρ (j)}^{T} (A_{1} s_{j} + A_{3} s_{j}^{'})]}_{1} ⊞ μ_{j}$ .

(2)

If $φ^{- 1} (j) = t^{'}$ , $c_{1, j} = {[t_{β}]}_{1}$ , $c_{2, j} = W_{ρ (j)}^{T} ⊙ {[t_{β}]}_{1} ⊞ μ_{j} = {[W_{ρ (j)}^{T} t_{β}]}_{1} ⊞ μ_{j}$ .

(3)

If $φ^{- 1} (j) > t^{'}$ , randomly select $s_{j} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{2, j} = W_{ρ (j)}^{T} ⊙ {[A_{1} s_{j}]}_{1} ⊞ μ_{j} = {[W_{ρ (j)}^{T} A_{1} s_{j}]}_{1} ⊞ μ_{j}$ .

For $ρ (j) = 0$ , $j$ represents the nonleaf node. (1)

(2)

If $φ^{- 1} (j) = t^{'}$ , $c_{1, j} = {[t_{β}]}_{1}$ , $c_{2, j} = μ_{j}$ .

(3)

If $φ^{- 1} (j) > t^{'}$ , randomly select $s_{j} \in Z_{p}^{k}$ , then $c_{1, j} = {[A_{1}]}_{1} ⊙ s_{j}$ , $c_{2, j} = μ_{j}$ .

$Guess:$ $A$ eventually outputs a guess bit $b^{'} \in {0, 1}$ . $B$ outputs 1 if $b^{'} = b$ and 0 otherwise.

When $t_{β} \leftarrow span (A_{1})$ , it implies that $c_{1, φ (t^{'})} = {[A_{1} s_{φ (t^{'})}]}_{1}$ , and when $ρ (φ (t^{'})) \in Y$ , $c_{2, φ (t^{'})} = {[W_{ρ (φ (t^{'}))}^{T} A_{1} s_{φ (t^{'})}]}_{1} ⊞ μ_{φ (t^{'})}$ , so it coincides with that in $H_{3, (t^{'} - 1)}$ . When $t_{β} \leftarrow span (A_{1}, A_{3})$ , it implies that $c_{1, φ (t^{'})} = {[A_{1} s_{φ (t^{'})} + A_{3} s_{φ (t^{'})}^{'}]}_{1}$ , and when $ρ (φ (t^{'})) \in Y$ , $c_{2, φ (t^{'})} = {[W_{ρ (φ (t^{'}))}^{T} (A_{1} s_{φ (t^{'})} + A_{3} s_{φ (t^{'})}^{'})]}_{1} ⊞ μ_{φ (t^{'})}$ , so it coincides with that in $H_{3, t^{'}}$ . If $A$ can successfully distinguish between $H_{3, (t^{'} - 1)}$ and $H_{3, t^{'}}$ , $B$ must be able to solve the ${SD}_{A_{1} \to A_{1}, A_{3}}^{G_{1}}$ assumption with a non-negligible advantage, which contradicts the hardness assumption.

Lemma 4

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{4, t} (\cdot)$ such that $\forall λ \in N,$

| Pr [⟨ A, H_{4, (t - 1)} ⟩ = 1] - Pr [⟨ A, H_{4, t} ⟩ = 1] | \leq n e g l_{4, t} (λ)

if the

{SD}_{B_{1} \to B_{1}, B_{3}}^{G_{2}}

assumption holds.

Proof.

The proof of this lemma is similar to that of Lemma 1, so we omit the details here.

Lemma 5

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{5} (\cdot)$ such that $\forall λ \in N,$

| Pr [⟨ A, H_{4, q} ⟩ = 1] - Pr [⟨ A, H_{5} ⟩ = 1] | \leq n e g l_{5} (λ)

if the

{SD}_{A_{1} \to A_{1}, a_{2}}^{G_{1}}

assumption holds.

Proof.

The proof of this lemma is similar to that of Lemma 2, so we omit the details here.

Lemma 6

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{6, t^{'}} (\cdot)$ such that $\forall λ \in N,$

| Pr [⟨ A, H_{6, (t^{'} - 1)} ⟩ = 1] - Pr [⟨ A, H_{6, t^{'}} ⟩ = 1] | \leq n e g l_{6, t^{'}} (λ)

if the

{SD}_{A_{1} \to A_{1}, a_{2}}^{G_{1}}

assumption holds.

Proof.

The proof of this lemma is similar to that of Lemma 3, so we omit the details here.

Lemma 7

For all PPT adversaries $A$ , there exists a negligible function $n e g l_{7, t} (\cdot)$ such that $\forall λ \in N,$

| Pr [⟨ A, H_{7, (t - 1)} ⟩ = 1] - Pr [⟨ A, H_{7, t} ⟩ = 1] | \leq n e g l_{7, t} (λ)

if the

{SD}_{B_{3} \to b_{2}, B_{3}}^{G_{2}}

assumption holds.

Proof.

The proof of this lemma is similar to that of Lemma 1, so we omit the details here.

Lemma 8

For all PPT adversaries $A$ , $H_{7, q} =_{c} H_{8}$ holds.

Proof.

In $H_{7, q}$ , we can see that

\begin{aligned} c_{0} & = m_{b} \cdot e ({[d^{T} A_{1}^{T} + (d^{'})^{T} A_{3}^{T} + {d}^{″} a_{2}^{T}]}_{1}, H) \\ = m_{b} \cdot e ({[d^{T} A_{1}^{T} + (d^{'})^{T} A_{3}^{T} + {d}^{″} a_{2}^{T}]}_{1}, {[A_{1}^{*} h]}_{2}) \\ = m_{b} \cdot e ({[d^{T} A_{1}^{T}]}_{1}, {[A_{1}^{*} h]}_{2}) \cdot e ({[(d^{'})^{T} A_{3}^{T}]}_{1}, {[A_{1}^{*} h]}_{2}) \\ \cdot e ({[{d}^{″} a_{2}^{T}]}_{1}, {[A_{1}^{*} h]}_{2}) . \end{aligned}

Because $A_{1}^{T} A_{1}^{*} = I^{k \times k}$ , $a_{2}^{T} a_{2}^{*} = 1$ , $A_{3}^{T} A_{3}^{*} = I^{k \times k}$ , $A_{1}^{T} a_{2}^{*} = A_{3}^{T} a_{2}^{*} = 0^{k \times 1}$ , $a_{2}^{T} A_{1}^{*} = a_{2}^{T} A_{3}^{*} = 0^{1 \times k}$ , $A_{1}^{T} A_{3}^{*} = A_{3}^{T} A_{1}^{*} = 0^{k \times k}$ , it can be seen that $c_{0} = m_{b} \cdot e ({[d^{T}]}_{1}, {[h]}_{2})$ , and $d, h$ only appear when the challenger responds to the query, which is confidential for $A$ . Therefore, $c_{0} = m_{b} \cdot e ({[d^{T}]}_{1}, {[h]}_{2})$ can be regarded as a uniform distribution, which is obviously the same as $c_{0}$ in $H_{7, q}$ , and $H_{7, q} =_{c} H_{8}$ holds.

Theorem 1

The MA-ABE scheme proposed in this article satisfies fully adaptive security under ${MDDH}_{k, 2 k + 1}^{G_{2}}$ assumption and $SD$ assumption.

Proof.

Assume that the attack advantage of MA-ABE scheme is ${Adv}_{A}^{MA-ABE} (λ) ≜ | Pr [β^{'} = β] - 1 / 2 |$ , the following advantage can be obtained by Lemmas 1–8:

\begin{aligned} {Adv}_{A}^{MA-ABE} (λ) \\ = \sum_{t \in {1, \dots, q}} | Pr [⟨ A, H_{1, (t - 1)} ⟩ = 1] - Pr [⟨ A, H_{1, t} ⟩ = 1] | \\ + | Pr [⟨ A, H_{1, q} ⟩ = 1] - Pr [⟨ A, H_{2} ⟩ = 1] | \\ + \sum_{t^{'} \in {1, \dots, | L_{1} | + | X |}} | Pr [⟨ A, H_{3, (t^{'} - 1)} ⟩ = 1] - Pr [⟨ A, H_{3, t^{'}} ⟩ = 1] | \\ + \sum_{t \in {1, \dots, q}} | Pr [⟨ A, H_{4, (t - 1)} ⟩ = 1] - Pr [⟨ A, H_{4, t} ⟩ = 1] | \\ + | Pr [⟨ A, H_{4, q} ⟩ = 1] - Pr [⟨ A, H_{5} ⟩ = 1] | \\ + \sum_{t^{'} \in {1, \dots, | L_{1} | + | X |}} | Pr [⟨ A, H_{6, (t^{'} - 1)} ⟩ = 1] - Pr [⟨ A, H_{6, t^{'}} ⟩ = 1] | \\ + \sum_{t \in {1, \dots, q}} | Pr [⟨ A, H_{7, (t - 1)} ⟩ = 1] - Pr [⟨ A, H_{7, t} ⟩ = 1] | \\ + | Pr [⟨ A, H_{7, q} ⟩ = 1] - Pr [⟨ A, H_{8} ⟩ = 1] | \\ \leq \sum_{t \in {1, \dots, q}} (n e g l_{1, t} (λ) + n e g l_{4, t} (λ) + n e g l_{7, t} (λ)) \\ + \sum_{t^{'} \in {1, \dots, | L_{1} | + | X |}} (n e g l_{3, t^{'}} (λ) + n e g l_{6, t^{'}} (λ)) \\ + n e g l_{2} (λ) + n e g l_{5} (λ) \end{aligned}

4. Parameter comparison

In this section, we compare the MA-ABE scheme proposed in this article with the scheme [10,11] in terms of storage overhead and time complexity of each algorithm. The symbol notations, parameter comparison, and the time complexity comparison are shown in Tables 10 –12, respectively.

Table 10.
Symbol notation.

Symbol Notations

$| Z_{p} |, | G_{1} |, | G_{2} |, | G_{T} |$ Byte lengths of the elements in groups $Z_{p}$ , $G_{1}$ , $G_{2}$ , and $G_{T}$

$A_{1}$ , $A_{2}$ , $A_{T}$ Time complexity of the double point operation over $G_{1}$ , $G_{2}$ , and $G_{T}$

$l$ Row number of LSSS matrix

$N$ The total number of shared values generated by the secret sharing scheme

$| m |$ Byte lengths of the plaintext

$P$ Time complexity of the bilinear operation

$I$ Time complexity of the inverse operation over $G_{T}$

$n_{1}$ The number of shared values generated at the leaf nodes

$n_{2}$ The number of shared values generated at the nonleaf nodes

Symbol	Notations
$\| Z_{p} \|, \| G_{1} \|, \| G_{2} \|, \| G_{T} \|$	Byte lengths of the elements in groups $Z_{p}$ , $G_{1}$ , $G_{2}$ , and $G_{T}$
$A_{1}$ , $A_{2}$ , $A_{T}$	Time complexity of the double point operation over $G_{1}$ , $G_{2}$ , and $G_{T}$
$l$	Row number of LSSS matrix
$N$	The total number of shared values generated by the secret sharing scheme
$\| m \|$	Byte lengths of the plaintext
$P$	Time complexity of the bilinear operation
$I$	Time complexity of the inverse operation over $G_{T}$
$n_{1}$	The number of shared values generated at the leaf nodes
$n_{2}$	The number of shared values generated at the nonleaf nodes

Table 11.

Parameter comparison.

Scheme	Length of master public keys	Length of master private keys	Length of user private keys	Length of ciphertext
Datta et al.⁷	$6 k^{2} \| G_{1} \|$	$18 k^{2} \| Z_{p} \|$	$6 k \| G_{2} \|$	$12 k l \| G_{1} \| + \| m \|$
Chen et al.⁸	$6 k^{2} \| G_{1} \|$	$(12 k^{2} + 6 k) \| Z_{p} \|$	$(4 k + 2) \| G_{2} \|$	$(10 k l + 2 l) \| G_{1} \| + \| m \|$
Our scheme	$(k^{2} + 2 k) \| G_{1} \|$	$(k^{2} + 4 k + 4) \| Z_{p} \|$	$(k + 2) \| G_{2} \|$	$(k + 2) (2 N + 1) \| G_{1} \| + \| G_{T} \|$

Table 12.

Time complexity comparison.

Scheme	$A u t h S e t u p$	$K e y G e n$	$E n c$	$D e c$
Datta et al.⁷	$6 k^{2} A_{1}$	$6 k A_{2}$	$12 k l A_{1} + P$	$(12 k P + 6 k I + 3 A_{T}) l$
Chen et al.⁸	$6 k^{2} A_{1}$	$(4 k + 2) A_{2}$	$(10 k l + 2 l) A_{1} + P$	$[(10 k + 2) P + (4 k + 2) I + 3 A_{T}] l$
Our scheme	$(k^{2} + 2 k) A_{1}$	$(k + 2) A_{2}$	$(k + 2) (2 N + 1) A_{1} + P$	$[(2 k + 4) P + (k + 2) I + A_{T}] n_{1} + (k + 2) P n_{2} + 2 (k + 2) P + 2 I + 2 A_{T}$

It can be directly seen from Tables 11 and 12 that the scheme in this article has obvious advantages in the length of the master public and private keys, and the user private keys, which indicates that $A u t h S e t u p$ algorithm and $K e y G e n$ algorithm are more efficient. In order to see the advantages of this scheme in $E n c$ and $D e c$ algorithms more intuitively, we will give the following example.

Let $k = 2$ and assume $| m | \leq 128$ bytes, when the embedded access structure is the circuit shown in Figure 6, $l = 6$ , $N = 10$ , $n_{1} = 6$ , $n_{2} = 4$ . We compare the specific parameters and time complexity by programming, as shown in Figures 7 and 8. The experimentation is performed on a Windows 10 64-bit operating system with an Intel Core i7-9700K @ 3.60 GHz processer, 32 GB RAM and the integrated development environment is Visual Studio 2022. The basic operations in the implementation of the algorithm depend on the Pairing-based Cryptography Library (PBC-0.5.14).

Figure 7.

Parameter length.

Figure 8.

Running time of algorithm.

5. Remark

This article constructs a collusion-resistant MA-ABE scheme based on the secret sharing scheme for multi-fan-in circuit, whose access structure supports many-time of attribute. Based on the RO model, we proved the fully adaptive security of the scheme. The experimental results show that the proposed scheme has obvious advantages in parameter size and algorithm efficiency. However, the size of the matrix $A$ cannot be further reduced due to the use of $SD$ assumption. At the same time, if the secret sharing scheme of multi-fan-in and multi-fan-out circuit can be constructed, the ciphertext size will be smaller. Therefore, our next research direction mainly considers the replacement of the hardness assumption and the design of MA-ABE for multi-fan-in and multi-fan-out circuits based on square matrix.

Footnotes

Acknowledgements

This research was funded by the National Cryptologic Science Fund of China (no. 2025NCSF02044).

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by the National Cryptologic Science Fund of China (nos.2025NCSF02044).

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

References

Sahai

Waters

. Fuzzy identity-based encryption. In: Advances in cryptology – EUROCRYPT 2005, 24th annual international conference on the theory and applications of cryptographic techniques (ed R Cramer), LNCS, Vol. 3494, 2005, pp.457–473. Heidelberg: Springer.

Goyal

Pandey

Saha

, et al. Attribute-based encryption for fine-grained access control of encrypted data. In: 13th ACM conference on computer and communications security, CCS 2006, 2006, pp.89–98. Alexandria, VA, USA: ACM.

Chase

. Multi-authority attribute based encryption. In: Theory of cryptography, 4th theory of cryptography conference (TCC), 2007, pp.515–534. Amsterdam, The Netherlands: Springer.

Okamoto

Takashima

. Decentralized attribute-based encryption and signatures. IEICE Trans Fundam Electron Commun Comput Sci 2020; 103-A(1): 41–73.

Datta

Komargodski

Waters

. Decentralized multi-authority ABE for DNFs from LWE. In: Advances in cryptology – EUROCRYPT 2021 – 40th annual international conference on the theory and applications of cryptographic techniques (eds A Canteaut and FX Standaert), LNCS, Vol. 12696, 2021, pp.177–209. Heidelberg: Springer.

Waters

Wee

. Multi-authority ABE from lattices without random oracles. In: Theory of cryptography – 20th international conference, 2022, pp.651–679. Chicago, IL, USA: Springer.

Datta

Komargodski

Waters

. Fully adaptive decentralized multi-authority ABE. In: Advances in cryptology – EUROCRYPT 2023 – 42nd annual international conference on the theory and applications of cryptographic techniques, 2023, pp.447–478. Lyon, France: Springer.

Chen

Chu

Gao

, et al. Improved fully adaptive decentralized MA-ABE for NC1 from MDDH. In: Advances in cryptology – ASIACRYPT 2023 – 29th international conference on the theory and application of cryptology and information security, 2023, pp.3–32. Guangzhou, China: Springer.

Brakerski

Vaikuntanathan

. Lattice-inspired broadcast encryption and succinct ciphertext-policy ABE. In: 13th innovations in theoretical computer science conference (ITCS), 2022, CA, USA, pp.28:1–28:20.

10.

Wee

. Optimal broadcast encryption and CP-ABE from evasive lattice assumptions. In: Advances in cryptology – EUROCRYPT 2022 – 41st annual international conference on the theory and applications of cryptographic techniques, 2022, pp.217–241. Trondheim, Norway: Springer.

11.

Tsabary

. Candidate witness encryption from lattice techniques. In: Advances in cryptology – CRYPTO 2022 – 41st annual international conference on the theory and applications of cryptographic techniques, 2022, pp.535–559. Santa Barbara, CA, USA: Springer.

12.

Kowalczyk

Wee

. Compact adaptively secure ABE for NC1 From k-Lin. J Cryptol 2020; 33(3): 954–1002.

13.

Benaloh

Leichter

. Generalized secret sharing and monotone functions. In: Advances in cryptology – CRYPTO 1988, 8th annual international cryptology conference, 1988, pp.27–35. Santa Barbara, CA, USA: Springer.

14.

Sun

Gao

. Adaptively secure KP-ABE for circuits with fan-in n and fan-out 1. Comput J 2023; 66(10): 2554–2573.

15.

Escala

Herold

Kiltz

, et al. An algebraic framework for Diffie-Hellman assumptions. J Cryptol 2017; 30(1): 242–288.

16.

Karchmer

Wigderson

. On span programs. In: Proceedings of the eighth annual structure in complexity theory conference, 1993, pp.102–111. San Diego, CA, USA: IEEE Computer Society.

17.

Rouselakis

Waters

. Efficient statically-secure large-universe multi-authority attribute-based encryption. In: Financial cryptography and data security – 19th international conference, FC 2015, 2015, pp.315–332. San Juan, Puerto Rico: Springer.

Scheme	Length of master public keys	Length of master private keys	Length of user private keys	Length of ciphertext
Datta et al.⁷	$6 k^{2} \| G_{1} \|$	$18 k^{2} \| Z_{p} \|$	$6 k \| G_{2} \|$	$12 k l \| G_{1} \| + \| m \|$
Chen et al.⁸	$6 k^{2} \| G_{1} \|$	$(12 k^{2} + 6 k) \| Z_{p} \|$	$(4 k + 2) \| G_{2} \|$	$(10 k l + 2 l) \| G_{1} \| + \| m \|$
Our scheme	$(k^{2} + 2 k) \| G_{1} \|$	$(k^{2} + 4 k + 4) \| Z_{p} \|$	$(k + 2) \| G_{2} \|$	$(k + 2) (2 N + 1) \| G_{1} \| + \| G_{T} \|$

Fully adaptive MA-ABE supporting multi-fan-in circuits

Abstract

Keywords

1. Introduction

Table 1. Comparison between different security models. Security model Authority corruption Authority setup queries Authority master key queries Whether to declare the attack target in advance Static Static × × √ Adaptive Static × × × Fully adaptive Adaptive √ √ ×

1.2. Organization

2. Preliminary

2.1. Prime-order bilinear group and the related symbol notations

Assumption 1 Escala et al. 15

2.3.1. N C 1 circuit and multi-fan-in circuit

2.5.1. Formal definition

2.5.2. Fully adaptive security model

3.1. Construction

3.2. Security proof

Table 8. Game sequences used in the proof.

Footnotes

Acknowledgements

Funding

Declaration of conflicting interests

References

Assumption 1 Escala et al.¹⁵

2.3.1. $N C^{1}$ circuit and multi-fan-in circuit

Table 8.
Game sequences used in the proof.