25 Mar 2022

Post Quantum Cryptography - Quantum Computing and Cryptography

Author: TCC  /  Categories: Blogs

What is Cryptography?
Cryptography is used to secure communications by protecting the confidentiality and integrity of messages and sensitive data. Plaintext messages are transformed into “ciphertext” using a cipher and the process of encryption. Decryption is just the reverse process, to obtain the plaintext. The cryptographic “key” is a secret or known long number (with many bits) that hides the information or provides other cryptographic mechanism (e.g., digital signature) in the context of a certain cryptographic service (e.g., confidentiality, source authentication).

There are two types of cryptography referred to as “symmetric key” and “asymmetric key” or “public-key” cryptography. In symmetric-key cryptography, the same key is used for both encryption and decryption. This key needs to be kept secret by all participants in a secure network. The major difficulty is to distribute the secret keys to legitimate parties without exposing them to eavesdroppers. Public-key cryptography involves two keys that are mathematically related, but only one (the private key) is kept secret while the other one is made public. For the encryption part, anyone can send an encrypted message using the public key of the recipient, but only the person knowing the private key (the recipient) can decrypt it. Public-key cryptography is also useful for digital signatures where the owner of a private key can sign a message that anyone can verify by using the public key of that person/entity.

Among many other advantages, Cryptography is important because it provides secrecy to sensitive data (i.e., confidentiality), it protects against changes to data over an unreliable public channel (i.e., data integrity), and it ensures communicating parties that they are indeed who they claim to be (i.e., authentication). To achieve secure transmission of information in modern communication networks, Cryptography is combined with security protocols that handle message formatting and cryptographic key management.

How does Quantum Computing Impact Cryptography?
The previous section proved that Cryptography plays a very important role in electronic communication systems ensuring among other aspects that only legitimate parties can exchange messages. Also, it made the assumption that cryptographic keys and their exchange & management are always secure.

Quantum computing threatens the very basic goals of secure & authenticated communication because it claims to be able to perform certain kinds of computations that conventional computers cannot. These classes of problems include integer factorization and discrete logarithms that are not solvable today with classical computers. If successful, a quantum computer would break certain types of cryptographic keys quickly, thus rendering some cryptographic algorithms useless. In turn, these algorithms would threaten many widely used public-key cryptosystems that base their security on the assumption that the above computational problems are difficult to solve, and thus require a very long time for their messages to be decrypted. This assumption is challenged by quantum computers running special quantum algorithms that claim to be able to solve these classes of problems quickly enough in a near future. The most well-known quantum algorithms (Shor's algorithm [1] and Grover's algorithm [2]) are used to factor numbers quickly and to speedup searches, respectively. Fortunately, quantum computers can not break all types of cryptographic keys, so it is safe to believe that some cryptographic algorithms in use today that rely on symmetric keys would work in the post-quantum era.

This blog provided a short description of two types of Cryptography, to clarify which algorithms are in danger of being broken by quantum computers. The next blog will emphasize the hard-to-solve Number Theory problems that are behind these algorithms.

[1] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, 1994.

[2] L. K. Grover, "A fast quantum mechanical algorithm for database search," in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), Philadelphia, PA, 1996.


Number of views (4776)      Comments (0)


Please login or register to post comments.

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