One might argue that calling O(1) just "constant time" in asymptotic complexity theory is click bait itself! Calling O(1) bounded time would have been better terminology, in my mathematical opinion.
Sometimes people actually count individual operations to form a function T(n) depending on the input n (see, for example, Knuth's books). If T(n) is the constant function, then the algorithm takes constant time in a much more literal sense.
(The "constant time" terminology bugged me when I first learned about computational complexity.)
Edit: It seems "constant time" in this paper might actually mean "the running time is uncorrelated with the precise secret value, only its size."
Sometimes people actually count individual operations to form a function T(n) depending on the input n (see, for example, Knuth's books). If T(n) is the constant function, then the algorithm takes constant time in a much more literal sense.
(The "constant time" terminology bugged me when I first learned about computational complexity.)
Edit: It seems "constant time" in this paper might actually mean "the running time is uncorrelated with the precise secret value, only its size."