Counting Cats in Zanzibar Rotating Header Image

Quantum Computers & Codes

According to Dale over at Samizdata quantum computing is here. Now I don’t want to entangle myself in all the details but just one consequence.

Quantum computing kills stone-dead RSA style encryption. Through the long history of human sneakiness there has been a war between cryptology and cryptanalysis. RSA was (is) a decisive victory for cryptology. It can be broken but only with a certain tonnage of super-computer. But that is not all that makes RSA so useful. It is a form of public key cryptography so the not inconsiderable problem of distributing keys is not an issue. If you want to send an encrypted message to someone you use their public key and they then de-crypt with their private key. It’s an asymmetric cipher using a different key to encrypt as is used to decrypt. Neat, eh?

So, what is left if you want to send secret messages? Well, oddly enough it really is back to the future time! Your options are:

One time pad ciphers. Now these date from 1917 and Claude Shannon subsequently proved them uncrackable if used correctly. The problem here is that the “if” there is a big one. To all intents and purposes the pad which is the key has to be distributed physically. This means a lot meeting in parks and feeding the ducks before handing over a USB stick on the sly or posting a DVD-R with “Jane and Bob’s Wedding” written on it and hoping nobody checks. It also of course means keeping all that data safe at the other end. And it goes without saying that when the length of the messages reaches the length of the pad getting a new one. The practicalities of the OTP are very tricky. It is impossible to imagine such cryptography being of any real use for most banking or for a military in the field.

Book codes and ciphers. Now we really are going back in time. The problems here are almost insurmountable for the sort of way in which we use cryptology in the internet age. Book codes in which entire words are substituted are deeply impractical unless your book contains all the ones you need. Book ciphers which use individual letters are more practical but generally less secure than book codes which can be very strong indeed. An example here are the infamous Beale ciphers some of which remain uncracked. I honestly can’t see book codes and ciphers despite their romance being of much use.

What I find really interesting – it’s the new/old physical element here. The secret to your nefarious communications will actually be an object. A thing. In order to defeat electronic surveillance of your communications you will have to have something on your person or in your home. It wouldn’t surprise me if security organisations are trading in their laptops for lockpicks in the future. If two suspected agents are both discovered to have on their book shelves some rather obscure text for example then bingo!

There is of course an alternative to codes and ciphers which is also of great antiquity – steganography. The art of hidden writing. In a modern context this wouldn’t be the old invisible ink or whatever. Perhaps one of the most unusual ways of doing it was a wheeze of an ancient Greek general or such who had the head of one of his soldiers shaved, a message tattooed there and then waited until the hair grew back. Obviously not a man in a hurry! No, I’m thinking of hiding messages in media files and that sort of thing. The possibilities are endless. Steganographic techniques also mean there isn’t a message that clearly you want to keep private. An encrypted message on the other hand is obviously encrypted.

So, yes, we live (perhaps, there is some quantum uncertainty here – some of the commentators on Dale’s post doubt this is a true quantum computer) in interesting times. There is of course the possibility of the ultimate encryption. Quantum encryption (not really related to the computation – yet another thing da Quantum does!). Lots of people are working on this because it can’t be cracked in principle. Unfortunately it’s not very practical. You need a direct fibre-optic or possibly a line of sight laser link. Oddly enough, just like the old skool methods I discussed above the encryption has physical – in the sense of “stuff” – requirements. Information may, if RSA can be routinly cracked retain it’s nature as a sort of quintessence but not if you want to keep it secret.

PS. I have discussed this in terms of espionage and stuff. I do appreciate the issue of digital security applies to you and me as much as to Smiley’s people but it’s just the way the words came out.

