arXiv CSopen access

PriSrv+: Privacy and Usability-Enhanced Wireless Service Discovery with Fast and Expressive Matchmaking Encryption

PriSrv+: Privacy and Usability-Enhanced Wireless Service Discovery with Fast and Expressive Matchmaking Encryption Yang Yang˚ , Guomin Yang˚ , Yingjiu Li: , Pengfei Wu˚ , Rui Shi; , Minming Huang˚ , Jian Weng§ , HweeHwa Pang˚ , Robert H. Deng˚

arXiv:2606.05902v1 [cs.CR] 4 Jun 2026

˚ Singapore Management University, Singapore

({yyang, gmyang, pfwu, mmhuang, hhpang, robertdeng}@smu.edu.sg) : University of Oregon, USA ([email protected]) ; Hainan University, China ([email protected]) § Jinan University, Guangzhou, China ([email protected])

Abstract—Service discovery is a fundamental process in wireless networks, enabling devices to find and communicate with services dynamically, and is critical for the seamless operation of modern systems like 5G and IoT. This paper introduces PriSrv+, an advanced privacy and usability-enhanced service discovery protocol for modern wireless networks and resource-constrained environments. PriSrv+ builds upon PriSrv (NDSS’24), by addressing critical limitations in expressiveness, privacy, scalability, and efficiency, while maintaining compatibility with widely-used wireless protocols such as mDNS, BLE, and Wi-Fi. A key innovation in PriSrv+ is the development of Fast and Expressive Matchmaking Encryption (FEME), the first matchmaking encryption scheme capable of supporting expressive access control policies with an unbounded attribute universe, allowing any arbitrary string to be used as an attribute. FEME significantly enhances the flexibility of service discovery while ensuring robust message and attribute privacy. Compared to PriSrv, PriSrv+ optimizes cryptographic operations, achieving 7.62ˆ faster for encryption and 6.23ˆ faster for decryption, and dramatically reduces ciphertext sizes by 87.33%. In addition, PriSrv+ reduces communication costs by 87.33% for service broadcast and 86.64% for anonymous mutual authentication compared with PriSrv. Formal security proofs confirm the security of FEME and PriSrv+. Extensive evaluations on multiple platforms demonstrate that PriSrv+ achieves superior performance, scalability, and efficiency compared to existing state-ofthe-art protocols.

I. I NTRODUCTION Service discovery (SD) protocols, including Wi-Fi [10], AirDrop [11], and BLE [12], are integral to modern wireless networks but lack robust privacy safeguards. This exposes them to tracking, linkability, and identity exposure attacks, where adversaries monitor device presence, track movements, and link sessions, leading to profiling and privacy breaches [22], [29], [41]. Despite the adoption of protocols like DNS-SD [14], mDNS [34], SSDP [27], and UPnP [15], their use of cleartext advertisements and lack of authentication lead to spoofing, MitM, and DoS attacks [17], [44], [45]. This is the full version of the research work published in Network and Distributed System Security Symposium (NDSS) 2026. https://dx.doi.org/10.14722/ndss.2026.230087

Existing privacy-enhancing protocols such as PrivateDrop [31] and WTSB [47] still fall short, as they lack policycontrolled access and attribute hiding, leaving users vulnerable to tracking and impersonation [42]. Similarly, CBN [22] provides anonymous client authentication but fails to protect service providers from spoofing. These limitations underscore the need for privacy-preserving SD mechanisms aligned with global standards. Regulations such as RFC 7258 [28], ISO/IEC 29184 [7], and GDPR [3] mandate confidentiality and privacy-by-design; NIST SP 80063B [4] and ETSI TS 103 465 [5] advocate bilateral access control; and RFC 6973 [26], the NIST Privacy Framework [8], and OECD Guidelines [2] emphasize bilateral anonymity. Sender authentication is equally essential, mandated by NIST SP 800-53 [9], ISO/IEC 29115 [1], and ETSI EN 303 645 [6]. Recently, Yang et al. [49] proposed PriSrv (NDSS’24), addressing major privacy and usability challenges in service discovery. Its dual-layer architecture enables only authorized clients to discover services, protecting sensitive information during interactions. Unlike protocols such as AirDrop and BLE that lack strong privacy guarantees, PriSrv supports bilateral policy control through anonymous credential-based matchmaking encryption (ACME), providing mutual authentication and defending against MitM attacks, tracking, and profiling. However, PriSrv inherits limitations from ACME. It reveals public attributes in the outer layer, potentially enabling tracking. Its binary attribute vector model (each attribute can only represent 1 or 0) restricts expressiveness and increases computation with large attribute sets. ACME’s small-universe design requires system rebuilds to add new attributes, hindering scalability. Additionally, large ciphertexts lead to high communication overhead, and pre-issued anonymous credentials introduce management complexity. To overcome these issues, we propose a fast and expressive matchmaking encryption (FEME) scheme, which is also of independent interest for advancing matchmaking encryption (ME). Unlike prior Identity-Based ME (IBME) schemes [16], [25] that support only equality policies, FEME enables expres-

sive policies with arbitrary strings and solves an open problem posed in CRYPTO’19 and ASIACRYPT’22. Additionally, FEME is significantly faster in encryption and decryption than the existing ME scheme supporting expressive policy control [49]. To further ensure robust authentication and privacy, FEME introduces a novel double re-randomization and binding technique, which prevents encryption key extraction, thwarts ciphertext forgery and component-mixing attacks, and conceals sensitive attribute values. FEME achieves bilateral access control, bilateral anonymity, and sender authentication in the context of expressive policies with high efficiency. It adopts a partially hidden access structure [33], where only attribute names are exposed while attribute values remain concealed, enabling efficient policy matching without revealing sensitive information. Combined with a randomness splitting technique [36], FEME offers a practical and privacy-preserving solution for expressive matchmaking encryption. Building on the strengths of FEME, PriSrv+ overcomes the limitations of its predecessor, PriSrv, and introduces new capabilities. It enhances usability by eliminating the reliance on anonymous credentials and the associated overhead of credential issuance and revocation. PriSrv+ supports expressive bilateral policy control and flexible attribute representation, lifting the constraints of binary vectors and small-universe designs in PriSrv. It also significantly reduces communication overhead, shrinking broadcast sizes by up to 87.33%, which boosts scalability and performance in low-bandwidth settings. Additionally, PriSrv+ improves privacy by concealing all attribute values during service discovery, providing a robust and efficient solution for privacy-preserving service discovery. The key contributions of PriSrv+ are outlined as follows. ‚ Fast and Expressive Matchmaking Encryption (FEME). At the core of PriSrv+, FEME is the first matchmaking encryption scheme capable of supporting expressive access control policies with an unbounded attribute universe, allowing any arbitrary string to be used as an attribute. FEME offers up to 7.62ˆ faster encryption and 6.23ˆ faster decryption compared with ACME, making PriSrv+ suitable for wireless environments. ‚ Enhanced Protocol Scalability and Flexibility. PriSrv+ significantly improves the scalability over PriSrv by supporting unrestricted attribute space. Attributes in PriSrv+ can be arbitrary strings, such as postal addresses, eliminating the restriction of rigid binary vectors used in PriSrv. This enhancement provides greater flexibility in service discovery and access control management, enabling the applicability of PriSrv+ across diverse real-world settings while maintaining low computation and communication overheads. ‚ Optimized Performance and Scalability. By reducing ciphertext size and optimizing cryptographic operations, PriSrv+ significantly lowers packet transmission overhead, leading to up to 7.17ˆ faster service broadcast and 3.32ˆ faster anonymous mutual authentication compared to PriSrv. This positions PriSrv+ as a more efficient and scalable protocol, particularly suitable for bandwidth-limited and latency-sensitive networks.

‚ Interoperability with Existing Protocols. PriSrv+ maintains compatibility with widely-used wireless protocols such as mDNS, BLE, EAP, AirDrop, and Wi-Fi, while addressing scalability issues in PriSrv. In comparison to PriSrv, for instance, PriSrv+ reduces the packet size in mDNS by 88.89%, in BLE by 87.73%, and in Wi-Fi by 86.64%, which makes it more suitable for low-bandwidth environments. ‚ Versatile Implementation across Platforms. PriSrv+ has been tested on a range of platforms, including desktops, laptops, mobile devices, and IoT systems like Raspberry Pi. Experimental results indicate that PriSrv+ reduces delays in both privacy-preserving service broadcast and mutual authentication, delivering immediate responses even in resourceconstrained environments. ‚ Formal Security and Privacy Guarantees. Rigorous formal security proofs demonstrate that FEME satisfies confidentiality, anonymity, and authenticity. PriSrv+ is proven to be a secure service discovery protocol with bilateral anonymity, offering superior protection compared to other state-of-the-art protocols. These contributions establish PriSrv+ as an efficient, secure, and scalable solution for wireless networks, offering robust security and privacy guarantees and adaptability to the evolving demands of modern communication systems. II. R ELATED W ORK A. Service Discovery Protocols Service discovery (SD) protocols such as Wi-Fi [10], AirDrop [11], and Bluetooth Low Energy (BLE) [12] facilitate the automatic detection and advertisement of services and devices in dynamic networks, streamlining device interactions. However, these protocols pose significant privacy risks, particularly for users wishing to safeguard sensitive or identifying information. Studies show that about 90% of users view the exposure of device names as a privacy threat [32], enabling adversaries to infer personal data such as location, mobility, and user profiles [41], [42], [47], [50]. For example, device names in public Wi-Fi can allow Internet Service Providers (ISPs) to track users [22], while attackers in IoT networks can analyze service data to reveal user routines [29]. Most existing SD protocols, including DNS-SD [14], mDNS [34], SSDP [27], and UPnP [15], lack strong privacy safeguards, leaving them vulnerable to man-in-the-middle (MitM), spoofing, and denial-of-service (DoS) attacks [17], [45]. These risks are exacerbated by the use of cleartext broadcasts in Wi-Fi and BLE, which expose device identifiers and enable adversarial tracking and profiling [44]. Although protocols like CBN [22] support anonymous client authentication, they offer insufficient protection for service providers, who remain exposed to impersonation and MitM attacks. Protocols such as AirDrop [11], PrivateDrop [31], and WTSB [47] introduce encryption and authentication to enhance service discovery privacy. While improving mutual authentication and anonymity, they still suffer from tracking, MitM, and DoS vulnerabilities due to incomplete privacy features, such as selective attribute disclosure and multi-show

unlinkability [17], [42]. For example, reliance on certificates in AirDrop and PrivateDrop may allow attackers to link sessions and track users [31]. Yang et al. introduced PriSrv [49], a private SD protocol that allows service providers and clients to define fine-grained access control policies, enabling mutual authentication while concealing private information. PriSrv leverages Anonymous Credential-based Matchmaking Encryption (ACME) to support bilateral policy control, selective attribute disclosure, and multishow unlinkability. However, its large message size results in high transmission overhead and reception delays, limiting its effectiveness in low-bandwidth networks like BLE and congested Wi-Fi. Additionally, the exposure of public attributes may lead to tracing and profiling attacks. Therefore, there is a critical need for private service discovery protocols that provide stronger privacy protections and enhanced usability, a gap that PriSrv+ is designed to fill. B. Matchmaking Encryption (ME) Matchmaking Encryption (ME) was introduced by Ateniese et al. [16] in CRYPTO’19 as a new encryption paradigm enabling both sender and receiver to specify policies that must be mutually satisfied for successful decryption. In ME, the sender with identity or attribute σ defines a policy R, and the receiver with ρ defines S; decryption succeeds only if σ satisfies S and ρ satisfies R. Ateniese et al. also instantiated IdentityBased Matchmaking Encryption (IBME) in the random oracle model, where equality-based identities are used, and sender authentication is achieved via embedded encryption keys. Francati et al. [30] extended IBME to the standard model using non-standard assumptions and NIZK proofs, while Chen et al. [25] constructed IBME under standard assumptions. Despite providing data privacy and authenticity, these schemes are limited to equality-based policies and 1-to-1 data sharing. To support one-to-many data sharing in ME, Sun et al. [43] and Yang et al. [48] in TIFS’23 proposed privacyaware ME (PSME) and certificateless ME (CLME), respectively—extending IBME to multi-user settings via identitybased broadcast encryption. Wu et al. [46] introduced fuzzy IBME (FBME), enabling decryption when the overlap between sender and receiver attributes exceeds a threshold. However, FBME’s threshold-based policies have limited expressiveness and incur high decryption costs. Recently, Yang et al. [49] in NDSS’24 developed ACME, an anonymous credential-based ME scheme with flexible bilateral policy control. Despite its utility, ACME suffers from large ciphertext size and a small-universe construction that requires binary attribute vectors—leading to large vector sizes and increased computation. In contrast, FEME supports monotonic Boolean policies with an unrestricted attribute universe, allowing arbitrary strings as attributes. It also improves performance, reducing ciphertext size by 87.33% and achieving up to 7.62ˆ faster encryption and 6.23ˆ faster decryption. III. P RELIMINARY We present notations, bilinear pairing, access structure, linear secret sharing scheme, and partially hidden access

