BRICS

Basic Research in Computer Science

A Quantum Cipher with Near Optimal Key-Recycling

Ivan B. Damgård Thomas B. Pedersen Louis Salvail BRICS Report Series RS-05-17 ISSN 0909-0878 May 2005 BRICS RS-05-17 Damgård et al.: A Quantum Cipher with Near Optimal Key-Recycling Copyright \begin{matrix}c \\ ◯ \end{matrix} 2005, Ivan B. Damgård & Thomas B. Pedersen &

Louis Salvail. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/05/17/

A Quantum Cipher with Near Optimal Key-Recycling

Ivan Damgård  Thomas Brochmann Pedersen^{∗} Louis Salvail^{∗}

May 2005

Abstract

Assuming an insecure quantum channel and an authenticated classical channel, we propose an unconditionally secure scheme for encrypting classical messages under a shared key, where attempts to eavesdrop the ciphertext can be detected. If no eavesdropping is detected, we can securely re-use the entire key for encrypting new messages. If eavesdropping is detected, we must discard a number of key bits corresponding to the length of the message, but can re-use almost all of the rest. We show this is essentially optimal. Thus, provided the adversary does not interfere (too much) with the quantum channel, we can securely send an arbitrary number of message bits, independently of the length of the initial key. Moreover, the key-recycling mechanism only requires one-bit feedback. While ordinary quantum key distribution with a classical one time pad could be used instead to obtain a similar functionality, this would need more rounds of interaction and more communication.

Key-words: quantum cryptography, key-recycling, unconditional security, private-key encryption.

1 Introduction

It is well known that only assuming a quantum channel and an authenticated classical channel, Quantum Key Distribution (qkd) can be used to generate an unconditionally secure shared key between two parties. If we want to use this key for encrypting classical messages, the simplest way is to use it as a one-time pad. This way, an m-bit key can be used to encrypt no more than m message bits, since re-using the key would not be secure (without extra assumptions like in the bounded storage model[19, 10, 13]).

However, if we allow the same communication model for message transmission as for key exchange — which seems quite natural — an obvious question is whether we might gain something by using the quantum channel to transmit ciphertexts. The reason why this might be a good idea is that the ciphertext is now a quantum state, and so by the laws of quantum mechanics, the adversary cannot avoid affecting the ciphertext when trying to eavesdrop. We may therefore hope being able to detect — at least with some probability — whether the adversary has interacted with the ciphertext. Clearly, if we know he has not, we can re-use the entire key. Even if he has, we may still be able to bound the amount of information he can obtain on the key, and hence we can still re-use part of the key. Note that the authenticated classical channel is needed in such a scheme, in order for the receiver to tell the sender whether the ciphertext arrived safely, and possibly also to exchange information needed to extract the part of the key that can be re-used. Such a system is called a Quantum Key-Recycling Scheme (qkrs).

∗Part of this research was funded by European projects PROSECCO and SECOQC.

A possible objection against qkrs is that since it requires interaction, we might as well use qkd to generate new key bits whenever needed. However, in the model where the authenticated classical channel is given as a black-box (i.e., not implemented via a shared key) qkd requires at least three messages: the quantum channel must be used, and the authenticated channel must be used in both directions, since otherwise the adversary could impersonate one of the honest parties. Further, each move requires a substantial amount of communication (if N qubits were transmitted then the two classical moves require more than N classical bits each). Finally, N is typically larger than the length of the secret-key produced. Hence, if we can build a qkrs scheme that is efficient, particularly in terms of how much key material can be re-used, this may be an advantage over straightforward use of qkd.

From a more theoretical point of view, our work can be seen as a study of the recycling capabilities of quantum ciphers in general. In particular, how many key bits can be recycled, and how much feedback information must go from receiver to sender in order to guarantee the security of the recycled key? How do these capabilities differ from those of classical ciphers? In this paper we give precise answers to these questions.

The idea behind a qkrs originates from Bennett and Brassard during the early days of quantum cryptography[4]. Although they did not provide any fully satisfying solution or security proof, their approach to the problem is similar to our. More recently Leung studied recycling of quantum keys in a model where Alice and Bob are allowed three moves of interaction[12]. In this model, however, quantum key distribution can be applied. Leung also suggested that classical keys can be recycled when no eavesdropping is detected. In [16], a qkrs was proposed based on quantum authentication codes[2]. The key-recycling capabilities of their scheme can be described in terms of 2 parameters: the message length m and the security parameter ℓ. The scheme uses 2m + 2ℓ bits of key, and is based on quantum authentication schemes that, as shown in [2], must always encrypt the message. The receiver first checks the authenticity of the received quantum state and then sends the result to the sender on the authenticated channel. Even when the receiver accepts, the adversary may still have obtained a small amount of information on the key. The receiver therefore also sends a universal hash function, and privacy amplification is used to extract from the original key a secure key of length 2m + ℓ. If the receiver rejects then a secure key of length m + ℓ can be extracted.

In this paper, we propose a qkrs for encrypting classical messages. Our qkrs is based on a new technique where we append a k-bit classical authentication tag to the message, and then encrypt the n = m + ℓ-bit plaintext using the W_{n}-quantum cipher introduced in [8]. The authentication is based on universal hashing using an m-bit key. The cipher uses 2n = 2(m + ℓ) bits of key, where m + ℓ bits are used as a one-time pad, and m + ℓ bits are used to select in which basis to send the result, out of a set of 2^{m+ℓ} so called mutually unbiased bases. Thus, the entire key of the qkrs consists of 3m+2ℓ bits. The receiver decrypts and checks the authentication tag. If the tag is correct, we can show that the adversary has exponentially small information about the key, and the entire key can therefore be recycled. If the tag is incorrect, we can still identify 2m + ℓ bits of the key, about which the adversary has no information, and they can therefore be re-used. Since this subset of bits is always the same, the receiver only needs to tell the sender whether he accepts or not.

Being able to recycle the entire key in case the receiver accepts is of course optimal. On the other hand, we can show that any qkrs must discard at least m − 1 bits of key in case the receiver rejects. Since m can be chosen to be much larger than ℓ, discarding m + ℓ bits, as we do, is almost optimal.

In comparison with earlier works, our technique completely eliminates the use of privacy amplification, and hence reduces the communication on the authenticated channel to a single bit. Moreover, we can recycle the entire key when the receiver accepts the authentication tag. Hence, in scenarios where interference from the adversary is not too frequent, our keys can last much longer than with previous schemes, even though we initially start with a longer key.

Our results differ from those of [16], since quantum authentication based qkrs do not guarantee the privacy of the authentication tag. Therefore, part of the key must be discarded even if the receiver accepts. Instead of quantum authentication, we use classical Wegman and Carter authentication codes[6] and a quantum encryption of classical messages[8] applied to both the message and the tag. This construction allows to recycle the entire authentication key securely.

The scheme we introduce can also be used as an authentication code for quantum messages. However, it requires a longer secret-key than the scheme in [2], but allows for recycling the authentication key entirely upon acceptance.

Our qkrs is composable since the security is expressed in terms of distance from uniform. The secret-keys and plaintexts are private when, from the adversary’s point of view, they look like uniformly distributed random variables. This has been shown to provide universal composability in the quantum world[17].

We end this introduction with some remarks on the authenticated classical channel. Having such a channel given for free as a black-box may not be a realistic assumption, but it is well known that it can be implemented assuming the players initially have a (short) shared key.^{1} In this model, the distinction between qkd and qkrs is not as clear as before, since we now assume an initial shared key for both primitives. Indeed, our qkrs can be seen as an alternative way to do qkd: we can form a message as the concatenation of new random key bits to be output and a short key for implementing the next usage of the authenticated channel. Having sent enough messages of this form successfully, we can generate a much larger number of secure key bits than we started from. Note that this is harder to achieve when using the earlier qkrs scheme since bits of the original key are lost even in successful transmissions.

2 Preliminaries

2.1 Density Operators and Distance Measures

We denote by 𝒮(ℋ) the set of density operators on Hilbert space ℋ (i.e. positive operators σ such that tr(σ) = 1). In the following, ℋ_{n} denotes the 2^{n}-dimensional Hilbert space over ℂ, 11_{n} denotes the 2^{n} × 2^{n} identity operator, and 𝕀_{n} = 2^{−n}11_{n} denotes the completely mixed state. The trace-norm distance between two quantum states ρ, σ ∈ 𝒮(ℋ) is defined as:

D(ρ, σ) = \frac{1}{2} tr (|ρ − σ|) ,

where the right-hand side denotes half the sum over the absolute value of all eigenvalues of ρ−σ. The trace-norm distance is a metric over the set of density operators in 𝒮(ℋ). In the following, we use the same notation as [17]. Let (Ω, P) be a discrete probability space. A random state ρ is a function from Ω to 𝒮(ℋ). This means that to ω ∈ Ω corresponds the mixed state ρ(ω). To an observer ignorant of the randomness ω ∈ Ω, the density operator described by ρ is given by

[ρ] = ∑_{ω∈Ω} P (ω)ρ(ω).

1Even in this case, qkd does something that is impossible classically, namely it generates a shared key that is longer than the initial one.

For any event ℰ, the density operator described by ρ conditioned on ℰ is given by

[ρ|ℰ] = \frac{1}{Pr (ℰ)} ∑_{ω∈ℰ}P (ω)ρ(ω).

Classical random variables can also be represented as random states. Let X be a random variable with range 𝒳 and let ℋ be a #𝒳-dimensional Hilbert space with orthonormal basis {|x⟩}_{x∈𝒳}. The random state corresponding to X is denoted by {X} = |X⟩⟨X| and [{X}] = ∑_{x∈𝒳} P (x)|x⟩⟨x| denotes its associated density operator. Let ρ ⊗ {X} be a random state with a classical part {X}. The corresponding density operator is given by

[ρ ⊗ \{X\}] = ∑_{x∈𝒳} P (x)[ρ|X = x] ⊗ {|x⟩ \atop ⟨x|}.

If X is independent of ρ then [ρ ⊗ {X}] = [ρ] ⊗ [{X}]. Let X be a classical random variable with range 𝒳 and let ρ be a random state. The distance to uniform of X given ρ is defined by

