Is the Universe a quantum computer?

jakub mielczarekLeave a comment

Every piece of information we deal with daily can be distilled into a sequence of just two distinct symbols, mirroring the elegant code of dots and dashes in the Morse alphabet. This unveils a profound parallel between the structure of information and that of matter—both possess a foundational granularity. The “elementary particle of information” is aptly named a “bit.”

The universally acknowledged symbols for these fundamental bits are 0 and 1, encapsulating the binary essence of information. In particular, we can represent any natural number as a finite binary sequence. Consequently, the inception year of the Jagiellonian University, etched indelibly into memory, materializes as 010101010100—a rhythmic amalgamation of five alternating 01s and 00s.

Interestingly, the concept of encoding not only natural numbers but also fractional quantities in a similar manner was a revelation that predates modern times. Ancient Egypt stands as a testament to this foresight. However, the purview of encoding extends beyond numerical constructs; it embraces the entire spectrum of human expression, encompassing alphabets, special characters, intricate images, and an array of information’s myriad forms.

Information, by its very nature, seldom remains stagnant but is subject to constant metamorphosis, which, by means of the representation of bits as electrical impulses, is conducted by computers. Computers, in turn, are nothing more than certain physical systems.

Following this line of thought, we can come to the conclusion that, basically, every piece of reality is a computer of some kind, processing or at least storing a certain type of information. But is this really the case? Does every physical process correspond to an information processing that a computer could handle? This contemplation unfurls into a grander query: is the totality of our reality computable?

An attempt to confront these ostensibly philosophical questions was made in the 1930s by a British mathematician, cryptologist, and decidedly versatile genius Alan Turing. Analyzing the problem of computability of various problems, he introduced an abstract model of a computing machine—an idea subsequently christened the Turing machine in his honor. The Turing machine stands as a conceptualization of an “imaginary mathematician” meticulously carrying out the step-by-step processing of information, which is represented as a binary string adorning an infinitely extensive tape.

Though it might appear astonishing, every operation executed by contemporary computers can be replicated using a construct as rudimentary as a Turing machine that can actually be built, for example, from LEGO bricks.

Turing machine built with LEGO bricks. Source.

While this particular construct does not offer an optimal method for information processing, contemplations surrounding it have yielded profound insight into the boundaries of computability. Notably, building upon Turing’s ideas, American mathematician Alonzo Church articulated a conjecture that, in one of its incarnations, can be framed thus: Any form of computation—pertaining to the manipulation of information—executed by a physical system (i.e., one that obeys the laws of physics) can be emulated by a Turing machine.

The Church-Turing hypothesis, as it is dubbed, holds profound significance in the context of simulating physical processes. Processes that can be represented through operations executable on a Turing machine are bestowed with the epithet of being “complete in the Turing sense.” The question of whether the entirety of physical phenomena can be encapsulated within such completeness, and by extension, whether the entire Universe is encompassed by this Turing-style completeness, stands as an unresolved enigma.

To date, no counterexample has emerged to challenge the Church-Turing hypothesis, yet the certainty eludes us. It is essential to emphasize that the completeness of the Universe in this framework implies that certain problems—known to be incomplete in the Turing sense—forever reside beyond the realm of solution.

The pursuit of an answer to the profound question regarding the completeness of the Universe within the framework of Turing’s conception is further compounded by the intricate adjustments necessary when entering the atomic realm. Here, the familiar encoding of information as binary sequences faces a fundamental rethinking. In the microcosmic domain governed by the intricate laws of quantum mechanics, classical information theory gracefully evolves into the realm known as quantum information theory.

Within this novel landscape, the very building block of information transforms from the conventional bit to the quantum variant—the qubit. Visualizing a qubit as a spherical canvas akin to Earth, where the poles host the familiar classical bit values of 0 and 1, we gain a glimpse into its essence. However, a qubit can “live” not only at the poles but at any other point, of which there are infinitely many on the sphere (which we call the Bloch sphere). On this sphere, each point represents a unique quantum superposition of the classical values 0 and 1, painting a vivid portrait of quantum possibility.

However, this narrative of quantum complexity does not halt there. The states of more intricate quantum systems are not confined to fixed bit sequences like 011. Instead, their depiction transcends such simplicity and embraces the entwined concept of superposition. Imagine these states as harmonious amalgamations of every feasible sequence of bits for a given length. In practical terms, this encompasses permutations like 000, 001, 010, 100, 011, 101, 110, and 111. The symphony of quantum states expands to include a diverse ensemble of possibilities. For a quantum system described by n qubits, its quantum state proliferates into a superposition of 2n binary strings, each boasting a length of n bits.

Geometric representation of bit and cubit. Source.

Quantum information processing is, to some extent, possible with classical computers and, therefore, with a Turing machine. Nonetheless, this endeavor is, in broad terms, an arduous endeavor. This is primarily due to the fact that for a quantum system comprised of n qubits, the undertaking necessitates the manipulation of 2n probability amplitudes. Each of these amplitudes corresponds to one of the feasible n-bit strings. Notably, every one of these amplitudes corresponds to a so-called complex number (composed of two real numbers), which can be represented by a sequence of bits. The length of this sequence burgeons in proportion to the precision sought in the calculation.

Hence, for even a modestly sized quantum system of, say, a hundred qubits, the challenge becomes monumental. To be precise, operations on 2100 = 1267650600228229401496703205376 probability amplitudes are requisite. This prodigious magnitude exceeds the capabilities of existing classical computers and even defies the bounds of conceivable future classical computing innovations.

Hence, attempting to simulate the intricate realm of quantum reality using a classical computational device is profoundly inefficient. A solution to this conundrum emerges through the extension of the Turing machine into the quantum domain, culminating in the model of a universal quantum computer.

The idea of such quantum computational frameworks traces back to the early 1980s, thanks to the pioneering work of physicists Paul Benioff and David Deutsch. Almost simultaneously, a luminary in the world of physics—Richard Feynman—proposed that any discrete quantum system can be simulated in an exact way (can be “imitated”) by means of operations performed on a quantum computer. Following this train of thought, if the Universe can be distilled into a finite arrangement of qubits, it would resonate with the completeness in the sense of the quantum Turing machine. In essence, the Universe could then serve as an example of a universal quantum computer, with the intricate dance of qubits orchestrating the fabric of existence.

Does the Universe, in reality, embody an immense quantum computer engaged in ceaseless quantum information processing? At this moment, this remains an enigma that eludes our grasp. However, our current comprehension of fundamental physics—at the very limit of our knowledge and imaginative capacity—does not preclude this intriguing possibility.

This boundary of our cognitive horizon is demarcated by the Planck scale, a realm where our understanding of physics encounters its utmost frontier. In this uncharted territory, a diverse array of quantum theories of gravity emerge as contenders, each offering a distinct portrayal of the quantum intricacies underpinning space and time.

Among these contenders, one theory stands prominently—the loop quantum gravity. Introduced in the early 1990s by Abhay Ashtekar, Carlo Rovelli, and Lee Smolin, this theory envisages a granular structure of space at the Planck scale—an architecture fundamentally discrete, resembling the concept of atoms in a quantum realm. This theory nurtures the possibility of simulating this quantum fabric, aligning with the essence of Feynman’s visionary ideas.

For over a decade, I have been pondering the feasibility of distilling loop quantum gravity into a system governed by qubits—a crucial step that could pave the way for the realm of quantum simulations. Yet, it was only in 2017 that I mustered the determination to propel this idea from the realm of theory into the realm of reality. This surge of initiative was catalyzed by a significant turning point: the debut of the first quantum computers, wielding the power of a handful to a dozen qubits.

In the course of the research we are currently conducting as part of the Quantum Cosmos Lab team operating at the Institute of Theoretical Physics at the Jagiellonian University, we have managed not only to theoretically demonstrate the possibility of running quantum simulations of models of the Universe described by loop quantum gravity but also to perform the first quantum simulations of this type.

A model of discrete quantum space made of two “atoms of space” (or equivalently, a dipole approximation of the Universe) and the corresponding quantum algorithm that can be executed on a quantum Turing machine. Source

The simulations we are conducting, constrained by the nascent capabilities of current quantum computers, remain in their rudimentary stages, employing at most a dozen “raw” qubits. Despite these limitations, these initial attempts enable us to sculpt configurations that paint a portrait of a homogeneous quantum universe model.

With the development of quantum computing engineering, we will be able to add more and more embellishments to this microscopic universe. Forecasts beckon a promising trajectory: in the coming five years, we anticipate reaching a level of simulation performance that surpasses the reach of contemporary classical supercomputers. The use of a classical Turing machine will still remain theoretically possible, but its extreme inefficiency renders it unfeasible in practice. Thus, while the development of quantum simulations ushers in an era of uncharted potential, it is essential to recognize that the resulting quantum emulation of the cosmos remains, at this juncture, a nascent quantum embryo—a reflection of the universe we inhabit, yet still in a very early stage of its evolution.

Looking thousands of years into an uncertain future, we find ourselves unable to definitively dismiss the prospect that comprehensive simulations of sizable portions of the Universe might eventually materialize. Yet, it remains an immutable truth that no simulation, no matter how advanced, can ever encapsulate the entirety of the Universe that envelopes us. Unless, of course, in the hypothetical limiting case when it would be used to simulate itself as a whole. Yet, this transcendental eventuality strays from the realm of simulation into the territory of reality. This theoretical juncture transforms the simulation into what we call “reality”— being complete in the Turing sense.

Bibliography

[1] J. Mielczarek, Prelude to Simulations of Loop Quantum Gravity on Adiabatic Quantum Computers,’ Front. Astron. Space Sci. 8 (2021), 95
[2] J. Mielczarek, Spin Foam Vertex Amplitudes on Quantum Computer – Preliminary Results, Universe 5 (2019) no.8, 179.
[3] G. Czelusta, J. Mielczarek, Quantum simulations of a qubit of space, Phys. Rev. D 103 (2021) no.4, 046001.

© Jakub Mielczarek

First post-quantum cryptography standards

jakub mielczarekLeave a comment

About a year ago, on July 5, 2022, the U.S. National Institute of Standards and Technology (NIST) announced the first results of a procedure initiated in 2016 to select post-quantum cryptographic standards. One key exchange algorithm and three electronic signature algorithms were selected. Based on these algorithms, new cryptographic standards will be developed to provide resistance to possible future attacks carried out with quantum computers. The post-quantum cryptographic algorithms selected by NIST will gradually replace the current asymmetric cryptography algorithms, which are the basis for the security of communications on the Internet, in the coming years.

Why do we need post-quantum cryptography?

The quantum computers available today are far from being capable of effectively cryptanalyzing the encryption algorithms in use today. Nevertheless, such a threat, although pushed back in time, theoretically exists and should be taken into account in risk analysis. This problem mainly concerns public key cryptography algorithms (asymmetric cryptography), in which encryption and decryption are carried out using two different keys: private and public. Using quantum cryptanalysis, it becomes computationally efficient to recover the private key based on knowledge of the public key. Examples of public key cryptography include the RSA (Rivest-Shamir-Adleman) algorithm, Elliptic Curve Cryptography (ECC) algorithms, and the Diffie-Hellman (DH) key exchange protocol (also based on elliptic curves, the so-called Elliptic Curve Diffie-Hellman (ECDH)).

One of the main uses of these algorithms is the remote exchange of a secret key, which is then used to encrypt a message (plaintext), already using symmetric algorithms. With symmetric ciphers, the same key is used to encrypt and decrypt the message.

The described procedure is widely used in the secure exchange of information, including that which we can characterize as particularly sensitive. Moreover, some of this type of information may remain sensitive for a long period of time, counting in tens of years. Hence, there is a legitimate concern that this information (in encrypted form) may be stored for a period of even several decades, after which it will be successfully read using quantum cryptanalysis – breaking asymmetric ciphers and gaining access to the key encrypting the relevant information. It is worth mentioning that even the property of so-called forward secrecy, commonly used today in encrypting Internet traffic, will not help here.

In light of the potential crisis, such a situation could cause, the cryptography community has taken steps to develop a set of cryptographic solutions resistant to known attacks using quantum computers. It is this branch of cryptography that we refer to as post-quantum cryptography (PQC) [1].

While, in light of the current relatively slow rate of growth in the computational resources of quantum computers and the many technical hurdles associated with scaling quantum processors, the widespread implementation of post-quantum cryptography may give the impression of being somewhat premature, one should keep in mind the complexity and length of time involved in the development, testing, standardization and widespread utilization of post-quantum algorithms. Quantum physicist Michele Mosca put this problem within the framework of the following inequality [2]: x+y>z, where x is the time we require to ensure information security, y is the time it takes to implement new solutions to ensure security against quantum attacks, z is the time it takes to develop a computer capable of breaking current public key cryptography ciphers. If the above inequality is satisfied, then we must consider the situation problematic.

Of course, there is a lot of uncertainty in determining the value of the z parameter. In this article, I focus my attention on post-quantum cryptography, and this is not the place for an in-depth analysis of the physical and technical aspects behind predicting the value of the z parameter. A simplified analysis presented in my earlier article titled Technologie kwantowe a cyberbezpieczeństwo [3] (in Polish), indicates that the value of z may currently be around 25 years. Realistically, we can assume that widespread implementation of post-quantum standards will take about 10 years. Applying these values to Mosca’s inequality leads to the expression: x > 15 years. This means that exchanging information on the Internet that we would not want to share publicly for more than 15 years will no longer be secure at the end of the post-quantum cryptography adaptation period. Considering more optimistic scenarios for the development of quantum technologies, this value will decrease. However, the limitation already shown here is a serious warning in light of the exchange of medical, business, or government communications.

NIST competitions

In January 1977, the U.S. National Bureau of Standards, which was renamed NIST in 1988, published the first widely used standard for symmetric cryptography – the Digital Encryption Standard (DES). Despite the selection of the algorithm’s designer through a competitive process, which became IBM, the standardization process was not transparent, and the results quickly stirred up controversy in the cryptology community. This happened, in particular, due to the relatively short 56-bit key. Its length, as we know it today, was influenced by the US National Security Agency (NSA), which was involved in the process of developing the DES standard [4]. As a result, already twenty years after the introduction of the DES cipher, its breaking by brute force did not pose any major problems. DES thus became useless (except for its use in 3DES or DES-X algorithms, among others), and NIST began the procedure for selecting a block cipher, which is the new standard for symmetric cryptography. This time, however, to avoid previous controversies (also related to the origin of the so-called S-blocks, which are the building blocks of the DES algorithm), it was decided to have a fully open and transparent competition procedure. This is how the Rijndael algorithm emerged, which took the form of a new standard – Advanced Encryption Standard (AES), adopted in 2001 and still in force today. Moreover, its 256-bit key version is classified as a post-quantum algorithm.

Over the past two decades, NIST has developed dozens of standards and recommendations for cryptographic algorithms, including those for hash functions, electronic signatures, and key generators. NIST’s most recent cryptography standardization initiatives include lightweight cryptography standards dedicated to devices with limited computing resources (microcontrollers, IoT solutions, etc.) and the standardization of post-quantum cryptography discussed here [5].

The procedure for selecting post-quantum cryptography standards was initiated in December 2016. The competition announced by NIST concerned the selection of a post-quantum public key cryptography algorithm, Key Encapsulation Mechanism (KEM), and electronic signature. Five levels of security for post-quantum algorithms were specified, corresponding to security due to brute force attacks on block ciphers with key lengths of 128, 192, and 256 bits, and due to collision attacks on hash functions with hashes of 256 and 384 bits. The interested reader can find further detailed information on the requirements for candidates in [6].

It is worth noting, is that the new post-quantum cryptography standards move away from the DH key exchange protocol (KEX), which involves two communicating parties. Thus, a post-quantum version of the Diffie-Hellman protocol is not envisioned. Instead, the aforementioned key encapsulation mechanism (KEM), in which one party selects a secret key and encrypts it with a post-quantum asymmetric algorithm using a public key, is adopted as an alternative. The encrypted key is then retrieved by the other party using the private key. Such a solution was found to be simpler and easier to implement and analyze [7].

It is also worth adding that the NIST competition does not include new hash function standards. Those currently in use (e.g., SHA-3) are considered resistant to quantum attacks. As a result, they are also used in post-quantum algorithms for electronic signatures based on hash functions (Hash-based signatures).

Post-quantum winners

From the eighty-two proposals initially sent, four algorithms were selected after the third round was completed. In addition, four more were qualified for the next fourth round [8].

CRYSTALS-Kyber [9] has emerged as the public key cryptography algorithm. This algorithm also provides a key encapsulation mechanism (KEM). CRYSTALS-Kyber belongs to the class of lattice-based cryptography [10], in which operations are performed on multidimensional lattices, similar to crystal lattices. The lattices provide an opportunity to define a number of problems that are considered computationally difficult. One of them is the Learning With Errors (LWE) problem, which in 2005, was proposed by Israeli computer theorist Oded Regev. He was awarded the prestigious Gödel Prize in 2018 for his discovery. The CRYSTALS-Kyber algorithm is based on a variant of the LWE problem in which the lattice defining the problem has a certain imposed structure, the so-called Module-LWE. In justifying the choice of this algorithm, NIST emphasized, among other things, its speed and small key size, being of the order of a kilobyte.

An artistic take on the Markle tree (used to create public keys in electronic signature algorithms based on hash functions) and lattices. Source.

The following have emerged as electronic signature algorithms: CRYSTALS-Dilithium [9], FALCON [11] and SPHINCS+ [12]. CRYSTALS-Dilithium, was designed by the same group as CRYSTALS-Kyber and is considered the main algorithm for post-quantum electronic signatures. The CRYSTALS-Dilithium algorithm was based on a modification of the LWR problem, the so-called Learning With Rounding (LWR). In this problem, instead of adding Gaussian noise (as in LWE), a rounding function is introduced, making it more difficult to recover the secret message. Moreover, like CRYSTALS-Kyber, CRYSTALS-Kyber uses an imposed lattice structure, which ultimately leads to the Module-LWR problem.

The future FALCON standard is based on the well-studied NTRU algorithm, which in its first version, was introduced in 1996 [13]. The algorithm is considered the protoplast of lattice ciphers. It is fast and easy to implement. While initially, its operation can be understood without referring to lattices – namely, it is based on operations performed on so-called quotient rings of polynomials – the essence of its security is already directly derived from the properties of lattices. Despite the relatively small size of the key, the weakness of the FALCON cipher is the lack of a constant-time implementation, which is resistant to extracting the private key from the timing of the algorithm. Another trouble is the required fast double-precision arithmetic, making the implementation of this cipher difficult [14].

Unlike previous cases, the SPHINCS+ cipher is not based on lattice mathematics. It was selected by NIST as a backup algorithm in case time unveiled previously unknown vulnerabilities of lattice ciphers. And I write about the fact that this may indeed happen later in this text. For now, it should still be added that the SPHINCS+ algorithm is based on well-known and cryptographically strong hash functions. The idea of using hash functions for signatures was proposed back in 1975 by American computer scientist Leslie Lamport. In this approach, a private key is consumed to create public keys by creating a hash function from part of its bits. Consequently, practical applications of electronic signature algorithms based on hash functions require the use of large keys, the size of which can reach tens of kilobytes. This is the main shortcoming of this approach. Besides, these algorithms are both secure and easy to implement, as they are based on well-tested and widely implemented solutions.

Controversy before the finish line

On April 4 last year, 3 months before NIST announced its results, cryptologists from the prestigious Center of Encryption and Information Security (MATZOV), which is Israel’s main cryptology facility, shook up the crypto world, or at least the post-quantum part of it, by releasing their report, the result of an audit of the main candidates for the post-quantum cryptography standard. The report is entitled “Report on the Security of LWE: Improved Dual Lattice Attack,” and focuses attention on approaches based on LWE and LWR [15]. The best-known cryptanalytic techniques for these types of ciphers are based on so-called primal lattice attacks and dual lattice attacks. Neither of these attacks has been considered a viable threat to date. In particular, the latter approach seemed impractical. However, the MATZOV report showed that there is room for improvement in the second type of attack, which clearly weakens the security of the CRYSTALS-Kyber, SABER and CRYSTALS-Dilithium algorithms. Specifically, the new cryptanalytic technique was shown to weaken the security of these algorithms slightly below the thresholds specified in NIST’s competition requirements. The reader interested in the discussion of the post-quantum cryptology community on the MATZOV report is referred to reference [16].

