Quantum is being really heavily hyped at the moment and even my good self has been caught up in some of the Hoo-ha around it! Specifically which parts of Db2 are not “quantum safe”?
Quantum?
Yep, not like the TV Series “Quantum Leap” at all! The idea of quantum data goes back many, many decades but has only recently really started earning a living instead of being a scientific curiosity! There are six basic concepts that you must know a little about to start to “grasp the basics” of Quantum Computing.
Have you Qubit off more than you can chew?
The most important bit about quantum computers is the fact that they have qubits and not bits! The difference is staggeringly huge and mind-bendingly weird but boils down to the simple fact that a bit can be 0 (off) or 1 (on) – That’s it folks! On the other hand, a qubit can be anywhere between 0 (off) and 1 (on), in fact an infinite number, and it gets weirder when you have more qubits to play with. They do not join linearly but exponentially! This means that with 1,024 Qubits you have a mind-meltingly high number of possible values.
Ice Ice Baby!
You gotta keep qubits cold and I mean really cold… best is 0o Kelvin (Absolute zero) which is pretty nippy in July! For me in Germany that is -273.15o Celsius and for those of you “over the pond” a very large negative number of Fahrenheit! Ok, the actual number is -459.67o Fahrenheit. Naturally, we never can reach 0o Kelvin but we can get pretty close these days and at this temperature it minimizes error rates and enables superconducting behavior as well. The warmer they get the more they are prone to losing their quantum state, or decoherence in the jargon.
Superposition – the first Concept
Qubits are in a superposition of all possible values between 0 and 1 until they are measured. Then they snap back, the quantum state collapses is the correct term, and resolve to a 0 or 1 – This gives you the “answer” if you like. We can never fully predict the outcome but we can calculate the probability of a given outcome.
Entangled – the second Concept
Entanglement is crucial to getting Quantum computers to do any meaningful work for us humans. It is, at a minimum, two particles that are paired up in such a way that the quantum state of one particle cannot be determined independently of the state of the other, irrespective of the distance between the two. In other words, you can work out the quantum state of a particle when it is a light year away from its partner! Einstein famously wrote in 1947 about “spukhafte Fernwirkung”, in English “spooky action at a distance” as he could not believe this! But it has now been proven over and over that entanglement does happen and with many more than just two qubits.
Exponential speed-up?
Using entanglement puts two or more qubits into a single shared quantum state, so they stop behaving independently and combined with interference (coming up) that is where the real speed-up lives. Please also remember that measuring one does instantly pin down the others, but no usable information actually travels faster than light. For one qubit we have probabilities distributed over two states. For two qubits the distribution goes over four states, for three qubits it is eight states etc. In general, the rule is for N qubits the probability is over 2n states.
Interference – the third Concept
We have all thrown stones into a pond or the sea and seen the ripples spread outwards. When the waves bounce back from the edge of a wall or boat you might have noticed that the waves interact with each other. When the peaks meet, you get a big wave. When troughs meet, you get a big hole. And when a peak meets a trough – nothing.
Give us a Wave!
In the quantum world this a wave function which is a mathematic description based on polynomials. To measure the entangled qubits, you just add the individual wave functions for every qubit until you have a single wave function of a single quantum state. This adding of the wave function gives us an interference pattern where we can change probabilities of the correct answer by using constructive interference (The peaks of the wave add up) or reduce the probability of a wrong answer by using destructive interreference (Where the two waves cancel each other out).
Tunneling – the fourth Concept
Now it gets weird! (Only now, you ask? Well …) This is where an object can pass through an energy barrier that within normal classical physics it should not be able to pass through! Think of a high mountain and then imagine that someone has bored a tunnel at the base of the mountain right on through. If the object can use the tunnel, it will make it much faster to the other side! Remember, the wave function is a probability so when this function encounters a potential barrier and if the barrier is thin enough it can indeed tunnel through and then there is a chance that the particle will appear on the other side.
Examples abound!
Nuclear fusion in stars is where protons overcome their electrostatic repulsion which allows the sun to shine, or radioactive decay where Alpha particles tunnel out of the nucleus. Modern electronics rely on this phenomena for tunnel diodes which were invented in 1957, for scanning tunneling microscopes invented in 1981 and also for flash memory as well.
Synchronization – the fifth Concept
We have all been to concerts where people start clapping. At some point all the clapping synchronizes and gets very loud! This is where the wave functions of independent particles can all “march to the same beat” and spontaneously synchronize – this is very important when using certain algorithms.
Quantum Parallelization – the sixth Concept
Behind this is the really weird idea of parallel universes where each universe does one calculation and with N parallel universes the time of one calculation is enough for *all* calculations. At the moment of “observation” the qubit ends in a “collapsed” state and you get a result. This is also used in quantum chip design where the second, or more, input can be influenced by the first input!
The Traveling Salesman gets his Route!
The Traveling Salesman is a very old problem, from 1930, where you must calculate the optimal route for a poor traveling salesman to visit N cities with the shortest route, visit each city only once and return to the starting city. It sounds “easy” but is actually NP-Hard. In math terms this means it is not solvable in polynomial time and for every city added the time goes up exponentially. If you have three cities anyone can do it but when you have just 20 it gets practically unsolvable!
Give me numbers!
A raw brute force “try every possible route” approach takes a running time within a polynomial factor of O(n!) where O is the Order of growth in Landau notation – fittingly, it comes from the German word “Ordnung” (Order). So you can see that after 20 Cities the numbers get silly. The Held-Karp algorithm from 1962 solves it in time O(N22N) whereas the latest quantum algorithm from Ambainis et al. from 2019 runs in just O(1.728N).
| Cities | Brute Force | Held-Karp | Quantum |
| 3 | 6 | 72 | 5 |
| 10 | 3,628,800 | 102,400 | 237 |
| 20 | 2.43 x 1018 | 419,430,400 | 56,347 |
As you can clearly see, Quantum Computers will greatly help with this problem and all derivatives in logistics, and DNA sequencing, for example. Note that the quantum solution is still exponential but just not as bad as before as it is a NP-Hard problem after all!
Spinning on your Heels?
To get this level of improvement the Quantum Computer uses an Ising Machine where spinning particles are each a city and they will eventually all synchronize on the most efficient path. Calibration is on various factors but for the Traveling Salesman problem it is on distance.
Now we are Experts – Why?
Factoring of numbers is the number one reason, as of today, for doing all this! But, unlike the Traveling Salesman, factoring is not actually NP-Hard – it sits in a curious middle ground, and it is exactly that hidden structure a quantum computer can exploit (quantum computers are not believed to crack genuine NP-Hard problems). Encryption is basically two large prime numbers multiplied together. Computers can do that very easily! Going back, or factoring, from a huge semi-prime number to the two starting primes is, however, very difficult for a classic computer. Shor’s algorithm lets a quantum computer recover those prime factors efficiently – not by trying everything at once, but by exploiting interference – and that breaks the public-key (asymmetric) encryption such as RSA and ECC which protects key exchange and digital certificates.
Grover’s Algorithm
Lov Grover created this in 1996 and it is basically an enhanced search with O(√N) evaluations but it can brute-force a 128-bit key in 264 iterations or 256-bit in 2128 iterations. It is quadratically better than simple brute-force and there are improvements on their way – especially the class of non-local hidden variable quantum computers could do the search in O(∛N) – the cube root of N – evaluations instead of O(√N) evaluations!
Finally Db2!
Yeah! I made it nearly to the end before even getting into the reason for the newsletter!!! The problem is that all of our data is encrypted, most of you are using 128-bit keys which are ok and are still pretty hard to crack. Anything less than 128-bit keys is crackable now in a brute force attack. The recommended way forward and to remain “Quantum Safe” is to change all your encryption today to use at least 256-bit keys. These will be safe from Quantum Computers for a long time.
Post-quantum…
One nuance worth stating plainly: the Db2 ENCRYPT and HASH functions listed below are symmetric, where a quantum computer (Grover) only halves the effective key strength – so moving to 256-bit gives you 128-bit of real protection and is exactly the right fix here. The factoring threat from Shor described above instead breaks asymmetric public-key crypto such as RSA and ECC, where larger keys do not help and post-quantum algorithms are required – that protects your TLS handshakes and certificates and is a separate piece of work.
How long is long?
The so-called Q-Day is expected in 2030 when anyone with a Quantum Computer can then read all the data you are *now* storing…
Stuff to do, then?
Yes indeed, any use of the following is no longer really secure for “tomorrow” anymore and steps must be taken to raise the level of encryption. If any of the following scalar functions are being used in your shops it is time to start a project group “Quantum Safe Encryption”:
DECRYPT_BINARY
DECRYPT_BIT
DECRYPT_CHAR
DECRYPT_DB
ENCRYPT Triple Data Encryption Standard 128 Bits
ENCRYPT_TDES Triple Data Encryption Standard 128 Bits
HASH(xxxx) Message Digest 5 128 Bits
HASH(xxxx,0) Message Digest 5 128 Bits
HASH(xxxx,1) Secure Hash Algorithm 1 160 Bits
HASH_CRC32(xxxx) Cyclic Redundancy Check 32 Bits
HASH_MD5(xxxx) Message Digest 5 128 Bits
HASH_SHA1(xxxx) Secure Hash Algorithm 1 160 Bits
Replacements, please!
If you find any of these in your SQL workload you must get the application teams to replace them with:
DECRYPT_DATAKEY_type With the new full list of types.
ENCRYPT_DATAKEY(xxxx,
key-label-name,
AES256R or AES256D) All 256 Bits. Using AES256D enables EQUAL
usage as the same value will encrypt to the
same encrypted value but is not as secure
as AES256R.
HASH(xxxx,2) Secure Hash Algorithm 2 with 256 Bits
HASH_SHA256(xxxx) Secure Hash Algorithm 2 with 256 Bits
The highest Bits have it!
As you can see, anything less than 256-bit keys is nowadays not deemed “Quantum Safe” which means someone will be able to easily decode your emails, data, transactions, logs etc. when that Q-Day comes – and it may come sooner than you would think or like!
Not easy to do!
So now, if you find any of these functions you must decrypt the data and then re-encrypt the data with one of the 256-bit keys so you are “safe for a while” – Of course how long we will be “Quantum Safe” with 256-bit keys is a very open question indeed!
Finally a small course from IBM
Here’s a nice intro to all of the above from IBM.
TTFN,
Roy Boxwell