3 Oct 2022

Post Quantum Cryptography - Quantum-Safe Cryptographic Algorithms

Author: TCC  /  Categories: Blogs

We mentioned in a previous blog that not all cryptographic algorithms are vulnerable to quantum attacks. One such cryptographic primitive and the protocols that use it can be deemed quantum-safe only if enough research was dedicated to prove that they can resist all known quantum algorithms attacks. We also mentioned that algorithms relying on the intractability of factoring or finding the discrete logarithm of large numbers (with hundreds or thousands of bits) will be the first ones broken by quantum computers. Such cryptosystems include RSA, DSA, DH, ECDH, ECDSA and other variants of these ciphers. Thus, any security protocol, product or cryptosystem that derives security from these public-key ciphers is in danger to be rendered unusable.

The algorithms that are somewhat vulnerable to quantum attacks, but can be easily “repaired” include symmetric-key algorithms (e.g., AES). The claim is that they can be broken faster by a quantum computer running Grover's algorithm than by a classical computer. However, if we double the cipher's key length, the task of a quantum computer to break the algorithm is just as hard as for a conventional computer. Therefore, AES-128 is as difficult for a classical computer to break as AES-256 would be for a quantum computer.

Unlike AES that can adapt to a quantum attack by increasing its key size, ciphers like RSA and ECC are not quantum safe because they cannot increase their key sizes in a practical way, to thwart this attack. To have an idea about the required resources, a 3072-bit RSA key would be broken with a quantum computer with a few thousand logical qubits. Because the number of logical qubits scales linearly with the bit length of the RSA key, moving to a larger RSA key size to block a quantum attack (until a larger quantum computer is invented) means doubling the size of an RSA or ECC key. That increases the running time of the cipher on a conventional computer by a factor of 8 because the algorithm complexity of the signature generation and decryption operations is , where is the size in bits of the modulus used in the modular arithmetic RSA calculations (, ). If we assume that a quantum computer attack power could double every two years, then the running time of the RSA cipher on a conventional computer increases by a factor of 8 (every two years). This makes the use of such ciphers on a classical computer impossible because this rate of growth outpaces Moore's law. Therefore, key sizes become rapidly impractical because of the data rate and channel bandwidth required to transmit the key information over an electronic medium.

The conclusion is that symmetric-key ciphers are believed to be quantum-safe, whereas protocols that rely exclusively on ciphers like RSA and ECC are vulnerable to quantum attacks. Thus, the requirement is to migrate to quantum-safe ciphers. A snapshot of the key sizes and security strengths is provided in the table below, extracted from NIST IR 8105 “Report on Post-Quantum Cryptography” [1].

The next blog will provide more details about research & design directions for the generation of quantum-safe cryptographic algorithms.

Bibliography
[1] L. Chen et al., "Report on Post-Quantum Cryptography," NIST - U.S. Department of Commerce, Gaithersburg, MD, 2016.

Print

Number of views (2962)      Comments (0)

Tags:

Please login or register to post comments.

Name:
Email:
Subject:
Message:
x
Cipher One

CipherONE® Optimized Network Encryption

Our solutions meet TCC's CipherONE Optimized Network Encryption best-in-class criteria for maximum cryptographic strength, and are optimized for performance and ease of use for our customers.

Read More