Post Quantum Cryptography

https://access.redhat.com/blogs/766093/posts/3031361?sc_cid=7016000000127ECAAY

The SSL/TLS protocol uses RSA, Diffie-Hellman (DH) or Elliptic Curve Diffie-Hellman (ECDH) primitives for the key exchange algorithm.

RSA is based on the fact that when given a product of two large prime numbers, factorizing the product (which is the public key) is computationally intensive, but a quantum computer could efficiently solve this problem using Shor’s algorithm. Similarly, DH and ECDH key exchanges could all be broken very easily using sufficiently large quantum computers.

For symmetric ciphers, the story is slightly different. It has been proven that applying Grover’s algorithm the strength of symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover’s algorithm that AES-128 has against classical brute-force search. Hashes are also affected in the same way symmetric algorithms are.

Therefore, we need new algorithms which are more resistant to quantum computations. This article introduces you to 5 proposals, which are under study.

12 Comments

  1. Tomi Engdahl says:

    World’s Leading Physicist Says Quantum Computers Are “Tools of Destruction, Not Creation”
    by Patrick Caughill on August 9, 2017
    https://futurism.com/worlds-leading-physicist-says-quantum-computers-are-tools-of-destruction-not-creation/

    Weapon of Mass Disruption

    Quantum Computers are heralded as the next step in the evolution of data processing. The future of this technology promises us a tool that can outperform any conventional system, handling more data and at faster speeds than even the most powerful of today’s supercomputers.

    However, at the present juncture, much of the science dedicated to this field is still focused on the technology’s ultimate utilization. We know that quantum computers could manage data at a rate that is remarkable, but exactly what kind of data processing will they be good for?

    This uncertainty raises some interesting questions about the potential impact of such a theoretically powerful tool.

    “No encryption existing today would be able to hide from the processing power of a functioning quantum computer.”

    Last month, some of the leading names in quantum technologies gathered at the semi-annual International Conference on Quantum Technologies in Moscow. Futurism was in attendance and was able to sit and talk with some of these scientists about how their work is moving us closer to practical quantum computers, and what impact such developments will have on society.

    What is it about quantum computers that would incite such a claim? In the end, it comes down to one thing, which happens to be one of the most talked about potential applications for the technology: Breaking modern cryptography.
    With Great Power…

    Today, all sensitive digital information sent over the internet is encrypted in order to protect the privacy of the parties involved. Already, we have seen instances where hackers were able to seize this information by breaking the encryption. According to Lvovsky, the advent of the quantum computer will only make that process easier and faster.

    In fact, he asserts that no encryption existing today would be able to hide from the processing power of a functioning quantum computer. Medical records, financial information, even the secrets of governments and military organizations would be free for the taking—meaning that the entire world order could be threatened by this technology.

    The consensus between other experts is, essentially, that Lvovsky isn’t wrong. “In a sense, he’s right,” Wenjamin Rosenfeld, a physics professor at the Ludwig Maximilian University of Munich, stated in an interview. He continued, “taking a quantum computer as a computer, there’s basically not much you can do with this at the moment;” however, he went on to explain that this may soon be changing.

    To break this down, there are only two quantum algorithms at the moment, one to allow a quantum computer to search a database, and the other, Shor’s algorithm, which can be used by a quantum computer to break encryption.

    Quantum computers may not be capable of the physical destruction of a nuclear bomb, but their potential application is the digital equivalent.

    Reply
  2. Tomi Engdahl says:

    Joshua Holden / Nautilus:
    How quantum computers will speed up the breaking of public-key cryptography and how “post-quantum cryptography” researchers are trying counter that threat

    How Classical Cryptography Will Survive Quantum Computers
    http://nautil.us/blog/-how-classical-cryptography-will-survive-quantum-computers

    Some are looking at ways to “fight quantum with quantum”—but there is another (and cheaper) option.

    The methods of post-quantum cryptography have not been used in the past because they are less efficient than current public-key methods, but they are getting better. In August 2015, the N.S.A. announced that it was planning to introduce a list of approved cryptography methods that would resist quantum computers. In April 2016, the National Institute of Standards and Technology followed suit, starting a public vetting process lasting 4 to 6 years.

    That’s not an unreasonable amount of time to need in order to be sure that a cryptographic method is really secure.

    Four to six years is also not an unreasonable amount of time to wait for a new cryptographic standard. Government agencies are concerned about protecting data that might have to remain secure for decades into the future, so they are preparing now for computers that could still be 10 or 20 years into the future.

    If you are worried about quantum criminals getting your credit card number off of the Internet, you can breathe a little easier. When quantum computers come, cryptographers expect to be ready for them. And you will be able to keep shopping safely without buying your own quantum computer, although I’m sure Amazon will be happy to sell you one.

    Reply
  3. Tomi Engdahl says:

    The quantum computing apocalypse is imminent
    https://techcrunch.com/2018/01/05/the-quantum-computing-apocalypse-is-imminent/?utm_source=tcfbpage&sr_share=facebook

    According to experts, quantum computers will be able to create breakthroughs in many of the most complicated data processing problems, leading to the development of new medicines, building molecular structures and doing analysis going far beyond the capabilities of today’s binary computers.

    The National Security Agency, too, has sounded the alarm on the risks to cybersecurity in the quantum computing age.

    Reply
  4. Tomi Engdahl says:

    IBM warns of instant breaking of encryption by quantum computers: ‘Move your data today’
    https://www.zdnet.com/article/ibm-warns-of-instant-breaking-of-encryption-by-quantum-computers-move-your-data-today/

    Welcome to the future transparency of today as quantum computers reveal all currently encrypted secrets — a viable scenario within just a few years.

    Reply
  5. Tomi Engdahl says:

    Security Needs a Quantum Leap
    https://www.eetimes.com/author.asp?section_id=36&doc_id=1333341

    Engineers need to start studying the trade-offs of different post-quantum cryptography techniques so they are ready when quantum computers arrive.

    No one is sure when (or really even if) quantum computers will become practically useful, but some experts believe that within 10 years a quantum computer could be capable of breaking today’s cryptography. Google, Microsoft, IBM and Intel, as well as numerous well-funded startups, are making significant progress toward quantum computers. And scientists around the world are investigating a variety of technologies to make quantum computers real.

    Quantum computing strikes at the heart of the security of the public key infrastructure used to secure communications with keys typically encrypted with RSA and Elliptic Curve Cryptography (ECC). A quantum computer could easily break these algorithms currently used to authenticate the identity of senders and receivers and protect data from manipulation.

    Today’s algorithms are secure because they are based on intractably hard mathematical problems in number theory. However, they are only intractable for a classical computer where bits can have only one value (either 1 or a 0). In a quantum computer where k bits represent 2k values, RSA and ECC can be solved in polynomial time using a technique known as Shor’s algorithm.

    Once quantum computers can scale to work on tens of thousands of bits, today’s public key cryptography becomes immediately insecure. Simply changing parameters will not suffice–the whole industry will have to switch to completely different algorithms.

    The sky isn’t falling, but it is vital to begin transition planning now. Post-quantum cryptography has received an increasing amount of attention from both academics and from industry.

    Proposed post-quantum cryptographic algorithms are based on various underlying hard problems widely believed to be resistant to attacks even with quantum computers. These fall into the following classes of cryptography:

    Multivariate
    Hash-based
    Code-based
    Supersingular elliptic curve isogeny

    Each of these classes has various pros and cons.

    Reply
  6. Tomi Engdahl says:

    Microsoft Adds Post-Quantum Cryptography To an OpenVPN Fork
    https://tech.slashdot.org/story/18/06/06/138258/microsoft-adds-post-quantum-cryptography-to-an-openvpn-fork?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+Slashdot%2Fslashdot%2Fto+%28%28Title%29Slashdot+%28rdf%29%29

    Microsoft recently published an interesting open source project called “PQCrypto-VPN” that implements post-quantum cryptography (PQC) within OpenVPN. Being developed by the Microsoft Research Security and Cryptography group, as part of their research into post-quantum cryptography, this fork is being used to test PQC algorithms and their performance and functionality when used with VPNs.

    Microsoft Adds Post-Quantum Cryptography to an OpenVPN Fork
    https://www.bleepingcomputer.com/news/microsoft/microsoft-adds-post-quantum-cryptography-to-an-openvpn-fork/

    Microsoft’s PQCrypto-VPN is published on Github and allows anyone to build an OpenVPN implementation that can encrypt communications using three different post-quantum cryptography protocols, with more coming as they are developed. These protocols are:

    Frodo: a key exchange protocol based on the learning with errors problem
    SIKE: a key exchange protocol based on Supersingular Isogeny Diffie-Hellman
    Picnic: a signature algorithm using symmetric-key primitives and non-interactive zero-knowledge proofs

    https://github.com/Microsoft/PQCrypto-VPN

    Reply
  7. Tomi Engdahl says:

    Security Startup Quantum Xchange Promises Unbreakable Quantum-Safe Encryption
    https://www.securityweek.com/security-startup-quantum-xchange-promises-unbreakable-quantum-safe-encryption

    Quantum Xchange Raises $10 Million, Launches Quantum Key Distribution Service

    Bethesda, MD-based start-up Quantum Xchange has announced $10 Million Series A funding from New Technology Ventures, and the launch of the first commercial quantum key distribution (QKD) service in the U.S. The funding will support the deployment of a fiber network serving the Northeast Corridor from Washington D.C. to Boston, connecting the financial markets on Wall Street with back office operations in New Jersey.

    The business premise is simple. The budding arrival of quantum computers will make current strong public key encryption immensely weak. Where current computing power would take too long or too many computers to make factoring large numbers feasible, one quantum computer could factor current public key lengths in a matter of minutes. Public key encryption will not provide security against quantum computers.

    Reply
  8. Tomi Engdahl says:

    Quantum encryption combats threat posed by quantum computing hacks
    https://www.lightwaveonline.com/articles/2018/07/quantum-encryption-combats-threat-posed-by-quantum-computing-hacks.html?cmpid=enl_lightwave_lightwave_datacom_2018-07-03&pwhid=6b9badc08db25d04d04ee00b499089ffc280910702f8ef99951bdbdad3175f54dcae8b7ad9fa2c1f5697ffa19d05535df56b8dc1e6f75b7b6f6f8c7461ce0b24&eid=289644432&bid=2161879

    With the impending advent of quantum computing threatening to increase the horsepower of cyberattacks, ADVA Optical Networking has reported on its participation in a pair of efforts to enable quantum-level encryption. One, led by the University of Cambridge, has seen the deployment of fiber links in the UK fortified with a quantum key distribution (QKD) scheme. The second trialed a potentially even greater level of security via a post-quantum public-key encryption system on a route that leveraged multiple research and education (R&E) networks.

    Reply
  9. Tomi Engdahl says:

    Key Researchers on the Pace and Peculiarities of Developing Quantum Computing—and the Possible End of Bitcoin
    https://spectrum.ieee.org/view-from-the-valley/computing/hardware/quantum-computing-researchers-on-the-pace-of-development-managing-a-quantum-group-and-the-end-of-bitcoin

    On when we’ll have a useful quantum computer:

    “We are at the point now where we have the science developed so far that we see a path to scaling it and building a quantum computer that solves problems in the next five to ten years,” predicted Microsoft’s Troyer.

    “I don’t want people to get the idea that if we don’t get this working in the next couple of years, it’s not going to work.”
    —John Martinis, Google

    “We are looking for scientist/engineers, [people] who can think as an engineer when they need to, and as a scientist”

    “If you have a secret today, don’t encrypt it with RSA if you believe quantum computing is coming.”
    —Matthias Troyer, Microsoft

    On the end of Bitcoin:

    In response to an audience question about the future of Bitcoin in the quantum computing era, Troyer pointed out that his group calculated that once a quantum computer can be built with just over 2000 qubits, “you can crack Bitcoin.”

    “We joke that then we can fund all of our programming” with Bitcoin, he said.

    Reply
  10. Tomi Engdahl says:

    Quantum encryption combats threat posed by quantum computing hacks
    https://www.lightwaveonline.com/articles/2018/07/quantum-encryption-combats-threat-posed-by-quantum-computing-hacks.html?cmpid=enl_lightwave_lightwave_datacom_2018-07-10&pwhid=6b9badc08db25d04d04ee00b499089ffc280910702f8ef99951bdbdad3175f54dcae8b7ad9fa2c1f5697ffa19d05535df56b8dc1e6f75b7b6f6f8c7461ce0b24&eid=289644432&bid=2165892

    With the impending advent of quantum computing threatening to increase the horsepower of cyberattacks, ADVA Optical Networking has reported on its participation in a pair of efforts to enable quantum-level encryption. One, led by the University of Cambridge, has seen the deployment of fiber links in the UK fortified with a quantum key distribution (QKD) scheme. The second trialed a potentially even greater level of security via a post-quantum public-key encryption system on a route that leveraged multiple research and education (R&E) networks.

    Current optical networks can enjoy a significant amount of security from data transmission breaches, says Jörg-Peter Elbers, senior vice president, advanced technology, at ADVA. Layer 1 encryption capabilities using Diffie-Hellman key exchange techniques are widely considered sufficient to withstand de-encryption attempts that use current technology. However, security experts fear that Diffie-Hellman won’t hold up to the power of attacks that use quantum computing resources. More robust key exchange and, potentially, encryption algorithms likely will need to be employed, Elbers explains.

    Post-quantum key exchange

    Meanwhile, security specialists also have interest in quantum-sturdy techniques that can augment existing security schemes quickly and efficiently. ADVA participated in a demonstration of such an approach alongside Broadnet, GÉANT, NORDUnet, PSNC, and UNINETT. Here, the partners demonstrated the use of “post-quantum” key encryption based on a variant of the Niederreiter scheme. The scheme has been around for some time, explained Elbers. It uses larger keys than those typically employed in Diffie-Hellman; optical transport systems now support transmission rates great enough that the larger key size no longer significantly degrades transmission efficiency. One benefit of the approach is that it can be implemented at the network endpoints, leaving the rest of the network untouched. Thus, such key encryption can complement any encryption scheme the network has in place. The Niederreiter scheme is one option under consideration within the NIST Post Quantum Encryption Standardization effort.

    The field trial saw the Niederreiter-based approach implemented on a 2,300-km link from Poznań, Poland, to Trondheim, Norway.

    Reply

Leave a Comment

Your email address will not be published. Required fields are marked *

*

*