Royal Society Publishing

The locking-decoding frontier for generic dynamics

Frédéric Dupuis , Jan Florjanczyk , Patrick Hayden , Debbie Leung

Abstract

It is known that the maximum classical mutual information, which can be achieved between measurements on pairs of quantum systems, can drastically underestimate the quantum mutual information between them. In this article, we quantify this distinction between classical and quantum information by demonstrating that after removing a logarithmic-sized quantum system from one half of a pair of perfectly correlated bitstrings, even the most sensitive pair of measurements might yield only outcomes essentially independent of each other. This effect is a form of information locking but the definition we use is strictly stronger than those used previously. Moreover, we find that this property is generic, in the sense that it occurs when removing a random subsystem. As such, the effect might be relevant to statistical mechanics or black hole physics. While previous works had always assumed a uniform message, we assume only a min-entropy bound and also explore the effect of entanglement. We find that classical information is strongly locked almost until it can be completely decoded. Finally, we exhibit a quantum key distribution protocol that is ‘secure’ in the sense of accessible information but in which leakage of even a logarithmic number of bits compromises the secrecy of all others.

1. Introduction

One of the most basic and intuitive properties of most information measures is that the amount of information carried by a physical system must be bounded by its size. For example, if one receives 10 physical bits, then one's information, regardless of what that information is ‘about’, should not increase by more than 10 bits. While this is true for most information measures, in quantum mechanics, there exist natural ways of measuring information that violate this principle by a wide margin. In particular, this violation occurs when one defines the information contained in a quantum system as the amount of classical information that can be extracted by the best possible measurement. To construct examples of this effect, we take a classical message and encode it into a two-part quantum message: a cyphertext, which is roughly as large as the message, and a much smaller key. Given both the cyphertext and the key, the message can be perfectly retrieved. We can then look at the amount of information that can be extracted about the message by a measurement given only access to the cyphertext. Locking occurs if this amount of information is less than the amount of information in the message minus the size of the key.

In previous work on locking [1,2], this amount of information was taken to be the accessible information, the maximum (classical) mutual information between the message and the result of a measurement. DiVincenzo et al. [1] constructed the first example of locking as follows: the cyphertext consists of the uniformly random message, encoded in one of two mutually unbiased bases and the (one-bit) key reveals the basis in which the encoding was done. In this example, given only the cyphertext, the classical mutual information is only n/2 for an n-bit message. Hence, the one-bit key can increase the classical mutual information by another n/2 bits. Hayden et al. [2] considered a protocol in which one encodes a classical message using a fixed basis, and then applies one of k fixed unitaries (where Embedded Image); the classical key reveals which unitary was applied. If the unitaries are chosen according to the Haar measure, then with high probability, the accessible information was shown to be at most εn when one only has the cyphertext.

In this paper, we present stronger and more general locking results and show that this effect is generic. Our results will be stronger in the sense that instead of using the accessible information, we will define locking in terms of the trace distance between measurement results on the real state and measurement results on a state completely independent of the message (see definition 2.4). Unlike the accessible information, this has a very natural operational interpretation: it bounds the largest probability with which we can guess, given a message m and the result x of a measurement done on a cyphertext, whether x comes from a valid cyphertext for m or from a cyphertext generated independently of m. In other words, one could almost perfectly reproduce any measurement results made on a valid cyphertext without having access to the cyphertext at all. Moreover, we recover a strengthened version of the earlier statements about the accessible information. Whereas previously the accessible information was shown to be at most 3 bits, our techniques show that the accessible information can be made arbitrarily small. A very good review of previous results can be found in table 1 of [3]. That paper also strengthened the definition and explored connections to low-distortion embeddings.

Despite this stronger definition, we will be able to show that the locking phenomenon is generic. Instead of having a classical key reveal the basis in which the information is encoded, as in [1,2], we consider the case where there is a single unitary, and the key is simply a small part of the quantum system after the unitary is applied.1 This means that we can make not only cryptographic statements, but also statements about the dynamics of physical systems, where the unitary represents the evolution of the system. In particular, we will be able to show that locking occurs with high probability in physical systems whose internal dynamics are sufficiently generic to be adequately modelled by a Haar-distributed unitary. This can therefore give interesting results in the context of thermodynamics, or of the black hole information problem.

In that vein, we will also allow the measuring device to share entanglement with the cyphertext-key compound system. While this may not correspond to a very meaningful cryptographic scenario, it allows us to study the behaviour of entanglement in physical systems, and to study the extent to which the presence of entanglement interferes with this locking effect.

