ABEAT: Efficient and Anonymous Encryption for ABE-based Dynamic Group Communication

ABEAT: Efficient and Anonymous Encryption for ABE-based Dynamic Group Communication Hongmiao Yu∗ , Silas Richelson∗ , Jiachen Chen† , K. K. Ramakrishnan∗ ∗ Department of Computer Science and Engineering, University of California Riverside, Riverside, USA

arXiv:2608.19302v1 [cs.CR] 19 Aug 2026

† WINLAB, Rutgers University, North Brunswick, NJ, USA.

Abstract—Confidential communication among a dynamic group of participants that ensures flexible and efficient many-tomany communication is highly desired capability. We leverage attribute-based encryption (ABE) for confidential group communication and enhance it by a graph-based namespace to create an efficient framework that allows groups to be formed and changed dynamically. In this paper, we focus on the important additional need to maintain the anonymity of recipients of a message, when using ABE for group communication for a variety of usage scenarios (e.g., emergency response). We propose ABEAT, an efficient and anonymous dynamic group communication system that also minimizes overhead on receivers who are not the intended recipients of a message. In ABEAT, we propose a new anonymous KP-ABE approach to maintain recipient anonymity. ABEAT hides the clear attribute in the ciphertext of KP-ABE, and also prevents several attacks that seek to break anonymity. ABEAT provides fast recipient verification, dramatically lowering the decryption overhead for non-recipients by more than a factor of 90 versus the current state of the art such as hidden vector encryption (HVE). In fact, it is even 40% less than FABEO, which offers no anonymity.

I. I NTRODUCTION Group communication is critical to our society, being utilized for immediate interactive communication and notification among people and organizations. While commercial platforms such as WhatsApp and Signal provide large-scale solutions for secure communication, many specialized use cases require additional features which are not provided by the big platforms. Consider, for example, situations such as emergency response, military tactical operations, or corporate communications. Since group management (creation and modification) is costly for these large platforms, they are problematic in situations where the group composition changes dynamically. Additionally, end-to-end encryption (usually considered the “gold standard” for security in group communication) actually precludes features such as auditing which might be desirable. Indeed, during an emergency, first responders from different departments might collaborate, forming task-oriented groups for specific missions. Membership of these groups may need to change on the fly, without requiring costly group management operations every time. Moreover, while communication transcripts must be encrypted to ensure confidentiality against malicious parties, they would also need to be accessible to internal departments to ensure accountability, and allow for post-incident forensic analysis. Another requirement is that the underlying network infrastructure during emergencies may experience disruptions, resulting in loss, delay, and messages being delivered out-of-order, rather than delivering messages (especially application control messages) reliably. Use of Namespaces for Groups. Previous work has shown that namespaces are an effective mechanism for managing

dynamic group communication for emergency response [22], [50]. Namespaces facilitate the dynamic formation of groups among recipients and are typically used in a publish/subscribe framework structured according to the role-hierarchy of the participating members. Before an operation begins, members subscribe to names that correspond to their assigned roles. During the operation, a sender publishes messages to one or more roles rather than to specific individuals. Furthermore, namespaces can be flexibly modified, or names (or even subtrees of the namespace) added during an emergency response, supporting highly dynamic group membership changes. As described in [50], Attribute-Based Encryption (ABE) can be an effective mechanism to ensure confidentiality for such namespace-based dynamic group communication. ABE provides several advantages: (1) No need for group key establishment: ABE eliminates the requirement for a shared group key among members. This is especially valuable in emergency or tactical scenarios where some participants may be unreachable intermittently due to damaged infrastructure [22]. By treating namespaces as attributes, senders can target specific roles at the time of sending a message, freely adjusting the recipients for each transmission. In contrast, group messaging systems such as Message Layer Security (MLS) require ordered, lossless message delivery, and relatively stable membership, making them unsuitable for highly dynamic groups and unreliable communication environments. (2) Finegrained access control: ABE supports flexible policies with attributes, enabling mechanisms such as time-based access control (e.g., using timestamps as attributes to determine when a message becomes accessible). Other namespace-based encryption approaches that rely on traditional PKE—such as NDN trust schemes [52]—lack this level of expressiveness. (3) Centralized key issuance for accountability: ABE relies on a central authority to issue decryption keys. While centralized key management may raise privacy concerns in general-purpose consumer focused messaging applications, it is advantageous in specialized operations (first responder or corporate group communications). The key issuer can support auditing, oversight, and post-operation analysis by appropriate entities with authorized access. Anonymous ABE. Anonymity is a security notion which guarantees that nobody is able to tell who a message is intended for, unless it has been sent to them. Since ABE attributes are typically not hidden by ABE ciphertexts, our plan to use the attributes to identify the target recipients raises a security concern which would be extremely problematic in an emergency response scenario. For example, imagine a hostage situation: if law enforcement is communicating non-

anonymously, then the perpetrators might notice if the task force HQ sends a series of messages to a particular unit. This could reveal the rescue plan to perpetrators, even if they are unable to read the actual messages. Prior work has looked at strengthening ABE security by incorporating various notions of anonymity, and existing solutions can be broadly classified into two types. There are general purpose solutions which use exotic cryptographic primitives to provide full anonymity in ABE [26], [20], [36], [13]. However, the resulting schemes are very inefficient for practical use; e.g., they are orders of magnitude slower than state-of-the-art ABE without anonymity, as we show in our evaluations(§V). There are also application-specific solutions that sacrifice full anonymity to meet application-specific requirements in exchange for higher efficiency [30], [29]. A practical design that achieves both full anonymity and high efficiency is therefore needed. Our Contributions. In this work, we premier ABEAT − ABE that is Anonymous and Tunes out non-recipients − which enables lightweight anonymous group communication for a variety of situations involving dynamic groups. ABEAT is effective even when messages may not be delivered in sequence or in a timely manner, and end-to-end communication may be disrupted, such as during a disaster response. Specifically, ABEAT is an ABE-based group communication scheme with the following attractive features. • Seamless Group Management: ABEAT harnesses the “one-to-many” encryption capability of ABE to make group management completely trivial. ABEAT has no explicit group formation, using instead self-describing per-message groups. In other words, for each message the sender simply specifies the group of intended recipients during encryption. This stands in contrast to typical group communication systems where group management involves a non-trivial cost in terms of control plane messaging (whether it uses multicast or is server-based), especially when recipient anonymity is desired.

includes a novel recipient verification module so users can inexpensively tell whether a message is meant for them, without performing the expensive ABE decryption. This check is roughly 80x less costly than full decryption. • Dual authorities: Many modern group chat applications provide “end-to-end encryption” so that messages sent using the platform can only be decrypted by the intended receiver; in particular, the platform itself cannot decrypt and read the messages. One issue with using ABE for group messaging is that ABE systems produce a master secret key. This key is typically held by a central key authority who can use the master key to decrypt all messages. ABEAT instead splits the central key authority into two (or more) “dual key authorities”, each of which manages only a share of the master secret key. ABEAT provides end-to-end encryption as long as the authorities do not collude with one another. Moreover, ABEAT enables message auditing if and when the authorities cooperate to decrypt selected messages (e.g., for an audit of first responder operations). • Agnostic of Infrastructure: ABEAT can use any form of underlying message delivery, including broadcast. The cost of encryption for each party in ABEAT is not substantially higher than the standard one-to-one public key encryption. • Fine-Grained Access Control: As an ABE scheme, ABEAT is compatible with prior work in ABE-based group communication [48], [28], [44], [50]. In particular, ABEAT supports the efficient revocation procedure of [50]. • Working Dynamicity: ABEAT supports dynamic groups by utilizing publish/subscribe on namespaces (see Fig. 1 for an example). We discuss the details in III-A. Evaluation Our proposed anonymous ABE takes around 211.47ms to finish encryption for 100 attributes (recipients), while the decryption time is around 35.32ms. In contrast, HVE [21] takes 4480 ms for encryption and 68 ms for decryption. These experiments conservatively limited the total number of users (in the namespace) to 2000. Moreover, our efficient recipient verification module cuts decryption time for unintended recipients by roughly 80×.

• Recipient Anonymity: The most novel security feature of ABEAT is recipient anonymity, meaning that messages sent across the network in ABEAT do not reveal who they are intended for. Our solution is efficient and “application specific” (in the context of the previous discussion), taking advantage of the fact that in our setting, the attributes we wish to hide correspond to users who are registered into our system before communicating. By inserting a special key generation procedure into the registration process, we achieve anonymity for essentially the same cost as standard (non-anonymous) ABE.

II. BACKGROUND AND R ELATED W ORK Group Communication using Namespaces Users in a group communication environment may be organized into a namespace structured as a directed acyclic graph [22]. Each node in the graph has a name, and an edge between names indicates a heredity relationship (Fig. 1). The use of namespaces (whether as a strict tree or a more general graph) has been adopted in numerous domains (Domain Name System (DNS) [1], Information Centric Networks (ICN) [54], [22] etc.). Using a namespace framework naturally synchronizes dynamic group creation (e.g., when a team of first responders is ‘dispatched’ to an emergency [22]) and other changes across the system by publishing the updated namespace to all subscribers.

• Recipient Verification: One unintended side effect of introducing recipient anonymity, is that users cannot tell whether a particular message is intended for them, other than by attempting decryption. Obviously, requiring every user to decrypt every message (whether that user is a recipient of the message or not) would constitute a massive waste of system resources, and would be untenable. Instead, ABEAT

Dynamicity in group communication: The requirement that users interface with ABE via the namespace graph recognizes

2

Fig. 1: A Namespace Graph for First Responders

Fig. 2: KP-ABE Group Communication utilizing Namespace

the varying degrees of “dynamic” changes that occur in the system that may impact the ABE scheme. • Changes to the Set of Intended Recipients: When a group of communicating users need to add a user to their group, this is convenient, as every message in our system specifies its own set of intended recipients. A sender simply adds the user to the list of intended recipients of each new message.

authorities [14], [27], [40], [41]. In contrast, ABEAT splits each receiver’s decryption key between two authorities, so neither can generate a complete key alone. ABE-Based Group Communication Previous studies have applied ABE to secure group communication [16], [45], [51], [25], [39], [50]. However, some do not provide recipient anonymity [16], [45], [50], while others require costly cryptographic operations [51], an additional trusted intermediary [25], or restricted access policies [39]. In contrast, ABEAT combines a lightweight PKE-based method for anonymity and a graph-based namespace for flexible group management.

• Changes to the Set of Users Subscribing to a Name: Another type of change occurs when a user subscribes to a new name. The user simply receives the secret key from the key authorities for that corresponding name the user subscribes to. The user can then decrypt all messages addressed to that name. No other party needs to be involved.

Other Solutions for Secure Group Communication NonABE Secure group messaging (SGM) and continuous group key agreement (CGKA) protocols, including MLS [10], [6], [5], use TreeKEM [37], [19], [11] to manage group members. However, maintaining a consistent tree requires ordered and timely delivery of control updates, making these protocols less suitable for disruption-prone environments.

