Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1704.03606

Privacy-Aware Guessing Efficiency

Shahab Asoodeh, Mario Díaz, Fady Alajaji, Tamás Linder

Published Apr 12, 2017• 1 citation
arXivHTMLPDF

Abstract

We investigate the problem of guessing a discrete random variable $Y$ under a privacy constraint dictated by another correlated discrete random variable $X$, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define $h(P_{XY}, ε)$ as the maximum probability of correctly guessing $Y$ given an auxiliary random variable $Z$, where the maximization is taken over all $P_{Z|Y}$ ensuring that the probability of correctly guessing $X$ given $Z$ does not exceed $ε$. We show that the map $ε\mapsto h(P_{XY}, ε)$ is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for $h(P_{XY}, ε)$ when $X$ and $Y$ are connected via a binary-input binary-output channel. For $(X^n, Y^n)$ being pairs of independent and identically distributed binary random vectors, we similarly define $\underline{h}_n(P_{X^nY^n}, ε)$ under the assumption that $Z^n$ is also a binary vector. Then we obtain a closed form expression for $\underline{h}_n(P_{X^nY^n}, ε)$ for sufficiently large, but nontrivial values of $ε$.

DOI
10.48550/arxiv.1704.03606

Related papers

Privacy-aware guessing efficiency

Shahab Asoodeh, Mario Díaz, Fady Alajaji +1 more

We investigate the problem of guessing a discrete random variable Y under a privacy constraint dictated by another correlated discrete random variable X, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define h(PXY,ε) as the maximum probability of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Yensuring that the probability of correctly guessing X given Z does not exceed ε. We show that the map ε → h(PXY,ε) is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for h(PxY,ε) when X and Y are connected via a binary-input binary-output channel. For {(Xi, Yi)}ni=1being pairs of independent and identically distributed binary random vectors, we similarly define h_n(PX n Y n, ε) under the assumption that Znis also a binary vector. Then we obtain a closed form expression for h_n(PX n Y n, ε) for sufficiently large, but nontrivial values of ε.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•21 citations

Maximal Guesswork Leakage

Gowtham R. Kurri, Malhar A. Managoli, Vinod M. Prabhakaran

We study information leakage through guesswork, the minimum expected number of guesses required to guess a random variable. In particular, we define maximal guesswork leakage as the multiplicative decrease, upon observing$Y$, of the guesswork of a randomized function of$X$, maximized over all such randomized functions. We also study a pointwise form of the leakage which captures the leakage due to the release of a single realization of$Y$. We also study these two notions of leakage with oblivious (or memoryless) guessing. We obtain closed-form expressions for all these leakage measures, with the exception of one. Specifically, we are able to obtain closed-form expression for maximal guesswork leakage for the binary erasure source only; deriving expressions for arbitrary sources appears challenging. Some of the consequences of our results are - a connection between guesswork and differential privacy and a new operational interpretation to maximal$\alpha$-leakage in terms of guesswork.

arXiv:2405.02585•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•3 citations

An operational measure of information leakage

Ibrahim Issa, Sudeep Kamath, Aaron B. Wagner

Given two discrete random variables X and Y, an operational approach is undertaken to quantify the “leakage” of information from X to Y. The resulting measure ℒ(X→Y ) is called maximal leakage, and is defined as the multiplicative increase, upon observing Y, of the probability of correctly guessing a randomized function of X, maximized over all such randomized functions. It is shown to be equal to the Sibson mutual information of order infinity, giving the latter operational significance. Its resulting properties are consistent with an axiomatic view of a leakage measure; for example, it satisfies the data processing inequality, it is asymmetric, and it is additive over independent pairs of random variables. Moreover, it is shown that the definition is robust in several respects: allowing for several guesses or requiring the guess to be only within a certain distance of the true function value does not change the resulting measure.

Conference on Information Sciences and Systems•Mar 1, 2016•113 citations

On Perfect Privacy

Borzoo Rassouli, Denız Gündüz

For a pair of (dependent) random variables (X, Y), the following problem is addressed: What is the maximum information that can be revealed about Y, while disclosing no information about X? Assuming that a Markov kernel maps Y to the revealed information U, it is shown that the maximum mutual information between Y and U, i.e., I(Y; U), can be obtained as the solution of a standard linear program, when X and U are required to be independent, called perfect privacy. The resulting quantity is shown to be greater than or equal to the non-private information about X carried by Y. For jointly Gaussian (X, Y), it is shown that perfect privacy is not possible if the kernel is applied to only Y; whereas perfect privacy can be achieved if the mapping is from both X and Y; that is, if the private variables can also be observed at the encoder. Finally, it is shown that when Y is not a deterministic function of X, perfect privacy is always feasible when the mapping has access to both X and Y1.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•21 citations

Communication with secrecy constraints

Alon Orlitsky, Abbas El Gamal

Let x, y, z be finite sets, X,Y random variables uniformly distributed over x×y, f a function from x×y to Z and 0≤ε&le1. A person PX knows X and a person PY knows Y and they want to exchange X and Y. An eavesdropper who knows their protocol listens to their communication in order to obtain information about f(X, Y). PX and PY want to ensure that for every value (x,y) of (X,Y) the eavesdropper's a priori and a posteriori probabilities of {f(X,Y)=j} are ε-close for all j. Therefore, they encrypt some of the transmitted bits. The problem is to find a protocol that minimizes the number of bits encrypted in the worst case. Two kinds of protocols are considered: deterministic and randomized.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1984•25 citations

Secure computation of randomized functions: Further results

Deepesh Data, Vinod M. Prabhakaran

We consider secure computation of randomized functions by two users, where both the users (Alice and Bob) have inputs, Alice sends a message to Bob over a rate-limited, noise-free link, and then Bob produces the output. We study this problem when privacy is required only against Bob, i.e., from the message, Bob must not learn any information about Alice's input other than what can be inferred by his own input and output. We give a single-letter expression for the optimal rate. We also explicitly characterize securely computable randomized functions when input has full support, which leads to a much simpler expression for the optimal rate. Recently, Data (ISIT 2016) studied the other two cases (first, when privacy is required against both the users; and second, when privacy is required only against Alice) and obtained single-letter expressions for optimal rates in both the scenarios. Yassaee, Gohari, and Aref (IEEE Transactions on Information Theory 2015) studied the case when there is no privacy requirement and obtained a single-letter expression for the optimal rate, when Alice and Bob interact for arbitrary but finite number of rounds, and both of them may produce potentially different outputs.

