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

Source: arXiv:2606.05902 · Published 2026-06-04 · By Yang Yang, Guomin Yang, Yingjiu Li, Pengfei Wu, Rui Shi, Minming Huang et al.

TL;DR

This paper addresses the significant privacy, scalability, and usability challenges in wireless service discovery (SD) protocols that are widely used in modern networks such as 5G and IoT. Existing protocols like mDNS, BLE, and Wi-Fi expose device attributes in cleartext, enabling tracking, impersonation, and profiling attacks. Prior privacy-enhancing works including PriSrv improve on this by applying matchmaking encryption (ME) schemes, but PriSrv suffers from limitations like inflexible binary attributes, large ciphertexts, and pre-issued credentials. This work introduces PriSrv+, an enhanced protocol built around a novel Fast and Expressive Matchmaking Encryption (FEME) scheme that supports an unbounded attribute universe with arbitrary string attributes, fully conceals attribute values, and achieves bilateral access control and authentication with anonymity.

The key novelty is FEME, which improves on the previous ACME scheme by delivering up to 7.62x faster encryption and 6.23x faster decryption, while reducing ciphertext sizes by 87.33%. FEME accomplishes this through a multi-stage design that combines and optimizes attribute-based encryption (ABE) mechanisms with novel double re-randomization and binding techniques to prevent ciphertext forgery and attribute leakage. PriSrv+ further eliminates reliance on anonymous credentials to simplify policy management, significantly reduces communication overhead (around 87% reduction in broadcast sizes), and maintains protocol compatibility with major wireless standards. Extensive formal security proofs guarantee confidentiality, authenticity, and anonymity, and experimental evaluation on diverse platforms including IoT devices demonstrates real-time performance and scalability improvements over PriSrv and existing state-of-the-art protocols.

Key findings

• FEME achieves up to 7.62x faster encryption and 6.23x faster decryption compared to PriSrv's ACME scheme.
• Ciphertext sizes in PriSrv+ are reduced by 87.33%, leading to broadcast packet size reductions of 88.89% (mDNS), 87.73% (BLE), and 86.64% (Wi-Fi) compared to PriSrv.
• Communication costs decrease by 87.33% for service broadcast and 86.64% for anonymous mutual authentication relative to PriSrv.
• FEME supports an unbounded attribute universe allowing arbitrary string attributes instead of fixed-size binary vectors, enabling more expressive policies and better scalability.
• Double re-randomization and binding techniques in FEME prevent sender key extraction, ciphertext forgery, component mixing attacks, and attribute guessing.
• Partial hiding of attribute values (only attribute names revealed) allows efficient policy matching without disclosing sensitive information.
• PriSrv+ supports bilateral access control, anonymity, and sender authentication while maintaining compatibility with popular wireless SD protocols including mDNS, BLE, and Wi-Fi.
• Experiments show PriSrv+ delivers up to 7.17x faster service broadcast and 3.32x faster anonymous mutual authentication compared to PriSrv, including tests on resource-constrained devices like Raspberry Pi.

Threat model

The threat model assumes an active network adversary aiming to breach privacy and integrity in wireless service discovery by performing eavesdropping, traffic analysis, injection of forged ciphertext, replay, and impersonation attacks. The attacker can observe multiple discovery sessions, attempt attribute guessing, link or track users based on visible information, and attempt to spoof services without possessing secret encryption keys. The adversary cannot break underlying cryptographic assumptions, nor access master secret keys or private keys issued to legitimate devices. The model demands bilateral anonymity, confidentiality, and sender authentication simultaneously.

Methodology — deep read

1. Threat Model and Assumptions: The adversary is modeled as an active network attacker capable of eavesdropping, traffic analysis, message injection, and replay attacks on wireless service discovery protocols. The attacker aims to breach confidentiality by deducing attributes, track users by linking sessions, impersonate devices through ciphertext forgery, or cause denial-of-service. The scheme assumes the attacker cannot compromise the master secret key or extract secret keys protected by cryptographic assumptions underlying bilinear pairings. Adversaries have no prior knowledge of the private attributes or keys other than what protocol messages reveal.

2. Data and Setup: Data used are service attributes attached to wireless devices/services expressed as unordered sets of attribute name-value pairs, where attribute names and values are arbitrary strings. Attribute policies are modeled as monotonic Boolean formulas represented via Linear Secret Sharing Schemes (LSSS) that are converted from access trees. No labeled datasets are involved as this is a cryptographic protocol design and evaluation. Realistic wireless environments including BLE, mDNS, and Wi-Fi contexts are considered for deployment.

3. Architecture and Algorithms: At the core is Fast and Expressive Matchmaking Encryption (FEME), combining optimized anonymous Key-Policy ABE (A-KP-ABE) and Ciphertext-Policy ABE (A-CP-ABE) schemes with a Hybrid-ABE scheme integrating sender authentication. FEME leverages bilinear pairings over Type-III groups and novel cryptographic primitives including randomness splitting and double re-randomization to conceal attribute values, reduce ciphertext size, and bind ciphertext components to prevent forgery. Partial hiding separates attribute names (visible) and values (hidden) to balance efficiency and privacy.

The scheme includes several algorithms: Setup generates system parameters; EKGen generates an attribute encryption key for the sender using Hybrid-ABE; DKGen and PolGen generate receiver decryption and policy keys from A-CP-ABE and A-KP-ABE respectively; Enc encrypts messages under both sender attributes and receiver policies; Dec decrypts only when bilateral policy satisfaction is met. The design eliminates reliance on pre-issued anonymous credentials by integrating sender authentication into the encryption key.

4. Training Regime: Not applicable as this is a cryptographic construction with proof-of-concept implementations rather than a ML system. Performance tuning includes adjusting randomness sampling, optimizing pairing operations, and ciphertext component sizes.

5. Evaluation Protocol: Protocols were evaluated by comparing computational cost (encryption/decryption time), ciphertext size, and communication overhead against PriSrv and other baselines. Metrics include number of pairing and exponentiation operations, ciphertext byte length, and latency in broadcast and mutual authentication operations. Evaluations were performed on multiple hardware platforms, including desktops, laptops, mobile devices, and Raspberry Pi IoT boards, simulating realistic wireless environments. The tests measured speedups, bandwidth reduction, and scalability as attribute sets and policies grew. Formal security proofs are presented to establish confidentiality, anonymity, and authenticity as per defined cryptographic games.

6. Reproducibility: The paper mentions formal proofs and provides algorithm pseudocode but does not explicitly state if source code or binaries are publicly released. Dataset details are tied to simulated wireless protocols rather than fixed corpora. Thus, reproducibility depends on re-implementing FEME modules from provided technical specifications.

Technical innovations

• First matchmaking encryption scheme supporting expressive access policies over an unbounded attribute universe with arbitrary string attributes, overcoming prior small-universe or binary vector limitations.
• Novel double re-randomization and binding technique that prevents encryption key extraction, ciphertext forgery, mixing attacks, and attribute guessing, enabling robust sender authentication.
• Integration of anonymous KP-ABE and CP-ABE with a Hybrid-ABE construction to achieve bilateral access control with privacy-preserving policy matching and sender authentication.
• Use of partially hidden access structures exposing only attribute names while concealing attribute values, balancing policy expressiveness, computational efficiency, and privacy.
• Randomness splitting technique that reduces vulnerability to attribute guessing attacks and reduces cryptographic overhead in encryption and decryption procedures.

Baselines vs proposed

• PriSrv (using ACME): Encryption time = baseline, PriSrv+ (FEME) = 7.62x faster encryption
• PriSrv: Decryption time = baseline, PriSrv+ = 6.23x faster decryption
• PriSrv: Ciphertext size = baseline, PriSrv+ = 87.33% reduction in ciphertext size
• Communication overhead - Service broadcast: PriSrv = baseline, PriSrv+ reduced by 87.33%
• Communication overhead - Anonymous mutual authentication: PriSrv = baseline, PriSrv+ reduced by 86.64%
• mDNS packet size: PriSrv reduced by 88.89% in PriSrv+
• BLE packet size: PriSrv reduced by 87.73% in PriSrv+
• Wi-Fi packet size: PriSrv reduced by 86.64% in PriSrv+

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.05902.

Fig 1: Technical Roadmap of FEME

Fig 7: Comparison of PriSrv+ and PriSrv

Fig 3 (page 12).

Limitations

• The reliance on bilinear pairings and complex group operations may still challenge highly constrained IoT devices despite improvements.
• The attribute universe is unbounded theoretically but large-scale empirical tests on extremely large attribute sets are not detailed.
• Detailed adversarial evaluation against adaptive attackers or advanced side-channel attacks was not presented.
• Compatibility tests cover major existing wireless standards but integration and deployment complexity in heterogeneous real-world networks require further study.
• No public code or dataset releases were mentioned, which could slow community verification and adoption.

Open questions / follow-ons

• How does FEME perform and scale with extremely large dynamic attribute sets, e.g., tens of thousands of diverse string attributes in real deployments?
• What are the resilience and performance trade-offs against side-channel or fault injection attacks on constrained devices implementing PriSrv+?
• Can the FEME scheme be integrated with post-quantum cryptographic primitives to future-proof confidentiality and authentication?
• How do real-world network conditions such as packet loss, jitter, and congestion impact PriSrv+ protocol effectiveness and latency compared to existing SD protocols?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, PriSrv+ offers a compelling cryptographic approach to mitigate device and service tracking risks in wireless networks by concealing sensitive attributes and enforcing mutual authentication with privacy guarantees. Techniques like FEME demonstrate how matchmaking encryption can strongly restrict access to services dynamically based on expressive, hidden policies—potentially useful in verifying genuine client attributes during service discovery or challenge issuance stages. The performance optimizations reducing ciphertext sizes and computation make such protocols feasible in resource-constrained environments common to IoT and mobile devices, aligning with security assurance goals in bot mitigation.

However, the complexity of deploying such cryptographic schemes and the requirement for bilateral policy agreement may pose integration challenges for real-time CAPTCHA workflows. Understanding novel cryptographic binding and re-randomization techniques could inspire new bot-defense mechanisms that protect challenge-response channels against impersonation and replay. Overall, this work elevates the security baseline for wireless service discovery, influencing how trust and privacy could be architected in systems that ultimately depend on CAPTCHA-like human verification to discern legitimate clients from bots.

Cite

@article{arxiv2606_05902,
  title={ PriSrv+: Privacy and Usability-Enhanced Wireless Service Discovery with Fast and Expressive Matchmaking Encryption },
  author={ Yang Yang and Guomin Yang and Yingjiu Li and Pengfei Wu and Rui Shi and Minming Huang and Jian Weng and HweeHwa Pang and Robert H. Deng },
  journal={arXiv preprint arXiv:2606.05902},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.05902}
}

Read the full paper

• arXiv:2606.05902 (abstract)
• arXiv:2606.05902 (PDF)