# Breaking Anonymity in Attribute-Based Access Control Encryption *

Baptiste Bazin, Clara Bertolissi, Alexis Bonnecaze, Kevin Thiry-Atighehchi

► To cite this version:

Baptiste Bazin, Clara Bertolissi, Alexis Bonnecaze, Kevin Thiry-Atighehchi. Breaking Anonymity in Attribute-Based Access Control Encryption *. The 41st ACM/SIGAPP Symposium On Applied Computing, ACM/SIGAPP, Mar 2026, Théssalonique, Greece. hal-05429402

HAL Id: hal-05429402

https://amu.hal.science/hal-05429402v1

Submitted on 22 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Breaking Anonymity in Attribute-Based Access Control Encryption*

Baptiste Bazin

Aix Marseille Univ, CNRS, I2M

Marseille, France

baptiste.bazin@univ-amu.fr

Clara Bertolissi

LIFO, INSA Centre Val de Loire, Université d'Orléans

Bourges, France

clara.bertolissi@insa-cvl.fr

Alexis Bonnecaze

Kevin Thiry-Atighehchi

Aix-Marseille Univ, CNRS, I2M

CRéA, École de l'Air et de l'Espace

Marseille, France

Salon-de-Provence, France

alexis.bonnecaze@univ-amu.fr

kevin.thiry@ecole-air.fr

December 22, 2025

## Abstract

Access Control Encryption (ACE) enforces sender and receiver access control while preserving traffic anonymity. Attribute-Based ACE (AB-ACE) extends this to attribute-based policies, claiming to achieve the same security guarantees under the *No-Read* and *No-Write* rules. In this paper, we show that existing AB-ACE schemes fail to ensure anonymity: most reveal the access structure in the ciphertext, and even schemes designed to hide it leak information through NIZK-related elements, violating the *No-Read Rule*. These results call for a reconsideration of both the construction techniques and the formal models of AB-ACE, if robust sender and receiver privacy is to be achieved.

## 1 Introduction

Access Control Encryption (ACE), introduced by Damgård et al. [1], is a cryptographic paradigm designed to enforce access control on users who can send or receive data. Unlike Attribute-Based Encryption (ABE), which limits access control on the receiver side, ACE also constrains senders: they cannot freely choose their recipients, but must conform to a predefined security policy. To enforce this policy, ACE involves an intermediary entity called a *sanitizer*. All ciphertexts produced by senders must pass through this sanitizer, which transforms them into sanitized ciphertexts and broadcasts them to all users. The sanitized ciphertexts are constructed in such a way that only receivers authorized by the policy are able to decrypt them.

In order to guarantee traffic anonymity, the sanitizer must not know the identity of the receivers, the identity of the senders, or the content of the encrypted messages. It is also generally

<footnote>*© Baptiste Bazin, Clara Bertolissi, Alexis Bonnecaze, Kevin Thiry-Atighehchi | ACM 2026. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record will be published in the Proceedings of the 41st ACM/SIGAPP Symposium on Applied Computing (SAC 2026), http://dx.doi.org/10.1145/3748522.3780004.</footnote>
unaware of the security policy itself. The implementation of such a mechanism relies on one trusted authority (or more, in the case of Cross-Domain ACE, where sender and receiver belong to different domains) responsible for distributing encryption keys to senders and decryption keys to receivers in accordance with the policy. The sanitizer must then ensure that each ciphertext transmitted by a sender has been produced using the encryption key assigned by the trusted authority, and not an arbitrary one.

The first ACE schemes were initially based on identities. However, in order to increase flexibility and eliminate dependence on identities, Han et al. [2] introduced an Attribute-Based ACE (AB-ACE) scheme.

Prior literature on ACE and AB-ACE is largely constructive, establishing security under no-read and no-write rule definitions, which respectively capture message confidentiality and sender anonymity, and guarantee that a sender cannot bypass the access policy. In this article, we examine the anonymity property of users with respect to the sanitizer in practice and identify where these guarantees can fall short.

A useful analogy comes from data protection. For years many systems treated pseudonymization as anonymization; practice and the Article 29 Working Party (WP29 [3]) made clear this is incorrect. WP29 characterizes anonymization by jointly preventing singling out of an individual, preventing linkability across records about the same individual, and preventing inference of attributes. Pseudonymization only replaces identifiers and often leaves linkability intact when auxiliary data is available. The same lesson applies in ACE: classic no-read rule confidentiality protects the content of a single ciphertext but can still allow correlations across multiple sanitized ciphertexts. Considering that the no-read rule involves anonymity therefore amounts to treating pseudonymization as anonymization. This motivates a security objective that explicitly addresses resistance to linking across ciphertexts.

<table><caption>Table 1: Summary of anonymity-related weaknesses in AB-ACE schemes. A ✓ means that information can be recovered; a ✗ means full resistance; a ~ means partial vulnerability.</caption><thead><tr><th>Scheme</th><th>Access Structure</th><th>Attribute Set</th><th>Identifier Leakage</th><th>Persistent Key Randomness</th><th>(Sender) Ciphertext Linkability</th><th>Receiver Inference</th></tr></thead><tbody><tr><td>Han et al. [2]</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td></tr><tr><td>Sedaghat & Preneel [4] § 5</td><td>✓</td><td>~</td><td>✗</td><td>✓</td><td>✓</td><td>~</td></tr><tr><td>Sedaghat & Preneel [4] § D</td><td>✓</td><td>~</td><td>✗</td><td>✓</td><td>✓</td><td>~</td></tr><tr><td>Cui et al. [5]</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td></tr><tr><td>Huang et al. [6]</td><td>~</td><td>✓</td><td>✗</td><td>✗</td><td>~</td><td>~</td></tr><tr><td>Wang et al. [7] § 6.A</td><td>✓</td><td>~</td><td>✗</td><td>✓</td><td>✓</td><td>~</td></tr><tr><td>Wang et al. [7] § 6.B</td><td>✓</td><td>~</td><td>✗</td><td>✓</td><td>✓</td><td>~</td></tr></tbody></table>

The main contributions of this work are as follows:

* We show that several existing AB-ACE schemes are vulnerable to attacks that compromise sender and receiver anonymity, even though they remain secure under their respective formulations of the *No-Read* property.

* We demonstrate that, in the schemes of Wang et al., the only AB-ACE constructions designed to conceal access structures, algebraic relations enable adversaries to distinguish the underlying access structure, thereby violating their formal *No-Read Rule* definition.

* Current formulations of the *No-Read* property, including the original *No-Read Rule* of Damgård et al. [1], fail to capture cross-ciphertext linkability when encryption key generation
is non-deterministic, leaving sender privacy insufficiently protected. A new formulation is proposed, for both ACE and AB-ACE, in order to rule out these types of attack.

Table 1 summarizes the main anonymity leakages observed in existing AB-ACE constructions. Each column corresponds to a specific vulnerability category: disclosure (or testability) of the access structure, exposure of the attribute set, presence of explicit or implicit identifiers in the ciphertext, correlation caused by persistent randomness in encryption keys, the ability to link multiple ciphertexts from the same sender, and finally, the sanitizer's capacity to infer potential receivers.

Leakage of either identifier information or persistent key randomness enables ciphertext linkability, as both types of information can allow linking ciphertexts to a single sender. Partial sender information can also be inferred indirectly through the disclosure of the access structure or the attribute set.

Overall, the table highlights that all existing AB-ACE constructions reveal, directly or indirectly, information that can be used to link ciphertexts together or to their senders. Even the recent schemes by Wang [7], although they conceal the access structure within the ciphertext, remain vulnerable: a sanitizer can still actively test whether a given structure is associated with a ciphertext, thereby undermining their formal No-Read Rule.

