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

Speakers: Yang Yang

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=n3eWe_PfrY4

Overview

Wireless service discovery protocols -- used in Wi-Fi, mDNS, DNS-SD, BLE advertisements, and AirDrop-like workflows -- are fundamentally leaky by design. They rely on cleartext broadcasts with weak or no authentication, enabling tracking, presence detection, session linkability, and identity exposure. Attackers can also inject spoofed messages for man-in-the-middle and denial-of-service attacks. This talk presents PriSrv+, a privacy-preserving service discovery protocol that replaces the core cryptographic primitive of its predecessor PriServ (NDSS 2024) with a new construction called FeME (Fast and Expressive Matchmaking Encryption). FeME supports expressive monotonic Boolean formula policies over arbitrary string attributes while achieving 87% smaller ciphertexts, approximately 7.7x faster broadcast, 3.32x faster mutual authentication, and 4.05x faster end-to-end performance compared to the previous system. The improvements make the protocol practical for resource-constrained devices in BLE and mDNS environments.

Background

▶ Watch: Service discovery privacy problem: tracking, spoofing, identity exposure (0:30)

Service discovery is a ubiquitous wireless operation where devices advertise and discover available services. Current protocols broadcast service information in cleartext, creating several security and privacy problems: repeated, structured broadcasts enable tracking and presence detection; lack of authentication allows spoofing and MITM attacks; and broadcast contents expose identity and service information.

