5 ms·

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator: The most normal, and fastest, approach is to go through data in the largest chunks the CPU can handle, returning 1 immediately a mismatch is found, and 0 at the end under the assumption that no termination = no mismatch. However, this reveals information about the values compared, as the time it takes to compare reveals where the mismatch is located. For constant time, your goal is to ensure that all data is processed equally regardless of outcome. You do this by effectively making the comparison a-b=c, or a^b=c, where a zero-result means equality. In reality, this would be implemented by XOR'ing the largest chunk the CPU can handle together, and then OR'ing the result with a global value starting at 0, overwriting it. This continues without termination to the very end, where you then simply return the running OR'd counter, which is either 0 for equality, or an arbitrary value for the opposite. Both of course leak the length of the values compared, but the lengths in these cases are commonly known by the adversary, making its protection less relevant.

caf 7y ago
This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).
- arghwhat 7y ago
  > for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1). I would argue that this particular example cannot be considered a case of arbitrarily-sized input: There is only a single meaningful bit of information, which is the single bit accessed. However, if you must, we can expand to clarify that the input is meant to include arbitrary meaningful bits of information that require processing and cannot simply be ignored.
  - repsilat 7y ago
    I think it would be tough to find a suitable definition of "meaningful". When searching for an element in an ordered list, how many items are meaningful? One if it's present, zero otherwise? Always log(n)? Always n? If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful. And it also leaves us with no way to talk about non-constant time algorithms for determining whether a number is odd. Can we say one runs in exponential time when we only talk about "meaningful" bits of input?
    - arghwhat 7y ago
      > I think it would be tough to find a suitable definition of "meaningful". I do not believe it is tough to find a suitable practical definition of meaningful: If a piece of information has no effect on the output of the algorithm, regardless of its value, then it is not meaningful. Examples of meaningful values would be any value in a list being sorted. Non-meaningful values would be any other bit than the lowest bit when determining if a number is even or odd. I find it to be an incredibly trivial definition when considering algorithms. > If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful. I find the case where the full input is not meaningful to be an outlier that does not at all affect how we normally deal with algorithms and bounds. However, when the two do not match, one can start discussing what your input actually is. I would, for example, argue that an even/odd number checker only ever takes a single bit as input. It may consume more due to architectural limitations around bit accesses on modern architectures, but that is not part of the core algorithm.
      - 112233 7y ago
        Ok, let's take as an example a string equality comparision algorithm (strcmp() == 0). What would be your definition of a meaningful input?
        arghwhat 7y ago
        For an equality operation, all bits are meaningful, as there are input configurations in which any bit can lead to a change in output. However, I do see your point in that whether a bit flip in input leads to a change in output depends on the particular input. My counter to that is that it is not the specific input, but the potential inputs that matter.
- fwip 7y ago
  "not all", not "none of".
  - caf 7y ago
    The "not all" is referring to the (executions of the algorithm under) potential inputs.
twic 7y ago
> This is standard terminology within programming and cryptography Within cryptography, yes, but in programming in general, absolutely not. The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.
- arghwhat 7y ago
  > Within cryptography, yes, but in programming in general, absolutely not. I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. The reason for that I do not find this possible with classical computers is that no matter what you do, reading data from memory is an unavoidable variable time process. Do not that arbitrary sized inputs here imply that the input is meaningful and must all be processed. I do not see algorithms that do not process their inputs as candidates here, such as the elsewhere stated example of even/odd test which just read a single bit. I consider an algorithm that only reads a fixed amount of information from its input to be a fixed-input algorithm, regardless of the "full" size of its input. Of course, if you place an upper bound on the input, then you can pad in various ways, or possibly have algorithms whose execution time is inversely proportional to its input size, thus balancing itself. However, placing an upper bound also mean violating the "arbitrary" requirement entirely, thus disqualifying the algorithm. Do note that I'd actually be quite interested if you have examples of such algorithms.
  - razorunreal 7y ago
    So binary search is not logn time because it only reads logn values from the input? To know which parts are not read you basically have to run the algorithm. I find your definition unhelpful.
  - throwawaymath 7y ago
    > I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessing-an-element-in-an-array-take-constant-time https://stackoverflow.com/questions/7297916/why-does-accessi... EDIT: Corrected "search" to "access"
