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•22 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•116 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•28 citations

Secret-Key Agreement Using Physical Identifiers for Degraded and Less Noisy Authentication Channels

Vamoua Yachongka, Hideki Yagi, Hideki Ochiai

Secret-key agreement based on biometric or physical identifiers is a promising security protocol for authenticating users or devices with small chips and has been extensively studied recently. Kittichokechai and Caire (2015) investigated the optimal trade-off in a secret-key agreement model with physical identifiers, where the structure of the authentication channels is similar to the wiretap channels, from information theoretic approaches. Later, the model was extended by Günlü et al. (2018) introducing noise in the enrollment phase and cost-constrained actions at the decoder. The results of these studies show that two auxiliary random variables are involved in the expressions of the optimal rate regions of secret-key, storage, and privacy-leakage rates. However, with these two auxiliary random variables, the complexity of computing the rate region may be prohibitively high. Due to this problem, we are interested in exploring classes of authentication channels that need only one auxiliary random variable in the capacity region expression for discrete source settings. The result shows for the class of degraded and less noisy authentication channels, a single auxiliary random variable is sufficient to express the capacity region of the model. As an example, we also derive the capacity region of secret-key, storage, and privacy-leakage rates for binary sources. Furthermore, the capacity region for scalar Gaussian sources is derived under Gaussian authentication channels.

arXiv:2208.10478•IEEE Information Theory Workshop (ITW)•Nov 1, 2022•3 citations
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.
Secret-key agreement based on biometric or physical identifiers is a promising security protocol for authenticating users or devices with small chips and has been extensively studied recently. Kittichokechai and Caire (2015) investigated the optimal trade-off in a secret-key agreement model with physical identifiers, where the structure of the authentication channels is similar to the wiretap channels, from information theoretic approaches. Later, the model was extended by Günlü et al. (2018) introducing noise in the enrollment phase and cost-constrained actions at the decoder. The results of these studies show that two auxiliary random variables are involved in the expressions of the optimal rate regions of secret-key, storage, and privacy-leakage rates. However, with these two auxiliary random variables, the complexity of computing the rate region may be prohibitively high. Due to this problem, we are interested in exploring classes of authentication channels that need only one auxiliary random variable in the capacity region expression for discrete source settings. The result shows for the class of degraded and less noisy authentication channels, a single auxiliary random variable is sufficient to express the capacity region of the model. As an example, we also derive the capacity region of secret-key, storage, and privacy-leakage rates for binary sources. Furthermore, the capacity region for scalar Gaussian sources is derived under Gaussian authentication channels.