Abstract:
Quantum computing poses a serious threat to the safety of our data and communications. Shor’s algorithm is a quantum algorithm that can efficiently break several classical cryptographic protocols. However, by considering certain mathematical structures, such as reflections and rotations on an infinite tiling of triangles, we may be able to design a Shor-proof protocol.
Blog:
Quantum computing has been all the buzz in technology news lately. You might have heard that it’s going to change the world or just another fad, but we know one thing for sure: when quantum computers become operational, they will pose a serious threat to the safety of our data and communications. They are currently protected by cryptographic protocols that allow people to communicate secrets safely, but quantum algorithms offer efficient ways to break them much faster than our classical computers are currently capable of.
A widely utilised protocol is the Diffie-Hellman key exchange. It works like this: suppose Alice and Bob both start with a bucket of yellow paint. Alice mixes red paint into her bucket to get orange paint, and Bob mixes blue paint into his bucket to get green paint, but they keep the colours they mixed in hidden from each other and from everyone else. Now they exchange their buckets, and mix their respective secret colours into the other’s bucket, both obtaining the same brownish paint. This is now their shared secret, since even if someone else saw the buckets they exchanged, they have no idea what colours to add to obtain the final secret colour.
In comes Shor’s algorithm, a quantum algorithm that provides the attacker an efficient way of solving this problem. In essence, Shor’s algorithm finds patterns in the way Alice and Bob’s colours mix, and using properties of quantum computing, it can check every combination of colours simultaneously to figure out what the secret colours are.
But Shor’s algorithm actually has a critical weakness: it fails to find the secret quick enough if the structure we’re using works differently when we swap the order. What this means is, if adding red paint first followed by yellow paint gets you a different colour than adding yellow paint first followed by red paint, then Shor’s algorithm is so much less likely to find the secret colours that it is no longer considered efficient.
While this desired property doesn’t make much sense with colour-mixing, we can find it in a myriad of mathematical structures. If we form a triangular lattice, which is an infinite tiling of triangles, then we can consider reflections and rotations of a point on that lattice, for which the order matters. In fact, these actions correspond to transformations on the solutions of a family of differential equations called the fourth Painlevé equations. Through this lens, we can define a protocol similar to the colour-mixing one that allows Alice and Bob to share a secret.
There is one barrier, however, to implementing this in practice. We don’t currently know an efficient way for Alice and Bob to compute these transformations repeatedly. It is not enough just for our protocol to be Shor-proof, but it must also be practical for the users to implement. This illustrates the difficulty of balancing efficiency and security when it comes to designing quantum-safe protocols. Hopefully, cryptographic protocols get up to standard before quantum computers do.
Jason Liu
The University of Sydney