• Changes to the Namespace Graph: When the namespace is modified, e.g., when a new name hierarchy is formed (e.g., when a new incident response group of first responders is created for a particular disaster), then the namespace needs to be updated for all users. This enables potential senders (any user) to send to a group identified by the new name (and all the names below that subtree with the new name as the root). Impact on key generation and distribution is controlled and limited. Only those subscribers in the subtree rooted at the node that changes in the namespace will need to receive new/additional keys, as can be expected. No other subscribers or senders require key updates.

III. P RELIMINARIES FOR ABEAT A. Our Model Network Layer’s role in ABEAT Let N denote the set of names in the namespace (i.e., the vertices of the namespace graph). Messages in our group communication system are addressed to a set P ⊂ N of intended recipients. We use attribute-based encryption to ensure message confidentiality. So our system delivers ciphertexts to the intended recipients in P , who recover the message via decryption. We intend ABEAT to be anonymous, namely to hide the set P , even from an adversary who is monitoring the network traffic. For this purpose, we intend that messages be delivered to a much larger set of receivers Q ⊂ N , even though only the intended recipients in P ⊂ Q will possess the keys necessary to decrypt. Q serves to obscure P and prevent revealing the intended recipients to anyone monitoring network traffic. Note that the size of Q represents a trade-off between anonymity and system efficiency. One extreme would be to let Q = N (i.e., broadcast every ciphertext to all users), though this is likely to be inappropriate in many settings (e.g., if there are millions of users) as it is too wasteful. On the other hand, setting Q = P does not introduce system overhead but, of course, completely reveals the intended recipients to anyone monitoring the network. Thus, P ⊊ Q ⊊ N would typically be the case, if the network used some form of multicast

Namespace Deployment During Disasters. Our earlier studies have explored the deployment of namespaces for publish/subscribe-based group communication [22], [38], [15], [23], [50]. A higher-level authority can deploy and manage a shared namespace for first responders across different departments. Devices can then synchronize namespace updates using the regional approach in [23]. A. Related work Improvements to ABE Several recent works have made advances to efficient ABE implemented in bilinear groups [4], [18], [7]. Other works focus on adding the guarantee of anonymity to ABE [20], [53], [49], [30], [32], [26] for various applications. These schemes either do not provide any anonymity [4], [18], [7], only partially hide the attributes [30], [32], [53], or incur high performance costs [49], [20], [26]. Multi-Authority ABE Multi-authority ABE limits singleauthority compromise by assigning attribute subsets to separate

3

(e.g., IP multicast or overlay multicast). This is a common scenario used for secure multiparty communication [8], [43], [46], where messages intended for selected recipients are encrypted within a larger set of receivers to whom the message is delivered. Our intention is to decouple the communication mechanism at the network layer (e.g., broadcast, multicast, multiple overlays, or even unicast) from how confidentiality is achieved using ABE in this group setting. We discuss various choices for |Q| compared to |P | in Section V. Finally, we mention here the importance of efficient recipient verification. Since setting |Q| to be large enables recipient anonymity, an extremely important element of our system is the ability of receivers in Q to efficiently check whether they are an intended recipient in P or not. A receiver would only perform the expensive ABE decryption if they are in P . Without this, the total computation of our system would be dominated by unintended recipients trying and failing to decrypt messages that are not addressed to them. Threat and Security Model for ABEAT Our target adversary is one who is able to intercept the network traffic in our system (possibly by sniffing, gaining access to network links, routers or switches) and seeks to identify the intended recipients of a message. Our goal is to hide the identities of the intended recipients from such an adversary. Naturally, we also require message confidentiality, which is inherently provided by ABE. We also consider another type of attack where the master key is leaked. Our dual key authority approach, splitting the single authority into two (or more), achieves security even when the master secret key of one of the authorities is leaked. Our primary goal is to provide recipient anonymity. We acknowledge that a complete group communication solution should also address sender anonymity and message authenticity. Existing techniques for anonymizing the sender (e.g., onion routing [17]) and ensuring message authenticity (e.g., digital signatures [33]) can be readily integrated with our approach. Our work builds on top of the efficient FABEO encryption scheme [16], where security is proved in the generic group model (GGM). We inherit these assumptions and focus on confidentiality and anonymity, excluding message blocking, in-transit modification, and denial-of-service attacks. B. Group Communication using ABE without Anonymity

This syntax is standard for the “key-policy” variant of ABE (KP-ABE). We also remind the reader that the key generation procedure for KP-ABE is handled by a central key-authority who takes an access structure A as input, and (using the master secret key) outputs a secret key skA for A. Decryption allows anyone with a skA to recover msg from (S, ABE.ct) when A(S) = 1 holds. Suppose Alice wishes to send a message to a set P ⊂ N of intended recipients in the namespace, she can simply have the attribute set S contain the names in P , and then can publish

In this subsection, we describe a scheme that uses ABE to build secure group communication without anonymity, as the simplest building block (shown in Fig. 2). It demonstrates syntactically how ABE connects with the namespace graph for the purposes of achieving group communication. For the remainder of this section, we let ABE.Enc denote the encryption procedure of an ABE scheme, and so it takes/gives:

• Payload anonymity: Cryptographic payload ABE.ct must not leak information enabling an adversary to recover S. Payload anonymity has been addressed in previous work like [30]. In later sections, we will discuss how we extend this scheme to support dual authorities and other desirable features. In this section, we give an overview of our approach for achieving attribute anonymity. ABEAT’s key idea is to use standard (or vanilla) encryption to encrypt each attribute in S. Specifically, we assume every name p ∈ N is associated with some key pair (pkp , skp ) of a vanilla encryption scheme, where the public key pkp is known to all users in the system, while the secret key skp is known only to the users who subscribe to p. With this setup, we modify the previous scheme by having Alice publish (B, ABE.ct),

(S, ABE.ct) ∼ ABE.Enc(mpk, S, msg). Any user in the system who subscribes to a name p ∈ N will hold a secret key skAp for the access structure Ap that takes a set S ⊂ N (the attribute should be names in the namespace) as input and outputs 1 if p ∈ S, and 0 if not. So in this way, any user subscribing to some p ∈ P will be able to decrypt Alice’s message. See Fig. 2 for a visual description. Fine-Grained Access Control of ABE. In this scheme, ABE is used as a means to conveniently interface with the namespace graph. This alone does not warrant the use of ABE, as other crypto primitives (e.g., hierarchical identity based encryption) can be used for this purpose. However, the fine-grained access control afforded by ABE allows implementing additional features. For example, prior work [50] has implemented an ABE-based “timeout-based” revocation procedure, by which compromised or deprecated users can be unsubscribed from a name at the end of a time period. Our final scheme is compatible with this, and in Section V we measure the cost of implementing this useful feature. C. Adding Recipient Anonymity for ABE-based Group Communication We now introduce recipient anonymity for ABE’s group communication by encrypting the attributes. Two conditions on the ciphertext pair (S, ABE.ct) have to be met to be able to provide recipient anonymity: • Attribute anonymity: The attribute set S must remain hidden from the adversary, since the attributes in S are names of the intended recipients when ABE is used for secure group communication.

Input: a tuple (mpk, S, msg), where mpk is the master public key, S is a set of attributes, and msg is a message; Output: a pair (S, ABE.ct), where S is the attribute set and ABE.ct is the remainder of the ABE ciphertext which we will call the cryptographic payload. 1 1 This is consistent with the terminology in [30].

4

(a) Sender Flow during Encryption

(b) Recipient (both Intended and Unintended) Flow during Decryption

Fig. 3: Example of Encryption and Decryption in ABEAT: Attribute set is encypted in the vanilla encryption block separately from the ciphertext; Tags help the intended recipient to find the correct vanilla encryption block to recover the attribute set

secret key (msk (1) and msk (2) ). As a result, the setup function is executed jointly by both authorities. They first collaborate to generate the shared parameters (e.g., public parameters and the public/secret key pairs for each name), and then each authority generates its respective share of the 1 in the figure). master secret key (⃝

where B is a collection of vanilla ciphertexts which we call the vanilla encryption block with tags for intended recipients (or just vanilla encryption block, for short), and ABE.ct is the cryptographic payload that achieve payload anonymity (confidentiality). This is shown in Fig. 3. The important things about the vanilla block are 1) the intended recipients need to be able to recover the attribute set S, to use in decrypting ABE.ct; and 2) other parties (unintended recipients or external adversaries) cannot learn who the intended recipients are. Note,  some nuance is required here. For example, setting B = (p, ctp ) p∈P where for all p ∈ P (intended recipients), ctp ∼ PKE.Enc(pkp , S), so that each user subscribing to p ∈ P can use skp to decrypt ctp and recover S. Note that while the ciphertexts {ctp }p∈P are indeed hiding S (hence P ), any party who sees B learns who the intended recipients are by simply reading them off the indices. Our solution is to set B =  (tp , ctp ) p∈P , where the tp are cryptographically generated “tags”. At a high level, any user subscribed to p can, using the secret key skp , compute tp and find their ciphertext ctp ; while tp appears random to anyone who does not have skp .