arXiv:1705.07081•IEEE Information Theory Workshop (ITW)•Nov 1, 2017•1 citation
We investigate the problem of guessing a discrete random variable YYY under a privacy constraint dictated by another correlated discrete random variable XXX, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define h(PXY,ε)h(P_{XY}, ε)h(PXY​,ε) as the maximum probability of correctly guessing YYY given an auxiliary random variable ZZZ, where the maximization is taken over all PZ∣YP_{Z|Y}PZ∣Y​ ensuring that the probability of correctly guessing XXX given ZZZ does not exceed εεε. We show that the map ε↦h(PXY,ε)ε\mapsto h(P_{XY}, ε)ε↦h(PXY​,ε) is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for h(PXY,ε)h(P_{XY}, ε)h(PXY​,ε) when XXX and YYY are connected via a binary-input binary-output channel. For (Xn,Yn)(X^n, Y^n)(Xn,Yn) being pairs of independent and identically distributed binary random vectors, we similarly define h‾n(PXnYn,ε)\underline{h}_n(P_{X^nY^n}, ε)h​n​(PXnYn​,ε) under the assumption that ZnZ^nZn is also a binary vector. Then we obtain a closed form expression for h‾n(PXnYn,ε)\underline{h}_n(P_{X^nY^n}, ε)h​n​(PXnYn​,ε) for sufficiently large, but nontrivial values of εεε.
We investigate the problem of guessing a discrete random variable Y under a privacy constraint dictated by another correlated discrete random variable X, where both guessing efficiency and privacy are assessed in terms of the probability of correct guessing. We define h(PXY,ε) as the maximum probability of correctly guessing Y given an auxiliary random variable Z, where the maximization is taken over all PZ|Yensuring that the probability of correctly guessing X given Z does not exceed ε. We show that the map ε → h(PXY,ε) is strictly increasing, concave, and piecewise linear, which allows us to derive a closed form expression for h(PxY,ε) when X and Y are connected via a binary-input binary-output channel. For {(Xi, Yi)}ni=1being pairs of independent and identically distributed binary random vectors, we similarly define h_n(PX n Y n, ε) under the assumption that Znis also a binary vector. Then we obtain a closed form expression for h_n(PX n Y n, ε) for sufficiently large, but nontrivial values of ε.
We study information leakage through guesswork, the minimum expected number of guesses required to guess a random variable. In particular, we define maximal guesswork leakage as the multiplicative decrease, upon observingYYY, of the guesswork of a randomized function ofXXX, maximized over all such randomized functions. We also study a pointwise form of the leakage which captures the leakage due to the release of a single realization ofYYY. We also study these two notions of leakage with oblivious (or memoryless) guessing. We obtain closed-form expressions for all these leakage measures, with the exception of one. Specifically, we are able to obtain closed-form expression for maximal guesswork leakage for the binary erasure source only; deriving expressions for arbitrary sources appears challenging. Some of the consequences of our results are - a connection between guesswork and differential privacy and a new operational interpretation to maximalα\alphaα-leakage in terms of guesswork.
Given two discrete random variables X and Y, an operational approach is undertaken to quantify the “leakage” of information from X to Y. The resulting measure ℒ(X→Y ) is called maximal leakage, and is defined as the multiplicative increase, upon observing Y, of the probability of correctly guessing a randomized function of X, maximized over all such randomized functions. It is shown to be equal to the Sibson mutual information of order infinity, giving the latter operational significance. Its resulting properties are consistent with an axiomatic view of a leakage measure; for example, it satisfies the data processing inequality, it is asymmetric, and it is additive over independent pairs of random variables. Moreover, it is shown that the definition is robust in several respects: allowing for several guesses or requiring the guess to be only within a certain distance of the true function value does not change the resulting measure.
For a pair of (dependent) random variables (X, Y), the following problem is addressed: What is the maximum information that can be revealed about Y, while disclosing no information about X? Assuming that a Markov kernel maps Y to the revealed information U, it is shown that the maximum mutual information between Y and U, i.e., I(Y; U), can be obtained as the solution of a standard linear program, when X and U are required to be independent, called perfect privacy. The resulting quantity is shown to be greater than or equal to the non-private information about X carried by Y. For jointly Gaussian (X, Y), it is shown that perfect privacy is not possible if the kernel is applied to only Y; whereas perfect privacy can be achieved if the mapping is from both X and Y; that is, if the private variables can also be observed at the encoder. Finally, it is shown that when Y is not a deterministic function of X, perfect privacy is always feasible when the mapping has access to both X and Y1.
Let x, y, z be finite sets, X,Y random variables uniformly distributed over x×y, f a function from x×y to Z and 0≤ε&le1. A person PX knows X and a person PY knows Y and they want to exchange X and Y. An eavesdropper who knows their protocol listens to their communication in order to obtain information about f(X, Y). PX and PY want to ensure that for every value (x,y) of (X,Y) the eavesdropper's a priori and a posteriori probabilities of {f(X,Y)=j} are ε-close for all j. Therefore, they encrypt some of the transmitted bits. The problem is to find a protocol that minimizes the number of bits encrypted in the worst case. Two kinds of protocols are considered: deterministic and randomized.
We consider secure computation of randomized functions by two users, where both the users (Alice and Bob) have inputs, Alice sends a message to Bob over a rate-limited, noise-free link, and then Bob produces the output. We study this problem when privacy is required only against Bob, i.e., from the message, Bob must not learn any information about Alice's input other than what can be inferred by his own input and output. We give a single-letter expression for the optimal rate. We also explicitly characterize securely computable randomized functions when input has full support, which leads to a much simpler expression for the optimal rate. Recently, Data (ISIT 2016) studied the other two cases (first, when privacy is required against both the users; and second, when privacy is required only against Alice) and obtained single-letter expressions for optimal rates in both the scenarios. Yassaee, Gohari, and Aref (IEEE Transactions on Information Theory 2015) studied the case when there is no privacy requirement and obtained a single-letter expression for the optimal rate, when Alice and Bob interact for arbitrary but finite number of rounds, and both of them may produce potentially different outputs.