What is the time complexity of the basic components of a symmetric cipher? 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:


matrix multiplication (including permutation matrices)
XOR of bit strings
expansions, for instance expanding 64 bits to 128 bits
bit shifts
permutations using a P-box (say the one in PRESENT)
substitutions using an S-box (again, say the one in PRESENT)
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:


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 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.