structure, for constructing FEME and PriSrv+. A. Notation and Bilinear Pairing Let integers m and n satisfy m ă n, with rm, ns representing the set tm, m`1, ..., nu, and rns denoting the set t1, ..., nu. For a prime p, define Zp as the set t0, 1, ..., p ´ 1u, where addition and multiplication are performed modulo p. The set Z˚p excludes 0 from Zp . The security parameter is denoted by λ. We use bold lowercase letters for vectors and bold uppercase letters for matrices. A vector v denotes a column vector by default, and vk represents its k-th element. For a matrix M, Mi is the i-th row, and Mi,j denotes the element at position pi, jq. $ The notation s Ð S indicates that s is uniformly sampled from set S. The notation y Ð Algopxq refers to the output y after running algorithm Algo on input x. An algorithm is probabilistic polynomial time (PPT) if it runs in polynomial time with respect to the input length. We assume a master public key is an implicit input to all algorithms. A bilinear group with Type-III pairings is defined as BG “ pG1 , G2 , GT , e, pq, where there is no efficiently computable isomorphism between G1 and G2 . For any g1 P G1 and g2 P G2 , the pairing epg1 , g2 q $ maps to GT . For a, b Ð Z˚p , one has epg1a , g2b q “ epg1 , g2 qab . B. Access Structure Definition 1 (Access Structure [18]). Let tP1 , ¨ ¨ ¨ , Pn u be a set of parties. A collection A Ď 2tP1 ,¨¨¨ ,Pn u is monotone if @B, C: if B P A and B Ď C, then C P A. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of non-empty subsets of tP1 , ¨ ¨ ¨ , Pn u, i.e., A Ď 2tP1 ,¨¨¨ ,Pn u ztHu. The sets in A are called authorized sets, and the sets not in A are called unauthorized sets. An access structure is said to be monotone if, for any two sets S and T of attributes, S Ď T and S being authorized imply that T is also authorized. It ensures that any user possessing a set of attributes that satisfies the access policy continues to have access if additional attributes are granted. C. Linear Secret Sharing Scheme (LSSS) Definition 2 (Linear Secret Sharing Scheme (LSSS) [18]). A secret sharing scheme Π over a set of parties P is called linear (over Zp ) if (1) the shares of each party form a vector over Zp . (2) there exists a matrix A with m rows and n columns called the share-generating matrix for Π. For all i “ 1, ¨ ¨ ¨ , m, the i-th row of A is labeled by a party ρpiq (ρ is a function from t1, ¨ ¨ ¨ , mu to P). When we consider the column vector v “ ps, r2 , ¨ ¨ ¨ , rn q, where s P Zp is the secret to be shared, and r2 , ¨ ¨ ¨ , rn P Zp are randomly chosen, then Av is the vector of m shares of the secret s according to Π. The share pAvqi belongs to party ρpiq. LSSS possesses the linear reconstruction property [18]. Let Π be an LSSS for the access structure A, and S P A be an authorized set with I Ă t1, ¨ ¨ ¨ , mu, where I “ ti|ρpiq P Su. There exists a set of constants tωi P Zp uiPI such that, given any valid shares tλi u of a secret s in Π, the relationship

ř

iPI ω ři λi “ s holds. Let Ai be the i-th row of A, we similarly have iPI ωi Ai “ p1, 0, ¨ ¨ ¨ , 0q. These constants tωi u are computable in time polynomial [18] in the size of A. Notably, constants tωi u cannot be constructed for unauthorized sets. Boolean Formulas. Boolean formulae are a common way to model access control. LSSS is a more general class of functions and include Boolean formulas. Using established methods [18], any monotone Boolean formula can be transformed into an LSSS format. Such a formula can be structured as an access tree, where an access tree with m nodes yields an LSSS matrix of m rows.

D. Partially Hidden Access Structure In a partially hidden access structure [33], attributes are divided into attribute names and attribute values, where only attribute names are exposed, while attribute values remain hidden. For example, consider an access policy that requires “Role: Admin AND Department: Research OR Level: Confidential” to access certain data, where “Role”, “Department”, and “Level” are attribute names, and “Admin”, “Research”, and “Confidential” are attribute values. In a partially hidden access structure, the policy is transformed to “Role AND Department OR Level”, revealing attribute names only. This contrasts with a traditional access structure, where attributes are exposed in the policy. We first define the structures of an attribute set and an access policy. Let the attribute set be S “ tui uiPrℓs containing ℓ attributes, where each attribute belongs to a unique category. Each attribute is denoted as ui “ xni , vi y, with ni representing the attribute name and vi the attribute value. An access policy is defined as A “ pM, π, T q, where M is an m ˆ n access control matrix, Mi is the i-th row of M, and π is a mapping function that associates each row Mi with an attribute πpiq. The policy T is expressed as pΨπp1q , ¨ ¨ ¨ , Ψπpmq q, where each Ψπpiq “ xnπpiq , vπpiq y consists of a name nπpiq and value vπpiq . In a partially hidden attribute set, attribute values vi are concealed, leaving only attribute names ni visible. The resulting attribute set is modified to Spartial “ tni uiPrℓs . Similarly, in a partially hidden access policy, the attribute values vπpiq are removed from T , exposing only the attribute names. The modified policy is represented as Apartial “ pM, π, Tname q, where Tname “ pnπp1q , ¨ ¨ ¨ , nπpmq q. It conceals attribute values to enhance privacy while using attribute names for efficient policy matching. We define partial satisfaction Spartial |ù Apartial if the attribute names in Spartial match those in Apartial . Full satisfaction (S |ù A) requires matching both names and values, whereas partial satisfaction only matches attribute names. IV. FAST AND E XPRESSIVE M ATCHMAKING E NCRYPTION (FEME) We construct FEME, a fast and expressive matchmaking encryption scheme, as the core component of PriSrv+. It is also of independent interest for advancing ME techniques. A. Technical Roadmap In an ME system, both sender and receiver, each possessing a set of attributes, define access policies that the other

must meet to decrypt any message. FEME features privacypreserving policy matching and user anonymity. We leverage Attribute-Based Encryption (ABE) [19], [23] with expressive access policies to enable bilateral matching of the policies of both sender and receiver. ABE is available in two forms: ciphertext-policy ABE (CP-ABE) and key-policy ABE (KPABE), both essential for building FEME.

Fig. 1: Technical Roadmap of FEME The design of FEME, as shown in Fig. 1, follows a structured, multi-stage roadmap that enhances existing ABE schemes to address privacy and efficiency challenges. We build on FABEO [38], a dual-form KP-ABE and CP-ABE scheme1 that supports expressive policies without restrictions on policy type or attribute range. However, while FABEO excels in policy expressiveness, it lacks privacy-preserving policy matching or anonymity. FABEO’s CP-ABE exposes access policies with plaintext attribute values, and its KP-ABE reveals attribute values in attribute sets. Moreover, FABEO’s decryption incurs high computation overhead due to pairing and exponentiation operations that scale with policy complexity. FEME addresses these limitations in three distinct stages. Stage 1 enhances FABEO’s KP-ABE and CP-ABE schemes, creating anonymous versions (A-KP-ABE in Fig. 2 and A-CPABE in Fig. 3), that hide attribute values in attribute sets and access policies, greatly improving computational efficiency. Stage 2 introduces Hybrid-ABE (Fig. 4), bridging the gap between ME with CP-ABE/KP-ABE and supporting bilateral policy-matching and sender authentication. Stage 3 integrates A-KP-ABE, A-CP-ABE, and Hybrid-ABE schemes to create FEME, an ME that enhances both privacy and efficiency. B. Novelty of FEME Distinct from Existing ABE-Based Solutions. FEME achieves bilateral access control, bilateral anonymity, and sender authentication—features not simultaneously supported by existing ABE-based schemes such as FABEO [38], FEASE [36], and FABESA [35]. These works optimize ABE 1 Both schemes control access by matching attributes to policies, but they reverse the roles of the ciphertext and key in defining access control. They share the same design mechanism and common parameters.

efficiency or enable unilateral anonymity for searchable encryption but lack bilateral policy matching and sender authentication, both of which are critical for privacy-preserving service discovery. Technical Challenges and Innovations. Designing an ME scheme for real-time service discovery presents significant challenges beyond traditional ABE systems. Existing ABE schemes, including combinations of CP-ABE and KP-ABE, cannot enforce sender authentication—a critical requirement in ME. Without sender authentication, malicious entities can forge ciphertexts with fabricated attributes, enabling impersonation, spoofing, and injection attacks that threaten both security and availability. Prior techniques such as partial policy hiding and randomness splitting, used in works like FEASE and FABESA, fall short of defending against these advanced threats in bilateral settings. To overcome these limitations, FEME introduces a novel double re-randomization and binding technique that ensures both efficiency and robust sender authentication. The firstlevel re-randomization randomizes encryption key components using a shared factor, preventing adversaries from extracting or reusing the sender’s encryption key. The second-level rerandomization applies additional independent randomness to specific ciphertext components while enforcing a constraint across them. This enforces binding between encryption keyderived components and other ciphertext elements, ensuring they cannot be mixed or tampered with to create forged messages. Moreover, the second-level re-randomization conceals sensitive attribute values to resist attribute guessing attacks. Together, these mechanisms provide strong protection against impersonation, ciphertext injection, and attribute guessing attacks—enabling secure, private, and authenticated service discovery in adversarial settings. C. Technical Details Following the above roadmap, we transform FABEO into a privacy-preserving and efficient ME scheme. Stage 1. We create A-CP-ABE and A-KP-ABE as anonymous variants of FABEO’s CP-ABE and KP-ABE, respectively, using the following techniques. (1) Partially Hidden Access Structure. To balance privacy and efficiency, we adopt a partially hidden access structure (§III-D) that separates each attribute into a visible attribute name and a concealed attribute value, protecting sensitive information. Since attribute names—visible in A-KP-ABE or A-CP-ABE ciphertexts—are typically less sensitive, this design enables significant efficiency gains. Our A-CP-ABE and A-KP-ABE constructions minimize costly pairing and exponentiation operations, accelerating policy matching and improving suitability for resource-constrained environments. (2) Randomness Splitting Technique. To address the vulnerability of attribute guessing attacks in the FABEO KP-ABE scheme, we implement a randomness splitting technique. In the original FABEO KP-ABE scheme (see Fig. 1 in [38]), the reuse of a single random value s across ciphertext components ct1,u “ Hpuqs and ct2 “ g2s makes it possible for an

A-KP-ABE: Anonymous KP-ABE Setupp1λ q Ñ pmpk, mskq. Generate G :“ pp, G1 , G2 , GT , e, g1 , g2 q. $

˚ Pick α, b1 , b2 Ð Z˚ Ñ G1 . Compute p and a hash function H : t0, 1u b b Z “ epg1 , g2 qα , δ1 “ g21 , δ2 “ g22 . Output the master public key mpk :“ pG, H, Z, δ1 , δ2 q and master secret key msk :“ pα, b1 , b2 q. Remind that KeyGenpmsk, A “ pA, ρ, tΨρpiq uiPrms qq Ñ SKA . $ “ txnρpiq , vρpiq yuiPrms . Pick r 1 Ð Z˚ p and ` Ai pα||yqJ n´1 r1 y Ð Zp . Compute sk1 “ g2 , sk2,i “ g1 ¨ ` A pα||yqJ 1˘ 1 1˘ 1 ¨ HpΨρpiq qr b2 . Output HpΨρpiq qr b1 , sk3,i “ g1 i SKA :“ ppA, ρ, tnρpiq uiPrms q, sk1 , tsk2,i , sk3,i uiPrms q.

tΨρpiq uiPrms $

$

EncpS “ tui uiPrℓs “ txni , vi yuiPrℓs , msgq Ñ CTS . Pick s1 , s2 Ð Z˚ “ s1 ` s2 . Compute ct0 “ epg1 , g2 qαs ¨ msg, p . Let s 1

2

