We are waiting for first [working] q.computer for ages. I do remember lots of articles and news and of course speculation around q.computing and especially q.cryptography in early 2K. Post-quantum cryptography, how would you look like?
“New q. generation would kill all existing cryptosystem based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem !” – said journalists. And everyone were filled up with awe.
Well new q.generation of machines means only that we might need to consider another options for widely used algorithms including public key systems like RSA.
Do we have something except well known RSA? Yes we do… indeed, not joking, we have lots of different algorithms and even approaches. It just easy to use well known library rather then right and spend nights testing something new, which might become vulnerable in one day.
Linear codes cryptosystems family. Those systems are based on … right, linear codes! but those codes are made to correct errors you would say, not encode/decode messages. Well in the first instance, yes. But all technological discoveries are cross-disciplinary, based on classical concepts and grow between scientific branches.
Let’s have a look at McEliece or similar (in fact opposite) Niederreiter cryptosystems which was invented in 1986. That’s actually a very cool idea to use error detection mechanism to encrypt/decrypt messages. Just imagine they use a syndrome as ciphertext and the message treat as an error pattern.
The original Niederreiter system was cracked in 1992 by Sidel’nikov&Shestakov. Since that time lots of crypto-strong (yeah, until someone else would find a way to crack them) modifications have been proposed and designed. If you know Russian please have a look at existing linear codes based algorithms review . Yeah, I should find time and energy to translate it into English some day…
One of those modifications is Frobenius matrix based modification my supervisor E.Gabidulin with assistance of myself in 2009.