1 Introduction↩︎

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 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]–[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]–[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 dual-layer architecture, PriSrv builds a private-enhanced service discovery protocol with high usability.

1.1 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.

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.

1.2 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.

\(\bullet\) 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.

\(\bullet\) 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.

\(\bullet\) 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.

\(\bullet\) 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.

\(\bullet\) Formal Security Proofs. We provide formal security proofs for the security and privacy properties of PriSrv in 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.

\(\bullet\) 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.

1.2mm

2 Related Work↩︎

A variety of protocols have been developed for service discover in network environments. As shown in Table 1, 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-the-middle (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 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 multi-show 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 deep-learning-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 Wi-attack 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 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 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.

3 Preliminaries↩︎

3.1 Notation and Bilinear Pairing↩︎

Let \(\vec{x}\) denote the full attribute set, \(\vec{x}^{(in)}\) the private attributes for an inner layer and \(\vec{x}^{(out)}\) the public attributes for an outer layer, where \(\vec{x}^{(in)},\vec{x}^{(out)}\subseteq\vec{x}\). Let \(f:\{0,1\}^n\rightarrow\{0,1\}\) denote the policy; \(f(\vec{x})=1\) denote \(\vec{x}\) satisfying \(f\), and \(f(\vec{x})=0\) denote \(\vec{x}\) not satisfying \(f\).

Let \(s\xleftarrow{\$}S\) denote \(s\) sampled uniformly at random from a set \(S\); \(\mathbb{N}\) denote the natural number; \(\lambda\in\mathbb{N}\) denote the security parameter; \([n_1,n_2]\) denote \(\{n_1,\cdots,n_2\}\); PPT denote probabilistic polynomial time; \(\mathbb{Z}_p\) represent the group of integers modulo \(p\), and \(\mathbb{Z}_p^*=\mathbb{Z}_p\backslash\{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 \(\mathcal{BG}=(G_1,G_2,G_T,e,p)\), where there is no efficiently computable isomophism between \(G_1\) and \(G_2\). Let \(g_1\in G_1\), \(g_2\in G_2\) and \(g_T=e(g_1,g_2)\in G_T\) be the respective generators. For a matrix \(\boldsymbol{A}\) over \(\mathbb{Z}_p\), define \([\boldsymbol{A}]_1:=g_1^{\boldsymbol{A}}\), \([\boldsymbol{A}]_2:=g_2^{\boldsymbol{A}}\), \([\boldsymbol{A}]_T:=g_T^{\boldsymbol{A}}\), where exponentiation is carried out component-wise.

3.2 Assumptions↩︎

\(\quad\)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 \(\mathcal{A}\), the advantage function \(\textsf{Adv}_{\mathcal{A}}^{\text{DL}}(\lambda):=Pr[\mathcal{A}(g,g^a)=a]\) is negligible, where \(a \xleftarrow{\$}\mathbb{Z}_p^*\).

Definition 3.2. (Decisional Diffie-Hellman (DDH) Assumption). Let \(g\) be a generator of \(G\) and \(\mathcal{T}=(g,g^a,g^b)\in G^3\), where \(a,b\xleftarrow{\$}\mathbb{Z}_p^*\). DDH assumption holds if for all PPT adversary \(\mathcal{A}\), the advantage \(|Pr[\mathcal{A}(\mathcal{T},g^{ab})=1]-Pr[\mathcal{A}(\mathcal{T},g^{c})=1]|\) is negligible, where \(c\xleftarrow{\$}\mathbb{Z}_p^*\).

Definition 3.3. (Matrix DDH (MDDH\(_{k}\)) Assumption) [26]. Let \(\ell>k\geq1\), \(d\geq 1\). MDDH\(_{k}\) assumption holds if for all PPT adversary \(\mathcal{A}\), the advantage \(\textsf{Adv}_{\mathcal{A}}^{\text{MDDH}_{k}}(\lambda):=\) \(|Pr[\mathcal{A}([\boldsymbol{M}]_1,[\boldsymbol{MS}]_1)=1]-Pr[\mathcal{A}([\boldsymbol{M}]_1,[\boldsymbol{U}]_1)=1]|\) is negligible, where \(\boldsymbol{M}\xleftarrow{\$}\mathbb{Z}_p^{\ell\times k}\), \(\boldsymbol{S}\xleftarrow{\$}\mathbb{Z}_p^{k\times d}\) and \(\boldsymbol{U}\xleftarrow{\$}\mathbb{Z}_p^{\ell\times d}\).

3.3 Linear Secret Sharing for Monotone Boolean Formulae↩︎

The information-theoretic linear secret sharing for monotone Boolean formulae [26], [27] is described below.

\(\underline{\textsf{share}(f,\mu)}\). Input: A formula \(f:\{0,1\}^n\rightarrow\{0,1\}\) of size \(m\) (i.e., the number of edges in \(f\) is \(m\)), and a secret \(\mu\in\mathbb{Z}_p\). 1) For each non-output wire \(j=1,\cdots,m-1\), select \(\hat{\mu}_j\xleftarrow{\$}\mathbb{Z}_p\). For the output wire, set \(\hat{\mu}_m:=\mu\). 2) For each outgoing wire \(j\) from input node \(i\), add \(\mu_j:=\hat{\mu}_j\) to the output set of shares and set \(\rho(j):=i\). 3) For each AND gate \(g\) with input wires \(a\), \(b\) and output wire \(c\), add \(\mu_{c_a}:=\hat{\mu}_c+\hat{\mu}_a+\hat{\mu}_b\in\mathbb{Z}_p\) to the output set of shares and set \(\rho(c):=0\). 4) For each OR gate \(g\) with input wires \(a\), \(b\) and output wire \(c\), add \(\mu_{c_a}:=\hat{\mu}_c+\hat{\mu}_a\in\mathbb{Z}_p\) and \(\mu_{c_b}:=\hat{\mu}_c+\hat{\mu}_b\in\mathbb{Z}_p\) to the output set of shares and set \(\rho(c_a):=0\) and \(\rho(c_b):=0\). 5) Output \((\{\mu_j\}_{j\in[\hat{m}]},\rho)\).

\(\underline{\textsf{reconstruct}(f,x,\{\mu_j\}_{\rho(j)=0\vee x_{\rho(j)}=1})}\). Input: A formula \(f\), \(\vec{x}\in\{0,1\}^n\), and \(\{\mu_j\}_{\rho(j)=0\vee x_{\rho(j)}=1}\). From the leaves of the formula to the root, calculate the output wire value \(\hat{\mu}_c\) at each node. 1) Given \(\hat{\mu}_a,\hat{\mu}_b\) associated with the input wires \(a\) and \(b\) of an AND gate, compute \(\hat{\mu}_c=\mu_c-\hat{\mu}_a-\hat{\mu}_b\). 2) Given \(\hat{\mu}_a\) (or \(\hat{\mu}_b\)) associated with the input wires \(a\) (or \(b\)) of an OR gate, compute \(\hat{\mu}_c=\mu_{c_a}-\hat{\mu}_a\) (or \(\hat{\mu}_c=\mu_{c_b}-\hat{\mu}_b\)). 3) Output \(\mu=\hat{\mu}_m\).

3.4 \(\textsf{NC}^1\) Circuit and Monotone Formulae↩︎

