Compact Adaptively Secure ABE for $\mathsf {NC^1}$ from k-Lin

Abstract

We present compact attribute-based encryption (ABE) schemes for $\mathsf {NC^1}$ that are adaptively secure under the k-Lin assumption with polynomial security loss. Our KP-ABE scheme achieves ciphertext size that is linear in the attribute length and independent of the policy size even in the many-use setting, and we achieve an analogous efficiency guarantee for CP-ABE. This resolves the central open problem posed by Lewko and Waters (CRYPTO 2011). Previous adaptively secure constructions either impose an attribute “one-use restriction” (or the ciphertext size grows with the policy size), or require q-type assumptions.

L. Kowalczyk—Supported in part by an NSF Graduate Research Fellowship DGE-16-44869; The Leona M. & Harry B. Helmsley Charitable Trust; ERC Project aSCEND (H2020 639554); the Defense Advanced Research Project Agency (DARPA) and Army Research Office (ARO) under Contract W911NF-15-C-0236; and NSF grants CNS-1445424, CNS-1552932 and CCF-1423306. Any opinions, findings and conclusions or recommendations expressed are those of the authors and do not necessarily reflect the views of the Defense Advanced Research Projects Agency, Army Research Office, the National Science Foundation, or the U.S. Government.

H. Wee—Supported in part by ERC Project aSCEND (H2020 639554).

1 Introduction

Attribute-based encryption (ABE) [17, 31] is a generalization of public-key encryption to support fine-grained access control for encrypted data. Here, ciphertexts and keys are associated with descriptive values which determine whether decryption is possible. In a key-policy ABE (KP-ABE) scheme for instance, ciphertexts are associated with attributes like ‘(author:Waters), (inst:UT), (topic:PK)’ and keys with access policies like ((topic:MPC) OR (topic:SK)) AND (NOT(inst:UCL)), and decryption is possible only when the attributes satisfy the access policy. A ciphertext-policy (CP-ABE) scheme is the dual of KP-ABE with ciphertexts associated with policies and keys with attributes.

Over past decade, substantial progress has been made in the design and analysis of ABE schemes, leading to a large families of schemes that achieve various trade-offs between efficiency, security and underlying assumptions. Meanwhile, ABE has found use as a tool for providing and enhancing privacy in a variety of settings from electronic medical records to messaging systems and online social networks. Moreover, we expect further deployment of ABE, thanks to the recent standardization efforts of the European Telecommunications Standards Institute (ETSI).

In this work, we consider KP-ABE schemes for access policies in $\mathsf {NC^1}$ that simultaneously:

• (1) enjoy compact ciphertexts whose size grows only with the length of the attribute and is independent of the policy size, even for complex policies that refer to each attribute many times;

• (2) achieve adaptive security (with polynomial security loss);

• (3) rely on simple hardness assumptions in the standard model;

• (4) can be built with asymmetric prime-order bilinear groups.

We also consider the analogous question for CP-ABE schemes with compact keys. In both KP and CP-ABE, all four properties are highly desirable from both a practical and theoretical stand-point and moreover, properties (1), (2) and (4) are crucial for many real-world applications of ABE. In addition, properties (2), (3) and (4) are by now standard cryptographic requirements pertaining to speed and efficiency, strong security guarantees under realistic and natural attack models, and minimal hardness assumptions. There is now a vast body of works on ABE (e.g. [17, 23, 26, 27], see Fig. 1) showing how different combinations of (1)–(4), culminating in several unifying frameworks that provide a solid understanding of the design and analysis of these schemes [1,2,3, 6, 34]. Nonetheless, prior to this work, it was not known how to even simultaneously realize (1)–(3) for $\mathsf {NC^1}$ access policies¹; indeed, this is widely regarded one of the main open problems in pairing-based ABE.

Our Results. We present the first KP-ABE and CP-ABE schemes for $\mathsf {NC^1}$ that simultaneously realize properties (1)–(4). Our KP-ABE scheme achieves ciphertext size that is linear in the attribute length and independent of the policy size even in the many-use setting; the same holds for the key size in our CP-ABE. Both schemes achieve adaptive security under the k-Lin assumption in asymmetric prime-order bilinear groups with polynomial security loss. We also present an “unbounded” variant of our compact KP-ABE scheme with constant-size public parameters.

As an immediate corollary, we obtain delegation schemes for $\mathsf {NC^1}$ with public verifiability and adaptive soundness under the k-Lin assumption [9, 26, 30].

Our construction leverages a refinement of the recent “partial selectivization” framework for adaptive security [20] (which in turn builds upon [12, 13, 18, 21]) along with the classic dual system encryption methodology [26, 33].

Fig. 1.

Summary of KP-ABE schemes for NC1

1.1 Technical Overview

Our starting point is the Lewko-Waters framework for constructing compact adaptively secure ABE [26] based on the dual system encryption methodology² [23, 25, 33]. Throughout, we focus on monotone $\mathsf {NC^1}$ circuit access policies, and note that the constructions extend readily to the non-monotone setting³. Let $(G_1,G_2,G_T)$ be an asymmetric bilinear group of prime order p, where g, h are generators of $G_1,G_2$ respectively.

Warm-Up. We begin with the prior compact KP-ABE for monotone $\mathsf {NC^1}$ [17, 23, 26]; this is an adaptively secure scheme that comes with the downside of relying on q-type assumptions (q-type assumptions are assumptions of size that grows with some parameter q. It is known that many q-type assumptions become stronger as q grows [10], and in general such complex and dynamic assumptions are not well-understood). The construction uses composite-order groups, but here we’ll suppress the distinction between composite-order and prime-order groups for simplicity. We associate ciphertexts $\mathsf {ct}_\mathbf {x}$ with attribute vectors⁴ $\mathbf {x}\in \{0,1\}^n$ and keys $\mathsf {sk}_f$ with Boolean formulas f:

(1)

where $\mu _1,\ldots ,\mu _m$ are shares of $\mu \in \mathbb {Z}_p$ w.r.t. the formula f; the shares satisfy the requirement that for any $\mathbf {x}\in \{0,1\}^n$, the shares $\{ \mu _j \}_{x_{\rho (j)} = 1}$ determine $\mu$ if $\mathbf {x}$ satisfies f (i.e., $f(\mathbf {x}) = 1$), and reveal nothing about $\mu$ otherwise; and $\rho$ is a mapping from the indices of the shares (in [m]) to the indices of the attributes (in [n]) to which they are associated. For decryption, observe that we can compute $\{ e(g,h)^{\mu _j s} \}_{x_i=1}$, from which we can compute the blinding factor $e(g,h)^{\mu s}$ via linear reconstruction “in the exponent”.

Here, m is polynomial in the formula size, and we should think of $m = {\text {poly}}(n) \gg n$. Note that the ciphertext consists only of O(n) group elements and therefore satisfies our compactness requirement.

Proving Adaptive Security. The crux of the proof of adaptive security lies in proving that $\mu$ remains computationally hidden given just a single ciphertext and a single key and no (the more general setting with and multiple keys follows via what is by now a textbook application of the dual system encryption methodology). In fact, it suffices to show that $\mu$ is hidden given just

