Workshop Programme
for period 6  10 September 2004
Focus Week: Quantum Cryptography
6  10 September 2004
Timetable
Monday 6 September  
11:3012:15  Lo, HK (Toronto)  
Decoy state quantum key distribution: the best of both worlds?  Sem 2  
The standard weak coherent state implementation of quantum cryptography has nontrivial security issues because an eavesdropper can, in principle, suppress singlephoton signals relative to multiphoton signals. This leads to fundamental limits to the key generation rate [of order O (\eta2), where \eta is the transmission probability of the channel] and distance of uncondiitonally secure quantum key distribution [of order 20km for Telecom fibers]. Here, we show that the decoy state, first suggested by Hwang, can be used to prove unconditional security in the standard entanglement distillation approach. Our result shows that rather surprisingly, by using only current technology, unconditionally secure quantum key distribution can be achieved with a key generation rate of order O (\eta) and substantially longer distances (more than double). In our method, Alice simply turns the power of her laser up and down and prepares decoy states. The statistical properties of the transmitted decoy states are then analyzed to derive constraints on the signal states. 

12:1513:00  Renner, R (ETH Zurich)  
Privacy amplification against quantum adversaries  Sem 2  
Privacy amplification is the art of shrinking a partially secret string Z to a highly secret key S. We show that, even if an adversary holds quantum information about the initial string Z, the key S obtained by twouniversal hashing is secure, according to a universally composable security definition. Additionally, we give an asymptotically optimal lower bound on the length of the extractable key S in terms of the adversary's (quantum) knowledge about Z. Our result has applications in quantum cryptography. In particular, it implies that many of the known quantum key distribution protocols are universally composable. 

14:1515:00  Christandl, M (Cambridge)  
A generic security proof for quantum key distribution  Sem 2  
Quantum key distribution allows two parties, traditionally known as Alice and Bob, to establish a secure random cryptographic key if, firstly, they have access to a quantum communication channel, and secondly, they can exchange classical public messages which can be monitored but not altered by an eavesdropper, Eve. Quantum key distribution provides perfect security because, unlike its classical counterpart, it relies on the laws of physics rather than on ensuring that successful eavesdropping would require excessive computational effort. However, security proofs of quantum key distribution are not trivial and are usually restricted in their applicability to specific protocols. In contrast, we present a general and conceptually simple proof which can be applied to a number of different protocols. It relies on the fact that a cryptographic procedure called privacy amplification is equally secure when an adversary's memory for data storage is quantum rather than classical. 
Tuesday 7 September  
11:3012:15  Gisin, N (Geneva)  
1. A new protocol for high bit rates 2. A new type of security proofs  Sem 2  
Main message: Q crypto is entering the industrial age, but basic research is still needed. Examples: 1. New Q crypto protocols should be designed taking into account realistic constraints. Examples are "continuous variables" and the SARG protocol [PRL 92,057901,2004]. In this talk we present another new protocol that aims at Gbit/sec rates. 2. It is desirable to simplify proofs of security against the most general coherent attack. We take advantage of some recent results in classical information based cryptography and on the symmetry of the 6state protocol to demonstrate that coherent attacks are not more powerfull than collective attacks. Using this we present a new kind of security proof that improves over the ShorPreskill result. 

12:1513:00  Unruh, D; MuellerQuade, J (Karlsruhe)  
Relating formal security for classical and quantum protocols  Sem 2  
Using a simple example we demonstrate the necessity of a formal modelling of security. We explain the established notion of simulatable security (e.g. reactive simulatability by Backes, Pfitzmann, Waidner, or universal composability by Canetti) and show how this model can be extended to encompass quantum security (cf. also the work of BenOr, Mayers). We conclude with a Quantum Embedding Theorem that allows to securely use quantum protocols as subprotocols in classically secure protocols. 

14:1514:35  Wehner, S (CWI)  
Quantum anoymous transmissions  Sem 2  
We consider the problem of hiding sender and recipient of classical and quantum bits, even if all physical transmissions can be monitored. We present a quantum protocol for sending and receiving classical bits anonymously, which unlike all classical protocols, prevents later reconstruction of the sender. It appears that entangled quantum states are uniquely suited for anonymous transmissions. We then extend this protocol to provide sender and recipient untraceability for transmissions of qubits as well. In the process we also introduce a new primitive called anonymous entanglement, which may be useful for other protocols as well. 

14:3514:55  Colbeck, R (Cambridge)  
Variable bias coin tossing  Sem 2  
I will introduce the task of variable bias coin tossing, and describe two protocols for achieving it. 

14:5515:15  Kent, APA (Cambridge)  
A simple nogo lemma  Sem 2  
I describe a simple general nogo result in mistrustful quantum cryptography. 
Wednesday 8 September  
11:0011:30  Coffee  
11:3012:15  Barrett, J (Universite Bruxelles Libre)  
Nonlocal correlations and key distribution  Sem 2  
We present a quantum key distribution scheme that is secure even against eavesdroppers who can break the laws of quantum mechanics, as long as superluminal signalling is impossible. The scheme is based on violation of a Bell inequality, and its security stems from the fact that nonlocal correlations are monogamous, in analogy with the monogamy of entanglement. 

