News for hackers. Stuff that matters.
Re:Calculating integer factorials in constant time, taking a... by uxcn on Wednesday December 16, 2015 @01:15AM (#10742703)
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..).

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Wednesday December 16, 2015 @11:45AM (#10745424)
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.

Re:Calculating integer factorials in constant time, taking a... by uxcn on Wednesday December 16, 2015 @04:22PM (#10747451)
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?

Re:Calculating integer factorials in constant time, taking a... by Dylan16807 on Wednesday December 16, 2015 @05:53PM (#10748005)
>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.