where $\mathbf {x}, f$ are adaptively chosen subject to the constraint $f(\mathbf {x}) = 0$. Henceforth, we refer to $( \mathsf {ct}'_\mathbf {x}, \mathsf {sk}_f)$ as our “core 1-ABE component”. Looking ahead to our formalization of adaptive security for this core 1-ABE, we actually require that $\mu$ is hidden even if the adversary sees $h^{w_1},\ldots ,h^{w_n}$; this turns out to be useful for the proof of our KP-ABE (for improved concrete efficiency).

Core Technical Contribution. The technical novelty of this work lies in proving adaptive security of the core 1-ABE component under the DDH assumption. Previous analysis either relies on a q-type assumption [1, 2, 4, 26], or imposes the one-use restriction (that is, $\rho$ is injective and $m=n$, in which case security can be achieved unconditionally) [23, 34]. Our analysis relies on a piecewise guessing framework which refines and simplifies a recent framework of Jafargholi et al. for proving adaptive security via pebbling games [20] (which in turn builds upon [12, 13, 18, 21]).

Let denote the view of the adversary $( \mathsf {ct}'_\mathbf {x}, \mathsf {sk}_f)$ in the real game, and denote the same thing except we replace $\{\mu _j\}$ in $\mathsf {sk}_f$ with shares of a random value independent of $\mu$. Our goal is to show that . First, let us define an additional family of games parameterized by $U \subseteq [m]$: is the same as except we replace $\{\mu _j : j \in U\}$ in $\mathsf {sk}_f$ with uniformly random values. In particular, .

We begin with the “selective” setting, where the adversary specifies $\mathbf {x}$ at the start of the game. Suppose we can show that in this simpler setting via a series of $L+1$ hybrids of the form:

where $h_0,\ldots ,h_L : \{0,1\}^n \rightarrow \{ U \subseteq [m] : |U| \le R'\}$ are functions of the adversary’s choices $\mathbf {x}$. Then, the piecewise guessing framework basically tells us that in the adaptive setting with a security loss roughly $m^{R'} \cdot L$, where the factor L comes from the hybrid argument and the factor $m^{R'}$ comes from guessing $h_i(\mathbf {x})$ (a subset of [m] of size at most $R'$). Ideally, we would want $m^{R'} \ll 2^n$, where $2^n$ is what we achieve from guessing $\mathbf {x}$ itself.

First, we describe a straight-forward approach which achieves $L=2$ and $R' = m$ implicit in [26] (but incurs a huge security loss $2^m \gg 2^n$) where

$$h_1(\mathbf {x}) = \{ j : x_{\rho (j)} = 0 \}.$$

That is, is with $\mu _j$ in $\mathsf {sk}_f$ replaced by fresh $\mu '_j \leftarrow \mathbb {Z}_p$ for all j satisfying $x_{\rho (j)} = 0$. Here, we have

• via DDH, since $h^{\mu _j + w_{\rho (j)} r_j}, h^{r_j}$ computationally hides $\mu _j$ whenever $x_{\rho (j)} = 0$ and $w_{\rho (j)}$ is not leaked in $\mathsf {ct}_\mathbf {x}$;

• via security of the secret-sharing scheme since the shares $\{ \mu _j : x_{\rho (j)} = 1\}$ leak no information about $\mu$ whenever $f(\mathbf {x}) = 0$.

This approach is completely generic and works for any secret-sharing scheme.

In our construction, we use a variant of the secret-sharing scheme for $\mathsf {NC^1}$ in [20] (which is in turn a variant of Yao’s secret-sharing scheme [19, 32]), for which the authors also gave a hybrid argument achieving $L = 8^d$ and $R' = O(d \log m)$ where d is the depth of the formula; this achieves a security loss $2^{O(d \log m)}$. Recall that the circuit complexity class $\mathsf {NC^1}$ is captured by Boolean formulas of logarithmic depth and fan-in two, so the security loss here is quasi-polynomial in n. We provide a more detailed analysis of the functions $h_0,h_1,\ldots ,h_L$ used in their scheme, and show that the subsets of size O(d) output by these functions can be described only O(d) bits instead of $O(d \log m)$ bits. Roughly speaking, we show that the subsets are essentially determined by a path of length d from the output gate to an input gate, which can be described using O(d) bits since the gates have fan-in two. Putting everything together, this allows us to achieve adaptive security for the core 1-ABE component with a security loss $2^{O(d)} = {\text {poly}}(n)$.

Our ABE Scheme. To complete the overview, we sketch our final ABE scheme which is secure under the k-Linear Assumption in prime-order bilinear groups.

To obtain prime-order analogues of the composite-order examples, we rely on the previous framework of Chen et al. [5, 6, 15] for simulating composite-order groups in prime-order ones. Let $(G_1,G_2,G_T)$ be a bilinear group of prime order p. We start with the KP-ABE scheme in (1) and carry out the following substitutions:

$$\begin{aligned} g^s \mapsto [\mathbf {s}^{\top }\mathbf {A}]_1, \; h^{r_j} \mapsto [\mathbf {r}_j]_2, \; w_i \mapsto \mathbf {W}_i \leftarrow \mathbb {Z}_p^{(k+1) \times k}, \; \mu \mapsto \mathbf {v}\leftarrow \mathbb {Z}_p^{k+1} \end{aligned}$$

(2)

where $\mathbf {A}\leftarrow \mathbb {Z}_p^{k \times (k+1)},\mathbf {s}, \mathbf {r}_j \leftarrow \mathbb {Z}_p^k$, k corresponds to the k-Lin Assumption desired for security⁵, and $[\cdot ]_1,[\cdot ]_2$ correspond respectively to exponentiations in the prime-order groups $G_1,G_2$. We note that the naive transformation following [6] would have required $\mathbf {W}_i$ of dimensions at least $(k+1) \times (k+1)$; here, we incorporated optimizations from [5, 15]. This yields the following prime-order KP-ABE scheme for $\mathsf {NC^1}$:

where $\mathbf {v}_j$ is the j’th share of $\mathbf {v}$. Decryption proceeds as before by first computing

$$\{ e([\mathbf {s}^{\top }\mathbf {A}]_1,[\mathbf {v}_j]_2) \}_{\rho (j) = 0 \vee x_{\rho (j)} = 1}$$

and relies on the associativity relations $\mathbf {A}\mathbf {W}_i \cdot \mathbf {r}_j = \mathbf {A}\cdot \mathbf {W}_i \mathbf {r}_j$ for all i, j [8].

In the proof, in place of the DDH assumption which allows us to argue that $(h^{w_i r_j}, h^{r_j})$ is pseudorandom, we will rely on the fact that by the k-Lin assumption, we have

$$(\mathbf {A}, \mathbf {A}\mathbf {W}_i, [\mathbf {W}_i \mathbf {r}_j]_2, [\mathbf {r}_j]_2) \approx _c (\mathbf {A}, \mathbf {A}\mathbf {W}_i, [\mathbf {W}_i \mathbf {r}_j + \delta _{ij} \mathbf {a}^\perp ]_2, [\mathbf {r}_j]_2)$$

where $\mathbf {A}\leftarrow \mathbb {Z}_p^{k \times (k+1)}, \mathbf {W}_i \leftarrow \mathbb {Z}_p^{(k+1) \times 2k}, \mathbf {r}_j \leftarrow \mathbb {Z}_p^{2k}$ and $\mathbf {a}^\perp \in \mathbb {Z}_p^{k+1}$ satisfies $\mathbf {A}\cdot \mathbf {a}^\perp = \mathbf {0}$.

Organization. We describe the piecewise guessing framework for adaptive security in Sect. 3 and a pebbling strategy (used to define $h_0,\ldots ,h_L$) in Sect. 4. We describe a secret-sharing scheme and prove adaptive security of the core 1-ABE component in Sect. 5. We present our full KP-ABE scheme in Sect. 6, and present a CP-ABE and unbounded KP-ABE scheme in the full version of this paper [22].

2 Preliminaries

Notation. We denote by $s \leftarrow S$ the fact that s is picked uniformly at random from a finite set S. By PPT, we denote a probabilistic polynomial-time algorithm. Throughout this paper, we use $1^\lambda$ as the security parameter. We use lower case boldface to denote (column) vectors and upper case boldcase to denote matrices. We use $\equiv$ to denote two distributions being identically distributed, and $\approx _c$ to denote two distributions being computationally indistinguishable. For any two finite sets (also including spaces and groups) $S_1$ and $S_2$, the notation “$S_1 \approx _c S_2$” means the uniform distributions over them are computationally indistinguishable.

2.1 Monotone Boolean Formulas and $\mathsf {NC^1}$

Monotone Boolean Formula. A monotone Boolean formula $f : \{0,1\}^n \rightarrow \{0,1\}$ is specified by a directed acyclic graph (DAG) with three kinds of nodes: input gate nodes, gate nodes, and a single output node. Input nodes have in-degree 0 and out-degree 1, AND/OR nodes have in-degree (fan-in) 2 and out-degree (fan-out) 1, and the output node has in-degree 1 and out-degree 0. We number the edges (wires) $1,2,\ldots ,m$, and each gate node is defined by a tuple $(g,a_g,b_g,c_g)$ where $g : \{0,1\}^2 \rightarrow \{0,1\}$ is either AND or OR, $a_g,b_g$ are the incoming wires, $c_g$ is the outgoing wire and $a_g,b_g < c_g$. The size of a formula m is the number of edges in the underlying DAG and the depth of a formula d is the length of the longest path from the output node.

$\mathsf {NC^1}$ and Log-Depth Formula. A standard fact from complexity theory tells us that the circuit complexity class monotone $\mathsf {NC^1}$ is captured by monotone Boolean formulas of log-depth and fan-in two. This follows from the fact that we can transform any depth d circuit with fan-in two and unbounded fan-out into an equivalent circuit with fan-in two and fan-out one (for all gate nodes) of the same depth, and a $2^d$ blow-up in the size. To see this, note that one can start with the root gate of an $\mathsf {NC^1}$ circuit and work downward by each level of depth. For each gate g considered at depth i, if either of its two input wires are coming from the output wire of a gate (at depth $i-1$) with more than one output wire, then create a new copy of the gate at depth $i-1$ with a single output wire going to g (note that this copy may increase the output wire multiplicity of gates at depth strictly lower than $i-1$). This procedure preserves the functionality of the original circuit, and has the result that at its end, each gate in the circuit has input wires which come from gates with output multiplicity 1. The procedure does not increase the depth of the circuit (any duplicated gates are added at a level that already exists), so the new circuit is a formula (all gates have fan-out 1) of depth d with fan-in 2, so its size is at most $2^d$. d is logarithmic in the size of the input for $\mathsf {NC^1}$ circuits, so the blowup from this procedure is polynomial in n. Hence we will consider the class $\mathsf {NC^1}$ as a set of Boolean formulas (where gates have fan-in 2 and fan-out 1) of depth $O(\log n)$ and refer to $f \in \mathsf {NC^1}$ formulas.

2.2 Secret Sharing

A secret sharing scheme is a pair of algorithms $(\mathsf {share}, \mathsf {reconstruct})$ where $\mathsf {share}$ on input $f : \{0,1\}^n \rightarrow \{0,1\}$ and $\mu \in \mathbb {Z}_p$ outputs $\mu _1,\ldots ,\mu _m \in \mathbb {Z}_p$ together with $\rho : [m] \rightarrow \{0,1,\ldots ,n\}$.

• Correctness stipulates that for every $x \in \{0,1\}^n$ such that $f(x) = 1$, we have

  $$\mathsf {reconstruct}(f,x, \{ \mu _j \}_{\rho (j) = 0 \vee x_{\rho (j)} = 1}) = \mu .$$

• Security stipulates that for every $x \in \{0,1\}^n$ such that $f(x)=0$, the shares $\{ \mu _j \}_{\rho (j) = 0 \vee x_{\rho (j)} = 1}$ perfectly hide $\mu$.

Note the inclusion of $\rho (j) = 0$ in both correctness and security. All the secret sharing schemes in this work will in fact be linear (in the standard sense): $\mathsf {share}$ computes a linear function of the secret $\mu$ and randomness over $\mathbb {Z}_p$, and $\mathsf {reconstruct}$ computes a linear function of the shares over $\mathbb {Z}_p$, that is, $\mu = \sum _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \omega _j \mu _j$.

2.3 Attribute-Based Encryption

An attribute-based encryption (ABE) scheme for a predicate $\textsf {\small {pred} }(\,\cdot \,,\,\cdot \,)$ consists of four algorithms $(\mathsf {Setup}, \mathsf {Enc},\mathsf {KeyGen},\mathsf {Dec})$:

• . The setup algorithm gets as input the security parameter $\lambda$, the attribute universe $\mathcal {X}$, the predicate universe $\mathcal {Y}$, the message space $\mathcal {M}$ and outputs the public parameter , and the master key .

• . The encryption algorithm gets as input , an attribute $x \in \mathcal {X}$ and a message $m\in \mathcal {M}$. It outputs a ciphertext $\mathsf {ct}_{x}$. Note that x is public given $\mathsf {ct}_x$.

• . The key generation algorithm gets as input and a value $y \in \mathcal {Y}$. It outputs a secret key $\mathsf {sk}_{y}$. Note that y is public given $\mathsf {sk}_y$.

• $\mathsf {Dec}( \mathsf {mpk}, \mathsf {sk}_{y}, \mathsf {ct}_x ) \rightarrow m$. The decryption algorithm gets as input $\mathsf {sk}_y$ and $\mathsf {ct}_x$ such that $\textsf {\small {pred} }(x,y)=1$. It outputs a message m.

Correctness. We require that for all $(x,y) \in \mathcal {X}\times \mathcal {Y}$ such that $\textsf {\small {pred} }(x,y)=1$ and all $m\in \mathcal {M}$,

where the probability is taken over , , and the coins of $\mathsf {Enc}$.

Security Definition. For a stateful adversary $\mathcal {A}$, we define the advantage function

with the restriction that all queries y that $\mathcal {A}$ makes to satisfy $\textsf {\small {pred} }(x^*,y) = 0$ (that is, $\mathsf {sk}_y$ does not decrypt $\mathsf {ct}_{x^*}$). An ABE scheme is adaptively secure if for all PPT adversaries $\mathcal {A}$, the advantage $\mathsf {Adv}^{\textsc {abe}}_{\mathcal {A}}(\lambda )$ is a negligible function in $\lambda$.

2.4 Prime-Order Bilinear Groups and the Matrix Diffie-Hellman Assumption

A generator $\mathcal {G}$ takes as input a security parameter $\lambda$ and outputs a group description $\mathbb {G} := (p,G_1,G_2,G_T,e)$, where p is a prime of $\varTheta (\lambda )$ bits, $G_1$, $G_2$ and $G_T$ are cyclic groups of order p, and $e : G_1 \times G_2 \rightarrow G_T$ is a non-degenerate bilinear map. We require that the group operations in $G_1$, $G_2$ and $G_T$ as well the bilinear map e are computable in deterministic polynomial time with respect to $\lambda$. Let $g_1 \in G_1$, $g_2 \in G_2$ and $g_T = e(g_1,g_2) \in G_T$ be the respective generators. We employ the implicit representation of group elements: for a matrix $\mathbf {M}$ over $\mathbb {Z}_p$, we define $[\mathbf {M}]_1:=g_1^{\mathbf {M}},[\mathbf {M}]_2:=g_2^{\mathbf {M}},[\mathbf {M}]_T:=g_T^{\mathbf {M}}$, where exponentiation is carried out component-wise. Also, given $[\mathbf {A}]_1,[\mathbf {B}]_2$, we let $e([\mathbf {A}]_1,[\mathbf {B}]_2) = [\mathbf {A}\mathbf {B}]_T$.

We define the matrix Diffie-Hellman (MDDH) assumption on $G_1$ [11]:

Definition 1

(${\mathbf {MDDH}}^{m}_{k,\ell }$  Assumption). Let $\ell > k \ge 1$ and $m \ge 1$. We say that the $\textit{MDDH}_{k,\ell }^{m}$ assumption holds if for all PPT adversaries $\mathcal {A}$, the following advantage function is negligible in $\lambda$.

where $\mathbf {M}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{\ell \times k}$, $\mathbf {S}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{k \times m}$ and $\mathbf {U}\leftarrow _{\textsc {r}}\mathbb {Z}_p^{\ell \times m}$.

The MDDH assumption on $G_2$ can be defined in an analogous way. Escala et al. [11] showed that

$$\begin{aligned} k\text{-Lin } \Rightarrow \text {MDDH}_{k,k+1}^1 \Rightarrow \text {MDDH}_{k,\ell }^m\; \forall \ell > k, m \ge 1 \end{aligned}$$

with a tight security reduction (that is, ). In fact, the MDDH assumption is a generalization of the k-Lin Assumption, such that the k-Lin Assumption is equivalent to the $\text {MDDH}^{1}_{k,k+1}$ Assumption as defined above.

Definition 2

(k-Lin Assumption). Let $k \ge 1$. We say that the k-Lin Assumption holds if for all PPT adversaries $\mathcal {A}$, the following advantage function is negligible in $\lambda$.

Henceforth, we will use $\text {MDDH}_{k}$ to denote $\text {MDDH}_{k,k+1}^1$. Lastly, we note that the k-Lin Assumption itself is a generalization, where setting $k=1$ yields the Symmetric External Diffie-Hellman Assumption (SXDH), and setting $k=2$ yields the standard Decisional Linear Assumption (DLIN).

3 Piecewise Guessing Framework for Adaptive Security

We now refine the adaptive security framework of [20], making some simplifications along the way to yield the piecewise guessing framework that will support our security proof. We use to denote the output of an adversary $\mathsf {A}$ in an interactive game , and an adversary wins if the output is 1, so that the winning probability is denoted by .

Suppose we have two adaptive games and which we would like to show to be indistinguishable. In both games, an adversary $\mathsf {A}$ makes some adaptive choices that define $z \in \{0,1\}^R$. Informally, the piecewise guessing framework tells us that if we can show that are $\epsilon$-indistinguishable in the selective setting where all choices defining z are committed to in advance via a series of $L+1$ hybrids, where each hybrid depends only on at most $R' \ll R$ bits of information about z, then are $2^{2R'} \cdot L \cdot \epsilon$-indistinguishable in the adaptive setting.

Overview. We begin with the selective setting where the adversary commits to $z = z^*$ in advance. Suppose we can show that in this simpler setting via a series of $L+1$ hybrids of the form:

where $h_0,\ldots ,h_L : \{0,1\}^R \rightarrow \{0,1\}^{R'}$ and $\{\mathsf {H}^u\}_{u \in \{0,1\}^{R'}}$ is a family of games where the messages sent to the adversary in $\mathsf {H}^u$ depend on u.⁶ In particular, the $\ell$’th hybrid only depends on $h_\ell (z^*)$ where $|h_\ell (z^*)| \ll |z^*|$.

Next, we describe how to slightly strengthen this hybrid sequence so that we can deduce that even for an adaptive choice of z. Note that $\{\mathsf {H}^u\}_{u \in \{0,1\}^{R'}}$ is now a family of adaptive games where z is adaptively defined as the game progresses. We have two requirements:

The first, end-point equivalence, just says the two equivalences

hold even in the adaptive setting, that is, even if the adversary’s behavior defines an z different from $z^*$. In our instantiation, $h_0$ and $h_L$ are constant functions, so this equivalence will be immediate.

The second, neighbor indistinguishability, basically says that for any $\ell \in [L]$, we have

$$\begin{aligned} \mathsf {H}^{u_0} \approx _c \mathsf {H}^{u_1}, \;\forall \, u_0,u_1 \in \{0,1\}^{R'} \end{aligned}$$

as long as the adversary chooses z such that $h_{\ell -1}(z) = u_0 \wedge h_{\ell }(z) = u_1$ It is easy to see that this is a generalization of $\mathsf {H}^{h_{\ell -1}(z^*)} \approx _c \mathsf {H}^{h_{\ell }(z^*)}$ if we require $z = z^*$. To formalize this statement, we need to formalize the restriction on the adversary’s choice of z by having the game output 0 whenever the restriction is violated. That is, we define a pair of “selective” games $\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1),\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1)$ for any $u_0,u_1 \in \{0,1\}^{R'}$, where

$\widehat{\mathsf {H}}_{\ell ,b}(u_0,u_1)$ is the same as $\mathsf {H}^{u_{b}}$, except we replace the output with 0 whenever $(h_{\ell -1}(z),h_\ell (z)) \ne (u_0,u_1)$.

That is, in both games, the adversary “commits” in advance to $u_0,u_1$. Proving indistinguishability here is easier because the reduction knows $u_0,u_1$ and only needs to handle adaptive choices of z such that $(h_{\ell -1}(z),h_\ell (z)) = (u_0,u_1)$.

Adaptive Security Lemma. The next lemma tells us that the two requirements above implies that with a security loss $2^{2R'} \cdot L$ (stated in the contra-positive). In our applications, $2^{R'}$ and L will be polynomial in the security parameter.

Lemma 1

(adaptive security lemma). Fix along with $h_0,h_1,\ldots ,h_L : \{0,1\}^R \rightarrow \{0,1\}^{R'}$ and $\{ \mathsf {H}^u \}_{u \in \{0,1\}^{R'}}$ such that

Suppose there exists an adversary $\mathsf {A}$ such that then there exists $\ell \in [L]$ and $u_0,u_1 \in \{0,1\}^{R'}$ such that

$$ \Pr [\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1) \rangle = 1] - \Pr [\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1) \rangle = 1] \ge \frac{\epsilon }{2^{2R'}L}$$

This lemma is essentially a restatement of the main theorem of [20, Theorem 2]; we defer a comparison to the end of this section.

Proof

For the proof, we need to define the game $\mathsf {H}_\ell (z^*)$ for all $\ell =0,1,\ldots ,L$ and all $z^* \in \{0,1\}^{R}$

$\mathsf {H}_\ell (z^*)$ is the same as $\mathsf {H}^{h_\ell (z^*)}$, except we replace the output with 0 whenever $z \ne z^*$.

Roughly speaking, in $\mathsf {H}_\ell (z^*)$, the adversary “commits” to making choices $z = z^*$ in advance.

• Step 1. We begin the proof by using “random guessing” to deduce that

  $$ \mathop {\Pr }_{z^* \leftarrow \{0,1\}^R}[\langle \mathsf {A},\mathsf {H}_0(z^*) \rangle = 1] - \mathop {\Pr }_{z^* \leftarrow \{0,1\}^R}[\langle \mathsf {A},\mathsf {H}_L(z^*) \rangle = 1] \ge \frac{\epsilon }{2^R} $$

  This follows from the fact that which implies

  

• Step 2. Via a standard hybrid argument, we have that there exists $\ell$ such that

  $$\mathop {\Pr }_{z^* \leftarrow \{0,1\}^R}[\langle \mathsf {A},\mathsf {H}_{\ell -1}(z^*) \rangle = 1] - \mathop {\Pr }_{z^* \leftarrow \{0,1\}^R}[\langle \mathsf {A},\mathsf {H}_\ell (z^*) \rangle = 1] \ge \frac{\epsilon }{2^R L} $$

  which implies that:

  $$ \sum _{z' \in \{0,1\}^R}[\langle \mathsf {A},\mathsf {H}_{\ell -1}(z') \rangle = 1] - \sum _{z' \in \{0,1\}^R}[\langle \mathsf {A},\mathsf {H}_\ell (z') \rangle = 1] \ge \frac{\epsilon }{ L } $$

• Step 3. Next, we relate $\widehat{\mathsf {H}}_{\ell ,0},\widehat{\mathsf {H}}_{\ell ,1}$ and $\mathsf {H}_{\ell -1},\mathsf {H}_\ell$. First, we define the set

  $$\begin{aligned} \mathcal {U}_\ell := \{ (h_{\ell -1}(z'),h_\ell (z')) : z' \in \{0,1\}^R \} \subseteq \{0,1\}^{R'} \times \{0,1\}^{R'}, \ell \in [L] \end{aligned}$$

  Observe that for all $(u_0,u_1) \in \mathcal {U}_\ell$, we have

  $$ \Pr [\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1) \rangle = 1] = \sum _{z' : (h_{\ell -1}(z'),h_\ell (z')) = (u_0,u_1)} \Pr [\langle \mathsf {A},\mathsf {H}_\ell (z') \rangle = 1]$$

  Then, we have

  

  By the same reasoning, we also have

  $$\begin{aligned} \sum _{z' \in \{0,1\}^R} \Pr [\langle \mathsf {A},\mathsf {H}_{\ell -1}(z') \rangle = 1] = \sum _{(u_0,u_1) \in \mathcal {U}_\ell } \Pr [\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1) \rangle = 1] \end{aligned}$$

  This means that

  

  where the last inequality follows from Step 2.