The results of the MATZOV report ultimately did not prevent the selection of the CRYSTALS-Kyber and CRYSTALS-Dilithium algorithms. However, they may have influenced the rejection of the SABER algorithm from the competition. It is worth clarifying at this point that we have no proof of the safety of the CRYSTALS-Kyber and CRYSTALS-Dilithium algorithms. The statements regarding their safety are related to the so-called Shortest Vector Problem (SVP) on lattices [17]. As proven, SVP is the so-called NP-difficult problem, which makes it impossible to solve it efficiently (in polynomial time). The LWE and LWR problems can be reduced to an approximate SVR problem. However, there is no proof that these are NP-hard problems. Thus, from the security side, the justification for using these problems in post-quantum cryptography is based on the lack of knowledge of algorithms that would allow efficient solutions to these problems. However, it cannot be guaranteed that such algorithms will not be discovered in the future.

The fourth round

The process of selecting post-quantum cryptographic standards by NIST did not end with the selection of the four algorithms discussed above. The game continues, and four more algorithms have qualified for the fourth round of evaluation, which still have a chance to join the ranks of NIST’s post-quantum standards. We are talking about the ciphers BIKE [18], Classic McEliece [19], HQC [20], and SIKE [21].

Let’s begin by presenting the second on the list, the Classic McEliece cipher, which belongs to the class of asymmetric ciphers based on correction codes. Such codes, through some redundant information, allow the correction of errors created during the transmission or storage of information. In 1978, Robert McEliece showed that correction codes could also be used to implement, introduced a few years earlier, asymmetric cryptography. Despite more than forty years of attempts and in-depth knowledge of the algorithm, launching a successful attack on it has not been possible. The weakness of the algorithm is the large key size – even on the order of a megabyte. The BIKE (Bit Flipping Key Encapsulation) algorithm is, like Classic McEliece, also based on correction codes. In this case, the so-called QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check) code is used. Also, the HQC (Hamming Quasi-Cyclic) algorithm is based on correction codes.

The last of the ciphers, SIKE (Supersinguar Isogeny Key Encapsulation), uses a completely different approach than the previous three. Namely, it involves morphisms (certain relations) between elliptic curves to build an asymmetric cryptosystem. Despite being computationally demanding, this approach was recently considered secure and characterized by an extremely short key. This forecasted the usage of the SIKE algorithm in areas of special-purpose applications. To the great surprise of the cryptology community, on July 30, 2022, two cryptologists from the University of Leuven published a recipe for an effective attack on the SIKE algorithm [22,23]. Exploiting a previously unknown vulnerability, they managed, using a personal computer, to recover the private key. This algorithm, despite the hopes attached to it and the implementations already tested, will certainly not become a post-quantum standard. However, it is still possible that the vulnerability that enabled the attack will be eliminated in further incarnations of this algorithm.

What about symmetric cryptography?

Modern symmetric cryptography algorithms are considered invulnerable to quantum attacks. Their level of security is essentially determined by brute force attack, the feasibility of which is determined by the size of the key space. In the case of the AES algorithm with a 256-bit key, this space has a dimension of N=2256, which is comparable to the number of atoms in the observed Universe.

The best-known quantum strategy for power attacks is to use Grover’s algorithm. This algorithm makes it possible to search a quantum database containing N elements, not in an average of N/2 steps, as is classically the case, but in an average of N1/2 steps. For the AES-256 algorithm, this means a reduction in security from 256 to 128, a value that is still considered post-quantum secure. In addition, it should be noted that already from the theoretical side, the very implementation of the Grover search algorithm for a given symmetric algorithm poses a major challenge. Namely, one has to build a circuit of the so-called quantum oracle (oracle) for a given symmetric algorithm. This in itself is a complex task, requiring making a representation of a given symmetric algorithm in the form of a binary function and its further implementation as a quantum circuit. This poses a huge challenge already at the algorithmic level.

The algorithm proposed by Lov K. Grover in 1996 was considered by many to be the only quantum threat to symmetric algorithms. However, the outlook on cryptanalysis of symmetric algorithms gradually started to change since 2012, when Kuwakado and Morii have shown [24], that it is possible to achieve the so-called exponential acceleration for cryptanalysis of the symmetric Even-Mansour cipher. This is due to the clever use of Simon’s quantum algorithm, which is a simpler version of Shor’s algorithm. In turn, Shor’s algorithm poses a fundamental threat to asymmetric algorithms.

The use of Simon’s algorithm makes it possible to efficiently break the simple Even-Mansour algorithm as well as some other cryptosystems [25]. Although the Even-Mansour algorithm is too simple to find practical use, variants of it can be found in lightweight cryptography ciphers. In particular, these include the Chaskey and Elephant algorithms, which is one of the finalists in the NIST process for standardizing lightweight cryptography.

The caveat, however, is that the quantum oracle for the cipher Evena-Mansour must be implementable (the so-called Q2 case). It has recently been proven that if the quantum oracle is not available (the Q1 case), which is the typical situation in practice, the Even-Mansour cipher is post-quantum secure [26].

It should be noted that the quantum cryptanalysis of symmetric ciphers is becoming an increasingly active field of research. The issue of security of symmetric ciphers should, therefore, not be underestimated.

What’s next?

It could take another year to prepare ready-made standards based on the selected algorithms, NIST declares. In the meantime, the agency encourages learning about and testing the picked algorithms. NIST also suggests refraining from practical implementations at this stage since the final form of the standards may differ from the current specification of the algorithms. The time is undoubtedly also worth using to broaden awareness related to the implementation of post-quantum cryptography and to prepare for the activities that the announcement of the new standards will entail in the coming years. This applies, in particular, to IT departments of companies and institutions. Attention to the issue of new standards should immediately turn to those operating in the areas of network infrastructure, data storage, and cyber security. One should also be aware that in the next few years, every network administrator will have to become familiar with the new post-quantum versions of the Transport Layer Security (TLS) protocol and the post-quantum cipher suites they offer.

We are waiting, moreover, for the identification of possible additional standards that can play a reserve and special purpose role. Given the recent reports cited, the SIKE algorithm is most likely already out of the game.

The near future should also bring the initiation of a procedure for selecting a post-quantum standard for homomorphic encryption. Encryption of this type is gaining more and more interest due to the rapid development of cloud services. Namely, homomorphic cryptography allows performing arbitrary operations on encrypted data without having direct access to it.

References

[1] D. Bernstein, T. Lange,  Post-quantum cryptography, Nature 549, 188–194 (2017).

[2] M. Mosca, Cybersecurity in an era with quantum computers: will we be ready ?,  IEEE Security & Privacy, vol. 16, no. 5, pp. 38-41, (2018).

[3] J. Mielczarek,  Technologie kwantowe a cyberbezpieczeństwo, CyberDefence24,  (2019).

[4] T. R. Johnson, American Cryptology during the Cold War, 1945-1989 (The Complete Declassified Official Four-Volume History of the NSA), Center for Cryptologic History, Washington DC (1995) – Book III, Rozdział 19, Public Cryptography.

[5] https://www.nist.gov/cryptography

[6] https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

[7] https://blog.cloudflare.com/towards-post-quantum-cryptography-in-tls/

[8] https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

[9] https://pq-crystals.org/

[10] https://itwiz.pl/czym-jest-szyfrowanie-kratowe-jak-zabezpiecza-czasach-quantum-computing/

[11] https://falcon-sign.info/

[12] https://sphincs.org/

[13] J. Hoffstein, J. Pipher, J. H. Silverman,  NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (eds) Algorithmic Number Theory. ANTS 1998. Lecture Notes in Computer Science, vol 1423. Springer, Berlin, Heidelberg (1998).  

[14] https://blog.cloudflare.com/nist-post-quantum-surprise/

[15] https://zenodo.org/record/6412487#.Yu2VuexBx4I

[16] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/v5odfcpfBwAJ?pli=1

[17] http://www.deltami.edu.pl/temat/matematyka/kryptologia/2017/11/25/Kryptologia_postkwantowa/

[18] https://bikesuite.org/

[19] https://classic.mceliece.org/

[20] http://pqc-hqc.org/

[21] https://sike.org/

[22] W. Castryck and T. Decru, An efficient key recovery attack on SIDH (preliminary version) (2022)

[23] https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/

[24] H. Kuwakado, and M. Morii, Security on the quantum-type Even-Mansour cipher, 2012 International Symposium on Information Theory and its Applications, Honolulu, HI, USA, 2012, pp. 312-316.

[25] M. Kaplan, G. Leurent., A. Leverrier, M. Naya-Plasencia,  Breaking Symmetric Cryptosystems Using Quantum Period Finding. In: Robshaw, M., Katz, J. (eds) Advances in Cryptology – CRYPTO 2016. CRYPTO 2016. Lecture Notes in Computer Science, vol 9815. Springer, Berlin, Heidelberg (2016).

[26] G. Alagic, C. Bai, J. Katz, and C. Majenz, Post-Quantum Security of the Even-Mansour Cipher,  In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13277. Springer, Cham.

© Jakub Mielczarek

Pierwsze standardy kryptografii postkwantowej

jakub mielczarek1 Comment

5 lipca bieżącego roku, amerykański Narodowy Instytut Norm i Techniki (National Institute of Standards and Technology – NIST) ogłosił pierwsze wyniki zainicjowanej w 2016 roku procedury wyłonienia postkwantowych standardów kryptograficznych. Wybrano jeden algorytm wymiany klucza oraz trzy algorytmy podpisu elektronicznego. W oparciu o te algorytmy, zostaną opracowane nowe standardy kryptograficzne, zapewniające odporność na możliwe przyszłe ataki przeprowadzane z udziałem komputerów kwantowych. Wyłonione przez NIST postkwantowe algorytmy kryptograficzne, będą w najbliższych latach stopniowo zastępować obecnie stosowane algorytmy kryptografii asymetrycznej, stanowiące podstawę bezpieczeństwa komunikacji w internecie. 

Po co nam kryptografia postkwantowa?

Dostępnym obecnie komputerom kwantowym daleko jeszcze do osiągnięcia zdolności umożliwiających skuteczną kryptoanalizę stosowanych współcześnie algorytmów szyfrujących. Niemniej jednak, zagrożenie takie, choć odsunięte w czasie, teoretycznie istnieje i należy je brać pod uwagę w analizie ryzyka. Problem ten dotyczy głównie algorytmów kryptografii klucza publicznego (kryptografii asymetrycznej), w których szyfrowanie i deszyfrowanie odbywa się za pomocą dwóch różnych kluczy: prywatnego i publicznego. Wykorzystując kryptoanalizę kwantową, możliwe staje się efektywne obliczeniowo odzyskiwanie klucza prywatnego w oparciu o znajomość klucza publicznego. Do przykładów kryptografii klucza publicznego należą algorytm RSA (Rivest-Shamir-Adleman), algorytmy kryptografii krzywych eliptycznych (Elliptic Curve Cryptography – ECC) oraz protokół uzgadaniania klucza Diffiego-Hellmana (DH) (także w wersji opartej na krzywych eliptycznych, czyli tzw. Elliptic Curve Diffie-Hellman – ECDH). 

Jednym z głównych zastosowań tych algorytmów jest zdalna wymiana sekretnego klucza, służącego następnie do zaszyfrowania wiadomości (tekstu jawnego), już za pomocą algorytmów symetrycznych. W przypadku szyfrów symetrycznych, ten sam klucz jest wykorzystywany do szyfrowania i odszyfrowania wiadomości. 

Opisana procedura znajduje szerokie zastosowanie w bezpiecznej wymianie informacji, w tym tych które możemy scharakteryzować jako szczególnie wrażliwe. Co więcej, część tego typu informacji może pozostać wrażliwa przez długi okres czasu, liczony w dziesiątkach lat. Stąd też istnieje uzasadniona obawa, że informacje te (w postaci zaszyfrowanej) mogą zostać przechowywane przez okres nawet kilkudziesięciu lat, po czym zostaną skutecznie odczytane z zastosowaniem kryptoanalizy kwantowej –  łamiąc szyfry asymetryczne i uzyskując dostęp do klucza szyfrującego właściwą informację. Warto dodać, że nie pomoże tu nawet własność tzw. utajnienia z wyprzedzeniem (ang. forward secrecy), stosowana dziś powszechnie w szyfrowaniu ruchu w internecie. 

W świetle potencjalnego kryzysu jaki taka sytuacja mogłaby wywołać, społeczność kryptograficzna podjęła działania mające na celu opracowanie zbioru rozwiązań kryptograficznych odpornych na znane ataki z wykorzystaniem komputerów kwantowych. Właśnie tę gałąź kryptografii określamy mianem kryptografii postkawntowej (ang. post-quantum cryptography – PQC) [1].

O ile, w świetle obecnego stosunkowo wolnego tempa wzrostu zasobów  obliczeniowych komputerów kwantowych i wielu przeszkód technicznych związanych ze skalowaniem procesorów kwantowych, szerokie wprowadzanie kryptografii postkwantowej może stwarzać wrażenie działań nieco przedwczesnych, należy mieć na uwadze złożoność i długotrwałość procesu opracowania, testowania, standaryzacji i szerokiej implementacji algorytmów postkwantowych. Fizyk kwantowy Michele Mosca, ujął ten problem w ramach następującej nierówności [2]: x+y>z,  gdzie x to wymagany przez nas czas zapewnienia bezpieczeństwa informacji, y to czas wdrożenia nowych rozwiązań zapewniających bezpieczeństwo przed atakami kwantowymi, z to czas potrzebny na powstanie komputera zdolnego do łamania obecnych szyfrów kryptografii klucza publicznego. Jeśli powyższa nierówność zachodzi, to musimy uznać sytuację za problematyczną.  

Oczywiście, dużą niepewnością obarczone jest wyznaczenie wartości parametru z. W niniejszym artykule, koncentruję uwagę na kryptografii postkwantowej i nie jest to miejsce na wnikliwą analizą aspektów fizycznych i technicznych stojących za prognozowaniem wartości parametru z. Uproszczona analiza, przedstawiona w moim wcześniejszym artykule pt. “Technologie kwantowe a cyberbezpieczeństwo” [3], wskazuje, że wartość z może wynosić obecnie około 25 lat. Realistycznie, możemy przyjąć, że szerokie wdrożenie standardów postkwantowych zajmie około 10 lat. Zastosowanie tych wartości do nierówności Mosca, prowadzi do wyrażenia: x > 15 lat. Oznacza, to że wymiana w internecie informacji, którymi nie chcielibyśmy się publicznie dzielić przez okres większy niż 15 lat, przestanie być bezpieczna pod koniec okresu adaptacji kryptografii postkwantowej. Rozważając bardziej optymistyczne scenariusze rozwoju technologii kwantowych, wartość ta ulegnie obniżeniu. Jednakże, już przytoczone tu ograniczenie, stanowi poważne ostrzeżenie w świetle wymiany informacji medycznych, biznesowych czy też komunikacji rządowej. 

Konkursy NIST

W styczniu 1977 roku, amerykańskie Narodowe Biuro Standardów (ang. National Bureau of Standards),  które w 1988 roku zostało przemianowane w NIST, opublikowało pierwszy powszechnie stosowany standard kryptografii symetrycznej – Digital Encryption Standard (DES). Pomimo wyłonienia projektanta algorytmu na drodze konkursowej, którym został IBM, proces standaryzacji nie przebiegł w sposób transparentny i jego wyniki szybko wzbudziły kontrowersje w środowisku kryptologicznym. Stało się to, w szczególności, za sprawą stosunkowo krótkiego, 56-bitowego, klucza. Na jego długość, jak dzisiaj wiemy, wpływ miała amerykańska National Security Agency (NSA), zaangażowana w przebieg procesu opracowania standardu DES [4].  W konsekwencji, już po dwudziestu latach od wprowadzenia szyfru DES, jego łamanie metodą siłową (ang. brute force) nie nastręczało większych problemów. DES stał się tym samym bezużyteczny (poza jego wykorzystaniem m.in. w algorytmach 3DES czy też DES-X) a NIST rozpoczął procedurę wyboru szyfru blokowego, stanowiącego nowy standard kryptografii symetrycznej. Tym razem jednak, w celu uniknięcia wcześniejszych kontrowersji (związanych również z pochodzeniem tak zwanych S-bloków, stanowiących element budulcowy algorytmu DES), zdecydowano się na w pełni otwartą i transparentną procedurę konkursową. Tak też wyłoniono algorytm Rijndael, który przybrał formę nowego standardu – Advanced Encryption Standard (AES), przyjętego w 2001 roku i obowiązującego do dzisiaj. Co więcej, w wersji z kluczem 256 bitowym jest on klasyfikowany jako algorytm postkwantowy. 

W przeciągu ostatnich dwudziestu lat NIST opracował dziesiątki standardów i rekomendacji dotyczących algorytmów kryptograficznych, m.in. dotyczących funkcji skrótu (funkcji haszujących), podpisów elektronicznych, czy też generatorów kluczy. Do najnowszych inicjatyw NIST w zakresie standaryzacji kryptografii należą standardy lekkiej kryptografii (ang. lightweight cryptography), dedykowane dla urządzeń o ograniczonych zasobach obliczeniowych (mikrokontrolery, rozwiązania IoT, itp.), oraz dyskutowana tutaj standaryzacja kryptografii postkwantowej [5]. 

Procedura wyłonienia standardów kryptografii postkwantowej została zainicjowana w grudniu 2016 roku.  Ogłoszony przez NIST konkurs dotyczył wyboru  postkwantowego algorytm kryptografii klucza publicznego, mechanizmu enkapsulacji klucza (ang. Key Encapsulation Mechanism – KEM) oraz podpisu elektronicznego. Określono, pięć poziomów bezpieczeństwa dla algorytmów postkwantowych, odpowiadających bezpieczeństwu ze względu na ataki siłowe na szyfr blokowy z kluczem o długości 128, 192 i 256 bitów oraz ze względu na ataki kolizyjne na funkcje skrótu ze skrótem 256 i 384 bitowym. Dalsze, szczegółowe informacje dotyczące wymogów stawianych przed kandydatami zainteresowany Czytelnik znajdzie w dokumencie [6].  

Warte podkreślenia, jest, że nowe standardy kryptografii postkwantowej odchodzą od protokołu uzgadniania klucza DH, w którym uczestniczą dwie komunikujące się strony. Nie przewiduje się zatem postkwantowej wersji protokołu Diffiego-Hellmana. Jako alternatywę przyjęto natomiast wspomnianą enkapsulację klucza, w której jedna ze stron wybiera sekretny klucz i dokonuje jego zaszyfrowania postkwantowym algorytmem asymetrycznym, wykorzystując klucz publiczny. Zaszyfrowany klucz jest następnie odzyskiwany przez drugą stronę, za pomocą klucza prywatnego. Rozwiązanie takie uznano za prostsze i łatwiejsze do implementacji i analizy [7]. 

Warto również podkreślić, że konkurs NIST nie obejmuje nowych standardów funkcji skrótu. Te obecnie stosowane (np. SHA-3) uważane są za odporne na ataki kwantowe. Dzięki temu, znajdują one także zastosowanie w postkwantowych algorytmach podpisu elektronicznego, opartych na funkcjach skrótu (ang. Hash-based signatures).

Postkwantowi zwycięzcy

Z przesłanych wyjściowo osiemdziesięciu dwóch propozycji, po zakończonej trzeciej rundzie, wyłoniono cztery algorytmy. Ponadto, cztery kolejne, zostały zakwalifikowane do, następnej, czwartej rundy [8].  

