Free-Space Quantum Cryptography

Contents

1 Introduction

2 Classical Cryptography
2.1 General Remarks
2.2 Glossary
2.3 Kerckhoffs’ Principle and Encryption Keys
2.4 Symmetric and Asymmetric Ciphers
2.5 Transposition Ciphers
2.6 Substitution Ciphers
· Monoalphabetic Substitution
· Polyalphabetic Substitution
· Homophonic Substitution
· Polygraphic Substitution
· Rotor Machines
2.7 One-time Pad
· Problems with One-time Pad
2.8 Modern Cryptography
2.8.1 Symmetric Key Algorithms: DES and AES
· The Feistel Function
2.8.2 Asymmetric Algorithms
2.8.3 Hybrid Cryptosystems
2.9 Security
2.9.1 Computational Complexity
2.9.2 Successful Attacks

3 Quantum Cryptography
3.1 Introduction
3.2 Quantum Mechanical Background
3.2.1 Qubits
· Practical Realization of Qubit States
3.2.2 No-go Theorems
3.3 Quantum Entanglement and Bell’s Theorem
3.4 Quantum Protocols
3.4.1 Four-State Protocol: BB
· Security: Intercept-Resend and Cloning Attack
3.4.2 Two-State Protocol: B92
· Security: Unambiguous State Discrimination Attack
Contents
3.4.3 QKD with Weak Coherent Pulses
· Decoy State Protocol
3.4.4 Entanglement-Based QKD: Original and Simplified
Ekert Protocols
3.5 Error Correction and Privacy Amplification
3.5.1 Error Correction
3.5.2 Privacy Amplification

4 The Munich Experiment
4.1 Sender Unit: Alice
· Driving Electronics
4.1.1 LD Electrical Characterization
4.1.2 Laser Diode Spectral Characterization
4.1.3 Information Gain from Spectral Measurements
4.2 Quantum Channel
· Automatic Alignment
4.3 Receiver Unit: Bob
4.4 Synchronization
4.5 Conclusion

5 Temperature Stabilization
5.1 The Main Idea
5.2 Thermal Management
5.2.1 Spectral Dependency
5.2.2 Preliminary Analysis
5.2.3 TEC Device
5.2.4 TEC Controller Unit
5.3 New Design

6 Summary & Outlook

A The Extended Euclidean Algorithm

B Beam Parameters

Bibliography

1 Introduction

Cryptography is the art of obscuring the content of a message to unauthorized people, but to make it accessible to trusted parties. This practice has ancient origins and, in the course of the centuries, it could meet more and more de- manding requirements determined by the parallel ability of codebreakers to gain knowledge about those secrets. Nevertheless, particularly in the informa- tion age in which we live, concerns about security questions have become an everyday topic. If, on the one hand, the internet is now the ultimate place to accelerate the flow of relevant information, on the other hand, companies, government facilities, or even private people must be sure that confidential data flows cannot be accessible to someone else but the authorized party the message is addressed to. In order to ensure such a security level over publicly available networks, some nowadays standardized procedures come into play.

For practical reasons, the most frequently used protocols rely on so called asymmetric key algorithms (public-key cryptography), where the encryption key is published, which allows any sender to perform encryption and to safely send his message, while a private key is kept secret by the receiver, which enables only him to perform decryption. Although widely used, e.g. in online- banking transactions or e-commerce, the security of such cryptographic rou- tines is taken for granted only under some reasonable (but not necessarily true) assumptions, such, e.g., limited computational power at one’s disposal or low efficiency of factorizing algorithms.