d(X|ρ) = D([{X} ⊗ ρ], [{U}] ⊗ [ρ]),  (1)

where U is a random variable uniformly distributed over 𝒳.

2.2 Quantum Ciphers

A quantum encryption scheme for classical messages is the central part of any qkrs. Such schemes where introduced in [1], and further studied in [8], where their performances were analyzed against known-plaintext attacks. We adopt a similar definition here except that we allow for the encryption to provide only statistical instead of perfect privacy. As in [1, 8], we model encryption under key k by an appropriate unitary operator E_{k} acting upon the message and a possible ancilla of any size initially in state |0⟩. Decryption is simply done by applying the inverse unitary.

For convenience we will use the notation

ρ_{x} = ∑_{k∈\{0,1\}^{n}} 2^{−n}E_{k}{|x⟩ \atop ⟨x|} ⊗ {|0⟩ \atop ⟨0|}E_{k}^{†},

for the equal mixture of a plaintext x ∈ {0, 1}^{m} encrypted under all possible keys with uniform probability. A quantum cipher is private if, given a cipherstate, almost no information can be extracted about the plaintext.

Definition 1 For a non-negative function ϵ(n), a ϵ(n)-private (n, m)-quan-tum cipher is described by a set of 2^{n} unitary encryption operators {E_{k}}_{k∈{0,1}^{n}}, acting on a set of m-bit plaintexts and an arbitrary ancilla initially in state |0⟩ such that,

(∀x, x′ ∈ {0, 1}^{m})[D(ρ_{x}, ρ_{x′}) < ϵ(n)].

If ϵ(n) is a negligible function of n we say that the scheme is statistically private.

The total mixture of ciphertexts associated with an ϵ-private (n, m)-quantum cipher with encryption operators {E_{k}}_{k∈{0,1}^{n}} is

ξ = ∑_{k∈\{0,1\}^{n}} 2^{−n} ∑_{x∈\{0,1\}^{m}} 2^{−m}E_{k}{|x⟩ \atop ⟨x|} ⊗ {|0⟩ \atop ⟨0|}E_{k}^{†}.  (2)

The next technical Lemma states that the total mixture of any ϵ-private quantum cipher is ϵ-close to any plaintext encryption under a random and private key.

Lemma 1 Any ϵ-private (n, m)-quantum cipher satisfy that for all x ∈ {0, 1}^{m}, D(ξ, ρ_{x}) < ϵ.

Proof. Simply observe that,

D(ξ, ρ_{x}) = D (2^{−m} ∑_{y∈{0,1}^{m}} ρ_{y}, ρ_{x}) ≤ ∑_{y∈{0,1}^{m}} 2^{−m}D(ρ_{y}, ρ_{x}) < ϵ,

from the convexity of D(·, ·) and the ϵ-privacy of the quantum cipher. □

2.3 Mutually Unbiased Bases

A set ℬ_{n} = {B_{1}, …, B_{2^{t}}} of 2^{t} orthonormal bases in a Hilbert space of dimension 2^{n} is said to be mutually unbiased (we abbreviate mutually unbiased bases set as mubs) if for all |u⟩ ∈ B_{i} and |v⟩ ∈ B_{j} for i ≠ j, we have |⟨u|v⟩| = 2^{−n/2}. Wootters and Fields[20] have shown that there are mubss of up to 2^{n} + 1 bases in a Hilbert space of dimension 2^{n}, and such sets are maximum. They also give a construction for a maximal mubs in Hilbert spaces of prime-power dimensions. For ℬ_{n} = {B_{b}}_{b∈{0,1}^{t}} a mubs, w ∈ {0, 1}^{n}, and b ∈ {0, 1}^{t}, we denote by |v_{w}^{(b)}⟩ the w-th state in basis B_{b} ∈ ℬ_{n}.

Lawrence, Brukner, and Zeilinger[11] introduced an alternative construction for maximal mubss based on algebra in the Pauli group. Their construction plays an important role in the security analysis of our qkrs. The method for constructing a maximal mubs in ℋ_{n} relies on a special partitioning of all Pauli operators in ℋ_{n}. These operators live in a vector space of dimension 4^{n}. Let Σ = {σ_{x}, σ_{y}, σ_{z}, σ_{11}} (where σ_{11} = 11_{1}) be the set of Pauli operators in ℋ_{1}.

This set forms a basis for all one-qubit operators. A basis for operators on n qubits is constructed as follows for i ∈ {0, …, 4^{n} − 1}:

O_{i} = σ_{μ(1,i)}^{1}σ_{μ(2,i)}^{2} … σ_{μ(n,i)}^{n} = ∏_{k=1}^{n} σ_{μ(k,i)}^{k},  (3)

such that σ_{μ(k,i)}^{k} is an operator in Σ acting only on the k-th qubit. We use the convention O_{0} = 11_{n}. The action of O_{i} on the k-th qubit is σ_{μ(k,i)} where μ(k, i) ∈ {x, y, z, 11}. The basis described in (3) is orthogonal, tr(O_{i}O_{j}) = 2^{n}δ_{i,j} where i = j means that μ(k, i) = μ(k, j) for any qubit k. Every Pauli operator O_{i} is such that O_{i}^{2} = 11_{n}. Apart from the identity 11_{n}, all O_{i}’s are traceless and have eigenvalues ±1.

In [11], it is first shown how to partition the set of 4^{n} − 1 non-trivial Pauli operators {O_{i}}_{i=1}^{4^{n}−1} into 2^{n} + 1 subsets, each containing 2^{n} − 1 commuting members. Second, each such partitioning is shown to define a maximal mubs. Let us denote by P_{β}^{b} = |v_{β}^{(b)}⟩⟨v_{β}^{(b)}| the projector on the β-th vector in basis B_{b}. Saying that ℬ_{n} = {B_{i}}_{i} is a mubs means that tr(P_{α}^{a}P_{β}^{b}) = 2^{−n} when a ≠ b and tr(P_{β}^{b}P_{β′}^{b}) = δ_{β,β′}. Let (ε_{b,β})_{b,β} be a 2^{n} × 2^{n} matrix consisting of orthogonal rows, one of which is all +1, and the remaining ones all contain as many +1 as −1. The b-th partition contains Pauli operators {O_{β}^{b}}_{β=1}^{2^{n}−1} such that

O_{β}^{b} = ∑_{α=1}^{2^{n}} ε_{β,α}P_{α}^{b}.  (4)

In the following, (ε_{β,α})_{β,α} will always denote the operator 2^{n/2}H^{⊗n} where H^{⊗n} is the n-qubit Hadamard transform (i.e. ε_{β,α} = (−1)^{β·α}).

The number of partitions {O_{β}^{b}}_{β} defined by (4) is 2^{n} + 1 when constructed from a maximal mubs. Each partition contains 2^{n} − 1 operators after discarding the identity (they all contain the identity). Each of these operators is traceless and has ±1 eigenvalues as for the Pauli operators. It is easy to verify that for a ≠ b,

tr (O_{α}^{a}O_{β}^{b}) = ∑_{μ,ν} ε_{α,μ}ε_{β,ν} tr (P_{μ}^{a}P_{ν}^{b}) = 0.  (5)

Moreover,

tr (O_{β}^{b}O_{β′}^{b}) = ∑_{μ,ν} ε_{β,μ}ε_{β′,ν} tr (P_{μ}^{b}P_{ν}^{b}) = ∑_{μ} ε_{β,μ}ε_{β′,μ} = 2^{n}δ_{β,β′}.  (6)

It follows from (5) and (6) that all operators in (4) are unitarily equivalent to Pauli operators. This essentially shows that partitioning the Pauli operators the way we want is always possible.

It remains to argue that any such partitioning defines a maximal mubs. Notice that partition {O_{1}^{b}, …, O_{2^{n}−1}^{b}} (i.e. without the identity O_{0}^{b}) defines a unique basis {P_{β}^{b}}_{β} where

P_{β}^{b} = 2^{−n} ∑_{μ} ε_{μ,β}O_{μ}^{b}.  (7)

It is not difficult to verify that tr(P_{β}^{b}P_{β′}^{b}) = δ_{β,β′} and for a ≠ b, tr(P_{β}^{b}P_{α}^{a}) = 2^{−n} thus leading to a maximal mubs.

In other words, there is a one-to-one correspondence between maximal mubss and the partitionings {{O_{β}^{b}}_{β}}_{b} of the 4^{n}−1 Pauli operators (except the identity), acting on n qubits, into 2^{n} +1 partitions {O_{β}^{b}}_{β} of 2^{n} −1 commuting members. Each partition is a subgroup of the n-qubit Pauli group and is generated by n of these operators. Any Pauli operator commutes with all other operators in the partition in which it is, and anti-commutes with exactly half of the operators, including the identity, in all other partitions. See [11] for more details.

2.4 The W_{n}-Cipher

In [8], quantum ciphers based on mubss were introduced and studied with respect to their secret-key uncertainty against known-plaintext attacks. Our qkrs, presented in Sect. 5.1, uses one of these ciphers, the W_{n}-cipher, as its main building block. The W_{n}-cipher is a (2n, n)-quantum cipher, that is, it encrypts n-bit classical messages with the help of a 2n-bit secret-key. The W_{n}-cipher enjoys perfect privacy when the secret-key is perfectly private. It is easy to verify that the cipher is ϵ-private if the secret-key is only ϵ-close to uniform[17].

Let ℬ_{n} = {B_{b}}_{b∈{0,1}^{n}} be a mubs of cardinality 2^{n} for ℋ_{n}. Remember that |v_{w}^{(b)}⟩ denotes the w-th basis state in basis B_{b} ∈ ℬ. The secret-key k for the W_{n}-cipher is conveniently written as k = (z, b) where z, b ∈_{R} {0, 1}^{n}. Encryption according secret-key k = (z, b) of message x ∈ {0, 1}^{n} consists in preparing the following state:

E_{k}|x⟩ = E_{(z,b)}|x⟩ = |v_{x⊕z}^{(b)}⟩ ∈ B_{b}.

In other words, the encryption process first one-time pad message x with key z before mapping the resulting state to basis B_{b}. Encryption and decryption can be performed efficiently on a quantum computer[20, 8].

3 Key-Recycling Schemes

A qkrs is an encryption scheme with authentication. In addition, there are two key-recycling mechanisms, R_{ok}^{n,s} and R_{no}^{n,t}, allowing one to recycle part of the secret-key shared between Alice and Bob in case where the authentication succeeds and fails respectively. We model the recycling mechanism by privacy amplification. That is, R_{ok}^{n,s} and R_{no}^{n,t} are classes of hashing functions mapping the current key k ∈ {0, 1}^{n} into a recycled key k̂ of length s and t respectively. In order to apply privacy amplification, an authentic classical feedback channel is necessary for announcing Bob’s random recycling function R ∈_{R} R_{ok}^{n,s} or R ∈_{R} R_{no}^{n,t} depending on the outcome of authentication. Alice and Bob then compute k̂ = R(k) as their recycled secret-key. We do not allow further interaction between Alice and Bob since otherwise quantum key distribution could take place between them allowing not only to recycle their secret-key but even to increase its length. Key-recycling should be inherently non-interactive from Bob to Alice since the authentication outcome should anyway be made available to Alice. For simplicity, we assume that the classical feedback channel between Bob and Alice is authenticated. In general, a small secret key could be used for providing classical message-authentication on the feedback channel.

Definition 2 A (n, m, s, t)-qkrs is defined by a pair (ℭ^{m,n}, (R_{ok}^{n,s}, R_{no}^{n,t})) where

• ℭ^{m,n} is a (m, n)-quantum cipher, and

• (R_{ok}^{n,s}, R_{no}^{n,t}) is a key-recycling mechanism.

In this paper, the privacy of the recycled key is characterized by its distance from uniform. In [17], it is shown that when the distance is negligible, the key behaves as a perfectly private key except with negligible probability. It follows that the application is composable provided the adversary is static[14, 17, 3].

For a qkrs to be secure, we require that even knowing the plaintext, the function R, and the authentication outcome, the adversary’s view about the recycled key is at negligible distance from uniform. This should hold except for a negligible number of functions in R_{ok}^{n,s} and R_{no}^{n,t}. Security against known plaintext attacks is an important property of good key-recycling mechanisms. Otherwise, extra conditions on the a posteriori probability distribution over plaintexts have to be enforced. In particular a recycled key could be compromised if a previous plaintext gets revealed to the adversary.

The adversary’s view typically changes depending on whether the authentication succeeds or fails. Let 𝒜_{ok} (resp. 𝒜_{no}) be the event consisting in a successful (resp. unsuccessful) authentication. Conditioned on 𝒜_{ok}, the adversary should have access only to very limited amount of information about the secret-key. The better the authentication scheme is, the more key material the recycling mechanism can handle. When 𝒜_{no} occurs, however, the adversary may hold the entire cipherstate. Let K be the random variable for the secret-key. Let ρ(x) be the random state corresponding to the adversary’s view on an encryption of classical message x using a random key. We denote by [ρ_{ok}(x)] = [ρ(x)|𝒜_{ok}] and [ρ_{no}(x)] = [ρ(x)|𝒜_{no}] the random state ρ(x) conditioned on the event 𝒜_{ok} and 𝒜_{no} respectively.

Definition 3 A key-recycling mechanism (R_{ok}^{n,s}, R_{no}^{n,t}) is (δ_{ok}, δ_{no})-indistinguish-able if for all x ∈ {0, 1}^{m}:

1. d(R(K)|ρ_{ok}(x) ⊗ {R}) ≤ δ_{ok} (where R ∈_{R} R_{ok}^{n,s}), and

2. d(R(K)|ρ_{no}(x) ⊗ {R}) ≤ δ_{no} (where R ∈_{R} R_{no}^{n,t}).

For δ_{ok},δ_{no} negligible functions of n, we say that the key-recycling mechanism is statistically indistinguishable. The class of key-recycling functions R_{ok}^{n,s} or R_{no}^{n,t} is said to be δ-indistinguishable if condition 1 or 2 respectively holds relative to δ.

Finally, a qkrs is secure if it is a private encryption scheme together with a statistically indistinguishable key-recycling mechanism. In general,

Definition 4 A (n, m, s, t)-qkrs defined by (ℭ^{m,n}, (R_{ok}^{n,s}, R_{no}^{n,t})) is (ϵ, δ_{ok}, δ_{no})- secure if

1. ℭ^{m,n} is ϵ-private,

2. when no eavesdropping occurs the key-recycling mechanism R_{ok}^{n,s} is used, and

3. (R_{ok}^{n,s}, R_{no}^{n,t}) is a (δ_{ok}, δ_{no})-indistinguishable key-recycling mechanism.

If the scheme is such that ϵ, δ_{ok}, and δ_{no} are all negligible functions of n then we say that the scheme is statistically secure.

The efficiency of a qkrs is characterized by n, s and t. When authentication succeeds n − s bits of secret-key must be thrown away while, when authentication fails, n − t have to be discarded. Clearly, any purely classical key-recycling scheme must have s, t ≤ n − m. This does not have to hold for quantum schemes. However, we show next that quantum schemes suffer the same restrictions as classical ciphers when authentication fails.

4 Upper Bound on Key-Recycling

In this section, we show that any statistically secure qkrs must discard as many key-bits as the length of the plaintext (minus one bit) when the authentication fails. In other words, when authentication fails no qkrs does better than the classical one-time-pad.

When authentication fails, the adversary may have kept the entire ciphertext and may know the plaintext x ∈ {0, 1}^{m}. On the other hand, condition 2 in Definition 3 requires that the key-recycling mechanism satisfies d(R(K)|ρ_{no}(x) ⊗ {R}) ≤ δ(n) where δ(n) is negligible and R ∈_{R} R_{no}^{n,t}. Using (1), it follows that

D([{R(K)} ⊗ ρ_{no}(x) ⊗ {R}], [{U}] ⊗ [ρ_{no}(x) ⊗ {R}]) ≤ δ(n).  (8)

The density operator ρ_{no}(k̂, x, R) = [ρ_{no}(x)|R(K) = k̂] corresponds to the adversary’s view when the plaintext is x, the recycled key is k̂ ∈ {0, 1}^{t}, and the privacy amplification function is R ∈ R_{no}^{n,t}. We have that,

ρ_{no}(k̂, x, R) = ∑_{k:R(k)=k̂} \frac{1}{#R^{−1}(k̂)}E_{k}{|x⟩ \atop ⟨x|} ⊗ {|0⟩ \atop ⟨0|}E_{k}^{†}.  (9)

For convenience, we define ρ_{no}(k̂, x) = \frac{1}{#R_{no}^{n,t}} ∑_{R∈R_{no}^{n,t}} ρ_{no}(k̂, x, R) ⊗ |R⟩⟨R|. If a key-recycling scheme is statistically indistinguishable then for a negligible function δ(n),

δ(n) ≥ d(R(K)|ρ_{no}(x) ⊗ {R})  (10)
= D (∑_{k̂} pK̂(k̂)\begin{matrix}| & k̂ & ⟩ \\ ⟨ & k̂ & | \end{matrix} ⊗ ρ_{no}(k̂, x), 𝕀_{t} ⊗ ∑_{k̂} pK̂(k̂)ρ_{no}(k̂, x)) (11)

≥ \frac{1}{#R_{no}^{n,t}} ∑_{R} ∑_{k̂} 2^{−n}#R^{−1}(k̂)D(ρ_{no}(k̂, x, R), ρ_{x}),  (12)

where (10) follows by definition of statistical indistinguishability, and (11) is obtained using (8) and (9). The last step follows from the fact that D(ρ, σ) = max_{{E_{m}}_{m}} D(p(m), q(m)) where the maximum is computed over all POVMs {E_{m}}_{m} and p(m) = tr(ρE_{m}), q(m) = tr(σE_{m}) are probability distributions for the outcomes of {E_{m}}_{m} when applied to ρ and σ respectively (see for example Theorem 9.1 in [15]). In order to get (12) from (11) one only has to consider a POVM that first measures R and k̂ before performing the POVM {E′_{m}}_{m} (depending on R and k̂) on the residual state that satisfies D(ρ_{no}(k̂, x, R), ρ_{x}) = d(p′(m), q′(m)).

It can be shown that for t ≥ n−m+2, (12) implies the existence of R ∈ R_{no}^{n,t} and k̂_{0} ∈ {0, 1}^{t} such that #R^{−1}(k̂_{0}) ≤ 2^{m−1} and D(ρ_{no}(k̂_{0}, x, R), ρ_{x}) ≤ c for any constant 0 < c ≤ 1. Moreover, since the cipher is statistically private, there exists a negligible function ϵ(n) such that,

D(ρ_{no}(k̂_{0}, x, R), ξ) ≤ D(ξ, ρ_{x}) + D(ρ_{x}, ρ_{no}(k̂_{0}, x, R)) ≤ ϵ(n) + c.  (13)

On the other hand, an argument along the lines of the proof of Lemma IV.3.2 in [5] allows us to conclude that when #R^{−1}(k̂_{0}) ≤ 2^{m−1}, D(ρ_{no}(k̂_{0}, x, R), ξ) ≥ 1/2 which contradicts (13) when c < 1/2 and ϵ(n) is negligible (see Lemma 3 in [9]). Next Theorem, proven in Appendix A, follows:

Theorem 1 (Key-Recycling Bound) Any statistically secure (n, m, s, t)- qkrs is such that t ≤ n − m + 1.

We believe that a more careful analysis would show that statistically secure (n, m, s, t)-qkrs must satisfy t ≤ n − m. Theorem 1 implies that in order to recycle more secret-key bits than any classical scheme, quantum ciphers must provide authentication. It is only when the authentication succeeds that a qkrs may perform better than classical ones.

5 A Near Optimal Quantum Key-Recycling Scheme

We introduce a qkrs, called W_{n}C_{m}, that recycles an almost optimal amount of key material. Moreover, the key-recycling mechanism does not use privacy amplification. Deterministic functions are sufficient to guarantee the statistical indistinguishability of the recycled key. The scheme is introduced in Sect. 5.1. In Sect. 5.2 we present an EPR-version of the scheme and we prove it secure. In Sect. 5.3 we reduce the security of W_{n}C_{m} to that of the EPR-version.

5.1 The Scheme

The W_{n}C_{m}-cipher encrypts a message together with its Wegman-Carter onetime authentication tag[6] using the W_{n}-cipher[8]. We need an authentication code constructed from xor-universal classes of hash-functions:

Definition 5 ([6]) An xor-universal family of hash-functions is a set of functions H_{m,μ} = {h_{u} : {0, 1}^{m} → {0, 1}^{μ}}_{u} such that for all a ≠ b ∈ {0, 1}^{m} and all x ∈ \{0, 1\}^{μ}, #\{h ∈ H_{m,μ}|h(a) ⊕ h(b) = x\} = \frac{#H_{m,μ}}{2^{μ}} .

There exists an xor-universal class of hash-functions H_{m,μ}^{⊕} (for any m ≥ μ) that requires only m bits to specify and such that picking a function at random can be done efficiently.

For the transmission of m-bit messages, W_{n}C_{m} requires Alice and Bob to share a secret-key of size N = 2n + m bits where n = m + ℓ(m), and ℓ(m) ∈ Ω(m) is the size of the Wegman-Carter authentication tag. We denote secret-key k by the triplet: k = (z, b, u) where z, b ∈ {0, 1}^{n} is the key for the W_{n}-cipher and u ∈ {0, 1}^{m} is the description of a random function h_{u} ∈ H_{m,ℓ(m)}^{⊕}. Encrypting message x ∈ {0, 1}^{m} is performed by first computing the Wegman-Carter one-time authentication tag h_{u}(x). The message (x, h_{u}(x)) ∈ {0, 1}^{n} is then encrypted using the W_{n}-cipher with secret-key (z, b). Bob decrypts the W_{n}-cipher and verifies that a message of the form (x, h_{u}(x)) is obtained. Bob announces to Alice the outcome of the authentication using the authenticated feedback channel. When it is successful, Alice and Bob recycle the whole secret-key. If the authentication fails then Alice and Bob throw away the one-time-pad z. The remaining part (b, u) is entirely recycled. In other words, R_{ok}^{N,s} is the identity with s = N and R_{no}^{N,t} is deterministic with t = N − n = N − m − ℓ(m).

Private-Key: (z, b, u) ∈_{R} {0, 1}^{2n+m} where n = m + ℓ(m).

1. Alice creates the message c = (x, h_{u}(x)) where h_{u} ∈ H_{m,ℓ(m)}^{⊕}. She then encrypts this message with key (z, b) according to the W_{n}-cipher.

2. Bob decodes the received W_{n}-cipher with key (z, b) and gets c′ = (x′, t′). He then verifies the authentication tag t′ = h_{u}(x′). Bob sends the result of the test to Alice through a classical authentic channel.

3. [Key-Recycling] If Bob accepts then Alice and Bob recycle the entire key (b, z, u). If Bob rejects then Alice and Bob recycle (b, u) and throw away z ∈ {0, 1}^{n}.

Figure 1: The W_{n}C_{m}.

It is almost straightforward to show that our key-recycling function is perfectly indistinguishable when authentication fails.

Lemma 2 Let N = 2n + m where n = m + ℓ(m),ℓ(m) > 0 be the key-length used in W_{n}C_{m} and let R(z, b, u) = (b, u) for z, b ∈ {0, 1}^{n} and u ∈ {0, 1}^{m}. The key-recycling mechanism R_{no}^{N,N−n} = {R} is 0-indistinguishable.

Proof. Since ρ_{no}((b, u), x, R) = 𝕀_{n} = ρ_{no}((b′, u′), x, R) for all (b, u),(b′, u′), and x, it easily follows that d(R(K)|ρ_{no}(x) ⊗ {R}) = 0. □ Since

W_{n}C_{m} encrypts m-bit messages and recycles N − n bits of key, the scheme is sub-optimal according Theorem 1. In the next sections, we see that W_{n}C_{m} remains statistically secure for any ℓ(m) ∈ Ω(m). It follows that although sub-optimal, W_{n}C_{m} is nearly optimal.

5.2 An EPR variant of W_{n}C_{m}

We establish the security of the key-recycling mechanism in W_{n}C_{m} when the authentication is successful. We prove this case using a Shor-Preskill argument[18] similar to the ones invoked in [16] and [2] for key-recycling and quantum authentication respectively.

We first define a variant of W_{n}C_{m}, called epr-W_{n}C_{m}, using EPR-pairs and having access to an additional authenticated and private classical channel. The key-recycling mechanism of epr-W_{n}C_{m} can be proven secure more easily since it has access to more powerful resources. Second, we show that the security of W_{n}C_{m} follows from the security of epr-W_{n}C_{m}.

In epr-W_{n}C_{m}, Alice and Bob initially share an n-bit key b, and an m-bit key u. They agree on 2^{n} mutually unbiased bases in ℋ_{n}, and a family of xor-universal hash-functions H_{m,μ}^{⊕} = {h_{u}}_{u∈{0,1}^{m}}. As for W_{n}C_{m}, the key b is used to select in which of the bases of the mubs the encryption will take place. The key u indicates the selection of the hash-function for authentication. The key z in epr-W_{n}C_{m} is not shared beforehand but will be implicitly generated by measuring the shared EPR-pairs. This corresponds to refreshing z before each round of epr-W_{n}C_{m}.

In order for Alice to send classical message x ∈ {0, 1}^{m} to Bob, Alice and Bob proceeds as described in Fig. 2. The key-recycling mechanism of epr-W_{n}C_{m} only takes place when authentication succeeds. The quantum transmission in W_{n}C_{m} is replaced by transmitting half of a maximally entangled state consisting of n EPR-pairs.

|Ψ⟩ = ∑_{x∈{0,1}^{n}} 2^{−n/2}|x⟩^{A}|x⟩^{B} = ∑_{x∈{0,1}^{n}} 2^{−n/2}|ξ_{x}^{(b)}⟩^{A}|v_{x}^{(b)}⟩^{B},  (14)

for some orthonormal basis {|ξ_{x}^{(b)}⟩}_{x}.

Any trace-preserving operator the adversary can apply to Bob’s half EPRpairs can be described in terms of the 4^{n} Pauli operators,

ρ̂ = ℰ({|Ψ⟩ \atop ⟨Ψ|}) = ∑_{i=0}^{4^{n}−1} ∑_{j=0}^{4^{n}−1} c_{i}\overline{c_{j}}(11_{n} ⊗ O_{i}){|Ψ⟩ \atop ⟨Ψ|}(11_{n} ⊗ O_{j})^{†},  (15)

where O_{0} = 11_{n}. We can split (15) into the case where the error leaves the state untouched, and the case where the state is changed

ρ̂ = |c_{0}|^{2}{|Ψ⟩ \atop ⟨Ψ|} + (1 − |c_{0}|^{2})ρ_{E}^{b,u},  (16)

where ρ_{E}^{b,u} = ∑_{(i,j)≠(0,0)} \frac{c_{i}\overline{c_{j}}}{(1−|c_{0}|^{2})}(11_{n} ⊗ O_{i})|Ψ⟩⟨Ψ|(11_{n} ⊗ O_{j})^{†}, and |c_{0}|^{2} is the probability that the state is left unchanged by ℰ.

The idea behind the security of the key-recycling mechanism is that an eavesdropper, performing any non-trivial action upon Bob’s system, will fail authentication with high probability. Any eavesdropping strategy that remains undetected with a not too small probability is such that |c_{0}|^{2} is at negligible distance from 1. This means that the ciphertext will be left untouched with probability essentially 1. In other words the probability of being detected is closely related to 1 − |c_{0}|^{2}.

The probability that Bob will accept the authentication tag, when Alice and Bob share key (b, u) can be expressed by the observable projecting onto Private-Key: (b, u) ∈_{R} {0, 1}^{n+m}.

1. Alice prepares the n EPR-pairs in state |Ψ⟩^{AB}.

2. Alice sends the B-register to Bob.

3. Bob acknowledges receiving the state using the classical authentic feedback channel.

4. Alice measures her A-register in basis {|ξ_{c}^{(b)}⟩}_{c∈{0,1}^{n}} (See (14)). On classical outcome c, she computes z := c ⊕ (x, h_{u}(x)).

5. Alice sends z to Bob through the additional private and authenticated classical channel.

6. Bob measures his B-register in the b-th basis of the mubs, gets outcome c′, and computes (x′, t′) = c′ ⊕ z. Bob verifies that t′ = h_{u}(x′) and announces the result to Alice through the classical authenticated feedback channel.

7. If Bob accepts, Alice and Bob recycle the whole key (b, u).

Figure 2: The epr-W_{n}C_{m}-cipher using an extra private and authentic classical channel.

the space of states where Alice has her untouched EPR-halves, and Bob has anything that passes the authentication test:

Π_{Acc}^{b,u} = ∑_{z∈{0,1}^{n}} ∑_{x̂∈{0,1}^{m}} |ξ_{e_{z,u}(x)}^{(b)}⟩⟨ξ_{e_{z,u}(x)}^{(b)}| ⊗ |v_{e_{z,u}(x̂)}^{(b)}⟩⟨v_{e_{z,u}(x̂)}^{(b)}|,  (17)

where e_{z,u}(x) = z ⊕ (x, h_{u}(x)). The probability that Bob will accept the authentication, when using key (b, u), is p_{Acc}^{b,u} = tr(Π_{Acc}^{b,u}ρ̂).

As mentioned in Sect. 2.3, all 4^{n}−1 Pauli operators (excluding the identity) are partitioned into 2^{n} + 1 sets, each containing 2^{n} − 1 commuting members. Each operator, O_{i}, appearing in (15), will be in one of the 2^{n}+1 partitions (i.e. which each forms a subgroup). In the partition or basis where an error operator O_{i} belongs, its action will leave all cipherstates unchanged. For each other 2^{n} basis b, O_{i} will anti-commute with exactly half the operators (including the identity). This means that in basis b, the action of O_{i} permutes the basis vectors. Since this permutation is independent of the authentication code, we can show that the probability for O_{i} to remain undetected is negligible when the class of Wegman-Carter authentication functions is xor-universal. Let ρ̂_{Acc}^{b,u} be the normalized state conditioned on 𝒜_{ok} defined as,

ρ̂_{Acc}^{b,u} = \frac{Π_{Acc}^{b,u}ρ̂Π_{Acc}^{b,u}}{tr (Π_{Acc}^{b,u}ρ̂)}.  (18)

We are going to estimate the average fidelity^{2} of ρ̂_{Acc}^{b,u} to the ideal state |Ψ⟩⟨Ψ|. To do so we split ρ̂ according to (16) and use the concavity of the fidelity, F (ρ̂_{Acc}^{b,u}, |Ψ⟩⟨Ψ|) ≥ \frac{|c_{0}|^{2}}{p_{Acc}^{b,u}}. Applying (16) to p_{Acc}^{b,u}, gives us

F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ \frac{|c_{0}|^{2}}{|c_{0}|^{2} + (1 − |c_{0}|^{2}) tr (Π_{Acc}^{b,u}ρ_{E}^{b,u})}.

To lower bound the average fidelity, ∑_{b,u} 2^{−n−m}F (ρ̂_{Acc}^{b,u}, |Ψ⟩⟨Ψ|). We split the sum into keys (bases and authentication keys) for which tr(Π_{Acc}^{b,u}ρ_{E}^{b,u}) is small, and keys for which this probability is large. We know from the previous argument, that the probability of accepting a non-trivial error will be small in most bases, and indeed the terms with tr(Π_{Acc}^{b,u}ρ_{E}^{b,u}) negligible compared to |c_{0}|^{2} give the main contribution to the fidelity.

In summary, an undetected attack is almost always trivial since it corresponds to the case where no eavesdropping occurred. Next Theorem, proven in Appendix B, gives the desired result.

Theorem 2 For all adversary strategies for which p_{Acc} ≥ 2^{−(n−m−2)/2+1},

∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} 2^{−n−m}F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ 1 − 2^{− \frac{n−m−2}{4} +1},

provided n is sufficiently large.

Let ρ_{ok}^{epr}(x) be the random state corresponding to the adversary’s view in epr-W_{n}C_{m} given 𝒜_{ok}. Let K = (B, U, Z) be the random variable describing the key (b, u) ∈ {0, 1}^{n} × {0, 1}^{m}, and z ∈ {0, 1}^{n} computed from the measurement outcome. Using the same line of arguments as [3] (for completeness, the proof can be found in Appendix C), Theorem 2 implies that:

Theorem 3 For all adversary strategies for which p_{Acc} ≥ 2^{−(n−m−2)/2+1},

d(K|ρ_{ok}^{epr}(x) ⊗ \{R\}) ≤ 2^{− \frac{(n−m−2)}{8} +1},

provided n is sufficiently large.

2Where the fidelity F (ρ̂_{Acc}^{b,u}, |Ψ⟩⟨Ψ|) = ⟨Ψ|ρ̂_{Acc}^{b,u}|Ψ⟩.

5.3 Back to W_{n}C_{m}

We now show that Theorem 3 also applies to W_{n}C_{m}. Similarly to other Shor-Preskill arguments[18, 2, 16], we transform epr-W_{n}C_{m} into W_{n}C_{m} by simple modifications leaving the adversary’s view unchanged.

In Step 4 of epr-W_{n}C_{m}, Alice measures her part of the entangled pair in order to extract c ∈ {0, 1}^{n}. Instead, she could have measured already in Step 1 since the measurement commutes with everything the adversary and Bob do up to Step 4. Measuring half the EPR-pairs immediately after creating them is equivalent to Alice preparing c ∈_{R} {0, 1}^{n} before sending |v_{c}^{(b)}⟩ in Step 2.

Instead of picking c ∈_{R} {0, 1}^{n} in Step 1, Alice could choose z ∈_{R} {0, 1}^{n} at random before sending |v_{z⊕(x,h_{u}(x))}^{(b)}⟩ to Bob. All these modifications change nothing to the adversary’s view.

Now, sending z through the private and authenticated classical channel in Step 5 becomes unnecessary if Alice and Bob share z before the start of the protocol (thus making z part of the key). We have now removed the need for the private and authenticated classical channel.

The resulting protocol is such that Bob first acknowledges receiving the cipher, then measures it, and finally replies with either accept or reject. The acknowledgment of Step 3 is unnecessary and can safely be postponed to Bob’s announcement in Step 6. The epr-W_{n}C_{m}-cipher has now been fully converted into the W_{n}C_{m}-cipher without interfering with the eavesdropper’s view. It follows directly that Theorem 3 also applies to W_{n}C_{m}.

Theorem 3 shows that one use of the W_{n}C_{m}-cipher leaves the secret-key at negligible distance from uniform when it was initially 0-indistinguishable. In general, if a random variable K is at distance no more than ϵ from uniform then K behaves exactly like a uniform random variable except with probability at most ϵ[17]. Our main result follows:

Theorem 4 (Main Result) Let n = m + ℓ(m). For all adversary strategies the W_{n}C_{m}-cipher used with an initial ϵ-indistinguishable private-key satisfies,

1. either d(K|ρ_{ok}(x) ⊗ \{R\}) ≤ ϵ + 2^{− \frac{ℓ(m)−2}{8} +1} or p_{Acc} ≤ 2^{−(ℓ(m)−2)/2+1},

2. d(K|ρ_{no}(x) ⊗ {R}) ≤ ϵ,

provided n is sufficiently large.

In other words, the key-recycling mechanism is statistically indistinguishable when ℓ(m) ∈ Ω(m). It follows that, when starting from a statistically indistinguishable secret-key, key-recycling can take place exponentially many times without compromising the statistical indistinguishability of the resulting key. As mentioned in Sect. 3, Theorem 4 and the discussion in [17] imply that the W_{n}C_{m}-cipher is universally composable against static adversaries.

6 Conclusion and Open Questions

We have shown that the W_{n}C_{m}-cipher is an almost optimal key-recycling cipher with one-bit feedback. There are many possible improvements of our scheme. In this paper, we assume noiseless quantum communication. This is of course an unrealistic assumption. Our scheme can easily be made resistant to noise by encoding the quantum cipher using a quantum error-correcting code. Since a quantum error-correcting code is also a secret-sharing[7], it can be shown that when authentication succeeds almost no information about the cipherstate is available to the eavesdropper. On the other hand, if the eavesdropper gains information about the cipherstate then authentication will fail similarly to the case where no error-correction is used.

It would be interesting to show that the key recycling bound(i.e. Theorem 1) can be improved to t ≤ n−m (instead of n−m+1) as for classical schemes. It is an open question whether there exists a qkrs achieving this upper bound.

It is also possible to allow for more key-recycling mechanisms associated to different output values for the authentication process. Such a generalized scheme would allow to recycle key-material as a function of the adversary’s available information but would require more than one-bit feedback.

It is easy to see that the W_{n}C_{m}-cipher can be used as a re-usable quantum authentication scheme when authentication succeeds. Our construction (using mubss) is different than the ones based on purity testing codes[2] and may be of independent interest.

Acknowledgments. The authors would like to thank M. Horodecki, D. Leung, and J. Oppenheim for enlightening discussions. We are also grateful to the program committee for valuable comments and suggestions.

References

[1] A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf. Private quantum channels. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science — FOCS 2000, pages 547–553, 2000.

[2] H. Barnum, C. Crépeau, D. Gottesman, A. Smith, and A. Tapp. Authentication of quantum messages. In Proc. 43rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’02), pages 449–458, 2002.

[3] M. Ben-Or, M. Horodecki, D. W. Leung, D. Mayers, and J. Oppenheim. The universal composable security of quantum key distribution. In J. Kilian, editor, Theory of Cryptography — TCC 2005, volume 3378 of Lecture Notes in Computer Science, pages 386–406. Springer-Verlag Heidelberg, 2005.

[4] C. H. Bennett, G. Brassard, and S. Breidbart. Quantum cryptography II: How to re-use a one-time pad safely even if P = NP. Unpublished manuscript, 1982.

[5] R. Bhatia. Matrix Analysis. Graduate Texts in Mathematics. Springer-Verlag, 1997.

[6] J. L. Carter and M. N. Wegman. Universal classes of hash functions (extended abstract). In Proceedings of the 9th ACM Symposium on Theory of Computing — STOC 1977, pages 106–112. ACM Press, 1977.

[7] R. Cleve, D. Gottesman, and H.-K. Lo. How to share a quantum secret. Physical Review Letter, 83(3):648–651, 1999.

[8] I. B. Damgård, T. B. Pedersen, and L. Salvail. On the key-uncertainty of quantum ciphers and the computational security of one-way quantum transmission. In Advances in Cryptology — EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 91–108. Springer-Verlag Heidelberg, 2004.

[9] I. B. Damgård, T. B. Pedersen, and L. Salvail. A quantum cipher with near optimal key-recycling. rs RS-05-17, BRICS, Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Aarhus C, Denmark, 2005.

[10] S. Dziembowski and U. M. Maurer. On generating the initial key in the bounded-storage model. In Advances in Cryptology — EUROCRYPT 2004, pages 126–137, 2004.

[11] J. Lawrence, Č. Brukner, and A. Zeilinger. Mutually unbiased binary observable sets on N qubits. Physical Review A, 65(3), 2002.

[12] D. W. Leung. Quantum vernam cipher. Quantum Information and Computation, 2(1):14–34, 2002.

[13] C.-J. Lu. Encryption against storage-bounded adversaries from on-line strong extractors. Journal of Cryptology, 17(1):27–42, 2004.

[14] J. B. Nielsen. Private communication, 2005.

[15] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge university press, 2000.

[16] J. Oppenheim and M. Horodecki. How to reuse a one-time pad and other notes on authentication, encryption and protection of quantum information. Available at http://arxiv.org/abs/quant-ph/0306161.

[17] R. Renner and R. König. Universally composable privacy amplification against quantum adversaries. In J. Kilian, editor, Theory of Cryptography — TCC 2005, volume 3378 of Lecture Notes in Computer Science, pages 407–425. Springer-Verlag Heidelberg, 2005.

[18] P. W. Shor and J. Preskill. Simple proof of security of the BB84 quantum key distribution protocol. Physical Review Letters, 85:441–444, 2000.

[19] S. P. Vadhan. On constructing locally computable extractors and cryptosystems in the bounded storage model. Journal of Cryptology, 17(1):43– 77, 2004.

[20] W. K. Wootters and B. D. Fields. Optimal state-determination by mutually unbiased measurements. Annals of Physics, 191(2):363–381, 1989.

A Proof of Theorem 1

The following lemma will be useful in the proof of Theorem 1.

Lemma 3 Let 0 < c ≤ 1 be a constant. Let R_{no}^{n,t} be a statistically indistinguishable key-recycling mechanism in case of authentication failure. Then, there exists R ∈ R_{no}^{n,t} and k̂ ∈ {0, 1}^{t} such that

1. D(ρ_{no}(k̂, x, R), ρ_{x}) ≤ c, and

2. #R^{−1}(k̂) ≤ 2^{n−t+1}.

Proof. Suppose for a contradiction that for all R ∈ R_{no}^{n,t}, all k̂ ∈ {0, 1}^{t}, and a constant c < 1/2 either

• D(ρ_{no}(k̂, x, R), ρ_{x}) > c, or

• #R^{−1}(k̂) > 2^{n−t+1}.

Let δ(n) be a negligible function such that R_{no}^{n,t} is δ(n)–indistinguishable. We define K^{∗}(R) = {k̂ | D(ρ_{no}(k̂, x, R), ρ_{x}) > c_{n}} as the set of recycled keys for which condition 1 is not satified under R. Remember that Pr (K̂ = k̂ | R) = 2^{−n}#R^{−1}(k̂) where K̂ is the random variable for the recycled key. Using (12), we easily get

δ(n) ≥ \frac{1}{#R_{no}^{n,t}} ∑_{R} ∑_{k̂} 2^{−n}#R^{−1}(k̂)D(ρ_{no}(k̂, x, R), ρ_{x})

≥ \frac{1}{#R_{no}^{n,t}} ∑_{R} ∑_{k̂∈K^{∗}(R)} 2^{−n}#R^{−1}(k̂) · c

= \frac{c}{#R_{no}^{n,t}} ∑_{R} Pr (k̂ ∈ K^{∗}(R) | R)
= c · Pr (k̂ ∈ K^{∗}(R)),

which implies

Pr (k̂ ∈ K^{∗}(R)) ≤ \frac{δ(n)}{c}.  (19)

On the other hand, when k̂ ∉ K^{∗}(R) it must be the case that #R^{−1}(k̂) > 2^{n−t+1}. However, by definition of a statistically indistinguishable key-recycling mechanism,

δ(n) ≥ d(R(K) | ρ_{no}(x) ⊗ {R}) ≥ d(R(K) | {R})
≥ \frac{1}{2} ∑_{R} \frac{1}{#R_{no}^{n,t}} ∑_{k̂∉K^{∗}(R)} Pr (K̂ = k̂ | R) − 2^{−t}

≥ \frac{1}{2} ∑_{R} \frac{1}{#R_{no}^{n,t}} ∑_{k̂∉K^{∗}(R)} \frac{Pr (K̂ = k̂ | R)}{2}

= \frac{1}{4}(1 − \frac{δ(n)}{c}),

which is clearly impossible when δ(n) is negligible. It follows that conditions 1 and 2 must be satisfied by some R and k̂. □

We are now ready to prove Theorem 1. Proofof Theorem 1. Suppose for a contradiction the existence of a statistically indistinguishable key-recycling mechanism such that t = n − m + 2. By Lemma 3, there exists R and k̂_{0} such that D(ρ_{no}(k̂_{0}, x, R), ρ_{x}) ≤ c < \frac{1}{2}, and #R^{−1} ≤ 2^{n−t+1} = 2^{m−1}. From Lemma 1, D(ξ, ρ_{x}) < ϵ(n) for negligible ϵ(n). Using the triangle inequality together with (12), it follows that

D(ρ_{no}(k̂_{0}, x, R), ξ) ≤ D(ξ, ρ_{x}) + D(ρ_{x}, ρ_{no}(k̂_{0}, x, R)) ≤ ϵ(n) + c.  (20)

On the other hand, we can lower bound the trace-norm distance between ρ_{no}(k̂_{0}, x, R) and ξ using a similar argument as in the proof of Lemma IV.3.2 in [5]. We rewrite the operator ρ_{no}(k̂_{0}, x, R) − ξ as P − N, where P, and N are positive operators with orthogonal support. We then have,

D(ρ_{no}(k̂_{0}, x, R), ξ) = \frac{1}{2} tr (|ρ_{no}(k̂_{0}, x, R) − ξ|) = \frac{1}{2} tr (P + N) .

Since ρ_{no}(k̂_{0}, x, R)−ξ = P −N, we define the operator C = ρ_{no}(k̂_{0}, x, R)+N = ξ + P so that,

D(ρ_{no}(k̂_{0}, x, R), ξ) = \frac{1}{2} tr (C − ξ + C − ρ_{no}(k̂_{0}, x, R))

≥ \frac{1}{2} ∑_{i} 2λ_{i}^{↓}(C) − λ_{i}^{↓}(ξ) − λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R)),

where λ_{i}^{↓}(C) are the eigenvalues of C in decreasing order. By Weyl’s monotonicity theorem, λ_{i}^{↓}(C) ≥ λ_{i}^{↓}(ξ) and λ_{i}^{↓}(C) ≥ λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R)) for all i. Applying these inequalities and subtracting from λ_{i}^{↓}(C) the largest of the values λ_{i}^{↓}(ξ) and λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R)), lead to

D(ρ_{no}(k̂_{0}, x, R), ξ) ≥ \frac{1}{2} ∑_{i} λ_{i}^{↓}(C) − min\{λ_{i}^{↓}(ξ), λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R))\}
≥ \frac{1}{2} ∑_{i} (max\{λ_{i}^{↓}(ξ), λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R))\}
− min{λ_{i}^{↓}(ξ), λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R))})

= \frac{1}{2} ∑_{i} |λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R)) − λ_{i}^{↓}(ξ)|.  (21)

The eigenvalues of ξ are λ(ξ) = λ(∑_{k} 2^{−n}M_{k}), where M_{k} = ∑_{x} 2^{−m}E_{k}|x⟩⟨x|⊗ |0⟩⟨0|E_{k}^{†} is a rank 2^{m} matrix with eigenvalues 2^{−m}. By Lidskii’s theorem (for example see equation III.13 in [5]) λ^{↓}(∑_{k} 2^{−n}M_{k}) ≺ ∑_{k} 2^{−n}λ^{↓}(M_{k}) which is the vector where the first 2^{m} entries are 2^{−m}, and the remaining ones are all 0’s^{3} This means that the largest eigenvalue of ξ is at most 2^{−m}. Since the rank of ρ_{no}(k̂_{0}, x, R) cannot exceed the cardinality of R^{−1}(k̂_{0}) which by assumption is 2^{m−1}, (21) is minimized when λ_{i}^{↓}(ρ_{no}(k̂_{0}, x, R)) = 2^{−m+1}, for i = 1, …, 2^{m−1}, and λ_{i}^{↓}(ξ) = 2^{−m}, for i = 1, …, 2^{m}. We finally get,

D(ρ_{no}(k̂_{0}, x, R), ξ) ≥ \frac{1}{2} (2^{m−1}(2^{−m+1} − 2^{−m}) + (2^{m} − 2^{m−1})2^{−m}) = \frac{1}{2}. (22)

Equation 20 and (22) lead to the desired contradiction since ϵ(n) + c < 1/2 for n sufficiently large. □

B Proof of Theorem 2

The following Lemma is the main tool for proving Theorem 2.

Lemma 4 Let p_{Acc} = ∑_{b,u} 2^{−m−n} tr(Π_{Acc}^{b,u}ρ̂) be the probability that Bob accepts the authentication (when probability is taken over all keys), and let |c_{0}|^{2} be defined as in (15), then

p_{Acc} ≤ |c_{0}|^{2} + 2^{−n+m+2}.

Proof. The probability that Bob will accept the authentication, when probability is taken over all keys (b, u), is p_{Acc} = 2^{−n−m} ∑_{b,u} tr(Π_{Acc}^{b,u}ρ̂). Applying (16) we rewrite the trace as tr(Π_{Acc}^{b,u}ρ̂) = |c_{0}|^{2} tr(|Ψ⟩⟨Ψ|)+(1−|c_{0}|^{2}) tr(Π_{Acc}^{b,u}ρ_{E}^{b,u}), and we get

p_{Acc} = |c_{0}|^{2} + (1 − |c_{0}|^{2})2^{−n−m} ∑_{b∈{0,1}^{n}} ∑_{u∈{0,1}^{m}} tr (Π_{Acc}^{b,u}ρ_{E}^{b,u}) .  (23)

Since ρ_{E}^{b,u} = ∑_{(i,j)≠(0,0)} \frac{c_{i}\overline{c_{j}}}{(1−|c_{0}|^{2})}(11_{n} ⊗ O_{i})|Ψ⟩⟨Ψ|(11_{n} ⊗ O_{j})^{†}, the trace of (23) is

∑_{(i,j)≠(0,0)} \frac{c_{i}\overline{c_{j}}}{(1 − |c_{0}|^{2})}2^{−n} ∑_{k,l∈\{0,1\}^{m}} tr (Π_{Acc}^{b,u} (|ξ_{k}^{(b)}⟩⟨ξ_{l}^{(b)}| ⊗ O_{i}|v_{k}^{(b)}⟩⟨v_{l}^{(b)}|O_{j}^{†})) .

(24)

3(x_{1}, …, x_{n}) ≺ (y_{1}, …, y_{n}) means that vector x is majorized by vector y. That is, ∑_{i=1}^{ℓ} x_{i} ≤ ∑_{i=1}^{ℓ} y_{i} for all 1 ≤ ℓ ≤ n.

Using the notation from Sect. 2.3 (i.e. P_{a}^{b} := |v_{a}^{(b)}⟩⟨v_{a}^{(b)}|), and applying the equality tr(A ⊗ B) = tr(A) tr(B), the inner sum of (24) becomes