Jako algorytm kryptografii klucza publicznego wyłoniony został CRYSTALS-Kyber [9].  Algorytm ten zapewnia również mechanizm enkapsulacji klucza (KEM). CRYSTALS-Kyber należy do klasy szyfrów kratowych (ang. lattice-based cryptography) [10], w których operacje wykonywane są na wielowymiarowych kratach, podobnych do sieci krystalicznych. Kraty dają możliwość zdefiniowania szeregu problemów, które uważane są za trudne obliczeniowo. Jednym z nich jest problem nauczania z błędami (ang. Learning With Errors – LWE), który w 2005 roku, zaproponował izraelski informatyk-teoretyk Oded Regev. Za swoje odkrycie został On w 2018 roku uhonorowany prestiżową Nagrodą Gödla. Algorytm CRYSTALS-Kyber bazuje na wariancie problemu LWE, w którym krata definiująca problem posiada pewną narzuconą strukturę, tzw. Module-LWE. W uzasadnieniu wyboru tego algorytmu, NIST podkreślił m.in. jego szybkość oraz nieduży rozmiar kluczy, rzędu kilobajta. 

Artystyczne ujęcie drzewa Markle’a (stosowanego do tworzenia kluczy publicznych w algorytmach podpisu elektronicznego opartych na funkcjach skrótu) oraz krat. Źródło

Jako algorytmy podpisu elektronicznego zostały wyłonione: CRYSTALS-Dilithium [9], FALCON [11] oraz SPHINCS+ [12]. CRYSTALS-Dilithium, został zaprojektowany przez tę samą grupę co CRYSTALS-Kyber i uznano go za główny algorytm postkwantowego podpisu elektronicznego. Algorytm CRYSTALS-Dilithium oparty został na modyfikacji problemu LWR, tak zwanej nauce z zaokrągleniem (ang. Learning With Rounding – LWR). W problemie tym, zamiast dodawania szumu gaussowskiego (jak w LWE), wprowadza się funkcję zaokrąglającą, utrudniającą odzyskanie sekretnej wiadomości. Co więcej, podobnie jak CRYSTALS-Kyber, tak i CRYSTALS-Kyber, wykorzystuje narzuconą strukturę kraty, co ostatecznie prowadzi do problemu Module-LWR. 

Przyszły standard FALCON opiera się na dobrze zbadanym algorytmie NTRU, który w swojej pierwszej wersji, został wprowadzony w 1996 roku [13]. Algorytm jest uznawany za protoplastę szyfrów kratowych. Jest on szybki oraz łatwy w implementacji. O ile wyjściowo, jego działanie można zrozumieć nie odwołując się do krat – bazuje on mianowicie na operacjach wykonywanych na tzw. pierścieniach ilorazowych wielomianów – to już istota jego bezpieczeństwa bezpośrednio wynika z własności krat.  Pomimo stosunkowo małych rozmiarów klucza, słabą stroną szyfru FALCON jest brak realizacji stałoczasowej, odpornej na ekstrahowanie klucza prywatnego z pomiaru czasu działania algorytmu. Kolejnym kłopotem jest wymagana szybka arytmetyka o podwójnej precyzji, utrudniająca implementację tego szyfru [14]. 

W odróżnieniu od wcześniejszych przypadków, szyfr SPHINCS+ nie jest oparty na matematyce krat. Został on wyłoniony przez NIST jako algorytm rezerwowy, na wypadek gdyby czas odsłonił nieznane dotychczas podatności szyfrów kratowych. A o tym, że faktycznie może się tak zdarzyć, piszę w dalszej części tego tekstu. Póki co, należy jeszcze dodać, że algorytm SPHINCS+ opiera się na dobrze poznanych i silnych kryptograficznie funkcjach skrótu. Idea wykorzystania funkcji skrótu do składania podpisu, została zaproponowane jeszcze w 1975 roku przez amerykańskiego informatyka Leslie Lamporta. W podejściu tym, klucz prywatny jest zużywany do tworzenia kluczy publicznych, poprzez utworzenie funkcji skrótu z części jego bitów. W konsekwencji, praktyczne zastosowania algorytmów podpisu elektronicznego opartych na funkcjach skrótu wymagają zastosowania dużych kluczy, których rozmiary mogą sięgać kilkudziesięciu kilobajtów. Jest to główny mankament tego podejścia. Poza tym, algorytmy te są zarówno bezpieczne, jak i łatwe w implementacji, gdyż opierają się na dobrze przetestowanych i szeroko wdrożonych rozwiązaniach. 

Kontrowersje na finiszu 

4 kwietnia bieżącego roku, na 3 miesiące przed ogłoszeniem wyników przez NIST, kryptolodzy z prestiżowego Center of Encryption and Information Security (MATZOV), będącego głównym zapleczem kryptologicznym Izraela, zatrzęśli światem kryptologicznym, a przynajmniej jego postkwantową częścią,  publikując swój raport, będący wynikiem przeprowadzonego audytu głównych kandydatów do standardu kryptografii postkwantowej. Raport zatytułowany jest “Report on the Security of LWE: Improved Dual Lattice Attack” i skupia uwagę na podejściach opartych na LWE oraz LWR [15]. Najlepiej znane techniki kryptoanalityczne dla tego typu szyfrów opierają się na tak zwanych primal lattice attacks oraz dual lattice attacks. Żaden z tych ataków nie uważano jednach dotychczas za realne zagrożenie. W szczególności, drugie z tych podejść wydawało się niepraktyczne. W raporcie MATZOVa wykazno jednak, że istnieje możliwość ulepszenia drugiego typu ataku, co wyraźnie osłabia bezpieczeństwo algorytmów CRYSTALS-Kyber, SABER oraz CRYSTALS-Dilithium. W szczególności, wykazano, że nowa technika kryptoanalityczna osłabia bezpieczeństwo tych algorytmów nieznacznie poniżej progów określonych w wymaganiach konkursowych NIST. Czytelnika zainteresowanego dyskusją środowiska kryptologów postkwantowych na temat raportu MATZOVa odsyłam do referencji [16]. 

Wyniki raportu MATZOVa ostatecznie nie przeszkodziły w wyborze algorytmów CRYSTALS-Kyber i CRYSTALS-Dilithium. Mogły mieć jednak wpływ na odrzucenie z rywalizacji algorytmu SABER.  Warto w tym miejscu wyjaśnić, że nie dysponujemy dowodem bezpieczeństwa algorytmów CRYSTALS-Kyber i  CRYSTALS-Dilithium. Stwierdzenia dotyczące ich bezpieczeństwa wiążą się z tzw. problemem najkrótszego wektora (ang. Shortest Vector Problem – SVP) na kratach [17]. Jak dowiedziono, SVP jest tzw. problemem NP-trudnym, co uniemożliwia jego efektywne rozwiązywania (w czasie wielomianowym). Problemy LWE i LWR można zredukować do przybliżonego problemu SVR. Nie istnieje jednakże dowód tego, że są to problemy NP-trudne. Od strony bezpieczeństwa, uzasadnienie zastosowania tych problemów w kryptografii postkwantowej opiera się więc na braku znajomości algorytmów które pozwalałyby na efektywne rozwiązywanie tych problemów.  Nie można jednak zagwarantować tego, że takie algorytmy nie zostaną odkryte w przyszłości. 

Czwarta runda 

Proces wyboru postkwantowych standardów kryptograficznych przez NIST, nie zakończył się wraz z wyborem omówionych powyżej czterech algorytmów. Gra toczy się dalej i do czwartej rundy ewaluacyjnej zakwalifikowano cztery kolejne algorytmy, które wciąż mają szansę dołączyć do grona postkantowych standardów NIST. Mowa to szyfrach:  BIKE [18], Classic McEliece [19], HQC [20], oraz SIKE [21]. 

Zacznijmy od przedstawienia drugiego z listy, szyfru Classic McEliece, należącego do klasy szyfrów asymetrycznych opartych na kodach korekcyjnych. Kody takie, poprzez pewną nadmiarową informację, pozwalają na korekcję błędów powstałych w trakcie transmisji lub magazynowania informacji. W 1978 roku Robert McEliece pokazał, że kody korekcyjne mogą być również użyte do realizacji, wprowadzonej kilka lat wcześniej, kryptografii asymetrycznej. Pomimo, ponad czterdziestu lat prób i dogłębnego poznania algorytmu, nie udało się przeprowadzić na niego skutecznego ataku. Słabą stroną algorytmu jest duży rozmiar klucza – nawet rzędu megabajta. Algorytm BIKE (Bit Flipping Key Encapsulation) jest, podobnie jak Classic McEliece, również oparty na kodach korekcyjnych. W tym przypadku wykorzystywany jest tzw. kod QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check). Także algorytm HQC (Hamming Quasi-Cyclic) opiera swoje działanie na kodach korekcyjnych.  

Ostatni z szyfrów, SIKE (Supersinguar Isogeny Key Encapsulation), wykorzystuje zupełnie inne podejście niż trzy poprzednie. A mianowicie, angażuje on morfizmy (pewne powiązania) pomiędzy krzywymi eliptycznymi do budowy kryptosystemu asymetrycznego. Podejście to, pomimo, że jest wymagające obliczeniowo, uważne było do niedawna za bezpieczne i charakteryzujące się wyjątkowo krótkim kluczem. Prognozowało to wykorzystaniem algorytmu SIKE, w obszarach zastosowań specjalnego przeznaczenia. Ku wielkiemu zaskoczeniu społeczności kryptologicznej, 30 lipca tego roku dwójka kryptologów z Uniwersytetu w Leuven, opublikowała receptę skutecznego ataku na algorytm SIKE [22,23]. Wykorzystując nieznaną wcześniej podatność, udało się, wykorzystując komputer osobisty, odzyskać klucz prywatny. Algorytm ten, pomimo wiązanych z nim nadziejami i już testowanych implementacji, nie stanie się z pewnością standardem postkwantowym. Wciąż możliwe jest jednak, że podatność która umożliwiła atak zostanie wyeliminowana w dalszych wcieleniach tego algorytmu.    

Co z kryptografią symetryczną?

Współczesne algorytmy kryptografii symetrycznej są uważane za niepodatne na ataki kwantowe. Ich poziom bezpieczeństwa jest zasadniczo określany ze względu na atak siłowy, którego możliwość realizacji determinuje rozmiar przestrzeni klucza. W przypadku algorytmu AES z kluczem 256 bitowym, przestrzeń ta ma wymiar N=2256, co jest porównywalne z liczbą atomów w obserwowanym Wszechświecie.

Najlepszą znaną strategią kwantową w przypadku ataków siłowych jest zastosowanie algorytmu Grovera. Algorytm ten umożliwia przeszukanie kwantowej bazy danych, zawierającej N elementów, nie jak to ma miejsce klasycznie w średnio N/2 krokach, a w średnio N1/2 krokach. Dla algorytmu AES-256 oznacza to redukcję bezpieczeństwa z poziomu 256 do 128, co jest wciąż wartością uznawaną za bezpieczną postkwantowo. Ponadto, należy podkreślić, że już od strony teoretycznej, samo zaimplementowanie algorytmu przeszukiwania Grovera dla danego algorytmu symetrycznego stanowi duże wyzwanie. Trzeba mianowicie zbudować obwód tzw. kwantowej wyroczni (ang. oracle) dla danego algorytmu symetrycznego. To samo w sobie złożone zadanie, wymagające dokonania reprezentacji danego algorytmy symetrycznego w postaci funkcji binarnej i jej dalszej implementacji jako obwodu kwantowego. Stanowi to ogromne wyzwanie już na poziomie algorytmicznym. 

Zaproponowany przez Lova K. Grovera w 1996 algorytm był przez wielu uważany za jedyne kwantowe zagrożenie dla algorytmów symetrycznych. Spojrzenie na kryptoanalizę algorytmów symetrycznych uległo jednak zmianie w 2016 roku, wraz opublikowaniem publikacji pt. “Breaking Symmetric Cryptosystems Using Quantum Period Finding” [24]. Pokazano, mianowicie, że możliwe jest osiągnięcie tzw. przyśpieszenia wykładniczego dla kryptoanalizy pewnych algorytmów symetrycznych. Ma to miejsce za sprawą sprytnego zastosowania kwantowego algorytmu Simona, który jest prostszą wersją algorytmu Shora. Algorytm Shora stanowi zaś podstawowe zagrożenie dla algorytmów asymetrycznych. 

Zastosowanie algorytmu Simona umożliwia, w szczególności, efektywną kryptoanalizę prostego szyfru blokowego, jakim jest algorytm Even-Mansoura. Choć algorytm Even-Mansoura jest zbyt prosty by mógł znaleźć praktyczne zastosowanie, jego warianty odnaleźć można w szyfrach lekkiej kryptografii.  W szczególności, należą do nich algorytmy Chaskey i Elephant, będący jednym z finalistów procesu NIST standaryzacji kryptografii lekkiej. 

Należy zauważyć, że kwantowa kryptoanaliza szyfrów symetrczynych staje się coraz bardziej aktywnym polem badań. Kwestii bezpieczeństwa szyfrów symetrycznych nie należy zatem bagatelizować. 

Co dalej?

Jak deklaruje NIST, przygotowanie gotowych standardów na podstawie wybranych algorytmów może zająć kolejne dwa lata. W międzyczasie, agencja zachęca do poznawania i testowania wyłonionych algorytmów. NIST sugeruje również powstrzymanie się z praktycznymi implementacjami na tym etapie, gdyż finalna forma standardów może odbiegać od obecnej specyfikacji algorytmów. Czas ten warto niewątpliwie wykorzystać także na poszerzenie świadomości związanej z wdrażaniem kryptografii postkwantowej i przygotowanie się do działań jakie ogłoszenie nowych standardów pociągnie za sobą w nadchodzących latach. Dotyczy to, w szczególności, działów IT firm i instytucji. Uwagę na kwestię nowych standardów powinny niezwłowcznie zwrócić podmioty działające w obszarach infrastruktury sieciowej, magazynowania danych  oraz cyberbezpieczeństwa. Należy mieć także świadomość tego, że w przeciągu najbliższych kilku lat, każdy administrator sieciowy będzie musiał zaznajomić się z nowymi postkwantowymi wersjami protokołu TLS (Transport Layer Security) oraz oferowanymi przez nie postkwantowymi zestawami szyfrów (ang. cipher suites).

Czekamy, ponadto, na wyłonienie ewentualnych dodatkowych standardów, które będą mogły pełnić rolę rezerwową i specjalnego przeznaczenia. Z uwagi na przywołane niedawne doniesienia, z gry najprawdopodobniej wypadł już algorytm SIKE. 

Nieodległy czas powinien przynieść również zainicjowanie procedury wyboru postkwantowego standardu szyfrowania homomorficznego (ang. homomorphic encryption). Szyfrowania tego typu zyskuje coraz większe zainteresowanie z uwagi na dynamiczny rozwój usług chmurowych. Kryptografia homomorficzna pozwala mianowicie na wykonywanie dowolnych operacji na zaszyfrowanych danych, nie mając do nich bezpośredniego dostępu.  

Referencje 

[1] D. Bernstein, T. Lange,  Post-quantum cryptography, Nature 549, 188–194 (2017).

[2] M. Mosca, Cybersecurity in an era with quantum computers: will we be ready ?,  IEEE Security & Privacy, vol. 16, no. 5, pp. 38-41, (2018).

[3] J. Mielczarek,  Technologie kwantowe a cyberbezpieczeństwo, CyberDefence24,  (2019).

[4] T. R. Johnson, American Cryptology during the Cold War, 1945-1989 (The Complete Declassified Official Four-Volume History of the NSA), Center for Cryptologic History, Washington DC (1995) – Book III, Rozdział 19, Public Cryptography.

[5] https://www.nist.gov/cryptography

[6] https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

[7] https://blog.cloudflare.com/towards-post-quantum-cryptography-in-tls/

[8] https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

[9] https://pq-crystals.org/

[10] https://itwiz.pl/czym-jest-szyfrowanie-kratowe-jak-zabezpiecza-czasach-quantum-computing/

[11] https://falcon-sign.info/

[12] https://sphincs.org/

[13] J. Hoffstein, J. Pipher, J. H. Silverman,  NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (eds) Algorithmic Number Theory. ANTS 1998. Lecture Notes in Computer Science, vol 1423. Springer, Berlin, Heidelberg (1998).  

[14] https://blog.cloudflare.com/nist-post-quantum-surprise/

[15] https://zenodo.org/record/6412487#.Yu2VuexBx4I

[16] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/v5odfcpfBwAJ?pli=1

[17] http://www.deltami.edu.pl/temat/matematyka/kryptologia/2017/11/25/Kryptologia_postkwantowa/

[18] https://bikesuite.org/

[19] https://classic.mceliece.org/

[20] http://pqc-hqc.org/

[21] https://sike.org/

[22] W. Castryck and T. Decru, An efficient key recovery attack on SIDH (preliminary version) (2022)

[23] https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/

[24] M. Kaplan., G. Leurent., A. Leverrier, M. Naya-Plasencia,  Breaking Symmetric Cryptosystems Using Quantum Period Finding. In: Robshaw, M., Katz, J. (eds) Advances in Cryptology – CRYPTO 2016. CRYPTO 2016. Lecture Notes in Computer Science, vol 9815. Springer, Berlin, Heidelberg (2016).

© Jakub Mielczarek

Artykuł został opublikowany na portalu Nauka UJ.

Kosmiczny Szyfr

jakub mielczarekLeave a comment

Każdy z nas intuicyjnie wie, że szyfr służy ukrywaniu wiadomości. Jednak większość z nas nie uświadamia sobie, że z szyframi mamy do czynienia cały czas. Bo to dzięki nim, ukrytym nierzadko głęboko w czeluściach internetu, możemy bezpiecznie poruszać się w sieci. To szyfrom zawdzięczamy dostęp do bankowości elektronicznej, możliwość płacenia kartami chipowymi, jak również zachowanie pewnej dozy prywatności podczas rozmów telefonicznych. Dzięki nim odchodzimy też od ręcznych podpisów na rzecz elektronicznych. Przykłady można mnożyć. Jedno jest pewne – swoją ciężką pracę wykonują, pozostając w cieniu.

Czym właściwie jest szyfr? Jeśli popatrzymy na rzecz z czysto matematycznego punktu widzenia, dojdziemy do wniosku, że szyfrowanie jest odwracalnym przekształceniem – funkcją, której argumentem jest tak zwany tekst jawny. Co więcej, operacja ta jest zaprojektowana tak, żeby otrzymany na jej wyjściu szyfrogram przestawał mieć dla nas jakikolwiek sens i sprawiał wrażenie, jak gdyby początkowa informacja całkiem się rozpłynęła.

Informacja oczywiście nie znika, lecz zostaje ukryta w pozornie przypadkowej kompozycji symboli szyfrogramu. Szyfr, czy też inaczej algorytm szyfrujący, jest przepisem, który mówi nam, co należy zrobić, żeby wiadomość ukryła swoje znaczenie. Niezbędnym elementem jest klucz, który umożliwia wielokrotne korzystanie z tego samego szyfru. W przypadku tak zwanych szyfrów symetrycznych klucz pozwala nam zarówno zaszyfrować wiadomość, jak i ją odszyfrować – wykonując algorytm szyfrujący “wstecz”.

Tak na szyfry patrzą lubujący się w abstrakcji matematycy. Fizycy, do których sam się zaliczam, mają odwrotnie – próbują dopasować każdy element matematyki do otaczającego nas świata. Nie inaczej jest w tym przypadku. Zatem okiem fizyka, szyfr to przykład deterministycznej dynamiki chaotycznej.

Prostym przykładem deterministycznego układu chaotycznego jest wahadło podwójne. Źródło

Dynamika chaotyczna to szczególny typ ewolucji układów fizycznych, w którym bardzo szybko zaciera się informacja o ich stanie początkowym. Innymi słowy, ewolucja układu chaotycznego jest bardzo czuła na warunki początkowe – zachowanie to jest powszechnie znane pod nazwą efektu motyla. Stąd też różnica chociażby jednej litery w szyfrowanej wiadomości może prowadzić do kompletnie innego szyfrogramu. Determinizm gwarantuje nam natomiast, że cały proces jest odwracalny i zawsze możemy odtworzyć stan wyjściowy, nawet kiedy wydaje się to zupełnie nieprawdopodobne, bo powrót ten może być bardzo trudny w realizacji. Bo jak sprawić, by rozbite fragmenty filiżanki wskoczyły z powrotem na stół? Jest to jednak teoretycznie dopuszczalne i można próbować przeprowadzić symulację takiego procesu na komputerze.