Finally, in contrast to previous studies, we will not limit the message (or the entanglement) to be uniform; the size of the key will instead depend on the min-entropy of the message. This assumption is easier to justify in cryptographic applications. Indeed, while the locking results we present here can be interpreted as demonstrating the possibility of encrypting classical messages in quantum systems using only very small keys, care must be taken when composing such encryption with other protocols. We use our results to exhibit a quantum key distribution protocol, for example, that appears to be secure if the eavesdropper's information about the secret key is measured using the accessible information, but in which leakage of a logarithmic amount of key causes the entire key to be compromised.

(a) Transmitting information through a generic unitary

To end the introduction, we introduce the physical scenario that will occupy us throughout the article. The situation is depicted in figure 1.

Figure 1.

A quantum circuit depicting the physical scenario. The classical message M gets encoded in N, and the unitary then mixes it with the E part of the pure shared entanglement state ω. If the information is locked, any joint measurement Embedded Image on C and E′ will yield a result X that is almost independent of the message. On the other hand, if C is large enough, there will be a joint measurement Embedded Image reliably decoding M.

Now, let Embedded Image be any orthonormal basis for N. The analysis will focus on the properties of the states Embedded Image1.1and Embedded Image1.2

Our objective is to demonstrate that until C is large enough that there exists a measurement on CE′ capable of revealing all the information about the message M, no measurement will reveal any information about the message. This cannot quite be true, of course, so what we will demonstrate is that the jump from no information to complete information involves enlarging C by a number of qubits logarithmic in the size of the message M and the amount of entanglement E.

For example, assume for simplicity that M is uniformly distributed and that the state ωEE is maximally entangled. As a first step, it is necessary to determine how large C needs to be in order for there to exist a measurement on CE′ that will reveal the message M. Begin by purifying the state σ to Embedded Image1.3Even more demanding than performing a measurement to reveal m is the task of transmitting the quantum information about RM through U, allowing the decoder, who has access only to CE′, to recover a high fidelity copy of the state |σRMN. If U is selected according to the Haar measure, then theorem IV.1 of [4] implies that there is a quantum operation Embedded Image acting only on CE′ such that Embedded Image1.4Because the trace distance is monotonic under quantum operations, it will not increase by taking the partial trace over R and measuring in the basis {|ψm〉} [5]. If we let p(m′|m) be the probability of getting an outcome |ψm〉 when the message was in fact m, equation (1.4) implies that Embedded Image1.5In words, the probability of the measurement yielding the incorrect outcome, averaged over all messages, is at most Embedded Image. So, as soon as C is significantly larger than M, a measurement on CE′ can be found that will reveal the message. Our goal in this article will be to demonstrate that until this condition is met, no measurement will reveal any significant information about the message.

(b) Structure and notation

All logarithms are taken base 2. |A| will denote the dimension of Hilbert space A. However, we will often drop the |⋅|. For example, the dimension of the composite system MCK is denoted by MCK (a scalar value). A⊗2 will denote two identical copies of A, the second of which is denoted by Embedded Image. πA is the maximally mixed state Embedded Image. Embedded Image is the unitary group on A. Embedded Image will denote the set of all (s,η)-quasi-measurements, see definition 2.3. We will use MN to denote MNM. The following three norms are defined: Embedded Image, Embedded Image and Embedded Image. We will denote by Embedded Image the largest singular value of M. H2(A)ρ will be the Rényi 2-entropy of A, defined as Embedded Image. Embedded Image will be the quantum min-entropy of A, defined as Embedded Image. Embedded Image will be the quantum max-entropy of A, defined as Embedded Image. We will denote by I(A;B)ρ the mutual information of A and B, defined as H(A)ρ+H(B)ρH(AB)ρ.

2. Definitions

This section will present the basic definitions needed to state our results.

Definition 2.1 (measurement superoperator)

We call a completely positive, trace-preserving (CPTP) map Embedded Image a measurement superoperator if it is of the form Embedded Image, where {|iA:i∈{1,…,N}} is an orthonormal basis for X, each Embedded Image is positive semidefinite and Embedded Image.

These play a central role in the definition of accessible information.

Definition 2.2 (accessible information [6])

Let ρAB be a quantum state. Then, the accessible information Iacc(A;B) is defined as Embedded Imagewhere Embedded Image and Embedded Image are measurement superoperators, and the supremum is taken over all possible superoperators. In other words, the accessible information is the largest possible mutual information between the results of measurements made on A and B.

We also need to introduce the concept of quasi-measurements for our analysis. They are, as their name indicates, almost measurements, but differ in three ways: they contain only rank-one elements of equal weight, they have exactly s outcomes, and the sum of all the elements does not necessarily equal the identity, but is instead bounded by Embedded Image:

Definition 2.3 (quasi-measurement)

We call a superoperator Embedded Image an (s,η)-quasi-measurement if it is of the form Embedded Image where the |i〉 index an orthonormal basis for B, and Embedded Image. We call the set of all (s,η)-quasi-measurements on a given system, Embedded Image.

It can easily be seen that projective measurements are simply (A,1)-quasi-measurements.

We now give the formal, strengthened definition of locking. The states in question were introduced in §1a. However, because the cyphertext will always be smaller than or equal to the message when locking occurs, certain identifications become possible. In particular, we can assume without loss of generality that NCK and DEK. Since the analysis will be performed using only C, K and E, we reproduce the illustration of the physical scenario with the identifications made in figure 2.

Figure 2.

A quantum circuit depicting the physical scenario with the locking-specific identifications NCK and DEK made.

Definition 2.4 (ε-locking scheme)

Let M,C,K,E and E′ be quantum systems. Let ρMCKEE be a quantum state of the form Embedded Image2.1where the |ψm〉 are orthogonal and UCKE is unitary. Then we call ρ an ε-locking scheme if for any measurement superoperator Embedded Image, we have that Embedded ImageWe may also call this trace distance the decoupling distance or the distinguishability.

Our definition implies the older definitions of locking [1,2] via a direct application of the Alicki–Fannes inequality [7].

Four quantities will be particularly useful for quantifying variations from uniform messages and maximal entanglement, Embedded Image2.2 Embedded Image2.3 Embedded Image2.4 and Embedded Image2.5

The Δ terms are used in the calculations to provide more general statements relating the entropy of the message and entanglement to the key size.

3. Main results and proof sketch

The locking scheme we study is one where the unitary in definition 2.4 is chosen according to the Haar measure. Let c,e and n be the logarithms of |C|,|E| and |M|=|N|, respectively. In particular, the message is n bits long. Define K=M/C and Embedded Image. Then k=nc is the difference in size between the message and cyphertext, that is, the size of the key. Our main theorem is the following:

Theorem 3.1

If U is chosen according to the Haar measure, then the scheme described in definition 2.4 is an ε-locking scheme with probability at least 1− 2−9(|C||E|)2 if Embedded Imageand if Embedded Image.

For the cryptographically relevant case in which there is no entanglement shared with the measuring device, we therefore get:

Corollary 3.2

If U is chosen according to the Haar measure, then the scheme described in definition 2.4 without shared entanglement is an ε-locking scheme with probability at least 1−2−9|C|2 if Embedded Imageand if Embedded Image.

Hence, the size of the key must be at least as large as half the ‘min-entropy deficit’ (Embedded Image) of the message plus a term of logarithmic order in the size of the message.

Conversely, we can show that in certain regimes, if the information is not locked, then it is completely decodable, with almost no middle ground. More precisely, we have the following:

Theorem 3.3

If U is chosen according to the Haar measure, then the information in the scheme described in figure 1 is asymptotically almost surely decodable to within ε in trace distance for a receiver with only C as long asEmbedded Image

Note that decoding the message will often require that the cyphertext be longer than the message, in which case k will be negative. Comparing theorems 3.1 and 3.3 reveals that the difference between being ε-locked and being able to decode quantum information to within ε is determined by at most Embedded Imagequbits, where the inequality Embedded Image has been used to simplify the expression.

In other words, if we consider the case of maximal entanglement, then the gap between locking and decodability can only be as wide as the difference between the min- and max-entropies of the message modulo logarithmic terms. One should note that this gap is real, and not only an artefact of our proof technique. To see this, consider an n-bit message distributed such that with probability 1/2, the first bit is uniform and the rest of the string is always zero, and with probability 1/2 the whole string is uniform. The max-entropy of such a message is nearly n, but the min-entropy is tiny. Now, to be able to decode, one must be able to decode the entire string in the ‘worst-case’ scenario where the whole string is uniform, so the max-entropy is relevant in this case. But in the locking case, we must be able to lock even in the worst-case scenario of only one bit being random, so the min-entropy is the relevant quantity here.

