2
$\begingroup$

I am interested to know if work factor means the same thing as time complexity.

Quoting Work Factor : Uncovering keys in cryptosystems

The Work Factor of a cryptosystem is related to its key-length and the working mechanism used (encryption and decryption algorithms). For example, if the brute force attack method is used to break the system (trying all possible combinations of the key), then the work factor is directly proportional to the length of the key.

This sounds awfully similar to what time complexity means to me. I hope to find out if the terminologies are similar.

$\endgroup$
2
$\begingroup$

Work factor is a more appropriate description because time factor is relative to processing power. Time factor, time complexity, computational complexity, and work factor, are used to describe the same thing. When someone says time complexity, they are probably not talking about actual time, but rather computation.

Work factor would be something like "200 trillion iterations of the block cipher", which is constant.

Time factor would be something like "20 years", but if you double the compute power, that is now 10 years. Therefore, time factor is only a good comparison with a fixed level of compute or when you can accurately estimate the amount of computation over a given length of time. Time is easier to explain to someone, and compute power raises at a fairly consistent rate, so using time is acceptable, and thus you can give an expiration date to things like public keys.

That being said, "time complexity" is probably the more common term used to describe computational complexity.

$\endgroup$
  • $\begingroup$ does a statement such as, "the cryptanalysis of x has a work factor of O(n)" make sense? $\endgroup$ – laycat Feb 28 '15 at 18:03
  • $\begingroup$ @laycat yes, that is saying a specific amount of work is required, linear to the size of n. If n was the key, and it was 5 bits, and took 5 million operations, a 20 bit key would take 20 million operations. $\endgroup$ – Richie Frame Feb 28 '15 at 21:53
  • $\begingroup$ does that mean that this 2 statements, "the cryptanalysis of x has a work factor of O(n)" and "the cryptanalysis of x is O(n)" are equivalent? this is how i learn sry T_T $\endgroup$ – laycat Mar 3 '15 at 3:21
  • 2
    $\begingroup$ @laycat "Big O" notation is used to describe not just computation/time complexity, but also memory complexity, or data processed, in relation to "n", which could be the key size, or the amount of available ciphertext/plaintext pairs to an attacker, or something else. So I cannot say for sure that those 2 would be the same, the 2nd one seems like poor wording. $\endgroup$ – Richie Frame Mar 3 '15 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.