∑_{k,l∈{0,1}^{m}} tr (Π_{Acc}^{b,u} (|ξ_{k}^{(b)}⟩⟨ξ_{l}^{(b)}| ⊗ O_{i}|v_{k}^{(b)}⟩⟨v_{l}^{(b)}|O_{j}^{†}))

= ∑_{k,l,x̂∈{0,1}^{m}} ∑_{z∈{0,1}^{n}} tr (|ξ_{e_{z,u}(x)}^{(b)}⟩⟨ξ_{e_{z,u}(x)}^{(b)}||ξ_{k}^{(b)}⟩⟨ξ_{l}^{(b)}|) tr (|v_{e_{z,u}(x̂)}^{(b)}⟩⟨v_{e_{z,u}(x̂)}^{(b)}|O_{i}|v_{k}^{(b)}⟩⟨v_{l}^{(b)}|O_{j}^{†})

= ∑_{z∈{0,1}^{n}} ∑_{x̂∈{0,1}^{m}} tr (P_{e_{z,u}(x̂)}^{b}O_{i}P_{e_{z,u}(x)}^{b}O_{j}^{†}) . (25)

We further re-write the trace by writing the two projectors as linear combinations of Pauli operators as in (7). This way, the trace in (25) can be re-written as

tr ((2^{−n} ∑_{μ′∈{0,1}^{n}} ε_{(μ′,e_{z,u}(x̂))}O_{μ′}^{b}) O_{i} (2^{−n} ∑_{μ∈{0,1}^{n}} ε_{(μ,e_{z,u}(x))}O_{μ}^{b}) O_{j}^{†})

= 2^{−2n} ∑_{μ,μ′∈{0,1}^{n}} ε_{(μ′,e_{z,u}(x̂))}ε_{(μ,e_{z,u}(x))} tr (O_{μ′}^{b}O_{i}O_{μ}^{b}O_{j}^{†})

= 2^{−2n} ∑_{μ,μ′∈{0,1}^{n}} ε_{(μ′,e_{z,u}(x̂))}ε_{(μ,e_{z,u}(x))}(−1)^{Com(O_{i},O_{μ}^{b})} tr (O_{μ′}^{b}O_{μ}^{b}O_{i}O_{j}^{†}) , (26)

where Com(O_{i}, O_{μ}^{b}) is 0 if O_{i} and O_{μ}^{b} commute, and 1 if they anti-commute. Since both O_{i} and O_{μ}^{b} are Pauli operators they will either commute or anticommute.

Using the fact that (ε_{α,β})_{α,β} represents the operator 2^{n/2}H^{⊗n} and summing ε_{(μ′,e_{z,u}(x̂))}ε_{(μ,e_{z,u}(x))} over z, we see that

∑_{z∈{0,1}^{n}} ε_{(μ′,e_{z,u}(x̂))}ε_{(μ,e_{z,u}(x))} = ∑_{z∈{0,1}^{n}}(−1)^{μ′·(z⊕(x̂,h_{u}(x̂)))}(−1)^{μ·(z⊕(x,h_{u}(x)))}
= ∑_{z∈{0,1}^{n}}(−1)^{z·(μ⊕μ′)⊕μ′·(x̂,h_{u}(x̂))⊕μ·(x,h_{u}(x))}
= 2^{n}δ_{μ,μ′}(−1)^{μ′·(x̂,h_{u}(x̂))⊕μ·(x,h_{u}(x))}.  (27)

We insert (26) into (25) while using (27) and the fact that (O_{μ}^{b})^{2} = 11_{n}:

∑_{k,l∈{0,1}^{m}} tr (Π_{Acc}^{b,u}|ξ_{k}^{(b)}⟩⟨ξ_{l}^{(b)}| ⊗ O_{i}|v_{k}^{(b)}⟩⟨v_{l}^{(b)}|O_{j}^{†})

= ∑_{x̂∈{0,1}^{m}} 2^{−2n} ∑_{μ∈{0,1}^{n}} 2^{n}(−1)^{μ·(x̂,h_{u}(x̂))⊕μ·(x,h_{u}(x))}(−1)^{Com(O_{i},O_{μ}^{b})} tr (O_{i}O_{j}^{†}) , (28)

which is non-zero only when i = j, since tr(O_{i}O_{j}^{†}) = δ_{i,j}2^{n}. Inserting (28) into (24), we get

∑_{i≠0} \frac{2^{−n}|c_{i}|^{2}}{(1 − |c_{0}|^{2})} ∑_{x̂∈\{0,1\}^{m}} ∑_{μ∈\{0,1\}^{n}}(−1)^{μ·((x̂,h_{u}(x̂))⊕(x,h_{u}(x)))}(−1)^{Com(O_{i},O_{μ}^{b})}. (29)

Let μ_{0} ∈ {0, 1}^{m} be the first m bits of μ, and μ_{1} ∈ {0, 1}^{n−m} the last n−m bits of μ. We can now use the properties of xor-universal classes of hash-functions to upper bound

∑_{x̂∈{0,1}^{m}} ∑_{u∈{0,1}^{m}}(−1)^{μ·((x̂,h_{u}(x̂))⊕(x,h_{u}(x)))}.  (30)

When x̂ = x, the whole sum is 2^{2m} so (30) is

2^{2m} + ∑_{x̂∈{0,1}^{m},x̂≠x}(−1)^{μ_{0}·(x̂⊕x)} ∑_{u∈{0,1}^{m}}(−1)^{μ_{1}·(h_{u}(x̂)⊕h_{u}(x))}.  (31)

If μ_{1} = 0 then the inner sum is 2^{m}, else it is zero since, by the definition of xor-universal hash-functions, each n bit string occurs the same number of times:

2^{2m} + δ_{μ_{1},0}2^{m} ∑_{x̂∈{0,1}^{m},x̂≠x}(−1)^{μ_{0}·(x̂⊕x)}.  (32)

The last sum is 2^{m} if μ_{0} = 0, else it is −1, since the only element x̂ ⊕ x we do not include in the sum is the bit-string of m zeros. We get,

∑_{x̂∈{0,1}^{m}} ∑_{u∈{0,1}^{m}}(−1)^{μ·((x̂,h_{u}(x̂))⊕(x,h_{u}(x)))} = 2^{2m} + δ_{μ_{1},0}2^{m}(δ_{μ_{0},0}2^{m} − (1 − δ_{μ_{0},0}))
≤ 2^{2m} + δ_{μ,0}(2^{2m} + 2^{m}).  (33)

Inserting (29) into (23) using (33), we get

p_{Acc} = |c_{0}|^{2} + (1 − |c_{0}|^{2})2^{−n−m} ∑_{b∈{0,1}^{n}} ∑_{u∈{0,1}^{m}} tr (Π_{Acc}^{b,u}ρ_{E}^{b,u})

= |c_{0}|^{2}+2^{−2n−m} ∑_{b∈{0,1}^{n}} ∑_{i≠0} |c_{i}|^{2} ∑_{μ∈{0,1}^{n}} ∑_{x̂∈{0,1}^{m}} ∑_{u∈{0,1}^{m}}(−1)^{μ·((x̂,h_{u}(x̂))⊕(x,h_{u}(x)))}(−1)^{Com(O_{i},O_{μ}^{b})}

≤ |c_{0}|^{2} + 2^{−2n−m} ∑_{b∈{0,1}^{n}} ∑_{i≠0} |c_{i}|^{2} ∑_{μ}(2^{2m} + δ_{μ,0}(2^{2m} + 2^{m}))(−1)^{Com(O_{i},O_{μ}^{b})}. (34)

When μ = 0, Com(O_{i}, O_{μ}^{b}) = 0 and (34) becomes

|c_{0}|^{2} + 2^{−n−m} ∑_{i≠0} |c_{i}|^{2}(2^{2m+1} + 2^{m}).  (35)

Since the Pauli operator O_{i} anti-commutes with exactly half the Pauli operators (including the identity) in all bases except one, in which it commutes with all the operators, summing (−1)^{Com(O_{i},O_{μ}^{b})} over terms μ ≠ 0 is (2^{n} − 1) if O_{i} ∈ {O_{μ}^{b}}_{μ}, and −1 otherwise (since O_{i} ≠ 11_{n}). Let b_{i} be the basis where O_{i} commutes with all operators. In this case (34) becomes

|c_{0}|^{2} + 2^{−2n−m} ∑_{i≠0} |c_{i}|^{2}2^{2m} ((2^{n} − 1) + ∑_{b≠b_{i}} −1)

= |c_{0}|^{2} + 2^{−2n−m} ∑_{i≠0} |c_{i}|^{2}2^{2m}((2^{n} − 1) − (2^{n} − 1)) = 0. (36)

Thus, (34) can finally be re-written as,

|c_{0}|^{2}+2^{−n−m} ∑_{i≠0} |c_{i}|^{2}(2^{2m+1}+2^{m}) ≤ |c_{0}|^{2}+2^{−n+m+2}(1−|c_{0}|^{2}) ≤ |c_{0}|^{2}+2^{−n+m+2}, (37)

which completes the proof. □

We are now ready to prove Theorem 2. Proofof Theorem 2.

Let an adversary strategy be given, such that p_{Acc} ≥ 2^{−(1−γ)(n−m−2)+1}, for some 0 < γ < 1.

Note first that, when |c_{0}|^{2} = 1, the eavesdropper does not interfere with the shared state |Ψ⟩⟨Ψ|, and the average fidelity ∑_{b,u} 2^{−m−n}F (ρ̂_{Acc}^{b,u}, |Ψ⟩⟨Ψ|) = 1. When |c_{0}|^{2} = 0, Lemma 4 implies that p_{Acc} ≤ 2^{−(n−m−2)}, which can only be possible if γ ≤ 0, which contradicts γ > 0. In the rest of this proof, we assume that 0 < |c_{0}|^{2} < 1.

Let p_{E}^{b,u} = tr(Π_{Acc}^{b,u}ρ_{E}^{b,u}). Using (16) we define,

ρ̂_{Acc}^{b,u} = Π_{Acc}^{b,u}ρ̂Π_{Acc}^{b,u}/p_{Acc}^{b,u} = \frac{|c_{0}|^{2}}{p_{Acc}^{b,u}} {|Ψ⟩ \atop ⟨Ψ|} + \frac{(1 − |c_{0}|^{2})}{p_{Acc}^{b,u}}Π_{Acc}^{b,u}ρ_{E}^{b,u}Π_{Acc}^{b,u}