The only encryption procedure which has been shown to be unbreakable¹ is the one-time pad, a symmetric key algorithm. Unfortunately, some major drawbacks, key distribution above all, make this process hard to implement in the framework of classical information theory. Nevertheless, though this deficiency, it turns out that quantum information theory is able to provide a way-out to this problem. Unlike classical cryptography, which uses mathema- tical techniques to restrict the amount of eavesdropped information, quantum cryptography exploits the quantum character of nature to ensure secure com- munication between two trusted parties. This new issue, known under the name of Quantum Key Distribution (QKD) ², provides the two parties, Alice and Bob, with a setup to generate a secret key, which can be used afterwards in the encryption/decryption process of the secret message (e.g. with one-time pad). Within this scheme, single key bits are encoded in states of a quantum mechanical system (e.g. polarization states of a photon), and then distributed between two or more parties. If an eavesdropper would ever attempt to in- tercept key bits, he has to carry out a measurement on a quantum mechan- ical system, unavoidably changing its status, hence introducing errors. This revolutionary principle of eavesdropping can be detected, is used in analysis protocols which can assert whether the key exchange was secure, or someone tried to eavesdrop, in which case the key has to be dismissed.

In this work we present an experimental implementation of such a scheme, in which raw key bits are encoded in four different polarization states of photons. Using the first proposed quantum encoding protocol, the BB84, and weak co- herent pulses from a laser source, we could realize a stable link between trans- mitter and receiver units over a free-space distance of 500 m. Software-based procedures for key extraction and privacy amplification lead to the final shared secure key. This thesis-work is articulated in four main sections: In the first (Chap. 2), we provide the reader with a wide overview of classical crypto- graphic methods, how they work and their security issues. The second (Chap. 3) illustrates the main concepts of QKD and the underlying physics involved in them. The third section (Chap. 4) deals with the description of our test-setup located in downtown Munich, with particular attention paid to transmitter/re- ceiver units and source spectral selection. The last part describes the applied procedures for thermal management, which aims to stabilize the spectral char- acteristics of the source.

2 Classical Cryptography

2.1 General Remarks

Before computer age, the term cryptography (from the Greek κρυπτ óς “hid- den” and γραϕη “to write”), referred solely to the process of changing the con- tent of a message in order to make it unreadable without special knowledge. Since then, the meaning assumed a wider dimension, and nowadays can be summarized with the words of a famous cryptologist, Ron Rivest, who stated: “ Cryptography is about communication in the presence of adversaries ” [Riv90]. Moreover, the art of gaining unauthorized information, is called cryptanalysis (loosely speaking codebreaking), and together with cryptography constitutes the field of studies of cryptology.

In the technical literature, a fundamental distinction between “classical” and “modern” cryptography is made. The former refers to the age where cryp- tographic procedures were still accomplished with paper and pen; the latter refers to almost the same tasks but carried out with the help of computers. Nevertheless, throughout this work, the meaning of the adjective “classical” is extended to include also the modern cryptography as a subset, to better outline the difference relative to cryptographic tasks accomplished with the help of quantum based devices.

2.2 Glossary

For the general discussion we need some fundamental definitions beforehand.

Plaintext: The message, cleartext or bit string, one wishes to obscure.

Cipher: The algorithm by which the plaintext is made unintelligible to unauthorized parties.

Ciphertext: The output of an encrypting algorithm.

Key: Additional piece of information which is needed for performing encryption and decryption.

illustration not visible in this excerpt

Figure 2.1: Alice wishes to send a message to Bob without revealing its content either to accidental or bad intentioned eavesdroppers. To do this, she first encrypts the message, then sends it out to Bob over a possibly unsafe communication channel; after Bob has received it, he applies the deciphering algorithm to finally get the original information again.

Encryption: The process of obscuring the information contained in the plaintext through application of a cipher.

Decryption: The process of recovering the original message from the ciphertext. It is the inverse of encryption.

Stream Cipher: Encrypting algorithm that acts on the smallest unit of the message (e.g. a letter in traditional “analog” cryptography, or a bit in computer based applications).

Block Cipher: Unlike a stream cipher, the algorithm manipulates block of characters or bits of the plaintext.

The general scheme we have in mind is depicted in Fig. 2.1.

2.3 Kerckhoffs’ Principle and Encryption Keys

