High-Dimensional Semi-Quantum Cryptography
Hasan Iqbal Walter O. Krawec
quant-ph

Signatures of a pair density wave at high magnetic fields in cuprates with charge and spin orders
    Zhenzhong Shi,^1† P. G. Baity,^1,2†† J. Terzic,^1 T. Sasagawa,^3 Dragana Popović^1,2∗



^1National High Magnetic Field Laboratory, Florida State University,

Tallahassee, Florida 32310, USA

^2Department of Physics, Florida State University,

Tallahassee, Florida 32306, USA

^3Materials and Structures Laboratory, Tokyo Institute of Technology,

Kanagawa 226-8503, Japan



^† Present address: Department of Physics, Duke University,

Durham, North Carolina 27708, USA

^†† Present address: James Watt School of Engineering, University of Glasgow,

Glasgow, G12 8QQ, Scotland, United Kingdom

^∗To whom correspondence should be addressed; E-mail: dragana@magnet.fsu.edu

    
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


A semi-quantum key distribution (SQKD) protocol allows two users, one of whom is restricted in their quantum capabilities, to establish a shared secret key, secure against an all-powerful adversary.  In this paper, we design a new SQKD protocol using high-dimensional quantum states and conduct an information theoretic security analysis.  We show that, similar to the fully-quantum key distribution case, high-dimensional systems can increase the noise tolerance in the semi-quantum case.  Along the way, we prove several general security results which are applicable to other SQKD protocols (both high-dimensional ones and standard qubit-based protocols).




§ INTRODUCTION

It is well known that secure key distribution, using only classical communication, is impossible unless computational assumptions are placed on the power of the adversary.  If both A and B are able to communicate using quantum resources, however, perfect security is possible and the only assumption on the adversary required is that she obey the laws of quantum physics.  Quantum Key Distribution (QKD) protocols allow two parties (Alice, A, and Bob, B) to establish a shared secret key, secure against an all-powerful adversary (Eve, E).  Since the first QKD protocol developed by Bennett and Brassard in 1984 (the so-called BB84 protocol <cit.>), both the theory and practice of QKD has been increasing dramatically.  For a general survey of QKD, both the theory and practice, the reader is referred to <cit.>.



Since perfect security for key distribution is impossible if both A and B are restricted to classical communication while it is possible if both A and B are “quantum capable,” a natural question to ask is “what is the middle ground?”  A communication model designed to help answer this question is the so-called semi-quantum model of cryptography, first introduced in 2007 by Boyer et al. <cit.>.  In this model, one party is “fully quantum” in that they can do anything the protocol requires of them so long as it is possible according to quantum mechanics.  The second party, however, is restricted to operations which are mathematically equivalent to classical communication.  Thus, one party is quantum while the other party is “classical.”  Since its original introduction in 2007, there have been numerous new semi-quantum key distribution (SQKD) protocols developed <cit.>.  There have also been extensions to the model beyond basic key distribution including secret sharing <cit.> and state comparison <cit.>.

(S)QKD protocols operate in two stages: first is a quantum communication stage whereby users utilize the quantum channel, along with the classical authenticated channel (which is a classical communication channel that is authenticated, but not secret), to establish a raw key.  A and B both have their own raw key which  is a string of classical bits that are partially correlated (there may be some errors due to an adversary's attack or just natural noise) and partially secret (an adversary may have some information on this raw key).  Thus this raw-key by itself cannot be used directly as a secret key.  Users, therefore, must run a second stage where, at a minimum, they will execute an error correction protocol using the authenticated classical channel (leaking additional information to E) followed by a privacy amplification protocol which takes the error-corrected raw key and hashes it down to a smaller secret key.  The relative size of the secret key compared to the initial raw-key (called the key-rate of the protocol) is a statistic of great importance in QKD research and bounding it, as a function of observed noise in the quantum channel, is the main challenge in any (S)QKD security proof.  A related statistic is the noise tolerance of the protocol which specifies the noise threshold after which the adversary has too much information and so users must simply abort (e.g., BB84's noise tolerance is 11% <cit.>).  Before this tolerance threshold is reached, privacy amplification is able to give a positive, though potentially small, key (the size of the secret key decreases as the noise increases due to the direct correlation between noise and adversarial information gain).

As far as semi-quantum cryptography is concerned, there have been, by now, several proofs of security based on key-rate computations for SQKD protocols and, rather surprisingly, despite the limitations on one of the users, along with the increased attack strategy space afforded to the adversary (due to the requirement of a two-way quantum channel allowing quantum resources to travel from A, to B, then back to A), noise tolerances compare favorably to several fully quantum protocols.  In particular, in <cit.>, the noise tolerance of the original Boyer et al., protocol can approach 11%, the same as BB84.  However, this optimistic result required looking at numerous mismatched statistics (a technique introduced in <cit.>, extended for one-way channels in <cit.>, and expanded for two-way quantum channels in <cit.>).  Without these statistics, and only looking at the error rate, the Boyer et al., protocol has a noise tolerance of 6.14%, though this is only a lower-bound and future refinements to the security proof techniques may improve this to the 11% found with mismatched measurements.  Currently, the best-known noise tolerance for an SQKD protocol is from <cit.> which can attain a tolerance of 17.8% or even as high as 26% for certain, practical, quantum channels (a result comparable to BB84 with Classical Advantage Distillation <cit.>).  Again, this high tolerance bound required looking at numerous  mismatched measurements.

Designing protocols with increased noise tolerance is an important task.  Encouraged by recent theoretical successes in fully-quantum QKD using high-dimensional carriers <cit.> and, in particular, these protocols' ability to withstand high channel noise levels (some reaching 50% as the dimension of the quantum carrier approaches infinity), we ask, can a high dimensional quantum communication channel also benefit semi-quantum key distribution?  Or does this substantial improvement in noise tolerance require two fully quantum users to truly harness?  We note that a high-dimensional SQKD protocol was introduced in <cit.>, using a quantum walk as the information carrier, however a noise tolerance computation was not performed due to the great complexity of that protocol and so this question still remained open (though the methods we develop in this paper may be applicable to other protocols such as this quantum-walk based protocol).

In this paper, we show high dimensional states can benefit semi-quantum communication and in doing so, make several contributions in this work.  We design a new high-dimensional SQKD protocol and conduct an information theoretic security analysis allowing us to compute a lower-bound on its key-rate based on observed channel noise.  Our security proof introduces several new techniques which may be applicable to other (S)QKD protocols (both standard qubit-based and future-developed high-dimensional ones including, perhaps, the quantum-walk SQKD protocol developed in <cit.>).  Semi-quantum protocols rely on a two-way quantum channel giving the adversary a greater attack strategy space making security analyses for semi-quantum protocols difficult, especially in higher dimensions (all past work involving key-rate computations have been for the qubit case). As such, our new methods may prove beneficial not only for other semi-quantum protocols, but also fully-quantum protocols reliant on a two way quantum channel (of which there are several <cit.>).  Finally, we evaluate our protocol's performance and determine its noise tolerance for varying dimensions and show that, indeed, high dimensional carriers do benefit the noise tolerance of semi-quantum protocols.  We show that our protocol's noise tolerance tends to 30% as the dimension increases; this result is without requiring any mismatched statistics.  While this is not as high as the 50% achieved in the fully quantum case, this is still higher than any other SQKD protocol to-date and, considering that this is a semi-quantum protocol, where one participant is severely limited in their capabilities, is still a very positive result.  This work paves the way for future research in higher-dimensional systems for semi-quantum or two-way quantum cryptography.  By analyzing semi-quantum protocols with high dimensional systems, we further map out the “gap” between classical and quantum communication systems.

In this work, we are primarily concerned with a theoretical protocol and not practical attacks or complications involving its implementation.  We note that several fully quantum high-dimensional QKD protocols have been experimentally implemented and the experimental generation of high dimensional entangled states has seen rapid progress lately <cit.>.  However, we do not concern ourselves with practical implementations of this system. Instead, we are solely interested in understanding how high-dimensional quantum states may benefit the semi-quantum model of cryptography, leaving practical issues as future work.



§ PRELIMINARIES