Jak odzyskać informację z szyfru?

Algorytmy szyfrujące możemy zatem postrzegać jako pewne szczególne deterministyczne układy chaotyczne, które ewoluują zadany stan początkowych (tekst jawny) do stanu końcowego (szyfrogramu). O ile szyfrogram wydaje się być stanem zupełnie nieuporządkowanym, to poprzez zastosowanie na nim operacji odwrotnej (ewolucji wstecz w czasie), możemy odzyskać skrywaną informację. Oczywiście trzeba w tym celu wiedzieć, ile czasu upłynęło pomiędzy początkiem a końcem ewolucji.

Trudno przypuszczać, że stworzone przez ludzi algorytmy szyfrujące odpowiadają układom chaotycznym spotykanym naturalnie w przyrodzie. Aktywność ludzka jest oczywiście również jej częścią, więc wszytko co tworzymy, wliczając algorytmy szyfrujące, z konieczności staje się jej fragmentem. Nie określamy jednakże naszych tworów mianem naturalnych. Nie to jednak będzie nas tu interesować. Ważne, że dynamika chaotyczna jest szeroko rozpowszechnionym rodzajem zachowania w otaczającym nas świecie. Występuje praktycznie wszędzie tam, gdzie mamy do czynienia z dużą ilością cząstek, związanych poprzez nieliniowe oddziaływania. Idąc dalej tym tokiem rozumowania, można dojść do wniosku, że przeważająca część ewolucji wszechświata przybiera formę dynamiki chaotycznej.

Szyfry w naturze

Istnieją oczywiście pewne regularne trendy, takie jak ruchy planet, gwiazd i ewolucja kosmologiczna, gdzie zachowania chaotyczne nie pełnią obecnie głównej roli. Ale i w tych przypadkach nie zawsze tak musiało być. Na podstawie słynnej hipotezy Belinskiego-Khalatnikowa-Lifszyca (BKL), oczekujemy, że ewolucja wczesnego wszechświata była wręcz w nieunikniony sposób chaotyczna. Przypuszczenie to znalazło poparcie w licznych rozważaniach teoretycznych i symulacjach komputerowych. Także na skali atomowej wszechświat ogarnięty jest totalnym chaosem, a jego złożoną ewolucję można postrzegać jako morze atomowego chaosu z pewnymi regularnościami, falującymi na jego powierzchni.

Chaotyczna ewolucja wszechświata w modelu Belinskiego-Khalatnikowa-Lifszyca (BKL). Źródło

Możemy zatem stwierdzić, że nawet szklanka wody mogłaby pełnić funkcję algorytmu szyfrującego. Oczywiście – o ile tylko potrafilibyśmy określić precyzyjnie położenie cząsteczek wody, moglibyśmy za ich pomocą stworzyć maszynę szyfrującą. Wykracza to jednak poza nasze obecne umiejętności, dlatego w praktyce posługujemy się sztucznie wykreowanymi układami chaotycznymi, istniejącymi jedynie w pamięci naszych komputerów. Jednakże pewne układy chaotyczne występujące naturalnie w przyrodzie wykorzystuje się do projektowania algorytmów szyfrujących. Przykładem jest układ Lorenza, który pojawił się w latach sześćdziesiątych ubiegłego wieku jako opis zjawiska konwekcji termicznej w atmosferze. W modelu tym obserwujemy tak zwany dziwny atraktor, którego chaotyczne własności mają zastosowanie w konstrukcji szyfrów symetrycznych.

Skoro jednak szklanka wody albo zjawiska atmosferyczne mogą posłużyć nam jako szyfrator, to czemu nie moglibyśmy za takowy uznać całego znanego nam wszechświata? Ewolucja kosmosu jest w znacznym stopniu zdeterminowana przez zjawiska chaotyczne, związane z procesami nieliniowymi. Na dużych skalach przykładem jest formowanie się, w toku ewolucji wszechświata, zwartych układów grawitacyjnych, takich jak galaktyki i gwiazdy. Jednak na wczesnym etapie jego ewolucji, zgodnie z przewidywaniem hipotezy BKL, chaotyczne zachowanie dotyczyło największych skal. Oprócz tego na małych dystansach mamy całą mnogość nieliniowych zjawisk atomowych.

Wszechświat jako Kosmiczny Szyfrator

Nieliniowości decydują również o sile współczesnych szyfrów. Tak więc nie popełnimy nadużycia, jeśli do celów naszej popularnonaukowej dyskusji potraktujemy wszechświat jako Kosmiczny Szyfrator, który stale ukrywa przed nami informację o swoim stanie początkowym. Chcąc zaś poznać informację, jaką przed nami skrył, musimy przyjąć rolę kryptoanalityków – specjalistów w łamaniu szyfrów.

Pracę, która jest do wykonania, możemy podzielić na dwie kategorie. Pierwsza z nich to poznanie mechanizmu działania Kosmicznego Szyfratora. Druga to znalezienie sekretnego klucza. Potrzebujemy więc najpierw zrozumieć elementarne kroki, jakie wykonuje gigantyczna maszyna szyfrująca, w której żyjemy. Tym zajmuje się fizyka teoretyczna, opisująca mechanikę wszechświata na coraz to głębszym poziomie, sięgając aż do tak zwanej skali Plancka, gdzie pojęcie czasoprzestrzeni wydaje się tracić sens. W przypadku zwykłych szyfrów mechanizm działania algorytmu szyfrującego jest zazwyczaj znany – zgodnie z Zasadą Kerckhoffsa, która mówi, że szyfr powinien pozostawać bezpieczny nawet w przypadku, kiedy znane są jego wszystkie szczegóły. W konsekwencji działanie szyfru jest często upubliczniane po to, by kryptoanalitycy mogli bez ograniczeń wyszukiwać jego potencjale słabości. To, co pozostaje niejawne to sekretny klucz. Planu działania Kosmicznego Szyfratora niestety nikt nam nie udostępnił, więc musimy sami cierpliwie dokonać jego inżynierii odwrotnej.

Nawet bez dogłębnej znajomości działania szyfru, można podjąć próbę odczytania szyfrogramu stworzonego przez Kosmiczny Szyfrator – czyli obecnego stanu wszechświata. Szyfrogram ten zawzięcie rekonstruują astronomowie i kosmolodzy obserwacyjni, tworząc coraz to dokładniejsze mapy rozkładu materii (zarówno tej widzialnej, jak i ciemnej) w obserwowanym Wszechświecie. Bazując na tych danych oraz na fizyce teoretycznej, kosmolodzy-teoretycy starają się modelować dynamikę Wszechświata wstecz. To zaś w naszym kryptograficznym porównaniu, nic innego jak wykonywanie deszyfracji.

Jednak wciąż brakuje nam klucza. W naszej kosmicznej analogii jest nim przede wszystkim czas. To on mówi nam, ile podstawowych kroków szyfrujących trzeba wykonać. A musimy to wiedzieć, jeśli chcemy odzyskać stan początkowy. Nie znając klucza, musimy próbować z różnymi jego wartościami. W tym jednak zarówno krypktoanalitycy, jak i kosmolodzy są zaprawieni. Łamacze szyfrów zaprzęgają superkomputery, które sprawdzają wszystkie dopuszczalne wartości. To mało wyrafinowane podejście określa się mianem ataku siłowego. Igły w stogu siana szukają także kosmolodzy-teoretycy, analizujący ewolucję kosmologiczną dla różnych modeli, różnych wartości parametrów i różnych czasów. Oczywiście z niesłabnącą nadzieją na “szczęśliwy traf”.

Sukces zależy nie tylko od naszej determinacji. Jeśli ewolucja wszechświata nie jest deterministyczna, jej odszyfrowanie jest z góry skazane na niepowodzenie. Wpływ na to mogą mieć procesy kwantowe, leżące u znanych nam podstaw mechaniki wszechświata. O tym jednak przy innej okazji.

© Jakub Mielczarek

Artykuł został opublikowany na portalu Onet.

Hakowanie satelitów

jakub mielczarekLeave a comment

Współczesne, sztuczne satelity Ziemi można postrzegać jako wyspecjalizowane komputery, przetwarzające informacje i komunikujące się ze stacjami naziemnymi lub innymi satelitami. Z tego punktu widzenia, rysuje się ich podobieństwo do serwerów, będących częstym celem cyberataków. Z uwagi na duży koszt budowy i umieszczenia na orbicie satelitów, oraz ich nierzadko strategiczne przeznaczenie, również one mogą stać się celem hakerów. Motywacje do podejmowania prób takich ataków mogą być różne, wliczając chęć przejęcia satelity w celu otrzymania okupu, czy też działania dywersyjne. Sytuacje takie nie są jedynie hipotetyczne, lecz zostały już odnotowane w przeszłości. Publicznie dostępna lista cyber-incydentów z udziałem satelitów jest już całkiem spora a przypuszczalna faktyczna skala tego procederu jest znacznie szersza [1, 2]. Biorąc pod uwagę obecny dynamiczny rozwój technologii satelitarnych, w szczególności, związany z budową konstelacji satelitarnych dostarczających internet, spodziewać się można narastania tego problemu. Dlatego też, warto temu zagadnieniu poświęcić należytą uwagę. Niniejszy tekst ma na celu zarysowanie zagadnienia cyberbezpieczeństwa rozwiązań satelitarnych i sprowokowanie Czytelnika do dalszych, pogłębionych, studiów w tym obszarze.

Mogłoby się wydawać, że uzyskanie nieautoryzowanego dostępu do systemu operacyjnego satelity, krążącego na wysokości kilkuset kilometrów nad powierzchnią Ziemi, jest zadaniem praktycznie niewykonalnym. Przekonanie takie ma swoje uzasadnienie w tym, iż informacje związane zarówno z systemami samych satelitów, jak i ze sposobami ich komunikacji, zazwyczaj pozostają niedostępne. Jest to klasyczny przykład tzw. security by obscurity (bezpieczeństwa przez niejawność). To, z jednej strony, ma na celu zniechęcenie do podejmowania jakichkolwiek prób ataków. Z drugiej jednak strony, podejście takie może uśpić czujność osób stojących na straży bezpieczeństwa systemów satelitarnych. Biorąc zaś pod uwagę dynamikę wzrostu ilości umieszczanych na orbicie okołoziemskiej satelitów, możliwości wystąpienia błędów i luk w systemach zabezpieczeń nie można wykluczyć. Chętnych do lokalizacji tych podatności  i ich późniejszego wykorzystania może być wielu. 

Jednym ze sposobów wykrywania słabości zabezpieczeń jest przekonanie tak zwanych “etycznych hakerów” do tego by zechcieli ich poszukać – inaczej mówiąc, włamać się do danego satelity. Działania takie mogą przyjąć formę otwartego konkursu z motywacją (oprócz satysfakcji) w postaci pokaźnej nagrody pieniężnej. W maju ubiegłego roku konkurs taki, pod nazwą Space Security Challenge 2020: HACK-A-SAT, został zorganizowany przez Siły Powietrzne Stanów Zjednoczonych (United States Air force – USAF), wraz z Służbą Obrony Cyfrowej (Defense Digital Service – DDS). Celem rywalizacji było m.in. przywrócenie kontroli nad satelitą, na który przeprowadzono symulowany cyberatak. W konkursie wykorzystano eksperymentalne konstrukcje satelitarne, znajdujące się na Ziemi. Jednakże, najepszym drużynom, udostępniony został również w pełni profesjonalny satelita orbitujący Ziemię. Do konkursu przystąpiło ponad tysiąc drużyn z całego świata. Tym bardziej, godne uznania jest zajęcie drugiego miejsca w tym konkursie przez drużynę “Poland Can Into Space” z Polski.

Należy podkreślić, że przeprowadzenie ataków na systemy satelitarne nie musi wiązać się z użyciem kosztownego sprzętu, co zaś znacząco rozszerza grono potencjalnych atakujących. W szczególności, hakerzy nie muszą być wyposażeni w zaawansowane urządzenia telekomunikacyjne. Celem ataków mogą być bowiem nie koniecznie bezpośrednio same satelity, lecz autoryzowane stacje naziemne, za pośrednictwem których są one kontrolowane. Obejście zabezpieczeń takich stacji może pozwolić na nawiązanie pożądanego połączenia z komputerem satelity i wpłynięcie na jego funkcjonowanie.

W ten sposób, atakujący mogą osiągnąć jeden z wielu możliwych celów, takich jaki np.: 

  • Zainfekowanie komputera satelity złośliwym oprogramowaniem, co może mieć na celu zaburzenie jego pracy. Na przykład, powodując zafałszowanie informacji i wprowadzanie operatora satelity w błąd (również, w sposób trudny do wykrycia). 
  • Zebranie wrażliwych lub cennych informacji. Na przykład, pozyskiwanie danych obrazowych lub sygnałowych. 
  • Szantaż, czy też atak typu ransomware, mający na celu otrzymanie okupu za przywrócenie satelity do działania. Jest to szczególnie kusząca możliwość, z uwagi na typowo ogromne koszty rozwiązań satelitarnych. 

Ataki na systemy satelitarne, wykorzystujące podatności stacji naziemnych, są jednak zasadniczo trudne do przeprowadzenia. Wynika to z zastosowania silnych zabezpieczeń w tego typu obiektach. W takiej sytuacji, łatwiejszym celem może okazać się próba ataku bezpośredniego. Uzasadnione jest to tym, że szyfrowanie kanału komunikacji pomiędzy satelitą a stacją naziemną może być stosunkowo słabe. Związane to jest z ograniczeniami na przepustowość wykorzystywanych łączy radiowych oraz kosztem energetycznym transmisji, co zaś wyklucza stosowanie silnych algorytmów szyfrujących. Przykładem tego jest chociażby wykazana możliwość kryptoanalizy algorytmów GMR-1 i GMR-2, stosowanych w telefonii satelitarnej [3]. Ponadto, ograniczenia na rozwiązania kryptograficzne są narzucane przez rozmiary pakietów danych wymienianych radiowo w trakcie przelotu satelity nad stacją naziemną (co nie dotyczy satelitów geostacjonarnych). Te więzy czasowe, wymuszają stosowanie kompromisowych rozwiązań, biorąc z jednej strony ilość przesyłanych danych użytkowych a z drugiej bezpieczeństwo tych danych.  

Wykorzystanie podatności otwierających się poprzez bezpośrednie nawiązanie łączności z satelitą urealnione jest przez dostępność i stosunkowo niski koszt niezbędnego sprzętu. W wielu przypadkach, wystarczy do tego celu antena paraboliczna o średnicy około dwóch metrów i układ nadawczo-odbiorczy, zamykające się w kwocie kilkunastu tysięcy złotych. Już takie wyposażenie może pozwolić na podszycie się pod autoryzowaną stację nadawczą (tzw. spoofing) i nawiązanie komunikacji z satelitą. A stąd już krok do zainfekowania systemu operacyjnego satelity, lub przejęcia nad nim kontroli.  

Przedmiotem zainteresowania hakerów mogą być także same dane przesyłane z satelitów. Odbieranie takich danych nie wymaga zaś nawiązania dwukierunkowej komunikacji z satelitą. Wystarczyć więc może nawet zwykły tuner i antena satelitarna. Większość z przesyłanych na ziemię danych jest jednak zaszyfrowana. Dotyczy to również telewizji satelitarnej. Z kosmosu trafia do nas jednak cała masa, innych, dużo bardziej wrażliwych danych, takich jak np. rozmowy prowadzone za pomocą telefonów satelitarnych, czy też dane przemysłowe. Za sprawą powstającego globalnego internetu satelitarnego, danych tych będzie znacząco przybywać. To też rodzi obawy, że będą one mogły zostać przechwycone i bezprawnie wykorzystywane (jeśli nie zostaną wystarczająco silnie zabezpieczone).  Przykładu takiej możliwości dostarcza wykazana niedawno podatność, zainstalowanych na statkach, satelitarnych systemów VSAT (Very Small Aperture Terminals) [4].

Na styku cyberataków i ataków fizycznych znajdują się również ataki typu DoS (Denial-of-Service), polegające na zablokowaniu danej usługi, na przykład poprzez zawieszenie witryny internetowej. Stosowaną często wersją takiego ataku jest DDoS (Distributed Denial-of-Service), w którym wykorzystuje się masowo zainfekowane komputery do połączenia z danym serwerem w celu jego przeciążenia i w konsekwencji zawieszenia. 

Za satelitarny odpowiednik ataku DoS możemy uznać zakłócenie pracy satelity (tzw. jamming). Zakłócany może być zarówno tzw. downlink (komunikacja z satelity na ziemię) oraz tzw. uplink (komunikacja z ziemi do satelity). Zakłócenie radioelektroniczne można przeprowadzić za pomocą naziemnej stacji radiowej, lub też dedykowanego do tego celu satelity. O ile ta druga możliwość dana jest nielicznym, to już ataki typu DoS z powierzchni Ziemi można realizować w oparciu o stosunkowo nieduże zasoby sprzętowe.  

Jednymi z najpowszechniejszych przypadków ataków na satelitarną usługę w transmisji downlink są zakłócenia pracy systemów nawigacji satelitarnej (GNSS), takich jak GPS czy Galileo, oraz telewizji satelitarnej.  Zakłócenia systemów GNSS mogą uniemożliwić z korzystania z nawigacji satelitarnej w danym obszarze jego stosowania. Ataki tego mają miejsce dosyć często, o czym świadczą udokumentowane przypadki [2]. Licznych przykładów takich działań dostarcza raport “Above Us Only Stars – Exposing GPS Spoofing in Russia and Syria,” (pdf) przygotowany przez ośrodek C4ADS. Raport przytacza również przykładów spoofingu GPS (czyli podszywania się pod system GPS), co może być działaniem jeszcze bardziej niebezpiecznym, gdyż nieświadomy użytkownik może zostać wprowadzony w błąd a jego pojazd (samochód, statek, samolot) może być skierowany np. na kurs kolizyjny z przeszkodą. Sposobem radzenia sobie z takimi sytuacjami jest m.in. kryptograficzne uwierzytelnienie źródeł sygnału.

Warto dodać, że z uwagi na dominujące znaczenie transmisji internetowej, zakłócenie telewizji satelitarnej traci obecnie na znaczeniu. Działania takie miały jednak miejsce w przeszłości. Udokumentowanym incydentem tego typu było np. zakłócenie kurdyjskiego kanału satelitarnego MED-TV w 1995 roku [2].   

Podsumowując, cyberataki na systemy satelitarne są realnym zagrożeniem, a ich znaczenie będzie wzrastało, wraz z rozwojem internetu satelitarnego (dostarczanego z niskiej orbity okołoziemskiej) oraz innych usług satelitarnych. Na szczególną uwagę i monitorowanie od strony cyberbezpieczeństwa zasługuje tu konstelacja Starlink, budowana obecnie przez firmę SpaceX. 

Konstelacji satelitów Starlink (stan na styczeń 2021). Interaktywna mapa pod adresem: https://satellitemap.space/

Jednym z obiecujących kierunków, który może zmniejszyć ryzyko bezpośrednich ataków na satelity, jest zastąpienie komunikacji radiowej, łącznością laserową. Łączność laserowa wdrażana jest już m.in. w komunikacji międzysatelitarnej w konstelacji Starlink (ale nie w komunikacji ze stacjami naziemnymi). Wykorzystanie satelitarnych łączy optycznych jest obecnie bardzo ważnym kierunkiem rozwoju. Wynika to zarówno, z dużo większych przepustowości, jak i mniejszych strat energetycznych, w przypadku łączy laserowych. Zaletą, w stosunku do komunikacji radiowej, jest także dużo mniejsza podatność na przechwycenie komunikacji, wynikająca z małego kąta rozbieżności wiązki laserowej. Własność ta stanowi zasadniczą trudność przy próbach cyberataków na systemy satelitarne. Równocześnie, wysokie przepustowości łączy optycznych pozwalają na stosowanie silnych algorytmów kryptograficznych, w tym algorytmów kryptografii postkwantowej. Łącza optyczne nie są jednak wolne od słabości. Największym ich wrogiem są czynniki atmosferyczne, takie jak chmury, które są zdolne do tego by skutecznie przeprowadzić atak DoS.