• Step 4. By an averaging argument, and using the fact that $|\mathcal{U}_\ell | \le 2^{2R'}$, there exists $(u_0,u_1) \in \mathcal {U}_\ell$ such that

  $$ \Pr [\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1) \rangle = 1] - \Pr [\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1) \rangle = 1] \ge \frac{\epsilon }{2^{2R'}L} $$

This completes the proof. Note that $2^{2R'}$ can be replaced by $\max _\ell |\mathcal {U}_\ell |$.    $\square$

Comparison with [20]. Our piecewise guessing framework makes explicit the game $\mathsf {H}^u$ which are described implicitly in the applications of the framework in [20]. Starting from $\mathsf {H}^u$ and $h_0,\ldots ,h_L$, we can generically specify the intermediate games $\widehat{\mathsf {H}}_{\ell ,0},\widehat{\mathsf {H}}_{\ell ,1}$ as well as the games $\mathsf {H}_0,\ldots ,\mathsf {H}_L$ used in the proof of security. The framework of [20] does the opposite: it starts with the games $\mathsf {H}_0,\ldots ,\mathsf {H}_L$, and the theorem statement assumes the existence of $h_0,\ldots ,h_L$ and $\widehat{\mathsf {H}}_{\ell ,0},\widehat{\mathsf {H}}_{\ell ,1}$ that are “consistent” with $\mathsf {H}_0,\ldots ,\mathsf {H}_L$ (as defined via a “selectivization” operation). We believe that starting from $\mathsf {H}^u$ and $h_0,\ldots ,h_L$ yields a simpler and clearer framework which enjoys the advantage of not having to additionally construct and analyze $\widehat{\mathsf {H}}_{\ell ,0},\widehat{\mathsf {H}}_{\ell ,1}$ and $\mathsf {H}_\ell$ in the applications.

Finally, we point out that the sets $\mathcal {U}$ and $\mathcal {W}$ in [20, Theorem 2] corresponds to $\mathcal {U}_\ell$ and $\{0,1\}^R$ over here (that is, we do obtain the same bounds), and the i’th function $h_i$ corresponds to the $\ell$’th function $h_{\ell -1} \circ h_\ell$ over here.

4 Pebbling Strategy for $\mathsf {NC^1}$

We now define a pebbling strategy for $\mathsf {NC^1}$ which will be used to define the functions $h_0,\ldots ,h_L$ we’ll use in the piecewise guessing framework. Fix a formula $f : \{0,1\}^n \rightarrow \{0,1\}$ of size m and an input $x \in \{0,1\}^n$ for which $f(x) = 0$. A pebbling strategy specifies a sequence of L subsets of [m], corresponding to subsets of input nodes and gates in f that are pebbled. We refer to each subset in the sequence as a pebbling configuration and the i’th term in this sequence is the output of $h_i(f,x)$ (where the combination of f, x correspond to the adaptive choices z made in our security game that will be later analyzed in the piecewise guessing framework).

Our pebbling strategy is essentially the same as that in [20, Section 4]; the main difference is that we provide a better bound on the size of the description of each pebbling configuration in Theorem 1.

4.1 Pebbling Rules

Fix a formula $f : \{0,1\}^n \rightarrow \{0,1\}$ and an input $x \in \{0,1\}^n$ for which $f(x) = 0$. We are allowed to place or remove pebbles on input nodes and gates in f, subject to some rules. The goal of a pebbling strategy is to find a sequence of pebbling instructions that follow the rules and starting with the initial configuration (in which there are no pebbles at all), will end up in a configuration where only the root gate has a pebble. Intuitively, the rules say that we can place a pebble a node or a gate if we know that the out-going wire will be 0. More formally,

Definition 3

(Pebbling Rules)

• 1. Can place or remove a pebble on any AND gate for which (at least) one input wire comes out of a node with a pebble on it.

• 2. Can place or remove a pebble on any OR gate for which all of the incoming wires come out of nodes which have pebbles on them.

• 3. Can place or remove a pebble on any input node for which $x_i = 0$.

Given (f, x), a pebbling strategy returns a sequence of pebbling instructions of the form or un for some gate g, with the property that each successively applied instruction follows the pebbling rules in Definition 3.

4.2 Pebbling Strategy

Given an $\mathsf {NC^1}$ formula f (recall Sect. 2.1) and an input x on which the formula evaluates to 0, consider the pebbling instruction sequence returned by the following recursive procedure, which maintains the invariant that the output wire evaluates to 0 for each gate that the procedure is called upon. The strategy is described in Fig. 2 and begins by calling $\mathsf {Pebble}(f, x, g^*)$ on the root gate $g^*$. We give an example in Fig. 3.

Fig. 2.

$\mathsf {NC^1}$ formula pebbling strategy.

Fig. 3.

Intermediate pebbling configurations on input $x = 001$. The thick black outline around a node corresponds to having a pebble on the node. Note that steps 10–17 correspond to “undoing” steps 1–8 so that at the end of step 17, there is exactly one pebble on the $\vee$ node leading to the output node.

Note that if this procedure is called on the root gate of a formula f with an input x such that $f(x)=0$, then every AND gate on which the $\mathsf {Pebble}()$ procedure is called will have at least one child node with an output wire which evaluates to 0, and every OR gate on which the $\mathsf {Pebble}()$ procedure is called will have child nodes with output wires which both evaluate to 0. Furthermore, by inspection, $\mathsf {Pebble}(f,x,g^*)$ returns a sequence of pebbling instructions for the circuit that follows the rules in Definition 3.

4.3 Analysis

To be useful in the piecewise guessing framework, we would like for the sequence of pebbling instructions to have the property that each configuration formed by successive applications of the instructions in the sequence is as short to describe as possible (i.e., minimize the maximum representation size $R'$). One way to achieve this is to have, at any configuration along the way, as few pebbles as possible. An even more succinct representation can be obtained if we allow many pebbles but have a way to succinctly represent their location. Additionally, we would like to minimize the worst-case length, L, of any sequence produced. We achieve these two goals in the following theorem.

Theorem 1

(pebbling $\mathsf {NC^1}$). For every input $x \in \{0,1\}^n$ and any monotone formula f of depth d and fan-in two for which $f(x) = 0$, there exists a sequence of $L(d) = 8^d$ pebbling instructions such that every intermediate pebbling configuration can be described using $R'(d) = 3d$ bits.

Proof

Follows from the joint statements of Lemmas 2 and 4 applied to the pebbling strategy in Fig. 2.

Comparison with [20]. Note that the strategy reproduced in Fig. 2 is essentially the same as one analyzed by [20], which argued that every configuration induced by the pebbling instruction sequence it produces can be described using $d (\log m+2)$ bits, where m is the number of wires in the formula. This follows from the fact that each such pebbling configuration has at most d gates with pebbled children, and we can specify each such gate using $\log m$ bits and the pebble-status of its two children using an additional two bits. Our Lemma 4 analyzes the same pebbling strategy but achieves a more succinct representation by leveraging the fact that not all configurations of d pebbled gates are possible due to the pebbling strategy used, so we don’t need the full generality allowed by $d \cdot \log m$ bits. Instead, Lemmas 3 and 4 show that every configuration produced follows a pattern that can be described using only 3d bits.

Lemma 2

([20]). The pebbling strategy in Fig. 2 called on the root gate $g^*$ for a formula f of depth d with assignment x such that $f(x)=0$, $\mathsf {Pebble}(f, x, g^*)$, returns a sequence of instructions of length at most $L(d) \le 8^{d}$.

This bound is a special case of that shown in [20, Lemma 2] for fan-in two circuits.

Proof

This statement follows inductively on the depth of the formula on which $\mathsf {Pebble}()$ is called.

For the base case, when $d = 0$ (and $\mathsf {Pebble}$ has therefore been called on an input node) there is just one instruction returned, and: $1 \le 8^{0}$

When $\mathsf {Pebble}()$ is called on a node at depth $d>0$, the node is either an OR gate or an AND gate.

When $\mathsf {Pebble}()$ is called on an OR gate, using our inductive hypothesis for the instructions returned for the subformula of depth $d-1$, notice that the number of instructions returned is:

$$\begin{aligned}L(d-1) + L(d-1) + 1 + L(d-1) + L(d-1) = 8^{d-1} + 8^{d-1} + 1 + 8^{d-1} + 8^{d-1} = 4 \cdot 8^{d-1 } + 1 \le 8^{d}\end{aligned}$$

When $\mathsf {Pebble}()$ is called on an AND gate, using our inductive hypothesis for the instructions returned for the subformula of depth $d-1$, notice that the number of instructions returned is:

$$L(d-1) + 1 + L(d-1) = 8^{d-1} + 1 + 8^{d-1} = 2 \cdot 8^{(d-1) } + 1 \le 8^{d}$$

   $\square$

We note that the following lemma is new to this work and will be used to bound the representation size R(d) of any configuration produced by application of the instructions output by the pebbling strategy.

Lemma 3

(structure of pebbling configuration). Every configuration induced by application of the instructions produced by the pebbling strategy in Fig. 2 called on the root gate $g^*$ of a formula f of depth d with assignment x such that $f(x)=0$, $\mathsf {Pebble}(f, x, g^*)$, has the following property for all gates g in f with children $g_L, g_R$:

If any node in the sub-tree rooted at $g_R$ is pebbled, then there exists at most one pebble on the sub-tree rooted at $g_L$, namely a pebble on $g_L$ itself

Proof

Call a node “good” if it satisfies the property above. First, we make the following observation about the behavior of $\mathsf {Reverse}()$: Applying $\mathsf {Reverse}()$ to a list of instructions inducing a list of configurations for which all nodes are “good” produces a new list for which this is true. This holds since $\mathsf {Reverse}()$ does not change the configurations induced by a list of instructions, just the ordering (which is reversed). This follows from a simple proof by induction on the length of the input instruction list and the fact that for an input list of instructions parsed as $L_1 \circ L_2$ for two smaller-length lists, we can implement $\mathsf {Reverse}(L_1 \circ L_2)$ as $\mathsf {Reverse}(L_2) \circ \mathsf {Reverse}(L_1)$.

We proceed with our original proof via a proof by induction on the depth of the formula upon which $\mathsf {Pebble}()$ is called.

Inductive Hypothesis: For formulas f of depth $d-1$ with root gate $g^*$ and assignment x such that $f(x)=0$, $\mathsf {Pebble}(f, x, g^*)$ returns a sequence of instructions that induces a sequence of configurations that (1) end with a configuration where $g^*$ is the only pebbled node, and satisfies: (2) in every configuration all nodes are “good.”

Base Case: when $\mathsf {Pebble}(f, x, g^*)$ is called on a formula of depth 0, the formula consists of just an input node $g^*$. The (single) returned instruction then satisfies that in both the initial and final configuration, the single node $g^*$ is good. Also, the sequence ends in the configuration where $g^*$ is the only pebbled node.

Inductive Step: when $\mathsf {Pebble}(f, x, g^*)$ is called on formula of depth $d > 0$. Let $g^*_L,g^*_R$ denote the children of the root gate $g^*$ (either an AND or OR gate). Note that the sub-formulas $f_{g^*_L}$ and $f_{g^*_R}$ rooted at $g^*_L$ and $g^*_R$ have depth $d-1$. We proceed via a case analysis:

If $g^*$ is an AND gate, then suppose the sequence of instructions returned is

(The case with $g^*_L$ instead of $g^*_R$ is handled analogously, even simpler). Suppose $\mathsf {Pebble}(f_{g^*_R}, x, g^*_R)$ (and thus $\mathsf {Reverse}(\mathsf {Pebble}(f_{g^*_R}, x, g^*_R))$) produces $L_0$ instructions. We proceed via a case analysis:

• Take any of the first $L_0$ configurations (starting from 0’th). Here, all pebbles are in the subformula rooted at $g^*_R$. We can then apply part (2) of the inductive hypothesis to the subformula $f_{g^*_R}$ rooted at $g^*_R$ (of depth $d-1$) to deduce that property “good” holds for all nodes in $f_{g^*_R}$. All nodes in $f_{g^*_L}$ are unpebbled in all configurations, so they are automatically good. Lastly, the root gate $g^*$ has no pebbled nodes in the subformula rooted at $g_L$, so it is also good.

• For the $(L_0+1)$’th configuration reached after , there are only two pebbles, one on $g^*$ (from the instruction) and another on $g^*_R$ (from part (1) of our inductive hypothesis applied to the (depth $d-1$) subformula $f_{g^*_R}$). It is clear that all nodes in this configuration are good.

• For the last $L_0$ configurations, there is one pebble on $g^*$ and all remaining pebbles are in the subformula rooted at $g^*_R$. Clearly, $g^*$ is good. All nodes in $f_{g^*_L}$ are unpebbled in all configurations, so they are also good. Moreover, we can apply the inductive hypothesis to $f_{g^*_R}$ combined with our observation that $\mathsf {Reverse}$ preserves property (2) of this hypothesis to deduce that all nodes in the subformula are also good for all configurations.

Lastly, notice that since the last $L_0$ instructions undo the first $L_0$ instructions, the final configuration features a single pebble on $g^*$.

If $g^*$ is an OR gate, then the sequence of instructions returned is

Suppose $\mathsf {Pebble}(f_{g^*_R}, x, g^*_R), \mathsf {Pebble}(f_{g^*_L}, x, g^*_L)$, and thus $\mathsf {Reverse}(\mathsf {Pebble}(f_{g^*_R},$ $x, g^*_R))$, $\mathsf {Reverse}(\mathsf {Pebble}(f_{g^*_L}, x, g^*_L))$, produces $L_0, L_1$ instructions. We proceed via a case analysis:

• Take any of the first $L_0$ configurations (starting from 0’th). Here, all pebbles are in the subformula $f_{g^*_L}$ rooted at $g^*_L$. We can then apply part (2) of the inductive hypothesis to (depth $d-1$) $f_{g^*_L}$ to deduce that property “good” holds for all nodes in $f_{g^*_L}$. All nodes in the subformula rooted at $g^*_R$, $f_{g^*_R}$, are unpebbled in all configurations, so they are automatically good. Lastly, the root gate $g^*$ has no pebbled nodes in the subformula rooted at $g^*_R$, so it is also good. Finally, by part (1) of this application of the inductive hypothesis, we know that $L_0$th configuration features a single pebble on $g^*_L$.

• Take any of the next $L_1$ configurations (starting from the $L_0$’th). Here, all pebbles are in the subformula rooted at $g^*_R$ except for the single pebble on $g^*_L$. We can then apply part (2) of the inductive hypothesis to (depth $d-1$) $f_{g^*_R}$ (of depth $d-1$) to deduce that property “good” holds for all nodes in $f_{g^*_R}$. All nodes in the subformula rooted at $g^*_L$ have no pebbles in their own subformulas, so they are automatically good. Lastly, the root gate $g^*$ may have pebbled nodes in the subformula rooted at $g^*_R$ but the only pebbled node in the subformula rooted at $g^*_L$ is $g^*_L$ itself, so it is also good. Finally, we know that the $L_0 + L_1$th configuration features two pebbles: a pebble on $g^*_L$ (from the first $L_0$ instructions), and a pebble on $g^*_R$ (by part (1) of this application of the inductive hypothesis).

• For the $(L_0+ L_1+ 1)$’th configuration reached after , there are only three pebbles, one on $g^*$ (from the instruction), one on $g^*_L$ (from the first $L_0$ instructions), and another on $g^*_R$ (from the next $L_1$ instructions). It is clear that all nodes in this configuration are good.

• For the next $L_1$ configurations (reversing the instructions of the set of size $L_1$), there is one pebble on $g^*$, one pebble on $g^*_L$, and all remaining pebbles are in the subformula rooted at $g^*_R$, $f_{g^*_R}$. $g^*$ is good, since it only has one pebble in the subformula rooted at $g^*_L$, on $g^*_L$ itself. All nodes in the subformula rooted at $g^*_L$ have no pebbles in their own subformulas, so they are also good. Moreover, we can apply the inductive hypothesis to (depth $d-1$) $f_{g^*_R}$ combined with our observation that $\mathsf {Reverse}$ preserves property (2) of this hypothesis to deduce that all nodes in $f_{g^*_R}$ are also good for all configurations. Note the final configuration in this sequence then contains two pebbles, one of $g^*$ and one on $g^*_L$.

• For the final $L_0$ configurations (reversing the instructions of the set of size $L_0$), there is one pebble on $g^*$, and all remaining pebbles are in the subformula rooted at $g^*_L$. $g^*$ is good, since it has no pebbles in the subformula rooted at $g^*_R$. Similarly, all nodes in the subformula rooted at $g^*_R$ are also good. Moreover, we can apply the inductive hypothesis to (depth $d-1$) $f_{g^*_L}$ combined with our observation that $\mathsf {Reverse}$ preserves property (2) of this hypothesis to deduce that all nodes in $f_{g^*_L}$ are also good for all configurations.

Lastly, notice that since the last $L_0 + L_1$ instructions undo the first $L_0+L_1$ instructions, the final configuration features a single pebble on $g^*$.    $\square$

Lemma 4

($R'(d) = 3d$). Every configuration induced by application of the instructions produced by the pebbling strategy in Fig. 2 for a formula f of depth d with assignment x such that $f(x)=0$ can be described using $R'(d) = 3d$ bits.

Proof

We can interpret 3d bits in the following way to specify a pebbling: the first d bits specify a path down the formula starting at the root gate (moving left or right based on the setting of each bit), the next $2(d-1)$ bits specify, for each of the $(d-1)$ non-input nodes along the path, which of its children are pebbled. Finally one of the last 2 bits is used to denote if the root node is pebbled.

From Lemma 3, we know that for all gates g with children $g_L, g_R$, if any node in the sub-tree rooted at $g_R$ is pebbled, then there exists at most one pebble on the sub-tree rooted at $g_L$, namely a pebble on $g_L$ itself. So, given a pebbling configuration, we can start at the root node and describe the path defined by taking the child with more pebbles on its subtree using d bits. All pebbles in the configuration are either on the root node or on children of nodes on this path and therefore describable in the remaining 2d bits.   $\square$

5 Core Adaptive Security Component

In this section, we will describe the secret-sharing scheme $(\mathsf {share},\mathsf {reconstruct})$ used in our ABE construction. In addition, we describe a core component of our final ABE, and prove adaptive security using the pebbling strategy defined and analyzed in Sect. 4 to define hybrids in the piecewise guessing framework of Sect. 3.

Overview. As described in the overview in Sect. 1.1, we will consider the following “core 1-ABE component”:

where $(\{\mu _j\}, \rho ) \leftarrow \mathsf {share}(f,\mu )$. We want to show that under the DDH assumption, $\mu$ is hidden given just $( \mathsf {ct}'_\mathbf {x}, \mathsf {sk}_f)$ where $\mathbf {x}, f$ are adaptively chosen subject to the constraint $f(\mathbf {x}) = 0$. We formalize this via a pair of games and the requirement . In fact, we will study a more abstract construction based on any CPA-secure encryption with:

5.1 Linear Secret Sharing for $\mathsf {NC^1}$

We first describe a linear secret-sharing scheme for $\mathsf {NC^1}$; this is essentially the information-theoretic version of Yao’s secret-sharing for $\mathsf {NC^1}$ in [19, 20, 32]. It suffices to work with Boolean formulas where gates have fan-in 2 and fan-out 1, thanks to the transformation in Sect. 2.1. We describe the scheme in Fig. 4, and give an example in Fig. 5. Note that our non-standard definition of secret-sharing in Sect. 2.2 allows the setting of $\rho (j) = 0$ for shares that are available for reconstruction for all x. We remark that the output of share satisfies $|\{\mu _j\}| \le 2m$ since each of the m nodes adds a single $\mu _j$ to the output set, except for OR gates which add two: $\mu _{j_a}$ and $\mu _{j_b}$.

Fig. 4.

Information-theoretic linear secret sharing scheme $\mathsf {share}$ for $\mathsf {NC^1}$

The reconstruction procedure $\mathsf {reconstruct}$ of the scheme is essentially applying the appropriate linear operations to get the output wire value $\hat{\mu }_c$ at each node starting from the leaves of the formula to get to the root $\hat{\mu }_m = \mu$.

• Given $\hat{\mu }_a, \hat{\mu }_b$ associated with the input wires of an AND gate, we recover the gate’s output wire value $\hat{\mu }_c$ by subtracting their values from $\mu _c$ (which is available since $\rho (c) = 0$).

• Given one of $\hat{\mu }_a, \hat{\mu }_b$ associated with the input wires of an OR gate, we recover the gate’s output wire value $\hat{\mu }_c$ by subtracting it from the appropriate choice of $\mu _{c_a}$ or $\mu _{c_b}$ (which are both available since $\rho (c_a) = \rho (c_b) = 0$).

Note that $\mathsf {reconstruct}(f,x, \{ \mu _j \}_{\rho (j) = 0 \vee x_{\rho (j)} = 1})$ computes a linear operation with respect to the shares $\mu _j$. This follows from the fact that the operation at each gate in reconstruction is a linear operation, and the composition of linear operations is itself a linear operation. Therefore, $\mathsf {reconstruct}(f,x, \{ \mu _j \}_{\rho (j) = 0 \vee x_{\rho (j)} = 1})$ is equivalent to identifying the coefficients $\omega _j$ of this linear function, where $\mu = \sum _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \omega _j \mu _j$.

Fig. 5.

Left: Formula $(x_1 \vee x_2) \vee (x_1 \wedge x_3)$, where the wires are numbered $1,2,\ldots ,7$. Right: Shares $(\mu _1,\ldots ,\mu _{7_b})$ and mapping $\rho$ for the formula corresponding to secret $\mu \in \mathbb {Z}_p$

As with any linear secret-sharing scheme, $\mathsf {share}$ and $\mathsf {reconstruct}$ can be extended in the natural way to accommodate vectors of secrets. Specifically, for a vector of secrets $\mathbf {v}\in \mathbb {Z}^k_p$, define:

$$\mathsf {share}(f, \mathbf {v}) := (\{\mathbf {v}_j := (v_{1, j}, ..., v_{k, j}))\}, \rho ) \text { where }(\{v_{i, j}\}, \rho ) \leftarrow \mathsf {share}(f, v_i) $$

(note that $\rho$ is identical for all i). $\mathsf {reconstruct}$ can also be defined component-wise:

$$\begin{aligned}\mathsf {reconstruct}(f,x, \{ \mathbf {v}_j \}_{\rho (j) = 0 \vee x_{\rho (j)} = 1}) := \displaystyle \sum _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \omega _j \mathbf {v}_j \text { where }\omega _j \text { are computed as above } \end{aligned}$$

Our final ABE construction will use this extension.

5.2 Core 1-ABE Security Game

Definition 4

(core 1-ABE security ). For a stateful adversary $\mathcal {A}$, we define the following games for $\beta \in \{0,1\}$.

where the adversary $\mathcal {A}$ adaptively interacts with three oracles:

$$\begin{aligned} \mathcal {O}_\mathsf {F}(f):= & {} \{ \mathsf {sk}'_f = \{ \mu _j \}_{\rho (j) = 0} \cup \{\mathsf {CPA}.\mathsf {Enc}(w_{\rho (j)},\mu _j)\}_{\rho (j) \ne 0} \text { where }(\{\mu _j\}, \rho ) \leftarrow \mathsf {share}(f,\mu ^{(\beta )})\\ \mathcal {O}_\mathsf {X}(x):= & {} ( \mathsf {ct}'_x = \{ w_i \}_{x_i = 1} )\\ \mathcal {O}_\mathsf {E}(i,m):= & {} \mathsf {CPA}{.}\mathsf {Enc}_{w_i}(m) \end{aligned}$$

with the restrictions that (i) only one query is made to each of $\mathcal {O}_\mathsf {F}(\cdot )$ and $\mathcal {O}_\mathsf {X}(\cdot )$, and (ii) the queries f and x to $\mathcal {O}_\mathsf {F}(\cdot ),\mathcal {O}_\mathsf {X}(\cdot )$ respectively, satisfy $f(x) = 0$.

To be clear, the $\beta$ in affects only the implementation of the oracle $\mathcal {O}_\mathsf {F}$ (where $\mu ^{(\beta )}$ is shared). We will show that where we instantiate $\mathsf {share}$ using the scheme in Sect. 5.1. That is, Theorem 2 will bound the quantity:

Comparison with [20]. Proving adaptive security for the core 1-ABE with $\mathsf {share}$ is very similar to the proof for adaptive secret-sharing for circuits in [20]. One main difference is that in our case, the adaptive choices z correspond to both (f, x), while in the adaptive secret-sharing proof of [20], f is fixed, and the adaptive choices correspond to x, but revealed one bit at a time (that is, $\mathcal {O}_\mathsf {X}(i,x_i)$ returns $w_i$ if $x_i = 1$). Another difference is the $\mathcal {O}_\mathsf {E}$ oracle included in our core 1-ABE game, which enables the component to be embedded in a standard dual-system hybrid proof for our full ABE systems. Lastly, we leverage our improved analysis in Lemmas 3 and 4 to achieve polynomial security loss, rather than the quasi-polynomial loss we would get from following their proof more directly.

5.3 Adaptive Security for Core 1-ABE Component

We will show that as defined in Definition 4 using the piecewise guessing framework. To do this, we need to first define a family of games $\{ \mathsf {H}^u \}$ along with functions $h_0,\ldots ,h_L$, using the pebbling strategy in Sect. 4. First, we will describe $\mathsf {share}^u$, which will be used to define $\mathsf {H}^u$.

Defining $\varvec{\mathsf {share}^u.}$ Recall that Lemma 4 describes how to parse a $u \in \{0,1\}^{3d}$ as a pebbling configuration: a subset of the nodes of f. Further, note that each node contains one output wire, so we can equivalently view u as a subset of [m] denoting the output wires of pebbled gates. Given a pebbling configuration u of an $\mathsf {NC^1}$ formula, the shares are generated as in the secret-sharing scheme in Fig. 4, except for each pebbled node with output wire c, we replace $\mu _c$ with an independent random $\mu _c \leftarrow \mathbb {Z}_p$ (in the case of a pebbled OR gate, we replace both associated $\mu _{c_a}$ and $\mu _{c_b}$ with independent random $\mu _{c_a}, \mu _{c_b} \leftarrow \mathbb {Z}_p$, i.e: both $\mu _{c_a}, \mu _{c_b}$ are associated with wire c.). In particular, we get the procedure $\mathsf {share}^u(f, \mu )$ defined in Fig. 6.

Fig. 6.

Pebbling-modified secret sharing scheme $\mathsf {share}^u$

Hybrid Distribution ${\varvec{\mathsf {H}^{u}.}}$ We now define our hybrid games, and remark that Sect. 3 used $z \in \{0,1\}^{R}$ to denote the adaptive choices made by an adversary, and the functions $h_\ell$ that define our hybrid games will depend on the adaptive choices of both the $f \in \mathsf {NC^1}$ and $x \in \{0,1\}^{n}$ chosen during the game, so in our application of the piecewise guessing framework of Sect. 3, z will be (f, x). Note that the conclusion of the framework is independent of the size of the adaptive input $(R = |f| + n)$, and the framework allows its x to be defined in parts over time, though in our application, x will be defined in one shot.

Definition 5

($\mathsf {H}^u$ and $h_\ell$). Let $\mathsf {H}^{u}$ be with $\boxed {\mathsf {share}^{u}}(f, \mu ^{(0)})$ used in the implementation of oracle $\mathcal {O}_\mathsf {F}(f)$ (replacing $\boxed {\mathsf {share}}(f, \mu ^{(0)})$). Let $h_\ell : \mathsf {NC^1}\times \{0,1\}^n \rightarrow \{0,1\}^{R'}$ denote the function that on formula f with root gate $g^*$ and input $x \in \{0,1\}^n$ where $f(x)=0$, outputs the pebbling configuration created from following the first $\ell$ instructions from $\mathsf {Pebble}(f, x, g^*)$ of Fig. 2.

Note that the first 0 instructions specify a configuration with no pebbles, so $h_0$ is a constant function for all f, x. Also, from the inductive proof in Lemma 3, we know that all sequences of instructions from $\mathsf {Pebble}(f, x, g^*)$ when $f(x)=0$ result in a configuration with a single pebble on the root gate $g^*$, so $h_L$ is a constant function for all f, x where $f(x)=0$. Furthermore, note that for all such f, x:

• $\mathsf {H}^{h_0(f,x)}$ is equivalent to (since $\mathsf {share}^{h_0(f,x)}(f, \mu ^{(0)}) = \mathsf {share}(f,\mu ^{(0)})$);

• $\mathsf {H}^{h_L(f,x)}$ is equivalent to (since $\mathsf {share}^{h_L(f,x)}(f, \mu ^{(0)}) = \mathsf {share}(f,\mu ^{(1)})$ for an independently random $\mu ^{(1)}$ which is implicitly defined by the independently random value associated with the output wire of the pebbled root gate: $\mu _{m}$).

We now have a series of hybrids which satisfy end-point equivalence and, according to the piecewise guessing framework described in Sect. 3, define games $\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1), \widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1)$ for $\ell \in [0, L]$.

Lemma 5

(neighboring indistinguishability). For all $\ell \in [L]$ and $u_0,u_1 \in \{0,1\}^{R'}$, .

Proof

First, observe that the difference between $\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1)$ and $\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1)$ lies in $\mathcal {O}_\mathsf {F}(\cdot )$: the former uses $\boxed {\mathsf {share}^{u_0}}$ and the latter uses $\boxed {\mathsf {share}^{u_1}}$. Now, fix the adaptive query f to $\mathcal {O}_\mathsf {F}$. We consider two cases.

First, suppose there does not exist $x' \in \{0,1\}^n$ such that $h_{\ell -1}(f,x') = u_0$ and $h_\ell (f,x') = u_1$. Then, both $\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1) \rangle$ and $\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1) \rangle$ output 0 (i.e., abort) with probability 1 and then we are done.

In the rest of the proof, we deal with the second case, namely there exists $x' \in \{0,1\}^n$ such that $h_{\ell -1}(f,x') = u_0$ and $h_\ell (f,x') = u_1$. This means that $u_0$ and $u_1$ are neighboring pebbling configurations in $\mathsf {Pebble}(f,x', g^*)$, so they differ by a pebbling instruction that follows one of the rules in Definition 3. We proceed via a case analysis depending on what the instruction taking configuration $u_0$ to $u_1$ is (the instruction is uniquely determined given $u_0,u_1,f$):

• pebble/unpebble input node with out-going wire $\boxed {j}$: Here, the only difference from $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ to $\mathsf {share}^{u_1}(f, \mu ^{(0)})$ is that we change $\boxed {\mu _j}$ to a random element of $\mathbb {Z}_p$ (or vice-versa). The pebbling rule for an input node requires that the input x to $\mathcal {O}_\mathsf {X}(\cdot )$ in both $\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1)$ and $\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1)$ satisfies $x_{\rho (j)} = 0$. Indistinguishability then follows from the CPA security of $(\mathsf {CPA}{.}\mathsf {Setup}, \mathsf {CPA}{.}\mathsf {Enc}, \mathsf {CPA}{.}\mathsf {Dec})$ under key $w_{\rho (j)}$; this is because $x_{\rho (j)} = 0$ and therefore $w_{\rho (j)}$ will not need to be supplied in the answer to the query to $\mathcal {O}_\mathsf {X}(x)$. In fact, the two hybrids are computationally indistinguishable even if the adversary sees all $\{ w_i : i \ne \rho (j) \}$ (as may be provided by $\mathcal {O}_\mathsf {X}(x)$).