If ρ_AB is a density operator (i.e., a Hermitian positive semi-definite operator of unit trace) acting on Hilbert space ℋ_A⊗ℋ_B, then we write ρ_A to mean the partial trace over the B portion, namely ρ_A = tr_Bρ_AB.  Similarly for other, or multiple, systems.  Given a system ρ_AB which is unmeasured, and an orthonormal basis V = {|v_1⟩,⋯,|v_d⟩} for the A system (which is of dimension d), then we write ρ_A^VB to mean the density operator resulting from a measurement of the A register in this V basis.

We use H(A)_ρ to mean the entropy function - either the classical Shannon entropy (if ρ is a classical state) or the quantum von Neumann entropy (the context will always be clear which we mean).  Note this implies ρ is a density operator acting on at least some A register (if it acts on others, we first trace out those additional spaces and compute the entropy in the resulting A space only).  The von Neumann entropy is defined: H(A)_ρ = H(ρ_A) = -tr(ρ_Alogρ_A) (where all logarithms in this paper are base two).  The conditional entropy is denoted H(A|B)_ρ and defined H(AB)_ρ - H(A)_ρ.  If ρ_AB is an unmeasured quantum state, then by H(A^V|B)_ρ we mean the conditional entropy in the operator resulting from measuring the A portion of ρ_AB in the V basis (the B portion remains unmeasured).  By H(A^V|B^V)_ρ we  mean the same, but after also measuring the B portion (in which case the entire state is classical and so Shannon entropy is used).  If the context is clear, we may drop the subscript.  Finally, for a real number x∈[0,1] we write H(x) to mean the binary Shannon entropy, namely H(x) = -xlog x - (1-x)log(1-x).

Given operator X, we write ||X|| to mean the trace distance.  If X is Hermitian and finite dimensional, then this is simply the sum of the absolute values of the eigenvalues of X.

Finally, let ρ_ABE be a quantum state where the A portion is d-dimensional and let V = {|v_1⟩,⋯,|v_d⟩} and U={|u_1⟩,⋯,|u_d⟩} be two orthonormal bases.  An important entropic uncertainty relation which will be used later, was proven in <cit.> and states that for any quantum state ρ_ABE, it holds that:

    H(A^V|E)_ρ + H(A^U|B) ≥ -log c,

where c = max_i,j|⟨v_i|u_j||⟩^2.  This will be used in our proof of security later.



 §.§ Semi-Quantum Cryptography

The semi-quantum model, as introduced in <cit.>, consists of at least one “fully-quantum” user (typically A) and one “classical” or “semi-quantum” user (typically B).  This classical user is only allowed to interact with the quantum channel in a very restricted way.  In particular, he can choose to do one of two things on receiving any quantum state from A:

  
  * : If he chooses this option, he will disconnect from the quantum channel, creating a loop back to A.  In this case, the quantum user is simply “talking to herself” over a large, looped, quantum channel.
  
  * : If he chooses this option, he will perform a measurement of the quantum state in a single, publicly known, basis (typically the computational basis).  Based on his measurement result, he will then send a new quantum state, prepared in this same basis, back to A.


Clearly, if both users are semi-quantum and can only perform these two operations, the system is mathematically equivalent to a classical communication protocol as both users would be restricted to only operating directly in a single, publicly known, basis.  Thus, the interest in semi-quantum cryptography is to see how security holds when one user is quantum, but the other is classical according to the above functionality.

Note that we are not considering practical device security in this work and are only interested in the theoretical properties of semi-quantum communication.  Thus we do not concern ourselves with such attacks as the photon tagging attack <cit.> or multi-photon attacks (especially problematic when B chooses  as he must re-prepare qubits in the observed state).  Though interesting, these are outside the scope of this work - techniques from <cit.> may prove beneficial to securing our protocol against these attacks but we leave this as interesting future work.

As mentioned earlier, (S)QKD protocols operate, first, through a quantum communication stage.  This stage utilizes the quantum communication channel and the authenticated classical channel to output a raw-key of size N bits.  From this error correction and privacy amplification are run outputting a secret key of size ℓ(N) bits.  The key-rate is defined to be the ratio ℓ(N)/N.  We are interested in the theoretical asymptotic limit.  In this case, assuming collective attacks (i.i.d. attacks where E is free to store a quantum memory system for measurement at any future point in time <cit.>), it was shown in <cit.> that:

    r = lim_N→∞ℓ(N)/N = inf(H(A|E)_ρ - H(A|B)_ρ),

where ρ_ABE is a density operator describing a single iteration of the quantum communication stage, conditioned on that iteration being used to distill raw key material (i.e., not on an iteration used only for error checking or an iteration that is later discarded due to an incompatible basis choice).  The infimum is over all collective attacks that induce the observed noise statistics.  Above, the A and B registers are the actual classical raw-key bit registers and only the E portion is quantum.  It is this entropy equation, and in particular the von Neumann entropy H(A|E), that we are interested in computing and is the main challenge (computing H(A|B) is generally trivial given the observed noise statistics).

Our protocol uses higher-dimensional systems and, as such, we must define the bases we work with.  For the classical user, we will use the computational basis of dimension 2^n, namely: {|0⋯ 00⟩, |0⋯01⟩, ⋯, |1⋯ 11⟩} which, when needed to simplify  notation, we will also label equivalently as {|0⟩, |1⟩, ⋯, |2^n-1⟩}.  We use  to denote this basis.

The quantum user, of course, is not restricted to operating in only one basis and so we also define the following “” basis:

    = {|F_0⟩, |F_1⟩, ⋯, |F_2^n-1⟩},

where |F_x⟩ = ℱ|x⟩ and ℱ is the quantum Fourier transform, namely:

    ℱ|x⟩ = 1/√(2^n)∑_y=0^2^n-1exp(-π i  x y/2^n-1)|y⟩.


Of course, one may consider other bases that the quantum user may utilize.  However, our protocol will make use of both the  and  bases.  Note that, for the classical user, if he chooses  or , that operation is performed on an entire n-qubit signal state (e.g., he cannot reflect “half” the qubits and measure the other half in our model).



§ THE PROTOCOL

Our protocol is shown in Protocol <ref>.  The protocol operates by having A send signals of n-qubits each.  For each iteration, B will either  the entire n-qubit state or he will  the entire state.  Whenever A sends a  basis state and B chooses to , they will add n bits to their raw key.  Once a sufficiently large raw key has been established, standard error correction and privacy amplification are run.  In the next section we will compute a lower-bound on the key-rate of this protocol.  We will consider a noisy, but loss-less, quantum channel and ideal devices.  Practical security concerns, though interesting, are outside the scope of this work and would provide interesting future work.  Any collective attack against this protocol consists of two unitary operators (U_F, U_R) where U_F is applied in the forward channel and U_R is applied in the reverse.






§ SECURITY ANALYSIS

We now analyze the security of our protocol.  As with other (S)QKD protocols, we show security against collective attacks.  We will comment on general attacks later.  Our security analysis extends ideas introduced in our conference paper <cit.> but to the higher-dimensional case and consists of two main parts: First, we will prove that it is sufficient to analyze a particular one-way fully quantum protocol and, once security is proven there assuming the same channel observations are made, security of our SQKD protocol follows immediately.  This reduction is very general and can apply to other SQKD protocols.  Thus, to analyze security of the two-way semi-quantum protocol, it suffices to consider a particular one-way protocol which is easier to analyze as E only attacks once.  Second, we analyze the security of this one-way protocol through the use of entropic uncertainty relations, and continuity of conditional von Neumann entropy.  The techniques we develop in both steps are often general and may be applicable to other two-way (S)QKD protocols.



 §.§ Reduction to a One-Way Protocol