• KeyGen This function is used for generating decryption keys for subscribers. Since ABEAT splits key authorities, each key authority (KA) runs this function independently with its part of the master secret key (msk (1) or msk (2) ) (1) (2) to generate a partial decryption key (skA and skA ). Also, the KAs must distribute the secret key of each subscribed name (skp ) to the corresponding subscriber for use in the vanilla encryption block. All the partial decryption keys and the secret key of each subscribed name are then transferred to the subscriber, and the subscriber combines them to have 2 in the figure). the decryption key (sk) (⃝ • Enc This function is used for encryption when the sender transmits messages. It represents the core component of our design, incorporating the vanilla encryption block. The sender takes the public keys of the target recipient names ({pkp p∈P ) as input to construct the vanilla encryption block (B). This block hides the attribute set (S), thereby providing attribute anonymity. In addition, the “tag” embedded in the vanilla encryption block enables fast recipient verification, allowing unintended recipients to quickly determine that they are not the intended targets, without incurring further decryption cost. To ensure payload anonymity and message confidentiality, a KP-ABE ciphertext is also generated. Since standard KP-ABE operates under a single authority and provides only message confidentiality (but not payload anonymity), we design a new scheme, KP-ABE with split key authorities and payload anonymity. The resulting KP-ABE ciphertext (ctP L ) is combined with the vanilla encryption block to form the final ciphertext (ct), which 3 in the figure). is then delivered to the recipients (⃝

IV. O UR M AIN C ONTRIBUTION : ABEAT A. Overview of ABEAT Fig 4 shows how the key authorities, sender, and recipients execute the algorithms of ABEAT. • Setup This function serves as the global setup for ABEAT and is executed once during system initialization. Its purpose is to generate the public parameters used by subsequent functions, as well as several important global keys: (1) the master public key (mpk), which is publicly available and used for encryption; (2) the master secret key (msk), which is used to generate decryption keys and must remain confidential; and (3) a public/secret key pair for each name in the namespace ({(pkp , skp )}p∈N ), which are used in the vanilla encryption block. The public keys are publicly accessible, while the corresponding secret keys are distributed only to subscribers of each name. A key distinction from standard ABE is that ABEAT employs split key authorities to mitigate the risk of master secret key leakage. Specifically, each authority independently generates a share of the master

• Dec Upon receiving the ciphertext, each recipient executes Dec to recover the original message. The Dec function first performs recipient verification using the secret key of the

5

• VEB.KeyGen(N ): outputs  (pkp , skp ) p∈N .

a

family

of

key

pairs

• VEB.Enc P, {pkp }p∈P , msg : outputs B; here P ⊂ N is a subset. • VEB.Dec(skp , B): outputs a message msg′ , or the failure symbol ⊥. Fig. 6: Vanilla Encryption Block Syntax • Building Blocks: · a scheme for generating a block of vanilla encryptions
VEB = VEB.KeyGen, VEB.Enc, VEB.Dec ; · a KP-ABE scheme with split key-authority and payload anonymity

Fig. 4: Process for ABEAT Algorithms

subscribed name (skp ) on the vanilla encryption block to determine whether the recipient is an intended recipient. If not, the process terminates early to avoid unnecessary decryption overhead. Otherwise, the recipient decrypts the vanilla encryption block to obtain the attribute set and then 4 in the figure). decrypt the KP-ABE ciphertext (⃝ As stated before, ABEAT is built on top of two key building blocks: the KP-ABE scheme with split key-authority and payload anonymity, and the vanilla encryption block scheme. First, we describe the building block syntax and how it constructs ABEAT. We then detail the implementation of the building blocks and provide the security proof. B. Construction of ABEAT

ABE = ABE.Setup, {ABE.KeyGen

}j=1,2 , ABE.Enc, ABE.Dec .

• Setup(N ):
· draw mpk, msk(1) , msk(2) ∼ ABE.Setup(1λ );  · draw (pkp , skp ) p∈N ∼ VEB.KeyGen(N ); 
· output mpk, msk(1) , msk(2) , (pkp , skp ) p∈N . • KeyGen(j) (mpk, msk(j) , A): for j = 1, 2 (j)

· draw and output skA ∼ ABE.KeyGen(j) (mpk, msk(j) , A). • Enc(mpk, S, {pkp }p∈P , msg): · draw (S, ctPL ) ∼ ABE.Enc(mpk, S, msg);
· draw B ∼ VEB.Enc {pkp }p∈P , S ;

KP-ABE with Split Key-Authority and Payload Anonymity. We say that the 5 component algorithms

· output ct = (B, ctPL ).

(Setup, KeyGen(1) , KeyGen(2) , Enc, Dec)

(1)

(2)

• Dec(skA , skA , skp , ct): · parse ct = (B, ctP L ); · compute S ′ = VEB.Dec(skp , B); if this decryption fails, output the failure symbol ⊥ and halt;

have the syntax of a key-policy ABE scheme with the split key authorities (KA) if they satisfy the input/output of Fig. 5. • ABE.Setup(1λ ): outputs keys (mpk, msk(1) , msk(2) )

(1)

(2)

· otherwise output msg′ = ABE.Dec(skA , skA , S ′ , ctPL ).

· Setup can also optionally output public information which will be used implicitly by the remaining algorithms.

Fig. 7: Overall construction of ABEAT

• ABE.KeyGen(j) (mpk, msk(j) , A) for j = 1, 2 : outputs (j) skA .

C. Constructing the Building Blocks KP-ABE with Split Key-Authority and Payload Anonymity. We build on top of the KP-ABE construction of [18], using ideas similar to those in [30] for achieving payload anonymity. Roughly speaking, in [30], payload anonymity is achieved by splitting the sender’s encryption randomness into two parts, essentially adding an extra degree of freedom which eliminates certain “anonymity attacks” which are possible on [18]. Our main idea is to split not just the sender’s encryption randomness but the entire key authority. The result is two independent authorities who each control a share of the master secret key. In addition to payload anonymity, splitting of the authorities alleviates the risk that the master secret key is leaked (since both shares would now have to be leaked). In the KP-ABE constructions of [18] and [30], a secret value (α) is used to provide message confidentiality which must remain confidential. In ABEAT, we require both authorities to collaboratively generate this secret at the beginning of the setup phase. The details of our construction is in Fig. 8.

• ABE.Enc(mpk, S, msg): outputs ct. (1) (2) • ABE.Dec(skA , skA , ct): outputs msg′

(j)

or the failure sym-

bol ⊥.

Fig. 5: Syntax of Key-Policy ABE w/Split KA (A is access structure)

Block of Vanilla Encryptions. We now define our second building block: a scheme for generating a vanilla encryption block. This is the gadget we use for converting an ABE with payload anonymity into an ABE with anonymity for group messaging which supports efficient recipient verification. The syntax for the vanilla encryption block scheme is in Fig. 6. Construction for ABEAT We now give the construction for ABEAT on top of the two key building blocks in Fig. 7. Specifically, the Setup algorithm invokes ABE.Setup and VEB.KeyGen. The KeyGen algorithm calls ABE.KeyGen. The Enc algorithm invokes ABE.Enc and VEB.Enc to produce the ciphertext. The Dec algorithm runs VEB.Dec and ABE.Dec to decrypt the ciphertext. The detailed construction of the building blocks is described next.

6

• KeyGen(N ): For each p ∈ N , draw a random exponent αp
and set (pkp , skp ) = g αp , αp .
• Enc P, {pkp }p∈P , msg : Parse the public keys pkp = g αp for p ∈ P . Choose random exponents β, γ and output    B = g β , g γ , (g αp β , g αp γ · msg) p∈P .

• Public Parameters : A pairing group (G1 , G2 , GT , g1 , g2 , e). • Setup(1λ ): A secret α ∼ Zp is drawn jointly by both key authorities. Specifically, authority j will α generate αj , and send g1 j to the other party. Both α authority will then calculate g1α = Πj g1 j . Additionally, two pairs of secrets β1 , β2 ∼ Zp , δ1 , δ2 ∼ Zp are drawn independently. Both βj , δj are drawn by the key authority j. Output is:
− mpk = g2β1 , g2β2 , g2δ1 , g2δ2 , g1α , e(g1 , g2 )α ;

• Dec(skp , B): Parse skp = αp . Retrieve g β and g γ from B, and compute g αp β and g αp γ . Find in B the pair whose first coordinate is g αp β , and let h be the second coordinate of this pair (if there is no such pair, output the failure symbol ⊥). Output h/g αp γ . Fig. 9: Generating the Vanilla Encryption Block

− msk(j) = (βj , δj ) for j = 1, 2. • KeyGen(j) (mpk, msk(j) , A): Parse
mpk = g2β1 , g2β2 , g2δ1 , g2δ2 , g1α , e(g1 , g2 )α and msk(j) = (βj , δj ) and let (M, π) be the monotone 2 span program computing A. Draw rj ∼ Zp , vj ∼ Zn .
p (j) (j) (j) (j) Output skA = {sk1,i }i∈[n1 ] , sk2 , {sk3,i }i∈[n1 ] : (j)

M ·α·vj /βj

− sk1,i = g1 i

· H(π(i))rj /βj , for j = 1, 2;

r (j) − sk2 = g2j , for j = 1, 2. (j) − sk3,i = H(π(i))rj /δj , for j = 1, 2.

Fig. 10: Timeout-Based Revocation, for FF1 as an example

D. Security for ABEAT

• Enc(mpk, S, msg): Parse
mpk = g2β1 , g2β2 , g2δ1 , g2δ2 , e(g1 , g2 )α . Draw s1 , s2 ∼ Zp and let s = s1 + s2 . Output is (S, ctPL ), where   (2) (1) (2) (1) ctPL = ct1,u u∈S , ct2 , ct2 , ct3 , ct3 , ct4 , where − ct1,u = H(u)s ; (j)

In this section, we discuss the security of ABEAT, which is based on its two main building blocks, the vanilla encryption and KP-ABE with split key-authority and payload anonymity. We provide a high-level overview of the formal proof, with the Appendix providing the detailed proofs.

β s

Security of the Vanilla Encryption Block Security of our vanilla encryption block component holds assuming the Decisional Diffie–Hellman (DDH) assumption [12]. Roughly speaking, the DDH assumption states that an adversary cannot distinguish a triple (g x , g y , g xy ) from a uniformly random triple, unless it knows x or y. So, nobody other than the sender (who knows x) and the receiver (who knows y) can distinguish the tag g xy from a random string.

− ct2 = g2 j j for j = 1, 2; δ s (j) − ct3 = g2j 3−j

for j = 1, 2;

− ct4 = e(g1 , g2 )αs · msg. (1)

(2)

• Dec(skA , skA , S, ct): Parse (j) skA =

(j) (j) (j) {sk1,i }i∈[n1 ] , sk2 , {sk3,i }i∈[n1 ] , for

j = 1, 2 and (2) (1) (2) (1) ct = {ct1,u }u∈S , ct2 , ct2 , ct3 , ct3 , ct4 ). If S satisfies P (M, π) then find the scalars {γi }i∈IS such that i γi Mi = (1, 0, . . . , 0) and compute: (j)
(j) (j)
γi Y Y e (sk(j) e (sk3,i )γi , ct3 1,i ) , ct2 val := . (j)
e (ct1,π(i) )γi , sk2 i∈IS j=1,2

Security of KP-ABE with Split Key-Authority and Payload Anonymity The security proof of our ABE building block follows the security proof in [18], with minor modifications because of our splitting of the key-authority. Specifically, our proof uses the symbolic security framework of prior work [18], [3], [7] within the generic group model (GGM) [42]. Security is argued by expressing the data which is available to the adversary (including public keys, auxiliary secret keys and ciphertexts) as well as the data desired by the adversary (target secret keys) as sets of linear equations, and by showing that the linear span of the equations which the adversary has is disjoint from the linear span of the equations he desires.

Output ct4 /val. Fig. 8: KP-ABE with Split KA and PA

The Block of Vanilla Encryptions. The Vanilla Encryption Block can be implemented using a standard PKE scheme. Each block is generated for a specific intended recipient and encrypts the corresponding attribute set under that recipient’s public key. In addition to the encrypted attribute set, each block also contains a tag. This tag enables the intended recipient to efficiently identify which block is meant for them, while not revealing this information to unintended recipients.

Security of ABEAT The security proof of ABEAT proceeds by reduction to the security of the two building blocks. Specifically, we show that an adversary who is able to break the security of ABEAT, must also be able to break the security of either the vanilla encryption block or the KPABE with split authority and payload anonymity. This is done using a hybrid argument where a modified version of

Our construction builds on classical Diffie–Hellman key agreement, where Alice and Bob derive a shared encryption secret. We derive two shared-secret values, one for tagging and one for message encryption, as shown in Fig. 9.

7

ABEAT is considered which includes a “dummy” vanilla block containing random strings, rather than vanilla encryptions of the intended recipients and tags. We then show two things: 1) any adversary that can distinguish this hybrid version of ABEAT from the original must be able to directly break the security of the vanilla block; 2) any adversary that can break security of this hybrid version must be able to break security of the KP-ABE with split authority and payload anonymity. Since we already proved that the adversary cannot break the security of the vanilla block and the security of the KP-ABE with split authority and payload anonymity, ABEAT is secure.