• pebble/unpebble AND gate with out-going wire $\boxed {c}$ and input wires a, b corresponding to nodes $g_a,g_b$. Here, the only difference from $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ to $\mathsf {share}^{u_1}(f, \mu ^{(0)})$ is that we change $\boxed {\mu _c}$ from an actual share $\hat{\mu }_a + \hat{\mu }_b + \hat{\mu }_c$ to a random element of $\mathbb {Z}_p$ (or vice-versa). The pebbling rules for an AND gate require that there is a pebble on either $g_a$ or $g_b$, say $g_a$. Therefore, $\mu _a$ is independent and uniformly random in both distributions $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ and $\mathsf {share}^{u_1}(f, \mu ^{(0)})$, and thus $\hat{\mu }_a$ is fresh and independently random in both distributions (this uses the fact that $g_a$ has fan-out 1) and makes the distribution of $\mu _c = \hat{\mu }_a + \hat{\mu }_b + \hat{\mu }_c$ in hybrid $\ell -1$ independently random. We may then deduce that $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ and $\mathsf {share}^{u_1}(f, \mu ^{(0)})$ are identically distributed, and therefore so is the output $\mathcal {O}_\mathsf {F}(f)$. (This holds even if the adversary receives all of $\{ w_i : i \in [n]\}$ from its query to $\mathcal {O}_\mathsf {X}(x)$).