**Outline** Section 2 reviews related work. Section 3 recalls the building blocks used throughout the paper. Section 4 summarizes AB-ACE and states the security model. Section 5 presents our attack methodology. Section 6 details the *Multi-Valued AND-Gates* by Wang *et al.* [7]. Section 7 analyzes the scheme and its weaknesses. Section 8 discusses possible defenses and their impact. Section 9 concludes the paper.

## 2 Related Work

The concept of Access Control Encryption (ACE) was first introduced by Damgård *et al.* [1], who formalized the notions of *No-Read* and *No-Write* properties through the use of a sanitizer. In this model, communication is governed by a security policy $P$, where a sender $i$ is allowed to send messages to a receiver $j$ if and only if $P(i, j) = 1$. They proposed two ACE constructions in which the sanitizer holds a private key.

Later, Fuchsbauer *et al.* [8] designed the first ACE scheme where the sanitizer operates without a private key, using a digital signature. In their design, the encryption key is attached with a signature issued by a trusted authority, and the sender must prove that his ciphertext was honestly generated using a key from a trusted authority.

Han *et al.* [2] introduced the first attribute-based ACE (AB-ACE) construction. Their scheme, built upon the Waters CP-ABE scheme [9], associates each user with a set of attributes and embeds a signature within the user's secret key. Cui *et al.* [5] proposed an alternative construction based on the Agrawal-Chase ABE scheme [10], which also associates an attribute set with each user but removes the need for a sanitizer key.

Huang *et al.* [6] presented the first key-policy AB-ACE (KP-AB-ACE) construction, adapting the methodology of Fuchsbauer *et al.* to eliminate the sanitizer's private key in a KP-ABE setting [11].

The cross-domain notion was introduced by Wang *et al.* [12], who proposed the first CD-ACE scheme. It leverages the sanitizer-without-private-key approach of Fuchsbauer *et al.*, while separating the roles of sender and receiver authorities - one generating encryption keys and the other decryption keys. Sedaghat *et al.* [4] extended this model to the attribute-based setting, proposing
two CD-AB-ACE variants, respectively built from the CP-ABE schemes of Guo et al. [13] and
Waters [9].

Beyond payload confidentiality, ACE deployments must protect the anonymity of communicat-
ing parties relative to both the sanitizer and observers. For instance, when ciphertexts expose their
access policy, the policy itself becomes a quasi-identifier of potential recipients: an adversary can
enumerate all users whose attributes satisfy the predicate, intersect this candidate set with auxiliary
records, and correlate across flows via stable labels induced by policy reuse. This policy-in-the-clear
leakage is well recognized in the ABE literature and has motivated policy-hiding CP-ABE designs
precisely to preserve recipient privacy and mitigate inference on who can (or did) decrypt [14, 15].

Finally, Wang et al. [7] proposed the first CD-AB-ACE constructions that conceal the access structure within the ciphertext, based on the CP-ABE scheme of Zhang et al. [16]. Although there are emerging attempts to realize AB-ACE with strong anonymity guarantees, the security of these constructions is not yet well understood.

3 Preliminaries

This section recalls the mathematical and cryptographic tools used throughout this work.

3.1 Bilinear Groups

Some AB-ACE schemes rely on bilinear pairings, in particular Type-III pairings. Let ($G_1, G_2, G_T$)
be cyclic groups of prime order $p$ with generators $g_1 \in G_1$ and $g_2 \in G_2$, and let $e : G_1 \times G_2 \to G_T$
be an efficiently computable, non-degenerate bilinear pairing satisfying $e(g_1^a, g_2^b) = e(g_1, g_2)^{ab}$ for all
$a, b \in \mathbb{Z}_p$. In the Type-III (asymmetric) setting, no polynomial-time isomorphism exists between
$G_1$ and $G_2$.

3.2 Non-Interactive Zero-Knowledge Proof System

A non-interactive zero-knowledge (NIZK) proof in the common reference string (CRS) model [17]
is a one-message proof system. A prover uses a short public string, the CRS, to send a single proof
$\pi$ that convinces a verifier that a statement $x$ is true, typically that $x$ belongs to an NP language.
The proof must satisfy four properties: completeness, language soundness, knowledge soundness,
and zero-knowledge. Completeness means that a prover who holds a valid NP witness can convince
the verifier. Language soundness means that if the statement is false, no efficient adversary can
make the verifier accept. Knowledge soundness means that if a proof is accepted, then the prover
really knows a witness, and with the CRS trapdoor, an extractor could recover a witness for $x$.
Zero-knowledge means that the verifier learns nothing beyond the truth of the statement.

3.3 Attribute-Based Encryption

*Attribute-Based Encryption (ABE)* generalizes *Identity-Based Encryption (IBE)* by enabling access control through attributes taken from a universe *U*. Decryption is allowed only if an attribute set *L* satisfies an access structure *A*, denoted *A*(*L*) = 1. It is crucial to distinguish this cryptographic access structure from the security policy: the former is a logical rule used to control decryption, while the latter governs how these structures and attributes are assigned to enforce which users are authorized to communicate.
Two main variants exist: Key-Policy ABE (KP-ABE), where ciphertexts are associated with an attribute set $\mathcal{L}$, while decryption keys embed an access policy $\mathcal{A}$; and Ciphertext-Policy ABE (CP-ABE), where ciphertexts are associated with $\mathcal{A}$, while decryption keys embed $\mathcal{L}$.
A CP-ABE scheme is defined by the following algorithms:

* **Setup(1^λ, U):** on input a security parameter $1^λ$ and the attribute universe $U$, outputs the public parameters $pp$ and a master secret key $msk$.

* **KeyGen(pp, msk, L):** on input the public parameters, the master secret key, and an attribute set $\mathcal{L}$, outputs a decryption key $dk_{\mathcal{L}}$.

* **Enc(pp, m, A):** on input a message $m$ and an access structure $A$, outputs a ciphertext $c \in \mathcal{C}$.

* **Dec(dk_{\mathcal{L}}, c):** on input a decryption key $dk_{\mathcal{L}}$ and a ciphertext $c$, outputs $m \in \mathcal{M} \cup \{\perp\}$.

**Correctness.** For any access structure $\mathcal{A}$ and any attribute set $\mathcal{L}$ such that $\mathcal{L} \models \mathcal{A}$,

$$ \Pr(\text{Dec}(dk_{\mathcal{L}}, \text{Enc}(pp, m, A)) \neq m) < \text{negl}(\lambda), $$

where $(pp, msk) \leftarrow \text{Setup}(1^\lambda, U)$, $dk_{\mathcal{L}} \leftarrow \text{KeyGen}(pp, msk, \mathcal{L})$.

**wPH-IND-CPA.** Beyond standard IND-CPA security, ensuring message confidentiality against adversaries with unauthorized attributes, the weak Payload-Hiding IND-CPA (wPH-IND-CPA) additionally requires hiding the access structure itself.

In the wPH-IND-CPA experiment, the adversary selects two access structures $A_0, A_1$ and two messages $m_0, m_1$, with the assistance of a decryption key oracle. The challenger encrypts $m_b$ under $A_b$ for a random coin $b$, and the adversary must guess $b$ without having queried decryption keys $dk_{\mathcal{L}}$ satisfying either structure. The advantage

