What is the time complexity of the basic components of a symmetric cipher?

Question

I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in symmetric ciphers. In particular:

1. matrix multiplication (including permutation matrices)
2. XOR of bit strings
3. expansions, for instance expanding 64 bits to 128 bits
4. bit shifts
5. permutations using a P-box (say the one in PRESENT)
6. substitutions using an S-box (again, say the one in PRESENT)
7. combining the operations (as above or other operations)

Related to item 1: If I multiply (say) $vP$ where $v$ is a $1 \times n$ vector and $P$ is an $n \times n$ permutation matrix I see $1 \times n \times n$ multiplications and $n \times n$ XORs (assuming bits). So am I right to sat $O(vP) = n^2 + n \approx n^2$ ?

Related to item 2: a linear operation so I assume $O(1)$ for each XOR and therefore $O(n) = n$ for $n$-bit string XOR another $n$-bit-string.

Related to item 3: If expanding $64$ bits to $128$ bits then it seems there are $128$ operations so $O(n) = n$

Related to item 4: intuitively I should say $O(1)$ for each bit shift and therefore for $n$ bit-shifts $O(n)=n$.

Related to items 5 and 6: I really have little idea. But if it is the $PRESENT$ P-box then I suppose $64$ operations and therefore $O(n=64)=n$. As for the S-box, I think $O(n = 16) = n$, assuming the $PRESENT$ S-box.

Related to item 7: I think we add the time complexities of each component but can approximate the answer as the most time consuming of all terms.

I have looked at a few videos and books on time complexity but most speak in programming languages, and I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above.

One final question:

8. I assume a cipher has a total time complexity. Where can I find the time complexities of a given cipher, especially DES, PRESENT and AES? And is there available time complexities per round of these ciphers?

Answer 1

8. I assume a cipher has a total time complexity. Where can I find the time complexities of a given cipher, especially DES, PRESENT and AES? And is there available time complexities per round of these ciphers?

I did not see, any DES, or similar cryptographic algorithm complexity in the literature. They are, usually, compared by the speed of their software and hardware implementations as encryption/per sec, or hash/per sec as in AES candidates. And if you check the implementation articles and books you will see that, people are using nice tricks to increase the bandwidth.

---

Note that : The memory requirements are also important if the target environment has limited memory, as in blue-tooth devices.

If a chip design is required than the number of transistors etc. plays an important factor to reduce the heat and battery consumption.

Landau

Landau (also “Big-Oh”) notation focuses what is essential and constant factors and in Landau notation, small input size doesn't matter. See this nice blog on Landau notation's advantages and problems.

In Landau, if you want to find the time/space complexity of an algorithm you concentrate on the basic operation. For example; in RSA the basic operation is modular multiplication. You will not concentrate on the counters, memory assignments, if conditions, etc.

What you are trying to in your question is not Landau, you are trying to derive an exact formula as Donald Knuth did in his Volumes. And, by using the exact formulate, placing the timing of each operation to estimate the timing.

On the attack cases, we talk about the complexity of the attack to compare against the brute-force attack and the others. Remember Landu notation hides the constants. As in XLS attack on AES;

The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive search^XLS.

Your Numbers

I'll look at some of your numbers;

1. matrix multiplication (including permutation matrices)

Assuming a square Matrix has input size $n$ then we will have exactly $n^3 \in \mathcal{O(n^3)}$ multiplication with standard matrix multiplication. The fastest is $\mathcal{O(n^{2.373})}$, see Wikipedia article on Matrix Multiplication

2. XOR of bit strings

Theoretically true, but in hardware, we can execute 32-bit at once. X-oring two $m$-bit integers will require $m/32$ operations.

3. expansions, for instance, expanding 64 bits to 128 bits

This really depends on the expansion algorithm, if it is just copy than $\mathcal{O(1)}$

4. bit shifts

If single instruction as in addition in CPUs. $\mathcal{O(1)}$ and Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.

7.combining the operations (as above or other operations)

As, mentioned at the beginning when started to talk about the Landau, you have to choose the basic operation or the dominant operation. If you want to calculate the real-time, a quick question will be in which platform? does it have 128-bit instructions? Does it have rotate instruction or I have to rotate by shifts, masks, and x-or operation?

Answer 2

I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above

You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).

Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.

Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.

Answer 3

You may need to specify your model of computation to make your question answerable.

In some models bitwise XOR is ${\rm O}(n)$ in the number of bits being XORed; it others it can be ${\rm O}(1)$, because all those bits can be processed in parallel. In some models the answer can even depend on the relationship between the number of bits being XORed and the size of the input (or the security parameter). In particular, it seems quite common to assume that basic arithmetic (or bitwise) operations on words of up to $k$ bits can be done in constant time, where $k$ is the security parameter. Asymptotically, this assumption thus implies that XORing $n$-bit strings requires ${\rm O}(n \mathbin/ k)$ time.

Of course, all of those time complexities still differ from each other by only a factor of (up to) $n$. In particular, they're all polynomial in $n$, which is one reason why theoretical work tends to focus on polynomial time as the definition of what's "efficiently computable": it allows us to ignore such "minor" practical details like what the machine word size is or how many parallel cores it has or even whether it's using random-access memory or just a Turing machine -like tape.

Conversely, when comparing the performance of ciphers in practice, big-O asymptotical complexity isn't generally that interesting anyway; what matters more is the actual number of nanoseconds the algorithm requires to encrypt this many bytes on this processor, or the number of gates needed to implement it on this FPGA architecture with this throughput per cycle, etc.