Formalize Open Quantum Problem #47: Is there bound information?

[MarioKrenn6240]

What is the conjecture

This is problem #47 in the Open Quantum Problems collection.

Problem (Open Quantum Problem #47: “Is there bound information?”).
In the standard secret-key-agreement source model, Alice, Bob, and Eve observe i.i.d. samples of jointly distributed random variables (X,Y,Z).
Alice and Bob may use local processing and authenticated public discussion, observed by Eve, to distill a shared secret key.
Does there exist a distribution P_{XYZ} such that the optimal asymptotic secret key rate is 0, but the secret key cost / information of formation is strictly positive?

A standard finite-alphabet formalization is in terms of asymptotic resource conversion of i.i.d. classical correlations:

• Let P_{XYZ} be a joint distribution of finite random variables (X,Y,Z).
  Alice, Bob, and Eve receive n i.i.d. samples
  (X^n,Y^n,Z^n) ~ P_{XYZ}^{⊗ n}.

• Alice and Bob are allowed local operations and public communication (LOPC):
  local random processing plus authenticated two-way public messages, all of which are available to Eve.

• The secret key rate S(X;Y || Z) is the supremum of all rates R for which Alice and Bob can, from P_{XYZ}^{⊗ n}, produce keys K_A,K_B ∈ {0,1}^{⌊Rn⌋} such that
  Pr[K_A = K_B] → 1,
  the key is asymptotically uniform,
  and it is asymptotically independent of Eve’s total view (her side information Z^n together with the full public transcript).

• The information of formation I_form(X;Y | Z) (often called the secret key cost) is the infimum of all rates R such that, given ⌈Rn⌉ pre-shared secret bits, Alice and Bob can use LOPC to generate outputs (X'^n,Y'^n) whose joint law is asymptotically that of P_{XY}^{⊗ n}, with a public transcript C that can be simulated from Z^n, so that Eve learns no more from the protocol than in the original source model.

Then the bound-information question becomes:

• Main open question (two honest parties / bipartite secrecy): does there exist a distribution P_{XYZ} such that
  S(X;Y || Z) = 0
  but
  I_form(X;Y | Z) > 0?

Equivalently, do there exist secret correlations that cannot be created by LOPC alone, yet from which no secret key can be distilled?

Two standard intermediate quantities are:

• the intrinsic information
  I(X;Y ↓ Z) := inf_{Z → \bar Z} I(X;Y | \bar Z),
• the reduced intrinsic information I(X;Y ↓↓ Z).

They satisfy the standard bounds

• S(X;Y || Z) ≤ I(X;Y ↓↓ Z) ≤ I(X;Y ↓ Z) ≤ I_form(X;Y | Z).

So the problem asks whether the separation between extraction and formation can be pushed all the way to the extreme case 0 < I_form while S = 0 for a single bipartite source.

There are two important nearby facts to keep distinct from the open question:

• Renner–Wolf proved an asymptotic separation: there are sequences of distributions for which the secret key rate tends to 0 while the intrinsic information stays bounded away from 0. This shows an arbitrarily large gap between formation-type and extraction-type quantities, but does not yet exhibit a single distribution with S=0 < I_form.

• Multipartite bound information is known to exist: with three honest parties and an eavesdropper there are explicit distributions that are non-distillable yet cannot be created by LOPC. The present OQP problem is specifically the unresolved Alice–Bob–Eve (2 honest parties) case.

A natural related sub-problem is:

• Determine whether explicit bipartite candidate distributions obtained from measurements on known bound-entangled states really satisfy S(X;Y || Z)=0, and whether any such bipartite bound information can be activated by combining several resources.

Where to find the details / references

Primary sources:

• Open Quantum Problems site (Problem #47)
• Open Quantum Problems master list (for numbering/metadata)
• N. Gisin and S. Wolf, “Linking classical and quantum key agreement: is there ‘bound information’?” (CRYPTO 2000):
  https://arxiv.org/abs/quant-ph/0005042

Key related references (including the ones listed on the OQP page):

• U. M. Maurer, “Secret key agreement by public discussion from common information” (IEEE Trans. Inf. Theory 39(3), 733–742 (1993))
  (introduces the basic source model of secret-key agreement by public discussion)
• U. M. Maurer and S. Wolf, “Unconditionally secure key agreement and the intrinsic conditional information” (IEEE Trans. Inf. Theory 45(2), 499–514 (1999))
  (introduces intrinsic information and its role as an upper bound on distillable secret key)
• R. Renner and S. Wolf, “New bounds in secret-key agreement: the gap between formation and secrecy extraction” (EUROCRYPT 2003, 562–577 (2003))
  (introduces reduced intrinsic information and information of formation, and proves asymptotic gaps between extraction and formation)
• N. Gisin, R. Renner, and S. Wolf, “Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?” (Algorithmica 34, 389–412 (2002))
  (expanded journal version of the original bound-information work)
• A. Acín, J. I. Cirac, and Ll. Masanes, “Multipartite Bound Information exists and can be activated” (Phys. Rev. Lett. 92, 107903 (2004); arXiv: quant-ph/0311064)
  (proves the multipartite analogue, clarifying that the open case is the bipartite one)
• G. Prettico and A. Acín, “Can bipartite classical information resources be activated?” (arXiv: 1203.1445)
  (gives evidence for bipartite candidates and activation phenomena, without resolving the existence question)
• M. Ozols, G. Smith, and J. A. Smolin, “Bound entangled states with private key and their classical counterpart” (Phys. Rev. Lett. 112, 110502 (2014); arXiv: 1305.0848)
  (constructs a different classical analogue of bound entanglement, distinct from the long-sought bipartite bound information)
• M. Christandl and A. Winter, “Squashed entanglement: an additive entanglement measure” (J. Math. Phys. 45(3), 829–840 (2004); arXiv: quant-ph/0308088)
  (introduced on the quantum side in direct analogy with intrinsic information)

(For writing the issue, the OQP page plus Maurer/Wolf and Renner/Wolf are probably the core references. Acín–Cirac–Masanes and Prettico–Acín are useful to make the current status completely clear.)

Prerequisites needed

• Classical information theory: discrete random variables, joint/conditional distributions, entropy, mutual information, conditional mutual information
• Asymptotic i.i.d. source models and rate notions
• Secret-key agreement by public discussion / LOPC, including correctness and secrecy criteria
• Intrinsic information and reduced intrinsic information; information of formation / secret key cost
• (Optional) Quantum-information analogy: distillable entanglement vs entanglement cost, bound entanglement, and how these motivate the conjecture

AMS categories

• ams-94 (Information and communication, circuits)
• ams-81 (Quantum theory)
• ams-68 (Computer science)
• ams-60 (Probability theory and stochastic processes)

Choose either option

• I plan on adding this conjecture to the repository
• This issue is up for grabs: I would like to see this conjecture added by somebody else

---