We define \(\textsf{NC}^1\) circuit and monotone Boolean formulae following Kowalczyk’s [26] and Katsumata’s [27] works. A monotone Boolean formula \(f:\{0,1\}^n\rightarrow\{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,\cdots,m\), and each gate node is defined by a tuple \((g,a_g,b_g,c_g)\), where \(g:\{0,1\}^2\rightarrow\{0,1\}\) is either AND or OR, \(a_g,b_g\) are the incoming wires, \(c_g\) is the outgoing wire and \(a_g,b_g< c_g\). 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 \(\textsf{NC}^1\) circuits.

4 PriSrv’s Overview↩︎

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 \(\S\)1.1, we design a dual-layer 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]–[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 (\(\textsf{snd}\)) and receiver (\(\textsf{rcv}\)) possess a set of attributes \(\vec{x}_\textsf{snd}\) and \(\vec{x}_\textsf{rcv}\), respectively. The sender is able to specify an authorization policy \(f_{\textsf{snd}}\) for the receiver’s attributes \(\vec{x}_{\textsf{rcv}}\) 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: \(\vec{x}_s\)=(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 select a set of public attributes \(\vec{x}^{(out)}_s\)=(device type, vendor, domain name) to be used in the outer layer, and a set of private attributes \(\vec{x}^{(in)}_s\)=(IP address) to be used in the inner layer. The client device is associated with another set of attributes: \(\vec{x}_c\)=(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 client selects a set of public attributes \(\vec{x}^{(out)}_c\)=(device type, OS, department) for outer layer matching, and a set of private attributes \(\vec{x}^{(in)}_c\)=(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 \[\begin{align} f_s=\big(&&\text{Device Type = ``Smart phone} \vee \text{Laptop"}\\ &\bigwedge& \text{OS = ``Android} \vee \text{iOS} \vee \text{Windows"}\\ &\bigwedge& \text{Department = ``A} \vee \text{B"}\big). \end{align}\] The client device specifies a connection policy as \[\begin{align} f_c=\big(&&\text{Device Type = ``TV" }\bigwedge \text{Vendor = ``C} \vee \text{D"}\\ &\bigwedge& \text{Domain Name = ``*.XYZ.COM"}\big). \end{align}\]

The screen mirroring service can be discovered by the client if and only if \(f_s(\vec{x}^{(out)}_c)=1\wedge f_c(\vec{x}^{(out)}_s)=1\), which indicates 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 \(\S\)1.1.

- 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: (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 [sec:Appendix:PriSrv].

5 Fast Anonymous Credential↩︎

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.

5.1 Syntax of Anonymous Credential↩︎

Anonymous credential (AC) is formally defined by the following PPT algorithms [34], [35].

\(\bullet\) \(\textsf{Setup}(1^{\lambda}, 1^{n})\rightarrow \textsf{pp}\): On input a security parameter \(\lambda\) and a function parameter \(1^n\), it outputs public parameter \(\textsf{pp}\), which is an implicit input to all the other algorithms.

\(\bullet\) \(\textsf{CredKeyGen}(\textsf{pp})\rightarrow(\textsf{pk},\textsf{sk})\): On input \(\textsf{pp}\), this algorithm creates credential issuer’s public/secret keys \(\textsf{pk}\)/\(\textsf{sk}\), where \(\textsf{pk}\) is an implicit input to the algorithms below.

\(\bullet\) \(\textsf{UserKeyGen}(\textsf{pp})\rightarrow(\textsf{upk},\textsf{usk})\): On input \(\textsf{pp}\), the algorithm generates user’s public key \(\textsf{upk}\) and secret key \(\textsf{usk}\).

\(\bullet\) \(\left<\textsf{Issue.I}(\textsf{sk},\textsf{upk})\rightleftarrows\textsf{Issue.U}(uid,\vec{x},\textsf{usk})\right>\rightarrow \textsf{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 \(\vec{x}\) and a secret key \(\textsf{usk}\). The credential issuer runs the protocol by inputting \(\textsf{sk}\) and \(\textsf{upk}\). The issuer hands over a credential \(\textsf{cred}\) to user via secure channel.

\(\bullet\) \(\textsf{Show}(uid,\{x_i\}_{i\in\mathcal{I}},\textsf{cred},\textsf{usk},m)\rightarrow \textsf{tok}\): On input \(uid\), an attribute subset \(\{x_i\}_{i\in\mathcal{I}}\subseteq\vec{x}\) (\(\mathcal{I}\subseteq [1,n]\)), \(\textsf{cred}\), \(\textsf{usk}\) and a message \(m\), it outputs an authentication token \(\textsf{tok}\).

\(\bullet\) \(\textsf{Verify}(\textsf{tok},m)\rightarrow b\in\{0,1\}\). On input \(\textsf{tok}\) and \(m\), it outputs \(b=1\) if \(\textsf{tok}\) is valid; otherwise, it outputs \(b=0\).

Following the security definitions in [34], [35], the correctness, unforgeability, anonymity and unlinkability of AC are defined, which are shown in Appendix 9.1.

5.2 Construction of FAC↩︎

Our construction of FAC is given below.

\(\bullet\) \(\textsf{Setup}(1^{\lambda},1^n)\rightarrow \textsf{pp}\): Let \(\lambda\) be the security parameter, and \(n\) the attribute number in the system. Run \(\mathbb{G}=(p,G_1,G_2,G_T,e)\xleftarrow{\$}\mathsf{GGen}(1^{\lambda})\), and output \(\textsf{pp}=(g,h,n)\), where \(g,h\) are the generators of \(G_1\), \(G_2\), respectively.

\(\bullet\) \(\textsf{CredKeyGen}(\textsf{pp})\rightarrow(\textsf{pk},\textsf{sk})\): The issuer samples \(\tau,y_i\xleftarrow{\$}\mathbb{Z}_p^*\), computes \(W\leftarrow g^{\tau}\), \(X_i\leftarrow h^{y_i}\), \(Y_i\leftarrow g^{y_i}\) for \(i\in[0,n+1]\), and \(Z_{i,j}=g^{y_i\cdot y_j}\) for \(0\leq i\neq j\leq n+1\). Then, it outputs secret key \(\textsf{sk}=(\tau,\{y_i\}_{i\in[0,n+1]})\) and public key \(\textsf{pk}\leftarrow(W,\{X_i,Y_{i}\}_{i\in[0,n+1]},\{Z_{i,j}\}_{0\leq i\neq j\leq n+1})\).

\(\bullet\) \(\textsf{UserKeyGen}(\textsf{pp})\rightarrow(\textsf{upk},\textsf{usk})\): The user with \(uid\) samples \(\textsf{usk}\xleftarrow{\$}\mathbb{Z}_p^*\), computes \(\textsf{upk}\leftarrow h^{\textsf{usk}}\), and creates a signature proof of knowledge \(\pi_1\) as \(\textsf{SPK}\{\textsf{usk}:\textsf{upk}= h^{\textsf{usk}}\}.\) The issuer registers \(\textsf{upk}\) if \(\textsf{Verify}_{\textsf{SPK}}(\textsf{upk},\pi_1)=1\) holds.

\(\bullet\) \(\left<\textsf{Issue.I}(\textsf{sk},\textsf{upk})\rightleftarrows\textsf{Issue.U}(uid,\vec{x},\textsf{usk})\right>\rightarrow\textsf{cred}\). The secure channel between issuer and user can be established by standard protocols, such as TLS.

(1) User sends \(uid\) and attributes \(\vec{x}=\{x_i\}_{i\in[1,n]}\) to issuer.

(2) The issuer samples \(r\overset{\$}{\leftarrow}\mathbb{Z}_p^*\) to calculate \(\textsf{cred}\leftarrow (\sigma_1,\sigma_2)\), where \[\sigma_1\leftarrow h^r,\sigma_2\leftarrow \textsf{upk}^{r\cdot y_0}\cdot h^{r(\tau+\sum_{i=1}^ny_ix_i+y_{n+1}\cdot uid)}.\]

(3) The user accepts the credential \(\textsf{cred}\) if the following equation holds \[e(W\cdot Y_0^{\textsf{usk}}\cdot Y_{n+1}^{uid}\prod\nolimits_{i=1}^nY_i^{x_i},\sigma_1)=e(g,\sigma_2).\]

\(\bullet\) \(\textsf{Show}(uid,\{x_i\}_{i\in\mathcal{I}},\textsf{cred},\textsf{usk},m)\rightarrow \textsf{tok}\): The user generates a token on selected attribute subset \(\{x_i\}_{i\in\mathcal{I}}\), \(\mathcal{I}\subseteq [1,n]\). Select \(t_1,t_2\overset{\$}{\leftarrow}\mathbb{Z}_p^*\) to compute \[T_1=g^{t_1}\prod_{j\in[1,n]\backslash\mathcal{I}}Y_j^{x_j},~~T_2=(\prod_{i\in\mathcal{I}'}Y_i)^{t_1}\prod_{i\in\mathcal{I}',j\in[1,n]\backslash\mathcal{I}}Z_{i,j}^{x_j},\] \(\bar{\sigma}_1=\sigma_1^{t_2}\), \(\bar{\sigma}_2=\sigma_2^{t_2}\bar{\sigma}_1^{t_1}\), and create \(\pi_2\) as \[\textsf{SPK}\left\{(\textsf{usk},uid):\begin{matrix}\bar{\sigma}_1=\sigma_1^{t_2},\bar{\sigma}_2=\sigma_2^{t_2}\bar{\sigma}_1^{t_1},\sigma_1= h^r,\\ \sigma_2= (h^{\textsf{usk}})^{r\cdot y_0}h^{r(\tau+\sum\limits_{i=1}^ny_ix_i+y_{n+1}\cdot uid)} \end{matrix} \right\}(m),\] where \(\mathcal{I}'=\mathcal{I}\cup\{0,n+1\}\). The token is \[\textsf{tok}\leftarrow(\{x_i\}_{i\in\mathcal{I}},T_1,T_2,\bar{\sigma}_1,\bar{\sigma}_2,\pi_2).\]

\(\bullet\) \(\textsf{Verify}(\mathsf{tok},m)\rightarrow b\in\{0,1\}\). The algorithm outputs \(b=1\) if \(\textsf{Verify}_{\textsf{SPK}}(\textsf{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 \(\pi_1\):

Prove: Prover selects \(\widetilde{\textsf{usk}}\overset{\$}{\leftarrow}\mathbb{Z}_p^*\) and computes \(\gamma\leftarrow h^{\widetilde{\textsf{usk}}}\), \(c\leftarrow H(\textsf{upk},\gamma)\), \(\overline{\textsf{usk}}=\widetilde{\textsf{usk}}-c\cdot \textsf{usk} \mod p\). Return \(\pi_1\leftarrow(c,\gamma,\overline{\textsf{usk}})\).

Verify: Given \(\textsf{upk}\) and SPK \(\pi_1\), the verifier checks \(c\overset{?}{=}H(\textsf{upk},\gamma)\), \(\gamma\overset{?}{=}h^{\overline{\textsf{usk}}}\textsf{upk}^{c}\). It outputs 1 if these equations hold, and 0 otherwise.

The SPK \(\pi_2\):

Prove: Prover selects \(\widetilde{uid},\widetilde{\textsf{usk}}\overset{\$}{\leftarrow}\mathbb{Z}_p^*\) and computes \(\Lambda\leftarrow e(Y_0^{\widetilde{\textsf{usk}}}Y_{n+1}^{\widetilde{uid}},\bar{\sigma}_1)\), \(c\leftarrow H(m,\{x_i\}_{i\in\mathcal{I}},\Lambda,T_1,T_2,\bar{\sigma}_1,\bar{\sigma}_2)\), \(\overline{uid}\leftarrow \widetilde{uid}-c\cdot uid \mod p\), \(\overline{\textsf{usk}}\leftarrow \widetilde{\textsf{usk}}-c\cdot \textsf{usk} \mod p\). Set \(\pi_2\leftarrow(c,\overline{uid},\overline{\textsf{usk}},\Lambda)\), and return \(\textsf{tok}\leftarrow(\{x_i\}_{i\in\mathcal{I}},T_1,T_2,\bar{\sigma}_1,\bar{\sigma}_2,\pi_2)\).

Verify: Given \(\textsf{tok}\), the verifier checks \(c\overset{?}{=}H(m,\{x_i\}_{i\in\mathcal{I}},\Lambda,\) \(T_1,T_2,\bar{\sigma}_1,\bar{\sigma}_2)\), \(e(Y_0^{\overline{\textsf{usk}}}Y_{n+1}^{\overline{uid}},\bar{\sigma}_1)^{-1}\cdot\Lambda\overset{?}{=}[e(g,\bar{\sigma}_2)\cdot\Gamma]^{c}\), \(e(T_1,\) \(\prod\nolimits_{i\in\mathcal{I}'}X_i)\overset{?}{=}e(T_2,h)\), where \(\Gamma=e(W\cdot T_1\cdot\prod\nolimits_{i\in\mathcal{I}}Y_i^{x_i},\bar{\sigma}_1)^{-1}\). It outputs 1 if these equations hold, and 0 otherwise.

Our fast anonymous credential (FAC) scheme has the following advantages: 1) FAC offers a non-interactive \(\textsf{Show}\leftrightarrows \textsf{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 [35], which is one of the initial frameworks for generating constant-size redactable signatures on attributes \(\vec{x}=(x_1,\cdots,x_n)\). FAC generates an anonymous credential \(\textsf{cred}\) based on the URS scheme [35]. When a request is made to verify the authenticity of a subset of attributes \(\{x_i\}_{i\in\mathcal{I}}\subseteq\vec{x}\), the \(\textsf{Show}\) algorithm in FAC performs the following steps: it derives an authentication token \(\textsf{tok}\) from the anonymous credential \(\textsf{cred}\), and then produces a signature proof of knowledge (SPK) for the authentication token. The \(\textsf{Verify}\) algorithm in FAC is responsible for checking the validity of \(\textsf{tok}\). The correctness proof of FAC is shown in Appendix 9.1.

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 9.1.

6 Anonymous 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.

6.1 Design Intuition↩︎

Matchmaking Encryption (ME) is a natural starting point to construct ACME. However, the conception of ME [15] that 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 highly-usable 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 \(\textsf{cred}_{\textsf{snd}}\) from a credential issuer for all its attributes \(\vec{x}_{\textsf{snd}}\). 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 \(\mathcal{FAC}.\textsf{Show}\) from a message \(M\) and selected attributes (including public and private attributes) based on the received credential \(\textsf{cred}_{\textsf{snd}}\). In the outer layer, sender snd encrypts the authentication token and the message \(M\) using an authentication policy \(f_{\textsf{snd}}\) (specified by \(\textsf{snd}\) for \(\textsf{rcv}\)) and the sender’s selected public attributes. Then, sender \(\textsf{snd}\) transmits the ciphertext to receiver \(\textsf{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 \(\mathcal{FAC}.\textsf{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 \(\mathcal{FAC}.\textsf{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.

6.2 Syntax of ACME↩︎

Anonymous credential-based matchmaking encryption (ACME) is formally defined below, and the correctness of ACME is defined in Appendix 9.2.

\(\bullet\) \(\textsf{Setup}(1^{\lambda},1^n)\): On input a security parameter \(1^{\lambda}\) and a function parameter \(1^n\), this algorithm outputs the master public/secret keys \(\textsf{mpk}\)/\(\textsf{msk}\). Note that \(\textsf{mpk}\) is implicit input in all the following algorithms.

\(\bullet\) \(\textsf{CredKeyGen}(\textsf{mpk})\rightarrow(\textsf{pk},\textsf{sk})\): On input \(\textsf{mpk}\), this algorithm creates credential issuer’s public key \(\textsf{pk}\) and secret key \(\textsf{sk}\). \(\textsf{pk}\) is an implicit input to the following algorithms.

\(\bullet\) \(\textsf{UserKeyGen}(\textsf{mpk})\rightarrow(\textsf{upk},\textsf{usk})\): On input \(\textsf{mpk}\), the algorithm generates user’s public key \(\textsf{upk}\) and secret key \(\textsf{usk}\).

\(\bullet\) \(\left<\textsf{Issue.I}(\textsf{sk},\textsf{upk})\rightleftarrows\textsf{Issue.U}(uid,\vec{x},\textsf{usk})\right>\rightarrow \textsf{cred}\). The issuer inputs \(\textsf{sk}\), \(\textsf{upk}\) and the user inputs \(uid\), \(\textsf{usk}\), full attributes \(\vec{x}\). The issuer interacts with user to generate a credential \(\textsf{cred}\) for the user.

\(\bullet\) \(\textsf{DKGen}(\mathsf{msk},\vec{x}_{\textsf{rcv}})\): On input \(\mathsf{msk}\) and attributes \(\vec{x}_{\textsf{rcv}}\), this algorithm outputs an attribute decryption key \(\textsf{DK}_{\vec{x}_{\textsf{rcv}}}\).

\(\bullet\) \(\textsf{PolGen}(\mathsf{msk},f_{\textsf{rcv}})\): On input \(\mathsf{msk}\) and policy \(f_{\textsf{rcv}}\), this algorithm outputs a policy decryption key \(\textsf{DK}_{f_{\textsf{rcv}}}\).

\(\bullet\) \(\mathsf{Enc}(\textsf{cred}_{\textsf{snd}},\vec{x}_{\textsf{snd}},f_{\textsf{snd}},M)\): On input \(\textsf{cred}_{\textsf{snd}}\), full attributes \(\vec{x}_{\textsf{snd}}\), policy \(f_{\textsf{snd}}\) and message \(M\) as input, the sender selects a set of private attributes \(\vec{x}_{\textsf{snd}}^{(in)}\) for an inner layer and a set of public attributes \(\vec{x}_{\textsf{snd}}^{(out)}\) for an outer layer from \(\vec{x}_{\textsf{snd}}\). It firstly generates a token \(\textsf{tok}_{\textsf{snd}}\) for \(\vec{x}_{\textsf{snd}}^{(in)}\), \(\vec{x}_{\textsf{snd}}^{(out)}\) and message \(M\). Then, it encrypts \((M,\textsf{tok}_{\textsf{snd}})\) using the public attributes \(\vec{x}_{\textsf{snd}}^{(out)}\) and policy \(f_{\textsf{snd}}\), and outputs a ciphertext \(\textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}}\).

\(\bullet\) \(\mathsf{Dec}(\textsf{DK}_{\vec{x}_{\textsf{rcv}}},\textsf{DK}_{f_{\textsf{rcv}}},\textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}})\): On input \(\textsf{DK}_{\vec{x}_{\textsf{rcv}}}\), \(\textsf{DK}_{f_{\textsf{rcv}}}\) and \(\textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}}\), the receiver recovers \((M,\textsf{tok}_{\textsf{snd}})\) iff \(f_{\textsf{snd}}(\vec{x}_{\textsf{rcv}}^{(out)})=1\) and \(f_{\textsf{rcv}}(\vec{x}_{\textsf{snd}}^{(out)})=1\); otherwise, it outputs \(\bot\). If the above step succeeds, the receiver verifies \(\textsf{tok}_{\textsf{snd}}\) for \(\vec{x}_{\textsf{snd}}^{(in)}\cup\vec{x}_{\textsf{snd}}^{(out)}\) and \(M\). It outputs the message \(M\) if the token is valid; otherwise, it outputs \(\bot\).

Remark. In encryption algorithm, the authentication token \(\textsf{tok}_{\textsf{snd}}\) 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 9.2.

6.3 Construction of ACME↩︎

FAC in \(\S\)5 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 CP-ABE (resp. KP-ABE) functions as attribute decryption key (resp. policy decryption key) produced by the \(\textsf{DKGen}\) (resp. \(\textsf{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 candidates because they are in the dual form with common parameters and support Boolean formulae (equivalent to \(\textsf{NC}^1\) circuits¹). 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 \(\textsf{NC}^1\)). 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 \(\mathcal{FAC}\), a symmetric encryption scheme \(\mathcal{SE}=(\textsf{SGen},\textsf{SEnc},\textsf{SDec})\) with key space \(\mathcal{K}\), and a hash function \(H:\{0,1\}^*\rightarrow\mathcal{K}\).

\(\mathsf{Setup}(1^{\lambda},1^{n})\): Run \(\mathbb{G}=(p,G_1,G_2,G_T,e)\xleftarrow{\$}\mathsf{GGen}(1^{\lambda})\). Let \(g,h\) be the generators of \(G_1\), \(G_2\), respectively. Run \(\mathcal{FAC}.\textsf{Setup}(1^{\lambda}, 1^{n})\) to get \(\textsf{pp}\). Sample \(\mathbf{A}\xleftarrow{\$}\mathbb{Z}_p^{k\times 2k}\), \(\mathbf{B}\xleftarrow{\$}\mathbb{Z}_p^{k\times k}\), \(\boldsymbol{U}_0,\boldsymbol{W}_i\xleftarrow{\$}\mathbb{Z}_p^{2k\times k}\) for \(i\in[n]\), \(\boldsymbol{v}\xleftarrow{\$}\mathbb{Z}_p^{2k}\), output \[\begin{align} &\mathsf{msk}=(\boldsymbol{v},\boldsymbol{B},\boldsymbol{U}_0,\boldsymbol{W}_1,\cdots,\boldsymbol{W}_n),\\ &\mathsf{mpk}=(\textsf{pp},[\boldsymbol{A}]_1,[\boldsymbol{AU}_0]_1,[\boldsymbol{AW}_1]_1,\cdots,[\boldsymbol{AW}_n]_1,e([\boldsymbol{A}]_1,[\boldsymbol{v}]_2)). \end{align}\]

\(\textsf{CredKeyGen}(\textsf{mpk})\rightarrow(\textsf{pk},\textsf{sk})\): This algorithm executes \(\mathcal{FAC}.\textsf{CredKeyGen}\) to generate issuer’s \(\textsf{pk}\) and \(\textsf{sk}\).

\(\textsf{UserKeyGen}(\textsf{mpk})\rightarrow(\textsf{upk},\textsf{usk})\): This algorithm executes \(\mathcal{FAC}.\textsf{UserKeyGen}\) to generate user’s \(\textsf{upk}\) and \(\textsf{usk}\).

\(\left<\textsf{Issue.I}(\textsf{sk},\textsf{upk})\rightleftarrows\textsf{Issue.U}(uid,\vec{x},\textsf{usk})\right>\rightarrow \textsf{cred}\). This algorithm executes \(\mathcal{FAC}.\textsf{Issue}\) to create user’s credential \(\textsf{cred}\).

\(\mathsf{DKGen}(\mathsf{msk},\vec{x}_{\textsf{rcv}})\): To generate an attribute decryption key for receiver’s attributes \(\vec{x}_{\textsf{rcv}}\), it samples \(\boldsymbol{r}\xleftarrow{\$}\mathbb{Z}_p^{k}\) and outputs \(\textsf{DK}_{\vec{x}_{\textsf{rcv}}}=(\textsf{dk}_1,\textsf{dk}_2,\textsf{dk}_{3})\): \[\textsf{dk}_1=[\boldsymbol{v}+\boldsymbol{U}_0\boldsymbol{B}\boldsymbol{r}]_2,\textsf{dk}_2=[\boldsymbol{B}\boldsymbol{r}]_2,\textsf{dk}_{3}=[\sum\nolimits_{i:x_{r,i}^{(out)}=1}\boldsymbol{W}_{i}\boldsymbol{B}\boldsymbol{r}]_2.\]

\(\mathsf{PolGen}(\mathsf{msk},f_{\textsf{rcv}})\): To generate a policy decryption key for receiver’s policy \(f_{\textsf{rcv}}\), this algorithm samples \((\{\boldsymbol{v}_j\}_{j\in[\hat{m}_r]},\rho_r)\xleftarrow{\$}\textsf{share}(f_{\textsf{rcv}},\boldsymbol{v})\), \(\boldsymbol{r}_j\xleftarrow{\$}\mathbb{Z}_p^{k}\) and outputs \(\textsf{DK}_{f_{\textsf{rcv}}}=(\{\textsf{dk}_j,\textsf{dk}_{\rho_r(j),j},\{\textsf{dk}_{i,j}\}_{i\in[n]\backslash\{\rho_r(j)\}}\}_{j\in[\hat{m}_r]}):\) \[\textsf{dk}_j=[\boldsymbol{r}_j]_2,\textsf{dk}_{\rho_r(j),j}=[\boldsymbol{v}_j+\boldsymbol{W}_{\rho_r(j)}\boldsymbol{r}_j]_2,\textsf{dk}_{i,j}=[\boldsymbol{W}_{i}\boldsymbol{r}_j]_2,\] where \(\boldsymbol{W}_0=\boldsymbol{0}\), \(\hat{m}_r\) is the number of shares for receiver’s policy, and \(\rho_r\) is a mapping from the indices of the shares to the indices of receiver’s public attributes². For \(\rho_r(j)=0\), we have \([n]\backslash\{\rho_r(j)\}=[n]\).

\(\mathsf{Enc}(\textsf{cred}_{\textsf{snd}},\vec{x}_{\textsf{snd}}, f_{\textsf{snd}},M)\): The sender selects the private attributes \(\vec{x}_{\textsf{snd}}^{(in)}\) for inner layer and public attributes \(\vec{x}_{\textsf{snd}}^{(out)}\) for outer layer from \(\vec{x}_{\textsf{snd}}\). Then, it runs \(\mathcal{FAC}.\textsf{Show}\) to obtain \(\textsf{tok}_{\textsf{snd}}\) for \(\vec{x}_{\textsf{snd}}^{(in)}\), \(\vec{x}_{\textsf{snd}}^{(out)}\) and \(M\in\{0,1\}^*\). Next, it encrypts \((M,\textsf{tok}_{\textsf{snd}})\) using the public attributes \(\vec{x}_{\textsf{snd}}^{(out)}\) and policy \(f_{\textsf{snd}}\) as follows.

The sender samples \(\widetilde{\boldsymbol{s}},\boldsymbol{s},\boldsymbol{s}_j\xleftarrow{\$}\mathbb{Z}_p^{k}\), \((\{\boldsymbol{u}_j^{\top}\}_{j\in[\hat{m}_s]},\rho_s)\xleftarrow{\$}\textsf{share}(f_{\textsf{snd}},\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0)\), \(K\in G_T\), and compute \(\textsf{CT}_{\vec{x}_{\textsf{snd}}, f_{\textsf{snd}}}=(\textsf{ct}_M,\textsf{ct}_0,\textsf{ct}_1',\textsf{ct}_2',\textsf{ct}_1,\{\widetilde{\textsf{ct}}_{j},\textsf{ct}_{\rho_s(j),j},\{\textsf{ct}_{i,j}\}_{i\in[n]\backslash\{\rho_s(j)\}}\}_{j\in[\hat{m}_s]}):\) \[\begin{align} &&\textsf{ct}_M=\mathcal{SE}.\textsf{SEnc}(H(K),(M,\textsf{tok}_{\textsf{snd}})),\\ &&\textsf{ct}_0=e([\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}+\boldsymbol{s}^{\top}\boldsymbol{A}]_1,[\boldsymbol{v}]_2)\cdot K,\\ &&\textsf{ct}_1'=[\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}]_1,~~~\textsf{ct}_2'=\big[\widetilde{\boldsymbol{s}}^{\top}\sum\nolimits_{i:x_{s,i}^{(out)}=1}\boldsymbol{AW}_i\big]_1,\\ &&\textsf{ct}_1=[\boldsymbol{s}^{\top}\boldsymbol{A}]_1,~~~\widetilde{\textsf{ct}}_{j}=[\boldsymbol{s}_j^{\top}\boldsymbol{A}]_1,\\ &&\textsf{ct}_{\rho_s(j),j}=\big[\boldsymbol{u}_j^{\top}+\boldsymbol{s}_j^{\top}\boldsymbol{AW}_{\rho_s(j)}\big]_1,~~\textsf{ct}_{i,j}=\big[\boldsymbol{s}_j^{\top}\boldsymbol{AW}_i\big]_1, \end{align}\] where \(\boldsymbol{W}_0=\boldsymbol{0}\), \(x_{s,i}^{(out)}\) is sender’s \(i\)-th public attribute for outer layer, \(\hat{m}_s\) is the number of shares for sender’s policy, and \(\rho_s\) is a mapping from the indices of the shares to the indices of sender’s public attributes.

\(\mathsf{Dec}(\textsf{DK}_{\vec{x}_{\textsf{rcv}}},\textsf{DK}_{ f_{\textsf{rcv}}},\textsf{CT}_{\vec{x}_{\textsf{snd}}, f_{\textsf{snd}}})\): The receiver recovers \((M,\textsf{tok}_{\textsf{snd}})\) using \((\textsf{DK}_{\vec{x}_{\textsf{rcv}}},\textsf{DK}_{ f_{\textsf{rcv}}})\) as follows. It compute \(\omega_j,\mu_j\) such that \(\boldsymbol{v}=\sum\nolimits_{j\in\mathcal{S}_r}\omega_j\boldsymbol{v}_j\), \(\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0=\sum\nolimits_{j\in\mathcal{S}_s}\mu_j\boldsymbol{u}_j^{\top},\) and calculates \[\begin{align} \small K&=&\textsf{ct}_0\cdot \frac{e\big(\textsf{ct}_2',\prod\nolimits_{j\in\mathcal{S}_r}\textsf{dk}_j^{\omega_j}\big)\cdot}{e\big(\textsf{ct}_1',\prod\nolimits_{j\in\mathcal{S}_r}\big(\prod_{i:x_{s,i}^{(out)}=1}\textsf{dk}_{i,j}\big)^{\omega_j}\big)}\\ &&\cdot \frac{e(\prod\nolimits_{j\in\mathcal{S}_s}(\prod\nolimits_{i:x_{r,i}^{(out)}=1}\textsf{ct}_{i,j})^{\mu_j},\textsf{dk}_2)}{e(\textsf{ct}_1,\textsf{dk}_1)e(\prod\nolimits_{j\in\mathcal{S}_s}\widetilde{\textsf{ct}}_{j}^{\mu_j},\textsf{dk}_3)}, \end{align}\] where \(\mathcal{S}_r=\{j:\rho_r(j)=0\vee x_{s,\rho_r(j)}^{(out)}=1\}\), \(\mathcal{S}_s=\{j:\rho_s(j)=0\vee x_{r,\rho_s(j)}^{(out)}=1\}\) and \(x_{r,i}^{(out)}\) is receiver’s \(i\)-th public attribute for outer layer.

If \(f_{\textsf{snd}}(\vec{x}_{\textsf{rcv}}^{(out)})=0 \vee f_{\textsf{rcv}}(\vec{x}_{\textsf{snd}}^{(out)})=0\), it outputs \(\bot\); otherwise, it recovers \((M,\textsf{tok}_{\textsf{snd}})\leftarrow\mathcal{SE}.\textsf{SDec}(H(K),\textsf{ct}_M)\). Then, the receiver runs \(\mathcal{FAC}.\textsf{Verify}(\textsf{tok}_{\textsf{snd}},M)\) to verify \(\textsf{tok}_{\textsf{snd}}\) for \(\vec{x}_{\textsf{snd}}^{(in)}\cup\vec{x}_{\textsf{snd}}^{(out)}\) and \(M\). It outputs the message \(M\) if the token is valid; otherwise, it outputs \(\bot\).

The correctness of ACME scheme is analyzed below.

Denote \(\mathcal{S}_s=\{j:\rho_s(j)=0\vee x_{r,\rho_s(j)}^{(out)}=1\}\) and \(\mathcal{S}_r=\{j:\rho_r(j)=0\vee x_{s,\rho_r(j)}^{(out)}=1\}\). The correctness of ACME relies on the fact that \(\prod\nolimits_{j\in\mathcal{S}_r}\textsf{dk}_j^{\omega_j}=\prod\nolimits_{j\in\mathcal{S}_r}[\boldsymbol{r}_j]_2^{\omega_j}=[\hat{\boldsymbol{r}}]_2\), \[\begin{align} &&\prod\limits_{j\in\mathcal{S}_r}\big(\prod\limits_{i:x_{s,i}^{(out)}=1}\textsf{dk}_{i,j}\big)^{\omega_j}=[\boldsymbol{v}+\sum\limits_{i:x_{s,i}^{(out)}=1}\boldsymbol{W}_{i}\hat{\boldsymbol{r}}]_2, \end{align}\] where \(\hat{\boldsymbol{r}}=\sum_{j\in\mathcal{S}_r}\omega_j\boldsymbol{r}_j\). Also we have, \[\begin{align} &&e(\textsf{ct}_1,\textsf{dk}_1)=[\textsf{s}^{\top}\boldsymbol{A}\boldsymbol{v}+\textsf{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0\boldsymbol{B}\boldsymbol{r}]_{T},\\ &&\prod\nolimits_{j\in\mathcal{S}_s}\widetilde{\textsf{ct}}_{j}^{\mu_j}=\prod\nolimits_{j\in\mathcal{S}_s}[\boldsymbol{s}_j^{\top}\boldsymbol{A}]_1^{\mu_j}=[\hat{\boldsymbol{s}}^{\top}\boldsymbol{A}]_1,\\\\ &&\prod\limits_{j\in\mathcal{S}_s}\big(\prod\limits_{i:x_{r,i}^{(out)}=1}\textsf{ct}_{i,j}\big)^{\mu_j}=[\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0+\hat{\boldsymbol{s}}^{\top}\sum\limits_{i:x_{r,i}^{(out)}=1}\boldsymbol{A}\boldsymbol{W}_{i}]_1, \end{align}\] where \(\hat{\boldsymbol{s}}^{\top}=\sum\nolimits_{j\in\mathcal{S}_s}\mu_j\boldsymbol{s}_j^{\top}\).

Therefore, for all \(f_{\textsf{rcv}},\vec{x}_{\textsf{snd}}\) such that \(f_{\textsf{rcv}}(\vec{x}_{\textsf{snd}}^{(out)})=1\), we have: \[\begin{align} && \frac{e\big(\textsf{ct}_2',\prod\nolimits_{j\in\mathcal{S}_r}\textsf{dk}_j^{\omega_j}\big)\cdot}{e\big(\textsf{ct}_1',\prod\nolimits_{j\in\mathcal{S}_r}\big(\prod_{i:x_{s,i}^{(out)}=1}\textsf{dk}_{i,j}\big)^{\omega_j}\big)}\\ &=& \frac{e\big(\big[\widetilde{\boldsymbol{s}}^{\top}\sum_{i:x_{s,i}^{(out)}=1}\boldsymbol{AW}_i\big]_1,[\hat{\boldsymbol{r}}]_2)}{e\big([\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}]_1,[\boldsymbol{v}+\sum_{i:x_{s,i}^{(out)}=1}\boldsymbol{W}_{i}\hat{\boldsymbol{r}}]_2\big)}\\ &=&\frac{[\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}\hat{\boldsymbol{r}}\sum_{i:x_{s,i}^{(out)}=1}\boldsymbol{W}_i\big]_T}{[\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}\boldsymbol{v}+\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}\hat{\boldsymbol{r}}\sum_{i:x_{s,i}^{(out)}=1}\boldsymbol{W}_{i}]_T}=([\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}\boldsymbol{v}]_T)^{-1}. \end{align}\] where \(\hat{\boldsymbol{r}}=\sum_{j\in\mathcal{S}_r}\omega_j\boldsymbol{r}_j\).

For all \(f_{\textsf{snd}},\vec{x}_{\textsf{rcv}}\) such that \(f_{\textsf{snd}}(\vec{x}_{\textsf{rcv}}^{(out)})=1\), we have: \[\begin{align} &&\frac{e(\prod\nolimits_{j\in\mathcal{S}_s}(\prod\nolimits_{i:x_{r,i}^{(out)}=1}\textsf{ct}_{i,j})^{\mu_j},\textsf{dk}_2)}{e(\textsf{ct}_1,\textsf{dk}_1)\cdot e(\prod\nolimits_{j\in\mathcal{S}_s}\widetilde{\textsf{ct}}_{j}^{\mu_j},\textsf{dk}_3)}\\ &=&\frac{e([\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0+\hat{\boldsymbol{s}}^{\top}\sum\nolimits_{i:x_{r,i}^{(out)}=1}\boldsymbol{A}\boldsymbol{W}_{i}]_1,[\boldsymbol{B}\boldsymbol{r}]_2)}{[\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{v}+\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0\boldsymbol{B}\boldsymbol{r}]_T\cdot e([\hat{\boldsymbol{s}}^{\top}\boldsymbol{A}]_1,[\sum\nolimits_{i:x_{r,i}^{(out)}=1}\boldsymbol{W}_{i}\boldsymbol{B}\boldsymbol{r}]_2)}\\ &=&\frac{[\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0\boldsymbol{B}\boldsymbol{r}]_T}{[\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{v}+\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{U}_0\boldsymbol{B}\boldsymbol{r}]_T}=([\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{v}]_T)^{-1}. \end{align}\]

Theorem 6.2. The ACME scheme achieves privacy, authenticity, anonymity and unlinkability if the \(MDDH_k\) assumption holds and the underlying FAC is secure.

The proof of Theorem 6.2 is shown in Appendix 9.2.

6.4 Comparison of ME Schemes↩︎

Mathmaking encryption (ME) protects data confidentiality with bilateral control for both senders and receivers in communications. The existing instantiations of ME include an identity-based scheme (IBME) [15] proposed in CRYPTO’19 and a security enhanced version [31] in Asiacrypt’22, but they do not support fine-grained access control. Table 2 compares our ACME with IBME [15], [31]. Since IBME simply sets \(\vec{x}_{\textsf{snd}}=\textsf{snd}\), \(f_{\textsf{snd}}=\textsf{rcv}\) and \(\vec{x}_{\textsf{rcv}}=\textsf{rcv}\), \(f_{\textsf{rcv}}=\textsf{snd}\), it requires pre-registration pairing between service providers and clients. On the contrary, ACME relies on bilateral policy matching for service discovery and thus it does not need pre-registration pairing. Furthermore, ACME supports expressive policy (i.e., Boolean formulae equivalent to \(\textsf{NC}^1\) circuit), while IBME is constrained to equality policy. On the other hand, the expressive policy in ACME is public to enable fast service discovery, while the equality policy is hidden from the public in IBME.

0.5mm

7 PriSrv: Privacy-enhanced Fast Service Discovery↩︎

7.1 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 \(\mathcal{MAC}=(\textsf{Setup},\textsf{KeyGen},\textsf{MAC},\textsf{Verify})\) be a message authentication code (MAC) scheme [34], [36], [37], and \(H:\{0,1\}^*\rightarrow\mathcal{K}\) be a hash function, where \(\mathcal{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 \(f_s\) to be satisfied by \(C\). \(S\) selects an ephemeral Diffie-Hellman (DH) exponent \(z\xleftarrow{\$} \mathbb{Z}_p^*\) and calculates \(Z\leftarrow h^z\). \(S\) also runs \(K_c\leftarrow\mathcal{MAC}.\textsf{KeyGen}(1^{\lambda})\) to generate an MAC key. \(S\) generates the broadcast message \(MSG_B=\{bid||Z||\) \(Service_{Type}||Service_{Par}||K_c\}\) including the broadcast identifier, service type and parameters as well as a MAC key for the client. Next, \(S\) encrypts \(MSG_B\) to a broadcast ciphertext \(\textsf{CT}_B=\textsf{CT}_{\vec{x}_s, f_s}\leftarrow\mathcal{ACME}.\textsf{Enc}(\textsf{cred}_s,\vec{x}_s, f_s,MSG_B).\) Then, the broadcast identifier \(bid\) and service ciphertext \(\textsf{CT}_B\) 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 \(SSK_{c,s}\).

(1) To discover the private service, \(C\) firstly checks whether \(\vec{x}_c^{(out)}\) satisfies with the anonounced access policy \(f_s\) of \(S\), i.e. \(f_s(\vec{x}_c^{(out)})\overset{?}{=}1\). \(C\) quickly filters out mismatched services without decryption when \(f_s(\vec{x}_c^{(out)})=0\). Otherwise, \(C\) attempts to decrypt \(\textsf{CT}_B\) using its attribute and policy decryption keys \((\textsf{DK}_{\vec{x}_c},\textsf{DK}_{f_c})\). If the decryption fails which means \(f_{s}(\vec{x}_{c}^{(out)})=0 \vee f_{c}(\vec{x}_{s}^{(out)})=0\), then \(C\) aborts. Otherwise, \(C\) responds to the broadcast message by executing \(\mathcal{ACME}.\textsf{Dec}\) to recover \(MSG_B\). Next, \(C\) selects ephemeral DH exponents \(x_1,x_2\xleftarrow{\$} \mathbb{Z}_p^*\) and calculates \(X_1=g^{x_1}\), \(X_2=h^{x_2}\). \(C\) computes a MAC key \(K_s\) and an authentication tag \(\sigma_c\) of \(M_c=(``C\rightarrow S",bid,sid,X_1,X_2,Z)\) using \(K_c\) from \(MSG_B\), where \(``C\rightarrow S"\) denotes the message direction. Then, \(C\) defines a policy \(f_c\) 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 \(\mathcal{ACME}.\textsf{Enc}\) to compute \(\textsf{CT}_{c}=\textsf{CT}_{\vec{x}_c,f_c}\) and sends it to \(S\).

(2) \(S\) authenticates \(C\)’s service access request and computes a secret session key. \(S\) executes \(\mathcal{ACME}.\textsf{Dec}\) to recover \(MSG_c\). \(S\) aborts the protocol if decryption fails. Next, \(S\) verifies \(\sigma_c\) and selects DH exponent \(y\xleftarrow{\$} \mathbb{Z}_p^*\) to calculate \(Y\leftarrow g^y\). \(S\) sets \(M_s=(``S\rightarrow C",bid,sid,X_1,X_2,Y,Z)\) and generates a tag \(\sigma_s\leftarrow\mathcal{MAC}.\textsf{MAC}(K_s,M_s)\) using \(K_s\) from \(MSG_c\). Then, \(S\) computes a secret session key \(SSK_{c,s}\leftarrow H(X_1^{y},X_2^{z})\) and sends \((M_s,\sigma_s)\) to \(C\).

(3) Receiving the message, \(C\) checks the validity of \(\sigma_s\). If it is valid, \(C\) computes \(SSK_{c,s}\leftarrow H(Y^{x_1},Z^{x_2})\) using the secret values \((x_1,x_2)\). Therefore, \(C\) and \(S\) derive the same session key \(SSK_{c,s}\) since \(X_1^{y}=Y^{x_1}=g^{x_1y}\in G_1\) and \(X_2^{z}=Z^{x_2}=h^{x_2z}\in G_2\).

The following theorem shows the security of PriSrv.

Theorem 7.1. Suppose that the DDH assumption holds, \(\mathcal{ACME}\) is secure, \(\mathcal{MAC}\) is unforgeable, and \(H\) is a random oracle, then \(\textsf{PriSrv}\) is a secure service discovery protocol and satisfies bilateral anonymity.

The proof of Theorem 7.1 is shown in Appendix [sec:Appendix:PriSrv].

7.2 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) [38] and Verifiable Credentials (VC) [39] specifications to regulate verifiable and decentralized digital identities. Decentralized Identity Foundation (DIF) [40] developed a set of standards to support a decentralized identity ecosystem [41]. Technology giants, such as IBM [42] and Microsoft [43], also provide flexible identity governance and administration services for credentials. CanDID proposed in [44] 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 [38] and VC [39] have regulated the process for inteoperable usage of credentials, which is also supported by DIF [40]. Backed by Microsoft, Google, Yahoo, IBM, VeriSign, PayPal, and Facebook, the OpenID Foundation³ 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 [45]–[47]. It can also be achieved by the combination of ElGamal encryption and Schnorr proofs [48], or \(n\)-times unlinkable proofs [49]. PriSrv may incorporate the above techniques to realize credential revocation.

7.3 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.

7.3.1 Privacy Enhanced mDNS and BLE↩︎

PriSrv can be integrated in the Vanadium⁴ 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 [50], [51] and BLE [3]. mDNS can work in conjunction with DNS Service Discovery (DNS-SD), a companion zero-configuration networking technique specified separately in RFC 6763⁵. 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,\textsf{CT}_B)\), which takes 531996 bytes in communications on BN256 elliptic curve (100-bit security) [52]. 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.

7.3.2 Privacy Enhanced EAP↩︎

Figure 4 presents the architecture of privacy enhanced EAP using PriSrv, which extends RFC 3748 on Extensible Authentication Protocol (EAP) [53] 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 [53]. 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 identifier \(bid\) and the broadcast ciphertext \(\textsf{CT}_B=\textsf{CT}_{\vec{x}_s, f_s}=\mathcal{ACME}.\textsf{Enc}(\cdots,MSG_B)\). This step corresponds to the statement “the authenticator sends a request to authenticate the peer" in EAP Standard. (2) If the client can decrypt \(MSG_B\) from \(\textsf{CT}_B\), he/she sends a response packet \((bid,sid,\sigma_c,\textsf{CT}_c)\) as reply to the service provider, where \(\textsf{CT}_c=\textsf{CT}_{\vec{x}_c, f_c}=\mathcal{ACME}.\textsf{Enc}(\cdots,MSG_C)\) and \(sid\) is a session identifier. (3) Receiving the response, the service provider proceeds to recover \(MSG_c\) from \(\textsf{CT}_c\). If it succeeds, the service provider sends \((M_s,\sigma_s)\) to client, where \(M_s\) contains the DH shares for computing a session key and \(\sigma_s\) is the corresponding MAC value. After the client verifies \(\sigma_s\), it calculates a secret session key \(SSK_{c,s}\), and responds with a message”succeed". (4) Finally, the service provider also computes \(SSK_{c,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.

7.3.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.

7.4 Limitations of PriSrv↩︎

One limitation of PriSrv lies in its large message size when compared to existing protocols. This large size of the outer 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 privacy-preserving 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 Wi-Fi 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.

8 Implementation and Comparison↩︎

We benchmark the performance of PriSrv on various hardware platforms, including desktop, laptop, smartphone, and Raspberry Pi as shown in Table 3. Three asymmetric elliptic curves are selected from the MIRACL library [54] for evaluation, including MNT159 (80-bit security), MNT201 (90-bit security), and BN256 (100-bit security) [52]. We use AES-CTR with 100-bit keys to instantiate the \(\textsf{SEnc}\)/\(\textsf{SDec}\) algorithms in PriSrv, using SHA-256 as the hash function, and use \(\textsf{MAC}_{\textsf{GGM}}\) [34] as suf-cma secure MAC. The source code of our experiments is written in C/C++ and publicly available on GitHub⁶. For each test case, we report the average over 20 executions.

0.1mm

8.1 Evaluation of FAC↩︎

In Table 4, 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 up-to-date optimal solution. The \(O(1)\) communication complexity in [29] for its \(\textsf{Show}\) algorithm (i.e., \(|\textsf{Show}|\)) is composed of about 100 group elements. Since the scheme in [29] is the only one to achieve UC security in Table 4, these overheads can be seen as a tradoff between efficiency and security. Compared with [30], our credential only consists of 2 elements in \(G_2\), which is approximately \(2\times\) more efficient than that of [30] (i.e., \(3|G_1|+|G_2|+2|\mathbb{Z}_p|\)). To show a credential in FAC, a user transmits 2 elements in \(G_1\), 2 in \(G_2\), 1 in \(G_T\) and three scalar elements, which is smaller than 8 elements in \(G_1\), 1 in \(G_2\) and two scalar elements for [30].

2.2mm

Table 5 compares the performance of FAC with Idemix, UProve and the schemes in [29], [30] on desktop. The parameters for FAC are \(n=10\) and \(|\mathcal{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 \(\textsf{Issue}\), \(\textsf{Show}\), \(\textsf{Verify}\) are the lowest or the second lowest among those supporting multi-show unlinkability.

8.2 Evaluation of ACME and PriSrv↩︎

Table 6 presents the computation cost (comp.) and communication cost (comm.) of ACME for different algorithms on desktop following the example in \(\S\)4, where the parameters are \(n=10\), \(k=2\), \(\hat{m}=9\) and \(|\mathcal{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 (\(|\textsf{mpk}|\)) and master secret key (\(|\textsf{msk}|\)) for BN256 are 4.128 KB and 1.6 KB, respectively. The credential key generation (\(\textsf{CredKeyGen}\)) and user key generation (\(\textsf{UserKeyGen}\)) cost no more than 118.622 ms and 9.102 ms, respectively. The credential issue (\(\textsf{Issue}\)) algorithm is efficient (39.383 ms) and the size of generated anonymous credential (\(|\textsf{cred}|\)) is merely 0.544 KB on BN256 curve, which is consistant with the theoretical analysis of FAC in \(\S\)8.1. The size of attribute decryption key (\(\textsf{DK}_{\vec{x}}\)) and the size of policy decryption key (\(\textsf{DK}_{f}\)) 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.

0.6mm

1.15mm

Using the same example and parameter settings, Table 7 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 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 (\(T_B\)), server’s computation time (\(T_S\)) and client’s computation time (\(T_C\)) during the anonymous mutual authentication phase, where the total mutual authentication time is \(T_{MA}=T_S+T_C\). The left y-axis shows the computation time, and right y-axis indicates the communication overhead in the broadcast phase (\(|\textsf{Broadcast}|\)) and the communication overhead of service provider/client in the authentication phase (\(|\textsf{Server}|\)/\(|\textsf{Client}|\)). The performance of PriSrv varies with the attribute number \(n\) (top x-axis) and the wire number \(\hat{m}\) of \(\textsf{NC}^1\) (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 of access policy \(\hat{m}\) among \(\{1, 3, 7, 11\}\) for practicality test. For \(n=15\), \(\hat{m}=11\), we have \(T_B=763.892\) ms, \(T_S=302.973\) ms and \(T_C=938.395\) ms, \(|\textsf{Client}|\)=573.852 KB and \(|\textsf{Server}|=0.82\) KB. Fig. 6 sets \(n=25,50\) and varies \(\hat{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 \(\hat{m}=27\), the computation costs are \(T_B=5.711\)s, \(T_S=0.549\)s, \(T_C=6.262\)s. 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.

9 Conclusion↩︎

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.

Acknowledgment↩︎

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.

9.1 FAC: Security Model and Proof↩︎

(1) Security Model

Following the definitions in [34], [35], we define correctness, unforgeability, anonymity and unlinkability for anonymous credential scheme. The lists in the security models are given in Table 8.

Definition A.1 Let \(\mathcal{D}\) be the universe of user identity, and \(\Omega\) be the universe of attribute sets. Then an anonymous credential scheme \(\mathcal{AC}\) is correct for \(\mathcal{D},\Omega\) if all \(uid\in\mathcal{D}\), all \(\vec{x}\subseteq\Omega\), for all security parameter \(\lambda\), \[\textsf{Pr}\left[ \begin{array}{l} \textsf{pp}\xleftarrow{\$}\textsf{Setup}(1^{\lambda}, 1^{n});(\textsf{pk},\textsf{sk})\xleftarrow{\$}\textsf{CredKeyGen}(\textsf{pp});\\ (\textsf{upk},\textsf{usk})\xleftarrow{\$}\textsf{UserKeyGen}(\textsf{pp});\\ \textsf{cred}\xleftarrow{\$}\left<\textsf{Issue.I}(\textsf{sk},\textsf{upk})\rightleftarrows\textsf{Issue.U}(uid,\vec{x},\textsf{usk})\right>;\\ \textsf{tok}\xleftarrow{\$}\textsf{Show}(uid,\{x_i\}_{i\in\mathcal{I}},\textsf{cred},\textsf{usk},m):\\ \textsf{Verify}(\textsf{tok},m)=0 \end{array} \right]\] \(\leq\nu(\lambda)\), where \(\nu\) is a negligible function.

Definition A.2 An AC scheme satisfies unforgeability if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\mathcal{AC}}^{\textsf{unforge}}(\lambda)\overset{\textsf{def}}{=}\) \[\textsf{Pr}\left[b=1~ \begin{array}{|l} \textsf{pp}\leftarrow\textsf{Setup}(1^{\lambda},1^n),\\ (\textsf{pk,sk})\leftarrow\textsf{CredKeyGen}(\textsf{pp})\\ (uid^*,\vec{x}^*,m^*,\textsf{cred}^*,\textsf{tok}^*)\leftarrow\mathcal{A}^{\mathcal{O}(\textsf{sk},\cdot)}(\textsf{pp},\textsf{pk})\\ b\leftarrow\textsf{Verify}(\textsf{tok}^*,m^*)\\ \text{return } b~\text{if}\quad (m^*,\vec{x}^*,\textsf{cred}^*,\textsf{tok}^*)\notin\mathcal{L}_{\textsf{show}}\\ \quad\quad\wedge~\textsf{cred}^*\notin\mathcal{L}_{\textsf{issue}}\wedge~(uid^*,\vec{x}^*)\notin\mathcal{L}_{\textsf{corrupt}}\\ \text{else abort} \end{array} \right]\] \(\leq\nu(\lambda)\), where the oracle set \(\mathcal{O}=\{\textsf{UserKeyGen},\textsf{Issue},\) \(\textsf{Show},\) \(\textsf{Corrupt}\}\) is implemented by \(\textsf{UserKeyGen}(\textsf{pp},\cdot),\) \(\textsf{Issue}(\textsf{sk},\textsf{st},\cdot)\), \(\textsf{Show}(\textsf{pk},\cdot)\) and \(\textsf{Corrupt}(\cdot)\).

Definition A.3 An AC scheme \(\mathcal{AC}\) satisfies anonymity if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\mathcal{AC}}^{\textsf{anon}}(\lambda)\overset{\textsf{def}}{=}\) \[\textsf{Pr}\left[b'=b~ \begin{array}{|l} \textsf{pp}\leftarrow\textsf{Setup}(1^{\lambda},1^n),\\ (\textsf{pk,sk})\leftarrow\textsf{CredKeyGen}(\textsf{pp})\\ (uid_0^*,uid_1^*,\vec{x}^*,m^*)\leftarrow\mathcal{A}^{\mathcal{O}(\textsf{sk},\cdot)}(\textsf{pp},\textsf{pk})\\ \text{abort if } \exists d\xleftarrow{\$}\{0,1\}:\\ (uid_d^*,\vec{x}^*,\textsf{cred}_d)\notin\mathcal{L}_{\textsf{honest}};~ b\xleftarrow{\$}\{0,1\}\\ \textsf{tok}^*\leftarrow\textsf{Show}(uid_b^*,\textsf{cred}_b,\textsf{usk}_b,\vec{x}^*,m^*)\\ b'\leftarrow\mathcal{A}^{\mathcal{O}(\textsf{sk},\cdot)}(\textsf{pp},\textsf{tok}^*)\\ \text{return } b'~\text{if}~~~ \textsf{cred}^*\notin\mathcal{L}_{\textsf{issue}}\wedge\\ (m^*,\vec{x}^*,\textsf{tok}^*)\notin\mathcal{L}_{\textsf{show}}~\wedge~(uid_{0/1}^*,\vec{x}^*)\notin\mathcal{L}_{\textsf{corrupt}}\\ \text{else abort} \end{array} \right]\] \(\leq\nu(\lambda)\), where the oracle set \(\mathcal{O}=\{\textsf{UserKeyGen},\textsf{Issue},\) \(\textsf{Show},\) \(\textsf{Corrupt}\}\) is implemented by \(\textsf{UserKeyGen}(\textsf{pp},\cdot),\) \(\textsf{Issue}(\textsf{sk},\textsf{st},\cdot)\), \(\textsf{Show}(\textsf{pk},\cdot)\) and \(\textsf{Corrupt}(\cdot)\).

Definition A.4 An AC scheme \(\mathcal{AC}\) satisfies unlinkability if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\mathcal{AC}}^{\textsf{unlink}}(\lambda)\overset{\textsf{def}}{=}\) \[\textsf{Pr}\left[b'=b~ \begin{array}{|l} \textsf{pp}\leftarrow\textsf{Setup}(1^{\lambda},1^n),\\ (\textsf{pk,sk})\leftarrow\textsf{CredKeyGen}(\textsf{pp})\\ (uid_0^*,uid_1^*,\mathcal{I}^*,\vec{x}_0^*,\vec{x}_1^*,m^*)\leftarrow\mathcal{A}^{\mathcal{O}(\textsf{sk},\cdot)}(\textsf{pp},\textsf{pk})\\ \text{where } \mathcal{I}^*\subseteq[1,n],\vec{x}_d^*=\{x_i^{(d)}\}_{i\in[1,n]},d\in\{0,1\}\\ \text{abort if }\exists j\in\mathcal{I}^*: x_j^{(0)}\neq x_j^{(1)}\\ \text{or } \exists d\xleftarrow{\$}\{0,1\}: (uid_d^*,\vec{x}_d^*,\textsf{cred}_d)\notin\mathcal{L}_{\textsf{honest}},\\ b\xleftarrow{\$}\{0,1\}\\ \textsf{tok}_b^*\leftarrow\textsf{Show}(uid_b^*,\textsf{cred}_b^*,\textsf{usk}_b^*,\{x_i^{(b)}\}_{i\in\mathcal{I}^*},m^*)\\ b'\leftarrow\mathcal{A}^{\mathcal{O}(\textsf{sk},\cdot)}(\textsf{pp},\textsf{tok}_b^*)\\ \text{return } b'~\text{if }~\forall d'\in\{0,1\},~~~\textsf{cred}_{d'}^*\notin\mathcal{L}_{\textsf{issue}}\wedge\\ (m^*,\vec{x}_{d'}^*,\textsf{tok}_{d'}^*)\notin\mathcal{L}_{\textsf{show}}~\wedge~(uid_{d'}^*,\vec{x}_{d'}^*)\notin\mathcal{L}_{\textsf{corrupt}}\\ \text{else abort} \end{array} \right]\] \(\leq\nu(\lambda)\), where the oracle set \(\mathcal{O}=\{\textsf{UserKeyGen},\textsf{Issue},\) \(\textsf{Show},\) \(\textsf{Corrupt}\}\) is implemented by \(\textsf{UserKeyGen}(\textsf{pp},\cdot),\) \(\textsf{Issue}(\textsf{sk},\textsf{st},\cdot)\), \(\textsf{Show}(\textsf{pk},\cdot)\) and \(\textsf{Corrupt}(\cdot)\).

It is easy to see that the security definition of unlinkability implicitly implies that of anonymity.

3.2mm

(2) Correctness Proof

Theorem A.1 The FAC scheme satisfies correctness.

(3) Security Proof

The security of FAC in Theorem 5.1 is proved in aspects of unforgeability, anonymity and unlinkability.

3.1) Unforgeability Proof of FAC

Lemma A.1 The FAC scheme is unforgeable if the underlying unforgeable redactable signature (URS) [35] is unforgeable and the discrete logarithm (DL) assumption holds.

3.2) Anonymity and Unlinkability of FAC

Lemma A.2 The FAC scheme satisfies anonymity and unlinkability under the decisional Diffie–Hellman (DDH) assumption.

9.2 ACME: Security Model and Proof↩︎

(1) Security Model

This section defines correctness, privacy, authenticity, anonymity and unlinkability for ACME scheme.

Definition B.1. Let \(\mathcal{D}\) be the universe of user identity, and \(\Omega\) be the universe of attributes. An anonymous credential-based matchmaking encryption encryption scheme \(\mathcal{ACME}\) is correct for \(\mathcal{D},\Omega\) if all \(uid\in\mathcal{D}\), all \(\vec{x}\subseteq\Omega\) for all security parameter \(\lambda\), \[\textsf{Pr}\left[ \begin{array}{l} (\textsf{mpk},\textsf{msk})\xleftarrow{\$}\textsf{Setup}(1^{\lambda},1^n);\\ (\textsf{pk},\textsf{sk})\xleftarrow{\$}\textsf{CredKeyGen}(\textsf{mpk});\\ (\textsf{upk},\textsf{usk})\xleftarrow{\$}\textsf{UserKeyGen}(\textsf{mpk});\\ \textsf{cred}_{\textsf{snd}}\xleftarrow{\$}\left<\textsf{Issue.I}(\textsf{sk},\textsf{upk})\rightleftarrows\textsf{Issue.U}(uid,\vec{x}_{\textsf{snd}},\textsf{usk})\right>;\\ \textsf{DK}_{\vec{x}_{\textsf{rcv}}}\xleftarrow{\$}\textsf{DKGen}(\mathsf{msk},\vec{x}_{\textsf{rcv}});\\ \textsf{DK}_{f_{\textsf{rcv}}}\leftarrow\textsf{PolGen}(\mathsf{msk},f_{\textsf{rcv}});\\ \textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}}\xleftarrow{\$}\mathsf{Enc}(\textsf{cred}_{\textsf{snd}},\vec{x}_{\textsf{snd}},f_{\textsf{snd}},M):\\ f_{\textsf{rcv}}(\vec{x}_{\textsf{snd}}^{(out)})=1 \wedge f_{\textsf{snd}}(\vec{x}_{\textsf{rcv}}^{(out)})=1 \wedge\\ \mathsf{Dec}(\textsf{DK}_{\vec{x}_{\textsf{rcv}}},\textsf{DK}_{f_{\textsf{rcv}}},\textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}})=\bot \end{array} \right]\] \(\leq\nu(\lambda)\), where \(\nu\) is a negligible function.

Definition B.2. An ACME scheme \(\mathcal{ACME}\) satisfies privacy if for any PPT adversary \(\mathcal{A}=(\mathcal{A}_1,\mathcal{A}_2)\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\mathcal{ACME}}^{\textsf{priv}}(\lambda)\overset{\textsf{def}}{=}\) \[\textsf{Pr}\left[b'=b~ \begin{array}{|l} (\textsf{mpk},\textsf{msk})\leftarrow\textsf{Setup}(1^{\lambda},1^n),b\xleftarrow{\$}\{0,1\}\\ (M_0^*,M_1^*, \textsf{cred}_{\textsf{snd}_0}^*,\textsf{cred}_{\textsf{snd}_1}^*, \vec{x}_{\textsf{snd}_0}^*, \vec{x}_{\textsf{snd}_1}^*,f_{\textsf{snd}}^*)\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\leftarrow\mathcal{A}_1^{\mathcal{O}_1,\mathcal{O}_2,\mathcal{O}_3}(\textsf{mpk})\\ \textsf{CT}^*\leftarrow\textsf{Enc}(\textsf{cred}_{\textsf{snd}_b}^*,\vec{x}_{\textsf{snd}_b}^*,f_{\textsf{snd}}^*,M_b)\\ b'\leftarrow\mathcal{A}_2^{\mathcal{O}_1,\mathcal{O}_2,\mathcal{O}_3}(\textsf{mpk},\textsf{CT}^*)\\ \end{array} \right]\] \(\leq\nu(\lambda),\) where oracles \(\mathcal{O}_1\), \(\mathcal{O}_2\), \(\mathcal{O}_3\) are implemented by \(\textsf{Issue}\) \((\textsf{msk},\cdot)\), \(\textsf{DKGen}(\textsf{msk},\cdot)\), \(\textsf{PolGen}(\textsf{msk},\cdot)\), respectively. It is required that \(\mathcal{O}_2\) and \(\mathcal{O}_3\) are not queried for attributes and policies that can satisfy \((\vec{x}_{\textsf{snd}_0}^*, f_{\textsf{snd}}^*)\) or \((\vec{x}_{\textsf{snd}_1}^*, f_{\textsf{snd}}^*)\). It is also required that for public attributes \(\vec{x}_{\textsf{snd}_0}^{(out)*}\)/ \(\vec{x}_{\textsf{snd}_1}^{(out)*}\) in \(\vec{x}_{\textsf{snd}_0}^*\) / \(\vec{x}_{\textsf{snd}_1}^*\), we have \(\vec{x}_{\textsf{snd}_0}^{(out)*} = \vec{x}_{\textsf{snd}_1}^{(out)*}\).

This model only captures security under chosen plaintext attacks (CPA). We can extend the above definition by introducing another decryption oracle \(\mathcal{O}_4\) which can decrypt ciphertexts except the challenge ciphertext \(\textsf{CT}^*\) to capture security under chosen-ciphertext attacks (CCA).

Definition B.3. An ACME scheme \(\mathcal{ACME}\) satisfies authenticity if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\mathcal{ACME}}^{\textsf{auth}}(\lambda)\overset{\textsf{def}}{=}\) \[\textsf{Pr}\left[ \begin{array}{l} (\textsf{mpk},\textsf{msk})\leftarrow\textsf{Setup}(1^{\lambda},1^n)\\ (\textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}},\vec{x}_{\textsf{rcv}}, f_{\textsf{rcv}})\leftarrow\mathcal{A}^{\mathcal{O}_1,\mathcal{O}_2,\mathcal{O}_3}(\textsf{mpk})\\ \textsf{DK}_{\vec{x}_{\textsf{rcv}}}\leftarrow\textsf{DKGen}(\textsf{msk},\vec{x}_{\textsf{rcv}})\\ \textsf{DK}_{ f_{\textsf{rcv}}}\leftarrow\textsf{PolGen}(\textsf{msk}, f_{\textsf{rcv}})\\ M=\textsf{Dec}(\textsf{DK}_{\vec{x}_{\textsf{rcv}}},\textsf{DK}_{ f_{\textsf{rcv}}},\textsf{CT}_{\vec{x}_{\textsf{snd}},f_{\textsf{snd}}})\\ \forall\vec{x}\in \mathcal{Q}_{\mathcal{O}_1,\mathcal{O}_2}:( f_{\textsf{rcv}}(\vec{x}^{(out)})=0)\wedge (M\neq\bot)\\ \end{array} \right]\] \(\leq\nu(\lambda),\) where oracles \(\mathcal{O}_1\), \(\mathcal{O}_2\), \(\mathcal{O}_3\) are implemented by \(\textsf{Issue}\) \((\textsf{msk},\cdot)\), \(\textsf{DKGen}(\textsf{msk},\cdot)\), \(\textsf{PolGen}(\textsf{msk},\cdot)\).

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

Theorem 6.2. The proposed ACME scheme achieves privacy, authenticity, anonymity and unlinkability if the \(MDDH_k\) 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 \(MDDH_k\) assumption.

Proof Intuition. In our proposed ACME scheme, the message \(M\) and the FAC token \(\textsf{tok}_{\textsf{snd}}\) (corresponding to the private attributes) are encrypted using a symmetric key \(K\) which is encapsulated in \(\textsf{ct}_0=e([\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}+\boldsymbol{s}^{\top}\boldsymbol{A}]_1,[\boldsymbol{v}]_2)\cdot K.\) Hence, the privacy of both \(M\) and \(\textsf{tok}_{\textsf{snd}}\) is based on the confidentiality of the symmetric key \(K\).

As shown in the correctness, when \(f_{\textsf{rcv}}(\vec{x}_{\textsf{snd}}^{(out)})=1\) (corresponding to KP-ABE), we have \[\frac{e\big(\textsf{ct}_2',\prod\nolimits_{j\in\mathcal{S}_r}\textsf{dk}_j^{\omega_j}\big)}{e\big(\textsf{ct}_1',\prod\nolimits_{j\in\mathcal{S}_r}\big(\prod_{i:x_{s,i}^{(out)}=1}\textsf{dk}_{i,j}\big)^{\omega_j}\big)} = ([\widetilde{\boldsymbol{s}}^{\top}\boldsymbol{A}\boldsymbol{v}]_T)^{-1}\] and when \(f_{\textsf{snd}}(\vec{x}_{\textsf{rcv}}^{(out)})=1\) (corresponding to CP-ABE), we have \[\frac{e(\prod\nolimits_{j\in\mathcal{S}_s}(\prod\nolimits_{i:x_{r,i}^{(out)}=1}\textsf{ct}_{i,j})^{\mu_j},\textsf{dk}_2)}{e(\textsf{ct}_1,\textsf{dk}_1)\cdot e(\prod\nolimits_{j\in\mathcal{S}_s}\widetilde{\textsf{ct}}_{j}^{\mu_j},\textsf{dk}_3)} = ([\boldsymbol{s}^{\top}\boldsymbol{A}\boldsymbol{v}]_T)^{-1}.\] 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, if \(f_{\textsf{rcv}}(\vec{x}^{(out)*}_{\textsf{snd}})\ne1\), 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 to obtain keys for \(f_{\textsf{rcv}}\) and \(\vec{x}_{\textsf{rcv}}\) such that \(f_{\textsf{rcv}}(\vec{x}^{(out)*}_{\textsf{snd}}) = 1 \wedge f^*_{\textsf{snd}}(\vec{x}^{(out)}_{\textsf{rcv}})=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 would not query a key for \(f_{\textsf{rcv}}\) such that \(f_{\textsf{rcv}}(\vec{x}^{(out)*}_{\textsf{snd}}) = 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.

9.3 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], [37] and the service discovery model in [5].
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 message if their credentials satisfy the service authorization policy.

Protocol participants. The participants of PriSrv includes a set of clients \(\textsf{C}=\{C_1,\cdots,C_{n_1}\}\) and a set of service providers \(\textsf{S}=\{S_1,\cdots,S_{n_2}\}\).

Long-term Keys. Each \(C_i\in\textsf{C}\) and \(S_j\in\textsf{S}\) hold long-term secret keys for bilateral authentication and message decryption.

Session and Pairing. Denote the \(\rho\)-th instance of participant \(U\in \textsf{C} \cup \textsf{S}\) as \(U^{\rho}\), which is modeled as a PPT Turing machine. A participant \(U^{\rho}\) can be activated to initiate a session with a broadcast identifier \(bid_{U}^{\rho}\), a session identifier \(sid_{U}^{\rho}\), attributes \(\vec{x}_{U}^{\rho}\), and a policy \(f_{U}^{\rho}\). A client instance \(C_i^{\rho}\) and a service provider instance \(S_j^{\delta}\) are said to be paired if their session instances \((C_i^{\rho},bid_{C_i}^{\rho},sid_{C_i}^{\rho},\vec{x}_{C_i}^{\rho},f_{C_i}^{\rho})\) and \((S_j^{\delta},bid_{S_j}^{\delta},sid_{S_j}^{\delta},\vec{x}_{S_j}^{\delta},f_{S_j}^{\delta})\) satisfy \(bid_{C_i}^{\rho}=bid_{S_j}^{\delta}\), \(sid_{C_i}^{\rho}\) \(=sid_{S_j}^{\delta}\), \(f_{S_j}^{\delta}(\vec{x}_{C_i}^{\rho(out)})=1\), \(f_{C_i}^{\rho}(\vec{x}_{S_j}^{\delta(out)})=1\). A completed session contains a tuple \((C_i^{\rho},bid_{C_i,S_j}^{\rho,\delta},sid_{C_i,S_j}^{\rho,\delta},S_j^{\delta},SSK_{C_i,S_j}^{\rho,\delta})\), where \(bid_{C_i,S_j}^{\rho,\delta}=bid_{C_i}^{\rho}=bid_{S_j}^{\delta}\), \(sid_{C_i,S_j}^{\rho,\delta}=sid_{C_i}^{\rho}=sid_{S_j}^{\delta}\).

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 \(\mathcal{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 long-term secrets possessed by participants.

\(\bullet\) \(\textsf{Send}(U^{\rho},M)\): transmits a message \(M\) to \(U^{\rho}\), who executes the protocol and returns the operation result to adversary \(\mathcal{A}\). If the message in the query causes the protocol to execute or abort, it will be made known to \(\mathcal{A}\).

\(\bullet\) \(\textsf{Execute}(C_i^{\rho},S_j^{\delta})\): executes a complete protocol between \(C_i^{\rho}\) and \(S_j^{\delta}\). The adversary captures all messages transmitted over the public network. Hence, the query to \(\textsf{Execute}\) oracle models passive eavesdropping capability of the adversary.

\(\bullet\) \(\textsf{RevealBroadcast}(S_j^{\delta},bid)\): returns the semi-static state in a service provider \(S_j^{\delta}\) that is maintained for the lifetime of its current broadcast with identifier \(bid\), including the attributes \(\vec{x}_{S_j^{\delta}}\) and authorization policy \(f_{S_j^{\delta}}\). The revealed state does not involve the long-term secrets. \(\mathcal{A}\) is allowed to make query for any service provider \(S_j\in\textsf{S}\).

\(\bullet\) \(\textsf{RevealState}(U^{\rho},bid,sid)\): returns the local state associated with the targeted session, which does not contain the long-term secrets.

\(\bullet\) \(\textsf{RevealKey}(U^{\rho},bid,sid)\): outputs the secret session key associated with a targeted session.

\(\bullet\) \(\textsf{Corrupt}(U)\): returns all information (including ephemeral and long-term secrets) held by \(U\).

\(\bullet\) \(\textsf{TestSession}(U^{\rho},bid,sid)\): This oracle is used to model key secrecy. A random bit \(b\in\{0,1\}\) is selected to respond this query. If \(b=1\), the target session key is returned to \(\mathcal{A}\). Otherwise, a randomly value picked from the secret session key space is returned.

Session Exposure. A session \((U^{\rho},bid,sid)\) is said to be exposed if the adversary makes the following queries.

- The adversary makes a \(\textsf{RevealKey}\) query on the session.

- The adversary makes a \(\textsf{Corrupt}\) query on \(U\), or any partner with \((\vec{x},f)\) satisfying \(f_{U}(\vec{x}^{(out)}) = 1 \wedge f(\vec{x}_U^{(out)}) = 1\), before the session has expired.

- \(U\) is the client in the protocol and the adversary has made a \(\textsf{RevealState}\) query on the session.

- \(U\) is the server in the protocol and the adversary has made a \(\textsf{RevealState}\) query on the session, and also made a \(\textsf{RevealBroadcast}\) query on the session or a \(\textsf{Corrupt}\) query on \(U\) before the session has expired.

Session Freshness. A session \((U^{\rho},bid,sid)\) is said to be fresh if itself is not exposed and all its matching sessions are not exposed.

Definition C.1 Let \(\textsf{Succ}_{\textsf{PriSrv}}^{\textsf{Sec}}(\mathcal{A})\) denote the event that \(\mathcal{A}\) makes a single \(\textsf{TestSession}\) query with the restriction that the queried session \((U^{\rho},bid,sid)\) is fresh, and finally outputs a bit \(b'=b\), where \(b\) is the random value selected in the \(\textsf{TestSession}\) query. A private service discovery protocol \(\textsf{PriSrv}\) is secure if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\textsf{PriSrv}}^{\textsf{Sec}}(\mathcal{A})\overset{\textsf{def}}{=}2\textsf{Pr}[\textsf{Succ}_{\textsf{PriSrv}}^{\textsf{Sec}}(\mathcal{A})]-1\leq\nu(\lambda).\)
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 \(C_{i_0}^*\) or \(C_{i_1}^*\) (challenge clients). Let \(n\) be the number of parties participating in the protocol execution experiment, which are denoted as \((P_1,\cdots,P_n)\). A special test party \(P_T\) is introduced at the beginning of the experiment whose identity is kept confidential from the adversary. We introduce two experiments \(\textsf{Exp}_0\) and \(\textsf{Exp}_1\), and select random \(b\in\{0,1\}\) at the beginning of the game. The experiment \(\textsf{Exp}_b\) proceeds as below.

Setup Phase. At the beginning of the experiment, adversary \(\mathcal{A}\) submits a set of identities (with attributes and policies) \(\{(uid_{j},\vec{x}_{j},f_{j})\}_{j=1}^n\) for parties \((P_1,\cdots,P_n)\). For each \(j\in[n]\), the challenger sets up anonymous credential and long-term secret attribute/policy keys for party \(P_j\). \(\mathcal{A}\) also submits two challenge clients \(C_{i_0}^*,\) \(C_{i_1}^*\in\textsf{C}\), where \(C_{i_0}^*\) possesses \((uid_{i_0}^*,\vec{x}_{i_0}^*,f_{i_0}^*)\) and \(C_{i_1}^*\) has \((uid_{i_1}^*,\vec{x}_{i_1}^*,f_{i_1}^*)\). It is required that \(\vec{x}_{i_0}^* = \vec{x}_{i_1}^*\) and \(f_{i_0}^* = f_{i_1}^*\). Note that the challenge tuples \((uid_{i_0}^*,\vec{x}_{i_0}^*,f_{i_0}^*)\) and \((uid_{i_1}^*,\vec{x}_{i_1}^*,f_{i_1}^*)\) are distinct from \(\{(uid_{j},\vec{x}_{j},f_{j})\}_{j=1}^n\). Then, the challenger associates \((uid_{i_b}^*,\vec{x}_{i_b}^*,f_{i_b}^*)\) with \(P_T\), and executes the setup algorithm for \(P_T\) that is defined in the protocol.

Protocol Execution. Adversary \(\mathcal{A}\) is allowed to issue the following queries.

\(\bullet\) \(\textsf{Reg}(U^{\rho},uid_U^{\rho},\vec{x}_U^{\rho}, f_U^{\rho})\): If \(U^{\rho}\in(P_1,\cdots,P_n)\) with user identifier \(uid_U^{\rho}\), attributes \(\vec{x}_U^{\rho}\) and policy \(f_U^{\rho}\) is unregistered, it executes as the protocol definition, and returns the result to \(\mathcal{A}\).

\(\bullet\) \(\textsf{Send}\), \(\textsf{RevealBroadcast}\), \(\textsf{RevealState}\), \(\textsf{RevealKey}\) and \(\textsf{Corrupt}\) are the same as the definition in “Service Discovery Security" model.

\(\bullet\) \(\textsf{Challenge}\). In \(\textsf{Exp}_b\), the instance \(C_{i_b}^*\) with \((uid_{i_b}^*,\vec{x}_{i_b}^*,f_{i_b}^*)\) executes PriSrv by following the protocol steps. The restriction is that \(\mathcal{A}\) does not issue any of the following queries:

- \(\textsf{Reg}\) query on \((uid_{i_0}^*,\vec{x}_{i_0}^*, f_{i_0}^*)\) or \((uid_{i_1}^*,\vec{x}_{i_1}^*, f_{i_1}^*)\) or any service provider whose attributes and policy satisfy \((\vec{x}_{i_0}^*,f_{i_0}^*)\) or \((\vec{x}_{i_1}^*,f_{i_1}^*)\);

- \(\textsf{RevealState}\) or \(\textsf{RevealKey}\) query on any \((P_T,bid,sid)\) or its matching session;

- \(\textsf{Corrupt}\) query on \(C_{i_0}^{*}\) or \(C_{i_1}^{*}\) or any service provider whose attributes and policy satisfy \((\vec{x}_{i_0}^*,f_{i_0}^*)\) or \((\vec{x}_{i_1}^*,f_{i_1}^*)\).

- If \(\mathcal{A}\) associates a policy \((\vec{x}_{S_j}, f_{S_j})\) with a service provider session \((S_j^\delta, bid, sid)\), it is required that either both \(C_{i_0}^*\) and \(C_{i_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 \(\mathcal{A}\).

Output phase. \(\mathcal{A}\) outputs a guess \(b'\in\{0,1\}\) for \(b\).

A service discovery protocol achieves client anonymity if no adversary can distinguish the experiments \(\textsf{Exp}_0\) and \(\textsf{Exp}_1\) with non-negligible advantage greater than 1/2, which captures the property that no active adversary can distinguish communications with a client \(C_{i_0}^*\) from those with a client \(C_{i_1}^*\). Here is the formal definition.

Definition C.2 Let \(\textsf{Succ}_{\textsf{PriSrv}}^{\textsf{anon-C}}(\mathcal{A})\) denote the event that \(\mathcal{A}\) outputs a bit \(b'=b\). \(\textsf{PriSrv}\) satisfies client anonymity if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\textsf{PriSrv}}^{\textsf{anon-C}}(\mathcal{A})\overset{\textsf{def}}{=}2\textsf{Pr}[\textsf{Succ}_{\textsf{PriSrv}}^{\textsf{anon-C}}(\mathcal{A})]-1\leq\nu(\lambda).\)

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 \(\textsf{Revealbroadcast}\) for the challenge sessions. The concrete security model is omitted for brevity.

Definition C.3 Let \(\textsf{Succ}_{\textsf{PriSrv}}^{\textsf{anon-S}}(\mathcal{A})\) denote the event that \(\mathcal{A}\) outputs a bit \(b'=b\). \(\textsf{PriSrv}\) satisfies service provider anonymity if for any PPT adversary \(\mathcal{A}\), there exists a negligible function \(\nu\) such that \(\textsf{Adv}_{\textsf{PriSrv}}^{\textsf{anon-S}}(\mathcal{A})\overset{\textsf{def}}{=}2\textsf{Pr}[\textsf{Succ}_{\textsf{PriSrv}}^{\textsf{anon-S}}(\mathcal{A})]-1\leq\nu(\lambda).\)

Definition C.4 \(\textsf{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, \(\mathcal{ACME}\) is secure, \(\mathcal{MAC}\) is unforgeable, and \(H\) is a random oracle, then \(\textsf{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 [57]) to transform our ACME construction to achieve CCA security.

Lemma C.1. (Service discovery privacy with bilateral control.) Suppose that DDH assumption holds on \(G_1\) and \(G_2\), \(\mathcal{ACME}\) is secure, \(\mathcal{MAC}\) is unforgeable, and \(H\) is random oracle, then \(\textsf{PriSrv}\) is a secure service discovery protocol with bilateral control.

Lemma C.2. (Client anonymity) \(\textsf{PriSrv}\) protocol satisfies client anonymity assuming the ACME scheme is private.

Lemma C.3. (Server anonymity) \(\textsf{PriSrv}\) protocol satisfies server anonymity assuming the ACME scheme is private.

References↩︎

---

1. In computational complexity theory, \(\textsf{NC}^i\) 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(\log^i n)\), or the class of decision problems solvable in time \(O(\log^i n)\) on a parallel computer with a polynomial number of processors, where \(\textsf{NC}\) is short for "Nick Pippenger’s Class".↩︎

2. Please refer to the details of linear secret sharing for \(\textsf{NC}^1\) in §5.1 of [26].↩︎

3. OpenID Foundation: https://openid.net/foundation.↩︎

4. Vanadium. https://vanadium.github.io/.↩︎

5. https://tools.ietf.org/html/rfc6763.↩︎

6. Source Code: https://github.com/prisrv.↩︎