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 his 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 more and more 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 running of human activities. To guarantee secrecy, Cryptography was born, that is the Science that studies methods to ensure that a message can only be read by the authorized recipient. This need, in fact, was already felt in the times of the Ancient Romans, when Julius Caesar, to communicate orders to his troops, used his own cipher now known as the "Cifrario di Cesare".

A cipher is a tool created specifically to "encrypt" and "decrypt" messages through the use of a simple algorithm. The Cifrario di Cesare, just to give an example, can be used to encrypt a text by "moving" the letters to be encrypted by three positions to the right, in this way: The word "HELLO", becomes "FLDR" (opening a image to explain the "displacement").

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 at war try to steal information from each other, both to be able to predict and annihilate the enemy strategies before the battle, and to discover their movements during the same. To meet this need, "cryptanalysis" was born, that is the set of methods and studies to try to decipher the message without knowing its "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 moves or prepare a secret strategy. This possibility of "breaking" the algorithms used to guarantee the secrecy of the enemy, has led to an inexorable run-up among 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 has been mathematically proven, the One Time Pad.

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", that is, 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 re-generate all the previously generated "random" numbers. For this reason, 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 algorithms, widely used for the web and real-time communications, such as chats, requires that an individual be associated with two keys, one strictly personal (private) and one to be shared with everyone (public). An interlocutor can encrypt a message with the recipient's public key, but only the recipient will be able to read the message, decrypting it thanks to his own “private key”. Since all public key ciphers base their security on complex mathematical functions, to decrypt a message without knowing the key, an enormously higher computing power is required than the machines currently on the market, proving to be practically impossible, although theoretically feasible thanks to a brute-force attack (i.e. try all 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 encryption of WhatsApp), that is an interchange system that allows only the interested interlocutors to read the content of the communication. Whatsapp itself can read the content of the exchanged messages. However, it is important to remember that the Whatsapp application and other similar ones are closed code, consequently it is not given to the public to know 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 race for technologies has no brakes and this may suggest that as time goes on these ciphers can be "broken" thanks to increasingly powerful computing powers and processors, that's why we run for cover by updating algorithms or creating new ones, more and more 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 exploits the principles of Quantum Mechanics to be able to carry out operations and process information. In fact, in order to function, 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, it 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 spinning it around 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 be found, however, in "superposition of states", ie the states "0" and "1" can combine with each other 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 Cloud infrastructure which allows you to program up to 5 qubits 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 lines of "code", one per qubit.

It is easy to see how a "quantum rush" has begun, but why this?
The main reason for this race to the "quantum bit", is to be found in the war, or the "conquest" of the enemy's information. Anyone with a military interest 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, any 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 commonly used, as 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 was studied using 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 safely, this because any measurement on a quantum system alters its state (uncertainty principle), consequently the interlocutors would immediately discover that someone is trying to capture 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 to be 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 an encrypted quantum network between Asia and Europe by 2020, and by 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 was able to carry out the first teleportation of photons thanks to the Micius satellite. The QUESS project is currently under development, and despite the limitations (the network cannot be used with the presence of sunlight), the first video call on the quantum network was made in 2016. Therefore, obtaining supremacy in this area could have a huge advantage over competitors.

Given the computing power of quantum computers and the real risk that the ciphers currently in use cannot resist, cryptographers are studying algorithms, specially created to withstand these extremely powerful computers. From this study, the term "post-quantum cryptography" was 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.

Are you ready for the future? ... because, after all, it is 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...