Historically, in the field of cryptography, we can distinguish between two different approaches. The first is condensed in the principle “ security by obscurity ”, that is the difficulty for an eavesdropper to gain information relies on his ignorance about the cipher which generated the ciphertext. This principle is widely used in computer related applications, where secrecy (of design, implementation, etc.) is used to gain security.

The problem of the “security by obscurity” approach is the actual difficulty to ensure secrecy of all sensible parts of the encrypting system for arbitrary long time. Moreover, as soon as the details of a cryptographic implementation are disclosed, all past, present and future pieces of encrypted informations become accessible at once. These major objections are more precisely referred to as Kerckhoffs’ law, stated by the Flemish linguist and cryptographer Auguste Kerckhoffs in 1883 [Ker83]. After this principle, a good cryptographic system should remain secure even if it falls in adversary’s hands, or, in Shannon’s other formulation: “ the enemy knows the system ”. Within this second inter- pretation, the aim is making the output of the cipher as strongly as possible dependent from another piece of information, the key, which must be kept secret.

In every cryptographic design relying to the latter method, decrypting the ciphertext with the wrong key will produce a useless random sequence.

2.4 Symmetric and Asymmetric Ciphers

Following [Sch96], we can further divide key-based algorithms into two sub- sets: symmetric and asymmetric ones. Ciphers belonging to the first class use trivially related keys for the encryption/decryption process. Though in most algorithms of this kind the encryption and decryption key are simply identical, this doesn’t need to be true in general; the important point is that the encryption key can be easily calculated from the decryption key and vice versa. The successful implementation of symmetric-key algorithms (also called secret-key algorithms), requires that sender and receiver agree on a key before the communication takes place. Moreover, since the security of the process rests in the key, this has to be safely distributed between the two parties. Actually, this last requirement constitutes a serious deficiency in the security of classical symmetric-key procedures.

Ciphers belonging to the second class use a key-pair: one for encryption and one for decryption. The encryption key is mathematically related to the decryption key by a so called one-way function: given the decryption key, it is easy to deduct the corresponding encryption key, while it results computationally difficult to go the other way around.

The advantage of the latter scheme is exploited in public-key algorithms, such as RSA (see Section 2.8.2), where the encryption key doesn’t need to be secret, so that everyone can encrypt his message, while it can be read only by those who possess the corresponding private decryption key.

2.5 Transposition Ciphers

Because of their character based nature, this type of ciphers are among the oldest ones. The algorithm is fairly straightforward: given a plaintext, it shuffles its characters assigning to every letter a new position on an imaginary indexed table. Mathematically, the encrypting process can be seen as a bijective discrete function which maps a character position into a new one (permutation); decryption takes place with the inverse mapping.

A quite smart device to practically implement such an operation was invented in ancient Greece and widely used for military communications by the Spar- tans. It is called Scytale (Greek σκυτ αλη “stick”) and consists of a wooden cylinder, around which is wound a strip of paper. On the wrapped paper is now possible to write the message in the usual way, but, after unwinding, a random sequence of characters appears instead. To decrypt the message one needs to have a stick of the same diameter, which clearly plays the role of the (symmetric) key.

2.6 Substitution Ciphers

This class of algorithms replaces a unit of plaintext with another unit of text following a defined pattern; the substitution unit can be thereby a single char- acter or an entire block of them. They are generally divided into four sub- classes:

Monoalphabetic Substitution

Each character in the plaintext is replaced by another one in the ciphertext. Here are two examples.

Caesar Cipher: This is the simplest monoalphabetic substitution cipher, in which every character is substituted by the character three places on its right in the alphabet. So, for example, an “a” is replaced by “d”, a “b” by “e” and so on. It is named after Julius Caesar who applied it to secretely communicate with his generals. The key is simply the integer by which the alphabet is shifted. A modern application can be found in the ROT13¹ (“Rotate by 13 places”) system. This particular cipher is its own inverse, also called an involution, i.e. applying it twice gives the original message back. Substitution ciphers can be regarded as weak encryption: since a given plaintext character is always substituted by the corresponding cipher character, the statistical distribution of the letters in the ciphertext is unchanged and a frequency analysis² would successfully yield the plaintext. An example of the Caesar cipher (key=3) is given in Fig. 2.2.

