ABE for Circuits with Constant-Size Secret Keys and Adaptive Security

Abstract

An important theme in the research on attribute-based encryption (ABE) is minimizing the sizes of secret keys and ciphertexts. In this work, we present two new ABE schemes with constant-size secret keys, i.e., the key size is independent of the sizes of policies or attributes and dependent only on the security parameter $\lambda$.

• We construct the first key-policy ABE scheme for circuits with constant-size secret keys, ${|{\textsf{sk}}_f| = {\text {poly}}(\lambda )}$, which concretely consist of only three group elements. The previous state-of-the-art scheme by [Boneh et al., Eurocrypt ’14] has key size polynomial in the maximum depth d of the policy circuits, ${|{\textsf{sk}}_f| = {\text {poly}}(d,\lambda )}$. Our new scheme removes this dependency of key size on d while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, ${|{\textsf{ct}}_{{{\textbf{x}}}}| = |{{\textbf{x}}}|{\text {poly}}(d, \lambda )}$.

• We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, namely, ${|{\textsf{sk}}_f| = {\text {poly}}(\lambda )}$ and ${|{\textsf{ct}}_{{{\textbf{x}}}}| = {\text {poly}}(|{{\textbf{x}}}|, \lambda )}$. Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non-constant-size keys [Agrawal–Yamada, Eurocrypt ’20, Agrawal–Wichs–Yamada, TCC ’20], or constant-size keys but large ciphertexts that grow with the policy size as well as the attribute length. Our second construction is the first ABE scheme achieving double succinctness, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them.

Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach–Wee–Wichs FOCS ’18], the constructions become adaptively secure.

1 Introduction

Attribute-based encryption (ABE) [24, 37] is a novel generalization of public-key encryption for enforcing fine-grained access control. In this work, we focus on improving the efficiency of ABE schemes, especially on minimizing the sizes of secret keys while keeping ciphertexts small. In key-policy (KP) ABE, a secret key ${\textsf{sk}}_f$ is tied to a policy f and a ciphertext ${\textsf{ct}}_{{\textbf{x}}}$ encrypting a message $\mu$ is tied to an attribute ${{\textbf{x}}}$, so that a secret key is only “authorized” to decrypt a ciphertext if the associated attribute ${{\textbf{x}}}$ satisfies the policy f. At first glance, since a secret key specifies the associated policy f, it appears that the size of the secret key would have to depend at least linearly on the (description) size of f. Similarly, a ciphertext would have to grow linearly with the length of the associated attribute ${{\textbf{x}}}$. Secret keys and ciphertexts with linear dependency of their sizes on the policies and attributes they are tied to are said to be compact, and most ABE schemes are indeed compact.

However, upon closer examination, as ABE does not guarantee privacy of the policies nor the attributes, it is possible to give a description of the policy f in the clear in the secret key, and the non-trivial part of the secret key may be smaller than the policy. In this case, the right measure of efficiency should be the size of the non-trivial part (i.e., the overhead), which we now view as the secret key. We can now aim for secret keys of size smaller than that of the policy — i.e., ${|{\textsf{sk}}_f|=\textrm{o}(|f|)}$ — referred to as succinct keys, or even keys of size independent of that of the policy — i.e., ${|{\textsf{sk}}_f| = \textrm{O}(1)}$ — referred to as constant-size keys.¹ Similarly, succinct ciphertexts have size smaller than the length of the attributes, ${|{\textsf{ct}}_{{\textbf{x}}}|=\textrm{o}(|{{\textbf{x}}}|)}$, and constant-size ciphertexts satisfy ${|{\textsf{ct}}_{{\textbf{x}}}| = \textrm{O}(1)}$. We further examine the efficiency of ciphertext-policy (CP) ABE [10], which enables instead the ciphertexts ${\textsf{ct}}_f$ to specify the policies, so that only secret keys ${\textsf{sk}}_{{\textbf{x}}}$ with attributes satisfying the policies can decrypt them. Naturally, succinct keys and ciphertexts have size ${|{\textsf{sk}}_{{\textbf{x}}}|=\textrm{o}(|{{\textbf{x}}}|)}$ and ${|{\textsf{ct}}_f|=\textrm{o}(|f|)}$, and constant size means the same as in KP-ABE.

How close can we get to the ideal efficiency of having both constant-size keys and ciphertexts? Despite tremendous effort, the state-of-the-art is still far from the ideal. Current ABE schemes with either succinct keys or succinct ciphertexts can be broadly classified as follows (see Figs. 1 and 2):

• The work of [11] built KP-ABE based on LWE for polynomial-size circuits with succinct keys ${|{\textsf{sk}}_f|= {\text {poly}}(d)}$ and ciphertexts of size ${|{\textsf{ct}}_{{\textbf{x}}}| = |{{\textbf{x}}}|{\text {poly}}(d)}$, where d is the depth of the circuit.

• Several works [5,6,7, 32, 38, 42, 43] constructed KP-ABE and CP-ABE for low-depth computations with either constant-size secret keys or constant-size ciphertexts from pairing, i.e., either ${|{\textsf{sk}}| = \textrm{O}(1)}$ or ${|{\textsf{ct}}| = \textrm{O}(1)}$, at the cost of the other component being much larger, of size ${{\Omega }(|f|\cdot |{{\textbf{x}}}|)}$.

• The recent works of [3, 4] constructed CP-ABE for Boolean formulae with succinct ciphertexts ${|{\textsf{ct}}_f| = {\Theta }(|{{\textbf{x}}}|)}$ and compact keys ${|{\textsf{sk}}_{{\textbf{x}}}| = {\Theta }(|{{\textbf{x}}}|)}$. These schemes are based on LWE and strong assumptions on pairing groups — either the generic (pairing) group model [4] or knowledge assumptions [3].

In this work, we set out to improve the state-of-the-art towards the direction of ideal efficiency.[3] We observe that though there are ABE schemes for low-depth computations with constant-size keys, we do not have such ABE for general circuits. We ask:

Can we construct ABE for circuits with constant-size keys?

Furthermore, all of the above schemes either have succinct keys or succinct ciphertexts, but never both at the same time. If we were to eventually achieve ideal efficiency, we would have to first overcome the intermediate barrier of simultaneously having succinct keys and ciphertexts — we refer to this as double succinctness. We thus ask:

Can we construct ABE for expressive policies with

both succinct keys and succinct ciphertexts?

We note that the above questions are unanswered even when assuming the strong primitive of indistinguishability obfuscation (iO). Several works [17, 18, 27] constructed ABE for circuits (or even functional encryption for circuits) using indistinguishability obfuscation or related primitives. However, they all have large secret keys of size ${\text {poly}}(|f|)$. The only work that manages to obtain ABE for RAM with constant-size keys [20] rely on a strong primitive called extractable witness encryption, which however lacks provably secure instantiation.

Fig. 1.

Efficiency comparison for KP-ABE schemes. The pink region highlights succinctness for $|{\textsf{ct}}_{{{\textbf{x}}}}|$ and $|{\textsf{sk}}_f|$. This work and [BGG⁺14] are KP-ABE schemes for circuits, while the rest of the schemes are for low-depth computation (Color figure online).

Fig. 2.

Efficiency comparison for CP-ABE schemes. The pink region highlights succinctness for $|{\textsf{ct}}_{f}|$ and $|{\textsf{sk}}_{{{\textbf{x}}}}|$. All the included schemes are CP-ABE for low-depth computation (Color figure online).

Our Results. We address both questions. For the former, we construct the first KP-ABE scheme for circuits with constant-size keys while keeping the ciphertext size the same as in [11]. Concretely, each secret key consists of only 3 group elements. For the latter, we present the first CP-ABE scheme for Boolean formulae achieving double succinctness — it has constant-size keys and succinct ciphertexts. Concretely, each secret key consists of only 2 group elements. Both constructions rely on LWE and the generic (pairing) group model, similar to [4].

Theorem

(KP-ABE). Assuming LWE, in the generic (pairing) group model, there is a KP-ABE for circuits (Construction 2) that achieves selective security and has key size ${|{\textsf{sk}}_C|={\text {poly}}(\lambda )}$ (concretely, containing 3 group elements) and ciphertext size ${|{\textsf{ct}}_{{\textbf{x}}}|=|{{\textbf{x}}}|{\text {poly}}(\lambda ,d)}$, where d is the maximum depth of the policy circuits.

Theorem

(CP-ABE). Assuming LWE, in the generic (pairing) group model, there is a CP-ABE for Boolean formulae [31] that achieves very selective security, and has constant-size keys ${|{\textsf{sk}}_{{\textbf{x}}}|={\text {poly}}(\lambda )}$ (concretely, containing 2 group elements) and ciphertexts of size ${|{\textsf{ct}}_f|=|{{\textbf{x}}}|^2{\text {poly}}(\lambda )}$ independent of the formula size |f|.

Additional Contribution — Adaptive Security. The standard security property of ABE is collusion resistance, which stipulates that no information of the message $\mu$ encrypted in a ciphertext should be revealed even when multiple secret keys are issued, as long as none of the keys alone is authorized to decrypt the ciphertext. Adaptive security requires collusion resistance to hold even when attributes and policies tied to the challenge ciphertext and the secret keys are chosen adaptively by the adversary. The weaker selective security restricts the adversary to commit to the attribute (in KP-ABE) or the policy (in CP-ABE) associated with the challenge ciphertext before seeing any parameters of the system, and very selective security further requires all attributes and policies in both the challenge ciphertext and the secret keys to be chosen statically.

Adaptive security guards against more powerful adversaries than selective security. It is known that the latter can be generically lifted to the former via complexity leveraging, at the cost of subexponential hardness assumptions. However, complexity leveraging is undesirable not only because it requires subexponential hardness, but also because it requires scaling the security parameter to be polynomial in the length of the information to be guessed, $\lambda = {\text {poly}}(|x|)$ in KP-ABE or $\lambda = {\text {poly}}(|f|)$ in CP-ABE. As a result, complexity leveraging is not a viable solution when aiming for constant-size keys, as key size ${\text {poly}}(\lambda )$ would already depends on |x| or |f|.

Instead, we show that in our constructions of KP- and CP-ABE, if assume adaptive LWE instead of plain LWE, then they achieve adaptive security and our reduction only incurs a polynomial amount of security loss. The adaptive LWE assumption [36] postulates that LWE samples of the form $\{{{{\textbf{s}}}^{{\textsf{T}}}({{\textbf{A}}}_i - {{\textbf{x}}}[i]{{\textbf{G}}}) + {{\textbf{e}}}_i^{{\textsf{T}}}}\}_i$ are pseudorandom, even if the adversary adaptively chooses ${{\textbf{x}}}$ depending on the random matrices $\{{{\textbf{A}}}_i\}_i$.

Theorem

(adaptive security). Assuming the polynomial hardness of adaptive LWE (instead of LWE), in the generic (pairing) group model, the KP-ABE scheme (Construction 2) and the CP-ABE scheme [31] are adaptively secure.

In the literature, the ABE schemes for circuits based on lattices [11, 21] achieve only selective security (without complexity leveraging). Adapting it to have adaptive security has remained a technical barrier, except for very limited classes of policies such as 3-CNF [39]. Alternatively, there are schemes based on indistinguishability obfuscation or functional encryption for all circuits that are adaptively secure [27, 40], but requiring stronger assumptions. Our technique can be viewed as making the lattice-based schemes adaptively secure when combined with pairing. Note that this is not trivial, for instance, the recent CP-ABE schemes in [3, 4] that combine [11] with pairing groups inherit the selective security of the former (even if assuming adaptive LWE).

Organization. In Sect. 2, we present an overview of our techniques. In Sect. 3, we introduce preliminaries. In Sect. 4, we define nearly linear secret sharing schemes and non-annihilability, and construct such a scheme for bounded-depth circuits based on the adaptive LWE assumption. In Sect. 5, we present our adaptively secure KP-ABE for bounded-depth circuits. Due to space constraints, we refer the readers to the full version [31] for our doubly succinct CP-ABE as well as the secret sharing scheme and our new analysis of IPFE of [1] for that.

2 Technical Overview

High-Level Ideas. Let’s focus on our KP-ABE scheme for circuits first. The first known construction of KP-ABE for circuits from LWE [22] has keys of size $|f|{\text {poly}}(d,\lambda )$. The scheme of [11] reduces the key size to ${\text {poly}}(d,\lambda )$. Both schemes achieve only selective security because they rely on the lattice trapdoor simulation techniques. Consider the BGG⁺ scheme. Its ciphertext encodes the attributes ${{\textbf{x}}}$ and message $\mu$ as follows.

$$\begin{aligned} \mathrm{BGG:}\qquad {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{A}}}+ {{\textbf{e}}}^{{\textsf{T}}}, \quad {{\textbf{s}}}^{{\textsf{T}}}\bigl (\smash {\overbrace{({{\textbf{A}}}_1|| \cdots ||{{\textbf{A}}}_\ell )}^{{{\textbf{B}}}}} - {{\textbf{x}}}\otimes {{\textbf{G}}}\bigr ) + ({{\textbf{e}}}')^{{\textsf{T}}}, \quad {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{v}}}+ e'' + \mu \lfloor q/2 \rceil . \end{aligned}$$

One can homomorphically evaluate any circuit f on the attribute encoding to obtain ${{\textbf{s}}}^{{\textsf{T}}}({{\textbf{B}}}_f - f(x) {{\textbf{G}}}) + {{\textbf{e}}}_f^{{\textsf{T}}}$. To decrypt, the secret key ${\textsf{sk}}_f$ simply is a short vector ${{\textbf{r}}}_{{{\textbf{A}}},f}$ satisfying $({{\textbf{A}}}||{{\textbf{B}}}_f){{\textbf{r}}}_{{{\textbf{A}}},f} = {{\textbf{v}}}$, which can be sampled using a trapdoor ${\textbf{T}}_{{{\textbf{A}}}}$ for ${{\textbf{A}}}$. This approach however has two drawbacks:

• Difficulty towards Constant-Size Keys. The short vector ${{\textbf{r}}}_{{{\textbf{A}}},f}$ contained in the secret key ${\textsf{sk}}_f$ has size ${\text {poly}}(d, \lambda )$. This is because it has dimension $m = n \log q$ for $\log q = {\text {poly}}(d, \lambda )$ and entries of magnitude exponential in d.

• Difficulty towards Adaptive Security. The security proof relies on the ability to simulate trapdoors for these matrices ${{\textbf{A}}}||{{\textbf{B}}}_f$ corresponding to secret keys that are unauthorized to decrypt the challenge ciphertext with attribute ${{\textbf{x}}}^*$, that is $f({{\textbf{x}}}^*) = 1$. However, to do so, current technique plants ${{\textbf{x}}}^*$ in the public matrices ${{\textbf{A}}}_i$’s (contained in ${\textsf{mpk}}$), leading to selective security. Note that even with the stronger adaptive LWE assumption, it is unclear how to simulate these trapdoors in another way.

Towards constant-size keys and adaptive security, our construction circumvents the use of lattice trapdoors all together. At a high level, we turn attention to a much weaker lattice primitive called attribute-based laconic function evaluation (AB-LFE) [36], and lifts it to a KP-ABE scheme for circuits using pairing. AB-LFE is an interactive protocol where a receiver sends a digest of a function, which is exactly the matrix ${{\textbf{B}}}_f$ in BGG. The sender then encodes the attribute ${{\textbf{x}}}$ and message $\mu$ as follows.

where ${{\textbf{r}}}= {{\textbf{G}}}^{-1}({{\textbf{a}}})$ is the bit decomposition of a random vector ${{\textbf{a}}}$. Security guarantees that the encoding reveals only the output $f({{\textbf{x}}})$. At a first glance, the LFE encoding appears the same as BGG, but the novelty is in details. Since the LFE encoding depends on ${{\textbf{B}}}_f$ (and hence f), it can be generated without using lattice trapdoors — the short vector ${{\textbf{r}}}$ sampled first, and ${{\textbf{B}}}_f {{\textbf{r}}}$ computed next. When $f(x)=1$, the hiding of $\mu$ follows directly from the pseudorandomness of LWE samples ${{\textbf{s}}}^{{\textsf{T}}}(({{\textbf{A}}}_1|| \cdots ||{{\textbf{A}}}_\ell ) - {{\textbf{x}}}\otimes {{\textbf{G}}})) + {{\textbf{e}}}'$ and ${{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+ e'''$. When ${{\textbf{x}}}$ is adaptively chosen, security follows naturally from adaptive LWE.

However, AB-LFE is able to avoid lattice trapdoor only because it is significantly weaker than ABE, or even 1-key ABE: 1) its message encoding depends on ${{\textbf{B}}}_f$ (unknown at ABE encryption time), and 2) it is only secure for a single function. Our next challenge is lifting AB-LFE back to full ABE, for which we use pairing.

More specifically, we first modify the AB-LFE scheme of [36] to obtain a nearly linear secret sharing scheme for circuits. It contains two parts.

$$\begin{aligned} \text {Our LSS encoding:} \qquad L_{{\textbf{x}}}&{}= {{\textbf{s}}}^{{\textsf{T}}}\bigl (({{\textbf{A}}}_1|| \cdots ||{{\textbf{A}}}_\ell ) - {{\textbf{x}}}\otimes {{\textbf{G}}}\bigr ) + ({{\textbf{e}}}')^{{\textsf{T}}}\bmod q,\\ L_f&{}= {{\textbf{s}}}^{{\textsf{T}}}\textsf{Round}( {{\textbf{B}}}_f {{\textbf{r}}}) + e'' + \mu \lfloor p/2 \rceil \bmod p. \end{aligned}$$

Note that we round ${{\textbf{B}}}_f {{\textbf{r}}}$ from modulus q of ${\text {poly}}(d)$ length to p of ${\text {poly}}(\lambda )$ length so that the component $L_f$ in the secret sharing that depends on f and $\mu$ has constant size, which is the key towards constant-size ABE keys. To solve the problem that $L_f$ requires knowledge of ${{\textbf{B}}}_f$ unknown at encryption time, we use a pairing-based inner-product functional encryption (IPFE) to compute $L_f$ in the exponent, by viewing it as inner product $L_f = \langle {{\textbf{s}}}^{{\textsf{T}}}||\mu \lfloor p/2 \rceil , \textsf{Round}( {{\textbf{B}}}_f {{\textbf{r}}}) || 1\rangle$, where the two vectors are known respectively at ABE encryption and key generation time. To overcome that AB-LFE only guarantees security for a single $L_f$. We follow the idea of [3, 4] to compute $\delta _f\cdot L_f$ in the exponent instead, where $\delta _f$ is an independent and random scalar chosen at key generation time. In GGM, the presence of $\delta _f$ prevents adversaries from meaningfully “combining” information from multiple $L_f$ for different f.

Comparison with [3, 4]. Our way of combining lattice-based LSS with pairing-based IPFE differs from that of [3, 4], in order to address unique technical difficulties. To start with, they use an LSS scheme based on the BGG ABE and inherits the selective security. Second, our KP-ABE scheme reveals part of the secret h $L_{{\textbf{x}}}$ in the clear (in ciphertext), and only compute $L_f$ in the exponent, whereas [3, 4] computes the entire LSS in the exponent. This is because the decryptor needs to perform the non-linear rounding operation on the result of homomorphic evaluation on $L_{{\textbf{x}}}$, in order to obtain $\textsf{Round}({{\textbf{s}}}^{{\textsf{T}}}({{\textbf{B}}}_f-f(x){{\textbf{G}}}){{\textbf{r}}}+ {{\textbf{e}}}^{{\textsf{T}}}_f)$ for decryption. Keeping $L_{{\textbf{x}}}$ in the clear allows rounding, but renders security harder to prove.

Furthermore, the security proof of AB-LFE relies on noise flooding — their technique can only show that $L_f + \tilde{e}$ is secure for a super-polynomially large $\tilde{e}$. But noise flooding is incompatible with computing $L_f$ in the exponent, since we must keep noises polynomially small in order for decryption to be efficient (which performs discrete logarithm). Without noise flooding, we cannot prove that unauthorized shares are pseudorandom as in [36]. Nevertheless, we show that unauthorized shares are “entropic”, captured by a new notion called non-annihilability, and that the “entropic” $L_f$ computed in the exponent still hides the message $\mu$. The proof of non-annihilability combines techniques from AB-LFE and leakage simulation [16, 25]. The work of [3, 4] does not encounter issues with super-polynomial noises.

We add a note on our doubly succinct CP-ABE for Boolean formulae. It is closer to the CP-ABE scheme of [3, 4]. However, to obtain constant-size keys, we rely on an IPFE scheme with strong (selective) simulation security — it enables simultaneously simulating a polynomial number k of ciphertexts, by programming k inner products for every secret key, while keeping the secret key constant-size (independent of k). Such strong simulation is impossible in the standard model following an incompressibility argument. We show that this is possible in GGM, in particular, the IPFE scheme of [1] satisfies it. IPFE with such strong simulation may find other applications.

Next, we explain our ideas in more details.

Combining LSS with IPFE. An IPFE scheme enables generating keys ${\textsf{isk}}({{\textbf{v}}}_j)$ and ciphertexts ${\textsf{ict}}({{\textbf{u}}}_i)$ associated with vectors ${{\textbf{v}}}_j, {{\textbf{u}}}_i \in {\mathbb {Z}}_p^N$ such that decryption reveals only their inner products $\langle {{\textbf{u}}}_i,{{\textbf{v}}}_j\rangle$ and hides all other information about ${{\textbf{u}}}_i$ encrypted in the ciphertexts (whereas ${{\textbf{v}}}_j$ associated with the keys are public). It can be based on a variety of assumptions such as MDDH, LWE, or DCR [1, 2].

A nearly linear secret sharing scheme enables generating shares $L_f, L_0, \{L_i^b\}$ associated with a policy f and some secret $\mu$, such that for any input ${{{\textbf{x}}}\in {\{0,1\}}^\ell }$, its corresponding subset of shares ${L^{{{\textbf{x}}}} = (L_0,\{L_i^{{{\textbf{x}}}[i]}\})}$, together with $L_f$ can be used to approximately reconstruct the secret $\mu$ if and only if ${f({{\textbf{x}}}) = 0}$:

$$\begin{aligned} (L_f, L_0, \{L_i^b\}_{i \in [\ell ], b \in \{0,1\}}) \leftarrow {}&{\textsf{Share}}(f, \mu ; {{\textbf{r}}})\\ f(x)=0\quad \Longrightarrow&\quad \mu \approx {\textsf{Recon}}(f, {{\textbf{x}}}, L_f, L^{{{\textbf{x}}}}). \end{aligned}$$

Near linearity means that ${\textsf{Recon}}$ is linear in the shares $L_f,L^{{{\textbf{x}}}}$ and that its output is close to the secret $\mu$.

How can we combine these two primitives to construct a KP-ABE? We require $L_0, \{L_i^b\}$ to be independent of f and $\mu$, and $L_f$ to be linear in $\mu$ and the randomness ${{\textbf{r}}}$ of ${\textsf{Share}}$. The first requirement allows us to simply put $L^{{\textbf{x}}}$ in the ciphertext. The second requirement allows us to encode $\mu , {{\textbf{r}}}$ into ${\textsf{ict}}$’s and the coefficients (of $L_f$ as a function of $\mu ,{{\textbf{r}}}$) into ${\textsf{isk}}$’s, so that their inner product is exactly $L_f$. For convenience, we write $[\![x]\!]_i$ for $g_i^x$ and use additive notation for the groups. The idea is as follows:

$$\begin{aligned} \left. \begin{aligned} {\textsf{kp}}.{\textsf{sk}}_f:\quad&[\![\delta ]\!]_2,\quad {\textsf{isk}}(\mathrm{coefficients\;of\;}\delta L_f)\\ {\textsf{kp}}.{\textsf{ct}}_{{\textbf{x}}}:\quad&L^{{\textbf{x}}},\quad \;\; {\textsf{ict}}(\mu , {{\textbf{r}}}) \end{aligned} \quad \right\} \quad [\![\delta L_f]\!]_{{\textrm{T}}}\;\textrm{and}\;L^{{\textbf{x}}}. \end{aligned}$$

(1)

If ${f({{\textbf{x}}}) = 0}$, the linear reconstruction can be carried out in the exponents to approximately obtain $[\![\delta \mu ]\!]_{{\textrm{T}}}$. Decryption enumerates all possible errors to recover $\mu$ exactly. We stress again that different from [3, 4], we keep $L_{{\textbf{x}}}$ in the clear (in the ciphertext), instead of computing the entire secret sharing $L_{{\textbf{x}}}, L_f$ in the exponent, which is important for achieving constant-size keys, but makes proving security more difficult.

We construct a secret sharing scheme that features $L_f$ of constant size, which translates to KP-ABE with constant-size secret keys.

Combining secret sharing and IPFE to construct CP-ABE is similar. We can encode $L_0, \{L_i^b\}$ in ${\textsf{ict}}$’s, and a “selection” vector according to ${{\textbf{x}}}$ in ${\textsf{isk}}$’s, so that their inner products are exactly $L^{{\textbf{x}}}$:

$$\begin{aligned} \left. \begin{aligned} {\textsf{cp}}.{\textsf{sk}}_{{\textbf{x}}}:\quad&[\![\delta ]\!]_2,\qquad {\textsf{isk}}(\delta \cdot \;\textrm{selection}\; \textrm{vector}\; \textrm{for}\; {{\textbf{x}}}) \\ {\textsf{cp}}.{\textsf{ct}}_f:\quad&[\![L_f]\!]_1,\quad \; {\textsf{ict}}(L_0, \{L_i^b\}). \end{aligned} \quad \right\} \quad [\![\delta L_f]\!]_{{\textrm{T}}}\; \textrm{and }\;[\![\delta L^{{\textbf{x}}}]\!]_{{\textrm{T}}}. \end{aligned}$$