contravariant 7y ago
It might be standard notation, but not only is O(1) misleading as it misrepresents the dependency on the problem size, it is also the wrong symbol as it hides the exact thing it's trying to convey.
throwawaymath 7y ago
> A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator: This is incorrect. The paper explicitly uses "constant time" in the sense of O(1). You can see this listed throughout the paper, in various complexity analyses, beginning from Section 2.
davemp 7y ago
> This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). How about 'consistent time' or 'uniform time' for non-O(1) uses?

caf 7y ago

This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).

arghwhat 7y ago
> for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1). I would argue that this particular example cannot be considered a case of arbitrarily-sized input: There is only a single meaningful bit of information, which is the single bit accessed. However, if you must, we can expand to clarify that the input is meant to include arbitrary meaningful bits of information that require processing and cannot simply be ignored.
- repsilat 7y ago
  I think it would be tough to find a suitable definition of "meaningful". When searching for an element in an ordered list, how many items are meaningful? One if it's present, zero otherwise? Always log(n)? Always n? If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful. And it also leaves us with no way to talk about non-constant time algorithms for determining whether a number is odd. Can we say one runs in exponential time when we only talk about "meaningful" bits of input?
  - arghwhat 7y ago
    > I think it would be tough to find a suitable definition of "meaningful". I do not believe it is tough to find a suitable practical definition of meaningful: If a piece of information has no effect on the output of the algorithm, regardless of its value, then it is not meaningful. Examples of meaningful values would be any value in a list being sorted. Non-meaningful values would be any other bit than the lowest bit when determining if a number is even or odd. I find it to be an incredibly trivial definition when considering algorithms. > If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful. I find the case where the full input is not meaningful to be an outlier that does not at all affect how we normally deal with algorithms and bounds. However, when the two do not match, one can start discussing what your input actually is. I would, for example, argue that an even/odd number checker only ever takes a single bit as input. It may consume more due to architectural limitations around bit accesses on modern architectures, but that is not part of the core algorithm.
    - 112233 7y ago
      Ok, let's take as an example a string equality comparision algorithm (strcmp() == 0). What would be your definition of a meaningful input?
      - arghwhat 7y ago
        For an equality operation, all bits are meaningful, as there are input configurations in which any bit can lead to a change in output. However, I do see your point in that whether a bit flip in input leads to a change in output depends on the particular input. My counter to that is that it is not the specific input, but the potential inputs that matter.
fwip 7y ago
"not all", not "none of".
- caf 7y ago
  The "not all" is referring to the (executions of the algorithm under) potential inputs.

twic 7y ago

> This is standard terminology within programming and cryptography Within cryptography, yes, but in programming in general, absolutely not. The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.

arghwhat 7y ago
> Within cryptography, yes, but in programming in general, absolutely not. I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. The reason for that I do not find this possible with classical computers is that no matter what you do, reading data from memory is an unavoidable variable time process. Do not that arbitrary sized inputs here imply that the input is meaningful and must all be processed. I do not see algorithms that do not process their inputs as candidates here, such as the elsewhere stated example of even/odd test which just read a single bit. I consider an algorithm that only reads a fixed amount of information from its input to be a fixed-input algorithm, regardless of the "full" size of its input. Of course, if you place an upper bound on the input, then you can pad in various ways, or possibly have algorithms whose execution time is inversely proportional to its input size, thus balancing itself. However, placing an upper bound also mean violating the "arbitrary" requirement entirely, thus disqualifying the algorithm. Do note that I'd actually be quite interested if you have examples of such algorithms.
- razorunreal 7y ago
  So binary search is not logn time because it only reads logn values from the input? To know which parts are not read you basically have to run the algorithm. I find your definition unhelpful.
- throwawaymath 7y ago
  > I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessing-an-element-in-an-array-take-constant-time https://stackoverflow.com/questions/7297916/why-does-accessi... EDIT: Corrected "search" to "access"

contravariant 7y ago

It might be standard notation, but not only is O(1) misleading as it misrepresents the dependency on the problem size, it is also the wrong symbol as it hides the exact thing it's trying to convey.

throwawaymath 7y ago

> A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator: This is incorrect. The paper explicitly uses "constant time" in the sense of O(1). You can see this listed throughout the paper, in various complexity analyses, beginning from Section 2.

davemp 7y ago

> This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). How about 'consistent time' or 'uniform time' for non-O(1) uses?