My assumption: It would seem logical that a cipher that cannot be run in parallel is (in some ways) more secure compared to one which can. Or two ciphers with equal security levels are not truly equal if one of them runs a billion times quicker on a supercomputer.
Is my assumption misguided?
A cipher with $n$-bit security means that there are $2^n$ keys to choose as an encryption key. If we can iterate the key, that is always possible, then we can start to brute-force in parallel. Therefore, this not a good premise.
A cipher can be faster than others like Rijndael was faster than MARS and that is one of the reasons for the choice of Rijndael as AES. We still consider the $n$-bit security as the number of possible keys. When comparing the attacks on the cipher we consider how the attack faster than the brute-force. So we compare the brute-force time - the running time of the one encryption times the number of keys - vs. the time of the attack. The first one is easy but still depends on the platform, the second one can be hard since the attack can depend on many parameters and the measure may not be easy.
For example, in the Improving the Biclique Cryptanalysis of AES article Tao et. al considered the actual computation of running a brute force in all details and compared their attack in the same detail level to compare the success of the attack.
On the other hand, the factoring attacks use Landau notation to express their complexity.
If there is a faster attack we consider this as the encryption algorithm is broken. This still doesn't mean that it is broken practically. Consider AES256 has attacks but they are not feasible. Also, the attack may require too much random memory access that can severe the computation time. Therefore, it is totally dependent on the attack.
Are there any alternative approaches to measuring cipher security that takes into account the computational expense of the algorithm? If not, why not?
We don't consider the computational expense of the algorithm as a weakness, indeed it is greatness. Who doesn't want a fast and secure algorithm instead of slow and secure? Time is Money, area cost is money. In the and we want the cipher to resist all attack to be secure $n$-bit ciphers.
If we consider the security against all possible attacks than this is a huge list of the attacks
- Linear attack security
- Differential attack security
- Algebraic attack security
- The number of required known-plaintext
- The number of required chosen-plaintext
- Multi-target security.
- Possibility of running parallel
- Quantum security
- Memory requirements
Consider the linear and differential attacks on DES. They are faster on the computation requirements but required known-plaintext and chosen-plaintext
for the attacks are so huge that they were not practical. Even today, the fastest attacks implemented on the DES are based on brute-force.
Therefore, it is not an easy job to put a metric. The real metric is the implementation and comparison with the brute-force. If this is not possible, and it is not most of the time, either a complexity analysis is preferred or detailed as in AES attack.