A privacy-preserving service discovery protocol should provide: confidential service discovery with bilateral policy control (both sides enforce who can discover or connect), bilateral anonymity (neither party learns the other's sensitive attributes unless policies are satisfied), and sender authentication to prevent spoofing -- all while remaining efficient enough for bandwidth-constrained devices.

PriServ (NDSS 2024) established the correct architecture: a dual-layer design supporting privacy-preserving discovery and anonymous mutual authentication with bilateral policy control. However, its core primitive, ACME (Anonymous Credential-based Matchmaking Encryption), introduced significant limitations: it exposed some public attributes in the outer layer (enabling tracking), used a binary vector small-universe attribute model (limiting expressiveness and scalability), produced large ciphertexts, required high computation, and introduced external anonymous credential lifecycle management complications.

Key Findings

▶ Watch: PriSrv+ improvements: 87% ciphertext reduction and full attribute hiding (3:30)

FeME eliminates four key limitations of ACME:

1. No external credential lifecycle: Removes the need for credential issuance and revocation infrastructure
2. Full attribute value hiding: Fixes the outer-layer attribute exposure issue by revealing attribute names (for efficient filtering) while hiding attribute values cryptographically
3. 87% smaller ciphertexts: Critical for BLE and mDNS environments where broadcast packet sizes are severely constrained
4. Faster end-to-end performance: 7.7x faster broadcast, 3.32x faster authentication, 4.05x faster overall

Randomness splitting prevents attribute guessing attacks: In the original KPABE-style component, reusing the same randomness across ciphertext parts allowed attackers to test guessed attribute values against observable relations. FeME splits randomness into two independent parts, breaking the observable relations while providing matching key components that cancel extra exponents during legitimate decryption.

Scalar-style ciphertext design eliminates the decryption bottleneck: The original CPABE used a vector of randomness that made decryption scale with policy complexity (many pairings and exponentiations). FeME replaces this with a scalar-style design, collapsing decryption to approximately one pairing plus I exponentiations (where I is the number of attributes used to satisfy the policy).

Technical Deep Dive

▶ Watch: Three-stage FeME construction from ABE components (5:30)

FeME is constructed through a three-stage process building on expressive Attribute-Based Encryption (ABE) components:

Stage 1 -- Anonymous ABE Variants: Starting from the Fabio ABE scheme, the researchers transform both CP-ABE (Ciphertext-Policy) and KP-ABE (Key-Policy) into anonymous variants that hide attribute values. Two key techniques are applied: randomness splitting (preventing attribute guessing by using two independent random values instead of one) and scalar-style ciphertext redesign (replacing vector-style components to reduce decryption cost from polynomial pairings/exponentiations to roughly constant pairings plus linear exponentiations).

Stage 2 -- Hybrid ABE: This bridges the ABE world to the ME world by enforcing sender authentication. In Matchmaking Encryption, it is not enough that a ciphertext matches a policy -- only an authorized sender with a valid encryption key tied to its attributes should produce a legitimate ciphertext. Hybrid ABE achieves this by combining ideas from anonymous CP-ABE and KP-ABE, re-randomizing the sender's encryption key into ciphertext components and structuring decryption so that only a valid key produces consistent results.

Stage 3 -- FeME Construction: The final primitive provides setup, sender/receiver key generation, policy key generation, encryption, and decryption. Encryption combines three fractions (from CP-ABE, KP-ABE, and Hybrid ABE pieces) and wraps payloads using authenticated encryption derived from group elements. The output ciphertext enables receiver policy checking, sender policy checking, and sender authentication while keeping all attribute values hidden.

Protocol workflow: A trusted Key Generation Center (KGC) sets up keys. A service provider broadcasts a FeME-encrypted service advertisement with a partially hidden policy (names visible, values hidden). An eligible client decrypts and responds with a FeME-encrypted reply. Both sides complete mutual authentication and derive a shared session key via Diffie-Hellman and MAC authentication.

Demo / Proof of Concept

▶ Watch: Hybrid ABE: bridging ABE to matchmaking encryption with sender auth (8:00)

The evaluation compares FeME against ACME across multiple curves (80-bit and 100-bit security levels) and four platforms. FeME achieves substantially lower computation costs and much smaller ciphertexts, with the advantage persisting across security levels. Protocol-level benchmarks show 7.70x faster broadcast, 3.32x faster mutual authentication, and 4.05x faster end-to-end performance. Communication drops by 87.3% for broadcast and 96.64% for authentication due to FeME's ciphertext compactness. A real wireless prototype in a Wi-Fi environment confirms the dramatic communication reduction while server-side communication remains constant in its setup.

Defensive Implications

▶ Watch: Performance results: 7.7x faster broadcast, 87% communication reduction (11:00)

For wireless protocol designers, PriSrv+ demonstrates that privacy-preserving service discovery is now practical even for bandwidth-constrained environments like BLE. The 87% ciphertext reduction makes the protocol compatible with existing wireless transmission size requirements, addressing the primary deployment barrier of its predecessor.

For enterprise security architects, the current state of wireless service discovery is fundamentally insecure. Every device broadcasting mDNS, Wi-Fi Direct, or BLE advertisements is leaking information that enables tracking, presence detection, and service enumeration. PriSrv+ provides a path toward addressing this, though adoption requires changes to wireless stack implementations.

For privacy-focused organizations, the bilateral policy control model is particularly valuable: both the service provider and the client enforce access policies, and neither learns the other's attribute values unless policies are mutually satisfied. This provides a stronger privacy model than simple encryption, which only protects confidentiality without policy enforcement.

The interoperability considerations discussed in the paper address how PriSrv+ can be made compatible with existing Wi-Fi, AirDrop, and DNS protocols, acknowledging that protocol evolution is a gradual process.

Key Takeaways

• Current wireless service discovery protocols are fundamentally leaky, enabling tracking and spoofing through cleartext broadcasts
• FeME achieves 87% smaller ciphertexts than the previous ACME primitive, making privacy-preserving discovery practical for BLE and mDNS
• Randomness splitting prevents attribute guessing attacks that were possible against the original construction
• Scalar-style ciphertext design reduces decryption cost from polynomial to approximately constant pairings
• Protocol achieves 7.7x faster broadcast and 4.05x faster end-to-end compared to PriServ
• Removes the need for external anonymous credential lifecycle management, simplifying deployment
• Real wireless prototype validates practical performance in Wi-Fi environments

About the Speaker(s)

Yang Yang is a researcher at Singapore Management University specializing in applied cryptography and privacy-preserving wireless protocols. The work builds on the team's prior research on PriServ (NDSS 2024) and represents a continuation of their program to enhance the privacy and security of wireless service discovery across multiple protocol stacks.