# D Anonymity

Within the broadcast encryption setting, the anonymity property, introduced in [6], further requests to hide the used user set, and is useful in some practical cases. In this appendix, we prove that our generic construction of (Aug) BE from a pattern hiding WIBE gives us an anonymous scheme.

## Anonymous Broadcast encryption.

**Definition 27. Anonymous BE scheme (ANO-BE) [6, 26]**

We say that a BE scheme is adaptively anonymous (or satisfies ANO-BE security) if all polynomial time adaptive adversaries $\mathcal{A}$ have at most negligible advantage in the game presented in Figure 14, where $\mathcal{A}$'s advantage is defined as

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{ANO-BE}}(\lambda) = \left| \mathrm{Pr} \left[ b' = b \right] - 1/2 \right|. $$

SETUP: challenger $\mathcal{C}$ runs Setup($1^{\lambda}$, $1^N$) to generate pk and msk, and gives pk to $\mathcal{A}$.

KEY QUERY: $\mathcal{A}$ issues queries to $\mathcal{C}$ for index $i \in [N]$. $\mathcal{C}$ returns $sk_i \leftarrow \mathrm{KeyGen}(msk, i)$.

CHALLENGE: $\mathcal{A}$ selects two messages $m_0, m_1$ and two distinct sets $S^0, S^1 \subseteq [N]$ of users. We impose the restriction that $\mathcal{A}$ has not issued key queries for any $i$ such that $i \in S^0 \land i \notin S^1$ or $i \in S^1 \land i \notin S^0$. Further, if there exists an $i \in S^0 \cap S^1$ for which $\mathcal{A}$ has queried the key, then we require that $m_0 = m_1$. $\mathcal{A}$ passes $m_0, m_1$ and $S^0, S^1$ to $\mathcal{C}$. The latter picks $b \in \{0, 1\}$ random and computes $ct^* \leftarrow \mathrm{Encrypt}(pk, S^b, m_b)$ which is returned to $\mathcal{A}$.

KEY QUERY: $\mathcal{A}$ continues to make queries for index $i \in [N]$ with the restriction that $i \notin S^0 \land i \notin S^1$ or $i \in S^0 \land i \in S^1$ and if $m_0 \neq m_1$ then $i \notin S^0 \cap S^1$.

GUESS: $\mathcal{A}$ outputs its guess $b' \in \{0, 1\}$ for $b$, and wins the game if $b' = b$.

<caption>**Fig. 14. ANO-BE security game.**</caption>

*Note 13.* Many BE schemes require the encryption set $S$ to be publicly given as an input of decryption algorithm. Otherwise even authorized users will not be able to decrypt. However, anonymous schemes does not need the encryption set description as an input for the decryption algorithm.

Our first generic construction gives us a broadcast encryption scheme from a WIBE. Let us show that if the underlying WIBE is also pattern-hiding, then the obtained BE is anonymous.

**Theorem 11.** If WIBE satisfies adaptive (resp. selective) pattern hiding security, then the obtained BE scheme is adaptive (resp. selective) anonymous.

*Proof.* Let $\mathcal{B}$ be an adversary against anonymous security, that wins with non negligible advantage. In Figure 15 we construct $\mathcal{A}$, an adversary against pattern hiding security that uses $\mathcal{B}$ and wins with non negligible advantage. Let $\mathcal{C}$ be a challenger's queries satisfy the game constraints, then all $\mathcal{A}$'s queries have the same property. Thus $\mathcal{A}$'s simulation is perfect, and the advantage of $\mathcal{A}$ is the same as $\mathcal{B}$'s. This concludes the proof.
**SETUP:** $\mathcal{C}$ runs Setup$(1^{\lambda}, 1^N) \to (\text{msk}, \text{pk})$ and sends $\text{pk}$ to $\mathcal{A}$, who sends it to $\mathcal{B}$.

**KEY QUERY:** $\mathcal{B}$ chooses $i \in [N]$, sends it to $\mathcal{A}$ who creates the pattern $\mathbf{P}^i$ such that for $j \in [1, N]$, $P_j^i = 1$ if $i = j$ and $P_j^i = 0$ otherwise. $\mathcal{A}$ sends $\mathbf{P}^i$ to $\mathcal{C}$ who runs KeyDer($\text{msk}, \mathbf{P}^i$) $\to \text{sk}_{\mathbf{P}^i}$. $\mathcal{A}$ receives $\text{sk}_{\mathbf{P}^i}$ and sends it to $\mathcal{B}$ as $\text{sk}_i$.

**CHALLENGE:** $\mathcal{B}$ chooses message $m$, two sets $S_0, S_1$ and sends them to $\mathcal{A}$ who creates patterns $\mathbf{P}^0, \mathbf{P}^1$ s.t. for $j \in [1, N]$, $P_j^0 = \star$ if $j \in S_0$, $P_j^0 = 0$ otherwise, and $P_j^1 = \star$ if $j \in S_1$, $P_j^1 = 0$ otherwise. $m, \mathbf{P}^0, \mathbf{P}^1$ are sent to $\mathcal{C}$. If for any queried $\mathbf{P}^i$ during previous step, $\mathbf{P}^i \in_* \mathbf{P}^0 \wedge \mathbf{P}^i \notin_* \mathbf{P}^1$ or $\mathbf{P}^i \notin_* \mathbf{P}^0 \wedge \mathbf{P}^i \in_* \mathbf{P}^1$, $\mathcal{C}$ aborts. Otherwise, it chooses $b \leftarrow \{0, 1\}$ and runs $\text{ct}^* \leftarrow \text{Encrypt}(\text{pk}, \mathbf{P}^b, m)$. $\mathcal{C}$ sends $\text{ct}^*$ to $\mathcal{A}$, who sends it to $\mathcal{B}$.

**KEY QUERY:** $\mathcal{B}$ and $\mathcal{A}$ proceeds as in the first **KEY QUERY** step. If $\mathbf{P}^i \in_* \mathbf{P}^0 \wedge \mathbf{P}^i \notin_* \mathbf{P}^1$ or $\mathbf{P}^i \notin_* \mathbf{P}^0 \wedge \mathbf{P}^i \in_* \mathbf{P}^1$, $\mathcal{C}$ aborts, otherwise it runs KeyDer($\text{msk}, \mathbf{P}^i$) $\to \text{sk}_{\mathbf{P}^i}$. $\text{sk}_{\mathbf{P}^i}$ is sent to $\mathcal{A}$, who sends it to $\mathcal{B}$ as $\text{sk}_i$.

**GUESS:** $\mathcal{B}$ outputs its guess $b'$ to $\mathcal{A}$, who outputs it as its guess.

<caption>**Fig. 15.** Construction of pattern hiding adversary from anonymous BE adversary.</caption>

*State of art.* In the anonymous BE setting, the Libert et al. scheme ([26]) is the best known option so far, even if [25] proposes a slight improvement regarding the ciphertext size. The main practical problem with both constructions is however that each user has to try each element of the ciphertext to find the one he/she can truly decrypt. In 2014, [4] proposed a generic construction of anonymous BT from anonymous BE, and an instantiation based on [26]'s anonymous BE scheme.

Notice that [26] said that achieving shorter than linear size for ciphertext is impossible when considering the used users set description as part of the ciphertext. With our second WIBE and our generic constructions, setting $L = N + 1$, we obtain a new anonymous broadcast encryption scheme. Our scheme does not improve the efficiency of the Libert et al. scheme [26], which is the best known so far. In particular, their scheme has $\text{pk}$ and $\text{sk}_i$ sizes in respectively $O(N)$ and $O(1)$ while in our scheme the same parameters have sizes in $O(N^2)$ and $O(N)$ respectively. Regarding security, their scheme achieves the stronger CCA security in the standard model while we only reach a CPA security. However, in Libert et al.'s scheme, each user has to try each element of the ciphertext to find the one he can truly decrypt, while this is not necessary in our construction.

**Anonymous Augmented Broadcast encryption.** As notice in section ??, the AugBE scheme obtained from our second WIBE instantiation is actually the first known anonymous AugBE. Eventually, the derivation of our anonymous AugBE to an anonymous BT scheme is quite direct from the generic construction given in [10]. A formal definition of an anonymous BT scheme is quite straightforward from the one of anonymous AugBE and can be found in e.g., [4]. The only existing anonymous BT is the one of [4], which is based on the anonymous BE scheme of [26]: it directly inherit advantages and drawbacks compare to our resulting scheme.