= \frac{|c_{0}|^{2}}{p_{Acc}^{b,u}} {|Ψ⟩ \atop ⟨Ψ|} + \frac{(1 − |c_{0}|^{2})p_{E}^{b,u}}{p_{Acc}^{b,u}} ρ̃,  (38)

where ρ̃ = Π_{Acc}^{b,u}ρ_{E}^{b,u}Π_{Acc}^{b,u}/p_{E}^{b,u} when p_{E}^{b,s} ≠ 0, and is arbitrary otherwise. By the concavity of the fidelity, after discarding ρ̃, gives

F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ \frac{|c_{0}|^{2}}{p_{Acc}^{b,u}} F ({|Ψ⟩ \atop ⟨Ψ|}, {|Ψ⟩ \atop ⟨Ψ|}) = \frac{|c_{0}|^{2}}{tr (Π_{Acc}^{b,u}ρ̂)}.  (39)

Applying (16) to tr(Π_{Acc}^{b,u}ρ̂), and using the linearity of the trace

F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ \frac{|c_{0}|^{2}}{|c_{0}|^{2} + (1 − |c_{0}|^{2})p_{E}^{b,u}} .  (40)

Lemma 4 states that when |c_{0}|^{2} is small, then so is the probability of accepting the authentication is small for most keys. We split the sum,

\frac{1}{2^{n+m}} ∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ,  (41)

up in key-pairs, (b, u), for which p_{E}^{b,u} is larger than a threshold t, and key-pairs where p_{E}^{b,u} is smaller than t. We define,

L_{t} := {(b, u)| p_{E}^{b,u} ≤ t} .  (42)

Now

\frac{1}{2^{n+m}} ∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ ∑_{b∈\{0,1\}^{n}} ∑_{s∈\{0,1\}^{m}} \frac{1}{2^{n+m}} \frac{|c_{0}|^{2}}{|c_{0}|^{2} + (1 − |c_{0}|^{2})p_{E}^{b,u}}

≥ #L_{t} 2^{−n−m} \frac{|c_{0}|^{2}}{|c_{0}|^{2} + (1 − |c_{0}|^{2})t}.  (43)

Since p_{Acc} = ∑_{b,u} 2^{−n−m}p_{Acc}^{b,u} = |c_{0}|^{2} + ∑_{b,u}(1 − |c_{0}|^{2})2^{−n−m}p_{E}^{b,u} ≥ |c_{0}|^{2} + (2^{n+m} − #L_{t})2^{−n−m}(1 − |c_{0}|^{2})t, we have that the number of keys for which p_{E}^{b,u} ≤ t is #L_{t} ≥ 2^{n+m}(1 − \frac{p_{Acc}−|c_{0}|^{2}}{t(1−|c_{0}|^{2})} ). Using this bound on #L_{t} in (43), and setting t = (2^{−(2−γ)(n−m−2)/2})/(1 − |c_{0}|^{2}), we get:

\frac{1}{2^{n+m}} ∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ (1 − \frac{p_{Acc} − |c_{0}|^{2}}{t(1 − |c_{0}|^{2})} ) \frac{|c_{0}|^{2}}{|c_{0}|^{2} + (1 − |c_{0}|^{2})t}

= (1 − \frac{p_{Acc} − |c_{0}|^{2}}{2^{−(2−γ)(n−m−2)/2}} ) \frac{|c_{0}|^{2}}{|c_{0}|^{2} + 2^{−(2−γ)(n−m−2)/2}} . (44)

The assumption p_{Acc} > 2^{−(1−γ)(n−m−2)+1}, together with Lemma 4, implies |c_{0}|^{2} > 2^{−(1−γ)(n−m−2)+1} −2^{−(n−m−2)} > 2^{−(1−γ)(n−m−2)}. Furthermore Lemma 4 implies p_{Acc} − |c_{0}|^{2} ≤ 2^{−(n−m−2)}:

\frac{1}{2^{n+m}} ∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ (1 − \frac{2^{−(n−m−2)}}{2^{−(2−γ)(n−m−2)/2}} ) \frac{1}{1 + 2^{−(2−γ)(n−m−2)/2}/|c_{0}|^{2}}

≥ \frac{1 − 2^{−γ(n−m−2)/2}}{1 + 2^{−γ(n−m−2)/2}}

≥ 1 − 2^{−γ(n−m−2)/2+1}.  (45)

Setting γ = 1/2, we have that

\frac{1}{2^{n+m}} ∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) ≥ 1 − 2^{−(n−m−2)/4+1}, (46)

when p_{Acc} ≥ 2^{−(n−m−2)/2+1}. This completes the proof. □

C Proof of Theorem 3

The proof of Theorem 3 is essentially identical to the proof in section 5.3 of [3]. ProofOf Theorem 3. We know from Theorem 2 that

∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} 2^{−n−m} (1 − F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|})) ≤ 2^{−(n−m−2)/4+1}  (47)

Let |ψ_{1}^{b,u}⟩ be a purification of the state held by Alice, Bob, and Eve, that contains a description of the key. If we trace out the systems of Eve, the key, and the environment of |ψ_{1}^{b,u}⟩ we get ρ̂. If we trace out the systems of Alice, Bob, the key, and the environment we get ρ_{ok}((b, u), x). So |ψ_{1}^{b,u}⟩ is also a purification of the states ρ̂_{Acc}^{b,u}, and ρ_{ok}((b, u), x). By Ulhmann’s Theorem, there exists a purification |ψ_{2}^{b,u}⟩ of |Ψ⟩⟨Ψ|, such that

F (|ψ_{1}^{b,u}⟩, |ψ_{2}^{b,u}⟩) = F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) .  (48)

When measuring the systems of Alice and Bob, and tracing out the environment of |ψ_{1}^{b,u}⟩ we get |b, u⟩⟨b, u| ⊗ ρ_{ok}((b, u), x). Since |Ψ⟩⟨Ψ| is already a pure state, measuring the systems of Alice and Bob, and tracing out the environment of |ψ_{2}^{b,u}⟩ gives |b, u⟩⟨b, u| ⊗ |ψ⟩⟨ψ|, for some pure-state |ψ⟩. Since measuring and tracing out can only increase the fidelity,

F ({|b, u⟩ \atop ⟨b, u|} ⊗ ρ_{ok}((b, u), x), {|b, u⟩ \atop ⟨b, u|} ⊗ {|ψ⟩ \atop ⟨ψ|}) ≥ F (ρ̂_{Acc}^{b,u}, {|Ψ⟩ \atop ⟨Ψ|}) . (49)

Using the fact that D(ρ, σ)^{2} ≤ 1 − F (ρ, σ), and (47), we get

D({K} ⊗ ρ_{ok}^{epr}(x)], [{U}] ⊗ [ρ_{ok}^{epr}(x)])

≤ ∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} 2^{−n−m}D({|b, u⟩ \atop ⟨b, u|} ⊗ ρ_{ok}((b, u), x), {|b, u⟩ \atop ⟨b, u|} ⊗ {|0⟩ \atop ⟨0|})

≤ \sqrt{∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} 2^{−n−m}D({|b, u⟩ \atop ⟨b, u|} ⊗ ρ_{ok}((b, u), x), {|b, u⟩ \atop ⟨b, u|} ⊗ {|0⟩ \atop ⟨0|})^{2}}

≤ \sqrt{∑_{b∈\{0,1\}^{n}} ∑_{u∈\{0,1\}^{m}} 2^{−n−m}(1 − F ({|b, u⟩ \atop ⟨b, u|} ⊗ ρ_{ok}((b, u), x), {|b, u⟩ \atop ⟨b, u|} ⊗ {|0⟩ \atop ⟨0|}))}

≤ 2^{−(n−m−2)/8+1/2} ≤ 2^{−(n−m−2)/8+1}. (50)

□

Recent BRICS Report Series Publications

RS-05-17 Ivan B. Damgård, Thomas B. Pedersen, and Louis Salvail. A Quantum Cipher with Near Optimal Key-Recycling. May 2005.

RS-05-16 Dariusz Biernacki, Olivier Danvy, and Kevin Millikin. A Dynamic Continuation-Passing Style for Dynamic Delimited Continuations. May 2005. ii+24 pp.

RS-05-15 Ma�gorzata Biernacka and Olivier Danvy. A Concrete Framework for Environment Machines. May 2005. ii+25 pp.

RS-05-14 Olivier Danvy and Henning Korsholm Rohde. On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation. April 2005. ii+8 pp.

RS-05-13 Dariusz Biernacki, Olivier Danvy, and Chung-chieh Shan. On the Dynamic Extent of Delimited Continuations. April 2005. ii+32 pp. Extended version of an article to appear in Information Processing Letters. Subsumes BRICS RS-05-2.

RS-05-12 Ma�gorzata Biernacka, Olivier Danvy, and Kristian Støvring. Program Extraction from Proofs of Weak Head Normalization. April 2005. 19 pp. Extended version of an article to appear in the preliminary proceedings of MFPS XXI, Birmingham, UK, May 2005.

RS-05-11 Ma�gorzata Biernacka, Dariusz Biernacki, and Olivier Danvy. An Operational Foundation for Delimited Continuations in the CPS Hierarchy. March 2005. iii+42 pp. A preliminary version appeared in Thielecke, editor, 4th ACM SIGPLAN Workshop on Continuations, CW ’04 Proceedings, Association for Computing Machinery (ACM) SIGPLAN Technical Reports CSR-04-1, 2004, pages 25–33. This version supersedes BRICS RS-04-29, but is superseded by BRICS RS-05-24.

RS-05-10 Dariusz Biernacki and Olivier Danvy. A Simple Proof of a Folklore Theorem about Delimited Control. March 2005. ii+11 pp. Superseded by BRICS RS-05-25.

RS-05-9 Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing Bounds on the Circuit Size of the Hardest Functions. March 2005. 6 pp. To appear in Information Processing Letters.

RS-05-8 Peter D. Mosses. Exploiting Labels in Structural Operational Semantics. February 2005. 15 pp. Appears in Fundamenta Informaticae, 60:17–31, 2004.