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:2405.02585 · IEEE International Symposium on Information Theory (ISIT)

Maximal Guesswork Leakage

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

Published Jul 7, 2024• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit57864.2024.10619300

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(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 $ε$.

arXiv:1704.03606•Apr 12, 2017•1 citation

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

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 quantum leakage: operational interpretation and quantum channel analysis

Shuixin Xiao, Zijia Zhao, Jingge Zhu +1 more

Maximal quantum leakage quantifies privacy against adversaries with arbitrary intentions. In this work, we prove that computing this leakage is equivalent to minimum-error quantum state discrimination with equal priors. This establishes a computable operational interpretation, addressing the previous difficulty in computing maximal quantum leakage. We further analyze the impact of collective measurements on multiple copies of a state, demonstrating that leakage increases monotonically with the number of copies, which leads to explicitly characterizing the maximal leakage in the asymptotic limit. Extending this framework to quantum channels, we develop an iterative algorithm for the jointly designing of input states and measurements. Numerical examples involving collective measurements and the maximal channel leakage demonstrate our theoretical findings.

quant-pharXiv:2607.15853•Jul 20, 2026•0 citations

Measuring Information Leakage in Non-stochastic Brute-Force Guessing

Farhad Farokhi, Ni Ding

We propose an operational measure of information leakage in a non-stochastic setting to formalize privacy against a brute-force guessing adversary. We use uncertain variables, non-probabilistic counterparts of random variables, to construct a guessing framework in which an adversary is interested in determining private information based on uncertain reports. We consider brute-force trial-and-error guessing in which an adversary can potentially check all the possibilities of the private information that are compatible with the available outputs to find the actual private realization. The ratio of the worst-case number of guesses for the adversary in the presence of the output and in the absence of it captures the reduction in the adversary’s guessing complexity and is thus used as a measure of private information leakage. We investigate the relationship between the newly-developed measure of information leakage with maximin information and stochastic maximal leakage that are shown to arise in one-shot guessing.

arXiv:2004.10911•IEEE Information Theory Workshop (ITW)•Apr 11, 2021•10 citations

Guesswork with Quantum Side Information: Optimal Strategies and Aspects of Security

Eric P. Hanson, Vishal Katariya, Nilanjana Datta +1 more

What is the minimum number of guesses needed on average to correctly guess a realization of a random variable? The answer to this question led to the introduction of the notion of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single quantum measurement and choosing a guessing strategy based on the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, and we prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•0 citations
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.
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 εεε.
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.
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 ε.
Maximal quantum leakage quantifies privacy against adversaries with arbitrary intentions. In this work, we prove that computing this leakage is equivalent to minimum-error quantum state discrimination with equal priors. This establishes a computable operational interpretation, addressing the previous difficulty in computing maximal quantum leakage. We further analyze the impact of collective measurements on multiple copies of a state, demonstrating that leakage increases monotonically with the number of copies, which leads to explicitly characterizing the maximal leakage in the asymptotic limit. Extending this framework to quantum channels, we develop an iterative algorithm for the jointly designing of input states and measurements. Numerical examples involving collective measurements and the maximal channel leakage demonstrate our theoretical findings.
We propose an operational measure of information leakage in a non-stochastic setting to formalize privacy against a brute-force guessing adversary. We use uncertain variables, non-probabilistic counterparts of random variables, to construct a guessing framework in which an adversary is interested in determining private information based on uncertain reports. We consider brute-force trial-and-error guessing in which an adversary can potentially check all the possibilities of the private information that are compatible with the available outputs to find the actual private realization. The ratio of the worst-case number of guesses for the adversary in the presence of the output and in the absence of it captures the reduction in the adversary’s guessing complexity and is thus used as a measure of private information leakage. We investigate the relationship between the newly-developed measure of information leakage with maximin information and stochastic maximal leakage that are shown to arise in one-shot guessing.
What is the minimum number of guesses needed on average to correctly guess a realization of a random variable? The answer to this question led to the introduction of the notion of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single quantum measurement and choosing a guessing strategy based on the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, and we prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion.