PriSrv: Privacy-Enhanced and Highly Usable Service Discovery in Wireless Communications Yang Yang1 , Robert H. Deng1 , Guomin Yang1 , Yingjiu Li2 , HweeHwa Pang1 , Minming Huang1 , Rui Shi3 , Jian Weng4
arXiv:2606.05821v1 [cs.CR] 4 Jun 2026
1. School of Computing and Information Systems, Singapore Management University, Singapore {yyang,robertdeng, gmyang,hhpang,mmhuang}@smu.edu.sg 2. Department of Computer Science, University of Oregon, USA ([email protected]) 3. Beijing Electronic Science and Technology Institute, Beijing, China ([email protected]) 4. College of Information Science and Technology, Jinan University, Guangzhou, China ([email protected]) Abstract—Service discovery is essential in wireless communications. However, existing service discovery protocols provide no or very limited privacy protection for service providers and clients, and they often leak sensitive information (e.g., service type, client’s identity and mobility pattern), which leads to various network-based attacks (e.g., spoofing, man-in-the-middle, identification and tracking). In this paper, we propose a private service discovery protocol, called PriSrv, which allows a service provider and a client to respectively specify a fine-grained authentication policy that the other party must satisfy before a connection is established. PriSrv consists of a private service broadcast phase and an anonymous mutual authentication phase with bilateral control, where the private information of both parties is hidden beyond the fact that a mutual match to the respective authentication policy occurred. As a core component of PriSrv, we introduce the notion of anonymous credentialbased matchmaking encryption (ACME), which exerts duallayer matching in one step to simultaneously achieve bilateral flexible policy control, selective attribute disclosure and multishow unlinkability. As a building block of ACME, we design a fast anonymous credential (FAC) scheme to provide constant size credentials and efficient show/verification mechanisms, which is suitable for privacy-enhanced and highly usable service discovery in wireless networks. We present a concrete PriSrv protocol that is interoperable with popular wireless communication protocols, such as WiFi Extensible Authentication Protocol (EAP), mDNS, BLE and Airdrop, to offer privacy-enhanced protection. We present formal security proof of our protocol and evaluate its performance on multiple hardware platforms: desktop, laptop, mobile phone and Raspberry Pi. PriSrv accomplishes private discovery and secure connection in less than 0.973 s on the first three platforms, and in less than 2.712 s on Raspberry Pi 4B. We also implement PriSrv into IEEE 802.1X in the real network to demonstrate its practicality.
I. I NTRODUCTION Service discovery (SD) protocols, such as Wi-Fi [1], AirDrop [2], and BLE [3], are essential components of networking systems that enable devices and services to dynamically discover and communicate with each other in a network environment. They facilitate the automatic detection and advertisement of available services, making it easier for devices to locate and interact with desired resources. However, there This is the full version of the research work published in Network and Distributed System Security Symposium (NDSS) 2024. https://dx.doi.org/10.14722/ndss.2024.24174
is a lack of highly usable approaches to sufficiently protect identification and private information in protocol executions, especially for privacy-concerned parties. A survey [4] showed that about 90% users considered the exposure of device names from wireless network services as a privacy risk, as such exposure may lead to adversarial inference of users’ private information such as mobility patterns, profiles, and locations [5], [6], [7], [8]. For instance, in public Wi-Fi, ISP could easily identify a person via the announced device names [9]. In IoT networks, an attacker may infer a user’s regular routine by collecting the service data from user’s smart devices [10]. Several vulnerabilities spanning from Wi-Fi, BLE to Apple Wireless Direct Link (AWDL) are discovered in recently years which lead to tracking, DoS, and MitM attacks on iOS and macOS [8]. On the other hand, users prefer high usability in accessing wireless network services, which include no pre-registered pairing, no third-party dependence for service discovery, and low computation and communication overheads. A major barrier in increasing user satisfaction for accessing wireless network services is the technical difficulty of elevating privacy protection without sacrificing high usability in wireless network protocols. Existing privacy-aware wireless network protocols and other related works fail to overcome this barrier as they either leak private information [11], [12], [13] or violate high usability requirements in protocol executions [14]. Our objective is to develop a privacy-enhanced and highly usable service discovery protocol between wireless network service access point (service provider) and client to enable them to discover each other within range and establish a secure communication channel only if they meet each other’s connection requirements. The challenges to achieve this objective are three folds: (1) ensure that services are only discoverable by an authorized set of clients; (2) enable clients to filter out unauthorized services without heavy computation; (3) allow both service provider and client to specify policies the other party must satisfy in order for their private information to be revealed. In certain service discovery protocols, such as AirDrop and BLE, both service provider and client are wireless devices, which necessitates reciprocal privacy protection. We propose a dual-layer architecture to solve this problem,
which includes an outer layer and an inner layer. In the outer layer, each service provider or client is associated with a set of public attributes (such as domain name) that can be revealed to everyone and a public authentication policy, which are used for fast bilateral policy matching without decryption. Specifically, a service provider broadcasts a ciphertext encrypted by its policy and public attributes. A client first checks whether its public attributes match with the service provider’s public policy, and vice versa, which filters the mismatch services accordingly. If and only if their public attributes satisfy the bilateral policy, the client can decrypt the ciphertext. In the inner layer, each party is associated with a set of private attributes (such as device ID) that are only revealed to the intended peers. Only when the decryption of the outer layer ciphertext is successful, the client can recover the private attributes of the service provider, which allows the client to authenticate the service provider by verifying the authenticity of the latter’s attributes, including both public attributes and private attributes. The service provider authenticates the client using the same mechanism. Then, they establish a session key using a secure key agreement protocol to enable secure communication between them. By applying the above duallayer architecture, PriSrv builds a private-enhanced service discovery protocol with high usability.
In addition to these privacy enhancement requirements, SD protocols are expected to meet the following high usability requirements. 1. No Pre-registered Pairing. Clients are not required to subscribe to or share a secret key with any service providers beforehand. It allows clients to discover and connect to service providers seamlessly without any manual setup or configuration. 2. No Third-party Dependency during Service Discovery Process. Service discovery should not depend on any external services such as a third-party server or a directory provider during protocol execution. Protocols relying on external servers presume a reliable Internet connection for mobile devices. However, this presumption may not hold in wireless communications (e.g., BLE communications). 3. No In-advance Identity Issuance. Users are not required to register to a third-party to obtain identity certification documents, such as certificates, credentials, etc. In-advance identity issuance has less impact on the usability of service discovery process since it occurs only once before the execution of SD protocol. We note that PriSrv requires in-advance identity issuance. B. Contributions We propose PriSrv, a service discovery protocol, to meet both privacy enhancement and high usability requirements. The main contributions of this work are summarized as follows. • A New Privacy-Enhanced Service Discovery Protocol with High Usability. PriSrv is the first privacy-enhanced and highly usable service discovery protocol that can be integrated into a wide range of wireless applications. • Anonymous Credential-based Matchmaking Encryption (ACME). We propose a novel cryptographic primitive called anonymous credential-based matchmaking encryption (ACME). ACME supports bilateral fine-grained policies and selective attribute disclosure for private mutual authentication in service discovery. ACME outperforms the matchmaking encryption (ME) in CRYPTO’19 [15] in terms of functionality and efficiency. This is a contribution of independent interest for the advancement of matchmaking encryption. • Fast Anonymous Credential. As a building block of ACME, we propose a fast anonymous credential (FAC) scheme to support anonymous authentication with selective attribute disclosure and multi-show unlinkability. A comprehensive comparison with existing anonymous credential schemes demonstrates its superior efficiency for credential showing and verification with constant and small credential. • Interoperability with Existing Protocols. To demonstrate interoperability, we present concrete methods for integrating PriSrv with mainstream service discovery protocols including Extensible Authentication Protocol (EAP), mDNS, BLE and AirDrop. Through experimentation, we show the applicability and effectiveness of PriSrv in real-world scenarios. • Formal Security Proofs. We provide formal security proofs for the security and privacy properties of PriSrv in
A. Privacy Enhancement and High Usability Requirements To mitigate the leakage of any private information in service discovery, SD protocols should meet the following privacy enhancement requirements. 1. Private Service Broadcast. Service contents broadcasted by service providers must be both confidential and unforgeable, preventing unintended clients from learning service content and enabling the detection of bogus service providers broadcasting fraudulent services. 2. Mutual Authentication. Service providers and clients authenticate each other in a secure manner to ensure that the private information of both parties will not be leaked to any unauthenticated entity. 3. Bilateral Anonymity. Both service providers and clients remain anonymous to a third-party during protocol execution, and no third-party can identify the private information of the involved parties. 4. Bilateral Flexible Policy Control. Both service providers and clients can specify fine-grained access policies for authorized peers and simultaneously check the satisfaction of policies from both sides, which guarantees that private information of both sides are only exposed to their authorized peers. 5. Selective Attribute Disclosure. It refers to the ability of an entity (either service provider or client) to choose which specific attributes they disclose to the other, while keeping other attributes undisclosed. It allows each entity to share only the necessary and relevant information while maintaining control over their private information. 6. Multi-Show Unlinkability. It allows a user to prove possession of a credential or attributes without revealing their identity or linking their actions across multiple sessions.
2
a security model that captures various attack vectors, such as intercepting, tampering with channel messages, replaying, injecting data packets, and interleaving messages among different sessions in realistic settings. • Deployment on Multiple Platforms in Real Networks: The performance of PriSrv is evaluated on multiple hardware platforms, including desktop, laptop, mobile phone and Raspberry Pi, in the Wi-Fi WPA-Enterprise framework. Our experiments demonstrate the efficiency of PriSrv across different platforms. The private service broadcast phase in PriSrv takes less than 0.483 seconds, and the anonymous mutual authentication phase takes less than 0.973 seconds on the first three devices. The delays stay well below 1 second, which humans perceive as an “immediate response” [16], [17]. While on Raspberry Pi, the delays are 1.189 and 2.712 seconds for private broadcast and mutual authenticationon, respectively, which demonstrates additional costs on IoT devices.
scheme [9] only requires clients to anonymously authenticate to service providers in a private manner, while the authentication/anonymity of service providers and private broadcast are not supported, making it vulnerable to MitM attacks and spoofing attacks. Among these protocols, DNS-SD relies on DNS records to advertise and discover services within a network. CBN scheme relies on a pre-registration pairing mechanism: service provider maintains a directory to control the access of subscribers while clients are required to register to service providers beforehand, where the size of directory grows linearly with the number of clients. Although Wi-Fi [1] and BLE [3] support mutual authentication, they dissatisfy other privacy enhancement requirements, including private broadcast, bilateral anonymity, bilateral flexible policy control, selective attribute disclosure and multishow unlinkability. Wi-Fi [1] enables devices to discover and connect to services available on a local-area network. Bluetooth Low Energy (BLE) [3] is designed for low-power devices, such as IoT devices and wearable devices, to advertise their available services, allowing other devices to discover and connect to them for data exchange and interaction. A common problem of Wi-Fi and BLE is that the private information of service providers and clients is advertised publicly in wireless network, which may induce user identification, impersonation attacks and spoofing attacks. A survey [4] indicated that 59% investigated devices periodically announce their owners’ real names for Wi-Fi network, which is deemed as a privacy risky by about 90% users. A deeplearning-based identification mechanism (with accuracy over 80%) was demonstrated in [23] to identify mobile devices from broadcast and multicast packets. Na et al. [11] proposed Wiattack to leverage the wide-deployed Wi-Fi devices (such as Wi-Fi APs) to conduct poisonous impersonation attacks, where the vulnerability is caused by the open nature of these cleartext advertisements. Similarly, BLE-equipped devices consistently advertise their unique identifiers in cleartext [10], making them vulnerable to BLE Spoofing Attacks (BLESA) [24]. Revealing of device identifiers in Wi-Fi and BLE is a stepping stone toward advanced attacks such as user profiling and tracking [10]. Large-scale tracking attack in real-time can be mounted by deploying multiple low-cost Wi-Fi and BLE nodes throughout an area. This allows adversaries to infer additional user information such as home and work locations, movement patterns and behavior profiling, which are useful for targeted tracking [25]. AirDrop [2], PrivateDrop [16] and WTSB [5] employ encryption and authentication mechanisms to protect communications in service discovery. AirDrop [2] is an SD protocol for file-sharing on Apple devices, which utilizes a combination of Wi-Fi and Bluetooth technologies to enable devices in close proximity to discover each other and share files wirelessly. AirDrop and PrivateDrop need to establish TLS connection with client and server certificates for authentication. PrivateDrop realizes private mutual authentication for AirDrop by protecting device identifiers in an optimized private set intersection
II. R ELATED W ORK A variety of protocols have been developed for service discover in network environments. As shown in Table I, none of them, except PriSrv, satisfy all privacy enhancement requirements. In particular, the protocols DNS-SD [18], mDNS [19], SSDP [20], UPnP [21] and CBN [9] do not meet any privacy enhancement requirement. First, DNS-based Service Discovery (DNS-SD) [18] utilizes the Domain Name System (DNS) to enable service discovery. It allows service providers to advertise their services by registering them with a DNS server, and clients can discover these services by querying the DNS server, which is widely used in local networks and the Internet. Second, multicast DNS (mDNS) [19] enables service discovery in local networks without the need for a central DNS server, and allows service providers to announce their services using multicast DNS packets, and clients can resolve and discover these services directly. Third, Simple Service Discovery Protocol (SSDP) [20] is designed based on the Internet protocol suite for advertisement and discovery of network services and presence information. Fourth, Universal Plug and Play (UPnP) [21] permits networked devices, such as personal computers, printers, Internet gateways, Wi-Fi access points and mobile devices to seamlessly discover each other’s presence on the network and establish functional network services. Lastly, CBN scheme [9] requires clients to subscribe to service providers so that service providers can unilaterally authenticate clients anonymously for service discovery. The above SD protocols are vulnerable to man-in-themiddle (MitM) attacks, spoofing attacks and denial-of-service (DoS) attacks due to the lack of proper privacy protection. Bai et al. [12] launched MitM attacks against mDNS and illustrated how a malicious device can impersonate a printer by spoofing its mDNS hostname. According to Wang et al. [22], UPnP is vulnerable to DoS attacks: a device receiving a request from a potentially spoofed control point may respond to the supposed requester, unknowingly contributing to the amplification and intensification of the attack. CBN
3
Privacy Enhancement SD Protocols
Private
Mutual Bilateral Bilateral Flex.
Broadcast Authn.
Pol. Ctrl.
×
×
×
×
×
×
×
×
×
×
×
×
×
×
× √
×
×
×
×
×
×
×
×
×
×
×
×
√
× √
×
×
×
×
×
mDNS [19]
×
SSDP [20]
×
UPnP [21]
×
Wi-Fi [1]
×
√
BLE [3]
×
AirDrop [2]
×
PrivateDrop [16]
×
CBN [9]
× √
× √
× √
√
√
√
PriSrv
Multi-Show
Anon.
DNS-SD [18]
WTSB [5]
High Usability
Sel. Attr.
√
Disclosure Unlinkability
×
×
×
×
×
×
× √
× √
× √
No Pre-reg. No 3rd-party No In-advance Pairing √
Dependence
ID Issuance
√
× √
×
√
√
× √
√
√
√
√
√
√
√
√
√
√
√
× √ √
√ √ √
× √ × × × × ×
TABLE I: Comparison of Service Discovery Protocols
a Diffie-Hellman-based Private Set Intersection (PSI) scheme, which exclusively entails exponentiation computations. Moreover, WTBS [5] further enhances privacy by encrypting broadcast messages, achieving private broadcasting in addition to these features. WTSB has the advantage of high efficiency due to the usage of efficient identity-based prefix encryption scheme. Conversely, PriSrv utilizes both exponentiation and bilinear pairing operations within ACME, and the time consumption increases with the complexity of access policy. Therefore, PriSrv achieves improved privacy but incurs a higher computational overhead as a trade-off. After conducting a comprehensive comparison, it becomes evident that PriSrv stands out as the only SD protocol that successfully meets all the privacy enhancement requirements. As for high usability, PriSrv satisfies no pre-registerd pairing and no third-party dependence during service discovery. PriSrv does require in-advance identity issuance, but it does not affect the service discovery process.
protocol [16]. WTSB [5] realizes private service discovery by leveraging prefix encryption (a variant of identity-based encryption) and standard digital signature-based key exchange protocol. WTSB [5] supports private broadcast, mutual authentication and bilateral anonymity. However, these SD protocols (AirDrop, PrivateDrop [16] and WTSB [5]) suffer from MitM attacks, DoS attacks, impersonation attacks or user tracking attacks due to the lack of privacy enhanced properties, such as bilateral policy control, selective attribute disclosure and multi-show unlinkability. The attacker is able to link multiple sessions using client and server certificates in AirDrop and PrivateDrop protocols. Stute et al. [7] exposed several security and privacy vulnerabilities in Apple Wireless Direct Link (AWDL) ranging from design flaws to implementation bugs leading to (i) MitM attacks enabling stealthy modification of files transmitted via AirDrop, (ii) DoS attacks disrupting communications, and (iii) privacy leaks enabling user identification and long-term tracking. Bai et al. [12] demonstrated impersonation and spoofing attacks on certain Zeroconf protocols (e.g. AirDrop), which even allows attackers to steal clients’ SMS messages, documents, email notifications and photos [13]. Heinrich et al. [16] discovered a series of flaws in AirDrop that allow attackers to learn phone numbers and email addresses of both sender and receiver devices. As stated in the work [16], users of PrivateDrop can be tracked via UUIDs in the TLS certificates used for establishing the protocol communication channels. WTBS [5] dissatisfies bilateral flexible policy control: service providers have the ability to specify the type of clients they intend to communicate with, but clients do not have the option to choose the service providers they want to communicate with. Furthermore, WTBS [5] is susceptible to user tracking attack due to the lack of multi-show unlinkability. AirDrop and PrivateDrop offer mutual authentication, while PrivateDrop provides an additional feature of bilateral anonymity. The fundamental building block of PrivateDrop is
III. P RELIMINARIES A. Notation and Bilinear Pairing Let ⃗x denote the full attribute set, ⃗x(in) the private attributes for an inner layer and ⃗x(out) the public attributes for an outer layer, where ⃗x(in) , ⃗x(out) ⊆ ⃗x. Let f : {0, 1}n → {0, 1} denote the policy; f (⃗x) = 1 denote ⃗x satisfying f , and f (⃗x) = 0 denote ⃗x not satisfying f . $ Let s ← − S denote s sampled uniformly at random from a set S; N denote the natural number; λ ∈ N denote the security parameter; [n1 , n2 ] denote {n1 , · · · , n2 }; PPT denote probabilistic polynomial time; Zp represent the group of integers modulo p, and Z∗p = Zp \{0}. We use lower case boldface to denote (column) vectors and upper case boldface to denote matrices. Denote a bilinear group with Type-3 pairings as BG = (G1 , G2 , GT , e, p), where there is no efficiently computable isomophism between G1 and G2 . Let g1 ∈ G1 , g2 ∈ G2 and gT = e(g1 , g2 ) ∈ GT be the respective
4
generators. For a matrix A over Zp , define [A]1 := g1A , [A]2 := g2A , [A]T := gTA , where exponentiation is carried out component-wise. B. Assumptions Definition 3.1. (Discrete Logarithm (DL) Assumption). Let g be a generator of a cyclic group G. DL assumption holds if for all PPT adversary A, the advantage function $ a AdvDL − Z∗p . A (λ) := P r[A(g, g ) = a] is negligible, where a ← Definition 3.2. (Decisional Diffie-Hellman (DDH) Assumption). Let g be a generator of G and T = (g, g a , g b ) ∈ G3 , $ where a, b ← − Z∗p . DDH assumption holds if for all PPT adversary A, the advantage |P r[A(T , g ab ) = 1] − P r[A(T , g c ) = $ 1]| is negligible, where c ← − Z∗p . Definition 3.3. (Matrix DDH (MDDHk ) Assumption) [26]. Let ℓ > k ≥ 1, d ≥ 1. MDDHk assumption holds if k for all PPT adversary A, the advantage AdvMDDH (λ) := A |P r[A([M]1 , [MS]1 ) = 1] − P r[A([M]1 , [U]1 ) = 1]| is neg$ $ $ − Zℓ×k − Zk×d and U ← − Zℓ×d ligible, where M ← p , S← p p .
ag , bg < cg . The size m of a formula is the number of edges in the underlying DAG and the depth d of a formula is the length of the longest path from the output node. Lemma 2.1 in Katsumata’s work [27] states the well-known equivalence between the monotone Boolean formulae and NC1 circuits.
C. Linear Secret Sharing for Monotone Boolean Formulae
IV. P RI S RV ’ S OVERVIEW
The information-theoretic linear secret sharing for monotone Boolean formulae [26], [27] is described below. share(f, µ). Input: A formula f : {0, 1}n → {0, 1} of size m (i.e., the number of edges in f is m), and a secret µ ∈ Zp . 1) $ For each non-output wire j = 1, · · · , m − 1, select µ̂j ← − Zp . For the output wire, set µ̂m := µ. 2) For each outgoing wire j from input node i, add µj := µ̂j to the output set of shares and set ρ(j) := i. 3) For each AND gate g with input wires a, b and output wire c, add µca := µ̂c + µ̂a + µ̂b ∈ Zp to the output set of shares and set ρ(c) := 0. 4) For each OR gate g with input wires a, b and output wire c, add µca := µ̂c + µ̂a ∈ Zp and µcb := µ̂c + µ̂b ∈ Zp to the output set of shares and set ρ(ca ) := 0 and ρ(cb ) := 0. 5) Output ({µj }j∈[m̂] , ρ). reconstruct(f, x, {µj }ρ(j)=0∨xρ(j) =1 ). Input: A formula f , ⃗x ∈ {0, 1}n , and {µj }ρ(j)=0∨xρ(j) =1 . From the leaves of the formula to the root, calculate the output wire value µ̂c at each node. 1) Given µ̂a , µ̂b associated with the input wires a and b of an AND gate, compute µ̂c = µc − µ̂a − µ̂b . 2) Given µ̂a (or µ̂b ) associated with the input wires a (or b) of an OR gate, compute µ̂c = µca − µ̂a (or µ̂c = µcb − µ̂b ). 3) Output µ = µ̂m .
First, we present a technical overview of PriSrv. Next, we provide an example to illustrate how PriSrv is used. Finally, we highlight how PriSrv meets all privacy-enhancement and high usability requirements. Technical overview. At a high level, PriSrv is a private service discovery protocol that ensures services are only discoverable by an authorized set of clients. PriSrv consists of a private service broadcast phase and an anonymous mutual authentication phase as shown in Fig. 1. PriSrv’s design incorporates a novel crypto-enforced construction that enables both service providers and clients to express flexible access control policies and disclose partial attributes. To meet the privacy enhancement and high usability requirements outlinted in §I-A, we design a duallayer matching mechanism: an outer layer defines bilateral public authorization policies for filtering unauthorized service providers and clients based on their public attributes; an inner layer performs mutual authentication based on the selectively disclosed private attributes. We design a new cryptographic primitive, named anonymous credential-based matchmaking encryption (ACME), to realize such a dual-layer design in PriSrv. Anonymous credential (AC) realizes attribute based anonymous authentication with selective attribute disclosure, making it a potential tool for ACME construction. Existing AC schemes suffer from either large credential sizes or cumbersome show and verification mechanisms [28], [29], [30], rendering them unsuitable for privacy-enhanced and highly usable service discovery in wireless networks. We design a new AC scheme, named fast anonymous credential (FAC) as a building block of ACME. To realize bilateral policy control in ACME, one promising technology is the Matchmaking Encryption (ME) proposed by Ateniese et al. in CRYPTO’19 [15]. In ME, sender (snd) and
Fig. 1: Overview of PriSrv
D. NC1 Circuit and Monotone Formulae We define NC1 circuit and monotone Boolean formulae following Kowalczyk’s [26] and Katsumata’s [27] works. A monotone Boolean formula f : {0, 1}n → {0, 1} is specified by a directed acyclic graph (DAG) with three kinds of nodes: input gate nodes, gate nodes and a single output node. Input nodes have in-degree 0 and out-degree 1, AND/OR nodes have in-degree (fan-in) 2 and out-degree (fan-out) 1, and the output node has in-degree 1 and out-degree 0. We number the edges (wires) 1, 2, · · · , m, and each gate node is defined by a tuple (g, ag , bg , cg ), where g : {0, 1}2 → {0, 1} is either AND or OR, ag , bg are the incoming wires, cg is the outgoing wire and
5
receiver (rcv) possess a set of attributes ⃗xsnd and ⃗xrcv , respectively. The sender is able to specify an authorization policy fsnd for the receiver’s attributes ⃗xrcv to satisfy, and vice versa. ME enables both participants to specify fine-grained policies for encrypted data, which satisfies our need for bilateral policy control. Nonetheless, the ME in [15] has three limitations: (1) the conception of ME to support expressive policies relies on heavy cryptographic tools, including Functional Encryption (FE) and general Zero-Knowledge Proof (ZKP), whose known instantiations are still far from practical; (2) ME does not support selective attribute disclosure; (3) concrete instantiations of ME [15], [31] only support identity-based equality matching. It remains an open problem to develop an efficient ME that supports fine-grained policy based fuzzy matching [15]. We develop ACME to solve this open problem and overcome the above limitations. We further develop PriSrv based on ACME to meet both privacy enhancement and high usability requirements. Example. We provide a smart office example to exemplify the use of bilateral policy control and selective attribute disclosure in PriSrv. Consider a screen mirroring service provided by a smart TV, which only allows authorized devices to connect to it. On the other hand, a client device should only project its screen to an authorized screen mirroring service device to prevent any leakage of private information. The service type in this scenario is the screen mirroring service, and the service parameters include resolution, refresh rate, etc. The smart TV is associated with a set of attributes: ⃗xs =(device type, vendor, model, OS, domain name, device name, location, IP address, security domain), where the first five are public attributes and the rest are private. The mirroring service provider may (out) select a set of public attributes ⃗xs =(device type, vendor, domain name) to be used in the outer layer, and a set of (in) private attributes ⃗xs =(IP address) to be used in the inner layer. The client device is associated with another set of attributes: ⃗xc =(device type, model, OS, department, device name, classified device, IP address, security domain), where the first four are public attributes and the rest are private. The (out) client selects a set of public attributes ⃗xc =(device type, OS, department) for outer layer matching, and a set of private (in) attributes ⃗xc =(classified device, security domain) for inner layer authentication. To realize bilateral control, the service provider (i.e., the smart TV) sets a service policy as
that the public attributes of the service provider (and the client, respectively) satisfy the policy of its peer. The private attributes selected by smart TV and client device are used for mutual authentication. How PriSrv Meets Requirements. PriSrv meets both privacy enhancement and high usability requirements as outlined in §I-A. - Private Service Broadcast & Mutual Authentication. The messages broadcasted by service providers are encrypted using ACME such that only intended clients can obtain the decrypted information. Both service providers and clients authenticate each other’s private attributes before establishing a secure communication channel. - Bilateral Anonymity & Bilateral Flexible Policy Control. Both service providers and clients maintain their anonymity during the discovery process. Bilateral flexible policy control is achieved via ACME, as decryption fails if any protocol participant’s policy is not satisfied by its peers’ attributes. - Selective Attribute Disclosure & Multi-Show Unlinkability. According to the minimum privacy leakage principle, any participant in PriSrv only reveals a subset of its attributes to its peer. Both service provider and client select a subset of their attributes, including public attributes and private attributes to generate their authentication tokens. Multi-show unlinkability of PriSrv is inherited from that of FAC, which ensures the unlinkability of multiple instances of authentication tokens generated by the same entity across multiple protocol sessions (even using the same subset of non-unique attributes). - No Pre-registered Pairing & No Third-party Dependency for Service Discovery. PriSrv protocol execution does not require any service provider to know its clients, or any client to subscribe to its service providers in advance. PriSrv operates without relying on any external services during protocol execution. Threat and Attacker Model. The credential issuer is considered trustworthy to issue and revoke anonymous credentials. Both service providers and clients in the protocol are considered untrustworthy, as they have the potential to launch any passive or active attacks. Specifically, a service provider may attempt to impersonate other providers by broadcasting deceptive messages or to track clients’ activities. Likewise, a client may impersonate other clients to obtain unauthorized network access. Following the Canetti-Krawczyk model for authenticated key-exchange (AKE) in [32], [33] and the service discovery model in [5], the attackers against PriSrv include malicious service providers, clients, and external adversaries. We aim to comprehensively model the attackers’ capabilities in the real world to gain full control over public network communication. This control encompasses actions such as revealing certain protocol secrets, intercepting or tampering with channel messages, replaying, delaying, injecting or dropping data packets, and interleaving messages from different sessions, etc. They are capable to launch various types of attacks, including eavesdropping attacks, spoofing attacks, impersonation attacks, man-in-the-middle attacks, etc. The attackers’ goals include:
Device Type = “Smart phone ∨ Laptop”
fs = V V
OS = “Android ∨ iOS ∨ Windows” Department = “A ∨ B” .
The client device specifies a connection policy as ^ fc = Device Type = “TV” Vendor = “C ∨ D” V Domain Name = “*.XYZ.COM” . The screen mirroring service can be discovered by the client (out) (out) if and only if fs (⃗xc ) = 1 ∧ fc (⃗xs ) = 1, which indicates
6
(1) breaking authenticated key-exchange security; and (2) revealing sensitive information pertaining to clients or service providers, enabling attackers to track their activities. Formal Security Definition and Analysis. The formal security models of private service discovery include service discovery security and bilateral anonymity, which is followed by formal security proofs. The formal security models and proofs are shown in Appendix C.
• UserKeyGen(pp) → (upk, usk): The user with uid $ samples usk ← − Z∗p , computes upk ← husk , and creates a signature proof of knowledge π1 as SPK{usk : upk = husk }. The issuer registers upk if VerifySPK (upk, π1 ) = 1 holds. • ⟨Issue.I(sk, upk) ⇄ Issue.U(uid, ⃗x, usk)⟩ → cred. The secure channel between issuer and user can be established by standard protocols, such as TLS. (1) User sends uid and attributes ⃗x = {xi }i∈[1,n] to issuer.
V. FAST A NONYMOUS C REDENTIAL
(2) The issuer samples r ← Z∗p to calculate cred ← (σ1 , σ2 ), where
$
We propose a fast anonymous credential scheme (FAC) as a component of ACME to enable fast anonymous authentication while maintaining a constant and small credential size. FAC supports re-randomization of credentials to support multi-show unlinkability, and selective attribute disclosure. We provide the syntax for anonymous credentials and proceed to construct a concrete FAC scheme for mobile devices.
σ1 ← hr , σ2 ← upkr·y0 · hr(τ +
Pn
i=1 yi xi +yn+1 ·uid)
.
(3) The user accepts the credential cred if the following equation holds Yn uid e(W · Y0usk · Yn+1 Yixi , σ1 ) = e(g, σ2 ). i=1
• Show(uid, {xi }i∈I , cred, usk, m) → tok: The user generates a token on selected attribute subset {xi }i∈I , I ⊆ [1, n]. $ Select t1 , t2 ← Z∗p to compute Y Y Y x x T1 = g t1 Yj j , T2 = ( Yi )t1 Zi,jj ,
A. Syntax of Anonymous Credential Anonymous credential (AC) is formally defined by the following PPT algorithms [35], [36]. • Setup(1λ , 1n ) → pp: On input a security parameter λ and a function parameter 1n , it outputs public parameter pp, which is an implicit input to all the other algorithms. • CredKeyGen(pp) → (pk, sk): On input pp, this algorithm creates credential issuer’s public/secret keys pk/sk, where pk is an implicit input to the algorithms below. • UserKeyGen(pp) → (upk, usk): On input pp, the algorithm generates user’s public key upk and secret key usk. • ⟨Issue.I(sk, upk) ⇄ Issue.U(uid, ⃗x, usk)⟩ → cred. This is an interactive protocol for AC issuance executed between the issuer and a user over a secure channel. The user executes the protocol by inputting a user’s identity uid, an attribute set ⃗x and a secret key usk. The credential issuer runs the protocol by inputting sk and upk. The issuer hands over a credential cred to user via secure channel. • Show(uid, {xi }i∈I , cred, usk, m) → tok: On input uid, an attribute subset {xi }i∈I ⊆ ⃗x (I ⊆ [1, n]), cred, usk and a message m, it outputs an authentication token tok. • Verify(tok, m) → b ∈ {0, 1}. On input tok and m, it outputs b = 1 if tok is valid; otherwise, it outputs b = 0. Following the security definitions in [35], [36], the correctness, unforgeability, anonymity and unlinkability of AC are defined, which are shown in Appendix A.
j∈[1,n]\I
i∈I ′
i∈I ′ ,j∈[1,n]\I
σ̄1 = σ1t2 , σ̄2 = σ2t2 σ̄1t1 , and create π2 as σ̄1 = σ1t2 , σ̄2 = σ2t2 σ̄1t1 , σ1 = hr , n P (m), SPK (usk, uid) : r(τ + yi xi +yn+1 ·uid) i=1 σ2 = (husk )r·y0 h where I ′ = I ∪ {0, n + 1}. The token is tok ← ({xi }i∈I , T1 , T2 , σ̄1 , σ̄2 , π2 ). • Verify(tok, m) → b ∈ {0, 1}. The algorithm outputs b = 1 if VerifySPK (tok, m) = 1. Otherwise, it returns b = 0. Instantiation of SPK. Following the standard Fiat-Shamir paradigm, SPKs in FAC are instantiated as follows. The SPK π1 : f $ g← Prove: Prover selects usk Z∗p and computes γ ← husk , g − c · usk mod p. Return π1 ← c ← H(upk, γ), usk = usk (c, γ, usk). ? Verify: Given upk and SPK π1 , the verifier checks c = ? H(upk, γ), γ = husk upkc . It outputs 1 if these equations hold, and 0 otherwise. The SPK π2 : $ g ← f usk Prove: Prover selects uid, Z∗ and computes
B. Construction of FAC Our construction of FAC is given below. • Setup(1λ , 1n ) → pp: Let λ be the security parameter, and n the attribute number in the system. Run G = $ (p, G1 , G2 , GT , e) ← − GGen(1λ ), and output pp = (g, h, n), where g, h are the generators of G1 , G2 , respectively. • CredKeyGen(pp) → (pk, sk): The issuer samples $ τ, yi ← − Z∗p , computes W ← g τ , Xi ← hyi , Yi ← g yi for i ∈ [0, n + 1], and Zi,j = g yi ·yj for 0 ≤ i ̸= j ≤ n + 1. Then, it outputs secret key sk = (τ, {yi }i∈[0,n+1] ) and public key pk ← (W, {Xi , Yi }i∈[0,n+1] , {Zi,j }0≤i̸=j≤n+1 ).
p
uid Λ ← e(Y0usk Yn+1 , σ̄1 ), c ← H(m, {xi }i∈I , Λ, T1 , T2 , σ̄1 , σ̄2 ), g − c · usk f uid ← uid − c · uid mod p, usk ← usk mod p. Set π2 ← (c, uid, usk, Λ), and return tok ← ({xi }i∈I , T1 , T2 , σ̄1 , σ̄2 , π2 ). ? Verify: Given tok, the verifier checks c = H(m, {xi }i∈I , Λ, ? uid T1 , T2 , σ̄1 , σ̄2 ), e(Y0usk Yn+1 , σ̄1 )−1 · Λ = [e(g, σ̄2 ) · Γ]c , e(T1 , Q Q ? xi −1 . i∈I ′ Xi ) = e(T2 , h), where Γ = e(W ·T1 · i∈I Yi , σ̄1 ) It outputs 1 if these equations hold, and 0 otherwise. f
7
g
can simultaneously support expressive policy (e.g., monotone Boolean formulae) and policy hiding is of theoretical interest only since no concrete instantiation has been proposed. Although identity-based ME schemes supporting equality policies were introduced in [15], [31], they do not fit for highlyusable service discovery since in general participants of service discovery are unaware of their peers’ identities and thus cannot define identity-based equality policies. Meanwhile, we notice that the original ME schemes [15], [31] support hidden policies, but they are not ideal for service discovery because such schemes require clients to blindly decrypt every service advertisement, bringing high costs when multiple services are in presence. To balance fast service discovery and privacy protection, ACME adopts a dual-layer matching design for a sender (snd) to encrypt any message M and send the ciphertext to a receiver (rcv) with bilateral policy control. Sender snd receives an anonymous credential credsnd from a credential issuer for all its attributes ⃗xsnd . As shown in Fig. 2, ACME consists of an inner layer and an outer layer. In the inner layer, sender snd generates an authentication token using F AC.Show from a message M and selected attributes (including public and private attributes) based on the received credential credsnd . In the outer layer, sender snd encrypts the authentication token and the message M using an authentication policy fsnd (specified by snd for rcv) and the sender’s selected public attributes. Then, sender snd transmits the ciphertext to receiver rcv. On the receiver side, the ciphertext is decrypted in the outer layer using receiver’s policy decryption key and attribute decryption key to recover the authentication token and message M . In the inner layer, the authentication token is verified using FAC.Verify to authenticate the sender’s selected private attributes, public attributes and the message M . Impersonation Resistance. ACME is the core component of PriSrv to prevent impersonation attacks. As shown in Fig. 2, both the public and private attributes are used as inputs for authentication token generation in the inner layer. This design has been purposefully engineered to provide robust protection against impersonation attacks. Although the public attributes used in the service provider’s outer layer are public, a malicous service provider (without all the authorized public attributes) is not able to impersonate any legal provider since the forged authentication token cannot pass the verification by the receiver (using FAC.Verify). On the other hand, if the public attributes used in the outer layer are not unique, PriSrv relies on the inner layer to authenticate both public and private attributes, which rules out any impersonation attack. Meanwhile, an attacker impersonating a legitimate receiver cannot be successful in decryption without a valid secret key.
Fig. 2: Architecture of ACME
Our fast anonymous credential (FAC) scheme has the following advantages: 1) FAC offers a non-interactive Show ⇆ Verify process, ensuring fast anonymous authentication. 2) FAC generates anonymous credentials of a constant and small size. 3) An authentication token generated in FAC consists of only two group elements. The construction is based on the unlinkable redactable signature (URS) scheme [36], which is one of the initial frameworks for generating constantsize redactable signatures on attributes ⃗x = (x1 , · · · , xn ). FAC generates an anonymous credential cred based on the URS scheme [36]. When a request is made to verify the authenticity of a subset of attributes {xi }i∈I ⊆ ⃗x, the Show algorithm in FAC performs the following steps: it derives an authentication token tok from the anonymous credential cred, and then produces a signature proof of knowledge (SPK) for the authentication token. The Verify algorithm in FAC is responsible for checking the validity of tok. The correctness proof of FAC is shown in Appendix A. Theorem 5.1. The FAC scheme is secure (i.e., achieves unforgeability, anonymity and unlinkability) under the DL and DDH assumptions. The proof of Theorem 5.1 is shown in Appendix A. VI. A NONYMOUS CREDENTIAL - BASED MATCHMAKING ENCRYPTION (ACME) We introduce a new cryptographic primitive named ACME to support several core features in PriSrv protocol, including bilateral policy control, anonymous authentication and selective attribute disclosure. ACME is a variant of ME where the sender and the receiver can use anonymous credentials to prove their attributes without revealing their identities. This is useful because it allows for stronger privacy guarantees and flexible policy enforcement in scenarios such as secure online dating, e-voting, and anonymous whistleblowing, where the parties do not trust each other or third parties. ACME is of independent interests for advancing research on Matchmaking Encryption.
B. Syntax of ACME
A. Design Intuition
Anonymous credential-based matchmaking encryption (ACME) is formally defined below, and the correctness of ACME is defined in Appendix B.
Matchmaking Encryption (ME) is a natural starting point to construct ACME. However, the conception of ME [15] that
8
• Setup(1λ , 1n ): On input a security parameter 1λ and a function parameter 1n , this algorithm outputs the master public/secret keys mpk/msk. Note that mpk is implicit input in all the following algorithms. • CredKeyGen(mpk) → (pk, sk): On input mpk, this algorithm creates credential issuer’s public key pk and secret key sk. pk is an implicit input to the following algorithms. • UserKeyGen(mpk) → (upk, usk): On input mpk, the algorithm generates user’s public key upk and secret key usk. • ⟨Issue.I(sk, upk) ⇄ Issue.U(uid, ⃗x, usk)⟩ → cred. The issuer inputs sk, upk and the user inputs uid, usk, full attributes ⃗x. The issuer interacts with user to generate a credential cred for the user. • DKGen(msk, ⃗xrcv ): On input msk and attributes ⃗xrcv , this algorithm outputs an attribute decryption key DK⃗xrcv . • PolGen(msk, frcv ): On input msk and policy frcv , this algorithm outputs a policy decryption key DKfrcv . • Enc(credsnd , ⃗xsnd , fsnd , M ): On input credsnd , full attributes ⃗xsnd , policy fsnd and message M as input, the sender (in) selects a set of private attributes ⃗xsnd for an inner layer and a (out) set of public attributes ⃗xsnd for an outer layer from ⃗xsnd . It (out) (in) firstly generates a token toksnd for ⃗xsnd , ⃗xsnd and message M . Then, it encrypts (M, toksnd ) using the public attributes (out) ⃗xsnd and policy fsnd , and outputs a ciphertext CT⃗xsnd ,fsnd . • Dec(DK⃗xrcv , DKfrcv , CT⃗xsnd ,fsnd ): On input DK⃗xrcv , DKfrcv and CT⃗xsnd ,fsnd , the receiver recovers (M, toksnd ) iff (out) (out) fsnd (⃗xrcv ) = 1 and frcv (⃗xsnd ) = 1; otherwise, it outputs ⊥. If the above step succeeds, the receiver verifies toksnd for (out) (in) ⃗xsnd ∪ ⃗xsnd and M . It outputs the message M if the token is valid; otherwise, it outputs ⊥. Remark. In encryption algorithm, the authentication token toksnd is generated for selected public and private attributes rather than just private attributes. The purpose is to authenticate sender’s selective attributes in both layers to prevent spoofing attacks. The token also authenticates M to prevent message forgery. Definition 6.1. An ACME scheme is secure if it satisfies privacy, authenticity, anonymity and unlinkability. The formal definitions of these security properties are provided in Appendix B.
candidates because they are in the dual form with common parameters and support Boolean formulae (equivalent to NC1 circuits1 ). Nonetheless, the decryption process of the dual ABE schemes in [26] involves a large number of time-consuming pairing operations (depending on the complexity of NC1 ). If we construct ACME based on the dual schemes given in [26], such ACME would incur high computational costs for wireless devices. Meanwhile, we notice that for KP-ABE, Katsumata et al. proposed an improved scheme in [27] with faster decryption, which requires only a constant number of pairing operations. We apply the technique in [27] to improve CP-ABE scheme in [26] to achieve fast decryption with a constant number of pairing operations. By integrating the improved CP-ABE with Katsumata’s KP-ABE [27], which are also in a dual form, we can achieve both fine-grained bilateral policy control and fast decryption. Concrete Construction. Our ACME scheme for general policies is built from the above fast anonymous credential scheme FAC, a symmetric encryption scheme SE = (SGen, SEnc, SDec) with key space K, and a hash function H : {0, 1}∗ → K. $ Setup(1λ , 1n ): Run G = (p, G1 , G2 , GT , e) ← − GGen(1λ ). Let g, h be the generators of G1 , G2 , respectively. Run $ $ FAC.Setup(1λ , 1n ) to get pp. Sample A ← − Zk×2k , B ← − p $
$
Zk×k , U0 , Wi ← − Z2k×k for i ∈ [n], v ← − Z2k p p p , output msk = (v, B, U0 , W1 , · · · , Wn ), mpk = (pp, [A]1 , [AU0 ]1 , [AW1 ]1 , · · · , [AWn ]1 , e([A]1 , [v]2 )). CredKeyGen(mpk) → (pk, sk): This algorithm executes FAC.CredKeyGen to generate issuer’s pk and sk. UserKeyGen(mpk) → (upk, usk): This algorithm executes FAC.UserKeyGen to generate user’s upk and usk. ⟨Issue.I(sk, upk) ⇄ Issue.U(uid, ⃗x, usk)⟩ → cred. This algorithm executes FAC.Issue to create user’s credential cred. DKGen(msk, ⃗xrcv ): To generate an attribute decryption key $ for receiver’s attributes ⃗xrcv , it samples r ← − Zkp and outputs DK⃗xrcv = (dk1 , dk2 , dk3 ): X dk1 = [v+U0 Br]2 , dk2 = [Br]2 , dk3 = [ Wi Br]2 . (out)
C. Construction of ACME FAC in §V is leveraged in the inner layer of ACME for authentication. For outer-layer encryption and bilateral policy control, we resort to attribute-based encryption (ABE) that supports expressive access policies. However, ABE only supports unilateral policy control. To enable bilateral control, a potential solution is to integrate key policy (KP-)ABE and ciphertext policy (CP-)ABE so that the secret key of CPABE (resp. KP-ABE) functions as attribute decryption key (resp. policy decryption key) produced by the DKGen (resp. PolGen) algorithm. Although the idea seems straightforward, there are a few subtleties to be addressed. Firstly, compact ABE schemes are preferred for compact ciphertext size and key size. The compact KP-ABE and CP-ABE schemes proposed by Kowalczyk et al. [26] in Eurocrypt’19 are natural
i:xr,i
=1
PolGen(msk, frcv ): To generate a policy decryption key for receiver’s policy frcv , this algorithm samples $ $ ({vj }j∈[m̂r ] , ρr ) ← − share(frcv , v), rj ← − Zkp and outputs DKfrcv = ({dkj , dkρr (j),j , {dki,j }i∈[n]\{ρr (j)} }j∈[m̂r ] ) : dkj = [rj ]2 , dkρr (j),j = [vj + Wρr (j) rj ]2 , dki,j = [Wi rj ]2 , where W0 = 0, m̂r is the number of shares for receiver’s policy, and ρr is a mapping from the indices of the shares to 1 In computational complexity theory, NCi is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and depth O(logi n), or the class of decision problems solvable in time O(logi n) on a parallel computer with a polynomial number of processors, where NC is short for ”Nick Pippenger’s Class”.
9
the indices of receiver’s public attributes2 . For ρr (j) = 0, we X Y Y µj have [n]\{ρr (j)} = [n]. AWi ]1 , cti,j = [s⊤ AU0 + ŝ⊤ Enc(credsnd , ⃗xsnd , fsnd , M ): The sender selects the private (out) j∈Ss i:x(out) =1 i:xr,i =1 (in) (out) r,i attributes ⃗xsnd for inner layer and public attributes ⃗xsnd for P outer layer from ⃗xsnd . Then, it runs FAC.Show to obtain where ŝ⊤ = j∈Ss µj s⊤ (in) (out) ∗ j . toksnd for ⃗xsnd , ⃗xsnd and M ∈ {0, 1} . Next, it encrypts (out) (out) Therefore, for all frcv , ⃗xsnd such that frcv (⃗xsnd ) = 1, we (M, toksnd ) using the public attributes ⃗xsnd and policy fsnd have: as follows. $ $ k ⊤ Q The sender samples es, s, sj ← − Zp , ({uj }j∈[m̂s ] , ρs ) ← − ω e ct′2 , j∈Sr dkj j · ⊤ share(fsnd , s AU0 ), K ∈ GT , and compute CT⃗xsnd ,fsnd = ωj Q Q dki,j e ct′1 , j∈Sr e j , ctρ (j),j , {cti,j }i∈[n]\{ρ (j)} }j∈[m̂ ] ) : (out) (ctM , ct0 , ct′1 , ct′2 , ct1 , {ct i:xs,i =1 s s s ⊤P AWi 1 , [r̂]2 ) e es ctM = SE.SEnc(H(K), (M, toksnd )), (out) i:xs,i =1 ⊤ = P ⊤ ct0 = e([es A + s⊤ A]1 , [v]2 ) · K, e [es A]1 , [v + i:x(out) =1 Wi r̂]2 X s,i ⊤ ⊤ ′ ′ ct1 = [es A]1 , ct2 = es AWi 1 , P (out) ⊤ i:xs,i =1 [es Ar̂ i:x(out) =1 Wi T ⊤ s,i e j = [s⊤ = = ([es Av]T )−1 . P ct1 = [s⊤ A]1 , ct ⊤ ⊤ j A]1 , e [es Av + s Ar̂ i:x(out) =1 Wi ]T ⊤ ⊤ s,i ctρs (j),j = u⊤ j + sj AWρs (j) 1 , cti,j = sj AWi 1 , P (out) where W0 = 0, xs,i is sender’s i-th public attribute for outer where r̂ = j∈Sr ωj rj . (out) layer, m̂s is the number of shares for sender’s policy, and ρs For all fsnd , ⃗xrcv such that fsnd (⃗xrcv ) = 1, we have: is a mapping from the indices of the shares to the indices of Q Q sender’s public attributes. e( j∈Ss ( i:x(out) =1 cti,j )µj , dk2 ) r,i Dec(DK⃗xrcv , DKfrcv , CT⃗xsnd ,fsnd ): The receiver recovers Q e µj e(ct , dk ) · e( 1 1 j∈Ss ctj , dk3 ) (M, toksnd ) using (DK , DK ) as follows. It compute f ⃗ x rcv rcv P P P ωj , µj such that v = j∈Sr ωj vj , s⊤ AU0 = j∈Ss µj u⊤ e([s⊤ AU0 + ŝ⊤ i:x(out) =1 AWi ]1 , [Br]2 ) j , r,i and calculates = P ⊤ Av + s⊤ AU Br] · e([ŝ⊤ A] , [ ωj [s Wi Br]2 ) (out) ′ Q 0 T 1 i:xr,i =1 e ct2 , j∈Sr dkj · K = ct0 · Q Q ωj [s⊤ AU0 Br]T e ct′1 , j∈Sr dki,j (out) i:xs,i =1 = = ([s⊤ Av]T )−1 . Q Q [s⊤ Av + s⊤ AU0 Br]T µj e( j∈Ss ( i:x(out) =1 cti,j ) , dk2 ) r,i , · Q Theorem 6.2. The ACME scheme achieves privacy, authene µj j , dk3 ) e(ct1 , dk1 )e( j∈Ss ct ticity, anonymity and unlinkability if the M DDHk assumption (out) where Sr = {j : ρr (j) = 0 ∨ xs,ρr (j) = 1}, Ss = {j : ρs (j) = holds and the underlying FAC is secure. (out) (out) The proof of Theorem 6.2 is shown in Appendix B. 0 ∨ xr,ρs (j) = 1} and xr,i is receiver’s i-th public attribute for outer layer. (out) (out) If fsnd (⃗xrcv ) = 0 ∨ frcv (⃗xsnd ) = 0, it outputs ⊥; D. Comparison of ME Schemes otherwise, it recovers (M, toksnd ) ← SE.SDec(H(K), ctM ). Mathmaking encryption (ME) protects data confidentiality Then, the receiver runs F AC.Verify(toksnd , M ) to verify (in) (out) toksnd for ⃗xsnd ∪ ⃗xsnd and M . It outputs the message M with bilateral control for both senders and receivers in communications. The existing instantiations of ME include an if the token is valid; otherwise, it outputs ⊥. identity-based scheme (IBME) [15] proposed in CRYPTO’19 The correctness of ACME scheme is analyzed below. (out) Denote Ss = {j : ρs (j) = 0 ∨ xr,ρs (j) = 1} and Sr = {j : and a security enhanced version [31] in Asiacrypt’22, but they do not support fine-grained access control. Table II compares (out) ρr (j) = 0 ∨ xs,ρr (j) = 1}. The correctness of ACME relies Q Q our ACME with IBME [15], [31]. Since IBME simply sets ωj ωj on the fact that j∈Sr dkj = j∈Sr [rj ]2 = [r̂]2 , ⃗xsnd = snd, fsnd = rcv and ⃗xrcv = rcv, frcv = snd, Y Y X ωj it requires pre-registration pairing between service providers dki,j = [v + Wi r̂]2 , and clients. On the contrary, ACME relies on bilateral policy (out) (out) j∈Sr i:x =1 i:xs,i =1 s,i matching for service discovery and thus it does not need preP registration pairing. Furthermore, ACME supports expressive where r̂ = j∈Sr ωj rj . Also we have, policy (i.e., Boolean formulae equivalent to NC1 circuit), ⊤ ⊤ e(ct1 , dk1 ) = [s Av + s AU0 Br]T , while IBME is constrained to equality policy. On the other Y Y µj ⊤ e µj j = ct [s⊤ hand, the expressive policy in ACME is public to enable fast j A]1 = [ŝ A]1 , j∈Ss j∈Ss service discovery, while the equality policy is hidden from the 2 Please refer to the details of linear secret sharing for NC1 in §5.1 of [26]. public in IBME.
10
Service Broadcast Phase Service Provider S’s Broadcast: bid, CTB ← ACME.Enc(creds , ⃗ xs , fs , M SGB ) $
where M SGB = {bid||Z||ServiceT ype ||ServiceP ar ||Kc }, z ← − Z∗p , Z ← hz ∈ G2 , Kc ← MAC.KeyGen(1λ ) Anonymous Mutual Authentication Phase Client (C)
Service Provider (S)
(credc , DK⃗xc , DKfc )
(creds , DK⃗xs , DKfs )
M SGB ← ACME.Dec(DK⃗xc , DKfc , CTB ) $
x1 , x2 ← − Z∗p , X1 ← g x1 ∈ G1 , X2 ← hx2 ∈ G2 σc ← MAC.MAC(Kc , Mc ) where Mc = (“C → S”, bid, sid, X1 , X2 , Z) Ks ← MAC.KeyGen(1λ )
bid,sid,σc ,CTc
−−−−−−−−−−−−−−−−→
M SGc ← ACME.Dec(DK⃗xs , DKfs , CTc )
CTc ← ACME.Enc(credc , ⃗ xc , fc , M SGc )
bc ← MAC.Verify(Kc , Mc , σc )
where M SGc = (Ks , Mc )
If bc = 0, abort; otherwise, $
y← − Z∗p , Y ← g y ∈ G1 bs ← MAC.Verify(Ks , Ms , σs ) If bs = 0, abort; otherwise,
σs ← MAC.MAC(Ks , Ms ) Ms ,σs
←−−−−−−−−−−−−−−−−
where Ms = (“S → C”, bid, sid, X1 , X2 , Y, Z) SSKc,s ← H(X1y , X2z )
SSKc,s ← H(Y x1 , Z x2 )
Fig. 3: PriSrv Protocol Complex Selective No Pre-reg. Hidden ME Anon. Policy Disclosure Pairing Policy √ √ √ IBME [15], [31] × × × √ √ √ √ √ ACME × Scheme
TABLE II: Comparison of ME Schemes
VII. P RI S RV: P RIVACY- ENHANCED FAST S ERVICE D ISCOVERY A. PriSrv Protocol and Security Fig. 3 shows PriSrv, which consists of a service broadcast phase and an anonymous mutual authentication phase. A unique broadcast identifier bid is assigned to each broadcast cycle; and a unique session identifier sid is assigned to each session. A lifetime should be set for each broadcast cycle (e.g., 30 seconds) by including a timestamp (which can be part of bid) and a client verifies the timestamp upon successful decryption to ensure the freshness. Let MAC = (Setup, KeyGen, MAC, Verify) be a message authentication code (MAC) scheme [35], [37], [38], and H : {0, 1}∗ → K be a hash function, where K is the secret session key space. We assume that the generation and dissemination of anonymous credential, attribute and policy decryption keys to both service provider (S) and client (C) are performed according to ACME. Service Broadcast Phase. To initiate a broadcast session with identifier bid, S defines a policy fs to be satisfied by C. S selects an ephemeral Diffie-Hellman (DH) $ exponent z ← − Z∗p and calculates Z ← hz . S also runs Kc ← MAC.KeyGen(1λ ) to generate an MAC key. S generates the broadcast message M SGB = {bid||Z|| ServiceT ype ||ServiceP ar ||Kc } including the broadcast iden-
11
tifier, service type and parameters as well as a MAC key for the client. Next, S encrypts M SGB to a broadcast ciphertext CTB = CT⃗xs ,fs ← ACME.Enc(creds , ⃗xs , fs , M SGB ). Then, the broadcast identifier bid and service ciphertext CTB are announced over the public network. Anonymous Mutual Authentication Phase. To establish a secure session between C and S, the anonymous mutual authentication is executed to establish a session key SSKc,s . (1) To discover the private service, C firstly checks whether (out) satisfies with the anonounced access policy fs of ⃗xc ? (out) S, i.e. fs (⃗xc ) = 1. C quickly filters out mismatched (out) services without decryption when fs (⃗xc ) = 0. Otherwise, C attempts to decrypt CTB using its attribute and policy decryption keys (DK⃗xc , DKfc ). If the decryption fails which (out) (out) means fs (⃗xc ) = 0 ∨ fc (⃗xs ) = 0, then C aborts. Otherwise, C responds to the broadcast message by executing ACME.Dec to recover M SGB . Next, C selects ephemeral $ DH exponents x1 , x2 ← − Z∗p and calculates X1 = g x1 , X2 = hx2 . C computes a MAC key Ks and an authentication tag σc of Mc = (“C → S”, bid, sid, X1 , X2 , Z) using Kc from M SGB , where “C → S” denotes the message direction. Then, C defines a policy fc to be satisfied by S, and selects a set of public attributes and a set of private attributes to be disclosed to S. C runs ACME.Enc to compute CTc = CT⃗xc ,fc and sends it to S. (2) S authenticates C’s service access request and computes a secret session key. S executes ACME.Dec to recover M SGc . S aborts the protocol if decryption fails. Next, S veri$ fies σc and selects DH exponent y ← − Z∗p to calculate Y ← g y . S sets Ms = (“S → C”, bid, sid, X1 , X2 , Y, Z) and generates a tag σs ← MAC.MAC(Ks , Ms ) using Ks from M SGc .
Then, S computes a secret session key SSKc,s ← H(X1y , X2z ) and sends (Ms , σs ) to C. (3) Receiving the message, C checks the validity of σs . If it is valid, C computes SSKc,s ← H(Y x1 , Z x2 ) using the secret values (x1 , x2 ). Therefore, C and S derive the same session key SSKc,s since X1y = Y x1 = g x1 y ∈ G1 and X2z = Z x2 = hx2 z ∈ G2 . The following theorem shows the security of PriSrv. Theorem 7.1. Suppose that the DDH assumption holds, ACME is secure, MAC is unforgeable, and H is a random oracle, then PriSrv is a secure service discovery protocol and satisfies bilateral anonymity. The proof of Theorem 7.1 is shown in Appendix C.
C. Interoperability of PriSrv with Existing Protocols There are two approaches to make PriSrv work on top of/with different layers of different wireless protocols. The first approach is to position PriSrv at the application layer providing application payload to lower layers. If the payload of PriSrv is oversized in lower layers, the lower layer protocols need to perform segmentation on the sender side and assembling on the receiver side without changing the protocol logics. The second approach is to substitute target protocols at lower layers with PriSrv. However, the second approach requests for specific adaptations of the concret protocols. In the following, we give two examples for each approach, including mDNS and BLE for the first approach, and EAP, AirDrop for the second approach. 1) Privacy Enhanced mDNS and BLE: PriSrv can be integrated in the Vanadium4 framework for developing privacy enhanced mDNS and BLE. Vanadium provides service discovery APIs to broadcast and scan services over widely deployed protocols, such as mDNS [51], [52] and BLE [3]. mDNS can work in conjunction with DNS Service Discovery (DNS-SD), a companion zero-configuration networking technique specified separately in RFC 67635 . DNS-SD extends the functionality of mDNS by adding additional attributes to the service discovery process. Specifically, the TXT (Text) resource record can be used to carry the attributes in the payload, where the maximum size for a single TXT record in DNS is 65535 bytes. The service broadcast of PriSrv is in the form (bid, CTB ), which takes 531996 bytes in communications on BN256 elliptic curve (100-bit security) [53]. Therefore, privacy enhanced mDNS may use 9 TXT records in DNS-SD to transmit the broadcast ciphertext of PriSrv. On the other hand, the payload of BLE broadcast is constrained to 31 bytes, which is too small for carrying a broadcast ciphertext in PriSrv. To enable privacy enhanced BLE using PriSrv, the BLE Attribute Protocol (ATT) and Attribute Protocol Data Unit (PDU) Segmentation techniques can be leveraged to extend the payload size. If the payload exceeds the standard packet size in BLE, the ATT protocol (which is used for exchanging data between devices) can segment the payload data into multiple Attribute Protocol Data Units (PDUs) and transmit them sequentially. These PDUs can be reassembled on the receiver side to recover the original payload for the ciphertext in PriSrv. 2) Privacy Enhanced EAP: Figure 4 presents the architecture of privacy enhanced EAP using PriSrv, which extends RFC 3748 on Extensible Authentication Protocol (EAP) [54] to support private service discovery. An access point (AP) is involved in the interactions between client and service provider, which acts as a pass-through agent for a backend authentication server [54]. The anonymous authentication exchange in privacy enhanced EAP proceeds as follows. (1) At the beginning, the service provider announces private service broadcast information via AP, which contains the broadcast
B. PriSrv Credential Management Now we discuss credential management, including credential issuance, credential interoperability, and credential revocation. Credential Issuance. PriSrv leverages FAC to implement a digital identity system for service providers and clients, offering the advantages of unforgeability, anonymous authentication, unlinkability, and selective attribute disclosure. W3C published Decentralized Identifiers (DIDs) [39] and Verifiable Credentials (VC) [40] specifications to regulate verifiable and decentralized digital identities. Decentralized Identity Foundation (DIF) [41] developed a set of standards to support a decentralized identity ecosystem [42]. Technology giants, such as IBM [43] and Microsoft [44], also provide flexible identity governance and administration services for credentials. CanDID proposed in [45] allows user’s attributes to be verified by issuers or imported from existing authority systems. PriSrv may follow any of these existing DID frameworks to issue credentials. Credential Interoperability. Credentials complying with standard specifications are interoperable across different platforms. DID [39] and VC [40] have regulated the process for inteoperable usage of credentials, which is also supported by DIF [41]. Backed by Microsoft, Google, Yahoo, IBM, VeriSign, PayPal, and Facebook, the OpenID Foundation3 promotes identity management, federation and interoperation, in compliance with the specifications of W3C. PriSrv may follow these specifications to ensure credential interoperability when deployed in various service discovery settings. Credential Revocation. Another consideration of PriSrv is to manage revocation of user’s credentials whenever it is necessary. Credential revocation has been intensively studied in the last decade: various types of dynamic accumulators (such as RSA-based and bilinear map based) with ZKP are adopted for credential revocation [46], [47], [48]. It can also be achieved by the combination of ElGamal encryption and Schnorr proofs [49], or n-times unlinkable proofs [50]. PriSrv may incorporate the above techniques to realize credential revocation.
4 Vanadium. https://vanadium.github.io/. 3 OpenID Foundation: https://openid.net/foundation.
5 https://tools.ietf.org/html/rfc6763.
12
discovery broadcast poses a scalability challenge, particularly on slower networks like BLE, resulting in high transmission overhead and reception delays. Moreover, on networks such as Wi-Fi, broadcasts must always be transmitted at the lowest feasible speed, further exacerbating airtime congestion. The issue of large message sizes also compounds another challenge in wireless networks: packet loss, especially when using opportunistic transmission protocols like mDNS, which relies on UDP. Although UDP packets can theoretically reach sizes of up to 64K, they are fragmented to align with the Maximum Transmission Unit (MTU) of the physical network. Any loss of a single fragment results in the entire packet being discarded. While Wi-Fi incorporates a rudimentary acknowledgment and retry mechanism, this only applies to unicast traffic and can only recover from brief RF disruptions. Consequently, clients must wait for the broadcast ciphertext in the subsequent round to receive full packets, causing additional delays in reception. How to design efficient privacypreserving discovery protocols remain an open problem for future research. PriSrv protects its own payloads for achieving unlinkability at its positioned layer. As for achieving unlinkability at lower layers, the lower layer headers must be protected using specific anti-tracking mechanisms designed at lower layers. For example, PriSrv can work with MAC randomization mechanism at data link layer. Smartphone manufacturers (e.g., Apple iOS) incorporate MAC randomization for WiFi and AWDL connections to provide unlinkability at the link layer, but devices can still be tracked at the layer where PriSrv resides. PriSrv complements the MAC randomization mechanism to realize unlinkability in different layers. Nevertheless, the current MAC address randomization approach (e.g., as implemented in Android and iOS) only performs randomization once when connecting to a new network and not with each subsequent connection. To achieve more robust unlinkability, a more effective MAC address randomization strategy should be devised to ensure unlinkability for each individual connection. Achieving unlinkability across multiple layers remains a persistent challenge.
Fig. 4: Architecture of Privacy Enahnced EAP
identifier bid and the broadcast ciphertext CTB = CT⃗xs ,fs = ACME.Enc(· · · , M SGB ). This step corresponds to the statement “the authenticator sends a request to authenticate the peer” in EAP Standard. (2) If the client can decrypt M SGB from CTB , he/she sends a response packet (bid, sid, σc , CTc ) as reply to the service provider, where CTc = CT⃗xc ,fc = ACME.Enc(· · · , M SGC ) and sid is a session identifier. (3) Receiving the response, the service provider proceeds to recover M SGc from CTc . If it succeeds, the service provider sends (Ms , σs ) to client, where Ms contains the DH shares for computing a session key and σs is the corresponding MAC value. After the client verifies σs , it calculates a secret session key SSKc,s , and responds with a message “succeed”. (4) Finally, the service provider also computes SSKc,s so that a secure session is established between service provider and client. All subsequent protocol messages are encapsulated in EAPOL frames and re-encapsulated as RADIUS packets on the back-haul. Following [9], the privacy enhanced EAP can be adopted to enhance the privacy of Wi-Fi connections. 3) Privacy Enhanced Apple AirDrop: AirDrop applies BLE to advertise the hashed identity of a service provider to look for potential clients in their proximity. If a match is confirmed, a TLS handshake is performed to exchange their certificates in cleartext. Both hashed identities and certificates are disclosed to the public, which is subject to identification and tracking attacks. Following the PrivateDrop mechanism in [16], we can improve the privacy of AirDrop by avoiding transmitting private information (such as identifier) of service provider during the advertising phase using BLE, and then encrypt the certificates of both parties using ACME at the beginning of TLS handshake. Apple may take the role of credential issuer in this case to generate necessary secret keys and credentials in addition to their existing iCloud certificates.
VIII. I MPLEMENTATION AND C OMPARISON We benchmark the performance of PriSrv on various hardware platforms, including desktop, laptop, smartphone, and Raspberry Pi as shown in Table III. Three asymmetric elliptic curves are selected from the MIRACL library [55] for evaluation, including MNT159 (80-bit security), MNT201 (90-bit security), and BN256 (100-bit security) [53]. We use AES-CTR with 100-bit keys to instantiate the SEnc/SDec algorithms in PriSrv, using SHA-256 as the hash function, and use MACGGM [35] as suf-cma secure MAC. The source code of our experiments is written in C/C++ and publicly available on GitHub6 . For each test case, we report the average over 20 executions.
D. Limitations of PriSrv One limitation of PriSrv lies in its large message size when compared to existing protocols. This large size of the outer
6 Source Code: https://github.com/prisrv.
13
No. Type Hardware Platforms B. Evaluation of ACME and PriSrv 1 Desktop Intel® Core™ i9-7920X CPU @ 2.9GHz×12, 16GB Table VI presents the computation cost (comp.) and com2 Laptop Intel® Core™ i5-10210U CPU @ 1.6GHz×4, 8GB munication cost (comm.) of ACME for different algorithms on 3 Phone ARM Cortex @2.84GHz+3×2.4GHz, 4GB desktop following the example in §IV, where the parameters 4 Raspberry Pi ARM Cortex @1.5GHz×4, 2GB
are n = 10, k = 2, m̂ = 9 and |S| = 9. The system setup time, performed on various curves, ranges from 20.526 ms to 33.344 ms. The sizes of master public key (|mpk|) and master secret key (|msk|) for BN256 are 4.128 KB and 1.6 KB, respectively. The credential key generation (CredKeyGen) and user key generation (UserKeyGen) cost no more than 118.622 ms and 9.102 ms, respectively. The credential issue (Issue) algorithm is efficient (39.383 ms) and the size of generated anonymous credential (|cred|) is merely 0.544 KB on BN256 curve, which is consistant with the theoretical analysis of FAC in §VIII-A. The size of attribute decryption key (DK⃗x ) and the size of policy decryption key (DKf ) are no more than 2.72 KB and 44.064 KB, respectively. The computation costs for encryption and decryption are less than 188 ms and 232 ms, respectively, on BN256 curve. While the computation costs on MNT159 and MNT201 are significantly lower than those on BN256.
TABLE III: Hardware Platforms for Experiments
A. Evaluation of FAC In Table IV, we compare FAC with typical anonymous credential schemes. FAC constructs a constant-size anonymous credential. With FAC, a verifier only needs to conduct k operations to check the proof of k attributes, which is an upto-date optimal solution. The O(1) communication complexity in [29] for its Show algorithm (i.e., |Show|) is composed of about 100 group elements. Since the scheme in [29] is the only one to achieve UC security in Table IV, these overheads can be seen as a tradoff between efficiency and security. Compared with [30], our credential only consists of 2 elements in G2 , which is approximately 2× more efficient than that of [30] (i.e., 3|G1 | + |G2 | + 2|Zp |). To show a credential in FAC, a user transmits 2 elements in G1 , 2 in G2 , 1 in GT and three scalar elements, which is smaller than 8 elements in G1 , 1 in G2 and two scalar elements for [30].
Curve and Security Level MNT159 MNT201 BN256 (80-bit Security) (90-bit Security) (100-bit Security) Setup 20.526 26.882 33.344 CredKeyGen 98.261 105.883 118.622 UserKeyGen 6.153 7.582 9.102 Issue 29.298 33.783 39.383 DKGen 21.63 18.64 15.75 PolGen 359.807 327.796 237.675 Enc 146.931 167.337 187.822 Dec 123.772 188.346 231.214 Comp. (ms)
Ref. Issue |cred| |Show| Show Verify [56] O(1) 2|QRN | + |ℓN | O(k) O(k) O(k) [57] O(1) |G1 | + 2|Zq | O(n) O(n) O(n) [28] O(n) (2n + 4)(|G1 | + |Zq |) O(n) O(n) O(n) [29] O(1) 6|G1 | + 2|G2 | + |Zp | O(1) O(n − k) O(k) [30] O(1) 3|G1 | + |G2 | + 2|Zp | O(1) O(n − k) O(k) FAC O(1) 2|G2 | O(1) O(n − k) O(k)
Comm. (KB) MNT159 MNT201 BN256 |mpk|/|msk| 1.044 / 1.2 1.332 / 1.36 4.128 / 1.6 |pk|/|sk| 0.91 / 0.18 1.158 / 0.204 3.408 / 0.24 |upk|/|usk| 0.116 / 0.03 0.148 / 0.034 0.4 / 0.04 |DK⃗x |/|DKf | 0.86 / 13.932 1.1 / 17.82 2.72 / 44.064 |cred|/|CT| 0.172 / 164.34 0.220 / 212.964 0.544 / 537.984
TABLE IV: Comparison of Anonymous Credential Schemes |Show| indicates the communication cost for showing k attributes. Show and Verify represent the computational costs. QRN represents the group of quadratic residues modulo a composite N , and ℓN is an RSA moduli defined in [56].
Ref. Idemix [56] UProve [57] [29] [30] FAC
|Cred| 0.671 0.768 1.352 0.736 0.544
Issue 76.437 37.422 389.513 371.126 39.387
Show 283.245 12.264 657.024 87.625 28.302
TABLE VI: Performance of ACME
Verify 210.783 33.231 253.453 284.719 65.819
Using the same example and parameter settings, Table VII provides a comprehensive evaluation of PriSrv on multiple hardware platforms with various elliptic curves and security levels. The communication overheads of the broadcast and mutual authentication phases are similar, as both of them are primarily determined by the size of the ACME ciphertext. The communication costs remain the same for different platforms, and the computation costs gradually increase from desktop to Raspberry Pi. The desktop, laptop and smartphone take less than 0.483 s for private service broadcast, and less than 0.973 s for anonymous mutual authentication. Raspberry Pi is relatively resource-limited, which takes 1.189 s and 2.712 s for private broadcast and authentication, respectively. The experimental results show that the broadcast and anonymous mutual authentication delays on the first three devices stay well
TABLE V: Performance of AC (ms/KB) (BN256) Table V compares the performance of FAC with Idemix, UProve and the schemes in [29], [30] on desktop. The parameters for FAC are n = 10 and |I| = 4. UProve incurs a low cost without providing multi-show unlinkability, while the other schemes support this privacy property. FAC has the smallest credential size (0.544 KB) in this comparison and its overheads for Issue, Show, Verify are the lowest or the second lowest among those supporting multi-show unlinkability.
14
Private Service Broadcast MNT159 MNT201 BN256 Device (80-bit Security) (90-bit Security) (100-bit Security) Comp. Comm. Comp. Comm. Comp. Comm. 1 158.931 164.34 180.337 212.96 202.822 537.98 2 216.493 164.34 261.059 212.96 287.287 537.98 3 385.553 164.34 443.686 212.96 482.725 537.98 4 638.259 164.34 880.868 212.96 1188.392 537.98 Anonymous Mutual Authentication MNT159 MNT201 BN256 Device (80-bit Security) (90-bit Security) (100-bit Security) Comp. Comm. Comp. Comm. Comp. Comm. 1 429.282 164.45 517.512 213.09 673.039 538.83 2 576.161 164.45 686.054 213.09 854.177 538.83 3 727.572 164.45 892.712 213.09 972.163 538.83 4 1224.365 164.45 1832.187 213.09 2711.013 538.83
Fig. 6: Performance of PriSrv with Complex Policies
of access policy m̂ among {1, 3, 7, 11} for practicality test. For n = 15, m̂ = 11, we have TB = 763.892 ms, TS = 302.973 ms and TC = 938.395 ms, |Client|=573.852 KB and |Server| = 0.82 KB. Fig. 6 sets n = 25, 50 and varies m̂ among {3, 7, 11, 13, 17, 21, 27} for testing complex policies involving large number of attributes. The computation time increases with the number of attributes and complexity of access policies. For n = 50 and m̂ = 27, the computation costs are TB = 5.711s, TS = 0.549s, TC = 6.262s. The communication cost in the broadcast phase grows from 0.549 MB to 0.881 MB. The transmission overhead of the server in the authentication phase remains relatively low (no more than 0.82 KB), while that of the client is mainly influenced by the ACME ciphertext, ranging from 0.549 MB to 0.881 MB. The comprehensive evaluations demonstrate the efficiency of PriSrv in wireless communications.
TABLE VII: Performance of PriSrv (ms/KB)
Fig. 5: Computation/Communication cost of PriSrv
IX. C ONCLUSION below 1 s, which humans perceive the delays as an “immediate response” [16], [17], while the delays on Raspberry Pi are longer but not too significant. We further implement PriSrv in wireless environment by adapting an open-source project of Wi-Fi Alliance [1], which implements IEEE 802.1X and enables the deployment of clients (running wpa supplicant program of the project) and service providers (running hostapd program). Experiments of PriSrv in wireless communication use two laptops running Ubuntu 20.04. We deploy one laptop as the service provider and the other as the client. Fig. 5-6 present the broadcast time (TB ), server’s computation time (TS ) and client’s computation time (TC ) during the anonymous mutual authentication phase, where the total mutual authentication time is TM A = TS +TC . The left y-axis shows the computation time, and right y-axis indicates the communication overhead in the broadcast phase (|Broadcast|) and the communication overhead of service provider/client in the authentication phase (|Server|/|Client|). The performance of PriSrv varies with the attribute number n (top x-axis) and the wire number m̂ of NC1 (i.e. number of shares for policy, bottom x-axis), where the matrix size is fixed to be k = 2. In Fig. 5, we set n = 8, 11, 15 and vary the complexity
This paper presented PriSrv, a privacy-enhanced service discovery protocol with high usability, for wireless communications. PriSrv enforces bilateral flexible policy control for anonymous mutual authentication, making it an ideal solution for enhancing privacy protection in popular wireless communication protocols such as EAP, mDNS, BLE, and AirDrop. PriSrv is built upon a novel primitive called anonymous credential-based matchmaking encryption (ACME), which extends the concept of ME proposed in CRYPTO’19 by offering selective attribute disclosure and eliminating the need for heavy cryptographic tools. ACME relies on a newly designed Fast Anonymous Credential (FAC) scheme to generate and verify authentication tokens that are unlinkable across multiple protocol sessions. Comprehensive experimental evaluations and comparisons demonstrated that ACME outperforms existing ME instantiations in terms of functionality and efficiency, which makes it a contribution of independent interests. Formal security models are provided to prove that PriSrv, ACME and FAC have desired security and privacy properties. Benchmarks on multiple hardware platforms demonstrated that PriSrv is suitable for interoperating with a wide range of service discovery protocols with enhanced privacy protection and high usability.
15
ACKNOWLEDGMENT
[17] S. K. Stuart, G. G. George, J. D. Jock. The Information Visualizer, an Information Workspace. In CHI, 1991. [18] S. Cheshire, M. Krochmal. RFC 6763: DNS-based service discovery. 2013. [19] S. Cheshire, M. Krochmal. RFC 6762: Multicast DNS. 2013. [20] Y. Y. Goland, T. Cai, P. Leach, Y. Gu. Simple service discovery protocol/1.0 operating without on arbiter. IETF INTERNET-DRAFT draft-caissdp-v1-03. 1999. [21] M. Boucadair, R. Penno, D. Wing. Universal Plug and Play (UPnP) Internet Gateway Device - Port Control Protocol Interworking Function (IGD-PCP IWF). RFC 6970: Multicast DNS. 2013. [22] X. Wang, Y. Sun, S. Nanda, X. Wang. Looking from the Mirror: Evaluating IoT Device Security through Mobile Companion Apps. In USENIX Security, 2019. [23] L. Yu, B. Luo, J. Ma, Z. Zhou, Q. Liu. You Are What You Broadcast: Identification of Mobile and IoT Devices from (Public) WiFi. In USENIX Security, 2020. [24] J. Wu, Y. Nan, V. Kumar, D. Tian, A. Bianchi, M. Payer, D. Xu. BLESA: Spoofing Attacks against Reconnections in Bluetooth Low Energy. In WOOT@USENIX Security, 2020. [25] R. H. Venkatnarayan, M. Shahzad, S. Yun, C. Vlachou, K. H. Kim. Leveraging polarization of WiFi signals to simultaneously track multiple people. In Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 2020, 4(2): 1-24. [26] L. Kowalczyk, H. Wee. Compact adaptively secure ABE for NC1 from k-Lin. Journal of Cryptology, 2020, 33(3): 954-1002. [27] S. Katsumata, R. Nishimaki, S. Yamada, T. Yamakawa. Compact NIZKs from standard assumptions on bilinear maps. In EUROCRYPT, 2020. [28] S. Ringers, E. Verheul, J. H. Hoepman. An efficient self-blindable attribute-based credential scheme. In FC, 2017. [29] J. Camenisch, M. Dubovitskaya, K. Haralambiev, M. Kohlweiss. Composable and modular anonymous credentials: definitions and practical constructions. In ASIACRYPT, 2015. [30] G. Fuchsbauer, C. Hanser, D. Slamanig. Structure-preserving signatures on equivalence classes and constant-size anonymous credentials. Journal of Cryptology, 2019. [31] J. Chen, Y. Li, J. Wen, J. Weng. Identity-based matchmaking encryption from standard assumptions. In ASIACRYPT, 2022. [32] R. Canetti, H. Krawczyk. Analysis of key-exchange protocols and their use for building secure channels. In EUROCRYPT, 2001. [33] R. Canetti, H. Krawczyk. Security analysis of IKE’s signature-based key-exchange protocol. In CRYPTO, 2002. [34] J. Camenisch, M. Drijvers, M. Dubovitskaya. Practical UC-secure delegatable credentials with attributes and their application to blockchain. In CCS, 2017. [35] M. Chase, S. Meiklejohn, G. Zaverucha. Algebraic MACs and keyedverification anonymous credentials. In CCS, 2014. [36] O. Sanders. Efficient redactable signature and application to anonymous credentials. In PKC, 2020. [37] M. Chase, T. Perrin, G. Zaverucha. The signal private group system and anonymous credentials supporting efficient verifiable encryption. In CCS, 2020. [38] Z. Zhang, K. Yang, X. Hu, Y. Wang. Practical anonymous password authentication and TLS with anonymous client authentication. In CCS, 2016. [39] D. Reed, M. Sporny, D. Longley, C. Allen, R. Grant, M. Sabadello, J. Holt. Decentralized identifiers (DIDs) v1.0: Core architecture, data model, and representations. W3C Working Draft, 2020. [40] M. Sporny, D. Longley, D. Chadwick. Verifiable credentials data model v1.1. Available: https://www.w3.org/TR/vc-data-model, 2022. [41] DIF. Decentralized Identity Foundation. [Online]. Available: https:// identity.foundation/. [42] L. Lesavre, P. Varin, P. Mell, M. Davidson, J. Shook. A taxonomic approach to understanding emerging blockchain identity management systems. NIST Cybersecurity White Paper, 2019. [43] IBM. Blockchain for Digital Identity and Credentials. [Online]. Available: https://www.ibm.com. [44] Microsoft. Decentralized Identity, Blockchain, and Privacy. [Online]. Available: https://www.microsoft.com. [45] D. Maram, H. Malvai, F. Zhang, N. Jean-Louis, A. Frolov, T. Kell, T. Lobban, C. Moy, A. Juels, A. Miller. Candid: Can-do decentralized identity with legacy compatibility, sybil-resistance, and accountability. In S&P, 2021.
The authors would like to thank the shepherd and anonymous reviewers for their valuable comments and insightful suggestions. Yang Yang is supported by Lee Kong Chian Professor Fund, National Natural Science Foundation of China under Grant No. 62372110, and Fujian Provincial Natural Science of Foundation under Grant 2023J02008. Robert Deng is supported by AXA Research Fund. Guomin Yang is supported by Lee Kong Chian Fellowship awarded by Singapore Management University. HweeHwa Pang is supported by Lee Kong Chian Chair Professor Fund. Jian Weng is supported by National Key Research and Development Plan of China under Grant No. 2020YFB1005600, National Natural Science Foundation of China under Grant Nos. 61825203, 62332007 and U22B2028, Science and Technology Major Project of Tibetan Autonomous Region of China under Grant No. XZ202201ZD0006G, 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. R EFERENCES [1] WiFi [Online]. Available: https://w1.fi. [2] How to use AirDrop on your iPhone or iPad. [Online]. Available: https://support.apple.com/en-us/HT204144. [3] Bluetooth specification version 4.2. [Online]. Available: Bluetooth.com. [4] B. Könings, C. Bachmaier, F. Schaub, M. Weber. Device names in the wild: Investigating privacy risks of zero configuration networking. In MDM, 2013. [5] D. J. Wu, A. Taly, A. Shankar, D. Boneh. Privacy, discovery, and authentication for the internet of things. In ESORICS, 2016. [6] W. Zhou, Y. Jia, Y. Yao, L. Zhu, L. Guan, Y. Mao, P. Liu, Y. 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. [7] M. Stute, S. Narain, A. Mariotto, A. Heinrich, D. Kreitschmann, G. Noubir, M. 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. [8] M. Stute, A. Heinrich, J. Lorenz, M. 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. [9] A. Cassola, E. O. Blass, G. Noubir. Authenticating privately over public Wi-Fi hotspots. In CCS, 2015. [10] K. Fawaz, K. H. Kim, K. G. Shin. Protecting privacy of BLE device users. In USENIX Security, 2016. [11] X. Na, X. Guo, Y. He, R. Xi. Wi-attack: cross-technology impersonation attack against iBeacon services. In SECON, 2021. [12] X. Bai, L. Xing, N. Zhang, X. Wang, X. Liao, T. Li, S. M. Hu. Staying secure and unprepared: understanding and mitigating the security risks of apple zeroconf. In S&P, 2016. [13] X. Bai, L. Xing, N. Zhang, X. Wang, X. Liao, T. Li, S. M. Hu. Apple ZeroConf holes: how hackers can steal iPhone photos. IEEE Security & Privacy Magazine, 2017, 15(2): 42-49. [14] J. Xu, Y. Liu, H. Shi. A survey on privacy-preserving wireless network protocols: techniques and challenges. IEEE Communications Surveys & Tutorials, 2020: 22(1), 572-598. [15] G. Ateniese, D. Francati, D. Nuñez, D. Venturi. Match me if you can: matchmaking encryption and its applications. Journal of Cryptology, 2021, 34: 1-50. [16] A. Heinrich, M. Hollick, T. Schneider, M. Stute, C. Weinert. PrivateDrop: practical privacy-preserving authentication for Apple airDrop. In USENIX Security, 2021.
16
[46] D. Boneh, B. Bünz, B. Fisch. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In CRYPTO, 2019. [47] J. Camenisch, M. Kohlweiss, C. Soriente. An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In PKC, 2009. [48] F. Baldimtsi, J. Camenisch, M. Dubovitskaya, A. Lysyanskaya, L. Reyzin, K. Samelin, S. Yakoubov. Accumulators with applications to anonymity-preserving revocation. In EuroS&P, 2017. [49] D. Bogatov, A. De Caro, K. Elkhiyaoui, B. Tackmann. Anonymous transactions with revocation and auditing in hyperledger fabric. In CANS, 2021. [50] J. Camenisch, M. Drijvers, J. Hajny. Scalable revocation scheme for anonymous credentials based on n-times unlinkable proofs. In WPES, 2016. [51] S. Cheshire, M. Krochmal. DNS-based service discovery. Technical Report. RFC 6763, 2013. [52] S. Cheshire, M. Krochmal. Multicast DNS. Technical Report. RFC 6762, 2013. [53] Pairing-Friendly Curves. [Online]. Available: https://www.ietf.org/ archive/id/draft-irtf-cfrg-pairing-friendly-curves-02.html. [54] B. Aboba, L. Blunk, J. Vollbrecht, J. Carlson, H. Levkowetz. Extensible authentication protocol (EAP). 2004. [55] MIRACL: Multiprecision integer and rational arithmetic c/c++ library. [Online]. Available: https://github.com/miracl/MIRACL. [56] J. Camenisch, A. Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT, 2001. [57] C. Paquin, G. Zaverucha. U-prove cryptographic specification v1.1. Technical Report, Microsoft Corporation, 2011. [58] M. Bellare, R. Canetti, H. Krawczyk. A modular approach to the design and analysis of authentication and key exchange protocols. In STOC, 1998. [59] E. Fujisaki, T. Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In CRYPTO, 1999. [60] H. Krawczyk, H. Wee. The OPTLS protocol and TLS 1.3. In EuroS&P, 2016.
17
A PPENDIX A. FAC: Security Model and Proof (1) Security Model Following the definitions in [35], [36], we define correctness, unforgeability, anonymity and unlinkability for anonymous credential scheme. The lists in the security models are given in Table VIII. Definition A.1 Let D be the universe of user identity, and Ω be the universe of attribute sets. Then an anonymous credential scheme AC is correct for D, Ω if all uid ∈ D, all ⃗x ⊆ Ω, for all security parameter λ, $ $ pp ← − Setup(1λ , 1n ); (pk, sk) ← − CredKeyGen(pp); $ (upk, usk) ← − UserKeyGen(pp); $ Pr cred ← − ⟨Issue.I(sk, upk) ⇄ Issue.U(uid, ⃗ x , usk)⟩ ; $ − Show(uid, {xi }i∈I , cred, usk, m) : tok ← Verify(tok, m) = 0 ≤ ν(λ), where ν is a negligible function. Definition A.2 An AC scheme satisfies unforgeability if for any PPT adversary A, there exists a negligible function ν such def unforge that AdvAC (λ) = pp ← Setup(1λ , 1n ), (pk,sk) ← CredKeyGen(pp) ∗ ∗ (uid∗ , ⃗x∗ , m∗ , cred , tok ) ← AO(sk,·) (pp, pk) ∗ ∗ Pr b = 1 b ← Verify(tok , m ) ∗ ∗ return b if (m∗ , ⃗x∗ , cred , tok ) ∈ / Lshow ∧ cred∗ ∈ / Lissue ∧ (uid∗ , ⃗x∗ ) ∈ / Lcorrupt else abort
Definition A.4 An AC scheme AC satisfies unlinkability if for any PPT adversary A, there exists a negligible function ν def such that Advunlink AC (λ) = pp ← Setup(1λ , 1n ), (pk,sk) ← CredKeyGen(pp) ∗ ∗ ∗ ∗ ∗ ∗ O(sk,·) (uid0 , uid1 , I , ⃗x0 , ⃗x1 , m ) ← A (pp, pk) (d) ∗ ∗ where I ⊆ [1, n], ⃗xd = {xi }i∈[1,n] , d ∈ {0, 1} (0) (1) abort if ∃j ∈ I ∗ : xj ̸= xj $ ∗ ∗ or ∃d ← − {0, 1} : (uidd , ⃗xd , credd ) ∈ / Lhonest , ′ Pr b = b $ b← − {0, 1} (b) tok∗b ← Show(uid∗b , cred∗b , usk∗b , {xi }i∈I ∗ , m∗ ) b′ ← AO(sk,·) (pp, tok∗b ) ∗ ′ ′ return b if ∀d ∈ {0, 1}, credd′ ∈ / Lissue ∧ ∗ ∗ ∗ ∗ ∗ (m , ⃗xd′ , tokd′ ) ∈ / Lshow ∧ (uidd′ , ⃗xd′ ) ∈ / Lcorrupt else abort ≤ ν(λ), where the oracle set O = {UserKeyGen, Issue, Show, Corrupt} is implemented by UserKeyGen(pp, ·), Issue(sk, st, ·), Show(pk, ·) and Corrupt(·). It is easy to see that the security definition of unlinkability implicitly implies that of anonymity. List Lregisterd Lissue Lshow Lhonest Lcorrupt Lauth Lexec
Description registered users credentials that have been issued credentials that have been shown registered users that are honest registered users that are corrupted authorized users in service discovery session contains all messages that user or adversary exchanged during executions of protocol
≤ ν(λ), where the oracle set O = {UserKeyGen, Issue, TABLE VIII: Lists in Security Experiments Show, Corrupt} is implemented by UserKeyGen(pp, ·), Issue(sk, st, ·), Show(pk, ·) and Corrupt(·). (2) Correctness Proof Definition A.3 An AC scheme AC satisfies anonymity if for Theorem A.1 The FAC scheme satisfies correctness. any PPT adversary A, there exists a negligible function ν such Proof. For the correctness proof, we need to demonstrate the def that Advanon AC (λ) = following properties: 1) the instantiation of SPK π1 is correct in the UserKeyGen algorithm; 2) the credential created by the λ n pp ← Setup(1 , 1 ), issuer is verified true by the user in the Issue algorithm; 3) (pk,sk) ← CredKeyGen(pp) the instantiation of SPK π is correct in Show and Verify 2 ∗ ∗ ∗ O(sk,·) ∗ algorithms. (pp, pk) (uid0 , uid1 , ⃗x , m ) ← A $ For the first property, The correctness of SPK π is verified abort if ∃d ← − {0, 1} : 1 f as γ = husk c usk usk c usk g− $ = h (h ) = h upk , where usk = usk ∗ ∗ ′ (uidd , ⃗x , credd ) ∈ / Lhonest ; b ← − {0, 1} c · usk mod p and upk = husk . Pr b = b tok∗ ← Show(uid∗b , credb , uskb , ⃗x∗ , m∗ ) For the second property, a received credential is cred = ∗ ′ O(sk,·) (σ , σ ), σ = hr , σ = upkr·y0 · hr(τ +Pni=1 yi xi +yn+1 ·uid) , b ←A (pp, tok ) 1 2 2 1 Qn ? xi uid return b′ if cred∗ ∈ / Lissue ∧ and the user verifies it as e(W · Y0usk · Yn+1 i=1 Yi , σ1 ) = ∗ ∗ ∗ ∗ ∗ (m , ⃗x , tok ) ∈ / Lshow ∧ (uid0/1 , ⃗x ) ∈ / Lcorrupt e(g, σ2 ). This equation holds since Yn else abort uid e(W · Y0usk · Yn+1 Y xi , σ1 ) i=1 i Yn ≤ ν(λ), where the oracle set O = {UserKeyGen, Issue, = e(g τ · (g y0 )usk · (g yn+1 )uid (g yi )xi , hr ) i=1 Show, Corrupt} is implemented by UserKeyGen(pp, ·), Pn = e(g, (husk )r·y0 hr(τ + i=1 yi xi +yn+1 ·uid) ) Issue(sk, st, ·), Show(pk, ·) and Corrupt(·).
18
=
e(g, upkr·y0 · hr(τ +
Pn
i=1 yi xi +yn+1 ·uid)
) = e(g, σ2 ).
the number of honest user. We define two types of adversaries (A1 , A2 ) that possess different resources for the attack: type-1 adversary A1 : ∃uidβ ∗ ∈ Lhonest , s.t., uskβ ∗ = usk∗ ; type2 adversary A2 : ∀uidi ∈ Lhonest , s.t., uski ̸= usk∗ . In the following, we prove the unforgeability of FAC with two propositions for the two types of adversaries. Proposition A.1 Suppose type-1 adversary A1 is able to break the unforgeability of FAC with advantage ϵ1 . Then, we can utilize A1 to solve the DL problem with advantage ϵ1 /q, where q is the number of honest users.
For the third property, assume that cred is a valid anonymous credential on uid, ⃗x and usk, and we have Yn uid e(W · Y0usk · Yn+1 Yixi , σ1 ) = e(g, σ2 ), i=1
uid ⇒ e(Y0usk · Yn+1 , σ1 ) = e(g, σ2 )e(W ·
Yn i=1
Yixi , σ1 )−1 .
The correctness of SPK π2 can be derived from uid e(Y0usk Yn+1 , σ̄1 )−1 · Λ
Proof. The proof reduces the unforgeability of FAC to the security of DL assumption. Let A1 be a PPT adversary uid = e(Y0usk Yn+1 , σ1 )c·t2 that wins the security game with probability ϵ1 . Consider Y xi −1 c·t2 a simulator S which runs A1 as a subroutine and interacts = [e(g, σ2 )e(W · Y , σ1 ) ] i∈[1,n] i with a challenger C for the DL-assumption. According to Y = [e(g, σ̄2 )e(g, σ̄1 )−t1 e(W · Y xi , σ̄1 )−1 ]c the definition of type-1 adversary A1 , there exists an index i∈[1,n] i Y Y β ∗ ∈ [1, q] for A1 to impersonate the β ∗ -th honest user in Yixi Yixi , σ̄1 )−1 ]c Lhonest . Then, the challenger C is requested to make a guess = [e(g, σ̄2 )e(W · g t1 · i∈[1,n]\I i∈I Y on β ∗ from the q honest users. If A1 is able to break the Yixi , σ̄1 )−1 ]c = [e(g, σ̄2 ) · Γ]c . = [e(g, σ̄2 )e(W · T1 · unforgeability of FAC, C could makes use of the advantage i∈I of A1 to solve the DL problem. Let g, h be the generators On the other hand, of groups G1 and G2 , respectively. Let (h, ha ) be challenge Y e(T1 , X ) i tuple of DL assumption on group G2 . ′ Yi∈I Y Y Setup. S creates the public key pk = (W, {Xi , Yi }i∈[0,n+1] , xj t1 = e(g , Xi )e( Yj , Xi ) i∈I ′ i∈I ′ {Zi,j }0≤i̸=j≤n+1 ) following the Setup and CredKeyGen j∈[1,n]\I algorithms in FAC and forwards it to A1 . Y Y x t1 = e( Yi , h) e( Zi,jj , h) Query. The adversary A1 adaptively makes the following i∈I ′ i∈I ′ ,j∈[1,n]\I queries. Y Y x − According to the definition of type-1 adversary A1 , there Zi,jj , h) = e(T2 , h). = e(( Yi )t1 exists an index β ∗ ∈ [1, q] for A1 to impersonate the β ∗ ′ ′ i∈I i∈I ,j∈[1,n]\I th honest user in Lhonest . For the UserKeyGen queries on Therefore, a valid credential cred and its SPK π2 will be (uidβ ∗ , ⃗xβ ∗ ), S implicitly sets uskβ ∗ = a, and sends upk ∗ = β verified true. ha to A1 . For the UserKeyGen queries on (uidj , ⃗xj ) with $ j ̸= i, S generates user’s secret key uskj ← − Z∗p and public key (3) Security Proof The security of FAC in Theorem 5.1 is proved in aspects upkj = huskj , which are returned to A1 . S adds (uid, ⃗x, upk) to a list Lhonest . If (uid, ⃗x) already exists in Lhonest , S just of unforgeability, anonymity and unlinkability. replies with the same answer. 3.1) Unforgeability Proof of FAC − For the Issue queries on (uidj , ⃗xj ) with restriction that Lemma A.1 The FAC scheme is unforgeable if the underlyj ̸= β ∗ , S runs UserKeyGen to generate (upkj , uskj ) if ing unforgeable redactable signature (URS) [36] is unforgeable (uidj , ⃗xj ) has not been queried beforehand. Otherwise, S exand the discrete logarithm (DL) assumption holds. tracts user’s keys (upkj , uskj ) from Lhonest . Then, S queries signature σj = (e σ1 , σ e2 ), Proof. The proof reduces the unforgeability of FAC to the C on (uidj , ⃗xj ) and obtains a URS P τ+ n $ i=1 yi ·xi existential unforgeability of the unlinkable redactable signa- where σ e1 ← − G2 and σ e2 ← σ e1 . S implicitly sets ture (URS) scheme (in §4 of [36]) and discrete logarithm σ1 = σ e1 = hr , computes (DL) assumption. Let A be a PPT adversary that wins the σ2 = (e σ1 )uskj ·y0 (e σ1 )yn+1 ·uid σ e2 unforgeability game with probability ϵ. P usk r·y0 r(τ + n yi xi +yn+1 ·uid) i=1 During the challenge phase, A returns a challenge user iden= (hj ) h P r·y0 tifier uid∗ , attribute set ⃗x∗ and proves possession of a valid aur(τ + n i=1 yi xi +yn+1 ·uid) , = upk · h ∗ ∗ thentication token tok for credential cred on (uid∗ , ⃗x∗ ). Obviously, it should be constrained that (m∗ , ⃗x∗ , cred∗ , tok∗ ) ∈ / and returns credj ← (σ1 , σ2 ) to A1 . S inserts (uidj , ⃗xj , upkj , Lshow , cred∗ ∈ / Lissue , (uid∗ , ⃗x∗ ) ∈ / Lcorrupt . Let usk∗ be the credj ) into a list Lissue . secret key whose knowledge should be proved by A when it − To answer the Show query on (uidj , {xi }i∈I , credj , mj ) generates a challenge credential cred∗ on (uid∗ , ⃗x∗ ). Denote with restriction that j ̸= β ∗ , S runs UserKeyGen to generate Lhonest as a set of registered users that are honest and Lcorrupt (upkj , uskj ) if uidj has not been queried beforehand. Otheras a set of registered users that are corrupted. Denote q as wise, S extracts user’s keys (upkj , uskj ) from Lhonest . Then, =
uid uid , σ̄1 )−1 · e(Y0usk Yn+1 e(Y0usk Yn+1 , σ̄1 ) f
g
19
S answers the query by executing the Show algorithm and returns the token tok to A1 . S inserts (uidj , {xi }i∈I , credj , mj , tokj ) into a list Lshow . − To answer the Corrupt request on (uidj , ⃗xj ) ∈ Lhonest with restriction that j ̸= β ∗ , simulator S returns the corresponding user secret key uskj , credential credj and the token tokj to A1 , which are recorded in Lhonest , Lissue and Lshow , respectively. S inserts (uidj , ⃗xj ) into Lcorrupt . If (uidj , ⃗xj ) does exist in these lists, S returns ⊥. Challenge. Adversary A1 outputs a challenge tuple (⃗x∗ , ∗ m , cred∗ , tok∗ ) with attributes ⃗x∗ , a message m∗ and an authentication token tok∗ for the β ∗ -th honest user with uidβ ∗ . The restriction is that (m∗ , ⃗x∗ , cred∗ , tok∗ ) ∈ / Lshow , cred∗ ∈ / Lissue , (uid∗ , ⃗x∗ ) ∈ / Lcorrupt . We say that A1 wins the game if FAC.Verify (tok∗ , m∗ ) = 1. One can note that this game is perfectly simulated if the guess on β ∗ ∈ [1, q] is correct, which occurs with probability 1/q. In this case, adversary A1 is succeed with advantage ϵ1 to prove knowledge of uskβ ∗ = a when it shows a valid credential. S sends the challenge tuple to C. Then, C runs the extractor of the proof of knowledge to recover a, which is a solution to the DL problem. Therefore, the probability for C to break the DL assumption is ϵ1 /q.
If (uid, ⃗x) already exists in Lhonest , S just replies with the same answer. − For the Issue queries on (uid, ⃗x), S runs UserKeyGen to generate (upk, usk) if (uid, ⃗x) has not been queried beforehand. Otherwise, S extracts user’s keys (upk, usk) from Lhonest . Then, S queries C on (uid, ⃗x) and obtains a URS $ signature σ = (e σ1 , σ e2 ), where σ e1 ← − G2 and σ e2 ← Pn τ + i=1 yi ·xi σ e1 . S implicitly sets σ1 = σ e1 = hr , computes σ2
= = =
σ1 )yn+1 ·uid σ (e σ1 )usk·y0 (e e2 (husk )r·y0 hr(τ + r·y0
upk
·h
r(τ +
Pn
i=1 yi xi +yn+1 ·uid)
Pn
i=1 yi xi +yn+1 ·uid)
,
and returns cred ← (σ1 , σ2 ) to A2 . S inserts (uid, ⃗x, upk, cred) into a list Lissue . − The inputs of Show query are (uid, {xi }i∈I , cred, m). A Show query can only be made for a credential that has been created in the Issue query since the latter uses the OSign∗ oracle of the unforgeability game of URS scheme [36] as subroutine. Then, S answers the query by executing the Show algorithm and returns the token tok to A2 . S inserts (uid, {xi }i∈I , cred, m, tok) into a list Lshow . − To answer Corrupt on (uid, ⃗x), simulator S returns the corresponding user secret key usk, credential cred and the token tok to A2 , which are recorded in Lhonest , Lissue and Lshow , respectively. S inserts (uid, ⃗x) into Lcorrupt . If (uid, ⃗x) does exist in these lists, S returns ⊥. Challenge. Adversary A2 outputs a challenge tuple (uid∗ , ∗ ⃗x , m∗ , cred∗ , tok∗ ), which associates with challenge secret key usk∗ . Since we are simulating a type-2 adversary A2 , it is requested that usk∗ should be different from uski for any honest user i. The constraints also include that (m∗ , ⃗x∗ , cred∗ , tok∗ ) ∈ / Lshow , cred∗ ∈ / Lissue , (uid∗ , ⃗x∗ ) ∈ / Lcorrupt . We say that A2 wins the game if FAC.Verify (tok∗ , m∗ ) = 1. If A2 is succeed with advantage ϵ2 to prove knowledge of usk∗ when it shows a valid credential. S sends the challenge tuple to C. Then, C runs the extractor of proof of knowledge to recover usk∗ . C parses cred∗ ← (σ1∗ , σ2∗ ) and calculates σ e1∗ = ∗ r ∗ ∗ ∗ −usk∗ ·y0 ∗ yn+1 ·uid∗ σ1 = P h , computes σ e2 = σ2 (σ1 ) (σ1 ) = n ∗ (e σ1∗ )τ + i=1 yi ·xi . Therefore, C obtains a valid forgery σ ∗ = (e σ1∗ , σ e2∗ ) for the URS scheme in [36] with advantage ϵ2 .
Proposition A.2 Suppose type-2 adversary A2 is able to break the unforgeability of FAC with advantage ϵ2 . Then, we can utilize A2 to break the existential unforgeability of URS in [36] with advantage ϵ2 . Proof. The proof reduces the unforgeability of FAC to the existential unforgeability of the unlinkable redactable signature (URS) scheme in Section 4 of [36]. As the unforgeability of URS relies on the DL assumption, this proposition follows. Let type-2 adversary A2 be a PPT adversary that wins the unforgeability game with probability ϵ2 . Consider a simulator S which runs A2 as a subroutine and interacts with a unforgeability game challenger C for the URS scheme in [36]. Setup. S generates the public parameter pp = (g, h, n) and sends it to C, where g, h are generators of G1 , G2 , respectively, f= and n is the attribute number. C generates the public key pk (W, {Xi , Yi }i∈[1,n] , {Zi,j }1≤i̸=j≤n ) of URS, and transmits it to simulator S, where W = g τ , Xi = hyi , Yi = g yi for i ∈ [1, n], and Zi,j = g yi ·yj for 1 ≤ i ̸= j ≤ n. Note that the e = (τ, {yi }i∈[1,n] ) of URS is unknown to S. S secret key sk
The proofs for two propositions against A = (A1 , A2 ) conclude the proof for unforgeability of FAC.
$
selects random elements y0 , yn+1 ← − Z∗p , and implicitly sets the secret key of FAC as sk = (τ, {yi }i∈[0,n+1] ). S calculates Xi = hyi , Yi = g yi for i = {0, n + 1}, computes Zi,n+1 = y Yi n+1 = g yi ·yn+1 for 1 ≤ i ≤ n, Z0,j = Yjy0 = g y0 ·yj for 1 ≤ j ≤ n, and Z0,n+1 = g y0 ·yn+1 . S sets the public key of FAC as pk = (W, {Xi , Yi }i∈[0,n+1] , {Zi,j }0≤i̸=j≤n+1 ) and forwards it to A2 . Query. The adversary A2 adaptively makes the following queries. − For the UserKeyGen queries on (uid, ⃗x), S generates $ user’s secret key usk ← − Z∗p and public key upk = husk , which are returned to A2 . S adds (uid, ⃗x, upk, usk) to a list Lhonest .
3.2) Anonymity and Unlinkability of FAC Lemma A.2 The FAC scheme satisfies anonymity and unlinkability under the decisional Diffie–Hellman (DDH) assumption. Proof. Suppose a PPT adversary A is able to break the anonymity of FAC with advantage ϵ. Then, we can utilize A to solve the DDH problem with advantage ϵ. Consider a simulator S which runs A as a subroutine and interacts with a challenger C for the DDH-assumption. Let g, h be the generators of
20
groups G1 and G2 , respectively. Let (h, ha , hb , hc ) be a challenge tuple of DDH assumption on group G2 . It is required $ to decide whether c = a · b or c ← − Z∗p . Setup. S creates the public key pk = (W, {Xi , Yi }i∈[0,n+1] , {Zi,j }0≤i̸=j≤n+1 ) following the Setup and CredKeyGen algorithms in FAC and forwards it to A. Query. A adaptively makes the following queries. − For the UserKeyGen queries on (uid, ⃗x), S generates $ user’s secret key usk ← − Z∗p and public key upk = husk , which are returned to A. S adds (uid, ⃗x, upk, usk) to a list Lhonest . If (uid, ⃗x) already exists in Lhonest , S just replies with the same answer. − For the Issue queries on (uid, ⃗x), S runs UserKeyGen to generate (upk, usk) if (uid, ⃗x) has not been queried beforehand. Otherwise, S extracts user’s keys (upk, usk) from Lhonest . Since S creates the issuer’s secret key sk by itself in Setup phase and knows user’s secret key usk, S executes the Issue protocol to obtain cred ← (σ1 , σ2 ), which is returned to A. S inserts (uid, ⃗x, upk, cred) into a list Lissue . − The inputs of Show query are (uid, {xi }i∈I , cred, m). A Show query can only be made for a credential that has been created in the Issue query. S extracts (uid, ⃗x, upk, cred) from Lissue . Then, S answers the query by executing the Show algorithm and returns the token tok to A. S inserts (uid, {xi }i∈I , cred, m, tok) into a list Lshow . − To answer Corrupt on (uid, ⃗x), simulator S returns the corresponding user secret key usk, credential cred and the token tok to A, which are recorded in Lhonest , Lissue and Lshow , respectively. S inserts (uid, ⃗x) into Lcorrupt . If (uid, ⃗x) does exist in these lists, S returns ⊥. Challenge. In this phase, A outputs two challenge users with attributes (uid∗0 , ⃗x∗0 ), (uid∗1 , ⃗x∗1 ), and message m∗ . The simulator S flips a random coin b̄ ∈ {0, 1} and generates challenge tok∗ for user uid∗b̄ , where ∗ ∗ ∗ ∗ ∗ ∗ ∗ tok∗ ← ({x = gα , Pi }i∈I ∗ , T1 , T2 , σ̄1 , σ̄2 , π2 ), T1 ∗ b ∗ ∗ ∗ ∗ ′ yi i∈I , σ̄1 = h , σ̄2 = (hc )y0 · T2 = P (T1 ) +yn+1 ·uid∗ ∗ α+τ + i∈I ∗ yi x∗ i b̄ ), π ∗ is a simulated knowledge (σ̄1 ) 2 of a, the disclosed attribute set I ∗ ⊆ [1, n], α ∈R Z∗p . The restriction is that the disclosed attributes in ⃗x∗0 and ⃗x∗1 / Lshow , / Lissue , (m∗ , ⃗x∗0/1 , tok∗0/1 ) ∈ are the same, cred∗0/1 ∈ (uid∗0/1 , ⃗x∗0/1 ) ∈ / Lcorrupt . Guess. The adversary A makes a guess b̄′ ∈ {0, 1} on the identity of the user from (uid∗0 , uid∗1 ). A wins the game if b̄′ = b̄. S sends the guessP result of A to C. It is noted that if c = ab, by setting t1 = α − i∈[1,n]\I ∗ yi x∗i , One can see that tok∗ is distributed as in the FAC scheme. Else, c is a random number in Z∗p and σ̄2∗ is a random element in G2 . Since (T1∗ , T2∗ , σ̄1∗ ) are independent of a and {x∗i }i∈[n]\I ∗ , A cannot succeed in this game with non-negligile advantage. If A is able to win the security game with advantage ϵ, C can makes use of A to solve the DDH problem with advantage ϵ.
This section defines correctness, privacy, authenticity, anonymity and unlinkability for ACME scheme. Definition B.1. Let D be the universe of user identity, and Ω be the universe of attributes. An anonymous credential-based matchmaking encryption encryption scheme ACME is correct for D, Ω if all uid ∈ D, all ⃗x ⊆ Ω for all security parameter λ,
$
(mpk, msk) ← − Setup(1λ , 1n );
$ (pk, sk) ← − CredKeyGen(mpk); $ − UserKeyGen(mpk); (upk, usk) ← $ credsnd ← − ⟨Issue.I(sk, upk) ⇄ Issue.U(uid, ⃗ xsnd , usk)⟩ ; $ Pr DK⃗xrcv ← − DKGen(msk, ⃗ x ); rcv DKfrcv ← PolGen(msk, frcv ); $ CT⃗xsnd ,fsnd ← − Enc(credsnd , ⃗ xsnd , fsnd , M ) : (out) (out) frcv (⃗ x ) = 1 ∧ fsnd (⃗ xrcv ) = 1∧ snd
Dec(DK⃗xrcv , DKfrcv , CT⃗xsnd ,fsnd ) = ⊥
≤ ν(λ), where ν is a negligible function. Definition B.2. An ACME scheme ACME satisfies privacy if for any PPT adversary A = (A1 , A2 ), there exists a def negligible function ν such that Advpriv ACME (λ) = $ − {0, 1} (mpk, msk) ← Setup(1λ , 1n ), b ← ∗ (M0∗ , M1∗ , cred∗snd0 , cred∗snd1 , ⃗ x∗snd0 , ⃗ x∗snd1 , fsnd ) ′ O ,O ,O Pr b = b ← A1 1 2 3 (mpk) ∗ ∗ ∗ ∗ CT ← Enc(credsnd , ⃗ xsnd , fsnd , Mb )
b
b
b′ ← A2O1 ,O2 ,O3 (mpk, CT∗ )
≤ ν(λ), where oracles O1 , O2 , O3 are implemented by Issue (msk, ·), DKGen(msk, ·), PolGen(msk, ·), respectively. It is required that O2 and O3 are not queried for attributes and ∗ ∗ policies that can satisfy (⃗x∗snd0 , fsnd ) or (⃗x∗snd1 , fsnd ). It is also (out)∗ (out)∗ required that for public attributes ⃗xsnd0 / ⃗xsnd1 in ⃗x∗snd0 / (out)∗ (out)∗ ⃗x∗snd1 , we have ⃗xsnd0 = ⃗xsnd1 . This model only captures security under chosen plaintext attacks (CPA). We can extend the above definition by introducing another decryption oracle O4 which can decrypt ciphertexts except the challenge ciphertext CT∗ to capture security under chosen-ciphertext attacks (CCA). Definition B.3. An ACME scheme ACME satisfies authenticity if for any PPT adversary A, there exists a negligible def function ν such that Advauth ACME (λ) = (mpk, msk) ← Setup(1λ , 1n ) O ,O ,O (CT xrcv , frcv ) ← A 1 2 3 (mpk) ⃗ xsnd ,fsnd , ⃗ DK ← DKGen(msk, ⃗ x ) rcv ⃗ xrcv Pr DKfrcv ← PolGen(msk, frcv ) M = Dec(DK⃗xrcv , DKfrcv , CT⃗xsnd ,fsnd ) (out) ∀⃗ x ∈ QO1 ,O2 : (frcv (⃗ x ) = 0) ∧ (M ̸= ⊥)
≤ ν(λ), where oracles O1 , O2 , O3 are implemented by Issue (msk, ·), DKGen(msk, ·), PolGen(msk, ·). ACME also satisfy the security properties of anonymous credential, namely anonymity (Def. A.3) and unlinkability (Def. A.4), against an entity who can decrypt the ciphertext. (2) Security Proof
B. ACME: Security Model and Proof (1) Security Model
21
Theorem 6.2. The proposed ACME scheme achieves privacy, authenticity, anonymity and unlinkability if the M DDHk assumption holds and the underlying FAC is secure. The security proofs of authenticity, anonymity and unlinkability of ACME follows those of unforgeability, anonymity and unlinkability of FAC. Next, we prove that the proposed ACME scheme achieves privacy under the M DDHk assumption. Proof Intuition. In our proposed ACME scheme, the message M and the FAC token toksnd (corresponding to the private attributes) are encrypted using a symmetric key K which is ⊤ encapsulated in ct0 = e([es A + s⊤ A]1 , [v]2 ) · K. Hence, the privacy of both M and toksnd is based on the confidentiality of the symmetric key K. (out) As shown in the correctness, when frcv (⃗xsnd ) = 1 (corresponding to KP-ABE), we have Q ω e ct′2 , j∈Sr dkj j ⊤ ωj = ([es Av]T )−1 Q Q dk e ct′1 , j∈Sr (out) i,j =1 i:x
A ciphertext (under access policy f and attributes ⃗x) can be in one of the following forms: - Normal: A normal ciphertext is generated by Enc. - SF: An SF ciphertext is the same as Normal ciphertext, ⊤ ⊤ except that s⊤ A, s⊤ j A are replaced with c , cj , where c, cj ← ⊤ Z2k c := es A as in the normal ciphertext, then CT⃗x,f := p . Let e ⊤
(ct0 = e([ec + c⊤ ]1 , [v]2 ) · K, ⊤X ⊤ ct′1 = [ec ]1 , ct′2 = ec Wi 1 , (out) i:xi
=1
⊤ ⊤ e j = [ c⊤ ct1 = [ c⊤ ]1 , {ct j ]1 , ctρ(j),j = [uj + cj Wρ(j) ]1 ,
cti,j =
c⊤ j Wi 1 }).
A secret key DKf (for policy f ) follows its normal form in this case. A secret key (for attributes ⃗x) can be in one of the following forms: - Normal: A normal secret key is generated by DKGen. - SF: An SF key is sampled as a Normal key, except v is replaced with v + A⊥ δ (q) , where a fresh δ (q) ← Zkp is chosen \{0} such that per SF key and A⊥ is any fixed A⊥ ∈ Z2k×k p AA⊥ = 0. That is DK⃗x :=
s,i
(out) and when fsnd (⃗xrcv ) = 1 (corresponding to CP-ABE), we
have Q Q e( j∈Ss ( i:x(out) =1 cti,j )µj , dk2 ) r,i = ([s⊤ Av]T )−1 . Q e µj j , dk3 ) e(ct1 , dk1 ) · e( ct j∈Ss
(dk1
Hence, the proof for the confidentiality of K essentially follows the same proof techniques used in the underlying (dual) CP-ABE and KP-ABE schemes [26], [27]. Specifically, (out)∗ if frcv (⃗xsnd ) ̸= 1, then the confidentiality of K is ensured by the security of the KP-ABE scheme; otherwise, since according to the security game, the adversary is not allowed (out)∗ to obtain keys for frcv and ⃗xrcv such that frcv (⃗xsnd ) = (out) ∗ 1 ∧ fsnd (⃗xrcv ) = 1, the security is ensured by that of the CP-ABE scheme. The dual ABE schemes in [26], [27] both applied a sequence of games and a hybrid argument in the security proofs. The initial game is the same as the original security game whereas in the last game, the encrypted symmetric key K is replaced by a random key. Here we follow the same game sequences defined in [26], [27] by considering two cases: if the adversary (out)∗ would not query a key for frcv such that frcv (⃗xsnd ) = 1, then we follow the transitions of the keys and ciphertexts in the proof of KP-ABE and use normal keys and ciphertexts for the CP-ABE componments; otherwise, we perfom the transitions in the opposite way. Below we outline the crucial steps of the proof.
dk3
[ v + A⊥ δ (q) + U0 Br]2 , dk2 = [Br]2 , X = [ Wi Br]2 ). (out)
=
i:xi
=1
- P-Normal: A P-Normal key as the same as a Normal key, except Br is replaced with d ← Zkp . That is DK⃗x := X dk1 = [v+U0 d ]2 , dk2 = [ d ]2 , dk3 = [ Wi d ]2 . (out) i:xi
=1
- P-SF: A P-SF key is the same as an SF key, except Br is replaced with d ← Zkp . That is DK⃗x := (dk1 = [ v + A⊥ δ (q) + U0 d ]2 , dk2 = [ d ]2 , X Wi d ]2 ). dk3 = [ (out) i:xi
=1
Next, we define the hybrid sequence for the proof. Assume the adversary A makes at most Qx attribute decryption key queries. - H0 : This is the real game where all secret keys and ciphertexts are Normal. - H1 : This game is the same as H0 except that the challenge ciphertext is SF. - H2,ℓ,1 : This game is the same as H1 except that the ℓ-th attribute decryption key is P-Normal, the first ℓ − 1 attribute decryption keys are SF and the last Qx −ℓ attribute decryption keys are Normal, where ℓ = 0, · · · , Qx . - H2,ℓ,2 : This game is the same as H2,ℓ,1 except the ℓ’th attribute decryption key is P-SF, where ℓ = 0, · · · , Qx . - H2,ℓ,3 : This game is the same as H2,ℓ,2 except the ℓ’th attribute decryption key is SF, where ℓ = 0, · · · , Qx . - H3 : This game is the same as H2,Qx ,3 except that the message encryption symmetric key K to be encrypted is e replaced by a random K.
Proof. Let ≡ denote that two distributions are identically distributed, and ≈c represent that two distributions are computationally indistinguishable. The security of ACME scheme is proved by a series of hybrid games, depending on whether the adversary would (out)∗ query a key for frcv such that frcv (⃗xsnd ) = 1. Case 1: the adversary queries a key for frcv such that (out)∗ frcv (⃗xsnd ) = 1. Note that in this case the adversary cannot (out) ∗ query a key for ⃗xrcv such that fsnd (⃗xrcv ) = 1.
22
Let A be a PPT adversary, and Advxxx be the advantage of A in game Hxxx . Also, define H1 ≡ H2,0,1 . To complete the proof for Case 1, we prove lemmas E.2-E.6 in the following. Lemma B.1. Under the M DDHk2m+1 assumption on G1 , we have
Setup. B chooses generators g ← G1 , h ← G2 , user’s attribute number n, and sets pp = (g, h, n). Next, B selects 2k×(k+1) A ← Zk×2k , U0 , Wi ← Zp , v ← Z2k p p , and forms mpk with these parameters as in the scheme. B computes A⊥ ∈ Z2k×k such that AA⊥ = 0, which is used for responding secret p key queries. B runs F AC.CredKeyGen to create (pk, sk). Issue Query. B firstly executes F AC.UserKeyGen to create user’s public/secret keys upk/usk. B can response to any credential issue query since credential issuer’s secret key sk is generated by B. Attribute Decryption Key. B simulates attribute decryption keys as below. - For the first ℓ − 1 attribute decryption key queries, say the q-th request is for ⃗x, B samples δ (q) , r(q) ∈ Zkp , and creates (SF) attribute decryption key DK⃗x := X [v + A⊥ δ (q) + U0 Br(q) ]2 , [Br(q) ]2 , [ Wi Br(q) ]2 .
|P r[⟨A, H0 ⟩ = 1] − P r[⟨A, H1 ⟩ = 1]| = negl(λ). Proof. Assume that A distinguishes H0 and H1 with nonnegligible advantage. Then, we can construct another adversary B to break the M DDHk2m+1 assumption. On input a M DDHk2m+1 challenge ([A]1 , [Z]1 ), where either Z⊤ = S⊤ A (2m+1)×k or Z = C, for S, C ← Zp . B proceeds as below. Setup. B chooses generators g ← G1 , h ← G2 , user’s attribute number n, and sets pp = (g, h, n). B runs FAC.CredKeyGen to create (pk, sk). B selects B ← Zk×k , p U0 , Wi ← Z2k×k , v ← Z2k p p and sets mpk, msk as in the scheme, where the elements [AWi ]1 in mpk can be derived from [A]1 and Wi . Issue Query. B firstly executes F AC.UserKeyGen to create user’s public/secret keys upk/usk. B can response to any credential issue query since credential issuer’s secret key sk is generated by B. Attribute Decryption Key Query. B can response to any attribute decryption key query since msk is generated by B. Policy Decryption Key Query. B can response to any policy decryption key query since msk is generated by B. Challenge. After the secret key queries, A requests for the challenge ciphertext corresponding to symmetric keys (K0 , K1 ), attributes ⃗x and formula f . B flips a random coin coin ← {0, 1} and constructs the challenge ciphertext for ⊤ Kcoin . B computes ({u⊤ j }, ρ) ← share(f, z2m+1 U0 ) and sets the challenge ciphertext as CT⃗x,f :=
i:xi =1
- For the last Qx − ℓ attribute decryption key queries, B proceeds as before for the first ℓ − 1 keys except substituting v + A⊥ δ (q) with v. It is obvious that it becomes a Normal key. - For the ℓth attribute decryption keyPrequest, A′ creates the secret key DK⃗x := [v + U0 z]2 , [z]2 , [ i:xi =1 Wi z]2 . Policy Decryption Key. B simulates any policy decryption key normally since the elements for generating policy decryption key are generated by B. Challenge. After the secret key queries, A requests for the challenge ciphertext corresponding to symmetric keys (K0 , K1 ), attributes ⃗x and formula f . B flips a random coin coin ← {0, 1} and constructs the challenge ciphertext for Kcoin . Sample c, cj ← Z2k p for each j, compute ⊤ ({u⊤ }, ρ) ← share(f, c U ) and return (SF) challenge 0 j ciphertext CT⃗x,f :=
⊤
(ct0 = e([ez + z⊤ 2m+1 ]1 , [v]2 ) · Kcoin , X ⊤ ⊤ ct′1 = [ez ]1 , ct′2 = [ez Wi ]1 , (out) i:xi
⊤
ct0 = e([ez + c⊤ ]1 , [v]2 ) · Kcoin , X ⊤ ⊤ ct′1 = [ez ]1 , ct′2 = [ez Wi ]1 , (out)
=1
⊤ ⊤ ⊤ e ct1 = [z⊤ 2m+1 ]1 , {ctj = [zj ]1 , ctρ(j),j = [uj + zj Wρ(j) ]1 ,
i:xi
cti,j = [z⊤ j Wi ]1 }),
=1
⊤ ⊤ e j = [c⊤ ct1 = [c⊤ ]1 , ct j ]1 , ctρ(j),j = [uj + cj Wρ(j) ]1 , cti,j = [c⊤ j Wi ]1 .
where (ez, ct′1 , ct′2 ) are computed normally and note that |{uj }| ≤ 2m. Guess. A halts the game with a guess coin′ ← {0, 1}. B outputs 1 if coin′ = coin, and 0 otherwise. It is straight forward to see that if Z⊤ = S⊤ A, the challenge ciphertext is Normal and B simulates H0 ; if Z⊤ = C⊤ , the challenge ciphertext is SF and B simulates H1 .
Guess. A halts the game with a guess coin′ ← {0, 1}. B outputs 1 if coin′ = coin, and 0 otherwise. It is straight forward to see that if z = Br, then the ℓth attribute decryption key is Normal and A′ has simulated H2,ℓ−1,3 ; if z = d, then the ℓth attribute decryption key is P-Normal and A′ has simulated H2,ℓ,1 .
Lemma B.2. Under the M DDHk assumption on G2 , we have
Lemma B.3. Under the M DDHk assumption, we have
|P r[⟨A, H2,ℓ−1,3 ⟩ = 1] − P r[⟨A, H2,ℓ,1 ⟩ = 1]| = negl(λ).
|P r[⟨A, H2,ℓ,1 ⟩ = 1] − P r[⟨A, H2,ℓ,2 ⟩ = 1]| = negl(λ).
Proof. Assume that A distinguishes H2,ℓ−1,3 and H2,ℓ,1 with non-negligible advantage. Then, we can construct another adversary B to break the M DDHk assumption. On input M DDHk challenge ([B]2 , [z]2 ), where either z = Br for r ← Zkp , or z = d for d ← Zk+1 . B proceeds as below. p
Proof. Assume that A distinguishes H2,ℓ,1 and H2,ℓ,2 with non-negligible advantage. Then, we can construct another adversary B that distinguishes the oracles in G1−ABE of [26], β which implies an attacker against the M DDHk assumption.
23
Given µ(0) as an input and equipped with oracles OF,β , OX and OE (defined in G1−ABE of [26]), B proceeds as below. β Setup. B chooses generators g ← G1 , h ← G2 , user’s attribute number n, and sets pp = (g, h, n). Next, B chooses e 0, W e i ← Z2k×k A ← Zk×2k , B ← Zk×k ,U for i ∈ [1, n], and p p p ⊥ ⊥ 2k 2k×k e v ← Zp , computes A ∈ Zp \{0}, b ← Zkp such that ⊥ ⊥ ⊤ AA = 0 and (b ) B = 0 and implicitly defines v := e v−
Policy Decryption Key. B can simulate any policy key normally since the elements for generating policy decryption key are generated by B. Challenge. When A requests a challenge ciphertext for symmetric keys (K0 , K1 ), attributes ⃗x and formula f , B flips a random coin coin ← {0, 1} and constructs the challenge ciphertext for Kcoin . B queries OF (f ) → {[µj + k r⊤ j wρ(j) ]1 , [rj ]1 } "on input # f . B samples ecj ← Zp for each (A⊥ )⊤ j, defines A⊥ ∈ Z2k×2k for a choice of M that C := p M ⊤ ⊥ e 0 ), makes A" ({e uj }, ρ) ← share(f, c⊤ U C invertible, computes !# −1 rj [cj ]1 := (A⊥ , and constructs the (SF) challenge C) ecj 1 ciphertext CT⃗x,f :=
µ(0) ((b⊥ )⊤ d) ⊥ A u, c ⊤ A⊥ u
(β) e0 + µ U0 := U A⊥ u(b⊥ )⊤ , c⊤ A⊥ u e i + A⊥ wi (b⊥ )⊤ , Wi := W
where wi ∈ Zkp , µ(β) ∈ Zp are chosen by the G1-ABE game β 2k in [26], c ← Zp is selected for generating the challenge ciphertext, d ← Zk+1 is selected for generating the ℓth secret p key, and u ← Zkp . Note that B can compute v since it has µ(0) from the game and knows all other vectors. Then, B creates
⊤
ct0 = e([ez + c⊤ ]1 , [v]2 ) · Kcoin , X ⊤ ⊤ e i + A⊥ wi (b⊥ )⊤ ]1 , W ct′1 = [ez ]1 , ct′2 = [ez {z } | (out) i:xi
e 0 ]1 , [AW e 1 ]1 , · · · , [AW e n ]1 , e([A]1 , [e mpk := (pp, [A]1 , [AU v]2 )). B runs F AC.CredKeyGen to create (pk, sk). Issue Query. B firstly executes F AC.UserKeyGen to create user’s public/secret keys upk/usk. B can response to any credential issue query since credential issuer’s secret key sk is generated by B. Attribute Decryption Key. B simulates attribute decryption key as below. - For the first ℓ − 1 attribute decryption key queries, say the qth request is for ⃗x, B samples δ (q) , r(q) ← Zkp , and creates the (SF) attribute decryption key: DK⃗x :=
(out)
i:xi
We can deduce that ⊤
⊥ ⊤ ⊤ e ctρ(j),j = [e uj + µj (b⊥ )⊤ + c⊤ j Wρ(j) + rj wρ(j) (b ) ]1 . | {z } | {z } ≡share(f,c⊤ U0 )
=v+
e d e v+U | {z 0 }
e i Br(q) ]2 ). W =1 | {z } =Wi Br(q)
]2 ,
Lemma B.4. Under the M DDHk assumption, we have |P r[⟨A, H2,ℓ,2 ⟩ = 1] − P r[⟨A, H2,ℓ,3 ⟩ = 1]| = negl(λ). Proof. Omitted, since this proof is similar to that of Lemma E.3. We need to substitute v with v + A⊥ δ (ℓ) for the ℓth attribute decryption key query, where δ (ℓ) is a random element.
dk2 = [d]2 ,
(µ(0) −µ(β) )((b⊥ )⊤ d) ⊥ A u+U0 d (c⊤ A⊥ u)
X dk3 = [
(out)
i:xi
Lemma B.5. We have
e i + A⊥ wi (b⊥ )⊤ )d]2 ). (W {z }
=1 |
=c⊤ j Wρ(j)
It should be noted that {µj (b⊥ )⊤ } is distributed like the output of share(f, µb (b⊥ )⊤ ), and therefore due to linearity ⊤ e 0 + µ(b) (b⊥ )⊤ , then {e and the fact that c⊤ U0 = c⊤ U uj + ⊥ ⊤ ⊤e (b) ⊥ ⊤ µj (b ) } is distributed like share(f, c U0 + µ (b ) ) ≡ ⊥ ⊤e share(f, c⊤ U0 ). Also, note that c⊤ j Wi = cj Wi + rj wρ(j) b ⊥ since c⊤ j A = rj . Guess. A halts the game with a guess coin′ ← {0, 1}. B outputs 1 if coin′ = coin, and 0 otherwise. Putting everything together, we can see that B simulates H2,ℓ,1 when β = 0; and H2,ℓ,2 when β = 1.
- For the last Qx − ℓ attribute decryption key queries, B proceeds as before for the first ℓ − 1 keys except using just v instead of v + A⊥ δ (q) . It is easy to see that it forms a Normal attribute decryption key. - For the ℓth attribute decryption key query for ⃗x, queries OX (⃗x) → ({wi }xi =1 ) and creates the attribute decryption key: DK⃗x := (dk1 = [
e j = [c⊤ ct j ]1 ,
⊥ ⊤ ⊤e cti,j = r⊤ j wi (b ) + cj Wi ]1 ).
=U0 Br(q)
dk2 = [Br(q) ]2 ,
=Wi
⊤ ⊥ ⊤ ⊤e ctρ(j),j = [e uj + (µj + r⊤ j wρ(j) )(b ) + cj Wρ(j) ]1 ),
e Br(q) ] , (dk1 = [v + A⊥ δ (q) + U | 0 {z } 2 X dk3 = [
ct1 = [c⊤ ]1 ,
=1
|P r[⟨A, H2,Qx ,3 ⟩ = 1] − P r[⟨A, H3 ⟩ = 1]| ≤ 1/p
=Wi d
We claim that if β = 0, then the ℓth key is a P-Normal (0) (0) )((b⊥ )⊤ d) ⊥ attribute decryption key since v+ (µ −µ A u = v; (c⊤ A⊥ u)
unconditionally. Proof. These two hybrids are identically distributed conditioned on c⊤ A⊥ ̸= 0. To see this, consider two ways of e for an choosing v : v = e v ← Z2k v + A⊥ m p and v : v = e
and if β = 1, then the ℓth key is a P-SF key since δ (ℓ) = (µ(0) −µ(1) )((b⊥ )⊤ d) u. (c⊤ A⊥ u)
24
e ← Zkp . Note that both result in v independently random m having a uniform distribution. Using e v to simulate hybrid H2,Qx ,3 obviously results in H2,Qx ,3 (where v = e v). However, using the identically dise to simulate H2,Qx ,3 results in H3 with tributed v = e v + A⊥ m e = Kcoin · [c⊤ A⊥ m] e T . Note that the information of m e is not K e is blinded by leaked to A from the secret key queries since m e is distributed random value δ (i) for each key. Therefore, K uniformly at random over GT as long as c⊤ A⊥ ̸= 0. ⊤ Since c is chosen at random and independent from es A and ⊥ ⊥ A ̸= 0, so c⊤ A = 0 with probability 1/p, and since we know that H2,Qx ,3 ≡ H3 conditioned on c⊤ A⊥ ̸= 0, then the lemma follows.
Lemma B.6. Under the M DDHk assumption on G1 , we have |P r[⟨A, H0 ⟩ = 1] − P r[⟨A, H1 ⟩ = 1]| = negl(λ). Proof. If A can distinguish H0 from H1 with non-negligible advantage, then we can construct an algorithm B that can solve the M DDHk assumption. On input a M DDHk challenge ⊤ ⊤ ([A]1 , [ez]1 ), where either ez = es A or ez = ec for es ← Zkp and ec ← Z2k p . B proceeds as in the proof of Lemma E.2 except that an SF challenge ciphertext is returned to A. B flips a random coin coin ← {0, 1} and constructs the challenge ciphertext ⊤ for Kcoin by computing ({u⊤ j }, ρ) ← share(f, z U0 ), where ⊤ ⊤ ⊤ ⊤ z = s A, and zj = sj A as in the normal ACME construction, and sets the challenge ciphertext as CT⃗x,f :=
Case 2: the adversary does not query a key for frcv such that (out)∗ frcv (⃗xsnd ) = 1. A ciphertext (under access policy f and attributes ⃗x) can be in one of the following forms: - Normal: A normal ciphertext is generated by Enc. - SF: An SF ciphertext is the same as Normal ciphertext, ⊤ ⊤ except that es A is replaced with ec ← Z2k x,f := p . That is CT⃗ ⊤
(ct0 = e([ ec
⊤
ct0 = e([ez + z⊤ ]1 , [v]2 ) · Kcoin , X ⊤ ⊤ Wi ]1 , ct′1 = [ez ]1 , ct′2 = [ez (out) i:xi
⊤
ct1 = [z
cti,j = [z⊤ j Wi ]1 } . Guess. A halts the game with a guess coin′ ← {0, 1}. B outputs 1 if coin′ = coin, and 0 otherwise. It is straight ⊤ ⊤ forward to see that if ez = es A, the challenge ciphertext ⊤ ⊤ is Normal and B simulates H0 ; if ez = ec , the challenge ciphertext is SF and B simulates H1 .
+ c⊤ ]1 , [v]2 ) · K,
⊤ X ⊤ ct′1 = [ ec ]1 , ct′2 = ec
(out)
i:xi
=1
Wi 1 ,
⊤ ⊤ e j = [c⊤ ct1 = [c⊤ ]1 , {ct j ]1 , ctρ(j),j = [uj + cj Wρ(j) ]1 ,
Lemma B.7. Under the M DDHk assumption on G2 , we have
cti,j = [c⊤ j Wi ]1 }),
|P r[⟨A, H2,ℓ−1 ⟩ = 1] − P r[⟨A, H2,ℓ ⟩ = 1]| = negl(λ).
⊤ where c⊤ = s⊤ A and c⊤ j = sj A are same as in the original ciphertext. A secret key (for attributes ⃗x) follows its normal form. A secret key (for a Boolean formula f ) can be one of the following forms: - Normal: A normal secret key is generated by PolGen. - SF: An SF key is sampled as a Normal key, except v is replaced with v + δa⊥ , where a fresh δ is chosen per SF key and a⊥ is any fixed a⊥ ∈ Z2k p \{0}. That is DKf := dkj = [rj ]2 , dkρ(j),j = [vj + Wρ(j) rj ]2 , dki,j = [Wi rj ]2 . $
=1
⊤ ⊤ e j = [z⊤ ]1 , {ct j ]1 , ctρ(j),j = [uj + zj Wρ(j) ]1 .
Proof. Assume that A distinguishes H2,ℓ−1 and H2,ℓ with non-negligible advantage. Then, we can construct another of [27], adversary B that distinguishes the oracles in G1−ABE β which implies an attacker against the M DDHk assumption. Given µ(0) as an input and equipped with oracles OF,β , OX and OE (defined in G1−ABE of [27]), B proceeds as below. β Setup. B chooses generators g ← G1 , h ← G2 , user’s attribute number n, and sets pp = (g, h, n). Next, B chooses $ $ $ e 0, W ei ← A← − Zk×2k ,U − Z2k×k for i ∈ [1, n], and e v← − Z2k p p p , ⊥ computes a⊥ ∈ Z2k \{0} such that Aa = 0. It then sets p e 0 := 0 and implicitly defines v := e W v + µ(0) a⊥ , Wi := ⊥ ⊤ k (0) e Wi + a wi , where wi ∈ Zp , µ ∈ Zp are chosen by the G1-ABE game in [27]. Then, B creates β
$
where ({vj }j∈[m̂] , ρ) ← − share(f, v + δa⊥ ), rj ← − Zkp . Next, we define hybrid sequences for the proof. Assume the adversary A makes at most Qx attribute decryption key queries and Qf policy decryption key queries. - H0 : This is the real game where all secret keys and ciphertexts are Normal. - H1 : This game is the same as H0 except that the challenge ciphertext is SF. - H2,ℓ : This game is the same as H1 except that the first ℓ policy decryption keys are SF and the remaining Qf − ℓ keys are Normal, where ℓ = 0, · · · , Qf . - H3 : This game is the same as H2,Qf except that the message encryption symmetric key K to be encrypted is e replaced by a random K.
e 0 ]1 , [AW e 1 ]1 , · · · , [AW e n ]1 , e([A]1 , [e mpk := (pp, [A]1 , [AU v]2 )). B runs F AC.CredKeyGen to create (pk, sk). Issue Query. B firstly executes F AC.UserKeyGen to create user’s public/secret keys upk/usk. B can response to any credential issue query since credential issuer’s secret key sk is generated by B. Attribute Decryption Key Query. B simulates any attribute decryption key normally. Policy Decryption Key Query. B responds to A’s policy decryption key queries as below.
25
ct1 = [c⊤ ]1 ,
- For the first ℓ − 1 policy decryption key queries, say for formula f of size m, B computes: $
e j = [c⊤ ct j ]1 ,
⊤ e ⊥ ⊤ ctρ(j),j = [u⊤ j + cj (Wρ(j) + a wρ(j) )]1 ), | {z }
e ⊥
({vj }j∈[m̂] , ρ) ← − share(f, e v + δa ), | {z }
=Wρ(j)
=v+δa⊥
⊥ ⊤ e cti,j = [c⊤ j (Wi + a wi )]1 ). | {z }
$
where δe ← − Zp is drawn independently for each key (here, the per-key δ = δe − µ(0) implicitly). Next, for each j ∈ [m̂], it queries OE → ([rj ]2 , {[w⊤ i rj ]2 }i∈[n] ) and forms the SF policy decryption key as DKf :=
=Wi
Guess. A halts the game with a guess coin′ ← {0, 1}. B outputs 1 if coin′ = coin, and 0 otherwise. Putting everything together, we can see that B simulates H2,ℓ−1 when β = 0; and H2,ℓ when β = 1.
e ρ(j) rj + a⊥ w⊤ rj ]2 , (dkj = [rj ]2 , dkρ(j),j = [vj + W ρ(j) | {z } vj +Wρ(j) rj
Lemma B.8. We have
e i r j + a ⊥ w⊤ dki,j = [W rj ]2 ). {z i } |
|P r[ A, H2,Qf = 1] − P r[⟨A, H3 ⟩ = 1]| ≤ 1/p
=Wi rj
unconditionally.
Then, it returns DKf to A. - For the last Qf − ℓ policy decryption key queries, say for formula f of size m, B proceeds as before for the first ℓ − 1 policy decryption keys except
Proof. The two hybrids are identically distributed conditioned ⊤ on ec a⊥ ̸= 0. To see this, consider two ways to sample v: as $ $ e v← − Z2k v + ma e ⊥ for an independent m e ← − Zp . Both p and as e result in v having a uniform distribution. Using e v to simulate hybrid H2,Qf obviously results in H2,Qf (where v = e v). However, using the identically distributed v = e = Kcoin · e v + ma e ⊥ to simulate H2,Qf results in H3 with K ⊤ ⊥ e [ec ma e ]T and re-defined randomness δj = δj + m e for all the keys. Note that the information of m e is not leaked to A from the secret key queries since m e is blinded by random value δj e is distributed uniformly at random for each key. Therefore, K ⊤ over GT as long as [ec a⊥ ]T ̸= 0. Since ec is chosen at random and independent from a⊥ ̸= 0, ⊤ so [ec a⊥ ]T = 0 with probability 1/p, and since we know that ⊤ H2,Qf ≡ H3 conditioned on [ec a⊥ ]T ̸= 0, then the lemma follows.
$
({vj }j∈[m̂] , ρ) ← − share(f, e v + µ(0) a⊥ ), | {z } =v
It is easy to see that it forms a Normal policy decryption key. - For the ℓ-th policy decryption key query, say for formula f of size m, B computes $ ({vj }j∈[m̂] , ρ) ← − share(f, e v), queries OF,β (f ) → ({[rj ]2 , [µj + wρ(j) rj ]2 , {[w⊤ r i j ]2 }i∈[n]\{ρ(j)} }j∈[m̂] ) and uses these components to return: DKf := e ρ(j) rj + a⊥ (µj + w⊤ rj )]2 , (dkj = [rj ]2 , dkρ(j),j = [vj + W ρ(j) | {z } =(vj +µj a⊥ )+Wρ(j) rj
e i r j + a ⊥ w⊤ dki,j = [W rj ]2 ). {z i } |
This completes the proof of Theorem 6.2.
=Wi rj
We claim that if β = 0, then DKf is a Normal policy decryption key, and if β = 1, then DKf is a SF policy key. This follows from the fact that thanks to linearity, the shares $ ({vj + µj a⊥ }j∈[m̂] , ρ), where ({vj }j∈[m̂] , ρ) ← − share(f, e v), $
C. PriSrv: Security Model and Proof (1) Security Model of PriSrv We formalize the security model for PriSrv, which includes the service discovery with bilateral control, key secrecy and bilateral anonymity, by following the Canetti-Krawczyk model for authenticated key-exchange (AKE) in [32], [33], [38] and the service discovery model in [5].
(β)
({µj }j∈[m̂] , ρ) ← − share(f, µ ), are identically distributed to share(f, e v + µ(β) a⊥ ). The claim follows the fact that v = e v + µ(0) a⊥ , where we set δ := µ(1) − µ(0) is a fresh random value for the key. Challenge. When A requests a challenge ciphertext for symmetric keys (K0 , K1 ), attributes ⃗x and formula f , B flips a random coin coin ← {0, 1} and constructs the challenge ciphertext for Kcoin . B queries OX on input ⃗x to obtain ⊤ ⊤ {wi }i:xi =1 . B computes c⊤ = s⊤ A, c⊤ j = sj A, ({uj }, ρ) ←
1.1) Service Discovery Security The service discovery security captures service discovery with bilateral control and AKE security. The framework of PriSrv contains two sub-protocols: a private broadcast protocol that announces the service type, server’s identifier, as well as other relevant information in a privacy-preserving manner; and an anonymous mutual authentication protocol with bilateral policy control. Compared with traditional mutual authentication settings, a remarkable difference in PriSrv is that multiple clients can respond to a service provider’s broadcast
$
share(f, c⊤ U0 ) normally, samples ec ← − Z2k p , and constructs the challenge ciphertext CT⃗x,f := ⊤
ct0 = e([ec + c⊤ ]1 , [e v + µ(0) a⊥ ]2 ) · Kcoin , X ⊤ ⊤ e i + a ⊥ w⊤ ]1 , ct′1 = [ec ]1 , ct′2 = [ec W {z i} | (out) i:xi
=1
=Wi
26
Otherwise, a randomly value picked from the secret session key space is returned.
message if their credentials satisfy the service authorization policy. Protocol participants. The participants of PriSrv includes a set of clients C = {C1 , · · · , Cn1 } and a set of service providers S = {S1 , · · · , Sn2 }. Long-term Keys. Each Ci ∈ C and Sj ∈ S hold longterm secret keys for bilateral authentication and message decryption. Session and Pairing. Denote the ρ-th instance of participant U ∈ C ∪ S as U ρ , which is modeled as a PPT Turing machine. A participant U ρ can be activated to initiate a session with a broadcast identifier bidρU , a session identifier sidρU , attributes ⃗xρU , and a policy fUρ . A client instance Ciρ and a service provider instance Sjδ are said to be paired if their session instances (Ciρ , bidρCi , sidρCi , ⃗xρCi , fCρ i ) and (Sjδ , bidδSj , sidδSj , ⃗xδSj , fSδj ) satisfy bidρCi = bidδSj , sidρCi = ρ(out)
Session Exposure. A session (U ρ , bid, sid) is said to be exposed if the adversary makes the following queries. - The adversary makes a RevealKey query on the session. - The adversary makes a Corrupt query on U , or any partner (out) with (⃗x, f ) satisfying fU (⃗x(out) ) = 1 ∧ f (⃗xU ) = 1, before the session has expired. - U is the client in the protocol and the adversary has made a RevealState query on the session. - U is the server in the protocol and the adversary has made a RevealState query on the session, and also made a RevealBroadcast query on the session or a Corrupt query on U before the session has expired. Session Freshness. A session (U ρ , bid, sid) is said to be fresh if itself is not exposed and all its matching sessions are not exposed. Definition C.1 Let SuccSec PriSrv (A) denote the event that A makes a single TestSession query with the restriction that the queried session (U ρ , bid, sid) is fresh, and finally outputs a bit b′ = b, where b is the random value selected in the TestSession query. A private service discovery protocol PriSrv is secure if for any PPT adversary A, there exists a negligible function ν such def Sec that AdvSec PriSrv (A) = 2Pr[SuccPriSrv (A)] − 1 ≤ ν(λ).
δ(out)
sidδSj , fSδj (⃗xCi ) = 1, fCρ i (⃗xSj ) = 1. A completed sesρ,δ ρ,δ δ sion contains a tuple (Ciρ , bidρ,δ Ci ,Sj , sidCi ,Sj , Sj , SSKCi ,Sj ), ρ ρ,δ ρ δ δ where bidρ,δ Ci ,Sj = bidCi = bidSj , sidCi ,Sj = sidCi = sidSj . Adversary Capability. We capture all of the adversary’s attack capabilities in real world to have full control over the public network communication, including revealing some secrets in the protocol, intercepting or tampering with the channel messages, replaying, delaying, injecting or dropping data packets, interleaving messages from different sessions, etc. Protocol Execution. An adversary A is modeled as a PPT machine with a distinguished query tape to issue a set of session exposure queries for gaining the ephemeral and longterm secrets possessed by participants. • Send(U ρ , M ): transmits a message M to U ρ , who executes the protocol and returns the operation result to adversary A. If the message in the query causes the protocol to execute or abort, it will be made known to A. • Execute(Ciρ , Sjδ ): executes a complete protocol between ρ Ci and Sjδ . The adversary captures all messages transmitted over the public network. Hence, the query to Execute oracle models passive eavesdropping capability of the adversary. • RevealBroadcast(Sjδ , bid): returns the semi-static state in a service provider Sjδ that is maintained for the lifetime of its current broadcast with identifier bid, including the attributes ⃗xSjδ and authorization policy fSjδ . The revealed state does not involve the long-term secrets. A is allowed to make query for any service provider Sj ∈ S. • RevealState(U ρ , bid, sid): returns the local state associated with the targeted session, which does not contain the long-term secrets. • RevealKey(U ρ , bid, sid): outputs the secret session key associated with a targeted session. • Corrupt(U ): returns all information (including ephemeral and long-term secrets) held by U . • TestSession(U ρ , bid, sid): This oracle is used to model key secrecy. A random bit b ∈ {0, 1} is selected to respond this query. If b = 1, the target session key is returned to A.
1.2) Bilateral Anonymity The bilateral anonymity property implies that no PPT service provider (or client) can learn anything about another participant’s identifier and private attributes unless it satisfies the latter’s authorization policy. The adversary is permitted to compromise multiple participants. This property should hold provided that the compromised participants do not satisfy the target’s policy. We include the registration query oracle in the security model for the bilateral anonymity proof. In the following, we firstly define the security game to prove the client anonymity, which captures the property that no adversary can distinguish the interactions with Ci∗0 or Ci∗1 (challenge clients). Let n be the number of parties participating in the protocol execution experiment, which are denoted as (P1 , · · · , Pn ). A special test party PT is introduced at the beginning of the experiment whose identity is kept confidential from the adversary. We introduce two experiments Exp0 and Exp1 , and select random b ∈ {0, 1} at the beginning of the game. The experiment Expb proceeds as below. Setup Phase. At the beginning of the experiment, adversary A submits a set of identities (with attributes and policies) {(uidj , ⃗xj , fj )}nj=1 for parties (P1 , · · · , Pn ). For each j ∈ [n], the challenger sets up anonymous credential and long-term secret attribute/policy keys for party Pj . A also submits two challenge clients Ci∗0 , Ci∗1 ∈ C, where Ci∗0 possesses (uid∗i0 , ⃗x∗i0 , fi∗0 ) and Ci∗1 has (uid∗i1 , ⃗x∗i1 , fi∗1 ). It is required that ⃗x∗i0 = ⃗x∗i1 and fi∗0 = fi∗1 . Note that the challenge tuples (uid∗i0 , ⃗x∗i0 , fi∗0 ) and (uid∗i1 , ⃗x∗i1 , fi∗1 ) are distinct from {(uidj , ⃗xj , fj )}nj=1 . Then, the challenger associates
27
(uid∗ib , ⃗x∗ib , fi∗b ) with PT , and executes the setup algorithm for PT that is defined in the protocol. Protocol Execution. Adversary A is allowed to issue the following queries. • Reg(U ρ , uidρU , ⃗xρU , fUρ ): If U ρ ∈ (P1 , · · · , Pn ) with user identifier uidρU , attributes ⃗xρU and policy fUρ is unregistered, it executes as the protocol definition, and returns the result to A. • Send, RevealBroadcast, RevealState, RevealKey and Corrupt are the same as the definition in “Service Discovery Security” model. • Challenge. In Expb , the instance Ci∗b with (uid∗ib , ⃗x∗ib , fi∗b ) executes PriSrv by following the protocol steps. The restriction is that A does not issue any of the following queries: - Reg query on (uid∗i0 , ⃗x∗i0 , fi∗0 ) or (uid∗i1 , ⃗x∗i1 , fi∗1 ) or any service provider whose attributes and policy satisfy (⃗x∗i0 , fi∗0 ) or (⃗x∗i1 , fi∗1 ); - RevealState or RevealKey query on any (PT , bid, sid) or its matching session; - Corrupt query on Ci∗0 or Ci∗1 or any service provider whose attributes and policy satisfy (⃗x∗i0 , fi∗0 ) or (⃗x∗i1 , fi∗1 ). - If A associates a policy (⃗xSj , fSj ) with a service provider session (Sjδ , bid, sid), it is required that either both Ci∗0 and Ci∗1 satisfy the policy, or neither of them satisfies the policy. In any above query, if the query causes an instance to accept or termination, these outputs will be shown to A. Output phase. A outputs a guess b′ ∈ {0, 1} for b.
oracle, then PriSrv is a secure service discovery protocol and satisfies bilateral anonymity. We utilize three lemmas to prove the security of PriSrv in Theorem 7.1, which demonstrate PriSrv is secure and private in extended Canetti-Krawzyk key-exchange model (Lemma C.1), and it provides anonymity for both the client and the server (Lemma C.2 and Lemma C.3). The security proof of PriSrv requires the underlying ACME scheme should be CCA secure. There are standard (and efficient) generic approaches (e.g., the Fujisaki-Okamoto transformation [59]) to transform our ACME construction to achieve CCA security. Lemma C.1. (Service discovery privacy with bilateral control.) Suppose that DDH assumption holds on G1 and G2 , ACME is secure, MAC is unforgeable, and H is random oracle, then PriSrv is a secure service discovery protocol with bilateral control. Proof. Following similar proofs for key-exchange and service discovery protocols proposed in [32], [33], [38], [5], we assume selective security in the adversary’s choice of the test session, i.e., at the beginning of the security game, the adversary commits to the following: • The test session (α∗ , bid, sid, ⃗xα∗ , fα∗ ). • The peer’s identity, attributes and policy (β ∗ , ⃗xβ ∗ , fβ ∗ ). • Whether α∗ is the initializer or the responder of the test session. Note that a selective security proof can be converted to an adaptive one at a security loss that increases polynomially in the number of parties and the number of sessions the adversary initiates. We define a simulator S = S(A). On input the number of parties n and an adversary A, the simulator S simulates a series of security games for the protocol. In the selective security setting, the adversary begins by committing to a test session (α∗ , bid, sid, ⃗xα∗ , fα∗ ), the peer (β ∗ , ⃗xβ ∗ , fβ ∗ ) in the test session, and whether α∗ was the initiator or the responder in the test session. Then, S initializes the n parties by generating anonymous credential, attribute decryption key and policy decryption key for each of them. When A activates a party, S executes as in the protocol on behalf of the parties, and outputs the corresponding messages to A as well as the public outputs of each session. Description of the simulator. We introduce several variants of S, which are generally denoted as S. The simulator S behaves similarly to S except the following differences. (1) At the beginning of the simulation, the simulator chooses $ four exponents z, x1 , x2 , y ← − Z∗p and a random session key SSK. The specification of the keys will determine the different variants of the simulator S. (2) In the selective security model, the adversary A commits to a test session (α∗ , bid, sid, ⃗xα∗ , fα∗ ), the peer (β ∗ , ⃗xβ ∗ , fβ ∗ ), and the role of α∗ in the session at the beginning of the experiment. Let S ∈ {α∗ , β ∗ } denote the server A commits to for a test session, and C ∈ {α∗ , β ∗ } the client to which it commits.
A service discovery protocol achieves client anonymity if no adversary can distinguish the experiments Exp0 and Exp1 with non-negligible advantage greater than 1/2, which captures the property that no active adversary can distinguish communications with a client Ci∗0 from those with a client Ci∗1 . Here is the formal definition. Definition C.2 Let Succanon-C PriSrv (A) denote the event that A outputs a bit b′ = b. PriSrv satisfies client anonymity if for any PPT adversary A, there exists a negligible function ν such def anon-C that Advanon-C PriSrv (A) = 2Pr[SuccPriSrv (A)] − 1 ≤ ν(λ). The security game for service provider anonymity is similar to that for the client anonymity, except for exchanging their roles and restriction that the adversary is not allowed to query Revealbroadcast for the challenge sessions. The concrete security model is omitted for brevity. Definition C.3 Let Succanon-S PriSrv (A) denote the event that A outputs a bit b′ = b. PriSrv satisfies service provider anonymity if for any PPT adversary A, there exists a negligible def anon-S function ν such that Advanon-S PriSrv (A) = 2Pr[SuccPriSrv (A)] − 1 ≤ ν(λ). Definition C.4 PriSrv satisfies bilateral anonymity if it achieves client anonymity and service provider anonymity. (2) Security Proof of PriSrv Theorem 7.1. Suppose that the DDH assumption holds, ACME is secure, MAC is unforgeable, and H is a random
28
The simulator S simulates the execution of the PriSrv security game as S, except for the following differences. • If the adversary A activates S to initiate the broadcast (S, bid, ⃗xS , fS ), the simulator uses z as the semi-static DH exponent in the broadcast. • If the adversary A activates C to initiate the session (C, bid, sid, ⃗xC , fC ), the simulator uses x1 , x2 as the ephemeral DH exponents of C. • If the adversary A activates S as a responder to the session (S, C, bid, sid, ⃗xS , fS , ⃗xC , fC ), the simulator uses y as the ephemeral DH exponent of S. • It uses SSK in place of SSK whenever the shares (hz , g x1 , hx2 , g y ) are used to derive the session key (that is, y z when the simulator needs to compute H(X 1 , X 2 )). (3) At the end of the protocol, A outputs a bit b ∈ {0, 1}. The simulator S outputs the same bit. The security proof contains two cases, depending on whether A compromises the server’s semi-static broadcast secret or not. We say the adversary is admissible as long as it is not the situation that both the server’s epheral DH secret and the server’s semi-static broadcast DH secret are compromised, which is similar to the security analysis in [60]. Specifically, the two cases in our proof are given below. • Case 1: A neither issues a RevealBroadcast query on (S, bid, ⃗xS , fS ) nor corrupt S before the broadcast session expires (i.e., the semi-static broadcast DH secret is not compromised). • Case 2: A does not issue a RevealState query on (S, bid, ⃗xS , fS ). For each case, we define a series of hybrid games to show that each consecutive pair of hybrid games are computationally indistinguishable. Before the formal case analysis, we prove the following proposition. Proposition C.1. Suppose a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ) completes with a peer (β ∗ , ⃗xβ ∗ , fβ ∗ ). Assume that neither α∗ nor β ∗ has been corrupted before the completion of (α∗ , bid, sid, ⃗xα∗ , fα∗ ). Then, assuming that ACME has authenticity, the following statements hold: (1) If α∗ is the client and β ∗ is the server, then A initiated a broadcast (β ∗ , bid, ⃗xβ ∗ , fβ ∗ ) and α∗ must have been activated to initiate a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ) with the broadcast (out) (out) message if and only if fα∗ (⃗xβ ∗ ) = 1 ∧ fβ ∗ (⃗xα∗ ) = 1. ∗ ∗ (2) If α is the server and β is the client, the session (β ∗ , bid, sid, ⃗xβ ∗ , fβ ∗ ) cannot complete with a peer (out) session (α′∗ , bid, sid, ⃗xα′∗ , fα′∗ ) such that fα′∗ (⃗xβ ∗ ) ̸= (out) 1 ∨ fβ ∗ (⃗xα′∗ ) ̸= 1.
and verifies the authenticity of CTB for further communication. Since (α∗ , bid, sid, ⃗xα∗ , fα∗ ) completes with β ∗ , it (out) (out) must be the case that fα∗ (⃗xβ ∗ ) = 1 ∧ fβ ∗ (⃗xα∗ ) = 1. Since β ∗ has not been corrupted before the completion with (α∗ , bid, sid, ⃗xα∗ , fα∗ ), it generates at most one broadcast ciphertext containing bid. Thus, if (α∗ , bid, sid, ⃗xα∗ , fα∗ ) completes with β ∗ , it must have been initialized with broadcast message output by (β ∗ , bid, ⃗xβ ∗ , fβ ∗ ) since this is the only message that contains a valid ACME ciphertext from β ∗ with the broadcast identifier bid. Otherwise, A can be used to break the authenticity of ACME. (2) If β ∗ is activated to initiate the session (β ∗ , bid, ⃗xβ ∗ , fβ ∗ ) and the session completes with a peer α′∗ (out) (out) with (⃗xα′∗ , fα′∗ ) such that fα′∗ (⃗xβ ∗ ) ̸= 1 ∨ fβ ∗ (⃗xα′∗ ) ̸= 1. In this case, an honest β ∗ would never succeed to decrypt the broadcast ciphertext and then generate the ACME ciphertext CTβ ∗ . Therefore, any adversary that can cause (α∗ , bid, sid, ⃗xα∗ , fα∗ ) to complete with peer β ∗ , and have (β ∗ , bid, sid, ⃗xβ ∗ , fβ ∗ ) complete with peer α′∗ can break the authenticity of ACME. Next we consider the two possible cases and prove that the adversary’s advantage in both cases is negligible. Case 1: A does not compromise the broadcast session and z is not disclosed. In this case, the security proof relies on the server’s broadcast secret for the privacy of the session. A series of hybrid games are defined. • Hybrid H0 : This game is the same as a real interaction with the PriSrv protocol. A random bit b ∈ {0, 1} is selected. When b = 1, the real session key is returned as a response to the TestSession query. Otherwise, a random key from the key space is returned as the session key. • Hybrid H1 : This game is the same as H0 , except that Z x2 = X2z is replaced by a random value in group G2 . • Hybrid H2 : This game is the same as H1 , except that S̄ also aborts if the session (β ∗ , bid, sid, ⃗xβ ∗ , fβ ∗ ) does not match (α∗ , bid, sid, ⃗xα∗ , fα∗ ). • Hybrid H3 : This game is the same as H2 , except that SSK is replaced by a random number from the secret session key space. In the following, we show that each consecutive pair of hybrid games described above are computationally indistinguishable. Claim C.1. Hybrids H0 and H1 are computationally indistinguishable if the DDH assumption holds in group G2 . Proof. Let (α∗ , bid, sid, ⃗xα∗ , fα∗ ) be the session and (β ∗ , ⃗xβ ∗ , fβ ∗ ) be the peer that the adversary commits to at the beginning of the experiment. By definition, this means that (α∗ , β ∗ , bid, sid, ⃗xα∗ , fα∗ , ⃗xβ ∗ , fβ ∗ ) is the public output of the test session. Let A be a distinguisher between H0 and H1 . We use A to build a DDH adversary B as below. B is given a DDH challenge tuple (hb1 , hb2 , hγ2 ) over group G2 , where γ2 = b1 b2 or γ2 is a random number from Z∗p .
Proof. We prove the two cases separately. (1) When α∗ is activated to initialize a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ) with a broadcast message (bid′ , CTB ), it decrypts the broadcast ciphertext utilizing its private attribute and policy (out) keys. If the decryption fails, it indicates that fα′∗ (⃗xβ ∗ ) ̸= (out) 1 ∨ fβ ∗ (⃗xα′∗ ) ̸= 1. Otherwise, α∗ is an intended client to obtain the broadcast messages, who checks whether bid′ = bid
29
At the beginning of the simulation, B generates anonymous credential, private attribute and policy key (in the same manner as the simulator S) for each of the n parties. B begins the simulation of the security game for A. In the following, we use C ∈ {α∗ , β ∗ } to denote the client and S ∈ {α∗ , β ∗ } to denote the server in the test session. • Server broadcast queries. If the adversary activates a server S to initiate the test broadcast session (S, bid, ⃗xs , fs ), the simulator uses hb1 from the DDH challenge instance as the semi-static DH share in the broadcast message. For other broadcast queries, B selects a random DH exponent z to constructs the broadcast ciphertext exactly as in the real protocol. • Client initialization queries. When A activates a party α∗ to initiate a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ), if (α∗ , bid, sid, ⃗xα∗ , fα∗ ) ̸= (C, bid, sid, ⃗xc , fc ), B selects a random DH exponent and generates the message exactly as in the real scheme. Otherwise, if (α∗ , bid, sid, ⃗xα∗ , fα∗ ) = (C, bid, sid, ⃗xc , fc ), B sets hb2 from the DDH challenge instance to be the DH share X2 = hx2 in its message. The other computation steps follow the real experiment. • Server response queries. When A activates a server S to respond to a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ), B selects a random DH exponent y and generates the message exactly as in the real scheme. • Client finish queries. When a client receives a response message for session (α∗ , bid, sid, ⃗xα∗ , fα∗ ), if (α∗ , bid, sid, ⃗xα∗ , fα∗ ) ̸= (C, bid, sid, ⃗xc , fc ), B constructs the outputs as in the real scheme (this is feasible since B selects the client’s ephemeral DH share in this case). Otherwise, if (α∗ , bid, sid, ⃗xα∗ , fα∗ ) = (C, bid, sid, ⃗xc , fc ), B runs the other computation steps following the real experiment except that it sets SSK = H(X1y , hγ2 ), where X1y = Y x1 (generated by B) and hγ2 is from the DDH challenge instance. • RevealState and RevealKey queries. These are handled exactly as in H0 . • Corrupt queries. If A corrupts a party U , B sends the anonymous credential and private attribute/policy keys of U to A, as well as ephemeral secrets in the local storage of U . B perfectly simulates H0 if γ2 = b1 b2 , and B simulates H1 if γ2 is a random number. Then, if A can distinguish H0 from H1 , B can succeed in the DDH game on G2 with the same advantage.
A against the PriSrv protocol in the security game, we build an adversary B0 as follows. Adversary B0 answers all queries made by A using its own oracles. If A outputs an instance (α∗ , bid, sid, ⃗xα∗ , fα∗ ) that has no matching session, B0 aborts without any output. Otherwise, adversary B0 outputs (α∗ , bid, sid, ⃗xα∗ , fα∗ ) in the TestSession query, and returns to adversary A the response it receives. Let E denote the event that the instance (α∗ , bid, sid, ⃗xα∗ , fα∗ ) in the TestSession query output by adversary A does not have a matching session. If event E does not happen, B0 and adversary A are the same. Otherwise, we can construct an encryption-aided forger B1 who aims to produce a forgery MAC.MAC(K ∗ , M ) for a secret key K ∗ that is encapsulated in an ACME ciphertext CT∗ [58]. B1 is given pp, mpk and access to an oracle OIssue (·) which creates anonymous credential for user U , an oracle ODKGen (·) which creates attribute decryption key for ⃗x, an oracle OPolGen (·) which creates policy decryption key for f , an oracle ODec (·) which decrypts ciphertexts. Assume that adversary A performs at most qI activations of parties with an incoming message. Forger B1 randomly chooses ℓ ← [1, qI ] and simulates the security game for adversary A in the following cases. • If adversary A does not make a TestSession query with an activation of α∗ , forger B1 aborts. • If β ∗ is not the matching session of α∗ , forger B1 aborts. • If (α∗ , bid, sid, ⃗xα∗ , fα∗ ) is not the ℓ-th activation, forger B1 aborts. • If adversary A makes a Corrupt query on β ∗ or any part(out) (out) ner β with (⃗xβ , fβ ) satisfying fα∗ (⃗xβ ) = 1 ∧ fβ (⃗xα∗ ) = 1, before the session has expired, forger B1 aborts. • In the ℓ-th activation, B1 uses (DK⃗xα∗ , DKfα∗ ) to derive the broadcast message M SG∗B ← ACME.Dec(DK⃗xα∗ , DKfα∗ , CTβ ∗ ), where M SGB = (bid, Z, · · · , Kα∗ ). B1 generates the ephemeral DH shares (X1 , X2 ) for (α∗ , bid, sid, ⃗xα∗ , fα∗ ). B1 sets Mα∗ = (“α∗ → ∗ β ”, bid, sid, X1 , X2 , Z) and creates the tag σα∗ using Kα∗ on Mα∗ . B1 asks its challenger to return CTα∗ = ACME.Enc(credα∗ , ⃗xα∗ , fα∗ , M SGα∗ ) where M SGα∗ = (K ∗ , Mα∗ ) and K ∗ is chosen by B1 ’s challenger. Forger B1 sets CT∗ = CTα∗ . • If adversary A sends (CT, · · · ) to β ∗ where CT ̸= CT∗ , forger B1 makes a query to its decryption oracle ODec (·) on input CT, and proceeds as usual after getting the response from ODec (·). • If adversary A sends (CT∗ , M ) to β ∗ , forger B1 issues a query to its oracle OMAC to generate the tag σ ∗ with regards to K ∗ and M . The restriction is that M does not contain (bid, sid) of challenge session. • When adversary A sends the tag σ ∗ to the ℓ-th activation, forger B1 outputs the tag σ ∗ and the corresponding message as its forgery. Therefore, we have ϵ = P r[B1 succeeds] ≥ q1I P r[E].
Claim C.2. Hybrids H1 and H2 are computationally indistinguishable if the ACME algorithm is private and MAC is unforgeable. Proof. If an adversary A outputs a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ) in the TestSession query, there must be a partner instance (β ∗ , bid, sid, ⃗xβ ∗ , fβ ∗ ). Otherwise, we can make use of the adversary A to break the privacy of ACME or the unforgeability of MAC. We define an adversary B0 such that in the TestSession query B0 outputs a session (α∗ , bid, sid, ⃗xα∗ , fα∗ ), which has a matching session (β ∗ , bid, sid, ⃗xβ ∗ , fβ ∗ ). Given an adversary
30
Given a forger B1 , we now construct another adversary B2 against the anonymous credential matchmaking encryption scheme ACME in the security game, which is given the public parameter pp and has access to the attribute/policy decryption key generation and decryption oracle. When forger B1 asks for a challenger with input participant α∗ , adversary B2 randomly chooses two keys K0 and K1 , and asks its challenger with inputs (K0 , Mα∗ ) and (K1 , Mα∗ ). After obtaining the challenge CT∗ (with respect to K0 or K1 ), adversary B2 sets CT∗ as forger B1 ’s challenge. When forger B1 makes a query with a ciphertext CT ̸= CT∗ , adversary B2 makes a decryption query with input CT to its challenger. When forger B1 makes an OMAC query on a message M , adversary B2 returns MAC.MAC(K0 , M ) to forger B1 . Finally, if forger B1 successfully makes a forgery MAC.MAC(K0 , Mα∗ ), B2 outputs 0 meaning that CT∗ is an encryption of (K0 , Mα∗ ). Otherwise, if forger B1 fails to make a forgery, adversary B2 outputs 1, meaning that CT∗ is an encryption of (K1 , Mα∗ ). Hence, we have
• Hybrid H2 : This game is the same as in Case 1. • Hybrid H3 : This game is the same as in Case 1. It suffices to prove that the hybrids H0 and H1 are computationally indistinguishable. Claim C.4. Hybrids H0 and H1 are computationally indistinguishable if the DDH assumption holds in group G1 . Proof. The proof follows the same arguments as in Case 1 except that the DDH tuple (hz , hx2 , hγ2 ) on group G2 used in the proof of the Case 1 is replaced by the DDH tuple (g y , g x1 , g γ1 ) on group G1 . Integrating the above proofs for the two cases, we conclude that PriSrv realizes secure service discovery with bilateral control. Lemma C.2. (Client anonymity) PriSrv protocol satisfies client anonymity assuming the ACME scheme is private. Proof. We define a simulator S that simulates the challenger for the adversary A in the client anonymity security game. At the beginning of the simulation, A submits a set of identities (with attributes and policies) {(uidj , ⃗xj , fj )}nj=1 for parties (P1 , · · · , Pn ), and two challenge tuples (uid∗i0 , ⃗x∗i0 , fi∗0 ) and (uid∗i1 , ⃗x∗i1 , fi∗1 ), which are distinct from {(uidj , ⃗xj , fj )}nj=1 . We define a series of hybrid experiments. During the protocol execution, the simulator responds to the adversary’s queries according to these hybrid experiments. • Hybrid H1 : This is the real experiment Exp0 , where the simulator responds to adversary’s queries as described in Exp0 . • Hybrid H2 : This is the real experiment Exp1 .
(λ) AdvACME B2 =
P r[B2 outputs 0|b = 0] · P r[b = 0] + P r[B2 outputs 0|b = 1] · P r[b = 1] −
1 2
1 P r[B1 succeeds|b = 0] + 2 1 1 1 (1 − P r[B1 succeeds|b = 1]) − 2 2 2 1 = (P r[B1 succeeds|b = 0] − P r[B1 succeeds|b = 1]) 2 1 (ϵ − AdvMAC = B1 (λ)). 2 The last line of the above equation is concluded from when b = 0, forger B1 is in the forgery game, and when b = 1, forger B1 is in the random message attack game. Therefore, Hybrids H1 and H2 are computationally indistinguishable. =
Next, we prove that Hybrids H1 and H2 are computationally indistinguishable if the underlying ACME is private. Let q be an upper bound on the number of sessions, where A activates the test party PT as the responder (the client). We define a sequence of q + 1 hybrid experiments H1,0 , · · · , H1,q , where hybrid experiment H1,i is defined as follows: H1,i is same as H1 except that for the first i times when PT is activated as the responder (the client) of the broadcast ciphertext, PT is instantiated using the credential of (uid∗i1 , ⃗x∗i1 , fi∗1 ) for generating the response message. In all subsequent times, PT PT is instantiated using the credential of (uid∗i0 , ⃗x∗i0 , fi∗0 ). By construction, H1 ≡ H1,0 and H2 ≡ H1,q . We prove that for all i ∈ [q], hybrid H1,i−1 and H1,i are computationally indistinguishable assuming that the ACME scheme is private. Suppose A is able to distinguish H1,i−1 from H1,i , we use A to construct an adversary B against ACME in the security game. First, B is given the public parameters mpk of the ACME scheme. Then, B begins running A and obtains set of identities (with attributes and policies) {(uidj , ⃗xj , fj )}nj=1 for parties (P1 , · · · , Pn ), and two challenge tuples (uid∗i0 , ⃗x∗i0 , fi∗0 ) and (uid∗i1 , ⃗x∗i1 , fi∗1 ), which are distinct from {(uidj , ⃗xj , fj )}nj=1 .
Claim C.3. Hybrids H2 and H3 are computationally indistinguishable when the hash function H is a random oracle. Proof. Since in H2 we replaced Z x2 with a random value hγ2 from G2 , the probability that the adversary can make a hash query H(Y x1 , hγ2 ) is negligible. When (Y x1 , hγ2 ) is not queried, its hash value (i.e., the session key) is an unknown random value to the adversary, same as in H3 . The claim follows. Case 2: A has compromised z. In this case, we rely on the ephemeral DH share y of the server to ensure confidentiality of the session key. The security proof is quite similar to that of Case 1. The hybrid experiments are described below. • Hybrid H0 : This game is the same as a real interaction with the PriSrv protocol. • Hybrid H1 : This game is the same as in Case 1, except that Y x1 = X1y is replaced by a random value in group G1 .
31
B simulates the setup procedure in H1 by creating anonymous credentials, private attribute/policy keys for each party. Then, B sends mpk to A and begins simulating the protocol execution experiment for A. • Server broadcast queries. These are handled exactly as in H1 and H2 . • Client initialization queries. When A activates a client C to respond to a broadcast (S, bid, ⃗xs , fs ), if C ̸= PT , algorithm B simulates the response as in the real scheme. If C = PT , then let ℓ be the number of times A has activated PT to respond to a broadcast. B queries the ACME key generation or decryption oracle to obtain a decrypted broadcast message, and performs the checks on the decrypted broadcast message. B then proceeds as below. - If ℓ < i − 1, B constructs the response message as described in H2 , that is using (uid∗i1 , ⃗x∗i1 , fi∗1 ) in client’s response message. - If ℓ ≥ i, B constructs the response message as described in H1 , that is using (uid∗i0 , ⃗x∗i0 , fi∗0 ) in client’s response message.
then it has correctly simulated the client’s response queries according to the specification of hybrid H1,i for A. Hence, if the ACME is private, then H1 and H2 are computationally indistinguishable. Therefore, we have proved that PriSrv satisfies client anonymity. Lemma C.3. (Server anonymity) PriSrv protocol satisfies server anonymity assuming the ACME scheme is private. Proof. This proof is similar to the proof of client anonymity (in Lemma F.7) except that PT initiates broadcast as a server in the simulation. We omit the details of the proof for briefty.
$
- If ℓ = i−1, B selects random DH shares x1 , x2 ← − Z∗p , and ∗ ∗ generates a MAC key Ks . It submits (credi0 , ⃗xi0 , fi0 , M SGc ) and (credi1 , ⃗x∗i1 , fi∗1 , M SGc ) to the ACME challenger, where M SGc = (Ks , Mc ), Mc = (“C → S”, bid, sid, X1 = g x1 , X2 = hx2 , Z), credib is the anonymous credential for uid∗ib , b ∈ {0, 1}. Then, it receives a ciphertext CT c from the challenger. B runs MAC scheme to obtain σc from Kc and Mc . B outputs the response (bid, sid, σc , CT c ). • Server response queries. When A delivers a message to server, B responds as below. - B parses A’s message as (bid, sid, σc , CTc ). - If B is in the pre-challenge phase, or if B is in the postchallenge phase, and either CTc ̸= CT c or B is allowed to obtain the decryption key for CTc , B queries the ACME decryption or key generation oracle to decrypt CTc . If B is in the post-challenge phase and CTc = CT c , B simulates the response by using the M SGc = (Ks , Mc ) it has chosen for generating CT c . • Client finish queries. These are handled exactly as in H1 and H2 . They are independent of the ACME parameters. • RevealState and RevealKey queries. These are handled exactly as in H1 and H2 . • Corrupt queries. If A corrupts a party P ̸= PT , B queries the ACME challenger for the private attribute/policy keys for P , and returns the keys as well as ephemeral secrets in the local storage of P to A. At the end of the game, A outputs a guess for whether it is in H1 or H2 . B forwards the guess to its security game. To complete the proof, we show that B is an elegible ACME adversary in the privacy security game since B does not need to request its challenger to decrypt the challenge ciphertext or return secret keys that can decrypt the challenge ciphertext. By construction, if B receives an encryption of (uid∗i0 , ⃗x∗i0 , fi∗0 ) from the ACME challenger, then it has correctly simulated the client’s response queries according to the specification of hybrid H1,i−1 for A. If it receives an encryption of (uid∗i1 , ⃗x∗i1 , fi∗1 ) from the ACME challenger,
32