back to article Actual quantum computers don't exist yet. The cryptography to defeat them may already be here

The US National Institute of Standards and Technology (NIST) has recommended four cryptographic algorithms for standardization to ensure data can be protected as quantum computers become more capable of decryption. Back in 2015, the NSA announced plans to transition to quantum-resistant cryptographic algorithms in preparation …

  1. msobkow Silver badge

    There is no privacy in the long run. Technology advances faster than we can come up with schemes to protect the data for, largely because their is no predicting the imagination and creativity of possible attacks and solutions in the future.

    Security is a shell game, and as the world becomes ever more interconnected, privacy becomes ever more eroded as we evolve into a digital Borg society, complete with people working on man-machine and brain-machine interfaces.

    Resistance is futile...

    1. Pascal Monett Silver badge

      On the contrary, resistance is highly necessary.

      1. LybsterRoy Bronze badge

        -- resistance is highly necessary --

        Whilst I agree with your statement I feel that we have more chance of success if we concentrate on the appropriate items to protect (eg stop them nicking my money) rather than everything in sight (eg eye colour)

      2. jmch Silver badge

        Resistance is highly necessary, but it's important to understand what can be resisted and what can't. For example if there is data that the owners want to be kept secret for 75 years, it has to be stored encrypted in a place where it's not going to be transmitted over a network, since if it's transmitted, the (encrypted) transmission can be intercepted.

        Is a current state-of-the-art encrypted transmission likely to be crackable in the next 5, 10 years? - probably not. But estimating that 15-20 years down the line is a fool's errand, let alone 75 years! Of course the other issue is volume. An attacker cannot feasibly intercept and store decades worth of traffic even from a single site, on the off chance there might be some data that can be usefully used decades in the future.

        1. El Bard

          Some Law: At some point, in any discussion about encryption, xkcd needs to be cited:

          https://xkcd.com/538/

          Corollary: A 5$ wrench can be substituted by a 6-figure bribe, optionally garnished with (veiled) threat to the subject's relatives.

        2. NoneSuch Silver badge
          Facepalm

          "Is a current state-of-the-art encrypted transmission likely to be crackable in the next 5, 10 years? - probably not. But estimating that 15-20 years down the line is a fool's errand, let alone 75 years!"

          So the NSA, the largest employer of mathematicians in the world and well known for building flaws into all past encryption methods, tells you to use these four algorithms and you think anything encrypted with them is safe for 5+ years.

          (Best Dr. Evil) Riiiiiiiiiiiiiight...

        3. CheesyTheClown

          Policy vs Technology

          Keeping data protected for 75 years is a matter more properly managed by policy than technology.

          It would be important to identify the reason you would encrypt there data and then identify why you would decrypt it.

          Most data doesn’t actually need to be encrypted if it is intended for offline storage. Rather, a good physical security policy such as long term media storage in a secure location would be ok.

          Encryption is primarily necessary for when data is to be transmitted. Until it needs to be transmitted plain text is probably ok. But when you transmit the data and it is intercepted, if it needs to remain private for 75 years from the time it is intercepted, it is clear that data will eventually be compromised. Therefore, such data should be physically transported rather than electronically.

          You’re absolutely right in my opinion. Looking 5-10 years ahead may be achievable. Looking 25 years ahead would be entirely impossible. We honestly have little or no idea how quantum computer work today and we have no ideas what break through swill occur in the next 25 years. At this time, every quantum programming language is roughly equivalent to a macro assembler. We are literally programming with gate operations like assembler op-codes and of course macros. 25 years ago, chip design was very similar… almost identical. Then we figured out how to write high level code which would automatically compile to synthesized logic. And then we rocketed decades ahead overnight. We have absolutely no idea what will happen when the quantum world sees such a leap.

          So, if data must be secure for extended periods, floppy-net will probably be the best option.

          1. Mike 137 Silver badge

            Re: Policy vs Technology

            "Keeping data protected for 75 years is a matter more properly managed by policy than technology."

            However keeping up with technology is not to be ignored. It will likely be quite a challenge to keep up with technology obsolescence over such a length of time. There's a distinct probability that a lot of (even important) data will no longer be accessible half a century or more down the line. I seem to remember the BBC 'Childrens' Doomsday Book' - a 14 inch video disk, for which specifications were fortunately still available a couple of decades after it was recorded. But I believe it cost around £10k to build a reader for it. I also seem to remember that quite a few of the Saturn V data tapes had decayed beyond readability before NASA got round to making use of them. And quite apart from forgotten formats and protocols, now most of our data storage depends on retention of very small but quite precise electrical charges in slightly leaky semiconductors that kind of problem is bound to become ever more significant. It may indeed become more significant than any fragility of encryption - in that it's possible that nobody will be able to read a lot of the data after seven or so decades.

    2. adam 40 Silver badge

      As we approach the Singularity, this becomes ever more important.

      Not to protect our secrets, but to prevent the computers compiling and downloading their own software to our machines, to network infrastructure, etc etc.

      Once the secret/private keys are broken, there will be no defence.

  2. eldakka Silver badge

    transition to quantum-resistant cryptographic algorithms in preparation for the time when quantum computers make it possible to access data encrypted by current algorithms, such as AES and RSA.
    This statement is 1/2 accurate ;)

    The concern with quantum computers and cryptography appies to Asymetric algorithms such as RSA, it does not apply to symmetric algorithms such as AES - at least not to as great an extent.

    All of the algorithms being tested in the article are Asymetric replacements. A sufficiently large AES key (256), is large enough to defeat quantum computers - at least in the time scales we are conerned about with respect to asymetric keys being defeated by quantum computers.

    Therefore for data at rest, as long as it is AES-256 (128 is probably sufficient, but to be sure to be sure if we are talking uber "I could tell you but I'd have to kill you afterwards" secret it should be 256) encrypted, it should be safe for well beyond the 75-year "this must remain encrypted for" period.

    However, when data is transmitted between systems that don't both have knowledge of the symmetric AES key, asymetric algorithms such as RSA are used to establish the trust between the two ends, through which the symetric can be exchanged, to do the actual heavy lifting of encypting and ecrypting the data stream in flight using AES. Therefore if 'safe' AES-256 data is being transmitted between two systems, and an unsafe RSA mechanism is used to exchange the AES-256 key between the 2 end points, someone listening could obtain the AES-256 key while it is being exchanged with RSA, thus netting them the (in practical terms) 'unbreakable' AES-256 key directly as the raw key is transmitted without having to 'crack' the AES-256 stream itself, they now have the key and can just straight decrypt it using that intercepted key.

    See this article Will Symmetric and Asymmetric Encryption Withstand the Might of Quantum Computing?from 2021 for reference.

    1. Anonymous Coward
      Anonymous Coward

      Be careful with that confidence.

      Suppose you generate a complete one-time pad, by measuring motion due to heat, or electrical noise from a gate, or even lava lamps at Cloudflare. A pad large enough so it never repeats. Not 256 bits but big.

      There may be a day, when that key can be broken down to a simply set of factored chunks.

      Here their algo appears to struggle because its [classical-chunk] then [quantum-factor-the-chunks], the quantum part doesn't do the heavy lifting, the classical part does. Fail to get those chunks and you fail to factor them. Perfectly break down those chunks, then all manner of factoring methods can work, not just quantum ones.

      But there was another science story recently, an experiment that stopped a magnetic spin by heating it. Implying that the chaotic motion of heat contains the same component of that spin, i.e. not a random system at all, just a complex sum of many chunks that appears to be random, one of which was that spin component.

      And so your 'random' key, generated from heat, would have an underlying pattern to it. A pattern you can ultimate identify by a *working* chunking-factoring-chunking-factoring approach.

      You could wake up one day, to find your random private key is not random.

      1. martinusher Silver badge

        True, but the point being made is that encryption itself is nothing like as vulnerable as the key exchange and verification. After all, there must be some reason why the typical quantum algorithm that you hear about involves factoring and prime numbers.

        (BTW -- The classical random number generator seems to involve two independent noise sources that individually generate numbers, the output being the difference between these numbers. This is obviously the simplest example of n sources being acted on by some arithmetical process but its way beyond my pay grade to figure out the 'why' and 'whats'.)

        1. dajames Silver badge

          After all, there must be some reason why the typical quantum algorithm that you hear about involves factoring and prime numbers.

          Yes, it's because there are prominent cryptosystems that depend on knowing the factors of large numbers (RSA does, Diffie-Hellman can), and it's relatively easy to explain how quantum techniques can achieve factorization (as opposed to, say, finding solutions of elliptical curve equations).

          A cryptosystem that doesn't depend on knowing the factors of large composite numbers won't be amenable to attacks by factorization.

          Your first point - that encryption itself is nothing like as vulnerable as key exchange and verification - is also correct, but I fail to see what that has to do with the latter?

          1. Mike 16 Silver badge

            Prominent Cryptosystems

            Let's not forget the "kinda RSA if you squint" code-signing on Atari 7800, Lynx, and Jaguar (IIRC, YMMV)

            As copyright extension head toward the heat death of the universe, there _must_ be some way to prevent our cockroach and cephalopod successors from viewing Little Mermaid without an unlock key purchased from a server that was turned into a steampunk watch-fob before the second "Big Meteor Event".

            I recall a bit of consternation when some time-sealed documents revealed (mid 1970s?) that the U.S. had preliminary studies of invasion plans for Canada, should the need arise.

            embarrassment and greed are the main drivers, I suspect.

  3. Pascal Monett Silver badge

    So, quantum is basically the new fusion

    Different types of qubits, you need millions to actually do anything but the best we can do is 5000 and we still don't know how to program them.

    177 days to decrypt with 13 thousand qubits ?

    I thought this stuff was supposed to be almost instantaneous.

    1. Anonymous Coward
      Anonymous Coward

      Re: So, quantum is basically the new fusion

      It is. You overlooked the time needed for the Windows front-end to boot.

    2. Eclectic Man Silver badge
      Boffin

      Re: So, quantum is basically the new fusion

      Years ago I went to a presentation at the Maths Institute in Oxford on Quantum Computation. I forget the name of the presenter from Plymouth University, but he said that QC was counter-intuitive, in that you programmed a quantum computer and waited a specific length of time fro the result. Indeed, one of his results was that you didn't even need to program the computer, you just need to wait the correct length of time for the computation.

      So it is all in how long the computation would take if you had programmed the quantum computer, apparently.

      (No, I don't understand this either.)

    3. Michael Wojcik Silver badge

      Re: So, quantum is basically the new fusion

      I thought this stuff was supposed to be almost instantaneous.

      Well, you thought wrong.

      There are plenty of accessible introductions to QC available online, and many accessible discussions of it from people like Scott Aaronson. Why not actually learn something about it rather than complaining you don't understand it?

      For problems where you need an exact solution rather than an approximation, if you're going to use general quantum computation to search for that solution, you'll need error correction. Error correction is the big stumbling block here (along with scaling up to a suitable number of qubits; Shor's algorithm requires on the order of (lg N)2 qubits, where N is the size in bits of the input, so it's logarithmic in space but not directly).

      Even then, Shor's runs in polynomial time on the length of the input, so it's not "instantaneous". And like all algorithms in BQP, testing the result is polynomial; in the case of factoring that's still very fast for a single candidate solution, but if your error correction is weak, you might be testing a lot of them.

      Also, ignore the bit from the article about 5000 qubits. Adiabatic QC is utterly irrelevant for cryptography.

  4. This post has been deleted by its author

    1. Dave 126 Silver badge

      Re: Who needs QC?

      It's a lot less noisy to just use one chimpanzee, if you can.

    2. Michael Wojcik Silver badge

      Re: Who needs QC?

      Not everything is encrypted with a password some user came up with.

      1. msobkow Silver badge

        Re: Who needs QC?

        Monkeys don't necessarily guess words and phrases. In fact, I'd expect most of their guesses to be pretty random.

  5. mbiggs

    Obsessed With Mathematics, Randomisation, N-bit Keys......

    ......but suppose the encryption is designed in some other way:

    * only designed to handle text

    * with an algorithm using some sort of word-substitution, based on a custom dictionary

    * implemented by a very limited group of participants

    Perhaps I'm just an ignorant, under-educated old fool, but (assuming it isn't a hoax), two of the three documents in the Beale Papers are still secret after more than a century! ....and these papers use a cipher which avoids the utilisation of Mathematics, Randomisation, N-bit Keys. Will quantum computers be any better at deciphering the two secret papers?

    See: https://en.wikipedia.org/wiki/Beale_ciphers

    See: The Code Book, Simon Singh

    1. Anonymous Coward
      Anonymous Coward

      Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

      Not me.....here's a message with a cipher based on the file linux.words. I wonder what a quantum computer might make of this example!

      *

      ambergrease sanddabs tetrahedrons diffusibleness pleasureproof surgency whitecap juicily somewhatness joyriders goodhumored reprehender subinfer -some tambuki pex vitus selfaccusing overdignify paper-waxing homologating unbroad eelcatcher ninut nedc intellectualised collusory bold-following curucucu codium antibilious preparateur impaled noverify sarsenets coprosma mimamsa salping- fraghan obstreperousness gimpier disulphide cochlospermaceous intershooting gulf aru seraph canamera rubstone hamesucken cacidrosis cockapoos well-written hobucken unvisiting marsiella thorlay beteach actors irradicated initive stiff-rusting invidiousness multifistular thyrorroria sturty incapsulate prehandicap semnopithecus loricated predrawing canopy minch exergonic anesthetist antisavage octile knockoff quasi-japanese pelecan uzbek bromize crinitory fungitoxic shadchen caenolestes twinset unfussily stanches daffodowndillies uninterested baubling stutter diphtheroidal chilotomy subalgebraical nematophyton pilosis restated multiuser spriglet overlather improprieties planets aldridge sabc scorkle micr roeg ubm progess pinknesses kaver smoke mutilla unsignable reveilles watersmeet protocolist cantoning bibenzyl law-merchant palaeotypical hyksos underdrawers fidelis woolly-white kirkcaldy fractured teaseller twitter pomerene unrun rice-planting theron colicroot coof self-destructively elbows stempien pneumohydrothorax bifidly lupercalian reexecuting hazeless brama monosulfone sellersburg counterglow solanidin priestship solated centralizes pinnate-ribbed

      *

      1. The Oncoming Scorn Silver badge
        Joke

        Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

        ambergrease - Johnny Depp calls it shit.

    2. Panicnow

      Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

      Yes, I've proposed methods of using and distributing cheap and unbreakable "one-time code books" for sometime. Even I can do the probability maths to demonstrate their strength. But there is the problem, an expert mathematician will never consider a system that doesn't need an expert mathematician to verify it!

    3. Dave 126 Silver badge

      Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

      Say you and I met up in seclusion and agreed in advance that parsnip means The Red Lion, and spaniel means The Bell. We go out separate ways. The next week I publically post on this forum, (or send you a letter that is intercepted) a message containing Parsnip. If we only used this substitution once, then yes, it is impossible for an attacker to know which pub we're meeting at.

      However, we've been seen in the Red Lion. In order to keep the destination of next week's meeting secret, we must agree in advance, and then substitute, a different word for Red Lion every time we wish to write about it. Excavator. Battery. Stallion. Paperclip. Granite. Confess. Etc etc.

      So, on our secure meet-up, we write down these long lists of substitutions, and when we part ways we each take one of only two copies. What we both have is a 'one-time pad'.

      Unbreakable if used properly. Not applicable to most applications, because it requires us to meet up in person to share a one time pad.

      1. Mike 137 Silver badge

        Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

        "Unbreakable if used properly."

        Except that you've both been seen in the Red Lion. If we isolate the decryption problem entirely from the world at large, your assumption is largely correct. But in the real world counter-espionage (which is what we're really discussing) gathers a wide variety of clues from multiple sources and assembles them into a single coherent picture. See R.V. Jones 'Most Secret War' [Hamish Hamilton 1978 and subsequent editions] and indeed the early work at Bletchley Park. So if you've both been seen several times regularly at the Red Lion, the meaning of your code words could be approximately inferred.

        So for very infrequent and short communications as in your example codes can be quite secure, but as the volume of traffic increases clues as to meanings start to emerge from context and they get easier to break.

    4. Michael Wojcik Silver badge

      Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

      Sure. Now explain how to use a random-substitution code in a TLS cipher suite, say, or full-disk encryption.

      Random-substitution codes aren't mechanical ciphers. They don't scale. No one cares if your secret message to your best pal remains undecoded forever. What people care about is mass encryption, and that requires machines and algorithms that scale.

      1. Anonymous Coward
        Anonymous Coward

        Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

        @Michael_Wojcik

        Quote: "....What people care about is mass encryption...."

        Ah....a very broad generalisation! Which "people" are you talking about?

        More narrowly.......I'd be prepared to bet that organisations like GCHQ, the NSA (and like organisations) spend a disproportionate amount of their time on email and text messages and documents.......you know, messages from one "pal" to another......

        .....and your observation doesn't change the fact that Thomas Beale, communicating with a "pal" or two, has kept his secrets pretty well.....despite "random-substitution", failure to "scale"......

        1. martinusher Silver badge

          Re: Obsessed With Mathematics, Randomisation, N-bit Keys......

          >you know, messages from one "pal" to another.

          All modern communications are encoded using what is effectively a stream cipher -- one character of plaintext becomes one character of encrypted data. Actual complexity will vary but the general idea is that the coding scheme codes the message and not the meaning.

          Older cipher systems, the commercial and military ciphers of the the 19th and early 20th century, encoded the meaning rather than the text. The reason for this wasn't just security -- being able to substitute a few characters for a word saved money and time on telegraph systems. This system has limitations but within those limitations it would be difficult for a machine to crack.

  6. Duncan Macdonald Silver badge

    True one time pad encryption

    If true one time pad encryption is used then successful decryption is only possible if the one time pad is disclosed

    A crude example the encrypted string "buvowwh isdjbcyu jnwxa"

    could decode to "Attack Pearl Harbor now"

    or to "Mary had a little lamb.."

    Without the pad there is no way to know which message is correct.

    Using code phrases is also immune to decryption without knowledge of what the code phrases mean (see examples of the messages sent to the French Resistance by the BBC in WW2).

    1. Mike 137 Silver badge

      Re: True one time pad encryption

      "Using code phrases is also immune to decryption without knowledge of what the code phrases mean"

      Theoretically, yes. But there's a human tendency to associate that frequently gives at least part of the game away. This is most obvious in codenames, which have a nasty tendency to relate to the operation or item named. See R.V. Jones 'Most Secret War' with reference to the codenames given to the German radar technologies.

      1. Dave 126 Silver badge

        Re: True one time pad encryption

        > codenames, which have a nasty tendency to relate to the operation or item named.

        Has this 'tendancy' been statically analysied, or has your source merely presented examples of when Operation Camel has actually been a long range attack in the desert?

        I ask because I would expect that if choosing codewords truly randomly, then by chance a fraction of them will reflect their subjects. In a war I'm assuming thousands of codewords must be assigned. Of course, if I was 6'9" and had a squarish head, I would veto Agent Lurch were it be assigned to me by chance.

        And that's before we get into the whole "I will name my amphibious assault Operation Sealion, because if the enemy hear about it they will assume I'm trying to lure them to the beach. So they won't go there. But I actually will invade there! Hahaha!" games.

        1. Mike 137 Silver badge

          Re: True one time pad encryption

          "Has this 'tendancy' been statically analysied,"

          It hasn't (as far as I know) been formally analysed in the secrets space, but there are enough well documented examples to make a pretty good empirical judgement, which is reinforced by more formal records of passwords that refer back to the creator's interests, family, pets &c. Apart from which the associative tendency has been tested by numerous abstract psychology experimenters. To avoid the tendency it's necessary to [a] recognise it (which doesn't always happen) and [b] implement some sort of effective randomiser (which can be hard). One useful approach is for the codeword to be chosen by someone who knows nothing about the mission or object, but it's quite surprising how infrequently that is done.

    2. Michael Wojcik Silver badge

      Re: True one time pad encryption

      OTPs are completely useless for mass encryption, which is what actually matters to the overwhelming majority of use cases. OTPs have no solution for key distribution (in fact they're maximally bad for it). They're symmetric, so they have no applicability to digital signatures. They don't scale.

      1. Duncan Macdonald Silver badge

        Re: True one time pad encryption

        However the messages that would be important enough for a government to use a quantum supercomputer to try to break are likely to be few and far between. They are far more likely to be messages suitable for one time pad use such as from a spy to his HQ or from a military HQ to one of its units.

        For the regular mass encryption (eg on websites) simple espionage (or even a NSA visit) is likely to be sufficient to obtain the private keys after which the traffic can be read in real time by a simple computer - no quantum supercomputer needed.

        With microSD cards being available in 1TB size for under £200, any spy could easily carry a big enough one time pad for his/her entire career.

  7. Michael Wojcik Silver badge

    adiabatic QC != general QC

    The JSC/D-Wave machine relies on a quantum annealing processor and is adept at solving optimization problems. IBM's machine is gate-based, which is better suited for running Shor's algorithm to break cryptography.

    The final clause should be "which is suited for running Short's algorithm to break non-quantum-resistant asymmetric cryptography".

    Adiabatic (annealing) QC is completely irrelevant to cryptography. General QC isn't "better suited" for Shor's; it's suited, full stop. The D-Wave machines are no more suited to running Shor's (or Grover's) than a toaster is. And the techniques for building adiabatic QC systems aren't relevant to building general QC systems. The D-Wave machines do not matter for the purposes of this article.

    1. yetanotheraoc Silver badge

      Re: adiabatic QC != general QC

      "The D-Wave machines do not matter for the purposes of this article."

      I have a different perspective. As someone who knows next to nothing about quantum computing, if I read an article that says a 13,000 qubit machine can do X and IBM has a 127 qubit machine and plans a 1,000 qubit machine, I really *do* want to know that the existing 5,000 qubit machine is less suitable for cryptography. I'm glad the article mentioned that. I'm less glad you said it was irrelevant, and that "less" should have been "not at all".

  8. The Oncoming Scorn Silver badge
    Coat

    Actual quantum computers don't exist yet

    or do they!

    1. Throatwarbler Mangrove Silver badge
      Holmes

      Re: Actual quantum computers don't exist yet

      They both do and don't, simultaneously.

      1. General Purpose Silver badge

        Re: Actual quantum computers don't exist yet

        Mine's collapsed.

        1. Rich 11 Silver badge

          Re: Actual quantum computers don't exist yet

          That was probable.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Other stories you might like

Biting the hand that feeds IT © 1998–2022