(2)

We use an IPFE scheme with secret keys of constant size, independent of the vector dimension or the number of ciphertexts, and a secret sharing scheme whose $L_f, L^{{\textbf{x}}}$ grows only with the input length $|{{\textbf{x}}}|$. This translates to CP-ABE with double succinctness.

Lattice-Based Nearly Linear Secret Sharing. The BGG⁺ ABE scheme introduces an important homomorphic evaluation procedure: Given public matrices ${{\textbf{B}}}= ({{\textbf{A}}}_1 || \cdots || {{\textbf{A}}}_{|{{\textbf{x}}}|})$, and the following encoding of an input ${{\textbf{x}}}$, one can homomorphically evaluate any circuit f on the encodings to obtain an encoding of the output.

$$\begin{aligned} {{\textbf{c}}}^{{\textsf{T}}}&{}={}{{\textbf{s}}}^{{\textsf{T}}}({{\textbf{B}}}- (1,{{\textbf{x}}})\otimes {{\textbf{G}}}) + {{\textbf{e}}}_2^{{\textsf{T}}}, \nonumber \\ {\textsf{EvalCX}}({{\textbf{c}}}_2, f, {{\textbf{x}}})&{}= {{\textbf{c}}}_f^{{\textsf{T}}}= {{\textbf{s}}}^{{\textsf{T}}}({{\textbf{B}}}_f - f({{\textbf{x}}}){{\textbf{G}}}) + {{\textbf{e}}}_f^{{\textsf{T}}}, \text { where } {\textsf{EvalC}}({{\textbf{B}}},f) = {{\textbf{B}}}_f . \end{aligned}$$

(3)

As discussed before, the BGG⁺ ABE scheme uses lattice trapdoor simulation technique, which we try to avoid in order to get constant-size key and adaptive security.

We hence turn to using the weaker primitive of AB-LFE scheme introduced by [36]. It is a two-party protocol between a sender and a receiver who share the LWE public matrix ${{\textbf{B}}}$ as the common reference string. The receiver first computes a digest ${{{\textbf{B}}}_f = {\textsf{EvalC}}({{\textbf{B}}},f)}$ for a function f and sends it to the sender. Upon receiving the digest, the sender masks a message $\mu$ by an LWE sample $c_0 = {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{v}}}_f + e + \mu \lfloor q/2\rceil$, where ${{\textbf{r}}}= {{\textbf{G}}}^{-1}({{\textbf{a}}})$ and ${{\textbf{v}}}_f = {{\textbf{B}}}_f {{\textbf{r}}}$ are analogues of ${{\textbf{r}}}_{{{\textbf{A}}},f}$ and ${{\textbf{v}}}$ in BGG⁺. It also encodes an attribute ${{\textbf{x}}}$ into LWE samples ${{\textbf{c}}}_1$ as described below.

To decrypt, first run ${\textsf{EvalCX}}({{\textbf{c}}}_1, f, {{\textbf{x}}})$ to obtain ${{{\textbf{c}}}_f={{\textbf{s}}}^{{\textsf{T}}}({{\textbf{B}}}_f - f({{\textbf{x}}}){{\textbf{G}}}) + {{\textbf{e}}}_f^{{\textsf{T}}}}$. If ${f({{\textbf{x}}}) = 0}$, the decryptor can compute ${c_0 - {{\textbf{c}}}_f^{{\textsf{T}}}{{\textbf{r}}}= \mu \lfloor q/2\rceil + (e - {{\textbf{e}}}_f^{{\textsf{T}}}{{\textbf{r}}})}$ and round it to recover $\mu$.

Observe that the above scheme can be viewed as a nearly linear secret sharing scheme, where the shares chosen by ${{\textbf{x}}}$ are exactly ${{{\textbf{L}}}^{{\textbf{x}}}= {{\textbf{c}}}_1}$ and the shares dependent on f and $\mu$ is ${L_f = c_0}$. At the moment, the bit-length of $L_f$ is ${\Theta }(\log q)$. Since the noise growth during the homomorphic evaluation is exponential to the depth of the computation, q is a ${\text {poly}}(d, \lambda )$-bit modulus in order to accommodate for the noise growth. We next turn to reducing the size of $L_f$ to a constant independent of d.

Rounding to Make $\boldsymbol{L_f}$ Constant-Size. Since the encrypted message is only a single bit, we can afford to lose a lot of precision in the above decryption process. In particular, the scheme is still correct if we round down the digest ${{\textbf{B}}}_f$ to a much smaller, depth-independent, modulus ${p \ll q}$, and change $c_0$ to use the rounded digest (while keeping ${{\textbf{c}}}_1^{{\textsf{T}}}$ unchanged):

$$\begin{aligned} c'_0 = {{\textbf{s}}}^{{\textsf{T}}}\lfloor {{\textbf{B}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \mu \lfloor p/2\rceil + e \qquad \textrm{over}\ {\mathbb {Z}}_p. \end{aligned}$$

During decryption, one now computes, over ${\mathbb {Z}}_p$,

$$\begin{aligned} c'_0 - \lfloor {{\textbf{c}}}^{{\textsf{T}}}_f {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p ={}&c'_0 - \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}}) + f({{\textbf{x}}}){{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+ {{\textbf{e}}}^{{\textsf{T}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p \nonumber \\ ={}&c'_0 - \bigl ({{\textbf{s}}}^{{\textsf{T}}}\lfloor {{\textbf{B}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + f({{\textbf{x}}})\lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}\rceil _p + {} \underbrace{\lfloor {{\textbf{e}}}^{{\textsf{T}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p}_{e'_f} {} + e_s \bigr ) \nonumber \\ ={}&\mu \lfloor p/2\rceil - f({{\textbf{x}}})\lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}\rceil _p + (e - e'_f - e_s), \end{aligned}$$

(4)

where the rounding error $e_s$ is of magnitude ${|e_s| ={\Theta }(\Vert {{\textbf{s}}}\Vert _1)}$. As long as the error terms are much smaller than p/2, when ${f({{\textbf{x}}}) = 0}$, one can still recover $\mu$. We can now recast the above rounded AB-LFE scheme into a secret sharing scheme with $L_f$ of bit-length ${\Theta }(\log p)$, independent of depth d. (Only the larger modulus q will, and thus ${{\textbf{e}}}_f$ itself can, grow with d.)

$$\begin{aligned} \begin{array}{rll} {\textsf{SS}}.{\textsf{pp}}:\quad &{} {{\textbf{a}}},{{\textbf{B}}}&{}\qquad \mod q;\\ L_f:\quad &{} c'_0 = {{\textbf{s}}}^{{\textsf{T}}}\lfloor {{\textbf{B}}}_f {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \mu \lfloor p/2\rceil + e &{}\qquad \mod p\ll q;\\ {{\textbf{L}}}^{{\textbf{x}}}:\quad &{} {{\textbf{c}}}^{{\textsf{T}}}_1 = {{\textbf{s}}}^{{\textsf{T}}}\bigl ({{\textbf{B}}}- (1,{{\textbf{x}}})\otimes {{\textbf{G}}}\bigr ) + {{\textbf{e}}}^{{\textsf{T}}}_1 &{}\qquad \mod q. \end{array} \end{aligned}$$

As shown in Eq. (1), to obtain KP-ABE, we will use a pairing-based IPFE to compute $L_f$ in the exponent. Specifically, the IPFE secret key ${\textsf{isk}}$ encodes $(\lfloor {{\textbf{B}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p,\lfloor p/2\rceil )$, and the IPFE ciphertext ${\textsf{ict}}$ encodes $({{\textbf{s}}}^{{\textsf{T}}}, \mu )$. Together, they decrypt to exactly $[\![L_f]\!]_{{\textrm{T}}}$. Since both vectors live in ${\mathbb {Z}}_p$, the KP-ABE key, consisting of only ${\textsf{isk}}$, is of size independent of d. Our secret sharing scheme is summarized below. It turns out that arguing security is actually tricky and requires additional modification.

Non-Annihilability by Leakage Simulation. However, using AB-LFE creates a further complication, as its security relies on flooding the $e'_f,e_s$ terms (which may contain information of ${{\textbf{s}}}$ and ${{\textbf{x}}}$) with e, in order to prove pseudorandomness of $L_f$. By Eqs. (3, 4), when ${f({{\textbf{x}}}) =1}$ we have

$$\begin{aligned} L_f {}={}&\lfloor {\textsf{EvalCX}}({{\textbf{L}}}^{{{\textbf{x}}}},f,{{\textbf{x}}})^{{\textsf{T}}}{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p \nonumber \\&{} - \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+e_a\rceil _p + \mu \lfloor p/2\rceil + (e - e'_f - e_s). \end{aligned}$$

(5)

Observe that in the above, for later convenience, an additional polynomial LWE noise $e_a$ is introduced in the term $\lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+e_a\rceil _p$ (which by rounding simply equals to $\lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}\rceil _p$).

At this point, in order to show that $L_f$ is pseudorandom, given that ${{\textbf{x}}}$ is selected before ${\textsf{Setup}}$, one could program the public matrices as ${{{\textbf{A}}}_i = {{\textbf{A}}}'_i + x_i{{\textbf{G}}}}$ according to ${{\textbf{x}}}$, where ${{\textbf{B}}}' = ({{\textbf{A}}}'_0, .., {{\textbf{A}}}'_\ell )$ are sampled at random. And one would hope to apply LWE to argue that

$$\begin{aligned} {{\textbf{L}}}_{{{\textbf{x}}}} = {{\textbf{s}}}^{{\textsf{T}}}({{\textbf{B}}}+ (1,{{\textbf{x}}})\otimes {{\textbf{G}}}) +{{\textbf{e}}}^{{\textsf{T}}}_1 = {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}' +{{\textbf{e}}}^{{\textsf{T}}}_1, \end{aligned}$$

and $({{{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+e_a})$ are jointly pseudorandom. However, the noise terms $e'_f$ and $e_s$ may leak information about ${{\textbf{e}}}_2$ and ${{\textbf{s}}}$.

The solution in [36] is noise flooding. By setting e to be super-polynomially larger than $({e'_f + e_s})$, we have ${e-e'_f - e_s \approx _{\textrm{s}}e}$. By LWE, we can now switch ${{\textbf{L}}}^{{{\textbf{x}}}}$ and $({{{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+ e_a})$ to random and conclude that $L_f$ is pseudorandom.

However, the unique challenge here is that $L_f$ is going to be computed in the exponent of the pairing group, and decryption only recovers $({\mu \lfloor p/2\rceil + e})$ in the exponent. When e is super-polynomial, we can no longer extract $\mu$ out of the exponent. Our solution is avoiding flooding altogether and remove the noise e from $L_f$. As such, we cannot prove pseudorandomness of $L_f$, but only a weaker security notion that we call non-annihilability (for $L_f$). This notion captures that $L_f$ is still entropic.

Non-Annihilability. Non-annihilability requires that no adversary, after seeing ${{\textbf{L}}}^{{{\textbf{x}}}}$ (but not $L_f$) can come up with an affine function $\gamma$ such that $\gamma (L_f) = 0$. As we will see, this security notion, combined with GGM, suffices for our proof.

Towards proving non-annihilability, we want to show that $L_f$ is highly entropic (even without e). Our idea is to view the noises $e'_f, e_s$ as leakage of the randomness that generates ${{\textbf{L}}}^{{{\textbf{x}}}}$ and $({{{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+ e_a})$ as well as the other information, and simulate $e'_f, e_s$ using leakage simulation [16, 25]. Crucially, because $e'_f, e_s$ have polynomial range, the simulation can run in polynomial time. More precisely, the leakage simulation lemma of [16] states that for any joint distribution ${(X, Z) \sim {\mathcal {D}}}$ (Z viewed as leakage of randomness for generating X), adversary size bound s, and error bound $\epsilon$, there is a simulator h simulating Z as h(X) such that (X, Z) and (X, h(X)) are $(s,\epsilon )$-indistinguishable. Furthermore, the running time of h is $\textrm{O}(s\epsilon ^{-2}2^{|Z|})$. Suppose for contradiction that there is an adversary ${\mathcal {A}}$ of size ${s={\text {poly}}(\lambda )}$ winning the non-annihilability game with probability ${2\epsilon \ge 1/{\text {poly}}(\lambda )}$. Consider the joint distribution ${\mathcal {D}}$ of running the game with ${\mathcal {A}}$, defined in the first line below:

$$\begin{aligned} \begin{array}{rll} {\mathcal {D}}\rightarrow {}&{} \{ X=({\textsf{pp}},{{\textbf{x}}},{{\textbf{L}}}^{{{\textbf{x}}}},f,\mu ,\gamma , \psi ={{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+e_a), &{}\quad Z=e'_f+e_s\} \\ {}\overset{s,\epsilon }{\approx }\text {Hybrid 1}\rightarrow {}&{} \{ X=({\textsf{pp}},{{\textbf{x}}},{{\textbf{L}}}^{{{\textbf{x}}}},f,\mu ,\gamma , \psi ={{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+e_a), &{}\quad Z=h(X)\} \\ {}{\approx }\text {Hybrid 2}\rightarrow {}&{} \{ X=({\textsf{pp}},{{\textbf{x}}},{{\textbf{L}}}^{{{\textbf{x}}}}\ \textrm{random},f,\mu ,\gamma , \psi \ \textrm{random}), &{}\quad Z=h(X) \}. \end{array} \end{aligned}$$

Using (X, Z), one can emulate $L_f$ as (cf. Eq. (5) with e removed and $({e'_f+e_s})$ replaced by Z)

$$\begin{aligned} L_f = \lfloor {\textsf{EvalCX}}({{\textbf{L}}}^{{{\textbf{x}}}},f,{{\textbf{x}}}) {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p - \lfloor \psi \rceil _p + \mu \lfloor p/2\rceil - Z. \end{aligned}$$

Since ${Z = e'_f+e_s}$, and $s, \epsilon ^{-1}$ are all polynomially bounded, we can simulate Z by h(X) in polynomial time (Hybrid 1). Now, we can apply LWE to switch ${{\textbf{L}}}^{{{\textbf{x}}}},{\psi = {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{a}}}+ e_a}$ to random (Hybrid 2). At this point, it seems that $L_f$ is just pseudorandom by the pseudorandomness of $\psi$. However, there is a subtle issue: $Z = h(X)$ depends on $\psi$ contained in X, and hence $({\lfloor \psi \rceil _p -Z})$ may not be pseudorandom, and neither may be $L_f$. Despite this dependency, thanks again to $({e'_f+e_s})$, thus h(X), being polynomially bounded, $({-\lfloor \psi \rceil _p + h(X)})$ still has almost full entropy (up to a logarithmic loss). Therefore, the probability that $L_f$ is annihilated by an affine function $\gamma$ chosen by ${\mathcal {A}}$ before $\psi$ is randomly sampled is negligible. This gives a contradiction and concludes the proof of non-annihilability.

Multi-Key Security of KP-ABE in GGM. Our KP-ABE scheme combines an IPFE scheme with the secret sharing scheme described above. As described before, in our KP-ABE scheme, we only compute the $L_f$ part of secret sharing using IPFE, and leave the ${{\textbf{L}}}^{{{\textbf{x}}}}$ part in the clear so that rounding can be performed. To achieve multi-key security, we further employ the idea from [3, 4] to “isolate” each ABE secret key in GGM by multiplying it with a fresh random element $\delta$.

$$\begin{aligned} \left. \begin{array}{rrr} {\textsf{kp}}.{\textsf{sk}}: &{}\quad [\![\delta ]\!]_2, &{}\quad {\textsf{isk}}\bigl ( [\![\delta (\lfloor {{\textbf{B}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p, \lfloor p/2\rceil )]\!]_2 \bigr ) \\ {\textsf{kp}}.{\textsf{ct}}: &{}\quad {{\textbf{L}}}^{{{\textbf{x}}}}, &{}\quad {\textsf{ict}}([\![({{\textbf{s}}}, \mu )]\!]_1) \end{array} \ \right\} \textrm{decrypt}\; \textrm{to}\; [\![\delta L_f]\!]_{{\textrm{T}}}. \end{aligned}$$

The decryption algorithm first computes IPFE decryption to recover $[\![\delta L_f]\!]_{{{\textrm{T}}}}$. It then computes (homomorphically in the exponent of $g_{{\textrm{T}}}$)

$$\begin{aligned}{}[\![\delta L_f]\!]_{{{\textrm{T}}}} - [\![\delta ]\!]_{{\textrm{T}}} \lfloor {{\textbf{c}}}^{{\textsf{T}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p = [\![\delta \bigl (\mu \lfloor p/2\rceil -(e'_f+e_s)\bigr )]\!]_{{\textrm{T}}}. \end{aligned}$$

Since the noise $({e'_f+e_s})$ has a polynomial range, the decryption algorithm enumerates all its possible values to recover $\mu$.

Multi-key security, at a high level, relies on the fact that in GGM, an adversary can only learn information about $[\![\delta L_f]\!]_{{\textrm{T}}}$ by submitting zero-test queries of affine functions. When the adversary attacks multiple keys, it essentially submits zero-test queries over the terms $\{\delta _j L_{f_j}\}$. Let $\gamma (\{\delta _j L_{f_j}\})$ be any zero-test query submitted by ${\mathcal {A}}$, we can view it as a degree-1 polynomial over $\delta _j$’s:

$$\begin{aligned} \gamma (\{\delta _j L_{f_j}\}) = \sum _j \gamma _j(L_{f_j}) \delta _j + \gamma _0, \end{aligned}$$

where $\gamma _j(L_{f_j})$ is the coefficient of $\delta _j$. Since each $\delta _j$ is sampled independently at random, by Schwartz–Zippel, with all but negligible probability, $\gamma$ evaluates to zero only if all $\gamma _j$’s evaluate to zero. In other words, the adversary is effectively constrained to annihilate each $L_{f_j}$ individually. By the non-annihilability for $L_f$, if $\gamma _j$ is not the zero function, it evaluates to non-zero with overwhelming probability. Hence the adversary learns no information of each $L_{f_j}$ and the message $\mu$ encoded in them.

Summary of Our KP-ABE. Combining the above secret sharing scheme with an IPFE scheme, we obtain a KP-ABE scheme for bounded-depth circuits as summarized above.

We note that our KP-ABE scheme achieves the same asymptotic ciphertext compactness as the BGG⁺ scheme. Let d be an upper bound on the depth of the policy f, then ${|{\textsf{ct}}| = {\text {poly}}(\lambda , d)|{{\textbf{x}}}|}$. The secret keys of our scheme contains only $\textrm{O}(1)$ group elements, in fact only three using the IPFE scheme of [2] in a group of order p. We set ${\log p = {\text {poly}}(\lambda )}$ and hence obtain constant size keys.

Security Sketch for KP-ABE. Finally, for completeness, we add a security sketch that puts the previous ideas together. We emphasize that we only use GGM in the last argument, when we need to isolate the share $L_{f_j}$ for each f.

The selective security game of ABE (summarized in ${\textsf{H}}_0$ below) at a high level is as follows: The adversary ${\mathcal {A}}$ first decides a challenge attribute ${{\textbf{x}}}^*$ before receiving a master public key ${\textsf{mpk}}$ and a ciphertext ${\textsf{ct}}^*$ from the challenger ${\mathcal {C}}$. It is then allowed to repeatedly query secret keys ${\textsf{sk}}_j$ for functions $f_j$. The adversary wins if every queried function $f_j$ satisfies $f_j({{\textbf{x}}}^*) \ne 0$, and if it guesses the encrypted bit $\mu$ correctly.

Note that we can generate the IPFE ciphertext ${\textsf{ict}}([\![{{\textbf{s}}},\mu ]\!]_1)$ before any IPFE secret keys ${\textsf{isk}}([\![\delta (\lfloor {{\textbf{B}}}_{f_j}{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p, \lfloor p/2\rceil )]\!]_2)$. Relying on the selective simulation security of IPFE, we can (as summarized in ${\textsf{H}}_1$ above) replace ${\textsf{ict}}([\![{{\textbf{s}}},\mu ]\!]_1)$ with a simulated ciphertext $\widetilde{{\textsf{ict}}}(\bot )$, and each ${\textsf{isk}}([\![\delta _j(\lfloor {{\textbf{B}}}_{f_j}{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p,\lfloor p/2\rceil )]\!]_2)$ with a simulated secret key $\widetilde{{\textsf{isk}}}([\![\delta _j L_{f_j}]\!]_2)$ using their inner products.

In GGM, we can now argue that ${\mathcal {A}}$ only learns information about $\mu$ through zero-test queries over $\{\delta _j L_{f_j}\}$. As argued before, by the non-annihilability of $L_f$, the adversary learns no information of $\mu$.

Building Doubly Succinct CP-ABE. To build a CP-ABE scheme we need a different secret sharing construction, because the previous rounding solution does not work anymore. As described in Eq. (2), in the CP case, we use IPFE to compute ${{\textbf{L}}}^{{\textbf{x}}}$ in the exponent, hence cannot perform rounding on it. Without rounding, the ${{\textbf{e}}}_f$ term, as a result of ${\textsf{EvalCX}}$, in Eq. (4) becomes super-polynomial. This again makes the ABE decryption inefficient.

Fortunately, for Boolean formulae, the work of [23] develops specialized homomorphic evaluation procedures ${\textsf{EvalF}},{\textsf{EvalFX}}$ that ensure the evaluation noise ${{\textbf{e}}}_f$ has a polynomial range. Therefore, our secret sharing scheme for CP removes the rounding and replaces ${\textsf{EvalC}}, {\textsf{EvalCX}}$ by ${\textsf{EvalF}}, {\textsf{EvalFX}}$. We summarize our modified secret sharing scheme below (${\textsf{Setup}}, {\textsf{ShareX}}$ are kept the same).

As noted before, in our CP-ABE scheme we use IPFE to compute ${{\textbf{L}}}^{{{\textbf{x}}}}$. To achieve double succinctness, we carefully implement a pair of functions ${\textsf{Sel}}, {\textsf{Encode}}$ using an IPFE with constant-size ${\textsf{isk}}$’s, such that ${\textsf{Sel}}([\![{{\textbf{x}}}]\!]_2)$ and ${\textsf{Encode}}([\![{{\textbf{L}}}_0,\{{{\textbf{L}}}_i^b\}]\!]_1)$ decrypts exactly to $[\![{{\textbf{L}}}^{{{\textbf{x}}}}]\!]_{{\textrm{T}}}$. We obtain a CP-ABE scheme for Boolean formulae as summarized below.

We now describe the ${\textsf{Sel}}, {\textsf{Encode}}$ functions. Let $\ell = |{{\textbf{x}}}|$ denote the length of ${{\textbf{x}}}$. The ${\textsf{Sel}}$ algorithm first computes the “selection vector” for ${{\textbf{x}}}$ as

$$\begin{aligned} {{\textbf{v}}}= (1, 1-{{\textbf{x}}}[1],{{\textbf{x}}}[1], \dots , 1-{{\textbf{x}}}[i], {{\textbf{x}}}[i], \dots ), \end{aligned}$$

and then computes an IPFE secret key ${\textsf{isk}}([\![{{\textbf{v}}}]\!]_2)$. The ${\textsf{Encode}}$ algorithm places input shares in the matrix

$$\begin{aligned} \begin{pmatrix} {{\textbf{L}}}_0 &{} {\textbf{0}} &{} {\textbf{0}} &{} \cdots &{} {\textbf{0}} &{} {\textbf{0}} &{} \cdots &{} {\textbf{0}} &{} {\textbf{0}} \\ {\textbf{0}}&{} {{\textbf{L}}}_1^0 &{} {{\textbf{L}}}_1^1 &{} \cdots &{} {\textbf{0}} &{} {\textbf{0}} &{} \cdots &{} {\textbf{0}} &{} {\textbf{0}} \\ {\textbf{0}}&{} \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots \\ {\textbf{0}}&{} {\textbf{0}} &{} {\textbf{0}} &{} \cdots &{} {{\textbf{L}}}_i^0 &{} {{\textbf{L}}}_i^1 &{} \cdots &{} {\textbf{0}} &{} {\textbf{0}} \\ {\textbf{0}}&{} \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots &{} \ddots &{} \vdots &{} \vdots \\ {\textbf{0}}&{} {\textbf{0}} &{} {\textbf{0}} &{} \cdots &{} {\textbf{0}} &{} {\textbf{0}} &{} \cdots &{} {{\textbf{L}}}_\ell ^0 &{} {{\textbf{L}}}_\ell ^1 \end{pmatrix} \end{aligned}$$

and computes one IPFE ciphertext for each row ${{\textbf{u}}}_{l}$ of the matrix. Our CP-ABE has both succinct keys and ciphertexts: ${|{\textsf{sk}}| = \textrm{O}(1)}$ and ${|{\textsf{ct}}| = {\text {poly}}(\lambda )|{{\textbf{x}}}|^2}$.

Simulation Security for IPFE in GGM. Similar to the security proof for KP-ABE, our security proof for CP-ABE requires selective simulation security of IPFE.

Note that above we need to simulate multiple IPFE ciphertexts and program all their decryption outcome ${{\textbf{L}}}^{{{\textbf{x}}}}$ in each secret key. This is possible using existing IPFE schemes [2, 32], but at the cost of having the secret key size proportional to the number $k = |{{\textbf{L}}}^{{{\textbf{x}}}}|$ of ciphertexts to be simulated. However, we aim for constant-size secret keys (independent of k). Unfortunately, in the standard model, it is impossible to achieve simulation security for k ciphertexts if the secret key is shorter than k bits by an incompressibility argument [12]. We show that simulation security for unbounded polynomially many ciphertexts can nevertheless be achieved with constant-size secret keys in the GGM. In particular, the IPFE scheme of [1], whose secret key contains a single group element, satisfies it. Roughly speaking, in the GGM, an adversary only learns information about values in the exponent through zero-test queries over the pairings of keys and ciphertexts, which the simulator can answer by translating them into zero-test queries over the inner products. As a side note, we can in fact prove adaptive simulation security for the [1] IPFE scheme, though our ABE scheme only relies on selective simulation security.

Achieving Adaptive Security. Examining the security sketch for KP-ABE, we observe that in our construction, the ${\textsf{ict}}([\![{{\textbf{s}}}, \mu ]\!]_1)$ component of ciphertext ${\textsf{ct}}^*$ doesn’t depend on the challenge attribute ${{\textbf{x}}}^*$. This means that even in the adaptive KP-ABE game, where ${{\textbf{x}}}^*$ is decided after some key queries, the ${\textsf{ict}}([\![{{\textbf{s}}}, \mu ]\!]_1)$ component of ${\textsf{ct}}^*$ can be fixed at the beginning of the game, before any key queries. Therefore, we can still rely on selective simulation security of IPFE for the first proof step.

However, when we next need to invoke non-annihilability for $L_f$, we run into a problem: the security for $L_f$ only holds when ${{\textbf{x}}}^*$ is chosen before the LWE public matrix ${{\textbf{B}}}$ is revealed in the public parameter ${\textsf{pp}}$ of the secret sharing. To achieve adaptive security, what we need is adaptive non-annihilability property, which allows ${{\textbf{x}}}^*$ to be chosen adaptively dependent on ${\textsf{pp}}$. We show that this is implied by the adaptive LWE assumption formulated in [36].

In summary, we obtain adaptively secure KP-ABE for circuits and CP-ABE for Boolean formulae both with constant-size keys from GGM and Adaptive LWE.

3 Preliminaries

Let $\lambda$ be the security parameter, which runs through ${\mathbb {N}}$. Except in the definitions, we suppress $\lambda$ for brevity. We write [a..b] for the set $\{a,a+1,\dots ,b\}$ and [n] for [1..n]. Vectors and matrices are written in boldface, and are always indexed using $[{\cdot }]$, i.e., ${{\textbf{A}}}[i,j]$ is the (i, j)-entry of ${{\textbf{A}}}$. The infinity norm of a vector and its induced operator norm of a matrix are denoted by $\Vert {\cdot }\Vert _\infty$. We will use the following lemma for various proofs:

Lemma 1

(Schwartz–Zippel). Let $P({{\textbf{z}}})$ be a non-zero polynomial with Z indeterminates of degree at most d over ${\mathbb {Z}}_p$, then .

3.1 Attribute-Based Encryption

Definition 1

(ABE [24]). Let ${{\mathcal {P}}=\{{\mathcal {P}}_\lambda \}_{\lambda \in {\mathbb {N}}}}$ be a sequence of predicate families with ${{\mathcal {P}}_\lambda =\bigl \{P:X_P\times Y_P\rightarrow {\{0,1\}}\bigr \}}$. An attribute-based encryption scheme for ${\mathcal {P}}$ consists of 4 efficient algorithms:

• ${\textsf{Setup}}(1^\lambda ,P)$ takes as input the security parameter $1^\lambda$ and a predicate ${P\in {\mathcal {P}}_\lambda }$, and outputs a pair of master public/secret keys $({\textsf{mpk}},{\textsf{msk}})$.

• ${\textsf{KeyGen}}({\textsf{msk}},y)$ takes as input the master secret key ${\textsf{msk}}$ and some ${y\in Y_P}$, and outputs a secret key ${\textsf{sk}}$.

• ${\textsf{Enc}}({\textsf{mpk}},x,\mu )$ takes as input the master public key ${\textsf{mpk}}$, some ${x\in X_P}$, and a message ${\mu \in {\{0,1\}}}$, and it outputs a ciphertext ${\textsf{ct}}$.

• ${\textsf{Dec}}({\textsf{mpk}},{\textsf{sk}},y,{\textsf{ct}},x)$ takes as input the master public key ${\textsf{mpk}}$, a secret key ${\textsf{sk}}$, its associated y, a ciphertext ${\textsf{ct}}$, and its associated x, and is supposed to recover the message if ${P(x,y)=1}$.

The scheme is required to be correct, i.e., for all ${\lambda \in {\mathbb {N}}}$, ${P\in {\mathcal {P}}_\lambda }$, ${x\in X_P}$, ${y\in Y_P}$, ${\mu \in {\{0,1\}}}$ such that ${P(x,y)=1}$, it holds that

In KP-ABE, each ${y\in Y_P}$ describes a function from $X_P$ to ${\{0,1\}}$, each ${x\in X_P}$ is an input (bit-string) to the functions, and P(x, y) evaluates y on x. When we want to emphasize x (resp. y) is a bit-string (resp. circuit), we write ${{\textbf{x}}}$ (resp. C) instead.

Security. Due to space constraints, we refer the readers to [4, 29, 31] for the definitions of adaptive, selective, and very selective security for ABE.

Computation Model. We will consider KP-ABE for bounded-depth circuits for any polynomial bound. Our CP-ABE for $\textsf{NC}^1$ can be found in the full version [31].

Definition 2

(KP-ABE for circuits). A KP-ABE for (bounded-depth) circuits is ABE for ${\mathcal {P}}^{\textsf{Ckt}}$:²

Here, $D_\lambda$ is a super-polynomial function (specified by the constructions). As an input to ${\textsf{Setup}}$, the predicate $P^{\textsf{Ckt}}_{\lambda ,\ell ,d}$ is represented by $(1^\ell ,1^d)$.

Note that since ${\textsf{Setup}}$ takes the unary representation of $\ell ,d$, which will be polynomial in $\lambda$, as input, they are bounded by that polynomial once the system is set up. However, d can be up to $D_\lambda$, which is super-polynomial in $\lambda$, so one can set up the system for any polynomial depth, i.e., our KP-ABE for circuits supports bounded-depth circuits for arbitrary polynomial depth bound.

Compactness and Succinctness. Since ${\textsf{KeyGen}},{\textsf{Enc}}$ run in polynomial time, the lengths of key and ciphertext could grow polynomially in |y|, |x|, respectively. Moreover, the input length is an argument passed into ${\textsf{Setup}}$, so both keys and ciphertexts could have polynomial size dependency on it. We are interested in ABE schemes with short keys and ciphertexts:

Definition 3

(ABE efficiency). A KP-ABE for circuits (of depth at most d) has

• succinct keys if ${|{\textsf{sk}}|={\text {poly}}(\lambda ,d)}$ is independent of $|C|,|{{\textbf{x}}}|$;

• compact ciphertexts if ${|{\textsf{ct}}|=|{{\textbf{x}}}|{\text {poly}}(\lambda ,d)}$ is independent of |C|.

We remark that an ideally succinct component should be of length ${\text {poly}}(\lambda )$. Nevertheless, our version defined above is still meaningful as the circuit size can be much larger than its depth.

3.2 Lattice Tools

Homomorphic Evaluation. We use the following abstraction of homomorphic evaluation for ABE over lattices, developed in a series of works [11, 19, 23] with the syntax in [13, 14]. The actual algorithm we use is a slightly changed version of that for ABE for circuits in [11]. In our version, instead of using ${{\textbf{G}}}$ as the gadget matrix, we consider ${{\textbf{Q}}}{{\textbf{G}}}$ for any invertible ${{\textbf{Q}}}$. Note that ${{\textbf{G}}}^{-1}({{\textbf{Q}}}^{-1}\times {\cdot })$ is a right inverse of ${{\textbf{Q}}}{{\textbf{G}}}$ with binary output. We replace any invocation of ${{\textbf{G}}}^{-1}({\cdot })$ in the original algorithms by ${{\textbf{G}}}^{-1}({{\textbf{Q}}}^{-1}\times {\cdot })$ to obtain the following:

Lemma 2

(homomorphic evaluation for circuits, adapted from [11]). ${\textsf{EvalC}}$ and ${\textsf{EvalCX}}$ are two efficient deterministic algorithms. Let $n,\ell ,q$ be positive integers, ${m=n\lceil \log _2 q\rceil }$, ${{\textbf{G}}}$ the gadget matrix, ${{\textbf{B}}}$ a matrix over ${\mathbb {Z}}_q$ of shape ${n\times (\ell +1)m}$, ${{\textbf{Q}}}$ an invertible matrix over ${\mathbb {Z}}_q$ of shape ${n\times n}$, ${{\textbf{x}}}$ an $\ell$-bit string (row vector), and C a circuit of depth d with input length $\ell$. The algorithms work as follows:

• ${\textsf{EvalC}}({{\textbf{B}}},{{\textbf{Q}}},C)$ outputs ${{{\textbf{H}}}_C\in {\mathbb {Z}}^{(\ell +1)m\times m}}$;

• ${\textsf{EvalCX}}({{\textbf{B}}},{{\textbf{Q}}},C,{{\textbf{x}}})$ outputs ${\widehat{{{\textbf{H}}}}_{C,{{\textbf{x}}}}\in {\mathbb {Z}}^{(\ell +1)m\times m}}$.

The outputs satisfy

$$\begin{aligned} \Vert {{\textbf{H}}}_C^{{\textsf{T}}}\Vert _\infty ,\Vert \widehat{{{\textbf{H}}}}_{C,{{\textbf{x}}}}^{{\textsf{T}}}\Vert _\infty \le (m+1)^d, \quad \bigl ({{\textbf{B}}}-(1,{{\textbf{x}}})\otimes {{\textbf{Q}}}{{\textbf{G}}}\bigr )\widehat{{{\textbf{H}}}}_{C,{{\textbf{x}}}} ={{\textbf{B}}}{{\textbf{H}}}_C-C({{\textbf{x}}}){{\textbf{Q}}}{{\textbf{G}}}. \end{aligned}$$

Gadget Matrix [33]. Let n, q be positive integers and ${m=n\lceil \log _2 q\rceil }$. The gadget matrix is ${{{\textbf{G}}}={{\textbf{g}}}^{{\textsf{T}}}\otimes {{\textbf{I}}}_n}$, where ${{{\textbf{g}}}^{{\textsf{T}}}=(2^0,2^1,\dots ,2^{\lceil \log _2 q\rceil -1})}$. There exists an efficiently computable function ${{{\textbf{G}}}^{-1}:{\mathbb {Z}}_q^n\rightarrow {\{0,1\}}^m}$ such that ${{{\textbf{G}}}\cdot {{\textbf{G}}}^{-1}({{\textbf{u}}})={{\textbf{u}}}}$ for all ${{{\textbf{u}}}\in {\mathbb {Z}}_q^n}$.

Assumption. We rely on the following assumption, a small-secret version of adaptive learning with errors (LWE), which itself is a natural variant of LWE first proposed in [36]:

Definition 4

(small-secret adaptive LWE). We suppress the security parameter $\lambda$ and all the parameters are dependent on $\lambda$. Let n be the dimension, q the modulus, $\chi$ the error distribution, ${m=n\lceil \log _2 q\rceil }$, and ${{\textbf{G}}}$ the gadget matrix. The small-secret adaptive LWE assumption ${\textrm{sALWE}}_{n,q,\chi }$ statesthat ${{\textsf{Exp}}_{{\textrm{sALWE}}}^0\approx {\textsf{Exp}}_{{\textrm{sALWE}}}^1}$, where ${\textsf{Exp}}_{{\textrm{sALWE}}}^b(1^n,q,\chi )$ with adversary ${\mathcal {A}}$ proceeds as follows:

• Setup. The challenger launches ${\mathcal {A}}$ and receives $(1^\ell ,1^{m'})$ from it. The challenger samples , , and a uniformly random invertible ${{{\textbf{Q}}}\in {\mathbb {Z}}_q^{n\times n}}$. It sends ${{\textbf{A}}},{{\textbf{B}}},{{\textbf{Q}}}$ to ${\mathcal {A}}$.

• Challenge. ${\mathcal {A}}$ submits ${{{\textbf{x}}}\in {\{0,1\}}^\ell }$. Depending on b,

  

  The challenger sends ${{{\textbf{c}}}},{{\textbf{d}}}$ to ${\mathcal {A}}$.

• Guess ${\mathcal {A}}$ outputs a bit, which is the outcome of the experiment.

Lemma 3

(small-secret adaptive LWE). The small-secret adaptive LWE assumption holds if the adaptive LWE assumption [36] holds for the same parameters.

The proof of Lemma 3 can be found in the full version [31].

Parameter Settings. We rely on the hardness of small-secret LWE with subexponential modulus-to-noise ratio. For some ${0<\delta <\frac{1}{2}}$, the small-secret LWE assumption is assumed to be hard when the dimension is ${n={\text {poly}}(\lambda )}$, the prime modulus is ${q=\textrm{O}(2^{n^\delta })}$, and the error distribution $\chi$ is the discrete Gaussian over ${\mathbb {Z}}$ of width ${\overline{B}}/\lambda$ truncated within ${[-{\overline{B}}..{\overline{B}}]}$ for ${{\overline{B}}={\text {poly}}(\lambda )}$.³ Hereafter we default to these parameters.

3.3 Pairing Groups and Generic Asymmetric Pairing Group Model

We construct our ABE using pairing groups and prove its security in the generic pairing group model.

Pairing Groups. Throughout the paper, we use a sequence of pairing groups

$$\begin{aligned} {\mathcal {G}}=\{(p_\lambda ,\, G_{\lambda ,1},G_{\lambda ,2},G_{\lambda ,{{\textrm{T}}}},\, g_{\lambda ,1},g_{\lambda ,2},g_{\lambda ,{{\textrm{T}}}},\, e_\lambda )\}_{\lambda \in {\mathbb {N}}}, \end{aligned}$$

where $G_{\lambda ,1}$ (resp. $G_{\lambda ,2}$, $G_{\lambda ,{{\textrm{T}}}}$) is a cyclic group generated by $g_{\lambda ,1}$ (resp. $g_{\lambda ,2}$, $g_{\lambda ,{{\textrm{T}}}}$) of prime order ${p_\lambda =2^{\lambda ^{{\Theta }(1)}}}$ and ${e_\lambda :G_{\lambda ,1}\times G_{\lambda ,2}\rightarrow G_{\lambda ,{{\textrm{T}}}}}$ is the pairing operation, satisfying ${e_\lambda (g_{\lambda ,1}^a,g_{\lambda ,2}^b)=g_{\lambda ,{{\textrm{T}}}}^{ab}}$ for all integers a, b. We require the group operations as well as the pairing operation to be efficiently computable.

For a fixed security parameter $\lambda$, we denote $g_{\lambda ,i}^x$ by $[\![x]\!]_i$ for ${i\in \{1,2,{{\textrm{T}}}\}}$. The notation extends to matrices, ${[\![{{\textbf{A}}}]\!]_i=g_{\lambda ,i}^{{{\textbf{A}}}}}$, where exponentiation is done component-wise. With these notations, the group operations are written additively and the pairing operation multiplicatively. For example, $[\![{\textbf{A}}]\!]_1-{\textbf{B}}[\![{\textbf{C}}]\!]_1{\textbf{D}}=[\![{\textbf{A}}-{\textbf{B}}{\textbf{C}}{\textbf{D}}]\!]_1$ and ${[\![{\textbf{X}}]\!]_2[\![{\textbf{Y}}]\!]_1=[\![{\textbf{X}}{\textbf{Y}}]\!]_{{\textrm{T}}}}$.

Generic Asymmetric Pairing Group. The security of our ABE scheme holds in the generic asymmetric pairing group model (GGM), where the pairing groups can only be accessed via (non-unique) handles representing group elements and oracles for operating the handles. Due to space constraints, we refer the readers to the full version [31] for the formal definition of the version we use in this work.

3.4 Inner-Product Functional Encryption

Inner-product functional encryption schemes enable generating keys and ciphertexts tied to vectors. Decryption reveals the inner product and nothing more about the plaintext vector. In this work, we consider IPFE schemes based on pairing, where keys and ciphertexts are encoded in the two source groups and decryption recovers inner products encoded in the target group.

Definition 5

(group-based IPFE). Let ${\mathcal {G}}$ be a sequence of pairing groups of order $\{p_\lambda \}_{\lambda \in {\mathbb {N}}}$. An inner-product functional encryption (IPFE) scheme based on ${\mathcal {G}}$ consists of 4 efficient algorithms:

• ${\textsf{Setup}}(1^\lambda ,1^N)$ takes as input the security parameter $1^\lambda$ and the vector dimension $1^N$. It outputs a pair of master public/secret keys $({\textsf{impk}},{\textsf{imsk}})$.

• ${\textsf{KeyGen}}({\textsf{imsk}},[\![{{\textbf{v}}}]\!]_2)$ takes as input the master secret key and a vector (encoded in $G_2$), and outputs a secret key ${\textsf{isk}}$.

• ${\textsf{Enc}}({\textsf{impk}},[\![{{\textbf{u}}}]\!]_1)$ takes as input the master public key and a vector (encoded in $G_1$), and outputs a ciphertext ${\textsf{ict}}$.

• ${\textsf{Dec}}({\textsf{isk}},[\![{{\textbf{v}}}]\!]_2,{\textsf{ict}})$ takes a secret key, the vector in the secret key, and a ciphertext as input, and is supposed to compute the inner product encoded in $G_{{\textrm{T}}}$.

The scheme is required to be correct, meaning that for all ${\lambda ,N\in {\mathbb {N}}},{{{\textbf{u}}},{{\textbf{v}}}\in {\mathbb {Z}}_{p_\lambda }^N}$,

Definition 6

(key-succinct IPFE). An IPFE scheme (Definition 5) is (key-)succinct if the length of ${\textsf{isk}}$ is a fixed polynomial in $\lambda$, independent of N.

Security. Our basic security notion is selective simulation:

Definition 7

(selective simulation [32, 41]). A simulator for an IPFE scheme (Definition 5) consists of 3 efficient algorithms:

• $\widetilde{\textsf{Setup}}(1^\lambda , 1^N)$ takes the same input as ${\textsf{Setup}}$, and outputs simulated keys $(\widetilde{{\textsf{impk}}},\widetilde{{\textsf{imsk}}})$.

• $\widetilde{\textsf{KeyGen}}(\widetilde{{\textsf{imsk}}}, [\![{{\textbf{v}}}]\!]_2, [\![z_i]\!]_2)$ takes as input the simulated master secret key, a vector encoded in $G_2$, and an inner product encoded in $G_2$. It outputs a simulated key $\widetilde{{\textsf{isk}}}$.

• $\widetilde{\textsf{Enc}}(\widetilde{{\textsf{imsk}}})$ takes as input the simulated master secret key. It outputs a simulated ciphertext $\widetilde{{\textsf{ict}}}$.

The IPFE scheme is selectively simulation-secure if there exists a simulator such that ${{\textsf{Exp}}_{\textrm{real}}\approx {\textsf{Exp}}_{\textrm{sim}}}$, where ${\textsf{Exp}}_{\textrm{real}}(1^\lambda )$ or ${\textsf{Exp}}_{\textrm{sim}}(1^\lambda )$ with ${\mathcal {A}}$ proceeds as follows:

• Challenge. The challenger launches ${\mathcal {A}}(1^{\lambda })$ and receives from it the vector dimension $1^N$ and the challenge vector ${{{\textbf{u}}}\in {\mathbb {Z}}_p^N}$.

• Setup. The challenger runs

  

  and sends ${\textsf{impk}}, {\textsf{ict}}$ to ${\mathcal {A}}$.

• Query. The following is repeated for arbitrarily many rounds determined by ${\mathcal {A}}$: In each round, ${\mathcal {A}}$ submits a vector $[\![{{\textbf{v}}}_j]\!]_2$ encoded in $G_2$. Upon receiving the query, the challenger runs

  

  and sends ${\textsf{isk}}_j$ to ${\mathcal {A}}$.

• Guess ${\mathcal {A}}$ outputs a bit b, which is the output of the experiment.

Lemma 4

([2, 41]). Assuming the MDDH assumption (true in GGM), there exists a succinct selectively simulation-secure IPFE scheme. Its components have sizes

$$\begin{aligned} \begin{array}{lr} |{\textsf{impk}}|=k(k+1+N)|G_1|, &{}\qquad |{\textsf{imsk}}|=(k+1)N\log _2 p,\;\\ \quad |{\textsf{isk}}|=(k+1)|G_2|, &{}\qquad |{\textsf{ict}}|=(k+1+N)|G_1|, \end{array} \end{aligned}$$

where p is the modulus, k is the MDDH parameter (can be 1 in GGM), N is the dimension, and $|G_i|$ is the bit-length of an element in $G_i$.

4 Computational Secret Sharing with Adaptive Security

Secret sharing schemes have been used extensively to construct ABE schemes. The seminal work of [24] and a long line of follow-up works ( [5, 28,29,30, 35] to name a few) used linear secret sharing schemes to construct ABE schemes in pairing groups. Policies with polynomial-sized shares and information-theoretic security are in NC [8, 9, 15, 26, 34].

The works of [3, 4] introduced the notion of nearly linear secret sharing with computational security. The relaxations enabled greater expressiveness and better efficiency. Assuming LWE, such a scheme exists for all polynomial-sized circuits [3, 4, 11, 23] and the shares are succinct, i.e., they only grow with the circuit depth, but not the circuit size. However, the scheme is only selectively secure. Furthermore, due to technical reasons, when combined with pairing to obtain ABE, it only applies to Boolean formulae (equivalent to 5-PBP).

This work follows the blueprint of [3, 4] for the notions of secret sharing schemes, but departs from them in three important aspects. First, we consider a different security notion, adaptive non-annihilability, which is incomparable⁴ to selective pseudorandomness considered in [3, 4] and enables us to prove adaptive security of ABE. Second, we further relax the linearity requirement so that it could apply to KP-ABE for polynomial-sized circuits. Third, we refine the syntax to separate encodings of input and function.

Definition 8

(secret sharing). Let ${\mathcal {F}}=\{{\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}\}_{\lambda ,\ell \in {\mathbb {N}},{\textsf{param}}}$ be an ensemble of Boolean function families such that for all ${\lambda ,\ell \in {\mathbb {N}}}$ and ${\textsf{param}}$, every ${f\in {\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}}$ is a function mapping ${\{0,1\}}^\ell$ to ${\{0,1\}}$. A secret sharing scheme for ${\mathcal {F}}$ consists of 4 efficient algorithms:

• ${\textsf{Setup}}(1^\lambda , 1^\ell , {\textsf{param}})$ takes the security parameter $1^\lambda$, the input length $1^\ell$, and additional parameters ${\textsf{param}}$ as input. It outputs some public parameter ${\textsf{pp}}$.

• ${\textsf{ShareX}}({\textsf{pp}})$ takes the public parameter ${\textsf{pp}}$ as input. It outputs ${1+2\ell }$ shares, $L_0, \{L_i^b\}_{i \in [\ell ]}^{b \in {\{0,1\}}}$, and some shared randomness r. For ${x \in {\{0,1\}}^\ell }$, we denote by $L^{{{\textbf{x}}}}$ the set of shares $L_0,\{L_i^{{{\textbf{x}}}[i]}\}_{i \in [\ell ]}$.

• ${\textsf{ShareF}}({\textsf{pp}}, f, \mu , r)$ takes the public parameter ${\textsf{pp}}$, a function ${f \in {\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}}$, a secret ${\mu \in {\{0,1\}}}$, and the shared randomness r (output by ${\textsf{ShareX}}$) as input. It outputs a share $L_f$.

• ${\textsf{Recon}}({\textsf{pp}}, f, {{\textbf{x}}}, L_f, L^{{{\textbf{x}}}})$ takes the public parameter ${\textsf{pp}}$, the Boolean function ${f \in {\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}}$, the input ${{{\textbf{x}}}\in {\{0,1\}}^\ell }$ to f, and the shares $L_f, L^{{{\textbf{x}}}}$ as input. It is supposed to recover the secret $\mu$ if ${f({{\textbf{x}}}) = 0}$.⁵

The scheme is required to be correct, i.e., for all ${\lambda ,\ell \in {\mathbb {N}}}$, ${\textsf{param}}$, ${{{\textbf{x}}}\in {\{0,1\}}^\ell }$, ${f \in {\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}}$, ${\mu \in {\{0,1\}}}$ such that ${f({{\textbf{x}}}) = 0}$, it holds that

Definition 9

(succinct shares). A secret sharing scheme is succinct if the size of each share output by ${\textsf{ShareX}},{\textsf{ShareF}}$ is a fixed polynomial in $\lambda$, independent of the length of ${{\textbf{x}}}$ or the description size of f, i.e., $|L_f|,|L_0|,|L_i^b|$ are all ${\text {poly}}(\lambda ,|{\textsf{param}}|)$, where ${i\in [\ell ]}$, ${b\in {\{0,1\}}}$.⁶

While correctness (Definition 8) and succinctness (Definition 9) are defined similarly to that of [3], our linearity and security notions are different.

4.1 Secret Sharing for Bounded-Depth Circuits from Adaptive LWE

In our KP-ABE construction, we need a secret sharing scheme with two linearity properties. The first is a relaxation of the nearly linear reconstruction requirement in [3]. requirement on reconstruction. Our relaxed version (Definition 10) only stipulates it to be linear in ${{\textbf{L}}}_f$ (and possibly non-linear in $L^{{\textbf{x}}}$).

Definition 10

(weakly nearly linear reconstruction). A secret sharing scheme (Definition 8) is weakly nearly linear if it satisfies the following requirements:

• Let $\{p_{\lambda }\}_{\lambda \in {\mathbb {N}}}$ be a sequence of prime numbers. ${{{\textbf{L}}}_f=L_f}$ is a vector over ${\mathbb {Z}}_{p_\lambda }$.

• There is an efficient coefficient-finding algorithm ${\textsf{FindCoef}}({\textsf{pp}},f,{{\textbf{x}}},L^{{\textbf{x}}})$, taking as input the public parameter ${\textsf{pp}}$, a Boolean function ${f \in {\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}}$, an input ${{{\textbf{x}}}\in {\{0,1\}}^{\ell }}$ to f, and the shares $L^{{{\textbf{x}}}}$. It outputs an affine function $\gamma$ and a noise bound $1^B$. For all ${\lambda ,\ell \in {\mathbb {N}}},{\textsf{param}},{{{\textbf{x}}}\in {\{0,1\}}^{\ell }},{f \in {\mathcal {F}}_{\lambda ,\ell ,{\textsf{param}}}},{\mu \in {\{0,1\}}}$ such that ${f({{\textbf{x}}})=0}$, it holds that

  

The second is an additional linearity requirement on ${\textsf{ShareF}}$.

Definition 11

(linear function sharing). Let $\{p_{\lambda }\}_{\lambda \in {\mathbb {N}}}$ be a sequence of primes. A secret sharing scheme (Definition 8) has linear function sharing if ${{{\textbf{r}}}=r}$ is a vector over ${\mathbb {Z}}_{p_\lambda }$ and ${\textsf{ShareF}}({\textsf{pp}}, f, \mu , {{\textbf{r}}})$ is deterministic and linear in $(\mu ,{{\textbf{r}}})$.

A (weakly) nearly linear scheme is by definition correct. Given ${\textsf{FindCoef}}$, we let ${\textsf{Recon}}$ call ${\textsf{FindCoef}}$ to obtain $\gamma ,B$ and output the unique ${\mu \in {\{0,1\}}}$ satisfying $\gamma ({{\textbf{L}}}_f)-\mu \lfloor p/2\rfloor \in [-B..B]$. The constructed ${\textsf{Recon}}$ is efficient and correct. Since ${\textsf{Recon}}$ is implied by ${\textsf{FindCoef}}$, we will only specify ${\textsf{FindCoef}}$ and omit ${\textsf{Recon}}$ when constructing (weakly) nearly linear secret sharing schemes.

Security. We consider a new security notion called non-annihilability. Unlike [3], which fixes the choice of policy f before ${\textsf{Setup}}$ is run, we allow the adversary to adaptively choose f after seeing the public parameters ${\textsf{pp}}$ and the input shares $L^{{\textbf{x}}}$. Another difference is that instead of requiring all shares $(L_f, L^{{\textbf{x}}})$ to look random, we only require that efficient adversaries cannot find a non-trivial affine function (potentially dependent on $L^{{\textbf{x}}}$) that evaluates to zero on ${{\textbf{L}}}_f$. This notion suffices for the security proofs of our KP-ABE scheme.

Definition 12

(non-annihilability for ${{\textbf{L}}}_f$). Let $\{p_{\lambda }\}_{\lambda \in {\mathbb {N}}}$ be a sequence of prime numbers. A secret sharing scheme (Definition 8) is adaptively non-annihilable for ${{\textbf{L}}}_f$ if the output ${{\textbf{L}}}_f$ of ${\textsf{ShareF}}$ is a vector over ${\mathbb {Z}}_{p_\lambda }$ and all efficient adversary wins ${\textsf{Exp}}_{\mathrm{ANN-f}}$ with negligible probability, where in ${\textsf{Exp}}_{\mathrm{ANN-f}}^{{\mathcal {A}}}(1^\lambda )$, the adversary ${\mathcal {A}}$ interacts with the challenger as follows:

• Setup. The challenger launches ${\mathcal {A}}(1^\lambda )$ and receives from it the input length $1^\ell$ and the additional parameter ${\textsf{param}}$. The challenger sets up the system by running , and sends ${\textsf{pp}}$ to ${\mathcal {A}}$.

• Share. ${\mathcal {A}}$ first submits an input ${{{\textbf{x}}}\in {\{0,1\}}^\ell }$. Upon receiving it, the challenger creates the input shares by running and sends $L^{{{\textbf{x}}}}$ to ${\mathcal {A}}$.

• Challenge. ${\mathcal {A}}$ outputs a Boolean function ${f\in {\mathcal {F}}_{\lambda ,\ell }}$, a message bit $\mu \in {\{0,1\}}$, and an affine function $\gamma$. Upon receiving them, the challenger runs and determines the outcome of the experiment. ${\mathcal {A}}$ wins if i) ${f({{\textbf{x}}})=1}$; ii) $\gamma$ is not the zero function; and iii) ${\gamma ({{\textbf{L}}}_f)=0}$. Otherwise, ${\mathcal {A}}$ loses.

Furthermore, a secret sharing scheme is selectively non-annihilable if it satisfies the above conditions, with the change that the adversary must choose the input ${{\textbf{x}}}$ before receiving ${\textsf{pp}}$.

We now construct a succinct secret sharing scheme, satisfying the above linearity and adaptive annihilability for bounded-depth circuits from small-secret adaptive LWE. Our construction is based on the attribute-based laconic function evaluation scheme [11, 36].

Construction 1

(secret sharing for circuits). Let n be the LWE dimension, $p=2^{{\omega }(\log \lambda )}$ a fixed prime modulus, (the LWE parameters will be chosen during ${\textsf{Setup}}$). We construct a weakly nearly linear and succinct secret sharing scheme, with linear function sharing, for the family of bounded-depth circuits (see Definition 2):

$$\begin{aligned} {\textsf{Ckt}}_{\lambda ,\ell ,d}&{}=\bigl \{\,\textrm{Boolean}\; \textrm{circuit }\; C:{\{0,1\}}^\ell \rightarrow {\{0,1\}}\; \textrm{of}\; \textrm{depth}\; \textrm{at}\; \textrm{most}\;d\,\bigr \}, \end{aligned}$$

where ${d\le \frac{p^{\delta /4}-\log _2 p}{(1+\delta ^{-1}){\Theta }(1)}}$. Let $({\textsf{EvalC}},{\textsf{EvalCX}})$ be the algorithms in Lemma 2.

• ${\textsf{Setup}}(1^\lambda , 1^\ell ,1^d)$ takes the input length $\ell$ in unary as input. It sets

  $$\begin{aligned} n&{}={\overline{B}}=\bigl ((d+1)(\delta ^{-1}+1)+\log _2p+\textrm{O}(d)\bigr )^{2/\delta },\quad q=2^{n^\delta },\quad m=n\lceil \log _2 q\rceil , \end{aligned}$$

  and picks $\chi$ to be ${\overline{B}}$-bounded. It next samples and sets

  

  It finally samples a random invertible matrix ${{{\textbf{Q}}}\in {\mathbb {Z}}_q^{n\times n}}$, and outputs ${\textsf{pp}}= (n, q, m, {\overline{B}}, \chi , {{\textbf{a}}}, {{\textbf{B}}}, {{\textbf{Q}}})$.

  Note: Recall that $\delta$ is a constant depending on the underlying adaptive LWE assumption. The choice of $n,{\overline{B}},q$ are subject to the requirement of the underlying adaptive LWE assumption as well as correctness and efficiency of the scheme. They satisfy ${q/{\overline{B}}\ge (m+1)^{d+1}}$ and ${4((n+1){\overline{B}}+3)+1<p}$.

• ${\textsf{ShareX}}({\textsf{pp}})$ takes the public parameter ${\textsf{pp}}$ as input. It samples and sets

  

  and outputs $({{\textbf{L}}}_0,\{{{\textbf{L}}}_i^b\}_{i\in [\ell ]}^{b\in {\{0,1\}}}, {{\textbf{s}}})$.

• ${\textsf{ShareF}}({\textsf{pp}}, f, \mu , {{\textbf{s}}})$ takes as input the public parameter ${\textsf{pp}}$, some $f\in {\textsf{Ckt}}_{\lambda ,\ell ,d}$, a secret bit $\mu \in {\{0,1\}}$, and the shared randomness ${{\textbf{s}}}$. It runs ${{\textbf{H}}}_f\leftarrow {\textsf{EvalC}}({{\textbf{B}}},{{\textbf{Q}}},f)$, and sets and outputs

  $$\begin{aligned} {{\textbf{L}}}_f = {{\textbf{s}}}^{{\textsf{T}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \mu \lfloor p/2\rceil ,\quad \textrm{where}\; \lfloor x\rceil _p = \lfloor px/q\rceil . \end{aligned}$$

  Note: The scheme indeed has linear function sharing (Definition 11) because ${\textsf{ShareF}}$ is a deterministic linear function over $\mu , {{\textbf{s}}}$ with coefficients $\lfloor p/2\rceil , \lfloor {{\textbf{B}}}{{\textbf{H}}}_f {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p$. The scheme is also succinct as ${{\textbf{L}}}_f$ contains 1 element in ${\mathbb {Z}}_p$, and each share output by ${\textsf{ShareX}}$ contains m elements in ${\mathbb {Z}}_q$. Note that m is a fixed polynomial in $\lambda ,d$ and is independent of the description size of f and the input length $\ell$.

• ${\textsf{FindCoef}}({\textsf{pp}}, f, {{\textbf{x}}}, {{\textbf{L}}}^{{\textbf{x}}})$ takes as input the public parameter ${\textsf{pp}}$, some ${{{\textbf{x}}}\in {\{0,1\}}^\ell }$, some ${f\in {\textsf{Ckt}}_{\lambda ,\ell ,d}}$, and the shares ${{\textbf{L}}}^{{\textbf{x}}}$. If ${f({{\textbf{x}}})=1}$, it outputs $\bot$ and terminates. Otherwise, it runs ${\widehat{{{\textbf{H}}}}_{f,{{\textbf{x}}}}\leftarrow {\textsf{EvalCX}}({{\textbf{B}}},{{\textbf{Q}}},f,{{\textbf{x}}})}$, and defines

  $$\begin{aligned} \gamma \bigl ({{\textbf{L}}}_f\bigr ) {}={{\textbf{L}}}_f- \lfloor {{\textbf{L}}}^{{\textbf{x}}}\widehat{{{\textbf{H}}}}_{f,{{\textbf{x}}}}{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p,\quad B{}=(n+1){\overline{B}}+3, \end{aligned}$$

  The algorithm outputs $(\gamma ,1^B)$.

  Note: The procedure is indeed efficient since $n, {\overline{B}}$ are polynomials in $\lambda ,d$. We show that ${\textsf{FindCoef}}$ is correct, i.e., if $f({{\textbf{x}}})=0$, then $4B+1 \le p$ and $\gamma ({{\textbf{L}}}_f) = \mu \lfloor p/2\rceil + e$ for some $e \in [-B,B]$. First, by the choice of $n,{\overline{B}}$,

  $$ 4B + 1 = 4((n+1){\overline{B}}+ 3) + 1 \le p. $$

  Next, by construction we have

  $$\begin{aligned} \gamma ({{\textbf{L}}}_f) ={}&{{\textbf{L}}}_f - \lfloor {{\textbf{L}}}^{{\textbf{x}}}\widehat{{{\textbf{H}}}}_{f,{{\textbf{x}}}} {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p \\ ={}&\underbrace{ {{\textbf{s}}}^{{{\textsf{T}}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \mu \lfloor p/2\rceil }_{{{\textbf{L}}}_f}\\&{}-{}\lfloor \bigl (\underbrace{ {{\textbf{s}}}^{{{\textsf{T}}}}({{\textbf{B}}}-(1,{{\textbf{x}}})\otimes {{\textbf{Q}}}{{\textbf{G}}}) + ({{\textbf{e}}}_0^{{\textsf{T}}},{{\textbf{e}}}_1^{{\textsf{T}}},\dots ,{{\textbf{e}}}_\ell ^{{\textsf{T}}}) }_{{{\textbf{L}}}^{{{\textbf{x}}}}} \bigr ) \widehat{{{\textbf{H}}}}_{f,{{\textbf{x}}}} {{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p \\ \text {(Lemma}~2\mathrm{)} ={}&{{\textbf{s}}}^{{{\textsf{T}}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \mu \lfloor p/2\rceil \\&{}-{}\lfloor {{\textbf{s}}}^{{{\textsf{T}}}}({{\textbf{B}}}{{\textbf{H}}}_f - \underbrace{f({{\textbf{x}}})}_{{}=0}{{\textbf{Q}}}{{\textbf{G}}}){{\textbf{G}}}^{-1}({{\textbf{a}}}) +\underbrace{ ({{\textbf{e}}}_0^{{\textsf{T}}},{{\textbf{e}}}_1^{{\textsf{T}}},\dots ,{{\textbf{e}}}_\ell ^{{\textsf{T}}}) \widehat{{{\textbf{H}}}}_{f,{{\textbf{x}}}}{{\textbf{G}}}^{-1}({{\textbf{a}}}) }_{=e_f}\rceil _p \\ ={}&{{\textbf{s}}}^{{{\textsf{T}}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \mu \lfloor p/2\rceil - \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}}) + e_f\rceil _p \end{aligned}$$

  Since ${{{\textbf{G}}}^{-1}({{\textbf{a}}})\in {\{0,1\}}^m}$, by the definition of ${\textsf{EvalCX}}$ (Lemma 2), we have

  $$ |e_f| \le m\cdot \Vert \widehat{{{\textbf{H}}}}_{f,{{\textbf{x}}}}^{{\textsf{T}}}\Vert _\infty \cdot \Vert ({{\textbf{e}}}_0^{{\textsf{T}}},{{\textbf{e}}}_1^{{\textsf{T}}},\dots ,{{\textbf{e}}}_\ell ^{{\textsf{T}}}) ^{{\textsf{T}}}\Vert _\infty \le (m+1)^{(d+1)}{\overline{B}}$$

  Note that we can break a rounded sum into a sum of individually rounded terms, at the expense of some rounding errors:

  $$\begin{aligned} \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}}) + e_f\rceil&{}= \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + \lfloor e_f\rceil _p + \epsilon ,\; \textrm{where}\ |\epsilon | \le 3, \\ \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p&{}= {{\textbf{s}}}^{{{\textsf{T}}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p + e_s,\; \textrm{where}\ |e_s| \le n\cdot \Vert {{\textbf{s}}}\Vert _\infty \le n{\overline{B}}. \end{aligned}$$

  Finally, we have

  $$\begin{aligned} \gamma ({{\textbf{L}}}_f)&{}= \mu \lfloor p/2\rceil + {{\textbf{s}}}^{{{\textsf{T}}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p - \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}}) + e_f\rceil _p\\&{}=\mu \lfloor p/2\rceil + {{\textbf{s}}}^{{{\textsf{T}}}}\lfloor {{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p - \lfloor {{\textbf{s}}}^{{\textsf{T}}}{{\textbf{B}}}{{\textbf{H}}}_f{{\textbf{G}}}^{-1}({{\textbf{a}}})\rceil _p - \lfloor e_f\rceil _p - \epsilon \\&{}=\mu \lfloor p/2\rceil \underbrace{{}- e_s- \lfloor e_f\rceil _p - \epsilon }_{=e}. \end{aligned}$$

  By the definition of $e_f,e_s,\epsilon$, and the setting of q, we have

  $$ |e| \le |e_s| + \left| \lfloor e_f\rceil _p\right| + |\epsilon | \le \left\lceil \frac{(m+1)^{(d+1)}}{q/p} {\overline{B}}\right\rceil + n{\overline{B}}+ 3 \le B. $$

Efficiency. In the above construction, the public parameters ${\textsf{pp}}$ mainly consists of three matrices ${{\textbf{a}}}\in {\mathbb {Z}}_q^n, {{\textbf{B}}}\in {\mathbb {Z}}_q^{n\times (m\ell )}, {{\textbf{Q}}}\in {\mathbb {Z}}_q^{n\times n}$, where $n = {\text {poly}}(\lambda ,d), q = 2^{n^\delta }$, and $m = n\lceil \log q \rceil = {\text {poly}}(\lambda ,d)$. Therefore, the bit length of ${\textsf{pp}}$ is $|{\textsf{pp}}| = {\text {poly}}(\lambda ,d)\cdot \ell$. The shares ${{\textbf{L}}}_0$ and $\{{{\textbf{L}}}_i^b\}$ are $2\ell +1$ vectors in ${\mathbb {Z}}_q^m$. Therefore $|{{\textbf{L}}}_0| = |{{\textbf{L}}}_i^b| = {\text {poly}}(\lambda ,d)$. Finally, ${{\textbf{L}}}_f$ is a single element in ${\mathbb {Z}}_p$, where $p = 2^{{\omega }(\log \lambda )}$. Therefore, $|{{\textbf{L}}}_f| = {\text {poly}}(\lambda )$.

We next state non-annihilability security for ${{\textbf{L}}}_f$ of the scheme. The proof can be found in the full version [31].

Proposition 5

Assuming the small-secret adaptive LWE assumption, Construction 1 is non-annihilable for ${{\textbf{L}}}_f$.

5 KP-ABE for Bounded-Depth Circuits

In this section, we combine a succinct and weakly nearly linear secret sharing scheme that has linear function sharing, with a succinct and selectively simulation-secure IPFE scheme to obtain a compact and adaptively secure KP-ABE scheme.

Construction 2

(KP-ABE). All variables $x_\lambda$ are indexed by $\lambda$. For simplicity of notations, we suppress $\lambda$ in subscripts. Our construction uses the following two ingredients:

• A group based IPFE scheme $({\textsf{IPFE}}.{\textsf{Setup}},{\textsf{IPFE}}.{\textsf{KeyGen}},{\textsf{IPFE}}.{\textsf{Enc}},{\textsf{IPFE}}.{\textsf{Dec}})$ with modulus p given by Lemma 4.

• A secret sharing scheme $({\textsf{SS}}.{\textsf{Setup}},{\textsf{SS}}.{\textsf{ShareX}},{\textsf{SS}}.{\textsf{ShareF}},{\textsf{SS}}.{\textsf{FindCoef}})$ for bounded-depth circuits as in Construction 1. Recall that the scheme has three properties. First, the shares are succinct: ${{\textbf{L}}}_0$ and ${{\textbf{L}}}_i^b$ are vectors in ${\mathbb {Z}}_q$ of length $m = {\text {poly}}(\lambda , d)$, and ${{\textbf{L}}}_C$ is a single element in ${\mathbb {Z}}_p$. Second, the scheme has weakly nearly linear reconstruction: the algorithm ${\textsf{SS}}.{\textsf{FindCoef}}$ outputs an affine function $\gamma$ over ${{\textbf{L}}}_C$ that approximately evaluates to $\mu \lfloor p/2\rceil$. Third, the scheme has linear function sharing: ${\textsf{SS}}.{\textsf{ShareF}}_{{\textsf{SS}}.{\textsf{pp}}, C}(\cdot , \cdot )$ is a deterministic linear function over ${\mathbb {Z}}_p$.

Our KP-ABE for circuits (see Definition 2) works as follows:

• ${\textsf{Setup}}(1^\lambda , P)$ takes as input the security parameter $\lambda$ in unary, and a predicate $P \in {\textsf{Ckt}}$. Let $\ell ,d$ be the attribute length and depth for P. The algorithm runs and sets

  

  It outputs ${\textsf{mpk}}, {\textsf{msk}}$.

• ${\textsf{KeyGen}}({\textsf{msk}}, C)$ takes as input the master secret key ${\textsf{msk}}$ and a policy $C \in {\textsf{Ckt}}_{\ell ,d}$. Since the secret sharing scheme has linear function sharing (Definition 11), the ${\textsf{SS}}.{\textsf{ShareF}}_{{\textsf{SS}}.{\textsf{pp}}, C}(\cdot , \cdot )$ function is a deterministic linear function with coefficients ${{\textbf{c}}}= (c_\mu ,{{\textbf{c}}}_{{{\textbf{r}}}})$. The ${\textsf{KeyGen}}$ algorithm samples , runs

  

  and outputs ${\textsf{sk}}=([\![\delta ]\!]_2, {\textsf{isk}})$ as the secret key for C.

• ${\textsf{Enc}}({\textsf{mpk}}, {{\textbf{x}}}, \mu )$ takes as input the master public key ${\textsf{mpk}}$, an attribute ${{\textbf{x}}}\in {\{0,1\}}^{\ell }$, and a message $\mu \in {\{0,1\}}$. The algorithm runs

  

  and outputs ${\textsf{ct}}=({{\textbf{L}}}^{{\textbf{x}}}, {\textsf{ict}})$.

• ${\textsf{Dec}}({\textsf{mpk}}, {\textsf{sk}}, C, {\textsf{ct}}, {{\textbf{x}}})$ takes as input the master public key ${\textsf{mpk}}$, a secret key ${\textsf{sk}}$, its associated policy C, a ciphertext ${\textsf{ct}}$, and its associated attribute ${{\textbf{x}}}$. If $P({{\textbf{x}}}, C) = 0$, the algorithm outputs $\bot$ and terminates. Otherwise, it parses ${{\textsf{sk}}=([\![\delta ]\!]_2,{\textsf{isk}})}$, and computes the coefficients ${{\textbf{c}}}= (c_\mu , {{\textbf{c}}}_{{{\textbf{r}}}})$ for ${\textsf{ShareF}}_{{\textsf{SS}}.{\textsf{pp}},C}(\cdot ,\cdot )$ as in ${\textsf{KeyGen}}$. The algorithm next parses ${\textsf{ct}}$ into ${{\textbf{L}}}^{{{\textbf{x}}}}, {\textsf{ict}}$, and runs

  

  The algorithm applies the affine function $\gamma$ homomorphically in the exponent of $G_{{\textrm{T}}}$ to compute $\gamma (\Lambda _C)$. It then finds and outputs the unique $\mu '\in {\{0,1\}}$ (as the decrypted message) such that $\gamma (\Lambda _C) = [\![\mu ' \lfloor p/2\rceil + e]\!]_1[\![\delta ]\!]_2,$ for some $e\in [-B .. B]$, by enumerating over all possible e. Note: We show that the scheme is correct. By the correctness of IPFE and by linear function sharing of the secret sharing scheme, we have

  $$ \Lambda _C = [\![\delta (c_\mu \cdot \mu + {{\textbf{c}}}_{{{\textbf{r}}}}\cdot {{\textbf{r}}})]\!]_{{\textrm{T}}} = [\![\delta {\textsf{SS}}.{\textsf{ShareF}}_{{\textsf{SS}}.{\textsf{pp}}, C}(\mu , {{\textbf{r}}})]\!]_{{{\textrm{T}}}} = [\![\delta {{\textbf{L}}}_C]\!]_{{{\textrm{T}}}}. $$

  Therefore, $\gamma (\Lambda _C) = [\![\delta \gamma ({{\textbf{L}}}_C)]\!]_{{{\textrm{T}}}} = [\![\gamma ({{\textbf{L}}}_C)]\!]_1[\![\delta ]\!]_2$. By the correctness of the weakly nearly linear secret sharing scheme, the decryption algorithm outputs the correct bit $\mu ' =\mu$.

Efficiency. By Lemma 4, for MDDH dimension $k={\text {poly}}(\lambda )$ and input vector length $N=n+1$, the IPFE components have bit lengths $|{\textsf{impk}}|,|{\textsf{imsk}}|,|{\textsf{ict}}| = {\text {poly}}(\lambda , d),|{\textsf{isk}}| = {\text {poly}}(\lambda )$. Also recall that the secret sharing components have bit lengths $|{\textsf{SS}}.{\textsf{pp}}| = {\text {poly}}(\lambda ,d)\cdot \ell , |{{\textbf{L}}}_0| = |{{\textbf{L}}}_i^b| = {\text {poly}}(\lambda ,d), |{{\textbf{L}}}_C| = {\text {poly}}(\lambda )$. In the above construction,

• the master public key consists of ${\textsf{SS}}.{\textsf{pp}}$ and ${\textsf{impk}}$, hence has bit length

  $|{\textsf{mpk}}| = |{\textsf{SS}}.{\textsf{pp}}| + |{\textsf{impk}}| = {\text {poly}}(\lambda ,d)\cdot \ell$.

• The master secret key consists of ${\textsf{imsk}}$, hence has bit length

  $|{\textsf{msk}}| = |{\textsf{imsk}}|= {\text {poly}}(\lambda ,d)$.

• A secret key consists of a single ${\textsf{isk}}$, and $[\![\delta ]\!]_2$ in $G_2$, hence has bit length

  $|{\textsf{sk}}| = |{\textsf{isk}}| + |G_2| = {\text {poly}}(\lambda )$.

• A ciphertext consists of a single ${\textsf{ict}}$, and $\ell +1$ shares, hence has bit length

  $|{\textsf{ct}}| = |{\textsf{ict}}| + (\ell +1)|{{\textbf{L}}}_0| = {\text {poly}}(\lambda ,d)\cdot \ell$.

We now state adaptive IND-CPA security of the scheme. The proof can be found in the full version [31].

Proposition 6

Suppose in Construction 2, the IPFE scheme is selectively simulation-secure, and the secret sharing scheme is non-annihilable for ${{\textbf{L}}}_f$. Then the constructed KP-ABE scheme is adaptively IND-CPA in GGM.