The effect of non-extremal entanglement is not entirely clear, however. There is a fairly large gap between our locking and decodability results here, but the locking side is almost certainly not tight in general.

(a) Proof sketch

We will give a very high-level overview of the proof. The basic idea is to start from the fact that, given a fixed measurement superoperator, the probability over the choice of unitaries that this measurement yields non-negligible correlations is extremely small. Then, we would like to discretize the space of all measurement superoperators and use the union bound to show that the probability that any measurement superoperator yields non-negligible correlations is still very small. For this to work, the ‘number’ of measurements has to be much smaller than the reciprocal of the probability of getting a bad U. However, the set of measurement superoperators cannot be discretized directly, since (among other things) they contain a potentially unbounded number of outputs. Hence, we will instead use the above argument on (s,η)-quasi-measurements, which can be discretized easily (see lemma 4.4), and then show that the best measurement cannot beat the best (s,η)-quasi-measurement by too much.

The basic ingredient of the proof is the following concentration of measure theorem on Haar-distributed unitaries:

Theorem 3.4 (corollary 4.4.28 in [8])

Let Embedded Image be a function with Lipschitz constant θ (the Lipschitz constant is taken with respect to the Hilbert–Schmidt distance on unitaries). Then, Embedded Image

We apply this theorem to the function Embedded Imagefor any fixed (s,η)-quasi-measurement Embedded Image, where ρ depends on U as in equation (2.1). This puts us in a position to use our ε-net over (s,η)-quasi-measurements (lemma 4.4) and the union bound to get a bound on the probability that there exists an (s,η)-quasi-measurement Embedded Image for which Embedded Image; this is done in theorem 4.5.

At this point, the proof splits into an ‘easy’ and a ‘hard’ branch. The easy branch (§5) applies theorem 4.5 to projective measurements. The hard branch (§6) goes for the full prize: showing that Embedded Image is small for every positive operator valued measure (POVM) with high probability.

4. Concentration of the distinguishability from independence

To be able to use the general concentration of measure theorem (theorem 3.4) on Embedded Image, we must first be able to upper-bound the expectation of Embedded Image with respect to U. The following lemma does this:

Lemma 4.1 (distinguishability for a fixed measurement)

If Embedded Image is an (s,η)-quasi-measurement, then Embedded Image

Proof.

We begin by expanding and simplifying the original expression Embedded Image4.1In the manipulations above, we have used lemma 5.1.3 in [9] with Embedded Image in the second line, noting that |X|=s. We will now use a helpful identity for the trace of an operator squared: Tr Z2=Tr[(Z⊗Z)F], where F is defined as the swap operator such that Embedded Image for two arbitrary states. This yields Embedded Image4.2This last line follows from the fact that results of the measurement Embedded Image are stored in an orthonormal basis of system X. We will proceed by evaluating Embedded Image, but before continuing we absorb the two σ−1/4 into the operator ρ. That is, we define Embedded Image and Embedded Image. With these two definitions in hand, we can expand Embedded Image as Embedded ImageThe evaluation of this integral can be found in the electronic supplementary materials. The results yield the following bound: Embedded Image □

We now introduce three lemmas that will form our concentration argument. The proofs of all three can be found in the electronic supplementary materials.

Lemma 4.2

Embedded Image the trace distance to independence for a fixed (s,η)-quasi-measurement, is Lipschitz continuous on the space Embedded Image with constant Embedded Image.

In order to discretize the set of all (s,η)-quasi-measurements, we require a distance measure for the set. We will define the distance between two quasi-measurements as Embedded Imagewhere χi and νi are the projectors associated with the quasi-measurements Embedded Image and Embedded Image, respectively.

Now letting Embedded Image vary instead of U, we define a new function, Embedded Imageof which the following lemma is true.

Lemma 4.3

Embedded Image is Lipschitz continuous on the space Embedded Image with constant Embedded Image.

In order to bound the number of relevant measurement superoperators Embedded Image, we construct an ε-net. The following lemma provides this bound,

Lemma 4.4

Given system A, there exists a ε-net Embedded Image over the set Embedded Image of all (s,η)-quasi-measurements on A, such that each element Embedded Image is at most ε-distant from an element of Embedded Image with respect to the metric d(⋅,⋅). The size of this net can be taken to be Embedded Image.