$$ \text{Adv}_{A, \text{CP-ABE}}^{w\text{PH-IND-CPA}} = \left| \Pr(b' = b) - \frac{1}{2} \right| $$

must be negligible. The standard IND-CPA security is a special case obtained by setting $A_0 = A_1$.

A sanitizable CP-ABE (sCP-ABE) scheme extends CP-ABE with a sanitization algorithm:

$$ \text{San}(pp, c) \rightarrow c'. $$

**Correctness.** For any access structure $\mathcal{A}$ and any attribute set $\mathcal{L}$ such that $\mathcal{A}(\mathcal{L}) = 1$:

$$ \Pr(\text{Dec}(dk_{\mathcal{L}}, \text{San}(pp, \text{Enc}(pp, m, A))) \neq m) < \text{negl}(\lambda). $$

**Weak Sanitizability.** [7]: No PPT adversary given $m_0, m_1, A_0$ and $A_1$ and a sanitized ciphertext $c'_b \leftarrow \text{San}(c_b; r')$, where $c_b \leftarrow \text{Enc}(A_b, m_b; r_b)$, can guess $b$ with a non-negligible advantage.

A KP-ABE scheme simply reverses the roles: keys are tied to an access structure $\mathcal{A}$ and ciphertexts to an attribute set $\mathcal{L}$. The definitions of correctness and wPH-IND-CPA security adapt naturally.
## 3.4 Linear Secret Sharing Scheme

A Secret Sharing Scheme $\Psi_A$ over $\mathbb{Z}_p$ (see [18]) for an access structure $\mathcal{A}$ over an attribute universe $U = \{U_1, \dots, U_n\}$ is called *linear* (following the definition of Waters [9]) if

1. The shares for an attribute set form a vector over $\mathbb{Z}_p$.

2. There exists a matrix $\mathbf{M}$, with dimension $l \times d$, called the share-generating matrix for $\Psi_A$. The $i^{th}$ row of $\mathbf{M}$, $\mathbf{M}_i$, is labeled by $\rho(i)$, where $\rho$ is a function from $\{1, 2, \dots, l\}$ to $U$. When we consider the column vector $\mathbf{v} = (s, r_2, \dots, r_d)$, where $s \in \mathbb{Z}_p$ is the secret to be shared and $r_2, \dots, r_d \in \mathbb{Z}_p$ are randomly chosen, then $\mathbf{M} \cdot \mathbf{v}$ is the vector of $l$ shares of the secret $s$ according to $\Psi_A$. The share $\lambda_i = \mathbf{M} \cdot \mathbf{v}_i$ corresponds to the attribute $\rho(i)$.

Let $\mathcal{L}$ denote an authorized set for the structure $\mathcal{A}$, i.e. $\mathcal{A}(\mathcal{L}) = 1$, and let $\mathcal{I} \subset \{1, 2, \dots, n\}$ be defined as $\mathcal{I} = \{i : \rho(i) \in \mathcal{L}\}$. Then, there exist constants $\{\omega_i \in \mathbb{Z}_p\}_{i \in \mathcal{I}}$ such that, if $\lambda_i$ are valid shares of any secret $s$ according to $\Psi_A$, then $\sum_{i \in \mathcal{I}} \omega_i \cdot \mathbf{M}_i = (1, 0, \dots, 0)_{1 \times d}$ and $\sum_{i \in \mathcal{I}} \omega_i \cdot \lambda_i = s$.

# 4 Attribute-Based Access Control Encryption

Attribute-Based Access Control Encryption (AB-ACE) extends ACE by integrating attribute-based encryption (ABE), thereby enforcing both sender and receiver access policies while preserving their anonymity. We outline the general construction and the corresponding security notions.

## 4.1 Constructing ACE from ABE

AB-ACE builds directly upon ABE primitives. The idea is to regulate encryption and decryption rights through attribute-based policies.

Two main approaches exist:

* **Separate keys for sending and receiving.** Each user receives two keys: an encryption key and a decryption key, associated respectively with an access structure $\mathcal{A}$ and an attribute set $\mathcal{L}$ (or vice versa, depending on whether KP-ABE or CP-ABE is used). This design supports both KP-ABE and CP-ABE-based ACE constructions [4, 6, 7].

* **Single key associated with an attribute set.** Each user holds one key tied to an attribute set $\mathcal{L}$, defining both the access structures they can specify for encryption (restricted to attributes contained in $\mathcal{L}$) and the ciphertexts they are allowed to decrypt. This design is specific to CP-ABE-based ACE schemes [2, 5].

Although both ABE types are theoretically suitable, almost all existing AB-ACE schemes rely on CP-ABE; the KP-ABE variant remains limited to a single work [6]. We therefore focus on CP-ABE-based constructions, noting that definitions adapt naturally to the KP-ABE case by swapping $\mathcal{A}$ and $\mathcal{L}$.

A generic AB-ACE scheme [2, 5, 6] consists of:

* **Setup(1^λ, U):** given a security parameter $1^\lambda$ and an attribute universe $U$, outputs the public parameters $\mathbf{pp}$ and a master secret key $\mathbf{msk}$. It may also generate a sanitizer secret key $\mathbf{ssk}$.

* **EKGen(pp, msk, A):** given the public parameters, the master key, and an access structure $\mathcal{A}$, outputs an encryption key $\text{ek}_A$ (resp. $\text{ek}_\mathcal{L}$).
• DKGen(pp, msk, L): given the public parameters, the master key, and an attribute set L, outputs a decryption key dkL (resp. dkA).

• Enc(pp, m, ekA): given a message m and an encryption key ekA, outputs a ciphertext c ∈ C.

• San(pp, c): given a ciphertext c, outputs a sanitized ciphertext c' ∈ C' ∪ {⊥}. It may also require the sanitizer secret key ssk as input.

• Dec(dkL, c'): given a decryption key dkL and a sanitized ciphertext c', outputs m ∈ M ∪ {⊥}.

In cross-domain variants [4, 7], key generation is split between a Receiver Authority (RA) and a Sender Authority (SA):

• GlobalSetup(1$^{λ}$, U): generates the global public parameters pp.

• RASetup(pp): given the global public parameters, the algorithm outputs the receiver au-
thority's public key mpk<sub>ra</sub> and master secret key msk<sub>ra</sub>.

• SASetup(pp, mpk<sub>ra</sub>): given the global public parameters and the receiver authority's public key, the algorithm outputs the sender authority's public key mpk<sub>sa</sub> and master secret key msk<sub>sa</sub>.

• EKGen(pp, msk<sub>sa</sub>, A) and DKGen(pp, msk<sub>ra</sub>, L) as above.

4.2 Security Model

No-Read Game Definition

1. pp ← GlobalSetup(1$^{λ}$, U)

2. msk<sub>ra</sub>, mpk<sub>ra</sub> ← RASetup(pp)

3. msk<sub>sa</sub>, mpk<sub>sa</sub> ← SASetup(pp, mpk<sub>ra</sub>)

4. (m<sub>0</sub>, m<sub>1</sub>, A<sub>0</sub>, A<sub>1</sub>) ←
A<sup>OEnc</sup>, O<sub>EKGen</sub>(·, 'II'), O<sub>DKGen</sub>(mpk<sub>ra</sub>, mpk<sub>sa</sub>)

5. b $\stackrel{\$}{\leftarrow}$ {0, 1}

6. ek<sub>A<sub>b</sub></sub> ← EKGen(pp, msk<sub>sa</sub>, A<sub>b</sub>)

7. c<sub>b</sub> ← Enc(pp, m<sub>b</sub>, ek<sub>A<sub>b</sub></sub>)

8. b' ← A<sup>OEnc</sup>, O<sub>EKGen</sub>(·, 'II'), O<sub>DKGen</sub>(c<sub>b</sub>)

No-Write Game Definition

1. pp ← GlobalSetup(1$^{λ}$, U)

2. msk<sub>ra</sub>, mpk<sub>ra</sub> ← RASetup(pp)

3. msk<sub>sa</sub>, mpk<sub>sa</sub> ← SASetup(pp, mpk<sub>ra</sub>)

4. (c*, A*) ←
A<sup>OEnc</sup>, O<sub>EKGen</sub>(·, 'I'), O<sub>DKGen</sub>(mpk<sub>ra</sub>, mpk<sub>sa</sub>)

5. c<sub>0</sub> := c*

6. ek<sub>A*</sub> ← EKGen(pp, msk<sub>sa</sub>, A*)

7. m $\stackrel{\$}{\leftarrow}$ M, aux $\leftarrow$ fix(c<sub>0</sub>)

8. c<sub>1</sub> ← Enc(pp, m, ek<sub>A*</sub>, aux)

9. b $\stackrel{\$}{\leftarrow}$ {0, 1}, c'<sub>b</sub> ← San(c<sub>b</sub>)

10. b' ← A<sup>OEnc</sup>, O<sub>EKGen</sub>(·, 'I'), O<sub>DKGen</sub>(c'<sub>b</sub>)