Bibliografia

  1. D. Housen-Couriel, Cybersecurity threats to satellite communications: Towards a typology of state actor responses, Acta Astronautica 128,  409-415 (2016). 
  2. A. Ali.Zare Hudaib,  Satellite Network Hacking & Security Analysis, International Journal of Computer Science and Security (IJCSS) 10, Issue (1),  8-55 (2016).
  3. B. Driessen, R. Hund, C. Willems, C. Paar, & T. Holz, Don’t Trust Satellite Phones: A Security Analysis of Two Satphone Standards, IEEE Symposium on Security and Privacy, 128-142 (2012).
  4.  J. Pavur, I. Martinovic, M. Strohmeier, V. Lenders, & D. Moser, A tale of sea and sky: On the security of maritime VSAT communications, IEEE, 1006–1022 (2020).

© Jakub Mielczarek

Artykuł został opublikowany na portalu Polish Brief.

Rozpinanie kwantowej sieci

jakub mielczarekLeave a comment

Pod koniec lat sześćdziesiątych ubiegłego stulecia w Stanach Zjednoczonych zaczął powstawać ARPANET – prekursor dzisiejszego Internetu. Zamysłem stojącym za stworzeniem pierwszej rozległej sieci komputerowej była decentralizacja zasobów obliczeniowych związanych z kontrolowaniem amerykańskiego arsenału nuklearnego. W czasie zimnej wojny, kiedy ryzyko konfliktu nuklearnego brano bardzo poważnie, konieczne stało się uchronienie przed sytuacją w której jeden precyzyjny atak nieprzyjaciela mógł unicestwić działanie całego systemu i w konsekwencji uniemożliwić kontratak. Rozwiązaniem była decentralizacja, która przyjęła formę, rozpiętej na terenie USA, sieci teleinformatycznej.

Schemat sieci ARPANET z 1977 roku. Warto zwrócić uwagę na istniejące już w tamtym czasie łącza satelitarne z węzłem na Hawajach oraz z centrum detekcji trzęsień Ziemi oraz wybuchów jądrowych NORSAR, zlokalizowanym w Norwegii. Źródło

Pomimo, że motywacja projektu związana była ściśle z obronnością, zdecydowano się na włączenie do sieci również segment cywilny, łączący wiodące amerykańskie uczelnie oraz instytucje naukowe. Dzięki temu, w prace nad rozwojem sieci mogła zaangażować się społeczność akademicka, która wykorzystywała ARPANET m.in. do prowadzenia zdalnej korespondencji oraz do współdzielenia zasobów obliczeniowych. Ta otwarta strona projektu dała również impuls do snucia wizji dotyczących możliwych przyszłych zastosowań sieci komputerowych, wykraczających daleko poza domenę militarną, rządową i naukową.

Jedną z osób zafascynowanych koncepcją publicznego wykorzystania sieci komputerowych był absolwent MIT, niezależny spec od bezpieczeństwa komputerowego Whitfield Diffie. Diffie doskonale zdawał sobie sprawę z tego, że urzeczywistnienie idei publicznej sieci wymagać będzie wcześniejszego rozwiązania dobrze znanego problemu wymiany klucza. A to dlatego, że tylko dzięki efektywnej metodzie wymiany sekretnego klucza, możliwe będzie wdrożenie rozwiązań kryptograficznych, gwarantujących bezpieczeństwo komunikacji w sieci. Problem ten, którego znaczenie miało swoje szerokie konsekwencje dla przebiegu II wojny światowej, uważano jednak za niemożliwy do rozwiązania. Nie zniechęciło to jednak upartego Diffi’ego do własnych badań i poszukiwań. I tak, w 1976 roku, razem z Martinem Hellman’em oraz Ralphem Markle, zaproponował On genialne rozwiązanie w postaci kryptografii asymetrycznej (znanej również jako kryptografia z kluczem publicznym), opartej nie na jednym, lecz na dwóch kluczach – sekretnym oraz publicznym.

Rok później powstał, najpopularniejszy algorytm kryptografii asymetrycznej, słynny RSA. Tak oficjalnie narodziła się kryptografia z kluczem publicznym, bez której trudno byłoby sobie wyobrazić późniejszy rozwój Internetu. Należy w tym miejscu jednak dodać, że kryptografia asymetryczna miała również swoją alternatywną historię narodzin, związaną z brytyjską Centralą Łączności Rządowej (ang. GCHQ – Government Communications Headquarters). Instytucja ta, skupiająca elitę brytyjskiej kryptologii, została utworzona po II wojnie światowej na bazie ośrodka w Bletchley Park (w którym złamano Enigmę). To właśnie w GCHQ, w 1969 roku, znany z nieszablonowego myślenia, inżynier i kryptolog James Ellis wpadł na podobny jak Diffie, Hellman i Markle pomysł. Jego ideę rozwiną zaś Clifford Cocks, matematyk który, w 1973 roku, tuż po wstąpieniu w szeregi GCHQ, zaproponował algorytm “odkryty” kilka lat później przez Ronalda Rivesta, Adi Shamira i Leonarda Adelmana (RSA). O Ellisie i Cocksie świat usłyszał jednak dopiero w drugiej połowie lat 90-tych, po częściowym odtajnieniu ich pracy w GCHQ. W tym czasie, algorytm RSA był już wdrożony na globalną skalę a jego oficjalni Twórcy odnieśli dzięki swojemu odkryciu ogromy sukces komercyjny.

Kiedy kryptografia asymetryczna święciła swoje triumfy, w jej piedestale pojawiła się jednak rysa. W 1994 roku, pracujący dla Bell Labs, amerykański matematyk Peter Shor pokazał, że bezpieczeństwo algorytmów kryptografii asymetrycznej, takich jak RSA, można podważyć z wykorzystaniem komputerów kwantowych. To zaś zrodziło obawy dotyczące możliwych przyszłych ataków kwantowych na kryptografię klucza publicznego. Pewne rozwiązanie tego problemu czekało już jednak na półce, a do odparcia kwantowego zagrożenia, wykorzystywało ten sam, kwantowy, oręż. Chodzi mianowicie o kwantową dystrybucję klucza (ang. Quantum Key Distribution – QKD), metodę zaproponowaną w 1984 roku przez Charles’a Bennett’a i Gilles’a Brassard’a. Warto dodać, że pomysł ten był rozwinięciem idei kwantowego pieniądza, która pojawiła się jeszcze na przełomie lat sześćdziesiątych i siedemdziesiątych za sprawą Stephena Weinera.

Kwantowa dystrybucja klucza umożliwia wymianę sekretnego klucza, wykorzystując stany polaryzacji pojedynczych kwantów światła – fotonów. Te zaś, co wynika z zasad rządzących mikroświatem, nie są skłonne do dzielenia się informacją, którą w sobie niosą. W szczególności, nie jest możliwe wykonanie idealnej kopii (klonu) takiego fotonu, jeśli jego stan nie jej nam wcześniej znany. Algorytmy QKD, takie jak zaproponowany przez Bennett’a i Brassard’a BB84, zaprzęgają tą własność do tego by ukryć przed światem wymieniane bity sekretnego klucza. Obrazowo rzecz ujmując, pomiędzy stronami wymieniającymi sekretny klucz powstaje “kwantowy tunel”, a każda próba jego nieuprawnionej eksploracji kończy się jego zasypaniem. Co więcej, bezpieczeństwo takiego rozwiązania możemy ściśle udowodnić na gruncie mechaniki kwantowej i teorii informacji.

Pomimo niezwykłej atrakcyjności QKD, jako wręcz idealnego sposobu wymiany sekretnego klucza, trudności natury technicznej przez wiele lat skutecznie utrudniały szerokie wdrożenie tego rozwiązania. Sytuacja ta uległa w ostatnim dziesięcioleciu znaczącej poprawie, a obecnie możemy mówić wręcz o rozkwicie technologii QKD. Pozostającym problemem jest wciąż dystans na który kwantowa dystrybucja klucza może zostać pomyślnie przeprowadzona, co jest skutkiem tłumienia fotonów w ośrodku optycznym. W konsekwencji, za pomocą światłowodu, QKD możemy skutecznie realizować na odległościach nie większych niż około 100 km. Dopuszczalnym, lecz zarazem bardzo kosztownym, sposobem ominięcia tej trudności jest wykorzystanie przestrzeni kosmicznej. Dzięki dużo słabszemu tłumieniu fotonów w powietrzu i w próżni, kwantowa dystrybucja klucza może być realizowana na znacznie dłuższych odległościach, co zostało potwierdzone dzięki eksperymentom z wykorzystaniem chińskiego satelity Micius. Alternatywnego rozwiązania dostarczają tak zwane powielacze kwantowe. Wymagają one jednak dalszych prac badawczo-rozwojowych.

Bez ich pomocy, już teraz, zaczynają powstawać pierwsze naziemne sieci realizujące QKD. Nie stanowią one jednak zupełnie odrębnych systemów. Tworzone są równolegle do konwencjonalnych sieci teleinformatycznych, dostarczając im sekretnych kluczy, niezbędnych do prowadzenia bezpiecznej wymiany informacji. A to zapewniane jest już przez bardzo silne szyfry symetryczne, które pozostaną nietknięte, nawet w epoce komputerów kwantowych.

Możemy zatem powiedzieć, że na naszych oczach rodzi się, zupełnie nowy typ (kwantowej) sieci. Sytuacja ta nasuwa skojarzenia z ARPANETem. Podobnie jak ARPANET, sieci kwantowe powstają w odpowiedzi na zagrożenia swoich czasów. W latach siedemdziesiątych ubiegłego stulecia, za największe niebezpieczeństwo uważano atak jądrowy. We współczesnym, coraz bardziej cyfrowym, świecie globalne zagrożenia nie tkwią już jednak tylko w silosach lecz także w serwerach. To w cyberprzestrzeni rozgrywa się wiele ze współczesnych konfliktów i to groźba rozległych ataków w cyberprzestrzeni staje się źródłem największych obaw. Dlatego też tak ważne jest bezpieczeństwo wymiany informacji w sieciach teleinformatycznych, której to fundamentem jest kryptografia. Kryptografia kwantowa, wcielona poprzez QKD, jest sposobem na wyniesienie cyberbezpieczeństwa na zupełnie nowy poziom. Podobnie jak w przypadku ARPANETu, tak i wdrożenie jego współczesnego odpowiednika – nazwijmy go QUANTUMNETem – dotyczyć będzie jednak wyjściowo jedynie zasobów o znaczeniu krytycznym. Przez co należy rozumieć zarówno najbardziej wrażliwe dane, jak i połączoną z siecią teleinformatyczną infrastrukturę o szczególnym znaczeniu (np. elektrownie i banki). Jednakże, już teraz, podobnie jak niegdyś Whitfield Diffie, możemy rozmyślać o korzyściach jakie mogłoby płynąć z upublicznienia sieci, w tym przypadku – sieci kwantowej. Czy zatem współczesne pierwsze sieci realizujące kwantową dystrybucję klucza staną się zalążkiem przyszłego Internetu kwantowego?

Dywagacje na ten, skądinąd fascynujący, temat pozostawmy na inną okazję. Teraz natomiast przyjrzyjmy się wybranym, obecnie rozpinanym, sieciom kwantowym. Do najważniejszych z nich należy bez wątpienia chińska sieć, o długości około 2000 km, łącząca miasta Pekin, Jinan, Hefei i Szanghaj. Sieć ta jest pierwszym etapem powstającej chińskiej kwantowej sieci szkieletowej. W jej skład wchodzą również lokalne kwantowe sieci miejskie.

Schemat chińskiej kwantowej sieci łączącej Pekin i Szanghaj. Żródło: [2]

Jak widać na rysunku powyżej, sieć ta złożona jest z szeregu segmentów. Wynika to ze wspomnianego ograniczenia na dystans na jaki można prowadzić QKD za pośrednictwem światłowodu. Każda z pomarańczowych kropek na schemacie to tak zwany zaufany węzeł, który podaje sekretny klucz przez kolejny segment sieci. Węzły te są klasyczne a informacja przez nie przekazywana pozostaje do dyspozycji operatora sieci. To, w naturalny sposób, rodzi obawy co do bezpieczeństwa takiego systemu i możliwości nieautoryzowanego dostępu do przekazywanej informacji. Temat ten jest dużo bardziej złożony i wykracza poza ramy tego tekstu. Dodam jedynie, że wprowadzenie wspomnianych powyżej powielaczy kwantowych powinno umożliwić zastąpienie zaufanych węzłów węzłami kwantowymi, zapewniającymi wyższe bezpieczeństwo przekazywanej informacji.

Ambicje Chin, wyrastających na światowego lidera technologii kwantowych, pozostają niezaspokojone i już teraz prowadzone są działania w kierunku rozszerzenia “kwantowej autostrady,” pokrywając wszystkie chińskie prowincje i regiony autonomiczne. Wraz z siecią naziemną ma powstać także komplementarny segment satelitarny, który jest już z powodzeniem testowany. Umożliwi on realizację QKD na dużych dystansach, częściowo rozwiązując problem zaufanych węzłów. Plan szkieletu tej sieci można znaleźć poniżej.

Planowana chińska szkieletowa sieć kwantowa. Niebieskie linki odpowiadają zbudowanym już fragmentom sieci. Żródło: [3]

Zarówno Stany Zjednoczone, jak i Unia Europejska (czy też inne rozwinięte technologicznie państwa) nie pozostają bierne i również prowadzą prace nad budową własnych kwantowych sieci. Na naszym europejskim podwórku, na szczególną uwagę zasługuje eksperymentalna kwantowa sieć miejska zbudowana w Madrycie. Sieć ta powstała we współpracy naukowców z Politechniki madryckiej oraz firm Telefonica i Huawei. Dostawcą systemów do kwantowej dystrubucji klucza jest tutaj niemiecki oddział firmy Huawei, natomiast Telefonica do celu projektu udostępnia swoje zasoby sieciowe. Madrycka sieć, której schemat przedstawiono poniżej, zawiera obecnie 13 połączeń i należy do najbardziej rozbudowanych tego typu sieci na świecie.

Schemat kwantowej sieci powstałej w Madrycie. Źródło

Kolejną ważną europejską inicjatywą związaną z QKD jest projekt OpenQKD. W jego ramach, testowane są lokalne komponenty sieci kwantowych oraz ich możliwe obszary zastosowań praktycznych. Sieć madrycka jest jedną z kilku eksperymentalnych sieci wchodzących w skład OpenQKD. Warto dodać, że w projekcie tym uczestniczy również Poznańskie Centrum Superkomputerowo-Sieciowe. Technologia QKD, w kontekście budowy sieci kwantowych, rozwijana jest również w projekcie CiViQ, finansowanym w ramach europejskiej inicjatywy Quantum Flagship.

Jednakże, największe nadzieje na utworzenie rozległej paneuropejskiej kwantowej sieci wiążą się z inicjatywą EuroQCI, koordynowaną przez Komisję Europejską. Zakłada ona, że do końca bieżącej dekady ma powstać w Europie rozbudowana kwantowa sieć, przeznaczona wyjściowo do użytku administracji europejskiej oraz biznesu. W lipcu 2019 roku do inicjatywy Euro QCI włączyła się również Polska. Podobnie jak w przypadku sieci chińskiej, planowany jest również komponent satelitarny, co wiąże się z zaangażowaniem w ten projekt Europejskiej Agencji Kosmicznej.

EuroQCI ma zapewnić Europie wejście na nowy poziom bezpieczeństwa cybernetycznego. Początkowo jednak, również opierać się będzie na zaufanych węzłach klasycznych, co pozostawia pewien niedosyt. Mianowicie, o ile zastosowanie QKD eliminuje możliwość przechwytu informacji na łączach optycznych, obawa związana z przejęciem informacji na węzłach pozostaje realna.

Kryptografia asymetryczna, umożliwiająca realizację tzw. szyfrowania end-to-end daje możliwość uzgodnienia sekretnego klucza nawet przez, powszechnie dostępny, kanał publiczny (stosując tzw. protokół Diffiego-Hellmana). Podejście to jest jednak opiera swoje bezpieczeństwo na złożoności obliczeniowej pewnych problemów matematycznych (podobnie jak RSA). To, z jednej strony, rodzi obawę pod kątem kryptoanalizy kwantowej a z drugiej nie daje nam gwarancji bezpieczeństwa nawet w przypadku ataków klasycznych. O ile nie dysponujemy skutecznymi algorytmami ataków na takie szyfry, nie posiadamy również dowodu na to, że takowe nie istnieją i nie zostaną w bliższej lub dalszej przyszłości odkryte i co gorsza zastosowane.

Implementując sieci kwantowe zmierzamy do odejścia od kryptografii asymetrycznej. Jednakże, w kontekście problemu klasycznych węzłów, konieczne może okazać się “wzmocnienie” takich sieci, uniemożliwiając operatorowi sieci dostęp do wymienianych informacji. Stosowanie współczesnych algorytmów asymetrycznych jest w tym kontekście nieuzasadnione. Nadzieję na wdrożenie takiego rozwiązania dają jednak rozwijane obecnie algorytmy kryptografii postkwantowej, takie jak np. algorytmy oparte na kratach.

Prawdziwie bezwarunkowo bezpiecznego rozwiązania może dostarczyć jednak jedynie zastąpienie węzłów klasycznych, węzłami kwantowymi, urzeczywistniając w pełni koncepcję sieci kwantowych. Teoretycznie, sieci takie mogą zagwarantować absolutną prywatność jej użytkownikom. Trudno być jednak przekonanym co do tego, że globalna kwantowa sieć, w takiej formie, kiedykolwiek powstanie. Wynika to nie z wyzwań technicznych, lecz z dobrze znanej kwestii znalezienia kompromisu pomiędzy prywatnością a bezpieczeństwem. Mianowicie, istotne znaczenie ma nie tylko uniknięcie nieuprawnionego przechwycenia naszej komunikacji w sieci ale również zachowanie odpowiednich standardów aktywności w samej sieci. Całkowicie niepodatna na kontrolę kwantowa sieć mogłaby stać nie tyle przestrzenią uszanowania naszej prywatności i swobody działań, co miejscem ekspresji bezkarności i działalności przestępczej. Dlatego też, nawet jeśli Internet kwantowy stanie się faktem, niezbędne będzie wcześniejsze rozwiązanie problemu tego jak sprawić by nie przeistoczył się on w “Kwantowy Darknet”.

Bibliografia

  1. Simon Signh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor Boks, New York (2000).
  2. Qiang Zhang, Feihu Xu, Yu-Ao Chen, Cheng-Zhi Peng, and Jian-Wei Pan, Large scale quantum key distribution: challenges and solutions [Invited], Opt. Express 26, 24260-24273 (2018).
  3. Martino Travagnin, Adam Lewis, Quantum Key Distribution in-field implementations, EUR 29865 EN, Publications Office of the European Union, Luxembourg (2019).
  4. H. Kimble, The quantum internet. Nature 453, 1023–1030 (2008).

© Jakub Mielczarek

Artykuł został opublikowany na portalu Nauka UJ.

Czy Wszechświat jest komputerem kwantowym?

jakub mielczarek6 Comments