derive a symmetric payload-encryption key. All schemes are evaluated on the same 2.1 GHz server, with results averaged over five runs. B. Cost of Providing Anonymity with ABE We first understand the cost of supporting anonymity in ABEAT compared to alternative approaches, including (1) HVE [21]; (2) KP-ABE with Split Key-Authority and Payload Anonymity. (as described in Section IV-B, we call it Payload Anonymous KP-ABE for short), but with the attribute set in the clear; (3) FABEO [18]; and (4) A simple concatenation of PKE encryption for all intended recipients. Both PKE and FABEO do not provide anonymity. PKE also does not provide fine-grained access control. Payload Anonymous KPABE provides only weaker anonymity as it does not hide the attribute set, which is in the clear. HVE provides full anonymity, but the encryption overhead depends on the size of the entire namespace (all possible receivers of a message). Note that the performance of all schemes except HVE is independent of namespace size. To conservatively estimate the relative encryption cost benefit of ABEAT, we set the HVE namespace size to be only twice the intended-recipient set. Encryption Fig. 11 shows the encryption cost for ABEAT. PKE, without anonymity is certainly the fastest, with FABEO being slightly slower than that. Payload Anonymous KPABE is also slightly faster than ABEAT, but it also does not provide full anonymity (it does not hide the attribute set). ABEAT provides a higher anonymity level, and takes more time for encryption. The proportionate increase in latency for encryption with ABEAT compared to the other non-anonymous approaches reduces slightly as we increase the number of intended recipients. HVE is by far the slowest. Even when we limit the namespace to only be twice as large as the intended recipient set, HVE’s overhead grows very rapidly compared to ABEAT. Even with a namespace that contains just 2000 names, HVE would take around 4480 ms for encryption (with 100 intended recipients), while ABEAT would take 211.47ms since the cost of ABEAT does not depend on namespace size. Overall, adding anonymity with ABEAT incurs about 88% more overhead compared to FABEO. Decryption Table I compares the decryption cost for intended and unintended recipients across different approaches. For intended recipients, ABEAT incurs about 2× the decryption cost of Payload Anonymous KP-ABE. FABEO, which provides neither anonymity nor dual authorities, is faster, while PKE, also without anonymity, remains the fastest. HVE provides anonymity but not dual authorities, and has the highest cost. For unintended recipients, FABEO and Payload Anonymous KP-ABE provide no or weaker anonymity and take about 0.8 ms to reject a ciphertext.In contrast, PKE requires trying every recipient ciphertext, taking 38.8 ms for 100 intended recipients, while HVE gives intended and unintended recipients comparable costs. ABEAT makes unintended-recipient decryption about 80× faster than intended-recipient decryption, over 90× faster than HVE, and 40% faster than non-anonymous FABEO, approaching the cost of non-anonymous schemes.

Security Properties of ABEAT We now summarize the system-level security properties and limitations of ABEAT: • Identity leakage through the receiver superset. An adversary observing the receiver superset Q may infer the intended recipient set P ⊆ Q through traffic or intersection analysis on repeated transmissions. While ABEAT cryptographically hides P within each Q, structural correlation across successive supersets can leak recipient identities. To mitigate this statistical leakage, the sender must construct Q with sufficient size and diversity, ensuring unintended recipients remain uncorrelated with P . • Leakage of the intended recipient-set size. Because the vanilla encryption block contains one entry for each intended recipient name, its length may reveal the number of intended recipient names, i.e., |P |. This leakage can be mitigated by padding the block with randomly generated dummy entries that are computationally indistinguishable from valid entries to an adversary who does not have the corresponding recipient secret keys. The sender may also use a fixed-size vanilla encryption block by adding dummy entries as needed. Consequently, equal-sized blocks prevent an adversary from inferring |P | from the block length. • Forward and backward secrecy. ABEAT adopts a timeoutbased revocation mechanism, as in [50]. As shown in Fig. 10, time is divided into slots, and each ciphertext and decryption key is bound to a specific slot. Thus, compromising a key exposes only messages from its corresponding slot, but not messages from earlier or later slots, thereby providing backward and forward secrecy respectively. We quantitatively evaluate the cost of this approach in V-D. • Confidentiality when an authority is compromised. ABEAT splits the master secret key between two independent authorities, so compromising either authority alone does not allow payload decryption. The authorities must collude to allow for recovery of the protected messages, while recipient anonymity is provided separately by the vanilla encryption block and payload-anonymous KP-ABE. V. E VALUATION A. Implementation details We implement ABEAT using Charm [24], with MNT224 pairing groups [9] and prime192v1 elliptic-curve PKE [34]. For key encapsulation, a random group element is used to

8

Fig. 11: Encryption Time Comparison

Fig. 12: Ciphertext Length Comparison Fig. 13: ABEAT Encryption: w & w/o Tag

TABLE I: Decryption Time (ms) & Encryption CPU Cycles (106 ) Scheme ABEAT HVE P-A-KP-ABE FABEO PKE

recipient intended unintended 35.32 0.42 40.69 40.67 17.77 0.82 12.97 0.84 38.8 0.43 100recipients

ABE payload decryption, which takes 34.31 ms; and the search time for locating the correct tag, denoted as ST in the table. The search time is typically negligible. For large vanilla encryption blocks, we use binary search to reduce it, as shown in Appendix B-C. For an unintended recipient with a tag, only recipient verification, which is comparable to a single PKE decryption, is required. Without tags, both intended and unintended recipients incur substantially higher overhead. Suppose the PKE ciphertext is stored in the t-th entry. An intended recipient must perform t PKE decryptions, each taking about 0.42 ms, before running a full KP-ABE decryption, which takes 17.6 ms, to recover the message. For an unintended recipient, the cost depends on the vanilla encryption block size M . Since none of the PKE-encrypted attribute sets can be decrypted successfully, the recipient must try all entries, resulting in a cost of M PKE decryptions.