• pebble/unpebble OR gate with out-going wire $\boxed {c}$ and input wires a, b corresponding to nodes $g_a,g_b$. Here, the only difference from $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ to $\mathsf {share}^{u_1}(f, \mu ^{(0)})$ is that we change $\boxed {\mu _{c_a},\mu _{c_b}}$ from actual shares $(\hat{\mu }_a + \hat{\mu }_c, \hat{\mu }_b + \hat{\mu }_c)$ to random elements of $\mathbb {Z}_p$ (or vice-versa). The pebbling rules for an OR gate require that there are pebbles on both $g_a$ and $g_b$. Therefore, $\mu _a$ and $\mu _b$ are independent and uniformly random in both distributions $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ and $\mathsf {share}^{u_1}(f, \mu ^{(0)})$, and thus $\hat{\mu }_a,\hat{\mu }_b$ are fresh and independently random in both distributions (using the fact that $g_a,g_b$ have fan-out 1), and make the distributions of $\mu _{c_a} = \hat{\mu }_a + \hat{\mu }_c$, $\mu _{c_b} = \hat{\mu }_a + \hat{\mu }_b$ in hybrid $\ell -1$ both independently random. We may then deduce that $\mathsf {share}^{u_0}(f, \mu ^{(0)})$ and $\mathsf {share}^{u_1}(f, \mu ^{(0)})$ are identically distributed, and therefore so is the output $\mathcal {O}_\mathsf {F}(f)$. (This holds even if the adversary receives all of $\{ w_i : i \in [n]\}$ in its query to $\mathcal {O}_\mathsf {X}(x)$).