Każdą informację z jaką mamy na co dzień do czynienia daje się sprowadzić do ciągu dwóch różnych symboli, na przykład kropek i kresek, jak w alfabecie Morse’a. Możemy zatem stwierdzić że, informacja podobnie jak materia posiada strukturę ziarnistą z „elementarną cząstką informacji” zwaną bitem. Do oznaczania dwóch możliwych wartości bitu, przyjęło się powszechnie używać 0 i 1. W szczególności, każdą liczbę naturalną możemy reprezentować jako skończony ciąg binarny. A zatem, rok założenia Uniwersytetu Jagiellońskiego to jak łatwo zapamiętać 010101010100 (pięć 01 i 00). W pewnym sensie, o tym, że również ułamki można reprezentować w podobny sposób zdawano sobie sprawę dużo wcześniej, bo już w starożytnym Egipcie. Nie tylko liczby ale także litery, znaki specjalne, obrazy i inne znane nam formy informacji dają się zakodować za pomocą zer i jedynek.

Informacja nie jest z reguły statyczna lecz podlega ciągłym metamorfozom w czym, za pomocą reprezentacji bitów jako impulsów elektrycznych, pomagają jej komputery. Komputery to zaś nic innego jak pewne układy fizyczne. Podążając tym tropem, możemy dojść do wniosku, że w zasadzie każdy wycinek rzeczywistości jest pewnego rodzaju komputerem, przetwarzającym lub przynajmniej przechowującym określony rodzaj informacji. Ale czy aby na pewno tak jest? Czy każdemu procesowi fizycznemu odpowiada przetworzenie informacji z którym poradziłby sobie komputer? Czy też ogólniej, czy nasza rzeczywistość jest obliczalna? 

Próbę zmierzenia się z tymi z pozoru czysto filozoficznymi pytaniami podjął w latach trzydziestych ubiegłego wieku brytyjski matematyk, kryptolog i zdecydowanie wszechstronny geniusz Alan Turing. Analizując problem obliczalności różnych problemów, wprowadził on abstrakcyjny model maszyny obliczeniowej, nazwany później od jego nazwiska maszyną Turinga.  Maszyna Turinga to idealizacja „matematyka” który, bit po bicie, dokonuje przetwarzania informacji zapisanej jako ciąg binarny na nieskończenie długiej taśmie. 

Choć może to brzmieć zaskakująco, wszystkie operacje wykonywane przez współczesne komputery można przeprowadzić za pomocą maszyny Turinga, którą faktycznie da się zbudować, na przykład z klocków LEGO.

Lego_Turing_Machine
Maszyna Turinga zbudowana z klocków LEGO. Źródło

Choć ta nie dostarcza optymalnego sposobu przetwarzania informacji, rozważania na jej temat pozwoliły wniknąć w naturę tego co obliczalne a co nie.  Mianowicie, na kanwie rozważań Turinga, amerykański matematyk Alonzo Church sformułował hipotezę którą, w jednej ze swoich wcieleń, możemy wyartykułować następująco: Każde obliczenie (przetworzenie informacji) wykonane przez układ fizyczny (czyli układ spełniający prawa fizyki) możne zostać wykonane za pomocą maszyny Turinga.

Ta tak zwana hipoteza Churcha-Turinga ma doniosłe znaczenie z punktu widzenia symulowania procesów fizycznych. Procesy które mają reprezentację w postaci operacji wykonywalnych na maszynie Turinga, określamy mianem zupełnych w sensie Turinga.  Otwartym problemem jest to czy wszystkie zjawiska fizyczne cechują się taką zupełnością i szczerzej czy cały Wszechświat można uznać za będący zupełnym w sensie Turinga. Choć, jak dotąd, nie przedstawiono kontrprzykładu dla hipotezy Churcha-Turinga, nie mamy jednak całkowitej pewności. Warto dodać, że zupełność Wszechświata implikuje to, że pewne problemy o których wiemy, że nie są zupełne w sensie Turinga, nie będą mogły zostać nigdy rozwiązane. 

Poszukiwanie odpowiedzi na pytanie o zupełność Wszechświata w sensie Turinga komplikuje fakt, że reprezentacja informacji za pomocą ciągu zer i jedynek wymaga rewizji, kiedy zanurzymy się do mikroświata. Tam, w świecie rządzonym przez prawa mechaniki kwantowej, klasyczna teoria informacji uogólnia się do tak zwanej teorii informacji kwantowej. Podstawową jednostką informacji kwantowej jest zaś nie bit lecz kubit (ang. qubit). Kubit można wyobrazić sobie jako sferyczną powierzchnię Ziemi, na której biegunach znajdujemy klasyczne wartkości bitu 0 i 1. Kubit może jednak „żyć” nie tylko na biegunach ale w dowolnym innym punkcie, których na sferze (którą nazywamy sferą Blocha) jest nieskończenie wiele.  Każdy z tych punktów jest tak zwaną kwantową superpozycją wartości klasycznych 0 i 1. Stany bardziej złożonych układów kwantowych nie reprezentujemy zaś jako ustalony ciąg bitów np. 011, lecz jako superpozycję wszystkich możliwych ciągów bitów o danej długości, w tym przypadku są to: 000, 001, 010, 100, 011, 101, 110 i 111. W ogólności zaś, dla układu kwantowego opisywanego przez n kubitów, stan kwantowy będzie superpozycją 2 do potęgi n ciągów binarnych, każdy o długości n bitów.

QUBIT
Geometryczna reprezentacja bitu i kubitu. Źródło

Przetwarzanie informacji kwantowej jest, do pewnego stopnia, możliwe za pomocą komputerów klasycznych, a więc i za pomocą maszyny Turinga. Jest to jednak w ogólności zadanie karkołomne, gdyż dla n-kubitowego układu kwantowego wymaga to wykonania operacji na 2n amplitudach prawdopodobieństwa, każdego z możliwych ciągów n bitowych.  Każdej z tych amplitud odpowiada zaś tak zwana liczna zespolona (złożona z dwóch liczb rzeczywistych), która może być reprezentowana przez ciąg bitów, o długości rosnącej wraz z dokładnością obliczeń. W konsekwencji, już dla stosunkowo małego układu kantowego złożonego ze stu kubitów potrzebujemy (w ogólnym przypadku) wykonać operacje na 2100 = 1267650600228229401496703205376 amplitudach, co jest poza zasięgiem jakichkowiek dostępnych obecnie, jak i możliwych do wyobrażenia sobie przyszłych, komputerów klasycznych. 

W konsekwencji, symulowanie rzeczywistości kwantowej za pomocą maszyny klasycznej jest skrajnie nieefektywne. Wyjściem z tego impasu jest uogólnienie maszyny Turinga do przypadku kwantowego, będącej modelem nie komputera klasycznego lecz uniwersalnego komputera kwantowego. Idea takich maszyn pojawiła się w pierwszej połowie lat osiemdziesiątych ubiegłego wieku za sprawą fizyków Paula Benioffa i Davida Deutscha. Niemal równocześnie, amerykański fizyk którego nie trzeba nikomu przedstawiać — Richard Feynman,  zaproponował, że każdy dyskretny układ kwantowy może być symulowany w sposób dokładny (może być “imitowany”) za pomocą operacji wykonywanych na komputerze kwantowym. Ekstrapolując to rozumowanie, jeśli więc Wszechświat da się zredukować do pewnego skończonego układu kubitów to będzie on zupełny w sensie kwantowej maszyny Turinga. Innymi słowy, możemy wtedy powiedzieć, że będzie on przykładem uniwersalnego komputera kwantowego.

Czy Wszechświat jest w istocie gigantycznym komputerem kwantowym nieustannie przetwarzającym informację kwantową? Tego wciąż nie wiemy. Natomiast, nasze obecne zrozumienie fizyki na najbardziej podstawowym poziomie do którego sięga nasza wiedza i wyobraźnia, nie wyklucza takiej możliwości. Tę granicę naszego dotychczasowego poznania określamy mianem skali Plancka, a na fizykę którą staramy się ją opisać składa się szereg propozycji kwantowych teorii grawitacji. Jedną z najpopularnieszych z nich jest teoria pętlowej grawitacji kwantowej, którą na początku lat dziewięćdziesiątych ubiegłego wieku wprowadzili Abhay Ashtekar, Carlo Rovelli i Lee Smolin. Teoria ta przewiduje, że przestrzeń na skali Plancka posiada dyskretną (“atomową”) postać, teoretycznie pozwalając na wykonanie jej symulacji kwantowych, w duchu idei Feynmana.

Nad tym jak zredukować pętlową grawitację kwantową do układu kubitów, co umożliwiłoby przeprowadzenie kwantowych symulacji, rozmyślam już od około dekady. Jednakże dopiero około trzech lat temu zabrałem się za podjęcie próby faktycznego urzeczywistnienie tego pomysłu.  Impulsem do tego był fakt pojawienia się pierwszych dostępnych komputerów kwantowych, operujących na kilku i kilkunastu kubitach. W toku badań, które obecnie prowadzimy w ramach działajacego w Instytucie Fizyki Teoretycznej UJ zespołu Quantum Cosmos Lab, udało się nie tylko teoretycznie wykazać możliwość prowadzenia kwantowych symulacji modeli Wszechświata opisywanych przez pętlową grawitację kwantową, ale również wykonać pierwsze symulacje kwantowe tego typu.

Pict
Model dyskretnej przestrzeni kwantowej zbudowanej z dwóch “atomów przestrzeni” (lub równoważnie dipolowe przybliżenie Wszechświata) oraz odpowiadający mu algorytm kwantowy, który można wykonać na kwantowej maszynie Turinga.  Źródło

 

Symulacje te, z uwagi na ograniczenia współczesnych pierwszych komputerów kwantowych są wciąż prymitywne i wykorzystują maksymalnie kilkanaście „nieoszlifowanych” kubitów. Pozwala to jednak na wytworzenie konfiguracji opisujących jednorodny model Wszechświata. Wraz z rozwojem inżynierii obliczeń kwantowych będziemy mogli temu mikroskopijnemu wszechświatowi dodawać coraz więcej upiększeń. Bazując na prognozach, już w przeciągu najbliższych pięciu lat możemy spodziewać się osiągnięcia poziomu symulacji z którymi nie poradzą sobie dostępne superkomputery klasyczne. Wykorzystanie klasycznej maszyny Turinga pozostanie wciąż teoretycznie możliwe lecz, z uwagi na jej skrajną nieefektywność, w praktyce niewykonalne. Otrzymana kwantowa symulacja wszechświata będzie jednak nadal jedynie kwantowym zarodkiem tego w którym żyjemy.

Spoglądając tysiące lat w niepewną przyszłość, nie możemy wykluczyć, że pełne symulacje makroskopowych wycinków Wszechświata staną się faktem. Nawet najbardziej zaawansowana symulacja nie będzie jednak w stanie odtworzyć w pełni Wszechświata w którym jesteśmy zanurzeni. Chyba, że w hipotetycznym przypadku granicznym kiedy to on cały zostałby wykorzystany do tego by symulować samego siebie. Ale to nie byłaby już symulacja, lecz to co nazywamy rzeczywistością i to na dodatek zupełną w sensie Turinga.    

Bibliografia

[1] J. Mielczarek, Quantum Gravity on a Quantum Chip, arXiv:1803.10592 [gr-qc].
[2] J. Mielczarek, Spin Foam Vertex Amplitudes on Quantum Computer – Preliminary Results, Universe 5 (2019) no.8, 179 [arXiv:1810.07100 [gr-qc]].
[3] G. Czelusta, J. Mielczarek, Quantum simulations of a qubit of space, arXiv:2003.13124 [gr-qc].

© Jakub Mielczarek

Artykuł został opublikowany na portalu Nauka UJ.

Splątanie kwantowe w nanosatelicie

jakub mielczarek6 Comments

Udało się zrealizować kolejny ważny krok w kierunku wykorzystania przestrzeni kosmicznej do prowadzenia komunikacji kwantowej oraz do badań nad zjawiskami kwantowymi w warunkach mikrograwitacji. Stało się to za sprawą nanaosatelity SpooQy-1, który zrealizował eksperyment demonstrujący splątanie kwantowe fotonów w warunkach kosmicznych [1]. Misja została przeprowadzona przez Centrum Technologii Kwantowych w Singapurze, we współpracy z partnerami ze Szwajcarii, Australii i Wielkiej Brytanii.

Pierwsze eksperymenty satelitarne z wykorzystaniem splątanych stanów fotonów zostały zrealizowane w ostatnich latach przez chińskiego satelitę średniego typu o nazwie Micius [2]. Jednakże, dopiero teraz udało się przeprowadzić eksperyment ze splątanymi stanami kwantowymi fotonów z wykorzystaniem miniaturowego nanosatelity typu CubeSat. W standardzie tym, nanosatelity budowane są z jednostek (unitów) w postaci sześcianów o długości krawędzi równej 10 cm. Pojedynczą kostkę określamy jako 1U – jedna jednostka. Nanosatelita SpooQy-1 zbudowany został z trzech jednostek (3U), przy czym, systemy sterowania, łączności i zasilania zamknięto w jednym z nich (1U), eksperyment kwantowy zajmował zaś pozostałe dwa bloki (2U).

Misja SpooQy-1 powstała na bazie wcześniejszego projektu nanosatelitarnego Galassia (2U), który w 2016 roku wykonał orbitalne testy układu do generowania splątanych stanów kwantowych kwantowych [3]. W ramach tej misji nie udało się jednak dokonać pomiarów samego splątania kwantowego. Z uwagi na stosunkowo niskie koszty zarówno budowy jak i umieszczania na niskiej orbicie okołoziemskiej CubseSatów, przeprowadzone misje torują drogę do realizacji kolejnych nanosatelitarnych projektów kwantowych przez mniejsze grupy naukowców i inżynierów.

SpooQy-deployment
Wypuszczenie nanosatelity SpooQy-1 z Międzynarodowej Stacji Kosmicznej. Źródło

Żeby zrozumieć znaczenie przeprowadzonego na pokładzie nanosatelity SpooQy-1 eksperymentu, warto przybliżyć (lub jedynie odświeżyć) to co rozumiemy przez splątanie kwantowe.   W tym celu, rozważmy foton, czyli podstawową porcję (kwant) pola elektromagnetycznego. Fotony, oprócz odpowiadającej im długości fali, czy też zbioru długości fali składających się na tak zwaną paczkę falową, posiadają również dwa wewnętrzne stopnie swobody związane z ich polaryzacją.  Wypadkowa polaryzacja fotonu ma postać kwantowej superpozycji dwóch stanów bazowych polaryzacji. Jako stany bazowe możemy wybrać przykładowo dwie prostopadłe względem siebie polaryzacje – poziomą (H – horizontal) oraz pionową (V – vertical). Kierunki polaryzacji są ustalone względem referencyjnego układu odniesienia, takiego jaki wyznacza chociażby płaszczyzna stołu optycznego.

Fotony możemy przygotować w stanach o pożądanej polaryzacji liniowej przepuszczając je przez polaryzator.  Jeśli będzie on ustawiony np. w pozycji H, to foton o początkowej dowolnej polaryzacji, po przejściu przez taki polaryzator znajdzie się stanie H. Ciekawą sytuacją jest, kiedy pozycja polaryzatora nie będzie pokrywała się z jedną z pozycji bazowych H i V, leczy np. będzie względem każdej z nich obrócona o 45 stopni. Odpowiada to polaryzacjom diagonalnej (D – diagonal) oraz antydiagonalnej (A – anti-diagonal). Wtedy to, analizując np. fotonu w stanie o polaryzacji D za pomocą analizatora złożonego z polaryzatorów ustawionych w pozycjach H i V, zaobserwujemy tak zwaną redukcji stanu kwantowego. Statystycznie, przepuszczając przez analizator pewną liczną fotonów przygotowanych w stanie D, połowę z nich zarejestrujemy jako będące w stanie H, a połowę w stanie V. Stan o polaryzacji D możemy więc uznać za superpozycję kwantową stanów bazowych H i V, z jednakowym rozkładem prawdopodobieństw równym 1/2. W trakcie aktu pomiaru, jakim jest analiza polaryzacji, stan ten redukuje się do jednego ze stanów bazowych (H,V) i pozostaje w nim.

Przejście od koncepcji superpozycji kwantowej do splątania kwantowego wymaga rozszerzenia powyższej dyskusji do przypadku stanu kwantowego dwóch lub więcej fotonów.  Do wyjaśnienia eksperymentu przeprowadzonego w misji SpooQy-1, wystarczy nam rozważanie splątania kwantowego dwóch fotonów. Tym bardziej, że jest to sytuacja najpowszechniejsza, a wytwarzanie stanów splątanych trzech i większej liczby fotonów jest wciąż raczkującym obszarem doświadczalnej optyki kwantowej.

Splątanie kwantowe jest szczególnym typem superpozycji kwantowej w układzie cząstek, takich jak fotony, prowadzące do występowania nielokalnych korelacji pomiędzy nimi.  Stanami dwufotonowymi, w których możemy zaobserwować splątanie kwantowe są w szczególności stany Bella: Φ+, Φ-, Ψ+ i Ψ-.  Stany te są szczególnie interesujące z tego powodu, że należą do przypadku w którym splątanie kwantowe jest najsilniejsze (mówimy, że są to stany maksymalnie splątane).

Przyjrzyjmy się teraz bliższej przypadkowi fotonów przygotowanych w stanie Φ+, co przedstawia rysunek poniżej. Fotony takie, wyemitowane ze źródła stanu splątanego, propagują się następnie do odległych punktów A i B, w których następuje pomiar. Podobnie jak w omawianym powyżej przypadku pojedynczego fotonu, a priori możemy z równym prawdopodobieństwem oczekiwać zarejestrowania każdego z fotonów w stanie o jednej z dwóch polaryzacji: H lub V. W tym momencie dochodzimy jednak do jednej z  najbardziej enigmatycznych własności mechaniki kwantowej. Mianowicie, jeśli dokonamy analizy polaryzacji jednego z fotonów, to będzie to miało natychmiastowy wpływ na wynik pomiaru przeprowadzonego na tym drugim. Jeśli np. w wyniku pomiaru okaże się, że foton w punkcie A jest stanie o polaryzacji H, to ze stuprocentową pewnością, analizując drugi foton w punkcie B, zaobserwujemy, że znajduje się on również w stanie H. Natomiast, jeśli nie dokonalibyśmy pomiaru w punkcie A, to wynik pomiaru w punkcie B wynosiłby w 50% przypadków H i w 50% przypadków V. Ta natychmiastowa redukcja stanu kwantowego,  odbiegająca od tak zwanego lokalnego realizmu, okazała się trudna do zaakceptowania przez wielu fizyków, co znalazło ucieleśnienie między innymi w paradoksie EPR (Einsteina-Podolskiego-Rosena). Przypuszczano, że mogą istnieć pewne dodatkowe (nieobserwowane) stopnie swobody, tak zwane zmienne ukryte,  znajomość których pozwoliłaby przewidzieć wyniki pomiarów i uniknąć konieczności natychmiastowej redukcji stanu kwantowego pomiędzy odległymi punktami.  Możliwość występowania zmiennych ukrytych, przynajmniej tych lokalnego typu, wyeliminował ostatecznie w latach sześćdziesiątych ubiegłego wieku północnoirlandzki fizyk John Bell, ten sam od którego nazwiska pochodzi wprowadzona powyżej rodzina stanów kwantowych.

Bell
Schemat eksperymentu Bella ze splątaniem kwantowym. Źródło

Rozważając korelacje pomiędzy wynikami pomiarów w punktach A, B wykazał on, że hipoteza zmiennych ukrytych wymaga spełnienia określonej nierówności pomiędzy wynikami pomiarów w różnych bazach. W celu wprowadzenia tej nierówności, oznaczmy wyniki pomiarów w bazie (H,V) w punktach A i B odpowiednio a i b. Natomiast, dla alternatywnego wyboru bazy, np. (D,A), niech wyniki pomiarów  w punktach A i B wynoszą a’ i b’. Korzystając z tych oznaczeń, możemy rozważań cztery różne konfiguracje dla funkcji korelacji, E(a,b), E(a’,b), E(a,b’) i E(a’,b’),  które pozwalają nam zdefiniować wielkość:

S =  E(a,b) – E(a,b’) + E(a’,b) + E(a’,b’),