The Lipschitz constants, expectation value, and net size give us all the pieces we need to make the concentration argument. We show that with very high probability, the distinguishability from independence of the joint distribution of messages and quasi-measurement outcomes is small.

Theorem 4.5 (measure concentration of the distinguishability from independence)

Given the quantum state ρMCKEE=UCKE⋅(σMCK⊗ωEE), where U is a random unitary operator chosen according to the Haar measure, σ is as defined in equation (1.1), E′≅E, and ωEE is a bipartite pure state, the following bound holds: Embedded ImageIn the above, Embedded Image ΔM,2, ΔE,2 and Embedded Image are as defined in equations (2.2)–(2.5).

Proof.

We apply theorem 3.4 to Embedded Image and consider only one direction of the divergence from the expected value. The exact statement can be written as Embedded Image4.3It is convenient to define Embedded ImageClearly, Embedded Image and hU are sections of f and we are interested in bounding Embedded Image. Let Embedded Imageand consider Embedded Image an ε′-net over all (s,η)-quasi-measurements Embedded Image. We found in lemma 4.3 that if two (s,η)-quasi-measurements were ε′ apart with respect to the distance measure d(⋅,⋅), then for a fixed unitary U, the values of f for each measurement would not differ by more than ε. Thus, we can state that the supremum deviation of f is not more than twice the maximum deviation found on measurements in the net, Embedded ImageA union bound argument now bounds the probability of deviation for the maximum measurement by the probability of deviation for a generic measurement Embedded ImageThankfully, we have an explicit bound for the probability of deviation for an arbitrary measurement and we can make a simplification Embedded ImageSubstituting in the fact that CK=M yields the desired inequality. □

5. Locking against projective measurements

Consider the case of projective measurements, i.e.: (s,η)=(CE′,1) and identify C=2c, K=2k and E=E′=2e (allowing us to state our results in terms of qubits).

Corollary 5.1 (locking for messages of bounded entropy with imperfect entanglement)

Consider the locking scheme described in Definition 2.4 for a message of bounded entropy with entanglement of a bounded fidelity available at the measurement. Choose ε and p satisfying Embedded ImageThen the scheme will be an ε-locking scheme except with probability p so long as the measurement superoperators are restricted to projective measurements and Embedded Image5.1

6. Locking against generalized measurements

We will now show that the results of §5 hold not only for projective measurements, but also for general POVMs, up to very minor changes in the various constants. The main difficulty at this point is that we cannot use theorem 4.5 directly, as it gives only bounds for (s,η)-quasi-measurements. We must therefore show that a general POVM behaves essentially like an (s,η)-quasi-measurement for the purposes of the theorem. Our strategy will be probabilistic in nature: we will show that doing a general POVM Embedded Image is mathematically equivalent to randomly selecting a measurement constructed from possible sequences of s measurement results obtained from Embedded Image. With overwhelming probability, the sequence chosen will be an (s,η)-quasi-measurement, and theorem 4.5 will then apply in this case.

We start by proving this last fact, namely that with very high probability, a sequence of s measurement results will be an (s,η)-quasi-measurement, for an appropriately chosen η.

Lemma 6.1

Let Embedded Image be any measurement superoperator with rank-one operators Mi, where Embedded Image and consider the operator-valued random variable Y which takes the value |χi〉〈χi| with probability αiχi|π|χi〉=αi/CE′. Then, s i.i.d. copies of Y will fail to be an (s,η)- quasi-measurement with probability at most Embedded Image.

Proof.

Y fulfils all the conditions for the operator Chernoff bound [10] to apply, with Embedded Image. This yields Embedded Imageand the probability on the left is an upper bound on the probability that the s-tuple Y 1,…,Y s is not an (s,η)-quasi-measurement. □

We now use this to show that the best general POVM cannot do much better than the best (s,η)-quasi-measurement:

Lemma 6.2

It is true that Embedded Image6.1where the supremum on the left-hand side is taken over all measurement superoperators.

Proof.

Let Embedded Image be any complete measurement superoperator of the form Embedded Image, and define Y to be the operator-valued random variable which takes value χi with probability αi/CE′. Let Q be the event that Y 1,…,Y n is an (s,η)-quasi-measurement, where the Y i are i.i.d. with the same distribution as Y . Embedded ImageAt this point, we separate the expression into two terms, one for the event Q and another for its complement. Embedded ImageIn the above, the sum of trace distances given Q was interpreted as executing an (s,η)-quasi-measurement described by Y 1,…,Y s, and the same sum given Embedded Image was simply bounded by 2η (there are s terms in the sum, each of which cannot exceed 2). In the last step, we have bounded Embedded Image using lemma 6.1 and made use of the fact that we can assume without loss of generality that |E|=|E′|.

