7 ms·

This isn't correct. Consider an algorithm that special cases powers of two for dividing a number. Both cases take a constant number of steps, although dividin

by uxcn 11y ago

This isn't correct. Consider an algorithm that special cases powers of two for dividing a number. Both cases take a constant number of steps, although dividing by a power of two is fewer. The lower and upper bound differ, but they are both still constant.

Dylan16807 11y ago
asymptotically constant != constant
- uxcn 11y ago
  Asymptotically constant is what we normally talk about in relation to constant time. An algorithm that always runs in n steps with respect to input would be considered constant given the definition you're using, which would at very least be confusing. It's also difficult to talk about constant time outside of an asymptotic context. There are a number of subtle sources for timing variances (e.g. branches, branch mispredicts, cache misses, pipeline stalls, context switches, etc..).
  - Dylan16807 11y ago
    Lower bound equaling upper bound was in addition to O(1), not instead of. In simpler terms, it always runs in exactly k time. It is a difficult problem. It's also a critically important one when you're doing things like cryptography. Maybe we look at different kinds of algorithms, because while I see a lot of worrying about O(n) vs. O(logn) vs. O(nlogn) vs. O(n^2), most of the time when I see people worry about whether something is constant or not, they mean truly constant, not asymptotically. They are worrying about side channels.
    - uxcn 11y ago
      I honestly haven't heard the term constant time used in a context other than asymptotic in computer science, even in relation to side-channels. I think this is the way the majority of people use the term. I worry that trying to use it another way will probably just confuse people, not to say I don't think it isn't a valid concept. In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops?
      - Dylan16807 11y ago
        >I worry that trying to use it another way will probably just confuse people, not to say I don't think it isn't a valid concept. I'll keep that in mind so I don't give wrong impressions in the future. >In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops? It can be extremely difficult to design algorithms so that they spend the same amount of time no matter what the input number is. You can't just use no-op instructions because you don't know how many cycles things will take, no-ops aren't perfect at soaking up extra time, and they don't help at all against something like an attacker on the same EC2 host. Even worse is if you have the OS interrupt mid-computation and wreck the cycle-accurate counters that would tell you how many no-ops to use. You want to design it so that the same instruction sequence happens every time, without branching based on input, without having varied memory accesses based on input. And avoiding other variable length pitfalls like division.

by uxcn 11y ago

Dylan16807 11y ago

asymptotically constant != constant

uxcn 11y ago
Asymptotically constant is what we normally talk about in relation to constant time. An algorithm that always runs in n steps with respect to input would be considered constant given the definition you're using, which would at very least be confusing. It's also difficult to talk about constant time outside of an asymptotic context. There are a number of subtle sources for timing variances (e.g. branches, branch mispredicts, cache misses, pipeline stalls, context switches, etc..).
- Dylan16807 11y ago
  Lower bound equaling upper bound was in addition to O(1), not instead of. In simpler terms, it always runs in exactly k time. It is a difficult problem. It's also a critically important one when you're doing things like cryptography. Maybe we look at different kinds of algorithms, because while I see a lot of worrying about O(n) vs. O(logn) vs. O(nlogn) vs. O(n^2), most of the time when I see people worry about whether something is constant or not, they mean truly constant, not asymptotically. They are worrying about side channels.
  - uxcn 11y ago
    I honestly haven't heard the term constant time used in a context other than asymptotic in computer science, even in relation to side-channels. I think this is the way the majority of people use the term. I worry that trying to use it another way will probably just confuse people, not to say I don't think it isn't a valid concept. In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops?
    - Dylan16807 11y ago
      >I worry that trying to use it another way will probably just confuse people, not to say I don't think it isn't a valid concept. I'll keep that in mind so I don't give wrong impressions in the future. >In relation to side-channel attacks, wouldn't it be sufficient to just pad the difference between upper and lower bounds using no-ops? It can be extremely difficult to design algorithms so that they spend the same amount of time no matter what the input number is. You can't just use no-op instructions because you don't know how many cycles things will take, no-ops aren't perfect at soaking up extra time, and they don't help at all against something like an attacker on the same EC2 host. Even worse is if you have the OS interrupt mid-computation and wreck the cycle-accurate counters that would tell you how many no-ops to use. You want to design it so that the same instruction sequence happens every time, without branching based on input, without having varied memory accesses based on input. And avoiding other variable length pitfalls like division.