Follow Slashdot blog updates by subscribing to our blog RSS feed


Forgot your password?
Encryption Government Communications Network Networking Security

NIST Asks Public For Help With Quantum-Proof Cryptography ( 138

chicksdaddy quotes a report from The Security Ledger: With functional, quantum computers on the (distant?) horizon, The National Institute of Standards and Technology (NIST) is asking the public for help heading off what it calls "a looming threat to information security:" powerful quantum computers capable of breaking even the strongest encryption codes used to protect the privacy of digital information. In a statement Tuesday, NIST asked the public to submit ideas for "post-quantum cryptography" algorithms that will be "less susceptible to a quantum computer's attack." NIST formally announced its quest in a publication on The Federal Register. Dustin Moody, a mathematician at NIST said the Institute's main focus is developing new public key cryptography algorithms, which are used today to protect both stored and transmitted information. "We're looking to replace three NIST cryptographic standards and guidelines that would be the most vulnerable to quantum computers," Moody said. They are FIPS 186-4, NIST SP 800-56A and NIST SP 800-56B. Researchers have until November, 2017 to submit their ideas. After the deadline, NIST will review the submissions. Proposals that meet the "post-quantum crypto" standards set up by NIST will be invited to present their algorithms at an open workshop in early 2018.
This discussion has been archived. No new comments can be posted.

NIST Asks Public For Help With Quantum-Proof Cryptography

Comments Filter:
  • by Anonymous Coward

    So, they want a code less vulnerable to math... good luck with that.

    • by ls671 ( 1122017 )

      Solution: One time pad; "mathematically unbreakable encryption",

      • Solution: One time pad; "mathematically unbreakable encryption",

        A concept born in 1882, and yet NIST is still looking for a solution in 2017.


      • Your pad is as big as the original message, so how do you send the pad to someone in a secure manner? One time pads are very secure but don't solve many real world problems.

    • by skids ( 119237 )

      That's more or less what we have now, until quantum computing is real. You don't need a quantum computer to use post-quantum cryptography [].

      What I haven't seen is how quantum simulators [] rate as a threat.

      • by gweihir ( 88907 )

        Of QC ever gets real. Strikes me a lot like "AI", which looks these days as it may actually be impossible in this universe if you want something at least as smart as a human moron. Quantum factoring has gone from 4 bits to 16 bits in 25 years or so. Even if it continues to scale like that (which it will not, there is indication it scales inverse-exponentially, so 30-100 bits or so may be the absolute upper limit), it will not be a threat to modern encryption for 50-100 years, and that is only if we continue

        • which looks these days as it may actually be impossible in this universe if you want something at least as smart as a human moron

          The progress has indeed been hyped, but that does not suggest in any way that it is impossible.
          Machine intelligence will progress in the future, sometimes quickly but mostly slow. Nobody has a clue as to how far it will go.

          • by gweihir ( 88907 )

            There are some rather strong indications it will not go very far at all. They are not reliable proof, sure, but proving a negative is notoriously hard. One is that at this time, after half a century of research into it, there still is no credible theory how intelligence could be generated artificially. The only thing we have that can mimic some aspects of intelligence is automated theorem proving, and that cannot scale up to what a smart human can do in this universe, not enough matter and energy available.

    • by gweihir ( 88907 )

      Most insight-less comment of the day. No wonder you post as AC.

  • Not Hard (Score:1, Interesting)

    This is a bad idea. We're in a weapons race, and so long as we keep playing the game, successive generations of crypto will be subject to attack. We need an end-run around the problem, which means changing how we think about encryption and data security.

    Encryption should begin with a physical exchange of one-time pads. If you open a bank account, you should get a key to it. The key is an exhaustible one-time pad you use to encrypt transmissions to and from the bank. You plug it into a machine which runs pac

    • Re: Not Hard (Score:5, Insightful)

      by thesupraman ( 179040 ) on Wednesday December 21, 2016 @11:52PM (#53535225)


      So.. You will personally go and visit each and every web site you want to access privately?
      Physically visit every inline store you want to deal with?
      Then secure all that data carefully! Remember.. If anyone gets a copy.. All security is give.. At either end!

      You need to think about things for more than 30 seconds.

      Or perhaps you should accept that armchair 'experts' like you who think this is so easy are actually a big part of the problem?

      Good crypto is hard.. QC proof crypto will be harder.. Such is life.
      The major historical mistake to avoid is over complex 'standards' that are therefore never implemented or used correctly (I am looking at you ipsec..)

      • So.. You will personally go and visit each and every web site you want to access privately?

        The obvious solution, if you could trust your government, would be to have them handle the issuance of one-time pads. Since you can't, you can still use the technology for banking, dealing with social security, or for several other purposes without undue inconvenience.

      • Ffs..

        So.. You will personally go and visit each and every web site you want to access privately?
        Physically visit every inline store you want to deal with?
        Then secure all that data carefully! Remember.. If anyone gets a copy.. All security is give.. At either end!

        You need to think about things for more than 30 seconds.

        Or perhaps you should accept that armchair 'experts' like you who think this is so easy are actually a big part of the problem?

        Good crypto is hard.. QC proof crypto will be harder.. Such is life.
        The major historical mistake to avoid is over complex 'standards' that are therefore never implemented or used correctly (I am looking at you ipsec..)

        Of course not. You build an infrastructure based on the premise of physical distribution of one-time pads. That doesn't mean you personally visit every web site you interact with; it means you assume that encryption of a website is breakable and you make the important sites uncrackable by using one-time pads. There are lots of ways to play around with the model and lots of weak points in bad implementations, but fundamentally any encryption algorithm other than that is breakable eventually. It's a much bett

        • by Anonymous Coward

          You know when laypeople that read about court cases have an opinion about how easy caselaw is if only lawyers would do this one thing they just made up? You are giving that cringy feeling to everyone here that deals in infosec.

          • by gweihir ( 88907 )

            The crypto-morons that think everything is easy and they of course understand the questions that takes an actual expert a decade or so to really get will never die out. They are a close cousin to the morons that think coding is easy.

        • You are extremely ignorant of modern encryption. Ciphers like AES have existed for 15+ years and never had any significant attacks against them. To brute force AES-256 you would exhaust all the energy in the universe. AES is also not vulnerable to attacks by quantum computers. You act like the sky is falling when in reality there have been very few fundamental breaks on cryptographic primitives. Every significant attack in the last decade has been on implementations and protocols, which would be equall
          • by gweihir ( 88907 )

            Well, to be fair, if a scaling QC ever materializes, AES-128 may be just barely vulnerable (2^64 effort). But AES-256 will still have a very comfortable security margin.

      • by gweihir ( 88907 )

        Indeed. On the plus side, we already have QC-proof symmetric encryption today. It just gives you a square-root improvement, so AES-256 is proof against a QC. The moron above probably does not know that, as a one-time pad is symmetrical encryption and hence does not improve against AES-256 in the presence og working, scaling QC in actual reality.

    • Banking with your local bank branch, fine.

      Sending in an online application to a graduate school a thousand miles away, not so much.

      Okay, I take that back: Physical "in person" key exchange could be done if you did your key exchange "in person" with agents acting on the other party's behalf, with the key sealed in a tamper-evident packaging and optionally encrypted with your public key. Oh way, scratch that optional part, or we will be reasoning in circles.

      Besides, one-time pads can be compromised.

      I do agr

    • People are thinking about one time pads in the wrong way. OTPs should be thought of not as a crypto algorithm, but rather as a time machine!

      Suppose that that Bob and Alice have a secure channel now, that they will not have in the future. They will have an insecure channel in the future. A OTP allows them to exchange messages now, that have not been written yet! A OTP is a message time machine. It allows you to securely exchange a message now, that you intend to write in the future.

      After they exchange a

    • Which machine do you plug it into? Endpoints are notoriously insecure, that's the #1 problem that needs to be fixed before anything else is even worth considering. Every current smart phone and PC is 100% hackable, no matter which operating system it is running. Modern PCs even have a separate operating system built into them, which can run independently of anything else that is running, can be activated and accessed from the network, and can access all disks and all memory. With this kind of "security" in
    • by gweihir ( 88907 )

      Protip: If anybody in an encryption-debate brings up the one-time pad, then they have just outed themselves as clueless amateurs.

  • Post backdoor (Score:3, Interesting)

    by Anonymous Coward on Wednesday December 21, 2016 @11:47PM (#53535179)

    NIST are hardly credible at this point, they previously were involved in the Dual EC fake random number generator, and now they're an agency under the Executive of Russian puppet leader, Trump. No credibility, means no trust.

    FBI has demanded backdoors, Trump has said he'll give them their backdoors. NIST are the backdoor implementers.

    • Re:Post backdoor (Score:5, Interesting)

      by skids ( 119237 ) on Thursday December 22, 2016 @12:07AM (#53535273) Homepage

      One should not trust NIST, but that doesn't stop NIST from providing a forum where trustworthy theoreticians can spar, and that's a helpful thing for them to do. It's not like they are entirely evil, just their decisions should not be trusted, but rather reviewed by the cryptomath community and either endorsed or criticized.

      Basically any government entity is going to be torn between wanting to break crypto (for cointel) and wanting to use it (for their own security or for the fact that it is pretty damn essential to a continuing economy.) They'll do some good things, and they'll do some bad things, but at least they'll do something, rather than just sitting on their hands.

    • Please implement your own encryption without any of our nasty backdoor review process! We're totally sure that it will be perfectly secure because we didn't put in a backdoor! NO REALLY!
      -- The NSA

    • In fairness to NIST, there's no evidence that had any reason to think that the elliptic curve encryption supplied by the NSA had a backdoor. In the past, the NSA had been highly helpful without pulling that sort of junk. You are correct to note that things might change under a Trump administration.
  • []

    They can write me a check.
  • They are the sheeps in the wolves clothing here. They well not allow anything they can't break.

    • by davidwr ( 791652 )

      They are the sheeps in the wolves clothing here.

      I think the NSA re-worded your message for you. Did you mean carnivors dressing up as herbivors by any chance?

  • so why are they still around if the Public constantly has to rectify them?
  • by 1 a bee ( 817783 ) on Thursday December 22, 2016 @12:15AM (#53535299)
    Here's a good wikipedia page [] summarizing the known approaches. Interestingly, most symmetric encryption schemes seem to be secure (you just need to increase the key size apparently): it's the public/private schemes that are in trouble.
  • They can take pretty much any concept and turn it into a hopelessly indecipherable mess that nobody else would ever be able to understand without guidance from the writer.... so I'm thinking they must be onto some pretty sophisticated encryption techniques right there.
  • A strange game. The only winning move is not to play." ~ War Games - 1983

    Encryption is not the solution; it's the problem.

    Quantum computers can't do a goddam thing better than what we already do except faster.

    The best new approach is to change paradigms.

    I'm not 16 anymore and I don't have enough time left to figure it out.

    That's the way to go, though.

    The problem with security today is the fucking DNA of the first computer ever built.

    The first automobile should have had seat belts.

    • It was WOPR, not WPOR.

    • Your post belies a significant misunderstanding of complexity theory. If we could do what we do today, only faster, then the world would be quite a different place than it is now. If we could constructively show that P = NP, we could make strong AI, cure most if not all diseases and revolutionize every field of science for a start. Quantum computers are able to solve problems in polynomial time (denoted QP) that classical computers are not known to be able to (good ol' P). That is a much bigger deal tha
      • ... we just have to do a little bit of planning ahead.

        That's what I said. We have to fight the problem of speed if we stick to the current paradigm.

        We need to change the rules so computers can't play.


        TRUE STORY

        I got a chess game for my Tandy 2000 back in the very early 80s. I had a hard time beating it because it would make a test move; predict my next move; make a test move based on that; rinse repeat,

        I won a lot after I figured out what was going on.

        My friends thought I was really good at chess.

        Not true.

        I fucked that computer over by making illogical moves

        • No, the "rules" are fine you just don't properly understand them. It is not about quantum computers being faster than classical computers it is about them literally being different computational machines that have different properties with respect to complexity theory. It just so happens that certain complexity assumptions we base modern cryptography on are not true in the quantum world. Fortunately there are other assumptions that still hold. It is not a "race" against faster computers, it is incorpora
          • You are not an editor, so I'm sorry you missed the digression markup, "--" that signals a change of subject.

            My bad.


            I've been in this business since Moby Dick was a minnow and I also grok quantum theory and the emergence of the computers.

            I also understand that when a problem is solved, a way to sabotage the process is to change the problem but not the solution.

            That, in a nutshell, is encryption.

            The NIST is looking for an elephant gun to kill a piss ant.

            Instead, we need to provide a solution where piss ants

  • I'm not sure I 100% understand this (but then it was Dr. Feynman who said that if you think you understand quantum mechanics then you don't)... but I read this 2002 paper by MS research that gives a method of transforming biprime factorization into an optimization problem []. Optimization problems are exactly what D-Wave's quantum annealing machine can do (very well)... so doesn't this kind of break RSA? Can somebody point me to the place where I can learn that I'm wrong and can start trusting RSA PKI again?
    • by cryptizard ( 2629853 ) on Thursday December 22, 2016 @08:25AM (#53536341)
      The reason the D-Wave doesn't "break" RSA is that it can only do quantum annealing, which as you say is basically a search algorithm. It does not give exponential increases in efficiency like a theoretical "complete" quantum processor would. For instance, using Shor's algorithm one can factor an N bit number in time something like O(log^2 N), compared to the best algorithm on a classical computer which is something like O(N^(1/3)). In the best case, quantum annealing allows one to do a search which would normally take O(N) time on a classical computer instead in O(sqrt(N)) = O(N^(1/2)). It does not break any "complexity barriers" like a real quantum computer would, just lets you solve certain problems a bit faster.

      This is a really big increase in efficiency, say going from a month worth of computation to solve a problem down to just an hour. But it is not anywhere near enough to break factoring since it would hypothetically take thousands of years to break on a classical computer. In fact, the best classical algorithm is actually slightly faster than quantum annealing because we happen to know that factoring is a problem that requires sub-exponential time to solve, O(N^(1/3)) on a classical computer vs O(N^(1/2)) on a D-Wave.
  • I'm not up on cryptography but from what I understand most encryption standards have a way to tell if a data set is decrypted correctly. Correct?

    So couldn't you implement a cypher that has no way to verify the result -- put in a key, any key, get an output file. If the proper key is used the output file is an encrypted file that can be decoded using another key, and a different encryption system that does a check for correctness.

    Wouldn't that greatly increase the difficulty in cracking the code? The file wo

    • It sounds to me like you've simply doubled the length of the key. Actually slightly worse than that due to collisions. You'd be more secure encrypting 128 bit blocks with a 128 bit key than encrypting a 64 bit block with a 64 bit key, then with another 64 bit key.

      It should be noted that making the key twice as long does NOT make it twice as hard to decrypt. Rather it SQUARES the time required. A 129 bit key takes twice as long as a 128 bit key (assuming blocks are long enough etc.) So your idea DOES ma

    • People have already tried this, they called it 2DES. It is a classical example you learn in an intro to cryptography course because it actually does not add any security at all. You can do something called a "meet-in-the-middle" attack where you try to decrypt from the right side and encrypt from the left side at the same time, looking for collisions in the middle. This means that even though you use two keys, you don't have to attack them in conjunction you can attack them separately giving you only one
  • by Anonymous Coward

    As a mathematician who occasionally works on cryptography problems, I read the statement, provided in the link, at the Federal Register, some thoughts:

    1) Quantum computers are a distant reality. From my understanding, they are still mostly theoretical. Those that do function, can only perform basic arithmetic -- or the equivalent -- or aren't considered fully quantum. So, it would have helped to define what quantum cryptography is. Presently, a key size, from my understanding, that's needed to prevent birth

    • 1) Because of Grover's algorithm, even encryption which is "secure" against quantum computers still needs twice the key length to have the same level of security as against classical computers. This is because Grover's algorithm lets you brute force a space of N possibilities in time O(sqrt(N)) instead of O(N). So if 90 bits is secure today, you would want 180 bits to be secure against quantum attacks.

      2) They can. AES goes up to 256 bits and there is no reason we couldn't make larger block ciphers if we

  • If you want unbreakable crypto... One time pad.

    and here someone says "but MOOOOOM its hard!"... no it isn't.

    How many gigs of communication do you need to secure per device? Lets presume that there are LEVELS of security that can be secured with varying levels of security.

    Naturally it is impractical to secure everything with the one time pad type encryption. Which to be clear would be a very large file stored on the sender and receiver and the data being encrypted would use only a portion of that seed data t

    • The one-time pad replaces a symmetric encryption scheme. We have AES which was invented by academic cryptographers unaffiliated with any government organization and has been vetted for over 15 years by academic and industrial cryptographers with no substantial weaknesses found. It would take all the energy in the universe to brute force one AES-256 key. You are replacing something that works and is secure with something much more cumbersome for no appreciable reason except that you read somewhere the one-ti
      • "NIST Asks Public For Help With Quantum-Proof Cryptography" ...

        • You obviously didn't read even the summary then because they are looking for replacements to asymmetric encryption schemes dude. Sorry for assuming that you read the paragraphs following the headline my bad.
          • Doesn't address the quantum aspect of the query. Define the danger of quantum cracking?

            Do you know how that is supposed to work? If you think your 256 bit key is going to hold against what that promises to be then maybe you should look that up.

            That said, I haven't seen any practical evidence of it actually working. So maybe it doesn't matter.

            Your sad dive into rudeness however is unfortunate. Why is your ego so small that when your obvious autism is revealed you have to lash out.

            Calm down, dude. You're auti

            • Cool story bro.
              • The air is let out of your pretensions and this is all you're left with...


                • Lol ok. What pretension? I literally have a PhD in cryptography. I've just realized that you are proud of your ignorance and it's not worth talking to you any more. I've gotten like 30 +informative upvotes on this article. Some people learned something. You are a lost cause. I read somewhere recently... I can't remember where... "I've decided to stop wasting my time responding." Have a good day bro.
                  • Still no response to the quantum bit that made you run away like a kicked dog. Pretension... I call you out on it and you claim a PhD... Irony.

                    • Run away? Sorry, I already answered your comment at least twice on this article responding to other people before you "challenged" me (go look if you don't believe it). I was just tired of responding to your arrogant uninformed bullshit. Quantum attacks reduce the security of all block ciphers by half due to grovers algorithm. AES-256 would still have 128 bits of effective security which is more than enough. Your comment about physical security is also ill informed btw google Software Guard Extensions and
    • How do I secure my one-time pads? WIth more one-time pads? Is it one-time pads all the way down?

      • ... It is assumed that the opposition doesn't have physical access to your system or the target system. Rather the assumption is that the encryption is required any other system besides the origin and destination of the message. If you need to secure things so that your own system isn't compromised then you're basically fucked via the first rule of computer security...

        Physical security. You either have that or kill yourself.

  • if you want to crack encryption with a powerful computer, you need a means to algorithmically verify your guesses. This is what you need to make hard. Essentially you need a way of encoding messages such that there are many many plausible decryptions. As such, if you took a dictionary of the most common 5000 English words, and forced all communications to use those, and only standard English grammar, you could algorithmically map strings of integers to English words and phrases. There are many ways to do th

    • This is called deniable encryption and there are information theoretic lower bounds on what you can actually accomplish with this unfortunately. Each ciphertext has to be carefully coded with full knowledge of what "domain" it comes from in order to produce other, plausible messages. It is incredibly cumbersome and not usable for real-world applications. For simple "spy games" it could be useful, but given the incredibly diversity of data that is encrypted on an average persons computer it is not practic
  • Considering the quantum computers seem to be mostly built on hype and not capable of beating regular computers in speed or cost I would not worry much about this.
    • I think you are thinking of the D-Wave computer, which is not actually a quantum computer in the most general sense. The great thing about quantum computers is that they actually break some complexity barriers that exist for classical computers, factoring being one of them. If we ever get a quantum computer that can handle a few hundred qubits then it would be able to instantly factor existing RSA moduli, compared to hundreds or thousands of years for a classical computer. Right now I think the record is

  • If I have an idea for creating encryption that's invulnerable(or extremely resistant) to attack by quantum computers, I'm going to the patent office not NIST.

  • Microsoft already did this.

    Do we the tax payers have to pay the government to make free (and probably bloated, not working) versions of everything?

    I don't see why anyone uses NIST outside the government. Almost no one does unless they have huge budgets not requiring profit.
  • Can God create a rock so heavy that He can not lift it? OK so quantum computers can solve problems that appear to us to be of infinite complexity. So could a quantum computer be programmed to create a password of an even more complex infinity ? I still like the idea of a ladder of passwords being created such that every rung of the ladder need be answered in frequent, quick steps. That way even a quantum computer could not solve the password fast enough and the first rung of the ladder would ch
    • The problem with this is that almost all encryption and decryption is done locally by an individual client. If the bad guy has the message, it is just inert data. The only person enforcing any kind of time constraints on him would be his self so he will just not do it. Moreover, if you are trying to use a password to login to a server (I think this is the problem you are trying to solve) then there is no need to do anything fancy like this because there are already existing zero-knowledge password protoc
  • There Came An Echo, anyone?

When a fellow says, "It ain't the money but the principle of the thing," it's the money. -- Kim Hubbard