Is there bound information? – Open Quantum Problems

Cite this problem as Problem 47.

Problem

Consider the following cryptographic scenario, known as secret key agreement [1]. A source distributes an i.i.d. stream of correlated triples of random variables with distribution $P(x,y,z)$ , which are accessible to Alice, Bob, and Eve, respectively. It is the task for Alice and Bob by public discussion to convert their symbols with high probability into a rate of perfectly random bits that are unknown to Eve. The rate at which this is possible is called the secret key rate of $P$ . Conversely, one may also define the rate of secret key cost (a.k.a. information of formation), by which we mean the rate of secret bits required for Alice and Bob to create, with high probability, a stream of symbols $x_i$ and $y_i$ , respectively, such that Eve learns from the communication transcript less than when she had access to $z_i$ . Importantly, $x_i, y_i, z_i$ are i.i.d. distributed according to $P$ [2].

Between the secret key rate and the secret key cost lie the intrinsic information [3] and the smaller reduced intrinsic information [2]. Since it is sometimes strictly smaller, we know that there can be a gap between the secret key rate and the secret key cost. Until here the situation is entirely analogous to the situation in entanglement theory, where we know that distillable entanglement can be strictly smaller than entanglement cost. Using the PPT criterion, one can even show the extreme situation, where distillable entanglement vanishes, yet entanglement cost stays strictly positive. States with this property are called bound entangled.

The problem of bound information is now the question of whether there is a distribution $P$ such that the secret key rate is zero yet the secret key cost is strictly positive. This would be a classical secrecy analog to the aforementioned phenomenon of bound entanglement. And indeed, rather intriguingly, there are candidate distributions inspired by bound entangled states [4].

The analogy between secret key agreement and entanglement distillation has also been fruitful in the other direction. It led, for example, to the introduction to squashed entanglement in analogy to the intrinsic information [5].

References

[1] U. M. Maurer, Secret key agreement by public discussion from common information, IEEE Trans. Inf. Theory 39(3), 733-742 (1993).

[2] R. Renner and S. Wolf, New bounds in secret-key agreement: the gap between formation and secrecy extraction. In Advances in Cryptology — EUROCRYPT 2003, 562-577 (2003). See also https://crypto.ethz.ch/publications/files/RenWol03.pdf.

[3] U. M. Maurer and S. Wolf, Unconditionally secure key agreement and the intrinsic conditional information, IEEE Trans. Inf. Theory 45(2), 499-514 (1999).

[4] N. Gisin and S. Wolf, Linking classical and quantum key agreement: is there “bound information”? In Advances in Cryptology — CRYPTO 2000, 482-500 (2000). See also arXiv:quant-ph/0005042.

[5] M. Christandl and A. Winter, Squashed entanglement: an additive entanglement measure, J. Math. Phys. 45(3) 829-840 (2004) and arXiv:quant-ph/0308088.