14:1515:00  Duer, W (Austria)  
Graph states  stability under decoherence, entanglement purification and possible applications  Sem 2  
We will consider a specific family of multipartite entangled states, namely (weighted) graph states. We investigate the influence of decoherence on the entanglement properties of the states for various decoherence models. We show that the lifetime of entanglement of GHZ states decreases with the number of particles, while cluster (and similar) graph states the lifetime is independent of the size of the system. We discuss several multiparty entanglement purification protocols which allow one to create and/or maintain two colorable graph states with high fidelity. We compare direct multiparty entanglement purification protocols with protocols based on bipartite purification and show that the former are more efficient. We investigate the influence of imperfections in local control operations, where we find a remarkable robustness against errors for protocols which allow one, e.g., to purify cluster states. The achievable fidelity using direct multiparty purification is higher than purification based on bipartite protocols. We discuss possible applications of multiparty entanglement purification protocols for secure multiparty communication. 

15:3016:15  Pederson, T (Colombia)  
On the keyuncertainty of quantum ciphers and the computational security of oneway quantum transmission  Sem 2  
We consider the scenario where Alice wants to send a secret (classical) $n$bit message to Bob using a classical key, and where only oneway transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then $n$. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns $n$ bits of information on the key in a known plaintext attack. We also show that there is a limit to how different the classical and quantum cases can be: the most probable key, given matching plain and ciphertexts, has the same probability in both the quantum and the classical cases. We suggest an application of our results in the case where only a short secret key is available and the message is much longer. Namely, one can use a pseudorandom generator to produce from the short key a stream of keys for a quantum cipher, using each of them to encrypt an $n$bit block of the message. Our results suggest that an adversary with bounded resources in a known plaintext attack may potentially be in a much harder situation against quantum streamciphers than against any classical streamcipher with the same parameters. 
Thursday 9 September  
11:3012:15  Hardy, L (Perimeter Institute)  
Cheat sensitive bit commitment  Sem 2  
We define cheat sensitive cryptographic protocols between mistrustful parties as protocols which guarantee that, if either cheats, the other has some nonzero probability of detecting the cheating. We give an example of an unconditionally secure cheat sensitive nonrelativistic bit commitment protocol which uses quantum information to implement a task which is classically impossible. Related Links


12:1513:00  Massar, S (ULB)  
Experimental quantum bit string generation  Sem 2  
I will discuss the theory of quantum bit string generation, present an experimental realisation of quantum bit string generation with security better than can be achieved classicaly, and discuss how to improve on this first experimental realisation. 

13:0014:15  Lunch Churchill College cafeteria will close at 13:30  
14:1515:00  Leung, D (Caltech)  
Applications of quantum universal composability theorem  Sem 2  
The quantum universal composability theorem will first be reviewed. Next, applications to a new security definition of QKD and security proofs will be given. Finally, we prove composable security for various variants of the quantum message authentication scheme proposed in quantph/0205128 with key recycling. 

16:0022:00  
PROSECCO meeting (joint with RESQ)  Sem 2 
Friday 10 September  
11:3012:15  Horodecki, M (Gdansk)  
Locking of entanglement  Sem 2  
We study the loss of entanglement of bipartite state subjected to discarding or measurement of one qubit. Examining the behavior of different entanglement measures, we find that entanglement of formation, entanglement cost, and negativity are lockable measures in that they can decrease arbitrarily after measuring one qubit. Relative entropy of entanglement is shown to be a nonlockable measure. 

12:1513:00  Lutkenhaus, N (ErlangenNurnberg)  
Quantum correlations in quantum cryptology  Sem 2  
In basic quantum communication protocols one party creates quantum states and uses a quantum channel to transmit it to another party that performs immediately some measurement on it. This means, we effectively create correlated (classical) data between distant parties. In order to use the power of quantum mechanics, these correlation must show effects of quantum mechanics. In the specific example of quantum key distribution one uses the correlations to distill a secret key in (classical) public discussion protocols e.g. via sifting, error correction and privacy amplification. We give a necessary condition for the success of any public discussion protocol: the observed correlations should allow to prove the presence of an internal, virtual state of entanglement in the distribution. This poses a first test whether any presented real quantum key distribution is indeed useful for the desired purpose. Moreover, a gap between the parameter regime of proven security of given realistic schemes and the regime of proven presence of vitual entanglement furthers the search for the optimal public discussion protocol. 

14:1515:00  Winter, A (Bristol)  
Distillation of secret key and entanglement from quantum states  Sem 2  
Based on techniques from classical information theory, which we generalise to the quantum domain, we show how to distill secret key between two parties by local operations and public communication from given states, at an asymptotically optimal rate. By implementing this protocol "coherently", we then show how it yields actually entanglement, at the same rate, proving the longconjectured "hashing inequality": it states that from a given quantum state, once can, using oneway LOCC, distill entanglement with rate given by the coherent information. This is joint work with Igor Devetak; it is contained in eprints quantph/0306078 and quantph/0307053. 

15:3016:15  Bennett, CH (IBM)  
Unlocking of a quantum channel's forward classical capacity by classical communication  Sem 2  
Classical back communication does not increase a classical channel's forward capacity, but for quantum channels the situation is more complicated. It is well known that classical back communication can increase quantum capacity, but no example was known where it increased a quantum channel's classical capacity. We have found channels whose Holevo capacity is almost zero, but whose quantum and classical capacities in the presence of classical back communication are quite large. The greater complexity of the situation with quantum channels stems from the fundamental difference between entanglement and its closest classical analog, shared secret randomness. Joint work with Igor Devetak, Peter Shor, and John Smolin. quantph/0406086. 