illustration not visible in this excerpt

Figure 2.2: Example of Caesar cipher, where the cipher alphabet is shifted by three places with respect to the plaintext alphabet.

Mixed Alphabet Cipher: It relies on a more complicated way to create the cipher alphabet. Usually one writes down a keyword, omitting letters that appear twice, followed by the remaining characters and maps one alphabet into the other. Refer to Fig. 2.3 to see how it works with the keyword “breakfast” .

illustration not visible in this excerpt

Figure 2.3: Mixed alphabet cipher at work. Notice how repeated letters in the keyword are discarded.

Polyalphabetic Substitution

This is in principle the same as the monoalphabetic case, only that two or more cipher alphabets are available for encryption. This kind of cipher has a rich history: first described by Leon Battista Alberti in 1463 in the form of discs, it became then usual practice to write it in a tableau to facilitate encryption/decryption. In particular, the so called Vigenère cipher deserves a closer look. First published in 1585 by the French diplomat Blaise de Vigenère, it was considered unbreakable until 1863, so that it earned the name of “ le chiffre indéchiffrable ”. Referring to figure 2.5, the first row of the Vigenère’s table (or square) is filled with the normal alphabet, the second row, called “cipher alphabet a” , with the alphabet self shifted by one place, and so on until the tableau is complete. A keyword defines the mapping between two alphabets in the following way: every character in the key specifies with which particular alphabet a letter in the plaintext must be encrypted. If the key is shorter than the message, it has to be repeated. Referring to the table, with “cateye” as key, encryption works like this:

illustration not visible in this excerpt

Figure 2.4: Example of Vigenère cipher. Encryption is performed with the help of a special look-up table, the Vigenère square.

Homophonic Substitution

In this kind of substitution a single plaintext character maps to more than one symbol in the cipher alphabet. We can imagine a simple numerical sub- stitution scheme where the letter “a” is mapped either to the numbers “24”, “7” or “83”, while more artistical variants can use fancy sets of symbols for encryption.

A suggestive version is the nomenclator ³, a hybrid mixture between a code- book⁴ and large homophonic substitution tables. At the beginning only names

illustration not visible in this excerpt

Figure 2.5: The so called Vigenère table to enable faster encryption/decryption. Every character in the key specifies with which particular alphabet a letter in the plaintext must be encrypted.

of prominent people were encoded, hence the cipher name, then the size ex- tended to cover common words and places. Historically, this kind of cipher was employed in the Babington Plot in 1586, that aimed at murdering Queen Elisabeth I of England, and replacing her on the throne with the Catholic Mary Queen of Scotland. Encrypted correspondence between Mary and Lord Babbington was regularly intercepted and analyzed by Elisabeth I’s Secretary of State Sir Francis Walsingham, who broke the code within a few months, with the help of his cipher school in London. All conspirators, including Queen Mary, were tried and sentenced to death.

Polygraphic Substitution

In such ciphers, blocks of letters (typically two, giving rise to digraphic ciphers) are substituted as a whole, instead of single characters. A famous digraphic method is the Playfair cipher, invented in 1854 by Charles Wheatstone and widely used by British forces during the Second Boer War and World War I and by Australians in WWII. His strength is based on the robustness against frequency analysis.

illustration not visible in this excerpt

Figure 2.6: Walsingham’s postscript to Mary’s letter to Babington, encrypted using the nomenclator cipher. It asks Babington to reveal her the names of the conspirators using the (already broken) cipher.

Rotor Machines

