[IncRnd]

> It also refers to time complexity: https://en.wikipedia.org/wiki/Time_complexity#Constant_time this predates the crypto jargon.

Looking at the very first sentence of your link: An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input.

That is true in this case.

Also, from the article here: It shall be noted that the expression "constant-time" is traditional but slightly confusing: constant-time code does not always execute in a constant amount of time; rather, this means that any variation in execution time is uncorrelated with secret information.

You are drawing a distinction that doesn't exist.

[friendlydude12]

There is in fact a distinction between the two usages. I can show it with a simple counter example:

    def matches_secret(a):
        return a == “secret”

The execution time of matches_secret is bounded by a constant and the variation in execution time is correlated with secret information. This precisely means that matches_secret is constant time in the O(1) sense and not in the security sense referenced by the original article.

[IncRnd]

Your example is incorrect. In your example, matches_secret's runtime depends on the input. You should reread the link that you posted.

An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input.

[friendlydude12]

There exists a constant, K, such that T(n) < K always holds true regardless of the input length. K is proportional to the length of the constant string “secret” and has no dependence on the input. Thus, matches_secret is O(1).

Furthermore, even though T(n) is bounded by a constant, it is not constant itself and its runtime is proportional to the amount of prefix characters the input has in common with the secret. This makes it not “constant time” in the crypto sense and it is susceptible to timing attacks.

The existence of a function that is constant time in the O(1) sense but not in the crypto sense proves that they are distinct concepts.

[IncRnd]

Fair point.