Sunday 18 October 2015

The trouble with crypto: Qubits

Up until the mid 1990s computer security was thought of in terms of isolationism.
For a large portion of that time computers and hardware in general were prohibitively expensive. Computing remained the purview of large corporations, academia and governments.

Towards the beginning of the 1980s this began to change. Isolation remained through restricted networks by nature of their cost and lack of infrastructure.
Come the turn of the century and computer security through isolation (in this form) was gone.

In hindsight, its almost comical to consider that relying on isolationism: the fact that computers were expensive and networks were inaccessible, was a good strategy for security.

Fortunately, far more sophisticated security concepts have been implemented to keep our information safe. That being said, it is undeniable that computer security is almost entirely dependant on crypto.

Cryptography in turn is also dependant on a strategy not too distant from the days of isolationism. This is because it relies on the fact that data is encrypted with a sufficiently complex cipher that is incredibly resource intensive to crack. That is to say, to crack it in a period of time that is useful, requires a level of computing power that is not available.

Massive Numbers

AES-256 is a widely used crypto specification. AES-256 features a key of up to 256 bits, of course, this means there are 2^256 possible combinations of bits in a 256 bit key.
To put that into perspective; if you were to count all the atoms in the universe, you would be well on your way when you reached 2^256.

To crack this 256 bit key, we would need a massive amount of computing power. A high end GPU can do approximately 2 billion calculations a second. If we had 1 billion of these GPUs working in parallel they could churn through 2e+18 keys per second.

At this rate it would take those 1 billion GPUs 14 billion years (the age of the universe) multiplied by 6.7e+40 to reach approximately half of the total bit combinations.
It is fair to say, that is not a useful time period.
Credit to INCOMPLETE_USERNAM for the math.

Quantum Bits

Bits and qubits have everything in common and nothing in common, a relationship itself which is in a quantum state.
A bit is a unit of information capable of indicating values based on receiving current or not receiving current; 1 or 0 respectively. Of course the mechanics of this are more complex.
A qubit (one quantum bit) is also a unit of information capable of indicating values. However, the process of this being achieved is entirely different to a bit. It goes without saying that the mechanics of this process are incredibly complex.
Courtesy of D-Wave Systems Inc.

Qubits on their own however are not generally more powerful than bits. When they are paired or “coupled” to each other then the true value of qubits is realised.

It would appear that it is possible to establish equivalencies between bits and coupled qubits.
Associate Professor Andrea Morello of the University of New South Wales (UNSW) Faculty of Engineering explains here, that the equivalent number of “classical bits” to qubits can be calculated with the following:

2^n where n = the number of qubits.

For example, using this equation 300 qubits are equivalent to 2.037036e+90 classical bits.

For perspective the highest transistor count in a commercially available CPU today is approximately 5.5e+9 (5.5 billion) transistors (18-core Xeon Haswell-EP made by Intel).
2.037036e+90 transistors would be needed to represent 300 qubits of information.

This month (6th October) engineers at the University of New South Wales in Sydney reported that they had demonstrated a 2 qubit logic gate in silicon for the first time. This has made calculations between two qubits possible. Crucially using a well established material already used in the computer industry – silicon.

In September, Google and NASA announced that they were upgrading their D-Wave quantum computer from 512 qubits to more than 1000 qubits, however it would appear that the true power of the qubits in the D-Wave have not been realised. In fact, its title of quantum computer has been questioned by some as it currently does not offer an advantage over a classical computer.
It would appear that quantum computing which offers the bit equivalency shown above, is not here yet.

Quantum Computing vs Crypto

Public information about quantum computers indicates they are still a number of years away before the technology could be used to crack (previously) highly secured cryptography.

None the less, ETSI (European Telecommunications Standards Institute) has formed The ETSI Quantum-Safe Cryptography Industry Specification Group. The group has identified quantum computing as posing a significant threat to crypto now and in the future.

The group state on their website “Without quantum-safe cryptography and security, all information that is transmitted on public channels now – or in the future – is vulnerable to eavesdropping. Even encrypted data that is safe against current adversaries can be stored for later decryption once a practical quantum computer becomes available.”

It is clear that quantum computers offer a giant leap forward in computing and as a result will provide a tremendous amount of computing power, an amount of computing power which might render some of our existing crypto useless, and at least significantly reduce the amount of time it would take to crack some of the strongest crypto standards that are used today. That said, AES-256 is considered a “quantum-safe” or “post-quantum” standard, provided it is used with sufficiently large key sizes (256 bit).

At this point in time, quantum computers are the purview of large corporations, academia and governments. Considering their huge computational power, quantum computers
are perfectly suited to tackling massive calculations at exponentially faster speeds; which makes them exceptionally good at (among other things) brute forcing crypto, and as a result, probably of great interest to government agencies.