16 Post Quantum Crypto for Dummies for quantum computers has an even more critical impact on the hardness of these problems and thus on all cryptographic systems based on these computational problems. Shor’s Algorithm Shor’s algorithm solves integer factorization and discrete logarithms in polynomial time on a quantum computer 54, 55 (see Figure 1.2). More generally, Shor’s algorithm efficiently solves the hidden-subgroup problem for finite Abelian groups 39. This directly breaks cryptographic primitives that are based on integer factorization, e.g., RSA, and the discrete-logarithm problem, e.g., Diffie-Hellman and ECC. The impact of Shor’s algorithm cannot practically be mitigated by increasing the security parameters of the affected primitives, because the computational complexity of a quantum-computer attack using Shor’s algorithm is similar to the computational complexity of using RSA and ECC. Choosing the security parameters large enough to defend against attacks by quantum computers makes using RSA and ECC itself infeasible. Therefore, the only cryptographic primitives listed above that are able to withstand attacks by quantum computers are AES and hash functions with sufficiently large security parameters. All commonly used asymmetric primitives are going to be broken by quantum computers using Shor’s algorithm. However, we are not unprepared: There are alternatives for the threatened primitives. One way to protect data against quantum computers is to use quantum technology itself in a constructive way. There are schemes for quantum key distribution (QKD) that rely on quantum physics as opposed to mathematics. However, this does not make QKD schemes naturally secure against hacking 41; they require defenses against physical attacks. An inherent problem of QKD is its requirement of a pre-shared secret for mutual authentication. Providing pairwise pre-shared secrets for a large number of communication endpoints in advance is infeasible for many applications. Furthermore, these schemes typically require point-to-point Fiber-optic connections or line-of-sight in order to transmit photons from sender to receiver. Therefore, they are not compatible with the existing communication infrastructure and they do not scale to a communication network of the size of the Internet. They are also not useful for mobile communication, e.g., mobile phones, car-to-x communication, and wireless sensor networks. A more practical solution therefore is to use different cryptographic schemes that rely on hard problems that cannot be solved efficiently on quantum computers. Cryptographic algorithms that are assumed to be secure against attacks
PQC_for_Dummies
To see the actual publication please follow the link above