zwaną parametrem CHSH (Clauser-Horne-Shimony-Holt).  Jak wykazał Bell, teoria lokalnych zmiennych ukrytych wymaga, żeby parametr ten spełnia następującą nierówność (zwana nierównością Bella, lub też nierównością Bella-CHSH):

|S|≤ 2.

Okazuje się jednak, że stany splątane takie jak rozważane tu stany Bella, jawnie łamią tę nierówność, przecząc lokalnemu realizmowi.

Wynik ten wspiera postrzeganie mechanik kwantowej jako teorii w pewnym stopniu nielokalnej. Mianowicie, stan splątany dwóch cząstek kwantowych traktujemy jako jeden obiekt kwantowy i niezależnie od tego czy jedna jego część znajduje się w dużej odległości od drugiej, ingerencja w tą pierwszą poniesie za sobą natychmiastowy skutek dla tej drugiej i vice versa. Jednakże, wbrew pierwotnym obawom, wyrażonym w paradoksie EPR, nie jest w ten sposób możliwa nadświetlna wymiana informacji. Pomimo, że splątanie kwantowe nie pozwala urzeczywistnić wizji znanych chociażby z serialu Star Trek, znajduje ono zastosowanie w komunikacji. Ma to miejsce za sprawą zarówno możliwości przeprowadzania za jej pośrednictwem tak zwanej teleportacji stanów kwantowych jak i kwantowej dystrybucji klucza. Oba te procesy zachodzą z prędkością światła w danym ośrodku, która jest mniejsza lub równa prędkości światła w próżni.

To drugie zastosowanie, czyli kwantowa dystrybucja, stanowiąca jeden z głównych filarów kryptografii kwantowej,  przyciąga szczególnie duże zainteresowanie i stanowiła jedną z głównych motywacji do przeprowadzenia misji SpooQy-1. Wytworzone stany Bella pozwalają m.in. na realizację protokołu Ekerta (E91) kwantowej dystrybucji klucza [4]. W podejściu tym, zaufana jednostka (na przykład nanosatelita) wytwarza pary splątanych fotonów, wysyłając jeden z nich do punku A a drugi do punktu B. Analizując otrzymane fotony, można otrzymać ciągi wyników pomiaru polaryzacji, np. HVHHVHVHV…. Przypisując zaś stanom polaryzacji wartości binarne np. H->0 i V->1, otrzymujemy ciąg bitów 010010101…, który może stanowić sekretny klucz, stosowany w protokołach klasycznej kryptografii symetrycznej. Przygotowując fotony np. w stanie Φ+, mamy pewność, że jeśli odbiorca A zarejestrował ciąg  010010101…, to taki sam ciąg zaobserwuje również odbiorca klucza w punkcie B.  Dodatkowym elementem takiego protokołu jest sprawdzenie na części bitów tego czy nie nastąpił podsłuch transmisji. Po pomyślnej weryfikacji, uzyskujemy wynikającą z praw mechaniki kwantowej gwarancję poufności wymienionego klucza.

Za pomocą satelity SpooQy-1, przeprowadzono testy zarówno wytwarzania jaki i analizy stanów splątanych. Splątane fotony nie były jednak emitowane poza nanosatelitę,  do odbiorców w przestrzeni kosmicznej lub na powierzchni Ziemi.  To już będzie stanowiło przedmiot kolejnych misji. W ramach tego projektu, cały eksperyment został przeprowadzony w obrębie zamkniętego modułu doświadczalnego, zawierającego źródło splatanych fotonów oraz ich analizator.

Do wytworzenia par splątanych kwantowo fotonów wykorzystano, powszechnie stosowany w warunkach laboratoryjnych, proces zwany spontanicznym parametrycznym obniżaniem częstości (SPDC – Spontaneous Parametric Down-Conversion). W zjawisku tym, wysokoenergetyczny (np. ultrafioletowy) foton ulega w optycznie nieliniowym ośrodku konwersji na dwa niżej-energetyczne fotony, występujące już w stanie splątanym. Wyniki przeprowadzonego eksperymentu raportują o wytworzeniu w ten sposób, w warunkach kosmicznych, stanu Bella Φ- (jest to stan bardzo podoby do stanu Φ+, różniący się od niego jedynie względną fazą pomiędzy stanami bazowymi).

BBO
Wytwarzanie splątanych kwantowo par fotonów w procesie spontanicznego parametrycznego obniżania częstości (SPDC – Spontaneous Parametric Down-Conversion). Źródło

W układzie eksperymentalnym, jako źródło fotonów zastosowano diodę laserową (LD) , generującą wiązkę fotonów o długości fali 405 nm (granica światła widzialnego, w stronę bliskiego ultrafioletu) i szerokości spektralnej równej 160 MHz. Do wytworzenia stanów splątanych wykorzystano dwie płytki wykonane z boranu baru (BBO), pomiędzy którymi ustawiono płytkę półfalową (HWP), dokonującą obrotu polaryzacji o 90 stopni. W celu usunięcia z wiązki wejściowego (pompującego) światła laserowego, które nie uległo konwersji w procesie SPDC, zastosowano lustro dichroiczne (DM1), pełniące funkcję filtru.  Natomiast, aby skompensować dyspersję otrzymanych fotonów na drodze optycznej zastosowano kryształ wanadanu (V) itru – YVO4. Tak otrzymany sygnał został rozdzielony do dwóch analizatorów za pomocą kolejnego lustra dichroicznego (DM2). Każdy z nich składał się z ciekłokrystalicznego rotatora polaryzacji (LCPR), polaryzatora (P) oraz fotodiody lawinowej (GM-APD) i analizował jeden z fotonów należący do kwantowo splątanej pary. Zarejestrowane fotony uznawano za pochodzące z jednej splątanej kwantowo pary jeśli zaobserwowano je w oknie czasowym o szerokości ~ 5 ns.

Spooqy_setup
Uproszczony schemat układu doświadczalnego w nanaosatelicie SpooQy-1. Źródło

Za pomocą takiego układu doświadczalnego, przeprowadzono eksperyment w którym wykazano, że wartość parametru S, dla wytworzonych w procesie SPDC stanów Bella przyjmuje wartości większe od klasycznej granicy S=2, a mniejsze od teoretycznie przewidzianej wartości równej S=2√2≈2.83. Uśredniona, otrzymana w ramach eksperymentu wartość to S=2.60±0.07 > 2. Potwierdzono tym samym łamanie nierówności Bella w warunkach orbitalnych. Otrzymany w eksperymencie poziom błędów, odpowiadający parametrowi QBER (Quantum Bit Error Rate) równemu ~ 4 % (około cztery na 100 transmitowanych bitów są błędne), jest wystarczający do tego żeby pomyślnie przeprowadzać kwantową dystrybucję klucza. To wymagać będzie jednak dostosowania układu doświadczalnego do pracy z laserem o większej mocy i układem optycznym umożliwiającym dalekodystansową komunikację optyczną.

MzY1Mzk5OQ
Fizyczna realizacja układu doświadczalnego w nanaosatelicie SpooQy-1. Źródło

Przybliżone tu wyniki grupy z Centrum Technologii Kwantowych w Singapurze, którego dyrektorem do niedawna pozostawał Polak prof. Artur Ekert, to z jednej strony zwieńczenie wielu lat intensywnej pracy a z drugiej preludium do kolejnych, jeszcze szerzej zakrojonych, kwantowych projektów kosmicznych.  Do następnych milowych kroków należą niewątpliwie przeprowadzanie kwantowej dystrybucji klucza pomiędzy dwiema nanosatelitami [5] oraz pomiędzy nanosatelitą a stacją naziemną [6].  Prace w tym kierunku, w szczególności w kontekście wykorzystania łatwiejszej wersji kwantowej dystrybucji klucza nie opartej na splątaniu kwantowym, już trwają. Ponadto, nanosatelitarne eksperymenty ze splątaniem kwantowym w warunkach orbitalnych otwierają możliwość do badań podstawowych, szczególnie w kontekście związku pomiędzy teorią grawitacji w fizyką kwantową.  Warte podkreślenia jest to, że dzięki wykorzystaniu platform typu CubeSat, projekty tego typu stają się możliwie do realizacji również w warunkach polskich.  W kierunku tym zwracamy się ramach działającego na Uniwersytecie Jagielloński w Krakowie zespołu naukowego Quantum Cosmos Lab.

Biblografia

[1] Aitor Villar, et al., Entanglement demonstration on board a nano-satellite, Optica 7, 734-737 (2020).
[2] J-G Ren et al., Ground-to-satellite quantum teleportation, Nature 549, 70–73 (2017).
[3] Zhongkan Tang, et al., Generation and Analysis of Correlated Pairs of Photons aboard a Nanosatellite, Phys. Rev. Applied 5, 054022  (2016).
[4] Artur K. Ekert, Quantum cryptography based on Bell’s theorem, Phys. Rev. Lett. 67, 661 (1991).
[5] Denis Naughton, et al., Design considerations for an optical link supporting intersatellite quantum key distribution, Optical Engineering 58(1), 016106 (2019).
[6] R. Bedington, et al., Nanosatellite experiments to enable future space-based QKD missions, EPJ Quantum Technology 2016 3:12 (2016).

         © Jakub Mielczarek

Artykuł został opublikowany na portalu Space24.

Co już potrafią komputery kwantowe?

jakub mielczarekLeave a comment

Internet stwarza szerokie pole do deformacji rzeczywistości. Sposobność ta nie oszczędziła komputerów kwantowych, które w ciągu ostatnich lat wyszły z laboratoriów badawczych do wielkiego świata, również tego wirtualnego.  Niestety, zderzenie praw fizyki kwantowej z prawami internetu (lub też ich brakiem), nie mogło obejść się bez szwanku dla samego przedmiotu naszego zainteresowania – komputerów kwantowych.  Kogo wszak interesują zawiłości techniczne, prawa natury, wyniki badań i analiz, czy też opinie specjalistów? Ważniejsze są przecież emocje bo to one podsycają zainteresowanie.  Te zaś przyczyniły się do wykreowanie obrazu komputerów kwantowych jako cudownych, ale i stanowiących zagrożenie, wszechmogących maszyn dostępnych już jakoby na wyciągnięcie ręki.

Co prawda, to przejaskrawienie pociągnęło za sobą większe inwestycje w technologie kwantowe. Nie oznacza to jednak czegoś jednoznacznie pozytywnego, ponieważ o ile wzmożone zainteresowanie przełożyło się na przyśpieszenie rozwoju technologii to wiotkie podstawy tego zauroczenia stworzyły zagrożenie wystąpienia patologii. W tym przypadku, istnieje chociażby ryzyko tego, że inwestorzy, nie koniecznie dysponujący specjalistyczną wiedzą z zakresu technologii kwantowych, podejmą decyzje inwestycyjne, w uproszczeniu, zwiedzeni tym, że pomysł zawiera słowo klucz – „kwantowy”. Wynikające stąd, rosnące i niespełniane oczekiwania pokładane w technologii mogą zaś wymuszać manipulacje w przekazach marketingowych, mające na celu wygenerowanie sprzedaży czegoś co nie dostarcza jeszcze bezpośrednich korzyści nad dostępnymi rozwiązaniami alternatywnymi. To zaś tylko wzmaga zafałszowanie przekazu, w szczególności tego wyłaniającego się w świecie wirtualnym.

Niestety, zjawisko takie dotknęło rodzącego się rynku komputerów kwantowych, który za wszelką cenę chciałby zacząć odrabiać poczynione niebotyczne inwestycje. Jest to koszt wyjścia technologii kwantowych poza sferę finansowania jedynie z grantów badawczych, nie narzucających wymogu bezpośredniego zwrotu z inwestycji. Oczywiście, nie dotyczy to jedynie technologii kwantowych, ale również innych nowych technologii wymagających ogromnych nakładów na badania i rozwój, takach jak chociażby technologie oparte na grafenie.

Z całego tego zgiełku, wyniknęło jednak ostatecznie coś dobrego. Mianowicie, pierwsze komputery kwantowe stały się dostępne niemal dla każdego.  Nie są one jednak tymi maszynami przed którymi ostrzegają nas doniesienia medialne o wykorzystaniu komputerów kwantowych do łamania szyfrów stosowanych w elektronicznych transakcjach bankowych. Na te będziemy musieli poczekać jeszcze kolejnych kilka dekad [1]. Dostępne już komputery kwantowe oferują bardzo ograniczone możliwości, nie wykraczające ponad to co dają nam te do korzystania z których przywykliśmy. Ponadto, borykają się one z trudnym do przezwyciężenia problemem dekoherencji kwantowej, znacznie ograniczającym ich obecną funkcjonalność, jak i możliwość dalszego skalowania. Pomimo tych przeszkód, możemy już dzisiaj zacząć naszą przygodę z obliczeniami kwantowymi, chociażby po to aby samemu przekonać się o możliwościach kwantowych maszyn. To co już da się z ich pomocą zdziałać postaram się zarysować poniżej.

Chciałbym jednak wcześniej podkreślić, że droga do miejsca w którym się obecnie znajdujemy nie była krótka. Komputery kwantowe nie wyskoczyły jak królik z kapelusza.   Może to zabrzmieć zaskakująco, ale już przed II wojną światową dysponowaliśmy aparatem teoretycznym niezbędnym do zaprojektowania komputera kwantowego. Tak już jest, że fizyka teoretyczna potrafi wyprzedzić inżynierię o dziesiątki, setki, czy nawet o tysiące lat.

Prawie już sto lat temu, w połowie lat dwudziestych ubiegłego wieku, stara teoria kwantów, do której zalicza się orbitalny model atomu Bohra, przekształciła się w mechanikę kwantową, taką jaką znamy ją dzisiaj. Ważnym krokiem w tym procesie było wprowadzenie przez de Broglie’a (1924) nowatorskiej koncepcji fal materii. Następnie, w 1926 roku, Erwin Schrödinger, zabrawszy pracę de Broglie’a oraz jedną ze swoich muz (nie kota), zaszył się na dwa i pół tygodnia w alpejskiej will, po czym pokazał światu, że rozchodzenie się fal materii można opisać równaniem matematycznym – znanym dzisiaj jako równanie Schrödingera.  Tego samego roku, urodzony w ówczesnym Breslau, Max Born zaproponował, że to co opisuje funkcja falowa to w istocie rozkład prawdopodobieństwa. Odsłoniło to probabilistyczną naturę mikroświata, która odgrywa ogromną rolę w technologiach kwantowych. Rok wcześniej, Born razem z Werner’em Heisenberg’iem wprowadzili równoważne sformułowanie macierzowe (operatorowe) mechaniki kwantowej, z którego na codzień korzystają obecnie programiści komputerów kwantowych. Związek mechaniki kwantowej z teorią informacji zaczął się zaś rysować dzięki pracom pioniera informatyki i fizyka matematycznego węgierskiego pochodzenia Johna Von Neumanna (rok 1932). Na odważny krok zaproponowania komputerów opierających swoje działanie na mechanice kwantowej musieliśmy jednak czekać do połowy lat osiemdziesiątych ubiegłego stulecia. Wtedy to, koncepcje taką zaczął poważnie rozważać, zafascynowany pierwszymi komputerami osobistym, znany wszystkim dobrze Richard Feynman [2]. Od tego czasu zaczął się wyścig w stronę zbudowania komputera kwantowego.

Na pierwsze prototypy musieliśmy poczekać kolejną dekadę. W konstrukcjach tych wykorzystano zjawisko jądrowego rezonansu magnetycznego (NMR), stosowane powszechnie w diagnostyce medycznej. Kierunek ten nie pozwolił jednak na stworzenie komputerów przetwarzających więcej niż kilka jednostek informacji kwantowej – tak zwanych kubitów [3].  Przełomowe okazało się wykorzystanie zjawiska fizycznego zwanego nadprzewodnictwem. Jest to zanik oporu elektrycznego niektórych materiałów ochłodzonych do temperatur bliskich zera bezwzględnego. Przykładem naturalnie występującego w przyrodzie nadprzewodnika jest pierwiastek Niob, który to przechodzi do fazy nadprzewodzącej w temperaturze poniżej 9.2 Kelwina. Jeśli z takiego materiału wykonamy pierścień i przepuścimy przez niego prąd elektryczny zadziała on jak elektromagnes, wytwarzając pole magnetyczne. Niezwykłe własności stanu nadprzewodzącego powodują jednak, że strumień pola magnetycznego przez taki pierścień może przyjmować tylko określone (skwantowane) wartości, podobnie jak poziomy energetyczne w atomie. Dwa najniższe energetycznie poziomy wykorzystuje się do stworzenia kubitu. To właśnie na tego typu nadprzewodzących kubitach opiera swoje działanie komputer kwantowy Sycamore firmy Google, na którym w ubiegłym roku po raz pierwszy wykazano eksperymentalnie przewagę czasową maszyny kwantowej nad klasyczną, wykorzystując 53 kubity [4]. Udało się tego dokonać dla tzw. problemu próbkowania (ang. sampling), sprowadzającego się do generowania ciągów bitów z rozkładu prawdopodobieństwa, który w przypadku komputera kwantowego jest określony przez sekwencję operacji wykonanych na kubitach. Komputery kwantowe oparte na kubitach nadprzewodzących rozwijają również firmy takie jak IBM, D-Wave i Rigetti Computing.

Artists-Rendition-Google-Quantum-Processor.
Artystyczna interpretacja komputera kwantowego Sycamore firmy Google.  Źródło

Od kilku już lat, proste (pod względem możliwości, nie zaś konstrukcji) komputery kwantowe działające na kubitach nadprzewodzących udostępnia potentat branży informatycznej – firma IBM. Każdy, za pomocą platformy online Quantum Experience, może spróbować swoich sił w programowaniu procesora 5 i 15 kubitowego. Istotnym ograniczeniem tych maszyn jest jednak nie tylko ilość dostępnych kubitów ale i długość tak zwanego czasu koherencji, który determinuje to ile operacji jesteśmy w stanie na nich wykonać. Niestety, pomimo ogromnej wykonanej pracy, dla procesorów kwantowych działajacych w oparciu o kubity nadprzewodzących, czasy te są nadal stosunkowo krótkie. Dlatego też, wciąż rozwijane są alternatywne kierunki, między innymi wykorzystujące fotony (np. firma Xanadu) oraz pułapki jonowe (np. firma IonQ).

Udostępnione przez IBM komputery kwantowe, nie dostarczają jak dotąd bezpośrednich korzyści obliczeniowych nad maszynami klasycznymi. Działanie komercyjnego 20 kubitowego komputera kwantowego IBM Q System One możemy emulować nawet na smartfonie. Wykładniczy charakter wzrostu ilości zmiennych potrzebnych do opisu stanu komputera kwantowego sprawia jednak,  że emulacji 100 kubitowego komputera nie bylibyśmy już w stanie przeprowadzić nawet na najpotężniejszym superkomputerze klasycznym. Przezwyciężenie problemów związanych z utrzymywaniem stabilnej pracy tych rozmiarów komputerów kwantowych pozwoli wejść w obszar niedostępny dla komputerów klasycznych.

IBM-Q-System-One
Design 20 kubitowego komputer kwantowy IBM Q System One może wzbudzać zachwyt.  Jednak, już nie jego możliwości, które da się osiągnąć na przeciętnym smartfonie.

Zanim to jednak nastąpi, warto zastanowić się nad tym co daje nam możliwość korzystania z istniejących już komputerów kwantowych. Moim zdaniem, do najważniejszych korzyści płynących z dostępu do tych maszyn należą: możliwość nauki pracy z komputerami kwantowymi,  poznawanie niedoskonałości które je charakteryzują i testowanie algorytmów kwantowych (w tym symulacji kwantowych). Zrozumienie niedoskonałości, przejawiających się w postaci błędów, pozwala opracowywać nowe i skuteczniejsze algorytmy tak zwanej kwantowej korekcji błędów. Na dostępnych komputerach kantowych możemy symulować proste kwantowe układy fizyczne, takie jak na przykład molekuły. Jest to domena chemii kwantowej, a symulacje takie pozwalają na przykład wyznaczać energie stanów podstawowych układów atomów. Wykorzystując komputery kwantowe, udało się to zrobić m.in. dla cząsteczki wodoru molekularnego [5]. W przyszłości, symulacje takie będzie można rozszerzyć do skomplikowanych molekuł, co może znaleźć zastosowanie w farmakologii.