encrypt cycles (#intended) 20 50 100 140.91 253.31 439.46 193.58 477.29 946.83 78.15 143.93 254.31 62.36 127.67 238.16 32.19

78.99

157.6

Ciphertext Length Fig. 12 shows the total ciphertext length resulting from each approach. We use the serialization method provided in Charm to convert the ciphertext to bytes, to estimate length. Non-anonymous PKE group communication has the largest ciphertext length, because the message payload has to be replicated for each recipient when using PKE to send to multiple recipients. HVE and ABEAT have similar lengths, while the ciphertext length of FABEO and Payload Anonymous KP-ABE [30] is smaller.

D. ABEAT w/ Access Control and Revocation CPU cycles The utilization of the encryption CPU is similar to the encryption processing time as shown in Table I. HVE takes the most cycles during encryption. It takes around 946M cycles for 100 recipients. ABEAT is the next. For 100 recipients, the encryption process requires approximately 410M CPU cycles while the payload anonymous KP-ABE (P-A-KP-ABE) requires 254M cycles. FABEO KP-ABE is next, requiring 238M cycles. In contrast, PKE group communication requires the fewest CPU cycles, with 157M cycles for 100 recipients.

We implement the timeout-based revocation in [50] by adding one timestamp attribute. Our evaluation result shows it adds negligible overhead to encryption, as seen in Table III, even supporting 100 intended recipients with the timestamp. The decryption cost for adding fine-grained access control is shown in Table III. Adding a single fine-grained access control attribute adds just around 1% overhead to ABEAT. TABLE II: ABEAT Decryption: w & w/o Tag (ST : searching time; t: # of probes; M : size of vanilla encryption block) (ms)

C. Performance of ABEAT with Tags

Scheme ABEAT w/ Tag ABEAT w/t Tag

The Diffie-Hellman based tags could dramatically reduce the decryption processing time at recipients. However, ABEAT adds encryption processing at the sender. To quantitatively measure these overheads of ABEAT, we compare it with an approach that only contains the PKE ciphertext in the vanilla encryption block. Note that the decryption savings apply to (potentially) a very large number of unintended recipients, while the encryption overhead is only for a single sender.

intended recipient 0.77 + 34.31 + ST t × 0.42 + 34.31

unintended recipient 0.42 M × 0.42

TABLE III: ABEAT w/ Fine-grained Access Control (ms) Scheme ABEAT ABEAT w/ Access Control

Encryption Overhead: Fig. 13 shows the encryption time for ABEAT with and without the use of the tag. For adding a tag, ABEAT incurs a slightly higher encryption time. The overhead added for encryption varies from 10-30ms based on the number of intended recipients. The overhead added for 20 recipients is 11%, and is about 20% for 100 recipients.

encryption (# intended rec.) 20 50 100 67.17 120.37 209.94

recipient intended unintended 35.17 0.42

68.31

35.52

121.81

210.71

0.39

E. Key Generation Cost in ABEAT We now analyze the key generation time in ABEAT. Key generation is involved in three operations: namespace initialization, adding a new name, and subscribing to a name. Table IV reports the cost of each operation. During initialization, the two KAs generate their master public/private key pairs, taking ∼ 46.50 ms in total. In addition, each initial name in the namespace requires one PKE key pair, which takes 0.33 ms to generate. Thus, for N initial names, the total namespace initialization cost is N × 0.33 + 46.50 ms. Adding a new name

Decryption Savings: Table II shows the cost of decryption for ABEAT with and without the tag. For an intended recipient with a tag, the decryption cost has three components: recipient verification and PKE decryption, which together take 0.77 ms;

9

Fig. 14: ABEAT vs. MLS: Group Setup & Enc

(a) Encryption Time.

(b) Ciphertext Length.

Fig. 15: Comparison between ABEAT and PKE TABLE V: Total Cost for Large Scale Evaluation (ms)

only requires generating one PKE key pair, taking 0.33 ms. When a subscriber subscribes to a name, both authorities generate an ABE decryption key. For one attribute, generating the two partial ABE decryption keys takes 24.35 ms in total.

Setting

Scheme

sender

2× Intended

TABLE IV: Cost (time) for Key Generation (ms)

Broadcast

ABEAT Baseline ABEAT Baseline

566.41 275.65 564.23 272.97

Scheme ABEAT

initialization N × 0.33 + 46.50

adding a name 0.33

subscribing 24.35

intended recipients (total cost) 8382.85 4211.68 8370.85 4210.99

unintended recipients (total cost) 371.80 8418.09 899.04 19649.00

node, we expand toward the leaves to form a recipient group, resulting in 236 intended recipients. For unintended recipients, we randomly select 472 nodes (twice the number of intended recipients) from the graph. We compare ABEAT to a baseline anonymous ABE approach that is a combination of a mechanism using bloom filters as described in [20] and the payload anonymous KP-ABE we described previously [30]. Table V the overall results. Although the total cost for the sender is higher with ABEAT, the cost for all unintended recipients (summed together) is dramatically lower, by about a factor of 20x. The total computation for all intended recipients together is around 2x the bloom filter/payload anonymous KP-ABE baseline. However, ABEAT provides the dual KA feature that the baseline approach does not have. Thus, when we consider the overall system overhead, ABEAT is much lower. We also test the same large scale experiment using broadcast in the underlying network layer. Here, all nodes in the network that are not intended recipients will be considered unintended recipients. Since set size increases for broadcast, the cost for the baseline approach increases considerably, whereas ABEAT still maintains the low overhead for unintended recipients.

F. ABEAT vs. PKE: Is ABE really necessary? A common concern with ABE is its overhead. However, using only PKE introduces significant key management complexity. In a PKE-only design, all members of a relatively static group must agree on a common group key pair, which also raises the traditional problem of group key revocation. In contrast, ABE allows each ABEAT message to define a distinct, dynamically formed group based on its attributes. Although ABEAT still requires each recipient to hold a PKE key pair, this key pair is managed through the namespace. Recipients obtain it when subscribing to a name, avoiding complex key management. We also quantify the cost of anonymity. Fig. 15 compares ABEAT with anonymous PKE (A-PKE), where A-PKE uses the same vanilla encryption block as ABEAT. The encryption time of ABEAT is about 1.4× that of A-PKE for 100 recipients. However, as shown in Fig. 14b, the ciphertext length of ABEAT is about 66% shorter than that of A-PKE. Given the key management complexity and longer ciphertexts of A-PKE, we argue that building ABEAT on ABE is a better choice for anonymous group communication than using PKE alone. G. Comparison with Message Level Security

I. Overall Solution Evaluation

MLS [10] targets commercial group messaging over stable networks and does not provide recipient anonymity. We compare ABEAT with an open-source implementation of MLS, OpenMLS [35], under a highly dynamic setting in which group membership changes for every message. MLS therefore performs group formation before each transmission, whereas ABEAT requires no explicit group formation. In our experiment, all group members are hosted on the same machine, to eliminate network transmission delays for control messages during group formation. This setup obviously favors MLS. We measure the combined group-formation and encryption time in Fig. 14. Even without network delays, OpenMLS is over 200× slower than ABEAT for 50 members. System load remained well below CPU capacity, confirming that the difference results from protocol overhead rather than system overload. H. Large Scale Evaluation

This section evaluates the end-to-end performance of ABEAT when integrated into the name-based group messaging framework. Our experiments are conducted using the network simulator provided by POISE [2], with simulation settings comparable to those adopted in its original evaluation. The simulated environment includes multiple forwarding routers and end hosts serving as publishers and subscribers. For every published message, we extend the simulation to account for the corresponding encryption and decryption operations. The simulated network is based on the Rocketfuel 1221 Telstra topology [31]. For the naming structure, we construct a graph-based “Disaster Management” category namespace from the Wikipedia dataset [47]. The resulting hierarchy comprises 1,468 names distributed across six levels. Using the corresponding Wikipedia pages and files, we create a workload of 95,417 publications and shuffle their transmission order before running the simulation.

We generate a random namespace graph with 1337 nodes and select a random node as the recipient name. From this

10

POISE

1.0

KP-ABE

CP-ABE

ABEAT

[5] Joël Alwen et al. Continuous group key agreement with active security. In In TCC, 2020. [6] Joël Alwen et al. Modular design of secure group messaging protocols and the security of MLS. In In ACM CCS, 2021. [7] Miguel Ambrona et al. Attribute-based encryption in the generic group model: Automated proofs and new constructions. In Proceedings of the 2017 ACM SIGSAC CCS. [8] Fiat Amos et al. Broadcast encryption. In CRYPTO’93. Springer Berlin Heidelberg, 1994. [9] Miyaji Atsuko et al. New explicit conditions of elliptic curve traces for fr-reduction. IEICE transactions on fundamentals of electronics, communications and computer sciences, 84(5):1234–1243, 2001. [10] Richard Barnes et al. The messaging layer security (MLS) protocol. Technical report, 2023. [11] Karthikeyan Bhargavan et al. TreeKEM: asynchronous decentralized key management for large dynamic groups a protocol proposal for messaging layer security (MLS). PhD thesis, Inria Paris, 2018. [12] Dan Boneh. The decision diffie–hellman problem. In Proceedings of the Third Algorithmic Number Theory Symposium (ANTS III). [13] Jin Cancan et al. Fully secure hidden ciphertext policy attribute-based encryption with short ciphertext size. In the 6th ICCNS, 2016. [14] Melissa Chase. Multi-authority attribute based encryption. In TCC 2007, pages 515–534. Springer, 2007. [15] Jiachen Chen et al. CNS: content-oriented notification service for managing disasters. In Proceedings of the 3rd ACM Conference on Information-Centric Networking, 2016. [16] Ling Cheung, Joseph A Cooley, Roger Khazan, and Calvin Newport. Collusion-resistant group key management using attribute-based encryption. Group-Oriented Cryptographic Protocols, 23, 2007. [17] Roger Dingledine et al. Tor: The second-generation onion router. In USENIX security symposium, volume 4, pages 303–320, 2004. [18] Riepel Doreen et al. FABEO: Fast attribute-based encryption with optimal security. In Proceedings of the 2022 ACM SIGSAC CCS, 2022. [19] E. Rescorla. Subject: [MLS] TreeKEM: An alternative to ART. MLS mailing list, 2018. [20] Jialu Hao et al. Fine-grained data access control with attribute-hiding policy for cloud-based iot. Computer Networks, 153, 2019. [21] Vincenzo Iovino et al. Hidden-vector encryption with groups of prime order. In Pairing 2008, pages 75–88. Springer, 2008. [22] Mohammad Jahanian et al. Graph-based namespaces and load sharing for efficient information dissemination in disasters. In ICNP, 2019. [23] Mohammad Jahanian et al. CoNICE: Consensus in intermittentlyconnected environments by exploiting naming with application to emergency response. IEEE/ACM Transactions on Networking, 30(5):1926– 1939, 2022. [24] JHUISI. Charm: a framework for rapidly prototyping cryptosystems. https://github.com/JHUISI/charm. [accessed on May. 25, 2024]. [25] Apu Kapadia, Patrick P Tsang, and Sean W Smith. Attribute-based publishing with hidden credentials and hidden policies. In NDSS, volume 7, pages 179–192, 2007. [26] Jonathan Katz et al. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In EUROCRYPT 2008. [27] Allison Lewko et al. Decentralizing attribute-based encryption. In EUROCRYPT, pages 568–588. Springer, 2011. [28] Bing Li et al. An efficient and anonymous attribute-based group setup scheme. In GLOBECOM 2013, pages 861–866. IEEE, 2013. [29] Jingwei Liu et al. vFAC: Fine-grained access control with versatility for cloud storage. In (GLOBECOM), 2018. [30] Meng Long et al. FEASE: Fast and expressive asymmetric searchable encryption. In IACR Cryptol. ePrint Arch., 2024. [31] Ratul Mahajan, Neil Spring, David Wetherall, and Tom Anderson. Inferring link weights using end-to-end measurements. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, pages 231–236, 2002. [32] Long Meng et al. FABESA: fast (and anonymous) attribute-based encryption under standard assumption. IACR Cryptol. ePrint, 2024. [33] National Institute of Standards and Technology. Digital signature standard (DSS). FIPS PUB 186-4, 2013. Federal Information Processing Standards Publication. [34] National Institute of Standards and Technology. Digital signature standard (dss). Technical Report FIPS PUBS 186-4, U.S. Department of Commerce, 2013.

CDF

0.8 0.6 0.4 0.2 0.0

0.01

0.10

Notification Latency(s)

1.00

Fig. 16: Overall Solution Evaluation

Our primary metric is notification latency, defined as the total time spent delivering a publication and performing its associated encryption and decryption operations. Fig. 16 shows that incorporating these cryptographic operations increases the end-to-end notification latency. Without confidentiality and anonymity protection, POISE delivers 90% of publications within 0.02,s. At the same percentile, the KP-ABE and CPABE solutions require 0.05,s and 0.08,s, respectively, while ABEAT requires 0.1,s. Although the anonymity mechanisms introduce noticeable overhead relative to the network delay alone, the resulting latency remains acceptable for disseminating messages to first responders. VI. C ONCLUSION In this paper, we proposed ABEAT, an ABE-based system for confidential dynamic group communication in practical settings such as emergency response. ABEAT enables flexible group management by incorporating the namespace graph into the ABE setup. It also provides two key security guarantees through new cryptographic modules. First, ABEAT achieves recipient anonymity, preventing adversaries who monitor network traffic from identifying the intended recipients, by adding a block of standard vanilla encryptions to the ABE ciphertext. These vanilla ciphertexts are tagged to support efficient recipient verification, allowing users to cheaply check whether a message is intended for them before performing costly ABE decryption. Second, ABEAT reduces the risk of master-secretkey leakage by splitting the ABE key authority into two dual authorities. Our evaluation showed that ABEAT reduces computation time for unintended recipients by more than 90× compared to an anonymous scheme such as HVE, and by 40% compared to even the non-anonymous FABEO scheme. VII. ACKNOWLEDGEMENT This work was supported by NSF grants CNS-2434009 and CAREER-2441313. R EFERENCES [1] Domain names - concepts and facilities. RFC 1034, November 1987. [2] Networksimulator. https://github.com/SAIDProtocol/NetworkSimulator, 2018. GitHub repository, accessed March 6, 2026. [3] Shashank Agrawal et al. Simplifying design and analysis of complex predicate encryption schemes. In In proceedings of EUROCRYPT 2017. [4] Shashank Agrawal et al. FAME: Fast attribute-based message encryption. In In Proceedings of the 2017 CCS, 2017.

11

[35] OpenMLS Contributors. Openmls: A rust implementation of the messaging layer security (mls) protocol. https://github.com/openmls/openmls, 2023. Accessed: 2026-01-09. [36] Phuong et al. Hidden ciphertext policy attribute-based encryption under standard assumptions. IEEE TIFS, 11, 2015. [37] R. Barnes. Subject: [MLS] remove without double-join (in TreeKEM), 2018. [38] K. K. Ramakrishnan et al. Resilient communication for dynamic first responder teams in disaster management. IEEE Communications Magazine, 60(9):93–99, 2022. [39] Y Sreenivasa Rao and Ratna Dutta. Recipient anonymous ciphertextpolicy attribute based encryption. In International Conference on Information Systems Security, pages 329–344. Springer, 2013. [40] Doreen Riepel et al. Isabella: Improving structures of attribute-based encryption leveraging linear algebra. In Proceedings of the 2024 on CCS, pages 4628–4642, 2024. [41] Yannis Rouselakis et al. Practical constructions and new proof methods for large universe attribute-based encryption. In ACM CCS, pages 463– 474. ACM, 2013. [42] Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT ’97. [43] Agrawal Shweta et al. Optimal broadcast encryption from pairings and lwe. In EUROCRYPT. Springer International Publishing, 2020. [44] Dirk Thatmann et al. Applying attribute-based encryption on publish subscribe messaging patterns for the internet of things. In DSDIS 2015. [45] Patrick Traynor, Kevin RB Butler, William Enck, and Patrick D McDaniel. Realizing massive-scale conditional access systems through attribute-based cryptosystems. In NDSS, 2008. [46] Hoeteck Wee. Optimal broadcast encryption and CP-ABE from evasive lattice assumptions. In EUROCRYPT, 2022. [47] Wikipedia contributors. Category: Disaster management. https://en. wikipedia.org/wiki/Category:Disaster management, 2018. Online; accessed 21 May 2018. [48] Hu Xiong et al. Attribute-based privacy-preserving data sharing for dynamic groups in cloud computing. IEEE Syst. J., 2019. [49] Kan Yang et al. An efficient and fine-grained big data access control scheme with privacy-preserving policy. IEEE IoT Journal, 2016. [50] Hongmiao Yu et al. SAFE: Secure and flexible encryption for dynamic team communications in disaster management. In ICNP, 2023. [51] Shucheng Yu, Kui Ren, and Wenjing Lou. Attribute-based on-demand multicast group setup with membership anonymity. In Proceedings of the 4th international conference on Security and privacy in communication netowrks, pages 1–6, 2008. [52] Yingdi Yu et al. Schematizing trust in named data networking. In ICN ’15. [53] Leyou Zhang et al. Enhanced secure attribute-based dynamic data sharing scheme with efficient access policy hiding and policy updating for iomt. IEEE Internet of Things Journal, 2024. [54] Lixia Zhang et al. Named data networking. ACM SIGCOMM Computer Communication Review, 44(3):66–73, 2014.

12

c) The “Corrupt or Target” DDH Game. Our new security assumption is characterized by a security game between an adversary A and challenger C. Let n ∈ N be an integer parameter.

A PPENDIX A S ECURITY P ROOF A. Security of the Vanilla Encryption Block In this section we describe the corrupt or target DDH assumption and use it to prove security of our vanilla encryption block scheme. We first define the security game as showed in Fig. 17.  1. Setup: C draws (pkp , skp ) p∈N ∼ KeyGen(N ) and sends all public keys to A: {pkp }p∈N . Additionally, C chooses a random bit b ∼ {0, 1}.

• C draws random exponents x1 , . . . , xn ∼ $, sends (g x1 , . . . , g xn ) to A, and chooses a random bit b ∼ {0, 1}. • Corrupt or Target: The game now enters the “corrupt or target” phase and stays here until either A chooses to proceed, or until every i ∈ [n] has either been corrupted or targeted. Specifically, a set S is initialized to [n], and then A sends queries of the following type: · (i, corrupt), for i ∈ S; in this case C returns xi and removes i from S, i.e., S = S \ {i};

2. Queries: The game now enters the query phase and remains here until A chooses to proceed. During each round of the query phase, A will issue one of two types of queries to C and C will respond.

· (i, target), for i ∈ S; in this case C chooses a random exponent yi ∼ $ and sends (g yi , ci ) where ci = g xi yi if b = 0 and ci = g zi for another random exponent zi ∼ $ if b = 1; again i is removed from S, i.e., S = S \ {i}.

(i) Secret Key Queries − A sends p ∈ N to C; C sends skp to A. (ii) Ciphertext Queries − A sends (P, msg) to C, where P ⊂ N ; C returns B to A where B is prepared as follows:
· if b = 0: B ∼ Enc P, {pkp }p∈P , msg ;

• Finally, A sends a bit b′ ∈ {0, 1} and wins if b′ = b. Claim 1. Suppose an efficient adversary A breaks the security of the vanilla encryption block scheme above (i.e., A wins the security game in Fig. 17 with non-negligible advantage). Then there exists another efficient adversary who can win the corrupt or target DDH game with non-negligible advantage.

· if b = 1: B ∼ $ is drawn uniformly at random. 3. Guess: A sends b′ ∈ {0, 1} to C, and the game ends. Outcome: A wins if b’=b and additionally if: − p∈ / P for all p ∈ N sent by A during a secret key query and P ⊂ N sent by A during a ciphertext query.

Proof. The adversary B plays the corrupt or target DDH game against a challenger C. Additionally, B plays the vanilla encryption block security game as the challenger against the adversary A. B works as follows.

Fig. 17: Vanilla Encryption Block Security Game

a) Decisional Diffie-Hellman. Given a cyclic group G and generator g ∈ G, the decisional Diffie-Hellman (DDH) problem is the following. Given (a, b, c) ∈ G3 where (a, b) = (g x , g y ) for random exponents x, y ∼ $, and either: · c = g xy ; or

• On receiving {g αp }p∈N from C, B forwards {g αp }p∈N to A. • Now both games enter their respective query phases. B initializes the set S = N .

· c = g z for another random exponent z ∼ $; determine which is the case. We say that an algorithm breaks DDH if it can solve this problem with probability at least 1/2 + ϵ for non-negligible ϵ > 0.

· Whenever A sends the secret key query p ∈ N to B, B issues the query (p, corrupt) to C and receives αp from C which it forwards to A; B updates S = S \ {p}. · Whenever A sends the ciphertext query (P, msg) to B, B does the following for each p ∈ P :

b) Rerandomizing DDH Triples. We will need a common trick for using a DDH tuple (a, b, c) to generate a “fresh” DDH tuple (a, b′ , c′ ) “of the same type”. Specifically, there is an efficient procedure which takes (a = g x , b = g y , c) as ′ input and outputs (b′ = g y , c′ ) such that y ′ ∼ $ is a uniformly random exponent and: ′ · if c = g xy then c′ = g xy ; xy