Finally, a non-complete measurement superoperator can always be decomposed into a complete one by splitting the POVM elements of rank greater than 1; this process always increases the trace distance. □

What we have achieved with the above statement is to show that the decoupling distance for a general measurement superoperator is very close to the decoupling distance of an (s,η)-quasi-measurement. All that is now left to do is to use theorem 4.5 to bound the supremum over (s,η)-quasi-measurements, and we get the main theorem of this section:

Theorem 6.3 (locking theorem for general measurements)

Given the quantum state ρMCKEE=UCKE⋅(σMCK⊗ωEE), where U is a random unitary operator chosen according to the Haar measure, σ is as defined in equation (1.1) and ωEE a bipartite pure state, then Embedded ImageIn the above, Embedded Image ΔM,2, ΔE,2 and Embedded Image are as defined in equations (2.2)–(2.5).

Proof.

We may assume without loss of generality that |E′|≤|E|. If not, let E′′ be the range of ρE=ωE. Because ω is pure, |E′′|= rank ωE≤|E|. Let V be the isometric embedding E′′↪E′ and ρMCE′′ the projection of ρ to MCE′′. Then for any POVM measurement superoperator Embedded Image, Embedded Imageso measuring Embedded Image or Embedded Image will yield exactly the same measurement statistics. But the latter is a POVM on CE′′ and E′′ satisfies the desired dimension bound.

Substituting the results of lemma 6.2 into those of theorem 4.5, we get the following: Embedded Image6.2We now choose η=2 and Embedded Image and note that this immediately implies Embedded ImageWe absorb this factor into our ‘offset’ for the ε factor, Embedded ImageSubstituting the choices for s and η into equation (6.2) reveals the desired result. □

We now wish to express, in qubits, a lower bound for the key size for a given probability p and a given ε.

Corollary 6.4 (locking against POVMs for messages of bounded entropy with imperfect entanglement)

Consider the locking scheme described in definition 2.4 for a uniform message and maximal entanglement available at the measurement. Choose p and ε such that Embedded ImageThen the scheme will be an ε-locking locking scheme except with probability p so long as Embedded Image6.3

7. Locking versus decodability

Sections 5 and 6 have shown that, under certain conditions, no classical information is recoverable by the receiver. Here, we aim to show that, in many regimes, these results are essentially optimal. We do this by showing that if we make the key only very slightly smaller, then with overwhelming probability, the classical message will be decodable with a negligible error probability. In fact, we prove even more: in this regime where the information is decodable, the decoder can even decode a purification of the classical message. In other words, in this generic scenario where U is chosen with no preferred basis, either all classical information is locked away, or we can decode quantum information. This is formalized in the next theorem.

In order to study decodability, we must discard the identifications made in figure 2 to study locking and return to the original scenario described by figure 1. Whereas k was previously the number of qubits in system K, there is now no system K in figure 2. Instead, we define k=nc, which is consistent with its earlier definition. Now, however, it might be the case that k is negative since decoding could require the cyphertext to be longer than the message.

The following theorem generalizes the discussion of §1a to non-uniform messages and imperfect entanglement. The proof can, again, be found in the electronic supplementary materials.

Theorem 7.1

If U is chosen according to the Haar measure, then the information in the scheme described in figure 1 is such that there exists a decoding CPTP map Embedded Image such that Embedded Imageasymptotically almost surely, where σRMN is a purification of σMN, as long as Embedded Image

8. Implications for the security of quantum protocols against quantum adversaries

When designing quantum cryptographic protocols, it is often necessary to show that a quantum adversary (‘Eve’) is left with only a negligible amount of information on some secret string. An initial attempt at formalizing this idea is to say that, at the end of the protocol, regardless of what measurement Eve makes on her quantum system, the mutual information between her measurement result and the secret string is at most ε (in other words, her accessible information about the message is at most ε). This was often taken as the security definition for quantum key distribution, usually implicitly by simply not considering that the adversary might keep quantum data at the end of the protocol [5,1114] (see also discussion in [1517]). In the study of König et al. [17], it is shown that this definition of security is inadequate, precisely because of possible locking effects.