In this section we show how certain SQKD protocols, of arbitrary dimensions, may be reduced to a one-way protocol.  Note that in <cit.>, a method of reducing two-way fully quantum protocols to one-way, entanglement based protocols was shown, however that method only applies if the original protocol admits a certain symmetry property which semi-quantum protocols necessarily lack (due to B's use of ).  As a first step, we first consider an intermediate, two-way, SQKD protocol, which we denote by .  This intermediate protocol is no longer prepare-and-measure, but instead has A preparing entangled qudits and B performing a CNOT gate whenever he chooses .  The protocol is shown in Protocol <ref>.  It is not difficult to see that security of  implies security of  (i.e., ⇒ where “⇒” means “implies security of”).  Indeed, A's prepare-and-measure scheme in  is equivalent to her preparing the entangled state of 2n qubits |ψ_0⟩ = 1/2^n/2∑_a|a,a⟩ and sending the right register (consisting of n qubits) to B while keeping the left-half to herself.  If B chooses to reflect, this is nothing more than an identity operation whereas if he chooses to , then by applying CNOT gates targeting his register and then measuring at some future time, this is equivalent to him measuring immediately.  Finally, when qubits return to A, she may measure both n qubit registers in the same basis - standard arguments <cit.> show that her measurement of the A_1 register is equivalent to her initially preparing the state she observes at this later point.  Furthermore, a collective attack against this protocol is identical to the  case, namely two unitary attack operators (U_F, U_R).



Next, we introduce our one-way protocol, shown in Protocol <ref> and denoted .  At first glance, the two protocols,  (which is semi-quantum and uses a two-way quantum channel) and  (which is one-way and fully quantum) do not appear similar.  However, we will prove that security of  implies security of  (which, in turn, implies security of our actual protocol ).  We do this by showing that, for any attack against , there exists an attack against  which causes E to gain as much information on the raw-key as in  and, furthermore, the view according to A, B, and E are identical in both cases (i.e., the two cases are indistinguishable).  Thus, if we analyze  (which is easier to do since it is one-way), we automatically cover any attack against .  Ultimately, this technique is an extension of a result in our conference paper <cit.> to the arbitrary, N-dimensional case (only the qubit, N=2 case was considered before).  However, beyond being more general, our proof here is also more refined as it does not require an additional “simplification” step that was necessary in <cit.>.

Let N = 2^n.  An attack against  consists of a probability distribution {p(b)} for all b=0,1,⋯, N-1 along with a single attack operator U acting on 2n qubits and E's quantum ancilla.  Note that E gets to choose the values p(b) which B uses to prepare his states - thus, E has partial control over B's source device in ; the reason for this necessity will be apparent later in our proof.  We now prove it is sufficient to consider security of  (in which case we have ⇒⇒).




Let (U_F, U_R) be a collective attack against  and let ρ_ABE be the resulting density operator describing a single iteration of  in the event this attack is used.  Then, there exists an attack of the form ({p(b)}_b=0^2^n-1, U) against  such that, if σ_ABE is the resulting density operator of a single iteration of  in this case, it holds that σ_ABE = ρ_ABE.  In particular, there is no advantage to E in either case and, furthermore, no party A, B, or E can distinguish between the two scenarios.


Fix an attack (U_F, U_R). Without loss of generality, we may write U_F's action on basis states as:

    U_F|a⟩⊗|χ⟩_E = ∑_b=0^N-1|b, e_a,b⟩,

where N = 2^n and |e_a,b⟩ are arbitrary states in E's ancilla (we assume, without loss of generality in the collective attack case, that E's ancilla starts in some pure state |χ⟩_E).  Unitarity, of course, imposes some restrictions on these states.  In particular, for every a it holds that:

    ∑_b=0^N-1e_a,b = 1.


Given this attack, we construct ({p(b)}, U), an attack against , that satisfies the theorem statement.  To do so, we follow a technique first introduced in our conference paper <cit.> but generalized here for higher dimensions.  First, we set the values p(b) to:

    p(b) = 1/N∑_a=0^N-1e_a,b

Clearly p(b) ≥ 0 for all b.  Furthermore, from Equation <ref>, it follows that:

    ∑_bp(b) = 1/N∑_b∑_ae_a,b = 1/N∑_a∑_be_a,b = 1,

thus this is a valid probability distribution, and so a valid attack setting.

Now, consider the following operator  which we call the “rewind” operator as, in a way, it “rewinds” the channel so that a state prepared by B in the one-way case (i.e., protocol ) appears to all three parties as if it had been prepared by A in the two-way case (i.e., ).  In particular, it will “setup” the A_1 register and E's quantum memory as if this had been performed in the two-way  case.  The only thing that cannot be “rewound” is B's measurement distribution, thus the need for E to set this separately through the p(b) values.  This operator acts on basis states |b,b⟩ (sent by B in the one-way protocol ) as follows:

    |b,b⟩_A_1A_2 = ∑_a=0^N-1|a,b,e_a,b⟩/√(N· p(b)).

It is not difficult to see that  is an isometry.  Indeed, given |b,b⟩ and |b',b'⟩ for b  b', we have:

    0 = ⟨b,b|b',b'|   ⟩= 1/N√(p(b)p(b'))∑_a,a'⟨a,b,e_a,b|a',b',e_a',b'|=⟩ 0.

Furthermore, we have:

    1 = ⟨b,b|b,b|   ⟩= 1/N· p(b)∑_a,a'⟨a,b,e_a,b|a',b,e_a',b|
    ⟩   =1/N· p(b)∑_ae_a,b = 1.

Thus,  is an isometry and may be extended, using standard techniques, to a unitary operator implying it is an operation that E may do within the laws of quantum physics.  We claim that U = (I_A_1⊗ U_R) is the desired attack operator satisfying the theorem statement.




Refer to Figure <ref>.  Consider the case when B chooses .  At time t^* (after E attacks with U_F and B's  operation, but before E attacks a second time with U_R), the joint state held by A, B, and E using protocol  is found to be:

    |ψ^ent_MR⟩ = 1/√(N)∑_a|a⟩_A∑_b|b, e_a,b, b⟩_TEB.

Now, again, referring to Figure <ref>, consider the same case (namely, B choosing ) but with the  protocol.  In this event, B prepares the state ∑_b√(p(b))|b,b,b⟩_A_1A_2B and E attacks with .  The joint system then, at time t^* is:

    |ϕ_MR⟩ = ∑_b√(p(b))(∑_a|a,b,e_a,b⟩/√(N· p(b)))⊗|b⟩_B = 1/√(N)∑_a|a⟩_A_1∑_b|b,e_a,b,b⟩_A_2EB = |ψ^ent_MR⟩

Thus, after applying , the state of the joint system for the case of  is identical to that of .  Of course, after applying U_R (which happens in both scenarios since we constructed U = (I_A_1⊗ U_R)), the systems will remain the same.  Thus, any measurement outcomes or entropy computations will be identical in both scenarios.  It is trivial to show the same holds true in the  case for both protocols (in that case, the additional |b⟩ term is no longer there but the algebra remains the same otherwise).  Thus, if one were to write out a density operator description of both protocols, tracing their evolution, they would be identical as the underlying systems are identical in all cases.  Note that the only thing E could not “rewind” with  is the probability distribution of B's measurements (since he is now preparing).  Thus it is required that E gets to choose the distribution p(b) so that the probability distribution in  matches that observed in .  This completes the proof.


Theorem <ref> implies that it is sufficient to prove security of the one-way protocol .  Since any attack against  can also be transformed into an attack against , if we analyze a general attack against the latter, this automatically gives security against the former.  Indeed, there may be more attack strategies for E against  as E has access to both n qubit registers simultaneously; despite this, it is easier to analyze as it is a one-way protocol.  Furthermore, note that no party can distinguish between the two scenarios and, as a consequence, observed channel noise in the “real” SQKD protocol  translate directly to observed statistics in the one-way protocol .  Our goal is to prove security of  (which proves security of ) and, given observed noise statistics there, if we prove security of  given those same statistics, the key-rate can only be better in  (since  has potentially more attack strategies as mentioned).



 §.§ Proof of Security for 

We now prove security of .  In the following, we define N = 2^n where n is the user-defined number of qubits sent per iteration of our protocol.  Our proof of security is in three steps.  First, we compute the conditional entropy H(A|E) in the case where B chooses .  This, of course, is useless for key distillation as B is completely independent of the state in this case, but it will be used later to argue about the entropy in the actual key-distillation state (i.e., when B chooses ).  Second, we argue that E's optimal attack must take on a particular form if A and B use the  or  basis.  Third, and finally, we use these results, along with Winter's continuity bound on conditional entropy <cit.>, to compute the entropy of A's register conditioned on E's quantum memory in the actual key-distillation state when B chooses  giving us the desired key-rate.


First, we need a channel scenario for the real  protocol (which translates, as discussed, to observations for ).  Keeping in line with other high-dimensional QKD analyses <cit.>, we consider a symmetric attack modeled as a depolarization channel (which may even be enforced by users):

    ℰ_Q(σ) = (1-N/N-1Q)σ + Q/N-1I.

where σ is any N dimensional quantum state.

We will assume the noise in the forward channel and reverse channel are the same and parameterized by Q (though our analysis follows even if they are different, though the algebra complexity increases).  In the “reflect” case, we will use a depolarization parameter Q_F - this captures the practical case that, for certain fiber channels, reflecting a quantum state back can “undue” some noise (but in the  case this cannot happen as the “measurement” breaks any entanglement in the channel) <cit.>.

Let p(x|y) be the probability that a party observes x given the sender sent y (in the  or  basis) in either the forward or reverse channel.  From this model, we have:

    p(x|y) = {[       1-Q  if x = y;     Q/N-1 otherwise ].

In , the probability that A_1^Z (i.e., after measuring) is a, for any particular a, is simply p(a) = 1/N.  Furthermore the probability that B measures b is ∑_ap(b|a)p(a) = 1/N( 1-Q + (N-1)Q/N-1) = 1/N.  Thus, we set p(b) = 1/N when analyzing  (E's choice here must conform to the observed statistics in the “real” protocol ).

Let p(a,b,c) be the probability that, in the case of , if all parties measure in the  basis, A_1 measures a, B measures b, and A_2 measures c (recall A_1 is A's first n-qubit register and A_2 is her second register).  Then, since this is a classical probability distribution, by the chain rule it holds that:

    p(a,b,c) = p(c|b,a)· p(b|a)· p(a).

We will assume that in the  case of , the two channels act independently and, so, p(c|b,a) = p(c|b).  That is, A's measurement in the return channel, depends only on what B actually sends.  This is a very realistic noise scenario and can even be enforced by the users - A and B will simply abort if they do not observe this (natural) behavior.  Of course, as discussed, we do not assume the two channels act independently if B chooses to  (such an assumption would not be natural nor could it be enforced and so we do not make it here).  Under these assumptions, it is not difficult to see that:

    p(a,b,c) = 1/N×{[                β^2 if c = b and b = a;                 αβ  if c  b and b = a;                 αβ  if c = b and b  a;                α^2   if c  b and b  a ].

where:

    α = Q/N-1      β = 1-Q.


Given these observed channel statistics in  we now turn to  using this same distribution on measurement events.  Ultimately, our goal is to compute a lower-bound on the key-rate: H(A_1^Z|E)_μ - H(A_1^Z|B_1^Z)_μ, where μ_A_1B_1E is the density operator describing an iteration of the protocol in the  case.

First Step - Entropy in the Reflect Case:
Let ρ_A_1A_2BE be the density operator describing the state of the system (before measurements are made by any party) if B chooses .  Similarly, let μ_A_1A_2BE be the density operator in the case B chooses .  Since key-bits are only distilled in this  case, to compute the key-rate of the protocol we will require a bound on the von Neumann entropy H(A_1^Z|E)_μ.  However, we will actually, first, bound H(A_1^Z|E)_ρ and later argue that, due to continuity of entropy <cit.>, the difference in entropy between the two systems, ρ and μ, cannot be “too large.”

Consider the state ρ_A_1A_2BE.  In this  case, B's system is completely independent of all other systems; thus ρ_A_1A_2BE≡ρ_A_1A_2E⊗0_B and so the B portion does not factor into any entropy equations and may be ignored.  Using the entropic uncertainty relation proven in <cit.> (see Equation <ref>), we know:

    H(A_1^Z|E)_ρ≥ n - H(A_1^F|A_2)_ρ≥ n - H(A_1^F|A_2^F)_ρ,

where the second inequality follows from the fact that measurements cannot decrease uncertainty.  If we could distill a key from ρ, we would be finished - in fact, the above would be the case when A_1 is attempting to distill a key with herself, “A_2” which, of course, is meaningless from a practical standpoint.  However, as we now show, knowing the entropy in ρ allows us to bound the entropy in μ (which is what we actually want in order to compute the key-rate of our protocol).


Consider E's attack operator U against . Without loss of generality, we may write U's action on basis states of the form |b,b⟩ as follows:

    U|b,b⟩⊗|χ⟩_E = ∑_a=0^N-1∑_c=0^N-1|a,c, e_a,b,c⟩,

where the |e_a,b,c⟩ are arbitrary states in E's ancilla (again, we assume without loss of generality that E's ancilla is cleared to some initial pure state |χ⟩_E).  Note that we are not assuming a particular structure to this attack (e.g., we do not assume it consists of the  operator used in the proof of Theorem <ref> - instead, it may be arbitrary and if we prove security here, we will gain security of  since it will cover any attack against that protocol).


Consider ρ_A_1^ZE, i.e., the state of the system after A measures the A_1 register in the  basis and tracing out A_2.  Tracing the evolution of the state in this case, and recalling that p(b) = 1/N due to our (enforceable) symmetry assumption, we find:

    ρ_A_1^ZE = 1/N∑_a=0^N-1a⊗(∑_c=0^N-1P[∑_b=0^N-1|e_a,b,c⟩]),

where P(z) = zz^*.

On the other hand, tracing the evolution of the protocol in the case B chooses , gives us the following operator:

    μ_A_1^ZE = 1/N∑_a=0^N-1a⊗(∑_c=0^N-1∑_b=0^N-1e_a,b,c).


Our goal in the remainder of the security proof is to bound the difference between H(A_1^Z|E)_ρ and H(A_1^Z|E)_μ.  To do so, we will use Winter's continuity bound <cit.> and in particular, the case derived for classical-quantum states.  This bound states that (rewriting in terms of our notation of course):

    |H(A_1^Z|E)_ρ - H(A_1^Z|E)_μ| ≤Δlog A_1^Z + (1+Δ)H(Δ/1+Δ),

where:

    Δ = 1/2ρ_A_1^ZE - μ_A_1^ZE.

Of course log A_1^Z = n.  Thus, our goal is to determine an upper-bound on the trace distance Δ.  Note that an upper-bound will only increase the distance between the two entropies causing the key-rate to drop.  Thus by finding an upper-bound, we determine a worst-case key-rate and the actual key-rate can only be higher.

By elementary properties of trace distance, along with the triangle inequality, we have:

    Δ≤1/2N∑_a,c=0^N-1 P(∑_b=0^N-1|e_a,b,c⟩) - ∑_b=0^N-1e_a,b,c_Δ_a,c = 1/2N∑_a,cΔ_a,c.


Second Step - Structure of E's Attack Operator:
Before computing Δ, we argue now that E's optimal attack operator has a particular structure to it.
As discussed earlier, let p(a,b,c) denote the probability that measuring A_1 results in a; measuring B results in b; and measuring A_2 results in c (where these measurements are performed in the  basis in the  case; thus a,b,c ∈{0,1,⋯,N-1}).  It is not difficult to see that p(a,b,c) = e_a,b,c/N.  Indeed, note that the state μ_A_1^ZA_2^ZBE (i.e., the case where B chooses , but before tracing out A_2^Z and B which we did for Equation <ref>) is found to be:

    μ_A^Z_1A^Z_2BE = 1/N∑_aa_A_1⊗∑_cc_A_2⊗∑_bb_B⊗e_a,b,c,

from which it is clear that p(a,b,c) = e_a,b,c/N.  Since N is known and since p(a,b,c) is a value that can be observed by the parties running the protocol, this implies e_a,b,c is also an observable quantity.


We now claim that it is to E's advantage to choose her attack such that for any fixed a, c, it holds that:

    ⟨e_a,b,c|e_a,b',c|=⟩{[ N· p(a,b,c)  if  b = b';           0   if  b  b' ].

Indeed, orthogonal ancilla states cannot increase her uncertainty, thus the only reason to make these states non orthogonal would be if, by doing so, she could make some other, potentially “more important” vectors closer to orthogonal (e.g., the non-error cases such as ⟨e_0,0,0|e_1,1,1|$⟩) while still falling within the observed noise statistics.  But the inner-product⟨e_a,b,c|e_a,b',c|$⟩ does not contribute to the observed noise in any way, assuming basis  is used, and thus she might as well set them to be orthogonal potentially decreasing her overall uncertainty (but certainly not increasing it).

Clearly the inner-product ⟨e_a,b,c|e_a,b',c|$⟩ does not contribute to thebasis noise whenb b'.  We thus consider thebasis noise.  Consider the case whenBchoosesin which case the state arriving toA, before measuring, is:

    1/2^n/2∑_a,c|a,c⟩|g_a,c⟩,

where|g_a,c⟩ = ∑_b|e_a,b,c⟩.  Since the above is normalized, it holds that:

    1/2^n∑_a,cg_a,c = 1.

Now, changing basis, we may write|j⟩ = ∑_xβ_x,j|F_x⟩, whereβ_x,j = ⟨F_x|j|$⟩.  Clearly, due to our choice of basis , it holds that |β_x,j|^2 = 1/2^n.  Taking Equation <ref> and changing basis in both the A_1 and A_2 registers yields:

    1/2^n/2∑_x,y|F_x, F_y⟩(∑_a,cβ_x,aβ_y,c|g_a,c⟩).

Thus, the probability that A_1 measures F_x and A_2 measures F_y, for any x,y is:

    1/2^n|∑_a,cβ_x,aβ_y,c|g_a,c⟩|^2
    
    =   1/2^n∑_a,c1/2^2ng_a,c + ∑_(a,c)(a',c')β_x,aβ_x,a'^*β_y,cβ_y,c'^*⟨g_a,c|g_a',c'|
    ⟩
    =   1/2^2n + ∑_(a,c)(a',c')β_x,aβ_x,a'^*β_y,cβ_y,c'^*⟨g_a,c|g_a',c'|,⟩

where for the third equality, we use Equation <ref>.
Note that ⟨g_a,c|g_a',c'|$⟩, for(a,c) (a',c')has no terms of the form⟨e_a,b,c|e_a,b',c|$⟩ (since either a' or c' will not equal a or c).  Thus the ⟨e_a,b,c|e_a,b',c|$⟩ inner product cannot affect any observed noise statistic.  Therefore there is no advantage toEin making it non-orthogonal as it cannot benefit her by “hiding” other states in the noise of the channel (e.g., she cannot use⟨e_a,b,c|e_a,b',c|$⟩ to increase the orthogonality of other vectors to her advantage while still keeping within the observed noise statistics).  We may therefore assume the attack operator U is such that Equation <ref> applies.  Note that this proof would not hold if |β_i,j|^2  1/2^n for all i,j.

Thus, for any fixed a and c, we may define an orthonormal basis {|ν_b^(a,c)⟩}_b=0^N-1 and write:

    |e_a,b,c⟩ = √(N· p(a,b,c))|ν_b^(a,c)⟩.

Note that we do not assume any relation between these vectors for differing a and c.  I.e., we do not make any assumptions on the value ⟨ν_b^(a,c)|ν_b'^(a',c')|$⟩ whenaa'orc c'. Third Step - Continuity Bound Analysis:
From the above analysis on the structure ofE's optimal attack operator, we may writeΔ_a,c, defined in Equation <ref>, as:

    Δ_a,c   =  P(∑_b=0^N-1√(N· p(a,b,c))|ν_b^(a,c)⟩) - ∑_b=0^N-1N· p(a,b,c)ν_b^(a,c)
       =N  P(∑_b=0^N-1√(p(a,b,c))|b⟩) - ∑_b=0^N-1p(a,b,c)b

where the last equality follows from the fact that trace distance is invariant to changes in basis and, again, we useP(z) = zz^*.





Recall our description of the channel, and in particular the value ofp(a,b,c)given in Equation <ref>.  Note that, ifQ = 0, then it is easy to see thatΔ_a,c = 0for alla,cand so we are done.  Thus, in the following, we will consider0 < Q < 1/2.  Due to the symmetry in a depolarization channel as clearly seen in the expression forp(a,b,c)in Equation <ref> (again, this may even be enforced by users), there are two cases to consider, first whenc = aand second whenc a.  For the first, we have:

    Δ_a,a   = N P(∑_b=0^N-1√(p(a,b,a))|b⟩) - ∑_b=0^N-1p(a,b,a)b
       =N∑_b b'√(p(a,b,a)p(a,b',a))|b⟩⟨b'|.


LetXbe the operatorX = N∑_bb'√(p(a,b,a)·p(a,b'a))|b⟩⟨b'|.  ThusΔ_a,a = ||X||.  Since it is Hermitian, we may decomposeXas:

    X = ∑_j=0^N-1λ_jv_j,

where{|v_j⟩}are orthogonal eigenvectors andλ_jare (real) eigenvalues; thusX|v_j⟩ = λ_j|v_j⟩for allj=0,⋯, N-1and, of course,||X|| = ∑_j|λ_j|.  Consider a particular eigenvector|v⟩ = |v_j⟩ = ∑_ix_i|i⟩.  Then:

    X|v⟩ = N∑_b=0^N-1(∑_i=0
    i b^N-1x_i√(p(a,b,a)· p(a,i,a)))_y_b|b⟩ = N∑_by_b|b⟩.

Thus, forλ= λ_jto be the corresponding eigenvalue, it must hold thatNy_b = λx_bfor allb=0,⋯,N-1.  Note that, whenb=a, it holds that:

    Ny_a = λ x_a  N∑_i=0
    i a^N-1x_i√(p(a,a,a)· p(a,i,a))=λ x_aαβ∑_i ax_i = λ x_a.

Whenb a, thenNy_bsimplifies to:

    N∑_i bx_i√(p(a,b,a)· p(a,i,a)) = N(x_a√(p(a,b,a)· p(a,a,a)) + ∑_i b
    i ax_i√(p(a,b,a)· p(a,i,a)))

and thus it must hold that:

    αβ x_a + α^2∑_i b
    i  ax_i = λ x_b.


Now, assume that there exists akk'such thatx_k x_k'and bothkandk'are not equal toa(we will handle the case when this is not true afterwards).  From Equation <ref> we have, using the case whenb = kandb = k'respectively:

    αβ x_a + α^2∑_i k
    i  ax_i    = λ x_k
    αβ x_a + α^2∑_i k'
    i  ax_i    = λ x_k'.

Subtracting these two expressions yields:

    α^2(x_k' - x_k) = λ (x_k - x_k')
    ⇒   λ  = -α^2.

We next claim the geometric multiplicity of this eigenvalue isN-2and, thus, this eigenvalue appearsN-2times in Equation <ref>.  Consider the operatorX-λI.  By choosing a suitable basis we may write this in matrix form as:

    X-λ I = (
    [  -λ  αβ  αβ   ⋯  αβ;  αβ  -λ α^2   ⋯ α^2;  αβ α^2  -λ   ⋯ α^2;   ⋮   ⋮   ⋮   ⋱   ⋮;  αβ α^2 α^2   ⋯  -λ ])

Substitutingλ= -α^2it is clear that the rank ofX - (-α^2)Iis at most two.  Thus the geometric multiplicity is at leastN-2(and indeed is exactlyN-2except whenQ=0orQ = 1-1/N; but the first case is considered separately as mentioned, and the second case impliesQ > 1/2which is much larger than our evaluations later and so not considered).  Therefore, exactlyN-2of the eigenvalues ofXare-α^2 = -Q^2/(N-1)^2.

The remaining two eigenvalues are found when there does not existk k'(wherek aandk' a) such thatx_k x_k'.  In this case we havex_k = x_k' = xfor allk, k'not equal toa.  Using Equation <ref> we find:

    αβ(N-1)x = λ x_a ⟹ x_a = αβ(N-1)x/λ.

Note that the above equation forcesx 0as, otherwise,x_ais also0and so|v⟩would be the zero vector and not an eigenvector of Hermitian operatorX.  Substituting this into Equation <ref> (for anyb a) we find:

    αβ(αβ(N-1)x/λ) + α^2(N-2)x = λ x
       λ^2 - α^2(N-2)λ - α^2β^2(N-1) = 0,

thus leading us to the two remaining eigenvalues, which we denoteλ^X_±:

    λ^X_± = 1/2(α^2(N-2)±α√(α^2(N-2)^2 + 4β^2(N-1))).

Since there was no dependence onain the above analysis, this leads us to conclude that:

    Δ_a,a = (N-2)Q^2/(N-1)^2 + |λ^X_+| + |λ^X_-|.


We next consider the case whenc aand computeΔ_a,c.  Following the same logic as before, fix a particularc aand consider the operatorY = N∑_bb'√(p(a,b,c)·p(a,b',c))|b⟩⟨b'|(and soΔ_a,c = ||Y||).  Let|v⟩ = ∑_ix_i|i⟩be an eigenvector ofYsuch thatY|v⟩ = λ|v⟩.  Then:

    Y|v⟩ = N∑_b=0^N-1(∑_i=0
    i  b^N-1x_i√(p(a,b,c)· p(a,i,c)))_z_b|b⟩ = N∑_bz_b|b⟩.

To satisfy the equationY|v⟩ = λ|v⟩we requireNz_b = λx_bfor allb=0,⋯, N-1.  There are three cases ofbto consider here:b=a,b=candba,c.  For each of these cases we find:

    b = a: Nz_a = λ x_a       αβ x_c + ∑_i c
     i  ax_i√(α^3β) = λ x_a
    
    b = c: Nz_c = λ x_c       αβ x_a + ∑_i  c 
     i  ax_i√(α^3β) = λ x_c
    
    b a,c: Nz_b = λ x_b       √(α^3β)x_a + √(α^3β)x_c + ∑_i a
    i  b
     i  cα^2x_i = λ x_b.


As with the previous operatorX, we break this up into several cases depending on the eigenvector|v⟩.  For the first case, assume there existsk k'withk a,candk'a,csuch thatx_k x_k'.  Then, using Equation <ref>, forb = kandb=k'and subtracting the resulting expressions yields:

    α^2(x_k' - x_k) = λ(x_k - x_k') ⟹λ = -α^2

We claim this eigenvalue has geometric multiplicityN-3.  Consider the operatorY - λIand, as before, by considering a suitable basis, we may write this in matrix form as:

    Y-λ I = (
    [      -λ      αβ √(α^3β) √(α^3β)       ⋯ √(α^3β);      αβ      -λ √(α^3β) √(α^3β)       ⋯ √(α^3β); √(α^3β) √(α^3β)      -λ     α^2       ⋯     α^2; √(α^3β) √(α^3β)     α^2      -λ       ⋯     α^2;       ⋮       ⋮       ⋮       ⋯       ⋱       ⋮; √(α^3β) √(α^3β)     α^2     α^2       ⋯      -λ ])