In all cases, the simulator can return an appropriately distributed answer to $\mathcal {O}_\mathsf {X}(x) = \{w_i\}_{x_i=1}$ since it has all $w_i$ except in the first case, where it is missing only a $w_i$ such that $x_i = 0$. Additionally, we note that in all cases, a simulator can return appropriately distributed answers to queries to the encryption oracle $\mathcal {O}_\mathsf {E}(i, m) = \mathsf {Enc}_{w_i}(m)$, since only in the first case (an input node being pebbled or unpebbled) is there a $w_i$ not directly available to be used to simulate the oracle, and in that case, the simulator has oracle access to an $\mathsf {Enc}_{w_i}(\cdot )$ function in the CPA symmetric-key security game, and it can uniformly guess which of the n variables is associated with the input node being pebbled and answer $\mathcal {O}_\mathsf {E}$ requests to that variable with the CPA $\mathsf {Enc}_{w_i}(\cdot )$ oracle (the factor of n due to guessing is introduced here since the simulator may not know which variable is associated with the input node at the time of the oracle request, e.g.: for requests to $\mathcal {O}_\mathsf {E}$ made before $\mathcal {O}_\mathsf {X}$, so the simulator must guess uniformly and take a security loss of n).

In all but the input node case, the two distributions $\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,0}(u_0,u_1) \rangle$ and $\langle \mathsf {A},\widehat{\mathsf {H}}_{\ell ,1}(u_0,u_1) \rangle$ are identical, and in the input node case, we’ve bounded the difference by the distinguishing probability of the symmetric key encryption scheme, the advantage function , conditioned on a correct guess of which of the n input variables corresponds to the pebbled/unpebbled input node. Therefore,    $\square$