The locking scheme presented in this work allows us to demonstrate a much more spectacular failure of this security definition. There exists a quantum key distribution protocol that ensures that an adversary has negligible accessible information about the final key, but with which an adversary can recover the entire key upon learning only a very small fraction of it.

This faulty protocol starts with a protocol that is truly secure, and then has Alice send a locked version of the secret string directly to Eve. Regardless of what measurement Eve makes on her state, she will learn essentially no information on the string, but of course, she needs only to learn a tiny amount of information to unlock what Alice sent her. More precisely, let P be a quantum key distribution protocol such that, at the end of its execution, Alice and Bob share an n-bit string, and Eve has a quantum state representing everything that she has managed to learn about the string. We will also assume that P is a truly secure protocol: the string together with Eve's quantum state can be represented as a quantum state σSE such that Embedded Image, where S is a quantum register holding the secret string, and E is Eve's quantum register. Now, we will define the protocol P′ to be the following quantum key distribution protocol: Alice and Bob first run P to generate a string s of length n, and then Alice splits s into two parts: the first part sk is of size Embedded Image, and the second part sc contains the rest of the key. Alice then uses the classical key sk to create a quantum state in register C that contains a locked version of sc and sends the system C to Eve.

How secure is P′? It is clearly very insecure, since, if Eve ever ends up learning sk (via a known plaintext attack, for instance), she can then completely recover sc. However, in the following theorem, P′ satisfies the requirement that Eve's accessible information on the key be very low.

Theorem 8.1

Let P and P′ be quantum key distribution protocols as defined above, and let ρCES be the state at the end of the execution of P′:S contains the n-bit string s, E is Eve's quantum register after the execution of P, and C contains the locked version of sc that Alice sent to Eve. Then, for any measurement superoperator Embedded Image there exists a state ξX such that Embedded ImageThis also entails that Embedded Imagevia the Alicki–Fannes inequality.

The full proof of the above is available in the electronic supplementary materials. Hence, we have shown that requiring that Eve's accessible information on the generated key below is not an adequate definition of security for quantum key distribution.

9. Discussion

It is natural in physics to measure the ‘correlation’ between two quantum physical systems using the correlation between the outcomes of measurements on those two systems. Two-point correlation functions are but the most ubiquitous examples. The results in this article demonstrate that this practice can sometimes be very misleading, although useful in cases such as quantum data hiding [1821]. The ϵ-locking quantum states exhibited in this article would reveal no correlations using any type of measurement, but enlarging one of the two systems by a small number of qubits would expose near-perfect correlation between the two systems. This is an important and counterintuitive property of information in quantum mechanical systems: local measurements can be distressingly bad ways to detect correlation.

The extensive literature on quantum discord is essentially devoted to exploring the relationship between accessible or classical, and quantum mutual information [22,23]. Since the discord is defined as the gap between the quantum and classical mutual informations, locking can be viewed as the extreme case where classical mutual information does not detect any of the very abundant quantum mutual information. This viewpoint applies equally well to accessible information and the Henderson–Vedral measure [24]. Previous work had demonstrated that transmitting a constant number of physical qubits can cause the classical mutual information to increase from a fixed small constant to an arbitrarily large value. In this article, we have strengthened the definition of locking, replacing the mutual information by the trace distance to a product distribution, at the cost of requiring a logarithmic number of qubits for unlocking. Moreover, we have shown that the locking effect still exists even when the trace distance (or the classical mutual information) is made arbitrarily small.

Previous studies of information locking had also always focused on the example of sending classical information in one of a small number of different bases unknown to the receiver. The intuition was that a receiver ignorant of the basis could not do much better than guessing the basis and then measuring. Most of the time, he would guess incorrectly and his measurement would then destroy the information. Moving away from that paradigm, in this article we consider classical information encoded using a single generic unitary transformation mixing the input information with half of an entangled state shared with the receiver. The ‘key’ then becomes a quantum system. While the original paradigm can be recovered by eliminating the entanglement and encrypting the key quantum system with a private quantum channel, the setting considered here is strictly more general.

Indeed, we find that, for an n-bit uniform message and maximal entanglement, the information is generically ϵ-locked until the receiver is within Embedded Image qubits of being able to completely decode the message. Our definition of locking is stronger than those previously studied and our results imply, for the first time, that the classical mutual information can be made arbitrarily small. Our method of proof in the case of projective measurements was a fairly standard discretization argument but the extension to POVM measurements required a new strategy exploiting the operator Chernoff bound. In contrast to previous studies of locking, we do not require the message to be uniformly distributed, working instead with a min-entropy bound on the distribution of messages. In that case, we found that the key size was at most the gap between the max- and min-entropies of the message, modulo the logarithmic terms that dominate in the uniform situation.

For information theorists, this may appear reminiscent of a strong converse to a channel capacity problem. Roughly, a strong converse theorem states that any attempt to transmit above the channel capacity will result in the decoding error probability approaching one. In our setting, the analogue of the strong converse would be a matching lower bound to equation (1.5) of the form Embedded Image9.1whenever C<M, indicating the probability of incorrectly decoding the message is at least 1−ϵ. What we prove here is much stronger. Equation (9.1) does not rule out the possibility of being able to pin the message down to some relatively small set. More generally, it does not imply a small mutual information between the message and the measurement outcome. Information locking does imply these stronger statements.

As such, information locking has a natural cryptographic interpretation even if we have not emphasized it in this article. The special case of our scenario mentioned above, with no entanglement and a quantum key encrypted using a private quantum channel, leads to a method for encrypting classical messages using a secret key of size independent of the length of the message. Similarly, information locking schemes can be used to construct string commitment protocols with surprisingly good parameters [25,26]. These cryptographic applications are emphasized in the companion article [3].

To the extent that random unitary transformations provide good models of black hole evaporation, our results might also have implications for that process. Oppenheim & Smolin [27] had previously suggested that information locking could rescue the long-lived remnant hypothesis. In essence, their idea was that a remnant with a small number of states could lock all the information of a large black hole, thereby evading the inconsistencies with low energy physics that arise from having large numbers of remnant species [28,29]. Their proposal, however, relied on previously studied locking states that treated the encoded message and the key very differently. Consequently, the proposal required that the black hole keep hold of the key until the very last moments of its evaporation, implying some ad hoc dynamical distinction between encoded message and key in the evaporation process. Our results imply that if the dynamics are well modelled by a Haar random unitary transformation, then any small portion of the output system can be used as the key. No ad hoc distinction is necessary.

Ironically, the information locking effect is also perfectly compatible with the rapid release of information from a black hole predicted in [30], assuming a unitary evaporation process. That article observed that if a black hole is already highly entangled with Hawking radiation from an earlier time, then messages would be released from the black hole in the Hawking radiation once the black hole dynamics had sufficiently ‘scrambled’ the message with internal black hole degrees of freedom. By virtue of the fact that we treat generic unitary transformations acting on a message and half of an entangled state, our results apply to the setting of that paper and the follow-up [31]. Specifically, our results imply that in the case of a larger message, no information about the message could be obtained from the Hawking radiation until moments before it could all be obtained. The conclusion depends, of course, on whether the random unitary transformation is a good model of the evaporation process. While the generic unitary transformations considered here would take exponential time to implement on a quantum computer, [3] shows that at least locking can be achieved with a quantum circuit of depth only slightly superlinear in the number of qubits in the system. Other attempts to apply random unitary transformations to the black hole information problem, such as [32,33], will be affected similarly by information locking.

To summarize, this article defined information locking more stringently than previously and nonetheless found that this stronger form of locking is generic: if information is encoded using a random unitary transformation, then it will either be decodable or locked. Almost no middle ground occurs. This observation has implications for cryptography and, potentially, for black hole physics.

Funding statement

This research was supported by the Canada Research Chairs program, the Perimeter Institute, CIFAR, CFI, FQRNT's INTRIQ, MITACS, NSERC, ORF, ONR through grant no. N000140811249, QuantumWorks and the Swiss National Science Foundation through grant no. 200021-119868.

Acknowledgements

The authors would like to thank Gilles Brassard for his suggestion of writing up the implications of our results for QKD security definitions (§8). Andreas Winter has independently established some locking results for generic unitary transformations. We would like to thank Jonathan Oppenheim for helpful discussions and the Mittag-Leffler Institute for its kind hospitality.

Footnotes

  • 1 Note that our results can immediately be converted into results where the key is classical: one simply perfectly encrypts the quantum key using a classical key, which costs two bits per qubit, and makes the newly encrypted quantum key part of the cyphertext.

  • Received May 7, 2013.
  • Accepted August 23, 2013.

References

View Abstract