In the early 1920’s many electro-mechanical devices were invented to perform cryptographic tasks, thereby increasing cipher efficiency and its complexity. The basic mechanism all based on, was the rotor, a wired wheel with 26 dif- ferent positions, each of them representing one specific alphabet permutation. The number of rotors varied from three to five on more complicated machines, while output pins of one rotor are wired to the input pins of the next, thus implementing a multiple Vigenère cipher. A famous example is the ingenious German encrypting machine called ENIGMA, invented by Arthur Scherbius and Arvid Gerhard Damm, later patented by Scherbius in the United States (“Ciphering Machine” U.S. Patent 1,657,411, 24 Jan 1928).

Commercially available from the early 20’s, it was then adopted by the German Navy in 1926, by the Army in 1928 and used throughout all World War II among German forces. Though some cryptographic weaknesses, Allied could break the cipher and gain precious intelligence (codenamed ULTRA), only thanks to some accidental factors, like errors by operators, procedural flaws or captured machines and codebooks.

illustration not visible in this excerpt

Figure 2.7: A picture of the Enigma encrypting/decrypting machine. This particular military model worked with three rotors.

2.7 One-time Pad

To understand how this special stream cipher works, suppose Alice wishes to send the message “under the bridge” to Bob. To do this, she first maps the alphabet to integer numbers from 0 to 25, as illustrated below.

illustration not visible in this excerpt

In this symmetric cipher, Alice and Bob must already share a random key, which has to be as long as the message. Every letter of the ciphertext is the result of a modular addition with a letter of the key. In our case the sum is carried out mod 26, meaning that the remainder of the division by 26 is taken.

illustration not visible in this excerpt

Figure 2.8: One time pad encryption procedure. The algorithm works with mod- ular addition mod 26. Moreover, the encryption key must be chosen randomly, as long as the message and used only once.

illustration not visible in this excerpt

Figure 2.9: One time pad decryption procedure. The algorithm works with modular subtraction mod 26.

The encryption procedure is illustrated in Fig. 2.8. To decrypt the message Bob has now to carry out a modular subtraction with the same key. As expected, he gets the original message back (see Fig. 2.9).

The first algorithm of this type was realized in 1917 by Gilbert Vernam (of AT&T), and is called after him Vernam Cipher, later patented (U.S. Patent 1,310,719).

In this first implementation each character of the message was electrically combined with a character on a long punched strip of paper. Shortly thereafter, Captain Joseph Mauborgne recognized that, if the characters on the paper tape key were random, it should be much more difficult to break the cipher. In fact, the Vernam-Mauborgne cipher, commonly known as the one-time pad, takes up a special place in the field of cryptography since the late 40’s, when Claude Shannon published a paper [Sha48], in which he proved its perfect secrecy (his terminology). In his formulation this property is equivalent to say that the information about the plaintext contained in the ciphertext is zero, thus meaning that all plaintexts are equally probable. This can be understood with the help of an example. Assume one has to encrypt the message APPLEPIE with the random key JTHSZCRE; the ciphertext is the sequence JIWDDRZI. Decrypting with the right key leads of course to the original message, but if we try to decrypt with the key IXCZZTVQ, this gives us the plaintext BLUEEYES. Analogously, with the key EOLSRDLV we get the plaintext FULLMOON. Since the key has been chosen randomly, all keys

[...]

¹ The precise expression is unconditional secure, that is no restriction is made about com- putational power or scientific progress available. The proof for the one-time pad is due to Claude Shannon, who published it in the Bell Labs Technical Journal in 1949.

² Sometimes the expression Quantum Key Growing is used, emphasizing the fact that an initial shared secret key is needed for the process to work.

¹ ROT13 originated in the net.joke newsgroup in the early 1980’s to temporarily obscure the content of jokes which might be considered offensive, or the solution to simple puzzles. On UNIX-like machines the shell command ”tr A-Za-z N-ZA-Mn-za-m” implements a ROT13 encryption/decryption.

² In cryptanalysis, the study of the statistical distribution of characters or groups of char- acters in the ciphertext.

³ A king’s subordinate whose task was to announce the visiting dignitaries.

⁴ A set of coded words (codewords) and their usual meanings, like a dictionary.