ct1,i “ Hpui qs , ct2 “ δ1s , ct3 “ δ2s . Output CTS :“ ptni uiPrℓs , ct0 , tct1,i uiPrℓs , ct2 , ct3 q. DecpSKA , CTS q Ñ msg{K. If there is any subset I that matches the attribute names tni uiPrℓs inřCT with pA, ρ, tnρpiq uiPrms q in SK, there exist constants tωi uiPI s.t. iPI ωi Ai “ p1, 0, ¨ ¨ ¨ , 0q. Output ś ct0 ¨ ep iPI pct1,ρpiq qωi , sk1 q . msg “ ś ś ω ep iPI psk2,i q i , ct2 q ¨ ep iPI psk3,i qωi , ct3 q

Fig. 2: A-KP-ABE Scheme A-CP-ABE: Anonymous CP-ABE Setupp1λ q Ñ pmpk, mskq. Generate G :“ pp, G1 , G2 , GT , e, g1 , g2 q. $

$

˚ Pick α Ð Z˚ Ñ G1 . p , h Ð G1 and a hash function H : t0, 1u Compute Z “ epg1 , g2 qα . Output the master public key mpk :“ pG, H, Z, hq and master secret key msk :“ α. $ KeyGenpmsk, S “ tui uiPrℓs “ txni , vi yuiPrℓs q Ñ SKS . Pick r Ð ˚ α r r r Zp . Computes sk1 “ g1 h , sk3 “ g2 , sk2,i “ Hpui q for i P rℓs. Output SKS :“ ptni uiPrℓs , sk1 , tsk2,i uiPℓ , sk3 q. Remind that EncpA “ pM, π, tΨπpiq uiPrms q, msgq Ñ CTA . $

tΨπpiq uiPrms “ txnπpiq , vπpiq yuiPrms . Pick s1 , s1 Ð Z˚ p and $

vector v Ð Zn´1 . Compute ciphertext ct0 “ epg1 , g2 qαs1 ¨ msg, p s

1

J

1

ct1 “ g21 , ct2 “ g2s , ct3,i “ hMi ps1 ||vq ¨ HpΨπpiq qs . Output CT :“ ppM, π, tnπpiq uiPrms q, ct0 , ct1 , ct2 , tct3,i uiPrms q. DecpSKS , CTA q Ñ msg{K. If there is any subset I that matches the attribute names tni uiPrℓs inřSK with pM, π, tnπpiq uiPrms q in CT, there exist constants tγi uiPI s.t. iPI γi Mi “ p1, 0, ¨ ¨ ¨ , 0q. Output ś ct0 ¨ ep iPI pct3,i qγi , sk3 q msg “ . ś epsk1 , ct1 q ¨ ep iPI psk2,πpiq qγi , ct2 q

Fig. 3: A-CP-ABE Scheme

attacker to deduce an attribute u by testing the equality epct1,u , g2 q “ epHpuq, ct2 q. To mitigate this risk, our A-KPABE scheme (see Fig. 2) splits the randomness s into two independent values, s1 and s2 , such that s “ s1 ` s2 . This adjustment modifies the ciphertext components as follows: 2 1 ct1,i “ Hpui qs , ct2 “ δ1s , and ct3 “ δ2s , where δ1 “ g2b1 b2 and δ2 “ g2 . To cancel the exponentiation b1 and b2 , the decryption key includes components sk2,i and sk3,i , which use exponentiation by b11 and b12 . It ensures that the attribute set remains concealed, and the modified components ct1,i , ct2 , and ct3 reveal no information for any attacker to infer attributes, thus effectively preventing attribute guessing attacks. (3) Scalability and Efficiency Enhancement. We take several

Hybrid-ABE: Bridging CP-ABE and KP-ABE Setupp1λ q Ñ pmpk, mskq. Generate G :“ pp, G1 , G2 , GT , e, g1 , g2 q. $

$

˚ Pick x, µ, b1 , b2 Ð Z˚ Ñ p , h Ð G1 and a hash function H : t0, 1u b b G1 . Compute Y “ epg1 , g2 qxµ , δ0 “ g2µ , δ1 “ g21 , δ2 “ g22 . Output the master public key mpk :“ pG, H, Y, h, δ0 , δ1 , δ2 q and master secret key msk :“ px, µ, b1 , b2 q. EKGenpmsk, Ssnd “ tui uiPrℓs “ txni , vi yuiPrℓs q Ñ EKSsnd . Pick $

x τ τ τ τ Ð Z˚ p . Compute ek1 “ g1 h , ek3 “ δ1 , ek4 “ δ2 , ek2,i “ Hpui qτ . Output EKSsnd :“ ptni uiPrℓs , ek1 , tek2,i uiPℓ , ek3 , ek4 q. $

PolGenpArcv “ pmsk, A, ρ, tΨρpiq uiPrms qq Ñ SKArcv . Pick r 1 Ð Z˚ p ` M ps ||yqJ $ r1 i 1 and y Ð Zn´1 . Compute sk “ g , sk “ h ¨ 1 2,i p 2 ` J 1˘ 1 1˘ 1 HpΨρpiq qr b1 , sk3,i “ hMi ps1 ||yq ¨ HpΨρpiq qr b2 . Output SKArcv :“ ppA, ρ, tnρpiq uiPrms q, sk1 , tsk2,i , sk3,i uiPrms q. $

1 2 EncpEKSsnd , msgq Ñ CTsnd . Pick τ 1 , s1 , s2 Ð Z˚ p . Let s “ s ` s . 1

Compute ct0 “ Y s ¨ msg, ct1,i “ pek1,i ¨ Hpui qτ qs , ct2 “ pek2 ¨ 1 1 1 2 1 δ1τ qs , ct3 “ pek2 ¨ δ2τ qs , ct4 “ pek4 ¨ hτ qs . Output CTsnd :“ ptni uiPrℓs , ct0 , tct1,i uiPrℓs , ct2 , ct3 , ct4 q. DecpSKArcv , CTsnd q Ñ msg{K. If there is any subset I that matches tni uiPrℓs in CTsnd with ř pA, ρ, tnρpiq uiPrm2 s q in SKArcv , there exist constants tωi uiPI s.t. iPI ωi Ai “ p1, 0, ¨ ¨ ¨ , 0q. Output ś ś ep iPI psk2,i qωi , ct2 qep iPI psk3,i qωi , ct3 q . msg “ ct0 ¨ ś epct4 , δ0 qep iPI pct1,ρpiq qωi , sk1 q

Fig. 4: Hybrid-ABE Scheme

steps to make FEME highly scalable and efficient. First, we construct large-universe A-KP-ABE and A-CPABE schemes that allow FEME to handle an extensive and potentially unbounded set of attributes dynamically. This approach reduces the need for pre-defining and managing fixed attribute sets, enhancing scalability and minimizing the overhead associated with system updates and attribute expansions. By replacing the term Hp|U| ` 1q in FABEO with an element $ h Ð G1 in the master public key mpk, A-KP-ABE and A-CPABE become independent of the size of the attribute universe |U|. This modification eliminates dependence on a fixed set of attributes, thereby improving both scalability and efficiency, and allowing for a more flexible and adaptable system. Second, we address the main efficiency bottleneck in FABEO CP-ABE, which stems from its ciphertext compos1 rjs nents. Specifically, its ciphertext components ct2,j “ g2 J 1 and ct3,i “ Hp|U| ` 1qMi ps1 ||vq ¨ HpΨπpiq qs rζpiqs involve a $ random vector s⃗1 Ð Zτp , where τ represents vector size and ζpiq :“ |tz|πpzq “ πpiq, z ď iu|. This setup leads to decryption involving τ pairing operations and approximately τ I exponentiations, which becomes computationally expensive, where I represents the number of attributes required to satisfy an access policy. To mitigate this, we propose modifications 1 to the ciphertext components, simplifying them to ct2 “ g2s J 1 and ct3,i “ hMips1 ||vq ¨ HpΨπpiq qs in our developed A-CP$

ABE (Fig. 3), where s1 Ð Zp . This significantly reduces the decryption workload to a single pairing operation and I exponentiations, resulting in a more efficient decryption. Third, recognizing the dual structure between FABEO KPABE and FABEO CP-ABE, we apply the above optimization

technique to A-KP-ABE (Fig. 2). We replace its secret key 1 r 1 rjs A pα||yqJ components sk1,j “ g2 , sk2,i “ g1 i ¨HpΨρpiq qr rηpiqs , 1 $ A pα||yqJ where r⃗1 Ð Zτ , with sk1 “ g r and sk2,i “ g i ¨ p

1

2

$

1

HpΨρpiq qr , using r1 Ð Zp in our developed A-KP-ABE. Here, ηpiq is defined as |tz|ρpzq “ ρpiq, z ď iu|. Then, we utilize the randomness splitting technique to split sk2,i ` A pα||yqJ 1˘ 1 into two terms sk2,i “ g1 i ¨ HpΨρpiq qr b1 , sk3,i “ ` Ai pα||yqJ 1˘ 1 g1 ¨ HpΨρpiq qr b2 . These optimizations effectively reduce the computational overhead in both A-CP-ABE and AKP-ABE, making them more suitable for real-world applications, particularly those in resource-constrained environments. Stage 2. To address the gap between ME and A-CP-ABE/AKP-ABE, we develop a Hybrid-ABE scheme (Fig. 4). This gap stems from the sender authentication requirement in ME, which ensures that only authorized senders (with a valid encryption key EK tied to their attributes) can generate legitimate ciphertexts. However, FABEO CP-ABE and KP-ABE do not inherently support sender authentication, as senders only use the master public key mpk and an attribute set (in KP-ABE) or access policy (in CP-ABE) to derive ciphertext. To close this gap, Hybrid-ABE integrates the frameworks of A-CP-ABE and A-KP-ABE. Hybrid-ABE comprises the following algorithms: Setup, EKGen, PolGen, Enc and Dec. The EKGen algorithm generates the sender’s attribute encryption key EKSsnd , drawing from A-CP-ABE’s KeyGen algorithm and incorporating the randomness splitting technique from A-KP-ABE’s Enc algorithm. PolGen produces the receiver’s policy decryption key SKArcv , utilizing the exponentiation tricks from A-KP-ABE’s KeyGen. During encryption, the sender’s encryption key EKSsnd is used to generate ciphertext CTsnd , which wraps message msg in ciphertext component ct0 “ Y s ¨ msg. The sender’s encryption key is re-randomized into ciphertext components $ ct1,i , ct2 , ct3 , ct4 , using a nonce τ 1 Ð Z˚p and two split 1 2 randomness values s and s (where s “ s1 ` s2 ). The decryption algorithm unifies the processes of A-CP-ABE and A-KP-ABE, requiring only 4 pairings and 3I exponentiations (where I represents the number of attributes required to satisfy an access policy), ensuring high efficiency. Stage 3. We construct FEME as shown in Fig. 5 based on A-CP-ABE, A-KP-ABE, and Hybrid-ABE developed in Stages 1 and 2. FEME consists of the following algorithms: Setup, EKGen, DKGen, PolGen, Enc and Dec. The Setup algorithm initializes the master public key and the master secret key. EKGen generates the sender’s attribute encryption key following the process outlined in HybridABE. DKGen produces the receiver’s attribute decryption key, as KeyGen does from A-CP-ABE. Meanwhile, PolGen generates the receiver’s policy decryption key following the KeyGen method from A-KP-ABE for producing its components psk1 , tsk2,i , sk3,i uiPrm2 s q. Additionally, PolGen adopts the Hybrid-ABE framework for producing its components ptsk4,i , sk5,i uiPrm2 s q, where m2 denotes the number of rows in a receiver’s access matrix A.

FEME: Fast and Expressive Matchmaking Encryption 1. Setupp1λ q Ñ pmpk, mskq. // System Setup This algorithm takes in the security parameter 1λ and generates a bilinear pairing G :“ pp, G1 , G2 , GT , e, g1 , g2 q. $ $ The algorithm picks random numbers α, x, µ, b1 , b2 Ð Z˚p , h Ð G1 , hash functions H : t0, 1u˚ Ñ G1 , Ĥ : GT Ñ t0, 1ul0 , and a polynomial-time computable padding function ϕ : t0, 1un Ñ t0, 1uℓ0 . It computes Z “ epg1 , g2 qα , Y “ epg1 , g2 qxµ , δ0 “ g2µ , δ1 “ g2b1 , δ2 “ g2b2 . It outputs the master public key as mpk :“ pG, H, Ĥ, ϕ, Z, Y, h, δ0 , δ1 , δ2 q, and the master secret key as msk :“ pα, x, µ, b1 , b2 q. 2. EKGenpmsk, Ssnd “ tui uiPrℓ1 s “ txni , vi yuiPrℓ1 s q Ñ EKSsnd . // Attribute Encryption Key Generation This algorithm generates the sender’s attribute encryption key EKSsnd for attributes Ssnd “ tui uiPrℓ1 s “ txni , vi yuiPrℓ1 s , $

where ni denotes the attribute name and vi the attribute value. It picks a random number τ Ð Z˚p and computes as follows: ek1,i “ Hpui qτ for i P rℓ1 s, ek2 “ δ1τ , ek3 “ δ2τ , ek4 “ g1x hτ . It outputs the sender attribute encryption key EKSsnd :“ ptni uiPrℓ1 s , tek1,i uiPrℓ1 s , ek2 , ek3 , ek4 q. 3. DKGenpmsk, Srcv “ tui uiPrℓ2 s “ txni , vi yuiPrℓ2 s q Ñ DKSrcv . // Attribute Decryption Key Generation To generate the receiver’s attribute decryption key DKSrcv for attributes Srcv “ tui uiPrℓ2 s “ txni , vi yuiPrℓ2 s , this algorithm $

picks a random number r Ð Z˚p and computes as follows: dk1 “ g1α hr , dk2,i “ Hpui qr , dk3 “ g2r . It outputs the receiver attribute decryption key DKSrcv :“ ptni uiPrℓ2 s , dk1 , tdk2,i uiPrℓ2 s , dk3 q. 4. PolGenpmsk, Arcv “ pA, ρ, tΨρpiq uiPrm2 s qq Ñ SKArcv . // Policy Decryption Key Generation This receiver’s policy decryption key generation algorithm generates the secret key skArcv with receiver’s monotone span policy Arcv “ pA, ρ, tΨρpiq uiPrm2 s qq, where A is an m2 ˆn2 access control matrix, tΨρpiq uiPrm2 s “ txnρpiq , vρpiq yuiPrm2 s , $

$

nρpiq denotes attribute name and vρpiq attribute value. It picks a random number r1 Ð Z˚p , a random vector y Ð Znp 2 ´1 and computes as follows: A pα||yqJ

1

sk1 “ g2r ,

sk2,i “ pg1 i J

1

1

1

A pα||yqJ

1

¨ HpΨρpiq qr q b1 ,

sk3,i “ pg1 i J

1

1

1

¨ HpΨρpiq qr q b2 ,

1

sk5,i “ phAi pµ||yq ¨ HpΨρpiq qr q b2 , for each row i P rm2 s.

sk4,i “ phAi pµ||yq ¨ HpΨρpiq qr q b1 ,

It outputs the receiver policy decryption key SKArcv :“ ppA, ρ, tnρpiq uiPrm2 s q, sk1 , tsk2,i , sk3,i , sk4,i , sk5,i uiPrm2 s q. 5. EncpEKSsnd , Asnd “ pM, π, tΨπpiq uiPrm1 s q, msgq Ñ CTsnd . // Encrypt This algorithm encrypts a message msg P t0, 1un with sender’s monotone span policy Asnd “ pM, π, tΨπpiq uiPrm1 s q and sender attribute encryption key EKSsnd , where tΨπpiq uiPrm1 s “ txnπpiq , vπpiq yuiPrm1 s and matrix M P Zm1 ˆn1 . It $

$

selects s1 , s12 , s22 , s13 , s23 , τ 1 Ð Z˚p , a vector v Ð Znp 1 ´1 . Let s2 “ s12 ` s22 and s3 “ s13 ` s23 . It computes as follows: V “ Z s1 `s2 ¨ Y s3 ,

ct0 “ ϕpmsgq ‘ ĤpV q,

ct1 “ g2s1 ,

s1

J

ct3,i “ hMi ps1 ||vq ¨ HpΨπpiq qs3 for each row i P rm1 s, 1

ct2 “ g2s3 , s2

ct4,1 “ δ12 , ct4,2 “ δ22 , 1

1

1

2

1

ct5,i “ Hpui qs2 , ct6,i “ pek1,i ¨Hpui qτ qs3 for i P rℓ1 s, ct7 “ pek2 ¨δ1τ qs3 , ct8 “ pek3 ¨δ2τ qs3 , ct9 “ pek4 ¨hτ qs3 . It outputs the ciphertext CTsnd :“ ppM, π, tnπpiq uiPrm1 s q, tni uiPrℓ1 s , ct0 , ct1 , ct2 , tct3,i uiPrm1 s , ct4,1 , ct4,2 , tct5,i , ct6,i uiPrℓ1 s , ct7 , ct8 , ct9 q. 6. DecpDKSrcv , SKArcv , CTsnd q Ñ msg{K: // Decrypt This algorithm decrypts a given ciphertext ř CTsnd using DKSrcv and SKArcv . If Srcv |ù Asnd (denoting that Srcv satisfies Asnd ), there exist constants tγi uiPIř s.t. 1 iPI1 γi Mi “ p1, 0, ¨ ¨ ¨ , 0q. If Ssnd |ù Arcv (denoting that Ssnd satisfies Arcv ), there exist constants tωi uiPI2 s.t. iPI2 ωi Ai “ p1, 0, ¨ ¨ ¨ , 0q. This algorithm recovers V by computing ś ś ś epdk1 , ct1 qep iPI1 pdk2,πpiq qγi , ct2 q ep iPI2 psk2,ρpiq qωi , ct4,1 qep iPI2 psk3,ρpiq qωi , ct4,2 q ś ś ¨ V “ ep iPI1 pct3,πpiq qγi , dk3 q ep iPI2 pct5,ρpiq qωi , sk1 q ś epct9 , δ0 qep iPI2 pct6,ρpiq qωi , sk1 q ś ¨ ś . ep iPI2 psk4,ρpiq qωi , ct7 qep iPI2 psk5,ρpiq qωi , ct8 q It computes ϕpmsgq “ ct0 ‘ ĤpV q. If the padding is valid, this algorithm returns msg. Otherwise, it returns K. Fig. 5: FEME: Fast and Expressive Matchmaking Encryption Scheme

Scheme IBME [16] (Crypto’19) IBME [30] (IndoCrypt’21) IBME [25] (AsiaCrypt’21) FBME [46] (TIFS’23) PSME [43] (TIFS’23) CLME [48] (TIFS’23) ACME [49] (NDSS’24) FEME

Expressiveness Monotonic Arbitrary Large Policy Attribute Universe ‘ ˆ ˆ ‘ ˆ ˆ ‘ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ‘ ˆ ˆ ‘ ˆ ˆ ‘ ‘ ‘

Security and Privacy Data Data Attribute Privacy Authenticity Privacy ‘ ‘ ‘ ‘ ‘ ‘ ˆ{ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ˆ ‘ ‘ ‘

Usability No Pre-registration No Additional Pairing Component ‘ ˆ ‘ ˆ ‘ ˆ ‘ ˆ ‘ ˆ ‘ ˆ ‘ ˆ ‘ ‘

TABLE I: Comparison of Matchmaking Encryption (ME) Schemes During encryption, a message msg is encapsulated in ciphertext component ct0 “ ϕpmsgq ‘ ĤpV q with V “ Z s1 `s2 ¨ Y s3 , which combines elements from the ct0 components of all three schemes A-CP-ABE, A-KP-ABE, and Hybrid-ABE, where Ĥ is a hash function, and ϕ is a polynomial-time computable and efficiently invertible padding function to realize authenticated encryption. The encryption process generates pct1 , ct2 , tct3,i uiPrm2 s q based on Enc in A-CP-ABE, pct4,1 , ct4,2 , tct5,i uiPrm1 s q from A-KP-ABE, and ptct6,i uiPrℓ1 s , ct7 , ct8 , ct9 q based on Hybrid-ABE. Here, m1 denotes the number of rows in sender’s access matrix M, and ℓ1 the number of attributes in sender’s attribute set. FEME Dec incorporates the decryption processes of A-CPABE, A-KP-ABE, and Hybrid-ABE, with its three decryption fractions corresponding to Dec in each scheme. D. FEME Construction Following the above technical details, we describe the construction of FEME in Fig. 5. The security models for FEME, detailed in Appendix A, outline its confidentiality, anonymity, and authenticity properties. In FEME, a key generation center (KGC) runs Setup to generate the master public and secret keys, incorporating an efficiently computable and invertible padding function ϕ that enables integrity checks, thereby ensuring authenticated message encryption and robustness against unauthorized modifications [16]. To enable secure communication, the KGC executes EKGen to create the sender’s attribute encryption key, and DKGen/PolGen to generate the receiver’s attribute decryption key and policy decryption key. During Enc, the sender specifies an access policy that the receiver must meet to access the message. FEME ensures that decryption is only possible if the sender’s and receiver’s attributes match their respective policies, guaranteeing sender authenticity by certifying sender attributes through the attribute encryption key to prevent forged ciphertexts. A core innovation of FEME is its double re-randomization and binding technique, which ensures secure and efficient sender authentication. First re-randomization applies a shared random value τ 1 to encryption key components pek1,i , ek2 , ek3 , ek4 q, generating ciphertext components pct6,i , ct7 , ct8 , ct9 q, preventing adversaries from extracting valid encryption keys. Second re-randomization utilizes random values s3 , s13 , s23 , ensuring attackers cannot generate

new valid ciphertexts via mimicry. The same s3 binds encryption key-derived components with ciphertext elements pV, ct2 , ct3,i q, preventing attackers from mixing components from different ciphertexts. To conceal sensitive attribute values and prevent attribute guessing attacks, ps13 , s23 q are applied to further re-randomize ciphertext components pct7 , ct8 q. FEME’s partially hidden access structure enhances decryption efficiency by revealing only attribute names while concealing values. This allows the receiver to pre-filter unmatched ciphertexts without computation. In Dec, the receiver checks whether the sender’s attribute names satisfy its policy and vice versa. If either check fails, decryption aborts with output K. Otherwise, full decryption proceeds to verify attribute values and padding integrity. The message is returned only if both policies are satisfied and the padding is valid; otherwise, K ensures ciphertext integrity. Theorem 1. FEME satisfies confidentiality under the Generic Group Model (GGM) by modeling the hash function H as a random oracle. Theorem 2. FEME satisfies anonymity under GGM by modeling the hash function H as a random oracle. Theorem 3. FEME satisfies authenticity under GGM by modeling the hash function H as a random oracle. The proofs of Theorems 1-3 are deferred to Appendix B. E. Comparative Advantages of FEME Table I compares the existing ME schemes in terms of expressiveness, security and privacy, and usability. Expressiveness. Both FEME and ACME [49] support monotonic Boolean formula-based access structures, unlike other schemes limited to identity-based matching. However, ACME’s small-universe design restricts it to a fixed attribute set and relies on binary vectors, leading to longer vectors and higher computational costs for expressive policies. FEME supports an unrestricted attribute universe, allowing any arbitrary string as an attribute. Security and Privacy. All schemes ensure data confidentiality. Francati et al. [30] provide an IBME without authenticity and another using NIZK for authenticity. Except for ACME, all schemes preserve attribute privacy or identity privacy. ACME reveals outer-layer public attributes due to its dual-layer design.

Usability. IBME [16], [25], [30], FBME [46], PSME [43], and CLME [48] require pre-registration pairing, where the sender must know the receiver’s identity or attributes beforehand. This tight coupling restricts flexible and real-time service discovery, as these schemes rely on identity-based or broadcast encryption. ACME [49] avoids such pairing but incurs extra overhead due to its dependence on anonymous credentials for sender authentication. In contrast, FEME eliminates both pre-registration pairing and external credential management by integrating sender authentication directly into ciphertexts, offering higher usability and scalability. In summary, FEME stands out as the only ME scheme that achieves expressive bilateral access control, robust security and privacy, and advantageous usability. V. P RI S RV + P ROTOCOL PriSrv+ is a private service discovery protocol that leverages FEME to enable privacy-preserving service broadcasts and mutual authentication between a service provider and a client. Building on its predecessor PriSrv [49], PriSrv+ replaces the core ACME scheme with FEME to eliminate the need for issuing, managing, and revoking credentials. The overall workflow of PriSrv+ is as follows. (1) During the system setup phase, a KGC generates the attribute encryption key, attribute decryption key, and policy decryption key for the service provider (S) and the client (C) according to the FEME scheme. Both parties require a complete set of encryption and decryption keys as they act as both sender and receiver during interactions. (2) During the broadcast phase, the service provider announces an encrypted broadcast message using FEME. This message includes a service policy (in the partially hidden structure), service details, the provider’s Diffie-Hellman (DH) public key, and a MAC key for authentication. Consider a private journalist network operated by an NGO as an example, where the provider’s policy is “(Journalist Type: Investigative AND Focus Area: Government Corruption AND Journalist Affiliation: Independent Media) OR (Role: Whistleblower AND Level: High Threat),” which is transformed to its partially hidden form “(Journalist Type AND Focus Area AND Journalist Affiliation) OR (Role AND Level)” in the broadcast. (3) In the service discovery phase, the client checks if its attribute names match the service policy and if the provider’s attribute names (included in the broadcast message) meet its own policy. For the same example, the client may set its connection policy as “(Network Type: Investigative AND Affiliation: NGO-Backed) OR (Jurisdiction: EU AND Support: Protection Available)”. If both checks pass, the client executes the FEME decrypt algorithm to verify whether the hidden attribute values of both parties satisfy those in each other’s policies. If it succeeds, the client generates a response, and sends a FEME encrypted reply with its policy in its partially hidden form (which is “(Network Type AND Affiliation) OR (Jurisdiction AND Support)” in the above example) and an authentication tag, including its DH public key and MAC key, back to the provider. (4) The service provider decrypts

and verifies the client’s response, then sends a confirmation message with an authentication tag to the client. (5) Both parties independently compute a shared session key using their respective DH secret keys, ensuring mutual authentication and maintaining privacy for both the client and the provider. A. Security and Threat Models of PriSrv+ Security Model. The security model of PriSrv+ follows that of PriSrv (Appendix C in full version) [49], which defines service discovery security and bilateral anonymity (i.e., both anonymity of service provider and anonymity of client). Service discovery security ensures privacy-preserving service advertisement and anonymous mutual authentication with bilateral policy control, protecting sessions from adversarial exposure. It maintains confidentiality and authentication, allowing only authorized clients and service providers to establish secure communications. The bilateral anonymity property implies that neither the PPT service provider nor the PPT client can learn anything about the other participant’s attribute values unless they satisfy each other’s access policies. Threat Model. Similar to PriSrv, PriSrv+ assumes a fully trusted Key Generation Center (KGC) for key distribution, which does not participate in service discovery. Service providers and clients are considered untrustworthy and may attempt to gain unauthorized information or disrupt the protocol. Malicious providers may impersonate the other providers, track clients, or inject forged ciphertexts. Malicious clients may impersonate users or launch excessive requests to overwhelm providers. The mitigation of excessive requests is further discussed in Section V-D. Following the Canetti-Krawczyk model for authenticated key exchange (AKE) [20], [21] and the service discovery model in [47], PriSrv+ considers a strong adversary capable of controlling public communications—eavesdropping, injecting, modifying, replaying, or interleaving messages across sessions. The adversary, which may be external, a rogue service provider, or a compromised client, can launch attacks including spoofing, impersonation, MitM, and DoS. Their goals include breaking authenticated key exchange and exposing sensitive information for tracking and inference. B. PriSrv+ Construction Fig. 6 presents the PriSrv+ protocol, comprising a privacypreserving service broadcast phase and an anonymous mutual authentication phase. Key differences from PriSrv (highlighted in blue) include: (1) PriSrv+ uses the sender’s encryption key EK for authentication, replacing PriSrv’s anonymous credentials; and (2) PriSrv+ adopts FEME for bilateral policy control, whereas PriSrv employs ACME. A unique broadcast identifier (bid) is assigned to each broadcast cycle, and a session identifier (sid) is assigned to each session. The broadcast cycle has a lifetime (e.g., 30 seconds), with the timestamp included in bid. Clients verify the timestamp upon decryption to ensure message freshness. Let FEME “ pSetup, EKGen, DKGen, PolGen, Enc, Decq be a FEME scheme, MAC “ pSetup, KeyGen, MAC, Verifyq

Privacy-preserving Service Broadcast Phase Service Provider S’s Broadcast: bid, CTB Ð F EME.EncpEKSs , As , MSGB q $

z λ where MSGB “ pbid||Z||ServiceT ype ||ServiceP ar ||Kc q, z Ð Ý Z˚ p , Z Ð h P G2 , Kc Ð MAC.KeyGenp1 q

Anonymous Mutual Authentication Phase Client (C) pEKSc , DKSc , SKAc q MSGB Ð F EME.DecpDKSc , SKAc , CTB q

Service Provider (S) pEKSs , DKSs , SKAs q

$

x1 P G , X Ð hx2 P G x1 , x2 Ð Ý Z˚ 1 2 2 p , X1 Ð g σc Ð MAC.MACpKc , Mc q where Mc “ p“C Ñ S”, bid, sid, X1 , X2 , Zq

Ks Ð MAC.KeyGenp1λ q CTc Ð F EME.EncpEKSc , Ac , MSGc q where MSGc “ pKs , Mc q

bid,sid,σ ,CT

c c ÝÝÝÝÝÝÝÝÝÝÝ ÝÝÝ ÝÝÑ

MSGc Ð F EME.DecpDKSs , SKAs , CTc q bc Ð MAC.VerifypKc , Mc , σc q If bc “ 0, abort; otherwise, $

y yÐ Ý Z˚ p , Y Ð g P G1 σs Ð MAC.MACpKs , Ms q

bs Ð MAC.VerifypKs , Ms , σs q If bs “ 0, abort; otherwise, SSKc,s Ð H̄pY x1 , Z x2 q

M ,σ

s ÐÝÝÝÝÝÝÝsÝÝÝ ÝÝÝÝÝÝ

where Ms “ p“S Ñ C”, bid, sid, X1 , X2 , Y, Zq SSKc,s Ð H̄pX1y , X2z q

Fig. 6: PriSrv+ Protocol

be a message authentication code (MAC) scheme, and H̄ : t0, 1u˚ Ñ K be a hash function where K represents the secret session key space. Service Broadcast Phase: To initiate a broadcast, S selects an access policy As that C should satisfy. S chooses $ an ephemeral Diffie-Hellman (DH) exponent z Ð Ý Z˚p and computes Z “ hz . It generates a MAC key Kc Ð MAC.KeyGenp1λ q. The broadcast message MSGB “ pbid||Z||ServiceT ype ||ServiceP ar ||Kc q includes the broadcast identifier, service type, parameters, and the MAC key. S encrypts it into a ciphertext CTB using FEME.Enc, and broadcasts bid and CTB publicly. Anonymous Mutual Authentication Phase: This phase establishes a session key (SSKc,s ) between C and S. (1) Client Response: C checks whether its attribute name set tni uiPrℓ2 s satisfies S’s policy pM, π, tnπpiq uiPrm1 s q, and whether S’s attribute name set tni uiPrℓ1 s satisfies C’s policy pA, ρ, tnρpiq uiPrm2 s q. If either test fails, C discards the broadcast ciphertext without decryption. Otherwise, C decrypts CTB using its decryption keys pDKSc , DKAc q. If the decryption succeeds, C generates DH values X1 “ g x1 $ and X2 “ hx2 , where x1 , x2 Ð Ý Z˚p . C then computes an authentication tag σc for the message Mc “ p“C Ñ S”, bid, sid, X1 , X2 , Zq using Kc from the broadcast message MSGB . C defines a policy Ac for S, encrypts its message MSGc “ pKs , Mc q to ciphertext CTc using F EME.Enc, and sends pbid, sid, σc , CTcq to S. (2) Service Provider Response: S decrypts C’s ciphertext, verifies σc , and generates its own DH value Y Ð g y using a $ random exponent y Ð Ý Z˚p . It creates a message Ms “ p“S Ñ C”, bid, sid, X1 , X2 , Y, Zq and a tag σs using the MAC key Ks from M SGc . S then computes a session key SSKc, s Ð H̄pX1y , X2z q and sends pMs , σs q to C. (3) Client Finalization: Upon receiving pMs , σs q, C verifies σs . If valid, C computes a session key SSKc,s Ð H̄pY x1 , Z x2 q using its secret DH exponents px1 , x2 q. As

X1y “ Y x1 “ g x1 y and X2z “ Z x2 “ hx2 z , both C and S derive the same session key SSKc,s . Theorem 4. Suppose that the DDH assumption holds, FEME is secure, MAC is unforgeable, and H is a random oracle, then PriSrv+ is a secure service discovery protocol and satisfies bilateral anonymity. Proof Sketch. The security proof of PriSrv+ in Theorem 4 parallels that of PriSrv, as the main distinction between the protocols lies in replacing ACME (in PriSrv) with FEME (in PriSrv+). The service discovery security is proved based on the confidentiality and authenticity of FEME in Theorems 1 and 3. The bilateral anonymity is proved based on FEME’s anonymity in Theorem 2. C. Comparative Advantages of PriSrv+ In Table I of [49], PriSrv is shown to be the only protocol among 10 SD protocols—including 7 standard ones (DNS-SD [14], mDNS [34], SSDP [27], UPnP [15], Wi-Fi [10], BLE [12], AirDrop [11]) and 3 privacy-preserving ones (PrivateDrop [31], CBN [22], WTSB [47])—that achieves both high privacy and usability. Rather than revisiting prior comparisons, we directly compare PriSrv+ with PriSrv in terms of expressiveness, security and privacy, and usability. Table II summarizes the results. In terms of expressiveness, PriSrv+ supports LSSS-defined policies with a large-universe construction, allowing any arbitrary string (e.g., a postal address) as an attribute. In contrast, PriSrv’s small-universe design restricts it to a fixed attribute set, requiring a full system rebuild to add new attributes. Moreover, PriSrv represents attributes as binary vectors (1 or 0), resulting in longer vectors and increased encryption/decryption overhead for broader attribute sets. In terms of security and privacy, both protocols provide similar privacy protections. However, PriSrv discloses public attributes and access policies in its outer layer due to its dual-layer design. PriSrv+ mitigates this exposure by using a partially hidden access structure that separates attribute names

Expressiveness Security and Privacy Usability Monotonic Arbitrary Large Privacy Mutual Bilateral Pub. Attri. No Pre-reg. No 3rd-party No In-advance Policy Attribute Universe Broadcast Authn. Anon. Hidden Pairing Dependence ID Issuance ‘ ‘ ‘ ‘ ‘ ‘ PriSrv [49] ˆ ˆ ˆ ˆ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ PriSrv+ Protocol

TABLE II: Comparison of Private Service Discovery Protocols with Bilateral Policy Control

from values, revealing only names during matching while keeping values confidential. In terms of usability, neither protocol requires pre-registered pairings or third-party support for service discovery. However, PriSrv depends on anonymous credential issuance, adding management overhead. PriSrv+ eliminates this requirement by directly leveraging the sender’s encryption key, simplifying deployment without compromising functionality. This comparison shows that PriSrv+ achieves greater expressiveness, improved security and privacy, and usability. D. Discussions Justifying Attribute Concealment in PriSrv+. Although PriSrv could be modified to conceal all attributes and policies within its inner layer, this would substantially increase overhead. Its dual-layer architecture relies on public attributes in the outer layer to efficiently filter mismatched services without decryption. Concealing all attributes would force clients to decrypt every broadcast, incurring significant latency. PriSrv+ addresses this limitation using FEME, which reveals only attribute names while concealing values. This preserves fast filtering and eliminates tracking risks, leading to up to 3.55× faster encryption and 6.23× faster decryption compared to PriSrv, even with its outer-layer filtering mechanism. Need for Expressive Attributes. Modern service discovery in IoT, smart cities, enterprise systems, and 5G networks requires expressive attributes—e.g., building names, project codes, or service categories—not supported by fixed identifier sets. PriSrv+ accommodates these scenarios through support for arbitrary string attributes, enabling fine-grained policy enforcement beyond traditional service discovery. Mitigating DoS Attacks. To resist Denial-of-Service (DoS) attacks from excessive attribute submissions, PriSrv+ can incorporate a flexible Proof-of-Work (PoW) mechanism. The service provider embeds a difficulty level in the broadcast identifier (bid), and clients must compute a session ID (sid) such that Hpbid, sid, σc , CTc q satisfies this level (e.g., number of leading zeros). This imposes minimal overhead on legitimate users and service providers while significantly raising the attack cost. Dynamic difficulty adjustment and complementary measures—such as attribute limits and request throttling—further enhance resilience without harming usability. VI. I MPLEMENTATION AND E VALUATION For a fair comparison, we used the same benchmarks, crypto library, elliptic curves, and parameters as PriSrv [49] when implementing PriSrv+ and PriSrv in C/C++. We utilized (i)

MIRACL library2 for FEME and PriSrv+ implementations, (ii) three elliptic curves, including MNT159 (80-bit security), MNT201 (90-bit security), and BN256 (100-bit security) to evaluate different security levels3 , (iii) SHA-256 for the the hash function, and (iv) MAC-GGM [24] for the MAC scheme. Our source code is available at [37]. A. Evaluation of FEME and ACME Table III presents the computation cost (comp.) and communication (comm.) cost of FEME and ACME for various algorithms on a desktop (Intel Core i9-7920X, 12 cores, 16GB RAM). The experimental setup ensures that FEME and ACME operate under equivalent conditions as used in [49], with the same attribute numbers and policies. For FEME, parameters are ℓ1 “ ℓ2 “ 4, m1 “ m2 “ 2, and I1 “ I2 “ 4, representing the sender’s and receiver’s attribute numbers, access matrix rows, and the number of attributes satisfying the access policy. ACME parameters are set similarly for comparability: n “ 10, ℓ1 “ ℓ2 “ 4, k “ 2, and I1 “ I2 “ 4, where n is the system’s total attribute number (which is fixed in the smalluniverse setting), and k is the number of access matrix rows. This alignment allows a fair comparison of both schemes.

Schemes

MNT159 MNT201 BN256 (80-bit Security) (90-bit Security) (100-bit Security) ACME FEME ACME FEME ACME FEME

Algorithms Setup EKGen DKGen PolGen Enc Dec

Computation Costs (ms) 20.526 8.411 26.882 9.699 33.344 35.451 8.124 41.365 9.393 48.485 21.630 4.150 18.640 3.836 15.750 359.807 2.998 327.796 3.026 237.675 146.931 19.660 167.337 20.302 187.822 123.772 20.109 188.346 28.832 231.214

Curves

11.402 10.031 4.787 3.697 18.275 27.283

Algo. Param. Communication Costs (KB) Setup |mpk| 1.044 0.344 1.332 0.428 4.128 1.071 Setup |msk| 1.2 0.065 1.36 0.074 1.6 0.083 EKGen |EK| 0.172 0.320 0.220 0.417 0.544 1.184 DKGen |DK| 0.86 0.235 1.1 0.306 2.72 0.912 PolGen |SK| 13.932 0.127 17.82 0.165 44.064 1.169 Enc |CT| 164.34 23.287 212.964 29.599 537.984 63.104

TABLE III: Performance of FEME and ACME (on Desktop) Table III shows that FEME’s computation (upper part) and communication costs (lower part) are substantially lower than ACME’s. While both schemes see performance declines as security levels increase from 80-bit to 100-bit, FEME’s advantage generally grows, except for DKGen and PolGen, where the performance gap narrows. 2 MIRACL: multiprecision integer and rational arithmetic c/c++ library. https://github.com/miracl/MIRACL. 3 Pairing-Friendly Curves. https://datatracker.ietf.org/doc/draft-irtf-cfr gpairing-friendly-curves.

Curves Costs Protocols

MNT159 (80-bit Security) Comp. (ms) Comm. (KB) PriSrv PriSrv+ PriSrv PriSrv+

MNT201 (90-bit Security) Comp. (ms) Comm. (KB) PriSrv PriSrv+ PriSrv PriSrv+

BN256 (100-bit Security) Comp. (ms) Comm. (KB) PriSrv PriSrv+ PriSrv PriSrv+

No. 1 2 3 4

Devices Desktop Laptop Phone Raspberry Pi

158.931 216.493 385.553 638.259

22.891 31.168 55.531 91.927

164.34 164.34 164.34 164.34

23.29 23.29 23.29 23.29

Privacy-preserving Service Broadcast 180.337 23.512 212.96 29.602 261.059 34.035 212.96 29.602 443.686 57.853 212.96 29.602 880.868 114.832 212.96 29.602

202.822 287.287 482.725 1188.392

20.674 29.281 49.202 121.139

537.98 537.98 537.98 537.98

63.107 63.107 63.107 63.107

No. 1 2 3 4

Devices Desktop Laptop Phone Raspberry Pi

429.282 576.161 727.572 1224.365

97.067 130.268 164.512 276.851

164.45 164.45 164.45 164.45

24.69 24.69 24.69 24.69

Anonymous Mutual Authentication 517.512 119.389 213.09 31.364 686.054 158.271 213.09 31.364 892.712 205.952 213.09 31.364 1832.187 422.671 213.09 31.364

673.039 854.177 972.163 2711.013

158.003 201.518 228.222 636.443

538.83 538.83 538.83 538.83

66.385 66.385 66.385 66.385

TABLE IV: Performance of PriSrv+ and PriSrv (on Four Platforms) In Setup, ACME’s computation cost is pn`3qk 2 ¨exp1 `k ¨ expT , while FEME’s is only 3 exp2 `2 expT , where exp1 , exp2 , and expT represent the exponentiation costs in G1 , G2 , and GT , respectively. ACME averages 26.917 ms for system setup, whereas FEME takes 9.837 ms, making it 1.74ˆ faster. FEME also reduces the sizes of the master public key and master private key by 71.68% and 94.66%, respectively. In EKGen, FEME’s time cost is pl1 ` 2q exp1 `2 exp2 , while ACME’s time cost is pn ` 2q exp1 `7 exp2 `2 pair, where pair is the computation time for a bilinear pairing operation. FEME averages 9.183 ms versus ACME’s 41.767 ms, making it 3.55ˆ faster, though FEME’s EK size is larger at 0.640 KB compared to ACME’s 0.312 KB. In DKGen and PolGen, FEME shows significant improvements: DKGen time drops from 18.673 ms to 4.258 ms, and PolGen time from 308.426 ms to 3.240 ms, achieving 3.39ˆ and 94.19ˆ speedups, respectively. FEME’s DK and SK sizes are also reduced by 68.97% and 98.07%, respectively. FEME’s Enc and Dec are 7.62ˆ and 6.23ˆ faster than ACME’s, with times reduced from 167.383 ms to 19.412 ms and from 181.111 ms to 25.041 ms, respectively. Additionally, FEME’s ciphertext size |CT| is 87.33% smaller on average. Overall, FEME significantly outperforms ACME, except in the |EK| size of EKGen. B. Evaluation of PriSrv+ and PriSrv To comprehensively evaluate PriSrv+ and PriSrv [49], we conducted tests on four platforms (Table IV) using the same parameters as Table III across three elliptic curves. The platforms include a desktop (Intel Core i9-7920X), a laptop (Intel Core i5-10210U), a smartphone (ARM Cortex @2.4GHz), and a Raspberry Pi (ARM Cortex @1.5GHz), covering both highperformance and mobile environments relevant to wireless service discovery. PriSrv+ consistently outperforms PriSrv in computation overhead. In the broadcast phase (upper Table IV), PriSrv+ averages 54.336 ms across platforms, compared to PriSrv’s 443.868 ms—7.17ˆ faster. In the mutual authentication phase (lower Table), PriSrv+ averages 233.181 ms vs. PriSrv’s 1008.02 ms, achieving a 3.32ˆ improvement. The total computation time of PriSrv+ is 287.517 ms, well under one second

and perceived as an “immediate response” [31], [49], while PriSrv takes 1451.88 ms, making PriSrv+ 4.05ˆ faster overall. Table IV indicates similar communication costs between the two phases within each protocol, dominated by the ciphertext size. FEME’s efficiency results in PriSrv+ reducing broadcast phase communication by 87.33% and authentication phase by 86.64% compared to PriSrv on average.

(a) Computation Overheads

(b) Communication Overheads

Fig. 7: Comparison of PriSrv+ and PriSrv We implemented two protocols in a real-world wireless environment using an open-source Wi-Fi Alliance project [10] supporting IEEE 802.1X, with wpa supplicant for the client and hostapd for the service provider. Experiments were run on two laptops using BN256. Fig. 7(a) compares the computation costs of PriSrv+ and PriSrv under complex policies with more attributes. Bars show PriSrv+’s broadcast time (TB ), server time (TS ), and client time (TC ) in the anonymous authentication phase; symbols represent the same for PriSrv. We vary the number of attributes (top x-axis) and policy share number (bottom x-axis), where the latter reflects the number of shares required to reconstruct a secret [18] (i.e., the edge number in an equivalent access tree). Both protocols are tested with identical attribute and policy sizes to ensure fairness.

In Fig. 7(a), we vary the attribute number between t25, 50u and the share number of the access policy among t3, 7, 11, 13, 17, 21, 27u to test performance with expressive policies. PriSrv+ shows significantly lower computation times than PriSrv. Average times for PriSrv+ are TB = 0.252 s, TS = 0.166 s, and TC = 0.592 s, while for PriSrv, TB = 2.478 s, TS = 0.374 s, and TC = 2.853 s, making PriSrv+ 8.83ˆ, 1.25ˆ, and 3.82ˆ faster, respectively. Fig. 7(b) shows communication overheads using the same parameters as Fig. 7(a). Bars indicate PriSrv+ broadcast and the service provider’s/client’s authentication overheads (|Broadcast|, |Server|, |Client|), with PriSrv shown as symbols. The server’s communication cost during the authentication phase is constant and identical for both protocols at |Server| = 0.82 KB. PriSrv+ has average communication costs of |Broadcast| = 79.623 KB and |Client| = 83.64 KB, while PriSrv averages |Broadcast| = 677.488 KB and |Client| = 681.505 KB. PriSrv+ reduces these costs by 88.25% and 87.73%, respectively, compared to PriSrv. The evaluation shows that PriSrv+ is notably more efficient than PriSrv in computation and communication costs. Optimized Efficiency and Scalability. PriSrv+ ensures computational efficiency with overhead growing proportionally to the attribute number, consistent with standard ABE schemes. Unlike conventional ABE systems that suffer from performance degradation with flexible attributes, PriSrv+ supports an unrestricted attribute universe with minimal overhead. Experiments show up to 7.17ˆ faster service broadcasts and 3.32ˆ faster mutual authentication than PriSrv, even with complex policies. These gains result from encryption and decryption optimizations, enabling expressive attribute matching while maintaining real-time performance in wireless networks.

and PDU Segmentation, if the payload exceeds BLE’s limit, it is segmented into multiple PDUs and reassembled by the receiver. PriSrv+ achieves an average 87.73% reduction for clients compared to PriSrv, enabling efficient segmentation and limited fragmentation. Privacy-Enhanced EAP. PriSrv+ enhances privacy in EAP by integrating encrypted broadcasts and responses. An access point (AP) acts as a pass-through for interactions between the client and service provider. The provider broadcasts privacypreserving service information, including a broadcast identifier and FEME-generated ciphertext, matching EAP’s initial authentication request. A successful decryption by the client prompts an encrypted reply, which the provider decrypts and then responds with an authentication tag containing DH shares and a MAC. The client verifies the tag, computes a secret session key, and signals success, while the provider computes the same key for a secure session. EAP messages are then encapsulated in EAPOL frames and sent as RADIUS packets. Compared to PriSrv, PriSrv+ reduces communication costs by 86.64% during mutual authentication. Privacy-Enhanced Apple AirDrop. AirDrop uses BLE to broadcast a hashed service provider identity for detecting nearby clients, followed by a TLS handshake that exposes identities via cleartext certificate exchange. Using the PrivateDrop mechanism [31], PriSrv+ improves privacy by preventing the transmission of service provider identifiers during BLE advertising and encrypting both parties’ certificates with FEME at the start of the TLS handshake. Apple may act as a key generation center, producing the necessary secret keys alongside existing iCloud certificates. VII. L IMITATIONS AND F UTURE W ORK

C. Interoperability PriSrv+ is an enhanced version of PriSrv, improving expressiveness, privacy, and usability. Like PriSrv, it is interoperable with existing SD protocols like mDNS, BLE, EAP, AirDrop. Integration Approaches. PriSrv+ can be integrated through two approaches. The first places PriSrv+ at the application layer, allowing it to work with existing lower-layer protocols. If the payload exceeds protocol limits, the lower layers handle segmentation and reassembly without altering PriSrv+’s logic. The second replaces lower-layer protocols with PriSrv+, requiring specific adaptations. We illustrate the first approach using mDNS and BLE, and the second with EAP and AirDrop. Privacy-Enhanced mDNS and BLE. PriSrv+ can integrate into the Vanadium framework [13] to develop privacyenhanced mDNS and BLE. Vanadium provides service discovery APIs for protocols like mDNS [34] and BLE [12]. mDNS, often paired with DNS-SD [14], supports additional attributes in TXT records (up to 65,535 bytes). PriSrv+ broadcasts pbid, CTB q using 64,622 bytes on BN256 within a single TXT record, whereas PriSrv requires nine TXT records (to transmit 531,996 bytes), reducing the mDNS packet size by 88.89%. BLE’s standard 31-byte payload challenges the transmission of large ciphertexts. Using the BLE Attribute Protocol (ATT)

While PriSrv+ introduces notable advancements in private service discovery, certain limitations remain. Trusted Authority for Attribute Assignment. Although PriSrv+ eliminates credential issuance and revocation burdens of PriSrv, it still depends on a trusted authority for attribute assignment during registration—a common but centralized assumption in ABE systems. Future work could explore decentralized alternatives to reduce this trust dependency. Revocation Mechanism. PriSrv+ does not include an integrated revocation scheme, but it can adopt existing ABE-based approaches such as key updates, attribute expiration, proxy re-encryption, and server-assisted revocation. Future research may focus on lightweight, scalable revocation strategies suited to dynamic service discovery settings. Mitigating Client Abuse. Strong anonymity in PriSrv+ may allow clients to misuse services. Although not addressed natively, PriSrv+ can incorporate ABE-based traitor tracing techniques, such as embedding user-specific identifiers in keys or using traceable ciphertexts. Key-insulated architectures and dynamic revocation can further mitigate abuse. Future work should explore integrating such accountability mechanisms without compromising user privacy.

VIII. C ONCLUSION

R EFERENCES

PriSrv+ significantly advances privacy-preserving service discovery in wireless networks by introducing Fast and Expressive Matchmaking Encryption (FEME). It overcomes the limitations of prior schemes by enabling expressive bilateral access control while enhancing efficiency, security, privacy, and usability. Evaluations demonstrate notable gains in performance and reduced communication overhead, making it wellsuited for resource-constrained devices. With formal security guarantees and compatibility with existing wireless protocols, PriSrv+ effectively meets the privacy and security demands of wireless service discovery environments.

[1] ISO/IEC 29115:2013 - Entity authentication assurance framework. 2013. [2] OECD Guidelines on the Protection of Privacy and Transborder Flows of Personal Data. 2013. [3] Regulation (EU) 2016/679 - General Data Protection Regulation (GDPR). 2016. [4] NIST Special Publication 800-63B - Digital Identity Guidelines. 2017. [5] ETSI TS 103 465 V1.1.1 - Cyber Security for IoT. 2019. [6] ETSI EN 303 645 V2.1.1 - Cyber Security for Consumer IoT. 2020. [7] ISO/IEC 29184:2020 - Online privacy notices and consent. 2020. [8] NIST Privacy Framework: A Tool for Improving Privacy Through Enterprise Risk Management. 2020. [9] NIST Special Publication 800-53 - Security and Privacy Controls for Federal Information Systems. 2020. [10] Wi-fi. https://w1.fi, 2023. [11] Airdrop. https://support.apple.com/en-us/HT204144, 2024. [12] Bluetooth. https://www.bluetooth.com, 2024. [13] Vanadium. https://vanadium.github.io/, 2024. [14] DNS-SD. RFC 6763. Dns-based service discovery, 2013. [15] UPnP. RFC 6970. Universal plug and play (upnp) internet gateway device - port control protocol interworking function, 2013. [16] Giuseppe Ateniese, Danilo Francati, David Nunez, and Daniele Venturi. Match me if you can: Matchmaking encryption and its applications. In CRYPTO, 2019. [17] Xiaolong Bai, Luyi Xing, Nan Zhang, XiaoFeng Wang, Xiaojing Liao, Tongxin Li, and Shi-Min Hu. Staying secure and unprepared: understanding and mitigating the security risks of apple zeroconf. In IEEE S&P, 2016. [18] Amos Beimel. Secure schemes for secret sharing and key distribution. PhD thesis, Israel Institute of Technology, Technion, 1996. [19] John Bethencourt, Amit Sahai, and Brent Waters. Ciphertext-policy attribute-based encryption. In IEEE S&P, 2007. [20] Ran Canetti and Hugo Krawczyk. Analysis of key-exchange protocols and their use for building secure channels. In EUROCRYPT, pages 453– 474. Springer, 2001. [21] Ran Canetti and Hugo Krawczyk. Security analysis of ike’s signaturebased key-exchange protocol. In CRYPTO, pages 143–161. Springer, 2002. [22] Aldo Cassola, Erik-Oliver Blass, and Guevara Noubir. Authenticating privately over public wi-fi hotspots. In CCS, 2015. [23] Melissa Chase. Multi-authority attribute based encryption. In Theory of cryptography conference, pages 515–534. Springer, 2007. [24] Melissa Chase, Sarah Meiklejohn, and Greg Zaverucha. Algebraic macs and keyed-verification anonymous credentials. In CCS, 2014. [25] Jie Chen, Yu Li, Jinming Wen, and Jian Weng. Identity-based matchmaking encryption from standard assumptions. In ASIACRYPT. Springer, 2022. [26] A. Cooper and H. Tschofenig. Privacy Considerations for Internet Protocols. RFC 6973, 2013. [27] SSDP. IETF draft-cai-ssdp-v1 03. Simple service discovery protocol/1.0 operating without on arbiter, 1999. [28] S. Farrell and H. Tschofenig. Pervasive Monitoring Is an Attack. RFC 7258, 2014. [29] Kassem Fawaz, Kyu-Han Kim, and Kang G Shin. Protecting privacy of ble device users. In USENIX Security, 2016. [30] Danilo Francati, Alessio Guidi, Luigi Russo, and Daniele Venturi. Identity-based matchmaking encryption without random oracles. INDOCRYPT, 2021. [31] Alexander Heinrich, Matthias Hollick, Thomas Schneider, Milan Stute, and Christian Weinert. Privatedrop: Practical privacy-preserving authentication for apple airdrop. In USENIX Security, 2021. [32] Bastian Könings, Christoph Bachmaier, Florian Schaub, and Michael Weber. Device names in the wild: Investigating privacy risks of zero configuration networking. In MDM, 2013. [33] Junzuo Lai, Robert H Deng, and Yingjiu Li. Expressive cp-abe with partially hidden access structures. In Proceedings of the 7th ACM symposium on information, computer and communications security, pages 18–19, 2012. [34] mDNS. RFC 6762. Multicast dns, 2013. [35] Long Meng, Liqun Chen, Yangguang Tian, and Mark Manulis. Fabesa: Fast (and anonymous) attribute-based encryption under standard assumption. In CCS, pages 4688–4702, 2024.

ACKNOWLEDGMENT The authors thank the anonymous reviewers for their valuable comments and insightful suggestions. This research is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority under its Trust Tech Funding Initiative, AXA Research Fund, National Natural Science Foundation of China (No. 62372110, 62332007, U22B2028), Fujian Provincial Natural Science of Foundation (No. 2023J02008), Lee Kong Chian Chair Professorship, University of Oregon School of Law, Consumer Protection Research Grant 2025-2026 (under Grant No. 4236D0), National Science Foundation (No. 2112471), Werner Siemens-Stiftung (WSS) as part of the Centre for Cyber Trust (CEYT), Science and Technology Major Project of Tibetan Autonomous Region of China (No. XZ202201ZD0006G), Open Research Fund of Machine Learning and Cyber Security Interdiscipline Research Engineering Center of Jiangsu Province (No. SDGC2131), National Joint Engineering Research Center of Network Security Detection and Protection Technology, Guangdong Key Laboratory of Data Security and Privacy Preserving, Guangdong Hong Kong Joint Laboratory for Data Security and Privacy Protection, and Engineering Research Center of Trustworthy AI, Ministry of Education. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore and Infocomm Media Development Authority. E THICS C ONSIDERATIONS This work presents PriSrv+, a cryptographic protocol for privacy-preserving service discovery. It does not involve human subjects, real-world deployments, or personal data—only synthetic datasets and simulated attributes were used. PriSrv+ is designed to enhance user privacy and prevent tracking and profiling attacks, without introducing or exploiting system vulnerabilities. All cryptographic techniques follow established models, and no responsible disclosure was required. We conducted this research in accordance with ethical principles outlined in the Menlo Report and believe it contributes positively to secure communications.

[36] Long Meng, Liqun Chen, Yangguang Tian, Mark Manulis, and Suhui Liu. Fease: Fast and expressive asymmetric searchable encryption. In USENIX Security 24, pages 2545–2562, 2024. [37] PriSrv+. https://github.com/PriSrv-Plus, 2025. [38] Doreen Riepel and Hoeteck Wee. Fabeo: Fast attribute-based encryption with optimal security. In CCS, 2022. [39] Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 1980. [40] Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, 1997. [41] Milan Stute, Alexander Heinrich, Jannik Lorenz, and Matthias Hollick. Disrupting continuity of apple’s wireless ccosystem security: new tracking, dos, and mitm attacks on ios and macos through bluetooth low energy, awdl, and wi-fi. In USENIX Security, 2021. [42] Milan Stute, Sashank Narain, Alex Mariotto, Alexander Heinrich, David Kreitschmann, Guevara Noubir, and Matthias Hollick. A billion open interfaces for eve and mallory: Mitm, dos, and tracking attacks on ios and macos through apple wireless direct link. In USENIX Security, 2019. [43] Jianfei Sun, Guowen Xu, Tianwei Zhang, Xuehuan Yang, Mamoun Alazab, and Robert H Deng. Privacy-aware and security-enhanced efficient matchmaking encryption. IEEE TIFS, 2023. [44] Raghav H Venkatnarayan, Muhammad Shahzad, Sangki Yun, Christina Vlachou, and Kyu-Han Kim. Leveraging polarization of wifi signals to simultaneously track multiple people. In IMWUT, 2020. [45] Xueqiang Wang, Yuqiong Sun, Susanta Nanda, and XiaoFeng Wang. Looking from the mirror: Evaluating iot device security through mobile companion apps. In USENIX Security, 2019. [46] Axin Wu, Weiqi Luo, Jian Weng, Anjia Yang, and Jinghang Wen. Fuzzy identity-based matchmaking encryption and its application. IEEE TIFS, 2023. [47] David J Wu, Ankur Taly, Asim Shankar, and Dan Boneh. Privacy, discovery, and authentication for the internet of things. In ESORICS, 2016. [48] Ningbin Yang, Chunming Tang, and Debiao He. A lightweight certificateless multi-user matchmaking encryption for mobile devices: Enhancing security and performance. IEEE TIFS, 2023. [49] Yang Yang, Robert H Deng, Guomin Yang, Yingjiu Li, HweeHwa Pang, Minming Huang, Rui Shi, and Jian Weng. Prisrv: Privacy-enhanced and highly usable service discovery in wireless communications. In NDSS, 2024. https://dx.doi.org/10.14722/ndss.2024.24174, https://eprint.iacr. org/2024/1783 (Full version). [50] Wei Zhou, Yan Jia, Yao Yao, Lipeng Zhu, Le Guan, Yuhang Mao, Peng Liu, and Yuqing Zhang. Discovering and understanding the security hazards in the interactions between iot devices, mobile apps, and clouds on smart home platforms. In USENIX Security, 2019. [51] Richard Zippel. Probabilistic algorithms for sparse polynomials. In ISSAC, 1979.

A PPENDIX A S ECURITY M ODEL OF FEME The security models for FEME outline its confidentiality, anonymity, and authenticity properties. Confidentiality ensures that no probabilistic polynomial-time (PPT) adversary can distinguish between two challenge messages encrypted under a target attribute set and policy, even with access to all the key generation oracles, with a restriction that the decryption keys for the target attribute set and policy have not been queried. Anonymity guarantees that no PPT adversary, who outputs two target attribute sets and policies, can distinguish which attribute set or policy was used by the challenger to create a ciphertext, even with access to all the key generation oracles, with a restriction that the decryption keys for the two target attribute sets and policies have not been queried. Authenticity ensures that an adversary cannot forge a valid ciphertext capable of passing decryption without possessing an attribute encryption key with attributes that satisfy the

target access policy, even with access to all the key generation oracles. Definition 3. A FEME scheme F EME satisfies confidentiality if for any PPT adversary A “ pA1 , A2 q, there exists a def negligible function ν such that Advconf F EME pλq “ »

fi $ pmpk, mskq Ð Setupp1λ q, b Ð Ý t0, 1u ˚ ˚ ˚ — ffi pmsg˚ 0 , msg1 , Ssnd , Asnd q — ffi O1 ,O2 ,O3 — 1 Ð A1 pmpkq ffi Pr —b “ b ffi — ffi $ ˚ – fl CT˚ Ð Ý EncpEK , A , msg q ˚ snd b snd S snd

b1 Ð A2O1 ,O2 ,O3 pCT˚ snd q

ď νpλq, where oracles O1 , O2 , O3 are implemented by EKGen pmsk, ¨q, DKGenpmsk, ¨q, PolGenpmsk, ¨q, respectively. It is required that O2 and O3 are not queried for ˚ attributes and policies that can satisfy pSsnd , A˚snd q. Definition 4. A FEME scheme F EME satisfies anonymity if for any PPT adversary A “ pA1 , A2 q, there exists a negligible def function ν such that Advanon F EME pλq “ fi $ pmpk, mskq Ð Setupp1λ q, b Ð Ý t0, 1u ˚ ˚ ˚ ffi — pmsg˚ , Ssnd , Ssnd , A˚ snd0 , Asnd1 q ffi — 0 1 O1 ,O2 ,O3 — 1 Ð A1 pmpkq ffi Pr —b “ b ffi ffi — $ ˚ fl – CT˚ , msg q Ð Ý EncpEK , A ˚ snd b snd S »

snd

b1 Ð A2O1 ,O2 ,O3 pCT˚ snd q

ď νpλq, where oracles O1 , O2 , O3 are implemented by EKGen pmsk, ¨q, DKGenpmsk, ¨q, PolGenpmsk, ¨q, respectively. It is required that O2 and O3 are not queried for attributes and policies that can ˚ ˚ satisfy pSsnd , A˚snd0 q or pSsnd , A˚snd1 q, where 0 1 ˚ ˚ “ tni , vi,1 uiPrℓ1 s , Ssnd0 “ tni , vi,0 uiPrℓ1 s , Ssnd1 A˚snd0 “ pM, π, Ψπpiq,0 “ tnπpiq , vπpiq,0 uiPrm1 s q, and A˚snd1 “ pM, π, Ψπpiq,1 “ tnπpiq , vπpiq,1 uiPrm1 s q. Definition 5. A FEME scheme F EME satisfies authenticity if for any PPT adversary A, there exists a negligible function def ν such that Advauth F EME pλq “ fi pmpk, mskq Ð Setupp1λ q O ,O ,O — pCTsnd , Arcv , Srcv q Ð A 1 2 3 pmpkq ffi — ffi — DKSrcv Ð DKGenpmsk, Srcv q ffi Pr — ffi — SKArcv Ð PolGenpmsk, Arcv q ffi – msg “ DecpDK , SK , CT q fl Srcv Arcv Źsnd @Ssnd P QO1 : pSsnd ­|ù Arcv q pmsg ‰ Kq »

ď νpλq, where oracles O1 , O2 , O3 are implemented by EKGenpmsk, ¨q, DKGenpmsk, ¨q, PolGenpmsk, ¨q, and S ­|ù A denotes that attributes S does not satisfy A. A PPENDIX B S ECURITY P ROOFS OF FEME Generic Group Model (GGM). We use an extended GGM for bilinear groups, as outlined in [40]. This model includes three random encodings σ1 , σ2 , and σT for the additive group Zq . These encodings are injective mappings σ1 , σ2 , σT : Zq Ñ t0, 1um , where m ą 3 logpqq. The probability that an adversary A can guess an element within the image of σ1 , σ2 , or σT is negligible. For i “ 1, 2, T , we define the sets

1

κ

ti

ti τ

ti r

ti s2

x`κτ

κλi `tπ s3

ti τ1 s3

px`κτ1qs3

µ

µκ

µti

µti τ

µti r

µti s2

µpx`κτq

µpκλi `tπ s3q

µti τ1 s3

µpx`κτ1qs3

b1

b1 κ

b 1 ti

b1 ti τ

b 1 ti r

b1 ti s2

b1 px`κτq

b1 pκλi `tπ s3q

b1 ti τ1 s3

b1 px`κτ1qs3

1 pλ `t r 1q ρ b1 i µ pλ `tρ r 1q b1 i λi `tρ r 1

1 pκψ `t r 1q ρ i b1 µ pκψi `tρ r 1q b1 pκψi `tρ r 1q

1 pκψ `t r 1q ρ i b2 µ pκψi `tρ r 1q b2 b1 pκψi `tρ r 1q b2 –

b2 pκψi `tρ r 1q b1 r pλ `t r 1q r pκψ `t r 1q r pκψ `t r 1q ρ ρ ρ i i i b2 b1 b2 r 1 pλ `t r 1q r 1 pκψ `t r 1q r 1 pκψ `t r 1q r1 r1 κ r 1 ti r 1 ti τ ti rr 1 r 1 ti s2 r 1 px`κτq r 1 pκλi `tπ s3q r 1 ti τ1 s3 r 1 px`κτ1qs3 ρ ρ ρ i i b2 i b1 b2 s1 s1 s1 s1 s1 κ s 1 t i s1 t i τ s1 ti r s1 ti s2 s1 px`κτq s1 pκλi `tπ s3q s1 ti τ1 s3 s1 px`κτ1qs3 pλ `tρ r 1q pκψi `tρ r 1q pκψi `tρ r 1q b2 i b1 b2 s3 s3 s3 s3 s3 κ s 3 t i s3 t i τ s3 ti r s3 ti s2 s3 px`κτq s3 pκλi `tπ s3q ti τ1 s2 px`κτ1qs2 pλ `tρ r 1q pκψi `tρ r 1q pκψi `tρ r 1q 3 3 b2 i b1 b2 b1 τ b1 τ 1 1 b1 τ b1 τ κ b1 τ ti b1 τ ti τ b1 τ ti r b1 τ ti s2 px`κτq b1 τ pκλi `tπ s3q b1 τ ti τ1 s3 b1 τ px`κτ1qs3 pλi `tρ r q τ pκψi `tρ r q pκψi `tρ r 1q b2 b2 b2 τ b2 τ b2 τ b2 τ κ b2 τ ti b2 τ ti τ b2 τ ti r b2 τ ti s2 px`κτq b2 τ pκλi `tπ s3q b2 τ ti τ1 s3 b2 τ px`κτ1qs3 pλi `tρ r 1q – pκψi `tρ r 1q – b1 b1 b1 s12 b1 s12 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b 1 s2 b1 s2 κb1 s2 ti b1 s2 ti τ b1 s2 ti rb1 s2 ti s2 b1 s2 px`κτqb1 s2 pκλi `tπ s3qb1 s2 ti τ1 s3 b1 s2 px`κτ1qs3 s2 pλi `tρ r q pλi `tρ r q s2 pκψi `tρ r q pκψi `tρ r 1q b2 b2 b 2 s2 b2 s2 2 2 2 2 2 2 2 2 2 2 1 2 1 1 2 2 2 b2 s2 b2 s2 κb2 s2 ti b2 s2 ti τ b2 s2 ti rb2 s2 ti s2 b2 s2 px`κτqb2 s2 pκλi `tπ s3qb2 s2 ti τ1 s3 b2 s2 px`κτ1qs3 pλi `tρ r q s2 pλi `tρ r q pκψi `tρ r q s2 pκψi `tρ r 1q b1 b1 α`κr pκψ `t r 1q α`κr pλ `t r 1q α`κr pα`κrqκ pα`κrqti τ pα`κrqti s2 pα`κrqpκλi `tπ s3q pα`κrq¨ ρ ρ i i b1 b1 α`κr pλ `t r 1q α`κr pκψ `t r 1q α pα`κrqti pα`κrqti r pα`κrqpx`κτq pα`κrqti τ1 s3 px`κτ1qs3 ρ ρ i i b2 b2 b1 τ1 s13 b1 τ1 s13 κ b1 τ1 s13 ti τ b1 τ1 s13 ti s2 b1 τ1 s13 pκλi `tπ s3q b1 τ1 s13 ¨ τ1 s13 pλi `tρ r 1q τ1 s13 pκψi `tρ r 1q b1 τ1 s13 b1 τ1 s13 2 s1 t s xµ b1 τ1 s13 ti b1 τ1 s13 ti r b1 τ1 s13 px`κτq b1 τ1 px`κτ1qs3 pλi `tρ r 1q pκψi `tρ r 1q 3 i 3 b2 b2 2 2 b τ s b 2 1 3 pλ `t r 1q 2 τ1 s3 pκψ `t r 1q 2κ 2t τ 2t s 2 pκλ `t s q 2¨ b2 τ1 s2 b τ s b τ s b τ s b τ s b τ s π 3 ρ ρ 2 1 3 2 1 3 i 2 1 3 i 2 2 1 3 2 1 3 i i i 3 b1 b1 1 1 αs`xµs3 b2 τ1 s2 b2 τ1 s2 b2 τ1 s2 b 2 τ 1 s2 px`κτ1qs3 τ 1 s2 τ1 s2 3 ti 3 ti r 3 px`κτq 3 ti τ1 s3 3 pλi `tρ r q 3 pκψi `tρ r q b2

b2 κ

b 2 ti

b2 ti τ

b 2 ti r

b2 ti s2

b2 px`κτq

b2 pκλi `tπ s3q

b2 ti τ1 s3

b2 px`κτ1qs3

r

rκ

rti

rti τ

ti r 2

rti s2

rpx`κτq

rpκλi `tπ s3q

rti τ1 s3

rpx`κτ1qs3

b2 pλ `tρ r 1q b1 i r pλ `t r 1q ρ b1 i r 1 pλ `t r 1q ρ b1 i s1 pλ `tρ r 1q b1 i s3 pλ `tρ r 1q b1 i τ pλi `tρ r 1q

1 pλ `t r 1q ρ b2 i µ pλ `tρ r 1q b2 i b1 pλ `tρ r 1q b2 i –

TABLE V: Pairing elements in GT for the confidentiality (anonymity) proof of FEME (tπ denotes tπpiq , and tρ denotes tρpiq )

Gi “ σi pxq : x P Zp . The model provides oracles to compute group operations on G1 , G2 , and GT , as well as an oracle for a bilinear map e : G1 ˆ G2 Ñ GT . Random Oracle. The challenger C maintains a list LH containing entries of the form pui , hi , ti q, which starts out empty. When the adversary A queries the oracle with an attribute ui “ pni , vi q, the challenger checks whether a tuple with ui already exists in LH . If such a tuple is found, C responds with Hpui q “ hi P G1 . If no match is found, C $ selects a random value ti Ð Z˚p , computes hi “ g1ti P G1 , returns Hpui q “ hi , and adds the tuple pui , hi , ti q to LH . A. Proof of Theorem 1 (FEME: Confidentiality) Proof. Our proof close follows the proof structure in [19]. We start with a standard observation derived from a basic hybrid argument. In the confidentiality game, C generates a challenge ciphertext with a component ct0 , which is either ĤpV q ‘ ϕpmsg˚0 q or ĤpV q ‘ ϕpmsg˚1 q, where V “ epg1 , g2 qαs`xµs3 and s “ s1 ` s2 . Alternatively, We consider a modified game where V is either epg1 , g2 qαs`xµs3 or epg1 , g2 qθ , with θ randomly chosen from Z˚p . We show that the adversary A1 in the original game can be reduced to an adversary A2 in the modified game. Since no A2 has a non-negligible advantage, it implies that A1 cannot either. Given that A1 has an advantage ϵ in the original game, we can construct A2 as follows. During the challenge phase, after receiving msg0 and msg1 from A1 and V (which is either V p1q “ epg1 , g2 qαs`xµs3 or V p2q “ epg1 , g2 qθ from the challenger C, A2 flips a coin β P t0, 1u and sends ĤpV q ‘ ϕpmsgβ q to A1 . Once A1 outputs a bit β 1 , A2 outputs 1 if β 1 “ β, or 0 otherwise. If V “ V p1q “ epg1 , g2 qαs`xµs3 , the challenge is a wellformed FEME ciphertext, and A1 has an advantage ϵ in correctly guessing β 1 “ β. If V “ V p2q “ epg1 , g2 qθ , the

challenge becomes independent of msg0 and msg1 , giving A2 an advantage of 0. Consequently, we have PrrA2 wins

“

PrrV “ V p1q s ¨ Prrβ 1 “ β|V p1q s

ď

`PrrV “ V p2q s ¨ Prrβ 1 “ β|V “ V p2q s 1{2 ¨ p1{2 ` ϵq ` 1{2 ¨ 1{2 “ 1{2 ` ϵ{2,

and the overall advantage of A2 is ϵ{2. The existence of any successful A1 implies the existence of a corresponding A2 with a non-negligible advantage. Finally, we prove that no such A2 can distinguish between epg1 , g2 qαs`xµs3 and epg1 , g2 qθ in polynomial time. The combination of these results shows that no A1 can have a nonnegligible advantage. Simulation of the Modified Game. Let g1 “ σ1 p1q, g2 “ σ2 p1q and epg1 , g2 q “ σT p1q. We write g1x to denote σ1 pxq, g2y to denote σ2 pyq and epg1 , g2 qz to denote σT pzq. $ ˚ ‚ Setup. The challenger C chooses α, x, µ, b1 , b2 , κ Ð Zp , µ α xµ and calculates Z “ epg1 , g2 q , Y “ epg1 , g2 q , δ0 “ g2 , δ1 “ g2b1 , δ2 “ g2b2 and h “ g1κ . C sends the master public key mpk “ pZ, Y, h, δ0 , δ1 , δ2 q to A. ‚ Phase 1. In phase 1, A can make oracle queries to the random oracle and a key generation oracle as follows. ´ Random oracle pOH q. Same as defined above. ´ Attribute encryption key generation oracle pOEKGen q. When $ A makes a key query for an attribute set Ssnd , C picks τ Ð Z˚p . Then, C computes ek1,i “ g1ti τ , ek2 “ g2b1 τ , ek3 “ g2b2 τ , ek4 “ g1x`κτ .

Then, C sends to A the attribute encryption key EKSsnd “ ptni uiPrℓ1 s , tek1,i uiPrℓ1 s , ek2 , ek3 , ek4 q. ´ Attribute decryption key generation oracle pODKGen q. When $ A makes a key query for an attribute set Srcv , C picks r Ð Z˚p . Then, C generates the attribute decryption key as dk1 “ g1α`κr , dk2,i “ g1ti r , dk3 “ g2r .

Then, C sends to A the attribute decryption key DKSrcv “ ptni uiPrℓ2 s , dk1 , tdk2,i uiPrℓ2 s , dk3 q. ´ Policy decryption key generation oracle pOPolGen q. When A makes a key query for a policy Arcv “ pA, ρ, tΨρpiq uiPrm2 s q, C $

$

2 ´1 picks r1 Ð Z˚p and a vector y Ð Zm . Let λi “ Ai pα||yqJ p J and ψi “ Ai pµ||yq . Note that the λi (resp. ψi ) are chosen uniformly and independently at random from Z˚p subject to the random distribution of α (resp. µ) and y. Then, C generates the policy decryption key as 1 1 pλ `t i ρpiq r q b

1

sk1 “ g2r , sk2,i “ g1 1

1 1 pκψ `t i ρpiq r q b

sk4,i “ g1 1

1 1 pλ `t i ρpiq r q b

, sk3,i “ g1 2

1 1 pκψ `t i ρpiq r q b

, sk5,i “ g1 2

,

.

Then, C sends to A the policy decryption key SKArcv “ ppA, ρ, tnρpiq uiPrm2 s q, sk1 , tsk2,i , sk3,i , sk4,i , sk5,i uiPrm2 s q. ˚ ‚ Challenge. A outputs the sender’s attribute sets Ssnd , a policy ˚ ˚ ˚ Asnd and two messages msg0 , msg1 of equal length that it ˚ intends to challenge. C checks if Ssnd satisfies any of the access policy Arcv queried in Phase 1. If yes, C aborts. Otherwise, C $ chooses s1 , s12 , s22 , s13 , s23 , τ 1 Ð Z˚p and sets s2 “ s12 ` s22 , $

s3 “ s13 ` s23 , s “ s1 ` s2 . Then C selects λ1 , ¨ ¨ ¨ , λm1 Ð Z˚p $

˚ . The challenger selects θ Ð Z˚p . The for encryption of Ssnd challenger flips random coin b P t0, 1u to encrypt msg˚b , and random coin β P t0, 1u to determine which of the following ciphertext should be created. If β “ 0, it generates the challenge ciphertext as follows:

V “ epg1 , g2 qαs`xµs3 , ct0 “ ϕpmsg˚ b q ‘ ĤpV q, ct1 “ g2s1 , ct2 “ g2s3 , κλi `tπpiq s3

ct3,i “ g1

b s1

b s2

, ct4,1 “ g21 2 , ct4,2 “ g22 2 , b τ s1

ct5,i “ g1ti s2 , ct6,i “ g1ti τ1 s3 , ct7 “ g21 1 3 , b τ s2

px`κτ1 qs3

ct8 “ g22 1 3 , ct9 “ g1

, where τ1 “ τ ` τ 1 .

Otherwise, it generates V “ epg1 , g2 qθ , and the other ciphertext components are kept the same. Then, C sends to adversary A the ciphertext CTsnd “ ppM, π, tnπpiq uiPrm1 s q, ct0 , ct1 , ct2 , pct3,i qiPrm1 s , ct4,1 , ct4,2 , tct5,i , ct6,i uiPrℓ1 s , ct7 , ct8 , ct9 q. ‚ Phase 2. It is the same as in Phase 1 with the restriction that any input access policy A are not allowed to satisfy the ˚ challenge attribute sets Ssnd . ‚ Guess. A outputs a bit as a guess. Analysis of A’s Success Probability. To demonstrate that no PPT adversary A can distinguish between ct0 in the aforementioned game, we assume the contrary. The only way A’s views could differ is if there exist two distinct terms yielding the same result when θ “ δpαs`xµs3 q but producing different results when θ is sampled randomly. Let θ1 and θ2 be two such terms. Since θ only occurs in epg1 , g2 qθ , which cannot be paired, A can only create queries where θ is an additive term. Thus, θ1 and θ2 can be written as θ1 “ δθ ` θ11 and θ2 “ δθ ` θ21 for some θ11 , θ21 that do not contain θ. Based on the assumption that θ1 “ θ2 when θ “ δpαs ` xµs3 q, we have δ1 pαs ` xµs3 q ` θ11 “ δ2 pαs ` xµs3 q ` θ21 . Rearranging this

equation gives θ11 ´ θ21 “ pδ2 ´ δ1 qpαs ` xµs3 q , implying that A can algebraically construct epg1 , g2 qδpαs`xµs3 q for some δ P Zq using the oracle outputs it has already queried. Below, we show that constructing such an expression is computationally infeasible, giving A only a negligible advantage in winning the confidentiality game. To calculate the probability of A constructing epg1 , g2 qδpαs`xµs3 q for some δ P Zq , we perform a case analysis based on the information A receives from the simulation. For completeness, we first summarize the exponent elements available to A in groups G1 , G2 , GT . ´ G1 elements: 1, κ, ti , ti τ , ti r, ti s2 , x ` κτ , κλi ` tπpiq s3 , ti τ1 s3 , px`κτ1 qs3 , b11 pλi `tρpiq r1 q, b12 pλi `tρpiq r1 q, b11 pκψi ` tρpiq r1 q, b12 pκψi ` tρpiq r1 q. ´ G2 elements: 1, µ, b1 , b2 , r, r1 , s1 , s3 , b1 τ , b2 τ , b1 s12 , b2 s22 , α ` κr, b1 τ1 s13 , b2 τ1 s23 . ´ GT elements: 1, α, xµ. We now enumerate all possible queries into GT using the bilinear map and the group elements available to A, as shown in Table V. Note that the blue element αs ` xµs3 in Table V is not used in this proof. A can compute arbitrary linear combinations of these terms, and we will demonstrate that none can take the form δpαs ` xµs3 q, where s “ s1 ` s2 . (1) Consider how to construct epg1 , g2 qδαs1 for some δ. From Table V, the only possibility is that A could create λi s1 using terms such as s1 pκλi ` tπpiq s3 q, s1 κ, s1 ti , s1 ti τ , s1 ti r, s1 ti s2 , s1 px ` κτ q, s1 ti τ1 s3 , and s1 px ` κτ1 qs3 . However, λi s1 cannot be combined through addition or subtraction with any other elements in G1 , G2 , or GT . Hence, constructing δαs1 in GT is impossible for A. (2) Now, consider constructing epg1 , g2 qδαs2 for some δ, where s2 “ s12 ` s22 . According to Table V, A cannot combine s2 “ s12 ` s22 via simple addition or subtraction within the elements of G1 , G2 , or GT . The only way A could generate a term involving αs2 is by pairing b11 ¨ pλi ` tρpiq r1 q with b1 τ1 s13 and pairing b12 ¨ pλi ` tρpiq r1 q with b2 τ1 s23 , producing pλi ` tρpiq r1 qs12 and pλi ` tρpiq r1 qs22 , which combine to form pλi ` tρpiq r1 qps12 ` s22 q “ λi s2 ` tρpiq r1 s2 in GT . For A to construct δαs2 in GT , it must first construct tρpiq r1 s2 and then cancel out the term of λi s2 . From Table V, A can deduce tρpiq r1 s2 by pairing tρpiq s2 (derived from ti s2 ) with r1 . However, canceling λi s2 by reconstructing λi as α is impossible. The reason is that the input access policy A cannot be satisfied by the attribute sets S ˚ . Therefore, constructing δαs2 in GT is infeasible for A. (3) Finally, consider constructing epg1 , g2 qδxµs3 for some δ, where s3 “ s13 ` s23 . As shown in Table V, combining s3 “ s13 ` s23 through addition or subtraction within the elements of G1 , G2 , or GT is impossible. The only way A could generate a term involving xs3 is by pairing b11 ¨ pκψi ` tρpiq r1 q with b1 τ1 s13 and pairing b12 ¨ pκψi ` tρpiq r1 q with b2 τ1 s23 , yielding pκψi ` tρpiq r1 qτ1 s13 and pκψi ` tρpiq r1 qτ1 s23 , which combine to produce pκψi ` tρpiq r1 qτ1 s3 in GT .

Thus, A can only create xψi s3 from terms such as pκψi ` tρpiq r1 qτ1 s3 , s3 κ, s3 ti , and s3 px ` κτ q. However, combining xψi s3 via addition or subtraction within the elements of G1 , G2 , or GT is impossible. Therefore, constructing δxµs3 in GT is infeasible for A. Analysis of Simulation Failure. Let n represent the total number of group elements A receives from its oracle queries to the hash function, groups G1 , G2 , GT , the bilinear map e, and its interaction with the confidentiality game. We show that the views of A for β “ 0 and β “ 1 are identically distributed, except with probability Opn2 {qq, based on the randomness in the variable values chosen during the simulation. This probability arises from an accidental collision, where two distinct polynomials in the GGM evaluate to the same value. As indicated in Table V, the polynomial’s maximum degree is 5. By the Schwartz-Zippel lemma [39], [51], the probability of such a collision occurring is Op1{qq. Using a union bound, the probability of a collision across all n queries is at most Opn2 {qq, which is negligible when q is exponentially large in the secret parameter κ. In conclusion, A only holds a negligible advantage in the modified game, implying that it also has a negligible advantage in the confidentiality game. This completes the proof of Theorem 1. ■ B. Proof of Theorem 2 (FEME: Anonymity) Proof. The logic flow of this proof is similar to the one for the Theorem 1. Firstly, we consider a modified security game that implies anonymity. Next, we bound A’s success probability and analyze the simulation failure. In the anonymity game, the ciphertext components related to the two challenged attribute sets and the two challenged J access policies are ct3,i “ hMi ps1 ||vq ¨ HpΨπpiq qs3 , ct5,i “ Hpui qs2 and ct6,i “ Hpui qτ1 , where τ1 “ τ ` τ 1 . Similarly, J we can simulate them as ct3,i “ hMi ps1 ||vq ¨ HpΨπpiq qs3 “ κλ `t s g1 i πpiq 3 , ct5,i “ Hpui qs2 “ g1ti s2 and ct6,i “ Hpui qτ1 “ ti τ1 s3 g1 , where λi are chosen uniformly and independently at random from Z˚p subject to the random distribution of s1 and v. The challenger produces a challenge ciphertext element ct3,i κλ `t s κλ `t s either g1 i πpiq,0 3 or g1 i πpiq,1 3 (given two challenge tag t t sets ttπpiq,0 ui , ttπpiq,1 ui , using g1πpiq,0 , g1πpiq,1 as the querying results of HpΨπpiq q from the random oracle, respectively), t ¨s t ¨s generates ct5,i either g1i,0 2 or g1i,1 2 , creates ct6,i either ti,0 ¨τ1 s3 ti,1 ¨τ1 s3 g1 or g1 (given two challenge tag sets tti,0 ui , t t tti,1 ui , using g1i,0 , g1i,1 as the querying results of Hpui q from the random oracle, respectively). We can instead consider a modified experiment in which $ the challenger randomly samples a bit β Ð t0, 1u and $ θ1 , θ2 , θ3 Ð Z˚p . The generated challenge ciphertext element κλ `t s ct3,i is either g1 i πpiq,β 3 or g1θ1 , the element ct5,i is either ti,β ¨s2 t ¨τ s θ2 g1 or g1 , and ct6,i is either g1i,β 1 3 or g1θ3 . Therefore, assume that A has an advantage ϵ in winning the anonymity game. Then, A has an advantage ϵ{2 in κλ `t s distinguishing g1 i πpiq,β 3 from g1θ1 , an advantage ϵ{2 in

t

¨s

distinguishing g1i,β 2 from g1θ2 , and an advantage ϵ{2 in t ¨τ s distinguishing g1i,β 1 3 from g1θ3 . For instance, the probability t ¨τ s of distinguishing g1i,0 1 3 from g1θ3 is equal to that of distinti,1 ¨τ1 s3 guishing g1 from g1θ3 . We call them the three tuples for simplicity in the following proof. Simulation of the Modified Game. The adversary A aims to distinguish the three tuples. ‚ Setup. Same as defined in the proof of Theorem 1. ‚ Phase 1. In phase 1, A can make oracle queries to the random oracle and a key generation oracle as follows. ´ Random oracle pOH q. Same as defined above. ´ Key generation oracles pOEKGen , ODKGen , OPolGen q. Same as defined in the proof of Theorem 1. ˚ ‚ Challenge. A outputs S0 “ tui,0 uiPrms “ tni , vi,0 uiPrℓ1 s , ˚ S1 “ tui,1 uiPrℓ1 s “ tni , vi,1 uiPrℓ1 s , and two access policies A˚snd0 “ pM, π, Ψπpiq,0 “ tnπpiq , vπpiq,0 uiPrm1 s q, A˚snd1 “ pM, π, Ψπpiq,1 “ tnπpiq , vπpiq,1 uiPrm1 s q that it intends to attack. Note that S0˚ , S1˚ have the same attribute names tni uiPrℓ1 s , and A˚snd0 , A˚snd1 have the same attribute names tnπpiq uiPrm1 s . C checks whether S0˚ or S1˚ satisfies any of the access policy A queried in Phase 1. If yes, C rejects S0˚ , S1˚ . C also checks whether any of the attribute set S queried in Phase 1 satisfies A˚snd0 or A˚snd1 . If yes, C rejects A˚snd0 , $

A˚snd1 . Otherwise, C chooses θ, s1 , s12 , s22 , s13 , s23 , τ 1 Ð Z˚p and sets s2 “ s12 ` s22 , s3 “ s13 ` s23 , s “ s1 ` s2 . Then C selects $ β Ð t0, 1u for encryption one set of attributes, and flips a coin b P t0, 1u. If b “ 0, it generates the challenge ciphertext as follows: V “ epg1 , g2 qαs`xµs3 , ct0 “ ϕpmsgq ‘ ĤpV q, ct1 “ g2s1 , κλi `tπpiq,β s3

ct2 “ g2s3 , ct3,i “ g1 t

s

b s1

b s2

, ct4,1 “ g21 2 , ct4,2 “ g22 2 ,

t

τ s

b τ s1

ct5,i “ g1i,β 2 , ct6,i “ g1i,β 1 3 , ct7 “ g21 1 3 , b τ s2

px`κτ1 qs3

ct8 “ g22 1 3 , ct9 “ g1

, where τ1 “ τ ` τ 1 .

Otherwise, it generates ct3,i “ g1θ1 , ct5,i “ g1θ2 , ct6,i “ g1θ3 , and the other ciphertext components are kept the same. Then, C sends to adversary A the ciphertext CTsnd “ ppM, π, tnπpiq uiPrm1 s q, ct0 , ct1 , ct2 , pct3,i qiPrm1 s , ct4,1 , ct4,2 , tct5,i , ct6,i uiPrℓ1 s , ct7 , ct8 , ct9 q. ‚ Phase 2. It is the same as in Phase 1 with the restriction that any input access policy A are not allowed to satisfy the challenge attribute sets S0˚ and S1˚ . ‚ Guess. A outputs a bit as a guess. Analysis of A’s Success Probability. For simplicity, we denote tπpiq,β as tπpiq , and ti,β as ti in all further paragraphs. Suppose that A can algebraically construct epg1 , g2 qδ1 pκλi `tπpiq s3 q , epg1 , g2 qδ2 ti s2 , epg1 , g2 qδ3 ti τ1 s3 for some δ1 , δ2 , δ3 P Zq using all oracle outputs it has already queried, then it can use them to distinguish the three tuples. To calculate the probability of A constructing epg1 , g2 qδ1 pκλi `tπpiq s3 q , epg1 , g2 qδ2 ti s2 , epg1 , g2 qδ3 ti τ1 s3 for some δ1 , δ2 , δ3 P Zq , we perform a case analysis based on the information A receives from the simulation.

For completeness, we list all possible queries into GT using the bilinear map and group elements available to A, as shown in Table V. The violet elements in Table V should be excluded for this anonymity proof, they are used in the confidentiality proof. A can compute arbitrary linear combinations of these terms. Below, we show that constructing these expressions is computationally infeasible, giving A only a negligible advantage in winning the anonymity game. (1) Consider how to construct epg1 , g2 qδ1 pκλi `tπpiq s3 q for some δ1 . According to Table V, A cannot combine s3 “ s13 ` s23 via simple addition or subtraction within the elements of G1 , G2 , or GT . To generate a term involving κλi is by pairing b11 ¨ pλi ` tρpiq r1 q with b1 τ1 s13 and pairing b12 ¨ pλi ` tρpiq r1 q with b2 τ1 s23 , yielding pλi ` tρpiq r1 qτ1 s13 and pλi ` tρpiq r1 qτ1 s23 , which combine to produce pλi ` tρpiq r1 qτ1 s3 in GT . To generate a term involving ti s3 is by pairing b11 ¨ pκψi ` tρpiq r1 q with b1 τ1 s13 and pairing b12 ¨pκψi `tρpiq r1 q with b2 τ1 s23 , yielding pκψi ` tρpiq r1 qτ1 s13 and pκψi ` tρpiq r1 qτ1 s23 , which combine to produce pκψi ` tρpiq r1 qτ1 s3 in GT . However, κλi ` tπpiq s3 cannot be derived through addition or subtraction of pλi ` tρpiq r1 qτ1 s3 , pκψi ` tρpiq r1 qτ1 s3 with any other elements in G1 , G2 , or GT . Hence, constructing δ1 pκλi ` tπpiq s3 q in GT is impossible for A. (2) Now, consider constructing epg1 , g2 qδ2 ti s2 for some δ2 . According to Table V, A cannot combine s2 “ s12 ` s22 via simple addition or subtraction within the elements of G1 , G2 , or GT . The first way A could generate a term involving ti s2 is by pairing b11 ¨pλi `tρpiq r1 q with b1 s12 and pairing b12 ¨pλi `tρpiq r1 q with b2 s22 , producing pλi ` tρpiq r1 qs12 and pλi ` tρpiq r1 qs22 , which combine to pλi ` tρpiq r1 qps12 ` s22 q “ λi s2 ` r1 tρpiq s2 in GT . However, ti s2 cannot be derived through addition or subtraction of λi s2 ` r1 tρpiq s2 with any other elements in G1 , G2 , or GT . Hence, constructing δ2 ti s2 in GT is impossible for A. Another way A could generate a term involving ti s2 is by pairing b11 ¨ pκψi ` tρpiq r1 q with b1 s12 and pairing 1 1 2 1 1 b2 ¨ pκψi ` tρpiq r q with b2 s2 , producing pκψi ` tρpiq r qs2 and pκψi `tρpiq r1 qs22 , which combine to pκψi `tρpiq r1 qps12 `s22 q “ κψi s2 ` r1 tρpiq s2 in GT . However, ti s2 cannot be derived through addition or subtraction of κψi s2 ` r1 tρpiq s2 with any other elements in G1 , G2 , or GT . Hence, constructing δ2 ti s2 in GT is impossible for A. (3) Finally, consider constructing epg1 , g2 qδ3 ti τ1 s3 for some δ3 . According to Table V, A cannot combine s3 “ s13 ` s23 via simple addition or subtraction within the elements of G1 , G2 , or GT . The first way A could generate a term involving ti τ1 s3 is by pairing b11 ¨ pλi ` tρpiq r1 q with b1 τ1 s13 and pairing b12 ¨ pλi `tρpiq r1 q with b2 τ1 s23 , yielding pλi `tρpiq r1 qτ1 s13 and pλi ` tρpiq r1 qτ1 s23 , which combine to produce pλi ` tρpiq r1 qτ1 s3 “ λi ¨τ1 s3 ` r1 ¨ ti τ1 s3 in GT . However, ti τ1 s3 cannot be derived through addition or subtraction of λi ¨ τ1 s3 ` r1 ¨ tρpiq τ1 s3 with any other elements in G1 , G2 , or GT . Hence, constructing

δ3 ti τ1 s3 in GT is impossible for A. Another way A could generate a term involving ti τ1 s3 is by pairing b11 ¨ pκψi ` tρpiq r1 q with b1 τ1 s13 and pairing b12 ¨ pκψi ` tρpiq r1 q with b2 τ1 s23 , yielding pκψi ` tρpiq r1 qτ1 s13 and pκψi ` tρpiq r1 qτ1 s23 , which combine to produce pκψi ` tρpiq r1 qτ1 s3 in GT . However, ti τ1 s3 cannot be derived through addition or subtraction of pκψi ` tρpiq r1 qτ1 s3 with any other elements in G1 , G2 , or GT . Hence, constructing δ3 ti τ1 s3 in GT is impossible for A. Analysis of Simulation Failure. Same as that in the proof for Theorem 1. In conclusion, A only holds a negligible advantage in the modified game, implying that it also has a negligible advantage in the anonymity game. This completes the proof of Theorem 2. ■ C. Proof of Theorem 3 (FEME: Authenticity) To prove the authenticity of FEME, we show that an adversary cannot create a valid ciphertext that passes decryption without the proper attribute encryption keys. The challenger sets up the system, providing the adversary with master public keys and simulating key generation oracles. The adversary can query these oracles to obtain encryption and decryption keys for chosen attribute sets and policies, except for those matching the final target policy. The proof relies on a contradiction: assuming the adversary produces a valid ciphertext under conditions not allowed by the oracles, we demonstrate this would imply the adversary must have queried the sender’s encryption key with attributes matching the target policy, violating the security model’s constraints. This involves showing that certain polynomial relations between group elements must hold, which leads to the contradiction, proving that any valid forgery is computationally infeasible. Proof. The interaction between the adversary A and challenger C proceeds as follows. $ ˚ ‚ Setup. The challenger C chooses α, x, µ, b1 , b2 , κ Ð Zp , µ α xµ and calculates Z “ epg1 , g2 q , Y “ epg1 , g2 q , δ0 “ g2 , δ1 “ g2b1 , δ2 “ g2b2 and h “ g1κ . C sends the master public key mpk “ pZ, Y, h, δ0 , δ1 , δ2 q to A. ‚ Phase 1. In phase 1, A can make oracle queries to the random oracle and a key generation oracle as follows. ´ Random oracle pOH q. Same as defined above. ´ Attribute encryption key generation oracle pOEKGen q. When A makes a encryption key query for an attribute set Ssnd , $ C picks τj Ð Z˚p for the j-th query. Then, C generates the attribute encryption key as τ

τ

τ

ek1,i “ hi j , ek2 “ δ1j , ek3 “ δ2j , ek4 “ g1x ¨ hτj . Then, C sends to A the attribute encryption key EKSsnd “ ptni uiPrℓ1 s , tek1,i uiPrℓ1 s , ek2 , ek3 , ek4 q. ´ Attribute decryption key generation oracle pODKGen q. When $ A makes a key query for an attribute set Srcv , C picks r Ð Z˚p . Then, C generates the attribute decryption key as dk1 “ g1α ¨ hr , dk2,i “ hri , dk3 “ g2r .

Then, C sends to A the attribute decryption key DKSrcv “ ptni uiPrℓ2 s , dk1 , tdk2,i uiPrℓ2 s , dk3 q. ´ Policy decryption key generation oracle pOPolGen q. When A makes a key query for a policy Arcv “ pA, ρ, tΨρpiq uiPrm2 s q, C $

$

2 ´1 picks r1 Ð Z˚p and a vector y Ð Zm . Let λi “ Ai pα||yqJ p J and ψi “ Ai pµ||yq . Note that the λi (resp. ψi ) are chosen uniformly and independently at random from Z˚p subject to the random distribution of α (resp. µ) and y. Then, C generates the policy decryption key as 1

1

1

1

˚ ˚ Recall that CT˚snd is a valid ciphertext on Ssnd and Ssnd |ù ˚ Arcv . According to the correctness proof (shown in the full

version [37]), we know that: ś ś ep iPI2 psk4,ρpiq qωi , ct7 qep iPI2 psk5,ρpiq qωi , ct8 q ś “ Y ´s3 , epct9 , δ0 qep iPI2 pct6,ρpiq qωi , sk1 q ř where iPI2 pAi pµ||yqJ ¨ ωi q “ µ. Based on this equation, we derive that

1

sk1 “ g2r , sk2,i “ pg1λi ¨ hrρpiq q b1 , sk3,i “ pg1λi ¨ hrρpiq q b2 , 1

1

1

1

sk4,i “ phψi ¨ hrρpiq q b1 , sk5,i “ phψi ¨ hrρpiq q b2 . Then, C sends to A the policy decryption key SKArcv “ ppA, ρ, tnρpiq uiPrm2 s q, sk1 , tsk2,i , sk3,i , sk4,i , sk5,i uiPrm2 s q. ˚ ˚ ˚ ‚ Forgery. The attacker A sends pCTsnd , Ssnd , Arcv q to C, ˚ ˚ where Ssnd |ù Arcv . The restriction is that the attribute ˚ encryption key of Ssnd has not been queried in OEKGen , and the policy decryption key of A˚rcv and any other Arcv satisfying ˚ Ssnd |ù Arcv have not been queried in OPolGen . We must prove that under the restrictions, the adversary A cannot forge a valid ciphertext CT˚snd . We use proof by contradiction to assume that CT˚snd is a valid ciphertext. The adversary A has access to the group elements provided in the master public key mpk “ pZ, Y, h, δ0 , δ1 , δ2 q, hi “ Hpui q obtained from OH , and EKSsnd obtained from OEKGen , as they are the input of Enc for CT˚snd generation. Let pjq pjq pjq pjq pjq pjq EKSsnd “ ptni uiPrℓ1 s , tek1,i uiPrℓ1 s , ek2 , ek3 , ek4 q be the output of the j-th query to OEKGen . Denote qe as the query time to OEKGen . In GGM, the only way for the adversary to generate new group elements is to use the existing exponent elements available to A in groups G GT . This means that there are known scalars ˘ ` 1 , G12 and a, b, b , b2 , c, c1 , c2 , tdi uiPrm1 s , e, tf1,j , f2,j , f3,j , f4,j ujPrqe s such that:

“

ep

ś

“

iPI2 psk4,ρpiq q

“

i ś 1 1 τj f qe ψi ¨ hr 1 q b1 , 2,j c ¨ δ e¨c q 1 j“1 pδ1 q ρpiq śqe ep j“1 pg1x ¨ hτj qf4,j c ¨ he¨c , g2µ q

iPI2 ph

` bκ e g1 1

iPI2 ψi ωi

ct˚7

“

ct˚8

“

ct˚9

“

j“1 źqe j“1 źqe j“1 źqe

iPI2 ωi tρpiq

řqe f4,j cx¨ j“1

¨ “

řqe c1 b1 p j“1 f2,j τj `eq ˘

, g2

řqe f4,j τj `eqκ cp j“1

, g2µ q ř qe f3,j τj `eq ˘ c2 b2 p j“1 iPI2 ψi ωi , g2 ¨ g1 ř řqe f1,j τj `eq iPI ωi tρpiq cp 1 2 , g2r q epg1 j“1 ´xµ¨c ´c

` b e g1 2

¨ g1

r1 ř iPI2 ωi tρpiq b2

epg1 , g2 q

“Y

,

ř

where iPI2 ψi ¨ ωi “ µ, and ψi “ Ai pµ||yqJ . Then, we obtain the following polynomial relation: `κ ÿ b1 iPI

ψi ωi `

2

ÿqe ˘ ` ˘ r1 ÿ ωi tρpiq ¨ c1 b1 p f2,j τj ` eq j“1 b1 iPI 2

ÿqe ˘ ` ˘ r1 ÿ ` ψi ωi ` ωi tρpiq ¨ c2 b2 p f3,j τj ` eq j“1 b2 iPI b2 iPI 2 2 ÿqe ÿqe ` ˘ ´ cx ¨ f4,j ` cp f4,j τj ` eqκ ¨ µ j“1 j“1 ÿ ` ÿqe ˘ ´ cp f1,j τj ` eq ωi tρpiq ¨ r1 `κ ÿ

j“1

iPI2

´xµc

Let us rearrange the left side of this equation as follows. `κ ÿ b1 iPI

ψi ωi `

ÿqe ˘ ` ˘ r1 ÿ ωi tρpiq ¨ c1 b1 p f2,j τj ` eq j“1 b1 iPI 2

ÿqe ˘ ` ˘ r1 ÿ ` ψi ωi ` ωi tρpiq ¨ c2 b2 p f3,j τj ` eq j“1 b2 iPI b2 iPI 2 2 ÿqe ÿqe ˘ ` ´ cx ¨ f4,j ` cp f4,j τj ` eqκ ¨ µ j“1 j“1 ÿ ` ÿqe ˘ ´ cp f1,j τj ` eq ωi tρpiq ¨ r1 j“1 iPI2 ÿ ` 1 ÿqe ψi ωi q κc f2,j τj p `κ ÿ

pjq

pek1,i qf1,j ¨c ¨ he¨c i , pjq

1

1

pjq

2

2

pek2 qf2,j ¨c ¨ δ1e¨c , pek3 qf3,j ¨c ¨ δ2e¨c ,

pjq pek4 qf4,j ¨c ¨ he¨c . j“1

In the ciphertext CT˚snd construction, it implicit sets that a “ s1 , b “ s2 , c “ s3 , b1 “ s12 , b2 “ s22 , c1 “ s13 , c2 “ s23 , where b “ b1 `b2 and c “ c1 `c2 . It also implies that di “ Mi ps1 ||vqJ 1 and e “ τ .

ř

¨ g1 1

κ ř

2

źqe

r1 b

ř

2

“

ś

epg1

ct˚4,1 “ δ1b , ct˚4,2 “ δ2b , ct˚5,i “ hbi , ct˚6,i

ωi , ct qep 7

ωi ś ś 2 2 1 τ e pδ2j qf3,j c ¨ δ2e¨c q ep iPI2 phψi ¨ hrρpiq q b2 , qj“1 ¨ ś śqe τj 1 qωi , g2r q ep iPI2 p j“1 phρpiq qf1,j c ¨ he¨c ρpiq

“

1

ś

ω

V “ Z a`b ¨ Y c , ct0 “ ϕpmsgq ‘ ĤpV q, ct˚1 “ g2a , ct˚2 “ g2c , ct˚3,i “ hdi ¨ phπpiq qc ,

ωi iPI2 psk5,ρpiq q , ct8 q ś ω epct9 , δ0 qep iPI2 pct6,ρpiq q i , sk1 q 1 ś ś e 1 1 1 pjq ep iPI2 pphψi ¨ hrρpiq q b1 qωi , qj“1 pek2 qf2,j c ¨ δ1e¨c q ś e pjq ep qj“1 pek4 qf4,j c ¨ he¨c , δ0 q 1 ś ś e 2 2 1 pjq ep iPI2 pphψi ¨ hrρpiq q b2 qωi , qj“1 pek3 qf3,j c ¨ δ2e¨c q ¨ ś ś e 1 pjq ep iPI2 p qj“1 qωi , g2r q pek1,ρpiq qf1,j c ¨ he¨c ρpiq

ep

“

j“1

`r1 c1

iPI2

ÿqe

`κc1 e

j“1

ÿ

f2,j τj p

ÿ

ωi tρpiq q

iPI2

ψi ωi ` r1 c1 e

iPI2

ÿ iPI2

ÿ ÿqe ` ` κc2 f3,j τj p ψi ωi q j“1

iPI2

ωi tρpiq

˘

`r1 c2

ÿqe j“1

ÿ

`κc2 e

f3,j τj p

ÿ

˚ are created for the same Ssnd for all j P rqe s, where ˚ ˚ Ssnd |ù Arcv (the deduction of this step is deterred to the end of the proof). It indicates that the ciphertext CT˚snd must be constructed as qe ź τ0 e c ct˚6,i “ pHpui qτj qfj ¨c ¨ he¨c i “ pHpui q ¨ hi q ,

ωi tρpiq q

iPI2

ÿ

ψi ωi ` r1 c2 e

iPI2

ωi tρpiq

˘

iPI2

ÿqe ` ÿqe ˘ ´ f4,j ¨ xµc ` cp f4,j τj ` eqκ ¨ µ j“1 j“1 ÿqe ÿ ` ˘ ´ cr1 p f1,j τj ` eq ωi tρpiq j“1 iPI2 ÿ ÿqe ÿqe f3,j τj qp f2,j τj ` c2 ψi ωi q κpce ` c1

“

`r1 pce ` c1

j“1

j“1

ÿqe

ÿqe

j“1

f2,j τj ` c2

` ÿqe

iPI2

j“1

ÿ

f3,j τj qp

“

ct˚7

ωi tρpiq q

“

˘

ct˚8

j“1

` ˘c1 1 1 τ pδ1j qfj ¨c ¨ δ1e¨c “ δ1τ0 ¨ δ1e ,

j“1 qe ź

iPI2

ÿqe

f4,j ¨ xµc ` κ ¨ cµp f4,j τj ` eq j“1 ÿ ˘ ` 1 ÿqe ´ r pc ωi tρpiq f1,j τj ` ceq j“1 iPI2 ÿqe ÿqe κrpce ` c1 f2,j τj ` c2 f3,j τj qµ j“1 j“1 ÿqe ˘ ´cµp f4,j τj ` eq s ´

j“1 qe ź

“

` ˘c2 2 2 τ pδ2j qfj ¨c ¨ δ2e¨c “ δ2τ0 ¨ δ2e ,

j“1 qe ź

ct˚9

“

˘c ` pg1x hτj qfj ¨c ¨ he¨c “ pg1x hτ0 q ¨ he ,

j“1

j“1

qe ÿ

1

`r p´c

f1,j τj ` c

1

j“1

ÿ

qe ÿ

f2,j τj ` c

qe ÿ

2

j“1

where fj “ f1,j “ f2,j “ f3,j “ f4,j and τ0 “ We can deduce that

f3,j τj q

j“1

řqe

j“1 τj fj .

1

ωi tρpiq q

ct˚6,i “ pek˚1,i ¨ hei qc , ct˚7 “ pek˚2 ¨ δ1e qc ,

f4,j ¨ xµc

ct˚8 “ pek˚3 ¨ δ2e qc , ct˚9 “ pek˚4 ¨ he qc ,

¨p iPI2

´ “

ÿqe

p´c

j“1 ÿqe

f4,j τj ` c1

j“1 qe ÿ

`r1 p´c

ÿ

ÿqe

f1,j τj ` c1

j“1

j“1 qe ÿ

ÿqe

f2,j τj ` c2

qe ÿ

f2,j τj ` c2

j“1

j“1

where ek˚1,i “ Hpui qτ0 , ek˚2 “ `δ1τ0 , ek˚3 “ δ2τ0 , ek˚4 “ g1x hτ0 . Since the scalers c, c1 , c2 , eq are selected by the adversary, A can easily calculate EK˚snd “ ˚ ˚ and Ssnd |ù ptn˚i uiPrℓ1 s , tek˚1,i uiPrℓ1 s , ek˚2 , ek˚3 , ek˚4 q for Ssnd ˚ Arcv , which contradicts with the constraint. Therefore, the adversary cannot symbolically produce a valid forgery, and the authenticity of FEME is proved.

f3,j τj qκµ

f3,j τj q

j“1

ωi tρpiq q

¨p ´

2

iPI2 ÿqe j“1

f4,j ¨ xµc

Since the right side of the equation is ´xµc, we must have pjq

qe ÿ

´c j“1 qe ÿ

´c

qe ÿ

f4,j τj ` c1 f1,j τj ` c1

j“1

j“1 qe ÿ

f2,j τj ` c2 f2,j τj ` c2

j“1

qe ÿ j“1 qe ÿ

f3,j τj “ 0,

(1)

f3,j τj “ 0,

(2)

In the following, we proved that EKSsnd are created for the ˚ . same Ssnd (1) Let qe “ 1. We have f1,j “ f2,j “ f3,j “ f4,j “ fj “ 1 and ˚ c1 e¨c1 ct˚6,i “ pek1,i qc ¨ he¨c i , ct7 “ pek2 q ¨ δ1 ,

(3)

ct˚8 “ pek3 qc ¨ δ2e¨c , ct˚9 “ pek4 qc ¨ he¨c .

j“1 ÿqe

2

j“1

f4,j “ 1.

If the challenge ciphertext CT˚snd is valid, the adversary can ˚ ˚ and Ssnd |ù A˚rcv , which directly calculate EK˚snd for Ssnd contradicts with the constraint.

Combining equations (1)-(3), we derive that ÿqe ÿqe f1,j “ f4,j “ 1. j“1

2

j“1

(2) Let qe “ 2. We have f1,j “ f2,j “ f3,j “ f4,j “ fj and ř 2 j“1 fj “ f1 ` f2 “ 1.

We arrange equation (1) as ÿqe p´cf4,j ` c1 f2,j ` c2 f3,j qτj “ 0.

p1q

p1q

p2q

(2.1) We firstly prove that Ssnd “ tui uiPrℓp1q s and Ssnd “

j“1

1

According to linear algebraic theory, we deduce that ´cf4,j ` c1 f2,j ` c2 f3,j “ 0 for all j P rqe s. As c “ c1 ` c2 , we have ´pc1 ` c2 qf4,j ` c1 f2,j ` c2 f3,j

“

0

1

“

0

2

c pf2,j ´ f4,j q ` c pf3,j ´ f4,j q

Then, we deduce that f2,j “ f3,j “ f4,j for all j P rqe s. Similarly, we deduce that f1,j “ f2,j “ f3,j for all j P rqe s from equation (2). Then, f1,j “ f2,j “ f3,j “ f4,j for all j P rqe s. Under this situation, we have pjq

pjq

pjq

pjq

pjq

pjq

EKSsnd “ ptni uiPrℓ1 s , tek1,i uiPrℓ1 s , ek2 , ek3 , ek4 q

p2q

tui uiPrℓp2q s must have the same number of attributes, i.e., 1

p1q

p2q

ℓ1 “ ℓ1 . p1q p2q Suppose that Ssnd and Ssnd has different number of atp2q p1q tributes and ℓ1 ą ℓ1 . We have ` ˘c p1q p1q ct˚6,i “ Hpui qτ1 f1 ¨ hei , for i “ ℓ1 . ř2 Therefore, τ0 “ τ1 f1 . Since τ0 “ j“1 τj fj , it can be deduced that f2 “ 0. Since f1 ` f2 “ 1, we have f1 “ 1. Then, 1 ct˚6,i “ pek˚1,i ¨ hei qc , ct˚7 “ pek˚2 ¨ δ1e qc ,

2

p1q

ct˚8 “ pek˚3 ¨ δ2e qc , ct˚9 “ pek˚4 ¨ he qc . ˚ ˚ A can easily calculate EK˚snd for Ssnd and Ssnd |ù A˚rcv , which contradicts with the constraint. p1q

p2q

p1q

p1q

ct˚6,ℓp2q

ct˚6,ℓpqe q

¨¨¨ ˘c ` “ Hpũp1q qτ1 f1 ¨ ¨ ¨ Hpǔpqe q qτqe fqe ¨ heℓp3q , 1 ˘c ` where hℓp3q “ Hpǔq, “ Hpǔqτ0 ¨ heℓp3q ,

1

p2q

, where

ct˚7

“

2 ź

“ 2 ź

“

ct˚7

` ˘c1 1 1 τ pδ1j qfj ¨c ¨ δ1e¨c “ δ1τ0 ¨ δ1e ,

ct˚8

ct˚9

“

qe ź

“

ct˚9

` ˘c pg1x hτj qfj ¨c ¨ he¨c “ pg1x hτ0 q ¨ he ,

` ˘c 1 1 1 τ pδ1j qfj ¨c ¨ δ1e¨c “ δ1τ0 ¨ δ1e ,

j“1 qe ź

` ˘c 2 2 2 τ pδ2j qfj ¨c ¨ δ2e¨c “ δ2τ0 ¨ δ2e ,

“

˘c2 ` 2 2 τ pδ2j qfj ¨c ¨ δ2e¨c “ δ2τ0 ¨ δ2e ,

j“1 2 ź

1

1

j“1

ct˚8

1

1

2 ź

pjq pHpui qτj qfj ¨c ¨ he¨c i , j“1

1

1

where hℓp1q “ Hpup1q q, 1 ˘c ` “ Hpûp1q qτ1 f1 ¨ Hpûp2q qτ2 f2 ¨ heℓp2q 1 ˘c ` where hℓp2q “ Hpūq, “ Hpūqτ0 ¨ heℓp2q ,

1

ct˚6,i

pq q

1

p2q

(2.2) Next, we prove that Ssnd “ Ssnd . If Ssnd ‰ Ssnd , there p1q p2q p2q must exist some certain attribute ui ‰ ui , where i P rℓ1 s. p1q p2q Put ui and ui into the random oracle to get the hash values t t p1q p1q p2q p2q hi “ Hpui q “ g1i and hi “ Hpui q “ g1i p1q p2q $ p1q p2q ti , ti Ð Z˚p and ti ‰ ti . The ciphertext CT˚snd is constructed as

p2q

Suppose that Ssnd , Ssnd , ... Ssnde has different number of p1q p2q pq q attributes and ℓ1 ą ℓ1 ą ¨ ¨ ¨ ą ℓ1 e . We deduce that ˘c ˘c ` ` ct˚6,ℓp1q “ Hpup1q qτ1 f1 ¨ heℓp1q “ Hpup1q qτ0 ¨ heℓp1q ,

j“1 qe ź

` ˘c pg1x hτj qfj ¨c ¨ he¨c “ pg1x hτ0 q ¨ he ,

“

j“1

ř2

where fj “ f1,j “ f2,j “ f3,j “ f4,j . řqe Therefore, we have τ0 “ τ1 f1 and τ0 “ j“1 řτqjefj . It can be deduced that f2 “ f3 “ ¨ ¨ ¨ “ fqe “ 0. Since j“1 fj “ 1, we have f1 “ 1. Then,

2 ź

ct˚6,i “ pek˚1,i ¨ hei qc , ct˚7 “ pek˚2 ¨ δ1e qc ,

j“1

where τ0 “ j“1 τj fj . If the ciphertext CT˚snd is valid, it must have ct˚6,i “

1

pjq τ0 e c pHpui qτj qfj ¨c ¨ he¨c i “ pHpūi q ¨ hi q j“1 $

for some attribute ūi . Let h̄i “ Hpūi q “ g1t̄i , where t̄i Ð Z˚p . We have ź2 pjq ct˚6,i “ pHpui qτj qfj ¨c ¨ he¨c i j“1

“

` ř2j“1 tpjq ¨τj fj e ˘c g1 ¨ hi

ñ

˚ ˚ and Ssnd |ù A˚rcv , which A can easily calculate EK˚snd for Ssnd contradicts with the constraint. p1q

j“1 p1q p2q ti τ1 f1 ` ti τ2 f2 “ t̄i pτ1 f1 ` τ2 f2 q p1q p2q pti ´ t̄i qf1 τ1 ` pti ´ t̄i qf2 τ2 “ 0.

to get the hash values hi

(3) řqeLet qe ě 3. We have f1,j “ f2,j “ f3,j “ f4,j “ fj and j“1 fj “ 1. pjq

(3.1) We firstly prove that Ssnd must have the same number of attributes, where j P rq3 s.

p1q

p2q

pq q

t

p1q

p1q

pq q

“ Hpui q “ g1i , ¨ ¨ ¨ , hi e “

pq q

t e p1q pq q g1i , where ti , ¨ ¨ ¨ , ti e

ct˚6,i

“

$

p1q

Hpui e q “ Ð Z˚p and ti pqe q ¨ ¨ ¨ ‰ ti . The ciphertext CT˚snd is constructed as

ct˚7

qe ź

ct˚8 ct˚9

pjq

pHpui qτj qfj ¨c ¨ he¨c i ,

j“1 qe ź

` ˘c1 1 1 τ pδ1j qfj ¨c ¨ δ1e¨c “ δ1τ0 ¨ δ1e ,

“

p1q

As τ1 , τ2 are random numbers in Z˚p , we have pti ´t̄i qf1 “ p2q p1q 0 and pti ´ t̄i qf2 “ 0. Since f1 ` f2 “ 1, we have ti “ t̄i p2q and f1 “ 1, f2 “ 0, or f1 “ 0, f2 “ 1 and ti “ t̄i . In either way, if the challenge ciphertext CT˚snd is valid, the adversary ˚ ˚ can directly calculate EK˚snd for Ssnd and Ssnd |ù A˚rcv , which contradicts with the constraint.

pq q

(3.2) Next, we prove that Ssnd “ ¨ ¨ ¨ “ Ssnde . If Ssnd ‰ Ssnd , p1q pq q there must exist some certain attribute ui ‰ ¨ ¨ ¨ ‰ ui e , p3q p1q pq q where i P rℓ1 s. Put ui , ¨ ¨ ¨ , ui e into the random oracle p1q

pg t̄i τ0 ¨ hei qc “ pHpūi qτ0 ¨ hei qc . ř2 ř2 Since τ0 “ j“1 τj fj and j“1 fj “ f1 ` f2 “ 1, we can deduce that ÿ2 pjq ti ¨ fj τj “ t̄i τ0 “

ñ

2

ct˚8 “ pek˚3 ¨ δ2e qc , ct˚9 “ pek˚4 ¨ he qc .

j“1 qe ź

` ˘c2 2 2 τ pδ2j qfj ¨c ¨ δ2e¨c “ δ2τ0 ¨ δ2e ,

“

j“1 qe ź

` ˘c pg1x hτj qfj ¨c ¨ he¨c “ pg1x hτ0 q ¨ he ,

“

j“1

řqe

where τ0 “ j“1 τj fj . If the ciphertext CT˚snd is valid, it must have ct˚6,i “

qe ź

pjq

e c τ0 pHpui qτj qfj ¨c ¨ he¨c i “ pHpūi q ¨ hi q

j“1

‰

$

for some attribute ūi . Let h̄i “ Hpūi q “ g1t̄i , where t̄i Ð Z˚p . We have źqe pjq pHpui qτj qfj ¨c ¨ he¨c ct˚6,i “ i j“1

“

e tpjq ¨τ f ˘c ` řqj“1 j j ¨ hei g1

pg t̄i τ0 ¨ hei qc “ pHpūi qτ0 ¨ hei qc . řqe fj “ 1, we can deduce that Since τ0 “ j“1 τj fj and j“1 ÿqe ÿqe pjq ti fj τj “ t̄i τ0 “ t̄i τj fj j“1 j“1 ÿqe pjq pti ´ t̄i qfj τj “ 0. ñ “

řqe

j“1

pjq

As τ1 , ¨ ¨ ¨ , τqe are random numbers in Z˚p , we have pti ´ řqe pjq fj “ 1, we have ti “ t̄i , t̄i qfj “ 0 for j P rqe s. Since j“1 1 fj “ 1 for some j P rqe s, and fj 1 “ 0, for the j P rqe s and j 1 ‰ j. In either way, if the challenge ciphertext CT˚snd is ˚ valid, the adversary can directly calculate EK˚snd for Ssnd and ˚ ˚ Ssnd |ù Arcv , which contradicts with the constraint. ˚ Therefore, we prove that EK are created for the same Ssnd ˚ ˚ for all j P rqe s, where Ssnd |ù Arcv .

This completes the proof of Theorem 3.

■