′

− if p ∈ S, B issues the query (p, target) to C and receives the DDH challenge pair (bp , cp ); − if p ∈ / S because A has already issued a secret key query for p, B immediately halts and ouputs a random bit; − if p ∈ / S because A has already issued a ciphertext query involving p, then B has already obtained a challenge DDH pair (bp , cp ) for p;

z′

· if c ̸= g then c = g for a uniformly random exponent z ′ ∼ $. Such a procedure could work as follows: draw uniformly random exponents r, s ∼ $ and set

− at this point (assuming B has not already halted), B has a DDH challenge tuple (g αp , bp , cp ); B next rerandomizes this tuple twice obtaining (Bp , Cp ) and (Bp′ , Cp′ ).

b′ = br · g rs ; c′ = cr · ars .

13

Finally, B sends n
o B = Bp , Cp , Bp′ , Cp′ · msg

1. Setup: C draws (mpk, msk(1) , msk(2) ) ∼ Setup(1λ ), and also a secret bit b ∼ {0, 1}, and sends mpk to A.

p∈P

2. Queries: The game now enters the query phase and remains here until A chooses to proceed. During each round, A will issue one of the following types of queries to C and C will respond.

to A. • When A indicates that the query phase is over by sending the bit b′ ∈ {0, 1} to B, B forwards this bit to C and halts. It can be checked that B and A are playing the many-way semantic security game with active corruptions using C’s secret bit b. Thus, B wins the corrupt or target DDH game whenever A wins. The claim follows.

(i) Key Authority Query − A sends j ∈ {1, 2} to C, who returns msk(j) . (ii) Secret Key Queries − A sends A to C, who returns (1) (2) (j) (skA , skA ), where skA ∼ KeyGen(j) (msk(j) , A), for j = 1, 2. (iii) Ciphertext Queries − A sends (S0 , msg0 ), (S1 , msg1 ) to C with |S0 | = |S1 |; C draws ct ∼ Enc(mpk, Sb , msgb ), where ct = (Sb , ctPL ). C returns ctPL to A.

B. Security of ABE with Payload Anonymity 1) Quick Overview of FABEO In [18], a key-policy ABE scheme called FABEO is given. We describe a very simplified version of the encryption/decryption mechanism of FABEO here for readers who are unfamiliar.

3. Guess: A sends b′ ∈ {0, 1} to C, and the game ends. Outcome: A wins if b′ = b and additionally if: − A(S) = 0 for all A and S sent by A during the secret key and ciphertext queries; and

a) The Encryption/Decryption Mechanism We describe a stripped-down version of the scheme from FABEO [18] in order to illustrate the encryption and decryption mechanics used in our payload anonymity scheme. FABEO builds a fraction of pairings to help decrypt the message and achieve efficiency. Let α ∈ Zp be the secret key and e(g1 , g2 )α the public key. Let H : U → G1 be a hash function mapping attributes into G1 . Consider the policy which simply checks whether a single attribute u∗ ∈ U is satisfied.
The secret key for this policy will be g1α
· H(u∗ )r , g2r ; the ciphertext is H(u∗ )s , g2s , e(g1 , g2 )αs ·msg . Decryption works by computing
e g1α · H(u∗ )r , g2s
= e(g1 , g2 )αs , e H(u∗ )s , g2r

− A asked at most one key authority query (i.e., A did not receive both msk(1) and msk(2) ). Moreover, if A asked for one of msk(1) , msk(2) , then S0 = S1 for all ciphertext queries. Fig. 18: Security Game for KP-ABE with Split KA and PA

enters the query phase and can ask a key-authority query, secret key queries and ciphertext queries. Since A can only ask one key-authority query, we can selectively prepare and simplify the game a bit. Specifically, our starting point is the following game: • C chooses α, β, δ ∼ $ and sends [β]2 , [δ]2 and [α]T to A. Additionally, C chooses a random bit b ∼ {0, 1}.

and using this to recover msg. 2) Correctness of KP-ABE with Split KA and PA The correctness of KP-ABE with Split KA and PA shows as follows. Consider each factor in the quantity val computed during decryption. The numerator is
γi rj sj γ M ·v s
(j) (j)
e (sk1,i )γi , ct2 = e g1 i i j , g2j · e H(π(i)), g2 ,
γi rj sj and the denominator is e H(π(i)), g2 . Thus, we can cancel and we see that Y Y Y  (P γi Mi )·vj s  γ M ·v s
val = e g1 i i j , g2j = e g1 i , g2j i∈IS j=1,2

=

Y

j=1,2

s
e g1α , g2j = e(g1 , g2 )αs ,

j=1,2

and so decryption outputs msg. 3) Security Game We define the security game as Fig. 18. 4) Security Proof in the GGM In this section we prove that the KP-ABE scheme with split key-authority and payload anonymity is secure in the generic group model. To get started, we simplify the security game. Recall the game begins with C sending A mpk and then A

• Now A enters the query phase and asks two types of queries: − A can ask for a secret key query by sending an access structure (M, π), and C chooses a random v1 , v2 ∼ Znp 2 −1 , r1 , r2 ∼ Zp , and returns n    Mi (α, v1 )/β + hπ(i) r1 /β 1 , Mi (α, v2 ) + hπ(i) r2 1 , o [hπ(i) r1 /δ]1 , [hπ(i) r2 ]1 , i∈[n1 ]

, and [r1 ]2 , [r2 ]2 . − A can ask for a ciphertext query by sending S ⊂ U and C chooses s1 , s2 ∼ Zp and returns   [hu s]1 u∈S , [s1 β]2 , [s2 ]2 , [s2 δ]2 , [s1 ]2 , and [αs]T where s = s1 + s2 if b = 0 and [z]T for a random z ∼ Zp if b = 1. • Finally A outputs b′ and wins if b′ = b. It is easy to show that if A can win the payload anonymity game for the ABE scheme (see Fig. 18) then it can also win this game. Now, we prove that no adversary can win this game in