5.4 CPA-Secure Symmetric Encryption

We will instantiate $(\mathsf {CPA}{.}\mathsf {Setup}, \mathsf {CPA}{.}\mathsf {Enc}, \mathsf {CPA}{.}\mathsf {Dec})$ in our Core 1-ABE of Definition 4 with a variant of the standard CPA-secure symmetric encryption scheme based on k-Lin from [11] that supports messages $[M]_2 \in G_2$ of an asymmetric prime-order bilinear group $\mathbb {G}$:

• $\mathsf {CPA}{.}\mathsf {Setup}(1^\lambda ){:}$ Run $\mathbb {G} \leftarrow \mathcal {G}(1^\lambda )$. Sample $\mathbf {M}_0 \leftarrow \mathbb {Z}_p^{k \times k}$, $\mathbf {m}_1 \leftarrow \mathbb {Z}_p^{k}$,

  output $\mathsf {sk}= ( \mathsf {sk}_0, \mathsf {sk}_1) := (\mathbf {M}_0, \mathbf {m}_1^{\top })$

• $\mathsf {CPA}{.}\mathsf {Enc}( \mathsf {sk},[M]_2){:}$ Sample $\mathbf {r}\leftarrow \mathbb {Z}_p^{k}$, output $( \mathsf {ct}_0, \mathsf {ct}_1) := ([M + \mathbf {m}_1^{\top }\mathbf {r}]_2, [\mathbf {M}_0 \mathbf {r}]_2)$

• $\mathsf {CPA}{.}\mathsf {Dec}(( \mathsf {sk}_0, \mathsf {sk}_1),( \mathsf {ct}_0, \mathsf {ct}_1) ){:}$ Output $\mathsf {ct}_0 \cdot \mathsf {sk}_1 \cdot \mathsf {sk}_0^{-1} \cdot \mathsf {ct}_1$.

Correctness. Note that: $\mathsf {ct}_0 \cdot \mathsf {sk}_1 \cdot \mathsf {sk}_0^{-1} \cdot \mathsf {ct}_1 = [M + \mathbf {m}_1^{\top }\mathbf {r}- \mathbf {m}_1^{\top }\mathbf {r}]_2 = [M]_2$.

Lemma 6

.

Proof

Proof is contained in the full version of this paper [22] and omitted here for brevity.

Theorem 2

The Core 1-ABE component of Definition 4 implemented with $(\mathsf {share}, \mathsf {reconstruct})$ from Sect. 5.1 and the CPA-secure symmetric encryption scheme $(\mathsf {CPA}{.}\mathsf {Setup}, \mathsf {CPA}{.}\mathsf {Enc}, \mathsf {CPA}{.}\mathsf {Dec})$ from Sect. 5.4 satisfies:

Proof

