Understanding Complexity of Cryptographic Algorithms

1. Introduction

In this tutorial, we’ll examine computational complexity issues within cryptographic algorithms.

The discussion will not focus on any concrete cryptographic algorithm, but we’ll expose their basic general laws.

2. Symmetric and Public Key Cryptosystems

Suppose two people, and , want to communicate in a secret form. wants to send a message so that only can understand its content. To do this, it uses a protocol called cryptosystem or cipher, which produces a cryptogram or ciphertext of the original message via an encryption function :

   

uses a decryption function , basically the inverse function of , to get the original message:

Encryption and decryption can be considered components of the coding and decoding subsystems in a classic communication mechanism:

Suppose a third person able to intercept the message that sent to . The most unfavorable condition forces us to consider the fact that knows the protocol used by and . At this point, can decrypt the message by simply applying .

Therefore, we need an additional element to make communication secure. This element is a secret key, or simply a key, known to and without which cannot decrypt the message despite knowing the communication protocol used.

But does have to know ‘s secret key? Until the end of the twentieth century, most cryptographers would have answered this question in the affirmative. In this case, we talk about symmetric key systems, and their security rests on the secrecy of the key.

In 1976, Diffie and Hellman published the article “New directions in cryptography“, in which they proposed public-key cryptosystems. In them, encrypts the message with a public domain key or public key, that can decrypt with his private key, known only to him. Anyone can send an encrypted message to , but only can know its content. This eliminates the problem of key security, the weak point of symmetric cryptosystems.

3. Classical vs. Modern Cryptography

In the scenario where and suspect a potential attack by , we can ask ourselves two fundamental questions:

1. What can do with the message-cryptogram pair it gets?
2. Which result, from the point of view of security, is satisfactory for and ?

Depending on how we answer these questions, we have two different approaches: classical vs. modern cryptography.

To deepen the issues, we recommend the excellent text by Talbot and Welsh “Complexity and Cryptography, an introduction“.

3.1. Classical Cryptography

Based on Information Theory and largely elaborated by Shannon, for which it is known as the information-theoretic approach. The basic assumption is as follows:

The cryptogram must not reveal any information about the message.

This assumption leads to the concept of perfect-secrecy that we can formalize as follows:

   

This formula simply says that given a concrete message between a set of possible messages and given a concrete cipher between a set of possible ciphers , the probability of is independent of . Even if has access to the cryptogram of the message, he cannot learn anything about its content.

One problem with this approach is that a perfect-secrecy system requires a key length at least as large as any message that can be encrusted with it, making it unsuitable for modern communication systems, such as the Internet.

3.2. Modern Cryptography

Modern cryptography takes a completely different approach. The basic assumption is:

It doesn’t matter if a cryptogram reveals information about the message. What matters is whether can efficiently extract this information.

If we assume that has an unlimited computational capacity, then the previous proposition does not hold. Hence, modern cryptography considers that:

has limited computational resources.

But if this is true for , it is also true for and , which leads to an additional assumption:

There are mathematical functions that are easy to compute but difficult to invert, called one-way functions.

In this scenario, and can encrypt messages with few computational resources, but can get information from the message only if it has high computational capabilities. The last assumption clarifies the importance of issues related to the complexity of computational procedures, therefore to the ease or difficulty of their implementation.

Modern cryptography is the one used basically today in encrypted transactions and communications. However, any system that allows exponentially increasing computational capabilities, such as the quantum computer, is potentially endangered.

4. Framework of the Complexity Theory

Any computing system, including cryptographic ones, can only use computable functions. What matters is the ease or difficulty in making the calculation.

Suppose a specific problem, for example, sorting a set of numbers. We’ll call this problem . Complexity Theory tries to answer questions like these:

1. is inherently easy or difficult to solve?
2. Given and , which is easier to solve?

To give an answer, we classify algorithms into different complexity classes, which group computational procedures with common characteristics, according to the following ideas:

1. We measure the execution time of an algorithm in terms of the number of elementary operations.
2. The running time of an algorithm depends on the size of the input.

The -notation establishes a symbolism to express these ideas. An algorithm of complexity , for example, must perform a number of elementary operations equal to the square of the size of the input.

5. Complexity Classes