Could the “Spectral Gap Problem” Lead to Unbreakable Encryption?

Tweet about this on TwitterShare on FacebookShare on RedditShare on Google+Share on LinkedInEmail this to someone

padockResearchers in Madrid have recently discovered a mathematical problem that cannot be solved — at the quantum level (of course). Could the “Spectral Gap Problem” lead to unbreakable encryption?Encryption is based on public and private keys, and typically each version is either the right side or the left side of a complex calculation. Here’s the classic illustration: the left side of an equation may be a simple prime number, whereas the right side would be some extremely complicated computation that results in the prime number.

The simple left side represents the public key — the part of the encrypted data that the encryptor (if you will) gives to the world. The complex right side of the equation, however, represents the private key — the part of the encrypted data that can only be derived if the counter-party knows the equation (or an extremely fast computer).

In recent years, talk of the development of quantum computers has sent a cold wind of fear through the encryption community. Quantum computers — although not yet available in any practical form — promise to perform calculations so quickly that they could easily crack all current forms of encryption.

The idea of an “unsolvable” problem seems like a good starting point for the complex right side (private key) algorithm — a development that, if successful, could put to rest any fears of quantum computers having the capability of cracking encrypted data. Of course, if a problem is unsolvable, that would mean a user would never be able to retrieve his encrypted data!

If, however, it were possible to associate the unsolvable equation somehow with a known value, then it would truly represent perfect encryption. The rub, is of course, the “association” part! I have no doubt that more powerful minds than mine are already far down the path of exploring these possibilities.