Recall the hybrids defined in Sect. 5.3. Lemma 5 tells us that: for all $\ell \in [L]$ and $u_0,u_1 \in \{0,1\}^{R'}$,

These hybrids satisfy the end-point equivalence requirement, so Lemma 1 then tells us that:

Lemma 4 tells us that $R' \le 3d$, and Lemma 2 tells us that $L \le 8^{d}$, where d is the depth of the formula. Finally, Lemma 6 tells us that . So:    $\square$

6 Our KP-ABE Scheme

In this section, we present our compact KP-ABE for $\mathsf {NC^1}$ that is adaptively secure under the $\text {MDDH}_{k}$ assumption in asymmetric prime-order bilinear groups. For attributes of length n, our ciphertext comprises O(n) group elements, independent of the formula size, while simultaneously allowing attribute reuse in the formula. As mentioned in the overview in Sect. 1.1, we incorporated optimizations from [5, 15] to shrink $\mathbf {W}_i$ and thus the secret key, and hence the need for the $\mathcal {O}_\mathsf {E}$ oracle in the core 1-ABE security game.

6.1 The Scheme

Our KP-ABE scheme is as follows:

• $\mathsf {Setup}(1^\lambda ,1^n){:}$ Run $\mathbb {G} = (p, G_1, G_2, G_T, e) \leftarrow \mathcal {G}(1^\lambda )$. Sample

  $$\mathbf {A}\leftarrow \mathbb {Z}_p^{k \times (k+1)}, \mathbf {W}_i \leftarrow \mathbb {Z}_p^{(k+1) \times k} \; \forall i \in [n], \mathbf {v}\leftarrow \mathbb {Z}_p^{k+1}$$

  and output:

  

• $\mathsf {Enc}( \mathsf {mpk},x,M){:}$ Sample $\mathbf {s}\leftarrow \mathbb {Z}_p^k$. Output:

  $$\begin{aligned} \mathsf {ct}_\mathbf {x}= & {} ( \mathsf {ct}_{1}, \{ \mathsf {ct}_{2, i}\}_{x_i =1}, \mathsf {ct}_{3})\\:= & {} \Bigg ( [\mathbf {s}^{\top }\mathbf {A}]_1, \{ [\mathbf {s}^{\top }\mathbf {A}\mathbf {W}_i]_1 \}_{x_i = 1}, \quad e([\mathbf {s}^{\top }\mathbf {A}]_1,[\mathbf {v}]_2) \cdot M \Bigg ) \end{aligned}$$

• Sample $(\{\mathbf {v}_j\}, \rho ) \leftarrow \mathsf {share}(f, \mathbf {v})$, $\mathbf {r}_j \leftarrow \mathbb {Z}_p^k$. Output:

  $$\begin{aligned} \mathsf {sk}_f= & {} (\{ \mathsf {sk}_{1, j}, \mathsf {sk}_{2, j}\})\\:= & {} ( \{[\mathbf {v}_j+ \mathbf {W}_{\rho (j)} \mathbf {r}_j]_2, [\mathbf {r}_j]_2\} ) \end{aligned}$$

  where $\mathbf {W}_0 = \mathbf {0}$.

• Compute $\omega _j$ such that $\mathbf {v}= \displaystyle \sum _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \omega _j \mathbf {v}_j$ as described in Sect. 5.1. Output:

  $$ \mathsf {ct}_3 \cdot \displaystyle \prod _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \left( \frac{e( \mathsf {ct}_{2,\rho (j)}, \mathsf {sk}_{2,j})}{e( \mathsf {ct}_{1}, \mathsf {sk}_{1,j})}\right) ^{\omega _j}$$

6.2 Correctness

Correctness relies on the fact that for all j, we have

$$\begin{aligned} \frac{e( \mathsf {ct}_{1}, \mathsf {sk}_{1,j})}{e( \mathsf {ct}_{2,\rho (j)}, \mathsf {sk}_{2,j})} = [\mathbf {s}^{\top }\mathbf {A}\mathbf {v}_j]_T \end{aligned}$$

which follows from the fact that

$$ \mathbf {s}^{\top }\mathbf {A}\mathbf {v}_j = \underbrace{\mathbf {s}^{\top }\mathbf {A}}_{ \mathsf {ct}_1} \cdot (\underbrace{\mathbf {v}_j + \mathbf {W}_{\rho (j)} \mathbf {r}_j}_{ \mathsf {sk}_{1,j}}) - \underbrace{\mathbf {s}^{\top }\mathbf {A}\mathbf {W}_{\rho (j)}}_{ \mathsf {ct}_{2, \rho (j)}} \cdot \underbrace{\mathbf {r}_j}_{ \mathsf {sk}_{2,j}} $$

Therefore, for all f, x such that $f(x) = 1$, we have:

$$\begin{aligned} \mathsf {ct}_3 \cdot \displaystyle \prod _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \left( \frac{e( \mathsf {ct}_{2,\rho (j)}, \mathsf {sk}_{2,j})}{e( \mathsf {ct}_{1}, \mathsf {sk}_{1,j})}\right) ^{\omega _j}&= M \cdot [\mathbf {s}^{\top }\mathbf {A}\mathbf {v}]_T \cdot \prod _{\rho (j) = 0 \vee x_{\rho (j) = 1}} [\mathbf {s}^{\top }\mathbf {A}\mathbf {v}_j]_T^{-\omega _j}\\&= M \cdot [\mathbf {s}^{\top }\mathbf {A}\mathbf {v}]_T \cdot [-\mathbf {s}^{\top }\mathbf {A}\displaystyle \sum _{\rho (j) = 0 \vee x_{\rho (j) = 1}} \omega _j \mathbf {v}_j]_T\\&= M \cdot [\mathbf {s}^{\top }\mathbf {A}\mathbf {v}]_T \cdot [-\mathbf {s}^{\top }\mathbf {A}\mathbf {v}]_T\\&= M \end{aligned}$$

6.3 Adaptive Security

Description of Hybrids. To describe the hybrid distributions, it would be helpful to first give names to the various forms of ciphertext and keys that will be used. A ciphertext can be in one of the following forms:

• $\mathsf {Normal}$: generated as in the scheme.

• $\mathsf {SF}$: same as a $\mathsf {Normal}$ ciphertext, except $\mathbf {s}^{\top }\mathbf {A}$ replaced with $\mathbf {c}^{\top }\leftarrow \mathbb {Z}_p^{k+1}$. That is, $\mathsf {ct}_\mathbf {x}:= \Bigg ( [\boxed {\mathbf {c}^{\top }}]_1, \{ [\boxed {\mathbf {c}^{\top }}\mathbf {W}_i]_1 \}_{x_i = 1}, \quad e([\boxed {\mathbf {c}^{\top }}]_1,[\mathbf {v}]_2) \cdot M \Bigg )$

A secret key can be in one of the following forms:

• $\mathsf {Normal}$: generated as in the scheme.

• $\mathsf {SF}$: same as a $\mathsf {Normal}$ key, except $\mathbf {v}$ replaced with $\mathbf {v}+ \delta \mathbf {a}^\perp$, where a fresh $\delta \leftarrow \mathbb {Z}_p$ is chosen per $\mathsf {SF}$ key and $\mathbf {a}^\perp$ is any fixed $\mathbf {a}^\perp \in \mathbb {Z}_p^{k+1} \setminus \{\mathbf {0}\}$ such that $\mathbf {A}\mathbf {a}^\perp = \mathbf {0}$. That is, $\mathsf {sk}_f := ( \{[\mathbf {v}_j+ \mathbf {W}_{\rho (j)} \mathbf {r}_j]_2, [\mathbf {r}_j]_2\} )$

  where $(\{\mathbf {v}_j\}, \rho ) \leftarrow \mathsf {share}(f, \boxed {\mathbf {v}+ \delta \mathbf {a}^\perp })$, $\mathbf {r}_j \leftarrow \mathbb {Z}_p^k$.

$\mathsf {SF}$ stands for semi-functional following the terminology in previous works [25, 33].

Hybrid Sequence. Suppose the adversary $\mathsf {A}$ makes at most Q secret key queries. The hybrid sequence is as follows:

• $\mathsf {H}_0$: real game

• $\mathsf {H}_1$: same as $\mathsf {H}_0$, except we use a $\mathsf {SF}$ ciphertext.

• $\mathsf {H}_{2,\ell }, \ell =0,\ldots ,Q$: same as $\mathsf {H}_1$, except the first $\ell$ keys are $\mathsf {SF}$ and the remaining $Q-\ell$ keys are $\mathsf {Normal}$.

• $\mathsf {H}_3$: replace M with random $\widetilde{M}$.

Proof Overview

• We have via k-Lin, which tells us . Here, the security reduction will pick $\mathbf {W}_1,\ldots ,\mathbf {W}_n$ and $\mathbf {v}$ so that it can simulate the , the ciphertext and the secret keys.

• We have , for all . The difference between the two is that we switch the ’th from to using the adaptive security of our core 1-ABE component in from Sect. 5. The idea is to sample

  

  so that can be computed using and perfectly hide $\mu , \mathbf {w}_1,\ldots ,\mathbf {w}_n$. Roughly speaking: the reduction

  • uses $\mathcal {O}_\mathsf {X}(x)$ in to simulate the challenge ciphertext

  • uses $\mathcal {O}_\mathsf {F}(f)$ in to simulate $\ell$’th secret key

  • uses $\mu ^{(0)}$ from together with $\mathcal {O}_\mathsf {E}(i, \cdot ) = \mathsf {Enc}(w_i,\cdot )$ to simulate the remaining $Q-\ell$ secret keys

• We have . In , the secret keys only leak $\mathbf {v}+ \delta _1 \mathbf {a}^\perp ,\ldots ,\mathbf {v}+ \delta _Q \mathbf {a}^\perp$. This means that $\mathbf {c}^{\top }\mathbf {v}$ is statistically random (as long as $\mathbf {c}^{\top }\mathbf {a}^\perp \ne 0$).

Theorem 3

(adaptive KP-ABE). The KP-ABE construction in Sect. 6.1 is adaptively secure under the ${\textit{MDDH}}_{k}$ assumption.

Proof

The detailed proof is contained in the full version of this paper [22] and omitted here for brevity.