From this, it is evident that the rank ofY - (-α^2)Iis three and so the geometric multiplicity of the eigenvalue-α^2isN-3(again, assumingQ 0andQ 1-1/Nwhich holds since0 < Q < 1/2.

Thus, there are 3 more eigenvalues.  Next, consider the case ifx_a x_c.  In this case, subtracting Equation <ref> and <ref> yields:

    αβ(x_c-x_a) = λ(x_a-x_c) ⟹λ = -αβ


Finally, consider the case wherex_a = x_c = x_1andx_k = x_k' = x_2for everykk'andk,k' a,c.  In this case, Equation <ref> simplifies to:

    2√(α^3β)x_1 + α^2(N-3)x_2 = λ x_2

Note that this impliesx_2 0as, otherwise,x_1 = 0and so|v⟩is the zero vector and not an eigenvector.

Equation <ref> yields:

    αβ x_1 + (N-2)√(α^3β)x_2 = λ x_1

Note that the above equation also implies thatλαβsince if it were, we would havex_2 = 0which, as already discussed, is not true.  Thus we may solve:

    x_1 = (N-2)x_2√(α^3β)/λ-αβ.

Substituting this into Equation <ref> yields:

    2x_2α^3β(N-2)/λ-αβ + α^2(N-3)x_2 = λ x_2
       2α^3β(N-2) + α^2(N-3)(λ-αβ) = λ(λ-αβ).

Solving the above quadratic forλgives us the two remaining eigenvalues which we denoteλ^Y_±.  After some algebra, these eigenvalues are found to be:

    λ^Y_± = 1/2[αβ + α^2(N-3) ±α√((β+α[N-3])^2 + 4αβ(N-1))]

Since the above arguments were for arbitrarya c, this gives us the following:

    Δ_a,c   = (N-3)α^2 + αβ + |λ^Y_+| + |λ^Y_-|
       = (N-3)Q^2/(N-1)^2 + Q(1-Q)/N-1 + |λ^Y_+| + |λ^Y_-|.


Thus, we conclude:

    Δ   = 1/2N∑_a,c=0^N-1Δ_a,c = 1/2N∑_aΔ_a,a + 1/2N∑_a cΔ_a,c
       = 1/2((N-2)Q^2/(N-1)^2 + |λ^X_+| + |λ^X_-| + (N-1)[(N-3)Q^2/(N-1)^2 + Q(1-Q)/N-1 + |λ_+^Y| + |λ_-^Y|]).

At first glance, this expression may seem to scale exponentially withn(sinceN = 2^n).  However, note thatλ_±(for both theXandYoperators) are multiples ofα, which, itself, is a multiple of1/(N-1).








Returning to, we apply the Winter continuity bound (Equation <ref>) to attain:

    H(A_1^Z|E)_μ   ≥ H(A_1^Z|E)_ρ - Δlog N - (1+Δ)H(Δ/1+Δ)
       ≥ n - H(A_1^F|A_2^F)_ρ - Δlog N - (1+Δ)H(Δ/1+Δ)
       ≥ n(1 - Δ) - (1+Δ)H(Δ/1+Δ) - H(A_1^F|A_2^F)_ρ.

To finish the key-rate computation, we needH(A_1^F|A_2^F)_ρandH(A_1^Z|B^Z)_μ.  The first is determined through the observed valuesp_i,j^F, which we use to denote the probability thatAobserves|F_i⟩(inA_1) and|F_j⟩(inA_2) conditioned on the eventBchoose; the second is determined through the observed valuesp_i,j^Zwhich we use to denote the probability thatBobserves|j⟩andAobserves|i⟩inA_1(we useA_1as this is the register used for key-distillation) conditioned on the eventBchoose.  In both cases,i,j ∈{0,1,⋯,N-1}.  Clearly these are observable values allowingAandBto compute these final (classical) entropy expressions.  Since we are considering a symmetric attack modeled by the depolarization channel described in Equation <ref>, we havep_i,j^Z = 1/Np(j|i)and so we compute the joint entropy as:

    H(A_1^ZB^Z)_μ   = -∑_i,jp_i,j^Z log p_i,j^Z = -∑_i 1/Np(i|i)log_2 p(i|i) - ∑_i j1/Np(j|i)log_2p(j|i)
       =(1-Q)log_21-Q/N - QlogQ/N(N-1)
       = n + Qlog_2(N-1) + H(Q).

It is not difficult to show thatH(B^Z)_μ= n(since the attack is symmetric,B's probability of observing any particular value|j⟩is uniform).  Thus the conditional entropy is simply:

    H(A_1^Z|B^Z) = Qlog_2(N-1) + H(Q).


The case for thebasis is identical, though we use a different noise parameterQ_Fto parameterize the channel in this case (since the noise may be different in the reflection case as discussed earlier).  In this case we have:

    H(A_1^F|A_2^F) = Q_Flog_2(N-1) + H(Q_F).


Our final key-rate expression, therefore is:

    r    =H(A_1^Z|E) - H(A_1^Z|B^Z)
       ≥ n(1 - Δ) - (1+Δ)H(Δ/1+Δ) - (Q+Q_F)log_2(2^n-1) - H(Q) - H(Q_F).


Note that the above assumed collective attacks.  Ordinarily, one may extend such computations done for the collective attack case to prove security against arbitrary, general, attacks by using de Finetti style arguments or post-selection techniques <cit.>.  We suspect that this result holds for our protocol, however we leave a complete proof of that for future work.



 §.§ Evaluation

We evaluate our key-rate bound, Equation <ref>, in two scenarios.  First, we assume in the reflection case, that the reverse channel is independent of the forward and, so,Q_F = 2Q(1-Q)shown in Figure <ref>.  In the second dependent case, we assumeQ_F = Qshown in Figure <ref>.  We note that, similar to the fully-quantum case <cit.>, as the dimension increases, the noise tolerance also surpasses the single qubit case.  Thus, we prove that this high-dimensional advantage, known for fully-quantum protocols, also applies to the semi-quantum model.  We also observe numerically that, asnincreases, the maximal noise tolerance tends to approach26%in the independent case and30%in the dependent case.  As mentioned, fully-quantum high dimensional QKD protocols can tolerate up to50%error as the dimension increases; thus, while not as high as the fully-quantum case (which, perhaps, is to be expected), it is higher than any other semi-quantum protocol to-date.  Indeed, the highest known semi-quantum protocol <cit.> can tolerate up to17.8%in the independent case (as opposed to26%here) and26%in the dependent case (as opposed to30%here).  Of course, our Equation <ref> is only a lower-bound - future work may improve this.  In particular, the use of mismatched measurements (needed to attain a high noise tolerance in <cit.>) may greatly benefit our analysis here.  This we leave as an interesting future research direction.



§ CLOSING REMARKS


In this paper, we designed a new high-dimensional semi-quantum key distribution protocol and performed an information theoretic security analysis.  To conduct this security analysis, we developed several new techniques for high-dimensional protocols over two-way quantum channels which may be applicable to other (S)QKD protocols.  In particular we showed how one may reduce a two-way, high dimensional, semi-quantum protocol to a one-way protocol which is easier to analyze.   Thus, we produced new security results of broad application.  We also proved that high-dimensional quantum systems can benefit communication in the semi-quantum model just as they do in fully-quantum key distribution.

Many interesting future problems remain open.  For one thing, it would be interesting to see if our proof technique can be applied to the high-dimensional quantum-walk based SQKD protocol introduced in <cit.>.  If so, we would then be able to compare noise tolerance properties of the two protocols.  It would also be interesting to see if we can improve our bound and technique here.  One factor contributing to a potentially lower key-rate bound is our use of a continuity bound.  Other methods may produce more optimistic results.


10QKD-BB84
Charles H Bennett and Gilles Brassard.
 Quantum cryptography: Public key distribution and coin tossing.
 In  Proceedings of IEEE International Conference on Computers,
  Systems and Signal Processing, volume 175. New York, 1984.

qkd-survey
Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav
  Du ššek, Norbert Lütkenhaus, and Momtchil
  Peev.
 The security of practical quantum key distribution.
 Rev. Mod. Phys., 81:1301–1350, Sep 2009.

qkd-survey2
Akshata Shenoy-Hejamadi, Anirban Pathak, and Srikanth Radhakrishna.
 Quantum cryptography: Key distribution and beyond.
 Quanta, 6(1):1–47, 2017.

qkd-survey3
Mohsen Razavi, Anthony Leverrier, Xiongfeng Ma, Bing Qi, and Zhiliang Yuan.
 Quantum key distribution and beyond: introduction.
 J. Opt. Soc. Am. B, 36(3):QKD1–QKD2, Mar 2019.

SQKD-first-PRL
Michel Boyer, Dan Kenigsberg, and Tal Mor.
 Quantum key distribution with classical bob.
 Phys. Rev. Lett., 99:140501, Oct 2007.

SQKD-second
Michel Boyer, Ran Gelles, Dan Kenigsberg, and Tal Mor.
 Semiquantum key distribution.
 Phys. Rev. A, 79:032341, Mar 2009.

SQKD-mirror
Michel Boyer, Matty Katz, Rotem Liss, and Tal Mor.
 Experimentally feasible protocol for semiquantum key distribution.
 Physical Review A, 96(6):062335, 2017.

SQKD-lessthan4
Xiangfu Zou, Daowen Qiu, Lvzhou Li, Lihua Wu, and Lvjun Li.
 Semiquantum-key distribution using less than four quantum states.
 Phys. Rev. A, 79:052312, May 2009.

SQKD-no-measure1
Xiangfu Zou, Daowen Qiu, Shengyu Zhang, and Paulo Mateus.
 Semiquantum key distribution without invoking the classical party's
  measurement capability.
 Quantum Information Processing, pages 1–16, 2015.

med-sqkd1
Walter O. Krawec.
 Mediated semiquantum key distribution.
 Phys. Rev. A, 91:032323, Mar 2015.

med-sqkd2
Nan-Run Zhou, Kong-Ni Zhu, and Xiang-Fu Zou.
 Multi-party semi-quantum key distribution protocol with four-particle
  cluster states.
 Annalen der Physik, 0(0):1800520, 2018.

med-sqkd3
Po-Hua Lin, Chia-Wei Tsai, and Tzonelih Hwang.
 Mediated semi-quantum key distribution using single photons.
 Annalen der Physik, 0(0):1800347, 2019.

SQKD-secret1
Qin Li, W. H. Chan, and Dong-Yang Long.
 Semiquantum secret sharing using entangled states.
 Phys. Rev. A, 82:022303, Aug 2010.

SQKD-secret2
Lvzhou Li, Daowen Qiu, and Paulo Mateus.
 Quantum secret sharing with classical bobs.
 Journal of Physics A: Mathematical and Theoretical,
  46(4):045304, 2013.

SQKD-secret3
Jian Wang, Sheng Zhang, Quan Zhang, and Chao-Jing Tang.
 Semiquantum secret sharing using two-particle entangled state.
 International Journal of Quantum Information, 10(05), 2012.

state-comp1
Kishore Thapliyal, Rishi Dutt Sharma, and Anirban Pathak.
 Orthogonal-state-based and semi-quantum protocols for quantum private
  comparison in noisy environment.
 International Journal of Quantum Information, 16(05):1850047,
  2018.

state-comp2
Wen-Han Chou, Tzonelih Hwang, and Jun Gu.
 Semi-quantum private comparison protocol under an almost-dishonest
  third party.
 arXiv preprint arXiv:1607.07961, 2016.

state-comp3
Lang Yan-Feng.
 Semi-quantum private comparison using single photons.
 International Journal of Theoretical Physics,
  57(10):3048–3055, 2018.

QKD-BB84-rate1
Peter W. Shor and John Preskill.
 Simple proof of security of the bb84 quantum key distribution
  protocol.
 Phys. Rev. Lett., 85:441–444, Jul 2000.

renner-keyrate
Renato Renner, Nicolas Gisin, and Barbara Kraus.
 Information-theoretic security proof for quantum-key-distribution
  protocols.
 Physical Review A, 72(1):012332, 2005.

QKD-Tom-Krawec-Arbitrary
Walter O. Krawec.
 Quantum key distribution with mismatched measurements over arbitrary
  channels.
 Quantum Information and Computation, 17(3 and 4):209–241,
  2017.

QKD-Tom-First
Stephen M Barnett, Bruno Huttner, and Simon JD Phoenix.
 Eavesdropping strategies and rejected-data protocols in quantum
  cryptography.
 Journal of Modern Optics, 40(12):2501–2513, 1993.

QKD-Tom-KeyRateIncrease
Shun Watanabe, Ryutaroh Matsumoto, and Tomohiko Uyematsu.
 Tomography increases key rates of quantum-key-distribution protocols.
 Physical Review A, 78(4):042316, 2008.

QKD-Tom-KeyRateMismatchedDistill
Ryutaroh Matsumoto and Shun Watanabe.
 Key rate available from mismatched measurements in the bb84 protocol
  and the uncertainty principle.
 IEICE Transactions on Fundamentals of Electronics,
  Communications and Computer Sciences, 91(10):2870–2873, 2008.

QKD-Tom-BB84NarrowAngle
Ryutaroh Matsumoto and Shun Watanabe.
 Narrow basis angle doubles secret key in the bb84 protocol.
 Journal of Physics A: Mathematical and Theoretical,
  43(14):145302, 2010.

SQKD-high-noise
Omar Amer and Walter O Krawec.
 Semi-quantum key distribution with high quantum noise tolerance.
 arXiv preprint arXiv:1812.04144, 2018.

CAD-1
Geir Ove Myhr, Joseph M Renes, Andrew C Doherty, and Norbert Lütkenhaus.
 Symmetric extension in two-way quantum key distribution.
 Physical Review A, 79(4):042329, 2009.

BB84-CAD
Hoi Fung Chau.
 Practical scheme to share a secret key through a quantum channel with
  a 27.6% bit error rate.
 Physical Review A, 66(6):060302, 2002.

high-dim0
H Bechmann-Pasquinucci and Wolfgang Tittel.
 Quantum cryptography using larger alphabets.
 Physical Review A, 61(6):062308, 2000.

high-dim1
Hoi Fung Chau.
 Unconditionally secure key distribution in higher dimensions by
  depolarization.
 IEEE Transactions on Information Theory, 51(4):1451–1468,
  2005.

QKD-high-dim-dep
Lana Sheridan and Valerio Scarani.
 Security proof for quantum key distribution using qudit systems.
 Physical Review A, 82(3):030301, 2010.

QKD-high-dim-50
HF Chau.
 Quantum key distribution using qudits that each encode one bit of raw
  key.
 Physical Review A, 92(6):062324, 2015.

QKD-QW
Chrysoula Vlachou, Walter Krawec, Paulo Mateus, Nikola Paunković, and
  André Souto.
 Quantum key distribution with quantum walks.
 Quantum Information Processing, 17(11):288, 2018.

high-dim2
Nicolas J Cerf, Mohamed Bourennane, Anders Karlsson, and Nicolas Gisin.
 Security of quantum key distribution using d-level systems.
 Physical Review Letters, 88(12):127902, 2002.

high-dim3
Georgios M Nikolopoulos and Gernot Alber.
 Security bound of two-basis quantum-key-distribution protocols using
  qudits.
 Physical Review A, 72(3):032320, 2005.

high-dim4
Georgios M Nikolopoulos, Kedar S Ranade, and Gernot Alber.
 Error tolerance of two-basis quantum-key-distribution protocols using
  qudits and two-way classical communication.
 Physical Review A, 73(3):032325, 2006.

high-dim5
Toshihiko Sasaki, Yoshihisa Yamamoto, and Masato Koashi.
 Practical quantum key distribution protocol without monitoring signal
  disturbance.
 Nature, 509(7501):475, 2014.

high-dim6
Zhen-Qiang Yin, Shuang Wang, Wei Chen, Yun-Guang Han, Rong Wang, Guang-Can Guo,
  and Zheng-Fu Han.
 Improved security bound for the round-robin-differential-phase-shift
  quantum key distribution.
 Nature communications, 9(1):457, 2018.

high-dim7
Rong Wang, Zhen-Qiang Yin, Chao-han Cui, Shuang Wang, Wei Chen, Guang-Can Guo,
  and Zheng-Fu Han.
 Security proof for single-photon round-robin
  differential-quadrature-phase-shift quantum key distribution.
 Physical Review A, 98(6):062331, 2018.

lm05
Marco Lucamarini and Stefano Mancini.
 Secure deterministic communication without entanglement.
 Physical review letters, 94(14):140501, 2005.

pp-sdc
Kim Boström and Timo Felbinger.
 Deterministic secure direct communication using entanglement.
 Physical Review Letters, 89(18):187902, 2002.

lm05-ent
Normand J. Beaudry, Marco Lucamarini, Stefano Mancini, and Renato Renner.
 Security of two-way quantum key distribution.
 Phys. Rev. A, 88:062302, Dec 2013.

CV-floodlight
Quntao Zhuang, Zheshen Zhang, Justin Dove, Franco N. C. Wong, and Jeffrey H.
  Shapiro.
 Floodlight quantum key distribution: A practical route to
  gigabit-per-second secret-key rates.
 Phys. Rev. A, 94:012322, Jul 2016.

CV4
Carlo Ottaviani, Stefano Mancini, and Stefano Pirandola.
 Two-way gaussian quantum cryptography against coherent attacks in
  direct reconciliation.
 Physical Review A, 92(6):062323, 2015.

CV5
Quntao Zhuang, Zheshen Zhang, Norbert Lütkenhaus, and Jeffrey H Shapiro.
 Security-proof framework for two-way gaussian
  quantum-key-distribution protocols.
 Physical Review A, 98(3):032332, 2018.

high-dim5-exp
Jian-Yu Guan, Zhu Cao, Yang Liu, Guo-Liang Shen-Tu, Jason S Pelc, MM Fejer,
  Cheng-Zhi Peng, Xiongfeng Ma, Qiang Zhang, and Jian-Wei Pan.
 Experimental passive round-robin differential phase-shift quantum key
  distribution.
 Physical review letters, 114(18):180502, 2015.

high-dim5-exp2
Hiroki Takesue, Toshihiko Sasaki, Kiyoshi Tamaki, and Masato Koashi.
 Experimental quantum key distribution without monitoring signal
  disturbance.
 Nature Photonics, 9(12):827, 2015.

high-dim-exp3
Nurul T Islam, Clinton Cahall, Andrés Aragoneses, A Lezama, Jungsang Kim,
  and Daniel J Gauthier.
 Robust and stable delay interferometers with application to
  d-dimensional time-frequency quantum key distribution.
 Physical Review Applied, 7(4):044010, 2017.

high-dim-exp4
Shuang Wang, Zhen-Qiang Yin, HF Chau, Wei Chen, Chao Wang, Guang-Can Guo, and
  Zheng-Fu Han.
 Proof-of-principle experimental realization of a qubit-like
  qudit-based quantum key distribution scheme.
 Quantum Science and Technology, 3(2):025006, 2018.

QKD-uncertainty
Mario Berta, Matthias Christandl, Roger Colbeck, Joseph M Renes, and Renato
  Renner.
 The uncertainty principle in the presence of quantum memory.
 Nature Physics, 6(9):659–662, 2010.

SQKD-photon-tag
Yong-gang Tan, Hua Lu, and Qing-yu Cai.
 Comment on 'quantum key distribution with classical bob'.
 Phys. Rev. Lett., 102:098901, Mar 2009.

SQKD-photon-tag-comment
Michel Boyer, Dan Kenigsberg, and Tal Mor.
 Boyer, kenigsberg, and mor reply:.
 Phys. Rev. Lett., 102:098902, Mar 2009.

winter-keyrate
Igor Devetak and Andreas Winter.
 Distillation of secret key and entanglement from quantum states.
 Proceedings of the Royal Society A: Mathematical, Physical and
  Engineering Science, 461(2053):207–235, 2005.

krawec-conf
Walter O Krawec.
 Key-rate bound of a semi-quantum protocol using an entropic
  uncertainty relation.
 In  2018 IEEE International Symposium on Information Theory
  (ISIT), pages 2669–2673. IEEE, 2018.

winter-cont
Andreas Winter.
 Tight uniform continuity bounds for quantum entropies: Conditional
  entropy, relative entropy distance and energy constraints.
 Communications in Mathematical Physics, 347(1):291–313, Oct
  2016.

lucamarini2014quantum
Marco Lucamarini and Stefano Mancini.
 Quantum key distribution using a two-way quantum channel.
 Theoretical Computer Science, 560:46–61, 2014.

de-finetti1
Robert König and Renato Renner.
 A de finetti representation for finite symmetric quantum states.
 Journal of Mathematical physics, 46(12):122108, 2005.

postselection1
Matthias Christandl, Robert König, and Renato Renner.
 Postselection technique for quantum channels with applications to
  quantum cryptography.
 Physical review letters, 102(2):020504, 2009.