Symulacje układów fizycznych na komputerach kwantowych prowadzone są m.in. w moim zespole Quantum Cosmos Lab, który działa na Uniwersytecie Jagiellońskim w Krakowie. Badania te skupiają się na symulowaniu nie zwykłych atomów, ale „atomów przestrzeni” z których może być zbudowana tkanka naszej przestrzeni. Korzystając z komputerów kwantowych firmy IBM, udało nam się pomyślnie zasymulować pojedynczy kwant przestrzeni [6]. Celem jest jednak to by symulować setki i tysiące takich cegiełek, co pozwoliłoby nam zbadań proces formowania się przestrzeni. Komputery kwantowe otwierają drogę do tego by faktycznie to zrobić, musimy się jednak liczyć z tym, że może nam to zająć kolejne 20-30 lat pracy, podążającej za rozwojem komputerów kwantowych.

Kolejna obiecująca możliwość jaka rysuje się za sprawą zastosowania obecnych i spodziewanych w najbliższych latach komputerów kwantowych to kwantowe generatory liczb losowych, wykorzystujące probabilistyczną naturę świata kwantowego. Generatory takie są szczególnie atrakcyjne ze względu na zastosowanie w rozwiązaniach kryptograficznych, związanych z cyberbezpieczeństwem, takich jak generowanie kluczy. Zaleta komputerów kwantowych leży w tym, że losowość wygenerowania klucza może zostać zagwarantowana (certyfikowana) niemożliwością zasymulowania algorytmu generatora na superkomputerze klasycznym.  Algorytmy generujące certyfikowane kwantowe ciągi liczb losowych wykorzystują obwody kwantowe, podobne do tych za pomocą których  firma Google wykazała, przywołaną wcześniej, korzyść (supremację) komputerów kwantowych.

Duże zainteresowanie budzi zastosowanie komputerów kwantowych w obszarach sztucznej inteligencji i uczenia maszynowego. W przyszłości, kwantowe algorytmy uczenia maszynowego mogą stanowić konkurencję do algorytmów klasycznych. Wskazuje na to szereg badań teoretycznych [7]. Jednakże, na chwilę obecną implementacje takich algorytmów są w bardzo wczesnej fazie. Na uwagę zasługuje przykład niedawno przeprowadzonej symulacji prostego modelu neuronu – tak zwanego perceptronu – na 5 kubitowym komputerze kwantowym [8]. Natomiast, dobrym punktem wyjścia do rozpoczęcia przygody z kwantowych uczeniem maszynowym jest platforma PennyLane, udostępniona przez firmę  Xanadu.

Na koniec, warto przywołać również przypadek tak zwanych adiabatycznych komputerów kwantowych. Komercyjnym przykładem takiego komputera są maszyny oferowane przez firmę D-Wave. Można do nich uzyskać dostęp online poprzez platformę Leap.  Komputery takie realizują wyspecjalizowany algorytm związany z poszukiwaniem stanu o najniższej energii (tzw. stanu podstawowego) dla układu kubitów. Algorytm ten pozwala podejmować szereg złożonych zagadnień, takich jak problemy optymalizacyjne i uczenie maszynowe. Komputery te są również doskonałym narzędziem do przeprowadzania eksperymentów fizycznych dla układów wielu atomów [9]. Pomimo dużej (rzędu 2000) liczby kubitów, zjawiska kwantowe ogrywają w nich inną rolę niż w omawianych wcześniej komputerach kwantowych (powodują tzw. tunelowanie kwantowe) i jak do tej pory nie wykazano by komputery te potrafiły rozwiązać problemy zbyt trudne dla superkomputerów klasycznych.  Programując je można się jednak, z pewnością, bardzo wiele nauczyć.

Niewątpliwie, żyjemy w bardzo ciekawych czasach, które można uznać za przedsionek do ery komputerów kwantowych. Pierwsze z nich są już dostępne do użytku za pośrednictwem platform internetowych, otwartych dla wszystkich chcących spróbować swoich sił w ich programowaniu. I choć nie dają one jeszcze bezpośredniej przewagi nad komputerami klasycznymi, pozwalają zmierzyć się ze światem mechaniki kwantowej i algorytmów kwantowych. Osobiście, bardzo cieszy mnie to, że dzięki komputerom kwantowych, niezwykły kwantowy świat, jak dotąd poznawany prawie wyłącznie przez fizyków teoretyków, zaczyna eksplorować coraz większa liczba śmiałków, w tym szczególnie dużo, otwartych na nowe wyzwania, młodych osób. Liczę na to, że to właśnie dzięki nim na dobre zadomowimy się w świecie komputerów kwantowych.

Bibliografia

[1] J. Mielczarek, Technologie kwantowe a cyberbezpieczeństwo, CyberDefence24, 2019.
[2] R. Feynman, QuantumMechanicalComputers, Optics News, Vol. 11, Issue 2, 11–20, 1985.
[3] L. M. K. Vandersypen, et al., Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance,  Nature 414, 883–887, 2001.
[4] F. Arute, et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505-510, 2019.
[5] Y. Cao, et al., Quantum Chemistry in the Age of Quantum Computing, Chemical Reviews, 119 (19), 10856-10915,2019.
[6] G. Czelusta,  J. Mielczarek, Quantum simulations of a qubit of space, arXiv:2003.13124 [gr-qc], 2020.
[7] J. Biamonte, P. Wittek, et al., Quantum machine learning, Nature 549, 195–202, 2017.
[8] Tacchino, F., Macchiavello, C., Gerace, D. et al., An artificial neuron implemented on an actual quantum processor, npj Quantum Inf 5, 26, 2019.
[9] R. Harris, et al.,  Phase transitions in a programmable quantum spin glass simulator,
Science, Vol. 361, Issue 6398, 162–165, 2018.

© Jakub Mielczarek

Artykuł został opublikowany na portalu Polish Brief.

Optyczny mózg

jakub mielczarekLeave a comment

Prędkość rozchodzenia się informacji (za pośrednictwem impulsów nerwowych) w mózgach ssaków sięga około 120 m/s. Wartość ta determinuje czas potrzebny na komunikację pomiędzy dowolnymi obszarami w mózgu i w konsekwencji czas reakcji na bodźce. To zaś, przy narzuconych przez środowisko zewnętrzne skalach czasowych, rzutuje na maksymalne dopuszczalne rozmiary mózgu. Przykładowo, informacja pomiędzy dwoma odległymi o 10 cm częściami mózgu podróżuje co najmniej milisekundę (0,001 s). Zachowanie tego rzędu czasów propagacji sygnału jest niezbędne do tego, żeby organizm mógł przetworzyć bodziec zewnętrzny i zareagować na niego w ułamku sekundy. Takie tempo rekcji umożliwiło naszym przodkom przetrwać w potyczce z dzikim zwierzęciem i prowadzić polowania. Dzisiaj jest to niezbędne chociażby do tego, żeby sprawnie kierować pojazdami.

O ile prędkość propagacji impulsów w naszych mózgach jest ograniczona biochemiczną naturą naszego hardware’u, to w przypadku systemów neuromorficznych – naśladujących działanie mózgu –  ogranicza nas jedynie maksymalna prędkość rozchodzenia się informacji w przyrodzie, równa prędkość światła w próżni, c\approx 299\ 794\ 458 m/s.  Jeśli udałoby się zasymulować działanie sieci neuronowych za pomocą światła, mogłyby one przetwarzać informacje około 2,5 miliona razy szybciej niż ludzki mózg. To zaś,  z jednej strony znaczy, że optyczny mózg mógłby być znacznie większy niż ten biologiczny.  Dla przykładu, przy zachowaniu minimalnej latencji sygnałów w ludzkim mózgu (~1 ms dla ~10 cm) rozmiary świetlnej sieci neuronowej mogą sięgać 300 km. Z drugiej strony, możliwe stałoby się osiąganie dużo większego niż w ludzkim mózgu tempa przetwarzania informacji. Hipotetyczny, optyczny symulator ludzkiego mózgu o rozmiarach naturalnych działałaby około 2,5 miliona razy szybciej od jej biologicznego odpowiednika. Jeden dzień funkcjonowania ludzkiego mózgu odpowiadałby więc około czterem setnym sekundy pracy optycznego mózgu. Jeden ziemski rok, odpowiadałby w symulacji optycznej około 13 sekundom. Natomiast, w świecie optycznym, symulacja naszego całego życia nie trwałoby dłużej niż dwadzieścia kilka minut!

Powyższe szacunki zaniedbują dodatkowe czasy wynikające z propagacji sygnału w innym niż próżnia ośrodku, jak i te związane z nieliniowym przetwarzaniem informacji optycznej, uwzględnienie których może być konieczne do symulacji realistycznych sieci neuronowych. Są one jednak wystarczająco miarodajne to tego, żeby uzmysłowić nam bardzo ważną z punktu widzenia człowieka własność sztucznej inteligencji. Mianowicie, może stać się ona nie tylko potężniejsza do ludzkiej, pod względem ilości przetwarzanej informacji ale i znacznie od niej szybsza. Z taką, tak zwaną, superinteligencją (Artificial Super Intelligence – ASI) trudno byłoby człowiekowi konkurować, ponieważ żyłby on w zupełnie innych skalach czasowych, nieprzystających do tych obowiązujących w wirtualnym świecie superinteligencji. Kiedy w świecie optycznej superinteligencji upłynęłoby 2,5 miliona lat, czyli czyli okres porównywalny z całą historią Homo sapiens na Ziemi, w zewnętrznym świecie ludzkim upłynąłby zaledwie jeden rok ziemski.

Wróćmy zatem na Ziemię. Superinteligencja to wciąż domena futurologii, natomiast prace nad optycznymi sztucznymi sieciami neuronowymi i ogólniej procesorami optycznymi trwają na dobre [1,2,3,4].  To samo dotyczy innych podejść do sztucznej inteligencji i symulacji ludzkiego mózgu. Można o tym poczytać w moich wcześniejszych wpisach O symulacjach ludzkiego mózgu i Dwanaście technologii jutra, gdzie m.in. przywołuję prowadzone obecnie symulacje wykonywane za pomocą tzw. procesorów neuromorficznych. Tutaj chciałbym jednak pozostać przy podejściu optycznym, które można uważać za rozwiązanie docelowe, zarówno ze względu na dyskutowaną powyżej możliwość osiągnięcia maksymalnej dopuszczalnej w przyrodzie prędkości przesyłania informacji, jaki i z uwagi na możliwość przetwarzania informacji z niedostępną innymi metodami częstotliwością. Ponadto, podejście optyczne w sposób naturalny otwiera drogę do implementacji tak zwanej kwantowej sztucznej inteligencji (ang. quantum artificial intelligence) [5,6,7], ale o tym przy innej okazji.

Chociaż mogłoby się wydawać, że optyczna sieć neuronowa to nieuchronnie coś bardzo skomplikowanego i kosztownego, to prostą optyczną sieć neuronową może zbudować dosłownie Każdy, korzystając z powszechnie dostępnych elementów do budowy światłowodowych sieci internetowych. To zaś jak można to zrobić zarysuję poniżej i posłużę się tym przykładem do omówienia kilku wybranych aspektów optycznych implementacji sieci neuronowych.

20200317_113414
Prototyp optycznej sztucznej sieci neuronowej opartej o światłowody jednomodowe oraz dzielniki mocy (splittery). Źródłem światła jest laser, pracujący na długości fali 650 nm.

Do konstrukcji optycznej sieci neuronowej będziemy potrzebować sztuczne neurony oraz połączenia pomiędzy nimi. Te drugie możemy zrealizować wykorzystując światłowody, stosowane do komunikacji optycznej. Odcinki takich światłowodów można ze sobą łączyć stosując odpowiednie adaptery. Medium transmisyjne wykorzystywane w światłowodach to przeważnie domieszkowane szkło kwarcowe, dla którego współczynnik załamania n \approx 1.46, co daje prędkość propagacji sygnału v=c/n \approx 205\ 000 km/s, czyli około 70 \% prędkości światła w próżni.

Funkcją neuronów jest zbieranie sygnałów wejściowych z synaps i wytworzenie na ich podstawie sygnału wyjściowego. W biologicznych sieciach neuronowych, dodatkowym aspektem jest wytworzenie tak zwanego potencjału czynnościowego (ang. spike). Możliwość wytwarzania spike’ów jest brana pod uwagę w symulacjach mózgu, w szczególności z wykorzystaniem systemów neuromorficznych. Natomiast, są one zazwyczaj pomijane w uproszczonych modelach sieciach neuronowych stosowanych w uczeniu maszynowym. W tym przypadku, działanie sztucznego neuronu polega na zsumowaniu, z odpowiednimi wagami (synaptycznymi), sygnałów wejściowych i przetworzeniu takiej sumy przez tzw. funkcję aktywacji, otrzymując w ten sposób sygnał wyjściowy. Otrzymany sygnał jest następnie podawany na wejścia innych neuronów, lub też, na wejście tego samego neuronu. Do sytuacji bez tego typu pętli zalicza się sieć typu feedforward, na której skupimy poniżej naszą uwagę.

Najprostszą realizacją optycznego neuronu jest przypadek z liniową funkcją aktywacji,  dla którego neuron jest niczym innym jak sumatorem sygnałów wejściowych. Pomimo swojej prostoty, model ten jest wystarczający do tego by uchwycić podstawową ideę przetwarzania informacji przez sieć neuronową. Realizacją optyczną  neuronu-sumatora jest rozdzielacz (ang. splitter) światłowodowy. Dodatkowo, wagi na “synapsach” takiego optycznego neuronu można modyfikować stosując odpowiednio dobrane tłumiki mocy. W rozwiązaniu prototypowym widocznym na zdjęciu powyżej, wykorzystano standardowe rozdzielacze i połączenia stosowane przy budowie sieci światłowodowych. Całość układu można jednak znacząco zminiaturyzować stosując zintegrowane obwody fotoniczne, zawierajace sieci miniaturowych sztucznych neuronów.

Istota działania sieci neuronowych sprowadza się do wykrywania wzorów. Mogą to być zarówno wzory graficzne, dźwiękowe, lub też bardziej abstrakcyjne wzory związane z przetwarzaniem języka i wyższymi funkcjami poznawczymi. Rozpoznawanie wzoru w sieci neuronowej realizowane jest warstwowo. Żeby to zobrazować, posłużmy się przykładem rozważanej sieci optycznej,  z szesnastoma neuronami w warstwie wejściowej. Neurony te będą reprezentować 16 pikseli na mapie bitowej o rozmiarach 4×4. Łącznie mamy więc 2^{16} = 65536 możliwych binarnych konfiguracji wejściowych. W przypadku optycznym, stan “1” danego bitu oznacza wprowadzenie do obwodu światła o ustalonej mocy. Stan “0” to brak światła.  Ponieważ, w ogólności, możemy zmieniać w sposób ciągły natężenie świtała, dopuszczalnych analogowych stanów wejściowych jest nieskończenie wiele. Tutaj jednak, dla uproszczenia, zawęzimy rozważania do stanów binarnych.

Kolejna warstwa, a  zarazem jedyna tzw. warstwa ukryta, wykrywa  8 liniowych wzorów składowych, wynikających z zsumowania wybranych czterech pikseli w warstwie pierwszej. Są to pośrednie wzory z których w ostatniej (trzeciej) warstwie komponowane są wzory które nasza sieć ma za zadanie rozpoznać. Sytuację tę przedstawia rysunek poniżej:

Netork
Graf reprezentujący połączenia w prototypowej optycznej sztucznej sieci neuronowej, rozpoznającej wybrane 4 wzory na bitmapie o rozmiarach 4×4.

Zaprezentowany tu przykład optycznej sieci neuronowej jest niezwykle prosty i opiera się na dzieleniu mocy sygnałów optycznych. Z uwagi na liniowość funkcji aktywacji, uzasadnione było zastosowanie tylko jednej warstwy wewnętrznej. W celu wykrywania bardziej skomplikowanych wzorów, konieczne jest wprowadzenie nieliniowych funkcji aktywacji (np. sigmoidalnych) oraz większej ilości warstw. Wyzwanie to jest podejmowane w wielu aktualnych pracach nad optycznymi sieciami neuronowymi, zarówno klasycznymi, jak i tymi wykorzystującymi kwantową naturę światła.  Nad wdrożeniami takich rozwiązań pracują m.in.  takie startupy jak LightMatter i Xandu.

Implementacje te dotyczą “wąskiej” sztucznej inteligencji (Artificial Narrow Intelligence – ANI) nie zaś symulacji nakierowanych na stworzenie ogólnej sztucznej inteligencji (Artificial General Intelligence – AGI), nie wspominając nawet o superinteligencji. Faza ANI jest jednak przedsionkiem do dalszego rozwoju podejścia optycznego w kierunku AGI i ASI.  Warto ostatecznie podkreślić, że przetwarzanie informacji za pomocą światła rozważane jest nie tylko w kontekście sieci neuronowych, ale również (a obecnie nawet przede wszystkim) w kontekście akceleratorów optycznych, przyśpieszających działanie procesorów o standardowej, nieneuronalnej,  architekturze. Ponadto, korzyści płynące z wykorzystania światła nie polegają wyłącznie na wysokiej prędkość propagacji sygnału. W standardowym przewodzie elektrycznym, prędkość rozchodzenia się impulsu elektromagnetycznego jest również porównywalna z prędkością światła w próżni. Problemem jest natomiast dyssypacja energii w układach elektronicznych, która rośnie wraz z częstotliwością przetwarzania informacji.  Problem odprowadzania wytworzonego w ten sposób ciepła okazał się na tyle trudny, że częstotliwość taktowania naszych komputerów pozostaje praktycznie niezmieniona od przeszło dziesięciu lat i wynosi maksymalnie ~3,5 GHz. Wykorzystanie światła jako nośnika informacji otwiera drogę do wyjścia z tego impasu. Więcej informacji na ten temat można znaleźć w poniższym filmiku oraz w artykule [4].

Chciałbym na koniec dodać, że opisana tu przykładowa optyczna sieć neuronowa powstała dzięki zasobom Garażu Złożoności i Quantum Cosmos Lab, działających na Uniwersytecie Jagiellońskim. W ramach tych dwóch przedsięwzięć planujemy kolejne projekty związane z systemami neuromorficznymi, w szczególności opartymi o optyczne przetwarzanie informacji. Osoby zainteresowane współpracą w tym obszarze zachęcam do kontaktu.

Bibliografia

[1] R. Hamerly, L. Bernstein, A. Sludds, M. Soljačić, and D. Englund  Large-Scale Optical Neural Networks Based on Photoelectric Multiplication Phys. Rev. X 9, 021032 (2019).
[2] Xiao-Yun Xu  et al. A scalable photonic computer solving the subset sum problem, Science Advances,  Vol. 6, no. 5, eaay5853 (2020).
[3] Y. Zuo, B. Li, Y. Zhao, Y. Jiang, Y. Chen, P. Chen, G. Jo, J. Liu, and S. Du, All-optical neural network with nonlinear activation functions, Optica 6, 1132-1137 (2019).  
[4] K. Kitayama et al.,  Novel frontier of photonics for data processing – Photonic accelerator, APL Photonics 4, 090901 (2019)
[5] G.R. Steinbrecher, J.P. Olson , D. Englund et al. Quantum optical neural networks, npj Quantum Inf 5, 60 (2019).
[6] F. Tacchino, C. Macchiavello, D. Gerace et al. An artificial neuron implemented on an actual quantum processor, npj Quantum Inf 5, 26 (2019).
[7] J. Biamonte, P. Wittek, N. Pancotti et al. Quantum machine learning. Nature 549, 195-202 (2017).

© Jakub Mielczarek