• Milos Dunjic, AVP, Payments Innovation Technology at TD Bank Group


• 13.05.2018 05:15 am
#QuantumComputing , #QuantumMechanics , #cryptography , #security , #encryption , Milos has over 25 years of experience in senior technology roles having developed and launched innovative, commercially successful and award winning digital payments solutions based on mobile and chip card technologies. Winner of the TD Bank Group's "2017 Inventor Of The Year" Award. Milos holds a Master’s degree in Electrical Engineering with major in Computer Science from the University of Belgrade. Opinions are his own, not of his employers

Why Should Everyone Pay Close Attention to Quantum Computing?

For over a year now, I have been uncovering the secrets of quantum computing, which is an exciting and rather unusual field of informatics. It is somewhat weird and yet extremely fascinating discipline, by being very, very different than anything I have learned or encountered so far in my career, as a software developer and high-tech executive. Last week I had privilege to participate on The Quantum Panel, as part of the Payments Canada conference.

You may wonder how this could be so relevant to payments innovation, which was and still is my main focus, for almost a decade now? As scientific field that is still very much in its infancy, quantum computing is also rapidly developing and maturing. It will likely impact all security we have built and relied on so far. It is not anymore question of IF, but WHEN is that going to happen. 

The business of electronic payments is based on trust, basically on being able to protect the communication channels and storage of sensitive information - like user authentication credentials, account numbers, personally identifiable information, etc. This is not an easy task, as there are many dishonest actors, who would be more than happy to take advantage of any security holes left behind, and benefit from stealing someone’s identity, money, etc.

The Current State of The Cryptographic Art

In order to secure the financial system, including payments, we rely on the special area of mathematics and number theory, known as cryptography. Clearly, solid cryptography is not guarantee alone. There can always be insiders, who might be bribed (or simply disgruntled) and leak the secrets to an adversary. However, without help of rock solid cryptography, we would not stand even a slightest chance.

Today’s cryptography falls into 2 main categories: symmetric and asymmetric (also known as Public Key Infrastructure or PKI).

Symmetric cryptography is based on a principle that the same secret key is shared by all parties (sides) of the communication. The same key is also used for both encryption and decryption. Example of symmetric cryptographic algorithms would be DES (today there is stronger version known as triple-DES or 3DES) and AES. Various symmetric key sizes are mandated to make it unbreakable by brute force. As long as all participants can secretly agree on a secret key value and keep it secret, all is good. But that’s not easy to achieve, especially if those parties are remote from each other and / or if they can’t necessarily trust each other.

Asymmetric cryptography is based on principle that every participant has their own key pair, which is comprised of PUBLIC and PRIVATE key components. Participant’s public key can be shared with anyone else, while private key must stay protected. Public key is used for encrypting information and the corresponding private key is used for decrypting. On the other hand, private key can be used to digitally sign the information, as a proof of non-repudiation and public key can be used to verify that digital signature. Public and private keys are tightly mathematically related, in a way, that it is practically impossible to reverse engineer private key from the corresponding public key, by using classic computers, in any usable timeframe. By some estimates, even by using todays most powerful supercomputers, one would need several billion years to reverse engineer private key from RSA public key that is at least long 2048 bits (or 256 digits). This is in fact fantastic news, as it means that we can freely share our public key with anyone we want to communicate, without fear that they will be able to figure out our private key value. Two most popular PKI cryptography algorithms are RSA (acronym for Rivest, Shamir, and Adelman, the inventors) and ECC (acronym for Elliptic Curve Cryptography).

For secure internet communication used in e-commerce, mobile / online banking and B2B / P2P payments communicating parties use the combination of symmetric and asymmetric cryptography. In simple terms, they first exchange with each other their public keys. Then each side combines their private key and the other party’s public key, and uses well-known algorithm (Diffie-Hellman), to generate the secret ‘session’ symmetric key that is used to encrypt and decrypt the messages, during the lifetime of that particular communication session.

Why can’t today’s classical supercomputers reverse engineer private key from the public key, even with those two keys tightly related? Because classic computers are highly iterative in nature. If you imagine a single memory register that is 2048 bits long, it can hold only one of the possible values from the range [0 … 2²⁰⁴⁸-1], at each moment in time. That means that classic computer can basically only manipulate a single value at a time. You also intuitively feel that 2²⁰⁴⁸ is an awfully large number (about as large as 10⁶⁸²). Now, in order to process that large value range, only single value at the time, even with today’s ultra-fast CPU clock speeds, it will effectively take an infinite amount of time. Certainly, a lot longer than the usefulness of the information we were trying to protect in the first place. That inability of mainstream modern classic computers (even supercomputers) to process and examine very large ranges of values and discover any secret patterns or rules buried in there, is basically the strong foundation behind all of today's electronic security.

The Quantum Computing Threat

However, quantum computers are completely different type of machines. They differ from classic computers, first and foremost, because they are governed by and can take advantage of the laws of the sub-atomic world, known as quantum mechanics. In quantum world, bits are called Qbits and they can be implemented in variety of ways, for example as photons polarized in different ways, or electrons spinning in different directions, etc.

According to the laws of quantum mechanics, each Qbit can be in both states ‘0’ and ‘1’ at the same time, with equal probability amplitude. Following the same logic, a hypothetical quantum register, long 2048 Qbits, can be at the same time, in all of the possible states from the [0 … 2²⁰⁴⁸-1] range (known as ‘linear superposition’). This also means that on quantum computer, the same mathematical transformation can be applied to all of the linear superposition states from the [0 … 2²⁰⁴⁸-1] range, all AT THE SAME TIME.

Next, according to the same laws of quantum mechanics, each Qbit behaves as a ‘quantum wave’, and those Qbits can be creatively manipulated to constructively interfere (i.e. ‘add up’ their quantum wave amplitudes) or destructively interfere (i.e. ‘cancel out’) for certain states of the linear superposition.

Last but not the least, pair of Qbits (or even whole Qbit registers) can be made to be entangled, so that changes made in one register immediately set the state of its ‘entangled brother’ in certain way, governed by the laws of quantum mechanics.

All of these characteristics, combined together, give quantum computers huge and unfair advantage over classic computer ‘cousins’ – especially for certain types of mathematical problems, which are ultra-hard to be solved using classical computers alone.

Breaking the RSA Cryptography with Quantum Computers

Unfortunately, breaking the PKI cryptography (both RSA and ECC type), is one of those examples of mathematical problems, which may be ultra-hard for iterative classical computers, but are very natural and easy for quantum computer, given large enough number of Qbits.

The RSA algorithm’s security is based on inability of classic computers to discover which two distinct prime numbers p and q were multiplied to produce very large value n (called modulus). The currently used length of n is 2048 bits. The values of prime numbers p and q, are also used to calculate the private exponent e_s and public exponent e_p. The public key is then pair of values [n, e_p], while private key is pair of values [n, e_s].

Peter Shor, a mathematician and cryptographic scientist, back in 1994, had formulated an algorithm, which can combine steps executed on classical computer, together with steps executed on quantum computer, for efficiently finding the prime factors p and q of a given large number n, thus effectively breaking RSA’s security.

First thing Shor realized, based on his extensive understanding the number theory, was that ability to factor n into p and q, is in fact related to the ability to find the period of a special function

f(x) = (a^x mod n), for x = 0, 1, 2, 3, ...etc

where integer a < n, such that gcd (a, n) = 1, and ‘gcd’ stands for ‘greatest common divisor’. The period is defined as the smallest integer r, such that

f(x) = (a^x mod n) = f(x+r) = (a^x+r mod n)

i.e. results of applying f(x), would start repeating after r steps.

Once the period r is found out, the target q and p values can easily be calculated, using the classic computer, as:

p = gcd (n, a^r/2 – 1)

q = gcd (n, a^r/2 + 1)

Finding the period of f(x) = (a^x mod n) function is extremely difficult computational problem to be solved iteratively, when n is very large number (for example, 2048 bits long), because it is not smooth periodic function and the results of f(x) look rather like random noise to classic computers.

However, for the quantum computer, having couple of large enough of Qbit registers, and due to its unique quantum mechanics characteristics mentioned above, this is a very natural problem to solve. That’s is exactly what Peter Shor proposed.

On a very high level, without going into real details of his exact algorithm, and greatly simplified, Shor basically proposed following:

• applying f(x) = (a^x mod n) function to a linear superposition of Qbit register states in one of the Qbit registers
• creatively producing (and detecting using Quantum Fourier Transform) constructive interference between Qbit waves of that register and another register, entangled with it
  • Constructive interference is basically produced for states equal to the period r (or multiples of the period r), while destructive interference happens for all other states.

Pure genius. Done. RSA security can be broken, in a matter of hours, as long as there is readily available access to a stable quantum computer, with two registers and enough number of Qbits in each.

Shor then went on further and specified an algorithm for cracking the ECC security as well, by using quantum computations for similarly critical steps (in this case it was ‘discrete logarithm calculation’), another ultra-hard mathematical problem for classic computer to solve.

Conclusion

Should we be worried now? Comforting news is that currently, quantum computers with such large Qbit registers do not exist yet. However somewhat discomforting is that quantum computing field is rapidly developing, with major world powers and all high technology giants (Apple, Google, Microsoft, IBM, etc) actively funding their own quantum computing research and are collaborating with advanced university institutes specialized in quantum computing. We now already have experimental quantum computers with close to 100 Qbits available. That’s how Shor’s algorithms have been proven to actually work in practice. Microsoft is even developing high level programming language called Q#, having its own IDE. Educated forecasts speculate that within a decade, we can expect to have quantum computers with large enough Qbit registers, available for cracking 2048-bit long RSA keys. Especially if bad actors get access to them.

There is lot at stake here, basically the electronic security of the whole financial system may potentially be invalidated in about 10 years from now, if quantum computing progresses without alternative quantum-safe PKI algorithms emerging in parallel. Even with quantum-safe PKI cryptographic algorithms becoming available, the industry must plan for orderly transition and replacement of the legacy RSA and ECC algorithms with new, quantum safe equivalents.

This upgrade is not going to be an easy and trivial task, as RSA and ECC algorithms are embedded in all today’s protocols like VPN, SSL/TLS and payment protocols like EMV, etc. The right time to start planning and acting is NOW. Financial industry needs to be proactive and engage with quantum computing experts from universities, private research facilities and high-tech giants, in order to stay well ahead of the curve and avoid being caught by surprise.

Ten years will fly by, very quickly. Before we realize, the decade will be over. Let’s not hope someone else will solve these issues, because no stakeholder can stay isolated and hope they will not be affected, because they will. Also let’s not hope that we can protect access to future quantum computing by using today's legacy PKI :-)