July 2008

Cryptography from Noisy Storage

Physical Review Letters 100, 220502 (2008)

Stephanie Wehner, Christian Schaffner and Barbara M. Terhal

With the arrival of widespread electronic communication new cryptographic tasks have become increasingly important. We are no longer satisfied with the secure and reliable transmissions of messages, but want to solve a large number of tasks where the protocol participants themselves do not trust each other. Important examples of such tasks are secure identification, electronic voting, and contract signing. Unfortunately, it has been shown that it is impossible to implement such tasks securely without making assumptions on how powerful an attacker can be, even if we allow quantum communication. Classically a commonly used assumption is that it is difficult to factor a large number. This assumption, however, no longer holds once a quantum computer is built, and it is presently unknown whether this assumptions even holds classically. It is therefore an important problem to find realistic assumptions that allows us to achieve such tasks. Can quantum communication be of any help us?

Recently, it has been shown by QAP researchers that we can implement two-party protocols securely if we assume that it is difficult to store quantum states without errors. Here, the very problem that makes it so hard to implement a quantum computer can actually be turned to our advantage. Practically, such noise can arise as a result of transferring a photonic qubit onto a different physical carrier, such as for example an atomic ensemble or atomic state. In addition, a quantum state will undergo noise once it has been transferred into 'storage' if such quantum memory is not 100% reliable.

As a proof of principle, the QAP researchers have shown that we can obtain the two-party protocol 1-out-of-2 oblivious transfer in this model. This important primitive, that may indeed appear rather bizarre at first glance, can actually be used as a fundamental building block to implement any two party protocol. In oblivious transfer (see Figure 1), Alice holds two input bits s₀ and s₁. The goal of the protocol is to allow Bob to retrieve one of the two bits s_c according to his choice bit c, in such a way that Alice cannot learn which of the two bits Bob has retrieved. Thus, Bob cannot simply ask for one of the bits. At the same time, the protocol should guarantee that Bob can only learn exactly one of the two bits. Hence, Alice cannot simply send her two inputs to Bob. In their work, the QAP researchers have examined a simple protocol for this task, that can be implemented using hardware that is already used today to implement quantum key distribution (QKD). No quantum storage is thereby required for the honest participants. The key idea behind the protocol is to show that if Bob is dishonest (that is he tries to learn more than one of Alice's inputs) and attempts to store the quantum states sent by Alice until maybe later he received some additional information that would help him, he has already lost too much information due to the noise in the storage process. (see Figure 2)

In a real world setting, the honest players Alice and Bob do of course also experience some noise in their operations. In more recent work (arxiv:0807.1333) however it was shown that the protocol for oblivious transfer still remains secure, even if the honest participants experience 11% of noise and the noise on the channel and in their operations is strictly less than the noise in the quantum storage. This value may seem small, but unlike QKD, it is still interesting to implement such protocols even over very short distances. This is particularly the case for secure identification that is of relevance to banking applications.

This work shows that noise can indeed sometimes be a good thing and help us to implement cryptographic primitives which are otherwise impossible to obtain without making any assumptions. It opens the door for much further research in this direction. Can we find efficient protocols for other tasks? (without using the primitive oblivious transfer) What security to we obtain from more generalized noise models than the ones considered here? Finally, what are the fundamental limits of this model?

 

 Experimental Decoy-State Quantum Key Distribution with a Sub-Poissionian Heralded Single-Photon Source

Physical Review Letters 100, 220502 (2008)

Q. Wang, W. Chen, G. Xavier， M. Swillo, S. Sauge, M. Tengner, T. Zhang, Z. F. Han, G. C. Guo, A. Karlsson

Overview

Using an optimized heralded single-photon source (HSPS) based on parametric down-conversion, the KTH research group cooperating with a Chinese USTC group has experimentally demonstrated a decoy-state quantum key distribution scheme (QKD) [1-3]. They used a one-way BB84 protocol with a four states and one-detector phase-coding scheme, which is immune to recently proposed time-shift attacks, photon-number splitting attacks, and can also be proven to be secure against Trojan horse attacks and any other standard individual or coherent attacks.

As shown in Fig. 1 (below), using the BB84 protocol and under the same experimental conditions, we compare our HSPS with decoy state scheme to several other schemes, including HSPS without decoy states,
weak coherent state (WCS) with or without decoy states, and also the ideal single-photon source (SPS) case. (In order to give a fair comparison, all these lines are not taken statistical error into account.) As can be seen, our scheme (red solid line) gets the maximum tolerable losses or the highest key generation rate under fixed losses among all these practical schemes. Moreover, if a better HSPS (blue dashed line with 70% correlated photon pairs) is used, its performance comes close to the ideal single-photon source.
Our experimental setup is shown in Fig. 2, and our final experimental results fit our theoretical predictions [4] quite well as shown in Fig. 3.

However, our final key rate is lower than in other systems reported before, because there are large losses in our QKD system. With present technology, it is realistic to decrease the loss by 15 - 18 dB in this QKD system, which is quite considerable for a long distance transmission (>100 km).

Despite of these deficiencies in our present system, this experiment is still sufficient to prove, in principle, that our HSPS based decoy-state scheme can tolerate the highest losses among all practical schemes, which also means the highest secure key generation rate under fixed losses. Therefore, it is a good candidate for future quantum key distribution systems.

References
[1] W. Y. Hwang, Phys. Rev. Lett. 91, 057901 (2003).
[2] X. B. Wang, Phys. Rev. Lett. 94, 230503 (2005).
[3] H. K. Lo, X. Ma, and K. Chen, Phys. Rev. Lett. 94. 230504 (2005).
[4] Q. Wang et al. ArXiv: quant-ph/0803.3643