Misunderstanding Post-Quantum Crypto

In this article I try to get rid of some basic misunderstandings of post-quantum cryptography which ordinary applied IT professionals might have. This is turn prevents them from having a closer look on post-quantum cryptography which might be useful already today. This article is intended for general audience as well and is not written in a "complex" language of hardcore science.

I take a bunch of questions which were asked after the djb's talk and give answers to them. This article is easy to scroll through and check up your knowledge about post-quantum crypto needed for the practice today. A post-quantum crypto intro will help you to intuitively get the answers to the questions before even reading mine.

Quantum Computing and Cryptography

So what's the deal here? Classical crypto (used today) is based mainly on the theory of computational complexity. E.g. if a regular (not quantum) computer has to do very many steps to break the crypto, then this crypto is considered to be secure.

In the post-quantum era when a quantum computer will be created and will be practical enough to run attacks on it things will change. A quantum computer works (well, will work) entirely differently from a regular one.

Algorithms for quantum computer often do not have "steps" in the sense of the regular computer algorithms. Instead, a quantum computer is able to solve some problems just right after they are formulated and given to it by "matching" a random solution against the problem formulated very quickly. So to say an instant brute-force for some of the problems.

Because of this property even the tasks which require multiple steps of a quanto-algorithm can be performed by a quantum computer in a very much reduced number of "steps" compared to a regular computer. This makes some of the crypto we have right now not secure anymore. It can be broken much faster on a quantum computer.

One of the tasks sped up by quantum computations happens to be integer factorization on which many of the modern crypto algorithms are based. The Shor's algorithm could be used for this.

Disclaimer On this web site you might read about or get access to various kinds of software and technology, including but not limited to libraries, operating systems, software for communications, mobile phones and tablets, Android software and Linux, even cars and motorcycles, security and penetration testing software, software used in security research and forensics, some samples of software which can be used (elsewhere) for malicious or illegal purposes. You will read about or be provided with the ways to change it, to operate it and to use it. You might find advice and recommendations, which are only an opinion, and not a legal advice or commercial recommendation..
Bear in mind, please, that everything you do, you do solely at your own risk and responsibility. In no way the author of this web site, information, graphics and other materials presented here or related to it can be made liable or anyhow else responsible for your own actions as well as actions of any third party and their direct or indirect results or consequences with or without the use of this information as well as the software, technology and systems mentioned and/or presented here, no matter if developed by the author or by any third party.
In no way it is guaranteed that you will meet any suitability for any particular purpose, safety, security, legality or even simply functioning of the software and systems described here. You have to make sure each time yourself, whether what you do, is really what you intend to do, and that you are ready to be yourself responsible for. All the recommendations and experiences described here are the opinions of corresponding authors and are to be taken with care and own full responsibility.
The software provided on or through this web site, linked to from this web site or anyhow else related to this web site is provided by the corresponding authors on their own terms. We provide all the software here as is without any guarantees to you. You are responsible for deciding whether it is suitable for you or not. You are also responsible for all direct or indirect consequences of using this software.
Other web sites linked to from the current one are out of the author's control, we can not guarantee anything about their content, its quality or even legality. We can not be liable for any use of the linked to web sites or of the information presented there.
We reasonably try to keep this website running smoothly and to deliver information to the best of our knowledge corresponding to the state of the art at the times when the information is composed, usually presented together with the information, and out of good intents. We can not however guarantee and can not be liable for this website being temporarily or permanently unavailable, presenting unreliable information or software, or any other similar or not malfunctioning or functioning not up to your expectations as well as any consequences which might result from this site's operation.

Once a quantum computer has been built a number of algorithms get declared absolutely insecure. We might want to stop using these algorithms already now, in the same way NSA is going to - Tip: check this link as well for the modern recommended key sizes.

The crypto-algorithms currently known to be secure even against a quantum computer (or against known algorithms for it) go commonly under the term of post-quantum crypto.

Now we go on to the questions to bust some myths!

Do I need a quantum computer to use post-quantum crypto?

No, because the algorithms in post-quantum crypto are formulated for regular computers and can be used today.

Why would I care about 1MB large keys and signatures in post-quantum era?

Sometimes post-quantum algorithms require large keys. Well, you need to care about key sizes right now, not in the post-quantum era! See the next question!

Why using post-quantum crypto now?

Because when a quantum computer is build you will be readily safe, no urgent need for transitions, no revelations (from a Snowden 2.0), that you have communicated insecurely for a revealed period of time.

Quantum computers are believed to arrive in the upcoming few tens of years.

How much time does a Quantum computer takes to crack something?

Quantum computers work differently from regular computers. The algorithms for them often do not have "steps" or sequences of commands in the sense we know regular computers work. They are not to be compared to regular computers in the time needed to do something.

Answering practically, some cracking will be possible instantly!

Wait, what about the Perfect Forward Secrecy?

Bad news, you'll not be safe even if you use OTR. The perfect forward secrecy is a property of a crypto system to keep your communication safe if your stored long-term keys get compromised. This is achieved among others by using ephemeral keys which are exchanged, used once and then forgotten, for every single message. Bad news is that these exchanges and maybe the algorithms which use the keys themselves could get broken by a quantum computer.