Oracle Definition

$\mathcal{O}_{\text{EKGen}}(\mathbb{A}, \text{Phase}):$

1. If Phase = 'I' : I<sub>W</sub> = I<sub>R</sub> ∪ {A}

2. Return ek<sub>A</sub> ← EKGen(pp, msk<sub>sa</sub>, A)

$\mathcal{O}_{\text{DKGen}}(\mathcal{L}):$

1. I<sub>R</sub> = I<sub>R</sub> ∪ {L}

2. Return dkL ← DKGen(pp, mskL, L)

$\mathcal{O}_{\text{Enc}}(m, \mathbb{A}):$

1. ek<sub>A</sub> ← EKGen(pp, msk<sub>sa</sub>, A)

2. Return c ← Enc(pp, m, ek<sub>A</sub>)

$\mathcal{O}_{\text{SEnc}}(m, \mathbb{A}):$

1. ek<sub>A</sub> ← EKGen(pp, msk<sub>sa</sub>, A)

2. c ← Enc(pp, m, ek<sub>A</sub>)

3. Return c' ← San(pp, c)

Figure 1: Wang et al. [7] Security Games for No-Read and No-Write Rules of Cross-Domain AB-ACE.

Correctness. For all A and L such that L ⊊ A,

$$
\Pr[\text{Dec}(\text{dk}_L, \text{San}(\text{pp}, \text{Enc}(\text{pp}, \text{ek}_A, m))) \neq m] < \text{negl}(\lambda),
$$

where pp ← GlobalSetup(1$^{λ}$, U), (mpk<sub>ra</sub>, msk<sub>ra</sub>) ← RASetup(pp), (mpk<sub>sa</sub>, msk<sub>sa</sub>) ← SASetup(pp, mpk<sub>ra</sub>), ek<sub>A</sub> ← EKGen(pp, msk<sub>sa</sub>, A), and dk<sub>L</sub> ← DKGen(pp, msk<sub>ra</sub>, L).

This definition naturally adapts to non-cross-domain ACE schemes by taking
msk = (msk<sub>ra</sub>, msk<sub>sa</sub>).

To enforce access control without revealing sender or receiver identities, Damgård et al. [1] introduced two security principles:
*   **No-Read Property:** unauthorized receivers learn nothing about $m$ or the sender.

*   **No-Write Property:** senders unauthorized to communicate with a group of receivers cannot send them any information, even if they collaborate.

The formalization of the No-Read property was decomposed into payload privacy (unauthorized entities cannot recover $m$ or identify the sender) and sender anonymity (even authorized receivers cannot determine the sender), but the latter was soon dropped for lack of practical relevance. Consequently, "No-Read Rule" now denotes payload privacy only.

Originally defined for identity-based ACE, these rules were later adapted to the attribute-based setting by replacing user identities with access structures or attribute sets. The strongest formulation to date is due to Wang et al. [7], summarized in Figure 1.

**No-Read Rule.** An adversary $\mathcal{A}$ wins the No-Read Game defined in Figure 1, with access to the listed oracles, if it correctly guesses $b$ under the payload privacy condition

$$ \forall \mathcal{L} \in \mathcal{I}_R, \mathbb{A}_0(\mathcal{L}) = \mathbb{A}_1(\mathcal{L}) = 0. $$

The No-Read Rule is satisfied if for every PPT adversary $\mathcal{A}$,

$$ | \Pr(\mathcal{A} \text{ wins}) - \frac{1}{2} | < \text{negl}(\lambda). $$

Here, the challenger emulates the sender, while the adversary can hold decryption keys (including the sanitizer's, if any, in order to be able to construct sanitized ciphertext) to simulate a set of receivers unable to decrypt $c$. Wang et al. [7] propose the strongest known security model for AB-ACE. Earlier definitions usually imposed $\mathbb{A}_0 = \mathbb{A}_1$, since most CP-ABE schemes embed the access structure in cleartext within the ciphertext, making it trivially distinguishable. Wang's model removes this constraint by hiding $\mathcal{A}$, thereby ensuring confidentiality of both the message and the policy. However, this formulation no longer enforces the original No-Read Rule from identity-based ACE: by operating solely over attributes and access structures, it omits sender identities and thus provides no identifier confidentiality (if any).

**No-Write Rule.** An adversary wins the No-Write Game (Figure 1) if:

1.  $\mathbb{A}^* \in \mathcal{I}_W$;

2.  $\forall \mathbb{A} \in \mathcal{I}_W, \forall \mathcal{L} \in \mathcal{I}_R, \mathbb{A}(\mathcal{L}) = 0$;

3.  $\text{San}(\mathbb{p}\mathbb{p}, c_0) \neq \perp$;

4.  $b' = b$.

The No-Write Rule is satisfied if, for all PPT adversaries $\mathcal{A}$:

$$ | \Pr(\mathcal{A} \text{ wins}) - \frac{1}{2} | < \text{negl}(\lambda). $$

To ensure that a sender cannot transmit information bypassing the security policy, sanitization must eliminate all exploitable links between $c$ and $c'$. Oracle $\mathcal{O}_{SEnc}$ allows the adversary to obtain sanitized ciphertexts from any access structure, despite the limitations on encryption keys available via $\mathcal{O}_{EKGen}$. Wang et al. [12] introduced a fix function to handle metadata (e.g., timestamps) that could be easily distinguished. Weaker variants sometimes assume a fixed $\mathbb{A}^*$ or decompose sanitization into two sub-algorithms (*Authenticate*, *Sanitize*), where the adversary's goal is only
to produce a valid authentication without the corresponding key, ensuring compliance with the security policy but allowing linkability between $c$ and $c'$.

Finally, as pointed out by Badertscher et al. [19], the No-Write Rule still allows malleability attacks: a malicious sender may still exploit ciphertext transformations to leak information, a limitation inherited from Damgård's original formulation.

# 5 Breaking The Anonymity of Internal Traffic

This section presents attacks that compromise sender and receiver privacy. We show how ciphertext data, particularly the disclosure of the access structure, can be exploited to identify the sender or establish links between ciphertexts. We also show how this lack of anonymity can be used to infer some information about authorized receivers under specific policies.

## 5.1 Linking Ciphertexts from an Anonymous Sender

This subsection illustrates how ciphertexts can be *individualized*, i.e. linked to a unique (though still anonymous) sender.

Although AB-ACE schemes aim to move away from identities, several attack vectors can still reveal the sender of a ciphertext. As mentioned earlier, in most current AB-ACE schemes the access structure is included in the clear in ciphertext [2, 4, 5]. In AB-ACE systems, where each sender is restricted to using only one (or a very limited set of) access structure(s), learning the access structure $A$ allows the sanitizer to drastically narrow down the set of possible senders, or even identify the sender if each user employs a distinct access structure. The same reasoning applies to KP-ABE based constructions [6], where the attributes associated with the ciphertext are transmitted in clear.

However, this kind of leakage does not distinguish between two senders sharing the same access structure, nor does it apply to schemes that hide the access structure.

More critically, other forms of persistent fingerprints exist that can link ciphertexts from the same sender across multiple messages, even when the access structure is hidden. Some AB-ACE schemes embed values derived from user identifiers in their ciphertexts, such as hashed IDs within authentication tokens [2, 5]. In Cui et al.'s scheme [5], this hash is transmitted in clear. In contrast, the scheme of Han et al. [2] attempts to obfuscate this information by randomizing it with a fresh random value $z$, yet the underlying identifier remains recoverable: the authentication token includes randomized components $R_1 = g^{z/(\mathcal{H}(ID)+\gamma)}$ and $R_3 = g^{1/z}$, but their pairing yields a deterministic invariant $e(R_1, R_3) = g^{1/(\mathcal{H}(ID)+\gamma)}$ which is unique to each user $ID$ and reappears across all ciphertexts from that user. Similarly, a fresh random value may be embedded into the encryption key of each user and propagated into every ciphertext the user produces. If this user-specific randomness can be isolated from the randomness injected during encryption, the sender of a ciphertext becomes identifiable. An instance of this appears in the security analysis of the scheme of Wang et al. [7].

Among the five AB-ACE contributions studied [2, 4, 5, 6, 7], only the construction of Huang [6] appears to fully avoid any form of persistent fingerprints.

## 5.2 Identifying the Receivers

While ACE preserves the anonymity of issuers in principle, as described above, this anonymity can be compromised when the access structure is transmitted in clear text. Such a policy-in-the-clear opens the door to the same inference attacks as those documented in ABE.
More importantly, learning both the sender's identity and the access structure of a ciphertext may allow the sanitizer to infer the identity of potential receivers. In settings where each user receives a unique key associated with an attribute set $\mathcal{L}$ for both encryption and decryption, and where the access structures a user can formulate are determined by the attributes they possess (as in [2, 5]), identifying the sender of a ciphertext and observing the access structure immediately reveals that the sender holds the attributes appearing in that structure. Given the sender's attributes, the sanitizer can then infer which ciphertexts this user is able to decrypt. Consequently, by learning the attributes of each user, it can deduce all possible recipients for each ciphertext and reconstruct an almost complete view of the internal traffic.

This attack remains relevant even under the weaker assumption that users can decrypt their own ciphertexts (e.g. in cloud storage scenarios or when communication is allowed between users sharing the same attributes): knowing that a user satisfies the access structure associated with a ciphertext is sufficient to infer, with non-negligible probability, certain attributes she/he possesses, and thus to reduce the set of potential receivers, without relying on any additional information.

## 5.3 Extracting the Access Structure

Wang et al. [7] hide the access structure explicitly in the ciphertext, which prevents trivial information about authorized receivers. Still, information about (or even fully reconstruct) the structure $\mathcal{A}$ can be recovered by exploiting algebraic relations between ciphertext components and the policy used for encryption (or, in KP-ABE based constructions, the corresponding attribute set).

The core idea is to derive an invariant $\Delta$ from the ciphertext that depends only on $\mathcal{A}$ and data known to the adversary. For any candidate structure $\mathcal{A}'$, the adversary computes the corresponding $\Delta'$ and checks $\Delta =? \Delta'$. If $\Delta \neq \Delta'$ then $\mathcal{A} \neq \mathcal{A}'$. In some schemes one invariant suffices; in others a few complementary invariants are required. This idea can be implemented using two strategies:

**Direct structural invariants:** isolate in the ciphertext those terms that depend on the access structure (for example, products of public elements associated with attributes or attribute-values). By algebraic manipulation, it is possible to cancel out the fresh randomness injected during encryption and obtain an expression determined solely by $\mathcal{A}$. An adversary can precompute these invariants for all candidate structures and compare them to the invariant derived from the challenge ciphertext to determine the policy used (see Section 7.2).

**Boolean tests via attribute sets:** pick, for a candidate access structure $\mathcal{A}'$, an attribute set $\mathcal{L}$ with $\mathcal{A}'(\mathcal{L}) = 1$ and evaluate a predicate $f_{\mathcal{A}'}(c, \mathcal{L}) \in \{0, 1\}$ designed so that $f_{\mathcal{A}'}(c, \mathcal{L}) = 1$ implies $\mathcal{L}$ also satisfies the unknown structure $\mathcal{A}$. In the common case, a failed test only eliminates the specific candidate $\mathcal{A}'$ (see Section 7.3). However, the informational content of the predicate depends on how strongly it relates to $\mathcal{A}'$. Consider the set of structures compatible with the test outcome:

$$S_{\mathcal{A}'} = \{ \mathcal{A} \mid c \text{ was encrypted under } \mathcal{A} \wedge f_{\mathcal{A}'}(c, \mathcal{L}) = 1 \}.$$

