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

IEEE International Symposium on Information Theory (ISIT)

On Perfect Privacy

Borzoo Rassouli, Denız Gündüz

Published Jun 1, 2018• 21 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2018.8437481

Related papers

Mutual Information as Privacy-Loss Measure in Strategic Communication

Farhad Farokhi, Girish N. Nair

A game is introduced to study the effect of privacy in strategic communication between well-informed senders and a receiver. The receiver wants to accurately estimate a random variable. The sender, however, wants to communicate a message that balances a trade-off between providing an accurate measurement and minimizing the amount of leaked private information, which is assumed to be correlated with the to-be-estimated variable. The mutual information between the transmitted message and the private information is used as a measure of the amount of leaked information. An equilibrium is constructed and its properties are investigated.

arXiv:1509.05502•Sep 18, 2015•0 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(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

How to securely compute the modulo-two sum of binary sources

Deepesh Data, Bikash Kumar Dey, Manoj Mishra +1 more

In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of Körner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of Data et al. (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in blocklength, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.

arXiv:1405.2555•IEEE Information Theory Workshop (ITW)•Nov 1, 2014•9 citations

A no-go theorem for privacy in distributed sensing using Gaussian states

Jason L. Pereira, Damian Markham

In the discrete variable setting, entangled resource states allow a set of parties to learn a global function of a set of spatially separated systems, whilst keeping the local parameters of those systems completely private. In the continuous variable setting, distributed sensing has been carried out using Gaussian resource states, but without the same guarantees about privacy. Here, we show that perfect privacy is impossible to achieve for any distributed sensing protocol that uses Gaussian states as a resource. We also introduce a measure of relative privacy, bounding the degree to which any Gaussian distributed sensing protocol can keep local parameters hidden.

quant-pharXiv:2606.23796•Jun 24, 2026•0 citations

On the randomness requirements for privacy

Carl Bosley

Most cryptographic primitives require randomness (for example, to generate secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be achievable for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness? We completely resolve this question for information-theoretic private-key encryption, where parties wish to encrypt a b-bit value using a shared secret key sampled from some imperfect source of randomness [special characters omitted]. Our main result shows that if such n-bit source [special characters omitted] allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from [special characters omitted]. Further, the restriction that b > log n is nearly tight: there exist sources [special characters omitted] allowing one to perfectly encrypt (log n – loglog n) bits, but not to deterministically extract even a single slightly unbiased bit. Hence, to a large extent, true randomness is inherent for encryption : either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, the one-time pad scheme is essentially "universal". Our technique also extends to related primitives which are sufficiently binding and hiding, including computationally secure commitments and public-key encryption.

•Jan 1, 2010•0 citations

Revealing Additional Information in Two-Party Computations ⋆

Andreas Jakoby

Abstract. A two-argument function is computed privately by two parties if after the computation, no party should know anything about the other inputs except for what he is able to deduce from his own input and the function value. In [1] Bar-Yehuda, Chor, Kushilevitz, and Orlitsky give a complete characterisation of two-argument functions which can be computed privately (in the information-theoretical sense) in the Honest-But-Curious model and study protocols for “non-private ” functions revealing as little information about the inputs as possible. The authors define a measure which determines for any function f the additional information E(f) required for computing f and claim that f is privately-computable if and only if E(f) = 0. In our paper we show that the characterisation is false: we give a privately-computable function f with E(f) = 0 and another function g with E(g) =0thatisnot privately-computable. Moreover, we show some rather unexpected and strange properties of the measure for additional information given by Bar-Yehuda et al. and we introduce an alternative measure. We show that for this new measure the minimal leakage of information of randomized and deterministic protocols are equal. Finally, we present some general relations between the information gain of an optimal protocol and the communication complexity of a function. 1

•Jan 29, 2014•0 citations
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.
A game is introduced to study the effect of privacy in strategic communication between well-informed senders and a receiver. The receiver wants to accurately estimate a random variable. The sender, however, wants to communicate a message that balances a trade-off between providing an accurate measurement and minimizing the amount of leaked private information, which is assumed to be correlated with the to-be-estimated variable. The mutual information between the transmitted message and the private information is used as a measure of the amount of leaked information. An equilibrium is constructed and its properties are investigated.
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 εεε.
In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of Körner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of Data et al. (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in blocklength, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.
In the discrete variable setting, entangled resource states allow a set of parties to learn a global function of a set of spatially separated systems, whilst keeping the local parameters of those systems completely private. In the continuous variable setting, distributed sensing has been carried out using Gaussian resource states, but without the same guarantees about privacy. Here, we show that perfect privacy is impossible to achieve for any distributed sensing protocol that uses Gaussian states as a resource. We also introduce a measure of relative privacy, bounding the degree to which any Gaussian distributed sensing protocol can keep local parameters hidden.
Most cryptographic primitives require randomness (for example, to generate secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be achievable for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness? We completely resolve this question for information-theoretic private-key encryption, where parties wish to encrypt a b-bit value using a shared secret key sampled from some imperfect source of randomness [special characters omitted]. Our main result shows that if such n-bit source [special characters omitted] allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from [special characters omitted]. Further, the restriction that b > log n is nearly tight: there exist sources [special characters omitted] allowing one to perfectly encrypt (log n – loglog n) bits, but not to deterministically extract even a single slightly unbiased bit. Hence, to a large extent, true randomness is inherent for encryption : either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, the one-time pad scheme is essentially "universal". Our technique also extends to related primitives which are sufficiently binding and hiding, including computationally secure commitments and public-key encryption.
Abstract. A two-argument function is computed privately by two parties if after the computation, no party should know anything about the other inputs except for what he is able to deduce from his own input and the function value. In [1] Bar-Yehuda, Chor, Kushilevitz, and Orlitsky give a complete characterisation of two-argument functions which can be computed privately (in the information-theoretical sense) in the Honest-But-Curious model and study protocols for “non-private ” functions revealing as little information about the inputs as possible. The authors define a measure which determines for any function f the additional information E(f) required for computing f and claim that f is privately-computable if and only if E(f) = 0. In our paper we show that the characterisation is false: we give a privately-computable function f with E(f) = 0 and another function g with E(g) =0thatisnot privately-computable. Moreover, we show some rather unexpected and strange properties of the measure for additional information given by Bar-Yehuda et al. and we introduce an alternative measure. We show that for this new measure the minimal leakage of information of randomized and deterministic protocols are equal. Finally, we present some general relations between the information gain of an optimal protocol and the communication complexity of a function. 1