11 Comments

  1. Angry Exile says:

    I don’t know much about these things but what can it make of, say, my WPA2 key? Allowing for the fact that it would have to first be improved into laptop form could it just let itself into my WLAN from out in road?

    What I find really interesting – it’s the new/old physical element here. The secret to your nefarious communications will actually be an object. A thing.

    Unless you go new/old/newer and use electronic copies for a book code.

  2. Jiks says:

    Hmmm, I see the buyers of the first commercial Q computer are Lockheed Martin.

    I’m assisting D-Wave’s quantum computer research via the Berkley Open Infrastructure Computing network … may have to rethink this if that is the way things are going.

  3. Roue le Jour says:

    I would disagree about one time pads. I think they very practical, now that we have multi gigabyte storage in a tiny space, i.e. micro SD cards. Not only would they allow M and 007 to exchange 16gigs of data (and that number is bound to go up) completely securely, every agent would have their own card, so if 006 falls into Spectre’s hands, it doesn’t help with looking at 007′s comms. And of course you would use a new card for each film, sorry, mission, as well.

    Incidentally, you don’t have to post a DVD of Jane and Bob’s wedding. Hollywood does the distribution for you. You just have to agree, secretly, to use the DVD of Pirates of the Caribbean and then buy it locally. Any old globally available datastream will do, it could be CNN at 7pm off the satelite if you like. DVDs are already encrypted (poorly) so if you just look at the raw datastream off the disc it already looks like random numbers, which is just what you want.

    I did once toy with the idea of GPS encoding, i.e. the GPS data is used as the key, and thus you have to be in a particular place, say the Kremlin car park, in order to decode the message. Not particularly practical, but it might be a useful plot device in a story.

    Banking, yeah, probably not, but I don’t know how much data they need to move?

  4. NickM says:

    Roue,
    You have a very good point about “any datastream will do”. I’d actually been pondering that myself using the expansion of irrational numbers. No obviously you’re not going to choose pi anymore than you book code would be based on the King James Bible but there is an infinity of irrationals and it all depends on how many can be succinctly described and the computational effort of cranking out the digits. I shall bear the GPS idea in mind if I ever decide to de throne le Carre!

  5. Slamlander says:

    There are many older alternatives for encoding like steganographic distribution of an encrypted message. BTW, steganography is more of a distribution scheme than an encoding scheme. It’s interesting but still fails if a third party can obtain the entire message. However, when a proper Book Code is used, like the Code Talkers in WWII, it becomes almost uncrackable, especially when only a part of the message is available (via steganography).

    This is in addition to Roue le Jour’s points about OTP. A part of decryption is dependent on recognising the decoded message when you get it. When it is codified in a language that you can’t recognise then you have no clue when you are done. If, in addition, you layer a Book Code into that, and a cypher over that, then it becomes difficult to even know when you are done with the decoding. Yes, this is partly dependent on the third party not knowing how you’ve done it. But even so, a Quantum Computer would have a difficult time of it. There are too many independent variables that are non-mathmatical for the solution to come easily.

  6. Kevin B says:

    “So what does our multi-billion pound super quantum decryption computer make of the ultra-secret message then Perkins?”

    “It says “Send three and fourpence, we’re going to a dance”, Sir.

    “But at least it’s better than last time, Sir.”

    “Remind me Perkins, what did it say last time?”

    “Forty-two Sir.”

    “Ah.”

  7. Roue le Jour says:

    Slamlander, I don’t think anyone is suggesting a quantum computer would be any better at any other encryption than the one used on the internet. This encryption is based on the belief that is hard to factor large numbers, quantum computers have the theoretical ability to do just that.

    You point about languages is a good one. The CIA is so short of Middle Eastern language experts that a couple of terrorists can chat away quite happily on the phone in their native hill tribe dialect with no possibility of being understood. All the fancy hardware in the world isn’t going to fix that problem.

    Kevin B, my thanks to the the British Heritage Joke Foundation.

  8. Slamlander says:

    Roue, thank you but if I may expand on the concept a bit, for others;

    Given;
    N layers of encryption and decoding where N is unknown
    The plain-text language (L) is unknown
    The plain-text language’s written form (Lw) is unknown
    The plain-text language’s encoding map (Lm) is unknown

    Then;
    You run smack into one of Dykstra’s 7 non-computable tasks because you have no way to recognise the plain-text when you get it. It thus becomes an uncrackable code, even for a Quantum Computer.

    Our encryption technologies have been headed down the wrong path for decades, a point that any Natural Language AI worker can atest to. In short, CypherPunks have been doing it wrong; the answer is not in mathmatical forms and can’t be. There is no, and cannot ever be, an uncrackable cypher without at least one layer of encoding.

  9. NickM says:

    Slamlander,
    The Navajo codetalkers were not using a book code or as far as I can tell anything equivalent. The point is – as Roue hints – the Japanese simply had no speakers of that rather complicated language (not just different words but hellish grammar) . In a very limited sense it is a classic code of the sort school kids make up because the codetalkers had to take their names for birds and fish etc and use them to represent things like “dive bomber” or “destroyer”. It was a brilliant ruse of course because it easily enabled voice communication over radio which was totally secure in practice if not theory.

  10. David Gillies says:

    We have a quantum algorithm for RSA (and the related Diffie-Hellman key exchange, which is a problem in discrete logarithms.) To the best of my knowledge, there are no quantum algorithms for cracking other public key schemes like Lattice Cryptography (not to say none exist, but we don’t have ‘em.) There’s almost no advantage to be had for symmetric ciphers (where keys might well be distributed in a side-channel e.g.steganographically.) And by going to suitably large moduli, we can make it infeasible to crack even things like RSA. I can multiply two 50,000 bit numbers, find a number co-prime to the product, invert it in the ring of the modulus, and then do a modular expansion of a message in a fraction of a second on a cheap computer. You need a number of qubits of the order of the modulus you are trying to crack, and this is an arms race quantum computing is losing badly at the moment. Since RSA/DH are only used in the setup phase of an SSL connection and then the (symmetric) session keys are cached, this probably won’t have much impact on efficiency. Where this may have an impact is in breaking historical messages with inadequate moduli, but not for a while. Most people use 2048 bit moduli on their SSL certificates, and this new machine is a 128-qubit device. Even running traffic through an onion router is probably enough for the foreseeable future.

  11. Kevin B says:

    Thanks David, I’m glad you cleared that up.

Leave a Reply

%d bloggers like this: