Quantum Computing and Cryptography

(To Alessandro Fiori)
21/08/19

The Human Being, by its nature, needs to evolve and communicate.
Communication is one of the fundamental aspects in the growth of a human being and this is reflected in all its activities. Every human activity needs relationships that are maintained through the Language, of whatever type it is, by any means and form, regardless of the activity itself or the means of communication used. The means of communication used by man have evolved over time, becoming increasingly complex, up to the present day, allowing man to communicate over great distances and in real time, thanks to technology.

The secrecy of communication has always been a fundamental factor, necessary for the smooth execution of human activities. To ensure secrecy, Cryptography is born, that is Science that studies methods to ensure that a message can only be read by the authorized recipient. This requirement, in reality, was already felt at the time of the Ancient Romans, when Julius Caesar, to communicate the orders to his troops, used his own cipher today known as the "Caesar's Cipher".

A cipher is a tool created specifically to "encrypt" and "decrypt" messages through the use of a simple algorithm. The Caesar cipher, to give an example, can be used to encrypt a text by "moving" the letters to be encoded of three positions to the right, in this way: The word "CIAO", becomes "FLDR" (in opening a ' image to explain the "shift").

Moving backwards to three positions, the incomprehensible text "FLDR" returns to "CIAO".
Obviously this algorithm to date is very "vulnerable" and easily decipherable, with a little patience even by hand, from simple computers.

But let us pause for a second on the concept of "vulnerable algorithm". It is easy to see how, even from the example given, Cryptography played an important role in various Military Campaigns, in every Age.

Obviously two armies in war try to steal information from each other, both to predict and annihilate enemy strategies before the battle, and to discover their movements during the same. To overcome this need, cryptanalysis was born, which is the set of methods and studies to try to decipher the message without knowing the "key".

Still referring to the Caesar Cipher, the "key" used by Julius Caesar was three (together with the clockwise or counterclockwise direction), or the number of positions for the "displacement" of the letters of the alphabet.
A different key then returns a different text as a result, this means that the sender and the recipient must have the same key, one to encrypt and send the message, the other to decrypt it and read it.
From this derives one of the main problems in the use of this type of algorithm (symmetric cryptography): the distribution of the key.

Perhaps the most famous example of cryptanalysis we can refer to occurred during the Second World War, when Alan Turing created the "Colossus" machine, a very distant relative of modern computers, designed to decipher the encrypted messages with the Enigma machine (in reality the his specialization, namely Lorenz SZ40 and SZ42).

It is easy to see that through Cryptanalysis, if an Army manages to decipher the communications of the enemy, it can achieve an enormous and fundamental advantage.

In practice, in extreme cases, the enemy can no longer make any move or make a strategy in secrecy. This possibility of "breaking" the algorithms used to guarantee the secrecy of the enemy, has led to an inexorable chase between mathematicians, with those who have tried to create increasingly complex algorithms and those who have tried to decipher them. In that period, in fact, the only perfect cipher was born, that is the only cipher whose security and inviolability, the One Time Pad, was mathematically proven.

The Vernam cipher, also called "One Time Pad" (disposable notebook), is a special encryption algorithm, whose security has been mathematically proven by Claude Shannon, an American engineer considered the father of Information Theory, in 1949.

The security of the One Time Pad occurs if, and only if:
- The key is at least as long as the text to be encrypted
- The key is "really random", meaning that programs that generate numbers are not allowed. This is because the software, to generate a sequence of random numbers, use algorithms that start from "a starting point".

This starting point (which can be a number for example) means that the series of numbers generated is not really random. For an attacker, it may be possible to find the "starting point" and with the same algorithm generate again all the "random" numbers generated previously. For this reason, the number generation software is defined as "pseudo-random" or "pseudo-random".
- The key MUST be used only once.
This causes problems, as it is very difficult to exchange very long messages, and once the "pads" are finished, a key that is always really random must be regenerated, and exchanged with the recipient.

To overcome these limitations, the "Asymmetric Cryptography" was designed, using ciphers "with a public key".

This particular type of algorithm, widely used for the web and real-time communications, such as chats, provides for an individual to be associated with two keys, one strictly personal (private) and one to be shared with all (public). An interlocutor can encrypt a message with the recipient's public key, but only the recipient can read the message, decrypting it thanks to its own "private key". Since all public-key ciphers base their security on complex mathematical functions, to decrypt a message without knowing the key a computing power that is vastly superior to the machines currently on the market is required, revealing itself to be practically impossible, albeit theoretically feasible thanks to a brute-force attack (or try all the possible combinations) or using a network of computers that together try to force the algorithm through its mathematical vulnerabilities.

To date Cryptography is present in practically every moment of our lives, just think for example of websites that make available the "HTTPS" protocol, that is a system of data exchange between our browser, the program we use to navigate in Internet, and the website visited.

Another example is the end-to-end encryption (for example the WhatsApp encryption), that is an interchange system that allows only interested parties to read the content of the communication. With end-to-end encryption, not even the server of Whatsapp itself can read the contents of exchanged messages. It is however necessary to remember how the Whatsapp application and other similar ones have a closed code, therefore it is not possible to know the public about the actual operations that the application does.

It is good to remember, in fact, that even if the application is publicly recognized as reliable, it is not a mystery that some governments may ask interested companies to implement backdoors (literally "service ports" to read messages) or protocols such as the "ghost protocol" (that is, a "phantom interlocutor", in this case the government, which, as part of the conversation, could read the messages without effort).
It is easy to see that the technology race has no brakes and this may suggest that by going forward in time these ciphers can be "broken" thanks to increasingly powerful computing powers and processors, which is why we run for cover by updating the algorithms or creating them new, increasingly resistant and safe.

This "chasing each other", however, could undergo a major change, thanks to a new technology that is emerging in these years, which could really change the world of communication and cryptography, or "Quantum Computing".

The Quantum Computer is a new type of computer, which uses the principles of Quantum Mechanics to perform operations and process information. In order to work, in fact, the Quantum Computer does not use the ordinary bit, but the "qubit" or "quantum bit". The qubit differs from the "classic" bit in that it is not a simple "0" or "1", but rather encodes the information based on the state of the atom being observed.

As an example, the ordinary bit can be represented by the tossing of the coin in the classic "head or cross".
The result of the launch represents "0" or "1", going to encode the bits.

Now imagine taking the same coin, and making it rotate on itself, and imagine that the coin never stops. The coin will have two states, which can be represented as binary information "0" or "1". The same currency can, however, be found in "superposition of states", ie the states "0" and "1" can be combined together to give life to a certain number of new states.
This combination, that is the principle of superposition of the states, makes it possible to broaden the coding of information, allowing exponentially to expand the possibilities of calculation.

The superposition principle is the first postulate of quantum mechanics. It states that two or more "quantum states" can be added (superimposed), generating a valid quantum state. Furthermore, each state is the sum (overlap) of several quantum states.

A "quantum state" or "quantum state" is the mathematical representation of a physical system, or a "portion of the universe" or a phenomenon, the object of study.

Based on the principles of Quantum Mechanics, very complex systems have been built, called "Quantum Computers".

The first realization of this system dates back to 2001, when IBM creates the first quantum computer at 7 qubit.

In 2007, the company "D-Wave Systems" realizes the first quantum processor at 16 qubit.

Always D-Wave Systems, realizes in the 2011 the "D-Wave One", that is a computer with 128 qubit, the first quantum processor to be marketed.

In the 2013 the "D-Wave Two" is produced, processor to 512 qubit.

Between the 2016 and the 2019, IBM provides the so-called "Quantum Experience", which is a platform in the Cloud, which provides quantum processors and networks.

The two platforms (D-Wave and IBM) are very different from each other.

In detail, the D-Wave Two is made up of superconducting circuits.

Each superconductor represents a qubit.

The system is maintained at a temperature of -271 degrees Celsius.

When the temperature rises, the electrons can rotate on themselves, with equal probability, both clockwise and counterclockwise, thus generating the superposition of states, necessary for the functioning of the quantum computer.

IBM Quantum Experience, on the other hand, presents a connected infrastructure in Cloud which allows you to program up to 5 qubit and run your own quantum software on a quantum processor, or on a simulator connected in the Cloud. The Quantum Experience allows the creation of quantum software up to 5 "code" lines, one per qubit.

It is easy to see how a "quantum race" started, but why this?
The main reason for this race to the "quantum bit", is to be found in the field of war, or the "conquest" of information of the enemy. Anyone with an interest in war tries to "break" the enemy's cryptographic systems and the enormous computing power of the quantum computer seems to promise miracles. Like any technology, however, each tool can be used by both attackers and defenders.

But let's go back for a moment to the Perfect Cipher, the One Time Pad.
This cipher is not used in a common environment, since the distribution of the key is a problem that cannot be easily solved in a normal computer network. Therefore, the possibility of using the One Time Pad in a way never seen before has been studied through the same principles of quantum mechanics.

Two researchers and university professors (Geraldo A. Barbosa - University of Southern California and Jeroen van de Graaf - Universite de ´Montreal) in the 2015 presented a key creation and distribution system for the One Time Pad, exploiting the "noise" present in a fiber optic cable to the passage of the photon.

The noise is an interference, a slight alteration, compared to the original signal.
The noise is perfectly random so it can be used to generate an unlimited number of keys and also to distribute them easily, solving the problems of the One Time Pad so far presented.

The so-called "Quantum Key Distribution" or QKD was also created for the use of the One Time Pad. Through the Quantum Key Distribution, it is possible, through the principles of quantum mechanics, to generate keys and distribute them in a secure manner, this because any measurement on a quantum system alters their state (uncertainty principle), consequently the interlocutors would immediately discover that someone is trying to pick up the distributed key (and obviously, since the measurement is altered, the "captured" key would not be the correct one).

As for military uses, the scenarios are constantly evolving.
If in 2016 China has launched the first satellite, the Micius, for quantum communications into orbit, the possibilities of these new systems are being studied all over the world.

In detail the Micius satellite (name deriving from an ancient Chinese philosopher) is the first experimental satellite forming part of a much larger project called "QUESS" (Quantum Experiments at Space Scale), an international research project in the field of quantum physics . The objectives of the project are to bring within the 2020 an encrypted quantum network between Asia and Europe, and within the 2030 to extend this network globally.

The QUESS project aims to create a network that is not only "cryptographically" secure, but also impossible to intercept, and this is possible thanks to another principle of quantum physics not present in classical physics, called "entanglement".

Quantum entanglement is a phenomenon that occurs in particular conditions in which a quantum "state" cannot be studied or described individually, but only as a "superposition of states".
From this it follows that the measurement of a state also determines the value of others simultaneously.
A group of Glasgow researchers succeeded in photographing the entanglement between two photons (image).

Thanks to this special phenomenon, the QUESS project succeeded in executing the first photon transporter thanks to the Micius satellite. Currently the QUESS project is under development, and despite the limitations (the network cannot be used with the presence of sunlight), in the 2016 the first video call was made on the quantum network. Therefore, obtaining supremacy in this area could have a huge advantage over competitors.

Given the computing power of quantum computers and the actual risk that ciphers currently in use cannot withstand, cryptographers are studying algorithms, specially created to withstand these extremely powerful computers. From this study, the term "post-quantum cryptography" is born.

There are, however, algorithms that can already withstand a quantum computer attack if used with a sufficiently long key.

One of these is the AES, or the Advanced Encryption Standard, which is used by the American Government to protect the documents classified as "top secret", usable by anyone and included in numerous Frameworks, or packages, for developers, for create software.

The various companies, such as Microsoft and IBM, are also releasing quantum computer simulators to the general public, in order to learn how to program on this type of machine.

Microsoft has also released a special language, called "Q #" (Q-sharp) and exercises, called "Katas", to learn how to use this new technology.

And are you ready for the future? ... because, deep down, it's already here!

To learn more:

https://www.dwavesys.com/home
https://www.research.ibm.com/ibm-q/
https://docs.microsoft.com/en-us/quantum/language/?view=qsharp-preview
http://www.difesaonline.it/evidenza/cyber/difendersi-dai-computer-quanti...
http://www.difesaonline.it/evidenza/eventi/enigma-la-macchina-cifrante-c...ò-the-event-of-2agm
https://arxiv.org/abs/1406.1543
https://en.wikipedia.org/wiki/Q_Sharp
https://cloudblogs.microsoft.com/quantum/2018/07/23/learn-at-your-own-pa...
http://www.difesaonline.it/recensioni/andrew-hodges-alan-turing-storia-d...