back to article NIST requests ideas for crypto that can survive quantum computers

The United States' National Institute of Standards and Technology has issued a “Notice and request for nominations for candidate post-quantum algorithms.” The Institute (NIST) has cottoned on to the fact that “If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems …

  1. John Savard Silver badge

    Private Enterprise Has Started

    There was a news item not that long ago about a major browser maker testing a new form of public-key cryptography that might have some resistance to quantum computers. One of the problems, though, was that it wasn't certain the method would even be secure against ordinary computers. As I recall, it was based on lattice problems.

    1. Charles 9 Silver badge

      Re: Private Enterprise Has Started

      That's been the current situation. Creating a truly robust encryption system is HARD because it's a case of having to be lucky everywhere. Just ONE slip and you'll blow your whole scheme wide open.

      Such has been the case with all the post-quantum systems proposed so far. As I recall, all of them have either had flaws uncovered or are so computationally demanding in the classic sense as to be impractical for all but small pieces of information.

      1. allthecoolshortnamesweretaken

        Re: Private Enterprise Has Started

        Luck shouldn't be a factor in robust encryption.

        1. Destroy All Monsters Silver badge
          Holmes

          Re: Private Enterprise Has Started

          > Luck shouldn't be a factor in robust encryption.

          You wish.

          It isn't proved that prime factorization doesn't lie in P after all...

          1. JeffyPoooh
            Pint

            Re: Private Enterprise Has Started

            Cole 1903

            http://projecteuclid.org/download/pdf_1/euclid.bams/1183417760

            Merely interesting.

      2. patrickstar

        Re: Private Enterprise Has Started

        What can be done in case the overhead is acceptable is (obviously) to use one traditional and one fancy scheme and combine the results (eg. for key exchange you'd hash them together to get the actual session key, for signature checks you'd need both signatures accepted).

        This can also be leveraged to give somewhat better protection against things such as side-channel attacks.

  2. Rich 11 Silver badge

    Too far-sighted

    You read the above right: this is an example of a government agency being sensibly far-sighted.

    Guaranteeing that within a year the agency will be defunded by a senator who thinks that Jesus's return is imminent.

  3. frank ly

    Conditions

    It must have a master key that will be held by the government and various law enforcement departments. It must not be possible for bad people to use it.

  4. John Smith 19 Gold badge
    Black Helicopters

    Translation..

    NSA confirm they have a working quantum computer

  5. Peter2 Silver badge

    NIST requests ideas for crypto that can survive quantum computers

    I have a somewhat foolproof solution for point to point communications, using a digital one time pad communicated physically via USB or external HDD.

    It wouldn't work for any random website for blatantly obvious reasons, but between two known entities it'd be fine. For instance, between home and business and between you and bank would work perfectly well.

    The biggest problem is that 1 megabyte worth of data would require 1 megabyte worth of unique one time key pads, but with multiple terabyte sized external HDD's that's not THAT much of a limitation since transferring 2GB a day would take 1024 days, or 2.8 years to go through. High levels of data transfer such as 250GB a day would still take ~8 days to go through 2TB's worth.

    It'd be theoretically unbreakable if done correctly.

    1. Charles 9 Silver badge

      Re: NIST requests ideas for crypto that can survive quantum computers

      But easy for the cover to be blown. That's been the big problem with one-time pads: it's hard to really conceal the PAD, especially if the plods are onto you using that technique.

      1. Peter2 Silver badge

        Re: NIST requests ideas for crypto that can survive quantum computers

        Depends. That's moving from one threat class to another.

        If the threat your trying to defend against is interception and remote decryption through quantum computing then one time pads work perfectly well and it would be feasible to have software wipe keys that have been used.

        Against local attacks with physical access to the device, or the infamous $5 spanner attack with physical access to the user popularised by XKCD, then you really haven't got much security regardless.

        1. Charles 9 Silver badge

          Re: NIST requests ideas for crypto that can survive quantum computers

          Thing is, one dovetails into the other. The moment you use OTP or some other quantum-hardened system, you're likely to have just thrown up a big fat bullseye on yourself. At which point, you better be either a wimp or a masochist.

    2. Adam 1

      Re: NIST requests ideas for crypto that can survive quantum computers

      It's even easier though* given quantum computing. Bob can tell if the qubit from Alice has been observed by the waveform collapsing. Makes a very nice key exchange channel.

      * It's getting the quantum qubits to survive without near absolute zero and for more than a handful of milliseconds that's the hard bit.

      1. Anonymous Coward
        Anonymous Coward

        Re: NIST requests ideas for crypto that can survive quantum computers

        Bob can tell if the qubit from Alice has been observed by the waveform collapsing.

        Dude! You cannot just check whether "the waveform collapsed" any more than you check the probability of of the next dice throw showing snakes.

    3. JeffyPoooh
      Pint

      I believe that One Time Pads can be reused a 2nd time...

      The second use is to send an equal size replacement block of One Time Pad (noise). Kilobits blocks is probably about right.

      Noise .XOR. New Noise provides nothing. This 2nd use to refill the One Time Pads seems to be doable.

      The messages (info) being sent would need to be hashed into pseudo-whitenoise. Deterministically / algorithmically should be fine. Trivial. That's required to eliminate the obvious attack over the long run.

      Even if this process was arbitrarily truncated after N repetitions, if N=1000 then it's still a vast improvement in the practical application of One Time Pads.

      Call it Two Time Pads.

      If anyone else can figure out how to insert even the tiniest sliver of Pad growth into this algorithm, then it'd be the champ forever. That seems impossible to me.

      1. FlippingGerman

        Re: I believe that One Time Pads can be reused a 2nd time...

        I'm no expert, but I think the danger is that reuse means two messages XOR'ed toegther can be found, giving information. Your method should defeat that! I like it, I'd be interested to hear what an expert has to say.

    4. Anonymous Coward
      Anonymous Coward

      Re: NIST requests ideas for crypto that can survive quantum computers

      "using a digital one time pad communicated physically via USB or external HDD."

      Providing the device hasn't been compromised at the hardware level that is.

      1. Peter2 Silver badge

        Re: NIST requests ideas for crypto that can survive quantum computers

        That's the thing. This sort of code would be unbreakable against pretty much anything code breaking wise from decryption from interception in transit. What it doesn't guard against is compromise of the hardware/endpoint or the user. A small bit of thermite over the circuit board with an anti tamper device would probably be the solution to that, although it'd require military type R&D and severly paranoid users with an acceptence of their office/house being burnt down if their computer gets compromised.

        I'm not convinced that using a one time pad twice as suggested above is a good idea, since as soon as one code is cracked you'd then have the next pad, which would give you the next pad, etc. I think physical transfer of keys would be the way to go if you needed to be paranoid enough to implement this.

  6. Anonymous Coward
    Anonymous Coward

    What they need is a system where the wrong passkey can give you coherent data. Somebody's shopping list, or a copy of the Mr Blobby christmas video. Something either uninteresting or painful to investigate, so you never know whether you've found the data or not.

    1. Charles 9 Silver badge

      At which point the plods still assume you're hiding something and keep grilling you. The problem with plausible deniability is that the plods don't have to let you go yet.

    2. Adam 1

      No sympathy from me. Clearly using encryption makes you a pedoterrorist.

      Now that's off my chest, I can continue with the broadcast of my simulation of a very long running game of heads or tails.

  7. druck Silver badge
    Flame

    I'll beleive it when I see it...

    ...a working quantum computer capable of cracking conventional cryptography, that is.

    In the mean time I'll spend the time worrying about the myriad of crypto implementation weaknesses, that don't need magic quantum fairy dust dust to exploit.

    1. Charles 9 Silver badge

      Re: I'll beleive it when I see it...

      The US kept the existence of a working stealth aircraft secret for decades. When they REALLY don't want you to know, they can be pretty damned determined, and recall that "black" projects "don't even exist".

  8. mwnci

    The Key problem with this subject, is that people start spouting "Well because Quantum Computers can break all encryption, therefore the following holds true....." que some logical and straight-forward reasoning that is fundamentally wrong as the initial premise is wrong.

    Quantum computers are best suited for Optimization problems, classic examples being the "Travelling Salesman Problem" or TSP. Public-Private Key is likely to be problematic and not suitable in the age of the Quantum Computer, but currently it's looking likely that Symmetric keys can provide some protection and even developments like Grovers algorithm can be defeated by increasing Key-size.

    Post-quantum Cryptography will only advance, if we as a community actually learn about the subject and stop using "pseudo-intellectual" rules of thumb, and general positions like "ALL ENCRYPTION IS DOOMED IN THE AGE OF QUANTUM COMPUTING". It's sensationalist, and fundamentally wrong.

    1. Destroy All Monsters Silver badge
      Headmaster

      sensationalist

      YES!

      Quantum computers are best suited for Optimization problems, classic examples being the "Travelling Salesman Problem" or TSP.

      NO. There is no indication that Quantum Computers can solve NP-complete problems in polynomial time.

      See: BQP

      And also: MUST READ COMIC

  9. Nigel Smart

    PQC != QKD

    Again another fail from The Register re basic Crypto....

    NST are trying to find a POST Quantum Crypto algorithm (PQC in the jargon). That is a classical algorithm which resists a quantum computer. The current top favourite is based on lattices, which is something Google has been testing, based on a technique developed at Microsoft.

    The reference to the Microsoft work in the article is about Quantum Key Distribution (QKD). This is something very different, which uses quantum mechanics to solve a very very tiny part of the security problems.

    Its in the letters folks PQC != QKD

  10. Anonymous Coward
    Anonymous Coward

    Scott Aaronson writes

    Quantum computing news (98% Trump-free)

    As many of you will have seen, my former MIT colleagues, Lior Eldar and Peter Shor, recently posted an arXiv preprint claiming a bombshell result: namely, a polynomial-time quantum algorithm to solve a variant of the Closest Vector Problem in lattices. Their claimed algorithm wouldn’t yet break lattice-based cryptography, but if the approximation factors could be improved, it would be well on the way to doing so. This has been one of the most tempting targets for quantum algorithms research for more than twenty years—ever since Shor’s “original” algorithm laid waste to RSA, Diffie-Hellman, elliptic-curve cryptography, and more in a world with scalable quantum computers, leaving lattice-based cryptography as one of the few public-key crypto proposals still standing.

    Unfortunately, Lior tells me that Oded Regev has discovered a flaw in the algorithm, which he and Peter don’t currently know how to fix. So for now, they’re withdrawing the paper (because of the Thanksgiving holiday, the withdrawal won’t take effect on the arXiv until Monday). It’s still a worthy attempt on a great problem—here’s hoping that they or someone else manage to, as Lior put it to me, “make the algorithm great again.”

  11. Speltier

    It is much, much worse than you think it is.

    The legacy commercial crypto systems currently in use are subject to QC. The advent of QC guarantees that nation states-- first movers for QC since early tech is almost invariably atrociously expensive-- can sign an update to anyone's device, including those devices for which the nation-state has not yet obtained the keys. Who needs zero-days, complicated drive by attacks, Rowhammer, phishing attacks, rubber hoses, satchels of cash, or any of the others when you can just rewrite the software after stealing the source code which is secured by computers subject to QC attack. Presuming you can't steal the source code using simple ordinary means.

    There are a few speed bumps that can be thrown up, local keys using TPC add very slightly to the effort (or maybe not, most implementations are sadly deficient), air gap (really? What did you say your productivity is? military can afford this but can YOU?), or one can just block software updates but then mundane security holes blow up (XP users rejoice! You are ahead of the curve!) not to speak of network comms being broken.

    One needs PQC, or some other alternative new invention (at least for software updates)...

  12. Anonymous Coward
    Anonymous Coward

    Europe has already some initial recommendations/ under investigation algorithms here: https://pqcrypto.eu.org/docs/initial-recommendations.pdf

    Symmetric encryption:

    - AES-256

    - Salsa20 with a 256-bit key

    Symmetric authentication:

    - GCM using a 96-bit nonce and a 128-bit authenticator.

    - Poly1305

    Public-key encryption:

    - McEliece with binary Goppa codes using length n = 6960, dimension k = 5413 and adding t = 119 errors.

    - Quasi-cyclic MDPC codes for McEliece with parameters at least n = 2 elevated to 16 + 6; k = 2 elevated to 15 + 3; d = 274 and adding t = 264 errors.

    - The Stehlé-Steinfeld version of the NTRU lattice-based cryptosystem.

    Public-key signatures:

    - XMSS

    - SPHINCS-256

    - HFEv- multivariate-quadratic signature system

    ----

    Right now, between friends, or similar, when both can meet personally, they can exchange elliptic curve public keys or even passwords, and then encrypt and send to the other everything inside encrypted capsules.

    It is free and open source:

    https://www.fh-wedel.de/~an/crypto/Academic_signature_eng.html

    From the author:

    "There is increasing political pressure in my country(Germany) to criminalize encryption, further deteriorate civil rights and march into an Orwellian society. Thus the day may be near when we will all need steganography, hide our enforcement of privacy and need "plausible deniability".

    To get closer to this defense I introduced the concept of a "NADA Cap". NADA stands for No Access Data Available. A NADA Cap is an additional layer, which protects all format information and access data. A capped cipher file is indistinguishable from noise in toto. You can feed it to whatever "Die the Hardest" test of randomness without detecting the slightest sign of deviation from randomness. (Achieving this beautiful, perfect cipher state in Academic Signature gave me deep satisfaction.) Thus you will now always be able to claim your EC-cipher is just data from your last SETI search round, or you XOR it with your favourite Michael Jackson video and claim the cipher were just a one time pad for your illegally downloaded video. A featureless cipher is the ideal input for any steganography tool. There is always a good explanation for noise in your pictures or audio files if it truly looks like noise.

    Upon producing en elliptic curve cipher you can now tick a box "apply NADA Cap". If you do so, you will be asked for a NADA Cap key. If you use "intrinsic" the Cap key will be deterministically set from the public key data of the recipient. The "public key" should then be kept somewhat confidential, like confidential in the group of say your 10 coworkers. The recipient has to guess then, which of his private keys the file was encrypted to. Alternatively you could share a newly agreed on keyword within your group and keep that confidential. In this case you may even have your plain public key accessible to anyone. Please note, that this would also render your ECC-cipher secure against Shor's Algorithm which may become a threat after the future advent of Quantum Computing. Without knowledge of the ecc-header file, quantum computing doesn't help them shit."

    ( in. https://www.fh-wedel.de/~an/crypto/Read_me.html )

    1. Charles 9 Silver badge

      One question. How do you convince the plods of your plausible deniability so that they let you go instead of them thinking you're just hiding something under the something and keep grilling you?

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

Biting the hand that feeds IT © 1998–2021