Crypto Systems Which Resist Quantum Computers

by Dave D'Rave

Previously, I described how trends in quantum computer technology are likely to result in the total loss of security for mainstream crypto systems such as AES and DES.

In this article, we will look at crypto methods which are resistant to known algorithms used in quantum computers.

One-Time Pad

One-time pad encryption appears to be completely secure against quantum computers.  Unfortunately, this system suffers from extreme key distribution problems.

Quantum Cryptography

Quantum cryptography is a term for various technologies which use entangled photons to send information such that it detects any eavesdroppers in real time.

Such systems are highly resistant to attack by quantum computers, as long as proper operating procedures are followed.  Encrypted fiber optic systems which use quantum cryptography are currently being sold commercially.  These are semi-practical, in that they require a dedicated fiber optic cable between the two endpoints, and in that they cannot be used for encryption of stored data.  It is possible that future variants on the idea of quantum cryptography will allow information to be sent over a public network, or that a longterm stable method of storing Bell-state qubits will be developed.

The other problem with quantum crypto is, well, hackers.

For details, just go onto YouTube and do a search for "Vadim Makarov" or just go here: www.vad1.com/lab.  As my redneck friends used to say, "If one monkey can build it, another monkey can break it."

Exploiting Weakness in the Quantum Algorithms

Many of the proposed algorithms for breaking crypto systems use either a quantum Fourier transform or some kind of amplitude amplification algorithm.  The weakness in both cases is that these algorithms work a lot better if there is one and only one right answer.

Consider the case where we are using Grover's algorithm to perform a known plaintext attack on a given cryptogram.  The general situation is that the system starts with a state vector in the solution space.  We measure the error between the trial vector and the target vector, and produce a new state vector (named state vector 1).  Then, repeat using the new state vector.

Typically, each iteration produces a vector which is closer to the solution, and a relatively small number of iterations will provide the answer.  (Yes, I am leaving a lot of stuff out.  This is not a review article.)

Now consider a crypto system such that the cyphertext can be decoded using any of four different keys.

When the quantum computer attempts to find the current error vector, it will get a superposition of four vectors.  Depending on the details of how the algorithm works, this will either collapse to one of the four values, or will collapse to some weighted average value, or will produce some superposition of answers.  Each iteration of the error-and-update cycle will typically move the vector in a random direction, and the algorithm will never converge to a solution.

Multiple-valid-key coding systems have a similar effect on quantum Fourier transform algorithms.

When using such a system to break DES, the expected code space contains one valid decryption and (2⁵⁶ - 1) invalid decryptions.  These have been scrambled in digital phase space using some transform.  The quantum computer is going to perform an inverse transform on the superposition of all 2⁵⁶ possible decryptions, and then use Fourier transform methods to identify the one we want.

This method works on DES, because DES only supports one correct decryption key.

If we use some alternative algorithm which allows a large number of equally valid decryption keys, then the Fourier transform will produce an output which is some kind of superposition of the valid keys' descriptions.  If the number of valid keys is large enough, this output will be unintelligible.

Multiple Valid Key Code Systems

Multi-key crypto systems have the characteristic that a given cyphertext can be decoded into the correct plaintext by using any one of a number of keys.

For example, we could have a system which uses 512-bit blocks of data, and a 1024-bit key, such that 2⁵¹² of the possible keys are valid.

For a conventional computer using a brute-force attack, this would be equivalent to a key size of 512, since attempting 2⁵¹¹ keys would give a 50 percent chance of guessing the plaintext.  For a quantum computer, having this many correct results in the code space would restrict the number and type of algorithms which could be used.

Multiple valid key systems can be implemented by using RSA-type algorithms such that, instead of using two large prime numbers, you would use n (where n is something like 16) large prime numbers.  If the decryption problem requires that a given large number be factored, it would only require that one of the factors be known.

Another class of multiple valid key systems involves the use of error-correcting codes, such that a key which produces a decode which is close to the plaintext will work, after the error correction operation has been applied.  (Note that modern block cipher systems, such as AES and DES, have excellent entropy properties.  There will be no general way to find the other members of the key set, given one of the valid keys.)

Another way to produce a multiple valid key situation is to use two encoding methods in sequence, discussed below.

Multiple Use Pad Systems

The one-time pad crypto system consists of a very long key, which is used only once.

The modern procedure for encryption is for the sender to exclusive-OR the key with the message.  To decrypt the message, the receiver will exclusive-OR the key with the cyphertext.

The one-time pad is well-known as being unbreakable by any crypto system, as long as you have a reliable, secure, high-capacity key distribution system.  Wikipedia has a very good article on the subject.

At the same time, using a one-time pad more than once produces very, very weak crypto.  This is because the exclusive-OR of two plaintext messages contains a lot of redundancy which is easily exploited by cryptanalysis.

Also, multiple-time pads fall apart instantly when attacked with a known plaintext.

Oddly, using a multiple-time pad on top of a moderately strong block cipher such as DES gives a result which is stronger than the sum of the parts.  This is because the usual attacks on a multiple-time pad do not work if the message was pre-encrypted using something like DES or AES, which have good entropy characteristics.  The result is that 56-bit DES plus a 64-bit multiple-time pad provides better security than either method by itself.  How much better?  That depends.

In the case of a quantum computer, you can see that increasing the number of bits in the key will increase the cost of the decryption device, which is gratifying.  More important, you will observe that, for every possible 56-bit DES key, there exists a 64-bit "one-time pad" which will make the output equal the plaintext.  In other words, this system has the characteristic that it supports 2⁵⁶ valid decryption keys, each of which is 120-bits long.

For organizations with a large budget, it is still possible to attack this system by analysis of multiple blocks, etc.  It's just that low-cost additional coding steps can cause exponential additional effort to be required, which makes quantum computer resistant crypto systems secure, for all practical purposes.

Conclusion

While mainstream algorithmic coding systems are vulnerable to near-term quantum computers, it is possible to design coding systems which are more secure than current practice.

The most promising designs involve the use of multiple valid keys.