23.6 Post-Quantum Cryptography? – Introduction to Cryptography with Coding Theory, 3rd Edition

23.6 Post-Quantum Cryptography?

If a quantum computer is built (see Chapter 25), cryptosystems based on factorization or discrete logs will become less secure. An active area of current research involves designing systems that cannot be broken by a quantum computer. Some of the most promising candidates seem to be lattice-based systems since their security does not depend on the difficulty of computing discrete logs or factoring, and no attack with a quantum computer has been found. Similarly, the McEliece cryptosystem, which is based on error-correcting codes (see Section 24.10) and is similar to the system in Section 23.5, seems to be a possibility.

One of the potential difficulties with using many of these lattice-based systems is the key size: In the system in Section 23.5, the public key B requires 3002=90000 integer entries. Many of the entries of B should be large, so let’s say that we use 100 bits to specify each one. This means that the key requires 9×106 bits, much more than is used in current public key cryptosystems.

For more on this subject, see [Bernstein et al.].