Synopsis of our full article:
Though the research on quantum computers is still facing big challenges, there is also some progress in this field. The National Institute of Security and Technology (NIST) recently published a report on Post-Quantum Cryptography which informs about new developments. They believe that it is time to think of quantum-safe primitives, and announced open calls to encourage researchers to work on proposals. This continues prior work in the field by D. J. Bernstein and others.
Quantum computers would endanger all cryptographic protocols which are based on prime factorization and discrete logarithms. Private keys used for transactions in Ethereum and Bitcoin would no longer be safe. Shor`s algorithm could be used to discover them in quantum polynomial time. We will give a glimpse of the idea of how this algorithm works, starting with Deutsch´s quantum algorithm which is easier to understand but shows already some basic principles.
Some cryptographic protocols, including code-based, lattice-based or hash-based cryptography, would already survive quantum computers. De Feo and Jao´s proposal — the Supersingular Isogenous Diffie-Hellman Protocol — which we discuss in the article, has the advantage of being exponentially complex while having much smaller key-size compared to these other protocols. The very recent work by Castello-Longa-Naehrig presents a high-speed and constant-time implementation of SIDH which pushes this proposal further for practical use. We will briefly discuss their interesting proposals.
Permalink