14

coordinate of w is non-zero. So consider evaluating (α, v1 ) and (α, v2 ) to the multiple of w such that the first coordinate is α. Simplifying in this way gives us σ equals to: n o   (j) (j)   (j) (j)  (j) (j) (k) (k) · hu r1 /β 1 , hu r2 1 , hu r1 /δ 1 , [hu s1 ]1 ; u∈S n o  (j) (j) (j) (j) · Mi (α, v1 )/β + hπ(i) r1 /β 1 ; i:π(i)∈S / n o (j) (j) (j) (j)  · Mi (α, v2 ) + hπ(i) r2 1 .

the GGM using the symbolic security framework of prior work [18], [3], [7]. For this purpose, we interpret C’s responses to A’s queries as polynomial evaluations. GGM security then follows by establishing that the span of the query responses is disjoint from the span of the challenges. This is because the GGM restricts how A is allowed to manipulate group elements, so the only way A could try to use the query responses to decide whether C is sending [αs]T or random is by linearly converting the query responses to something in the span of αs and then testing for equality; however this is impossible if the spans are disjoint. We will prove our scheme satisfies strong symbolic security from [18] against an adversary who asks many times of ciphertext query and secret key query in order to derive GGM security. Now, let us zoom into the values that such an adversary receives from its queries. First consider the level one encodings that A gets for k ∈ Qct n,j ∈ Qsk :  o (j) (j) (j) (j) · Mi (α, v1 )/β + hπ(i) r1 /β 1 ; i∈[n1 ] n o (j) (j) (j) (j)  · Mi (α, v2 ) + hπ(i) r2 1 ; i∈[n1 ] n o (j) (j)  · hπ(i) r1 /δ 1 ; i∈[n1 ] o n (j) (j)  ; · hπ(i) r2 1 i∈[n1 ] o n (k) (k)  . · hu s1 1

i:π(i)∈S /

Thus we can consider i : π(i) ∈ S and i : π(i) ∈ / S separately.

a) Step 1: We first consider i : π(i) ∈ S, thus we have n   (j) (j)   (j) (j)  (k) (k) o (j) σ ∈ h(j) , hu r2 1 , hu r1 /δ 1 [hu s1 ]1 r /β u 1 1

u∈S

Then we can evaluate X ∈ {1, σ} and get Equation 2 equals to: X 1 ) (j1 ) −1 ej1 ,j2 ,k h(j · Y (j2 ,k) dα + u r1 β j1 ,j2 ,k

(k)

(k)

(k)

(k)

(k)

X

z = dα + n

o

dXY XY n

X∈ 1,σ ,Y ∈ 1,τ

(k)

j

where

(1)

· U (j) ∈

n  o (j) (j) (j) (j) Mi (α, v1 )/β + hπ(i) r1 /β 1

· V (j) ∈

o n (j) (j) (j) (j)  Mi (α, v2 ) + hπ(i) r2 1

i:π(i)∈S /

i:π(i)∈S /

;

.

Then we can evaluate X ∈ {1, σ} and get Equation 2 equals to X X dα+ ej1 ,j2 ,k U (j1 ) ·Y (j2 ,k) + fj1 ,j2 ,k V (j1 ) ·Y (j2 ,k)

k

and

j,k

/ S, thus we have b) Step 2: We then consider i : π(i) ∈ n o σ ∈ U (j) , V (j)

Proof. The proof proceeds by contradiction. Suppose there exist some z such that n n o n oo
(k) (k)

∩ span α, 1, σ ⊗ 1, τ , z = span α s1 + s2 ck α s1 + s2

pj,k Y (j,k)

(k)

where σ is an encoding from the level one and τ is an encoding from the level two.

z=

X

Equation 1 only contains the product of αs1 and αs2 . However, there is no α contained in Y . Althrough Y contains s1 and s2 , no product of Y contains α in our reduction of Equation 2. We can know Equation 2 does not have the product of αs1 and αs2 . Thus, Equation 1 and Equation 2 can not be equal when X ∈ {1, σ}.

Claim 2. For all Qct , Qsk ∈ N, such that k ∈ Qct , j ∈ Qsk , we have n n o n oo
(k) (k)

span α s1 + s2 ∩ span α, 1, σ ⊗ 1, τ = {0},

(k)

(k )