A positive result $f_{\mathcal{A}'}(c, \mathcal{L}) = 1$ implies that the actual structure $\mathcal{A}$ belongs to $S_{\mathcal{A}'}$, while a negative result implies $\mathcal{A} \notin S_{\mathcal{A}'}$.

Both strategies turn a supposedly anonymous ciphertext into a testable object whose algebraic properties leak information about the embedded access structure.

# 6 Multi-Valued AND-Gates ABACE

Wang et al. [7] introduced two schemes, both referred to as ABACE, designed to conceal the access structure within ciphertexts. The Multi-Valued AND-Gates ABACE variant considers a universe of
attributes $\mathbb{U} = \{\omega_1, \dots, \omega_n\}$, where each attribute $\omega_i$ takes a single value $v_{i,k_i}$ from a finite domain $S_i$. We denote by $m = \max_{i=1}^n |S_i|$ the maximum number of possible values for an attribute.

**Setup and Authorities.** The system operates over Type III bilinear groups $\mathcal{G} = (p, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, e)$ and involves two authorities: a receiver authority (RA) that executes a sCP-ABE setup derived from [16], and a sender authority (SA) responsible for issuing structure-preserving signatures [20] and publishing a CRS for a NIZK proof system.

For each attribute-value pair $v_{i,k_i}$, RA publishes elements $\beta_{i,k_i} \in \mathbb{G}_1$ and $\gamma_{i,k_i} \in \mathbb{G}_T$. SA publishes a verification key $vk = (V, X)$ and the common reference string crs.

**Encryption Keys.** An access structure $\mathbb{A} = \bigwedge_{i \in \mathcal{I}_\mathbb{A}} (\omega_i = v_{i,k_i})$ is encoded as

$$ \beta_{\mathbb{A}} = \prod_{i \in \mathcal{I}_{\mathbb{A}}} \beta_{i,k_i}, \quad \gamma_{\mathbb{A}} = \prod_{i \in \mathcal{I}_{\mathbb{A}}} \gamma_{i,k_i}. $$

To certify the origin of $\beta_{\mathbb{A}}$, SA signs it using the rerandomizable structure-preserving signature of [20], producing a signature $\sigma = (R_{\beta}, S_{\beta}, T_{\beta}) \in \mathbb{G}_2 \times \mathbb{G}_1^2$ with

$$ R_{\beta} = g_2^{t_u}, \quad S_{\beta} = \beta_{\mathbb{A}}^{v/t_u} X^{1/t_u}, \quad T_{\beta} = S_{\beta}^{v/t_u} g_1^{1/t_u}. $$

The resulting encryption key is

$$ \mathrm{ek}_{\mathbb{A}} = (\beta_{\mathbb{A}}, \gamma_{\mathbb{A}}, \sigma, W), $$

where $W = g_1^{1/t_u}$ acts as a randomization token. This signature will later be verified via a NIZK proof.

**Decryption Keys.** Decryption keys are generated as in Zhang et al. [16] for the attribute set $\mathcal{L}$. To conceal the access structure inside ciphertexts, each decryption key embeds a set $\mathbb{A}^*$ containing all access structures ever distributed to at least one sender and satisfied by $\mathcal{L}$. The decryption algorithm must test each $\mathbb{A} \in \mathbb{A}^*$ individually.

**Encryption and Sanitization.** To encrypt a message $m \in \mathbb{G}_T$ under $ek_{\mathbb{A}}$, the sender first rerandomizes the key:

$$ R'_{\beta} = R_{\beta}^{1/r}, \quad S'_{\beta} = S_{\beta}^{r}, \quad T'_{\beta} = T_{\beta}^{r^2} W^{r(1-r)}, \quad \sigma' = (R', S', T'), \quad \beta'_{\mathbb{A}} = \beta_{\mathbb{A}}^{r}, \quad \gamma'_{\mathbb{A}} = \gamma_{\mathbb{A}}^{r}. $$

This step simplifies the generation and verification of NIZK proofs. Then, sampling $u_1, u_2 \leftarrow \mathbb{Z}_p^*$, the sender computes:

$$ C_1 = g_1^{ru_1}, \quad C_2 = (\beta'_{\mathbb{A}})^{u_1}, \quad C_3 = m \cdot (\gamma'_{\mathbb{A}})^{u_1}, \quad c_1 = g_1^{ru_2}, \quad c_2 = (\beta'_{\mathbb{A}})^{u_2}, \quad c_3 = (\gamma'_{\mathbb{A}})^{u_2}. $$

A NIZK proof $\pi$ demonstrates that these components are correctly derived from a valid, SA-signed $\beta_{\mathbb{A}}$. The ciphertext is

$$ c = (C_1, C_2, C_3, c_1, c_2, c_3, \pi, \sigma', \beta'_{\mathbb{A}}, \gamma'_{\mathbb{A}}, V^{1/r}, g_1^r). $$

Before distribution, the sanitizer verifies both $\sigma'$ and $\pi$, then rerandomizes the ciphertext using random $u_3$:

$$ c' = (C'_1, C'_2, C'_3) = (C_1 \cdot c_1^{u_3}, C_2 \cdot c_2^{u_3}, C_3 \cdot c_3^{u_3}). $$
**Decryption.** Given $dk_{\mathcal{L}}$, the receiver iterates over all $\mathbb{A} \in \mathbb{A}^*$, attempting decryption for each. If the resulting message $m'$ is a valid plaintext, decryption is considered successful.

# 7 Security Analysis of ABACE

Wang et al. prove in [7] that their generic ABACE construction satisfies the No-Read and No-Write rules under standard cryptographic assumptions, notably that the underlying sCP-ABE scheme is wPH-IND-CPA secure. They instantiate their scheme using the rerandomizable signature of Abe et al. [20] and prove that their own sCP-ABE scheme satisfies the wPH-IND-CPA property.

Their security proof, however, considers an idealized ciphertext in which the NIZK-related elements are hidden. In the actual implementation, several auxiliary values included to facilitate proof generation and verification are exposed to the sanitizer. These values are not modeled in the proof, but can be exploited by an adversary, enabling the key-linking and policy-recovery attacks described next.

## 7.1 Linking Ciphertexts from an Anonymous Sender

Although Wang's No-Read Rule ensures message and policy confidentiality, it does not guarantee sender anonymity. During encryption key generation, the random value $t_u$ used in signing $\beta_{\mathbb{A}}$ (via Abe's rerandomizable signature) reappears in all ciphertexts encrypted with $ek_{\mathbb{A}}$. If an adversary isolates $t_u$ from the fresh randomness $(r, u_1, u_2)$ used during encryption, it can derive a persistent invariant tied to $ek_{\mathbb{A}}$ and thus link ciphertexts from the same sender. For instance:

$$e(g_1^r, R') = e(g_1, g_2)^{t_u} \quad \text{or} \quad e(S', V^{1/r}) = e(S_{\beta}, V),$$

both yield values independent of $r$, acting as fingerprints linking together all ciphertexts issued by the same user. Such linking does not contradict the No-Read game, where only one key and ciphertext are issued, but reveals a gap in its definition. The same approach can be applied to the scheme of Sedaghat et al., which similarly uses the rerandomizable signature of Abe et al. [20]. This randomness-based fingerprint constitutes a powerful anonymity breach, since it bypasses the intended protection of the No-Read property without revealing directly any plaintext or identity.

## 7.2 Breaking the No-Read Rule

To break the No-Read Rule, an adversary must be able to distinguish between two ciphertexts $c_0$ and $c_1$ respectively encrypted under $\mathbb{A}_0$ and $\mathbb{A}_1$. In Multi-Valued AND-Gates ABACE, this can be done by testing whether a ciphertext was produced under a given policy, using visible rerandomized terms:

$$\beta'_{\mathbb{A}} = \beta_{\mathbb{A}}^r, \quad V^{1/r}.$$

Since $\beta_{i,k_i}$ (public elements of $\beta_{\mathbb{A}}$) are known, we have

$$e(\beta'_{\mathbb{A}}, V^{1/r}) = e\left(\prod_{i \in \mathcal{I}_{\mathbb{A}}} \beta_{i,k_i}^r, V^{1/r}\right) = e\left(\prod_{i \in \mathcal{I}_{\mathbb{A}}} \beta_{i,k_i}, V\right),$$

which is entirely determined by $\mathbb{A}$ and the public parameters. An adversary can test whether the challenge ciphertext $c_b$ was encrypted under $\mathbb{A}_0$ by setting

$$\tau_b := e(\beta'_{\mathbb{A}_b}, V^{1/r}) \quad \text{and} \quad \tau_0 := e\left(\prod_{i \in \mathcal{I}_{\mathbb{A}_0}} \beta_{i,k_i}, V\right).$$
If $\tau_b = \tau_0$ then $\mathbb{A}_b = \mathbb{A}_0$ and $b = 0$, otherwise $b = 1$. Thus, the adversary can break the No-Read Rule.

When the number of possible policies $\mathbf{N} = (m+1)^n$ is small, the access structure used in a ciphertext can be identified through exhaustive testing. Once a sender's policy is learned, all ciphertexts from the same sender can be immediately linked to this policy. Furthermore, by prioritizing structures according to their frequency or other metadata, the adversary can significantly reduce the expected number of tests required.

## 7.3 LSSS-Based ABACE

A similar attack can be mounted against the Linear Secret Sharing Scheme (LSSS) based variant, derived from the Waters CP-ABE construction [9]. Each access structure is represented by $(\mathbf{M}, \rho)$, where $\mathbf{M} \in \mathbb{Z}_p^{l \times d}$ and $\rho$ is an injective mapping. Since the size of $(\mathbf{M}, \rho)$ depends on the access structure, the authors introduce a padding parameter $L$ to prevent leakage on the structure length.

For an access structure $(\mathbf{M}, \rho)$, the sender authority first chooses a random $s \in \mathbb{Z}_p^*$ and derives an encryption key containing policy-dependent components:

$$ (A_1 = g_1^{a\lambda_1} h_{\rho(1)}^{-r_1}, B_1 = g_1^{r_1}), \dots, (A_l = g_1^{a\lambda_l} h_{\rho(l)}^{-r_l}, B_l = g_1^{r_l}), $$

together with random padding pairs $(A_{l+1}, B_{l+1}), \dots, (A_L, B_L)$ and $A = e(g_1, g_2)^{\alpha s}$, $A_0 = g_1^s$. Here $\{h_i = g_1^{b_i}\}_{1 \le i \le L}$, $e(g_1, g_2)^{\alpha}$, $g_1^a$, and $g_2^a$ are public parameters. Encryption key also includes signatures generated using the same rerandomizable structure-preserving signature of Abe et al. [20] for all elements except $A \in \mathbb{G}_T$.

Encryption rerandomizes these values with a fresh exponent $r$ as in the multi-valued variant, and using random values $u_1 \in \mathbb{Z}_p^*$, computes ciphertext terms

$$ C_m = m \cdot A^{ru_1}, \quad C_0 = A_0^{ru_1}, \quad (C_i = A_i^{ru_1}, D_i = B_i^{ru_1})_{1 \le i \le L}, $$

together with sanitizing terms under $u_2$ and a NIZK proof of consistency.

As in the multi-valued variant, auxiliary data $V^{1/r}$ remain visible to the sanitizer, leading to the same attack as in Section 7.1.

Let $(\mathbf{M}^*, \rho^*)$ be the hidden access structure and $\mathbb{B} \subseteq \mathbb{U}$ a subset of attributes such that there exist coefficients $\omega_i$ satisfying

$$ \sum_{i \in \mathcal{I}_{\mathbb{B}}} \omega_i \mathbf{M}_i^* = (1, 0, \dots, 0). $$

From any ciphertext, an adversary can compute (using the public parameters $h'_i = g_2^{b_i}$)

$$ X_1 = \prod_{i \in \mathcal{I}_{\mathbb{B}}} e(D_i, h'_{\rho^*(i)})^{\omega_i}, \quad X_2 = e(C_0, g_2^a), \quad X_3 = e \left( \prod_{i \in \mathcal{I}_{\mathbb{B}}} C_i^{\omega_i}, g_2 \right). $$

The equality $X_3 \cdot X_1 = X_2$ fails only when the tested access structure $(\mathbf{M}, \rho) \neq (\mathbf{M}^*, \rho^*)$, regardless of the random values $r, u_1, u_2$. Hence, an adversary given two candidate policies $(\mathbf{M}_0, \rho_0)$ and $(\mathbf{M}_1, \rho_1)$ such that there exist coefficients $\omega_i$ verifying

$$ \sum_{i \in \mathcal{I}_{\mathbb{B}}} \omega_i \mathbf{M}_{0,i} = (1, 0, \dots, 0) \text{ and } \sum_{i \in \mathcal{I}_{\mathbb{B}}} \omega_i \mathbf{M}_{1,i} \neq (1, 0, \dots, 0), $$

can test which one was used in a challenge ciphertext simply by checking whether the above equality holds under $\rho^* = \rho_0$ and break the No-Read Rule. This attack relies solely on data from the
sCP-ABE and demonstrates that the proposed sCP-ABE construction does not satisfy the wPH-IND-CPA security notion. It highlights that merely concealing the access structure is insufficient to ensure wPH-IND-CPA security.

Note that the attack critically depends on the public availability of the terms $h_i' = g_2^{b_i}$ and $g_2^a$, which are used only during decryption-key generation. A straightforward fix is therefore to remove $g_2^a$ (and, if desired, the $h_i'$) from the public parameters and to include them instead in the Receiver Authority's master secret key, since they are never required during encryption. This prevents forming the test values $X_1, X_2, X_3$ and rules out the attack.

# 8 Mitigating Anonymity Leaks

The attacks of Sections 5 and 7 highlight three core sources of leakage:

1. explicit or implicit exposure of the access structure in the ciphertext;

2. presence of identifier-dependent fields that produce persistent fingerprints across ciphertexts;

3. persistence of randomness introduced at encryption key generation that survives rerandomization and becomes linkable.

Below we describe practical mitigation directions and discuss their trade-offs.

**Masking or abstracting the access structure** A first line of defense is to remove all direct encodings of the access structure from ciphertexts. One pragmatic design (used by Wang et al. [7]) is to include in each decryption key an aggregate set $A^*$ gathering all access structure ever issued to a sender and compatible with the receiver's attributes. This prevents trivial reading of the policy from the ciphertext. A symmetric adaptation can be applied to KP-ABE-based ACE schemes, such as that of Huang et al., by embedding in each decryption key a set $\mathcal{L}^*$ gathering all attribute sets ever assigned to a sender and compatible with the receiver's access structure.

However, abstraction alone is insufficient when algebraic dependencies remain in exposed components; an adversary can still test candidate structures by computing structure-dependent invariants. Another approach involves constructing AB-ACE schemes directly using wPH-IND-CPA secure ABE, though this may introduce efficiency challenges.

**Restricting or removing auxiliary NIZK data** Our analysis shows that auxiliary elements included to facilitate NIZK generation and verification can leak information. A stronger alternative is to eliminate these auxiliary elements entirely, or partially, ensuring they will not leak any information, even if this complicates NIZK proof generation.

**Removing identifier-dependent authentication terms** Several constructions (e.g., [2, 5]) include an *authentication token* in the ciphertext to let the sanitizer check that the ciphertext was produced using a legitimate key. When the token includes a (hash of an) identifier or can yield to an invariant (see Section 5), it becomes a persistent fingerprint. To avoid this, authentication can be done by using NIZK Proofs, as in all other schemes.
**Strengthening the No-Read Rule**

Beyond protocol-level fixes, the underlying security model itself must also be reinforced. Existing formulations of the *No-Read* property, including that of Damgård et al. [1], do not capture the possibility of linking multiple ciphertexts originating from the same sender, when encryption key generation is non-deterministic. To address this limitation, we propose a strengthened *No-Read Rule* defined through a new security game that requires an adversary to be unable to distinguish whether two ciphertexts were produced under the same encryption key.

The game in Figure 2 formalizes this notion in the context of cross-domain AB-ACE, using the oracles $O_{Enc}(\cdot)$, $O_{EKGen}(\cdot)$, and $O_{DKGen}(\cdot)$ defined in Figure 1.

1. $\mathbf{pp} \leftarrow \text{GlobalSetup}(1^{\lambda}, \mathcal{U})$

2. $\mathbf{msk}_{ra}, \mathbf{mpk}_{ra} \leftarrow \text{RASetup}(\mathbf{pp})$

3. $\mathbf{msk}_{sa}, \mathbf{mpk}_{sa} \leftarrow \text{SASetup}(\mathbf{pp}, \mathbf{mpk}_{ra})$

4. $(m_0, m_1, \mathbb{A}_0, \mathbb{A}_1) \leftarrow \mathcal{A}^{O_{Enc}, O_{EKGen}(\cdot, \cdot'II')}_{DKGen}(\mathbf{mpk}_{ra}, \mathbf{mpk}_{sa})$

5. $b \stackrel{\$}{\leftarrow} \{0, 1\}$

6. $ek_{\mathbb{A}_0} \leftarrow \text{EKGen}(\mathbf{pp}, \mathbf{msk}_{sa}, \mathbb{A}_0)$

7. $ek_{\mathbb{A}_1} \leftarrow \text{EKGen}(\mathbf{pp}, \mathbf{msk}_{sa}, \mathbb{A}_1)$

8. $\hat{c} \leftarrow \text{Enc}(\mathbf{pp}, m_0, ek_{\mathbb{A}_0})$

9. $c_b \leftarrow \text{Enc}(\mathbf{pp}, m_b, ek_{\mathbb{A}_b})$

10. $b' \leftarrow \mathcal{A}^{O_{Enc}, O_{EKGen}(\cdot, \cdot'II')}_{DKGen}(\hat{c}, c_b)$

<caption>Figure 2: Strengthened No-Read Rule for Cross-Domain AB-ACE.</caption>

The adversary $\mathcal{A}$ wins this game if it correctly guesses $b$ under the standard payload privacy condition ($\forall \mathcal{L} \in \mathcal{I}_R, \mathbb{A}_0(\mathcal{L}) = \mathbb{A}_1(\mathcal{L}) = 0$). The original *No-Read Rule* definition remains otherwise unchanged.

This upgraded game explicitly captures *cross-ciphertext unlinkability*. The definition can be naturally adapted to identity-based ACE by replacing access structures and attribute sets with identities. In that case, the adversary wins if it correctly guesses $b$ while satisfying $\forall i \in \mathcal{I}_R, P(i_0, i) = P(i_1, i) = 0$. It can also be applied to single-domain ACE by merging the GlobalSetup, RASetup, and SASetup algorithms. Finally, when encryption key generation is deterministic, the challenger's key can be returned by the oracle $O_{EKGen}(\cdot)$. Consequently, schemes with deterministic key generation remain unaffected by this strengthening and preserve their original security guarantees under the new game.

# 9 Conclusion

Traffic anonymity is an essential property to justify the use of ACE. Without it, a simpler model where the sanitizer directly verifies the identities of senders and receivers would be both easier to implement and more efficient, while offering the same level of access control. Nevertheless, ACE retains the formal advantage of ensuring message confidentiality, even in the presence of the sanitizer.

Our analysis, however, shows that current AB-ACE constructions fail to meet this objective. Most of them explicitly reveal the access structure, thus leaking sensitive information about senders
or receivers to the sanitizer, in some cases granting near-complete visibility over internal traffic. Even variants designed to hide the access structure remain vulnerable when the attribute space is restricted. Moreover, the various security games based on the *No-Read Rule* have proven insufficient to ensure anonymity of senders, including the original model of Damgård *et al*.

Finally, we demonstrate a critical flaw in the scheme of Wang *et al.*, in which some elements directly expose the access structure, constituting a fundamental breach of confidentiality that invalidates their security claims.

In summary, while ACE continues to ensure the confidentiality of messages, the anonymity of communications in current AB-ACE constructions remains unprotected. These observations emphasize the need to rethink both the constructions and the underlying security definitions of AB-ACE in order to achieve robust anonymity.

## Acknowledgment

This work was partially supported by the Agence de l'Innovation de Défense (AID, DGA), France, and by the TRUSTINCloudS project (ANR), under the France 2030 program, reference ANR-23-PECL-0002.

## References

[1] Ivan Damgård, Helle H. Haagh, and Claudio Orlandi. "Access Control Encryption: Enforcing Information Flow with Cryptography". In: *Theory of Cryptography (TCC 2016-B)*. Vol. 9985. Lecture Notes in Computer Science. Full version: IACR ePrint 2016/106. Springer, 2016, pp. 547-576.

[2] Jinguang Han, Liqun Chen, Willy Susilo, Xinyi Huang, Aniello Castiglione, and Kaitai Liang. "Fine-Grained Information Flow Control Using Attributes". In: *Information Sciences* 484 (2019), pp. 167-182.

[3] Article 29 Data Protection Working Party. *Opinion 05/2014 on Anonymisation Techniques*. Tech. rep. WP216. Adopted 10 April 2014. European Commission, Apr. 2014.

[4] Mahdi Sedaghat and Bart Preneel. "Cross-Domain Attribute-Based Access Control Encryption". In: *Cryptology and Network Security (CANS 2021)*. Vol. 13099. Lecture Notes in Computer Science. Springer, 2021, pp. 3-23.

[5] Jie Cui, Bo Li, Hong Zhong, Geyong Min, Yongxin Xu, and Lei Liu. "A Practical and Efficient Bidirectional Access Control Scheme for Cloud-Edge Data Sharing". In: *IEEE Transactions on Parallel and Distributed Systems* 33.2 (Feb. 2022), pp. 476-488.

[6] Qinlong Huang, Chao Wang, and Lixuan Chen. "Secure and Fine-Grained Flow Control for Subscription-Based Data Services in Cloud-Edge Computing". In: *IEEE Transactions on Services Computing* 16.4 (2023), pp. 2165-2177.

[7] Xiuhua Wang, Mengyang Yu, Yaohui Wang, Yinjia Pi, Peng Xu, Shuai Wang, Hai Jin, and Min Han. "Attribute-Based Access Control Encryption". In: *IEEE Transactions on Dependable and Secure Computing* 22.3 (2025), pp. 2227-2242.

[8] Georg Fuchsbauer, Romain Gay, Lukas Kowalczyk, and Claudio Orlandi. "Access Control Encryption for Equality, Comparison, and More". In: *Public-Key Cryptography (PKC 2017)*. Vol. 10174. Lecture Notes in Computer Science. Springer, 2017, pp. 88-118.
[9] Brent Waters. "Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization". In: *Public Key Cryptography (PKC 2011)*. Vol. 6571. Lecture Notes in Computer Science. Springer, 2011, pp. 53–70.

[10] Shashank Agrawal and Melissa Chase. "FAME: Fast Attribute-based Message Encryption". In: *Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS '17)*. ACM, 2017, pp. 665–682.

[11] Yannis Rouselakis and Brent Waters. "Practical Constructions and New Proof Methods for Large Universe Attribute-Based Encryption". In: *Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security (CCS '13)*. ACM, 2013, pp. 463–474.

[12] Xiuhua Wang and Sherman S. M. Chow. "Cross-Domain Access Control Encryption: Arbitrary-Policy, Constant-Size, Efficient". In: *2021 IEEE Symposium on Security and Privacy (SP)*. IEEE, 2021, pp. 748–761.

[13] Fuchun Guo, Yi Mu, Willy Susilo, Duncan S. Wong, and Vijay Varadharajan. "CP-ABE with Constant-Size Keys for Lightweight Devices". In: *IEEE Transactions on Information Forensics and Security* 9.5 (May 2014), pp. 763–771.

[14] Takashi Nishide, Kazuki Yoneyama, and Kazuo Ohta. "Attribute-Based Encryption with Partially Hidden Encryptor-Specified Access Structures". In: *Applied Cryptography and Network Security (ACNS) 2008*. Vol. 5037. Lecture Notes in Computer Science. Springer, 2008, pp. 111–129.

[15] Junzuo Lai, Robert H. Deng, and Yingjiu Li. "Fully Secure Cipertext-Policy Hiding CP-ABE". In: *Information Security Practice and Experience (ISPEC) 2011*. Vol. 6672. Lecture Notes in Computer Science. Springer, 2011, pp. 24–39.

[16] Yinghui Zhang, Dong Zheng, Xiaofeng Chen, Jin Li, and Hui Li. "Computationally Efficient Ciphertext-Policy Attribute-Based Encryption with Constant-Size Ciphertexts". In: *Provable Security (ProvSec 2014)*. Vol. 8782. Lecture Notes in Computer Science. Springer, 2014, pp. 259–273.

[17] Jens Groth and Amit Sahai. "Efficient Noninteractive Proof Systems for Bilinear Groups". In: *SIAM J. Comput.* 41 (2008), pp. 1193–1232.

[18] Amos Beimel. "Secret-Sharing Schemes: A Survey". In: *Coding and Cryptology – Third International Workshop, IWCC 2011*. Vol. 6639. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 2011, pp. 11–46.

[19] Christian Badertscher, Christian Matt, and Ueli Maurer. "Strengthening Access Control Encryption". In: *Advances in Cryptology – ASIACRYPT 2017, Part I*. Vol. 10624. Lecture Notes in Computer Science. Springer, 2017, pp. 502–532.

[20] Masayuki Abe, Jens Groth, Miyako Ohkubo, and Mehdi Tibouchi. "Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures". In: *Theory of Cryptography (TCC 2014)*. Vol. 8349. Lecture Notes in Computer Science. Springer, 2014, pp. 688–712.