When Information Retrieval (IR) models are applied to and trained on sensitive and personal information, users' privacy is at risk. While mechanisms have been presented to safeguard user privacy, the efectiveness of these privacy protections is generally evaluated by studying the relations between performance on a downstream task and the parameters of the mechanisms, e.g., the privacy budget in Diferential Privacy ( DP). This often causes a partial understanding between formal privacy and the privacy experienced by the user, the actual privacy. In this paper, we discuss the Query Inference for Privacy and Utility (QuIPU) framework, a novel evaluation methodology designed to assess actual privacy based on the risk that an “honest-but-curious” IR system may correctly guess the original query from the obfuscated queries received. The QuIPU framework constitutes the ifrst endeavour to quantify actual privacy for IR tasks, extending beyond the partial comparison of formal privacy parameters. Our findings show that formal privacy parameters do not necessarily correspond to actual privacy, resulting in cases where, despite identical privacy parameters, two systems reveal difering actual privacy levels.
Privacy is a fundamental right preserved by the Universal Declaration of Human Rights and its Article
12. Natural Language Processing (NLP) and Information Retrieval (IR) algorithms are trained and tested
using textual datasets consisting of queries, documents, reviews and posts on online social media. In
such a large amount of textual data, personal user profiles, personal opinions on diferent matters, such
as politics and religions [
Obfuscating a query concerns safeguarding the original information need of a user in such a manner
that the resulting obfuscated queries can retrieve relevant documents while not fully disclosing those
information needs. For example, the query “how tumour grows” may be transformed into the
obfuscated alternatives “how cancer grows”, “how infection spreads”, “how leukemia evolves”.
Focusing on the mechanisms’ privacy parameters represents a preliminary way to measure privacy.
Several attempts to assess the privacy provided have been proposed by adapting information security
measures based on entropy [
In this study, we discuss the Query Inference for Privacy and Utility (QuIPU) framework [
The paper is structured by first presenting the Related Works and Background in Section 2, introducing the diferent measures used in the privacy evaluation and the background on the Query Obfuscation protocol. Section 3 presents the formal definition of QuIPU, showing the phases completed to evaluate the actual textual privacy provided by a mechanism. Finally, Section 4 reports the results and discussion of the formal and actual privacy analysis performed on diferent obfuscation mechanisms.
Diferent metrics have been proposed to organize available privacy measures [
Traditional methods for evaluating privacy primarily focus on estimating the failure rates of
obfuscation mechanisms [
The research community has widely studied application of privacy measure when performing NLP
and IR tasks [
Heuristics Obfuscation. To protect privacy in IR tasks, non-formal obfuscation methods were
proposed [
Diferential Privacy ( DP) Obfuscation. Dwork et al. [
We present the Query Inference for Privacy and Utility (QuIPU) framework: we report the threat model for an obfuscation protocol and the settings of QuIA. Finally, we report the risk evaluation of the attack.
In this scenario, the adversary is represented by the IR system, which aims to understand the original user information need. In the query obfuscation protocol, the sweet spot for inferring the original queries is represented by the ones the system receives. The mechanism parameters, e.g., the privacy budget parameter of the DP obfuscation mechanisms, do not guarantee with absolute certainty that the original text is changed (or changed enough). Therefore, such queries may cause a leakage of the real information need. In addition, for the same parameters, diferent obfuscation strategies may produce texts with diferent obfuscation degrees. For instance, the efect of the parameter depends on the specific mechanism used [ 39, 40]. As a result, two DP mechanisms (one embedding-perturbation based and the other sampling-based) are both parametrized with = 3 and could lead to a situation where one method achieves an actual obfuscation while the other achieves only formal obfuscation. Therefore, the IR system aims to extract as much information as possible from the received queries, previously obfuscated on the user side, using this knowledge to infer the real text.
Consequently, the threat of a successful query inference stems not only from the obfuscation failure of the mechanism but also from the additional knowledge about the queries possessed by the adversary. The IR system might exploit its queries from the logs [41, 42]: by producing a classification on the information needs carried by the obfuscated queries received and the information in its logs, it aims to improve the chances of a correct guess of the original user query. Note that if the original query is not an extremely long tail one, it is reasonable to assume that the original information need has been previously submitted to the IR system, and thus, the attack can succeed with high probability.
Finally, a critical remark must be made regarding using cryptographic primitives in the protocol of the scenario we are analysing. Eavesdroppers or man-in-the-middle adversaries do not significantly threaten the user or the system. Cryptography can be employed while exchanging queries and documents between the client, i.e., the user, and server, i.e., the IR system, ensuring confidentiality among the internal parties of the protocol and security against external auditors. However, confidentiality does not imply privacy: if the IR system aims to disclose the user’s original query, cryptography techniques alone are insuficient to safeguard privacy concerning an internal adversary.
Result: Ranked list of query logs ℒ.
Data: obf (obf. queries ′), logs (query log ), (transformer encoder). 1 Encoding (obf) = { (′) ∈ R} and ︀( logs︀) = { () ∈ R}; 6 return ℒ; 3 Compute = [︀ cos (ˆ, ()) , () ∈ 4 Define ℒ = [︀ (, ) , ∈ , ∈ logs︀] ; 2 Define ˆ as the centroid of the vectors in (obf);
︀( logs︀)] ; 5 Sort ℒ in descending order considering the similarity score ;
The class of attacks known as Membership Inference Attack (MIA) was introduced by Shokri et
al. [
In an obfuscation protocol, the Query Inference Attack (QuIA) uses the received obfuscated queries and the query logs to generate a ranked list of queries from the logs based on the similarity with the information need. Similarly to the black-box of the MIA scenario, the assumption is that the IR system does not know the obfuscation mechanism used on the user side and the privacy parameters of the obfuscation mechanism. Algorithm 1 reports the pseudo-code of the attack: the system receives the set of obfuscated queries obf and knows its query logs logs. Firstly, it uses a Transformer [43] encoder to obtain the embeddings of the queries in the sets2. Once the texts in obf are encoded, it calculates the centroid ˆ of the vectors in (obf), to capture the average contextual similarities among the obfuscated queries received. The system computes the cosine similarity between the embeddings of the queries from the logs () ∈ ︀( logs︀) and the query ˆ to understand which queries from the logs most closely represents the average information need carried by the obfuscated queries and saves it into the list . The algorithm generates a ranked list ℒ of the queries in the logs ∈ logs by sorting (, ) in descending order based on the similarities ∈ . In case of inefective obfuscations, then most likely, the higher a query from the logs is ranked in ℒ, the more it fits the user information need.
Privacy is strictly linked with the definition of risk [ 44], i.e., the possibility that an action or event generates consequences that have an impact on what users value, in this scenario, disclosing sensitive information. The higher the risk, the lower the privacy. For example, DP obfuscation mechanisms ofer the possibility that privacy and utility can be balanced by tuning the privacy budget . However, the framework does not provide any assurance against inference attacks [45]. To overcome this limitation, we need a formal definition of the risk against inference in the obfuscation protocol. After the QuIA algorithm has returned the ranked list ℒ, the IR system is tasked to guess the original query. This inference is based on the computed ranking, which considers the similarities between the obfuscated queries received (potentially leaking information) and the system’s query logs (auxiliary knowledge for a correct guess of the original user query). At this point, the IR system strategy to guess the correct query is sequential: knowing that the first query is the most similar to the average information need carried by the obfuscated queries, it represents the best choice for the guess. If the first query in the logs ℒ is the correct query, the attack is successful, and there is a 100% risk of correct inference. On the other hand, if the first one is not the correct guess, the adversary tries with the second query in the list, and so on, until the original query is guessed, decreasing the risk of success. Therefore, the risk of 2 (obf) , (logs) indicate the sets of text embeddings, and with (′), () the singular vector embedding of the queries. successful QuIA in guesses can be defined as the probability that the IR system correctly guesses ¯ as the original query , seeing the sets obf and logs, i.e., = P ︀[ {¯= } ∩ { ≤ } |obf, logs︀] , with the maximum number of guessing attempts the IR system is willing to take. The upper bound for the value of is determined by the size of the set logs. However, determining the precise threshold and assessing the risk the user faces is impossible without access to the IR system’s internal data and kind of attack. Therefore, we propose to model the malicious IR system with three kinds of attackers, representing relevant use cases: i) the “lazy” attacker, i.e., the one that looks only at the top position of the ranked list ℒ and makes only one guess; ii) the “active” attacker, i.e., an adversary that selects the top- queries and checks only with them if the guess is correct; and iii) the “motivated” attacker, i.e., the one that tries all the queries until the original one has been found. To model the probability of the risk a user faces against each of such attackers, we propose to use proxy indicators computed on where the original query appears in the ranked list ℒ: Precision at 1 ( @1) for the lazy attacker, Recall at (@) for the active attacker, and Reciprocal Rank (RR) for the motivated attacker.
Drawing inspiration from the usual ROC AUC, Figure 2 illustrates the evaluation plane that links the risk of a successful QuIA and the utility measure considering a set of queries obf() – an efectiveness measure such as nDCG in the IR case – obfuscated by a certain formal parameter – the parameter in case of DP. In the risk-utility plane, the Risk-Utility Boundary line, i.e., the diagonal, describes two regions where the risk-utility trend (, ) can be: i) above the line indicates that the utility exceeds the risk , and ii) below the line, where is less than . Therefore, the QuIPU score in Equation 1 considers the pairs (, ) estimated by submitting the set of obfuscated queries obf().
QuIPU = 2(+ + − ) = 2 ∫︁ (, ) + 2 ∫︁ (, )
(1) + − where represents an infinitesimal variation on the Risk-Utility Boundary line, and the factor 2 is introduced to map the score from [︀ − 2 2
1 , 1 ]︀ to [
In Figure 2, four points are defined. The No Utility Point shows when the risk and utility are reduced to 0. It depicts the situation where the obfuscation mechanism fully modifies the original query, completely stopping a QuIA. However, the user completely renounces the efectiveness of the task, i.e., the submitted queries failed to retrieve any relevant documents. The No Privacy Point illustrates the efect of not using the obfuscation protocol. The queries are not obfuscated, meaning the original query is fully exposed to the IR system, resulting in 100% risk. Yet, utility is fully achieved, as the system uses the original query to retrieve the full list of relevant documents. Finally, the Optimal Point and the Trash Point present the best and worst cases theoretically obtainable. In the first, the obfuscation mechanism provides complete protection against Query Inference attacks, i.e., 0% of risk, maintaining maximum utility. The user’s information need are entirely met during the retrieval without exposing any information about the original query. The second is the opposite of the optimal point, i.e., the mechanism neither obfuscates the query nor can these queries retrieve any relevant documents. This case can happen in a “fully-dishonest” scenario, a.e., a phishing IR system [46].
We present the experimental setup and compare the results observed for the privacy analysis using the parameters and QuIPU score. Further analysis, the data used, and the code are publicly available3.
We test the QuIPU framework on three diferent TREC collections: Deep Learning (DL’19) [ 47] and
Deep Learning (DL’20) [48], based on the MS MARCO passages corpus, containing 43 and 54 queries
respectively, and the Robust ’04 (Robust ’04) [49] which relies on disks 4 and 5 of the TIPSTER corpus
and contains 249 queries. As obfuscation mechanisms, we consider those available in the pyPANTERA
framework [50], i.e., CMP, Mahalanobis, their Vickrey Variants, CusText, SanText, TEM, and WBB.
As privacy budget , we followed the parametrization reported in the original papers, which is also
the one used by the pyPANTERA package and other recent experiments [
The traditional privacy analysis evaluates the utility as a function of the formal privacy parameters,
e.g., . Figure 3 reports the results of the nDCG@10 vs the formal privacy parameters on the three
diferent collections analysed. Note that the x-axis, representing the PrivacyParameter, considers both
the values for the parameter of the DP mechanisms and the parameters of the heuristics [
Table 1 reports the QuIPU scores obtained analysing the Risk vs. Utility on each set of obfuscated queries of the collections. The results show three distinct patterns that can be traced back to the three diferent obfuscation strategies. The Sampling-based mechanisms show weaker defences against the three attackers, and especially against the “active” one, i.e., QuIPU score more negative. In contrast, the Embedding Perturbation mechanisms are designed to protect user information from attackers, yielding higher QuIPU scores even against a “motivated” attacker. This suggests that, when using as DP obfuscation mechanisms, if the user wants to achieve strong actual privacy guarantees against the QuIA, it should select an obfuscation relying on changing the word embeddings of the queries. Finally, the heuristics strategies obtain a null QuIPU score due to the stable risk and utility achieved. FEA reaches a slightly positive QuIPU score against the three attackers, implying that it is impractical for an attacker to guess the original query even if “motivated” to do so.
0.7 0.6 00.5 1 CG@0.4 D tyn0.3 il itU0.2 in terms of = nDCG@10, and the risk of a successful Query Inference considering diferent adversary models. Positive values correspond to a better Utility-Privacy trade-of, cf. Section 3.
Obfuscation
Strategy Sampling Embedding Perturbation Heuristics
Mechanism CusText SanText TEM WBB CMP Mahalanobis VickreyCMP VickreyMhl AEA FEA
Lazy Attacker
Active Attacker
Motivated Attacker DL’19
Assessing the privacy guarantees provided to users during IR tasks remains an open challenge. Relying solely on a formal privacy analysis considering the mechanism parameters is insuficient for concretely evaluating the privacy of obfuscation mechanisms. In this study, we introduced the QuIPU framework, a new benchmark designed to assess actual privacy provided to queries in an obfuscation protocol. We empirically evaluated the risk that an “honest-but-curious” IR system can accurately infer the original query from the obfuscated ones received using its queries from the logs. Our findings demonstrate that strong formal privacy guarantees do not necessarily imply actual privacy protection. In future work, we plan to explore additional proxy measures to investigate their correlation with the QuIPU score. In addition, we intend to explore the capabilities of Large Language Models in determining whether or not a query has been suficiently obfuscated, adopting such models as defensive mechanisms against a successful QuIA.
During the preparation of this work, the authors used Grammarly for Readability and Spelling checks. After using this tool, the authors reviewed and edited the content as needed and took full responsibility for the publication’s content.