1 1) Oj,k1 ,k2 h(k · Y (j,k2 ) + u s1

j,k1 ,k2

We can then show

X

(j )

1 −1 1) gj1 ,j2 ,k h(j · Y (j−2,k) + u r1 δ

j1 ,j2 ,k

X

[β]2 , [δ]2 , [r1 ]2 , [r2 ]2 , [s1 β]2 , [s2 ]2 , [s2 δ]2 , [s1 ]2 .

We can have

X

+

u∈S

(j)

(j )

1 1) fj1 ,j2 ,k h(j · Y (j2 ,k) u r2

j1 ,j2 ,k

Next, consider all of the second level encodings A gets for k ∈ Qct , j ∈ Qsk : (j)

X

+

(2)

o

j1 ,j2 ,k

j1 ,j2 ,k

+

for some ck , d, dX,Y . Since for all ciphertext queries and secret key queries, we have A(S) = 0. That means there exists some w such that Mi w = 0 for all i such that π(i) ∈ S, and moreover the first

X j

gj U (j) +

X

lj V (j)

j (k)

(k)

Since Equation 1 only contains the product of αs1 and αs2 , (k) (k) we can cancel the term that does not contains αs1 or αs2 .

15

(k)

· [hu ]1

Then we get X X (j) (j) (k) (j) (j) (k) ej,k Mi (α, v1 ) · s1 + ej,k (hπ(i) r1 ) · s1 +

j,k

j,k

X

(j) (j) (k) ej,k Mi (α, v1 ) · s2 /β +

j,k

+

X

X

(j) (j) (k) fj,k Mi (α, v2 ) · s1 β +

X

(j)

(j)

(k)

[β1 ]2 , [β2 ]2 , [δ1 ]2 , [δ2 ]2 , [s1 β1 ]2 , [s2 β2 ]2 , [s2 δ1 ]2 , [s1 δ2 ]2 .

(j) (j) (k) fj,k Mi (α, v2 ) · s2 +

X

(k)

(k)

Claim 3. For all Qct ∈ N, such that k ∈ Qct , we have n n o n oo
(k) (k)

span α s1 + s2 ∩ span α, 1, σ ⊗ 1, τ = {0},

(j) (j) (k) fj,k (hπ(i) r2 ) · s1 β

j,k

X j,k

X

(k)

We can then show (j) (j) (k) ej,k (hπ(i) r1 ) · s1 /β

j,k

X

X

(j)

(j)

(k)

(j)

(j)

(k)

(j)

(j)

(k)

where σ is an encoding from the level one and τ is an encoding from the level two.

fj,k (hπ(i) r2 ) · s2

j,k (j)

(j)

(k)

fj,k Mi (α, v2 ) · s2 δ +

j,k

+

Next, consider all of the second level encodings A gets for k ∈ Qct , j ∈ Qsk : (k)

X

j,k

+

(k)

ej,k (hπ(i) r1 )·s2 δ/β

(j) (j) (k) ej,k Mi (α, v1 ) · s1 /β +

j,k

+

(j)

j,k

X

+

(j)

ej,k (hπ(i) r1 ) · s2 /β

j,k (j) (j) (k) ej,k Mi (α, v1 )·s2 δ/β +

j,k

+

X

(k)

Note that A would also calculate [hu ]1 by itself.

X

fj,k (hπ(i) r2 ) · s2 δ

Proof. The proof proceeds by contradiction. Suppose there exist some z such that n n o n oo
(k) (k)

z = span α s1 + s2 ∩ span α, 1, σ ⊗ 1, τ ,

j,k (j)

(j)

(k)

fj,k Mi (α, v2 ) · s1 +

j,k

X

fj,k (hπ(i) r2 ) · s1

j,k

We can have z=

(j) (j) v1 , v2 , β, β −1 ,r1 .r2 and δ cannot be canceled, thus Equa(k) (k) tion 1 does not contains the product of αs1 and αs2 .

X

(k)

(k)

ck α s1 + s2

(3)

k

and

Equation 1 and Equation 2 cannot be equal when i : π(i) ∈ / S. For both i : π(i) ∈ S and i : π(i) ∈ / S, Equation 1 and Equation 2 cannot be equal. Thus, we show the contradiction.

X

z = dα + n

o

dXY XY n

X∈ 1,σ ,Y ∈ 1,τ

(4)

o

for some ck , d, dX,Y . This shows that our scheme has strong symbolic security, which by the arguments of [18], implies that it is secure in the GGM.

Then we can evaluate X ∈ {1, σ} and get Equation 4 equals to: X X (k) (k) (k) (k) dα+ β1 (ek,1 h(k) )+ β2 (fk,1 h(k) ) u +ek,2 hu s u +fk,2 hu s

C. Anonymity Proof in the GGM Similar as the security proof, we prove the anonymity of our scheme also in GGM. Consider the same game that used for security proof. Note that our anonymity adversary model intend to prevent attackers from outside the system, thus we only allow A do ciphertext queries. The game them can be simplify as follows: • C chooses α, β1 , β2 , δ1 , δ2 ∼ $ and sends [β1 ]2 , [β2 ]2 , [δ1 ]2 ,[δ2 ]2 and [α]T to A. Additionally, C chooses a random bit b ∼ {0, 1}.

k

+

X

k (k2 ) (k) (k) β1 s1 (gk1 ,k2 ,1 hu + gk1 ,k2 ,2 h(k) )+ u s

k1 k2

X

(k )

(k)

(k) β2 s2 2 (lk,1 h(k) u + lk,2 hu s1 )+

k1 k2

X

X (k) (k) (k) (k) δ1 (mk,1 h(k) δ2 (nk,1 h(k) u +mk,2 hu s1 )+ u +nk,2 hu s1 )+

k

k

X

(k )

(k )

δ1 s2 2 (ok1 ,k2 ,1 hu(k1 ) + ok1 ,k2 ,2 hu(k1 ) s1 2 )+

k1 k2

• Now A enters the query phase and can ask for a ciphertext query by sending S ⊂ U and C chooses s1 , s2 ∼ Zp and returns   [hu s]1 u∈S , [s1 β1 ]2 , [s2 β2 ]2 , [s2 δ1 ]2 , [s1 δ2 ]2 ,

X

(k )

(k )

1 1) δ2 s1 2 (pk1 ,k2 ,1 hu(k1 ) + pk1 ,k2 ,2 h(k ) u s1

k1 k2

We can group β1 as an example, and β2 , δ1 and δ2 will have similar result. X 1 ) (k1 ) β1 (ek1 ,1 hu(k1 ) + ek1 ,2 h(k + u s

and [αs]T where s = s1 +s2 if b = 0 and [z]T for a random z ∼ Zp if b = 1.

k1 ,k2

• Finally A outputs b′ and wins if b′ = b. Now, we prove that no adversary can win this game in GGM as security proof in A-B4. Let’s consider the level one encodings that o A gets for k ∈ Qct : n (k) (k)  · hu s ; 1

(k )

(k )

2 (k) gk1 ,k2 ,1 h(k) + gk1 ,k2 ,2 h(k) s1 2 u s1 u s

(k )

Since the left side only contains s1 + s2 , ek1 ,1 hu 1 and (k) (k ) gk1 ,k2 ,2 hu s(k) s1 2 has to be 0, thus we can cancle them.

u∈S

16

• B responds to the name query p ∈ N by forwarding p to C, receiving skp and forwarding skp back to A.

The formula can then be wirte as X (k2 ) 1 ) (k1 ) β1 (ek1 ,2 h(k + gk1 ,k2 ,1 h(k) ) u s u s1

• On receiving the ciphertext query (S0 , msg0 ), (S1 , msg1 ) from A, B returns (B, ctPL ), prepared as follows:

k1 ,k2

=

X

(k )

(k )

2 2 1) 1) β1 ((ek1 ,2 h(k +gk1 ,k2 ,1 h(k) +ek1 ,2 h(k u u )s1 u s2

− if S0 = S1 , then let S = S0 = S1 and let P ⊂ N be the intended recipient set inside S. B draws:
· B ∼ VEB.Enc P, {pkp }p∈P , S ; and

k1 ,k2

It’s easy to show this formula does not have s1 + s2 , and the same as the following parameters.

· (S, ctPL ) ∼ ABE.Enc(mpk, S, msgb ). − if S0 ̸= S1 , B draws (Sb , ctPL ) ∼ ABE.Enc(mpk, Sb , msgb ) and sends the ciphertext query (Pb , Sb ) to C where Pb ⊂ N is the intended recipient set inside Sb , receiving B.

D. Security of ABEAT Security Game We define the security game for ABEAT as Fig. 21.

Finally, B forwards A’s guess bit to C. When C answers B’s ciphertext queries honestly, A is playing G, while when C is answering B’s ciphertext queries with random strings, A is playing H. Thus, the claim follows from security of VEB. Claim 5. For any PPT adversary A,   1 Pr A wins H = + negl(λ). 2 Proof. This is by reduction to the security of ABE. Specifically, consider the following adversary B who plays the security game for ABE (see Fig. 21). On receiving mpk from C, B runs VEB.KeyGen(N ) and invokes A, sending mpk and {pkp }p∈N . B then enters the query phase with A, responding to A’s queries as follows: • B responds to the name query p ∈ N by sending skp to A.

Theorem 1. Assume VEB is a scheme for generating a block of vanilla encryptions, and ABE is a KP-ABE scheme with split key-authority and payload anonymity. Then ABEAT is a KP-ABE scheme with split key-authority and anonymity for group communication. Furthermore, the decryption costs for intended recipients and unintended recipients, respectively, are TVEB.Dec + TABE.Dec and TVEB.Dec , where TVEB.Dec and TABE.Dec are decryption times of VEB and ABE. Remark. Our implementations of the subroutines in the next section will obtain TABE.Dec ≫ TVEB.Dec , meaning that recipient verification is efficient compared to the decryption cost of intended recipients. Proof. It is clear that ABEAT has the required syntax and correctness follows immediately from correctness of VEB and ABE. The claims about the runtime of decryption are clear by inspecting ABEAT’s decryption procedure. Therefore, it suffices to prove security. Suppose an efficient adversary A plays G, the security game for KP-ABE with split keyauthority and anonymity for group messaging (see Fig. 21). Consider the hybrid game H which is the same as G except for how the challenger answers the ciphertext queries. Upon receiving (S0 , msg0 ), (S1 , msg1 ), C checks whether S0 = S1 . If equality holds, then C responds to the query just as it would in G. If S0 ̸= S1 , then C responds with ct = (B, ctPL ) prepared as follows: · (Sb , ctPL ) ∼ ABE.Enc(mpk, Sb , msgb ) is drawn;

• B handles key-authority and secret-key queries by forwarding the query to C and forwarding C’s response back to A. • B responds to the ciphertext query (S0 , msg0 ), (S1 , msg1 ) with (B, ctPL ), prepared as follows: − B forwards the ciphertext query to C and receives ctPL back; − if S0 ̸= S1 , then B draws B ∼ $ uniformly at random; − if S0 = S1 , then let S = S0 = S1 and let P ⊂ N be the intended recipient
set inside S. B draws B ∼ VEB.Enc P, {pkp }p∈P , S . Finally, when A outputs its guess bit b′ , B ′ simply copies b′ to C. If A wins H with non-negligible advantage, then B breaks the security of ABE.

· B ∼ $ is drawn uniformly at random. The theorem follows from Claims 4 and 5 below. Claim 4. For any PPT adversary A,     Pr A wins G − Pr A wins H = negl(λ).

A PPENDIX B S UPPLEMENTAL M ATERIAL A. How ABEAT Meets the Requirements of Special Operations

Proof. This is by reduction to the security of VEB. Specifically, consider the following adversary B who plays the security game of VEB (see Fig. 17). On receiving {pkp }p∈N from C, B runs ABE.Setup(1λ ) and invokes A, sending mpk and {pkp }p∈N . B then chooses b ∼ {0, 1} and enters the query phase with A, responding to A’s queries as follows: • B responds to key-authority and secret-key queries honestly using (msk(1) , msk(2) ).

We summarize the key features of ABEAT that make it suitable for secure communication among dynamically formed groups that is suitable for a number of situations allowing subsequent verification and auditing of the information exchanged. Anonymization and fast recipient verification ABEAT provides recipient anonymization and fast verification through the Vanilla Encryption Block. This protects the identity of the

17

(b) ABE based Construction

Fig. 19: Detailed Construction of ABEAT

Fig. 20: Changing of Secret Structure 200 Enc Time (s)

1. Setup: C draws a secret bit b ∼ {0, 1} and also    mpk, msk(1) , msk(2) , (pkp , skp ) p∈N ∼ Setup(N ),
and sends mpk, {pkp }p∈N to A. 2. Queries: The game now enters the query phase and remains here until A chooses to proceed. During each round, A will issue one of the following types of queries to C and C will respond.

120 100 80 60 40 20 0

150 100 50 0 0

5

Dec Time (ms)

(a) Diffie-Hellman based Construction

10 15 20 25 30 35 40 45 50 # of Intended Recipients (x103)

(i) Key Authority Query − A sends j ∈ {1, 2} to C, who returns msk(j) . (ii) Secret Key Queries − A sends A to C, who returns (1) (2) (j) (skA , skA ), where skA ∼ KeyGen(j) (msk(j) , A), for j = 1, 2.

ABEAT w/ linear search Enc

ABEAT w/ binary search Enc

ABEAT w/ linear search Dec

ABEAT w/ binary search Dec

Fig. 22: ABEAT w/ Binary Search

multiple rounds of interaction among members and relies on strict message ordering and consistency across participants— a requirement that is difficult to satisfy in disruption-prone networks. In contrast, ABEAT defines the message group at the time of encryption by the sender, allowing communication without having to maintain information of the static group. This makes ABEAT well-suited for highly dynamic environments where membership changes frequently and where the sequence of message arriving is not guaranteed.

(iii) Ciphertext Queries − A sends (S0 , msg0 ), (S1 , msg1 ) to C where |S0 | = |S1 | and where S0 and S1 have the intended recipient sets P0 , P1 ⊂ N , respectively, where |P0 | = |P1 |. C draws   ct ∼ Enc mpk, Sb , {pkp }p∈Pb , msgb and sends ct to A. (iv) Name Queries − A sends p ∈ N to C, who returns skp . 3. Guess: A sends b′ ∈ {0, 1} to C, and the game ends.

Split key authorities to mitigate risk of compromised keys ABEAT employs a split-authority design to reduce the security risk associated with compromised keys. No single authority holds enough information to decrypt ciphertexts, preventing unilateral abuse or leakage of a single master secret key. However, when auditing is required, a higher-level authority may combine the partial master secret keys held by each authority to decrypt and review messages as necessary. This design balances security against accountability, providing operational security without sacrificing auditability.

Outcome: A wins if b’=b and additionally if: − A(S) = 0 for all A and S sent by A during the secret key and ciphertext queries; and − A asked at most one key authority query (i.e., A did not receive both msk(1) and msk(2) ). Moreover, if A asked for one of msk(1) , msk(2) , then S0 = S1 for all ciphertext queries − for all (S0 , msg0 ), (S1 , msg1 ) sent by A as a ciphertext query and all p ∈ N sent by A as a name query, if p ∈ P0 ∪ P1 (where Pi is the intended recipient set specified in Si ), then S0 = S1 .

B. Implementation Details

Fig. 21: Security Game for KP-ABE with Split KA and A for GM

Fig. 19 shows an example construction of ABEAT that has “Fire Engine”, “Firefighter 1”, and “Firefighter 2” as intended recipients. An important part of ABE.ct is the set of perattribute secrets, since recipients are required to locate the corresponding per-attribute secret to enable decryption. As Fig. 20 shows, in non-anonymous KP-ABE, S will indicate the set of per-attribute secrets. However, in ABEAT, S is concealed, thus making it challenging for a recipient to identify the corresponding secret. To address this, while maintaining efficiency, we implement the vanilla encryption block by also encrypting an index that is used to map to the corresponding secret for each intended recipient.

recipients during transmission. In addition, fast verification lets unintended recipients efficiently determine whether a message is for them without heavy computation. Together, these features significantly reduce system overhead and allows ABEAT the flexibility to use a variety of underlying communication channels (e.g., multicast or broadcast) without incurring high cost for each receiver. Group messaging on a per-message basis ABEAT supports group communication on a per-message basis, eliminating the need for explicit and costly group formation protocol. For example, with MLS [10], establishing a group typically requires

18

C. Performance of ABEAT with Binary Search When the number of entries in the vanilla encryption block is large, a linear search for the tag could be inefficient. One solution is to use binary search instead of linear search when the number of entries in the vanilla encryption block is large. We use the x-coordinate as the key for binary search. Encryption We insert entries into the vanilla encryption block in sorted order, based on the tag. The solid line using the left y-axis in Fig. 22 shows the encryption time of ABEAT for both linear and binary search. The additional overhead for encryption for supporting binary search is only 1%. Decryption The dotted line using the right y-axis in Fig. 22 shows the decryption time of ABEAT with linear and binary search under a large intended recipients (vanilla encryption block size). Binary search considerably reduces the time of locating the correct tag. It is approximately 3% to 35% faster than linear search when the intended recipient set is large.

19

Related documents

• IBAKE: Identity-Based Authenticated Key Exchange#220731
• The Privacy Pass Architecture#134714
• Computing in Anonymous Dynamic Networks with One-Bit Communications#353028
• A Trusted Approach for Decentralised and Privacy-Preserving Identity Management#679029
• Secure and fair outsourced decryption service of attribute-based ciphertext using blockchain#457952