[ziedaniel1]

I think you misread slightly.

> All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).

This means that once you have chosen a particular n and c, the time no longer varies. However, if n and c vary, the running time is definitely allowed to vary also (as the formulas n(c + n) and (c + n)(log cn)^2+o(1) clearly do).

[throwawaymath]

No, I didn't misread. You and I are in (apparently violent) agreement. Constant time does not mean that running time cannot vary, in either complexity theory or cryptography. There are misconceptions on both sides here, with regard to what the terminology means in both complexity theory and cryptography.

For precision, I'll start with a good definition[1] for what "constant time" means in cryptography:

> Constant-time implementations are pieces of code that do not leak secret information through timing analysis. This is one of the two main ways to defeat timing attacks: since such attacks exploit differences in execution time that depend on secret elements, make it so that execution time does not depend on secret elements. Or, more precisely, that variations in execution time are not correlated with secret elements: execution time may still vary, but not in a way that can be traced back to any kind of value that you wish to keep secret, in particular (but not only) cryptographic keys.

Secure, constant time cryptographic algorithms need not have unvarying execution time. Now going back to complexity theory, it is also an extraordinarily common misconception that "constant time" means "the algorithm has the same execution time regardless of the size of the input." This is not the case. Big O notation doesn't even care about what always happens, it cares about what happens in the worst case. When we use "constant time" in the O(1) sense of the word, we are not precluding the possibility of an algorithm having variable execution time. Again, for precision, we are simply saying that the execution time (number of operations, etc) has an asymptotic upper bound which is independent of the input. The execution time may vary with the input, and generally speaking it will.

_________________________

1. Thomas Pornin, Why constant time crypto? https://bearssl.org/constanttime.html

[infinity0]

> Constant time does not mean that running time cannot vary, in either complexity theory or cryptography.

Again, overloading of the term "constant time" causes pointless misunderstanding and arguments. Your statement here is wrong.

In complexity theory the term "constant time" does indeed mean the running time is bounded even with unbounded input (e.g. goes to infinity), although it could vary within this bound.

In cryptography the term "constant time" is sometimes used to mean a different concept, that the operation actually takes constant non-varying time, so that an attacker can't exploit this as a side channel to figure out the input values.

The paper seems to be using the latter meaning.

[throwawaymath]

> In cryptography the term "constant time" is sometimes used to mean a different concept, that the operation actually takes constant non-varying time, so that an attacker can't exploit this as a side channel to figure out the input values.

Note that I cited Thomas Pornin for my definition of constant time cryptography, who is a cryptographer in theory and implementation. It is emphatically not necessary for software to run with unvarying execution time in order for it to be "constant time" according to the cryptographic sense of the term. This will be a poor hill for you to die on, but I invite you to provide literature supporting your alternative definition.